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

3 files changed, 85 insertions, 21 deletions

diff --git a/bench/ChecksumBench.cpp b/bench/ChecksumBench.cpp
index d2497d7f16..b125aa4d1f 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 @@ protected:
             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 @@ protected:
                     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 @@ private:
 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 287109fef9..bf3228f91d 100644
--- a/include/core/SkChecksum.h
+++ b/include/core/SkChecksum.h
@@ -36,6 +36,42 @@ private:
     }
 
 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 ee33d32acd..c2f2be2ae6 100644
--- a/tests/ChecksumTest.cpp
+++ b/tests/ChecksumTest.cpp
@@ -24,7 +24,8 @@ namespace skiatest {
         }
     private:
         enum Algorithm {
-            kSkChecksum
+            kSkChecksum,
+            kMurmur3,
         };
 
         // Call Compute(data, size) on the appropriate checksum algorithm,
@@ -38,6 +39,13 @@ namespace skiatest {
                 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 @@ namespace skiatest {
         }
 
         void RunTest() {
-            // Test self-consistency of checksum algorithms.
-            fWhichAlgorithm = kSkChecksum;
-            TestChecksumSelfConsistency(128);
-
-            // Test checksum results that should be consistent across
-            // versions and platforms.
-            fWhichAlgorithm = kSkChecksum;
-            REPORTER_ASSERT(fReporter, ComputeChecksum(NULL, 0) == 0);
-
-            // 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));
+            const Algorithm algorithms[] = { kSkChecksum, kMurmur3 };
+            for (size_t i = 0; i < SK_ARRAY_COUNT(algorithms); i++) {
+                fWhichAlgorithm = algorithms[i];
+
+                // Test self-consistency of checksum algorithms.
+                TestChecksumSelfConsistency(128);
+
+                // 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;