有一条x86汇编指令ADC。我发现它的意思是“带进位的加法”。这意味着什么?在C++中如何实现这条指令的行为?
ADC
信息:
在Windows上编译。我使用32位Windows安装。我的处理器是英特尔酷睿2双核。
aelbi1ox1#
ADC与ADD相同,但如果处理器的进位标志置位,则额外加1。
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 } }
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;
希望这个有用。
8gsdolmq4#
C++ 没有进位标志的概念,所以在ADC instruction周围做一个内在函数 Package 器是很笨拙的,但是Intel还是做了:据我所知,gcc在这方面做得很差(将进位结果保存到整数寄存器中,而不是留在CF中),但希望Intel自己的编译器做得更好。另请参见x86标记wiki以获取汇编文档。当添加大于单个寄存器的整数时,编译器将为您使用ADC,例如在32位代码中添加int64_t,或在64位代码中添加__int128_t。
int64_t
__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语言委员会积极考虑”
-fverbose-asm
mov
uint64_t sum = a+b;
carry = sum < a;
adc
add
c+d+carry_in
c+d+carry
+
_ExtInt
_ExtInt(width)
typedef _ExtInt(256) wide_int; wide_int add ( wide_int a, wide_int b) { return a+b; }
使用x86-64(Godbolt)的clang trunk -O2编译如下:
-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),这不会改变这一点。
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]);
修复它。
3z6pesqy6#
在x86-64中,ADD指令将两个64位整数相加:add rax, rbx做rax = rax + rbx。当出现无符号溢出时(=当结果不适合64位时),它还将进位标志设置为1,否则它将进位标志设置为0。在C++中,可以像这样模拟ADD:
add rax, rbx
rax = rax + rbx
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++中:
adc rax, rbx
rax = rax + rbx + carry_flag
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。
clang
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); }
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; }
7条答案
按热度按时间aelbi1ox1#
ADC与ADD相同,但如果处理器的进位标志置位,则额外加1。
6rqinv9w2#
从here(损坏)或here
然而,英特尔处理器有一个特殊的指令,叫做adc。这个命令的行为与add命令相似。唯一的额外之处是它还添加了值进位沿着。因此,这对于添加大整数可能非常方便。假设你想用16位寄存器添加一个32位整数。我们该怎么做呢?好吧,让我们假设第一个整数保存在寄存器对DX:AX上,第二个保存在BX:CX上。这就是:
啊,所以先用add ax,cx把低16位相加,然后用adc把高16位相加,而不是add,这是因为:如果有溢出,进位位会自动加到高16位。因此,不需要繁琐的检查。这种方法可以扩展到64位等等......注意:如果32位整数加法在高16位也溢出,则结果将不正确,并且进位标志被设置,例如将50亿加到50亿。
从这里开始的所有事情,请记住它几乎都福尔斯实现定义的行为。
下面是一个适用于VS 2010(32位,WinXp)的小示例
注意:$7.4/1-“asm声明是有条件支持的;其含义由实现定义。[注意:它通常用于通过实现向汇编程序传递信息。-end note ]”
lx0bsm1f3#
ADC行为可以在C和C++中模拟。以下示例将两个数字相加(存储为无符号数组,因为它们太大,无法放入单个无符号数组)。
希望这个有用。
8gsdolmq4#
C++ 没有进位标志的概念,所以在
ADC
instruction周围做一个内在函数 Package 器是很笨拙的,但是Intel还是做了:据我所知,gcc在这方面做得很差(将进位结果保存到整数寄存器中,而不是留在CF中),但希望Intel自己的编译器做得更好。另请参见x86标记wiki以获取汇编文档。
当添加大于单个寄存器的整数时,编译器将为您使用ADC,例如在32位代码中添加
int64_t
,或在64位代码中添加__int128_t
。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语言委员会积极考虑”
使用x86-64(Godbolt)的clang trunk
-O2
编译如下:显然,
_ExtInt
是通过整型寄存器中的值传递的,直到调用约定用完寄存器为止。(至少在这个早期版本中是这样;也许x86-64 SysV应该把它归类为“内存”,当它比2个或3个寄存器更宽时,比如大于16字节的结构体。虽然比结构体更宽,但把它放在寄存器中可能会很有用。只要把其他参数放在前面,这样它们就不会被替换。第一个_ExtInt参数位于R8:RCX:RDX:RSI中,第二个参数的低位qword位于R9中,其余参数位于内存中。
返回值对象的指针作为隐藏的第一个参数传递到RDI中;x86-64 System V最多只能返回2个整数寄存器(RDX:RAX),这不会改变这一点。
vatpfxk55#
这里面有一个错误。请尝试以下输入:
结果应为{0,0,1,...},但结果为{0,0,0,...}
更改此行:
改为:
修复它。
3z6pesqy6#
在x86-64中,ADD指令将两个64位整数相加:
add rax, rbx
做rax = rax + rbx
。当出现无符号溢出时(=当结果不适合64位时),它还将进位标志设置为1,否则它将进位标志设置为0。
在C++中,可以像这样模拟ADD:
ADC指令类似于ADD,但会将进位标志添加到结果中:
adc rax, rbx
做rax = rax + rbx + carry_flag
。如果存在无符号溢出,它还设置进位标志。
在C++中:
ADD与ADC指令可用于将大整数(带有 n 个“数字”)相加。
对最低有效数字使用ADD,然后使用ADC(n - 1)次将其余数字相加。
这就是“教科书加法算法"。
例如,将256位大整数与四个64位“数字”相加:
最新版本的
clang
编译器可以识别大整数加法和use ADD/ADC to implement it。6rvt4ljy7#