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 44 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
55 * Calculate 32-bit Murmur hash (murmur3). | 55 * Calculate 32-bit Murmur hash (murmur3). |
56 * This should take 2-3x longer than SkChecksum::Compute, but is a considera
bly better hash. | 56 * This should take 2-3x longer than SkChecksum::Compute, but is a considera
bly better hash. |
57 * See en.wikipedia.org/wiki/MurmurHash. | 57 * See en.wikipedia.org/wiki/MurmurHash. |
58 * | 58 * |
59 * @param data Memory address of the data block to be processed. Must be 32
-bit aligned. | 59 * @param data Memory address of the data block to be processed. Must be 32
-bit aligned. |
60 * @param size Size of the data block in bytes. Must be a multiple of 4. | 60 * @param size Size of the data block in bytes. Must be a multiple of 4. |
61 * @param seed Initial hash seed. (optional) | 61 * @param seed Initial hash seed. (optional) |
62 * @return hash result | 62 * @return hash result |
63 */ | 63 */ |
64 static uint32_t Murmur3(const uint32_t* data, size_t bytes, uint32_t seed=0)
{ | 64 static uint32_t Murmur3(const uint32_t* data, size_t bytes, uint32_t seed=0)
{ |
| 65 // Use may_alias to remind the compiler we're intentionally violating st
rict aliasing, |
| 66 // and so not to apply strict-aliasing-based optimizations. |
| 67 typedef uint32_t SK_ATTRIBUTE(may_alias) aliased_uint32_t; |
| 68 const aliased_uint32_t* safe_data = (const aliased_uint32_t*)data; |
| 69 |
65 SkASSERTF(SkIsAlign4(bytes), "Expected 4-byte multiple, got %zu", bytes)
; | 70 SkASSERTF(SkIsAlign4(bytes), "Expected 4-byte multiple, got %zu", bytes)
; |
66 const size_t words = bytes/4; | 71 const size_t words = bytes/4; |
67 | 72 |
| 73 |
68 uint32_t hash = seed; | 74 uint32_t hash = seed; |
69 for (size_t i = 0; i < words; i++) { | 75 for (size_t i = 0; i < words; i++) { |
70 uint32_t k = data[i]; | 76 uint32_t k = safe_data[i]; |
71 k *= 0xcc9e2d51; | 77 k *= 0xcc9e2d51; |
72 k = (k << 15) | (k >> 17); | 78 k = (k << 15) | (k >> 17); |
73 k *= 0x1b873593; | 79 k *= 0x1b873593; |
74 | 80 |
75 hash ^= k; | 81 hash ^= k; |
76 hash = (hash << 13) | (hash >> 19); | 82 hash = (hash << 13) | (hash >> 19); |
77 hash *= 5; | 83 hash *= 5; |
78 hash += 0xe6546b64; | 84 hash += 0xe6546b64; |
79 } | 85 } |
80 hash ^= bytes; | 86 hash ^= bytes; |
81 return Mix(hash); | 87 return Mix(hash); |
82 } | 88 } |
83 | 89 |
84 /** | 90 /** |
85 * Compute a 32-bit checksum for a given data block | 91 * Compute a 32-bit checksum for a given data block |
86 * | 92 * |
87 * WARNING: this algorithm is tuned for efficiency, not backward/forward | 93 * WARNING: this algorithm is tuned for efficiency, not backward/forward |
88 * compatibility. It may change at any time, so a checksum generated with | 94 * compatibility. It may change at any time, so a checksum generated with |
89 * one version of the Skia code may not match a checksum generated with | 95 * one version of the Skia code may not match a checksum generated with |
90 * a different version of the Skia code. | 96 * a different version of the Skia code. |
91 * | 97 * |
92 * @param data Memory address of the data block to be processed. Must be | 98 * @param data Memory address of the data block to be processed. Must be |
93 * 32-bit aligned. | 99 * 32-bit aligned. |
94 * @param size Size of the data block in bytes. Must be a multiple of 4. | 100 * @param size Size of the data block in bytes. Must be a multiple of 4. |
95 * @return checksum result | 101 * @return checksum result |
96 */ | 102 */ |
97 static uint32_t Compute(const uint32_t* data, size_t size) { | 103 static uint32_t Compute(const uint32_t* data, size_t size) { |
| 104 // Use may_alias to remind the compiler we're intentionally violating st
rict aliasing, |
| 105 // and so not to apply strict-aliasing-based optimizations. |
| 106 typedef uint32_t SK_ATTRIBUTE(may_alias) aliased_uint32_t; |
| 107 const aliased_uint32_t* safe_data = (const aliased_uint32_t*)data; |
| 108 |
98 SkASSERT(SkIsAlign4(size)); | 109 SkASSERT(SkIsAlign4(size)); |
99 | 110 |
100 /* | 111 /* |
101 * We want to let the compiler use 32bit or 64bit addressing and math | 112 * We want to let the compiler use 32bit or 64bit addressing and math |
102 * so we use uintptr_t as our magic type. This makes the code a little | 113 * so we use uintptr_t as our magic type. This makes the code a little |
103 * more obscure (we can't hard-code 32 or 64 anywhere, but have to use | 114 * more obscure (we can't hard-code 32 or 64 anywhere, but have to use |
104 * sizeof()). | 115 * sizeof()). |
105 */ | 116 */ |
106 uintptr_t result = 0; | 117 uintptr_t result = 0; |
107 const uintptr_t* ptr = reinterpret_cast<const uintptr_t*>(data); | 118 const uintptr_t* ptr = reinterpret_cast<const uintptr_t*>(safe_data); |
108 | 119 |
109 /* | 120 /* |
110 * count the number of quad element chunks. This takes into account | 121 * count the number of quad element chunks. This takes into account |
111 * if we're on a 32bit or 64bit arch, since we use sizeof(uintptr_t) | 122 * if we're on a 32bit or 64bit arch, since we use sizeof(uintptr_t) |
112 * to compute how much to shift-down the size. | 123 * to compute how much to shift-down the size. |
113 */ | 124 */ |
114 size_t n4 = size / (sizeof(uintptr_t) << 2); | 125 size_t n4 = size / (sizeof(uintptr_t) << 2); |
115 for (size_t i = 0; i < n4; ++i) { | 126 for (size_t i = 0; i < n4; ++i) { |
116 result = Mash(result, *ptr++); | 127 result = Mash(result, *ptr++); |
117 result = Mash(result, *ptr++); | 128 result = Mash(result, *ptr++); |
118 result = Mash(result, *ptr++); | 129 result = Mash(result, *ptr++); |
119 result = Mash(result, *ptr++); | 130 result = Mash(result, *ptr++); |
120 } | 131 } |
121 size &= ((sizeof(uintptr_t) << 2) - 1); | 132 size &= ((sizeof(uintptr_t) << 2) - 1); |
122 | 133 |
123 data = reinterpret_cast<const uint32_t*>(ptr); | 134 safe_data = reinterpret_cast<const aliased_uint32_t*>(ptr); |
124 const uint32_t* stop = data + (size >> 2); | 135 const aliased_uint32_t* stop = safe_data + (size >> 2); |
125 while (data < stop) { | 136 while (safe_data < stop) { |
126 result = Mash(result, *data++); | 137 result = Mash(result, *safe_data++); |
127 } | 138 } |
128 | 139 |
129 /* | 140 /* |
130 * smash us down to 32bits if we were 64. Note that when uintptr_t is | 141 * smash us down to 32bits if we were 64. Note that when uintptr_t is |
131 * 32bits, this code-path should go away, but I still got a warning | 142 * 32bits, this code-path should go away, but I still got a warning |
132 * when I wrote | 143 * when I wrote |
133 * result ^= result >> 32; | 144 * result ^= result >> 32; |
134 * since >>32 is undefined for 32bit ints, hence the wacky HALFBITS | 145 * since >>32 is undefined for 32bit ints, hence the wacky HALFBITS |
135 * define. | 146 * define. |
136 */ | 147 */ |
137 if (8 == sizeof(result)) { | 148 if (8 == sizeof(result)) { |
138 result ^= result >> HALFBITS; | 149 result ^= result >> HALFBITS; |
139 } | 150 } |
140 return static_cast<uint32_t>(result); | 151 return static_cast<uint32_t>(result); |
141 } | 152 } |
142 }; | 153 }; |
143 | 154 |
144 #endif | 155 #endif |
OLD | NEW |