fs/ceph/crush/hash.c

   1
   2 #include <linux/types.h>
   3 #include "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 }