visual-c++ - _umul128 在 Windows 32 位上

Question

在 Visual C++ 中，_umul128 在面向 Windows 32 位时未定义。
面向 Win32 时如何将两个无符号 64 位整数相乘？
该解决方案只需要在面向 Windows 32 位的 Visual C++ 2017 上运行。

Answer 1

这个答案有一个版本的 xmrrig function来自针对 MSVC 32 位模式优化的另一个答案。 原始版本适用于其他编译器，尤其是 clang。

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

如果您需要更灵活的任意精度(更大的数字)，请参阅 GMPlib's low-level functions有 asm 实现，而不是试图用这个 __umul128 建立一个 256b 的乘法.但如果你确实需要这个，那么值得一试。坚持使用 C++ 可以实现使用 asm 无法实现的常量传播和 CSE 优化。

clang 编译这个没有大问题，实际上使用 adc对于所有带进位的加法(除了用 setc 指令保存的那个)。 MSVC 分支上的进位检查，只会产生讨厌的代码。 GCC 的工作也不是很好，有一些分支在进行。 (因为 gcc 不知道如何将 carry = sum < a 变成 adc ， gcc bug 79173 。)

IDK，如果 MSVC 或 gcc 支持 32 位模式下 64 位整数的任何带进位内在函数。 _addcarry_u64 generates poor code with gcc anyway (in 64-bit mode) ，但 ICC 可能没问题。关于 MSVC 的 IDK。

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

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

带有 clang 的好代码。 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 的例子)。