lib: crc32: add functionality to combine two crc32{, c}s in GF(2)

[~andy/linux] / lib / crc32.c

diff --git a/lib/crc32.c b/lib/crc32.c
index 429d61ce6aa09ef1b14b04c1b8488d15c37c89d2..595205cddc307d01dc6bc78edba1417b897b4eb6 100644 (file)
--- a/lib/crc32.c
+++ b/lib/crc32.c
@@ -49,6 +49,30 @@ MODULE_AUTHOR("Matt Domsch <Matt_Domsch@dell.com>");
 MODULE_DESCRIPTION("Various CRC32 calculations");
 MODULE_LICENSE("GPL");
 
+#define GF2_DIM                32
+
+static u32 gf2_matrix_times(u32 *mat, u32 vec)
+{
+       u32 sum = 0;
+
+       while (vec) {
+               if (vec & 1)
+                       sum ^= *mat;
+               vec >>= 1;
+               mat++;
+       }
+
+       return sum;
+}
+
+static void gf2_matrix_square(u32 *square, u32 *mat)
+{
+       int i;
+
+       for (i = 0; i < GF2_DIM; i++)
+               square[i] = gf2_matrix_times(mat, mat[i]);
+}
+
 #if CRC_LE_BITS > 8 || CRC_BE_BITS > 8
 
 /* implements slicing-by-4 or slicing-by-8 algorithm */
@@ -130,6 +154,52 @@ crc32_body(u32 crc, unsigned char const *buf, size_t len, const u32 (*tab)[256])
 }
 #endif
 
+/* For conditions of distribution and use, see copyright notice in zlib.h */
+static u32 crc32_generic_combine(u32 crc1, u32 crc2, size_t len2,
+                                u32 polynomial)
+{
+       u32 even[GF2_DIM]; /* Even-power-of-two zeros operator */
+       u32 odd[GF2_DIM];  /* Odd-power-of-two zeros operator  */
+       u32 row;
+       int i;
+
+       if (len2 <= 0)
+               return crc1;
+
+       /* Put operator for one zero bit in odd */
+       odd[0] = polynomial;
+       row = 1;
+       for (i = 1; i < GF2_DIM; i++) {
+               odd[i] = row;
+               row <<= 1;
+       }
+
+       gf2_matrix_square(even, odd); /* Put operator for two zero bits in even */
+       gf2_matrix_square(odd, even); /* Put operator for four zero bits in odd */
+
+       /* Apply len2 zeros to crc1 (first square will put the operator for one
+        * zero byte, eight zero bits, in even).
+        */
+       do {
+               /* Apply zeros operator for this bit of len2 */
+               gf2_matrix_square(even, odd);
+               if (len2 & 1)
+                       crc1 = gf2_matrix_times(even, crc1);
+               len2 >>= 1;
+               /* If no more bits set, then done */
+               if (len2 == 0)
+                       break;
+               /* Another iteration of the loop with odd and even swapped */
+               gf2_matrix_square(odd, even);
+               if (len2 & 1)
+                       crc1 = gf2_matrix_times(odd, crc1);
+               len2 >>= 1;
+       } while (len2 != 0);
+
+       crc1 ^= crc2;
+       return crc1;
+}
+
 /**
  * crc32_le_generic() - Calculate bitwise little-endian Ethernet AUTODIN II
  *                     CRC32/CRC32C
@@ -200,8 +270,19 @@ u32 __pure __crc32c_le(u32 crc, unsigned char const *p, size_t len)
                        (const u32 (*)[256])crc32ctable_le, CRC32C_POLY_LE);
 }
 #endif
+u32 __pure crc32_le_combine(u32 crc1, u32 crc2, size_t len2)
+{
+       return crc32_generic_combine(crc1, crc2, len2, CRCPOLY_LE);
+}
+
+u32 __pure __crc32c_le_combine(u32 crc1, u32 crc2, size_t len2)
+{
+       return crc32_generic_combine(crc1, crc2, len2, CRC32C_POLY_LE);
+}
 EXPORT_SYMBOL(crc32_le);
+EXPORT_SYMBOL(crc32_le_combine);
 EXPORT_SYMBOL(__crc32c_le);
+EXPORT_SYMBOL(__crc32c_le_combine);
 
 /**
  * crc32_be_generic() - Calculate bitwise big-endian Ethernet AUTODIN II CRC32