1 2 #include <linux/ceph/types.h> 3 #include <linux/module.h> 4 5 /* 6 * Robert Jenkin's hash function. 7 * http://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) { /* all the case statements fall through */ 51 case 11: 52 c = c + ((__u32)k[10] << 24); 53 case 10: 54 c = c + ((__u32)k[9] << 16); 55 case 9: 56 c = c + ((__u32)k[8] << 8); 57 /* the first byte of c is reserved for the length */ 58 case 8: 59 b = b + ((__u32)k[7] << 24); 60 case 7: 61 b = b + ((__u32)k[6] << 16); 62 case 6: 63 b = b + ((__u32)k[5] << 8); 64 case 5: 65 b = b + k[4]; 66 case 4: 67 a = a + ((__u32)k[3] << 24); 68 case 3: 69 a = a + ((__u32)k[2] << 16); 70 case 2: 71 a = a + ((__u32)k[1] << 8); 72 case 1: 73 a = a + k[0]; 74 /* case 0: nothing left to add */ 75 } 76 mix(a, b, c); 77 78 return c; 79 } 80 81 /* 82 * linux dcache hash 83 */ 84 unsigned int ceph_str_hash_linux(const char *str, unsigned int length) 85 { 86 unsigned long hash = 0; 87 unsigned char c; 88 89 while (length--) { 90 c = *str++; 91 hash = (hash + (c << 4) + (c >> 4)) * 11; 92 } 93 return hash; 94 } 95 96 97 unsigned int ceph_str_hash(int type, const char *s, unsigned int len) 98 { 99 switch (type) { 100 case CEPH_STR_HASH_LINUX: 101 return ceph_str_hash_linux(s, len); 102 case CEPH_STR_HASH_RJENKINS: 103 return ceph_str_hash_rjenkins(s, len); 104 default: 105 return -1; 106 } 107 } 108 EXPORT_SYMBOL(ceph_str_hash); 109 110 const char *ceph_str_hash_name(int type) 111 { 112 switch (type) { 113 case CEPH_STR_HASH_LINUX: 114 return "linux"; 115 case CEPH_STR_HASH_RJENKINS: 116 return "rjenkins"; 117 default: 118 return "unknown"; 119 } 120 } 121 EXPORT_SYMBOL(ceph_str_hash_name); 122