1 /* hash-utils.c - computing hash values
2 *
3 ****************************************************************
4 * Copyright (C) 2000 Thomas Lord
5 *
6 * See the file "COPYING" for further information about
7 * the copyright and warranty status of this work.
8 */
9
10
11
12 #include "hackerlab/machine/alignment.h"
13 #include "hackerlab/hash/hash-utils.h"
14
15
16 /************************************************************************
17 *(h1 "Hash Utilities"
18 * :includes ("hackerlab/hash/hash-utils.h"))
19 *
20 * The functions in this section provide tools useful for computing
21 * hash values.
22 */
23
24
25
26
27 static unsigned long shuffled_bytes[] =
28 {
29 245, 184, 171, 36, 93, 194, 192, 143, 207, 89, 63, 175, 203, 231, 47, 238,
30 103, 67, 176, 102, 80, 133, 24, 155, 91, 141, 234, 58, 44, 191, 218, 157,
31 13, 168, 160, 113, 211, 213, 252, 236, 2, 19, 21, 148, 111, 251, 165, 74,
32 124, 25, 181, 210, 250, 195, 235, 97, 185, 1, 179, 198, 105, 101, 5, 220,
33 35, 162, 142, 41, 200, 209, 224, 71, 201, 134, 69, 48, 65, 170, 72, 167,
34 145, 205, 28, 88, 215, 81, 214, 78, 118, 26, 123, 84, 140, 49, 45, 8,
35 7, 107, 227, 60, 59, 32, 30, 82, 31, 189, 131, 17, 66, 239, 64, 10,
36 149, 40, 130, 146, 54, 147, 9, 114, 4, 254, 241, 116, 110, 249, 57, 233,
37 37, 55, 206, 100, 177, 119, 139, 158, 108, 75, 94, 23, 186, 152, 244, 27,
38 38, 33, 188, 87, 76, 166, 228, 52, 120, 99, 247, 174, 51, 183, 3, 161,
39 246, 135, 14, 178, 11, 216, 77, 172, 122, 154, 39, 253, 104, 34, 164, 230,
40 219, 242, 68, 151, 180, 115, 173, 73, 212, 90, 125, 29, 22, 221, 56, 121,
41 255, 204, 83, 169, 182, 112, 96, 187, 20, 106, 79, 15, 61, 223, 70, 85,
42 53, 197, 217, 232, 196, 95, 136, 150, 243, 109, 129, 202, 208, 237, 144, 156,
43 86, 127, 62, 248, 138, 229, 153, 226, 240, 199, 50, 12, 193, 98, 137, 126,
44 0, 159, 222, 18, 163, 117, 190, 46, 225, 132, 16, 43, 128, 42, 92, 6
45 };
46
47
48
49 /*(c hash_ul)
50 * unsigned long hash_ul (unsigned long n);
51 *
52 * Generate a hash value from an integer.
53 *
54 * This function is slow, but attempts to give a good distribution of
55 * hash values even for a series of `n' which are not particularly
56 * random.
57 */
58 unsigned long
hash_ul(unsigned long n)59 hash_ul (unsigned long n)
60 {
61 int rounds;
62 t_ulong answer = 0;
63
64 for (rounds = 0; rounds < 5; ++rounds)
65 {
66 int byte;
67
68 for (byte = 0; byte < sizeof (t_ulong); ++byte)
69 {
70 t_ulong new_byte;
71
72 new_byte = shuffled_bytes[0xff & (n >> byte)];
73 answer ^= (new_byte << byte);
74 }
75
76 n = ((n >> 3) ^ (n << 7));
77 }
78
79 return answer;
80 }
81
82
83 /*(c hash_double)
84 * unsigned long hash_double (double n);
85 *
86 * Generate a hash value from a double precision float.
87 *
88 * This function is slow, but attempts to give a good distribution of
89 * hash values even for a series of `n' which are not particularly
90 * random.
91 */
92 unsigned long
hash_double(double d)93 hash_double (double d)
94 {
95 union
96 {
97 t_uchar raw[sizeof (double)];
98 double d;
99 } data;
100
101 data.d = d;
102 return hash_mem (data.raw, sizeof (double));
103 }
104
105
106
107
108
109
110 /*(c hash_pointers)
111 * unsigned long hash_pointers (void * elts, size_t n_elts);
112 *
113 * Compute a hash value from an array of pointers.
114 *
115 * This function is slow, but attempts to give a good distribution of
116 * hash values even for a series of pointers which are not
117 * particularly random. Usually, pointers are not particularly
118 * random.
119 *
120 * `slow' means that the function does roughly `3 * sizeof (n)' array
121 * look-ups and lots of bit twiddling, per pointer.
122 *
123 */
124 unsigned long
hash_pointers(void * elts,size_t n_elts)125 hash_pointers (void * elts, size_t n_elts)
126 {
127 size_t x;
128 unsigned long hash;
129
130 hash = 0xdec0ded;
131 for (x = 0; x < n_elts; ++x)
132 {
133 hash ^= hash_ul (((unsigned long *)elts)[x]);
134 }
135 return hash;
136 }
137
138
139
140
141 /*(c hash_mem)
142 * unsigned long hash_mem (const t_uchar * elts, size_t n_bytes);
143 *
144 * Compute a hash value from an array of bytes.
145 *
146 * This function is slow, but attempts to give a good distribution of
147 * hash values even for a series of bytes which are not particularly
148 * random.
149 *
150 * `slow' means that the function does roughly `3 * sizeof (n)' array
151 * look-ups and lots of bit twiddling, per `sizeof (unsigned long)'
152 * bytes.
153 *
154 */
155 unsigned long
hash_mem(const t_uchar * elts,size_t n_elts)156 hash_mem (const t_uchar * elts, size_t n_elts)
157 {
158 size_t x;
159 unsigned long hash;
160
161 hash = 0xde7a115;
162
163 for (x = 0; (x < n_elts) && (MACHINE_ALIGNMENT - 1); ++x)
164 hash ^= hash_ul ((unsigned long)elts[x]);
165
166 while ((n_elts - x) >= sizeof (unsigned long))
167 {
168 hash ^= hash_ul (*(unsigned long *)(elts + x));
169 x += sizeof (unsigned long);
170 }
171
172 while (x < n_elts)
173 {
174 hash ^= hash_ul ((unsigned long)elts[x]);
175 ++x;
176 }
177 return hash;
178 }
179
180
181