| 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 33 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 44 */ | 44 */ |
| 45 static uint32_t Mix(uint32_t hash) { | 45 static uint32_t Mix(uint32_t hash) { |
| 46 hash ^= hash >> 16; | 46 hash ^= hash >> 16; |
| 47 hash *= 0x85ebca6b; | 47 hash *= 0x85ebca6b; |
| 48 hash ^= hash >> 13; | 48 hash ^= hash >> 13; |
| 49 hash *= 0xc2b2ae35; | 49 hash *= 0xc2b2ae35; |
| 50 hash ^= hash >> 16; | 50 hash ^= hash >> 16; |
| 51 return hash; | 51 return hash; |
| 52 } | 52 } |
| 53 | 53 |
| 54 // Remind compiler that our users will be intentionally violating strict ali
asing by casting | |
| 55 // their data to const uint32_t*, so don't apply any strict-aliasing-based o
ptimizations. | |
| 56 typedef uint32_t SK_ATTRIBUTE(may_alias) FourByteAligned; | |
| 57 | |
| 58 /** | 54 /** |
| 59 * Calculate 32-bit Murmur hash (murmur3). | 55 * Calculate 32-bit Murmur hash (murmur3). |
| 60 * 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. |
| 61 * See en.wikipedia.org/wiki/MurmurHash. | 57 * See en.wikipedia.org/wiki/MurmurHash. |
| 62 * | 58 * |
| 63 * @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. |
| 64 * @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. |
| 65 * @param seed Initial hash seed. (optional) | 61 * @param seed Initial hash seed. (optional) |
| 66 * @return hash result | 62 * @return hash result |
| 67 */ | 63 */ |
| 68 static uint32_t Murmur3(const FourByteAligned* data, size_t bytes, uint32_t
seed=0) { | 64 static uint32_t Murmur3(const uint32_t* data, size_t bytes, uint32_t seed=0)
{ |
| 69 SkASSERTF(SkIsAlign4(bytes), "Expected 4-byte multiple, got %zu", bytes)
; | 65 SkASSERTF(SkIsAlign4(bytes), "Expected 4-byte multiple, got %zu", bytes)
; |
| 70 const size_t words = bytes/4; | 66 const size_t words = bytes/4; |
| 71 | 67 |
| 72 uint32_t hash = seed; | 68 uint32_t hash = seed; |
| 73 for (size_t i = 0; i < words; i++) { | 69 for (size_t i = 0; i < words; i++) { |
| 74 uint32_t k = data[i]; | 70 uint32_t k = data[i]; |
| 75 k *= 0xcc9e2d51; | 71 k *= 0xcc9e2d51; |
| 76 k = (k << 15) | (k >> 17); | 72 k = (k << 15) | (k >> 17); |
| 77 k *= 0x1b873593; | 73 k *= 0x1b873593; |
| 78 | 74 |
| (...skipping 12 matching lines...) Expand all Loading... |
| 91 * WARNING: this algorithm is tuned for efficiency, not backward/forward | 87 * WARNING: this algorithm is tuned for efficiency, not backward/forward |
| 92 * compatibility. It may change at any time, so a checksum generated with | 88 * compatibility. It may change at any time, so a checksum generated with |
| 93 * one version of the Skia code may not match a checksum generated with | 89 * one version of the Skia code may not match a checksum generated with |
| 94 * a different version of the Skia code. | 90 * a different version of the Skia code. |
| 95 * | 91 * |
| 96 * @param data Memory address of the data block to be processed. Must be | 92 * @param data Memory address of the data block to be processed. Must be |
| 97 * 32-bit aligned. | 93 * 32-bit aligned. |
| 98 * @param size Size of the data block in bytes. Must be a multiple of 4. | 94 * @param size Size of the data block in bytes. Must be a multiple of 4. |
| 99 * @return checksum result | 95 * @return checksum result |
| 100 */ | 96 */ |
| 101 static uint32_t Compute(const FourByteAligned* data, size_t size) { | 97 static uint32_t Compute(const uint32_t* data, size_t size) { |
| 102 SkASSERT(SkIsAlign4(size)); | 98 SkASSERT(SkIsAlign4(size)); |
| 103 | 99 |
| 104 /* | 100 /* |
| 105 * We want to let the compiler use 32bit or 64bit addressing and math | 101 * We want to let the compiler use 32bit or 64bit addressing and math |
| 106 * so we use uintptr_t as our magic type. This makes the code a little | 102 * so we use uintptr_t as our magic type. This makes the code a little |
| 107 * more obscure (we can't hard-code 32 or 64 anywhere, but have to use | 103 * more obscure (we can't hard-code 32 or 64 anywhere, but have to use |
| 108 * sizeof()). | 104 * sizeof()). |
| 109 */ | 105 */ |
| 110 uintptr_t result = 0; | 106 uintptr_t result = 0; |
| 111 const uintptr_t* ptr = reinterpret_cast<const uintptr_t*>(data); | 107 const uintptr_t* ptr = reinterpret_cast<const uintptr_t*>(data); |
| (...skipping 27 matching lines...) Expand all Loading... |
| 139 * define. | 135 * define. |
| 140 */ | 136 */ |
| 141 if (8 == sizeof(result)) { | 137 if (8 == sizeof(result)) { |
| 142 result ^= result >> HALFBITS; | 138 result ^= result >> HALFBITS; |
| 143 } | 139 } |
| 144 return static_cast<uint32_t>(result); | 140 return static_cast<uint32_t>(result); |
| 145 } | 141 } |
| 146 }; | 142 }; |
| 147 | 143 |
| 148 #endif | 144 #endif |
| OLD | NEW |