Changeset 9501 in webkit for trunk/JavaScriptCore/kjs/ustring.cpp

Timestamp:

Jun 27, 2005, 5:02:08 PM (20 years ago)

Author:

mjs

Message:

Reviewed by Darin.

• replace hash functions with better ones

• JavaScriptCore.pbproj/project.pbxproj: Add new file to build.
• kjs/interpreter_map.cpp: (KJS::InterpreterMap::computeHash): Use shared pointer hash.
• kjs/pointer_hash.h: Added. (KJS::pointerHash): Pointer hash based on 32-bit mix and 64-bit mix hashes.
• kjs/protected_values.cpp: (KJS::ProtectedValues::computeHash): Use shared pointer hash.
• kjs/ustring.cpp: (KJS::UString::Rep::computeHash): Use SuperFastHash algorithm.

File:

• trunk/JavaScriptCore/kjs/ustring.cpp (modified) (1 diff)

trunk/JavaScriptCore/kjs/ustring.cpp

@@ -263 +263 @@
 const unsigned PHI = 0x9e3779b9U;
 
-// This hash algorithm comes from:
-// http://burtleburtle.net/bob/hash/hashfaq.html
-// http://burtleburtle.net/bob/hash/doobs.html
-unsigned UString::Rep::computeHash(const UChar *s, int length)
-{
-    int prefixLength = length < 8 ? length : 8;
-    int suffixPosition = length < 16 ? 8 : length - 8;
-
-    unsigned h = PHI;
-    h += length;
-    h += (h << 10); 
-    h ^= (h << 6); 
-
-    for (int i = 0; i < prefixLength; i++) {
-        h += s[i].uc; 
-        h += (h << 10); 
-        h ^= (h << 6); 
-    }
-    for (int i = suffixPosition; i < length; i++){
-        h += s[i].uc; 
-        h += (h << 10); 
-        h ^= (h << 6); 
-    }
-
-    h += (h << 3);
-    h ^= (h >> 11);
-    h += (h << 15);
- 
-    if (h == 0)
-        h = 0x80000000;
-
-    return h;
-}
-
-// This hash algorithm comes from:
-// http://burtleburtle.net/bob/hash/hashfaq.html
-// http://burtleburtle.net/bob/hash/doobs.html
+// Paul Hsieh's SuperFastHash
+// http://www.azillionmonkeys.com/qed/hash.html
+unsigned UString::Rep::computeHash(const UChar *s, int len)
+{
+  unsigned l = len;
+  uint32_t hash = PHI;
+  uint32_t tmp;
+
+  int rem = l & 1;
+  l >>= 1;
+
+  // Main loop
+  for (; l > 0; l--) {
+    hash += s[0].uc;
+    tmp = (s[1].uc << 11) ^ hash;
+    hash = (hash << 16) ^ tmp;
+    s += 2;
+    hash += hash >> 11;
+  }
+
+  // Handle end case
+  if (rem) {
+    hash += s[0].uc;
+    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;
+}
+
+// Paul Hsieh's SuperFastHash
+// http://www.azillionmonkeys.com/qed/hash.html
 unsigned UString::Rep::computeHash(const char *s)
 {
-    int length = strlen(s);
-    int prefixLength = length < 8 ? length : 8;
-    int suffixPosition = length < 16 ? 8 : length - 8;
-
-    unsigned h = PHI;
-    h += length;
-    h += (h << 10); 
-    h ^= (h << 6); 
-
-    for (int i = 0; i < prefixLength; i++) {
-        h += (unsigned char)s[i];
-        h += (h << 10); 
-        h ^= (h << 6); 
-    }
-    for (int i = suffixPosition; i < length; i++) {
-        h += (unsigned char)s[i];
-        h += (h << 10); 
-        h ^= (h << 6); 
-    }
-
-    h += (h << 3);
-    h ^= (h >> 11);
-    h += (h << 15);
-
-    if (h == 0)
-        h = 0x80000000;
-
-    return h;
+  // This hash is designed to work on 16-bit chunks at a time. But since the normal case
+  // (above) is to hash UTF-16 characters, we just treat the 8-bit chars as if they
+  // were 16-bit chunks, which should give matching results
+
+  uint32_t hash = PHI;
+  uint32_t tmp;
+  unsigned l = strlen(s);
+  
+  int rem = l & 1;
+  l >>= 1;
+
+  // Main loop
+  for (; l > 0; l--) {
+    hash += (unsigned char)s[0];
+    tmp = ((unsigned char)s[1] << 11) ^ hash;
+    hash = (hash << 16) ^ tmp;
+    s += 2;
+    hash += hash >> 11;
+  }
+
+  // Handle end case
+  if (rem) {
+    hash += (unsigned char)s[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;
 }