diff options
author | mtklein <mtklein@chromium.org> | 2015-11-16 09:08:21 -0800 |
---|---|---|
committer | Commit bot <commit-bot@chromium.org> | 2015-11-16 09:08:21 -0800 |
commit | 540e95483d285b555e9b1a73d18c16e7d7c0deba (patch) | |
tree | ed0b5c3e816c1016913ff0773887d970afb42d0c | |
parent | e004bfc0a5e28cc083158f1a75e981ffd58a8134 (diff) |
Switch uses of SkChecksum::Compute to Murmur3.
SkChecksum::Compute is a very, very poorly distributed hash function.
This replaces all remaining uses with Murmur3.
The only interesting stuff is in src/gpu.
BUG=skia:
Committed: https://skia.googlesource.com/skia/+/1d024a3c909ae5cefa5e8b339e2b52dc73ee85ac
Review URL: https://codereview.chromium.org/1436973003
-rw-r--r-- | bench/ChecksumBench.cpp | 9 | ||||
-rw-r--r-- | include/private/SkChecksum.h | 89 | ||||
-rw-r--r-- | src/core/SkPictureFlat.h | 4 | ||||
-rw-r--r-- | src/gpu/GrProgramDesc.h | 3 | ||||
-rw-r--r-- | src/gpu/GrResourceCache.cpp | 8 | ||||
-rw-r--r-- | tests/ChecksumTest.cpp | 2 |
6 files changed, 8 insertions, 107 deletions
diff --git a/bench/ChecksumBench.cpp b/bench/ChecksumBench.cpp index a2c282435e..92e7da662f 100644 --- a/bench/ChecksumBench.cpp +++ b/bench/ChecksumBench.cpp @@ -13,7 +13,6 @@ #include "SkTemplates.h" enum ChecksumType { - kChecksum_ChecksumType, kMD5_ChecksumType, kSHA1_ChecksumType, kMurmur3_ChecksumType, @@ -42,7 +41,6 @@ public: protected: const char* onGetName() override { switch (fType) { - case kChecksum_ChecksumType: return "compute_checksum"; case kMD5_ChecksumType: return "compute_md5"; case kSHA1_ChecksumType: return "compute_sha1"; case kMurmur3_ChecksumType: return "compute_murmur3"; @@ -53,12 +51,6 @@ protected: void onDraw(int loops, SkCanvas*) override { switch (fType) { - case kChecksum_ChecksumType: { - for (int i = 0; i < loops; i++) { - volatile uint32_t result = SkChecksum::Compute(fData, sizeof(fData)); - sk_ignore_unused_variable(result); - } - } break; case kMD5_ChecksumType: { for (int i = 0; i < loops; i++) { SkMD5 md5; @@ -91,7 +83,6 @@ private: /////////////////////////////////////////////////////////////////////////////// -DEF_BENCH( return new ComputeChecksumBench(kChecksum_ChecksumType); ) DEF_BENCH( return new ComputeChecksumBench(kMD5_ChecksumType); ) DEF_BENCH( return new ComputeChecksumBench(kSHA1_ChecksumType); ) DEF_BENCH( return new ComputeChecksumBench(kMurmur3_ChecksumType); ) diff --git a/include/private/SkChecksum.h b/include/private/SkChecksum.h index 4526416fc1..6289a444ae 100644 --- a/include/private/SkChecksum.h +++ b/include/private/SkChecksum.h @@ -12,31 +12,7 @@ #include "SkTLogic.h" #include "SkTypes.h" -/** - * Computes a 32bit checksum from a blob of 32bit aligned data. This is meant - * to be very very fast, as it is used internally by the font cache, in - * conjuction with the entire raw key. This algorithm does not generate - * unique values as well as others (e.g. MD5) but it performs much faster. - * Skia's use cases can survive non-unique values (since the entire key is - * always available). Clients should only be used in circumstances where speed - * over uniqueness is at a premium. - */ class SkChecksum : SkNoncopyable { -private: - /* - * Our Rotate and Mash helpers are meant to automatically do the right - * thing depending if sizeof(uintptr_t) is 4 or 8. - */ - enum { - ROTR = 17, - ROTL = sizeof(uintptr_t) * 8 - ROTR, - HALFBITS = sizeof(uintptr_t) * 4 - }; - - static inline uintptr_t Mash(uintptr_t total, uintptr_t value) { - return ((total >> ROTR) | (total << ROTL)) ^ value; - } - public: /** * uint32_t -> uint32_t hash, useful for when you're about to trucate this hash but you @@ -68,7 +44,6 @@ public: /** * Calculate 32-bit Murmur hash (murmur3). - * This should take 2-3x longer than SkChecksum::Compute, but is a considerably better hash. * See en.wikipedia.org/wiki/MurmurHash. * * @param data Memory address of the data block to be processed. @@ -77,70 +52,6 @@ public: * @return hash result */ static uint32_t Murmur3(const void* data, size_t bytes, uint32_t seed=0); - - /** - * Compute a 32-bit checksum for a given data block - * - * WARNING: this algorithm is tuned for efficiency, not backward/forward - * compatibility. It may change at any time, so a checksum generated with - * one version of the Skia code may not match a checksum generated with - * a different version of the Skia code. - * - * @param data Memory address of the data block to be processed. Must be - * 32-bit aligned. - * @param size Size of the data block in bytes. Must be a multiple of 4. - * @return checksum result - */ - static uint32_t Compute(const uint32_t* data, size_t size) { - // Use may_alias to remind the compiler we're intentionally violating strict aliasing, - // and so not to apply strict-aliasing-based optimizations. - typedef uint32_t SK_ATTRIBUTE(may_alias) aliased_uint32_t; - const aliased_uint32_t* safe_data = (const aliased_uint32_t*)data; - - SkASSERT(SkIsAlign4(size)); - - /* - * We want to let the compiler use 32bit or 64bit addressing and math - * so we use uintptr_t as our magic type. This makes the code a little - * more obscure (we can't hard-code 32 or 64 anywhere, but have to use - * sizeof()). - */ - uintptr_t result = 0; - const uintptr_t* ptr = reinterpret_cast<const uintptr_t*>(safe_data); - - /* - * count the number of quad element chunks. This takes into account - * if we're on a 32bit or 64bit arch, since we use sizeof(uintptr_t) - * to compute how much to shift-down the size. - */ - size_t n4 = size / (sizeof(uintptr_t) << 2); - for (size_t i = 0; i < n4; ++i) { - result = Mash(result, *ptr++); - result = Mash(result, *ptr++); - result = Mash(result, *ptr++); - result = Mash(result, *ptr++); - } - size &= ((sizeof(uintptr_t) << 2) - 1); - - safe_data = reinterpret_cast<const aliased_uint32_t*>(ptr); - const aliased_uint32_t* stop = safe_data + (size >> 2); - while (safe_data < stop) { - result = Mash(result, *safe_data++); - } - - /* - * smash us down to 32bits if we were 64. Note that when uintptr_t is - * 32bits, this code-path should go away, but I still got a warning - * when I wrote - * result ^= result >> 32; - * since >>32 is undefined for 32bit ints, hence the wacky HALFBITS - * define. - */ - if (8 == sizeof(result)) { - result ^= result >> HALFBITS; - } - return static_cast<uint32_t>(result); - } }; // SkGoodHash should usually be your first choice in hashing data. diff --git a/src/core/SkPictureFlat.h b/src/core/SkPictureFlat.h index 98a43ecb57..8befca0538 100644 --- a/src/core/SkPictureFlat.h +++ b/src/core/SkPictureFlat.h @@ -179,7 +179,7 @@ class SkFlatData; class SkFlatController : public SkRefCnt { public: - + SkFlatController(uint32_t writeBufferFlags = 0); virtual ~SkFlatController(); @@ -357,7 +357,7 @@ private: fIndex = index; fFlatSize = size; fTopBot[0] = SK_ScalarNaN; // Mark as unwritten. - fChecksum = SkChecksum::Compute((uint32_t*)this->data(), size); + fChecksum = SkChecksum::Murmur3(this->data(), size); } int fIndex; diff --git a/src/gpu/GrProgramDesc.h b/src/gpu/GrProgramDesc.h index 05b52cc7cd..9641195354 100644 --- a/src/gpu/GrProgramDesc.h +++ b/src/gpu/GrProgramDesc.h @@ -107,8 +107,7 @@ protected: *(this->atOffset<uint32_t, GrProgramDesc::kLengthOffset>()) = SkToU32(keyLength); uint32_t* checksum = this->atOffset<uint32_t, GrProgramDesc::kChecksumOffset>(); - *checksum = 0; - *checksum = SkChecksum::Compute(reinterpret_cast<uint32_t*>(fKey.begin()), keyLength); + *checksum = SkChecksum::Murmur3(fKey.begin(), keyLength); } // The key, stored in fKey, is composed of four parts: diff --git a/src/gpu/GrResourceCache.cpp b/src/gpu/GrResourceCache.cpp index cb6bcf75fd..4a0c9b2b36 100644 --- a/src/gpu/GrResourceCache.cpp +++ b/src/gpu/GrResourceCache.cpp @@ -42,7 +42,7 @@ GrUniqueKey::Domain GrUniqueKey::GenerateDomain() { } uint32_t GrResourceKeyHash(const uint32_t* data, size_t size) { - return SkChecksum::Compute(data, size); + return SkChecksum::Murmur3(data, size); } ////////////////////////////////////////////////////////////////////////////// @@ -564,7 +564,7 @@ uint32_t GrResourceCache::getNextTimestamp() { int currP = 0; int currNP = 0; while (currP < sortedPurgeableResources.count() && - currNP < fNonpurgeableResources.count()) { + currNP < fNonpurgeableResources.count()) { uint32_t tsP = sortedPurgeableResources[currP]->cacheAccess().timestamp(); uint32_t tsNP = fNonpurgeableResources[currNP]->cacheAccess().timestamp(); SkASSERT(tsP != tsNP); @@ -596,10 +596,10 @@ uint32_t GrResourceCache::getNextTimestamp() { // count should be the next timestamp we return. SkASSERT(fTimestamp == SkToU32(count)); - + // The historical timestamps of flushes are now invalid. this->resetFlushTimestamps(); - } + } } return fTimestamp++; } diff --git a/tests/ChecksumTest.cpp b/tests/ChecksumTest.cpp index c095a5ac11..cf9d65c59e 100644 --- a/tests/ChecksumTest.cpp +++ b/tests/ChecksumTest.cpp @@ -18,7 +18,7 @@ static uint32_t murmur_noseed(const uint32_t* d, size_t l) { return SkChecksum:: DEF_TEST(Checksum, r) { // Algorithms to test. They're currently all uint32_t(const uint32_t*, size_t). typedef uint32_t(*algorithmProc)(const uint32_t*, size_t); - const algorithmProc kAlgorithms[] = { &SkChecksum::Compute, &murmur_noseed }; + const algorithmProc kAlgorithms[] = { &murmur_noseed }; // Put 128 random bytes into two identical buffers. Any multiple of 4 will do. const size_t kBytes = SkAlign4(128); |