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

source code of qtbase/tests/baselineserver/shared/lookup3.cpp