Ethernet CRC-32 
Author Message
 Ethernet CRC-32

Hi,
Has anyone implemented the Ethernet CRC-32 on a data bus wider than
8-bit, say 64-bit bus? I just want to know how you would efficiently
(minimal logic) handle the various situations when the end of frame
does not fit onto a 64-bit boundary?
Thanks in advance
Yves


Fri, 05 Aug 2005 01:49:59 GMT  
 Ethernet CRC-32

Quote:

>Hi,
>Has anyone implemented the Ethernet CRC-32 on a data bus wider than
>8-bit, say 64-bit bus?

Sure.  How else would the 10G Ethernet interfaces do it?

Quote:
> I just want to know how you would efficiently
>(minimal logic) handle the various situations when the end of frame
>does not fit onto a 64-bit boundary?

Ah yes, the ragged end word problem.  There are actually multiple ways
to solve this problem, and only you can work out which method is best
for you.  Note that the best solution for a CRC generator may not
necessarily be the best solution for a CRC checker, and vice-versa.

Ummm, I wrote a large post explaining all the methods in terms of
their implementations, but then I realised that I would be giving away
valuable IP and had to delete it.
So instead I'll tell you about the CRC properties you need to know to
work it out for yourself.

1. If the CRC register is initialised to zero, adding zeros before the
message doesn't change the value of the CRC.  (Note: this doesn't
apply to zeros *appended* to the message, in general.)
If you think of a CRC as a function, then
CRC("0000" & A) = CRC(A)
but
CRC(A & "0000") /= CRC(A), in general

2.  If the CRC register is initialised to zero, the CRC calculation is
linear, i.e. you can calculate it in multiple parts then XOR the
partial results together.  
CRC(A xor B) = CRC(A) xor CRC(B)

