Revision: 10366
Author: [email protected]
Date: Tue Jan 10 04:58:41 2012
Log: Add seed to hash of numeric keyed properties. This is a commit
of http://codereview.chromium.org/9148006/ for Fedor Indutny.
http://code.google.com/p/v8/source/detail?r=10366
Modified:
/branches/bleeding_edge/src/arm/macro-assembler-arm.cc
/branches/bleeding_edge/src/arm/macro-assembler-arm.h
/branches/bleeding_edge/src/debug.h
/branches/bleeding_edge/src/frames.cc
/branches/bleeding_edge/src/ia32/macro-assembler-ia32.cc
/branches/bleeding_edge/src/ia32/macro-assembler-ia32.h
/branches/bleeding_edge/src/mips/macro-assembler-mips.cc
/branches/bleeding_edge/src/mips/macro-assembler-mips.h
/branches/bleeding_edge/src/objects-inl.h
/branches/bleeding_edge/src/objects.cc
/branches/bleeding_edge/src/objects.h
/branches/bleeding_edge/src/profile-generator.cc
/branches/bleeding_edge/src/profile-generator.h
/branches/bleeding_edge/src/utils.h
/branches/bleeding_edge/src/x64/macro-assembler-x64.cc
/branches/bleeding_edge/src/x64/macro-assembler-x64.h
/branches/bleeding_edge/test/cctest/test-hashing.cc
=======================================
--- /branches/bleeding_edge/src/arm/macro-assembler-arm.cc Mon Jan 9
08:37:47 2012
+++ /branches/bleeding_edge/src/arm/macro-assembler-arm.cc Tue Jan 10
04:58:41 2012
@@ -1412,6 +1412,35 @@
bind(&same_contexts);
}
+
+
+void MacroAssembler::GetNumberHash(Register t0, Register scratch) {
+ // First of all we assign the hash seed to scratch.
+ LoadRoot(scratch, Heap::kStringHashSeedRootIndex);
+ SmiUntag(scratch);
+
+ // Xor original key with a seed.
+ eor(t0, t0, Operand(scratch));
+
+ // Compute the hash code from the untagged key. This must be kept in
sync
+ // with ComputeIntegerHash in utils.h.
+ //
+ // hash = ~hash + (hash << 15);
+ mvn(scratch, Operand(t0));
+ add(t0, scratch, Operand(t0, LSL, 15));
+ // hash = hash ^ (hash >> 12);
+ eor(t0, t0, Operand(t0, LSR, 12));
+ // hash = hash + (hash << 2);
+ add(t0, t0, Operand(t0, LSL, 2));
+ // hash = hash ^ (hash >> 4);
+ eor(t0, t0, Operand(t0, LSR, 4));
+ // hash = hash * 2057;
+ mov(scratch, Operand(t0, LSL, 11));
+ add(t0, t0, Operand(t0, LSL, 3));
+ add(t0, t0, scratch);
+ // hash = hash ^ (hash >> 16);
+ eor(t0, t0, Operand(t0, LSR, 16));
+}
void MacroAssembler::LoadFromNumberDictionary(Label* miss,
@@ -1443,24 +1472,7 @@
// t2 - used for the index into the dictionary.
Label done;
- // Compute the hash code from the untagged key. This must be kept in
sync
- // with ComputeIntegerHash in utils.h.
- //
- // hash = ~hash + (hash << 15);
- mvn(t1, Operand(t0));
- add(t0, t1, Operand(t0, LSL, 15));
- // hash = hash ^ (hash >> 12);
- eor(t0, t0, Operand(t0, LSR, 12));
- // hash = hash + (hash << 2);
- add(t0, t0, Operand(t0, LSL, 2));
- // hash = hash ^ (hash >> 4);
- eor(t0, t0, Operand(t0, LSR, 4));
- // hash = hash * 2057;
- mov(t1, Operand(t0, LSL, 11));
- add(t0, t0, Operand(t0, LSL, 3));
- add(t0, t0, t1);
- // hash = hash ^ (hash >> 16);
- eor(t0, t0, Operand(t0, LSR, 16));
+ GetNumberHash(t0, t1);
// Compute the capacity mask.
ldr(t1, FieldMemOperand(elements, NumberDictionary::kCapacityOffset));
=======================================
--- /branches/bleeding_edge/src/arm/macro-assembler-arm.h Mon Jan 9
08:37:47 2012
+++ /branches/bleeding_edge/src/arm/macro-assembler-arm.h Tue Jan 10
04:58:41 2012
@@ -591,6 +591,9 @@
Label* miss);
+ void GetNumberHash(Register t0, Register scratch);
+
+
void LoadFromNumberDictionary(Label* miss,
Register elements,
Register key,
=======================================
--- /branches/bleeding_edge/src/debug.h Tue Nov 8 06:39:37 2011
+++ /branches/bleeding_edge/src/debug.h Tue Jan 10 04:58:41 2012
@@ -178,7 +178,9 @@
private:
// Calculate the hash value from the key (script id).
- static uint32_t Hash(int key) { return ComputeIntegerHash(key); }
+ static uint32_t Hash(int key) {
+ return ComputeIntegerHash(key, v8::internal::kZeroHashSeed);
+ }
// Scripts match if their keys (script id) match.
static bool ScriptMatch(void* key1, void* key2) { return key1 == key2; }
=======================================
--- /branches/bleeding_edge/src/frames.cc Mon Dec 5 13:54:45 2011
+++ /branches/bleeding_edge/src/frames.cc Tue Jan 10 04:58:41 2012
@@ -1303,7 +1303,8 @@
isolate_->counters()->pc_to_code()->Increment();
ASSERT(IsPowerOf2(kInnerPointerToCodeCacheSize));
uint32_t hash = ComputeIntegerHash(
- static_cast<uint32_t>(reinterpret_cast<uintptr_t>(inner_pointer)));
+ static_cast<uint32_t>(reinterpret_cast<uintptr_t>(inner_pointer)),
+ v8::internal::kZeroHashSeed);
uint32_t index = hash & (kInnerPointerToCodeCacheSize - 1);
InnerPointerToCodeCacheEntry* entry = cache(index);
if (entry->inner_pointer == inner_pointer) {
=======================================
--- /branches/bleeding_edge/src/ia32/macro-assembler-ia32.cc Mon Jan 9
08:37:47 2012
+++ /branches/bleeding_edge/src/ia32/macro-assembler-ia32.cc Tue Jan 10
04:58:41 2012
@@ -990,6 +990,49 @@
bind(&same_contexts);
}
+
+
+// Compute the hash code from the untagged key. This must be kept in sync
+// with ComputeIntegerHash in utils.h.
+//
+// Note: r0 will contain hash code
+void MacroAssembler::GetNumberHash(Register r0, Register scratch) {
+ // Xor original key with a seed.
+ if (Serializer::enabled()) {
+ ExternalReference roots_array_start =
+ ExternalReference::roots_array_start(isolate());
+ mov(scratch, Immediate(Heap::kStringHashSeedRootIndex));
+ xor_(r0, Operand::StaticArray(scratch,
+ times_pointer_size,
+ roots_array_start));
+ } else {
+ int32_t seed = isolate()->heap()->StringHashSeed();
+ xor_(r0, Immediate(seed));
+ }
+
+ // hash = ~hash + (hash << 15);
+ mov(scratch, r0);
+ not_(r0);
+ shl(scratch, 15);
+ add(r0, scratch);
+ // hash = hash ^ (hash >> 12);
+ mov(scratch, r0);
+ shr(scratch, 12);
+ xor_(r0, scratch);
+ // hash = hash + (hash << 2);
+ lea(r0, Operand(r0, r0, times_4, 0));
+ // hash = hash ^ (hash >> 4);
+ mov(scratch, r0);
+ shr(scratch, 4);
+ xor_(r0, scratch);
+ // hash = hash * 2057;
+ imul(r0, r0, 2057);
+ // hash = hash ^ (hash >> 16);
+ mov(scratch, r0);
+ shr(scratch, 16);
+ xor_(r0, scratch);
+}
+
void MacroAssembler::LoadFromNumberDictionary(Label* miss,
@@ -1017,30 +1060,7 @@
Label done;
- // Compute the hash code from the untagged key. This must be kept in
sync
- // with ComputeIntegerHash in utils.h.
- //
- // hash = ~hash + (hash << 15);
- mov(r1, r0);
- not_(r0);
- shl(r1, 15);
- add(r0, r1);
- // hash = hash ^ (hash >> 12);
- mov(r1, r0);
- shr(r1, 12);
- xor_(r0, r1);
- // hash = hash + (hash << 2);
- lea(r0, Operand(r0, r0, times_4, 0));
- // hash = hash ^ (hash >> 4);
- mov(r1, r0);
- shr(r1, 4);
- xor_(r0, r1);
- // hash = hash * 2057;
- imul(r0, r0, 2057);
- // hash = hash ^ (hash >> 16);
- mov(r1, r0);
- shr(r1, 16);
- xor_(r0, r1);
+ GetNumberHash(r0, r1);
// Compute capacity mask.
mov(r1, FieldOperand(elements, NumberDictionary::kCapacityOffset));
=======================================
--- /branches/bleeding_edge/src/ia32/macro-assembler-ia32.h Mon Jan 9
08:37:47 2012
+++ /branches/bleeding_edge/src/ia32/macro-assembler-ia32.h Tue Jan 10
04:58:41 2012
@@ -498,6 +498,9 @@
Label* miss);
+ void GetNumberHash(Register r0, Register scratch);
+
+
void LoadFromNumberDictionary(Label* miss,
Register elements,
Register key,
=======================================
--- /branches/bleeding_edge/src/mips/macro-assembler-mips.cc Thu Dec 8
00:53:09 2011
+++ /branches/bleeding_edge/src/mips/macro-assembler-mips.cc Tue Jan 10
04:58:41 2012
@@ -407,6 +407,44 @@
bind(&same_contexts);
}
+
+
+void MacroAssembler::GetNumberHash(Register reg0, Register scratch) {
+ // First of all we assign the hash seed to scratch.
+ LoadRoot(scratch, Heap::kStringHashSeedRootIndex);
+ SmiUntag(scratch);
+
+ // Xor original key with a seed.
+ xor_(reg0, reg0, scratch);
+
+ // Compute the hash code from the untagged key. This must be kept in
sync
+ // with ComputeIntegerHash in utils.h.
+ //
+ // hash = ~hash + (hash << 15);
+ nor(scratch, reg0, zero_reg);
+ sll(at, reg0, 15);
+ addu(reg0, scratch, at);
+
+ // hash = hash ^ (hash >> 12);
+ srl(at, reg0, 12);
+ xor_(reg0, reg0, at);
+
+ // hash = hash + (hash << 2);
+ sll(at, reg0, 2);
+ addu(reg0, reg0, at);
+
+ // hash = hash ^ (hash >> 4);
+ srl(at, reg0, 4);
+ xor_(reg0, reg0, at);
+
+ // hash = hash * 2057;
+ li(scratch, Operand(2057));
+ mul(reg0, reg0, scratch);
+
+ // hash = hash ^ (hash >> 16);
+ srl(at, reg0, 16);
+ xor_(reg0, reg0, at);
+}
void MacroAssembler::LoadFromNumberDictionary(Label* miss,
@@ -440,33 +478,7 @@
// at - Temporary (avoid MacroAssembler instructions also using 'at').
Label done;
- // Compute the hash code from the untagged key. This must be kept in
sync
- // with ComputeIntegerHash in utils.h.
- //
- // hash = ~hash + (hash << 15);
- nor(reg1, reg0, zero_reg);
- sll(at, reg0, 15);
- addu(reg0, reg1, at);
-
- // hash = hash ^ (hash >> 12);
- srl(at, reg0, 12);
- xor_(reg0, reg0, at);
-
- // hash = hash + (hash << 2);
- sll(at, reg0, 2);
- addu(reg0, reg0, at);
-
- // hash = hash ^ (hash >> 4);
- srl(at, reg0, 4);
- xor_(reg0, reg0, at);
-
- // hash = hash * 2057;
- li(reg1, Operand(2057));
- mul(reg0, reg0, reg1);
-
- // hash = hash ^ (hash >> 16);
- srl(at, reg0, 16);
- xor_(reg0, reg0, at);
+ GetNumberHash(reg0, reg1);
// Compute the capacity mask.
lw(reg1, FieldMemOperand(elements, NumberDictionary::kCapacityOffset));
=======================================
--- /branches/bleeding_edge/src/mips/macro-assembler-mips.h Fri Jan 6
03:33:20 2012
+++ /branches/bleeding_edge/src/mips/macro-assembler-mips.h Tue Jan 10
04:58:41 2012
@@ -406,6 +406,9 @@
Label* miss);
+ void GetNumberHash(Register reg0, Register scratch);
+
+
void LoadFromNumberDictionary(Label* miss,
Register elements,
Register key,
=======================================
--- /branches/bleeding_edge/src/objects-inl.h Thu Jan 5 02:18:28 2012
+++ /branches/bleeding_edge/src/objects-inl.h Tue Jan 10 04:58:41 2012
@@ -2057,7 +2057,7 @@
template<typename Shape, typename Key>
int HashTable<Shape, Key>::FindEntry(Isolate* isolate, Key key) {
uint32_t capacity = Capacity();
- uint32_t entry = FirstProbe(Shape::Hash(key), capacity);
+ uint32_t entry = FirstProbe(HashTable<Shape, Key>::Hash(key), capacity);
uint32_t count = 1;
// EnsureCapacity will guarantee the hash table is never full.
while (true) {
@@ -4536,15 +4536,28 @@
uint32_t NumberDictionaryShape::Hash(uint32_t key) {
- return ComputeIntegerHash(key);
+ // This function is unreachable, since shape has UsesSeed=true flag.
+ UNREACHABLE();
+ return 0;
}
uint32_t NumberDictionaryShape::HashForObject(uint32_t key, Object* other)
{
- ASSERT(other->IsNumber());
- return ComputeIntegerHash(static_cast<uint32_t>(other->Number()));
+ // This function is unreachable, since shape has UsesSeed=true flag.
+ UNREACHABLE();
+ return 0;
}
+uint32_t NumberDictionaryShape::SeededHash(uint32_t key, uint32_t seed) {
+ return ComputeIntegerHash(key, seed);
+}
+
+uint32_t NumberDictionaryShape::SeededHashForObject(uint32_t key,
+ uint32_t seed,
+ Object* other) {
+ ASSERT(other->IsNumber());
+ return ComputeIntegerHash(static_cast<uint32_t>(other->Number()), seed);
+}
MaybeObject* NumberDictionaryShape::AsObject(uint32_t key) {
return Isolate::Current()->heap()->NumberFromUint32(key);
=======================================
--- /branches/bleeding_edge/src/objects.cc Tue Jan 10 04:01:04 2012
+++ /branches/bleeding_edge/src/objects.cc Tue Jan 10 04:58:41 2012
@@ -10927,7 +10927,7 @@
uint32_t from_index = EntryToIndex(i);
Object* k = get(from_index);
if (IsKey(k)) {
- uint32_t hash = Shape::HashForObject(key, k);
+ uint32_t hash = HashTable<Shape, Key>::HashForObject(key, k);
uint32_t insertion_index =
EntryToIndex(new_table->FindInsertionEntry(hash));
for (int j = 0; j < Shape::kEntrySize; j++) {
@@ -12013,8 +12013,9 @@
if (!maybe_k->ToObject(&k)) return maybe_k;
}
PropertyDetails details = PropertyDetails(NONE, NORMAL);
- return Dictionary<Shape, Key>::cast(obj)->
- AddEntry(key, value, details, Shape::Hash(key));
+
+ return Dictionary<Shape, Key>::cast(obj)->AddEntry(key, value, details,
+ Dictionary<Shape, Key>::Hash(key));
}
@@ -12029,8 +12030,9 @@
{ MaybeObject* maybe_obj = EnsureCapacity(1, key);
if (!maybe_obj->ToObject(&obj)) return maybe_obj;
}
- return Dictionary<Shape, Key>::cast(obj)->
- AddEntry(key, value, details, Shape::Hash(key));
+
+ return Dictionary<Shape, Key>::cast(obj)->AddEntry(key, value, details,
+ Dictionary<Shape, Key>::Hash(key));
}
=======================================
--- /branches/bleeding_edge/src/objects.h Tue Jan 10 04:01:04 2012
+++ /branches/bleeding_edge/src/objects.h Tue Jan 10 04:58:41 2012
@@ -2593,9 +2593,44 @@
// beginning of the backing storage that can be used for non-element
// information by subclasses.
+template<typename Key>
+class BaseShape {
+ public:
+ static const bool UsesSeed = false;
+ static uint32_t Hash(Key key) { return 0; }
+ static uint32_t SeededHash(Key key, uint32_t seed) {
+ // Won't be called if UsesSeed isn't overridden by child class.
+ return Hash(key);
+ }
+ static uint32_t HashForObject(Key key, Object* object) { return 0; }
+ static uint32_t SeededHashForObject(Key key, uint32_t seed, Object*
object) {
+ // Won't be called if UsesSeed isn't overridden by child class.
+ return HashForObject(key, object);
+ }
+};
+
template<typename Shape, typename Key>
class HashTable: public FixedArray {
public:
+ // Wrapper methods
+ inline uint32_t Hash(Key key) {
+ if (Shape::UsesSeed) {
+ return Shape::SeededHash(key,
+ GetHeap()->StringHashSeed());
+ } else {
+ return Shape::Hash(key);
+ }
+ }
+
+ inline uint32_t HashForObject(Key key, Object* object) {
+ if (Shape::UsesSeed) {
+ return Shape::SeededHashForObject(key,
+ GetHeap()->StringHashSeed(), object);
+ } else {
+ return Shape::HashForObject(key, object);
+ }
+ }
+
// Returns the number of elements in the hash table.
int NumberOfElements() {
return Smi::cast(get(kNumberOfElementsIndex))->value();
@@ -2737,7 +2772,6 @@
};
-
// HashTableKey is an abstract superclass for virtual key behavior.
class HashTableKey {
public:
@@ -2754,7 +2788,8 @@
virtual ~HashTableKey() {}
};
-class SymbolTableShape {
+
+class SymbolTableShape : public BaseShape<HashTableKey*> {
public:
static inline bool IsMatch(HashTableKey* key, Object* value) {
return key->IsMatch(value);
@@ -2813,7 +2848,7 @@
};
-class MapCacheShape {
+class MapCacheShape : public BaseShape<HashTableKey*> {
public:
static inline bool IsMatch(HashTableKey* key, Object* value) {
return key->IsMatch(value);
@@ -2969,7 +3004,7 @@
};
-class StringDictionaryShape {
+class StringDictionaryShape : public BaseShape<String*> {
public:
static inline bool IsMatch(String* key, Object* other);
static inline uint32_t Hash(String* key);
@@ -3002,11 +3037,17 @@
};
-class NumberDictionaryShape {
+class NumberDictionaryShape : public BaseShape<uint32_t> {
public:
+ static const bool UsesSeed = true;
+
static inline bool IsMatch(uint32_t key, Object* other);
static inline uint32_t Hash(uint32_t key);
+ static inline uint32_t SeededHash(uint32_t key, uint32_t seed);
static inline uint32_t HashForObject(uint32_t key, Object* object);
+ static inline uint32_t SeededHashForObject(uint32_t key,
+ uint32_t seed,
+ Object* object);
MUST_USE_RESULT static inline MaybeObject* AsObject(uint32_t key);
static const int kPrefixSize = 2;
static const int kEntrySize = 3;
@@ -3062,7 +3103,7 @@
template <int entrysize>
-class ObjectHashTableShape {
+class ObjectHashTableShape : public BaseShape<Object*> {
public:
static inline bool IsMatch(Object* key, Object* other);
static inline uint32_t Hash(Object* key);
@@ -5974,7 +6015,7 @@
};
-class CompilationCacheShape {
+class CompilationCacheShape : public BaseShape<HashTableKey*> {
public:
static inline bool IsMatch(HashTableKey* key, Object* value) {
return key->IsMatch(value);
@@ -6078,7 +6119,7 @@
};
-class CodeCacheHashTableShape {
+class CodeCacheHashTableShape : public BaseShape<HashTableKey*> {
public:
static inline bool IsMatch(HashTableKey* key, Object* value) {
return key->IsMatch(value);
=======================================
--- /branches/bleeding_edge/src/profile-generator.cc Wed Jan 4 07:12:15
2012
+++ /branches/bleeding_edge/src/profile-generator.cc Tue Jan 10 04:58:41
2012
@@ -181,18 +181,21 @@
uint32_t CodeEntry::GetCallUid() const {
- uint32_t hash = ComputeIntegerHash(tag_);
+ uint32_t hash = ComputeIntegerHash(tag_, v8::internal::kZeroHashSeed);
if (shared_id_ != 0) {
- hash ^= ComputeIntegerHash(
- static_cast<uint32_t>(shared_id_));
+ hash ^= ComputeIntegerHash(static_cast<uint32_t>(shared_id_),
+ v8::internal::kZeroHashSeed);
} else {
hash ^= ComputeIntegerHash(
- static_cast<uint32_t>(reinterpret_cast<uintptr_t>(name_prefix_)));
+ static_cast<uint32_t>(reinterpret_cast<uintptr_t>(name_prefix_)),
+ v8::internal::kZeroHashSeed);
hash ^= ComputeIntegerHash(
- static_cast<uint32_t>(reinterpret_cast<uintptr_t>(name_)));
+ static_cast<uint32_t>(reinterpret_cast<uintptr_t>(name_)),
+ v8::internal::kZeroHashSeed);
hash ^= ComputeIntegerHash(
-
static_cast<uint32_t>(reinterpret_cast<uintptr_t>(resource_name_)));
- hash ^= ComputeIntegerHash(line_number_);
+ static_cast<uint32_t>(reinterpret_cast<uintptr_t>(resource_name_)),
+ v8::internal::kZeroHashSeed);
+ hash ^= ComputeIntegerHash(line_number_, v8::internal::kZeroHashSeed);
}
return hash;
}
@@ -1509,7 +1512,8 @@
HEAP->StringHashSeed());
intptr_t element_count = info->GetElementCount();
if (element_count != -1)
- id ^= ComputeIntegerHash(static_cast<uint32_t>(element_count));
+ id ^= ComputeIntegerHash(static_cast<uint32_t>(element_count),
+ v8::internal::kZeroHashSeed);
return id << 1;
}
=======================================
--- /branches/bleeding_edge/src/profile-generator.h Tue Dec 6 09:41:47 2011
+++ /branches/bleeding_edge/src/profile-generator.h Tue Jan 10 04:58:41 2012
@@ -750,7 +750,8 @@
static uint32_t AddressHash(Address addr) {
return ComputeIntegerHash(
- static_cast<uint32_t>(reinterpret_cast<uintptr_t>(addr)));
+ static_cast<uint32_t>(reinterpret_cast<uintptr_t>(addr)),
+ v8::internal::kZeroHashSeed);
}
bool initial_fill_mode_;
@@ -851,7 +852,8 @@
static uint32_t Hash(HeapThing thing) {
return ComputeIntegerHash(
- static_cast<uint32_t>(reinterpret_cast<uintptr_t>(thing)));
+ static_cast<uint32_t>(reinterpret_cast<uintptr_t>(thing)),
+ v8::internal::kZeroHashSeed);
}
static bool HeapThingsMatch(HeapThing key1, HeapThing key2) {
return key1 == key2;
@@ -1047,7 +1049,8 @@
void VisitSubtreeWrapper(Object** p, uint16_t class_id);
static uint32_t InfoHash(v8::RetainedObjectInfo* info) {
- return ComputeIntegerHash(static_cast<uint32_t>(info->GetHash()));
+ return ComputeIntegerHash(static_cast<uint32_t>(info->GetHash()),
+ v8::internal::kZeroHashSeed);
}
static bool RetainedInfosMatch(void* key1, void* key2) {
return key1 == key2 ||
@@ -1125,7 +1128,8 @@
INLINE(static uint32_t ObjectHash(const void* key)) {
return ComputeIntegerHash(
- static_cast<uint32_t>(reinterpret_cast<uintptr_t>(key)));
+ static_cast<uint32_t>(reinterpret_cast<uintptr_t>(key)),
+ v8::internal::kZeroHashSeed);
}
void EnumerateNodes();
=======================================
--- /branches/bleeding_edge/src/utils.h Tue Nov 29 02:56:11 2011
+++ /branches/bleeding_edge/src/utils.h Tue Jan 10 04:58:41 2012
@@ -252,10 +252,13 @@
//
----------------------------------------------------------------------------
// Hash function.
+static const uint32_t kZeroHashSeed = 0;
+
// Thomas Wang, Integer Hash Functions.
// http://www.concentric.net/~Ttwang/tech/inthash.htm
-inline uint32_t ComputeIntegerHash(uint32_t key) {
+inline uint32_t ComputeIntegerHash(uint32_t key, uint32_t seed) {
uint32_t hash = key;
+ hash = hash ^ seed;
hash = ~hash + (hash << 15); // hash = (hash << 15) - hash - 1;
hash = hash ^ (hash >> 12);
hash = hash + (hash << 2);
@@ -280,7 +283,8 @@
inline uint32_t ComputePointerHash(void* ptr) {
return ComputeIntegerHash(
- static_cast<uint32_t>(reinterpret_cast<intptr_t>(ptr)));
+ static_cast<uint32_t>(reinterpret_cast<intptr_t>(ptr)),
+ v8::internal::kZeroHashSeed);
}
=======================================
--- /branches/bleeding_edge/src/x64/macro-assembler-x64.cc Mon Jan 9
08:37:47 2012
+++ /branches/bleeding_edge/src/x64/macro-assembler-x64.cc Tue Jan 10
04:58:41 2012
@@ -3419,6 +3419,42 @@
}
+void MacroAssembler::GetNumberHash(Register r0, Register scratch) {
+ // First of all we assign the hash seed to scratch.
+ LoadRoot(scratch, Heap::kStringHashSeedRootIndex);
+ SmiToInteger32(scratch, scratch);
+
+ // Xor original key with a seed.
+ xorl(r0, scratch);
+
+ // Compute the hash code from the untagged key. This must be kept in
sync
+ // with ComputeIntegerHash in utils.h.
+ //
+ // hash = ~hash + (hash << 15);
+ movl(scratch, r0);
+ notl(r0);
+ shll(scratch, Immediate(15));
+ addl(r0, scratch);
+ // hash = hash ^ (hash >> 12);
+ movl(scratch, r0);
+ shrl(scratch, Immediate(12));
+ xorl(r0, scratch);
+ // hash = hash + (hash << 2);
+ leal(r0, Operand(r0, r0, times_4, 0));
+ // hash = hash ^ (hash >> 4);
+ movl(scratch, r0);
+ shrl(scratch, Immediate(4));
+ xorl(r0, scratch);
+ // hash = hash * 2057;
+ imull(r0, r0, Immediate(2057));
+ // hash = hash ^ (hash >> 16);
+ movl(scratch, r0);
+ shrl(scratch, Immediate(16));
+ xorl(r0, scratch);
+}
+
+
+
void MacroAssembler::LoadFromNumberDictionary(Label* miss,
Register elements,
Register key,
@@ -3449,30 +3485,7 @@
Label done;
- // Compute the hash code from the untagged key. This must be kept in
sync
- // with ComputeIntegerHash in utils.h.
- //
- // hash = ~hash + (hash << 15);
- movl(r1, r0);
- notl(r0);
- shll(r1, Immediate(15));
- addl(r0, r1);
- // hash = hash ^ (hash >> 12);
- movl(r1, r0);
- shrl(r1, Immediate(12));
- xorl(r0, r1);
- // hash = hash + (hash << 2);
- leal(r0, Operand(r0, r0, times_4, 0));
- // hash = hash ^ (hash >> 4);
- movl(r1, r0);
- shrl(r1, Immediate(4));
- xorl(r0, r1);
- // hash = hash * 2057;
- imull(r0, r0, Immediate(2057));
- // hash = hash ^ (hash >> 16);
- movl(r1, r0);
- shrl(r1, Immediate(16));
- xorl(r0, r1);
+ GetNumberHash(r0, r1);
// Compute capacity mask.
SmiToInteger32(r1,
=======================================
--- /branches/bleeding_edge/src/x64/macro-assembler-x64.h Mon Jan 9
08:37:47 2012
+++ /branches/bleeding_edge/src/x64/macro-assembler-x64.h Tue Jan 10
04:58:41 2012
@@ -987,6 +987,9 @@
Label* miss);
+ void GetNumberHash(Register r0, Register scratch);
+
+
void LoadFromNumberDictionary(Label* miss,
Register elements,
Register key,
=======================================
--- /branches/bleeding_edge/test/cctest/test-hashing.cc Fri Jan 6 03:33:20
2012
+++ /branches/bleeding_edge/test/cctest/test-hashing.cc Tue Jan 10 04:58:41
2012
@@ -115,6 +115,41 @@
__ nop();
#endif
}
+
+
+void generate(MacroAssembler* masm, uint32_t key) {
+#ifdef V8_TARGET_ARCH_IA32
+ __ push(ebx);
+ __ mov(eax, Immediate(key));
+ __ GetNumberHash(eax, ebx);
+ __ pop(ebx);
+ __ Ret();
+#elif V8_TARGET_ARCH_X64
+ __ push(kRootRegister);
+ __ InitializeRootRegister();
+ __ push(rbx);
+ __ movq(rax, Immediate(key));
+ __ GetNumberHash(rax, rbx);
+ __ pop(rbx);
+ __ pop(kRootRegister);
+ __ Ret();
+#elif V8_TARGET_ARCH_ARM
+ __ push(kRootRegister);
+ __ InitializeRootRegister();
+ __ mov(r0, Operand(key));
+ __ GetNumberHash(r0, ip);
+ __ pop(kRootRegister);
+ __ mov(pc, Operand(lr));
+#elif V8_TARGET_ARCH_MIPS
+ __ push(kRootRegister);
+ __ InitializeRootRegister();
+ __ li(v0, Operand(key));
+ __ GetNumberHash(v0, t1);
+ __ pop(kRootRegister);
+ __ jr(ra);
+ __ nop();
+#endif
+}
void check(i::Vector<const char> string) {
@@ -144,12 +179,47 @@
uint32_t runtime_hash = v8_string->Hash();
CHECK(runtime_hash == codegen_hash);
}
+
+
+void check(uint32_t key) {
+ v8::HandleScope scope;
+ v8::internal::byte buffer[2048];
+ MacroAssembler masm(Isolate::Current(), buffer, sizeof buffer);
+
+ generate(&masm, key);
+
+ CodeDesc desc;
+ masm.GetCode(&desc);
+ Code* code = Code::cast(HEAP->CreateCode(
+ desc,
+ Code::ComputeFlags(Code::STUB),
+ Handle<Object>(HEAP->undefined_value()))->ToObjectChecked());
+ CHECK(code->IsCode());
+
+ HASH_FUNCTION hash = FUNCTION_CAST<HASH_FUNCTION>(code->entry());
+#ifdef USE_SIMULATOR
+ uint32_t codegen_hash =
+ reinterpret_cast<uint32_t>(CALL_GENERATED_CODE(hash, 0, 0, 0, 0, 0));
+#else
+ uint32_t codegen_hash = hash();
+#endif
+
+ uint32_t runtime_hash = ComputeIntegerHash(
+ key,
+ Isolate::Current()->heap()->StringHashSeed());
+ CHECK(runtime_hash == codegen_hash);
+}
void check_twochars(char a, char b) {
char ab[2] = {a, b};
check(i::Vector<const char>(ab, 2));
}
+
+
+static uint32_t PseudoRandom(uint32_t i, uint32_t j) {
+ return ~(~((i * 781) ^ (j * 329)));
+}
TEST(StringHash) {
@@ -168,5 +238,23 @@
check(i::Vector<const char>("(>'_')>", 7));
check(i::Vector<const char>("-=[ vee eight ftw ]=-", 21));
}
+
+
+TEST(NumberHash) {
+ if (env.IsEmpty()) env = v8::Context::New();
+
+ // Some specific numbers
+ for (uint32_t key = 0; key < 42; key += 7) {
+ check(key);
+ }
+
+ // Some pseudo-random numbers
+ static const uint32_t kLimit = 1000;
+ for (uint32_t i = 0; i < 5; i++) {
+ for (uint32_t j = 0; j < 5; j++) {
+ check(PseudoRandom(i, j) % kLimit);
+ }
+ }
+}
#undef __
--
v8-dev mailing list
[email protected]
http://groups.google.com/group/v8-dev
