Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > linux.kernel > #1645108

[PATCH 11/31] crc32.txt: standardize document format

Show all headers | View raw

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>
---
 Documentation/crc32.txt | 75 +++++++++++++++++++++++++++----------------------
 1 file 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.
-- 
2.9.4

Back to linux.kernel | Previous | Next — Previous in thread | Next in thread | Find similar | Unroll thread

Thread

[PATCH 00/31] Standardize doc formats - part 1 Mauro Carvalho Chehab <mchehab@s-opensource.com> - 2017-05-19 03:30 +0200
  [PATCH 16/31] DMA-attributes.txt: standardize document format Mauro Carvalho Chehab <mchehab@s-opensource.com> - 2017-05-19 03:30 +0200
  [PATCH 27/31] intel_txt.txt: standardize document format Mauro Carvalho Chehab <mchehab@s-opensource.com> - 2017-05-19 03:30 +0200
  [PATCH 26/31] hwspinlock.txt: standardize document format Mauro Carvalho Chehab <mchehab@s-opensource.com> - 2017-05-19 03:30 +0200
  [PATCH 13/31] digsig.txt: standardize document format Mauro Carvalho Chehab <mchehab@s-opensource.com> - 2017-05-19 03:30 +0200
  [PATCH 19/31] efi-stub.txt: standardize document format Mauro Carvalho Chehab <mchehab@s-opensource.com> - 2017-05-19 03:50 +0200
  [PATCH 28/31] Intel-IOMMU.txt: standardize document format Mauro Carvalho Chehab <mchehab@s-opensource.com> - 2017-05-19 03:50 +0200
  [PATCH 06/31] cgroup-v2.txt: standardize document format Mauro Carvalho Chehab <mchehab@s-opensource.com> - 2017-05-19 03:50 +0200
    Re: [PATCH 06/31] cgroup-v2.txt: standardize document format Tejun Heo <tj@kernel.org> - 2017-05-19 17:00 +0200
  [PATCH 03/31] btmrvl.txt: standardize document format Mauro Carvalho Chehab <mchehab@s-opensource.com> - 2017-05-19 03:50 +0200
  [PATCH 22/31] futex-requeue-pi.txt: standardize document format Mauro Carvalho Chehab <mchehab@s-opensource.com> - 2017-05-19 03:50 +0200
  [PATCH 08/31] clk.txt: standardize document format Mauro Carvalho Chehab <mchehab@s-opensource.com> - 2017-05-19 03:50 +0200
  [PATCH 07/31] circular-buffers.txt: standardize document format Mauro Carvalho Chehab <mchehab@s-opensource.com> - 2017-05-19 03:50 +0200
  [PATCH 12/31] dcdbas.txt: standardize document format Mauro Carvalho Chehab <mchehab@s-opensource.com> - 2017-05-19 03:50 +0200
  [PATCH 25/31] hw_random.txt: standardize document format Mauro Carvalho Chehab <mchehab@s-opensource.com> - 2017-05-19 03:50 +0200
  [PATCH 21/31] flexible-arrays.txt: standardize document format Mauro Carvalho Chehab <mchehab@s-opensource.com> - 2017-05-19 03:50 +0200
  [PATCH 01/31] bcache.txt: standardize document format Mauro Carvalho Chehab <mchehab@s-opensource.com> - 2017-05-19 03:50 +0200
  [PATCH 04/31] bus-virt-phys-mapping.txt: standardize document format Mauro Carvalho Chehab <mchehab@s-opensource.com> - 2017-05-19 03:50 +0200
  [PATCH 23/31] gcc-plugins.txt: standardize document format Mauro Carvalho Chehab <mchehab@s-opensource.com> - 2017-05-19 03:50 +0200
    Re: [PATCH 23/31] gcc-plugins.txt: standardize document format Kees Cook <keescook@google.com> - 2017-05-24 19:40 +0200
      Re: [PATCH 23/31] gcc-plugins.txt: standardize document format Mauro Carvalho Chehab <mchehab@s-opensource.com> - 2017-05-24 22:20 +0200
  [PATCH 09/31] cpu-load: standardize document format Mauro Carvalho Chehab <mchehab@s-opensource.com> - 2017-05-19 03:50 +0200
  [PATCH 24/31] highuid.txt: standardize document format Mauro Carvalho Chehab <mchehab@s-opensource.com> - 2017-05-19 03:50 +0200
  [PATCH 17/31] DMA-ISA-LPC.txt: standardize document format Mauro Carvalho Chehab <mchehab@s-opensource.com> - 2017-05-19 03:50 +0200
  [PATCH 18/31] debugging-via-ohci1394.txt: standardize document format Mauro Carvalho Chehab <mchehab@s-opensource.com> - 2017-05-19 03:50 +0200
  [PATCH 05/31] cachetlb.txt: standardize document format Mauro Carvalho Chehab <mchehab@s-opensource.com> - 2017-05-19 03:50 +0200
  [PATCH 10/31] cputopology.txt: standardize document format Mauro Carvalho Chehab <mchehab@s-opensource.com> - 2017-05-19 03:50 +0200
  [PATCH 02/31] bt8xxgpio.txt: standardize document format Mauro Carvalho Chehab <mchehab@s-opensource.com> - 2017-05-19 03:50 +0200
  [PATCH 15/31] DMA-API-HOWTO.txt: standardize document format Mauro Carvalho Chehab <mchehab@s-opensource.com> - 2017-05-19 03:50 +0200
  [PATCH 11/31] crc32.txt: standardize document format Mauro Carvalho Chehab <mchehab@s-opensource.com> - 2017-05-19 03:50 +0200
  [PATCH 20/31] eisa.txt: standardize document format Mauro Carvalho Chehab <mchehab@s-opensource.com> - 2017-05-19 03:50 +0200
  [PATCH 14/31] DMA-API.txt: standardize document format Mauro Carvalho Chehab <mchehab@s-opensource.com> - 2017-05-19 03:50 +0200

csiph-web