Method of Offloading Cyclic Redundancy Check on Portions of a Packet

• US 20160337083A1
• Filed: 05/15/2015
• Published: 11/17/2016
• Est. Priority Date: 05/15/2015
• Status: Active Grant

• Current Assignee: NXP USA, Inc. (NXP Semiconductors NV)
• Original Assignee: Freescale Semiconductor, Inc. (NXP Semiconductors NV)
• Inventors: Englert, Eric, Marchand, Bernard, Pillar, John F.
• Granted Patent: US 9,680,605 B2
• Time in Patent Office: Days
• US Class Current: 1/1
• CPC Class Codes: H04L 1/0061 Error detection codes

Abstract

A method and apparatus are provided for computing a CRC value for a packet containing a data stream with a modified data unit data and one or more additional data units extending to the end of the data stream by computing a first CRC value from the one or more additional data units, computing a second CRC value from the modified data unit, adjusting the second CRC value based on a shift length equal to a distance of the one or more additional data units to compute a perspective shifted second CRC value by using fixed number of distance lookup table operations, and generating an updated CRC value from the first CRC value and perspective shifted second CRC value, thereby avoiding recalculating a complete CRC value based on an entirety of the modified data stream.

Claims

1. A method comprising:

receiving a packet from a network over one or more network interfaces, wherein the packet comprises;

an original data stream with an original data unit and one or more additional data units extending to the end of the original data stream, and

an original cyclical redundancy check (CRC) value computed from the original data stream;

inserting a modified data unit into the packet in place of the original data unit to generate a modified data stream;

generating a first CRC value from the one or more additional data units;

generating a second CRC value from the modified data unit;

adjusting the second CRC value based on a shift length equal to a distance of the one or more additional data units to generate a perspective shifted second CRC value by using fixed number of distance lookup table operations; and

generating an updated CRC value from the first CRC value and perspective shifted second CRC value, thereby avoiding recalculating a complete CRC value based on an entirety of the modified data stream.

2. The method of claim 1, where generating the first CRC value comprises computing a remainder of a CRC polynomial division of the one or more additional data units.

3. The method of claim 1, where generating the second CRC value comprises computing a remainder of a CRC polynomial division of the modified data unit.

4. The method of claim 1, where adjusting the second CRC value comprises:

accessing a single distance lookup table with the shift length to a generate a matrix of term enable values; and

applying the matrix of term enable values to an XOR logic circuit to compute the perspective shifted second CRC value, thereby generating the perspective shifted second CRC value using a single distance lookup table operation.

5. The method of claim 1, where adjusting the second CRC value comprises:

sequentially accessing n distance lookup tables with sequential portions of the shift length to a generate a matrix of term enable values; and

applying the matrix of term enable values to an XOR logic circuit to compute the perspective shifted second CRC value, thereby generating the perspective shifted second CRC value using n distance lookup table operations, where n is a power of 2.

6. The method of claim 1, further comprising:

generating a third CRC value from the original data unit;

adjusting the third CRC value based on a shift length equal to a distance of the one or more additional data units to compute a perspective shifted third CRC value by using fixed number of distance lookup table operations.

7. The method of claim 6, further comprising removing a contribution of the original data unit from the original CRC value by applying an inverse of the perspective shifted third CRC value to the original CRC value with an XOR operation.

8. The method of claim 1, where generating the updated CRC value comprises applying the perspective shifted second CRC value to the original CRC value with an XOR operation.

9. A network device comprising:

a memory that stores a packet comprising a data stream with a first data unit and one or more additional data units extending to the end of the data stream; and

CRC offload hardware circuitry comprising;

first CRC computation circuitry that produces a first CRC value from the first data unit,

projection circuitry configured to adjust the first CRC value based on a shift length equal to a distance of the one or more additional data units to compute a perspective shifted first CRC value by using fixed number of distance lookup table operations,

second CRC computation circuitry that produces a second CRC value from the one or more additional data units, and

XOR logic for combining perspective shifted first CRC value and second CRC value to generate a CRC value for the data stream, thereby avoiding recalculating a complete CRC value based on an entirety of the data stream.

10. The network device of claim 9, further comprising processing circuitry for generating the data stream by inserting the first data unit into the packet in place of an original data unit, the processing circuitry being in electrical communication with the memory and CRC offload hardware circuitry.

11. The network device of claim 9, further comprising a forwarding component that updates the data stream with the CRC value and outputs the packet to a network via one or more network interfaces.

12. The network device of claim 9, where the first CRC computation circuitry comprises circuitry for computing a remainder of a CRC polynomial division of the first data unit.

13. The network device of claim 9, where the second CRC computation circuitry comprises circuitry for computing a remainder of a CRC polynomial division of the one or more additional data units.

14. The network device of claim 9, where the projection circuitry comprises:

a distance lookup table for generating a matrix of term enable values in response to the shift length; and

an XOR logic circuit connected to receive the first CRC value and the matrix of term enable values to compute the perspective shifted first CRC value by using a single distance lookup table operation.

15. The network device of claim 9, where the projection circuitry comprises:

a plurality of distance lookup tables, each for generating a matrix of term enable values in response to sequential portions of the shift length; and

an XOR logic circuit connected to receive the first CRC value and the matrix of term enable values to compute the perspective shifted first CRC value by using a fixed number of distance lookup table operations.

16. The network device of claim 10, further comprising:

third CRC computation circuitry that produces a third CRC value from the original data unit, and

projection circuitry configured to adjust the third CRC value based on a shift length equal to a distance of the one or more additional data units to compute a perspective shifted third CRC value by using fixed number of distance lookup table operations.

17. The network device of claim 16, where the XOR logic is configured to remove a contribution from the original data unit to an original CRC value by applying an inverse of the perspective shifted third CRC value to the original CRC value with an XOR operation.

18. The network device of claim 9, where CRC offload hardware circuitry performs Layer 1 or Layer 2 operations of a network communications protocol.

19. The network device of claim 16, where the projection circuitry comprises one or more distance lookup tables for storing pre-computed term enable values that are loaded into gates of an XOR logic circuit in response to the shift length to compute the perspective shifted first CRC value by using a fixed number of distance lookup table operations.

20. The network device of claim 9, further comprising one or more network interfaces for receiving an original packet;

wherein the memory stores the original packet comprising;

an original data stream with an original data unit and one or more additional data units extending to the end of the original data stream, and

an original cyclical redundancy check (CRC) value computed from the original data stream.