crc32: move to documentation

Moved 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.

Signed-off-by: George Spelvin <linux@horizon.com>
Signed-off-by: Bob Pearson <rpearson@systemfabricworks.com>

Conflicts:

	lib/crc32.c
crc32: replace self test

Replaced 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.

Signed-off-by: Bob Pearson <rpearson@systemfabricworks.com>
crc32: add pointer to tab

Replace 2D array references by pointer references in loops.
This change has no effect on X86 code but improves PPC performance.

Signed-off-by: Bob Pearson <rpearson@systemfabricworks.com>
crc32: misc cleanup

Misc cleanup of lib/crc32.c and related files
- removed unnecessary header files.
- straightened out some convoluted ifdef's
- rewrote some references to 2 dimensional arrays as 1 dimensional arrays
to make them correct. I.e. replaced tab[i] with tab[0][i].
- a few trivial whitespace changes
- fixed 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.

Signed-off-by: Bob Pearson <rpearson@systemfabricworks.com>
crc32: fix check endian warnings

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.

Signed-off-by: Bob Pearson <rpearson@systemfabricworks.com>
crc32: add real 8 bit

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.

Signed-off-by: Bob Pearson <rpearson@systemfabricworks.com>

Conflicts:

	lib/crc32defs.h
crc32: add slicing by 8

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.

Signed-off-by: Bob Pearson <rpearson@systemfabricworks.com>
modified by faux123

Conflicts:

	lib/crc32defs.h
crc32: optimize loops for x86

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.

Signed-off-by: Bob Pearson <rpearson@systemfabricworks.com>
crc32: final

Some final changes
- added a comment at the top of crc32.c

Signed-off-by: Bob Pearson <rpearson@systemfabricworks.com>
crc32: Bolt on crc32c

Reuse the existing crc32 code to stamp out a crc32c implementation

Signed-off-by: Darrick J. Wong <djwong@us.ibm.com>
crc32: Add self-test code for crc32c

Add self-test code for crc32c.

Signed-off-by: Darrick J. Wong <djwong@us.ibm.com>
crypto: crc32c should use library implementation

Since lib/crc32.c now provides crc32c, remove the software
implementation here and call the library function instead.

Signed-off-by: Darrick J. Wong <djwong@us.ibm.com>
crc32: Select an algorithm via kconfig

Allow the kernel builder to choose a crc32* algorithm for the kernel.

Signed-off-by: Darrick J. Wong <djwong@us.ibm.com>
crc32: expose __crc32c_le to fix compilation error for crc32c
lib/string: use glibc version

the performance of memcpy and memmove of the general version is very
inefficient, this patch improved them.

Signed-off-by: Miao Xie <miaox*******>
adapted by faux123 for 3.0.13 kernel
lib/memcopy: use glibc version

the kernel's memcpy and memmove is very inefficient. But the glibc version is
quite fast, in some cases it is 10 times faster than the kernel version. So I
introduce some memory copy macros and functions of the glibc to improve the
kernel version's performance.

The strategy of the memory functions is:
1. Copy bytes until the destination pointer is aligned.
2. Copy words in unrolled loops.  If the source and destination are not
   aligned in the same way, use word memory operations, but shift and merge
   two read words before writing.
3. Copy the few remaining bytes.

Signed-off-by: Miao Xie <miaox*******>
adapted by faux123 for 3.0.13 kernel
lib/sha1: use the git implementation of SHA-1

For ChromiumOS, we use SHA-1 to verify the integrity of the root
filesystem.  The speed of the kernel sha-1 implementation has a major
impact on our boot performance.

To improve boot performance, we investigated using the heavily optimized
sha-1 implementation used in git.  With the git sha-1 implementation, we
see a 11.7% improvement in boot time.

10 reboots, remove slowest/fastest.

Before:

  Mean: 6.58 seconds Stdev: 0.14

After (with git sha-1, this patch):

  Mean: 5.89 seconds Stdev: 0.07

The other cool thing about the git SHA-1 implementation is that it only
needs 64 bytes of stack for the workspace while the original kernel
implementation needed 320 bytes.

Signed-off-by: Mandeep Singh Baines <msb@chromium.org>
Cc: Ramsay Jones <ramsay@ramsay1.demon.co.uk>
Cc: Nicolas Pitre <nico@cam.org>
Cc: Herbert Xu <herbert@gondor.apana.org.au>
Cc: David S. Miller <davem@davemloft.net>
Cc: linux-crypto@vger.kernel.org
Signed-off-by: Linus Torvalds <torvalds@linux-foundation.org>