include/hamt/hamt_hash.h

filter: Statementstmt 100% 27 / 27 Branchbran 100% 10 / 10 Conditioncond n/a MC/DCmcdc n/a Subroutinesub n/a Podpod n/a totaltotal 100% 37 / 37 CC 0 SCAR 0
CC
0
Cov
0%
CRAP 0
« blib/lib/HAMT/Vector/Transient.pm ↑ Summary include/hamt/hamt_iter.h »
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
BranchTrueFalseTotal
if (utf8) h ^= HAMT_M2; 53 2026702 2026755
36  
37 2108722 ▶ while (len - i >= 8) {
Branch: 1 branch
BranchTrueFalseTotal
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
BranchTrueFalseTotal
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
BranchTrueFalseTotal
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
BranchTrueFalseTotal
hamt_hash_mask = bits >= 64 ? ~(uint64_t)0 : (((uint64_t)1 << bits) - 1); 23 23 46
69 46 }
70  
71 #endif
« blib/lib/HAMT/Vector/Transient.pm ↑ Summary include/hamt/hamt_iter.h »