US 6,820,228 B1Granted

Fast cyclic redundancy check (CRC) generation

AssigneeNetwork Elements, Inc.

InventorRichard B. Keller

Life of this patent

Estimating the term…

Loading patent…

Abstract

A CRC generation unit includes a number of CRC calculation assemblies to be selectively employed to incrementally calculate a CRC value for a first sequence of N data bytes. The calculation is iteratively performed, one iteration at a time. Further, the selection of the CRC calculation assemblies is made in accordance with the group size of each of a number of data word groups of the N data bytes. In one embodiment, the CRC calculation assemblies include a first assembly for incrementally calculate the CRC value for an iteration, whenever the group size is n/2 bytes or less for the iteration, and a second assembly for incrementally calculate the CRC value for an iteration, whenever the group size is more than n/2 bytes for the iteration. In one embodiment, the CRC generation unit is a shared resource to multiple network traffic flow processing units of a network traffic routing IC.

Claims27

Dependent claims

An apparatus comprising:

a data word extractor to successively extract a first plurality of data word groups from a stream of input data, one data word group at a time, with each extracted data word group having a group size of at most n bytes, where n is an integer;
a plurality of CRC calculation assemblies coupled to the data word extractor to be selectively employed to incrementally calculate a CRC value for the first plurality of data word groups, the calculation being iteratively performed, one iteration at a time, and for each iteration, the selection of the CRC calculation assemblies being made in accordance with the group size of the data word group extracted for the iteration;
a plurality of storage elements correspondingly coupled to the plurality of CRC calculation assemblies to correspondingly store the results generated by the corresponding ones of the CRC calculation assemblies for one iteration of the iterative calculation;
and
a plurality of selectors coupled to storage elements and the plurality of CRC calculation assemblies to selectively re-circulate one of the stored results back to the selected one of the CRC calculation assemblies for the next iteration of calculation, and to selectively output one of the stored results as the calculated CRC value at the end of the iterative calculation.

2 more elements

A method comprising:

successively extracting a first plurality of data word groups from a stream of input data, one data word group at a time, with each extracted data word group having a group size of at most n bytes, where n is an integer;
selectively employing a plurality of CRC calculation assemblies coupled to the data word extractor to incrementally calculate a CRC value for the first plurality of data word groups, with the calculation being iteratively performed, one iteration at a time, and for each iteration, selecting the CRC calculation assemblies in accordance with the group size of the data word group extracted for the iteration;
correspondingly storing the results generated by the plurality of CRC calculation assemblies for one iteration of the iterative calculation into a plurality of storage elements;
and
selectively re-circulating one of the stored results back to the selected one of the CRC calculation assemblies for the next iteration of calculation, and selectively outputting one of the stored results as the calculated CRC value at the end of the iterative calculation.

2 more elements

An apparatus comprising:

a plurality of processing units to correspondingly process a plurality of network traffic flows;
and
a shared CRC generation block coupled to the processing units to alternately generate a CRC value for a data block of a selected one of the network traffic flows, the shared CRC generation block including at least one CRC generation unit to iteratively generate a first CRC value for the data block of the selected one of the network traffic flows, the at least one CRC generation unit including a plurality of CRC calculation assemblies to be selectively employed to incrementally calculate a CRC value for a first plurality of data word groups, the calculation being iteratively performed, one iteration at a time, and the selection of the CRC calculation assemblies for the various iterations being made in accordance with group sizes of extracted data word groups of the first plurality data words for the various iterations.

Dependencies are inferred from the claim text.