将 ADC（带进位相加）组装到 C++

Question

有一个 x86 汇编指令 ADC。我发现这意味着“带进位添加”。这是什么意思/做什么？如何在 C++ 中实现该指令的行为？

信息：
在 Windows 上编译。我使用的是 32 位 Windows 安装。我的处理器是 Intel 的 Core 2 Duo。

Answer 1

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

Answer 2

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;

希望这有帮助。

Answer 3

C++ 语言没有任何进位标志的概念，因此围绕 制作一个内部函数包装器ADC 指令 很笨拙。然而，英特尔还是这么做了： unsigned char _addcarry_u32（unsigned char c_in、unsigned a、unsigned b、unsigned * out）；。最后我检查了一下，gcc 在这方面做得很差（将进位结果保存到整数寄存器中，而不是将其保留在 CF 中），但希望英特尔自己的编译器能做得更好。

另请参阅 x86 汇编文档的标记 wiki。

---

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

#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 指令，因此可读性较差。

有时，您可以手持编译器发出 adc 或以其他方式使用成语 uint64_t sum = a+b; 进行 add 的进位> / 进位=总和<一个；。但是，当前的编译器无法扩展此功能以从 adc 获取进位，而不是从 add 获取； c+d+carry_in 可以一路回绕，编译器无法优化对 c+d 中每个 + 执行的多重检查+携带如果你安全的话。

---

Clang _ExtInt

我知道有一种方法可以获取 add/adc/.../adc 链：Clang 的新 _ExtInt(width) 功能提供了固定的-bit-width 任何大小的类型，最多 16,777,215 位（博客帖子）。它于 2020 年 4 月 21 日添加到 clang 的开发版本中，因此尚未出现在任何发布版本中。

这有望在某个时候出现在 ISO C 和/或 C++ 中； N2472 提案显然正在“被ISO WG14 C 语言委员会积极考虑”

（更新：现在在 C23 中为 _BitInt(256)，尽管支持的最大位宽取决于实现，可能低至 128。 Clang 支持将其作为 C++ 中的扩展，但 GCC 和 MSVC 不支持。）

typedef _ExtInt(256) wide_int;

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

使用 x86-64 的 clang trunk -O2 编译如下（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< /code> 按整数寄存器中的值传递，直到调用约定用完寄存器为止。 （至少在这个早期版本中；当 x86-64 SysV 比 2 个或 3 个寄存器宽时，也许 x86-64 SysV 应该将其归类为“内存”，例如大于 16 字节的结构。虽然比结构更多，但将其放在寄存器中很可能是只需将其他参数放在前面，这样它们就不会被替换。）

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

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

Answer 4

来自此处（已损坏）或此处

但是，英特尔处理器
有一个特殊的指令叫做adc。
该命令的行为与
添加命令。唯一额外的事情是
它还添加了值进位标志
沿着。所以，这可能非常方便
添加大整数。假设你想要
将 32 位整数与 16 位整数相加
寄存器。我们怎样才能做到这一点？出色地，
假设第一个整数是
保存在寄存器对 DX:AX 上，并且
第二个是在 BX:CX 上。这是
如何：

添加 ax, cx
adc dx, bx

啊，所以首先，低 16 位加上
添加斧头、CX。那么高16位就是
使用 adc 而不是 add 添加。这是
因为：如果有溢出，
进位位自动添加在
较高的 16 位。所以，不麻烦
检查。这个方法可以扩展
到 64 位等等...请注意：如果
32位整数加法溢出
也是在较高的 16 位，结果
将不正确并且进位标志
已设置，例如 5 加上 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
   }
}

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 + Carry_flag。
如果存在无符号溢出，它还会设置进位标志。

在 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) 次将其余数字相加。
这就是“教科书添加算法”。

例如，将 256 位大整数与四个 64 位“数字”相加：

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

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

修复它。

Answer 7

有__builtin_uadd_overflow内在函数可以通过编译器最佳地使用add/adc来构建加法链。

来自旧文档（早为 gcc 5!!!!）

https： //gcc.gnu.org/onlinedocs/gcc/Integer-Overflow-Builtins.html

https://gcc.gnu.org/onlinedocs/gcc-5.3.0/gcc/Integer-Overflow-Builtins.html

两者clang< /strong> 和 GCC 确实实现了这些内置函数，并且我验证了生成的代码在 x86_64 和 aarch64 目标上都是最佳的。

此功能现已在最新的产品更新发布版本 Visual Studio 2022 中发布版本 17.7（例如 _add_overflow_i8 ....）

#include <stdint.h>

typedef unsigned __int128 uint128_t;


// carry_out = a + b + carry_in
uint8_t my_addcarry_u64(uint8_t carry_in, uint64_t a, uint64_t b, uint64_t * sum)
{
        bool c;
        uint64_t res;
        c = __builtin_uaddll_overflow (a, b, (long long unsigned *)&res);
        c |= __builtin_uaddll_overflow (res, carry_in, (long long unsigned *)&res);
        *sum = res;
        return c;
}

// carry_out = a + b + carry_in
uint8_t my_addcarry_u128(uint8_t carry_in, uint128_t a, uint128_t b, uint128_t * sum)
{
        bool c;
        uint64_t res_lo, res_hi;
        c = __builtin_uaddll_overflow (a, b, (long long unsigned *)&res_lo);
        c |= __builtin_uaddll_overflow (carry_in, res_lo, (long long unsigned *)&res_lo);
        c = __builtin_uaddll_overflow (a >> 64, c, (long long unsigned *)&res_hi);
        c |= __builtin_uaddll_overflow (b >> 64, res_hi, (long long unsigned *)&res_hi);
        *sum = ((uint128_t)res_hi << 64) + res_lo;
        return c;
}

该线程相当旧，我对原始问题“如何在 C++ 中实现该指令的行为”提供了答复。

Answer 8

这是我最快的代码：

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

Answer 9

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