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