c - Arithmetic on a struct representing a large integer -

i've wrote implementation of murmur3 hash , have defined 128-bit keys hash128_t

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

i'm trying write own hashmap using these keys, i'm not sure how arithmetic struct nor number large. need modulo operations, on how treat these 2 blocks of memory 1 integer appreciated.

my modulo formula is

dividend - ((dividend/divisor) * divisor) 

the easiest thing can discard half of hash , modulo (simply using %) on other half.

the next simplest thing use existing bignum library.

if want use whole hash, though, need long division here. there number of ways this; here's 1 (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;      (int = 0; < 64; i++) {       accum = accum << 1 | (shift_buf >> 63);       shift_buf = shift_buf << 1;       if (accum & (~1lu << 63)) accum = accum % divisor;     }      return accum % divisor; } 

note break if divisor larger 2^63 - 1. fixing left exercise reader, various optimizations possible if can constrain divisor 32-bit space.