From 60e58d5c9d8d698600e8ccb44b5a13cf99d0d90f Mon Sep 17 00:00:00 2001 From: Bob Pearson Date: Fri, 23 Mar 2012 15:02:22 -0700 Subject: crc32: miscellaneous cleanups Misc cleanup of lib/crc32.c and related files. - remove unnecessary header files. - straighten out some convoluted ifdef's - rewrite some references to 2 dimensional arrays as 1 dimensional arrays to make them correct. I.e. replace tab[i] with tab[0][i]. - a few trivial whitespace changes - fix a warning in gen_crc32tables.c caused by a mismatch in the type of the pointer passed to output table. Since the table is only used at kernel compile time, it is simpler to make the table big enough to hold the largest column size used. One cannot make the column size smaller in output_table because it has to be used by both the le and be tables and they can have different column sizes. [djwong@us.ibm.com: Minor changelog tweaks] Signed-off-by: Bob Pearson Signed-off-by: Darrick J. Wong Signed-off-by: Andrew Morton Signed-off-by: Linus Torvalds --- lib/gen_crc32table.c | 6 +++--- 1 file changed, 3 insertions(+), 3 deletions(-) (limited to 'lib/gen_crc32table.c') diff --git a/lib/gen_crc32table.c b/lib/gen_crc32table.c index 85d0e412a04..eced7696eb7 100644 --- a/lib/gen_crc32table.c +++ b/lib/gen_crc32table.c @@ -7,8 +7,8 @@ #define LE_TABLE_SIZE (1 << CRC_LE_BITS) #define BE_TABLE_SIZE (1 << CRC_BE_BITS) -static uint32_t crc32table_le[4][LE_TABLE_SIZE]; -static uint32_t crc32table_be[4][BE_TABLE_SIZE]; +static uint32_t crc32table_le[4][256]; +static uint32_t crc32table_be[4][256]; /** * crc32init_le() - allocate and initialize LE table data @@ -62,7 +62,7 @@ static void crc32init_be(void) } } -static void output_table(uint32_t table[4][256], int len, char *trans) +static void output_table(uint32_t (*table)[256], int len, char *trans) { int i, j; -- cgit v1.2.3-70-g09d2 From 9a1dbf6a29694c9d81b498019f103aee0f8b5b6c Mon Sep 17 00:00:00 2001 From: Bob Pearson Date: Fri, 23 Mar 2012 15:02:23 -0700 Subject: crc32: make CRC_*_BITS definition correspond to actual bit counts crc32.c provides a choice of one of several algorithms for computing the LSB and LSB versions of the CRC32 checksum based on the parameters CRC_LE_BITS and CRC_BE_BITS. In the original version the values 1, 2, 4 and 8 respectively selected versions of the alrogithm that computed the crc 1, 2, 4 and 32 bits as a time. This patch series adds a new version that computes the CRC 64 bits at a time. To make things easier to understand the parameter has been reinterpreted to actually stand for the number of bits processed in each step of the algorithm so that the old value 8 has been replaced with the value 32. This also allows us to add in a widely used crc algorithm that computes the crc 8 bits at a time called the Sarwate algorithm. [djwong@us.ibm.com: Minor changelog tweaks] Signed-off-by: Bob Pearson Signed-off-by: Darrick J. Wong Signed-off-by: Andrew Morton Signed-off-by: Linus Torvalds --- lib/crc32.c | 17 ++++++++++++++--- lib/crc32defs.h | 18 ++++++++++-------- lib/gen_crc32table.c | 11 ++++++++++- 3 files changed, 34 insertions(+), 12 deletions(-) (limited to 'lib/gen_crc32table.c') diff --git a/lib/crc32.c b/lib/crc32.c index 7394288c045..5971f2ad46d 100644 --- a/lib/crc32.c +++ b/lib/crc32.c @@ -27,13 +27,13 @@ #include #include "crc32defs.h" -#if CRC_LE_BITS == 8 +#if CRC_LE_BITS > 8 # define tole(x) ((__force u32) __constant_cpu_to_le32(x)) #else # define tole(x) (x) #endif -#if CRC_BE_BITS == 8 +#if CRC_BE_BITS > 8 # define tobe(x) ((__force u32) __constant_cpu_to_be32(x)) #else # define tobe(x) (x) @@ -45,7 +45,7 @@ MODULE_AUTHOR("Matt Domsch "); MODULE_DESCRIPTION("Ethernet CRC32 calculations"); MODULE_LICENSE("GPL"); -#if CRC_LE_BITS == 8 || CRC_BE_BITS == 8 +#if CRC_LE_BITS > 8 || CRC_BE_BITS > 8 static inline u32 crc32_body(u32 crc, unsigned char const *buf, size_t len, const u32 (*tab)[256]) @@ -126,6 +126,12 @@ u32 __pure crc32_le(u32 crc, unsigned char const *p, size_t len) crc = (crc >> 4) ^ crc32table_le[0][crc & 15]; } # elif CRC_LE_BITS == 8 + /* aka Sarwate algorithm */ + while (len--) { + crc ^= *p++; + crc = (crc >> 8) ^ crc32table_le[0][crc & 255]; + } +# else const u32 (*tab)[] = crc32table_le; crc = (__force u32) __cpu_to_le32(crc); @@ -169,6 +175,11 @@ u32 __pure crc32_be(u32 crc, unsigned char const *p, size_t len) crc = (crc << 4) ^ crc32table_be[0][crc >> 28]; } # elif CRC_BE_BITS == 8 + while (len--) { + crc ^= *p++ << 24; + crc = (crc << 8) ^ crc32table_be[0][crc >> 24]; + } +# else const u32 (*tab)[] = crc32table_be; crc = (__force u32) __cpu_to_be32(crc); diff --git a/lib/crc32defs.h b/lib/crc32defs.h index f5a54017657..daa3a5e85f6 100644 --- a/lib/crc32defs.h +++ b/lib/crc32defs.h @@ -6,27 +6,29 @@ #define CRCPOLY_LE 0xedb88320 #define CRCPOLY_BE 0x04c11db7 -/* How many bits at a time to use. Requires a table of 4< 8 || CRC_LE_BITS < 1 || CRC_LE_BITS & CRC_LE_BITS-1 -# error CRC_LE_BITS must be a power of 2 between 1 and 8 +#if CRC_LE_BITS > 32 || CRC_LE_BITS < 1 || CRC_LE_BITS == 16 || \ + CRC_LE_BITS & CRC_LE_BITS-1 +# error "CRC_LE_BITS must be one of {1, 2, 4, 8, 32}" #endif /* * Big-endian CRC computation. Used with serial bit streams sent * msbit-first. Be sure to use cpu_to_be32() to append the computed CRC. */ -#if CRC_BE_BITS > 8 || CRC_BE_BITS < 1 || CRC_BE_BITS & CRC_BE_BITS-1 -# error CRC_BE_BITS must be a power of 2 between 1 and 8 +#if CRC_BE_BITS > 32 || CRC_BE_BITS < 1 || CRC_BE_BITS == 16 || \ + CRC_BE_BITS & CRC_BE_BITS-1 +# error "CRC_BE_BITS must be one of {1, 2, 4, 8, 32}" #endif diff --git a/lib/gen_crc32table.c b/lib/gen_crc32table.c index eced7696eb7..99ac744848f 100644 --- a/lib/gen_crc32table.c +++ b/lib/gen_crc32table.c @@ -4,8 +4,17 @@ #define ENTRIES_PER_LINE 4 +#if CRC_LE_BITS <= 8 #define LE_TABLE_SIZE (1 << CRC_LE_BITS) +#else +#define LE_TABLE_SIZE 256 +#endif + +#if CRC_BE_BITS <= 8 #define BE_TABLE_SIZE (1 << CRC_BE_BITS) +#else +#define BE_TABLE_SIZE 256 +#endif static uint32_t crc32table_le[4][256]; static uint32_t crc32table_be[4][256]; @@ -24,7 +33,7 @@ static void crc32init_le(void) crc32table_le[0][0] = 0; - for (i = 1 << (CRC_LE_BITS - 1); i; i >>= 1) { + for (i = LE_TABLE_SIZE >> 1; i; i >>= 1) { crc = (crc >> 1) ^ ((crc & 1) ? CRCPOLY_LE : 0); for (j = 0; j < LE_TABLE_SIZE; j += 2 * i) crc32table_le[0][i + j] = crc ^ crc32table_le[0][j]; -- cgit v1.2.3-70-g09d2 From 324eb0f17d9dcead3c60c133aa244f6b3631fec9 Mon Sep 17 00:00:00 2001 From: Bob Pearson Date: Fri, 23 Mar 2012 15:02:24 -0700 Subject: crc32: add slice-by-8 algorithm to existing code Add slicing-by-8 algorithm to the existing slicing-by-4 algorithm. This consists of: - extend largest BITS size from 32 to 64 - extend tables from tab[4][256] to up to tab[8][256] - Add code for inner loop. [djwong@us.ibm.com: Minor changelog tweaks] Signed-off-by: Bob Pearson Signed-off-by: Darrick J. Wong Signed-off-by: Andrew Morton Signed-off-by: Linus Torvalds --- lib/crc32.c | 38 +++++++++++++++++++++++++++----------- lib/crc32defs.h | 29 +++++++++++++++++++++-------- lib/gen_crc32table.c | 43 +++++++++++++++++++++++++++---------------- 3 files changed, 75 insertions(+), 35 deletions(-) (limited to 'lib/gen_crc32table.c') diff --git a/lib/crc32.c b/lib/crc32.c index 5971f2ad46d..826e16352e0 100644 --- a/lib/crc32.c +++ b/lib/crc32.c @@ -47,25 +47,28 @@ MODULE_LICENSE("GPL"); #if CRC_LE_BITS > 8 || CRC_BE_BITS > 8 +/* implements slicing-by-4 or slicing-by-8 algorithm */ static inline u32 crc32_body(u32 crc, unsigned char const *buf, size_t len, const u32 (*tab)[256]) { # ifdef __LITTLE_ENDIAN # define DO_CRC(x) crc = t0[(crc ^ (x)) & 255] ^ (crc >> 8) -# define DO_CRC4 crc = t3[(crc) & 255] ^ \ - t2[(crc >> 8) & 255] ^ \ - t1[(crc >> 16) & 255] ^ \ - t0[(crc >> 24) & 255] +# define DO_CRC4 (t3[(q) & 255] ^ t2[(q >> 8) & 255] ^ \ + t1[(q >> 16) & 255] ^ t0[(q >> 24) & 255]) +# define DO_CRC8 (t7[(q) & 255] ^ t6[(q >> 8) & 255] ^ \ + t5[(q >> 16) & 255] ^ t4[(q >> 24) & 255]) # else # define DO_CRC(x) crc = t0[((crc >> 24) ^ (x)) & 255] ^ (crc << 8) -# define DO_CRC4 crc = t0[(crc) & 255] ^ \ - t1[(crc >> 8) & 255] ^ \ - t2[(crc >> 16) & 255] ^ \ - t3[(crc >> 24) & 255] +# define DO_CRC4 (t0[(q) & 255] ^ t1[(q >> 8) & 255] ^ \ + t2[(q >> 16) & 255] ^ t3[(q >> 24) & 255]) +# define DO_CRC8 (t4[(q) & 255] ^ t5[(q >> 8) & 255] ^ \ + t6[(q >> 16) & 255] ^ t7[(q >> 24) & 255]) # endif const u32 *b; size_t rem_len; const u32 *t0=tab[0], *t1=tab[1], *t2=tab[2], *t3=tab[3]; + const u32 *t4 = tab[4], *t5 = tab[5], *t6 = tab[6], *t7 = tab[7]; + u32 q; /* Align it */ if (unlikely((long)buf & 3 && len)) { @@ -73,13 +76,25 @@ crc32_body(u32 crc, unsigned char const *buf, size_t len, const u32 (*tab)[256]) DO_CRC(*buf++); } while ((--len) && ((long)buf)&3); } + +# if CRC_LE_BITS == 32 rem_len = len & 3; - /* load data 32 bits wide, xor data 32 bits wide. */ len = len >> 2; +# else + rem_len = len & 7; + len = len >> 3; +# endif + b = (const u32 *)buf; for (--b; len; --len) { - crc ^= *++b; /* use pre increment for speed */ - DO_CRC4; + q = crc ^ *++b; /* use pre increment for speed */ +# if CRC_LE_BITS == 32 + crc = DO_CRC4; +# else + crc = DO_CRC8; + q = *++b; + crc ^= DO_CRC4; +# endif } len = rem_len; /* And the last few bytes */ @@ -92,6 +107,7 @@ crc32_body(u32 crc, unsigned char const *buf, size_t len, const u32 (*tab)[256]) return crc; #undef DO_CRC #undef DO_CRC4 +#undef DO_CRC8 } #endif diff --git a/lib/crc32defs.h b/lib/crc32defs.h index daa3a5e85f6..81815928848 100644 --- a/lib/crc32defs.h +++ b/lib/crc32defs.h @@ -6,29 +6,42 @@ #define CRCPOLY_LE 0xedb88320 #define CRCPOLY_BE 0x04c11db7 -/* How many bits at a time to use. Valid values are 1, 2, 4, 8, and 32. */ -/* For less performance-sensitive, use 4 or 8 */ +/* + * How many bits at a time to use. Valid values are 1, 2, 4, 8, 32 and 64. + * For less performance-sensitive, use 4 or 8 to save table size. + * For larger systems choose same as CPU architecture as default. + * This works well on X86_64, SPARC64 systems. This may require some + * elaboration after experiments with other architectures. + */ #ifndef CRC_LE_BITS -# define CRC_LE_BITS 32 +# ifdef CONFIG_64BIT +# define CRC_LE_BITS 64 +# else +# define CRC_LE_BITS 32 +# endif #endif #ifndef CRC_BE_BITS -# define CRC_BE_BITS 32 +# ifdef CONFIG_64BIT +# define CRC_BE_BITS 64 +# else +# define CRC_BE_BITS 32 +# endif #endif /* * Little-endian CRC computation. Used with serial bit streams sent * lsbit-first. Be sure to use cpu_to_le32() to append the computed CRC. */ -#if CRC_LE_BITS > 32 || CRC_LE_BITS < 1 || CRC_LE_BITS == 16 || \ +#if CRC_LE_BITS > 64 || CRC_LE_BITS < 1 || CRC_LE_BITS == 16 || \ CRC_LE_BITS & CRC_LE_BITS-1 -# error "CRC_LE_BITS must be one of {1, 2, 4, 8, 32}" +# error "CRC_LE_BITS must be one of {1, 2, 4, 8, 32, 64}" #endif /* * Big-endian CRC computation. Used with serial bit streams sent * msbit-first. Be sure to use cpu_to_be32() to append the computed CRC. */ -#if CRC_BE_BITS > 32 || CRC_BE_BITS < 1 || CRC_BE_BITS == 16 || \ +#if CRC_BE_BITS > 64 || CRC_BE_BITS < 1 || CRC_BE_BITS == 16 || \ CRC_BE_BITS & CRC_BE_BITS-1 -# error "CRC_BE_BITS must be one of {1, 2, 4, 8, 32}" +# error "CRC_BE_BITS must be one of {1, 2, 4, 8, 32, 64}" #endif diff --git a/lib/gen_crc32table.c b/lib/gen_crc32table.c index 99ac744848f..0d9edd17ee1 100644 --- a/lib/gen_crc32table.c +++ b/lib/gen_crc32table.c @@ -1,23 +1,28 @@ #include +#include "../include/generated/autoconf.h" #include "crc32defs.h" #include #define ENTRIES_PER_LINE 4 -#if CRC_LE_BITS <= 8 -#define LE_TABLE_SIZE (1 << CRC_LE_BITS) +#if CRC_LE_BITS > 8 +# define LE_TABLE_ROWS (CRC_LE_BITS/8) +# define LE_TABLE_SIZE 256 #else -#define LE_TABLE_SIZE 256 +# define LE_TABLE_ROWS 1 +# define LE_TABLE_SIZE (1 << CRC_LE_BITS) #endif -#if CRC_BE_BITS <= 8 -#define BE_TABLE_SIZE (1 << CRC_BE_BITS) +#if CRC_BE_BITS > 8 +# define BE_TABLE_ROWS (CRC_BE_BITS/8) +# define BE_TABLE_SIZE 256 #else -#define BE_TABLE_SIZE 256 +# define BE_TABLE_ROWS 1 +# define BE_TABLE_SIZE (1 << CRC_BE_BITS) #endif -static uint32_t crc32table_le[4][256]; -static uint32_t crc32table_be[4][256]; +static uint32_t crc32table_le[LE_TABLE_ROWS][256]; +static uint32_t crc32table_be[BE_TABLE_ROWS][256]; /** * crc32init_le() - allocate and initialize LE table data @@ -40,7 +45,7 @@ static void crc32init_le(void) } for (i = 0; i < LE_TABLE_SIZE; i++) { crc = crc32table_le[0][i]; - for (j = 1; j < 4; j++) { + for (j = 1; j < LE_TABLE_ROWS; j++) { crc = crc32table_le[0][crc & 0xff] ^ (crc >> 8); crc32table_le[j][i] = crc; } @@ -64,18 +69,18 @@ static void crc32init_be(void) } for (i = 0; i < BE_TABLE_SIZE; i++) { crc = crc32table_be[0][i]; - for (j = 1; j < 4; j++) { + for (j = 1; j < BE_TABLE_ROWS; j++) { crc = crc32table_be[0][(crc >> 24) & 0xff] ^ (crc << 8); crc32table_be[j][i] = crc; } } } -static void output_table(uint32_t (*table)[256], int len, char *trans) +static void output_table(uint32_t (*table)[256], int rows, int len, char *trans) { int i, j; - for (j = 0 ; j < 4; j++) { + for (j = 0 ; j < rows; j++) { printf("{"); for (i = 0; i < len - 1; i++) { if (i % ENTRIES_PER_LINE == 0) @@ -92,15 +97,21 @@ int main(int argc, char** argv) if (CRC_LE_BITS > 1) { crc32init_le(); - printf("static const u32 crc32table_le[4][256] = {"); - output_table(crc32table_le, LE_TABLE_SIZE, "tole"); + printf("static const u32 __cacheline_aligned " + "crc32table_le[%d][%d] = {", + LE_TABLE_ROWS, LE_TABLE_SIZE); + output_table(crc32table_le, LE_TABLE_ROWS, + LE_TABLE_SIZE, "tole"); printf("};\n"); } if (CRC_BE_BITS > 1) { crc32init_be(); - printf("static const u32 crc32table_be[4][256] = {"); - output_table(crc32table_be, BE_TABLE_SIZE, "tobe"); + printf("static const u32 __cacheline_aligned " + "crc32table_be[%d][%d] = {", + BE_TABLE_ROWS, BE_TABLE_SIZE); + output_table(crc32table_be, LE_TABLE_ROWS, + BE_TABLE_SIZE, "tobe"); printf("};\n"); } -- cgit v1.2.3-70-g09d2 From 46c5801eaf86e83cb3a4142ad35188db5011fff0 Mon Sep 17 00:00:00 2001 From: "Darrick J. Wong" Date: Fri, 23 Mar 2012 15:02:25 -0700 Subject: crc32: bolt on crc32c Reuse the existing crc32 code to stamp out a crc32c implementation. Signed-off-by: Darrick J. Wong Cc: Herbert Xu Cc: Bob Pearson Cc: Randy Dunlap Signed-off-by: Andrew Morton Signed-off-by: Linus Torvalds --- include/linux/crc32.h | 2 ++ lib/Kconfig | 8 +++--- lib/crc32.c | 79 ++++++++++++++++++++++++++++++++++++--------------- lib/crc32defs.h | 7 +++++ lib/gen_crc32table.c | 35 ++++++++++++++++++----- 5 files changed, 97 insertions(+), 34 deletions(-) (limited to 'lib/gen_crc32table.c') diff --git a/include/linux/crc32.h b/include/linux/crc32.h index 391a259b2cc..68267b64bb9 100644 --- a/include/linux/crc32.h +++ b/include/linux/crc32.h @@ -11,6 +11,8 @@ 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); +extern u32 __crc32c_le(u32 crc, unsigned char const *p, size_t len); + #define crc32(seed, data, length) crc32_le(seed, (unsigned char const *)(data), length) /* diff --git a/lib/Kconfig b/lib/Kconfig index d5a86aa441a..6d7ce4b138c 100644 --- a/lib/Kconfig +++ b/lib/Kconfig @@ -61,14 +61,14 @@ config CRC_ITU_T functions require M here. config CRC32 - tristate "CRC32 functions" + tristate "CRC32/CRC32c functions" default y select BITREVERSE help This option is provided for the case where no in-kernel-tree - modules require CRC32 functions, but a module built outside the - kernel tree does. Such modules that use library CRC32 functions - require M here. + modules require CRC32/CRC32c functions, but a module built outside + the kernel tree does. Such modules that use library CRC32/CRC32c + functions require M here. config CRC32_SELFTEST bool "CRC32 perform self test on init" diff --git a/lib/crc32.c b/lib/crc32.c index a1a5145a93b..87678dd1141 100644 --- a/lib/crc32.c +++ b/lib/crc32.c @@ -46,7 +46,7 @@ #include "crc32table.h" MODULE_AUTHOR("Matt Domsch "); -MODULE_DESCRIPTION("Ethernet CRC32 calculations"); +MODULE_DESCRIPTION("Various CRC32 calculations"); MODULE_LICENSE("GPL"); #if CRC_LE_BITS > 8 || CRC_BE_BITS > 8 @@ -135,45 +135,66 @@ crc32_body(u32 crc, unsigned char const *buf, size_t len, const u32 (*tab)[256]) * @p: pointer to buffer over which CRC is run * @len: length of buffer @p */ -u32 __pure crc32_le(u32 crc, unsigned char const *p, size_t len) +static inline u32 __pure crc32_le_generic(u32 crc, unsigned char const *p, + size_t len, const u32 (*tab)[256], + u32 polynomial) { #if CRC_LE_BITS == 1 int i; while (len--) { crc ^= *p++; for (i = 0; i < 8; i++) - crc = (crc >> 1) ^ ((crc & 1) ? CRCPOLY_LE : 0); + crc = (crc >> 1) ^ ((crc & 1) ? polynomial : 0); } # elif CRC_LE_BITS == 2 while (len--) { crc ^= *p++; - crc = (crc >> 2) ^ crc32table_le[0][crc & 3]; - crc = (crc >> 2) ^ crc32table_le[0][crc & 3]; - crc = (crc >> 2) ^ crc32table_le[0][crc & 3]; - crc = (crc >> 2) ^ crc32table_le[0][crc & 3]; + crc = (crc >> 2) ^ tab[0][crc & 3]; + crc = (crc >> 2) ^ tab[0][crc & 3]; + crc = (crc >> 2) ^ tab[0][crc & 3]; + crc = (crc >> 2) ^ tab[0][crc & 3]; } # elif CRC_LE_BITS == 4 while (len--) { crc ^= *p++; - crc = (crc >> 4) ^ crc32table_le[0][crc & 15]; - crc = (crc >> 4) ^ crc32table_le[0][crc & 15]; + crc = (crc >> 4) ^ tab[0][crc & 15]; + crc = (crc >> 4) ^ tab[0][crc & 15]; } # elif CRC_LE_BITS == 8 /* aka Sarwate algorithm */ while (len--) { crc ^= *p++; - crc = (crc >> 8) ^ crc32table_le[0][crc & 255]; + crc = (crc >> 8) ^ tab[0][crc & 255]; } # else - const u32 (*tab)[] = crc32table_le; - crc = (__force u32) __cpu_to_le32(crc); crc = crc32_body(crc, p, len, tab); crc = __le32_to_cpu((__force __le32)crc); #endif return crc; } + +#if CRC_LE_BITS == 1 +u32 __pure crc32_le(u32 crc, unsigned char const *p, size_t len) +{ + return crc32_le_generic(crc, p, len, NULL, CRCPOLY_LE); +} +u32 __pure __crc32c_le(u32 crc, unsigned char const *p, size_t len) +{ + return crc32_le_generic(crc, p, len, NULL, CRC32C_POLY_LE); +} +#else +u32 __pure crc32_le(u32 crc, unsigned char const *p, size_t len) +{ + return crc32_le_generic(crc, p, len, crc32table_le, CRCPOLY_LE); +} +u32 __pure __crc32c_le(u32 crc, unsigned char const *p, size_t len) +{ + return crc32_le_generic(crc, p, len, crc32ctable_le, CRC32C_POLY_LE); +} +#endif EXPORT_SYMBOL(crc32_le); +EXPORT_SYMBOL(__crc32c_le); /** * crc32_be() - Calculate bitwise big-endian Ethernet AUTODIN II CRC32 @@ -182,7 +203,9 @@ EXPORT_SYMBOL(crc32_le); * @p: pointer to buffer over which CRC is run * @len: length of buffer @p */ -u32 __pure crc32_be(u32 crc, unsigned char const *p, size_t len) +static inline u32 __pure crc32_be_generic(u32 crc, unsigned char const *p, + size_t len, const u32 (*tab)[256], + u32 polynomial) { #if CRC_BE_BITS == 1 int i; @@ -190,37 +213,47 @@ u32 __pure crc32_be(u32 crc, unsigned char const *p, size_t len) crc ^= *p++ << 24; for (i = 0; i < 8; i++) crc = - (crc << 1) ^ ((crc & 0x80000000) ? CRCPOLY_BE : + (crc << 1) ^ ((crc & 0x80000000) ? polynomial : 0); } # elif CRC_BE_BITS == 2 while (len--) { crc ^= *p++ << 24; - crc = (crc << 2) ^ crc32table_be[0][crc >> 30]; - crc = (crc << 2) ^ crc32table_be[0][crc >> 30]; - crc = (crc << 2) ^ crc32table_be[0][crc >> 30]; - crc = (crc << 2) ^ crc32table_be[0][crc >> 30]; + crc = (crc << 2) ^ tab[0][crc >> 30]; + crc = (crc << 2) ^ tab[0][crc >> 30]; + crc = (crc << 2) ^ tab[0][crc >> 30]; + crc = (crc << 2) ^ tab[0][crc >> 30]; } # elif CRC_BE_BITS == 4 while (len--) { crc ^= *p++ << 24; - crc = (crc << 4) ^ crc32table_be[0][crc >> 28]; - crc = (crc << 4) ^ crc32table_be[0][crc >> 28]; + crc = (crc << 4) ^ tab[0][crc >> 28]; + crc = (crc << 4) ^ tab[0][crc >> 28]; } # elif CRC_BE_BITS == 8 while (len--) { crc ^= *p++ << 24; - crc = (crc << 8) ^ crc32table_be[0][crc >> 24]; + crc = (crc << 8) ^ tab[0][crc >> 24]; } # else - const u32 (*tab)[] = crc32table_be; - crc = (__force u32) __cpu_to_be32(crc); crc = crc32_body(crc, p, len, tab); crc = __be32_to_cpu((__force __be32)crc); # endif return crc; } + +#if CRC_LE_BITS == 1 +u32 __pure crc32_be(u32 crc, unsigned char const *p, size_t len) +{ + return crc32_be_generic(crc, p, len, NULL, CRCPOLY_BE); +} +#else +u32 __pure crc32_be(u32 crc, unsigned char const *p, size_t len) +{ + return crc32_be_generic(crc, p, len, crc32table_be, CRCPOLY_BE); +} +#endif EXPORT_SYMBOL(crc32_be); #ifdef CONFIG_CRC32_SELFTEST diff --git a/lib/crc32defs.h b/lib/crc32defs.h index 81815928848..6fd191732fe 100644 --- a/lib/crc32defs.h +++ b/lib/crc32defs.h @@ -6,6 +6,13 @@ #define CRCPOLY_LE 0xedb88320 #define CRCPOLY_BE 0x04c11db7 +/* + * This is the CRC32c polynomial, as outlined by Castagnoli. + * x^32+x^28+x^27+x^26+x^25+x^23+x^22+x^20+x^19+x^18+x^14+x^13+x^11+x^10+x^9+ + * x^8+x^6+x^0 + */ +#define CRC32C_POLY_LE 0x82F63B78 + /* * How many bits at a time to use. Valid values are 1, 2, 4, 8, 32 and 64. * For less performance-sensitive, use 4 or 8 to save table size. diff --git a/lib/gen_crc32table.c b/lib/gen_crc32table.c index 0d9edd17ee1..8f8d5439e2d 100644 --- a/lib/gen_crc32table.c +++ b/lib/gen_crc32table.c @@ -23,6 +23,7 @@ static uint32_t crc32table_le[LE_TABLE_ROWS][256]; static uint32_t crc32table_be[BE_TABLE_ROWS][256]; +static uint32_t crc32ctable_le[LE_TABLE_ROWS][256]; /** * crc32init_le() - allocate and initialize LE table data @@ -31,27 +32,38 @@ static uint32_t crc32table_be[BE_TABLE_ROWS][256]; * fact that crctable[i^j] = crctable[i] ^ crctable[j]. * */ -static void crc32init_le(void) +static void crc32init_le_generic(const uint32_t polynomial, + uint32_t (*tab)[256]) { unsigned i, j; uint32_t crc = 1; - crc32table_le[0][0] = 0; + tab[0][0] = 0; for (i = LE_TABLE_SIZE >> 1; i; i >>= 1) { - crc = (crc >> 1) ^ ((crc & 1) ? CRCPOLY_LE : 0); + crc = (crc >> 1) ^ ((crc & 1) ? polynomial : 0); for (j = 0; j < LE_TABLE_SIZE; j += 2 * i) - crc32table_le[0][i + j] = crc ^ crc32table_le[0][j]; + tab[0][i + j] = crc ^ tab[0][j]; } for (i = 0; i < LE_TABLE_SIZE; i++) { - crc = crc32table_le[0][i]; + crc = tab[0][i]; for (j = 1; j < LE_TABLE_ROWS; j++) { - crc = crc32table_le[0][crc & 0xff] ^ (crc >> 8); - crc32table_le[j][i] = crc; + crc = tab[0][crc & 0xff] ^ (crc >> 8); + tab[j][i] = crc; } } } +static void crc32init_le(void) +{ + crc32init_le_generic(CRCPOLY_LE, crc32table_le); +} + +static void crc32cinit_le(void) +{ + crc32init_le_generic(CRC32C_POLY_LE, crc32ctable_le); +} + /** * crc32init_be() - allocate and initialize BE table data */ @@ -114,6 +126,15 @@ int main(int argc, char** argv) BE_TABLE_SIZE, "tobe"); printf("};\n"); } + if (CRC_LE_BITS > 1) { + crc32cinit_le(); + printf("static const u32 __cacheline_aligned " + "crc32ctable_le[%d][%d] = {", + LE_TABLE_ROWS, LE_TABLE_SIZE); + output_table(crc32ctable_le, LE_TABLE_ROWS, + LE_TABLE_SIZE, "tole"); + printf("};\n"); + } return 0; } -- cgit v1.2.3-70-g09d2