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

函数或者宏应添加两个无符号输入(同时需要16和32位版本)，如果总和溢出，则返回全1(0xFFFF或者0xFFFFFFFF)。

目标是使用gcc(4.1.2)和Visual Studio的x86和ARM(仅用于模拟，因此可以在此处进行后备实现)。

解决方案

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 */

<B>编辑：既然我们已经发布了版本，则不确定我的版本是否更干净/更好/更高效/更强大。

我们正在使用的当前实现是：

#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)))

我想，x86的最佳方法是使用内联汇编器在添加后检查溢出标志。就像是：

add eax, ebx
jno @@1
or eax, 0FFFFFFFFh
@@1:
.......

它不是很便携，但是恕我直言是最有效的方法。

在ARM中，我们可能已经内置了饱和算法。 ARMv5 DSP扩展可以将寄存器饱和到任何位长。同样，对于ARM饱和通常很便宜，因为我们可以有条件地执行大多数指令。

ARMv6甚至具有饱和的加，减和其他所有东西(32位和打包数字)。

在x86上，我们可以通过MMX或者SSE获得饱和算术。

所有这些都需要汇编程序，所以这不是我们所需要的。

也有C技巧来做饱和算术。这个小代码对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位常量。

编辑：并行版本最有可能比直接方法慢，但是如果我们一次要饱和多个值，则它们会更快。

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

我不确定这是否快于Skizz的解决方案(始终使用概要文件)，但这是另一种无分支装配解决方案。请注意，这需要条件移动(CMOV)指令，我不确定目标上是否可以使用该指令。

uint32_t sadd32(uint32_t a, uint32_t b)
{
    __asm
    {
        movl eax, a
        addl eax, b
        movl edx, 0xffffffff
        cmovc eax, edx
    }
}

在纯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;}

这几乎是宏观的，并直接传达了含义。

如果我们关心性能，那么我们真的想在SIMD中做这种事情，其中​​x86具有本机饱和算法。

由于标量数学中缺乏饱和算法，因此可以得出以下情况：在4变量宽SIMD上进行的运算比等效C快4倍以上(并且在8变量宽SIMD上也是如此)：

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

最好的性能通常涉及内联汇编(如某些人已经指出的那样)。

但是对于可移植的C，这些功能仅涉及一次比较，而没有类型转换(因此，我认为是最佳的)：

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"的版本留给读者练习。 ;-)

我们可能在这里需要可移植的C代码，编译器会将其转变为正确的ARM汇编。 ARM有条件移动，而这些可能是有条件溢出的。然后，该算法将成为add，并在检测到溢出时有条件地将目标设置为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-add32的O3输出：明显优于其他任何答案：

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

ARMv7：为adds32的gcc 4.8 -O3 -mcpu = cortex-a15 -fverbose-asm输出：

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

16位：仍不使用ARM的无符号饱和加法指令(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  @

零分支解决方案：

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语法中，" eax"和" ebx"中的" a"和" b"，导致" eax")：

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

8位和16位版本应该很明显。签名版本可能需要更多工作。