ktest: Add minor fixes for kernel tests
[akaros.git] / kern / include / hash.h
1 /* Fast hashing routine for ints,  longs and pointers.
2    (C) 2002 Nadia Yvette Chambers, IBM */
3
4 /* This file came from Linux, 4.6.
5  * This source code is licensed under the GNU General Public License
6  * Version 2. See the file COPYING for more details. */
7
8 #pragma once
9
10 /*
11  * Knuth recommends primes in approximately golden ratio to the maximum
12  * integer representable by a machine word for multiplicative hashing.
13  * Chuck Lever verified the effectiveness of this technique:
14  * http://www.citi.umich.edu/techreports/reports/citi-tr-00-1.pdf
15  *
16  * These primes are chosen to be bit-sparse, that is operations on
17  * them can use shifts and additions instead of multiplications for
18  * machines where multiplications are slow.
19  */
20
21 #include <arch/types.h>
22 #include <compiler.h>
23
24 /* 2^31 + 2^29 - 2^25 + 2^22 - 2^19 - 2^16 + 1 */
25 #define GOLDEN_RATIO_PRIME_32 0x9e370001UL
26 /*  2^63 + 2^61 - 2^57 + 2^54 - 2^51 - 2^18 + 1 */
27 #define GOLDEN_RATIO_PRIME_64 0x9e37fffffffc0001UL
28
29 #if BITS_PER_LONG == 32
30 #define GOLDEN_RATIO_PRIME GOLDEN_RATIO_PRIME_32
31 #define hash_long(val, bits) hash_32(val, bits)
32 #elif BITS_PER_LONG == 64
33 #define hash_long(val, bits) hash_64(val, bits)
34 #define GOLDEN_RATIO_PRIME GOLDEN_RATIO_PRIME_64
35 #else
36 #error Wordsize not 32 or 64
37 #endif
38
39 /*
40  * The above primes are actively bad for hashing, since they are
41  * too sparse. The 32-bit one is mostly ok, the 64-bit one causes
42  * real problems. Besides, the "prime" part is pointless for the
43  * multiplicative hash.
44  *
45  * Although a random odd number will do, it turns out that the golden
46  * ratio phi = (sqrt(5)-1)/2, or its negative, has particularly nice
47  * properties.
48  *
49  * These are the negative, (1 - phi) = (phi^2) = (3 - sqrt(5))/2.
50  * (See Knuth vol 3, section 6.4, exercise 9.)
51  */
52 #define GOLDEN_RATIO_32 0x61C88647
53 #define GOLDEN_RATIO_64 0x61C8864680B583EBull
54
55 static __always_inline uint64_t hash_64(uint64_t val, unsigned int bits)
56 {
57         uint64_t hash = val;
58
59 #if BITS_PER_LONG == 64
60         hash = hash * GOLDEN_RATIO_64;
61 #else
62         /*  Sigh, gcc can't optimise this alone like it does for 32 bits. */
63         uint64_t n = hash;
64         n <<= 18;
65         hash -= n;
66         n <<= 33;
67         hash -= n;
68         n <<= 3;
69         hash += n;
70         n <<= 3;
71         hash -= n;
72         n <<= 4;
73         hash += n;
74         n <<= 2;
75         hash += n;
76 #endif
77
78         /* High bits are more random, so use them. */
79         return hash >> (64 - bits);
80 }
81
82 static inline uint32_t hash_32(uint32_t val, unsigned int bits)
83 {
84         /* On some cpus multiply is faster, on others gcc will do shifts */
85         uint32_t hash = val * GOLDEN_RATIO_PRIME_32;
86
87         /* High bits are more random, so use them. */
88         return hash >> (32 - bits);
89 }
90
91 static inline unsigned long hash_ptr(const void *ptr, unsigned int bits)
92 {
93         return hash_long((unsigned long)ptr, bits);
94 }
95
96 static inline uint32_t hash32_ptr(const void *ptr)
97 {
98         unsigned long val = (unsigned long)ptr;
99
100 #if BITS_PER_LONG == 64
101         val ^= (val >> 32);
102 #endif
103         return (uint32_t)val;
104 }