samples/bpf/hash_func01.h

   1 /* SPDX-License-Identifier: LGPL-2.1
   2  *
   3  * Based on Paul Hsieh's (LGPG 2.1) hash function
   4  * From: http://www.azillionmonkeys.com/qed/hash.html
   5  */
   6
   7 #define get16bits(d) (*((const __u16 *) (d)))
   8
   9 static __always_inline
  10 __u32 SuperFastHash (const char *data, int len, __u32 initval) {
  11         __u32 hash = initval;
  12         __u32 tmp;
  13         int rem;
  14
  15         if (len <= 0 || data == NULL) return 0;
  16
  17         rem = len & 3;
  18         len >>= 2;
  19
  20         /* Main loop */
  21 #pragma clang loop unroll(full)
  22         for (;len > 0; len--) {
  23                 hash  += get16bits (data);
  24                 tmp    = (get16bits (data+2) << 11) ^ hash;
  25                 hash   = (hash << 16) ^ tmp;
  26                 data  += 2*sizeof (__u16);
  27                 hash  += hash >> 11;
  28         }
  29
  30         /* Handle end cases */
  31         switch (rem) {
  32         case 3: hash += get16bits (data);
  33                 hash ^= hash << 16;
  34                 hash ^= ((signed char)data[sizeof (__u16)]) << 18;
  35                 hash += hash >> 11;
  36                 break;
  37         case 2: hash += get16bits (data);
  38                 hash ^= hash << 11;
  39                 hash += hash >> 17;
  40                 break;
  41         case 1: hash += (signed char)*data;
  42                 hash ^= hash << 10;
  43                 hash += hash >> 1;
  44         }
  45
  46         /* Force "avalanching" of final 127 bits */
  47         hash ^= hash << 3;
  48         hash += hash >> 5;
  49         hash ^= hash << 4;
  50         hash += hash >> 17;
  51         hash ^= hash << 25;
  52         hash += hash >> 6;
  53
  54         return hash;
  55 }