Patchwork [1/4] crc32: Bolt on crc32c

login
register
mail settings
Submitter Darrick J. Wong
Date Oct. 4, 2011, 11:54 p.m.
Message ID <20111004235403.1560.55503.stgit@elm3c44.beaverton.ibm.com>
Download mbox | patch
Permalink /patch/117717/
State Not Applicable
Headers show

Comments

Darrick J. Wong - Oct. 4, 2011, 11:54 p.m.
Reuse the existing crc32 code to stamp out a crc32c implementation.

Signed-off-by: Darrick J. Wong <djwong@us.ibm.com>
---
 include/linux/crc32.h |    2 ++
 lib/Kconfig           |    8 +++---
 lib/crc32.c           |   62 +++++++++++++++++++++++++++++++------------------
 lib/crc32defs.h       |    7 ++++++
 lib/gen_crc32table.c  |   35 ++++++++++++++++++++++------
 5 files changed, 80 insertions(+), 34 deletions(-)



--
To unsubscribe from this list: send the line "unsubscribe linux-ext4" in
the body of a message to majordomo@vger.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Herbert Xu - Oct. 21, 2011, 12:28 p.m.
On Tue, Oct 04, 2011 at 04:54:03PM -0700, Darrick J. Wong wrote:
> Reuse the existing crc32 code to stamp out a crc32c implementation.
> 
> Signed-off-by: Darrick J. Wong <djwong@us.ibm.com>

Did you want this to go through my tree? If so then there is a
problem since it doesn't apply at all.

Cheers,
Darrick J. Wong - Oct. 21, 2011, 4:57 p.m.
On Fri, Oct 21, 2011 at 02:28:03PM +0200, Herbert Xu wrote:
> On Tue, Oct 04, 2011 at 04:54:03PM -0700, Darrick J. Wong wrote:
> > Reuse the existing crc32 code to stamp out a crc32c implementation.
> > 
> > Signed-off-by: Darrick J. Wong <djwong@us.ibm.com>
> 
> Did you want this to go through my tree? If so then there is a
> problem since it doesn't apply at all.

My patchset builds upon Bob Pearson's crc32 patchset from early September.  Do
my patches fail to apply after applying his patchset?

Or, to speed things along, should I simply repost both Bob's and my patches as
one big series?

Bob, have you sent out a new iteration of your patches since September 6th?

--D
> 
> Cheers,
> -- 
> Email: Herbert Xu <herbert@gondor.apana.org.au>
> Home Page: http://gondor.apana.org.au/~herbert/
> PGP Key: http://gondor.apana.org.au/~herbert/pubkey.txt
> --
> To unsubscribe from this list: send the line "unsubscribe linux-ext4" in
> the body of a message to majordomo@vger.kernel.org
> More majordomo info at  http://vger.kernel.org/majordomo-info.html
> 

--
To unsubscribe from this list: send the line "unsubscribe linux-ext4" in
the body of a message to majordomo@vger.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Herbert Xu - Oct. 21, 2011, 7:15 p.m.
On Fri, Oct 21, 2011 at 09:57:03AM -0700, Darrick J. Wong wrote:
> 
> My patchset builds upon Bob Pearson's crc32 patchset from early September.  Do
> my patches fail to apply after applying his patchset?
> 
> Or, to speed things along, should I simply repost both Bob's and my patches as
> one big series?
> 
> Bob, have you sent out a new iteration of your patches since September 6th?

I'm fine with you pushing this through whichever tree that Bob's
patches are going through.

Cheers,
Darrick J. Wong - Oct. 26, 2011, 5:16 p.m.
On Fri, Oct 21, 2011 at 09:15:14PM +0200, Herbert Xu wrote:
> On Fri, Oct 21, 2011 at 09:57:03AM -0700, Darrick J. Wong wrote:
> > 
> > My patchset builds upon Bob Pearson's crc32 patchset from early September.  Do
> > my patches fail to apply after applying his patchset?
> > 
> > Or, to speed things along, should I simply repost both Bob's and my patches as
> > one big series?
> > 
> > Bob, have you sent out a new iteration of your patches since September 6th?
> 
> I'm fine with you pushing this through whichever tree that Bob's
> patches are going through.

