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