Immer der hohe Teil des 64-bit-integer-Multiplikation

Dies ist ein unit-getestete version, die ich kam mit heute Abend, stellt die vollständige 128-bit-Produkt. Bei der Inspektion es scheint einfacher, als die meisten anderen online-Lösungen (in z.B. Botan-Bibliothek und anderen Antworten hier), weil es nutzt, wie der MITTLERE TEIL nicht überlaufen, wie in den Kommentaren im code.

Kontext ich es geschrieben habe für dieses github-Projekt: https://github.com/catid/fp61

//------------------------------------------------------------------------------
//Portability Macros

//Compiler-specific force inline keyword
#ifdef _MSC_VER
# define FP61_FORCE_INLINE inline __forceinline
#else
# define FP61_FORCE_INLINE inline __attribute__((always_inline))
#endif


//------------------------------------------------------------------------------
//Portable 64x64->128 Multiply
//CAT_MUL128: r{hi,lo} = x * y

//Returns low part of product, and high part is set in r_hi
FP61_FORCE_INLINE uint64_t Emulate64x64to128(
    uint64_t& r_hi,
    const uint64_t x,
    const uint64_t y)
{
    const uint64_t x0 = (uint32_t)x, x1 = x >> 32;
    const uint64_t y0 = (uint32_t)y, y1 = y >> 32;
    const uint64_t p11 = x1 * y1, p01 = x0 * y1;
    const uint64_t p10 = x1 * y0, p00 = x0 * y0;
    /*
        This is implementing schoolbook multiplication:

                x1 x0
        X       y1 y0
        -------------
                   00  LOW PART
        -------------
                00
             10 10     MIDDLE PART
        +       01
        -------------
             01 
        + 11 11        HIGH PART
        -------------
    */

    //64-bit product + two 32-bit values
    const uint64_t middle = p10 + (p00 >> 32) + (uint32_t)p01;

    /*
        Proof that 64-bit products can accumulate two more 32-bit values
        without overflowing:

        Max 32-bit value is 2^32 - 1.
        PSum = (2^32-1) * (2^32-1) + (2^32-1) + (2^32-1)
             = 2^64 - 2^32 - 2^32 + 1 + 2^32 - 1 + 2^32 - 1
             = 2^64 - 1
        Therefore it cannot overflow regardless of input.
    */

    //64-bit product + two 32-bit values
    r_hi = p11 + (middle >> 32) + (p01 >> 32);

    //Add LOW PART and lower half of MIDDLE PART
    return (middle << 32) | (uint32_t)p00;
}

#if defined(_MSC_VER) && defined(_WIN64)
//Visual Studio 64-bit

# include <intrin.h>
# pragma intrinsic(_umul128)
# define CAT_MUL128(r_hi, r_lo, x, y) \
    r_lo = _umul128(x, y, &(r_hi));

#elif defined(__SIZEOF_INT128__)
//Compiler supporting 128-bit values (GCC/Clang)

# define CAT_MUL128(r_hi, r_lo, x, y)                   \
    {                                                   \
        unsigned __int128 w = (unsigned __int128)x * y; \
        r_lo = (uint64_t)w;                             \
        r_hi = (uint64_t)(w >> 64);                     \
    }

#else
//Emulate 64x64->128-bit multiply with 64x64->64 operations

# define CAT_MUL128(r_hi, r_lo, x, y) \
    r_lo = Emulate64x64to128(r_hi, x, y);

#endif //End CAT_MUL128

TL:DR mit GCC für 64-bit-ISA: (a * (unsigned __int128)b) >> 64 kompiliert schön, zu einem ganzen zu multiplizieren oder zu hoch-die Hälfte multiply-Anweisung. Keine Notwendigkeit, mess around mit inline-asm.

Leider aktuellen Compilern nicht optimieren @craigster0 ist schön portable version, also, wenn Sie möchten, um die Vorteile von 64-bit-CPUs, Sie können es nicht verwenden, außer als fallback für Ziele, die Sie nicht haben eine #ifdef für. (Ich sehe nicht, eine generische Art und Weise zu optimieren; Sie müssen einer 128-bit-Typ oder einer systeminternen.)

GNU C (gcc, clang, ICC) hat unsigned __int128 auf den meisten 64-bit-Plattformen. (Oder in älteren Versionen __uint128_t). GCC nicht implementieren dieses Typs auf 32-bit-Plattformen, obwohl.

