summaryrefslogtreecommitdiff
path: root/Documentation/crc32.txt
diff options
context:
space:
mode:
authorMauro Carvalho Chehab <mchehab@s-opensource.com>2017-05-14 09:56:02 -0300
committerJonathan Corbet <corbet@lwn.net>2017-07-14 13:51:30 -0600
commit2e4e6f30f7ff84632e893786fab5e8ff44ff3e03 (patch)
tree33e07f82369ecaec0605fbe7c59b961a7e390b56 /Documentation/crc32.txt
parente8cb6f1edc57e5c729ce4e37a54a5f84fac0c6a4 (diff)
crc32.txt: standardize document format
Each text file under Documentation follows a different format. Some doesn't even have titles! Change its representation to follow the adopted standard, using ReST markups for it to be parseable by Sphinx: - Add a title for the document; - Mark literal blocks. While here, replace a comma by a dot at the end of a paragraph. Signed-off-by: Mauro Carvalho Chehab <mchehab@s-opensource.com> Signed-off-by: Jonathan Corbet <corbet@lwn.net>
Diffstat (limited to 'Documentation/crc32.txt')
-rw-r--r--Documentation/crc32.txt75
1 files changed, 41 insertions, 34 deletions
diff --git a/Documentation/crc32.txt b/Documentation/crc32.txt
index a08a7dd9d625..8a6860f33b4e 100644
--- a/Documentation/crc32.txt
+++ b/Documentation/crc32.txt
@@ -1,4 +1,6 @@
-A brief CRC tutorial.
+=================================
+brief tutorial on CRC computation
+=================================
A CRC is a long-division remainder. You add the CRC to the message,
and the whole thing (message+CRC) is a multiple of the given
@@ -8,7 +10,8 @@ remainder computed on the message+CRC is 0. This latter approach
is used by a lot of hardware implementations, and is why so many
protocols put the end-of-frame flag after the CRC.
-It's actually the same long division you learned in school, except that
+It's actually the same long division you learned in school, except that:
+
- We're working in binary, so the digits are only 0 and 1, and
- When dividing polynomials, there are no carries. Rather than add and
subtract, we just xor. Thus, we tend to get a bit sloppy about
@@ -40,11 +43,12 @@ throw the quotient bit away, but subtract the appropriate multiple of
the polynomial from the remainder and we're back to where we started,
ready to process the next bit.
-A big-endian CRC written this way would be coded like:
-for (i = 0; i < input_bits; i++) {
- multiple = remainder & 0x80000000 ? CRCPOLY : 0;
- remainder = (remainder << 1 | next_input_bit()) ^ multiple;
-}
+A big-endian CRC written this way would be coded like::
+
+ for (i = 0; i < input_bits; i++) {
+ multiple = remainder & 0x80000000 ? CRCPOLY : 0;
+ remainder = (remainder << 1 | next_input_bit()) ^ multiple;
+ }
Notice how, to get at bit 32 of the shifted remainder, we look
at bit 31 of the remainder *before* shifting it.
@@ -54,25 +58,26 @@ the remainder don't actually affect any decision-making until
32 bits later. Thus, the first 32 cycles of this are pretty boring.
Also, to add the CRC to a message, we need a 32-bit-long hole for it at
the end, so we have to add 32 extra cycles shifting in zeros at the
-end of every message,
+end of every message.
These details lead to a standard trick: rearrange merging in the
next_input_bit() until the moment it's needed. Then the first 32 cycles
can be precomputed, and merging in the final 32 zero bits to make room
-for the CRC can be skipped entirely. This changes the code to:
+for the CRC can be skipped entirely. This changes the code to::
-for (i = 0; i < input_bits; i++) {
- remainder ^= next_input_bit() << 31;
- multiple = (remainder & 0x80000000) ? CRCPOLY : 0;
- remainder = (remainder << 1) ^ multiple;
-}
+ for (i = 0; i < input_bits; i++) {
+ remainder ^= next_input_bit() << 31;
+ multiple = (remainder & 0x80000000) ? CRCPOLY : 0;
+ remainder = (remainder << 1) ^ multiple;
+ }
-With this optimization, the little-endian code is particularly simple:
-for (i = 0; i < input_bits; i++) {
- remainder ^= next_input_bit();
- multiple = (remainder & 1) ? CRCPOLY : 0;
- remainder = (remainder >> 1) ^ multiple;
-}
+With this optimization, the little-endian code is particularly simple::
+
+ for (i = 0; i < input_bits; i++) {
+ remainder ^= next_input_bit();
+ multiple = (remainder & 1) ? CRCPOLY : 0;
+ remainder = (remainder >> 1) ^ multiple;
+ }
The most significant coefficient of the remainder polynomial is stored
in the least significant bit of the binary "remainder" variable.
@@ -81,23 +86,25 @@ be bit-reversed) and next_input_bit().
As long as next_input_bit is returning the bits in a sensible order, we don't
*have* to wait until the last possible moment to merge in additional bits.
-We can do it 8 bits at a time rather than 1 bit at a time:
-for (i = 0; i < input_bytes; i++) {
- remainder ^= next_input_byte() << 24;
- for (j = 0; j < 8; j++) {
- multiple = (remainder & 0x80000000) ? CRCPOLY : 0;
- remainder = (remainder << 1) ^ multiple;
+We can do it 8 bits at a time rather than 1 bit at a time::
+
+ for (i = 0; i < input_bytes; i++) {
+ remainder ^= next_input_byte() << 24;
+ for (j = 0; j < 8; j++) {
+ multiple = (remainder & 0x80000000) ? CRCPOLY : 0;
+ remainder = (remainder << 1) ^ multiple;
+ }
}
-}
-Or in little-endian:
-for (i = 0; i < input_bytes; i++) {
- remainder ^= next_input_byte();
- for (j = 0; j < 8; j++) {
- multiple = (remainder & 1) ? CRCPOLY : 0;
- remainder = (remainder >> 1) ^ multiple;
+Or in little-endian::
+
+ for (i = 0; i < input_bytes; i++) {
+ remainder ^= next_input_byte();
+ for (j = 0; j < 8; j++) {
+ multiple = (remainder & 1) ? CRCPOLY : 0;
+ remainder = (remainder >> 1) ^ multiple;
+ }
}
-}
If the input is a multiple of 32 bits, you can even XOR in a 32-bit
word at a time and increase the inner loop count to 32.