Author |
Message |
Yves Tchap #1 / 6
|
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 |
|
|
Allan Herrima #2 / 6
|
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 |
|
|
Mike Tresele #3 / 6
|
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 |
|
|
Allan Herrima #4 / 6
|
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 |
|
|
Chris Rosewar #5 / 6
|
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 |
|
|
Allan Herrima #6 / 6
|
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 |
|
|
|