如何在C中进行饱和添加？

在C中编写饱和加法的最佳(最干净,最有效)方法是什么？

函数或宏应添加两个无符号输入(需要16位和32位版本),如果总和溢出,则返回所有位 - 一(0xFFFF或0xFFFFFFFF).

目标是x86和ARM使用gcc(4.1.2)和Visual Studio(仅用于模拟,因此可以使用后备实现).

在平原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;} 

这几乎是宏观的,直接传达了意义.

您可能需要可移植的C代码,编译器将转换为适当的ARM程序集.ARM有条件移动,这些可以以溢出为条件.然后该算法变为add,并且如果检测到溢出,则有条件地将目标设置为unsigned(-1).

uint16_t add16(uint16_t a, uint16_t b)
{
  uint16_t c = a + b;
  if (c

请注意,这与其他算法的不同之处在于它可以纠正溢出,而不是依赖于另一个计算来检测溢出.

x86-64 clang 3.7 -O3输出为adds32:明显优于其他任何答案:

    add     edi, esi
    mov     eax, -1
    cmovae  eax, edi
    ret


ARMv7:Cadds32的输出:

    adds    r0, r0, r1      @ c, a, b
    it      cs
    movcs   r0, #-1         @ conditional-move
    bx      lr


16bit:仍然不使用ARM的unsigned-saturating add指令(gcc 4.8 -O3 -mcpu=cortex-a15 -fverbose-asm)

    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  @

        
这会在带有clang（`mov eax，-1` /`add` /`cmovnc`）和[与gcc大致相同]（http://goo.gl/fQ2YI1）的x86上生成最佳代码。答案。这是唯一让gcc使用添加结果的标志结果的方法，而不是之后再进行其他测试（DGentry的答案除外，但gcc并未意识到这两个测试是相同的）。因此，可以说这是gcc“了解”正在发生的事情的唯一方法。甚至内联汇编也无法在x86上做得更好：编译器知道您的汇编正在发生什么，因此它知道它是关联的，并可以选择销毁哪个reg。 

3> Skizz..：
在没有条件跳转的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
}

        
如果问题想要可移植性,它不应该指定x86和ARM ;-) 
该函数仍然是可移植的 - 一旦elif和其他情况被填写.可移植代码并不意味着您无法针对特定平台进行优化. 
由YumeYao提出的编辑(我没有通过,因为它改变了答案的性质):3个指令(xor reg,reg; setne reg; dec reg;)可以用一个更有效的指令替换(sbb) REG,REG). 
有点烂：首先是因为它是MSVC内联汇编，所以输入/输出必须通过内存。（或者，如果此带有eax中的值的不返回语句起作用，则该函数本身无法内联。无论如何，输入都必须经过内存）。其次，因为`cmov`更好：关键路径更短，因为`mov eax，-1'不在关键路径上，这与`sbb`不同。 

4> Nils Pipenbr..：
在ARM中,您可能已经内置了饱和算术.ARMv5 DSP扩展可以使寄存器饱和到任何位长.同样在ARM饱和度上通常很便宜,因为你可以有条件地执行大多数指令.

ARMv6甚至具有饱和的加法,减法和32位和打包数字的所有其他东西.

在x86上,您可以通过MMX或SSE获得饱和算术. 

所有这些都需要汇编程序,所以这不是你要求的.

还有C-tricks来做饱和算术.这个小代码对dword的四个字节进行了饱和加法.它基于并行计算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上,您还希望更改符号掩码常量,因为ARM无法在单个循环中加载所有可能的32位常量.

编辑:并行版本很可能比直接版本慢,但如果你必须一次饱和多个值,它们会更快.

        

5> Dark Shikari..：
如果你关心性能,你真的想在SIMD中做这种事情,其中​​x86具有原生饱和算法.

由于缺乏在标量数学饱和算法的,可以得到其中的4变量宽SIMD进行的操作是个案更超过4倍的速度比同等的C(与8-可变宽SIMD相应真):

sub8x8_dct8_c: 1332 clocks
sub8x8_dct8_mmx: 182 clocks
sub8x8_dct8_sse2: 127 clocks

        
在您一次只操作一个变量的情况下,是否仍然更快地使用SSE指令？ 

6> R....：
零分支解决方案:

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以及bin eax和ebx,结果eax):

add %eax,%ebx
sbb %eax,%eax
or %ebx,%eax


8位和16位版本应该是显而易见的.签名版本可能需要更多工作.

        
您希望编译器会发现这一点，但事实并非如此。clang / gcc / icc都对[MSalter的答案以外的所有内容]（http://goo.gl/lcrN1X）做废话。您的编译为`lea eax，[rdi + rsi] / mov edx，edi / mov ecx，esi / add rdx，rcx / shr rdx，32 / neg edx /或eax，edx` 

7> DGentry..：
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 */


编辑:现在你已经发布了你的版本,我不确定我的是更清洁/更好/更有效/更多精彩.