1 #ifdef __KERNEL__ 2 # include <linux/crush/hash.h> 3 #else 4 # include "hash.h" 5 #endif 6 7 /* 8 * Robert Jenkins' function for mixing 32-bit values 9 * http://burtleburtle.net/bob/hash/evahash.html 10 * a, b = random bits, c = input and output 11 */ 12 #define crush_hashmix(a, b, c) do { \ 13 a = a-b; a = a-c; a = a^(c>>13); \ 14 b = b-c; b = b-a; b = b^(a<<8); \ 15 c = c-a; c = c-b; c = c^(b>>13); \ 16 a = a-b; a = a-c; a = a^(c>>12); \ 17 b = b-c; b = b-a; b = b^(a<<16); \ 18 c = c-a; c = c-b; c = c^(b>>5); \ 19 a = a-b; a = a-c; a = a^(c>>3); \ 20 b = b-c; b = b-a; b = b^(a<<10); \ 21 c = c-a; c = c-b; c = c^(b>>15); \ 22 } while (0) 23 24 #define crush_hash_seed 1315423911 25 26 static __u32 crush_hash32_rjenkins1(__u32 a) 27 { 28 __u32 hash = crush_hash_seed ^ a; 29 __u32 b = a; 30 __u32 x = 231232; 31 __u32 y = 1232; 32 crush_hashmix(b, x, hash); 33 crush_hashmix(y, a, hash); 34 return hash; 35 } 36 37 static __u32 crush_hash32_rjenkins1_2(__u32 a, __u32 b) 38 { 39 __u32 hash = crush_hash_seed ^ a ^ b; 40 __u32 x = 231232; 41 __u32 y = 1232; 42 crush_hashmix(a, b, hash); 43 crush_hashmix(x, a, hash); 44 crush_hashmix(b, y, hash); 45 return hash; 46 } 47 48 static __u32 crush_hash32_rjenkins1_3(__u32 a, __u32 b, __u32 c) 49 { 50 __u32 hash = crush_hash_seed ^ a ^ b ^ c; 51 __u32 x = 231232; 52 __u32 y = 1232; 53 crush_hashmix(a, b, hash); 54 crush_hashmix(c, x, hash); 55 crush_hashmix(y, a, hash); 56 crush_hashmix(b, x, hash); 57 crush_hashmix(y, c, hash); 58 return hash; 59 } 60 61 static __u32 crush_hash32_rjenkins1_4(__u32 a, __u32 b, __u32 c, __u32 d) 62 { 63 __u32 hash = crush_hash_seed ^ a ^ b ^ c ^ d; 64 __u32 x = 231232; 65 __u32 y = 1232; 66 crush_hashmix(a, b, hash); 67 crush_hashmix(c, d, hash); 68 crush_hashmix(a, x, hash); 69 crush_hashmix(y, b, hash); 70 crush_hashmix(c, x, hash); 71 crush_hashmix(y, d, hash); 72 return hash; 73 } 74 75 static __u32 crush_hash32_rjenkins1_5(__u32 a, __u32 b, __u32 c, __u32 d, 76 __u32 e) 77 { 78 __u32 hash = crush_hash_seed ^ a ^ b ^ c ^ d ^ e; 79 __u32 x = 231232; 80 __u32 y = 1232; 81 crush_hashmix(a, b, hash); 82 crush_hashmix(c, d, hash); 83 crush_hashmix(e, x, hash); 84 crush_hashmix(y, a, hash); 85 crush_hashmix(b, x, hash); 86 crush_hashmix(y, c, hash); 87 crush_hashmix(d, x, hash); 88 crush_hashmix(y, e, hash); 89 return hash; 90 } 91 92 93 __u32 crush_hash32(int type, __u32 a) 94 { 95 switch (type) { 96 case CRUSH_HASH_RJENKINS1: 97 return crush_hash32_rjenkins1(a); 98 default: 99 return 0; 100 } 101 } 102 103 __u32 crush_hash32_2(int type, __u32 a, __u32 b) 104 { 105 switch (type) { 106 case CRUSH_HASH_RJENKINS1: 107 return crush_hash32_rjenkins1_2(a, b); 108 default: 109 return 0; 110 } 111 } 112 113 __u32 crush_hash32_3(int type, __u32 a, __u32 b, __u32 c) 114 { 115 switch (type) { 116 case CRUSH_HASH_RJENKINS1: 117 return crush_hash32_rjenkins1_3(a, b, c); 118 default: 119 return 0; 120 } 121 } 122 123 __u32 crush_hash32_4(int type, __u32 a, __u32 b, __u32 c, __u32 d) 124 { 125 switch (type) { 126 case CRUSH_HASH_RJENKINS1: 127 return crush_hash32_rjenkins1_4(a, b, c, d); 128 default: 129 return 0; 130 } 131 } 132 133 __u32 crush_hash32_5(int type, __u32 a, __u32 b, __u32 c, __u32 d, __u32 e) 134 { 135 switch (type) { 136 case CRUSH_HASH_RJENKINS1: 137 return crush_hash32_rjenkins1_5(a, b, c, d, e); 138 default: 139 return 0; 140 } 141 } 142 143 const char *crush_hash_name(int type) 144 { 145 switch (type) { 146 case CRUSH_HASH_RJENKINS1: 147 return "rjenkins1"; 148 default: 149 return "unknown"; 150 } 151 } 152