Spaces:
Sleeping
Sleeping
| // MurmurHash3 32-bit implementation | |
| // Fast non-cryptographic hash function for hash tables | |
| uint32_t rotl32(uint32_t x, int8_t r) { | |
| return (x << r) | (x >> (32 - r)); | |
| } | |
| uint32_t murmur3_32(const uint8_t *key, size_t len, uint32_t seed) { | |
| uint32_t h = seed; | |
| const int nblocks = len / 4; | |
| const uint32_t c1 = 0xcc9e2d51; | |
| const uint32_t c2 = 0x1b873593; | |
| // Body | |
| const uint32_t *blocks = (const uint32_t *)(key); | |
| for (int i = 0; i < nblocks; i++) { | |
| uint32_t k1 = blocks[i]; | |
| k1 *= c1; | |
| k1 = rotl32(k1, 15); | |
| k1 *= c2; | |
| h ^= k1; | |
| h = rotl32(h, 13); | |
| h = h * 5 + 0xe6546b64; | |
| } | |
| // Tail | |
| const uint8_t *tail = key + nblocks * 4; | |
| uint32_t k1 = 0; | |
| switch (len & 3) { | |
| case 3: k1 ^= tail[2] << 16; | |
| case 2: k1 ^= tail[1] << 8; | |
| case 1: k1 ^= tail[0]; | |
| k1 *= c1; | |
| k1 = rotl32(k1, 15); | |
| k1 *= c2; | |
| h ^= k1; | |
| } | |
| // Finalization | |
| h ^= len; | |
| h ^= h >> 16; | |
| h *= 0x85ebca6b; | |
| h ^= h >> 13; | |
| h *= 0xc2b2ae35; | |
| h ^= h >> 16; | |
| return h; | |
| } | |
| void generate_key(uint8_t *key, int len, int seed) { | |
| for (int i = 0; i < len; i++) { | |
| seed = seed * 1103515245 + 12345; | |
| key[i] = seed & 0xFF; | |
| } | |
| } | |
| int main() { | |
| uint8_t **keys = (uint8_t**)malloc(NUM_KEYS * sizeof(uint8_t*)); | |
| for (int i = 0; i < NUM_KEYS; i++) { | |
| keys[i] = (uint8_t*)malloc(KEY_LEN); | |
| generate_key(keys[i], KEY_LEN, i); | |
| } | |
| clock_t start = clock(); | |
| uint32_t hash_sum = 0; | |
| for (int iter = 0; iter < 10; iter++) { | |
| for (int i = 0; i < NUM_KEYS; i++) { | |
| hash_sum ^= murmur3_32(keys[i], KEY_LEN, 42); | |
| } | |
| } | |
| clock_t end = clock(); | |
| double time_spent = (double)(end - start) / CLOCKS_PER_SEC; | |
| printf("MurmurHash3: %d keys, 10 iterations, %.6f seconds\n", | |
| NUM_KEYS, time_spent); | |
| printf("Hash XOR sum: 0x%08X\n", hash_sum); | |
| for (int i = 0; i < NUM_KEYS; i++) { | |
| free(keys[i]); | |
| } | |
| free(keys); | |
| return 0; | |
| } | |