Subject: CRC32C code -- please check

From: Luben Tuikov <[email-masked]>
Date: Sat, 24 Nov 2001 00:10:56 -0800 (PST)

Here is some C code at the end, the draft quoted and my
notes alongside it.

Please tell me where and what is wrong with the
interpretation, logic, etc.

> Padding bytes, when present, in a segment covered by a
> CRC, should be set to 0 and are included in the CRC. The
> CRC should be calculated as follows:
>
> - data are assumed to be in the numbering order that
appears
>   in the draft - start with byte 0 bit 0 continue byte 1
bit
>   0 etc. (Big Endian on bytes / Little Endian on bits)

Ok. The code presented satisfies this requirement.  I swap
the bits in the bytes on the fly.

Please note that we DO NOT have to swap the bits in the
last
4 bytes representing the CRC. This is clearly specified in
the draft.

Please also note that the draft doesn't specify how the
data
is to be transmitted, it only specifies how to build M(x),
i.e. MSB(lsb).

> - the CRC register is initialized with all 1s (equivalent
to 
>   complementing the first 32 bits of the message) 

Ok. The code also satisfies this requirement. In fact this
has no significance to the algorithm and R(x), if the
_same_
algorithm is used in both the sender and the receiver. As
the draft says, this just complements the first 32 bits of
the message, e.g. imagine the first 32 bits of the message
were already 1's.

> - the n PDU bits are considered coefficients of a
polynomial 
>   M(x) of order n-1, with bit 0 of byte 0 being x^(n-1) 

Ok.

> - the polynomial is multiplied by x^32 and divided by
G(x)- the 
>   generator polynomial - producing a remainder R(x) of
degree <= 
>   31 
> - the coefficients of R(x) are considered a 32 bit
sequence 

So, here we get M'(x) = x^32 * M(x). Getting R(x) is
trivial.  So we have:

   M'(x) = Q(x)*G(x) + R(x) = Q(x)*G(x) - R(x),         (1)

since plus is same as minus in modulo 2 arithmetic.

> - the bit sequence is complemented and the result is the
CRC 

Now, from boolean logic we know that b XOR 1 = ~b, then,

  ~R(x) = R(x) XOR I(x) = R(x) + I(x)                   (2)

where I(x) is a polynomial of the same degree as R(x) and
whose coefficients are all equal to 1. So, to get M''(x)
which we send we have:

  M''(x) = M'(x) + ~R(x)                   (draft)
         = Q(x)*G(x) - R(x) + R(x) + I(x)  (using (1) and
(2))
         = Q(x)*G(x) + I(x).

or succinctly,

  M''(x) = Q(x)*G(x) + I(x),                         (3)

and this is the message which we send.  On the other end we
get M''(x), assuming there was no noise, and all
link/TCP/Ethernet transformations are transparent for the
sender and the receiver.

> - after the last bit of the original segment the CRC bits
are 
>   transmitted with x^31 first followed by x^30 etc. (
whenever 
> examples are given the value to be specified in examples 
> follows the same rules of representation as the rest of
this 
> document) 

Ok.

> - a receiver of a "good" segment (data or header) built
using 
>   the generator 0x11edc6f41 will end-up having in the CRC

>   register the value 0x1c2d19ed (this a register value
and not a 
>   word as outlined in this draft)

Ok, so the receiver got M''(x) assuming no noise.

  M''(x) = Q(x)*G(x) + I(x).            (this is (3))

Now we work the algorithm again: ..., find the remainder:
Clearly, from (3) the remainder of M''(x) modulo G(x) is
I(x).

Then we complement the value as per the draft:

  ~I(x) = 0.

And we end up with remainder 0.

Now let A(x) be the polynomial represented by 0x1c2d19ed.
Then, we can add A(x) to M''(x) to get:

  M'''(x) = Q(x)*G(x) + I(x) + A(x)      (from (3))
          = Q(x)*G(x) + ~A(x).           (from (2))

Now we send M'''(x), we receive M'''(x), and we work the
algorithm again. Clearly the remainder is ~A(x) and
performing the final complement we get:

  ~~A(x) = A(x), which is 0x1c2d19ed.

So then I can just go ahead and send M'''(x),
since iSCSI is expecting to get A(x) as a remainder.

The C code:
---------cut-here--------------
/*
  crc32c.c -- Implement CRC32C: 32 bit CRC of the
polynomial
              represented by 0x11EDC6F41.

  Copyright (C) 2001 Splentec Ltd.
*/			    
#include <netinet/in.h>
#include <linux/types.h>
#include <stdio.h>

#define  SAMPLE_SIZE   28
#define  BIT(v, bit)   ((v) & (((typeof ((v))) 1) <<
(bit)))

const uint32_t Poly  = 0x1edc6f41UL;
const uint32_t Magic = 0x1c2d19edUL;

uint32_t table[256];

