将汇编中的ADC（带进位加法）转换为C++

Question

有一条x86汇编指令ADC。我发现这意味着"带进位相加"。这是什么意思/作用？如何在C++中实现这个指令的行为？ 信息：
在Windows上编译。我正在使用32位Windows安装程序。我的处理器是英特尔的Core 2 Duo。

- Martijn Courteaux

---

@Chubsdad：我已经尽力添加了一些信息。希望足够了。 - Martijn Courteaux

哪个编译器？要访问进位标志，您必须在C++代码中嵌入汇编代码。如何实现取决于您使用的编译器。 - TonyK

Answer 1

ADC与ADD相同，但是如果处理器的进位标志被设置，它会额外添加1。

- Simone

---

好的！谢谢。但是现在，我必须知道标志是否被设置。在C++中是否可能？ - Martijn Courteaux

不是使用标准的C++，你必须使用“asm”代码块。我不记得确切的语法，但你将失去代码的可移植性。 - Simone

ADC 的思想并不是为了知道进位标志，而是在 ADC 之前进行一次 ADD 操作，这样当 ADD 溢出时就会设置进位标志。 - stefaanv

@Martijn，如果你想知道进位标志的状态，可以像这样做：pushfd; pop eax; 现在进位标志位于eax的第0位。 - Simone

因为没有真正回答问题中的C++方面，所以被踩了。此外，与setc al（如果需要，则为movzx eax，al）相比，那个asm序列有点糟糕。在英特尔SnB系列CPU上，pushf是一个3-uop指令。push/pop存储转发往返会向涉及CF的依赖链添加约5个周期的延迟。 - Peter Cordes

我本来想编辑这个答案，详细说明并链接指令集参考手册，但最终发现修改内容太多，因此我将修改后的内容作为新答案发布了。 - Peter Cordes

Answer 2

从这里（失效）或这里获取。

然而，英特尔处理器有一条特殊的指令叫做adc。这个命令的行为与add命令类似，唯一的额外之处是它还会将进位标志也加上。因此，在添加大整数时，这可能非常方便。假设您想要使用16位寄存器添加32位整数。我们该怎么办呢？好吧，假设第一个整数存储在DX:AX寄存器对中，第二个整数存储在BX:CX中。方法如下：

add  ax, cx
adc  dx, bx

啊，首先，低16位使用 add ax，cx 进行相加。然后高16位使用 adc 而不是 add 进行相加。这是因为：如果有溢出，在高16位中自动添加进位标志位。所以，不需要繁琐的检查。这种方法可以扩展到64位等等...请注意：如果32位整数相加在高16位也发生了溢出，则结果将不正确，并且进位标志位被设置，例如将50亿加到50亿。

从这里开始的所有内容都记住它们基本上属于实现定义行为的范畴。

这是一个在VS 2010（32位，WinXp）上运行的小样例。

警告：$7.4/1- "asm 声明是有条件支持的；其含义是实现定义的。[ 注：通常用于通过实现向汇编程序传递信息。—注释结束 ]"

int main(){
   bool carry = false;
   int x = 0xffffffff + 0xffffffff;
   __asm {
      jc setcarry
setcarry:
      mov carry, 1
   }
}

- Chubsdad

---

我无法在我的回复中使用块引用来引用“Caveat....”部分。有时候这种格式化就是不正常。 - Chubsdad

0xffffffff 可能是 -1 或 UINT_MAX，它被储存在一个 int 中。或许应该将 'x' 设为 unsigned int，或者将 summands 设为 INT_MAX (0x7fffffff)。如果我们将 summands 视为与结果相同类型（即有符号整数），那么 OVERFLOW 标志不会被设置——结果是 -2 (0xfffffffe)。 - jww

那段代码太荒谬了；你不能从asm块外的C语句中依赖于CF是否被设置。它可能在调试模式下运行良好，但启用优化后就没什么用了。此外，请使用setc carry根据CF将进位设置为0或1。 - Peter Cordes

