Documentation/staging: Fix typo and incorrect citation in crc32.rst
Subsystems (3)
PATCH 1/1 Documentation/staging: Fix typo and incorrect citation in crc32.rst
In Documentation/staging/crc32.rst, below errors have been corrected:
1. Line 37: from "to being" to "to bring"
2. Line 119: Incorrect citation date:
It must be August 1988 instead of August 1998
--- Documentation/staging/crc32.rst | 4 ++-- 1 file changed, 2 insertions(+), 2 deletions(-)
Documentation/staging/crc32.rst +2 -2
@@ -34,7 +34,7 @@ do it in the right order, matching the endianness. Just like with ordinary division, you proceed one digit (bit) at a time. Each step of the division you take one more digit (bit) of the dividend and append it to the current remainder. Then you figure out the -appropriate multiple of the divisor to subtract to being the remainder +appropriate multiple of the divisor to subtract to bring the remainder back into range. In binary, this is easy - it has to be either 0 or 1, and to make the XOR cancel, it's just a copy of bit 32 of the remainder.
@@ -116,7 +116,7 @@ for any fractional bytes at the end. To reduce the number of conditional branches, software commonly uses the byte-at-a-time table method, popularized by Dilip V. Sarwate, "Computation of Cyclic Redundancy Checks via Table Look-Up", Comm. ACM -v.31 no.8 (August 1998) p. 1008-1013. +v.31 no.8 (August 1988) p. 1008-1013. Here, rather than just shifting one bit of the remainder to decide in the correct multiple to subtract, we can shift a byte at a time.
Signature · 1 line
2.43.0
Eric Biggers
maintainerQuoted 11 lines · Rakuram Eswaran
In
Documentation/staging/crc32.rst, below errors have been corrected:1. Line 37: from "to being" to "to bring"
2. Line 119: Incorrect citation date:
It must be August 1988 instead of August 1998Signed-off-by Rakuram Eswaran <[email protected]>--- Documentation/staging/crc32.rst | 4 ++-- 1 file changed, 2 insertions(+), 2 deletions(-)
Sure, why not. Applied to
https://git.kernel.org/pub/scm/linux/kernel/git/ebiggers/linux.git/log/?h=crc-next
Note that this file is somewhat dated and is due for a rewrite. It doesn't describe how most of the optimized CRC code actually works these days, using carryless multiplication or dedicated instructions.
- Eric
Thanks for applying my patch!
I noticed your comment about the file being dated.
I’d be interested in helping to update it to cover the more modern CRC implementations — things like carryless multiplication and hardware CRC instructions on x86, ARM, etc.
Since I’m not very familiar yet with these optimized approaches. Could you suggest a good starting point for exploring this in the kernel (or any references you recommend)?
I was planning to look at lib/crc32.c and the arch-specific implementations, but would appreciate your guidance.
Best Regards,
Rakuram
Eric Biggers
maintainerHi Rakuram,
Quoted 11 lines · Rakuram Eswaran
Thanks for applying my patch!
I noticed your comment about the file being dated.
I’d be interested in helping to update it to cover the more modern CRC implementations — things like carryless multiplication and hardware CRC instructions on x86, ARM, etc.Since I’m not very familiar yet with these optimized approaches. Could you suggest a good starting point for exploring this in the kernel (or any references you recommend)?
Quoted 5 lines
I was planning to look at
lib/crc32.cand the arch-specific implementations, but would appreciate your guidance.Best Regards,
Rakuram
https://www.corsix.org/content/alternative-exposition-crc32_4k_pclmulqdq
has a fairly good explanation.
In the kernel, x86 uses crc32 instructions for crc32c(), and arm64 uses crc32 instructions for crc32c(), crc32_le(), and crc32_be().
x86, arm, arm64, powerpc, s390, and riscv all have CRC implementations using carryless multiplication instructions. The riscv one might be the easiest to read since it is mostly written in C, rather than assembly.
See: lib/crc/riscv/crc-clmul-template.h
- Eric