1 /*++
2 Copyright (c) 2006 Microsoft Corporation
3
4 Module Name:
5
6 hash.cpp
7
8 Abstract:
9
10 Basic hash computation support.
11
12 Author:
13
14 Leonardo de Moura (leonardo) 2006-09-11.
15
16 Revision History:
17
18 --*/
19
20 #include "util/debug.h"
21 #include "util/hash.h"
22 #include <string.h>
23
read_unsigned(const char * s)24 static unsigned read_unsigned(const char *s) {
25 unsigned n;
26 memcpy(&n, s, sizeof(unsigned));
27 return n;
28 }
29
30 // I'm using Bob Jenkin's hash function.
31 // http://burtleburtle.net/bob/hash/doobs.html
string_hash(const char * str,unsigned length,unsigned init_value)32 unsigned string_hash(const char * str, unsigned length, unsigned init_value) {
33 unsigned a, b, c, len;
34
35 /* Set up the internal state */
36 len = length;
37 a = b = 0x9e3779b9; /* the golden ratio; an arbitrary value */
38 c = init_value; /* the previous hash value */
39
40 /*---------------------------------------- handle most of the key */
41 SASSERT(sizeof(unsigned) == 4);
42 while (len >= 12) {
43 a += read_unsigned(str);
44 b += read_unsigned(str+4);
45 c += read_unsigned(str+8);
46 mix(a,b,c);
47 str += 12; len -= 12;
48 }
49
50 /*------------------------------------- handle the last 11 bytes */
51 c += length;
52 switch(len) { /* all the case statements fall through */
53 case 11:
54 c+=((unsigned)str[10]<<24);
55 Z3_fallthrough;
56 case 10:
57 c+=((unsigned)str[9]<<16);
58 Z3_fallthrough;
59 case 9 :
60 c+=((unsigned)str[8]<<8);
61 Z3_fallthrough;
62 /* the first byte of c is reserved for the length */
63 case 8 :
64 b+=((unsigned)str[7]<<24);
65 Z3_fallthrough;
66 case 7 :
67 b+=((unsigned)str[6]<<16);
68 Z3_fallthrough;
69 case 6 :
70 b+=((unsigned)str[5]<<8);
71 Z3_fallthrough;
72 case 5 :
73 b+=str[4];
74 Z3_fallthrough;
75 case 4 :
76 a+=((unsigned)str[3]<<24);
77 Z3_fallthrough;
78 case 3 :
79 a+=((unsigned)str[2]<<16);
80 Z3_fallthrough;
81 case 2 :
82 a+=((unsigned)str[1]<<8);
83 Z3_fallthrough;
84 case 1 :
85 a+=str[0];
86 /* case 0: nothing left to add */
87 break;
88 }
89 mix(a,b,c);
90 /*-------------------------------------------- report the result */
91 return c;
92 }
93
94