Answer 3

C++语言没有进位标志的概念，因此编写一个内置函数包装器来处理ADC指令是很麻烦的。然而，英特尔还是做到了：unsigned char _addcarry_u32 (unsigned char c_in, unsigned a, unsigned b, unsigned * out);。据我所知，gcc对此做得不好（将进位结果保存到整数寄存器中，而不是留在CF中），但希望英特尔自己的编译器能做得更好。请参阅x86标签wiki以获取汇编文档。

---

当添加比单个寄存器更宽的整数时，例如在32位代码中添加int64_t或在64位代码中添加__int128_t，编译器将为您使用ADC。

#include <stdint.h>
#ifdef __x86_64__
__int128_t add128(__int128_t a, __int128_t b) { return a+b; }
#endif
    # clang 3.8 -O3  for x86-64, SystemV ABI.
    # __int128_t args passed in 2 regs each, and returned in rdx:rax
    add     rdi, rdx
    adc     rsi, rcx
    mov     rax, rdi
    mov     rdx, rsi
    ret

来自 Godbolt编译器浏览器的汇编输出。clang的-fverbose-asm不太详细，但是gcc 5.3/6.1浪费了两个mov指令，因此不易阅读。

有时候你可以通过使用习语 uint64_t sum = a+b; / carry = sum < a; 强制编译器发出 adc 或者其他使用 add 的进位标志。但是，使用当前的编译器无法将此扩展为从 adc 而不是 add 获取进位标志；如果你安全地在 c+d+carry 中执行多个进位标志检查，则可能会导致 c+d+carry_in 回绕。编译器无法优化每个 + 上的进位标志检查。

---

Clang _ExtInt

我知道一种使用 add/adc/.../adc 链的方法：Clang 的新特性 _ExtInt(width)，它提供了任意大小（最大可达16,777,215位）的固定位宽类型（blog post）。该特性于2020年4月21日添加到clang的开发版本中，因此尚未包含在任何发布版本中。

希望这个特性能够在ISO C和/或C++中出现； N2472 提案似乎正在被“ISO WG14 C语言委员会积极考虑”。

typedef _ExtInt(256) wide_int;

wide_int add ( wide_int a, wide_int b) {
    return a+b;
}

使用clang trunk -O2编译x86-64的代码（Godbolt）如下：

add(int _ExtInt<256>, int _ExtInt<256>):
        add     rsi, r9
        adc     rdx, qword ptr [rsp + 8]
        adc     rcx, qword ptr [rsp + 16]
        mov     rax, rdi                        # return the retval pointer
        adc     r8, qword ptr [rsp + 24]        # chain of ADD / 3x ADC!

        mov     qword ptr [rdi + 8], rdx        # store results to mem
        mov     qword ptr [rdi], rsi
        mov     qword ptr [rdi + 16], rcx
        mov     qword ptr [rdi + 24], r8
        ret

显然，_ExtInt 以整数寄存器的值传递，直到调用约定用完寄存器为止。(至少在这个早期版本中; 或许 x86-64 SysV 应该将其归类为“内存”，当它比2或3个寄存器更宽时，就像大于16字节的结构体一样。尽管与结构不同，但将其放在寄存器中可能很有用。只需将其他参数放在前面，使它们不被替换即可。)

第一个 _ExtInt 参数在 R8:RCX:RDX:RSI 中，第二个参数的低 qword 在 R9 中，其余在内存中。

返回值对象的指针作为隐藏的第一个参数传递到 RDI; x86-64 System V 只能在最多2个整数寄存器 (RDX:RAX) 中返回，这不会改变这一点。

- Peter Cordes

---

现在已经快4年了，我仍然无法让编译器（gcc、clang）生成add、adc指令链。你认为现在有可能吗？ - madhur4127

