32位整数乘法指令实现64位乘法

思路就是将64位数分解为两个32位数

(AB) * (CD) = A*C * (1<<64) + ( A*D + B*C )*(1<<32) +  B*D

由于计算结果也用64位数保存, 所以A*C可以丢弃了, 不用做这多余的计算, 总共需要3次32位乘法

具体实现如下(同样适用于int64_t):

#include <stdint.h>

typedef union {
    uint64_t qword;
    struct {
        int low;
        int high;
    } ddword;
} ii_t;

uint64_t mul(uint64_t a, uint64_t b) {
    ii_t x = (ii_t)a, y = (ii_t)b;
    __asm__(
            "movl   %0, %%ecxnt"
            "imull  %3, %%ecxnt"
            "movl   %2, %%eaxnt"
            "mull   %1nt"
            "addl   %%eax, %%ecxnt"
            "movl   %3, %%eaxnt"
            "mull   %1nt"
            "addl   %%ecx, %%edxnt"
            :"=m"(x.ddword.high),
            "=m"(x.ddword.low),
            "=m"(y.ddword.high),
            "=m"(y.ddword.low)
            );
}

其中第15, 17, 20行总共使用3次乘法指令 , 前两个对应的是A*D和B*C, 最后一个对应B*D

32位Windows和Linux都使用edx:eax保存64位返回值

将(A*D+B*C)截断的值与B*D进位的和, 保存在edx中, B*D的32位截断值保存在eax中

因为无符号乘法和补码乘法的截断结果一致, A*D和B*C的进位也可以丢弃, 所以这两次乘法使用mull和imull均可

而计算B*D的进位需要保存, 所以必须使用mull指令, imull会得到错误的进位