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 } 153