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

This patch adds a combinator to merge two or more crc32{,c}s
into a new one. This is useful for checksum computations of
fragmented skbs that use crc32/crc32c as checksums.

The arithmetics for combining both in the GF(2) was taken and
slightly modified from zlib. Only passing two crcs is insufficient
as two crcs and the length of the second piece is needed for
merging. The code is made generic, so that only polynomials
need to be passed for crc32_le resp. crc32c_le.

Signed-off-by: Daniel Borkmann <dborkman@redhat.com>
Cc: linux-kernel@vger.kernel.org
Signed-off-by: David S. Miller <davem@davemloft.net>

1 files changed, 81 insertions, 0 deletions

diff --git a/lib/crc32.c b/lib/crc32.c
index 429d61c..595205c 100644
--- 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