From eaf39b2a9c010ec662bf9517cba8e6a87a75f8e3 Mon Sep 17 00:00:00 2001 From: Sage Weil Date: Thu, 18 Jun 2009 14:23:29 -0700 Subject: [PATCH] crush: redefine hash using __u32, for consistency across 32/64 bit I'm pretty sure this was giving inconsistent results across archs, because bits would get shifted into the high 32 and then back again on x86_64 but not x86_32. --- src/crush/hash.h | 136 +++++++++++++++++++++++++---------------------- 1 file changed, 73 insertions(+), 63 deletions(-) diff --git a/src/crush/hash.h b/src/crush/hash.h index 5baf4443b0c2d..42f3312783a10 100644 --- a/src/crush/hash.h +++ b/src/crush/hash.h @@ -1,80 +1,90 @@ #ifndef _CRUSH_HASH_H #define _CRUSH_HASH_H -// Robert Jenkins' function for mixing 32-bit values -// http://burtleburtle.net/bob/hash/evahash.html -// a, b = random bits, c = input and output -#define hashmix(a,b,c) \ - a=a-b; a=a-c; a=a^(c>>13); \ - b=b-c; b=b-a; b=b^(a<<8); \ - c=c-a; c=c-b; c=c^(b>>13); \ - a=a-b; a=a-c; a=a^(c>>12); \ - b=b-c; b=b-a; b=b^(a<<16); \ - c=c-a; c=c-b; c=c^(b>>5); \ - a=a-b; a=a-c; a=a^(c>>3); \ - b=b-c; b=b-a; b=b^(a<<10); \ - c=c-a; c=c-b; c=c^(b>>15); +/* + * Robert Jenkins' function for mixing 32-bit values + * http://burtleburtle.net/bob/hash/evahash.html + * a, b = random bits, c = input and output + */ +#define crush_hashmix(a, b, c) do { \ + a = a-b; a = a-c; a = a^(c>>13); \ + b = b-c; b = b-a; b = b^(a<<8); \ + c = c-a; c = c-b; c = c^(b>>13); \ + a = a-b; a = a-c; a = a^(c>>12); \ + b = b-c; b = b-a; b = b^(a<<16); \ + c = c-a; c = c-b; c = c^(b>>5); \ + a = a-b; a = a-c; a = a^(c>>3); \ + b = b-c; b = b-a; b = b^(a<<10); \ + c = c-a; c = c-b; c = c^(b>>15); \ + } while (0) #define crush_hash_seed 1315423911 -static inline unsigned crush_hash32(unsigned a) { - unsigned hash = crush_hash_seed ^ a; - unsigned b = a; - unsigned x = 231232; - unsigned y = 1232; - hashmix(b, x, hash); - hashmix(y, a, hash); - return (hash & 0xFFFFFFFF); +static inline __u32 crush_hash32(__u32 a) +{ + __u32 hash = crush_hash_seed ^ a; + __u32 b = a; + __u32 x = 231232; + __u32 y = 1232; + crush_hashmix(b, x, hash); + crush_hashmix(y, a, hash); + return hash; } -static inline unsigned crush_hash32_2(unsigned a, unsigned b) { - unsigned hash = crush_hash_seed ^ a ^ b; - unsigned x = 231232; - unsigned y = 1232; - hashmix(a, b, hash); - hashmix(x, a, hash); - hashmix(b, y, hash); - return (hash & 0xFFFFFFFF); +static inline __u32 crush_hash32_2(__u32 a, __u32 b) +{ + __u32 hash = crush_hash_seed ^ a ^ b; + __u32 x = 231232; + __u32 y = 1232; + crush_hashmix(a, b, hash); + crush_hashmix(x, a, hash); + crush_hashmix(b, y, hash); + return hash; } -static inline unsigned crush_hash32_3(unsigned a, unsigned b, unsigned c) { - unsigned int hash = crush_hash_seed ^ a ^ b ^ c; - unsigned x = 231232; - unsigned y = 1232; - hashmix(a, b, hash); - hashmix(c, x, hash); - hashmix(y, a, hash); - hashmix(b, x, hash); - hashmix(y, c, hash); - return (hash & 0xFFFFFFFF); +static inline __u32 crush_hash32_3(__u32 a, __u32 b, __u32 c) +{ + __u32 hash = crush_hash_seed ^ a ^ b ^ c; + __u32 x = 231232; + __u32 y = 1232; + crush_hashmix(a, b, hash); + crush_hashmix(c, x, hash); + crush_hashmix(y, a, hash); + crush_hashmix(b, x, hash); + crush_hashmix(y, c, hash); + return hash; } -static inline unsigned crush_hash32_4(unsigned a, unsigned b, unsigned c, unsigned d) { - unsigned int hash = crush_hash_seed ^a ^ b ^ c ^ d; - unsigned x = 231232; - unsigned y = 1232; - hashmix(a, b, hash); - hashmix(c, d, hash); - hashmix(a, x, hash); - hashmix(y, b, hash); - hashmix(c, x, hash); - hashmix(y, d, hash); - return (hash & 0xFFFFFFFF); +static inline __u32 crush_hash32_4(__u32 a, __u32 b, __u32 c, + __u32 d) +{ + __u32 hash = crush_hash_seed ^ a ^ b ^ c ^ d; + __u32 x = 231232; + __u32 y = 1232; + crush_hashmix(a, b, hash); + crush_hashmix(c, d, hash); + crush_hashmix(a, x, hash); + crush_hashmix(y, b, hash); + crush_hashmix(c, x, hash); + crush_hashmix(y, d, hash); + return hash; } -static inline unsigned crush_hash32_5(unsigned a, unsigned b, unsigned c, unsigned d, unsigned e) { - unsigned int hash = crush_hash_seed ^ a ^ b ^ c ^ d ^ e; - unsigned x = 231232; - unsigned y = 1232; - hashmix(a, b, hash); - hashmix(c, d, hash); - hashmix(e, x, hash); - hashmix(y, a, hash); - hashmix(b, x, hash); - hashmix(y, c, hash); - hashmix(d, x, hash); - hashmix(y, e, hash); - return (hash & 0xFFFFFFFF); +static inline __u32 crush_hash32_5(__u32 a, __u32 b, __u32 c, + __u32 d, __u32 e) +{ + __u32 hash = crush_hash_seed ^ a ^ b ^ c ^ d ^ e; + __u32 x = 231232; + __u32 y = 1232; + crush_hashmix(a, b, hash); + crush_hashmix(c, d, hash); + crush_hashmix(e, x, hash); + crush_hashmix(y, a, hash); + crush_hashmix(b, x, hash); + crush_hashmix(y, c, hash); + crush_hashmix(d, x, hash); + crush_hashmix(y, e, hash); + return hash; } #endif -- 2.39.5