Cで飽和++

飽和 #とは

詳細は Saturation arithmetic を読むと良いけど、ようは signed char なら 126を++すると127になってほしいけど、127を++すると127のままになってほしいわけですよ。signedの整数はオーバーフローの挙動が未定義だしね。そういうことにならないようにしたい。

で、かつ、まあ、速く動いて欲しいわけ。わざわざCで書いてるんだからな。

解法

ものすごい最近のgccの場合

__GNUC__ >= 7 から組み込み関数 __builtin_add_overflow_p が増えているので、これで一発。すばらしい。

#define saturated_inc(x) __builtin_add_overflow_p(x, 1, x) ? x : ++x

ちなみにじゃあ実際の出力はどうなるかというと、これでたとえば以下のような関数を作ってコンパイルしてみると、

signed long long
func(signed long long x)
{
    return saturated_inc(x);
}

出力はこう。

% gcc-trunk -O3 -S -o- tmp.c
        .text
        .align 4,0x90
        .globl _func
_func:
LFB1:
        movq    %rdi, %rax
        addq    $1, %rax
        jo      L7
        ret
L7:
        movq    %rdi, %rax
        ret
LFE1:
(以下略)

1足してみてからオーバーフローフラグで返すものを変える、完璧に最短最速のコードが生成されてますね。素晴らしい。gcc7早く出て。

結構最近のgccとか結構最近のclangの場合

__GNUC__ >= 5 から組み込み関数 __builtin_add_overflow が増えている。これは上と違って実際に足し算を実行してしまうのでテンポラリの変数が必要なのがやや面倒だが、まあ式文を使えば回避できるから問題ない(この導入した変数はもちろん最適化すれば消える)。

#define saturated_inc(x) ({__typeof__(x) y; __builtin_add_overflow(x, 1, &y) ? x : ++x; })

これでたとえば以下のような関数を作ってコンパイルしてみると、

signed long long
func(signed long long x)
{
    return saturated_inc(x);
}

gccだとこうなって

% gcc-6 -O3 -S -o- tmp.c
        .text
        .align 4,0x90
        .globl _func
_func:
LFB1:
        movq    %rdi, %rax
        addq    $1, %rax
        jo      L7
        ret
L7:
        movq    %rdi, %rax
        ret
LFE1:
(以下略)

clangだとこうなる

% clang-3.8 -O3 -S -o- tmp.c
        .section        __TEXT,__text,regular,pure_instructions
        .macosx_version_min 10, 11
        .globl  _func
        .align  4, 0x90
_func:                                  ## @func
        .cfi_startproc
## BB#0:                                ## %entry
        pushq   %rbp
Ltmp0:
        .cfi_def_cfa_offset 16
Ltmp1:
        .cfi_offset %rbp, -16
        movq    %rsp, %rbp
Ltmp2:
        .cfi_def_cfa_register %rbp
        movq    %rdi, %rax
        incq    %rax
        seto    %al
        movzbl  %al, %eax
        xorq    $1, %rax
        addq    %rdi, %rax
        popq    %rbp
        retq
        .cfi_endproc


.subsections_via_symbols

gccは上の7系の時と同じで素直な感じだけど、clangトリッキーなコード吐いてますね。incしてsetoからのmobzxで%eaxにオーバーフローしたかが0/1で入ってくるから、それをxorでひっくり返してからaddでもとの引数に足し込む。たしかに。たしかに正しい。これ多分ジャンプ嫌ってるんだろうな。gccだとjoしてるけど、これのコストのほうが大きいという判断なんだと思う。

ここ数年のCコンパイラの場合

ここまでのやつはtype-neutralですべてのsigned/unsignedな整数に対して単一のマクロでいけたわけだが、__builtin_add_overflowが存在しない非gcc系のコンパイラとかclangだけどちょい古いとかだとどうするか。

まあ_Genericという話になるわけだけど、_Genericには罠があるので要注意で、_Genericの引数に無思慮にcharとか書いちゃうとintにtype promoteされる可能性がある(gccはする)ので、ポインタにひねらないといけない。罠い。。。

#define saturated_inc2(x, y) (((x) < (y)) ? ++ (x) : (x))
#define saturated_inc(x) _Generic( &(x),                \
          int8_t*: saturated_inc2((x),   INT8_MAX),     \
         uint8_t*: saturated_inc2((x),  UINT8_MAX),     \
         int16_t*: saturated_inc2((x),  INT16_MAX),     \
        uint16_t*: saturated_inc2((x), UINT16_MAX),     \
         int32_t*: saturated_inc2((x),  INT32_MAX),     \
        uint32_t*: saturated_inc2((x), UINT32_MAX),     \
         int64_t*: saturated_inc2((x),  INT64_MAX),     \
        uint64_t*: saturated_inc2((x), UINT64_MAX))

で、以下のような関数を作ってコンパイルしてみると、

signed long long
func(signed long long x)
{
    return saturated_inc(x);
}

gccだとこうなって

% gcc-4.9 -O3 -S -o- tmp.c
        .section __TEXT,__text_cold,regular,pure_instructions
LCOLDB0:
        .text
LHOTB0:
        .align 4,0x90
        .globl _func
_func:
LFB1:
        movabsq $9223372036854775807, %rax
        cmpq    %rax, %rdi
        setne   %al
        movzbl  %al, %eax
        addq    %rdi, %rax
        ret
LFE1:
(以下略)

clangだとこうなる

% clang-3.5 -O3 -S -o- tmp.c
        .section        __TEXT,__text,regular,pure_instructions
        .macosx_version_min 10, 11
        .globl  _func
        .align  4, 0x90
