libStatGen Software  1
Hash.cpp
1 /*
2  * Copyright (C) 2010 Regents of the University of Michigan
3  *
4  * This program is free software: you can redistribute it and/or modify
5  * it under the terms of the GNU General Public License as published by
6  * the Free Software Foundation, either version 3 of the License, or
7  * (at your option) any later version.
8  *
9  * This program is distributed in the hope that it will be useful,
10  * but WITHOUT ANY WARRANTY; without even the implied warranty of
11  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
12  * GNU General Public License for more details.
13  *
14  * You should have received a copy of the GNU General Public License
15  * along with this program. If not, see <http://www.gnu.org/licenses/>.
16  */
17 
18 #include "Hash.h"
19 
20 #include <ctype.h>
21 
22 // ********************************************************
23 //
24 // This code is based on the original by Robert Jenkins.
25 //
26 // http://burtleburtle.net/bob/hash/doobs.html
27 //
28 // ********************************************************
29 
30 #define MIX_INTEGERS(a,b,c) \
31  { \
32  a -= b; a -= c; a ^= (c>>13); \
33  b -= c; b -= a; b ^= (a<<8); \
34  c -= a; c -= b; c ^= (b>>13); \
35  a -= b; a -= c; a ^= (c>>12); \
36  b -= c; b -= a; b ^= (a<<16); \
37  c -= a; c -= b; c ^= (b>>5); \
38  a -= b; a -= c; a ^= (c>>3); \
39  b -= c; b -= a; b ^= (a<<10); \
40  c -= a; c -= b; c ^= (b>>15); \
41  }
42 
43 #define ui (unsigned int)
44 
45 unsigned int hash(const unsigned char * key, unsigned int length, unsigned int initval)
46 {
47  unsigned int a = 0x9e3779b9;
48  unsigned int b = 0x9e3779b9;
49  unsigned int c = initval;
50  unsigned int len = length;
51 
52  /*---------------------------------------- handle most of the key */
53  while (len >= 12)
54  {
55  a += (key[0] +(ui(key[1])<<8) +(ui(key[2])<<16) +(ui(key[3])<<24));
56  b += (key[4] +(ui(key[5])<<8) +(ui(key[6])<<16) +(ui(key[7])<<24));
57  c += (key[8] +(ui(key[9])<<8) +(ui(key[10])<<16)+(ui(key[11])<<24));
58  MIX_INTEGERS(a,b,c);
59  key += 12;
60  len -= 12;
61  }
62 
63  /*------------------------------------- handle the last 11 bytes */
64  c += length;
65  switch (len) /* all the case statements fall through */
66  {
67  case 11:
68  c+=(ui(key[10])<<24);
69  case 10:
70  c+=(ui(key[9])<<16);
71  case 9 :
72  c+=(ui(key[8])<<8);
73  /* the first byte of c is reserved for the length */
74 
75  case 8 :
76  b+=(ui(key[7])<<24);
77  case 7 :
78  b+=(ui(key[6])<<16);
79  case 6 :
80  b+=(ui(key[5])<<8);
81  case 5 :
82  b+=key[4];
83 
84  case 4 :
85  a+=(ui(key[3])<<24);
86  case 3 :
87  a+=(ui(key[2])<<16);
88  case 2 :
89  a+=(ui(key[1])<<8);
90  case 1 :
91  a+=key[0];
92  /* case 0: nothing left to add */
93  }
94  MIX_INTEGERS(a,b,c);
95 
96  /*-------------------------------------------- report the result */
97  return c;
98 }
99 
100 unsigned int hash_no_case(const unsigned char * key, unsigned int length, unsigned int initval)
101 {
102  unsigned int a = 0x9e3779b9;
103  unsigned int b = 0x9e3779b9;
104  unsigned int c = initval;
105  unsigned int len = length;
106 
107  /*---------------------------------------- handle most of the key */
108  while (len >= 12)
109  {
110  a += (toupper(key[0]) +(ui(toupper(key[1]))<<8) +(ui(toupper(key[2]))<<16) +(ui(toupper(key[3]))<<24));
111  b += (toupper(key[4]) +(ui(toupper(key[5]))<<8) +(ui(toupper(key[6]))<<16) +(ui(toupper(key[7]))<<24));
112  c += (toupper(key[8]) +(ui(toupper(key[9]))<<8) +(ui(toupper(key[10]))<<16)+(ui(toupper(key[11]))<<24));
113  MIX_INTEGERS(a,b,c);
114  key += 12;
115  len -= 12;
116  }
117 
118  /*------------------------------------- handle the last 11 bytes */
119  c += length;
120  switch (len) /* all the case statements fall through */
121  {
122  case 11:
123  c+=(ui(toupper(key[10]))<<24);
124  case 10:
125  c+=(ui(toupper(key[9]))<<16);
126  case 9 :
127  c+=(ui(toupper(key[8]))<<8);
128  /* the first byte of c is reserved for the length */
129 
130  case 8 :
131  b+=(ui(toupper(key[7]))<<24);
132  case 7 :
133  b+=(ui(toupper(key[6]))<<16);
134  case 6 :
135  b+=(ui(toupper(key[5]))<<8);
136  case 5 :
137  b+=toupper(key[4]);
138 
139  case 4 :
140  a+=(ui(toupper(key[3]))<<24);
141  case 3 :
142  a+=(ui(toupper(key[2]))<<16);
143  case 2 :
144  a+=(ui(toupper(key[1]))<<8);
145  case 1 :
146  a+=toupper(key[0]);
147  /* case 0: nothing left to add */
148  }
149  MIX_INTEGERS(a,b,c);
150 
151  /*-------------------------------------------- report the result */
152  return c;
153 }