Adding checksum to SkFlatData to accelerate SkPicture recording.

The checksum triggers an early exit in the mem compare use to search for duplicate flattened objects. Also, call to memcmp was replaced with 64-bit at a time comparison loop.

Review URL: http://codereview.appspot.com/6339046/
BUG=http://code.google.com/p/chromium/issues/detail?id=54079
TEST=Checksum and PictureRecord tests in bench.exe



git-svn-id: http://skia.googlecode.com/svn/trunk@4378 2bbb7eff-a529-9590-31e7-b0007b416f81

2 files changed, 74 insertions, 11 deletions

diff --git a/include/core/SkChecksum.h b/include/core/SkChecksum.h
new file mode 100644
index 0000000000..76f1461ed9
--- /dev/null
+++ b/include/core/SkChecksum.h
@@ -0,0 +1,70 @@
+/*
+ * Copyright 2012 Google Inc.
+ *
+ * Use of this source code is governed by a BSD-style license that can be
+ * found in the LICENSE file.
+ */
+
+#ifndef SkChecksum_DEFINED
+#define SkChecksum_DEFINED
+
+#include "SkTypes.h"
+
+#if !defined(SK_PREFER_32BIT_CHECKSUM)
+#define SK_PREFER_32BIT_CHECKSUM 0
+#endif
+
+enum {
+    ChecksumRotateBits = 17
+};
+
+#define SkCHECKSUM_MASH(CHECKSUM, NEW_CHUNK) \
+    CHECKSUM = (((CHECKSUM) >> (sizeof(CHECKSUM)*8 - ChecksumRotateBits)) + \
+        ((CHECKSUM) << ChecksumRotateBits)) ^ (NEW_CHUNK);
+
+
+/**
+ *  Compute a 64-bit checksum for a given data block
+ *
+ *  @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 8.
+ *  @return checksum result
+ */
+inline uint64_t SkComputeChecksum64(const uint64_t* ptr, size_t size) {
+    SkASSERT(SkIsAlign8(size));
+    // Strict 8-byte alignment is not required on ptr. On current
+    // CPUs there is no measurable performance difference between 32-bit
+    // and 64-bit aligned access to uint64_t data
+    SkASSERT(SkIsAlign4((intptr_t)ptr));
+
+    const uint64_t* stop = ptr + (size >> 3);
+    uint64_t result = 0;
+    while (ptr < stop) {
+        SkCHECKSUM_MASH(result, *ptr);
+        ptr++;
+    }
+    return result;
+}
+
+/**
+ *  Compute a 32-bit checksum for a given data block
+ *
+ *  @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
+ */
+inline uint32_t SkComputeChecksum32(const uint32_t* ptr, size_t size) {
+    SkASSERT(SkIsAlign4(size));
+    SkASSERT(SkIsAlign4((intptr_t)ptr));
+
+    const uint32_t* stop = ptr + (size >> 2);
+    uint32_t result = 0;
+    while (ptr < stop) {
+        SkCHECKSUM_MASH(result, *ptr);
+        ptr++;
+    }
+    return result;
+}
+#endif
\ No newline at end of file
diff --git a/include/core/SkDescriptor.h b/include/core/SkDescriptor.h
index b97b75f949..00bc9aa924 100644
--- a/include/core/SkDescriptor.h
+++ b/include/core/SkDescriptor.h
@@ -10,6 +10,7 @@
 #ifndef SkDescriptor_DEFINED
 #define SkDescriptor_DEFINED
 
+#include "SkChecksum.h"
 #include "SkTypes.h"
 
 class SkDescriptor : SkNoncopyable {
@@ -131,17 +132,9 @@ private:
 
     static uint32_t ComputeChecksum(const SkDescriptor* desc)
     {
-        const uint32_t*  ptr = (const uint32_t*)desc + 1; // skip the checksum field
-        const uint32_t*  stop = (const uint32_t*)((const char*)desc + desc->fLength);
-        uint32_t         sum = 0;
-
-        SkASSERT(ptr < stop);
-        do {
-            sum = (sum << 1) | (sum >> 31);
-            sum ^= *ptr++;
-        } while (ptr < stop);
-
-        return sum;
+        const uint32_t* ptr = (const uint32_t*)desc + 1; // skip the checksum field
+        const size_t len = desc->fLength-sizeof(uint32_t);
+        return SkComputeChecksum32(ptr, len);
     }
     
     // private so no one can create one except our factories