在加宽 128 位乘法中计算高 64 位的便携式实现

Question

如何实现两个 64 位数字的有符号和无符号乘法，扩展为 128 位，并丢弃低 64 位，返回高 64 位？乘法必须根据二进制补码正确换行，而不会表现出未定义的行为。

#include <stdint.h>

int64_t imul128hi(int64_t lhs, int64_t rhs);
uint64_t mul128hi(uint64_t lhs, uint64_t rhs);

需要具有

stdint.h

的简单便携式 C，没有不合理的

__builtin

本质。我将此代码用作 WASM JIT 编译器输出中的存根。请不要使用

((uint128_t)x * y) >> 64

。这里的目标是模拟

imul

和

mul

指令。

# printf '\x49\xf7\xe8' | ndisasm -b 64 -
00000000  49F7E8            imul r8
# printf '\x49\xf7\xe0' | ndisasm -b 64 -
00000000  49F7E0            mul r8

Answer 1

回到长手乘法...这次以 2^32 为底

     a    b
x    c    d
-----------
    ad   bd
ac  bc
-----------
ac ad+bc bd

--

uint64_t mul128hi(uint64_t lhs, uint64_t rhs) {
    uint64_t bd = (lhs & 0xffffffff) * (rhs & 0xffffffff);
    uint64_t ad = (lhs >> 32) * (rhs & 0xffffffff);
    uint64_t bc = (lhs & 0xffffffff) * (rhs >> 32);
    uint64_t ac = (lhs >> 32) * (rhs >> 32);
    uint64_t ad_plus_bc = ad + bc + (bd >> 32); // ad + bc + carry
    return ac + (ad_plus_bc >> 32);             // ac + carry
}