/* * Copyright (C) 2005, 2006, 2008, 2010 Apple Inc. All rights reserved. * * This library is free software; you can redistribute it and/or * modify it under the terms of the GNU Library General Public * License as published by the Free Software Foundation; either * version 2 of the License, or (at your option) any later version. * * This library is distributed in the hope that it will be useful, * but WITHOUT ANY WARRANTY; without even the implied warranty of * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU * Library General Public License for more details. * * You should have received a copy of the GNU Library General Public License * along with this library; see the file COPYING.LIB. If not, write to * the Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor, * Boston, MA 02110-1301, USA. * */ #ifndef WTF_StringHashFunctions_h #define WTF_StringHashFunctions_h #include <wtf/unicode/Unicode.h> namespace WTF { // Golden ratio - arbitrary start value to avoid mapping all 0's to all 0's static const unsigned stringHashingStartValue = 0x9e3779b9U; // stringHash methods based on Paul Hsieh's SuperFastHash. // http://www.azillionmonkeys.com/qed/hash.html // char* data is interpreted as latin-encoded (zero extended to 16 bits). inline unsigned stringHash(const UChar* data, unsigned length) { unsigned hash = WTF::stringHashingStartValue; unsigned rem = length & 1; length >>= 1; // Main loop for (; length > 0; length--) { hash += data[0]; unsigned tmp = (data[1] << 11) ^ hash; hash = (hash << 16) ^ tmp; data += 2; hash += hash >> 11; } // Handle end case if (rem) { hash += data[0]; hash ^= hash << 11; hash += hash >> 17; } // Force "avalanching" of final 127 bits hash ^= hash << 3; hash += hash >> 5; hash ^= hash << 2; hash += hash >> 15; hash ^= hash << 10; hash &= 0x7fffffff; // this avoids ever returning a hash code of 0, since that is used to // signal "hash not computed yet", using a value that is likely to be // effectively the same as 0 when the low bits are masked if (hash == 0) hash = 0x40000000; return hash; } inline unsigned stringHash(const char* data, unsigned length) { unsigned hash = WTF::stringHashingStartValue; unsigned rem = length & 1; length >>= 1; // Main loop for (; length > 0; length--) { hash += static_cast<unsigned char>(data[0]); unsigned tmp = (static_cast<unsigned char>(data[1]) << 11) ^ hash; hash = (hash << 16) ^ tmp; data += 2; hash += hash >> 11; } // Handle end case if (rem) { hash += static_cast<unsigned char>(data[0]); hash ^= hash << 11; hash += hash >> 17; } // Force "avalanching" of final 127 bits hash ^= hash << 3; hash += hash >> 5; hash ^= hash << 2; hash += hash >> 15; hash ^= hash << 10; hash &= 0x7fffffff; // this avoids ever returning a hash code of 0, since that is used to // signal "hash not computed yet", using a value that is likely to be // effectively the same as 0 when the low bits are masked if (hash == 0) hash = 0x40000000; return hash; } inline unsigned stringHash(const char* data) { unsigned hash = WTF::stringHashingStartValue; // Main loop for (;;) { unsigned char b0 = data[0]; if (!b0) break; unsigned char b1 = data[1]; if (!b1) { hash += b0; hash ^= hash << 11; hash += hash >> 17; break; } hash += b0; unsigned tmp = (b1 << 11) ^ hash; hash = (hash << 16) ^ tmp; data += 2; hash += hash >> 11; } // Force "avalanching" of final 127 bits. hash ^= hash << 3; hash += hash >> 5; hash ^= hash << 2; hash += hash >> 15; hash ^= hash << 10; hash &= 0x7fffffff; // This avoids ever returning a hash code of 0, since that is used to // signal "hash not computed yet", using a value that is likely to be // effectively the same as 0 when the low bits are masked. if (hash == 0) hash = 0x40000000; return hash; } } // namespace WTF #endif // WTF_StringHashFunctions_h