Line data Source code
1 : /*
2 : * vr_hash.h
3 : *
4 : * Copyright (c) 2013 Juniper Networks, Inc. All rights reserved.
5 : */
6 :
7 : #ifndef _VR_HASH_H
8 : #define _VR_HASH_H
9 :
10 : #include "vr_os.h"
11 :
12 : /* vr_hash.h: Jenkins hash support.
13 : *
14 : * License: Public Domain
15 : * Copyright (C) 2006. Bob Jenkins (bob_jenkins@burtleburtle.net)
16 : *
17 : * http://burtleburtle.net/bob/hash/
18 : *
19 : * These are the credits from Bob's sources:
20 : *
21 : * lookup3.c, by Bob Jenkins, May 2006, Public Domain.
22 : *
23 : * These are functions for producing 32-bit hashes for hash table lookup.
24 : * hashword(), hashlittle(), hashlittle2(), hashbig(), mix(), and final()
25 : * are externally useful functions. Routines to test the hash are included
26 : * if SELF_TEST is defined. You can use this free for any purpose. It's in
27 : * the public domain. It has no warranty.
28 : *
29 : * Copyright (C) 2009-2010 Jozsef Kadlecsik (kadlec@blackhole.kfki.hu)
30 : *
31 : * I've modified Bob's hash to be useful in the Linux kernel, and
32 : * any bugs present are my fault.
33 : * Jozsef
34 : */
35 :
36 : /* Best hash sizes are of power of two */
37 : #define vr_hash_size(n) ((uint32_t)1<<(n))
38 : /* Mask the hash value, i.e (value & vr_hash_mask(n)) instead of (value % n) */
39 : #define vr_hash_mask(n) (vr_hash_size(n)-1)
40 :
41 : #define rolword(x,k) (((x)<<(k)) | ((x)>>(32-(k))))
42 :
43 : /* __vr_hash_mix -- mix 3 32-bit values reversibly. */
44 : #define __vr_hash_mix(a, b, c) \
45 : { \
46 : a -= c; a ^= rolword(c, 4); c += b; \
47 : b -= a; b ^= rolword(a, 6); a += c; \
48 : c -= b; c ^= rolword(b, 8); b += a; \
49 : a -= c; a ^= rolword(c, 16); c += b; \
50 : b -= a; b ^= rolword(a, 19); a += c; \
51 : c -= b; c ^= rolword(b, 4); b += a; \
52 : }
53 :
54 : /* __vr_hash_final - final mixing of 3 32-bit values (a,b,c) into c */
55 : #define __vr_hash_final(a, b, c) \
56 : { \
57 : c ^= b; c -= rolword(b, 14); \
58 : a ^= c; a -= rolword(c, 11); \
59 : b ^= a; b -= rolword(a, 25); \
60 : c ^= b; c -= rolword(b, 16); \
61 : a ^= c; a -= rolword(c, 4); \
62 : b ^= a; b -= rolword(a, 14); \
63 : c ^= b; c -= rolword(b, 24); \
64 : }
65 :
66 : /* An arbitrary initial parameter */
67 : #define VR_HASH_INITVAL 0xdeadbeef
68 :
69 : __attribute__packed__open__
70 : struct __unaligned_u32 {
71 : uint32_t x;
72 : } __attribute__packed__close__;
73 :
74 2487 : static inline uint32_t __get_unaligned_word(const void *p)
75 : {
76 : union {
77 : uint8_t bytes[sizeof(uint32_t)];
78 : struct __unaligned_u32 u32;
79 : } word;
80 :
81 : size_t i;
82 12435 : for (i = 0; i < sizeof(struct __unaligned_u32); i++) {
83 9948 : word.bytes[i] = ((uint8_t *) p)[i];
84 : }
85 2487 : return word.u32.x;
86 : }
87 :
88 :
89 : /* vr_hash - hash an arbitrary key
90 : * @k: sequence of bytes as key
91 : * @length: the length of the key
92 : * @initval: the previous hash, or an arbitray value
93 : *
94 : * The generic version, hashes an arbitrary sequence of bytes.
95 : * No alignment or length assumptions are made about the input key.
96 : *
97 : * Returns the hash value of the key. The result depends on endianness.
98 : */
99 984 : static inline uint32_t vr_hash(const void *key, uint32_t length, uint32_t initval)
100 : {
101 : uint32_t a, b, c;
102 984 : const uint8_t *k = key;
103 :
104 : /* Set up the internal state */
105 984 : a = b = c = VR_HASH_INITVAL + length + initval;
106 :
107 : /* All but the last block: affect some 32 bits of (a,b,c) */
108 1813 : while (length > 12) {
109 829 : a += __get_unaligned_word(k);
110 829 : b += __get_unaligned_word(k + 4);
111 829 : c += __get_unaligned_word(k + 8);
112 829 : __vr_hash_mix(a, b, c);
113 829 : length -= 12;
114 829 : k += 12;
115 : }
116 : /* Last block: affect all 32 bits of (c) */
117 984 : if (length == 12) c += (uint32_t)k[11]<<24;
118 984 : if (length >= 11) c += (uint32_t)k[10]<<16;
119 984 : if (length >= 10) c += (uint32_t)k[9]<<8;
120 984 : if (length >= 9) c += k[8];
121 984 : if (length >= 8) b += (uint32_t)k[7]<<24;
122 984 : if (length >= 7) b += (uint32_t)k[6]<<16;
123 984 : if (length >= 6) b += (uint32_t)k[5]<<8;
124 984 : if (length >= 5) b += k[4];
125 984 : if (length >= 4) a += (uint32_t)k[3]<<24;
126 984 : if (length >= 3) a += (uint32_t)k[2]<<16;
127 984 : if (length >= 2) a += (uint32_t)k[1]<<8;
128 984 : if (length >= 1) {
129 984 : a += k[0];
130 984 : __vr_hash_final(a, b, c);
131 : }
132 :
133 984 : return c;
134 : }
135 :
136 : /* vr_hash2 - hash an array of u32's
137 : * @k: the key which must be an array of u32's
138 : * @length: the number of u32's in the key
139 : * @initval: the previous hash, or an arbitray value
140 : *
141 : * Returns the hash value of the key.
142 : */
143 : static inline uint32_t vr_hash2(const uint32_t *k, uint32_t length, uint32_t initval)
144 : {
145 : uint32_t a, b, c;
146 :
147 : /* Set up the internal state */
148 : a = b = c = VR_HASH_INITVAL + (length<<2) + initval;
149 :
150 : /* Handle most of the key */
151 : while (length > 3) {
152 : a += k[0];
153 : b += k[1];
154 : c += k[2];
155 : __vr_hash_mix(a, b, c);
156 : length -= 3;
157 : k += 3;
158 : }
159 :
160 : /* Handle the last 3 u32's: all the case statements fall through */
161 : switch (length) {
162 : case 3: c += k[2];
163 : case 2: b += k[1];
164 : case 1: a += k[0];
165 : __vr_hash_final(a, b, c);
166 : case 0: /* Nothing left to add */
167 : break;
168 : }
169 :
170 : return c;
171 : }
172 :
173 :
174 : /* vr_hash_3words - hash exactly 3, 2 or 1 word(s) */
175 2 : static inline uint32_t vr_hash_3words(uint32_t a, uint32_t b, uint32_t c, uint32_t initval)
176 : {
177 2 : a += VR_HASH_INITVAL;
178 2 : b += VR_HASH_INITVAL;
179 2 : c += initval;
180 :
181 2 : __vr_hash_final(a, b, c);
182 :
183 2 : return c;
184 : }
185 :
186 2 : static inline uint32_t vr_hash_2words(uint32_t a, uint32_t b, uint32_t initval)
187 : {
188 2 : return vr_hash_3words(a, b, 0, initval);
189 : }
190 :
191 : static inline uint32_t vr_hash_1word(uint32_t a, uint32_t initval)
192 : {
193 : return vr_hash_3words(a, 0, 0, initval);
194 : }
195 :
196 : #endif /* _VR_HASH_H */
|