/* 28 bytes + 4 bytes for the CRC */
uint8_t  zero[SAMPLE_SIZE+4];
uint8_t  ones[SAMPLE_SIZE+4];
uint8_t  incs[SAMPLE_SIZE+4];
uint8_t  decs[SAMPLE_SIZE+4];

int      test_packet(uint8_t *packet, size_t size, uint32_t
(*crc_func)(uint8_t *, size_t));
int      calc_table(uint32_t *table, uint32_t poly);
uint32_t crc(uint8_t *p, size_t size);
uint32_t crc_force(uint8_t *p, size_t size);
static inline uint8_t  mirror8(uint8_t v);

/* -------------------------------------------------- */

int main()
{
	uint32_t i;

	printf("Making the samples...\n");
	for (i = 0; i < SAMPLE_SIZE; i++) {
	        ones[i] = 0xFF;
		incs[i] = i;
		decs[i] = 0x1f - i;
	}
	
	/* -------------------------------------------------- */

	printf("Generating the table...\n");
	calc_table(table, Poly);
/*
	for (i = 0; i < 256; i++)
		printf("0x%08xU%s", table[i], (i % 4) == 3 ? ",\n" : ",
");
*/		

	/* -------------------------------------------------- */
	printf("Testing...with table\n");

	test_packet(zero, SAMPLE_SIZE+4, crc);
	test_packet(ones, SAMPLE_SIZE+4, crc);
	test_packet(incs, SAMPLE_SIZE+4, crc);
	test_packet(decs, SAMPLE_SIZE+4, crc);

	/* -------------------------------------------------- */
	printf("Testing...without table\n");

	test_packet(zero, SAMPLE_SIZE+4, crc_force);
	test_packet(ones, SAMPLE_SIZE+4, crc_force);
	test_packet(incs, SAMPLE_SIZE+4, crc_force);
	test_packet(decs, SAMPLE_SIZE+4, crc_force);

	return 0;	
} /* end main() */

/* -------------------------------------------------- */

/* test an augmented packet
 */
int test_packet(uint8_t *packet, size_t size, uint32_t
(*crc_func)(uint8_t *, size_t))
{
	uint32_t r;

	r = crc_func(packet, size);

	/* Now here we can form M'''(x) by doing the following:

	   r ^= Magic;

	*/
	
	*((uint32_t *)(packet + SAMPLE_SIZE)) = htonl(r);
	printf("packet %p has CRC %#x -> sending -> ", packet, r);

	/* The packet is sent and received on the other end.
	   Then we process it:
	*/
	
	r = crc_func(packet, size);
	printf("packet has CRC %#x\n", r);

	/* zero out the CRC space for later testing with no table
lookup */
	packet[SAMPLE_SIZE]
		= packet[SAMPLE_SIZE+1]
		= packet[SAMPLE_SIZE+2]
		= packet[SAMPLE_SIZE+3] = 0;

	return 0;
} /* end test_packet() */

/* -------------------------------------------------- */

int calc_table(uint32_t *table, uint32_t poly)
{
	register uint32_t crc, i;
	
	for (i = 0; i < 256; i++) {
		crc = i << 24;
		crc = BIT(crc, 31) ? ((crc<<1)^poly) : (crc<<1); /* 0 */
		crc = BIT(crc, 31) ? ((crc<<1)^poly) : (crc<<1); /* 1 */
		crc = BIT(crc, 31) ? ((crc<<1)^poly) : (crc<<1); /* 2 */
		crc = BIT(crc, 31) ? ((crc<<1)^poly) : (crc<<1); /* 3 */
		crc = BIT(crc, 31) ? ((crc<<1)^poly) : (crc<<1); /* 4 */
		crc = BIT(crc, 31) ? ((crc<<1)^poly) : (crc<<1); /* 5 */
		crc = BIT(crc, 31) ? ((crc<<1)^poly) : (crc<<1); /* 6 */
		crc = BIT(crc, 31) ? ((crc<<1)^poly) : (crc<<1); /* 7 */
		table[i] = crc;
        }
	
	return 0;
} /* end calc_table() */

/* -------------------------------------------------- */

/* p points to an augmented message, i.e.
   32 bits have been added at the end and set to 0.

   The last 4 bytes are never mirrored since the draft
   is clear on that: mirror only when building
   the polynomial, and send the CRC 31 bit first,
   then 30, etc.   
*/
uint32_t crc(uint8_t *p, size_t size)
{
	uint32_t r = ~((uint32_t) 0UL);
	uint8_t mp;

	for ( ; size-- > 0; p++) {
		/* do not mirror CRC code! (last 4 bytes) */
		mp = (size > 4) ? mirror8(*p) : *p;
		r = ((r << 8) | mp) ^ table[r >> 24];
	}

	return ~r;
} /* end crc() */

/* -------------------------------------------------- */

