Chromium Code Reviews
chromiumcodereview-hr@appspot.gserviceaccount.com (chromiumcodereview-hr) | Please choose your nickname with Settings | Help | Chromium Project | Gerrit Changes | Sign out
(863)

Side by Side Diff: src/core/SkChecksum.h

Issue 376183004: Slim Skia down to just one murmur3 implementation. (Closed) Base URL: https://skia.googlesource.com/skia.git@master
Patch Set: fix types Created 6 years, 5 months ago
Use n/p to move between diff chunks; N/P to move between comments. Draft comments are only viewable by you.
Jump to:
View unified diff | Download patch
« no previous file with comments | « no previous file | src/core/SkImageFilter.cpp » ('j') | no next file with comments »
Toggle Intra-line Diffs ('i') | Expand Comments ('e') | Collapse Comments ('c') | Show Comments Hide Comments ('s')
OLDNEW
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
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
OLDNEW
« no previous file with comments | « no previous file | src/core/SkImageFilter.cpp » ('j') | no next file with comments »

Powered by Google App Engine
This is Rietveld 408576698