Add SkChecksum::Murmur3.
BUG=
R=reed@google.com
Author: mtklein@google.com
Review URL: https://chromiumcodereview.appspot.com/19500020
git-svn-id: http://skia.googlecode.com/svn/trunk@10292 2bbb7eff-a529-9590-31e7-b0007b416f81
diff --git a/bench/ChecksumBench.cpp b/bench/ChecksumBench.cpp
index d2497d7..b125aa4 100644
--- a/bench/ChecksumBench.cpp
+++ b/bench/ChecksumBench.cpp
@@ -15,7 +15,8 @@
enum ChecksumType {
kChecksum_ChecksumType,
kMD5_ChecksumType,
- kSHA1_ChecksumType
+ kSHA1_ChecksumType,
+ kMurmur3_ChecksumType,
};
class ComputeChecksumBench : public SkBenchmark {
@@ -42,6 +43,8 @@
case kChecksum_ChecksumType: return "compute_checksum";
case kMD5_ChecksumType: return "compute_md5";
case kSHA1_ChecksumType: return "compute_sha1";
+ case kMurmur3_ChecksumType: return "compute_murmur3";
+
default: SK_CRASH(); return "";
}
}
@@ -70,6 +73,12 @@
sha1.finish(digest);
}
} break;
+ case kMurmur3_ChecksumType: {
+ for (int i = 0; i < N; i++) {
+ volatile uint32_t result = SkChecksum::Murmur3(fData, sizeof(fData));
+ sk_ignore_unused_variable(result);
+ }
+ }break;
}
}
@@ -83,7 +92,11 @@
static SkBenchmark* Fact0(void* p) { return new ComputeChecksumBench(p, kChecksum_ChecksumType); }
static SkBenchmark* Fact1(void* p) { return new ComputeChecksumBench(p, kMD5_ChecksumType); }
static SkBenchmark* Fact2(void* p) { return new ComputeChecksumBench(p, kSHA1_ChecksumType); }
+static SkBenchmark* Fact3(void* p) { return new ComputeChecksumBench(p, kMurmur3_ChecksumType); }
+
static BenchRegistry gReg0(Fact0);
static BenchRegistry gReg1(Fact1);
static BenchRegistry gReg2(Fact2);
+static BenchRegistry gReg3(Fact3);
+
diff --git a/include/core/SkChecksum.h b/include/core/SkChecksum.h
index 287109f..bf3228f 100644
--- a/include/core/SkChecksum.h
+++ b/include/core/SkChecksum.h
@@ -36,6 +36,42 @@
}
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. Must be 32-bit aligned.
+ * @param size Size of the data block in bytes. Must be a multiple of 4.
+ * @param seed Initial hash seed. (optional)
+ * @return hash result
+ */
+ static uint32_t Murmur3(const uint32_t* data, size_t bytes, uint32_t seed=0) {
+ SkASSERT(SkIsAlign4(bytes));
+ const size_t words = bytes/4;
+
+ uint32_t hash = seed;
+ for (size_t i = 0; i < words; i++) {
+ uint32_t k = data[i];
+ k *= 0xcc9e2d51;
+ k = (k << 15) | (k >> 17);
+ k *= 0x1b873593;
+
+ hash ^= k;
+ hash = (hash << 13) | (hash >> 19);
+ hash *= 5;
+ hash += 0xe6546b64;
+ }
+ hash ^= bytes;
+ hash ^= hash >> 16;
+ hash *= 0x85ebca6b;
+ hash ^= hash >> 13;
+ hash *= 0xc2b2ae35;
+ hash ^= hash >> 16;
+ return hash;
+ }
+
/**
* Compute a 32-bit checksum for a given data block
*
diff --git a/tests/ChecksumTest.cpp b/tests/ChecksumTest.cpp
index ee33d32..c2f2be2 100644
--- a/tests/ChecksumTest.cpp
+++ b/tests/ChecksumTest.cpp
@@ -24,7 +24,8 @@
}
private:
enum Algorithm {
- kSkChecksum
+ kSkChecksum,
+ kMurmur3,
};
// Call Compute(data, size) on the appropriate checksum algorithm,
@@ -38,6 +39,13 @@
REPORTER_ASSERT_MESSAGE(fReporter, SkIsAlign4(size),
"test data size is not 32-bit aligned");
return SkChecksum::Compute(reinterpret_cast<const uint32_t *>(data), size);
+ case kMurmur3:
+ REPORTER_ASSERT_MESSAGE(fReporter,
+ reinterpret_cast<uintptr_t>(data) % 4 == 0,
+ "test data pointer is not 32-bit aligned");
+ REPORTER_ASSERT_MESSAGE(fReporter, SkIsAlign4(size),
+ "test data size is not 32-bit aligned");
+ return SkChecksum::Murmur3(reinterpret_cast<const uint32_t *>(data), size);
default:
SkString message("fWhichAlgorithm has unknown value ");
message.appendf("%d", fWhichAlgorithm);
@@ -98,25 +106,32 @@
}
void RunTest() {
- // Test self-consistency of checksum algorithms.
- fWhichAlgorithm = kSkChecksum;
- TestChecksumSelfConsistency(128);
+ const Algorithm algorithms[] = { kSkChecksum, kMurmur3 };
+ for (size_t i = 0; i < SK_ARRAY_COUNT(algorithms); i++) {
+ fWhichAlgorithm = algorithms[i];
- // Test checksum results that should be consistent across
- // versions and platforms.
- fWhichAlgorithm = kSkChecksum;
- REPORTER_ASSERT(fReporter, ComputeChecksum(NULL, 0) == 0);
+ // Test self-consistency of checksum algorithms.
+ TestChecksumSelfConsistency(128);
- // TODO: note the weakness exposed by these collisions...
- // We need to improve the SkChecksum algorithm.
- // We would prefer that these asserts FAIL!
- // Filed as https://code.google.com/p/skia/issues/detail?id=981
- // ('SkChecksum algorithm allows for way too many collisions')
- fWhichAlgorithm = kSkChecksum;
- REPORTER_ASSERT(fReporter,
- GetTestDataChecksum(128) == GetTestDataChecksum(256));
- REPORTER_ASSERT(fReporter,
- GetTestDataChecksum(132) == GetTestDataChecksum(260));
+ // Test checksum results that should be consistent across
+ // versions and platforms.
+ REPORTER_ASSERT(fReporter, ComputeChecksum(NULL, 0) == 0);
+
+ const bool colision1 = GetTestDataChecksum(128) == GetTestDataChecksum(256);
+ const bool colision2 = GetTestDataChecksum(132) == GetTestDataChecksum(260);
+ if (fWhichAlgorithm == kSkChecksum) {
+ // TODO: note the weakness exposed by these collisions...
+ // We need to improve the SkChecksum algorithm.
+ // We would prefer that these asserts FAIL!
+ // Filed as https://code.google.com/p/skia/issues/detail?id=981
+ // ('SkChecksum algorithm allows for way too many collisions')
+ REPORTER_ASSERT(fReporter, colision1);
+ REPORTER_ASSERT(fReporter, colision2);
+ } else {
+ REPORTER_ASSERT(fReporter, !colision1);
+ REPORTER_ASSERT(fReporter, !colision2);
+ }
+ }
}
Reporter* fReporter;