| 1 |
|
| #ifndef HAMT_HASH_H |
| 2 |
|
| #define HAMT_HASH_H |
| 3 |
|
| |
| 4 |
|
| /* The hash a key's position in the trie is read from: 64 bits over the key's |
| 5 |
|
| * bytes, with a per-process seed. |
| 6 |
|
| * |
| 7 |
|
| * Seeded because a map will be keyed by somebody else's data sooner or |
| 8 |
|
| * later, and with a fixed hash a client can choose keys that all share one |
| 9 |
|
| * path. This is not a cryptographic hash and the seed is not a secret worth |
| 10 |
|
| * much; it is enough that the layout cannot be computed from outside. |
| 11 |
|
| * |
| 12 |
|
| * The body is Frozen's fz_hash with a 64-bit seed. It reads the key eight |
| 13 |
|
| * bytes at a time in host order, so the same key hashes differently on a |
| 14 |
|
| * machine of the other endianness - which is fine, because nothing built |
| 15 |
|
| * from it ever leaves the process. */ |
| 16 |
|
| |
| 17 |
|
| #define HAMT_M1 0xff51afd7ed558ccdULL |
| 18 |
|
| #define HAMT_M2 0xc4ceb9fe1a85ec53ULL |
| 19 |
|
| #define HAMT_M3 0x9e3779b97f4a7c15ULL |
| 20 |
|
| |
| 21 |
|
| /* Set once when the library loads. The mask is all ones outside the tests, |
| 22 |
|
| * which narrow it to force keys onto shared paths and into collision nodes. */ |
| 23 |
|
| static uint64_t hamt_seed = 0; |
| 24 |
|
| static uint64_t hamt_hash_mask = ~(uint64_t)0; |
| 25 |
|
| |
| 26 |
|
| /* `utf8` is part of the key: the caller has already downgraded every key |
| 27 |
|
| * that can be, so two keys with equal bytes and different flags are |
| 28 |
|
| * different strings. Folding the flag in keeps them off each other's path |
| 29 |
|
| * instead of leaving them to a full comparison at the end of it. */ |
| 30 |
2026755 |
| static uint64_t hamt_hash(const char *s, size_t len, int utf8) { |
| 31 |
2026755 |
| const unsigned char *p = (const unsigned char *)s; |
| 32 |
2026755 |
| uint64_t h = HAMT_M3 ^ (hamt_seed * HAMT_M1) ^ (uint64_t)len; |
| 33 |
2026755 |
| size_t i = 0; |
| 34 |
|
| |
| 35 |
2026755 |
▶ | if (utf8) h ^= HAMT_M2; |
Branch: 1 branch
| Branch | True | False | Total |
| if (utf8) h ^= HAMT_M2; |
53 |
2026702 |
2026755 |
|
| 36 |
|
| |
| 37 |
2108722 |
▶ | while (len - i >= 8) { |
Branch: 1 branch
| Branch | True | False | Total |
| while (len - i >= 8) { |
81967 |
2026755 |
2108722 |
|
| 38 |
|
| uint64_t k; |
| 39 |
81967 |
| memcpy(&k, p + i, 8); |
| 40 |
81967 |
| k *= HAMT_M1; |
| 41 |
81967 |
| k ^= k >> 33; |
| 42 |
81967 |
| h ^= k; |
| 43 |
81967 |
| h *= HAMT_M2; |
| 44 |
81967 |
| i += 8; |
| 45 |
|
| } |
| 46 |
2026755 |
▶ | if (i < len) { |
Branch: 1 branch
| Branch | True | False | Total |
| if (i < len) { |
2026376 |
379 |
2026755 |
|
| 47 |
|
| /* Byte by byte: a copy of a length not known until run time is a |
| 48 |
|
| * call into the C library, and most keys are all tail. */ |
| 49 |
2026376 |
| uint64_t k = 0; |
| 50 |
2026376 |
| size_t j, r = len - i; |
| 51 |
10677275 |
▶ | for (j = 0; j < r; j++) k |= (uint64_t)p[i + j] << (8 * j); |
Branch: 1 branch
| Branch | True | False | Total |
| for (j = 0; j < r; j++) k |= (uint64_t)p[i + j] << (8 * j); |
8650899 |
2026376 |
10677275 |
|
| 52 |
2026376 |
| k *= HAMT_M1; |
| 53 |
2026376 |
| k ^= k >> 33; |
| 54 |
2026376 |
| h ^= k; |
| 55 |
2026376 |
| h *= HAMT_M2; |
| 56 |
|
| } |
| 57 |
|
| |
| 58 |
2026755 |
| h ^= h >> 33; |
| 59 |
2026755 |
| h *= HAMT_M1; |
| 60 |
2026755 |
| h ^= h >> 29; |
| 61 |
2026755 |
| return h & hamt_hash_mask; |
| 62 |
|
| } |
| 63 |
|
| |
| 64 |
|
| /* Keep the low `bits` bits of every hash from here on. 64 or more restores |
| 65 |
|
| * the whole of it. A container built under one setting must not be read |
| 66 |
|
| * under another. */ |
| 67 |
46 |
| static void hamt_hash_set_bits(unsigned bits) { |
| 68 |
46 |
▶ | hamt_hash_mask = bits >= 64 ? ~(uint64_t)0 : (((uint64_t)1 << bits) - 1); |
Branch: 1 branch
| Branch | True | False | Total |
| hamt_hash_mask = bits >= 64 ? ~(uint64_t)0 : (((uint64_t)1 << bits) - 1); |
23 |
23 |
46 |
|
| 69 |
46 |
| } |
| 70 |
|
| |
| 71 |
|
| #endif |