libosmocore 1.13.1.1-afb4 Osmocom core library

hash.h
Go to the documentation of this file.
1#pragma once
2#include <osmocom/core/log2.h>
3/* Fast hashing routine for ints, longs and pointers.
4 (C) 2002 Nadia Yvette Chambers, IBM */
5
6#include <limits.h>
7#if ULONG_MAX == 4294967295
8#define BITS_PER_LONG 32
9#else
10#define BITS_PER_LONG 64
11#endif
12
13/*
14 * The "GOLDEN_RATIO_PRIME" is used in ifs/btrfs/brtfs_inode.h and
15 * fs/inode.c. It's not actually prime any more (the previous primes
16 * were actively bad for hashing), but the name remains.
17 */
18#if BITS_PER_LONG == 32
19#define GOLDEN_RATIO_PRIME GOLDEN_RATIO_32
20#define hash_long(val, bits) hash_32(val, bits)
21#elif BITS_PER_LONG == 64
22#define hash_long(val, bits) hash_64(val, bits)
23#define GOLDEN_RATIO_PRIME GOLDEN_RATIO_64
24#else
25#error Wordsize not 32 or 64
26#endif
27
28/*
29 * This hash multiplies the input by a large odd number and takes the
30 * high bits. Since multiplication propagates changes to the most
31 * significant end only, it is essential that the high bits of the
32 * product be used for the hash value.
33 *
34 * Chuck Lever verified the effectiveness of this technique:
35 * http://www.citi.umich.edu/techreports/reports/citi-tr-00-1.pdf
36 *
37 * Although a random odd number will do, it turns out that the golden
38 * ratio phi = (sqrt(5)-1)/2, or its negative, has particularly nice
39 * properties. (See Knuth vol 3, section 6.4, exercise 9.)
40 *
41 * These are the negative, (1 - phi) = phi**2 = (3 - sqrt(5))/2,
42 * which is very slightly easier to multiply by and makes no
43 * difference to the hash distribution.
44 */
45#define GOLDEN_RATIO_32 0x61C88647
46#define GOLDEN_RATIO_64 0x61C8864680B583EBull
47
48/*
49 * The _generic versions exist only so lib/test_hash.c can compare
50 * the arch-optimized versions with the generic.
51 *
52 * Note that if you change these, any <asm/hash.h> that aren't updated
53 * to match need to have their HAVE_ARCH_* define values updated so the
54 * self-test will not false-positive.
55 */
56#ifndef HAVE_ARCH__HASH_32
57#define __hash_32 __hash_32_generic
58#endif
59 static inline uint32_t __hash_32_generic(uint32_t val)
60{
61 return val * GOLDEN_RATIO_32;
62}
63
64#ifndef HAVE_ARCH_HASH_32
65#define hash_32 hash_32_generic
66#endif
67 static inline uint32_t hash_32_generic(uint32_t val, unsigned int bits)
68{
69 /* High bits are more random, so use them. */
70 return __hash_32(val) >> (32 - bits);
71}
72
73#ifndef HAVE_ARCH_HASH_64
74#define hash_64 hash_64_generic
75#endif
76 static __always_inline uint32_t hash_64_generic(uint64_t val, unsigned int bits)
77{
78#if BITS_PER_LONG == 64
79 /* 64x64-bit multiply is efficient on all 64-bit processors */
80 return val * GOLDEN_RATIO_64 >> (64 - bits);
81#else
82 /* Hash 64 bits using only 32x32-bit multiply. */
83 return hash_32((uint32_t)val ^ __hash_32(val >> 32), bits);
84#endif
85}
86
87 static inline uint32_t hash_ptr(const void *ptr, unsigned int bits)
88{
89 return hash_long((unsigned long)ptr, bits);
90}
91
92/* This really should be called fold32_ptr; it does no hashing to speak of. */
93 static inline uint32_t hash32_ptr(const void *ptr)
94{
95 unsigned long val = (unsigned long)ptr;
96
97#if BITS_PER_LONG == 64
98 val ^= (val >> 32);
99#endif
100 return (uint32_t)val;
101}
__always_inline
#define __always_inline
Definition: conv_acc_neon_impl.h:26
hash_32
#define hash_32
Definition: hash.h:65
hash_long
#define hash_long(val, bits)
Definition: hash.h:22
__hash_32_generic
static uint32_t __hash_32_generic(uint32_t val)
Definition: hash.h:59
hash_32_generic
static uint32_t hash_32_generic(uint32_t val, unsigned int bits)
Definition: hash.h:67
hash32_ptr
static uint32_t hash32_ptr(const void *ptr)
Definition: hash.h:93
GOLDEN_RATIO_32
#define GOLDEN_RATIO_32
Definition: hash.h:45
__hash_32
#define __hash_32
Definition: hash.h:57
GOLDEN_RATIO_64
#define GOLDEN_RATIO_64
Definition: hash.h:46
hash_ptr
static uint32_t hash_ptr(const void *ptr, unsigned int bits)
Definition: hash.h:87
hash_64_generic
static __always_inline uint32_t hash_64_generic(uint64_t val, unsigned int bits)
Definition: hash.h:76
log2.h