fs/ceph/crush/hash.h

   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