| OLD | NEW |
| 1 // Copyright 2012 the V8 project authors. All rights reserved. | 1 // Copyright 2012 the V8 project authors. All rights reserved. |
| 2 // Redistribution and use in source and binary forms, with or without | 2 // Redistribution and use in source and binary forms, with or without |
| 3 // modification, are permitted provided that the following conditions are | 3 // modification, are permitted provided that the following conditions are |
| 4 // met: | 4 // met: |
| 5 // | 5 // |
| 6 // * Redistributions of source code must retain the above copyright | 6 // * Redistributions of source code must retain the above copyright |
| 7 // notice, this list of conditions and the following disclaimer. | 7 // notice, this list of conditions and the following disclaimer. |
| 8 // * Redistributions in binary form must reproduce the above | 8 // * Redistributions in binary form must reproduce the above |
| 9 // copyright notice, this list of conditions and the following | 9 // copyright notice, this list of conditions and the following |
| 10 // disclaimer in the documentation and/or other materials provided | 10 // disclaimer in the documentation and/or other materials provided |
| (...skipping 4931 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 4942 // Slow case: compute hash code and set it. | 4942 // Slow case: compute hash code and set it. |
| 4943 return ComputeAndSetHash(); | 4943 return ComputeAndSetHash(); |
| 4944 } | 4944 } |
| 4945 | 4945 |
| 4946 | 4946 |
| 4947 StringHasher::StringHasher(int length, uint32_t seed) | 4947 StringHasher::StringHasher(int length, uint32_t seed) |
| 4948 : length_(length), | 4948 : length_(length), |
| 4949 raw_running_hash_(seed), | 4949 raw_running_hash_(seed), |
| 4950 array_index_(0), | 4950 array_index_(0), |
| 4951 is_array_index_(0 < length_ && length_ <= String::kMaxArrayIndexSize), | 4951 is_array_index_(0 < length_ && length_ <= String::kMaxArrayIndexSize), |
| 4952 is_first_char_(true), | 4952 is_first_char_(true) { |
| 4953 is_valid_(true) { | |
| 4954 ASSERT(FLAG_randomize_hashes || raw_running_hash_ == 0); | 4953 ASSERT(FLAG_randomize_hashes || raw_running_hash_ == 0); |
| 4955 } | 4954 } |
| 4956 | 4955 |
| 4957 | 4956 |
| 4958 bool StringHasher::has_trivial_hash() { | 4957 bool StringHasher::has_trivial_hash() { |
| 4959 return length_ > String::kMaxHashCalcLength; | 4958 return length_ > String::kMaxHashCalcLength; |
| 4960 } | 4959 } |
| 4961 | 4960 |
| 4962 | 4961 |
| 4962 uint32_t StringHasher::AddCharacterCore(uint32_t running_hash, uint32_t c) { |
| 4963 running_hash += c; |
| 4964 running_hash += (running_hash << 10); |
| 4965 running_hash ^= (running_hash >> 6); |
| 4966 return running_hash; |
| 4967 } |
| 4968 |
| 4969 |
| 4970 uint32_t StringHasher::GetHashCore(uint32_t running_hash) { |
| 4971 running_hash += (running_hash << 3); |
| 4972 running_hash ^= (running_hash >> 11); |
| 4973 running_hash += (running_hash << 15); |
| 4974 if ((running_hash & String::kHashBitMask) == 0) { |
| 4975 return 27; |
| 4976 } |
| 4977 return running_hash; |
| 4978 } |
| 4979 |
| 4980 |
| 4963 void StringHasher::AddCharacter(uint32_t c) { | 4981 void StringHasher::AddCharacter(uint32_t c) { |
| 4964 if (c > unibrow::Utf16::kMaxNonSurrogateCharCode) { | 4982 if (c > unibrow::Utf16::kMaxNonSurrogateCharCode) { |
| 4965 AddSurrogatePair(c); // Not inlined. | 4983 AddSurrogatePair(c); // Not inlined. |
| 4966 return; | 4984 return; |
| 4967 } | 4985 } |
| 4968 // Use the Jenkins one-at-a-time hash function to update the hash | 4986 // Use the Jenkins one-at-a-time hash function to update the hash |
| 4969 // for the given character. | 4987 // for the given character. |
| 4970 raw_running_hash_ += c; | 4988 raw_running_hash_ = AddCharacterCore(raw_running_hash_, c); |
| 4971 raw_running_hash_ += (raw_running_hash_ << 10); | |
| 4972 raw_running_hash_ ^= (raw_running_hash_ >> 6); | |
| 4973 // Incremental array index computation. | 4989 // Incremental array index computation. |
| 4974 if (is_array_index_) { | 4990 if (is_array_index_) { |
| 4975 if (c < '0' || c > '9') { | 4991 if (c < '0' || c > '9') { |
| 4976 is_array_index_ = false; | 4992 is_array_index_ = false; |
| 4977 } else { | 4993 } else { |
| 4978 int d = c - '0'; | 4994 int d = c - '0'; |
| 4979 if (is_first_char_) { | 4995 if (is_first_char_) { |
| 4980 is_first_char_ = false; | 4996 is_first_char_ = false; |
| 4981 if (c == '0' && length_ > 1) { | 4997 if (c == '0' && length_ > 1) { |
| 4982 is_array_index_ = false; | 4998 is_array_index_ = false; |
| 4983 return; | 4999 return; |
| 4984 } | 5000 } |
| 4985 } | 5001 } |
| 4986 if (array_index_ > 429496729U - ((d + 2) >> 3)) { | 5002 if (array_index_ > 429496729U - ((d + 2) >> 3)) { |
| 4987 is_array_index_ = false; | 5003 is_array_index_ = false; |
| 4988 } else { | 5004 } else { |
| 4989 array_index_ = array_index_ * 10 + d; | 5005 array_index_ = array_index_ * 10 + d; |
| 4990 } | 5006 } |
| 4991 } | 5007 } |
| 4992 } | 5008 } |
| 4993 } | 5009 } |
| 4994 | 5010 |
| 4995 | 5011 |
| 4996 void StringHasher::AddCharacterNoIndex(uint32_t c) { | 5012 void StringHasher::AddCharacterNoIndex(uint32_t c) { |
| 4997 ASSERT(!is_array_index()); | 5013 ASSERT(!is_array_index()); |
| 4998 if (c > unibrow::Utf16::kMaxNonSurrogateCharCode) { | 5014 if (c > unibrow::Utf16::kMaxNonSurrogateCharCode) { |
| 4999 AddSurrogatePairNoIndex(c); // Not inlined. | 5015 AddSurrogatePairNoIndex(c); // Not inlined. |
| 5000 return; | 5016 return; |
| 5001 } | 5017 } |
| 5002 raw_running_hash_ += c; | 5018 raw_running_hash_ = AddCharacterCore(raw_running_hash_, c); |
| 5003 raw_running_hash_ += (raw_running_hash_ << 10); | |
| 5004 raw_running_hash_ ^= (raw_running_hash_ >> 6); | |
| 5005 } | 5019 } |
| 5006 | 5020 |
| 5007 | 5021 |
| 5008 uint32_t StringHasher::GetHash() { | 5022 uint32_t StringHasher::GetHash() { |
| 5009 // Get the calculated raw hash value and do some more bit ops to distribute | 5023 // Get the calculated raw hash value and do some more bit ops to distribute |
| 5010 // the hash further. Ensure that we never return zero as the hash value. | 5024 // the hash further. Ensure that we never return zero as the hash value. |
| 5011 uint32_t result = raw_running_hash_; | 5025 return GetHashCore(raw_running_hash_); |
| 5012 result += (result << 3); | |
| 5013 result ^= (result >> 11); | |
| 5014 result += (result << 15); | |
| 5015 if ((result & String::kHashBitMask) == 0) { | |
| 5016 result = 27; | |
| 5017 } | |
| 5018 return result; | |
| 5019 } | 5026 } |
| 5020 | 5027 |
| 5021 | 5028 |
| 5022 template <typename schar> | 5029 template <typename schar> |
| 5023 uint32_t HashSequentialString(const schar* chars, int length, uint32_t seed) { | 5030 uint32_t HashSequentialString(const schar* chars, int length, uint32_t seed) { |
| 5024 StringHasher hasher(length, seed); | 5031 StringHasher hasher(length, seed); |
| 5025 if (!hasher.has_trivial_hash()) { | 5032 if (!hasher.has_trivial_hash()) { |
| 5026 int i; | 5033 int i; |
| 5027 for (i = 0; hasher.is_array_index() && (i < length); i++) { | 5034 for (i = 0; hasher.is_array_index() && (i < length); i++) { |
| 5028 hasher.AddCharacter(chars[i]); | 5035 hasher.AddCharacter(chars[i]); |
| (...skipping 521 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 5550 #undef WRITE_UINT32_FIELD | 5557 #undef WRITE_UINT32_FIELD |
| 5551 #undef READ_SHORT_FIELD | 5558 #undef READ_SHORT_FIELD |
| 5552 #undef WRITE_SHORT_FIELD | 5559 #undef WRITE_SHORT_FIELD |
| 5553 #undef READ_BYTE_FIELD | 5560 #undef READ_BYTE_FIELD |
| 5554 #undef WRITE_BYTE_FIELD | 5561 #undef WRITE_BYTE_FIELD |
| 5555 | 5562 |
| 5556 | 5563 |
| 5557 } } // namespace v8::internal | 5564 } } // namespace v8::internal |
| 5558 | 5565 |
| 5559 #endif // V8_OBJECTS_INL_H_ | 5566 #endif // V8_OBJECTS_INL_H_ |
| OLD | NEW |