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 42using namespace v8::internal; 43 44 45typedef uint32_t (*HASH_FUNCTION)(); 46 47#define __ masm-> 48 49 50void 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 __ push(kRootRegister); 70 __ InitializeRootRegister(); 71 __ push(rbx); 72 __ push(rcx); 73 __ movq(rax, Immediate(0)); 74 __ movq(rbx, Immediate(string.at(0))); 75 StringHelper::GenerateHashInit(masm, rax, rbx, rcx); 76 for (int i = 1; i < string.length(); i++) { 77 __ movq(rbx, Immediate(string.at(i))); 78 StringHelper::GenerateHashAddCharacter(masm, rax, rbx, rcx); 79 } 80 StringHelper::GenerateHashGetHash(masm, rax, rcx); 81 __ pop(rcx); 82 __ pop(rbx); 83 __ pop(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_MIPS 100 __ push(kRootRegister); 101 __ InitializeRootRegister(); 102 103 __ li(v0, Operand(0)); 104 __ li(t1, Operand(string.at(0))); 105 StringHelper::GenerateHashInit(masm, v0, t1); 106 for (int i = 1; i < string.length(); i++) { 107 __ li(t1, Operand(string.at(i))); 108 StringHelper::GenerateHashAddCharacter(masm, v0, t1); 109 } 110 StringHelper::GenerateHashGetHash(masm, v0); 111 __ pop(kRootRegister); 112 __ jr(ra); 113 __ nop(); 114#endif 115} 116 117 118void generate(MacroAssembler* masm, uint32_t key) { 119#if V8_TARGET_ARCH_IA32 120 __ push(ebx); 121 __ mov(eax, Immediate(key)); 122 __ GetNumberHash(eax, ebx); 123 __ pop(ebx); 124 __ Ret(); 125#elif V8_TARGET_ARCH_X64 126 __ push(kRootRegister); 127 __ InitializeRootRegister(); 128 __ push(rbx); 129 __ movq(rax, Immediate(key)); 130 __ GetNumberHash(rax, rbx); 131 __ pop(rbx); 132 __ pop(kRootRegister); 133 __ Ret(); 134#elif V8_TARGET_ARCH_ARM 135 __ push(kRootRegister); 136 __ InitializeRootRegister(); 137 __ mov(r0, Operand(key)); 138 __ GetNumberHash(r0, ip); 139 __ pop(kRootRegister); 140 __ mov(pc, Operand(lr)); 141#elif V8_TARGET_ARCH_MIPS 142 __ push(kRootRegister); 143 __ InitializeRootRegister(); 144 __ li(v0, Operand(key)); 145 __ GetNumberHash(v0, t1); 146 __ pop(kRootRegister); 147 __ jr(ra); 148 __ nop(); 149#endif 150} 151 152 153void check(i::Vector<const uint8_t> string) { 154 Isolate* isolate = CcTest::i_isolate(); 155 Factory* factory = isolate->factory(); 156 HandleScope scope(isolate); 157 158 v8::internal::byte buffer[2048]; 159 MacroAssembler masm(isolate, buffer, sizeof buffer); 160 161 generate(&masm, string); 162 163 CodeDesc desc; 164 masm.GetCode(&desc); 165 Handle<Object> undefined(isolate->heap()->undefined_value(), isolate); 166 Handle<Code> code = factory->NewCode(desc, 167 Code::ComputeFlags(Code::STUB), 168 undefined); 169 CHECK(code->IsCode()); 170 171 HASH_FUNCTION hash = FUNCTION_CAST<HASH_FUNCTION>(code->entry()); 172 Handle<String> v8_string = factory->NewStringFromOneByte(string); 173 v8_string->set_hash_field(String::kEmptyHashField); 174#ifdef USE_SIMULATOR 175 uint32_t codegen_hash = 176 reinterpret_cast<uint32_t>(CALL_GENERATED_CODE(hash, 0, 0, 0, 0, 0)); 177#else 178 uint32_t codegen_hash = hash(); 179#endif 180 uint32_t runtime_hash = v8_string->Hash(); 181 CHECK(runtime_hash == codegen_hash); 182} 183 184 185void check(i::Vector<const char> s) { 186 check(i::Vector<const uint8_t>::cast(s)); 187} 188 189 190void check(uint32_t key) { 191 Isolate* isolate = CcTest::i_isolate(); 192 Factory* factory = isolate->factory(); 193 HandleScope scope(isolate); 194 195 v8::internal::byte buffer[2048]; 196 MacroAssembler masm(CcTest::i_isolate(), buffer, sizeof buffer); 197 198 generate(&masm, key); 199 200 CodeDesc desc; 201 masm.GetCode(&desc); 202 Handle<Object> undefined(isolate->heap()->undefined_value(), isolate); 203 Handle<Code> code = factory->NewCode(desc, 204 Code::ComputeFlags(Code::STUB), 205 undefined); 206 CHECK(code->IsCode()); 207 208 HASH_FUNCTION hash = FUNCTION_CAST<HASH_FUNCTION>(code->entry()); 209#ifdef USE_SIMULATOR 210 uint32_t codegen_hash = 211 reinterpret_cast<uint32_t>(CALL_GENERATED_CODE(hash, 0, 0, 0, 0, 0)); 212#else 213 uint32_t codegen_hash = hash(); 214#endif 215 216 uint32_t runtime_hash = ComputeIntegerHash(key, isolate->heap()->HashSeed()); 217 CHECK(runtime_hash == codegen_hash); 218} 219 220 221void check_twochars(uint8_t a, uint8_t b) { 222 uint8_t ab[2] = {a, b}; 223 check(i::Vector<const uint8_t>(ab, 2)); 224} 225 226 227static uint32_t PseudoRandom(uint32_t i, uint32_t j) { 228 return ~(~((i * 781) ^ (j * 329))); 229} 230 231 232TEST(StringHash) { 233 v8::Isolate* isolate = CcTest::isolate(); 234 v8::HandleScope handle_scope(isolate); 235 v8::Context::Scope context_scope(v8::Context::New(isolate)); 236 237 for (uint8_t a = 0; a < String::kMaxOneByteCharCode; a++) { 238 // Numbers are hashed differently. 239 if (a >= '0' && a <= '9') continue; 240 for (uint8_t b = 0; b < String::kMaxOneByteCharCode; b++) { 241 if (b >= '0' && b <= '9') continue; 242 check_twochars(a, b); 243 } 244 } 245 check(i::Vector<const char>("*", 1)); 246 check(i::Vector<const char>(".zZ", 3)); 247 check(i::Vector<const char>("muc", 3)); 248 check(i::Vector<const char>("(>'_')>", 7)); 249 check(i::Vector<const char>("-=[ vee eight ftw ]=-", 21)); 250} 251 252 253TEST(NumberHash) { 254 v8::Isolate* isolate = CcTest::isolate(); 255 v8::HandleScope handle_scope(isolate); 256 v8::Context::Scope context_scope(v8::Context::New(isolate)); 257 258 // Some specific numbers 259 for (uint32_t key = 0; key < 42; key += 7) { 260 check(key); 261 } 262 263 // Some pseudo-random numbers 264 static const uint32_t kLimit = 1000; 265 for (uint32_t i = 0; i < 5; i++) { 266 for (uint32_t j = 0; j < 5; j++) { 267 check(PseudoRandom(i, j) % kLimit); 268 } 269 } 270} 271 272#undef __ 273