| 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 18 matching lines...) Expand all Loading... |
| 29 ROTR = 17, | 29 ROTR = 17, |
| 30 ROTL = sizeof(uintptr_t) * 8 - ROTR, | 30 ROTL = sizeof(uintptr_t) * 8 - ROTR, |
| 31 HALFBITS = sizeof(uintptr_t) * 4 | 31 HALFBITS = sizeof(uintptr_t) * 4 |
| 32 }; | 32 }; |
| 33 | 33 |
| 34 static inline uintptr_t Mash(uintptr_t total, uintptr_t value) { | 34 static inline uintptr_t Mash(uintptr_t total, uintptr_t value) { |
| 35 return ((total >> ROTR) | (total << ROTL)) ^ value; | 35 return ((total >> ROTR) | (total << ROTL)) ^ value; |
| 36 } | 36 } |
| 37 | 37 |
| 38 public: | 38 public: |
| 39 /** | |
| 40 * uint32_t -> uint32_t hash, useful for when you're about to trucate this h
ash but you | |
| 41 * suspect its low bits aren't well mixed. | |
| 42 * | |
| 43 * This is the Murmur3 finalizer. | |
| 44 */ | |
| 45 static uint32_t Mix(uint32_t hash) { | |
| 46 hash ^= hash >> 16; | |
| 47 hash *= 0x85ebca6b; | |
| 48 hash ^= hash >> 13; | |
| 49 hash *= 0xc2b2ae35; | |
| 50 hash ^= hash >> 16; | |
| 51 return hash; | |
| 52 } | |
| 53 | 39 |
| 54 /** | 40 /** |
| 55 * Calculate 32-bit Murmur hash (murmur3). | 41 * Calculate 32-bit Murmur hash (murmur3). |
| 56 * This should take 2-3x longer than SkChecksum::Compute, but is a considera
bly better hash. | 42 * This should take 2-3x longer than SkChecksum::Compute, but is a considera
bly better hash. |
| 57 * See en.wikipedia.org/wiki/MurmurHash. | 43 * See en.wikipedia.org/wiki/MurmurHash. |
| 58 * | 44 * |
| 59 * @param data Memory address of the data block to be processed. Must be 32
-bit aligned. | 45 * @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. | 46 * @param size Size of the data block in bytes. Must be a multiple of 4. |
| 61 * @param seed Initial hash seed. (optional) | 47 * @param seed Initial hash seed. (optional) |
| 62 * @return hash result | 48 * @return hash result |
| 63 */ | 49 */ |
| 64 static uint32_t Murmur3(const uint32_t* data, size_t bytes, uint32_t seed=0)
{ | 50 static uint32_t Murmur3(const uint32_t* data, size_t bytes, uint32_t seed=0)
{ |
| 65 SkASSERTF(SkIsAlign4(bytes), "Expected 4-byte multiple, got %zu", bytes)
; | 51 SkASSERT(SkIsAlign4(bytes)); |
| 66 const size_t words = bytes/4; | 52 const size_t words = bytes/4; |
| 67 | 53 |
| 68 uint32_t hash = seed; | 54 uint32_t hash = seed; |
| 69 for (size_t i = 0; i < words; i++) { | 55 for (size_t i = 0; i < words; i++) { |
| 70 uint32_t k = data[i]; | 56 uint32_t k = data[i]; |
| 71 k *= 0xcc9e2d51; | 57 k *= 0xcc9e2d51; |
| 72 k = (k << 15) | (k >> 17); | 58 k = (k << 15) | (k >> 17); |
| 73 k *= 0x1b873593; | 59 k *= 0x1b873593; |
| 74 | 60 |
| 75 hash ^= k; | 61 hash ^= k; |
| 76 hash = (hash << 13) | (hash >> 19); | 62 hash = (hash << 13) | (hash >> 19); |
| 77 hash *= 5; | 63 hash *= 5; |
| 78 hash += 0xe6546b64; | 64 hash += 0xe6546b64; |
| 79 } | 65 } |
| 80 hash ^= bytes; | 66 hash ^= bytes; |
| 81 return Mix(hash); | 67 hash ^= hash >> 16; |
| 68 hash *= 0x85ebca6b; |
| 69 hash ^= hash >> 13; |
| 70 hash *= 0xc2b2ae35; |
| 71 hash ^= hash >> 16; |
| 72 return hash; |
| 82 } | 73 } |
| 83 | 74 |
| 84 /** | 75 /** |
| 85 * Compute a 32-bit checksum for a given data block | 76 * Compute a 32-bit checksum for a given data block |
| 86 * | 77 * |
| 87 * WARNING: this algorithm is tuned for efficiency, not backward/forward | 78 * WARNING: this algorithm is tuned for efficiency, not backward/forward |
| 88 * compatibility. It may change at any time, so a checksum generated with | 79 * 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 | 80 * one version of the Skia code may not match a checksum generated with |
| 90 * a different version of the Skia code. | 81 * a different version of the Skia code. |
| 91 * | 82 * |
| (...skipping 43 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 135 * define. | 126 * define. |
| 136 */ | 127 */ |
| 137 if (8 == sizeof(result)) { | 128 if (8 == sizeof(result)) { |
| 138 result ^= result >> HALFBITS; | 129 result ^= result >> HALFBITS; |
| 139 } | 130 } |
| 140 return static_cast<uint32_t>(result); | 131 return static_cast<uint32_t>(result); |
| 141 } | 132 } |
| 142 }; | 133 }; |
| 143 | 134 |
| 144 #endif | 135 #endif |
| OLD | NEW |