如何在C中进行饱和加法?

您可能需要在这里使用可移植的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 clang 3.7 -O3 output for adds32 :明显优于其他答案:

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

ARMv7: gcc 4.8 -O3 -mcpu=cortex-a15 -fverbose-asm output for 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  @

普通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中,您可能已经内置了饱和算术。ARMv5DSP扩展可以将寄存器饱和到任何位长度。另外,手臂饱和通常是便宜的,因为你可以执行大多数有条件的指令。

ARMV6甚至还有饱和加法、减法和所有其他32位和压缩数的东西。

在x86上,您可以通过mmx或sse获得饱和算术。

所有这些都需要装配工,所以这不是你要的。

还有一些C-技巧可以做饱和算术。这个小代码对一个双字的四个字节进行饱和加法。它基于并行计算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位常量。

编辑: 并行版本最有可能比直进方法慢,但如果一次必须饱和多个值,则速度更快。

如果你关心表演,你 真的? 想在simd中做这类事情,在simd中x86有本地的饱和算法。

由于在标量数学中缺乏饱和算法,我们可以得到在4变量宽的SIMD上进行运算的情况。 更多 比等效C快4倍以上(对于8变量宽度的SIMD,也相应地正确):

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

零分支解决方案:

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 结果 埃克斯 ):

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

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

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

编辑: 既然你已经发布了你的版本,我不确定我的版本是否更干净/更好/更高效/更勤奋。

我不确定这是否比skizz的解决方案更快(总是概要),但这里有一个替代的无分支组装解决方案。请注意,这需要条件移动(cmov)指令,我不确定它是否适用于您的目标。

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

我们使用的当前实现是:

#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:
.......

它不是很轻便,但我觉得是最有效的方法。

最好的性能通常包括内联装配(正如一些人已经说过的那样)。

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

我把“无符号长整型”和“无符号长整型”的版本留给读者作为练习。;-)

以防有人想知道一个不使用2的补码32位整数进行分支的实现。

警告!此代码使用未定义的操作:“右移-1”,因此利用 Intel Pentium SAL instruction 将计数操作数屏蔽为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++可以编写更灵活的变体 雷莫 解决方案:

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 . 请注意 Fixed width integer types 可能在您的系统上不可用。

无分支x86 ASM解决方案的另一种选择是(AT&T语法,EAX和EBX中的A和B,导致EAX):

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

//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:网页上使用的编辑器不允许我发布宏,即它不理解非缩进语法等!

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操作符( == , != ) ?: 操作员。它只使用位运算符和逻辑运算符。

饱和算法不是C语言的标准,但通常是通过编译器内部实现的,所以最有效的方法是不干净的。必须添加ifdef块以选择正确的方式。msalters的答案对于x86体系结构来说是最快的。对于ARM,您需要在16位版本中使用ARM QAD16(Microsoft Visual Studio)的uuqadd16函数(ARM编译器),在32位版本中使用uuqadd16函数。 它将自动转换为单臂指令。

链接:

QADAD16 http://infocenter.arm.com/help/index.jsp?topic=/com.arm.doc.dui0491c/CJAICDDF.html

阿姆斯加德16 https://msdn.microsoft.com/en-US/library/hh875058.aspx

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