/* p points to an augmented message, i.e.
   32 bits have been added at the end and set to 0.

   The last 4 bytes are never mirrored since the draft
   is clear on that: mirror only when building
   the polynomial, and send the CRC 31 bit first,
   then 30, etc.
*/
uint32_t crc_force(uint8_t *p, size_t size)
{
	uint32_t r = ~((uint32_t) 0UL), t;
	uint8_t  mp;
	int i;

	for ( ; size-- > 0; p++) {
		/* do not mirror CRC code (last 4 bytes) */
		mp = (size > 4) ? mirror8(*p) : *p;
		for (i = 7; i >= 0; i--) {
			t = r;
			r = (r << 1) | (BIT(mp, i) >> i);
			if (BIT(t, 31))
				r ^= Poly;
		}
	}

	return ~r;
} /* end crc_force() */

/* -------------------------------------------------- */

static inline uint8_t mirror8(uint8_t v)
{
	return    ((0x80 & v) >> 7)
		| ((0x40 & v) >> 5)
		| ((0x20 & v) >> 3)
        	| ((0x10 & v) >> 1)
		| ((8 & v) << 1)
		| ((4 & v) << 3)
		| ((2 & v) << 5)
		| ((1 & v) << 7);
} /* end mirror8() */

/* -------------------------------------------------- */

---------------------cut-here----------------------

Thanks in advance,
Luben

=====
--

__________________________________________________
Do You Yahoo!?
Yahoo! GeoCities - quick and easy web site hosting, just $8.95/month.
http://geocities.yahoo.com/ps/info1

---

From: Paul Koning <[email-masked]>
Date: Mon, 26 Nov 2001 10:12:10 -0500 (EST)

>>>>> "Luben" == Luben Tuikov <[email-masked]> writes:

 Luben> Here is some C code at the end, the draft quoted and my notes
 Luben> alongside it. ...

 Luben> So, here we get M'(x) = x^32 * M(x). Getting R(x) is trivial.
 Luben> So we have:

 Luben> M'(x) = Q(x)*G(x) + R(x) = Q(x)*G(x) - R(x), (1)

 Luben> since plus is same as minus in modulo 2 arithmetic.

 >> - the bit sequence is complemented and the result is the
 Luben> CRC

 Luben> Now, from boolean logic we know that b XOR 1 = ~b, then,

 Luben> ~R(x) = R(x) XOR I(x) = R(x) + I(x) (2)

 Luben> where I(x) is a polynomial of the same degree as R(x) and
 Luben> whose coefficients are all equal to 1. So, to get M''(x) which
 Luben> we send we have:

 Luben> M''(x) = M'(x) + ~R(x) (draft) = Q(x)*G(x) - R(x) + R(x) +
 Luben> I(x) (using (1) and (2)) = Q(x)*G(x) + I(x).

 Luben> or succinctly,

 Luben> M''(x) = Q(x)*G(x) + I(x), (3)

 Luben> and this is the message which we send. 

Not quite.  Your M' is taken from M by complementing the first 32
bits and appending 32 zeroes.  That's what you feed into the CRC
calculation -- but what you transmit has the original (uncomplemented)
first 32 bits.

 Luben> On the other end we
 Luben> get M''(x), assuming there was no noise, and all
 Luben> link/TCP/Ethernet transformations are transparent for the
 Luben> sender and the receiver. ...

 Luben> Ok, so the receiver got M''(x) assuming no noise.

 Luben> M''(x) = Q(x)*G(x) + I(x).  (this is (3))

 Luben> Now we work the algorithm again: ..., find the remainder:
 Luben> Clearly, from (3) the remainder of M''(x) modulo G(x) is I(x).

 Luben> Then we complement the value as per the draft:

 Luben> ~I(x) = 0.

 Luben> And we end up with remainder 0.

I think I see the problem.

In CRC generation, you process the message (M).

In CRC checking, there are two approaches:

1. You process M and compare the 4 bytes that follow (the CRC) with
what you computed.  This is fine, if you know ahead of time where M
ends. 

2. If you don't know where M ends ahead of time (as in the Ethernet
MAC layer) or you simply prefer to process the whole received message,
you run everything including the received CRC through the CRC
algorithm.  Note that the string processed in this case is 4 bytes
longer than in case (1), because it includes the CRC.  That's what you
described, but I believe you missed a step.

The CRC algorithm says: take the message (M'' in this case) and
multiply by x^32, then divide by the CRC polynomial.  You missed the
multiply.   In other words, you should have:

	    (M''(x)*x^32) mod G(x)
rather than simply
            M''(x) mod G(x)

and that is *not* zero.  I haven't done the math but I expect that you
will find the answer to be the non-zero constant that appears in the
spec. 

Ethernet works the same way, except for a change in the polynomial.
You suggested earlier that Ethernet is using a non-standard algorithm
because it comes up with a non-zero remainder at the receive end.
That is not the case.

You should not need any fudge factors to make the answer come out
according to the spec if you get the algorithm right...

	  paul