hash.c

#include <stdint.h>

static uint32_t mul (uint32_t x1, uint32_t x2, uint32_t m) {
	return ((uint64_t)x1 * (uint64_t)x2) % m;
}

static uint32_t pow (uint32_t b, uint32_t e, uint32_t m) {
	if (e == 0) return 1;
	uint32_t f = 1;
	// invariant: f*b^e
	while (e > 1) {
		if (e % 2 == 0) {
			b = mul (b, b, m);
			e /= 2;
		}
		else {
			f = mul (f, b, m);
			e -= 1;
		}
	}
	return mul (f, b, m);
}

uint32_t hash (uint32_t a, uint32_t b) {
	return mul (pow(0xF000,a,0xC0000001), pow(0x10000,b,0xC0000001), 0xC0000001) - 1;
}

uint32_t hash_string (const char *s) {
	uint32_t result = 0;
	while (*s != '\0') {
		result = hash (*s, result);
		++s;
	}
	return result;
}