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) { 51 case 11: 52 c = c + ((__u32)k[10] << 24); 53 /* fall through */ 54 case 10: 55 c = c + ((__u32)k[9] << 16); 56 /* fall through */ 57 case 9: 58 c = c + ((__u32)k[8] << 8); 59 /* the first byte of c is reserved for the length */ 60 /* fall through */ 61 case 8: 62 b = b + ((__u32)k[7] << 24); 63 /* fall through */ 64 case 7: 65 b = b + ((__u32)k[6] << 16); 66 /* fall through */ 67 case 6: 68 b = b + ((__u32)k[5] << 8); 69 /* fall through */ 70 case 5: 71 b = b + k[4]; 72 /* fall through */ 73 case 4: 74 a = a + ((__u32)k[3] << 24); 75 /* fall through */ 76 case 3: 77 a = a + ((__u32)k[2] << 16); 78 /* fall through */ 79 case 2: 80 a = a + ((__u32)k[1] << 8); 81 /* fall through */ 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(s, len); 112 case CEPH_STR_HASH_RJENKINS: 113 return ceph_str_hash_rjenkins(s, 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