如何在C语言中进行无符号饱和加法？

Question

如何在C语言中进行无符号饱和加法？

calgorithmperformancesignal-processingsaturation-arithmetic

51

如何在C语言中实现最佳（最干净、最高效）的饱和加法？

该函数或宏应该将两个无符号输入相加（需要16位和32位版本），如果总和溢出，返回全1位（0xFFFF或0xFFFFFFFF）。

目标是在使用gcc（4.1.2）和Visual Studio（仅用于模拟，因此回退实现也可以）的x86和ARM上运行。

- Frank Szczerba

2

MSalters的答案编译成x86上迄今为止最好的代码，与我使用内联汇编能做到的最好的相当（实际上更好，因为编译器理解发生了什么，并且可以选择哪个操作数将是加法的目标）。在ARM上也同样不错。然而，gcc似乎没有使用ARM的带无符号饱和度的加法指令。MSalters的答案应该被接受。 - Peter Cordes

不幸的是，对于16位adds16_msalters，带有条件跳转和其他所有内容，胜利似乎在GCC 6中消失了。 - user1649948

相关：有符号饱和度：64位整数的有符号饱和加法？是一个更难的问题。我在那里的回答需要一个GCC内置函数来高效编译；与进位标志不同，很难让编译器使用有符号溢出标志输出。 - Peter Cordes

19个回答

26

使用普通的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;
}

这几乎是宏定义过的，直接传达了意义。

- rdentato

12

好的。一个小问题——如果我在代码中看到sadd16这个名字，我的第一反应会是s代表有符号（signed）。 - Craig McQueen

2

@匿名：Craig是从读取代码的角度来说的，当代码中有对sad16/32的调用时，你不会看到函数签名，除非你找到并打开头文件。 - Joseph Garvin

1

@Dietrich 那很愚蠢。我猜我从没注意过，因为我在 MSVC 中工作，完成后再移植到 GCC。 - Cole Tobin

3

只是一个小建议：0xFF..常量应该改为等价的UINTN_MAX常量（或(uintN_t)-1）。这样，只需要进行一次搜索和替换就可以编写sadd8或sadd64函数。同时也不需要计算0xFFFFFFFFFFFFFFFF中有多少个F。 - Alexandros

1

当针对armv4t时，在gcc 5.1中会生成漂亮的代码，仅使用4个无分支指令（其中两个是有条件的）。 - Alexandre Pereira Nunes

显示剩余13条评论

18

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

6

如果问题需要具备可移植性，它就不应该明确指定x86和ARM；-) - Steve Jessop

3

该函数仍然是可移植的——一旦填写了elif和else情况。可移植的代码并不意味着你不能针对特定平台进行优化。 - Arafangion

3

YumeYao提出了一个修改意见（我没有采纳），因为它改变了答案的性质：三个指令（xor reg,reg; setne reg; dec reg;) 可以用更高效的一条指令（sbb reg,reg）替代。 - Marc Gravell

1

两件事情：__asm 关键字是依赖于编译器的。标准没有为内联汇编指定关键字。因此，从这个意义上讲，它不是可移植的，因为它依赖于编译器。例如，英特尔 C++ 编译器仅适用于 Windows，因此，如果您编写使用英特尔 C++ 功能的可移植代码，则它将不具备可移植性。另一件事情：内联汇编会阻止编译器进行内联。因此，如果仍然存在函数调用开销，这种优化并不能真正帮助。 - Cole Tobin

3

有点糟糕，因为这是 MSVC 的内联汇编，所以输入/输出必须通过内存进行。（或者如果这个带有eax返回值的无返回语句可以工作，那么函数本身不能内联。无论如何，输入都必须通过内存进行）。其次，因为 "cmov" 更好：关键路径更短，因为 "mov eax, -1" 不在关键路径上，不像 "sbb"。 - Peter Cordes

显示剩余2条评论

13

在ARM中，您可能已经内置了饱和算术。ARMv5 DSP扩展可以使寄存器饱和到任意位长。此外，在ARM上，饱和通常很便宜，因为您可以有条件地执行大多数指令。

即使对于32位和打包数字，ARMv6也具有饱和加法、减法和所有其他功能。

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

通过更改符号掩码常量和底部的移位，您可以获得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位常量。

编辑：并行版本很可能比直接的方法更慢，但如果您需要同时饱和多个值，则它们将更快。

- Nils

1

我没有看到32位整数的无符号饱和指令，只有packed16 UQUADD16 and packed8。不过有一个带有有符号饱和的32位加法。另外，不幸的是，这个C代码在32位情况下编译成了可怕的代码：所有SWAR风格的开销，但只针对一个值。它不幸地不能被优化掉。请参见我在MSalters答案中的评论：godbolt链接包括您的版本。 - Peter Cordes

