Ignore:
Timestamp:
Jan 4, 2010, 2:00:38 PM (15 years ago)
Author:
[email protected]
Message:

JavaScriptCore: ​https://bugs.webkit.org/show_bug.cgi?id=33163
Add string hashing functions to WTF.
Use WTF's string hashing functions from UStringImpl.

Reviewed by Sam Weinig.

(JSC::UStringImpl::computeHash):

  • wtf/HashFunctions.h:

(WTF::stringHash):

WebCore: ​https://bugs.webkit.org/show_bug.cgi?id=33163
Use WTF's string hashing functions from StringImpl.

Reviewed by Sam Weinig.

  • platform/text/StringImpl.h:

(WebCore::StringImpl::computeHash):

File:
1 edited

Legend:

Unmodified
Added
Removed

  • trunk/JavaScriptCore/runtime/UStringImpl.cpp

    r52472 r52758  
    8282}
    8383
    84 // Golden ratio - arbitrary start value to avoid mapping all 0's to all 0's
    85 // or anything like that.
    86 const unsigned PHI = 0x9e3779b9U;
    87 
    88 // Paul Hsieh's SuperFastHash
    89 // http://www.azillionmonkeys.com/qed/hash.html
    90 unsigned UStringImpl::computeHash(const UChar* s, int len)
    91 {
    92     unsigned l = len;
    93     uint32_t hash = PHI;
    94     uint32_t tmp;
    95 
    96     int rem = l & 1;
    97     l >>= 1;
    98 
    99     // Main loop
    100     for (; l > 0; l--) {
    101         hash += s[0];
    102         tmp = (s[1] << 11) ^ hash;
    103         hash = (hash << 16) ^ tmp;
    104         s += 2;
    105         hash += hash >> 11;
    106     }
    107 
    108     // Handle end case
    109     if (rem) {
    110         hash += s[0];
    111         hash ^= hash << 11;
    112         hash += hash >> 17;
    113     }
    114 
    115     // Force "avalanching" of final 127 bits
    116     hash ^= hash << 3;
    117     hash += hash >> 5;
    118     hash ^= hash << 2;
    119     hash += hash >> 15;
    120     hash ^= hash << 10;
    121 
    122     // this avoids ever returning a hash code of 0, since that is used to
    123     // signal "hash not computed yet", using a value that is likely to be
    124     // effectively the same as 0 when the low bits are masked
    125     if (hash == 0)
    126         hash = 0x80000000;
    127 
    128     return hash;
    12984}
    130 
    131 // Paul Hsieh's SuperFastHash
    132 // http://www.azillionmonkeys.com/qed/hash.html
    133 unsigned UStringImpl::computeHash(const char* s, int l)
    134 {
    135     // This hash is designed to work on 16-bit chunks at a time. But since the normal case
    136     // (above) is to hash UTF-16 characters, we just treat the 8-bit chars as if they
    137     // were 16-bit chunks, which should give matching results
    138 
    139     uint32_t hash = PHI;
    140     uint32_t tmp;
    141 
    142     size_t rem = l & 1;
    143     l >>= 1;
    144 
    145     // Main loop
    146     for (; l > 0; l--) {
    147         hash += static_cast<unsigned char>(s[0]);
    148         tmp = (static_cast<unsigned char>(s[1]) << 11) ^ hash;
    149         hash = (hash << 16) ^ tmp;
    150         s += 2;
    151         hash += hash >> 11;
    152     }
    153 
    154     // Handle end case
    155     if (rem) {
    156         hash += static_cast<unsigned char>(s[0]);
    157         hash ^= hash << 11;
    158         hash += hash >> 17;
    159     }
    160 
    161     // Force "avalanching" of final 127 bits
    162     hash ^= hash << 3;
    163     hash += hash >> 5;
    164     hash ^= hash << 2;
    165     hash += hash >> 15;
    166     hash ^= hash << 10;
    167 
    168     // this avoids ever returning a hash code of 0, since that is used to
    169     // signal "hash not computed yet", using a value that is likely to be
    170     // effectively the same as 0 when the low bits are masked
    171     if (hash == 0)
    172         hash = 0x80000000;
    173 
    174     return hash;
    175 }
    176 
    177 }
Note: See TracChangeset for help on using the changeset viewer.