For example, A may be the full message with the last word set to all
zeros, and B may be the last word of the message (with zeros for the
previous words, but you don't have to calculate those, due to property
#1).

Think about how you would design a CRC generator that had separate
hardware for each of the 8 cases for the last word, and a mux to
select between the 8 results, and some extra hardware to combine it
with the CRC of the rest of the packet.  This might get rather big!

3.  Most CRC definitions (Ethernet included) specify that the CRC
register is initialised to all ones before the start of the message,
in order to make the system detect leading zero bits added by the
channel (property #1 again).
Initialising the register to all ones is equivalent to initialising
the register to all zeros and  *inverting the first N bits of the
message*.

So now it seems easy to deal with a "ragged start word" - just
initialise the CRC register to zero, zero out the leading unwanted
bytes in the bus, and invert the first 32 bits of wanted data on the
bus.

Think about how you would change a packet with a "ragged end word"
into a packet with a "ragged start word".  Hint: this isn't possible
on a checker, only a generator (or other system where you know the
packet length in advance).

4.  The CRC register will remain zero if it started at zero and the
input data is zero.  Surprisingly, the inverse is true:  The CRC
register will remain non-zero if it started non-zero and the input
data is zero.
The proof of that is a bit gnarly, but the result is simple enough to
use:
If we can arrange for the CRC register to be zero to indicate a
correct packet (including the incoming CRC), then the system
becomes insensitive to added trailing zeros (which could be the
unwanted bytes in the last word on your bus).
i.e.
(CRC(M) = 0) = (CRC(M & "0000") = 0)
Note that we can only tell whether the packet had an error; we lose
the actual value of the CRC, i.e. this is only useful in a checker,
not a generator.
So how do we arrange for the CRC register to be zero to indicate a
correct packet?  Well, (IIRC) all you have to do is invert the CRC
field in the incoming message.

I hope this helps (and I hope I didn't give away too much IP in this
post :).

Regards,
Allan.



Fri, 05 Aug 2005 03:38:37 GMT  
 Ethernet CRC-32

Quote:

> Has anyone implemented the Ethernet CRC-32 on a data bus wider than
> 8-bit, say 64-bit bus? I just want to know how you would efficiently
> (minimal logic) handle the various situations when the end of frame
> does not fit onto a 64-bit boundary?

I think you will find that the crc_shift routine I posted

(see google groups: vhdl crc_shift)

will actually work in parallel for any vector and poly width if you
simply remove the assertion stating otherwise.

You can handle the ragged last word with brute force,
with crc_shift cases for each possible parallel width,

or more subtly by using some of Mr. Herriman's insights.

    -- Mike Treseler



Sat, 06 Aug 2005 02:06:05 GMT  
 Ethernet CRC-32
On Mon, 17 Feb 2003 06:38:37 +1100, Allan Herriman

Quote:



>>Hi,
>>Has anyone implemented the Ethernet CRC-32 on a data bus wider than
>>8-bit, say 64-bit bus?

>Sure.  How else would the 10G Ethernet interfaces do it?

>> I just want to know how you would efficiently
>>(minimal logic) handle the various situations when the end of frame
>>does not fit onto a 64-bit boundary?

>Ah yes, the ragged end word problem.  There are actually multiple ways
>to solve this problem, and only you can work out which method is best
>for you.  Note that the best solution for a CRC generator may not
>necessarily be the best solution for a CRC checker, and vice-versa.

>Ummm, I wrote a large post explaining all the methods in terms of
>their implementations, but then I realised that I would be giving away
>valuable IP and had to delete it.
>So instead I'll tell you about the CRC properties you need to know to
>work it out for yourself.

>1. If the CRC register is initialised to zero, adding zeros before the
>message doesn't change the value of the CRC.  (Note: this doesn't
>apply to zeros *appended* to the message, in general.)
>If you think of a CRC as a function, then
>CRC("0000" & A) = CRC(A)
>but
>CRC(A & "0000") /= CRC(A), in general

>2.  If the CRC register is initialised to zero, the CRC calculation is
>linear, i.e. you can calculate it in multiple parts then XOR the
>partial results together.  
>CRC(A xor B) = CRC(A) xor CRC(B)

>For example, A may be the full message with the last word set to all
>zeros, and B may be the last word of the message (with zeros for the
>previous words, but you don't have to calculate those, due to property
>#1).

>Think about how you would design a CRC generator that had separate
>hardware for each of the 8 cases for the last word, and a mux to
>select between the 8 results, and some extra hardware to combine it
>with the CRC of the rest of the packet.  This might get rather big!

>3.  Most CRC definitions (Ethernet included) specify that the CRC
>register is initialised to all ones before the start of the message,
>in order to make the system detect leading zero bits added by the
>channel (property #1 again).
>Initialising the register to all ones is equivalent to initialising
>the register to all zeros and  *inverting the first N bits of the
>message*.

>So now it seems easy to deal with a "ragged start word" - just
>initialise the CRC register to zero, zero out the leading unwanted
>bytes in the bus, and invert the first 32 bits of wanted data on the
>bus.

>Think about how you would change a packet with a "ragged end word"
>into a packet with a "ragged start word".  Hint: this isn't possible
>on a checker, only a generator (or other system where you know the
>packet length in advance).

>4.  The CRC register will remain zero if it started at zero and the
>input data is zero.  Surprisingly, the inverse is true:  The CRC
>register will remain non-zero if it started non-zero and the input
>data is zero.
>The proof of that is a bit gnarly, but the result is simple enough to
>use:
>If we can arrange for the CRC register to be zero to indicate a
>correct packet (including the incoming CRC), then the system
>becomes insensitive to added trailing zeros (which could be the
>unwanted bytes in the last word on your bus).
>i.e.
>(CRC(M) = 0) = (CRC(M & "0000") = 0)
>Note that we can only tell whether the packet had an error; we lose
>the actual value of the CRC, i.e. this is only useful in a checker,
>not a generator.
>So how do we arrange for the CRC register to be zero to indicate a
>correct packet?  Well, (IIRC) all you have to do is invert the CRC
>field in the incoming message.

I forgot a really important identity:

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

e.g. B might be the last word of a packet, and A may be all words of
the packet except for the last one.

You could make a CRC generator that handles ragged end words with two
CRC generators: one that handles the complete words at the beginning
of the packet 'A' and one that handles the ragged end word 'B'.
The 'A' calculation should be straighforward; Mike's code should
handle it fine (we use similar behavioural code here that works quite
well at >> 10Gbps).
The 'B' calculation is more involved:
- concatenate the 32 bit CRC of A with the end word B to get a 96 bit
word with some unwanted trailing bytes.
- rotate the 96 bit word so that the unwanted bytes are now at the
leading end of the word.
- set the unwanted leading bytes to zero
- calculate the CRC of the 96 bit word.
- by using Properties #1 and #5, we now have the CRC of the full
packet.

I think this method may be much smaller than the one that has 8
separate CRCs for the last word and a mux (particularly for wide bus
widths), but you'll have to test that for yourself.

Regards,
Allan.



Sat, 06 Aug 2005 11:51:16 GMT  
 Ethernet CRC-32
Allan,

If I understand correctly, on the CRC Generator this method involves
shifting the data such that the end of packet is always aligned to a
occupy a whole bus word, introducing unused octets into the data bus
at the start of packet bus cycle.  Won't this cause a reduction in
bandwidth, especially when using very short packets?  The Checker
seems to have the same limitation, this time with unused octets on the
last bus cycle for a given packet.

Calyptech has a standard CRC32 Core that can calculate the CRC value
for a packet with no restrictions on its starting and ending octet
position in the data bus and no requirement to know the packet length
in advance.  The algorithm supports having one packet end and another
start on the same bus cycle, eliminating the need to bump up the clock
rate or duplicate the core to maintain full bandwidth under worst-case
conditions (ie shortest packets).  This can be used in either a
checker or generator, without introducing the inefficiency of unused
octets in the data bus.

cheers,
Chris

Quote:



> >Hi,
> >Has anyone implemented the Ethernet CRC-32 on a data bus wider than
> >8-bit, say 64-bit bus?

> Sure.  How else would the 10G Ethernet interfaces do it?

> > I just want to know how you would efficiently
> >(minimal logic) handle the various situations when the end of frame
> >does not fit onto a 64-bit boundary?

> Ah yes, the ragged end word problem.  There are actually multiple ways
> to solve this problem, and only you can work out which method is best
> for you.  Note that the best solution for a CRC generator may not
> necessarily be the best solution for a CRC checker, and vice-versa.

> Ummm, I wrote a large post explaining all the methods in terms of
> their implementations, but then I realised that I would be giving away
> valuable IP and had to delete it.
> So instead I'll tell you about the CRC properties you need to know to
> work it out for yourself.

> 1. If the CRC register is initialised to zero, adding zeros before the
> message doesn't change the value of the CRC.  (Note: this doesn't
> apply to zeros *appended* to the message, in general.)
> If you think of a CRC as a function, then
> CRC("0000" & A) = CRC(A)
> but
> CRC(A & "0000") /= CRC(A), in general

> 2.  If the CRC register is initialised to zero, the CRC calculation is
> linear, i.e. you can calculate it in multiple parts then XOR the
> partial results together.  
> CRC(A xor B) = CRC(A) xor CRC(B)

> For example, A may be the full message with the last word set to all
> zeros, and B may be the last word of the message (with zeros for the
> previous words, but you don't have to calculate those, due to property
> #1).

> Think about how you would design a CRC generator that had separate
> hardware for each of the 8 cases for the last word, and a mux to
> select between the 8 results, and some extra hardware to combine it
> with the CRC of the rest of the packet.  This might get rather big!

> 3.  Most CRC definitions (Ethernet included) specify that the CRC
> register is initialised to all ones before the start of the message,
> in order to make the system detect leading zero bits added by the
> channel (property #1 again).
> Initialising the register to all ones is equivalent to initialising
> the register to all zeros and  *inverting the first N bits of the
> message*.

> So now it seems easy to deal with a "ragged start word" - just
> initialise the CRC register to zero, zero out the leading unwanted
> bytes in the bus, and invert the first 32 bits of wanted data on the
> bus.

> Think about how you would change a packet with a "ragged end word"
> into a packet with a "ragged start word".  Hint: this isn't possible
> on a checker, only a generator (or other system where you know the
> packet length in advance).

> 4.  The CRC register will remain zero if it started at zero and the
> input data is zero.  Surprisingly, the inverse is true:  The CRC
> register will remain non-zero if it started non-zero and the input
> data is zero.
> The proof of that is a bit gnarly, but the result is simple enough to
> use:
> If we can arrange for the CRC register to be zero to indicate a
> correct packet (including the incoming CRC), then the system
> becomes insensitive to added trailing zeros (which could be the
> unwanted bytes in the last word on your bus).
> i.e.
> (CRC(M) = 0) = (CRC(M & "0000") = 0)
> Note that we can only tell whether the packet had an error; we lose
> the actual value of the CRC, i.e. this is only useful in a checker,
> not a generator.
> So how do we arrange for the CRC register to be zero to indicate a
> correct packet?  Well, (IIRC) all you have to do is invert the CRC
> field in the incoming message.

> I hope this helps (and I hope I didn't give away too much IP in this
> post :).

> Regards,
> Allan.



Mon, 08 Aug 2005 07:21:00 GMT  
 Ethernet CRC-32

Quote:

>Allan,

>If I understand correctly, on the CRC Generator this method involves
>shifting the data such that the end of packet is always aligned to a
>occupy a whole bus word, introducing unused octets into the data bus
>at the start of packet bus cycle.  Won't this cause a reduction in
>bandwidth, especially when using very short packets?  The Checker
>seems to have the same limitation, this time with unused octets on the
>last bus cycle for a given packet.

Yes, sure.  I understand that the OP's requirement is for 10GbE, so
the loss in bandwidth isn't an issue (since Ethernet wastes lots of
line bandwidth with preamble, interpacket gap, etc.)  You may have
been thinking of POS, etc. which allows a much greater packet rate for
a given bitrate.

Quote:
>Calyptech ...

[snip commercial plug]

I probably know about half the staff in the Calyptech Melbourne
office.  Say hi to them from me.

Regards,
Allan.

Quote:
>cheers,
>Chris




>> >Hi,
>> >Has anyone implemented the Ethernet CRC-32 on a data bus wider than
>> >8-bit, say 64-bit bus?

>> Sure.  How else would the 10G Ethernet interfaces do it?

>> > I just want to know how you would efficiently
>> >(minimal logic) handle the various situations when the end of frame
>> >does not fit onto a 64-bit boundary?

>> Ah yes, the ragged end word problem.  There are actually multiple ways
>> to solve this problem, and only you can work out which method is best
>> for you.  Note that the best solution for a CRC generator may not
>> necessarily be the best solution for a CRC checker, and vice-versa.

>> Ummm, I wrote a large post explaining all the methods in terms of
>> their implementations, but then I realised that I would be giving away
>> valuable IP and had to delete it.
>> So instead I'll tell you about the CRC properties you need to know to
>> work it out for yourself.

>> 1. If the CRC register is initialised to zero, adding zeros before the
>> message doesn't change the value of the CRC.  (Note: this doesn't
>> apply to zeros *appended* to the message, in general.)
>> If you think of a CRC as a function, then
>> CRC("0000" & A) = CRC(A)
>> but
>> CRC(A & "0000") /= CRC(A), in general

>> 2.  If the CRC register is initialised to zero, the CRC calculation is
>> linear, i.e. you can calculate it in multiple parts then XOR the
>> partial results together.  
>> CRC(A xor B) = CRC(A) xor CRC(B)

>> For example, A may be the full message with the last word set to all
>> zeros, and B may be the last word of the message (with zeros for the
>> previous words, but you don't have to calculate those, due to property
>> #1).

>> Think about how you would design a CRC generator that had separate
>> hardware for each of the 8 cases for the last word, and a mux to
>> select between the 8 results, and some extra hardware to combine it
>> with the CRC of the rest of the packet.  This might get rather big!

>> 3.  Most CRC definitions (Ethernet included) specify that the CRC
>> register is initialised to all ones before the start of the message,
>> in order to make the system detect leading zero bits added by the
>> channel (property #1 again).
>> Initialising the register to all ones is equivalent to initialising
>> the register to all zeros and  *inverting the first N bits of the
>> message*.

>> So now it seems easy to deal with a "ragged start word" - just
>> initialise the CRC register to zero, zero out the leading unwanted
>> bytes in the bus, and invert the first 32 bits of wanted data on the
>> bus.

>> Think about how you would change a packet with a "ragged end word"
>> into a packet with a "ragged start word".  Hint: this isn't possible
>> on a checker, only a generator (or other system where you know the
>> packet length in advance).

>> 4.  The CRC register will remain zero if it started at zero and the
>> input data is zero.  Surprisingly, the inverse is true:  The CRC
>> register will remain non-zero if it started non-zero and the input
>> data is zero.
>> The proof of that is a bit gnarly, but the result is simple enough to
>> use:
>> If we can arrange for the CRC register to be zero to indicate a
>> correct packet (including the incoming CRC), then the system
>> becomes insensitive to added trailing zeros (which could be the
>> unwanted bytes in the last word on your bus).
>> i.e.
>> (CRC(M) = 0) = (CRC(M & "0000") = 0)
>> Note that we can only tell whether the packet had an error; we lose
>> the actual value of the CRC, i.e. this is only useful in a checker,
>> not a generator.
>> So how do we arrange for the CRC register to be zero to indicate a
>> correct packet?  Well, (IIRC) all you have to do is invert the CRC
>> field in the incoming message.

>> I hope this helps (and I hope I didn't give away too much IP in this
>> post :).

>> Regards,
>> Allan.



Mon, 08 Aug 2005 11:36:57 GMT  
 
 [ 6 post ] 

 Relevant Pages 

1. Need PL1 CRC-16 or CRC-32 code

2. CRC-16, CRC-32 question/problem

3. CRC-16 and CRC-32 files wanted

4. 32-bit CRC Algorithm

5. crc-32 XFCN

6. Crc 16 and 32 bit 4 digit

7. 32 and/or 64 bit CRC code

8. 32 bit CRC

9. CRC-32 in Forth?

10. CRC-32

11. CRC-32 native code for DOS GForth 0.5.0

12. CRC-32

 

 
Powered by phpBB® Forum Software