ceph/src/crush/hash.c

   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 }