liblttng-ust/lttng-hash-helper.h

   1 /*
   2  * SPDX-License-Identifier: LGPL-2.1-only
   3  *
   4  * Copyright (C) 2012 Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
   5  *
   6  * LTTng hash table helpers.
   7  */
   8
   9 #ifndef _LTTNG_HASH_HELPER_H
  10 #define _LTTNG_HASH_HELPER_H
  11
  12 #include <assert.h>
  13 #include <stddef.h>
  14 #include <stdint.h>
  15 #include <urcu/compiler.h>
  16
  17 /*
  18  * Hash function
  19  * Source: http://burtleburtle.net/bob/c/lookup3.c
  20  * Originally Public Domain
  21  */
  22
  23 #define rot(x, k) (((x) << (k)) | ((x) >> (32 - (k))))
  24
  25 #define mix(a, b, c) \
  26 do { \
  27         a -= c; a ^= rot(c,  4); c += b; \
  28         b -= a; b ^= rot(a,  6); a += c; \
  29         c -= b; c ^= rot(b,  8); b += a; \
  30         a -= c; a ^= rot(c, 16); c += b; \
  31         b -= a; b ^= rot(a, 19); a += c; \
  32         c -= b; c ^= rot(b,  4); b += a; \
  33 } while (0)
  34
  35 #define final(a, b, c) \
  36 { \
  37         c ^= b; c -= rot(b, 14); \
  38         a ^= c; a -= rot(c, 11); \
  39         b ^= a; b -= rot(a, 25); \
  40         c ^= b; c -= rot(b, 16); \
  41         a ^= c; a -= rot(c,  4);\
  42         b ^= a; b -= rot(a, 14); \
  43         c ^= b; c -= rot(b, 24); \
  44 }
  45
  46 static inline __attribute__((unused))
  47 uint32_t lttng_hash_u32(
  48         const uint32_t *k,      /* the key, an array of uint32_t values */
  49         size_t length,          /* the length of the key, in uint32_ts */
  50         uint32_t initval)       /* the previous hash, or an arbitrary value */
  51 {
  52         uint32_t a, b, c;
  53
  54         /* Set up the internal state */
  55         a = b = c = 0xdeadbeef + (((uint32_t) length) << 2) + initval;
  56
  57         /*----------------------------------------- handle most of the key */
  58         while (length > 3) {
  59                 a += k[0];
  60                 b += k[1];
  61                 c += k[2];
  62                 mix(a, b, c);
  63                 length -= 3;
  64                 k += 3;
  65         }
  66
  67         /*----------------------------------- handle the last 3 uint32_t's */
  68         switch (length) {       /* all the case statements fall through */
  69         case 3: c += k[2];
  70         case 2: b += k[1];
  71         case 1: a += k[0];
  72                 final(a, b, c);
  73         case 0:                 /* case 0: nothing left to add */
  74                 break;
  75         }
  76         /*---------------------------------------------- report the result */
  77         return c;
  78 }
  79
  80 static inline
  81 void lttng_hashword2(
  82         const uint32_t *k,      /* the key, an array of uint32_t values */
  83         size_t length,          /* the length of the key, in uint32_ts */
  84         uint32_t *pc,           /* IN: seed OUT: primary hash value */
  85         uint32_t *pb)           /* IN: more seed OUT: secondary hash value */
  86 {
  87         uint32_t a, b, c;
  88
  89         /* Set up the internal state */
  90         a = b = c = 0xdeadbeef + ((uint32_t) (length << 2)) + *pc;
  91         c += *pb;
  92
  93         /*----------------------------------------- handle most of the key */
  94         while (length > 3) {
  95                 a += k[0];
  96                 b += k[1];
  97                 c += k[2];
  98                 mix(a, b, c);
  99                 length -= 3;
 100                 k += 3;
 101         }
 102
 103         /*----------------------------------- handle the last 3 uint32_t's */
 104         switch (length) {       /* all the case statements fall through */
 105         case 3: c += k[2];
 106         case 2: b += k[1];
 107         case 1: a += k[0];
 108                 final(a, b, c);
 109         case 0:                 /* case 0: nothing left to add */
 110                 break;
 111         }
 112         /*---------------------------------------------- report the result */
 113         *pc = c;
 114         *pb = b;
 115 }
 116
 117 #if (CAA_BITS_PER_LONG == 32)
 118 static inline
 119 unsigned long lttng_hash_mix(const void *_key, size_t length, unsigned long seed)
 120 {
 121         unsigned int key = (unsigned int) _key;
 122
 123         assert(length == sizeof(unsigned int));
 124         return lttng_hash_u32(&key, 1, seed);
 125 }
 126 #else
 127 static inline
 128 unsigned long lttng_hash_mix(const void *_key, size_t length, unsigned long seed)
 129 {
 130         union {
 131                 uint64_t v64;
 132                 uint32_t v32[2];
 133         } v;
 134         union {
 135                 uint64_t v64;
 136                 uint32_t v32[2];
 137         } key;
 138
 139         assert(length == sizeof(unsigned long));
 140         v.v64 = (uint64_t) seed;
 141         key.v64 = (uint64_t) _key;
 142         lttng_hashword2(key.v32, 2, &v.v32[0], &v.v32[1]);
 143         return v.v64;
 144 }
 145 #endif
 146
 147 #endif /* _LTTNG_HASH_HELPER_H */