对于仅有两个指令，使用纯C语言的sum=a+b; / carry = sum<a;技巧或者__int128是可行的。但是对于更长的链条，据我所知，即使使用_addcarry_u32编译器仍然很糟糕。 - Peter Cordes

@madhur4127：更新：clang _ExtInt 可以让您使用任何宽度高达 16,777,215 位的固定宽度整数类型。(http://blog.llvm.org/2020/04/the-new-clang-extint-feature-provides.html)。 https://godbolt.org/z/bsDCvh 显示 _ExtInt(256) 上的 + 编译为 add / adc / adc / adc。 - Peter Cordes

当前版本的ExtInt仅展开了所有内容，我看到了4000多行汇编，其中包括2048*2048的乘法没有任何循环。在(1<<20)位时，编译器资源监视器因超时而终止了该进程。 - madhur4127

@madhur4127：哈哈，这很有趣，谢谢你的检查。所以目前对于非常大的整数，特别是乘法来说并不实用。 - Peter Cordes

Answer 4

ADC的行为可以在C和C++中模拟。以下示例将两个数字相加（存储为无符号数组，因为它们太大而无法放入单个无符号数）。

unsigned first[10];
unsigned second[10];
unsigned result[11];

....   /* first and second get defined */

unsigned carry = 0;
for (i = 0; i < 10; i++) {
    result[i] = first[i] + second[i] + carry;
    carry = (first[i] > result[i]);
}
result[10] = carry;

希望这能帮到你。

- Sparky

---

如果 second==~0U && carry==1，那么这段代码将无法设置进位。例如：对于32位无符号整数来说，这将是 second[i]==0xFFFFFFFF && carry==1。在这种情况下，即使发生了溢出（进位），first[i] == result[i] 仍然成立。 - Stephane Hockenhull

工作代码是 unsigned tmp = second[i] + carry; result[i] = first[i] + tmp; carry = (first[i] > result[i]) | (second[i] > tmp);。 - Stephane Hockenhull

而且这个事实非常缓慢，这就是为什么它现在是用汇编语言编写的原因。 - Joshua

Answer 5

在x86-64中，ADD指令将两个64位整数相加：add rax，rbx执行rax = rax + rbx。
当无符号溢出时（即结果不适合64位），它还将进位标志设置为1，否则将进位标志设置为0。

在C++中，您可以这样模拟ADD：

uint64_t a, b;
bool carry;

a += b;
carry = (a < b);  // a+b can't be smaller than b: there must have been an overflow

ADC指令类似于ADD，但会将进位标志加到结果中：
adc rax, rbx执行rax = rax + rbx + 进位标志。
如果存在无符号溢出，它还会设置进位标志。

在C++中：

uint64_t tmp = b + carry;
a += tmp;
carry = (tmp < carry) + (a < tmp);  // only one overflow can happen

ADD和ADC指令可用于添加具有n“位”的大整数。
对于最低有效数字，请使用ADD，然后使用ADC（n - 1）次来添加其余数字。
这是“竖式加法算法”。

例如，使用四个64位“数字”添加256位大整数：

mov rax, [rsi]        ; load the least significant source digit
mov rbx, [rsi + 8]    ; ...
mov rcx, [rsi + 16]
mov rdx, [rsi + 24]
add [rdi], rax        ; add it to the least significant destination digit
adc [rdi + 8], rbx    ; ... propagate carry up
adc [rdi + 16], rcx
adc [rdi + 24], rdx

最近版本的clang编译器可以识别大整数加法并且使用ADD/ADC实现。

constexpr uint64_t n = 4;
uint64_t dst[n], src[n];

// Add src to dst.
uint64_t carry = 0;
for (int i = 0; i < n; i++) {
  uint64_t tmp = src[i] + carry;
  dst[i] += tmp;
  carry = (tmp < carry) + (dst[i] < tmp);
}

- Řrřola

---

非常酷，终于有一种方法可以用纯ISO C++编写它，以便在Clang 9及更高版本中编译为带有进位和进位输出的adc指令链（而clang 8及更早版本则会错过peephole优化，并使用setc或setb将carry实现为0/1）。 - Peter Cordes

Answer 6

这里有一个bug。请尝试输入以下内容：

unsigned first[10] =  {0x00000001};
unsigned second[10] = {0xffffffff, 0xffffffff};

这个结果应该是 {0, 0, 1, ...}，但是实际结果为 {0, 0, 0, ...}。

修改这一行：

carry = (first[i] > result[i]);

转换为：

if (carry)
    carry = (first[i] >= result[i]);
else
    carry = (first[i] > result[i]);

修复它。

- Oshkosher

---

carry=(carry&&first[i]>=result[i])||(!carry&&first[i]>result[i]) 避免分支并且执行相同的操作，如果有人感兴趣的话。 - Hassedev

实际上，||和&&运算符会导致分支，因为它们仅在必要时才评估右侧操作数。与易于阅读的if()语句相比，这个单行代码中有更多的分支。 - Stephane Hockenhull

Answer 7

这是我最快的代码：

template <class Ty>
constexpr bool add_carry_ux(bool carry_in, Ty src1, Ty src2, Ty* sum_out)
{
    const Ty sum = src1 + src2;
    const bool carry_out = (sum < src1) | ((sum == ~static_cast<Ty>(0)) & carry_in);

    *sum_out = sum + carry_in;

    return carry_out;
}

ASM：

add_carry_ux(bool, unsigned long, unsigned long, unsigned long*):
        add     rsi, rdx
        movzx   eax, dil
        setc    dl
        add     rax, rsi
        cmp     rsi, -1
        mov     QWORD PTR [rcx], rax
        sete    al
        movzx   edx, dl
        and     eax, edi
        or      eax, edx
        ret

- Loge

---

这个问题的另一个答案显示了一段代码，可以在最近的clang编译器中编译成单个adc指令。当内联时，是否能够更好地处理进位输入和输出在CF寄存器中的情况呢？因为这段代码看起来有很多汇编语句。 - Peter Cordes

Answer 8

int32_t adc(uint32_t first, uint32_t second, uint32_t *carry)
    {
        uint32_t res;
        uint32_t carry_out = 0;
    
        if (!*carry)
        {
            res = first + second;
            *carry = (res < first) && (res < second);
    
            return res;
        }
    
        res = adc(first, second, &carry_out);
        if (*carry)
        {
            res++;
            carry_out |= !res;
        }
        
        *carry = carry_out;
    
        return res;
    }

- Serg Stetsuk

---

通过更广泛的操作来构建一个带进位的16位加法有点违背初衷。只需将 result >> 16 右移即可获得高半部分（进位输出），或者直接使用该更宽的类型，并让编译器使用 adc 或目标ISA上有效的任何内容来实现它。 - Peter Cordes

另外，如果unsigned int实际上是一个像你所假设的16位类型，那么在你赋值给result之前，first + second已经发生了包装。也许你的意思是first + (unsigned long)second？ - Peter Cordes

你可以[编辑]你的答案，用好的代码替换坏的代码。但是请注意，在纯C中实现ADC的难点是处理进位。你的result < second足以检测到进位，但你不应该将其添加到this元素中，而应该单独返回它。这就像add eax，ecx / adc eax，0，这几乎永远不是你想要的。 - Peter Cordes

我认为这个新版本在像 0xffffffff + 0 + carry=1 这样的情况下会失败。while循环执行 0xffffffff + 1 = 0，产生一个进位，使得while循环再次运行，产生res=1和carry=0。然后它通过尾调用自身来执行 1 + 0，返回1并将carry留为0，而正确的结果是 0 和carry=1。在 first + second + *carry 中的任何一个 + 操作中，都需要将进位发送到最终的 *carry 输出中，而不是加回到返回值中。请记住，进位是32+32 => 33位加法的第33位，但进位具有仅为1的位值。 - Peter Cordes