~ubuntu-branches/ubuntu/oneiric/xserver-xorg-video-qxl/oneiric-security
» Revision
1
: src/lookup3.c
« back to all changes in this revision
Viewing changes to src/lookup3.c
- browse files at revision 1
- compare with another revision
- download diff
- download tarball
- view history from revision 1
- Committer: Bazaar Package Importer
- Author(s): Liang Guo
- Date: 2010-05-20 16:44:11 UTC
- Revision ID: james.westby@ubuntu.com-20100520164411-zzgi0hpy4iac2mj2
Tags: upstream-0.0.12
Import upstream version 0.0.12
- files added:
- src
added
removed
src/lookup3.c
1
/*
2
-------------------------------------------------------------------------------
3
lookup3.c, by Bob Jenkins, May 2006, Public Domain.
4
5
These are functions for producing 32-bit hashes for hash table lookup.
6
hashword(), hashlittle(), hashlittle2(), hashbig(), mix(), and final()
7
are externally useful functions. Routines to test the hash are included
8
if SELF_TEST is defined. You can use this free for any purpose. It's in
9
the public domain. It has no warranty.
10
11
You probably want to use hashlittle(). hashlittle() and hashbig()
12
hash byte arrays. hashlittle() is is faster than hashbig() on
13
little-endian machines. Intel and AMD are little-endian machines.
14
On second thought, you probably want hashlittle2(), which is identical to
15
hashlittle() except it returns two 32-bit hashes for the price of one.
16
You could implement hashbig2() if you wanted but I haven't bothered here.
17
18
If you want to find a hash of, say, exactly 7 integers, do
19
a = i1; b = i2; c = i3;
20
mix(a,b,c);
21
a += i4; b += i5; c += i6;
22
mix(a,b,c);
23
a += i7;
24
final(a,b,c);
25
then use c as the hash value. If you have a variable length array of
26
4-byte integers to hash, use hashword(). If you have a byte array (like
27
a character string), use hashlittle(). If you have several byte arrays, or
28
a mix of things, see the comments above hashlittle().
29
30
Why is this so big? I read 12 bytes at a time into 3 4-byte integers,
31
then mix those integers. This is fast (you can do a lot more thorough
32
mixing with 12*3 instructions on 3 integers than you can with 3 instructions
33
on 1 byte), but shoehorning those bytes into integers efficiently is messy.
34
-------------------------------------------------------------------------------
35
*/
36
37
#include <stdio.h> /* defines printf for tests */
38
#include <time.h> /* defines time_t for timings in the test */
39
#include "lookup3.h"
40
#ifdef linux
41
# include <endian.h> /* attempt to define endianness */
42
#endif
43
44
/*
45
* My best guess at if you are big-endian or little-endian. This may
46
* need adjustment.
47
*/
48
#if (defined(__BYTE_ORDER) && defined(__LITTLE_ENDIAN) && \
49
__BYTE_ORDER == __LITTLE_ENDIAN) || \
50
(defined(i386) || defined(__i386__) || defined(__i486__) || \
51
defined(__i586__) || defined(__i686__) || defined(vax) || defined(MIPSEL))
52
# define HASH_LITTLE_ENDIAN 1
53
# define HASH_BIG_ENDIAN 0
54
#elif (defined(__BYTE_ORDER) && defined(__BIG_ENDIAN) && \
55
__BYTE_ORDER == __BIG_ENDIAN) || \
56
(defined(sparc) || defined(POWERPC) || defined(mc68000) || defined(sel))
57
# define HASH_LITTLE_ENDIAN 0
58
# define HASH_BIG_ENDIAN 1
59
#else
60
# define HASH_LITTLE_ENDIAN 0
61
# define HASH_BIG_ENDIAN 0
62
#endif
63
64
#define hashsize(n) ((uint32_t)1<<(n))
65
#define hashmask(n) (hashsize(n)-1)
66
#define rot(x,k) (((x)<<(k)) | ((x)>>(32-(k))))
67
68
/*
69
-------------------------------------------------------------------------------
70
mix -- mix 3 32-bit values reversibly.
71
72
This is reversible, so any information in (a,b,c) before mix() is
73
still in (a,b,c) after mix().
74
75
If four pairs of (a,b,c) inputs are run through mix(), or through
76
mix() in reverse, there are at least 32 bits of the output that
77
are sometimes the same for one pair and different for another pair.
78
This was tested for:
79
* pairs that differed by one bit, by two bits, in any combination
80
of top bits of (a,b,c), or in any combination of bottom bits of
81
(a,b,c).
82
* "differ" is defined as +, -, ^, or ~^. For + and -, I transformed
83
the output delta to a Gray code (a^(a>>1)) so a string of 1's (as
84
is commonly produced by subtraction) look like a single 1-bit
85
difference.
86
* the base values were pseudorandom, all zero but one bit set, or
87
all zero plus a counter that starts at zero.
88
89
Some k values for my "a-=c; a^=rot(c,k); c+=b;" arrangement that
90
satisfy this are
91
4 6 8 16 19 4
92
9 15 3 18 27 15
93
14 9 3 7 17 3
94
Well, "9 15 3 18 27 15" didn't quite get 32 bits diffing
95
for "differ" defined as + with a one-bit base and a two-bit delta. I
96
used http://burtleburtle.net/bob/hash/avalanche.html to choose
97
the operations, constants, and arrangements of the variables.
98
99
This does not achieve avalanche. There are input bits of (a,b,c)
100
that fail to affect some output bits of (a,b,c), especially of a. The
101
most thoroughly mixed value is c, but it doesn't really even achieve
102
avalanche in c.
103
104
This allows some parallelism. Read-after-writes are good at doubling
105
the number of bits affected, so the goal of mixing pulls in the opposite
106
direction as the goal of parallelism. I did what I could. Rotates
107
seem to cost as much as shifts on every machine I could lay my hands
108
on, and rotates are much kinder to the top and bottom bits, so I used
109
rotates.
110
-------------------------------------------------------------------------------
111
*/
112
#define mix(a,b,c) \
113
{ \
114
a -= c; a ^= rot(c, 4); c += b; \
115
b -= a; b ^= rot(a, 6); a += c; \
116
c -= b; c ^= rot(b, 8); b += a; \
117
a -= c; a ^= rot(c,16); c += b; \
118
b -= a; b ^= rot(a,19); a += c; \
119
c -= b; c ^= rot(b, 4); b += a; \
120
}
121
122
/*
123
-------------------------------------------------------------------------------
124
final -- final mixing of 3 32-bit values (a,b,c) into c
125
126
Pairs of (a,b,c) values differing in only a few bits will usually
127
produce values of c that look totally different. This was tested for
128
* pairs that differed by one bit, by two bits, in any combination
129
of top bits of (a,b,c), or in any combination of bottom bits of
130
(a,b,c).
131
* "differ" is defined as +, -, ^, or ~^. For + and -, I transformed
132
the output delta to a Gray code (a^(a>>1)) so a string of 1's (as
133
is commonly produced by subtraction) look like a single 1-bit
134
difference.
135
* the base values were pseudorandom, all zero but one bit set, or
136
all zero plus a counter that starts at zero.
137
138
These constants passed:
139
14 11 25 16 4 14 24
140
12 14 25 16 4 14 24
141
and these came close:
142
4 8 15 26 3 22 24
143
10 8 15 26 3 22 24
144
11 8 15 26 3 22 24
145
-------------------------------------------------------------------------------
146
*/
147
#define final(a,b,c) \
148
{ \
149
c ^= b; c -= rot(b,14); \
150
a ^= c; a -= rot(c,11); \
151
b ^= a; b -= rot(a,25); \
152
c ^= b; c -= rot(b,16); \
153
a ^= c; a -= rot(c,4); \
154
b ^= a; b -= rot(a,14); \
155
c ^= b; c -= rot(b,24); \
156
}
157
158
/*
159
--------------------------------------------------------------------
160
This works on all machines. To be useful, it requires
161
-- that the key be an array of uint32_t's, and
162
-- that the length be the number of uint32_t's in the key
163
164
The function hashword() is identical to hashlittle() on little-endian
165
machines, and identical to hashbig() on big-endian machines,
166
except that the length has to be measured in uint32_ts rather than in
167
bytes. hashlittle() is more complicated than hashword() only because
168
hashlittle() has to dance around fitting the key bytes into registers.
169
--------------------------------------------------------------------
170
*/
171
uint32_t hashword(
172
const uint32_t *k, /* the key, an array of uint32_t values */
173
size_t length, /* the length of the key, in uint32_ts */
174
uint32_t initval) /* the previous hash, or an arbitrary value */
175
{
176
uint32_t a,b,c;
177
178
/* Set up the internal state */
179
a = b = c = 0xdeadbeef + (((uint32_t)length)<<2) + initval;
180
181
/*------------------------------------------------- handle most of the key */
182
while (length > 3)
183
{
184
a += k[0];
185
b += k[1];
186
c += k[2];
187
mix(a,b,c);
188
length -= 3;
189
k += 3;
190
}
191
192
/*------------------------------------------- handle the last 3 uint32_t's */
193
switch(length) /* all the case statements fall through */
194
{
195
case 3 : c+=k[2];
196
case 2 : b+=k[1];
197
case 1 : a+=k[0];
198
final(a,b,c);
199
case 0: /* case 0: nothing left to add */
200
break;
201
}
202
/*------------------------------------------------------ report the result */
203
return c;
204
}
205
206
207
/*
208
--------------------------------------------------------------------
209
hashword2() -- same as hashword(), but take two seeds and return two
210
32-bit values. pc and pb must both be nonnull, and *pc and *pb must
211
both be initialized with seeds. If you pass in (*pb)==0, the output
212
(*pc) will be the same as the return value from hashword().
213
--------------------------------------------------------------------
214
*/
215
void hashword2 (
216
const uint32_t *k, /* the key, an array of uint32_t values */
217
size_t length, /* the length of the key, in uint32_ts */
218
uint32_t *pc, /* IN: seed OUT: primary hash value */
219
uint32_t *pb) /* IN: more seed OUT: secondary hash value */
220
{
221
uint32_t a,b,c;
222
223
/* Set up the internal state */
224
a = b = c = 0xdeadbeef + ((uint32_t)(length<<2)) + *pc;
225
c += *pb;
226
227
/*------------------------------------------------- handle most of the key */
228
while (length > 3)
229
{
230
a += k[0];
231
b += k[1];
232
c += k[2];
233
mix(a,b,c);
234
length -= 3;
235
k += 3;
236
}
237
238
/*------------------------------------------- handle the last 3 uint32_t's */
239
switch(length) /* all the case statements fall through */
240
{
241
case 3 : c+=k[2];
242
case 2 : b+=k[1];
243
case 1 : a+=k[0];
244
final(a,b,c);
245
case 0: /* case 0: nothing left to add */
246
break;
247
}
248
/*------------------------------------------------------ report the result */
249
*pc=c; *pb=b;
250
}
251
252
253
/*
254
-------------------------------------------------------------------------------
255
hashlittle() -- hash a variable-length key into a 32-bit value
256
k : the key (the unaligned variable-length array of bytes)
257
length : the length of the key, counting by bytes
258
initval : can be any 4-byte value
259
Returns a 32-bit value. Every bit of the key affects every bit of
260
the return value. Two keys differing by one or two bits will have
261
totally different hash values.
262
263
The best hash table sizes are powers of 2. There is no need to do
264
mod a prime (mod is sooo slow!). If you need less than 32 bits,
265
use a bitmask. For example, if you need only 10 bits, do
266
h = (h & hashmask(10));
267
In which case, the hash table should have hashsize(10) elements.
268
269
If you are hashing n strings (uint8_t **)k, do it like this:
270
for (i=0, h=0; i<n; ++i) h = hashlittle( k[i], len[i], h);
271
272
By Bob Jenkins, 2006. bob_jenkins@burtleburtle.net. You may use this
273
code any way you wish, private, educational, or commercial. It's free.
274
275
Use for hash table lookup, or anything where one collision in 2^^32 is
276
acceptable. Do NOT use for cryptographic purposes.
277
-------------------------------------------------------------------------------
278
*/
279
280
uint32_t hashlittle( const void *key, size_t length, uint32_t initval)
281
{
282
uint32_t a,b,c; /* internal state */
283
union { const void *ptr; size_t i; } u; /* needed for Mac Powerbook G4 */
284
285
/* Set up the internal state */
286
a = b = c = 0xdeadbeef + ((uint32_t)length) + initval;
287
288
u.ptr = key;
289
if (HASH_LITTLE_ENDIAN && ((u.i & 0x3) == 0)) {
290
const uint32_t *k = (const uint32_t *)key; /* read 32-bit chunks */
291
#ifdef VALGRIND
292
const uint8_t *k8;
293
#endif
294
295
/*------ all but last block: aligned reads and affect 32 bits of (a,b,c) */
296
while (length > 12)
297
{
298
a += k[0];
299
b += k[1];
300
c += k[2];
301
mix(a,b,c);
302
length -= 12;
303
k += 3;
304
}
305
306
/*----------------------------- handle the last (probably partial) block */
307
/*
308
* "k[2]&0xffffff" actually reads beyond the end of the string, but
309
* then masks off the part it's not allowed to read. Because the
310
* string is aligned, the masked-off tail is in the same word as the
311
* rest of the string. Every machine with memory protection I've seen
312
* does it on word boundaries, so is OK with this. But VALGRIND will
313
* still catch it and complain. The masking trick does make the hash
314
* noticably faster for short strings (like English words).
315
*/
316
#ifndef VALGRIND
317
318
switch(length)
319
{
320
case 12: c+=k[2]; b+=k[1]; a+=k[0]; break;
321
case 11: c+=k[2]&0xffffff; b+=k[1]; a+=k[0]; break;
322
case 10: c+=k[2]&0xffff; b+=k[1]; a+=k[0]; break;
323
case 9 : c+=k[2]&0xff; b+=k[1]; a+=k[0]; break;
324
case 8 : b+=k[1]; a+=k[0]; break;
325
case 7 : b+=k[1]&0xffffff; a+=k[0]; break;
326
case 6 : b+=k[1]&0xffff; a+=k[0]; break;
327
case 5 : b+=k[1]&0xff; a+=k[0]; break;
328
case 4 : a+=k[0]; break;
329
case 3 : a+=k[0]&0xffffff; break;
330
case 2 : a+=k[0]&0xffff; break;
331
case 1 : a+=k[0]&0xff; break;
332
case 0 : return c; /* zero length strings require no mixing */
333
}
334
335
#else /* make valgrind happy */
336
337
k8 = (const uint8_t *)k;
338
switch(length)
339
{
340
case 12: c+=k[2]; b+=k[1]; a+=k[0]; break;
341
case 11: c+=((uint32_t)k8[10])<<16; /* fall through */
342
case 10: c+=((uint32_t)k8[9])<<8; /* fall through */
343
case 9 : c+=k8[8]; /* fall through */
344
case 8 : b+=k[1]; a+=k[0]; break;
345
case 7 : b+=((uint32_t)k8[6])<<16; /* fall through */
346
case 6 : b+=((uint32_t)k8[5])<<8; /* fall through */
347
case 5 : b+=k8[4]; /* fall through */
348
case 4 : a+=k[0]; break;
349
case 3 : a+=((uint32_t)k8[2])<<16; /* fall through */
350
case 2 : a+=((uint32_t)k8[1])<<8; /* fall through */
351
case 1 : a+=k8[0]; break;
352
case 0 : return c;
353
}
354
355
#endif /* !valgrind */
356
357
} else if (HASH_LITTLE_ENDIAN && ((u.i & 0x1) == 0)) {
358
const uint16_t *k = (const uint16_t *)key; /* read 16-bit chunks */
359
const uint8_t *k8;
360
361
/*--------------- all but last block: aligned reads and different mixing */
362
while (length > 12)
363
{
364
a += k[0] + (((uint32_t)k[1])<<16);
365
b += k[2] + (((uint32_t)k[3])<<16);
366
c += k[4] + (((uint32_t)k[5])<<16);
367
mix(a,b,c);
368
length -= 12;
369
k += 6;
370
}
371
372
/*----------------------------- handle the last (probably partial) block */
373
k8 = (const uint8_t *)k;
374
switch(length)
375
{
376
case 12: c+=k[4]+(((uint32_t)k[5])<<16);
377
b+=k[2]+(((uint32_t)k[3])<<16);
378
a+=k[0]+(((uint32_t)k[1])<<16);
379
break;
380
case 11: c+=((uint32_t)k8[10])<<16; /* fall through */
381
case 10: c+=k[4];
382
b+=k[2]+(((uint32_t)k[3])<<16);
383
a+=k[0]+(((uint32_t)k[1])<<16);
384
break;
385
case 9 : c+=k8[8]; /* fall through */
386
case 8 : b+=k[2]+(((uint32_t)k[3])<<16);
387
a+=k[0]+(((uint32_t)k[1])<<16);
388
break;
389
case 7 : b+=((uint32_t)k8[6])<<16; /* fall through */
390
case 6 : b+=k[2];
391
a+=k[0]+(((uint32_t)k[1])<<16);
392
break;
393
case 5 : b+=k8[4]; /* fall through */
394
case 4 : a+=k[0]+(((uint32_t)k[1])<<16);
395
break;
396
case 3 : a+=((uint32_t)k8[2])<<16; /* fall through */
397
case 2 : a+=k[0];
398
break;
399
case 1 : a+=k8[0];
400
break;
401
case 0 : return c; /* zero length requires no mixing */
402
}
403
404
} else { /* need to read the key one byte at a time */
405
const uint8_t *k = (const uint8_t *)key;
406
407
/*--------------- all but the last block: affect some 32 bits of (a,b,c) */
408
while (length > 12)
409
{
410
a += k[0];
411
a += ((uint32_t)k[1])<<8;
412
a += ((uint32_t)k[2])<<16;
413
a += ((uint32_t)k[3])<<24;
414
b += k[4];
415
b += ((uint32_t)k[5])<<8;
416
b += ((uint32_t)k[6])<<16;
417
b += ((uint32_t)k[7])<<24;
418
c += k[8];
419
c += ((uint32_t)k[9])<<8;
420
c += ((uint32_t)k[10])<<16;
421
c += ((uint32_t)k[11])<<24;
422
mix(a,b,c);
423
length -= 12;
424
k += 12;
425
}
426
427
/*-------------------------------- last block: affect all 32 bits of (c) */
428
switch(length) /* all the case statements fall through */
429
{
430
case 12: c+=((uint32_t)k[11])<<24;
431
case 11: c+=((uint32_t)k[10])<<16;
432
case 10: c+=((uint32_t)k[9])<<8;
433
case 9 : c+=k[8];
434
case 8 : b+=((uint32_t)k[7])<<24;
435
case 7 : b+=((uint32_t)k[6])<<16;
436
case 6 : b+=((uint32_t)k[5])<<8;
437
case 5 : b+=k[4];
438
case 4 : a+=((uint32_t)k[3])<<24;
439
case 3 : a+=((uint32_t)k[2])<<16;
440
case 2 : a+=((uint32_t)k[1])<<8;
441
case 1 : a+=k[0];
442
break;
443
case 0 : return c;
444
}
445
}
446
447
final(a,b,c);
448
return c;
449
}
450
451
452
/*
453
* hashlittle2: return 2 32-bit hash values
454
*
455
* This is identical to hashlittle(), except it returns two 32-bit hash
456
* values instead of just one. This is good enough for hash table
457
* lookup with 2^^64 buckets, or if you want a second hash if you're not
458
* happy with the first, or if you want a probably-unique 64-bit ID for
459
* the key. *pc is better mixed than *pb, so use *pc first. If you want
460
* a 64-bit value do something like "*pc + (((uint64_t)*pb)<<32)".
461
*/
462
void hashlittle2(
463
const void *key, /* the key to hash */
464
size_t length, /* length of the key */
465
uint32_t *pc, /* IN: primary initval, OUT: primary hash */
466
uint32_t *pb) /* IN: secondary initval, OUT: secondary hash */
467
{
468
uint32_t a,b,c; /* internal state */
469
union { const void *ptr; size_t i; } u; /* needed for Mac Powerbook G4 */
470
471
/* Set up the internal state */
472
a = b = c = 0xdeadbeef + ((uint32_t)length) + *pc;
473
c += *pb;
474
475
u.ptr = key;
476
if (HASH_LITTLE_ENDIAN && ((u.i & 0x3) == 0)) {
477
const uint32_t *k = (const uint32_t *)key; /* read 32-bit chunks */
478
#ifdef VALGRIND
479
const uint8_t *k8;
480
#endif
481
482
/*------ all but last block: aligned reads and affect 32 bits of (a,b,c) */
483
while (length > 12)
484
{
485
a += k[0];
486
b += k[1];
487
c += k[2];
488
mix(a,b,c);
489
length -= 12;
490
k += 3;
491
}
492
493
/*----------------------------- handle the last (probably partial) block */
494
/*
495
* "k[2]&0xffffff" actually reads beyond the end of the string, but
496
* then masks off the part it's not allowed to read. Because the
497
* string is aligned, the masked-off tail is in the same word as the
498
* rest of the string. Every machine with memory protection I've seen
499
* does it on word boundaries, so is OK with this. But VALGRIND will
500
* still catch it and complain. The masking trick does make the hash
501
* noticably faster for short strings (like English words).
502
*/
503
#ifndef VALGRIND
504
505
switch(length)
506
{
507
case 12: c+=k[2]; b+=k[1]; a+=k[0]; break;
508
case 11: c+=k[2]&0xffffff; b+=k[1]; a+=k[0]; break;
509
case 10: c+=k[2]&0xffff; b+=k[1]; a+=k[0]; break;
510
case 9 : c+=k[2]&0xff; b+=k[1]; a+=k[0]; break;
511
case 8 : b+=k[1]; a+=k[0]; break;
512
case 7 : b+=k[1]&0xffffff; a+=k[0]; break;
513
case 6 : b+=k[1]&0xffff; a+=k[0]; break;
514
case 5 : b+=k[1]&0xff; a+=k[0]; break;
515
case 4 : a+=k[0]; break;
516
case 3 : a+=k[0]&0xffffff; break;
517
case 2 : a+=k[0]&0xffff; break;
518
case 1 : a+=k[0]&0xff; break;
519
case 0 : *pc=c; *pb=b; return; /* zero length strings require no mixing */
520
}
521
522
#else /* make valgrind happy */
523
524
k8 = (const uint8_t *)k;
525
switch(length)
526
{
527
case 12: c+=k[2]; b+=k[1]; a+=k[0]; break;
528
case 11: c+=((uint32_t)k8[10])<<16; /* fall through */
529
case 10: c+=((uint32_t)k8[9])<<8; /* fall through */
530
case 9 : c+=k8[8]; /* fall through */
531
case 8 : b+=k[1]; a+=k[0]; break;
532
case 7 : b+=((uint32_t)k8[6])<<16; /* fall through */
533
case 6 : b+=((uint32_t)k8[5])<<8; /* fall through */
534
case 5 : b+=k8[4]; /* fall through */
535
case 4 : a+=k[0]; break;
536
case 3 : a+=((uint32_t)k8[2])<<16; /* fall through */
537
case 2 : a+=((uint32_t)k8[1])<<8; /* fall through */
538
case 1 : a+=k8[0]; break;
539
case 0 : *pc=c; *pb=b; return; /* zero length strings require no mixing */
540
}
541
542
#endif /* !valgrind */
543
544
} else if (HASH_LITTLE_ENDIAN && ((u.i & 0x1) == 0)) {
545
const uint16_t *k = (const uint16_t *)key; /* read 16-bit chunks */
546
const uint8_t *k8;
547
548
/*--------------- all but last block: aligned reads and different mixing */
549
while (length > 12)
550
{
551
a += k[0] + (((uint32_t)k[1])<<16);
552
b += k[2] + (((uint32_t)k[3])<<16);
553
c += k[4] + (((uint32_t)k[5])<<16);
554
mix(a,b,c);
555
length -= 12;
556
k += 6;
557
}
558
559
/*----------------------------- handle the last (probably partial) block */
560
k8 = (const uint8_t *)k;
561
switch(length)
562
{
563
case 12: c+=k[4]+(((uint32_t)k[5])<<16);
564
b+=k[2]+(((uint32_t)k[3])<<16);
565
a+=k[0]+(((uint32_t)k[1])<<16);
566
break;
567
case 11: c+=((uint32_t)k8[10])<<16; /* fall through */
568
case 10: c+=k[4];
569
b+=k[2]+(((uint32_t)k[3])<<16);
570
a+=k[0]+(((uint32_t)k[1])<<16);
571
break;
572
case 9 : c+=k8[8]; /* fall through */
573
case 8 : b+=k[2]+(((uint32_t)k[3])<<16);
574
a+=k[0]+(((uint32_t)k[1])<<16);
575
break;
576
case 7 : b+=((uint32_t)k8[6])<<16; /* fall through */
577
case 6 : b+=k[2];
578
a+=k[0]+(((uint32_t)k[1])<<16);
579
break;
580
case 5 : b+=k8[4]; /* fall through */
581
case 4 : a+=k[0]+(((uint32_t)k[1])<<16);
582
break;
583
case 3 : a+=((uint32_t)k8[2])<<16; /* fall through */
584
case 2 : a+=k[0];
585
break;
586
case 1 : a+=k8[0];
587
break;
588
case 0 : *pc=c; *pb=b; return; /* zero length strings require no mixing */
589
}
590
591
} else { /* need to read the key one byte at a time */
592
const uint8_t *k = (const uint8_t *)key;
593
594
/*--------------- all but the last block: affect some 32 bits of (a,b,c) */
595
while (length > 12)
596
{
597
a += k[0];
598
a += ((uint32_t)k[1])<<8;
599
a += ((uint32_t)k[2])<<16;
600
a += ((uint32_t)k[3])<<24;
601
b += k[4];
602
b += ((uint32_t)k[5])<<8;
603
b += ((uint32_t)k[6])<<16;
604
b += ((uint32_t)k[7])<<24;
605
c += k[8];
606
c += ((uint32_t)k[9])<<8;
607
c += ((uint32_t)k[10])<<16;
608
c += ((uint32_t)k[11])<<24;
609
mix(a,b,c);
610
length -= 12;
611
k += 12;
612
}
613
614
/*-------------------------------- last block: affect all 32 bits of (c) */
615
switch(length) /* all the case statements fall through */
616
{
617
case 12: c+=((uint32_t)k[11])<<24;
618
case 11: c+=((uint32_t)k[10])<<16;
619
case 10: c+=((uint32_t)k[9])<<8;
620
case 9 : c+=k[8];
621
case 8 : b+=((uint32_t)k[7])<<24;
622
case 7 : b+=((uint32_t)k[6])<<16;
623
case 6 : b+=((uint32_t)k[5])<<8;
624
case 5 : b+=k[4];
625
case 4 : a+=((uint32_t)k[3])<<24;
626
case 3 : a+=((uint32_t)k[2])<<16;
627
case 2 : a+=((uint32_t)k[1])<<8;
628
case 1 : a+=k[0];
629
break;
630
case 0 : *pc=c; *pb=b; return; /* zero length strings require no mixing */
631
}
632
}
633
634
final(a,b,c);
635
*pc=c; *pb=b;
636
}
637
638
639
640
/*
641
* hashbig():
642
* This is the same as hashword() on big-endian machines. It is different
643
* from hashlittle() on all machines. hashbig() takes advantage of
644
* big-endian byte ordering.
645
*/
646
uint32_t hashbig( const void *key, size_t length, uint32_t initval)
647
{
648
uint32_t a,b,c;
649
union { const void *ptr; size_t i; } u; /* to cast key to (size_t) happily */
650
651
/* Set up the internal state */
652
a = b = c = 0xdeadbeef + ((uint32_t)length) + initval;
653
654
u.ptr = key;
655
if (HASH_BIG_ENDIAN && ((u.i & 0x3) == 0)) {
656
const uint32_t *k = (const uint32_t *)key; /* read 32-bit chunks */
657
#ifdef VALGRIND
658
const uint8_t *k8;
659
#endif
660
661
/*------ all but last block: aligned reads and affect 32 bits of (a,b,c) */
662
while (length > 12)
663
{
664
a += k[0];
665
b += k[1];
666
c += k[2];
667
mix(a,b,c);
668
length -= 12;
669
k += 3;
670
}
671
672
/*----------------------------- handle the last (probably partial) block */
673
/*
674
* "k[2]<<8" actually reads beyond the end of the string, but
675
* then shifts out the part it's not allowed to read. Because the
676
* string is aligned, the illegal read is in the same word as the
677
* rest of the string. Every machine with memory protection I've seen
678
* does it on word boundaries, so is OK with this. But VALGRIND will
679
* still catch it and complain. The masking trick does make the hash
680
* noticably faster for short strings (like English words).
681
*/
682
#ifndef VALGRIND
683
684
switch(length)
685
{
686
case 12: c+=k[2]; b+=k[1]; a+=k[0]; break;
687
case 11: c+=k[2]&0xffffff00; b+=k[1]; a+=k[0]; break;
688
case 10: c+=k[2]&0xffff0000; b+=k[1]; a+=k[0]; break;
689
case 9 : c+=k[2]&0xff000000; b+=k[1]; a+=k[0]; break;
690
case 8 : b+=k[1]; a+=k[0]; break;
691
case 7 : b+=k[1]&0xffffff00; a+=k[0]; break;
692
case 6 : b+=k[1]&0xffff0000; a+=k[0]; break;
693
case 5 : b+=k[1]&0xff000000; a+=k[0]; break;
694
case 4 : a+=k[0]; break;
695
case 3 : a+=k[0]&0xffffff00; break;
696
case 2 : a+=k[0]&0xffff0000; break;
697
case 1 : a+=k[0]&0xff000000; break;
698
case 0 : return c; /* zero length strings require no mixing */
699
}
700
701
#else /* make valgrind happy */
702
703
k8 = (const uint8_t *)k;
704
switch(length) /* all the case statements fall through */
705
{
706
case 12: c+=k[2]; b+=k[1]; a+=k[0]; break;
707
case 11: c+=((uint32_t)k8[10])<<8; /* fall through */
708
case 10: c+=((uint32_t)k8[9])<<16; /* fall through */
709
case 9 : c+=((uint32_t)k8[8])<<24; /* fall through */
710
case 8 : b+=k[1]; a+=k[0]; break;
711
case 7 : b+=((uint32_t)k8[6])<<8; /* fall through */
712
case 6 : b+=((uint32_t)k8[5])<<16; /* fall through */
713
case 5 : b+=((uint32_t)k8[4])<<24; /* fall through */
714
case 4 : a+=k[0]; break;
715
case 3 : a+=((uint32_t)k8[2])<<8; /* fall through */
716
case 2 : a+=((uint32_t)k8[1])<<16; /* fall through */
717
case 1 : a+=((uint32_t)k8[0])<<24; break;
718
case 0 : return c;
719
}
720
721
#endif /* !VALGRIND */
722
723
} else { /* need to read the key one byte at a time */
724
const uint8_t *k = (const uint8_t *)key;
725
726
/*--------------- all but the last block: affect some 32 bits of (a,b,c) */
727
while (length > 12)
728
{
729
a += ((uint32_t)k[0])<<24;
730
a += ((uint32_t)k[1])<<16;
731
a += ((uint32_t)k[2])<<8;
732
a += ((uint32_t)k[3]);
733
b += ((uint32_t)k[4])<<24;
734
b += ((uint32_t)k[5])<<16;
735
b += ((uint32_t)k[6])<<8;
736
b += ((uint32_t)k[7]);
737
c += ((uint32_t)k[8])<<24;
738
c += ((uint32_t)k[9])<<16;
739
c += ((uint32_t)k[10])<<8;
740
c += ((uint32_t)k[11]);
741
mix(a,b,c);
742
length -= 12;
743
k += 12;
744
}
745
746
/*-------------------------------- last block: affect all 32 bits of (c) */
747
switch(length) /* all the case statements fall through */
748
{
749
case 12: c+=k[11];
750
case 11: c+=((uint32_t)k[10])<<8;
751
case 10: c+=((uint32_t)k[9])<<16;
752
case 9 : c+=((uint32_t)k[8])<<24;
753
case 8 : b+=k[7];
754
case 7 : b+=((uint32_t)k[6])<<8;
755
case 6 : b+=((uint32_t)k[5])<<16;
756
case 5 : b+=((uint32_t)k[4])<<24;
757
case 4 : a+=k[3];
758
case 3 : a+=((uint32_t)k[2])<<8;
759
case 2 : a+=((uint32_t)k[1])<<16;
760
case 1 : a+=((uint32_t)k[0])<<24;
761
break;
762
case 0 : return c;
763
}
764
}
765
766
final(a,b,c);
767
return c;
768
}
769
Loggerhead is a web-based interface for Breezy
Version: 2.0.1