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
25namespace WTF {
26
27// Golden ratio - arbitrary start value to avoid mapping all 0's to all 0's
28static 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
34inline 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
74inline 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
114inline 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