Bob,

Which tree (if any) are your patches going through?  

--D

--
To unsubscribe from this list: send the line "unsubscribe linux-ext4" in
the body of a message to majordomo@vger.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Darrick J. Wong - Oct. 27, 2011, 6:32 p.m.
Hi Bob,

Would you mind posting your current crc32 patches to lkml again?  A couple of
months have gone by, and it sure would be nice to replace the circa-July patch
in -next with a newer one.  I recall that there were requests for some code
changes even in Bob's 8/31 submission, so it'd be nice to have a fresh set from
you with your latest changes.

I'd also like to freshen my crc32c refactor patches and send them along too.

To clarify, I tried the new crc32{,c}  on my ppc32 and it passed the self test.

--D

On Wed, Oct 26, 2011 at 10:16:10AM -0700, Darrick J. Wong wrote:
> On Fri, Oct 21, 2011 at 09:15:14PM +0200, Herbert Xu wrote:
> > On Fri, Oct 21, 2011 at 09:57:03AM -0700, Darrick J. Wong wrote:
> > > 
> > > My patchset builds upon Bob Pearson's crc32 patchset from early September.  Do
> > > my patches fail to apply after applying his patchset?
> > > 
> > > Or, to speed things along, should I simply repost both Bob's and my patches as
> > > one big series?
> > > 
> > > Bob, have you sent out a new iteration of your patches since September 6th?
> > 
> > I'm fine with you pushing this through whichever tree that Bob's
> > patches are going through.
> 
> Bob,
> 
> Which tree (if any) are your patches going through?  
> 
> --D
> 
> --
> To unsubscribe from this list: send the line "unsubscribe linux-ext4" in
> the body of a message to majordomo@vger.kernel.org
> More majordomo info at  http://vger.kernel.org/majordomo-info.html

--
To unsubscribe from this list: send the line "unsubscribe linux-ext4" in
the body of a message to majordomo@vger.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Darrick J. Wong - Nov. 15, 2011, 8:48 a.m.
On Fri, Oct 21, 2011 at 09:15:14PM +0200, Herbert Xu wrote:
> On Fri, Oct 21, 2011 at 09:57:03AM -0700, Darrick J. Wong wrote:
> > 
> > My patchset builds upon Bob Pearson's crc32 patchset from early September.  Do
> > my patches fail to apply after applying his patchset?
> > 
> > Or, to speed things along, should I simply repost both Bob's and my patches as
> > one big series?
> > 
> > Bob, have you sent out a new iteration of your patches since September 6th?
> 
> I'm fine with you pushing this through whichever tree that Bob's
> patches are going through.

Well... it's been 2.5 weeks since I last asked about this.  No reply, afaict.
I haven't seen any complaints about Bob's latest patchset, nor any complaints
about my set that sits atop his.  On the other hand, I'm pretty sure I haven't
seen Bob's patches appear in any trees, and Google shows no recent progress.

Herbert, would you object to pushing the whole patchset through the crypto
tree?

--D
> 
> Cheers,
> -- 
> Email: Herbert Xu <herbert@gondor.apana.org.au>
> Home Page: http://gondor.apana.org.au/~herbert/
> PGP Key: http://gondor.apana.org.au/~herbert/pubkey.txt
> --
> To unsubscribe from this list: send the line "unsubscribe linux-ext4" in
> the body of a message to majordomo@vger.kernel.org
> More majordomo info at  http://vger.kernel.org/majordomo-info.html
> 

--
To unsubscribe from this list: send the line "unsubscribe linux-ext4" in
the body of a message to majordomo@vger.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Bob Pearson - Nov. 15, 2011, 3:38 p.m.
I'd have sent new bits by now. Although the changes are minor and cosmetic.
The problem is that due to getting things ready for SC11 (where I am now) I
have been unable to test anything for the past two weeks.
I can retest everything next week or you can go with the bits that are out
there.

