svn commit: r1054251 - /subversion/trunk/subversion/libsvn_diff/util.c

[st...@apache.org]

Author: stefan2
Date: Sat Jan  1 16:27:40 2011
New Revision: 1054251

URL: http://svn.apache.org/viewvc?rev=1054251&view=rev
Log:
SVN's Adler-32 implementation is relatively bad at larger buffers.
ZLIB already provides a very good implementation for that and
its next will possible include the new SSE2 implementation for
adler32(). 

See here for details:
http://mail.madler.net/pipermail/zlib-devel_madler.net/2010-April/002001.html

* subversion/libsvn_diff/util.c
  (ADLER_MOD_BLOCK_SIZE): drop because it's no longer needed
  (svn_diff__adler32): make it faster for shorter buffers;
   use zlib for longer ones

Modified:
    subversion/trunk/subversion/libsvn_diff/util.c

Modified: subversion/trunk/subversion/libsvn_diff/util.c
URL: http://svn.apache.org/viewvc/subversion/trunk/subversion/libsvn_diff/util.c?rev=1054251&r1=1054250&r2=1054251&view=diff
==============================================================================
--- subversion/trunk/subversion/libsvn_diff/util.c (original)
+++ subversion/trunk/subversion/libsvn_diff/util.c Sat Jan  1 16:27:40 2011
@@ -24,6 +24,7 @@
 
 #include <apr.h>
 #include <apr_general.h>
+#include <zlib.h>
 
 #include "svn_error.h"
 #include "svn_diff.h"
@@ -47,49 +48,60 @@
 #define ADLER_MOD_BASE 65521
 
 /*
- * "The modulo on unsigned long accumulators can be delayed for 5552 bytes,
- *  so the modulo operation time is negligible."
- */
-#define ADLER_MOD_BLOCK_SIZE 5552
-
-
-/*
  * Start with CHECKSUM and update the checksum by processing a chunk
  * of DATA sized LEN.
  */
 apr_uint32_t
 svn_diff__adler32(apr_uint32_t checksum, const char *data, apr_off_t len)
 {
-  const unsigned char *input = (const unsigned char *)data;
-  apr_uint32_t s1 = checksum & 0xFFFF;
-  apr_uint32_t s2 = checksum >> 16;
-  apr_uint32_t b;
-  apr_size_t blocks = len / ADLER_MOD_BLOCK_SIZE;
-
-  len %= ADLER_MOD_BLOCK_SIZE;
-
-  while (blocks--)
+  /* The actual limit can be set somewhat higher but should
+   * not be lower because the SIMD code would not be used
+   * in that case.
+   *
+   * However, it must be lower than 5552 to make sure our local
+   * implementation does not suffer from overflows.
+   */
+  if (len >= 80)
     {
-      int count = ADLER_MOD_BLOCK_SIZE;
-      while (count--)
+      /* Larger buffers can be effiently handled by Marc Adler's
+       * optimized code. Also, new zlib versions will come with
+       * SIMD code for x86 and x64.
+       */
+      return adler32(checksum, data, len);
+    }
+  else
+    {
+      const unsigned char *input = (const unsigned char *)data;
+      apr_uint32_t s1 = checksum & 0xFFFF;
+      apr_uint32_t s2 = checksum >> 16;
+      apr_uint32_t b;
+
+      /* Some loop unrolling
+       * (approx. one clock tick per byte + 2 ticks loop overhead)
+       */
+      for (; len >= 8; len -= 8, input += 8)
+      {
+        s1 += input[0]; s2 += s1;
+        s1 += input[1]; s2 += s1;
+        s1 += input[2]; s2 += s1;
+        s1 += input[3]; s2 += s1;
+        s1 += input[4]; s2 += s1;
+        s1 += input[5]; s2 += s1;
+        s1 += input[6]; s2 += s1;
+        s1 += input[7]; s2 += s1;
+      }
+
+      /* Adler-32 calculation as a simple two ticks per iteration loop.
+       */
+      while (len--)
         {
           b = *input++;
           s1 += b;
           s2 += s1;
         }
 
-      s1 %= ADLER_MOD_BASE;
-      s2 %= ADLER_MOD_BASE;
-    }
-
-  while (len--)
-    {
-      b = *input++;
-      s1 += b;
-      s2 += s1;
+      return ((s2 % ADLER_MOD_BASE) << 16) | (s1 % ADLER_MOD_BASE);
     }
-
-  return ((s2 % ADLER_MOD_BASE) << 16) | (s1 % ADLER_MOD_BASE);
 }