Dies ist ein einfacher und effizienter Weg, um den compiler zu emittieren, die eine 64-bit-voll-multiply-Anweisung und halten Sie die Obere Hälfte. (GCC weiß, dass ein uint64_t Besetzung einer 128-bit-integer hat immer noch die Obere Hälfte, die alle null sind, so dass Sie nicht bekommen, eine 128-bit-multiplizieren mit drei 64-bit multipliziert.)

MSVC hat auch eine __umulh intrinsische für 64-bit-high-Hälfte Multiplikation, aber wieder, es ist nur verfügbar auf 64-bit-Plattformen (insbesondere x86-64 und AArch64. Die docs auch erwähnen, IPF (IA-64) mit _umul128 erhältlich, aber ich habe nicht MSVC für Itanium verfügbar. (Wahrscheinlich sowieso nicht relevant.)

#define HAVE_FAST_mul64 1

#ifdef __SIZEOF_INT128__     //GNU C
 static inline
 uint64_t mulhi64(uint64_t a, uint64_t b) {
     unsigned __int128 prod =  a * (unsigned __int128)b;
     return prod >> 64;
 }

#elif defined(_M_X64) || defined(_M_ARM64)     //MSVC
   //MSVC for x86-64 or AArch64
   //possibly also  || defined(_M_IA64) || defined(_WIN64)
   //but the docs only guarantee x86-64!  Don't use *just* _WIN64; it doesn't include AArch64 Android /Linux

  //https://docs.microsoft.com/en-gb/cpp/intrinsics/umulh
  #include <intrin.h>
  #define mulhi64 __umulh

#elif defined(_M_IA64) //|| defined(_M_ARM)       //MSVC again
  //https://docs.microsoft.com/en-gb/cpp/intrinsics/umul128
  //incorrectly say that _umul128 is available for ARM
  //which would be weird because there's no single insn on AArch32
  #include <intrin.h>
  static inline
  uint64_t mulhi64(uint64_t a, uint64_t b) {
     unsigned __int64 HighProduct;
     (void)_umul128(a, b, &HighProduct);
     return HighProduct;
  }

#else

# undef HAVE_FAST_mul64
  uint64_t mulhi64(uint64_t a, uint64_t b);  //non-inline prototype
  //or you might want to define @craigster0's version here so it can inline.
#endif

Für x86-64, AArch64 und PowerPC64 (und andere), dies stellt an eine mul Unterricht, und ein paar movs Umgang mit der Aufrufkonvention (die optimieren der Weg nach dieser inlines).
Von die Godbolt compiler explorer (mit Quelle + asm für x86-64, PowerPC64, und AArch64):

     # x86-64 gcc7.3.  clang and ICC are the same.  (x86-64 System V calling convention)
     # MSVC makes basically the same function, but with different regs for x64 __fastcall
    mov     rax, rsi
    mul     rdi              # RDX:RAX = RAX * RDI
    mov     rax, rdx
    ret

(oder mit clang -march=haswell zu ermöglichen, BMI2: mov rdx, rsi /mulx rax, rcx, rdi um die high-Hälfte in RAX direkt. gcc ist dumm und nutzt noch eine zusätzliche mov.)

Für AArch64 (mit gcc unsigned __int128 oder MSVC mit __umulh):

test_var:
    umulh   x0, x0, x1
    ret

Mit einer compile-Zeit-Konstante Leistung von 2 Multiplikator, wir in der Regel die erwarteten rechts-shift zu greifen, ein paar high-bits. Aber gcc lustig verwendet shld (siehe Godbolt link).

Leider aktuellen Compilern nicht optimieren @craigster0 ist schön portable version. Sie bekommen 8x shr r64,32, 4x imul r64,r64, und eine Reihe von add/mov Anweisungen für x86-64. d.h. es kompiliert eine Menge von 32x32 => 64-bit multipliziert und entpackt die Ergebnisse. Also, wenn Sie etwas wollen, die die Vorteile von 64-bit-CPUs, müssen Sie einige #ifdefs.

Full-multiplizieren mul 64 Anleitung ist 2 uops auf Intel-Prozessoren, aber immer noch nur 3-Zyklus-Latenz, wie imul r64,r64 das erzeugt nur eine 64-bit-Ergebnis. Also die __int128 /innere-version ist 5-bis 10-mal günstiger in die Latenz und der Durchsatz (Auswirkungen auf die umliegenden code) auf modernen x86-64 als die portable version, von einem schnellen Augapfel Vermutung basiert auf http://agner.org/optimize/.

Check it out auf der Godbolt compiler-explorer auf den obigen link.

gcc nicht vollständig optimieren Sie diese Funktion bei der Multiplikation mit 16, aber: Sie bekommen einen einzigen shift rechts, effizienter als mit unsigned __int128 multiplizieren.