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