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)25 static 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