Add crc32_combine_gen() and crc32_combine_op() for fast combines.

When the same len2 is used repeatedly, it is faster to use
crc32_combine_gen() to generate an operator, that is then used to
combine CRCs with crc32_combine_op().

5 files changed, 108 insertions, 0 deletions

diff --git a/crc32.c b/crc32.c
index fb64b91..95080b3 100644
--- a/crc32.c
+++ b/crc32.c
@@ -41,6 +41,7 @@
 #define GF2_DIM 32      /* dimension of GF(2) vectors (length of CRC) */
 static uint32_t gf2_matrix_times(const uint32_t *mat, uint32_t vec);
 static uint32_t crc32_combine_(uint32_t crc1, uint32_t crc2, z_off64_t len2);
+static void crc32_combine_gen_(uint32_t *op, z_off64_t len2);
 
 /* ========================================================================= */
 static uint32_t gf2_matrix_times(const uint32_t *mat, uint32_t vec) {
@@ -410,3 +411,67 @@ ZLIB_INTERNAL void copy_with_crc(PREFIX3(stream) *strm, unsigned char *dst, unsi
 }
 #endif
 
+/* ========================================================================= */
+static void crc32_combine_gen_(uint32_t *op, z_off64_t len2)
+{
+    uint32_t row;
+    int j;
+    unsigned i;
+
+#ifdef DYNAMIC_CRC_TABLE
+    if (crc_table_empty)
+        make_crc_table();
+#endif /* DYNAMIC_CRC_TABLE */
+
+    /* if len2 is zero or negative, return the identity matrix */
+    if (len2 <= 0) {
+        row = 1;
+        for (j = 0; j < GF2_DIM; j++) {
+            op[j] = row;
+            row <<= 1;
+        }
+        return;
+    }
+
+    /* at least one bit in len2 is set -- find it, and copy the operator
+       corresponding to that position into op */
+    i = 0;
+    for (;;) {
+        if (len2 & 1) {
+            for (j = 0; j < GF2_DIM; j++)
+                op[j] = crc_comb[i][j];
+            break;
+        }
+        len2 >>= 1;
+        i = (i + 1) % GF2_DIM;
+    }
+
+    /* for each remaining bit set in len2 (if any), multiply op by the operator
+       corresponding to that position */
+    for (;;) {
+        len2 >>= 1;
+        i = (i + 1) % GF2_DIM;
+        if (len2 == 0)
+            break;
+        if (len2 & 1)
+            for (j = 0; j < GF2_DIM; j++)
+                op[j] = gf2_matrix_times(crc_comb[i], op[j]);
+    }
+}
+
+/* ========================================================================= */
+void ZEXPORT PREFIX(crc32_combine_gen)(uint32_t *op, z_off_t len2)
+{
+    crc32_combine_gen_(op, len2);
+}
+
+void ZEXPORT PREFIX(crc32_combine_gen64)(uint32_t *op, z_off64_t len2)
+{
+    crc32_combine_gen_(op, len2);
+}
+
+/* ========================================================================= */
+uint32_t ZEXPORT PREFIX(crc32_combine_op)(uint32_t crc1, uint32_t crc2, const uint32_t *op)
+{
+    return gf2_matrix_times(op, crc1) ^ crc2;
+}
diff --git a/zlib-ng.h b/zlib-ng.h
index 6010bba..7f1ce99 100644
--- a/zlib-ng.h
+++ b/zlib-ng.h
@@ -1701,6 +1701,21 @@ ZEXTERN uint32_t ZEXPORT zng_crc32_combine(uint32_t crc1, uint32_t crc2, z_off64
    len2.
 */
 
+/*
+ZEXTERN void ZEXPORT zng_crc32_combine_gen(uint32_t op[32], z_off_t len2);
+
+     Generate the operator op corresponding to length len2, to be used with
+   crc32_combine_op(). op must have room for 32 uint32_t values. (32 is the
+   number of bits in the CRC.)
+*/
+
+ZEXTERN uint32_t ZEXPORT zng_crc32_combine_op(uint32_t crc1, uint32_t crc2,
+                                              const uint32_t *op);
+/*
+     Give the same result as crc32_combine(), using op in place of len2. op is
+   is generated from len2 by crc32_combine_gen(). This will be faster than
+   crc32_combine() if the generated op is used many times.
+*/
 
                         /* various hacks, don't look :) */
 
@@ -1782,18 +1797,22 @@ ZEXTERN int ZEXPORT zng_gzgetc_(gzFile file);  /* backward compatibility */
 #ifdef Z_LARGE64
    ZEXTERN uint32_t ZEXPORT zng_adler32_combine64(uint32_t, uint32_t, z_off64_t);
    ZEXTERN uint32_t ZEXPORT zng_crc32_combine64(uint32_t, uint32_t, z_off64_t);
+   ZEXTERN void ZEXPORT zng_crc32_combine_gen64(uint32_t *op, z_off64_t);
 #endif
 
 #if !defined(ZLIB_INTERNAL) && defined(Z_WANT64)
 #    define zng_adler32_combine zng_adler32_combine64
 #    define zng_crc32_combine zng_crc32_combine64
+#    define zng_crc32_combine_gen zng_crc32_combine_gen64
 #  ifndef Z_LARGE64
      ZEXTERN uint32_t ZEXPORT zng_adler32_combine64(uint32_t, uint32_t, z_off_t);
      ZEXTERN uint32_t ZEXPORT zng_crc32_combine64(uint32_t, uint32_t, z_off_t);
+     ZEXTERN void ZEXPORT zng_crc32_combine_gen64(uint32_t *op, z_off64_t);
 #  endif
 #else
    ZEXTERN uint32_t ZEXPORT zng_adler32_combine(uint32_t, uint32_t, z_off_t);
    ZEXTERN uint32_t ZEXPORT zng_crc32_combine(uint32_t, uint32_t, z_off_t);
+   ZEXTERN void ZEXPORT zng_crc32_combine_gen(uint32_t *op, z_off_t);
 #endif
 
 
diff --git a/zlib-ng.map b/zlib-ng.map
index 32fe5cb..107d069 100644
--- a/zlib-ng.map
+++ b/zlib-ng.map
@@ -11,6 +11,8 @@ ZLIB_NG_1.9.9 {
     zng_crc32;
     zng_crc32_combine;
     zng_crc32_combine64;
+    zng_crc32_combine_gen;
+    zng_crc32_combine_op;
     zng_crc32_z;
     zng_deflate;
     zng_deflateBound;
diff --git a/zlib.h b/zlib.h
index af1ab73..49da9ae 100644
--- a/zlib.h
+++ b/zlib.h
@@ -1710,6 +1710,22 @@ ZEXTERN uint32_t ZEXPORT crc32_combine(uint32_t crc1, uint32_t crc2, z_off64_t l
    len2.
 */
 
+/*
+ZEXTERN void ZEXPORT crc32_combine_gen(uint32_t op[32], z_off_t len2);
+
+     Generate the operator op corresponding to length len2, to be used with
+   crc32_combine_op(). op must have room for 32 z_crc_t values. (32 is the
+   number of bits in the CRC.)
+*/
+
+ZEXTERN uint32_t ZEXPORT crc32_combine_op(uint32_t crc1, uint32_t crc2,
+                                          const uint32_t *op);
+/*
+     Give the same result as crc32_combine(), using op in place of len2. op is
+   is generated from len2 by crc32_combine_gen(). This will be faster than
+   crc32_combine() if the generated op is used many times.
+*/
+
 
                         /* various hacks, don't look :) */
 
@@ -1789,18 +1805,22 @@ ZEXTERN int ZEXPORT gzgetc_(gzFile file);  /* backward compatibility */
 #ifdef Z_LARGE64
    ZEXTERN uint32_t ZEXPORT adler32_combine64(uint32_t, uint32_t, z_off64_t);
    ZEXTERN uint32_t ZEXPORT crc32_combine64(uint32_t, uint32_t, z_off64_t);
+   ZEXTERN void ZEXPORT crc32_combine_gen64(uint32_t *op, z_off64_t);
 #endif
 
 #if !defined(ZLIB_INTERNAL) && defined(Z_WANT64)
 #    define adler32_combine adler32_combine64
 #    define crc32_combine crc32_combine64
+#    define crc32_combine_gen crc32_combine_gen64
 #  ifndef Z_LARGE64
      ZEXTERN uint32_t ZEXPORT adler32_combine64(uint32_t, uint32_t, z_off_t);
      ZEXTERN uint32_t ZEXPORT crc32_combine64(uint32_t, uint32_t, z_off_t);
+     ZEXTERN void ZEXPORT crc32_combine_gen64(uint32_t *op, z_off64_t);
 #  endif
 #else
    ZEXTERN uint32_t ZEXPORT adler32_combine(uint32_t, uint32_t, z_off_t);
    ZEXTERN uint32_t ZEXPORT crc32_combine(uint32_t, uint32_t, z_off_t);
+   ZEXTERN void ZEXPORT crc32_combine_gen(uint32_t *op, z_off_t);
 #endif
 
 
diff --git a/zlib.map b/zlib.map
index 82ce98c..28436d4 100644
--- a/zlib.map
+++ b/zlib.map
@@ -91,4 +91,6 @@ ZLIB_1.2.9 {
     deflateGetDictionary;
     adler32_z;
     crc32_z;
+    crc32_combine_gen;
+    crc32_combine_op;
 } ZLIB_1.2.7.1;