Changeset 52758 in webkit for trunk/JavaScriptCore/wtf/HashFunctions.h

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.

• JavaScriptCore.exp:
• runtime/UStringImpl.cpp:
• runtime/UStringImpl.h:

(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:

• trunk/JavaScriptCore/wtf/HashFunctions.h (modified) (2 diffs)

trunk/JavaScriptCore/wtf/HashFunctions.h

@@ -23 +23 @@
 
 #include "RefPtr.h"
+#include "wtf/unicode/Unicode.h"
 #include <stdint.h>
 
@@ -178 +179 @@
     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;
+
+        // 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 = 0x80000000;
+
+        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;
+
+        // 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 = 0x80000000;
+
+        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;
+
+        // 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 = 0x80000000;
+        
+        return hash;
+    }
+
 } // namespace WTF