libStatGen Software 1
Loading...
Searching...
No Matches
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
45unsigned 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
100unsigned 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}