_umul128

Question

在Visual C++中，当针对Windows 32位时_umul128未定义。 针对Win32时，两个无符号64位整数如何相乘？ 该解决方案只需在针对Windows 32位的Visual C++ 2017上工作。

Answer 1

我发现下面的代码（从xmrrig），这似乎做的工作就好了：

static inline uint64_t __umul128(uint64_t multiplier, uint64_t multiplicand, 
    uint64_t *product_hi) 
{ 
    // multiplier = ab = a * 2^32 + b 
    // multiplicand = cd = c * 2^32 + d 
    // ab * cd = a * c * 2^64 + (a * d + b * c) * 2^32 + b * d 
    uint64_t a = multiplier >> 32; 
    uint64_t b = multiplier & 0xFFFFFFFF; 
    uint64_t c = multiplicand >> 32; 
    uint64_t d = multiplicand & 0xFFFFFFFF; 

    //uint64_t ac = a * c; 
    uint64_t ad = a * d; 
    //uint64_t bc = b * c; 
    uint64_t bd = b * d; 

    uint64_t adbc = ad + (b * c); 
    uint64_t adbc_carry = adbc < ad ? 1 : 0; 

    // multiplier * multiplicand = product_hi * 2^64 + product_lo 
    uint64_t product_lo = bd + (adbc << 32); 
    uint64_t product_lo_carry = product_lo < bd ? 1 : 0; 
    *product_hi = (a * c) + (adbc >> 32) + (adbc_carry << 32) + product_lo_carry; 

    return product_lo; 
} 

Answer 2

这个答案已经从MSVC 32位模式优化了对方的回答某个版本的xmrrig function的。原始版本与其他编译器，特别是铿锵有关。

---

我看着@ Augusto的功能MSVC的输出，它真的很糟糕。 对于32x32 => 64b乘法使用__emulu明显改善了它（因为MSVC是愚蠢的，并且在已知输入实际上仅为32位且上半部分为零的情况下不优化uint64_t * uint64_t = uint64_t）。其他编译器（gcc和clang）生成一个单一的mul指令，而不是调用辅助函数。 MSVC的代码还有其他问题，我不知道如何通过调整源代码来修复，尽管。我认为，如果你想在该编译器上获得良好的性能，那么必须使用内联asm（或单独编译的asm函数）。

如果您需要更灵活的任意精度（更大的数字），请参阅GMPlib's low-level functions，它们有asm实现，而不是尝试从此__umul128中构建256b乘法。但如果你确切需要这个，那么值得尝试。使用C++支持恒定传播和CSE优化，您不会用asm获得。

---

铛编译此没有大的问题，实际使用adc所有附加有进位（除了一个，它与setc指令保存）。 MSVC在进位检查上分支，并且只是产生令人讨厌的代码。海湾合作委员会也没有做得很好，有一些分支随身携带。 （因为gcc不知道如何把carry = sum < a成adc，gcc bug 79173。）

IDK如果MSVC或GCC支持任何附加与携带的用于在32位模式的64位整数内部函数。 _addcarry_u64generates poor code with gcc anyway (in 64-bit mode)，但ICC可能会好。 IDK关于MSVC。

如果你想要一个asm实现，我建议使用这个函数的铿锵5.0的输出。你可能手工找到一些优化，但肯定比MSVC更好。但当然，https://gcc.gnu.org/wiki/DontUseInlineAsm中的大部分参数都适用：如果乘以内联变为常数的内容，或者上半部分已知为零，则阻塞恒定传播是一个主要问题。

Source + asm output for MSVC 32-bit and clang5.0 32-bit on Godbolt

漂亮的代码铿锵。有点不好的代码与MSVC，但比以前更好。有点不好与gcc也（没有改变与其他答案）。

#include <stdint.h> 

#ifdef _MSC_VER 
# include <intrin.h> 
#else 
// MSVC doesn't optimize 32x32 => 64b multiplication without its intrinsic 
// But good compilers can just use this to get a single mul instruction 
static inline 
uint64_t __emulu(uint32_t x, uint32_t y) { 
    return x * (uint64_t)y; 
} 
#endif 

// This is still pretty ugly with MSVC, branching on the carry 
// and using XMM store/integer reload to zero a register! 
// But at least it inlines 4 mul instructions 
// instead of calling a generic 64x64 => 64b multiply helper function 
uint64_t __umul128(uint64_t multiplier, uint64_t multiplicand, 
    uint64_t *product_hi) 
{ 
    // multiplier = ab = a * 2^32 + b 
    // multiplicand = cd = c * 2^32 + d 
    // ab * cd = a * c * 2^64 + (a * d + b * c) * 2^32 + b * d 
    uint64_t a = multiplier >> 32; 
    uint64_t b = (uint32_t)multiplier; // & 0xFFFFFFFF; 
    uint64_t c = multiplicand >> 32; 
    uint64_t d = (uint32_t)multiplicand; // & 0xFFFFFFFF; 

    //uint64_t ac = __emulu(a, c); 
    uint64_t ad = __emulu(a, d); 
    //uint64_t bc = __emulu(b, c); 
    uint64_t bd = __emulu(b, d); 

    uint64_t adbc = ad + __emulu(b , c); 
    uint64_t adbc_carry = (adbc < ad); // ? 1 : 0; 
    // MSVC gets confused by the ternary and makes worse code than using a boolean in an integer context for 1 : 0 

    // multiplier * multiplicand = product_hi * 2^64 + product_lo 
    uint64_t product_lo = bd + (adbc << 32); 
    uint64_t product_lo_carry = (product_lo < bd); // ? 1 : 0; 
    *product_hi = __emulu(a , c) + (adbc >> 32) + (adbc_carry << 32) + product_lo_carry; 

    return product_lo; 
} 

请确保您只在32位代码中使用它。在64位代码中，它无法优化到单个64位mul指令（这会产生全部结果的64位二分之一）。实现GNU C++扩展的编译器（clang，gcc，ICC）可以使用unsigned __int128并获得很好的代码。例如a * (unsigned __int128)b产生128b结果。 （Godbolt示例）。