103 lines · c
1// SPDX-License-Identifier: GPL-2.02// Copyright (c) 2019 Facebook3#include <features.h>4 5typedef unsigned int u32;6 7static __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 0xdeadbeef34 35static ATTR36u32 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 73static __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