The Tor Browser / file comparison
comparison: gfx/skia/trunk/include/core/SkChecksum.h
gfx/skia/trunk/include/core/SkChecksum.h
- branch
- TOR_BUG_3246
- changeset 7
- 129ffea94266
equal
deleted
inserted
replaced
| -1:000000000000 | 0:8c56913bb7fc |
|---|---|
| 1 /* | |
| 2 * Copyright 2012 Google Inc. | |
| 3 * | |
| 4 * Use of this source code is governed by a BSD-style license that can be | |
| 5 * found in the LICENSE file. | |
| 6 */ | |
| 7 | |
| 8 #ifndef SkChecksum_DEFINED | |
| 9 #define SkChecksum_DEFINED | |
| 10 | |
| 11 #include "SkTypes.h" | |
| 12 | |
| 13 /** | |
| 14 * Computes a 32bit checksum from a blob of 32bit aligned data. This is meant | |
| 15 * to be very very fast, as it is used internally by the font cache, in | |
| 16 * conjuction with the entire raw key. This algorithm does not generate | |
| 17 * unique values as well as others (e.g. MD5) but it performs much faster. | |
| 18 * Skia's use cases can survive non-unique values (since the entire key is | |
| 19 * always available). Clients should only be used in circumstances where speed | |
| 20 * over uniqueness is at a premium. | |
| 21 */ | |
| 22 class SkChecksum : SkNoncopyable { | |
| 23 private: | |
| 24 /* | |
| 25 * Our Rotate and Mash helpers are meant to automatically do the right | |
| 26 * thing depending if sizeof(uintptr_t) is 4 or 8. | |
| 27 */ | |
| 28 enum { | |
| 29 ROTR = 17, | |
| 30 ROTL = sizeof(uintptr_t) * 8 - ROTR, | |
| 31 HALFBITS = sizeof(uintptr_t) * 4 | |
| 32 }; | |
| 33 | |
| 34 static inline uintptr_t Mash(uintptr_t total, uintptr_t value) { | |
| 35 return ((total >> ROTR) | (total << ROTL)) ^ value; | |
| 36 } | |
| 37 | |
| 38 public: | |
| 39 | |
| 40 /** | |
| 41 * Calculate 32-bit Murmur hash (murmur3). | |
| 42 * This should take 2-3x longer than SkChecksum::Compute, but is a considerably better hash. | |
| 43 * See en.wikipedia.org/wiki/MurmurHash. | |
| 44 * | |
| 45 * @param data Memory address of the data block to be processed. Must be 32-bit aligned. | |
| 46 * @param size Size of the data block in bytes. Must be a multiple of 4. | |
| 47 * @param seed Initial hash seed. (optional) | |
| 48 * @return hash result | |
| 49 */ | |
| 50 static uint32_t Murmur3(const uint32_t* data, size_t bytes, uint32_t seed=0) { | |
| 51 SkASSERT(SkIsAlign4(bytes)); | |
| 52 const size_t words = bytes/4; | |
| 53 | |
| 54 uint32_t hash = seed; | |
| 55 for (size_t i = 0; i < words; i++) { | |
| 56 uint32_t k = data[i]; | |
| 57 k *= 0xcc9e2d51; | |
| 58 k = (k << 15) | (k >> 17); | |
| 59 k *= 0x1b873593; | |
| 60 | |
| 61 hash ^= k; | |
| 62 hash = (hash << 13) | (hash >> 19); | |
| 63 hash *= 5; | |
| 64 hash += 0xe6546b64; | |
| 65 } | |
| 66 hash ^= bytes; | |
| 67 hash ^= hash >> 16; | |
| 68 hash *= 0x85ebca6b; | |
| 69 hash ^= hash >> 13; | |
| 70 hash *= 0xc2b2ae35; | |
| 71 hash ^= hash >> 16; | |
| 72 return hash; | |
| 73 } | |
| 74 | |
| 75 /** | |
| 76 * Compute a 32-bit checksum for a given data block | |
| 77 * | |
| 78 * WARNING: this algorithm is tuned for efficiency, not backward/forward | |
| 79 * compatibility. It may change at any time, so a checksum generated with | |
| 80 * one version of the Skia code may not match a checksum generated with | |
| 81 * a different version of the Skia code. | |
| 82 * | |
| 83 * @param data Memory address of the data block to be processed. Must be | |
| 84 * 32-bit aligned. | |
| 85 * @param size Size of the data block in bytes. Must be a multiple of 4. | |
| 86 * @return checksum result | |
| 87 */ | |
| 88 static uint32_t Compute(const uint32_t* data, size_t size) { | |
| 89 SkASSERT(SkIsAlign4(size)); | |
| 90 | |
| 91 /* | |
| 92 * We want to let the compiler use 32bit or 64bit addressing and math | |
| 93 * so we use uintptr_t as our magic type. This makes the code a little | |
| 94 * more obscure (we can't hard-code 32 or 64 anywhere, but have to use | |
| 95 * sizeof()). | |
| 96 */ | |
| 97 uintptr_t result = 0; | |
| 98 const uintptr_t* ptr = reinterpret_cast<const uintptr_t*>(data); | |
| 99 | |
| 100 /* | |
| 101 * count the number of quad element chunks. This takes into account | |
| 102 * if we're on a 32bit or 64bit arch, since we use sizeof(uintptr_t) | |
| 103 * to compute how much to shift-down the size. | |
| 104 */ | |
| 105 size_t n4 = size / (sizeof(uintptr_t) << 2); | |
| 106 for (size_t i = 0; i < n4; ++i) { | |
| 107 result = Mash(result, *ptr++); | |
| 108 result = Mash(result, *ptr++); | |
| 109 result = Mash(result, *ptr++); | |
| 110 result = Mash(result, *ptr++); | |
| 111 } | |
| 112 size &= ((sizeof(uintptr_t) << 2) - 1); | |
| 113 | |
| 114 data = reinterpret_cast<const uint32_t*>(ptr); | |
| 115 const uint32_t* stop = data + (size >> 2); | |
| 116 while (data < stop) { | |
| 117 result = Mash(result, *data++); | |
| 118 } | |
| 119 | |
| 120 /* | |
| 121 * smash us down to 32bits if we were 64. Note that when uintptr_t is | |
| 122 * 32bits, this code-path should go away, but I still got a warning | |
| 123 * when I wrote | |
| 124 * result ^= result >> 32; | |
| 125 * since >>32 is undefined for 32bit ints, hence the wacky HALFBITS | |
| 126 * define. | |
| 127 */ | |
| 128 if (8 == sizeof(result)) { | |
| 129 result ^= result >> HALFBITS; | |
| 130 } | |
| 131 return static_cast<uint32_t>(result); | |
| 132 } | |
| 133 }; | |
| 134 | |
| 135 #endif |
