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