10

零分支解决方案：

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汇编语言（AT＆T语法中，eax 和 ebx 中的 a 和 b 分别作为输入，结果存放在 eax 中）：

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

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

- R.. GitHub STOP HELPING ICE

2

你希望编译器能够发现这个问题，但它们并没有。clang/gcc/icc在除了MSalter的答案之外的所有方面都做得很糟糕。你的编译结果为lea eax，[rdi + rsi] / mov edx，edi / mov ecx，esi / add rdx，rcx / shr rdx，32 / neg edx / or eax，edx。 - Peter Cordes

10

如果您关心性能，那么您真的希望在SIMD中进行此类操作，在其中x86具有本地饱和算术。

由于标量数学中缺乏饱和算术，因此可以出现情况，在4变量宽度的SIMD上执行的操作比等效的C更快(并且在8变量宽度的SIMD上也是如此)：

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

- Dark Shikari

8

如果只对一个变量进行操作，那么使用SSE指令是否仍然更快？ - Joseph Garvin

@JosephGarvin：如果你需要饱和的16位或8位加法或减法，它是可以的。或者使用SSSE3 pshufb进行位反转（使用每个nibble并行查找表）。或使用SSE4.1，在32位整数上进行min、max（或abs）运算，只需一条指令即可完成。甚至可以在32位代码中进行64位整数计算。但是，在将数字在XMM寄存器和整数寄存器之间传递时会产生开销，请谨慎使用。 - Peter Cordes

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

编辑：现在你已经发布了你的版本，我不确定我的版本是否更加简洁/优秀/高效/酷炫。

- Denton Gentry

你的回答看起来像是我认为我们应该做的，但正如你所说，我不确定哪个更好，这就是为什么我想在这里开放投票的原因。 - Frank Szczerba

它们两个看起来都正确，因此效率应该决定。额外的比较并不明显比过度调整加法慢（或快）。对两种解决方案在两种架构上进行一些效率测试，并选择更快的那一个。 - Rafał Dowgird

1

检查两个输入的总和是否必要？极限情况是(uint16_t)(0xffff + 1)，它既小于1又小于0xffff，因此似乎可以避免进行第二次检查。 - Frank Szczerba

你说得对，溢出的丢失位是最大整数值+1，因此溢出加法的结果等于a+b-(最大整数值+1)，其既小于a又小于b。 - Rafał Dowgird

为什么要使用~((uint32_t)0)？您已经包含了<limits.h>以获取uint32_t声明，那么为什么不直接使用UINT32_MAX呢？ - Cole Tobin

3

我们目前使用的实现方式是：

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

- Frank Szczerba

5

小写字母的函数宏？太邪恶了！ - Arafangion

3

我不确定这是否比Skizz的解决方案更快（始终进行性能分析），但这是一种替代的无分支汇编解决方案。请注意，这需要条件移动（CMOV）指令，我不确定您的目标平台是否可用。


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

- Adam Rosenfield

2

ARM拥有“C-everything”，不仅仅是跳转和移动。但它不支持32位常量。因此，您需要一个条件mov 0，然后是一个条件sub 1。 - MSalters

ARM可以使用立即数通过mvn（mov-NOT）创建小的负数。汇编器知道如何为您使用它，例如adds r0，r1（加和设置标志位）/ movCS r0，#-1（如果Carry Set，则mvn 0 = -1）。xD，MSalter的答案后来显示编译器已经完全做到了这一点。并且还会为x86发出此代码，因此您不必自己操作。而且以一种可以内联和常量传播的方式。 - Peter Cordes

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

这是我所知道的最好的实现方式

- Hannodje

你可以写overflow&31，它仍然会编译而不浪费and ecx, 31，因为gcc和clang知道移位指令的工作方式（ISA定义了在自286以来的每个CPU上都是这样）。请参见从x86标签wiki链接的Intel insn ref手册。在移位方式不同的目标上，它们将发出必要的指令使其正常工作。当然，这仍然依赖于使用算术移位对有符号整数进行右移，而C标准并不保证。 - Peter Cordes

2

这也使用了a+b的未定义操作溢出！在C和C++中，有符号溢出是UB。 - Peter Cordes

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- MSalters · Accepted Answer

在这里，您可能需要可移植的C代码，您的编译器将把它转换为适当的ARM汇编代码。 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;
}

请注意，这与其他算法不同之处在于它会纠正溢出，而不是依靠另一个计算来检测溢出。

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

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  @