OLD | NEW |
| (Empty) |
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 considera
bly 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 | |
OLD | NEW |