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