Sage Weil | 5ecc0a0 | 2009-10-06 11:31:11 -0700 | [diff] [blame^] | 1 | #ifndef _CRUSH_HASH_H |
| 2 | #define _CRUSH_HASH_H |
| 3 | |
| 4 | /* |
| 5 | * Robert Jenkins' function for mixing 32-bit values |
| 6 | * http://burtleburtle.net/bob/hash/evahash.html |
| 7 | * a, b = random bits, c = input and output |
| 8 | */ |
| 9 | #define crush_hashmix(a, b, c) do { \ |
| 10 | a = a-b; a = a-c; a = a^(c>>13); \ |
| 11 | b = b-c; b = b-a; b = b^(a<<8); \ |
| 12 | c = c-a; c = c-b; c = c^(b>>13); \ |
| 13 | a = a-b; a = a-c; a = a^(c>>12); \ |
| 14 | b = b-c; b = b-a; b = b^(a<<16); \ |
| 15 | c = c-a; c = c-b; c = c^(b>>5); \ |
| 16 | a = a-b; a = a-c; a = a^(c>>3); \ |
| 17 | b = b-c; b = b-a; b = b^(a<<10); \ |
| 18 | c = c-a; c = c-b; c = c^(b>>15); \ |
| 19 | } while (0) |
| 20 | |
| 21 | #define crush_hash_seed 1315423911 |
| 22 | |
| 23 | static inline __u32 crush_hash32(__u32 a) |
| 24 | { |
| 25 | __u32 hash = crush_hash_seed ^ a; |
| 26 | __u32 b = a; |
| 27 | __u32 x = 231232; |
| 28 | __u32 y = 1232; |
| 29 | crush_hashmix(b, x, hash); |
| 30 | crush_hashmix(y, a, hash); |
| 31 | return hash; |
| 32 | } |
| 33 | |
| 34 | static inline __u32 crush_hash32_2(__u32 a, __u32 b) |
| 35 | { |
| 36 | __u32 hash = crush_hash_seed ^ a ^ b; |
| 37 | __u32 x = 231232; |
| 38 | __u32 y = 1232; |
| 39 | crush_hashmix(a, b, hash); |
| 40 | crush_hashmix(x, a, hash); |
| 41 | crush_hashmix(b, y, hash); |
| 42 | return hash; |
| 43 | } |
| 44 | |
| 45 | static inline __u32 crush_hash32_3(__u32 a, __u32 b, __u32 c) |
| 46 | { |
| 47 | __u32 hash = crush_hash_seed ^ a ^ b ^ c; |
| 48 | __u32 x = 231232; |
| 49 | __u32 y = 1232; |
| 50 | crush_hashmix(a, b, hash); |
| 51 | crush_hashmix(c, x, hash); |
| 52 | crush_hashmix(y, a, hash); |
| 53 | crush_hashmix(b, x, hash); |
| 54 | crush_hashmix(y, c, hash); |
| 55 | return hash; |
| 56 | } |
| 57 | |
| 58 | static inline __u32 crush_hash32_4(__u32 a, __u32 b, __u32 c, |
| 59 | __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 inline __u32 crush_hash32_5(__u32 a, __u32 b, __u32 c, |
| 74 | __u32 d, __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 | #endif |