assembly 将ADC(带进位加法)汇编到C++

67up9zun  于 2023-03-18  发布在  其他
关注(0)|答案(7)|浏览(255)

有一条x86汇编指令ADC。我发现它的意思是“带进位的加法”。这意味着什么?在C++中如何实现这条指令的行为?

信息:

在Windows上编译。我使用32位Windows安装。我的处理器是英特尔酷睿2双核。

aelbi1ox

aelbi1ox1#

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

6rqinv9w

6rqinv9w2#

here(损坏)或here
然而,英特尔处理器有一个特殊的指令,叫做adc。这个命令的行为与add命令相似。唯一的额外之处是它还添加了值进位沿着。因此,这对于添加大整数可能非常方便。假设你想用16位寄存器添加一个32位整数。我们该怎么做呢?好吧,让我们假设第一个整数保存在寄存器对DX:AX上,第二个保存在BX:CX上。这就是:

add  ax, cx
adc  dx, bx

啊,所以先用add ax,cx把低16位相加,然后用adc把高16位相加,而不是add,这是因为:如果有溢出,进位位会自动加到高16位。因此,不需要繁琐的检查。这种方法可以扩展到64位等等......注意:如果32位整数加法在高16位也溢出,则结果将不正确,并且进位标志被设置,例如将50亿加到50亿。
从这里开始的所有事情,请记住它几乎都福尔斯实现定义的行为。
下面是一个适用于VS 2010(32位,WinXp)的小示例
注意:$7.4/1-“asm声明是有条件支持的;其含义由实现定义。[注意:它通常用于通过实现向汇编程序传递信息。-end note ]”

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

lx0bsm1f3#

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;

希望这个有用。

8gsdolmq

8gsdolmq4#

C++ 没有进位标志的概念,所以在ADC instruction周围做一个内在函数 Package 器是很笨拙的,但是Intel还是做了:据我所知,gcc在这方面做得很差(将进位结果保存到整数寄存器中,而不是留在CF中),但希望Intel自己的编译器做得更好。
另请参见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编译器资源管理器的asm输出。clang的-fverbose-asm不是很冗长,但是gcc 5.3 / 6.1浪费了两条mov指令,因此可读性较差。
有时候你可以用习惯用法uint64_t sum = a+b;/carry = sum < a;控制编译器发出adc或者使用add的进位输出,但是扩展这个用法以从adc而不是add获得进位输出在当前的编译器中是不可能的;c+d+carry_in可以完全绕回,如果您安全地执行,编译器无法优化c+d+carry中每个+上的多个执行检查。
叮当声_ExtInt
我知道有一种方法可以获得add/adc/.../adc链:Clang新推出的_ExtInt(width)特性,可提供最大16,777,215位(blog post)的任意大小的固定位宽类型,它于2020年4月21日加入到Clang的开发版本中,因此目前还没有发布任何版本。
这将有希望在ISO C和/或C++中出现;N2472提案显然“正在由ISO WG 14 C语言委员会积极考虑”

typedef _ExtInt(256) wide_int;

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

使用x86-64(Godbolt)的clang trunk -O2编译如下:

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),这不会改变这一点。

vatpfxk5

vatpfxk55#

这里面有一个错误。请尝试以下输入:

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

修复它。

3z6pesqy

3z6pesqy6#

在x86-64中,ADD指令将两个64位整数相加:add rax, rbxrax = 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, rbxrax = 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编译器可以识别大整数加法和use ADD/ADC to implement it

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

6rvt4ljy7#

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

相关问题