parallel CRC and ragged words

[Matt]

I've been looking over the following post concerning parallel crc
computation and how to handle a multi-byte parallel bus where the data
can end in any 8b position:
http://groups.google.com/group/comp.lang.vhdl/browse_frm/thread/587b14d0fc43dbc1

All of the identities Allan calls out make perfect sense, except when
I try
#5.) If the CRC register is initialised to zero,
CRC(A & B) = CRC(CRC(A) & B))

If I use some some test code, and the easics crc generator (http://
www.easics.com/webtools/crctool) :

reg [31:0]a = 32'haaaaaaaa;
reg [31:0]b = 32'hbbbbbbbb;

@(posedge clk) crca = nextCRC32_D64({{32{1'b0}},a}, {32{1'b0}});
@(posedge clk) crcab = nextCRC32_D64({a,b}, {32{1'b0}});
@(posedge clk) crcab2 = nextCRC32_D64({crca,b}, {32{1'b0}});

where nextCRC32_D64 is the easics CRC function, arguments are (data,
lfsr state)

I do not get CRC({A, B}) = CRC({CRC(A) , B}))

I'm replacing the &'s with {}'s, since this originally came from a
vhdl group, and I'm assuming he's referring to the vhdl concat
operator.

What I actually get is
CRC(A) = 85f89652
CRC({a,b}) = 8a0c00ba
CRC({CRC(A),b} = cae34aea

I'm sure I must have missed something along the way, but I don't know
what it is.


Any help or direction you could provide would be greatly appreciated.

Thank you

[glen herrmannsfeldt]

In comp.lang.verilog Matt <mapla...@gmail.com> wrote:
> I've been looking over the following post concerning parallel crc
> computation and how to handle a multi-byte parallel bus where the data
> can end in any 8b position:
> http://groups.google.com/group/comp.lang.vhdl/browse_frm/thread/587b14d0fc43dbc1

I haven't thought about the wide parallel CRC for a while, but...

> All of the identities Allan calls out make perfect sense,
> except when I try

> #5.) If the CRC register is initialised to zero,
> CRC(A & B) = CRC(CRC(A) & B))

My guess is that this is the case for the beginning of the
calculation, where some bytes are zeroed out.

With most CRC functions, CRC(0)==0, which my guess is what
he is using. Note the condition that it be initialized to zero.
That only matters at the beginning.

But for just this reason, most CRC's do not initialize to zero,
as it will give the same result for missing X'00' bytes
at the beginning.

As far as doing it for odd byte combinations, my first thought
is to compute it through the end, and then undo the last bytes.
The operation has an inverse, so you can cancel out the bytes at
the end that you don't want. You might be able to do that at
the beginning, too. Keep the complicated logic outside the
critical path.

-- glen

[Matt]

Hi Glen,

Yes, the idea is to rotate the unwanted bits following the frame (set
to zero) to the front of the word. The CRC initialized with 0 won't
change as a result. If I understand Allen correctly, he then goes on
to state that you shift in the previous word's CRC (thinking serially,
even though it's a parallel operation), followed by the last few data
bytes of the frame. This is where I'm having the problem. I assume
the intent is to load the lfsr with the old crc data, and then shift
in the remaining data bytes, but it doesn't appear to work the way I'm
attempting to do it.

What's the inverse operation you mentioned?

Thanks,

-- Matt


On Feb 8, 5:24 pm, glen herrmannsfeldt <g...@ugcs.caltech.edu> wrote:

> In comp.lang.verilog Matt <maplant...@gmail.com> wrote:
>
> > I've been looking over the following post concerning parallel crc
> > computation and how to handle a multi-byte parallel bus where the data
> > can end in any 8b position:

> >http://groups.google.com/group/comp.lang.vhdl/browse_frm/thread/587b1...

[Mark Curry]

In article <1953c27e-95f4-4be6...@vd8g2000pbc.googlegroups.com>,

Matt <mapla...@gmail.com> wrote:
>I've been looking over the following post concerning parallel crc
>computation and how to handle a multi-byte parallel bus where the data
>can end in any 8b position:
>http://groups.google.com/group/comp.lang.vhdl/browse_frm/thread/587b14d0fc43dbc1
>
>All of the identities Allan calls out make perfect sense, except when
>I try
>#5.) If the CRC register is initialised to zero,
>CRC(A & B) = CRC(CRC(A) & B))
>
>If I use some some test code, and the easics crc generator (http://
>www.easics.com/webtools/crctool) :

<snip>

While not directly answering your question, I'll add my 2 cents.

I commented on this before, but I do it again - I really don't like tools such as
those on easics web site. CRCs in verilog or VHDL are dead-nuts simple. Using
those tools leads to more confusion and obtuse code than not.

A great reference for crcs is:
http://www.ross.net/crc/download/crc_v3.txt

For HW guys - don't read past chapter 8. After chapter 8, the doc is all about
optimizing the calcs in SW. For HW, it's really simple - just code up the
algorithm shown in chapter 8, and put a for loop in it for the number of bits
you need. Done.

Now you know that basics, there's two references that can help for the
special cases you've got:

J. Satran, D. Sheinwald, and I. Shimony, "Out of Order Incremental CRC Computation"
IEEE Transactions on Computers, Vol. 54, No. 9, September 2005.

and

M. Walma, "Pipelined Cycle Redundancy Check (CRC) Calculation". Intel Corporation
(My paper is lacking a clear reference, but it looks to be from some
IEEE doc published in 2007)

Both these papers have some great ideas to do creative things with CRCs, including
similar to what you're trying to do.

Regards,

Mark

[Allan Herriman]

The answer to your question is that the statement #5 I made isn't
actually correct (which is another way of saying that it is wrong).

It's *almost* right, but there's something wrong in the detail. I didn't
discover this until a co-worker tried to implement a wide CRC following
those guidelines and came unstuck, just as you did.

In hand-waving terms, statement #5 says that you can break up the
calculation into two parts, which really helps at the end of a packet.

I'll look up some actual code (that works) to see if I can find the error.

Regards,
Allan

[Allan Herriman]

Got it.

Here's what I originally posted:

#5.) If the CRC register is initialised to zero,
CRC(A & B) = CRC(CRC(A) & B))

I'm inserting CRC(A) 32 bits too soon. Gah!

Instead of "CRC(A) & B" it really should say that the CRC(A) gets xored
with the first 32 bits of B, then we take the CRC of that result.

I think B might need to be at least 32 bits long, i.e. it will be the
last two words of the packet.

(Apologies to the c.l.verilog readers: ampersand (&) is the VHDL
concatenation operator.)

Regards,
Allan

[Matt]

Hi Allan,

Thanks for the correction! I tried your update, and was able to
generate a correct CRC on a 64b bus for a packet that ended on a 32b
boundary

i.e.

...
64'h2223242526272829;
64'h2a2b2c2d00000000; // last 32b invalid data

However I've been unable to get a correct crc for a packet ending in
any arbitrary position, like:

...
64'h2a2b2c2d2e2f3031;
64'h3200000000000000; // last 56b invalid data

xor'ing the previous crc with the last32b (if you pull from the
previous word, so 32'h2f303132) doesn't work; nor does it work if you
try to xor an 8b chunk of the previous crc with the remaining valid 8b
of data (if proceeded by 0's and the last crc is initialized to 0's).

Is there something else I should be doing?

Thanks for your help,

-- Matt

[Allan Herriman]

I think it's meant to work like this:

64'h1a1b1c1d1e1f2021;
64'h2223242526272829; // end of 'A'
---------------------
64'h2a2b2c2d2e2f3031; // start of 'B'

64'h3200000000000000; // last 56b invalid data

Lets assume that the CRC register was FFFF after the 'A' calculation.
Take that value, xor it into the start of the 'B' contents
(i.e. the 2a2b2c2d part).

This gives the following:

64'h d5d4d3d22e2f3031; // start of 'B'
64'h 32xxxxxxxxxxxxxx; // last 56b invalid data

Then rotate it so that the end is aligned:

64'hxxxxxxxxxxxxxxd5;
64'hd4d3d22e2f303132;

and zero out the unwanted leading octets:

64'h00000000000000d5;
64'hd4d3d22e2f303132;

Then take the CRC.

Sorry if I'm a bit rusty; I haven't done one of these at this level for
about a decade.


Regards,
Allan

[Matt]

Allan,

I looks like that may have worked. Thanks for all of your help!

BTW, Mark, I did grab a copy of that "Pipelined Cycle Redundancy Check
(CRC) Calculation" paper you mentioned. Very interesting. I'm a
little confused about where the G matrix comes from and how to
generate subsequent G^P's. I've generated their H up to 16384 and
matched that matrix.

Cheers,

-- Matt

-- Matt

[Mark Curry]

In article <a9dbb914-48ad-4bcc...@o4g2000pbc.googlegroups.com>,

Matt <mapla...@gmail.com> wrote:
>
>BTW, Mark, I did grab a copy of that "Pipelined Cycle Redundancy Check
>(CRC) Calculation" paper you mentioned. Very interesting. I'm a
>little confused about where the G matrix comes from and how to
>generate subsequent G^P's. I've generated their H up to 16384 and
>matched that matrix.

My goals in using the paper were a little different - I didn't need
the G matrix, but looks to me it's just the inverse operation of H.
H allows you to "shift N zeros" onto the previous CRC state.
G allows you to unshift N zeros back off. In your case, you'd use
it like - always assume you're shifting through for the full 32 bits.
But, in the case of only 1 byte of the last 4 was valid, you need
to reverse the final shift by three bytes. The G matrix allows
that.

I imagine you calculate it like H - calculate the matrix for one
bit unshift, then raise the matrix to the power of n for the other
bits.

--Mark