Cで飽和加算を書くための最良の（最もクリーンで効率的な）方法は何ですか?
関数またはマクロは、2 つの符号なし入力 (16 ビット バージョンと 32 ビット バージョンの両方が必要) を追加し、合計がオーバーフローした場合はすべてビット 1 (0xFFFF または 0xFFFFFFFF) を返す必要があります。
ターゲットは、gcc (4.1.2) および Visual Studio を使用する x86 および ARM です (シミュレーションのみのため、フォールバックの実装はそこで OK です)。
おそらく、コンパイラが適切な ARM アセンブリに変換する移植可能な C コードが必要になるでしょう。ARM には条件付きの移動があり、これらはオーバーフローの条件付きにすることができます。アルゴリズムは次のようになります。オーバーフローが検出された場合、宛先を追加し、条件付きで unsigned(-1) に設定します。
uint16_t add16(uint16_t a, uint16_t b)
{
uint16_t c = a + b;
if (c < a) /* Can only happen due to overflow */
c = -1;
return c;
}
これは、オーバーフローを検出するために別の計算に依存するのではなく、オーバーフローを修正するという点で、他のアルゴリズムとは異なることに注意してください。
x86-64 clang 3.7 -O3 adds32 の出力:他のどの回答よりも大幅に優れています:
add edi, esi
mov eax, -1
cmovae eax, edi
ret
ARMv7: gcc 4.8 -O3 -mcpu=cortex-a15 -fverbose-asmadds32 の出力:
adds r0, r0, r1 @ c, a, b
it cs
movcs r0, #-1 @ conditional-move
bx lr
16bit: ARM の unsigned-saturating add 命令をまだ使用していない ( UADD16)
add r1, r1, r0 @ tmp114, a
movw r3, #65535 @ tmp116,
uxth r1, r1 @ c, tmp114
cmp r0, r1 @ a, c
ite ls @
movls r0, r1 @,, c
movhi r0, r3 @,, tmp116
bx lr @
プレーンCで：
uint16_t sadd16(uint16_t a, uint16_t b) {
return (a > 0xFFFF - b) ? 0xFFFF : a + b;
}
uint32_t sadd32(uint32_t a, uint32_t b) {
return (a > 0xFFFFFFFF - b) ? 0xFFFFFFFF : a + b;
}
ほぼマクロ化され、意味をダイレクトに伝える。
条件付きジャンプのない IA32 の場合:
uint32_t sadd32(uint32_t a, uint32_t b)
{
#if defined IA32
__asm
{
mov eax,a
xor edx,edx
add eax,b
setnc dl
dec edx
or eax,edx
}
#elif defined ARM
// ARM code
#else
// non-IA32/ARM way, copy from above
#endif
}
ARM では、すでに飽和演算が組み込まれている場合があります。ARMv5 DSP 拡張機能は、レジスタを任意のビット長に飽和させることができます。また、ほとんどの命令を条件付きで実行できるため、ARM 飽和は通常安価です。
ARMv6 では、32 ビットとパックされた数に対して、飽和した加算、減算、およびその他すべてのものさえあります。
x86 では、MMX または SSE を介して飽和演算を取得します。
これにはすべてアセンブラーが必要なので、あなたが求めているものではありません。
飽和演算を行うための C トリックもあります。この小さなコードは、dword の 4 バイトに対して飽和加算を行います。これは、32 個の半加算器を並列に計算するという考えに基づいています。たとえば、キャリー オーバーフローなしで数値を加算します。
これが最初に行われます。次に、キャリーが計算され、追加され、追加がオーバーフローする場合はマスクに置き換えられます。
uint32_t SatAddUnsigned8(uint32_t x, uint32_t y)
{
uint32_t signmask = 0x80808080;
uint32_t t0 = (y ^ x) & signmask;
uint32_t t1 = (y & x) & signmask;
x &= ~signmask;
y &= ~signmask;
x += y;
t1 |= t0 & x;
t1 = (t1 << 1) - (t1 >> 7);
return (x ^ t0) | t1;
}
次のように、符号マスク定数と下部のシフトを変更することで、16 ビット (または任意の種類のビット フィールド) で同じ結果を得ることができます。
uint32_t SatAddUnsigned16(uint32_t x, uint32_t y)
{
uint32_t signmask = 0x80008000;
uint32_t t0 = (y ^ x) & signmask;
uint32_t t1 = (y & x) & signmask;
x &= ~signmask;
y &= ~signmask;
x += y;
t1 |= t0 & x;
t1 = (t1 << 1) - (t1 >> 15);
return (x ^ t0) | t1;
}
uint32_t SatAddUnsigned32 (uint32_t x, uint32_t y)
{
uint32_t signmask = 0x80000000;
uint32_t t0 = (y ^ x) & signmask;
uint32_t t1 = (y & x) & signmask;
x &= ~signmask;
y &= ~signmask;
x += y;
t1 |= t0 & x;
t1 = (t1 << 1) - (t1 >> 31);
return (x ^ t0) | t1;
}
上記のコードは、16 ビット値と 32 ビット値に対して同じことを行います。
関数が複数の値を並行して追加して飽和させる機能が必要ない場合は、必要なビットをマスクするだけです。ARM では、可能なすべての 32 ビット定数を 1 サイクルでロードできないため、signmask 定数も変更する必要があります。
編集:並列バージョンは、単純な方法よりも遅い可能性が高いですが、一度に複数の値を飽和させる必要がある場合は高速です。
ゼロ ブランチ ソリューション:
uint32_t sadd32(uint32_t a, uint32_t b)
{
uint64_t s = (uint64_t)a+b;
return -(s>>32) | (uint32_t)s;
}
優れたコンパイラはこれを最適化して、実際の 64 ビット演算s>>32を行わないようにします ( は単なるキャリー フラグで、-(s>>32)は の結果ですsbb %eax,%eax)。
x86 asm (AT&T 構文、aおよびbとeaxのebx結果はeax):
add %eax,%ebx
sbb %eax,%eax
or %ebx,%eax
8 ビット バージョンと 16 ビット バージョンは明らかです。署名されたバージョンでは、もう少し作業が必要になる場合があります。
パフォーマンスに関心がある場合は、x86 がネイティブの飽和演算を備えている SIMD でこの種の処理を実行する必要があります。
スカラー演算には飽和演算がないため、4 変数幅の SIMD で実行される演算が、同等の C よりも 4 倍以上高速になる場合があります (8 変数幅の SIMD でも同様です)。
sub8x8_dct8_c: 1332 clocks
sub8x8_dct8_mmx: 182 clocks
sub8x8_dct8_sse2: 127 clocks
uint32_t saturate_add32(uint32_t a, uint32_t b)
{
uint32_t sum = a + b;
if ((sum < a) || (sum < b))
return ~((uint32_t)0);
else
return sum;
} /* saturate_add32 */
uint16_t saturate_add16(uint16_t a, uint16_t b)
{
uint16_t sum = a + b;
if ((sum < a) || (sum < b))
return ~((uint16_t)0);
else
return sum;
} /* saturate_add16 */
編集：バージョンを投稿したので、私のバージョンがよりクリーン/より良い/より効率的/より研究的であるかどうかはわかりません。
現在使用している実装は次のとおりです。
#define sadd16(a, b) (uint16_t)( ((uint32_t)(a)+(uint32_t)(b)) > 0xffff ? 0xffff : ((a)+(b)))
#define sadd32(a, b) (uint32_t)( ((uint64_t)(a)+(uint64_t)(b)) > 0xffffffff ? 0xffffffff : ((a)+(b)))
これが Skizz のソリューション (常にプロファイル) よりも高速かどうかはわかりませんが、代替のブランチなしアセンブリ ソリューションを次に示します。これには条件付き移動 (CMOV) 命令が必要であることに注意してください。これは、ターゲットで使用できるかどうかはわかりません。
uint32_t sadd32(uint32_t a, uint32_t b)
{
__asm
{
movl eax, a
addl eax, b
movl edx, 0xffffffff
cmovc eax, edx
}
}
誰かが 2 の補数 32 ビット整数を使用して分岐せずに実装を知りたい場合に備えて。
警告！このコードは未定義の演算「-1 だけ右にシフトする」を使用しているため、Intel Pentium SAL 命令のプロパティを利用してカウント オペランドを 5 ビットにマスクしています。
int32_t sadd(int32_t a, int32_t b){
int32_t sum = a+b;
int32_t overflow = ((a^sum)&(b^sum))>>31;
return (overflow<<31)^(sum>>overflow);
}
それは私が知っている最高の実装です
通常、最高のパフォーマンスを得るには、インライン アセンブリが必要です (既に述べたように)。
しかし、移植可能な C の場合、これらの関数は 1 つの比較のみを含み、型キャストは行いません (したがって、私は最適だと思います)。
unsigned saturate_add_uint(unsigned x, unsigned y)
{
if (y > UINT_MAX - x) return UINT_MAX;
return x + y;
}
unsigned short saturate_add_ushort(unsigned short x, unsigned short y)
{
if (y > USHRT_MAX - x) return USHRT_MAX;
return x + y;
}
マクロとして、それらは次のようになります。
SATURATE_ADD_UINT(x, y) (((y)>UINT_MAX-(x)) ? UINT_MAX : ((x)+(y)))
SATURATE_ADD_USHORT(x, y) (((y)>SHRT_MAX-(x)) ? USHRT_MAX : ((x)+(y)))
読者への演習として、「unsigned long」と「unsigned long long」のバージョンを残しておきます。;-)
x86 の場合は、追加後にインライン アセンブラを使用してオーバーフロー フラグをチェックするのが最善の方法だと思います。何かのようなもの：
add eax, ebx
jno @@1
or eax, 0FFFFFFFFh
@@1:
.......
移植性は高くありませんが、IMHO が最も効率的な方法です。
int saturating_add(int x, int y)
{
int w = sizeof(int) << 3;
int msb = 1 << (w-1);
int s = x + y;
int sign_x = msb & x;
int sign_y = msb & y;
int sign_s = msb & s;
int nflow = sign_x && sign_y && !sign_s;
int pflow = !sign_x && !sign_y && sign_s;
int nmask = (~!nflow + 1);
int pmask = (~!pflow + 1);
return (nmask & ((pmask & s) | (~pmask & ~msb))) | (~nmask & msb);
}
==この実装では、制御フロー、campare 演算子 ( 、!=) および演算子は使用されません?:。ビット単位の演算子と論理演算子を使用するだけです。
//function-like macro to add signed vals,
//then test for overlow and clamp to max if required
#define SATURATE_ADD(a,b,val) ( {\
if( (a>=0) && (b>=0) )\
{\
val = a + b;\
if (val < 0) {val=0x7fffffff;}\
}\
else if( (a<=0) && (b<=0) )\
{\
val = a + b;\
if (val > 0) {val=-1*0x7fffffff;}\
}\
else\
{\
val = a + b;\
}\
})
簡単なテストを行ったところ、動作しているように見えますが、まだ広範囲に渡っていません! これは SIGNED 32 ビットで動作します。op : Web ページで使用されているエディターでは、マクロを投稿できません。つまり、インデントされていない構文を理解していないなどです。