net/ceph/crush/hash.c

   1 // SPDX-License-Identifier: GPL-2.0
   2 #ifdef __KERNEL__
   3 # include <linux/crush/hash.h>
   4 #else
   5 # include "hash.h"
   6 #endif
   7
   8 /*
   9  * Robert Jenkins' function for mixing 32-bit values
  10  * https://burtleburtle.net/bob/hash/evahash.html
  11  * a, b = random bits, c = input and output
  12  */
  13 #define crush_hashmix(a, b, c) do {                     \
  14                 a = a-b;  a = a-c;  a = a^(c>>13);      \
  15                 b = b-c;  b = b-a;  b = b^(a<<8);       \
  16                 c = c-a;  c = c-b;  c = c^(b>>13);      \
  17                 a = a-b;  a = a-c;  a = a^(c>>12);      \
  18                 b = b-c;  b = b-a;  b = b^(a<<16);      \
  19                 c = c-a;  c = c-b;  c = c^(b>>5);       \
  20                 a = a-b;  a = a-c;  a = a^(c>>3);       \
  21                 b = b-c;  b = b-a;  b = b^(a<<10);      \
  22                 c = c-a;  c = c-b;  c = c^(b>>15);      \
  23         } while (0)
  24
  25 #define crush_hash_seed 1315423911
  26
  27 static __u32 crush_hash32_rjenkins1(__u32 a)
  28 {
  29         __u32 hash = crush_hash_seed ^ a;
  30         __u32 b = a;
  31         __u32 x = 231232;
  32         __u32 y = 1232;
  33         crush_hashmix(b, x, hash);
  34         crush_hashmix(y, a, hash);
  35         return hash;
  36 }
  37
  38 static __u32 crush_hash32_rjenkins1_2(__u32 a, __u32 b)
  39 {
  40         __u32 hash = crush_hash_seed ^ a ^ b;
  41         __u32 x = 231232;
  42         __u32 y = 1232;
  43         crush_hashmix(a, b, hash);
  44         crush_hashmix(x, a, hash);
  45         crush_hashmix(b, y, hash);
  46         return hash;
  47 }
  48
  49 static __u32 crush_hash32_rjenkins1_3(__u32 a, __u32 b, __u32 c)
  50 {
  51         __u32 hash = crush_hash_seed ^ a ^ b ^ c;
  52         __u32 x = 231232;
  53         __u32 y = 1232;
  54         crush_hashmix(a, b, hash);
  55         crush_hashmix(c, x, hash);
  56         crush_hashmix(y, a, hash);
  57         crush_hashmix(b, x, hash);
  58         crush_hashmix(y, c, hash);
  59         return hash;
  60 }
  61
  62 static __u32 crush_hash32_rjenkins1_4(__u32 a, __u32 b, __u32 c, __u32 d)
  63 {
  64         __u32 hash = crush_hash_seed ^ a ^ b ^ c ^ d;
  65         __u32 x = 231232;
  66         __u32 y = 1232;
  67         crush_hashmix(a, b, hash);
  68         crush_hashmix(c, d, hash);
  69         crush_hashmix(a, x, hash);
  70         crush_hashmix(y, b, hash);
  71         crush_hashmix(c, x, hash);
  72         crush_hashmix(y, d, hash);
  73         return hash;
  74 }
  75
  76 static __u32 crush_hash32_rjenkins1_5(__u32 a, __u32 b, __u32 c, __u32 d,
  77                                       __u32 e)
  78 {
  79         __u32 hash = crush_hash_seed ^ a ^ b ^ c ^ d ^ e;
  80         __u32 x = 231232;
  81         __u32 y = 1232;
  82         crush_hashmix(a, b, hash);
  83         crush_hashmix(c, d, hash);
  84         crush_hashmix(e, x, hash);
  85         crush_hashmix(y, a, hash);
  86         crush_hashmix(b, x, hash);
  87         crush_hashmix(y, c, hash);
  88         crush_hashmix(d, x, hash);
  89         crush_hashmix(y, e, hash);
  90         return hash;
  91 }
  92
  93
  94 __u32 crush_hash32(int type, __u32 a)
  95 {
  96         switch (type) {
  97         case CRUSH_HASH_RJENKINS1:
  98                 return crush_hash32_rjenkins1(a);
  99         default:
 100                 return 0;
 101         }
 102 }
 103
 104 __u32 crush_hash32_2(int type, __u32 a, __u32 b)
 105 {
 106         switch (type) {
 107         case CRUSH_HASH_RJENKINS1:
 108                 return crush_hash32_rjenkins1_2(a, b);
 109         default:
 110                 return 0;
 111         }
 112 }
 113
 114 __u32 crush_hash32_3(int type, __u32 a, __u32 b, __u32 c)
 115 {
 116         switch (type) {
 117         case CRUSH_HASH_RJENKINS1:
 118                 return crush_hash32_rjenkins1_3(a, b, c);
 119         default:
 120                 return 0;
 121         }
 122 }
 123
 124 __u32 crush_hash32_4(int type, __u32 a, __u32 b, __u32 c, __u32 d)
 125 {
 126         switch (type) {
 127         case CRUSH_HASH_RJENKINS1:
 128                 return crush_hash32_rjenkins1_4(a, b, c, d);
 129         default:
 130                 return 0;
 131         }
 132 }
 133
 134 __u32 crush_hash32_5(int type, __u32 a, __u32 b, __u32 c, __u32 d, __u32 e)
 135 {
 136         switch (type) {
 137         case CRUSH_HASH_RJENKINS1:
 138                 return crush_hash32_rjenkins1_5(a, b, c, d, e);
 139         default:
 140                 return 0;
 141         }
 142 }
 143
 144 const char *crush_hash_name(int type)
 145 {
 146         switch (type) {
 147         case CRUSH_HASH_RJENKINS1:
 148                 return "rjenkins1";
 149         default:
 150                 return "unknown";
 151         }
 152 }