[webkit-changes] cvs commit: JavaScriptCore/kjs pointer_hash.h
interpreter_map.cpp protected_values.cpp ustring.cpp
Maciej
mjs at opensource.apple.com
Mon Jun 27 17:02:08 PDT 2005
mjs 05/06/27 17:02:08
Modified: . ChangeLog
kjs interpreter_map.cpp protected_values.cpp
ustring.cpp
Added: kjs pointer_hash.h
Log:
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.
Revision Changes Path
1.722 +16 -0 JavaScriptCore/ChangeLog
Index: ChangeLog
===================================================================
RCS file: /cvs/root/JavaScriptCore/ChangeLog,v
retrieving revision 1.721
retrieving revision 1.722
diff -u -r1.721 -r1.722
--- ChangeLog 22 Jun 2005 17:26:15 -0000 1.721
+++ ChangeLog 28 Jun 2005 00:02:07 -0000 1.722
@@ -1,3 +1,19 @@
+2005-06-26 Maciej Stachowiak <mjs at apple.com>
+
+ 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.
+
2005-06-22 Darin Adler <darin at apple.com>
Change by Anders Carlsson.
1.2 +2 -31 JavaScriptCore/kjs/interpreter_map.cpp
Index: interpreter_map.cpp
===================================================================
RCS file: /cvs/root/JavaScriptCore/kjs/interpreter_map.cpp,v
retrieving revision 1.1
retrieving revision 1.2
diff -u -r1.1 -r1.2
--- interpreter_map.cpp 9 Apr 2004 20:07:47 -0000 1.1
+++ interpreter_map.cpp 28 Jun 2005 00:02:07 -0000 1.2
@@ -20,6 +20,7 @@
*/
#include "interpreter_map.h"
+#include "pointer_hash.h"
namespace KJS {
@@ -165,39 +166,9 @@
free(oldTable);
}
-// Golden ratio - arbitrary start value to avoid mapping all 0's to all 0's
-// or anything like that.
-const unsigned PHI = 0x9e3779b9U;
-
-// This hash algorithm comes from:
-// http://burtleburtle.net/bob/hash/hashfaq.html
-// http://burtleburtle.net/bob/hash/doobs.html
unsigned InterpreterMap::computeHash(ObjectImp *pointer)
{
- int length = sizeof(ObjectImp *);
- char s[sizeof(ObjectImp *)];
-
- memcpy((void *)s, (void *)&pointer, sizeof(ObjectImp *));
-
- unsigned h = PHI;
- h += length;
- h += (h << 10);
- h ^= (h << 6);
-
- for (int i = 0; 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;
+ return pointerHash(pointer);
}
1.4 +4 -49 JavaScriptCore/kjs/protected_values.cpp
Index: protected_values.cpp
===================================================================
RCS file: /cvs/root/JavaScriptCore/kjs/protected_values.cpp,v
retrieving revision 1.3
retrieving revision 1.4
diff -u -r1.3 -r1.4
--- protected_values.cpp 18 Dec 2004 00:43:37 -0000 1.3
+++ protected_values.cpp 28 Jun 2005 00:02:08 -0000 1.4
@@ -21,7 +21,10 @@
*/
#include "protected_values.h"
+
+#include "pointer_hash.h"
#include "simple_number.h"
+#include <stdint.h>
namespace KJS {
@@ -183,57 +186,9 @@
free(oldTable);
}
-// Golden ratio - arbitrary start value to avoid mapping all 0's to all 0's
-// or anything like that.
-const unsigned PHI = 0x9e3779b9U;
-
-template <int size> static unsigned hash(ValueImp *pointer);
-
-template <> static inline unsigned hash<4>(ValueImp *pointer)
-{
- int a = (int)PHI;
- int b = (int)pointer;
- int c = 0;
-
- a -= b; a -= c; a ^= (c>>13);
- b -= c; b -= a; b ^= (a<<8);
- c -= a; c -= b; c ^= (b>>13);
- a -= b; a -= c; a ^= (c>>12);
- b -= c; b -= a; b ^= (a<<16);
- c -= a; c -= b; c ^= (b>>5);
- a -= b; a -= c; a ^= (c>>3);
- b -= c; b -= a; b ^= (a<<10);
- c -= a; c -= b; c ^= (b>>15);
-
- return (unsigned)c;
-}
-
-template <> static inline unsigned hash<8>(ValueImp *pointer)
-{
- int a = (int)PHI;
- int b = (int)(long)pointer;
- int c = (int)(((long)pointer >> 16) >> 16);
-
- a -= b; a -= c; a ^= (c>>13);
- b -= c; b -= a; b ^= (a<<8);
- c -= a; c -= b; c ^= (b>>13);
- a -= b; a -= c; a ^= (c>>12);
- b -= c; b -= a; b ^= (a<<16);
- c -= a; c -= b; c ^= (b>>5);
- a -= b; a -= c; a ^= (c>>3);
- b -= c; b -= a; b ^= (a<<10);
- c -= a; c -= b; c ^= (b>>15);
-
- return (unsigned)c;
-}
-
-
-// This hash algorithm comes from:
-// http://burtleburtle.net/bob/hash/hashfaq.html
-// http://burtleburtle.net/bob/hash/doobs.html
unsigned ProtectedValues::computeHash(ValueImp *pointer)
{
- return hash<sizeof(ValueImp *)>(pointer);
+ return pointerHash(pointer);
}
} // namespace
1.56 +81 -60 JavaScriptCore/kjs/ustring.cpp
Index: ustring.cpp
===================================================================
RCS file: /cvs/root/JavaScriptCore/kjs/ustring.cpp,v
retrieving revision 1.55
retrieving revision 1.56
diff -u -r1.55 -r1.56
--- ustring.cpp 16 May 2005 18:57:29 -0000 1.55
+++ ustring.cpp 28 Jun 2005 00:02:08 -0000 1.56
@@ -262,73 +262,94 @@
// or anything like that.
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);
- }
+// 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;
- h += (h << 3);
- h ^= (h >> 11);
- h += (h << 15);
-
- if (h == 0)
- h = 0x80000000;
-
- return h;
+ return hash;
}
-// 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 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);
+ // 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;
- if (h == 0)
- h = 0x80000000;
+ // 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 h;
+ return hash;
}
// put these early so they can be inlined
1.1 JavaScriptCore/kjs/pointer_hash.h
Index: pointer_hash.h
===================================================================
// -*- c-basic-offset: 2 -*-
/*
* This file is part of the KDE libraries
* Copyright (C) 2005 Apple Computer, Inc.
*
* This library is free software; you can redistribute it and/or
* modify it under the terms of the GNU Library General Public
* License as published by the Free Software Foundation; either
* version 2 of the License, or (at your option) any later version.
*
* This library is distributed in the hope that it will be useful,
* but WITHOUT ANY WARRANTY; without even the implied warranty of
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
* Library General Public License for more details.
*
* You should have received a copy of the GNU Library General Public License
* along with this library; see the file COPYING.LIB. If not, write to
* the Free Software Foundation, Inc., 59 Temple Place - Suite 330,
* Boston, MA 02111-1307, USA.
*
*/
#ifndef _KJS_POINTER_HASH_H_
#define _KJS_POINTER_HASH_H_
namespace KJS {
#include <stdint.h>
template <int size> unsigned pointerHash(void *pointer);
// Thomas Wang's 32 bit mix
// http://www.cris.com/~Ttwang/tech/inthash.htm
template <> inline unsigned pointerHash<4>(void *pointer)
{
uint32_t key = reinterpret_cast<uint32_t>(pointer);
key += ~(key << 15);
key ^= (key >> 10);
key += (key << 3);
key ^= (key >> 6);
key += ~(key << 11);
key ^= (key >> 16);
return key;
}
// Thomas Wang's 64 bit mix
// http://www.cris.com/~Ttwang/tech/inthash.htm
template <> inline unsigned pointerHash<8>(void *pointer)
{
uint64_t key = reinterpret_cast<uint64_t>(pointer);
key += ~(key << 32);
key ^= (key >> 22);
key += ~(key << 13);
key ^= (key >> 8);
key += (key << 3);
key ^= (key >> 15);
key += ~(key << 27);
key ^= (key >> 31);
return key;
}
inline unsigned pointerHash(void *p)
{
return pointerHash<sizeof(void *)>(p);
}
} // namespace KJS
#endif // _KJS_POINTER_HASH_H_
More information about the webkit-changes
mailing list