1 | |
2 | #include <linux/ceph/types.h> |
3 | #include <linux/module.h> |
4 | |
5 | /* |
6 | * Robert Jenkin's hash function. |
7 | * https://burtleburtle.net/bob/hash/evahash.html |
8 | * This is in the public domain. |
9 | */ |
10 | #define mix(a, b, c) \ |
11 | do { \ |
12 | a = a - b; a = a - c; a = a ^ (c >> 13); \ |
13 | b = b - c; b = b - a; b = b ^ (a << 8); \ |
14 | c = c - a; c = c - b; c = c ^ (b >> 13); \ |
15 | a = a - b; a = a - c; a = a ^ (c >> 12); \ |
16 | b = b - c; b = b - a; b = b ^ (a << 16); \ |
17 | c = c - a; c = c - b; c = c ^ (b >> 5); \ |
18 | a = a - b; a = a - c; a = a ^ (c >> 3); \ |
19 | b = b - c; b = b - a; b = b ^ (a << 10); \ |
20 | c = c - a; c = c - b; c = c ^ (b >> 15); \ |
21 | } while (0) |
22 | |
23 | unsigned int ceph_str_hash_rjenkins(const char *str, unsigned int length) |
24 | { |
25 | const unsigned char *k = (const unsigned char *)str; |
26 | __u32 a, b, c; /* the internal state */ |
27 | __u32 len; /* how many key bytes still need mixing */ |
28 | |
29 | /* Set up the internal state */ |
30 | len = length; |
31 | a = 0x9e3779b9; /* the golden ratio; an arbitrary value */ |
32 | b = a; |
33 | c = 0; /* variable initialization of internal state */ |
34 | |
35 | /* handle most of the key */ |
36 | while (len >= 12) { |
37 | a = a + (k[0] + ((__u32)k[1] << 8) + ((__u32)k[2] << 16) + |
38 | ((__u32)k[3] << 24)); |
39 | b = b + (k[4] + ((__u32)k[5] << 8) + ((__u32)k[6] << 16) + |
40 | ((__u32)k[7] << 24)); |
41 | c = c + (k[8] + ((__u32)k[9] << 8) + ((__u32)k[10] << 16) + |
42 | ((__u32)k[11] << 24)); |
43 | mix(a, b, c); |
44 | k = k + 12; |
45 | len = len - 12; |
46 | } |
47 | |
48 | /* handle the last 11 bytes */ |
49 | c = c + length; |
50 | switch (len) { |
51 | case 11: |
52 | c = c + ((__u32)k[10] << 24); |
53 | fallthrough; |
54 | case 10: |
55 | c = c + ((__u32)k[9] << 16); |
56 | fallthrough; |
57 | case 9: |
58 | c = c + ((__u32)k[8] << 8); |
59 | /* the first byte of c is reserved for the length */ |
60 | fallthrough; |
61 | case 8: |
62 | b = b + ((__u32)k[7] << 24); |
63 | fallthrough; |
64 | case 7: |
65 | b = b + ((__u32)k[6] << 16); |
66 | fallthrough; |
67 | case 6: |
68 | b = b + ((__u32)k[5] << 8); |
69 | fallthrough; |
70 | case 5: |
71 | b = b + k[4]; |
72 | fallthrough; |
73 | case 4: |
74 | a = a + ((__u32)k[3] << 24); |
75 | fallthrough; |
76 | case 3: |
77 | a = a + ((__u32)k[2] << 16); |
78 | fallthrough; |
79 | case 2: |
80 | a = a + ((__u32)k[1] << 8); |
81 | fallthrough; |
82 | case 1: |
83 | a = a + k[0]; |
84 | /* case 0: nothing left to add */ |
85 | } |
86 | mix(a, b, c); |
87 | |
88 | return c; |
89 | } |
90 | |
91 | /* |
92 | * linux dcache hash |
93 | */ |
94 | unsigned int ceph_str_hash_linux(const char *str, unsigned int length) |
95 | { |
96 | unsigned long hash = 0; |
97 | unsigned char c; |
98 | |
99 | while (length--) { |
100 | c = *str++; |
101 | hash = (hash + (c << 4) + (c >> 4)) * 11; |
102 | } |
103 | return hash; |
104 | } |
105 | |
106 | |
107 | unsigned int ceph_str_hash(int type, const char *s, unsigned int len) |
108 | { |
109 | switch (type) { |
110 | case CEPH_STR_HASH_LINUX: |
111 | return ceph_str_hash_linux(str: s, length: len); |
112 | case CEPH_STR_HASH_RJENKINS: |
113 | return ceph_str_hash_rjenkins(str: s, length: len); |
114 | default: |
115 | return -1; |
116 | } |
117 | } |
118 | EXPORT_SYMBOL(ceph_str_hash); |
119 | |
120 | const char *ceph_str_hash_name(int type) |
121 | { |
122 | switch (type) { |
123 | case CEPH_STR_HASH_LINUX: |
124 | return "linux" ; |
125 | case CEPH_STR_HASH_RJENKINS: |
126 | return "rjenkins" ; |
127 | default: |
128 | return "unknown" ; |
129 | } |
130 | } |
131 | EXPORT_SYMBOL(ceph_str_hash_name); |
132 | |