src/v8/test/cctest/test-hashing.cc

   1 // Copyright 2011 the V8 project authors. All rights reserved.
   2 // Redistribution and use in source and binary forms, with or without
   3 // modification, are permitted provided that the following conditions are
   4 // met:
   5 //
   6 //     * Redistributions of source code must retain the above copyright
   7 //       notice, this list of conditions and the following disclaimer.
   8 //     * Redistributions in binary form must reproduce the above
   9 //       copyright notice, this list of conditions and the following
  10 //       disclaimer in the documentation and/or other materials provided
  11 //       with the distribution.
  12 //     * Neither the name of Google Inc. nor the names of its
  13 //       contributors may be used to endorse or promote products derived
  14 //       from this software without specific prior written permission.
  15 //
  16 // THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
  17 // "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
  18 // LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
  19 // A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
  20 // OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
  21 // SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
  22 // LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
  23 // DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
  24 // THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
  25 // (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
  26 // OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
  27
  28 #include <stdlib.h>
  29
  30 #include "v8.h"
  31
  32 #include "factory.h"
  33 #include "macro-assembler.h"
  34 #include "cctest.h"
  35 #include "code-stubs.h"
  36 #include "objects.h"
  37
  38 #ifdef USE_SIMULATOR
  39 #include "simulator.h"
  40 #endif
  41
  42 using namespace v8::internal;
  43
  44
  45 typedef uint32_t (*HASH_FUNCTION)();
  46
  47 #define __ masm->
  48
  49
  50 void generate(MacroAssembler* masm, i::Vector<const uint8_t> string) {
  51   // GenerateHashInit takes the first character as an argument so it can't
  52   // handle the zero length string.
  53   ASSERT(string.length() > 0);
  54 #if V8_TARGET_ARCH_IA32
  55   __ push(ebx);
  56   __ push(ecx);
  57   __ mov(eax, Immediate(0));
  58   __ mov(ebx, Immediate(string.at(0)));
  59   StringHelper::GenerateHashInit(masm, eax, ebx, ecx);
  60   for (int i = 1; i < string.length(); i++) {
  61     __ mov(ebx, Immediate(string.at(i)));
  62     StringHelper::GenerateHashAddCharacter(masm, eax, ebx, ecx);
  63   }
  64   StringHelper::GenerateHashGetHash(masm, eax, ecx);
  65   __ pop(ecx);
  66   __ pop(ebx);
  67   __ Ret();
  68 #elif V8_TARGET_ARCH_X64
  69   __ pushq(kRootRegister);
  70   __ InitializeRootRegister();
  71   __ pushq(rbx);
  72   __ pushq(rcx);
  73   __ movp(rax, Immediate(0));
  74   __ movp(rbx, Immediate(string.at(0)));
  75   StringHelper::GenerateHashInit(masm, rax, rbx, rcx);
  76   for (int i = 1; i < string.length(); i++) {
  77     __ movp(rbx, Immediate(string.at(i)));
  78     StringHelper::GenerateHashAddCharacter(masm, rax, rbx, rcx);
  79   }
  80   StringHelper::GenerateHashGetHash(masm, rax, rcx);
  81   __ popq(rcx);
  82   __ popq(rbx);
  83   __ popq(kRootRegister);
  84   __ Ret();
  85 #elif V8_TARGET_ARCH_ARM
  86   __ push(kRootRegister);
  87   __ InitializeRootRegister();
  88
  89   __ mov(r0, Operand(0));
  90   __ mov(ip, Operand(string.at(0)));
  91   StringHelper::GenerateHashInit(masm, r0, ip);
  92   for (int i = 1; i < string.length(); i++) {
  93     __ mov(ip, Operand(string.at(i)));
  94     StringHelper::GenerateHashAddCharacter(masm, r0, ip);
  95   }
  96   StringHelper::GenerateHashGetHash(masm, r0);
  97   __ pop(kRootRegister);
  98   __ mov(pc, Operand(lr));
  99 #elif V8_TARGET_ARCH_ARM64
 100   // The ARM64 assembler usually uses jssp (x28) as a stack pointer, but only
 101   // csp is initialized by the calling (C++) code.
 102   Register old_stack_pointer = __ StackPointer();
 103   __ SetStackPointer(csp);
 104   __ Push(root, xzr);
 105   __ InitializeRootRegister();
 106   __ Mov(x0, 0);
 107   __ Mov(x10, Operand(string.at(0)));
 108   StringHelper::GenerateHashInit(masm, x0, x10);
 109   for (int i = 1; i < string.length(); i++) {
 110     __ Mov(x10, Operand(string.at(i)));
 111     StringHelper::GenerateHashAddCharacter(masm, x0, x10);
 112   }
 113   StringHelper::GenerateHashGetHash(masm, x0, x10);
 114   __ Pop(xzr, root);
 115   __ Ret();
 116   __ SetStackPointer(old_stack_pointer);
 117 #elif V8_TARGET_ARCH_MIPS
 118   __ push(kRootRegister);
 119   __ InitializeRootRegister();
 120
 121   __ li(v0, Operand(0));
 122   __ li(t1, Operand(string.at(0)));
 123   StringHelper::GenerateHashInit(masm, v0, t1);
 124   for (int i = 1; i < string.length(); i++) {
 125     __ li(t1, Operand(string.at(i)));
 126     StringHelper::GenerateHashAddCharacter(masm, v0, t1);
 127   }
 128   StringHelper::GenerateHashGetHash(masm, v0);
 129   __ pop(kRootRegister);
 130   __ jr(ra);
 131   __ nop();
 132 #else
 133 #error Unsupported architecture.
 134 #endif
 135 }
 136
 137
 138 void generate(MacroAssembler* masm, uint32_t key) {
 139 #if V8_TARGET_ARCH_IA32
 140   __ push(ebx);
 141   __ mov(eax, Immediate(key));
 142   __ GetNumberHash(eax, ebx);
 143   __ pop(ebx);
 144   __ Ret();
 145 #elif V8_TARGET_ARCH_X64
 146   __ pushq(kRootRegister);
 147   __ InitializeRootRegister();
 148   __ pushq(rbx);
 149   __ movp(rax, Immediate(key));
 150   __ GetNumberHash(rax, rbx);
 151   __ popq(rbx);
 152   __ popq(kRootRegister);
 153   __ Ret();
 154 #elif V8_TARGET_ARCH_ARM
 155   __ push(kRootRegister);
 156   __ InitializeRootRegister();
 157   __ mov(r0, Operand(key));
 158   __ GetNumberHash(r0, ip);
 159   __ pop(kRootRegister);
 160   __ mov(pc, Operand(lr));
 161 #elif V8_TARGET_ARCH_ARM64
 162   // The ARM64 assembler usually uses jssp (x28) as a stack pointer, but only
 163   // csp is initialized by the calling (C++) code.
 164   Register old_stack_pointer = __ StackPointer();
 165   __ SetStackPointer(csp);
 166   __ Push(root, xzr);
 167   __ InitializeRootRegister();
 168   __ Mov(x0, key);
 169   __ GetNumberHash(x0, x10);
 170   __ Pop(xzr, root);
 171   __ Ret();
 172   __ SetStackPointer(old_stack_pointer);
 173 #elif V8_TARGET_ARCH_MIPS
 174   __ push(kRootRegister);
 175   __ InitializeRootRegister();
 176   __ li(v0, Operand(key));
 177   __ GetNumberHash(v0, t1);
 178   __ pop(kRootRegister);
 179   __ jr(ra);
 180   __ nop();
 181 #else
 182 #error Unsupported architecture.
 183 #endif
 184 }
 185
 186
 187 void check(i::Vector<const uint8_t> string) {
 188   Isolate* isolate = CcTest::i_isolate();
 189   Factory* factory = isolate->factory();
 190   HandleScope scope(isolate);
 191
 192   v8::internal::byte buffer[2048];
 193   MacroAssembler masm(isolate, buffer, sizeof buffer);
 194
 195   generate(&masm, string);
 196
 197   CodeDesc desc;
 198   masm.GetCode(&desc);
 199   Handle<Object> undefined(isolate->heap()->undefined_value(), isolate);
 200   Handle<Code> code = factory->NewCode(desc,
 201                                        Code::ComputeFlags(Code::STUB),
 202                                        undefined);
 203   CHECK(code->IsCode());
 204
 205   HASH_FUNCTION hash = FUNCTION_CAST<HASH_FUNCTION>(code->entry());
 206   Handle<String> v8_string =
 207       factory->NewStringFromOneByte(string).ToHandleChecked();
 208   v8_string->set_hash_field(String::kEmptyHashField);
 209 #ifdef USE_SIMULATOR
 210   uint32_t codegen_hash = static_cast<uint32_t>(
 211         reinterpret_cast<uintptr_t>(CALL_GENERATED_CODE(hash, 0, 0, 0, 0, 0)));
 212 #else
 213   uint32_t codegen_hash = hash();
 214 #endif
 215   uint32_t runtime_hash = v8_string->Hash();
 216   CHECK(runtime_hash == codegen_hash);
 217 }
 218
 219
 220 void check(i::Vector<const char> s) {
 221   check(i::Vector<const uint8_t>::cast(s));
 222 }
 223
 224
 225 void check(uint32_t key) {
 226   Isolate* isolate = CcTest::i_isolate();
 227   Factory* factory = isolate->factory();
 228   HandleScope scope(isolate);
 229
 230   v8::internal::byte buffer[2048];
 231   MacroAssembler masm(CcTest::i_isolate(), buffer, sizeof buffer);
 232
 233   generate(&masm, key);
 234
 235   CodeDesc desc;
 236   masm.GetCode(&desc);
 237   Handle<Object> undefined(isolate->heap()->undefined_value(), isolate);
 238   Handle<Code> code = factory->NewCode(desc,
 239                                        Code::ComputeFlags(Code::STUB),
 240                                        undefined);
 241   CHECK(code->IsCode());
 242
 243   HASH_FUNCTION hash = FUNCTION_CAST<HASH_FUNCTION>(code->entry());
 244 #ifdef USE_SIMULATOR
 245   uint32_t codegen_hash = static_cast<uint32_t>(
 246         reinterpret_cast<uintptr_t>(CALL_GENERATED_CODE(hash, 0, 0, 0, 0, 0)));
 247 #else
 248   uint32_t codegen_hash = hash();
 249 #endif
 250
 251   uint32_t runtime_hash = ComputeIntegerHash(key, isolate->heap()->HashSeed());
 252   CHECK(runtime_hash == codegen_hash);
 253 }
 254
 255
 256 void check_twochars(uint8_t a, uint8_t b) {
 257   uint8_t ab[2] = {a, b};
 258   check(i::Vector<const uint8_t>(ab, 2));
 259 }
 260
 261
 262 static uint32_t PseudoRandom(uint32_t i, uint32_t j) {
 263   return ~(~((i * 781) ^ (j * 329)));
 264 }
 265
 266
 267 TEST(StringHash) {
 268   v8::Isolate* isolate = CcTest::isolate();
 269   v8::HandleScope handle_scope(isolate);
 270   v8::Context::Scope context_scope(v8::Context::New(isolate));
 271
 272   for (uint8_t a = 0; a < String::kMaxOneByteCharCode; a++) {
 273     // Numbers are hashed differently.
 274     if (a >= '0' && a <= '9') continue;
 275     for (uint8_t b = 0; b < String::kMaxOneByteCharCode; b++) {
 276       if (b >= '0' && b <= '9') continue;
 277       check_twochars(a, b);
 278     }
 279   }
 280   check(i::Vector<const char>("*",       1));
 281   check(i::Vector<const char>(".zZ",     3));
 282   check(i::Vector<const char>("muc",     3));
 283   check(i::Vector<const char>("(>'_')>", 7));
 284   check(i::Vector<const char>("-=[ vee eight ftw ]=-", 21));
 285 }
 286
 287
 288 TEST(NumberHash) {
 289   v8::Isolate* isolate = CcTest::isolate();
 290   v8::HandleScope handle_scope(isolate);
 291   v8::Context::Scope context_scope(v8::Context::New(isolate));
 292
 293   // Some specific numbers
 294   for (uint32_t key = 0; key < 42; key += 7) {
 295     check(key);
 296   }
 297
 298   // Some pseudo-random numbers
 299   static const uint32_t kLimit = 1000;
 300   for (uint32_t i = 0; i < 5; i++) {
 301     for (uint32_t j = 0; j < 5; j++) {
 302       check(PseudoRandom(i, j) % kLimit);
 303     }
 304   }
 305 }
 306
 307 #undef __