是的,谢谢,这有效。 @彼得科德斯。
__int128
也有效。但正如您所说,使用多精度算术的内在函数,即 C 中的 _addcarry_u64
,使用头文件 immintrin.h
我有以下代码
#include <stdio.h>
#include <stdlib.h>
#include <stdint.h>
#include <immintrin.h>
unsigned char _addcarry_u64(unsigned char c_in, uint64_t src1, uint64_t src2,uint64_t *sum);
int main()
{
unsigned char carry;
uint64_t sum;
long long int c1=0,c2=0;
uint64_t a=0x0234BDFA12CD4379,b=0xA8DB4567ACE92B38;
carry = _addcarry_u64(0,a,b,&sum);
printf("sum is %lx and carry value is %u n",sum,carry);
return 0;
}
您能指出我的错误吗?我收到了对
_addcarry_u64
的未定义引用。一些快速谷歌没有回答这个问题,如果要使用任何其他头文件或者它与 gcc 不兼容,为什么会这样
最初我有这段代码用于添加两个 64 位数字:
static __inline int is_digit_lessthan_ct(digit_t x, digit_t y)
{ // Is x < y?
return ( int)((x ^ ((x ^ y) | ((x - y) ^ y))) >> (RADIX-1));
}
#define ADDC(carryIn, addend1, addend2, carryOut, sumOut) \
{ digit_t tempReg = (addend1) + (int)(carryIn); \
(sumOut) = (addend2) + tempReg; \
(carryOut) = (is_digit_lessthan_ct(tempReg, (int)(carryIn)) | is_digit_lessthan_ct((sumOut), tempReg)); \
}
现在我知道使用汇编语言可以提高实现速度。所以我正在尝试做类似的事情,但我无法访问或返回携带。这是我的代码:
#include<stdio.h>
#include<stdlib.h>
#include<stdint.h>
uint64_t add32(uint64_t a,uint64_t b)
{
uint64_t d=0,carry=0;
__asm__("mov %1,%%rax\n\t"
"adc %2,%%rax\n\t"
"mov %%rax,%0\n\t"
:"=r"(d)
:"r"(a),"r"(b)
:"%rax"
);
return d;
}
int main()
{
uint64_t a=0xA234BDFA12CD4379,b=0xA8DB4567ACE92B38;
printf("Sum = %lx \n",add32(a,b));
return 0;
}
此加法的结果应为 14B100361BFB66EB1,其中 msb 中的第一个 1 是进位。我想将该进位保存在另一个寄存器中。我尝试了 jc,但遇到了一些错误。即使 setc 也给了我错误,可能是因为我不确定语法。那么谁能告诉我如何将进位保存在另一个寄存器中或通过修改此代码将其返回?
像往常一样,内联汇编并不是绝对必要的。 https://gcc.gnu.org/wiki/DontUseInlineAsm。但目前编译器对于实际的扩展精度加法有点糟糕,所以你可能需要 asm 来实现这一点。
adc
有一个英特尔内在函数:_addcarry_u64
。但不幸的是,gcc 和 clang 可能会使代码变慢。。在 64 位平台上的 GNU C 中,您可以只使用 unsigned __int128
。
更新:将 ADC(带进位添加)汇编到 C++ 显示了可移植的 C,该 C 获得最近的 clang 来创建一系列多个
adc
指令。(我尚未更新此答案的其余部分。)
编译器在检查加法进位时通常会设法编写出相当不错的代码,使用习惯用法
carry_out = (x+y) < x
,其中<
是无符号比较。例如:
struct long_carry { unsigned long res; unsigned carry; };
struct long_carry add_carryout(unsigned long x, unsigned long y) {
unsigned long retval = x + y;
unsigned carry = (retval < x);
return (struct long_carry){ retval, carry };
}
gcc7.2 -O3 发出这个(并且 clang 发出类似的代码):
mov rax, rdi # because we need return value in a different register
xor edx, edx # set up for setc
add rax, rsi # generate carry
setc dl # save carry.
ret # return with rax=sum, edx=carry (SysV ABI struct packing)
使用内联汇编,没有比这更好的方法了;该功能对于现代 CPU 来说已经是最佳选择。 (好吧,我猜如果
mov
不是零延迟,那么首先执行 add
会缩短准备就绪的延迟。但是在 Intel CPU 上,最好立即覆盖 mov-elimination 结果,所以它是最好先移动然后添加。)
Clang 甚至会使用
adc
将一个 add 的进位输出用作另一个 add 的进位输入,但仅限于第一个分支。也许是因为:更新:这个功能坏了:carry_out = (x+y) < x
在有进位时不起作用。使用 carry_out = (x+y+c_in) < x
,y+c_in
可以换行为零并给你 (x+0) < x
(假),即使有进位。
请注意,clang 的
cmp
/adc reg,0
完全实现了 C 的行为,这与另一个 adc
不同。
无论如何,在安全的情况下,gcc 第一次甚至不会使用
adc
。 (因此,对于不糟糕的代码使用 unsigned __int128
,对于比这更宽的整数使用 asm)。
// BROKEN with carry_in=1 and y=~0U
static
unsigned adc_buggy(unsigned long *sum, unsigned long x, unsigned long y, unsigned carry_in) {
*sum = x + y + carry_in;
unsigned carry = (*sum < x);
return carry;
}
// *x += *y
void add256(unsigned long *x, unsigned long *y) {
unsigned carry;
carry = adc(x, x[0], y[0], 0);
carry = adc(x+1, x[1], y[1], carry);
carry = adc(x+2, x[2], y[2], carry);
carry = adc(x+3, x[3], y[3], carry);
}
mov rax, qword ptr [rsi]
add rax, qword ptr [rdi]
mov qword ptr [rdi], rax
mov rax, qword ptr [rdi + 8]
mov r8, qword ptr [rdi + 16] # hoisted
mov rdx, qword ptr [rsi + 8]
adc rdx, rax # ok, no memory operand but still adc
mov qword ptr [rdi + 8], rdx
mov rcx, qword ptr [rsi + 16] # r8 was loaded earlier
add rcx, r8
cmp rdx, rax # manually check the previous result for carry. /facepalm
adc rcx, 0
...
这很糟糕,所以如果你想要扩展精度加法,你仍然需要 asm。但要将进位输出放入 C 变量中,则不需要。
对于C:
bool add(bool const c, uint64_t a, uint64_t const b, uint64_t* const sum)
{
*sum = a += b + c;
return c ? a <= b : a < b;
// return (((a <= b) ^ (a < b)) & c) ^ (a < b);
// return ((a == b) & c) ^ (a < b);
// return (a < b) || (c && (a == b));
}
一切都按照您的规格工作。
顺便说一句:您可以在《现代计算机算术(剑桥应用与计算数学专着第 18 册)第一版,Richard P. Brent(作者),Paul Zimmermann(作者)”一书中找到魔术背后的推理。