LXR linux/samples/bpf/hash

   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
   9static __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}
  56