如何在汇编中乘以两个十六进制128位数

Question

我在内存中有两个128位的十六进制数字,例如(小端):

x:0x12 0x45 0x00 0x00 0x00 0x00 0x00 0x00 0x00 0x00 0x00 0x00 0x00 0x00 0x00 0x00
y:0x36 0xa1 0x00 0x00 0x00 0x00 0x00 0x00 0x00 0x00 0x00 0x00 0x00 0x00 0x00 0x00

我要执行这两个数字之间的无符号乘法,所以我的新数字将是:

z:0xcc 0xe3 0x7e 0x2b 0x00 0x00 0x00 0x00 0x00 0x00 0x00 0x00 0x00 0x00 0x00 0x00

现在,我知道我可以将半个x和y数字移入rax并rbx注册,例如,执行mul操作,并对另一半执行相同的操作.问题是,通过这样做,我失去了结转,我不知道如何避免这种情况.大约4个小时我面临这个问题,我能看到的唯一解决方案是二进制转换(and< - > shl,1).

你能给我一些关于这个问题的意见吗？
我认为最好的解决方案是占用一个字节的时间.

Answer 1

令μ= 2 ⁶⁴,那么我们就可以分解的128比特数一和b为一个 = 一个₁ μ+ 一个₂和b = b ₁ μ+ b ₂.然后我们可以通过首先计算部分乘积来计算c = ab与64·64→128位乘法:

q ₁ μ+ q ₂ = 一个₂ b ₂
- [R ₁ μ+ - [R ₂ = 一个₁ b ₂
小号₁ μ+ 小号₂ = 一个₂ b ₁
吨₁ μ+ 吨₂ = 一个₁ b ₁

然后将它们累加到256位结果中(在进行添加时观察溢出!):

c ^ = 吨₁ μ ³ +(吨₂ + 小号₁ + - [R ₁)μ ² +(小号₂ + - [R ₂ + q ₁)μ+ q ₂

Answer 2

像往常一样,询问编译器如何有效地执行某些操作:64位平台上的GNU C支持__int128_t和__uint128_t.

__uint128_t mul128(__uint128_t a, __uint128_t b) { return a*b; }

汇编到(Godbolt -O3上的gcc6.2)

    imul    rsi, rdx        # tmp94, b
    mov     rax, rdi  # tmp93, a
    imul    rcx, rdi        # tmp95, a
    mul     rdx       # b
    add     rcx, rsi  # tmp96, tmp94
    add     rdx, rcx  #, tmp96
    ret

由于这是针对x86-64 System V调用约定,a因此在RSI:RDI中,而b在RCX:RDX中. 结果在RDX:RAX中返回.

非常漂亮,只需要一条MOV指令,因为gcc不需要a_upper*b_lower的高半结果,反之亦然.它可以用更快的2操作数形式的IMUL来破坏输入的高半部分,因为它们只使用一次.

通过-march=haswell启用BMI2,gcc使用MULX来避免一个MOV.

有时编译器输出并不完美,但通常一般策略是手动优化的良好起点.

当然,如果你真正想要的是C中的128位乘法,那么只需使用编译器的内置支持即可.这可以让优化器完成它的工作,通常比你在inline-asm中编写几个部分时提供更好的结果.(https://gcc.gnu.org/wiki/DontUseInlineAsm).