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 47static v8::Persistent<v8::Context> env; 48 49#define __ masm-> 50 51 52void generate(MacroAssembler* masm, i::Vector<const char> string) { 53 // GenerateHashInit takes the first character as an argument so it can't 54 // handle the zero length string. 55 ASSERT(string.length() > 0); 56#ifdef V8_TARGET_ARCH_IA32 57 __ push(ebx); 58 __ push(ecx); 59 __ mov(eax, Immediate(0)); 60 __ mov(ebx, Immediate(string.at(0))); 61 StringHelper::GenerateHashInit(masm, eax, ebx, ecx); 62 for (int i = 1; i < string.length(); i++) { 63 __ mov(ebx, Immediate(string.at(i))); 64 StringHelper::GenerateHashAddCharacter(masm, eax, ebx, ecx); 65 } 66 StringHelper::GenerateHashGetHash(masm, eax, ecx); 67 __ pop(ecx); 68 __ pop(ebx); 69 __ Ret(); 70#elif V8_TARGET_ARCH_X64 71 __ push(kRootRegister); 72 __ InitializeRootRegister(); 73 __ push(rbx); 74 __ push(rcx); 75 __ movq(rax, Immediate(0)); 76 __ movq(rbx, Immediate(string.at(0))); 77 StringHelper::GenerateHashInit(masm, rax, rbx, rcx); 78 for (int i = 1; i < string.length(); i++) { 79 __ movq(rbx, Immediate(string.at(i))); 80 StringHelper::GenerateHashAddCharacter(masm, rax, rbx, rcx); 81 } 82 StringHelper::GenerateHashGetHash(masm, rax, rcx); 83 __ pop(rcx); 84 __ pop(rbx); 85 __ pop(kRootRegister); 86 __ Ret(); 87#elif V8_TARGET_ARCH_ARM 88 __ push(kRootRegister); 89 __ InitializeRootRegister(); 90 91 __ mov(r0, Operand(0)); 92 __ mov(ip, Operand(string.at(0))); 93 StringHelper::GenerateHashInit(masm, r0, ip); 94 for (int i = 1; i < string.length(); i++) { 95 __ mov(ip, Operand(string.at(i))); 96 StringHelper::GenerateHashAddCharacter(masm, r0, ip); 97 } 98 StringHelper::GenerateHashGetHash(masm, r0); 99 __ pop(kRootRegister); 100 __ mov(pc, Operand(lr)); 101#elif V8_TARGET_ARCH_MIPS 102 __ push(kRootRegister); 103 __ InitializeRootRegister(); 104 105 __ li(v0, Operand(0)); 106 __ li(t1, Operand(string.at(0))); 107 StringHelper::GenerateHashInit(masm, v0, t1); 108 for (int i = 1; i < string.length(); i++) { 109 __ li(t1, Operand(string.at(i))); 110 StringHelper::GenerateHashAddCharacter(masm, v0, t1); 111 } 112 StringHelper::GenerateHashGetHash(masm, v0); 113 __ pop(kRootRegister); 114 __ jr(ra); 115 __ nop(); 116#endif 117} 118 119 120void generate(MacroAssembler* masm, uint32_t key) { 121#ifdef V8_TARGET_ARCH_IA32 122 __ push(ebx); 123 __ mov(eax, Immediate(key)); 124 __ GetNumberHash(eax, ebx); 125 __ pop(ebx); 126 __ Ret(); 127#elif V8_TARGET_ARCH_X64 128 __ push(kRootRegister); 129 __ InitializeRootRegister(); 130 __ push(rbx); 131 __ movq(rax, Immediate(key)); 132 __ GetNumberHash(rax, rbx); 133 __ pop(rbx); 134 __ pop(kRootRegister); 135 __ Ret(); 136#elif V8_TARGET_ARCH_ARM 137 __ push(kRootRegister); 138 __ InitializeRootRegister(); 139 __ mov(r0, Operand(key)); 140 __ GetNumberHash(r0, ip); 141 __ pop(kRootRegister); 142 __ mov(pc, Operand(lr)); 143#elif V8_TARGET_ARCH_MIPS 144 __ push(kRootRegister); 145 __ InitializeRootRegister(); 146 __ li(v0, Operand(key)); 147 __ GetNumberHash(v0, t1); 148 __ pop(kRootRegister); 149 __ jr(ra); 150 __ nop(); 151#endif 152} 153 154 155void check(i::Vector<const char> string) { 156 v8::HandleScope scope; 157 v8::internal::byte buffer[2048]; 158 MacroAssembler masm(Isolate::Current(), buffer, sizeof buffer); 159 160 generate(&masm, string); 161 162 CodeDesc desc; 163 masm.GetCode(&desc); 164 Code* code = Code::cast(HEAP->CreateCode( 165 desc, 166 Code::ComputeFlags(Code::STUB), 167 Handle<Object>(HEAP->undefined_value()))->ToObjectChecked()); 168 CHECK(code->IsCode()); 169 170 HASH_FUNCTION hash = FUNCTION_CAST<HASH_FUNCTION>(code->entry()); 171 Handle<String> v8_string = FACTORY->NewStringFromAscii(string); 172 v8_string->set_hash_field(String::kEmptyHashField); 173#ifdef USE_SIMULATOR 174 uint32_t codegen_hash = 175 reinterpret_cast<uint32_t>(CALL_GENERATED_CODE(hash, 0, 0, 0, 0, 0)); 176#else 177 uint32_t codegen_hash = hash(); 178#endif 179 uint32_t runtime_hash = v8_string->Hash(); 180 CHECK(runtime_hash == codegen_hash); 181} 182 183 184void check(uint32_t key) { 185 v8::HandleScope scope; 186 v8::internal::byte buffer[2048]; 187 MacroAssembler masm(Isolate::Current(), buffer, sizeof buffer); 188 189 generate(&masm, key); 190 191 CodeDesc desc; 192 masm.GetCode(&desc); 193 Code* code = Code::cast(HEAP->CreateCode( 194 desc, 195 Code::ComputeFlags(Code::STUB), 196 Handle<Object>(HEAP->undefined_value()))->ToObjectChecked()); 197 CHECK(code->IsCode()); 198 199 HASH_FUNCTION hash = FUNCTION_CAST<HASH_FUNCTION>(code->entry()); 200#ifdef USE_SIMULATOR 201 uint32_t codegen_hash = 202 reinterpret_cast<uint32_t>(CALL_GENERATED_CODE(hash, 0, 0, 0, 0, 0)); 203#else 204 uint32_t codegen_hash = hash(); 205#endif 206 207 uint32_t runtime_hash = ComputeIntegerHash( 208 key, 209 Isolate::Current()->heap()->HashSeed()); 210 CHECK(runtime_hash == codegen_hash); 211} 212 213 214void check_twochars(char a, char b) { 215 char ab[2] = {a, b}; 216 check(i::Vector<const char>(ab, 2)); 217} 218 219 220static uint32_t PseudoRandom(uint32_t i, uint32_t j) { 221 return ~(~((i * 781) ^ (j * 329))); 222} 223 224 225TEST(StringHash) { 226 if (env.IsEmpty()) env = v8::Context::New(); 227 for (int a = 0; a < String::kMaxAsciiCharCode; a++) { 228 // Numbers are hashed differently. 229 if (a >= '0' && a <= '9') continue; 230 for (int b = 0; b < String::kMaxAsciiCharCode; b++) { 231 if (b >= '0' && b <= '9') continue; 232 check_twochars(static_cast<char>(a), static_cast<char>(b)); 233 } 234 } 235 check(i::Vector<const char>("*", 1)); 236 check(i::Vector<const char>(".zZ", 3)); 237 check(i::Vector<const char>("muc", 3)); 238 check(i::Vector<const char>("(>'_')>", 7)); 239 check(i::Vector<const char>("-=[ vee eight ftw ]=-", 21)); 240} 241 242 243TEST(NumberHash) { 244 if (env.IsEmpty()) env = v8::Context::New(); 245 246 // Some specific numbers 247 for (uint32_t key = 0; key < 42; key += 7) { 248 check(key); 249 } 250 251 // Some pseudo-random numbers 252 static const uint32_t kLimit = 1000; 253 for (uint32_t i = 0; i < 5; i++) { 254 for (uint32_t j = 0; j < 5; j++) { 255 check(PseudoRandom(i, j) % kLimit); 256 } 257 } 258} 259 260#undef __ 261