使用进位标志添加多字
GCC具有128位整数。 使用这些我可以让编译器使用mul
(或只有一个操作数的imul
)指令。 例如
uint64_t x,y; unsigned __in128 z = (unsigned __int128)x*y;
生产多 我用它来创建一个128×128到256的函数(在更新之前,请参阅此问题的结尾,如果您感兴趣,请参阅此代码)。
现在我想要进行256位加法,除了使用汇编之外,我还没有找到让编译器使用ADC
的方法。 我可以使用汇编程序,但我想要内联函数以提高效率。 编译器已经生成了一个有效的128×128到256函数(因为我在这个问题的开头解释了)所以我不明白为什么我应该在汇编中重写它(或者编译器已经有效实现的任何其他函数) 。
这是我提出的内联汇编函数:
#define ADD256(X1, X2, X3, X4, Y1, Y2, Y3, Y4) \ __asm__ __volatile__ ( \ "addq %[v1], %[u1] \n" \ "adcq %[v2], %[u2] \n" \ "adcq %[v3], %[u3] \n" \ "adcq %[v4], %[u4] \n" \ : [u1] "+&r" (X1), [u2] "+&r" (X2), [u3] "+&r" (X3), [u4] "+&r" (X4) \ : [v1] "r" (Y1), [v2] "r" (Y2), [v3] "r" (Y3), [v4] "r" (Y4))
(可能不是每个输出都需要一个早期的修改器但是我得到了错误的结果,至少没有最后两个 )
这是一个在C中做同样事情的函数
void add256(int256 *x, int256 *y) { uint64_t t1, t2; t1 = x->x1; x->x1 += y->x1; t2 = x->x2; x->x2 += y->x2 + ((x->x1) x3; x->x3 += y->x3 + ((x->x2) x4 += y->x4 + ((x->x3) < t1); }
为什么需要assembly? 为什么编译器不能编译add256
函数来使用进位标志? 有没有办法强制编译器执行此操作(例如,我可以更改add256
以便它执行此操作)吗? 有人想为不支持内联汇编的编译器做什么 (在汇编中编写所有函数?)为什么没有内在的东西呢?
这是128×128到256的function
void muldwu128(int256 *w, uint128 u, uint128 v) { uint128 t; uint64_t u0, u1, v0, v1, k, w1, w2, w3; u0 = u >> 64L; u1 = u; v0 = v >> 64L; v1 = v; t = (uint128)u1*v1; w3 = t; k = t >> 64L; t = (uint128)u0*v1 + k; w2 = t; w1 = t >> 64L; t = (uint128)u1*v0 + w2; k = t >> 64L; w->hi = (uint128)u0*v0 + w1 + k; w->lo = (t << 64L) + w3; }
某些类型定义:
typedef __int128 int128; typedef unsigned __int128 uint128; typedef union { struct { uint64_t x1; uint64_t x2; int64_t x3; int64_t x4; }; struct { uint128 lo; int128 hi; }; } int256;
更新:
我的问题主要是这些问题的重复:
- 得到-GCC使用的携带的逻辑换任意精度算术-而不列直插组件
- 高效-128位加成使用进位标志
- multiword-addition-in-c 。
英特尔有一篇很好的文章( 新指令支持大整数运算 ),它讨论了大整数运算和三条新指令MULX,ADCX,ADOX。 他们写:
mulx,adcx和adox的内在定义也将集成到编译器中。 这是使用内在函数实现的“add with carry”类型指令的第一个示例。 内在支持将使用户能够使用更高级别的编程语言(如C / C ++)实现大整数运算。
内在的是
unsigned __int64 umul128(unsigned __int64 a, unsigned __int64 b, unsigned __int64 * hi); unsigned char _addcarry_u64(unsigned char c_in, unsigned __int64 a, unsigned __int64 b, unsigned __int64 *out); unsigned char _addcarryx_u64(unsigned char c_in, unsigned __int64 a, unsigned __int64 b, unsigned __int64 *out);
顺便说一句,MSVC已经有一个_umul128
内在函数 。 因此,即使MSVC没有__int128
, _umul128
内在函数也可用于生成mul
,因此可用于128位乘法。
MULX
自Haswell的MULX
提供。 ADCX
和ADOX
指令适用于Broadwell处理器。 太糟糕了,自1979年8086以来, ADC
没有固有的内在性。这将解决内联assembly问题。
编辑:实际上__int128
将使用mulx
如果定义了BMI2(例如使用-mbmi2
或 – march=haswell
)。
编辑:
我按照LưuVĩnhPhúc的建议尝试了Clang的附加内置装置
void add256(int256 *x, int256 *y) { unsigned long long carryin=0, carryout; x->x1 = __builtin_addcll(x->x1, y->x1, carryin, &carryout); carryin = carryout; x->x2 = __builtin_addcll(x->x2, y->x2, carryin, &carryout); carryin = carryout; x->x3 = __builtin_addcll(x->x3, y->x3, carryin, &carryout); carryin = carryout; x->x4 = __builtin_addcll(x->x4, y->x4, carryin, &carryout); }
但这并没有产生ADC
,而且比我预期的要复杂得多。
我使用_addcarry_u64
内在函数找到了ICC 13.0.01的解决方案
void add256(uint256 *x, uint256 *y) { unsigned char c = 0; c = _addcarry_u64(c, x->x1, y->x1, &x->x1); c = _addcarry_u64(c, x->x2, y->x2, &x->x2); c = _addcarry_u64(c, x->x3, y->x3, &x->x3); _addcarry_u64(c, x->x4, y->x4, &x->x4); }
产生
L__routine_start_add256_0: add256: xorl %r9d, %r9d #25.9 movq (%rsi), %rax #22.9 addq %rax, (%rdi) #22.9 movq 8(%rsi), %rdx #23.9 adcq %rdx, 8(%rdi) #23.9 movq 16(%rsi), %rcx #24.9 adcq %rcx, 16(%rdi) #24.9 movq 24(%rsi), %r8 #25.9 adcq %r8, 24(%rdi) #25.9 setb %r9b #25.9 ret #26.1
我用-O3
编译。 我不知道如何使用ICC启用adx
。 也许我需要ICC 14?
这正好是我期待的1 addq
和3 adcq
。
使用Clang,结果使用-O3 -madx
是一团糟
add256(uint256*, uint256*): # @add256(uint256*, uint256*) movq (%rsi), %rax xorl %ecx, %ecx xorl %edx, %edx addb $-1, %dl adcq %rax, (%rdi) addb $-1, %cl movq (%rdi), %rcx adcxq %rax, %rcx setb %al movq 8(%rsi), %rcx movb %al, %dl addb $-1, %dl adcq %rcx, 8(%rdi) addb $-1, %al movq 8(%rdi), %rax adcxq %rcx, %rax setb %al movq 16(%rsi), %rcx movb %al, %dl addb $-1, %dl adcq %rcx, 16(%rdi) addb $-1, %al movq 16(%rdi), %rax adcxq %rcx, %rax setb %al movq 24(%rsi), %rcx addb $-1, %al adcq %rcx, 24(%rdi) retq
如果没有在Clang中启用-madx
,结果就不会好多了。
编辑: 好的MSVC已经有_addcarry_u64
。 我试过它,它和ICC一样好(1x add
和3x adc
)。