tools/testing/selftests/bpf/progs/test_jhash.h

   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 }