怎么办饱和加用C？(How to do saturating addition in C?)

什么是最好的（最清洁，最高效的）的方式来编写C饱和加？

函数或宏应增加两个无符号输入（需要16位和32位版本），并返回所有位一个（0xF​​FFF或0xFFFFFFFF的），如果总和溢出。

目标是x86和使用gcc（4.1.2），ARM和Visual Studio（用于模拟而已，所以回退的实现是OK那里）。

Answer 1:

你可能想在这里可移植的C代码，编译器将变成正确的ARM汇编。 ARM具有条件的动作，而这些可以在溢出条件。 然后，该算法变得添加，以及目的地有条件地设置为无符号（-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铛3.7 -O3输出adds32 ：比其他任何答案显著更好：

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

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

    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  @

Answer 2:

In plain 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;} 

which is almost macro-ized and directly conveys the meaning.

Answer 3:

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

Answer 4:

在ARM你可能已经饱和算术内置。 所述的ARMv5 DSP的扩展可以饱和寄存器任何比特长度。 同样在ARM饱和度通常是便宜的，因为你可以EXCUTE大部分指令的条件。

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

您可以通过改变signmask不变，并在这样的底部的转变得到了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你也想改变signmask恒定的，因为ARM无法加载所有可能的32个常数，在一个周期。

编辑：并行版本比直截了当的方法最有可能较慢，但他们更快，如果你在某一时刻饱和多个值。

Answer 5:

If you care about performance, you really want to do this sort of stuff in SIMD, where x86 has native saturating arithmetic.

Because of this lack of saturating arithmetic in scalar math, one can get cases in which operations done on 4-variable-wide SIMD is more than 4 times faster than the equivalent C (and correspondingly true with 8-variable-wide SIMD):

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

Answer 6:

零分支机构解决方案：

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 ）。

在86 ASM（AT＆T的语法， a和b在eax和ebx ，导致eax ）：

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

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

Answer 7:

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

编辑：既然你已经发布你的版本，我不知道我的是任何清洁剂/更好/更高效/更studly。

Answer 8:

我不知道这是不是Skizz的解决方案快（通常配置文件），但这里的一个替代否分支总成解决方案。 请注意，这需要有条件移动（CMOV）指令，这我不知道可以用你的目标。

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

Answer 9:

我们使用当前的实现是：

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

Answer 10:

我想，对于x86的最好方法是使用内联汇编除了后检查溢出标志。 就像是：

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

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

Answer 11:

最佳的性能通常会涉及到内联汇编（象有些国家已注明）。

但是，对于便携式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)))

我离开版本“无符号长”和“无符号长长”作为练习读者。 ;-)

Answer 12:

以防万一有人想知道的实现，而无需使用2的补32位整数分支。

警告！ 此代码使用未定义操作：“通过右移-1”，因此利用了的属性英特尔奔腾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);
 }

据了解，以我最好的实现

Answer 13:

使用C ++，你可以写的Remo.D的解决方案更加灵活的变体：

template<typename T>
T sadd(T first, T second)
{
    static_assert(std::is_integral<T>::value, "sadd is not defined for non-integral types");
    return first > std::numeric_limits<T>::max() - second ? std::numeric_limits<T>::max() : first + second;
}

这可以很容易地转换到C -使用所定义的限制limits.h 。 还请注意， 固定宽度的整数类型可能没有您的系统上。

Answer 14:

到分支86自由汇编溶液另一种方法是（AT＆T的语法，a和b在EAX EBX和，导致EAX）：

add %eax,%ebx
sbb $0,%ebx

Answer 15:

//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;\
}\
})

我做了一个快速测试，似乎工作，但没有广泛撞坏它呢！ 这适用于32位有符号。 OP：在网页上使用的编辑器不会让我张贴即它不理解非缩语法等宏！

Answer 16:

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);
}

此实现不使用控制流，比比操作符（ == ， != ）和?:运营商。 它只是使用位运算符和逻辑运算符。

Answer 17:

饱和算术不是C标准，但通常通过编译器内在实现的，所以最有效的方法将是不干净的。 你必须选择正确的方法添加的#ifdef块。 MSalters的答案是最快的x86架构。 对于ARM你需要使用__qadd16 _arm_qadd16（微软的Visual Studio）的功能（ARM编译器），16位版本和__qadd 32位版本。 它会自动转换为一个ARM指令。

链接：

__qadd16 的Http：//infaochenter.aarmkcom/help/indekskjsp TOPIK = / com.aarmkdockdui049lc / CJAICDDFkhtml

_arm_qadd16 https://msdn.microsoft.com/en-US/library/hh875058.aspx

__qadd http://infocenter.arm.com/help/index.jsp?topic=/com.arm.doc.dui0472m/chr1359125002575.html

文章来源: How to do saturating addition in C?