1 | /* |
2 | * Copyright (C) 2005, 2006, 2008, 2010 Apple Inc. All rights reserved. |
3 | * |
4 | * This library is free software; you can redistribute it and/or |
5 | * modify it under the terms of the GNU Library General Public |
6 | * License as published by the Free Software Foundation; either |
7 | * version 2 of the License, or (at your option) any later version. |
8 | * |
9 | * This library 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 GNU |
12 | * Library General Public License for more details. |
13 | * |
14 | * You should have received a copy of the GNU Library General Public License |
15 | * along with this library; see the file COPYING.LIB. If not, write to |
16 | * the Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor, |
17 | * Boston, MA 02110-1301, USA. |
18 | * |
19 | */ |
20 | #ifndef WTF_StringHashFunctions_h |
21 | #define WTF_StringHashFunctions_h |
22 | |
23 | #include <wtf/unicode/Unicode.h> |
24 | |
25 | namespace WTF { |
26 | |
27 | // Golden ratio - arbitrary start value to avoid mapping all 0's to all 0's |
28 | static const unsigned stringHashingStartValue = 0x9e3779b9U; |
29 | |
30 | // stringHash methods based on Paul Hsieh's SuperFastHash. |
31 | // http://www.azillionmonkeys.com/qed/hash.html |
32 | // char* data is interpreted as latin-encoded (zero extended to 16 bits). |
33 | |
34 | inline unsigned stringHash(const UChar* data, unsigned length) |
35 | { |
36 | unsigned hash = WTF::stringHashingStartValue; |
37 | unsigned rem = length & 1; |
38 | length >>= 1; |
39 | |
40 | // Main loop |
41 | for (; length > 0; length--) { |
42 | hash += data[0]; |
43 | unsigned tmp = (data[1] << 11) ^ hash; |
44 | hash = (hash << 16) ^ tmp; |
45 | data += 2; |
46 | hash += hash >> 11; |
47 | } |
48 | |
49 | // Handle end case |
50 | if (rem) { |
51 | hash += data[0]; |
52 | hash ^= hash << 11; |
53 | hash += hash >> 17; |
54 | } |
55 | |
56 | // Force "avalanching" of final 127 bits |
57 | hash ^= hash << 3; |
58 | hash += hash >> 5; |
59 | hash ^= hash << 2; |
60 | hash += hash >> 15; |
61 | hash ^= hash << 10; |
62 | |
63 | hash &= 0x7fffffff; |
64 | |
65 | // this avoids ever returning a hash code of 0, since that is used to |
66 | // signal "hash not computed yet", using a value that is likely to be |
67 | // effectively the same as 0 when the low bits are masked |
68 | if (hash == 0) |
69 | hash = 0x40000000; |
70 | |
71 | return hash; |
72 | } |
73 | |
74 | inline unsigned stringHash(const char* data, unsigned length) |
75 | { |
76 | unsigned hash = WTF::stringHashingStartValue; |
77 | unsigned rem = length & 1; |
78 | length >>= 1; |
79 | |
80 | // Main loop |
81 | for (; length > 0; length--) { |
82 | hash += static_cast<unsigned char>(data[0]); |
83 | unsigned tmp = (static_cast<unsigned char>(data[1]) << 11) ^ hash; |
84 | hash = (hash << 16) ^ tmp; |
85 | data += 2; |
86 | hash += hash >> 11; |
87 | } |
88 | |
89 | // Handle end case |
90 | if (rem) { |
91 | hash += static_cast<unsigned char>(data[0]); |
92 | hash ^= hash << 11; |
93 | hash += hash >> 17; |
94 | } |
95 | |
96 | // Force "avalanching" of final 127 bits |
97 | hash ^= hash << 3; |
98 | hash += hash >> 5; |
99 | hash ^= hash << 2; |
100 | hash += hash >> 15; |
101 | hash ^= hash << 10; |
102 | |
103 | hash &= 0x7fffffff; |
104 | |
105 | // this avoids ever returning a hash code of 0, since that is used to |
106 | // signal "hash not computed yet", using a value that is likely to be |
107 | // effectively the same as 0 when the low bits are masked |
108 | if (hash == 0) |
109 | hash = 0x40000000; |
110 | |
111 | return hash; |
112 | } |
113 | |
114 | inline unsigned stringHash(const char* data) |
115 | { |
116 | unsigned hash = WTF::stringHashingStartValue; |
117 | |
118 | // Main loop |
119 | for (;;) { |
120 | unsigned char b0 = data[0]; |
121 | if (!b0) |
122 | break; |
123 | unsigned char b1 = data[1]; |
124 | if (!b1) { |
125 | hash += b0; |
126 | hash ^= hash << 11; |
127 | hash += hash >> 17; |
128 | break; |
129 | } |
130 | hash += b0; |
131 | unsigned tmp = (b1 << 11) ^ hash; |
132 | hash = (hash << 16) ^ tmp; |
133 | data += 2; |
134 | hash += hash >> 11; |
135 | } |
136 | |
137 | // Force "avalanching" of final 127 bits. |
138 | hash ^= hash << 3; |
139 | hash += hash >> 5; |
140 | hash ^= hash << 2; |
141 | hash += hash >> 15; |
142 | hash ^= hash << 10; |
143 | |
144 | hash &= 0x7fffffff; |
145 | |
146 | // This avoids ever returning a hash code of 0, since that is used to |
147 | // signal "hash not computed yet", using a value that is likely to be |
148 | // effectively the same as 0 when the low bits are masked. |
149 | if (hash == 0) |
150 | hash = 0x40000000; |
151 | |
152 | return hash; |
153 | } |
154 | |
155 | } // namespace WTF |
156 | |
157 | #endif // WTF_StringHashFunctions_h |
158 | |