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
