Revert r53454, since it causes much sadness in this world.
[WebKit-https.git] / JavaScriptCore / wtf / StringHashFunctions.h
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