Arithmetic on a struct representing a large integer

Question

I've wrote an implementation of Murmur3 hash and have defined the 128-bit keys as hash128_t

typedef struct
{
    uint64_t p1;
    uint64_t p2;
} hash128_t;

I'm trying to write my own hashmap using these keys, but I'm not exactly sure how to do arithmetic with a struct nor a number this large. I need help specifically with modulo operations, but help on how to treat these two blocks of memory as one integer would be greatly appreciated.

My modulo formula is

Dividend - ((Dividend/Divisor) * Divisor)

Answer 1

The easiest thing you can do is to simply discard half of the hash and do modulo (simply using %) on the other half.

The next simplest thing to do is to use an existing bignum library.

If you want to use the whole hash, though, you need to do a long division here. There are a number of ways to actually do this; here's one (completely untested) method:

uint64_t big_modulo(hash128_t hash, uint64_t divisor) {
    uint64_t accum = hash.p1 % divisor;
    uint64_t shift_buf = hash.p2;

    for (int i = 0; i < 64; i++) {
      accum = accum << 1 | (shift_buf >> 63);
      shift_buf = shift_buf << 1;
      if (accum & (~1LU << 63)) accum = accum % divisor;
    }

    return accum % divisor;
}

Note that this will break if divisor is larger than 2^63 - 1. Fixing this is left as an exercise to the reader, as are various optimizations that are possible if you can constrain the divisor to a 32-bit space.