> -----Original Message-----
> From: Darrick J. Wong [mailto:djwong@us.ibm.com]
> Sent: Tuesday, November 15, 2011 2:48 AM
> To: Herbert Xu
> Cc: Andreas Dilger; Theodore Tso; David Miller; Joakim Tjernlund; Bob
> Pearson; linux-kernel; Mingming Cao; linux-crypto; linux-fsdevel; linux-
> ext4@vger.kernel.org
> Subject: Re: [PATCH 1/4] crc32: Bolt on crc32c
> 
> On Fri, Oct 21, 2011 at 09:15:14PM +0200, Herbert Xu wrote:
> > On Fri, Oct 21, 2011 at 09:57:03AM -0700, Darrick J. Wong wrote:
> > >
> > > My patchset builds upon Bob Pearson's crc32 patchset from early
> September.  Do
> > > my patches fail to apply after applying his patchset?
> > >
> > > Or, to speed things along, should I simply repost both Bob's and my
> patches as
> > > one big series?
> > >
> > > Bob, have you sent out a new iteration of your patches since September
> 6th?
> >
> > I'm fine with you pushing this through whichever tree that Bob's
> > patches are going through.
> 
> Well... it's been 2.5 weeks since I last asked about this.  No reply,
afaict.
> I haven't seen any complaints about Bob's latest patchset, nor any
complaints
> about my set that sits atop his.  On the other hand, I'm pretty sure I
haven't
> seen Bob's patches appear in any trees, and Google shows no recent
> progress.
> 
> Herbert, would you object to pushing the whole patchset through the crypto
> tree?
> 
> --D
> >
> > Cheers,
> > --
> > Email: Herbert Xu <herbert@gondor.apana.org.au>
> > Home Page: http://gondor.apana.org.au/~herbert/
> > PGP Key: http://gondor.apana.org.au/~herbert/pubkey.txt
> > --
> > To unsubscribe from this list: send the line "unsubscribe linux-ext4" in
> > the body of a message to majordomo@vger.kernel.org
> > More majordomo info at  http://vger.kernel.org/majordomo-info.html
> >

--
To unsubscribe from this list: send the line "unsubscribe linux-ext4" in
the body of a message to majordomo@vger.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html

Patch

diff --git a/include/linux/crc32.h b/include/linux/crc32.h
index 391a259..68267b6 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 8e0bcbd..477be04 100644
--- a/lib/Kconfig
+++ b/lib/Kconfig
@@ -51,14 +51,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 d56516d..8df9561 100644
--- a/lib/crc32.c
+++ b/lib/crc32.c
@@ -46,7 +46,7 @@ 
 #include "crc32table.h"
 
 MODULE_AUTHOR("Matt Domsch <Matt_Domsch@dell.com>");
-MODULE_DESCRIPTION("Ethernet CRC32 calculations");
+MODULE_DESCRIPTION("Various CRC32 calculations");
 MODULE_LICENSE("GPL");
 
 #if CRC_LE_BITS > 8 || CRC_BE_BITS > 8
@@ -135,46 +135,57 @@  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;
 }
+
+u32 __pure crc32_le(u32 crc, unsigned char const *p, size_t len)
+{
+	return crc32_le_generic(crc, p, len, crc32table_le, CRCPOLY_LE);
+}
 EXPORT_SYMBOL(crc32_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);
+}
+EXPORT_SYMBOL(__crc32c_le);
+
 /**
  * crc32_be() - Calculate bitwise big-endian Ethernet AUTODIN II CRC32
  * @crc: seed value for computation.  ~0 for Ethernet, sometimes 0 for
@@ -182,7 +193,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 +203,40 @@  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;
 }
+
+u32 __pure crc32_be(u32 crc, unsigned char const *p, size_t len)
+{
+	return crc32_be_generic(crc, p, len, crc32table_be, CRCPOLY_BE);
+}
 EXPORT_SYMBOL(crc32_be);
 
 #ifdef CONFIG_CRC32_SELFTEST
diff --git a/lib/crc32defs.h b/lib/crc32defs.h
index 8181592..6fd1917 100644
--- a/lib/crc32defs.h
+++ b/lib/crc32defs.h
@@ -7,6 +7,13 @@ 
 #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.
  * For larger systems choose same as CPU architecture as default.
diff --git a/lib/gen_crc32table.c b/lib/gen_crc32table.c
index 0d9edd1..8f8d543 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;
 }