1/*
2Copyright (c) 2012, Broadcom Europe Ltd
3All rights reserved.
4
5Redistribution and use in source and binary forms, with or without
6modification, are permitted provided that the following conditions are met:
7 * Redistributions of source code must retain the above copyright
8 notice, this list of conditions and the following disclaimer.
9 * Redistributions in binary form must reproduce the above copyright
10 notice, this list of conditions and the following disclaimer in the
11 documentation and/or other materials provided with the distribution.
12 * Neither the name of the copyright holder nor the
13 names of its contributors may be used to endorse or promote products
14 derived from this software without specific prior written permission.
15
16THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND
17ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
18WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
19DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE FOR ANY
20DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
21(INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
22LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
23ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
24(INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
25SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
26*/
27
28#ifndef KHRN_INT_HASH_H
29#define KHRN_INT_HASH_H
30
31/*
32-------------------------------------------------------------------------------
33These are functions for producing 32-bit hashes for hash table lookup.
34khrn_hashword(), khrn_hashlittle(), hashlittle2(), hashbig(), mix(), and final()
35are externally useful functions. Routines to test the hash are included
36if SELF_TEST is defined. You can use this free for any purpose. It's in
37the public domain. It has no warranty.
38
39You probably want to use khrn_hashlittle(). khrn_hashlittle() and hashbig()
40hash byte arrays. khrn_hashlittle() is is faster than hashbig() on
41little-endian machines. Intel and AMD are little-endian machines.
42On second thought, you probably want hashlittle2(), which is identical to
43khrn_hashlittle() except it returns two 32-bit hashes for the price of one.
44You could implement hashbig2() if you wanted but I haven't bothered here.
45
46If you want to find a hash of, say, exactly 7 integers, do
47 a = i1; b = i2; c = i3;
48 mix(a,b,c);
49 a += i4; b += i5; c += i6;
50 mix(a,b,c);
51 a += i7;
52 final(a,b,c);
53then use c as the hash value. If you have a variable length array of
544-byte integers to hash, use khrn_hashword(). If you have a byte array (like
55a character string), use khrn_hashlittle(). If you have several byte arrays, or
56a mix of things, see the comments above khrn_hashlittle().
57
58Why is this so big? I read 12 bytes at a time into 3 4-byte integers,
59then mix those integers. This is fast (you can do a lot more thorough
60mixing with 12*3 instructions on 3 integers than you can with 3 instructions
61on 1 byte), but shoehorning those bytes into integers efficiently is messy.
62-------------------------------------------------------------------------------
63*/
64
65#define rot(x,k) (((x)<<(k)) | ((x)>>(32-(k))))
66
67/*
68-------------------------------------------------------------------------------
69mix -- mix 3 32-bit values reversibly.
70
71This is reversible, so any information in (a,b,c) before mix() is
72still in (a,b,c) after mix().
73
74If four pairs of (a,b,c) inputs are run through mix(), or through
75mix() in reverse, there are at least 32 bits of the output that
76are sometimes the same for one pair and different for another pair.
77This was tested for:
78* pairs that differed by one bit, by two bits, in any combination
79 of top bits of (a,b,c), or in any combination of bottom bits of
80 (a,b,c).
81* "differ" is defined as +, -, ^, or ~^. For + and -, I transformed
82 the output delta to a Gray code (a^(a>>1)) so a string of 1's (as
83 is commonly produced by subtraction) look like a single 1-bit
84 difference.
85* the base values were pseudorandom, all zero but one bit set, or
86 all zero plus a counter that starts at zero.
87
88Some k values for my "a-=c; a^=rot(c,k); c+=b;" arrangement that
89satisfy this are
90 4 6 8 16 19 4
91 9 15 3 18 27 15
92 14 9 3 7 17 3
93Well, "9 15 3 18 27 15" didn't quite get 32 bits diffing
94for "differ" defined as + with a one-bit base and a two-bit delta. I
95used http://burtleburtle.net/bob/hash/avalanche.html to choose
96the operations, constants, and arrangements of the variables.
97
98This does not achieve avalanche. There are input bits of (a,b,c)
99that fail to affect some output bits of (a,b,c), especially of a. The
100most thoroughly mixed value is c, but it doesn't really even achieve
101avalanche in c.
102
103This allows some parallelism. Read-after-writes are good at doubling
104the number of bits affected, so the goal of mixing pulls in the opposite
105direction as the goal of parallelism. I did what I could. Rotates
106seem to cost as much as shifts on every machine I could lay my hands
107on, and rotates are much kinder to the top and bottom bits, so I used
108rotates.
109-------------------------------------------------------------------------------
110*/
111#define mix(a,b,c) \
112do { \
113 a -= c; a ^= rot(c, 4); c += b; \
114 b -= a; b ^= rot(a, 6); a += c; \
115 c -= b; c ^= rot(b, 8); b += a; \
116 a -= c; a ^= rot(c,16); c += b; \
117 b -= a; b ^= rot(a,19); a += c; \
118 c -= b; c ^= rot(b, 4); b += a; \
119} while (0)
120
121/*
122-------------------------------------------------------------------------------
123final -- final mixing of 3 32-bit values (a,b,c) into c
124
125Pairs of (a,b,c) values differing in only a few bits will usually
126produce values of c that look totally different. This was tested for
127* pairs that differed by one bit, by two bits, in any combination
128 of top bits of (a,b,c), or in any combination of bottom bits of
129 (a,b,c).
130* "differ" is defined as +, -, ^, or ~^. For + and -, I transformed
131 the output delta to a Gray code (a^(a>>1)) so a string of 1's (as
132 is commonly produced by subtraction) look like a single 1-bit
133 difference.
134* the base values were pseudorandom, all zero but one bit set, or
135 all zero plus a counter that starts at zero.
136
137These constants passed:
138 14 11 25 16 4 14 24
139 12 14 25 16 4 14 24
140and these came close:
141 4 8 15 26 3 22 24
142 10 8 15 26 3 22 24
143 11 8 15 26 3 22 24
144-------------------------------------------------------------------------------
145*/
146#define final(a,b,c) \
147do { \
148 c ^= b; c -= rot(b,14); \
149 a ^= c; a -= rot(c,11); \
150 b ^= a; b -= rot(a,25); \
151 c ^= b; c -= rot(b,16); \
152 a ^= c; a -= rot(c,4); \
153 b ^= a; b -= rot(a,14); \
154 c ^= b; c -= rot(b,24); \
155} while (0)
156
157uint32_t khrn_hashword(const uint32_t *key, int length, uint32_t initval);
158uint32_t khrn_hashlittle(const void *key, int length, uint32_t initval);
159
160#endif
161
162