1 /* 2 * Copyright (C) 2018 The Android Open Source Project 3 * 4 * Licensed under the Apache License, Version 2.0 (the "License"); 5 * you may not use this file except in compliance with the License. 6 * You may obtain a copy of the License at 7 * 8 * http://www.apache.org/licenses/LICENSE-2.0 9 * 10 * Unless required by applicable law or agreed to in writing, software 11 * distributed under the License is distributed on an "AS IS" BASIS, 12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 13 * See the License for the specific language governing permissions and 14 * limitations under the License. 15 */ 16 17 #ifndef ART_LIBARTBASE_BASE_DATA_HASH_H_ 18 #define ART_LIBARTBASE_BASE_DATA_HASH_H_ 19 20 #include "base/macros.h" 21 22 namespace art { 23 24 // Hash bytes using a relatively fast hash. HashBytes(const uint8_t * data,size_t len)25static inline size_t HashBytes(const uint8_t* data, size_t len) { 26 size_t hash = 0x811c9dc5; 27 for (uint32_t i = 0; i < len; ++i) { 28 hash = (hash * 16777619) ^ data[i]; 29 } 30 hash += hash << 13; 31 hash ^= hash >> 7; 32 hash += hash << 3; 33 hash ^= hash >> 17; 34 hash += hash << 5; 35 return hash; 36 } 37 38 class DataHash { 39 private: 40 static constexpr bool kUseMurmur3Hash = true; 41 42 public: 43 template <class Container> operator()44 size_t operator()(const Container& array) const { 45 // Containers that provide the data() function use contiguous storage. 46 const uint8_t* data = reinterpret_cast<const uint8_t*>(array.data()); 47 uint32_t len = sizeof(typename Container::value_type) * array.size(); 48 if (kUseMurmur3Hash) { 49 static constexpr uint32_t c1 = 0xcc9e2d51; 50 static constexpr uint32_t c2 = 0x1b873593; 51 static constexpr uint32_t r1 = 15; 52 static constexpr uint32_t r2 = 13; 53 static constexpr uint32_t m = 5; 54 static constexpr uint32_t n = 0xe6546b64; 55 56 uint32_t hash = 0; 57 58 const int nblocks = len / 4; 59 typedef __attribute__((__aligned__(1))) uint32_t unaligned_uint32_t; 60 const unaligned_uint32_t *blocks = reinterpret_cast<const uint32_t*>(data); 61 int i; 62 for (i = 0; i < nblocks; i++) { 63 uint32_t k = blocks[i]; 64 k *= c1; 65 k = (k << r1) | (k >> (32 - r1)); 66 k *= c2; 67 68 hash ^= k; 69 hash = ((hash << r2) | (hash >> (32 - r2))) * m + n; 70 } 71 72 const uint8_t *tail = reinterpret_cast<const uint8_t*>(data + nblocks * 4); 73 uint32_t k1 = 0; 74 75 switch (len & 3) { 76 case 3: 77 k1 ^= tail[2] << 16; 78 FALLTHROUGH_INTENDED; 79 case 2: 80 k1 ^= tail[1] << 8; 81 FALLTHROUGH_INTENDED; 82 case 1: 83 k1 ^= tail[0]; 84 85 k1 *= c1; 86 k1 = (k1 << r1) | (k1 >> (32 - r1)); 87 k1 *= c2; 88 hash ^= k1; 89 } 90 91 hash ^= len; 92 hash ^= (hash >> 16); 93 hash *= 0x85ebca6b; 94 hash ^= (hash >> 13); 95 hash *= 0xc2b2ae35; 96 hash ^= (hash >> 16); 97 98 return hash; 99 } else { 100 return HashBytes(data, len); 101 } 102 } 103 }; 104 105 } // namespace art 106 107 #endif // ART_LIBARTBASE_BASE_DATA_HASH_H_ 108