Multiplication modulo 2^64-257

benchmark_mult_modp.c

#include <stdio.h>
#include <stdint.h>
#include <assert.h>

int main() {
    uint64_t a = 0x6dc06dabb8fb11a7ull;
    uint64_t b = 0x661f975dc51abe17ull;
    // uint64_t a = 1ull << 63;
    // uint64_t b = 1ull << 63;

    for (int i = 0; i < 1000 * 1000 * 1000; i++) {
        __uint128_t v = a * (__uint128_t)b;
        uint64_t hi, lo;

        #if 0
            // almost nothing (ensure hi is used)
            a = (v >> 64) ^ v;
        #endif
        #if 0
            // basic muls, slightly optimised (4.1s)
            hi = v >> 64;
            lo = v;
            v = lo + hi * (__uint128_t)257;

            hi = v >> 64;
            lo = v;
            v = lo + (__uint128_t)(hi * 257);

            // hi = v >> 64;
            // lo = v;
            // a = lo + hi * (__uint128_t)257;

            a = v;
            if (v >> 64)
                a+= 257;
        #endif
        #if 1
            // shift-based (3.9s)
            hi = v >> 64;
            lo = v;
            v = lo + (__uint128_t)hi + ((__uint128_t)(hi) << 8);

            uint32_t hii = v >> 64; // 9 bits max?
            v = (uint64_t)v;
            v += hii + (hii << 8);

            a = v;
            if (v >> 64)
                a += 257;
        #endif
    }
    printf("%016llx\n", a); // 0f01d820a8943349

    return 0;
}