_func:                                  ## @func
        .cfi_startproc
## BB#0:                                ## %entry
        pushq   %rbp
Ltmp0:
        .cfi_def_cfa_offset 16
Ltmp1:
        .cfi_offset %rbp, -16
        movq    %rsp, %rbp
Ltmp2:
        .cfi_def_cfa_register %rbp
        leaq    1(%rdi), %rax
        movabsq $9223372036854775807, %rcx ## imm = 0x7FFFFFFFFFFFFFFF
        cmpq    %rcx, %rdi
        cmoveq  %rdi, %rax
        popq    %rbp
        retq
        .cfi_endproc


.subsections_via_symbols

gccのやつはx < y ? ++x : xをx += (x < y ? 1 : 0)に変換してると解釈するとまあわりとわかる感じ。clangは++x部分を先頭のleaで投機的に作成してある。多分どうせCPUのinteger pipeline余ってんだろ? っていう前提か。

結構古いけどgccの場合

そろそろ「コンパイラ更新しろよ」という感じだが、gccならC11非対応の超古いやつでもなんとかなる。

#define maxof(x) \
    __builtin_choose_expr(__builtin_types_compatible_p(x,   int8_t),   INT8_MAX, \
    __builtin_choose_expr(__builtin_types_compatible_p(x,  uint8_t),  UINT8_MAX, \
    __builtin_choose_expr(__builtin_types_compatible_p(x,  int16_t),  INT16_MAX, \
    __builtin_choose_expr(__builtin_types_compatible_p(x, uint16_t), UINT16_MAX, \
    __builtin_choose_expr(__builtin_types_compatible_p(x,  int32_t),  INT32_MAX, \
    __builtin_choose_expr(__builtin_types_compatible_p(x, uint32_t), UINT32_MAX, \
    __builtin_choose_expr(__builtin_types_compatible_p(x,  int64_t),  INT64_MAX, \
    __builtin_choose_expr(__builtin_types_compatible_p(x, uint64_t), UINT64_MAX, \
    __builtin_trap()))))))))
#define saturated_inc(x) (((x) < maxof(typeof(x))) ? ++ (x) : (x))

これはマクロが生成するコードが上のC11の時と同じなので出力も同じ。__typeof__はかなり古くからあるのでgccならかなり昔のでも救済措置があるといえる。

__typeof__もないけどC++の場合

C++ならテンプレートメタプログラミングで普通に書ける。

#include <limits>
template<typename T> inline auto
saturated_inc(T& x)
{
    auto const max = std::numeric_limits<T>::max();

    return (x < max) ? ++x : x;
}

ぶっちゃけ一番読みやすい。これを以下のような関数を作ってコンパイルしてみると、

signed long long
func(signed long long x)
{
    return saturated_inc(x);
}

g++だとこうなって

% g++-trunk -std=c++1z -O3 -S -o- tmp.cpp
        .text
        .align 4,0x90
        .globl __Z4funcx
__Z4funcx:
LFB172:
        movabsq $9223372036854775807, %rax
        cmpq    %rax, %rdi
        setne   %al
        movzbl  %al, %eax
        addq    %rdi, %rax
        ret
LFE172:
(以下略)

clang++だとこう。

% clang++-3.8 -std=c++1z -O3 -S -o- tmp.cpp
        .section        __TEXT,__text,regular,pure_instructions
        .macosx_version_min 10, 11
        .globl  __Z4funcx
        .align  4, 0x90
__Z4funcx:                              ## @_Z4funcx
        .cfi_startproc
## BB#0:                                ## %entry
        pushq   %rbp
Ltmp0:
        .cfi_def_cfa_offset 16
Ltmp1:
        .cfi_offset %rbp, -16
        movq    %rsp, %rbp
Ltmp2:
        .cfi_def_cfa_register %rbp
        leaq    1(%rdi), %rax
        movabsq $9223372036854775807, %rcx ## imm = 0x7FFFFFFFFFFFFFFF
        cmpq    %rcx, %rdi
        cmoveq  %rdi, %rax
        popq    %rbp
        retq
        .cfi_endproc


.subsections_via_symbols

ようはC11の時と一緒。

それすらも選択肢として取れない場合

厳しいと言わざるをえない。多分これまでのように一つのマクロですべての型をカバーするのはできないと思う。ただunsignedを捨てて signedに限定 すると、以下の逃げ方があり得る。

#define maxof(x) (\
    (sizeof(x) == sizeof( int8_t)) ?  INT8_MAX : \
    (sizeof(x) == sizeof(int16_t)) ? INT16_MAX : \
    (sizeof(x) == sizeof(int32_t)) ? INT32_MAX : \
    (sizeof(x) == sizeof(int64_t)) ? INT64_MAX : \
    INTMAX_MAX)
#define saturated_inc(x) ((x) < maxof(x) ? ++ (x) : (x))

これは以下の理由によりダメの中でも一番マシな挙動をする

• unsignedはオーバーフローしたときの挙動が決まっているがsignedは未定義なので、signedには積極的にオーバーフローから救う理由がある。
• unsignedな型の変数を突っ込むと上の1bitを使わない感じとして動く。もちろん残念な動きだが、とはいえオーバーフローは発生しない。するよりマシである。

まとめ

• gcc7が最強
• gcc5以降とclang3.8以降は最強にほぼ近い
• それ以前のgccは読みづらいながらなんか方法がある
• C11ならまあOK
• C++はC11と同じコードを吐く上にC11よりかなり読みやすい
• 以上のどれにも該当しない人は相当厳しい