OLD | NEW |
1 /* | 1 /* |
2 * Copyright 2012 Google Inc. | 2 * Copyright 2012 Google Inc. |
3 * | 3 * |
4 * Use of this source code is governed by a BSD-style license that can be | 4 * Use of this source code is governed by a BSD-style license that can be |
5 * found in the LICENSE file. | 5 * found in the LICENSE file. |
6 */ | 6 */ |
7 | 7 |
8 #ifndef SkChecksum_DEFINED | 8 #ifndef SkChecksum_DEFINED |
9 #define SkChecksum_DEFINED | 9 #define SkChecksum_DEFINED |
10 | 10 |
(...skipping 58 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
69 /** | 69 /** |
70 * Calculate 32-bit Murmur hash (murmur3). | 70 * Calculate 32-bit Murmur hash (murmur3). |
71 * This should take 2-3x longer than SkChecksum::Compute, but is a considera
bly better hash. | 71 * This should take 2-3x longer than SkChecksum::Compute, but is a considera
bly better hash. |
72 * See en.wikipedia.org/wiki/MurmurHash. | 72 * See en.wikipedia.org/wiki/MurmurHash. |
73 * | 73 * |
74 * @param data Memory address of the data block to be processed. | 74 * @param data Memory address of the data block to be processed. |
75 * @param size Size of the data block in bytes. | 75 * @param size Size of the data block in bytes. |
76 * @param seed Initial hash seed. (optional) | 76 * @param seed Initial hash seed. (optional) |
77 * @return hash result | 77 * @return hash result |
78 */ | 78 */ |
79 static uint32_t Murmur3(const void* data, size_t bytes, uint32_t seed=0) { | 79 static uint32_t Murmur3(const void* data, size_t bytes, uint32_t seed=0); |
80 // Use may_alias to remind the compiler we're intentionally violating st
rict aliasing, | |
81 // and so not to apply strict-aliasing-based optimizations. | |
82 typedef uint32_t SK_ATTRIBUTE(may_alias) aliased_uint32_t; | |
83 typedef uint8_t SK_ATTRIBUTE(may_alias) aliased_uint8_t; | |
84 | |
85 // Handle 4 bytes at a time while possible. | |
86 const aliased_uint32_t* safe_data = (const aliased_uint32_t*)data; | |
87 const size_t words = bytes/4; | |
88 uint32_t hash = seed; | |
89 for (size_t i = 0; i < words; i++) { | |
90 uint32_t k = safe_data[i]; | |
91 k *= 0xcc9e2d51; | |
92 k = (k << 15) | (k >> 17); | |
93 k *= 0x1b873593; | |
94 | |
95 hash ^= k; | |
96 hash = (hash << 13) | (hash >> 19); | |
97 hash *= 5; | |
98 hash += 0xe6546b64; | |
99 } | |
100 | |
101 // Handle last 0-3 bytes. | |
102 const aliased_uint8_t* safe_tail = (const uint8_t*)(safe_data + words); | |
103 uint32_t k = 0; | |
104 switch (bytes & 3) { | |
105 case 3: k ^= safe_tail[2] << 16; | |
106 case 2: k ^= safe_tail[1] << 8; | |
107 case 1: k ^= safe_tail[0] << 0; | |
108 k *= 0xcc9e2d51; | |
109 k = (k << 15) | (k >> 17); | |
110 k *= 0x1b873593; | |
111 hash ^= k; | |
112 } | |
113 | |
114 hash ^= bytes; | |
115 return Mix(hash); | |
116 } | |
117 | 80 |
118 /** | 81 /** |
119 * Compute a 32-bit checksum for a given data block | 82 * Compute a 32-bit checksum for a given data block |
120 * | 83 * |
121 * WARNING: this algorithm is tuned for efficiency, not backward/forward | 84 * WARNING: this algorithm is tuned for efficiency, not backward/forward |
122 * compatibility. It may change at any time, so a checksum generated with | 85 * compatibility. It may change at any time, so a checksum generated with |
123 * one version of the Skia code may not match a checksum generated with | 86 * one version of the Skia code may not match a checksum generated with |
124 * a different version of the Skia code. | 87 * a different version of the Skia code. |
125 * | 88 * |
126 * @param data Memory address of the data block to be processed. Must be | 89 * @param data Memory address of the data block to be processed. Must be |
(...skipping 65 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
192 SK_WHEN(sizeof(K) != 4, uint32_t) operator()(const K& k) const { | 155 SK_WHEN(sizeof(K) != 4, uint32_t) operator()(const K& k) const { |
193 return SkChecksum::Murmur3(&k, sizeof(K)); | 156 return SkChecksum::Murmur3(&k, sizeof(K)); |
194 } | 157 } |
195 | 158 |
196 uint32_t operator()(const SkString& k) const { | 159 uint32_t operator()(const SkString& k) const { |
197 return SkChecksum::Murmur3(k.c_str(), k.size()); | 160 return SkChecksum::Murmur3(k.c_str(), k.size()); |
198 } | 161 } |
199 }; | 162 }; |
200 | 163 |
201 #endif | 164 #endif |
OLD | NEW |