CRC32C code -- please check

[Luben Tuikov <ltuikov@yahoo.com>]

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