linux-toradex.git/lib/crc32.c, branch v3.4.73

crc32: add self-test code for crc32c

2012-03-23T23:58:38+00:00

Add self-test code for crc32c.

Signed-off-by: Darrick J. Wong 
Cc: Bob Pearson 
Signed-off-by: Andrew Morton 
Signed-off-by: Linus Torvalds

crc32: bolt on crc32c

2012-03-23T23:58:38+00:00

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

crc32: add note about this patchset to crc32.c

2012-03-23T23:58:38+00:00

Add a comment at the top of crc32.c

[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

crc32: optimize loop counter for x86

2012-03-23T23:58:37+00:00

Add two changes that improve the performance of x86 systems

1. replace main loop with incrementing counter this change improves
   the performance of the selftest by about 5-6% on Nehalem CPUs.  The
   apparent reason is that the compiler can use the loop index to perform
   an indexed memory access.  This is reported to make the performance of
   PowerPC CPUs to get worse.

2. replace the rem_len loop with incrementing counter this change
   improves the performance of the selftest, which has more than the usual
   number of occurances, by about 1-2% on x86 CPUs.  In actual work loads
   the length is most often a multiple of 4 bytes and this code does not
   get executed as often if at all.  Again this change is reported to make
   the performance of PowerPC get worse.

[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

crc32: add slice-by-8 algorithm to existing code

2012-03-23T23:58:37+00:00

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

crc32: make CRC_*_BITS definition correspond to actual bit counts

2012-03-23T23:58:37+00:00

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

crc32: fix mixing of endian-specific types

2012-03-23T23:58:37+00:00

crc32.c in its original version freely mixed u32, __le32 and __be32 types
which caused warnings from sparse with __CHECK_ENDIAN__.  This patch fixes
these by forcing the types to u32.

[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

crc32: miscellaneous cleanups

2012-03-23T23:58:37+00:00

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

crc32: simplify unit test code

2012-03-23T23:58:37+00:00

Replace the unit test provided in crc32.c, which doesn't have a makefile
and doesn't compile with current headers, with a simpler self test
routine that also gives a measure of performance and runs at module init
time.  The self test option can be enabled through a configuration
option CONFIG_CRC32_SELFTEST.

The test stresses the pre and post loops and is thus not very realistic
since actual uses will likely have addresses and lengths that are at
least 4 byte aligned.  However, the main loop is long enough so that the
performance is dominated by that loop.

The expected values for crc32_le and crc32_be were generated with the
original version of crc32.c using CRC_BITS_LE = 8 and CRC_BITS_BE = 8.
These values were then used to check all the values of the BITS
parameters in both the original and new versions.

The performance results show some variability from run to run in spite
of attempts to both warm the cache and reduce the amount of OS noise by
limiting interrutps during the test.  To get comparable results and to
analyse options wrt performance the best time reported over a small
sample of runs has been taken.

[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

crc32: move long comment about crc32 fundamentals to Documentation/

2012-03-23T23:58:37+00:00

Move a long comment from lib/crc32.c to Documentation/crc32.txt where it
will more likely get read.

Edited the resulting document to add an explanation of the slicing-by-n
algorithm.

[djwong@us.ibm.com: minor changelog tweaks]
[akpm@linux-foundation.org: fix typo, per George]
Signed-off-by: George Spelvin 
Signed-off-by: Bob Pearson 
Signed-off-by: Darrick J. Wong 
Signed-off-by: Andrew Morton 
Signed-off-by: Linus Torvalds