1 // SPDX-License-Identifier: GPL-2.0 2 // Copyright (c) 2019 Facebook 3 #include <features.h> 4 5 typedef unsigned int u32; 6 7 static __always_inline u32 rol32(u32 word, unsigned int shift) 8 { 9 return (word << shift) | (word >> ((-shift) & 31)); 10 } 11 12 #define __jhash_mix(a, b, c) \ 13 { \ 14 a -= c; a ^= rol32(c, 4); c += b; \ 15 b -= a; b ^= rol32(a, 6); a += c; \ 16 c -= b; c ^= rol32(b, 8); b += a; \ 17 a -= c; a ^= rol32(c, 16); c += b; \ 18 b -= a; b ^= rol32(a, 19); a += c; \ 19 c -= b; c ^= rol32(b, 4); b += a; \ 20 } 21 22 #define __jhash_final(a, b, c) \ 23 { \ 24 c ^= b; c -= rol32(b, 14); \ 25 a ^= c; a -= rol32(c, 11); \ 26 b ^= a; b -= rol32(a, 25); \ 27 c ^= b; c -= rol32(b, 16); \ 28 a ^= c; a -= rol32(c, 4); \ 29 b ^= a; b -= rol32(a, 14); \ 30 c ^= b; c -= rol32(b, 24); \ 31 } 32 33 #define JHASH_INITVAL 0xdeadbeef 34 35 static ATTR 36 u32 jhash(const void *key, u32 length, u32 initval) 37 { 38 u32 a, b, c; 39 const unsigned char *k = key; 40 41 a = b = c = JHASH_INITVAL + length + initval; 42 43 while (length > 12) { 44 a += *(volatile u32 *)(k); 45 b += *(volatile u32 *)(k + 4); 46 c += *(volatile u32 *)(k + 8); 47 __jhash_mix(a, b, c); 48 length -= 12; 49 k += 12; 50 } 51 switch (length) { 52 case 12: c += (u32)k[11]<<24; 53 case 11: c += (u32)k[10]<<16; 54 case 10: c += (u32)k[9]<<8; 55 case 9: c += k[8]; 56 case 8: b += (u32)k[7]<<24; 57 case 7: b += (u32)k[6]<<16; 58 case 6: b += (u32)k[5]<<8; 59 case 5: b += k[4]; 60 case 4: a += (u32)k[3]<<24; 61 case 3: a += (u32)k[2]<<16; 62 case 2: a += (u32)k[1]<<8; 63 case 1: a += k[0]; 64 c ^= a; 65 __jhash_final(a, b, c); 66 case 0: /* Nothing left to add */ 67 break; 68 } 69 70 return c; 71 } 72 73 static __always_inline u32 jhash2(const u32 *k, u32 length, u32 initval) 74 { 75 u32 a, b, c; 76 77 /* Set up the internal state */ 78 a = b = c = JHASH_INITVAL + (length<<2) + initval; 79 80 /* Handle most of the key */ 81 while (length > 3) { 82 a += k[0]; 83 b += k[1]; 84 c += k[2]; 85 __jhash_mix(a, b, c); 86 length -= 3; 87 k += 3; 88 } 89 90 /* Handle the last 3 u32's */ 91 switch (length) { 92 case 3: c += k[2]; 93 case 2: b += k[1]; 94 case 1: a += k[0]; 95 __jhash_final(a, b, c); 96 break; 97 case 0: /* Nothing left to add */ 98 break; 99 } 100 101 return c; 102 } 103