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

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

Issue 19500020: Add SkChecksum::Murmur3. (Closed) Base URL: https://skia.googlecode.com/svn/trunk
Patch Set: Created 7 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 | Annotate | Revision Log
« no previous file with comments | « bench/ChecksumBench.cpp ('k') | tests/ChecksumTest.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 18 matching lines...) Expand all
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 /**
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
39 /** 75 /**
40 * Compute a 32-bit checksum for a given data block 76 * Compute a 32-bit checksum for a given data block
41 * 77 *
42 * WARNING: this algorithm is tuned for efficiency, not backward/forward 78 * WARNING: this algorithm is tuned for efficiency, not backward/forward
43 * 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
44 * 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
45 * a different version of the Skia code. 81 * a different version of the Skia code.
46 * 82 *
47 * @param data Memory address of the data block to be processed. Must be 83 * @param data Memory address of the data block to be processed. Must be
48 * 32-bit aligned. 84 * 32-bit aligned.
(...skipping 41 matching lines...) Expand 10 before | Expand all | Expand 10 after
90 * define. 126 * define.
91 */ 127 */
92 if (8 == sizeof(result)) { 128 if (8 == sizeof(result)) {
93 result ^= result >> HALFBITS; 129 result ^= result >> HALFBITS;
94 } 130 }
95 return static_cast<uint32_t>(result); 131 return static_cast<uint32_t>(result);
96 } 132 }
97 }; 133 };
98 134
99 #endif 135 #endif
OLDNEW
« no previous file with comments | « bench/ChecksumBench.cpp ('k') | tests/ChecksumTest.cpp » ('j') | no next file with comments »

Powered by Google App Engine
This is Rietveld 408576698