diff options
| -rw-r--r-- | include/linux/crc32.h | 40 | ||||
| -rw-r--r-- | lib/crc32.c | 81 |
2 files changed, 121 insertions, 0 deletions
diff --git a/include/linux/crc32.h b/include/linux/crc32.h index 68267b64bb98..7d275c4fc011 100644 --- a/include/linux/crc32.h +++ b/include/linux/crc32.h @@ -11,8 +11,48 @@ extern u32 crc32_le(u32 crc, unsigned char const *p, size_t len); extern u32 crc32_be(u32 crc, unsigned char const *p, size_t len); +/** + * crc32_le_combine - Combine two crc32 check values into one. For two + * sequences of bytes, seq1 and seq2 with lengths len1 + * and len2, crc32_le() check values were calculated + * for each, crc1 and crc2. + * + * @crc1: crc32 of the first block + * @crc2: crc32 of the second block + * @len2: length of the second block + * + * Return: The crc32_le() check value of seq1 and seq2 concatenated, + * requiring only crc1, crc2, and len2. Note: If seq_full denotes + * the concatenated memory area of seq1 with seq2, and crc_full + * the crc32_le() value of seq_full, then crc_full == + * crc32_le_combine(crc1, crc2, len2) when crc_full was seeded + * with the same initializer as crc1, and crc2 seed was 0. See + * also crc32_combine_test(). + */ +extern u32 crc32_le_combine(u32 crc1, u32 crc2, size_t len2); + extern u32 __crc32c_le(u32 crc, unsigned char const *p, size_t len); +/** + * __crc32c_le_combine - Combine two crc32c check values into one. For two + * sequences of bytes, seq1 and seq2 with lengths len1 + * and len2, __crc32c_le() check values were calculated + * for each, crc1 and crc2. + * + * @crc1: crc32c of the first block + * @crc2: crc32c of the second block + * @len2: length of the second block + * + * Return: The __crc32c_le() check value of seq1 and seq2 concatenated, + * requiring only crc1, crc2, and len2. Note: If seq_full denotes + * the concatenated memory area of seq1 with seq2, and crc_full + * the __crc32c_le() value of seq_full, then crc_full == + * __crc32c_le_combine(crc1, crc2, len2) when crc_full was + * seeded with the same initializer as crc1, and crc2 seed + * was 0. See also crc32c_combine_test(). + */ +extern u32 __crc32c_le_combine(u32 crc1, u32 crc2, size_t len2); + #define crc32(seed, data, length) crc32_le(seed, (unsigned char const *)(data), length) /* diff --git a/lib/crc32.c b/lib/crc32.c index 429d61ce6aa0..595205cddc30 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 |