| 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 |