Fast cyclic redundancy check (CRC) generation

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.

INFORMATION

DETAILED DESCRIPTION OF THE INVENTION

BRIEF DESCRIPTION OF DRAWINGS

The present invention will be described by way of exemplary embodiments, but not limitations, illustrated in the accompanying drawings in which like references denote similar elements, and in which:

FIG. 1 illustrates an overview of the present invention;

FIG. 2 illustrates an example of packet data alignment or the lack thereof;

FIG. 3 illustrates one of the fast CRC generators of FIG. 1 in further detail, in accordance with one embodiment;

FIGS. 4-illustrate the 8-5 bytes CRC Calculator of FIG. 3 in further detail, in accordance with two embodiments;

FIGS. 5-illustrate the 4-1 bytes CRC Calculator of FIG. 3 in further detail, in accordance with two embodiments; and

FIG. 6 illustrates an example routing device incorporated with the fast CRC generation teaching of the present invention.

DETAILED DESCRIPTION OF THE INVENTION

In the following description, various aspects of the present invention will be described. However, it will be apparent to those skilled in the art that the present invention may be practiced with only some or all aspects of the present invention. For purposes of explanation, specific numbers, materials and configurations are set forth in order to provide a thorough understanding of the present invention. However, it will also be apparent to one skilled in the art that the present invention may be practiced without the specific details. In other instances, well known features are omitted or simplified in order not to obscure the present invention. Further, the description repeatedly uses the phrase “in one embodiment”, which ordinarily does not refer to the same embodiment, although it may.

Overview

Referring now to FIG. 1, wherein an overview of the present invention is illustrated. As shown, data sender and data receiver are coupled to each other via communication link , over which data sender may send data, including associated CRC values, to data receiver . Both data sender and data receiver are equipped with fast CRC generator /of the present invention for generating CRC values for the data blocks being sent from data sender to data receiver . As will be described in more detail below, fast CRC generator /includes redundant circuit elements organized in accordance with a parallel architecture to allow various calculations to be performed in an overlapped and parallel manner. As a result, fast CRC generator /may generate CRC values of variable length data blocks, such as variable length packet data, efficiently. In fact, experience has shown that fast CRC generator /is sufficiently efficient to allow fast CRC generator /to be shared by as many as 64 collections of network traffic flow processing resources of an IC based gigabit Ethernet routing device, resulting in a substantial net reduction in real estate requirement (notwithstanding the duplication of certain elements to enable the overlapped and parallel computations).

Except for fast CRC generator /, data sender , data receiver and communication link are all intended to represent a broad range of data sending, data receiving and communication systems and/or components known in the art. Accordingly, except for fast CRC generator /, data sender , data receiver and communication link will not be otherwise further described.

Fast CRC Generator

FIG. 3 illustrates one of fast CRC generators /of FIG. 1 in further details, in accordance with one embodiment. As illustrated, each fast CRC generator /includes three CRC calculation assembly and accumulator pairs and , and , and and to facilitate overlapped CRC generation for two successive variable length series of data block groups. The CRC calculations are iteratively performed. Each fast CRC generator /further includes word extractor , and selectors and , complementing the three CRC calculation assembly and accumulator pairs. and , and , and and . The elements are coupled to each other as shown.

Word extractor is employed to extract data word groups from an input data stream. CRC calculation assembly and accumulator pair and is employed to incrementally calculate the CRC value for a series of data word groups, for an iteration, whenever the group size of the extracted data word group for the iteration is more than n/2 data bytes, where n is an integer. Each of CRC calculation assembly and accumulator pairs and , and and is employed to incrementally calculate the CRC value for a series of data word groups, for an iteration, whenever the group size of the extracted data word group for the iteration is n/2 data bytes or less.

Selector is employed to re-circulate an appropriate one of the accumulated calculation results stored in accumulator -to an appropriate one of calculation assemblies and -for the next iteration. At the end of the calculation, selector , in conjunction with selector , facilitates selection of one of the accumulated calculation results stored in accumulator -to output or generate as the calculated CRC value.

The duplication of the CRC calculation resources for handling extract data word group with group sizes n/2 data bytes or less, advantageously enable the overlapping calculation of two CRC values for two successive series of data word groups. More specifically, it enables the current handling of the last data word group of a series of data words (e.g. a packet), and the first data word group of the next series of data words (e.g. the immediately following packet). [Note that it is impossible for both data word groups to have a group size of greater than n/2, and of course if one of the data word group has a group size greater than n/2, the group size of the other data word group necessarily is less than n/2. For the latter situation, no duplication of resources is necessary.]

Before describing the particular embodiment of CRC generator /, we refer first to FIG. 2, illustrating input data , wherein the alignment or the lack thereof, for successive variable length series of data block groups, such as variable length series of data packets, is illustrated. As shown, each variable length series of data block groups may be received through m groups of data word groups, where m is an integer equal to or greater than 1. The group size of each data word group may be 1, 2, 3 . . . or n bytes, where n is also an integer. In various embodiments, n equals 8. For these embodiments, n/2 equals 4.

Referring back to FIG. 3, accordingly for the embodiments where n equals 8, CRC calculation assembly and accumulator pair and is employed to incrementally calculate the CRC value for a series of data word groups, for an iteration, whenever the group size of the extracted data word group for the iteration is more than 4 data bytes (i.e. between 8 to 5 data bytes). Each of CRC calculation assembly and accumulator pairs and , and and is employed to incrementally calculate the CRC value for a series of data word groups, for an iteration, whenever the group size of the extracted data word group for the iteration is 4 data bytes or less (i.e. between 4 to 1 data bytes).

CRC Calculation Assembly (8 to 5 bytes)

FIG. 4illustrates CRC calculation assembly of FIG. 3 in further details, in accordance with one embodiment. As illustrated, CRC calculation assembly includes four CRC calculators , , , and , and a multiplexor , coupled to each other as shown. Each of CRC calculators , , , and is employed to handle the incremental calculation for an iteration for one of the group sizes. The bit distribution for an embodiment using a 64-bit data line is labelled above each CRC calculator ([:], [:], [:], [:]). More specifically, CRC calculator is employed to handle the incremental calculation for an iteration for a data word group with a group size of 8 bytes, CRC calculator is employed to handle the incremental calculation for an iteration for a data word group with a group size of 7 bytes, and so forth.

In other words, CRC calculation assembly (for handling more than n/2 bytes calculations) has exactly n/2 CRC calculators. In each iteration, one of CRC calculators , , , and is selected for use tin accordance with the group size of the extracted data word group for the iteration).

Each CRC calculator , , or may be constituted with any one of a number of known CRC calculation circuitry, e.g. polynomial division circuitry.

FIG. 4illustrates CRC calculation assembly of FIG. 3 in further details, in accordance with another embodiment. As illustrated, CRC calculation assembly includes input multiplexor , three CRC calculators , , and , and multiplexors and , coupled to each other as shown. The bit distribution for an embodiment using a 64-bit data line is labelled above the input multiplexor ([:]). CRC calculators , , and are employed in combination at least some of the time to handle the incremental calculation for an iteration for one of the group sizes. More specifically, CRC calculator is employed to handle the incremental calculation for an iteration for a data word group with a group size of 5 bytes, and CRC calculators and are employed in combination to handle the incremental calculation for an iteration for a data word group with a group size of 6 bytes. Similarly, CRC calculators and are employed to handle the incremental calculation for an iteration for a data word group with a group size of 7 bytes, and CRC calculators , , and are employed in combination to handle the incremental calculation for an iteration for a data word group with a group size of 8 bytes.

In other words, CRC calculation assembly (for handing more than n/2 bytes calculation) has less than n/2 CRC calculators. In each of the iterations for some data group sizes, CRC calculators , , and are employed in combination.

Similarly, each CRC calculator , , or may be constituted with any one of a number of known CRC calculation circuitry, e.g. polynomial division circuitry.

CRC Calculation Assembly (4 to 1 byte)

FIGS. 5-illustrate CRC calculation assembly /of FIG. 3 in further details, in accordance with one embodiment. As illustrated, in each embodiment, CRC calculation assembly /is similarly constituted as the corresponding embodiment of CRC calculation assembly .

In other words, for the embodiment of FIG. 5, CRC calculation assembly /(for handling n/2 bytes or less calculations) has exactly n/2 CRC calculators, as the embodiment of FIG. 4for CRC calculation assembly . In each iteration, one of CRC calculators , , , and is selected for use (in accordance with the group size of the extracted data word group for the iteration). However, for the embodiment of FIG. 5, CRC calculation assembly /(for handling n/2 bytes or less calculations) has less than n/2 CRC calculators, as the embodiment of FIG. 4for CRC calculation assembly . In each of the iteration, for some data group sizes, CRC calculators , , and are employed in combination. Furthermore, the embodiment of FIG. 5includes multiplexors , , and coupled to the CRC calculators , , and and each other as shown.

Similar to FIGS. 4and , the bit distribution for an embodiment using a 64-bit data line is labelled above each CRC calculator ([:], [:], [:], [:]) in FIG. 5, and above the input multiplexor ([:]) in FIG. 5. Likewise, each CRC calculator, , , , and of FIG. 5, and , , and of FIG. 5, may be constituted with any one of a number of known CRC calculation circuitry, e.g. polynomial division circuitry.

Example Application

FIG. 6 illustrates an example application of the fast CRC generator of the present invention. As illustrated, data routing device comprising receive interface and transmit interface is advantageously provided with a number of per flow inbound processing units and a number of per flow outbound processing functions . Examples of these per flow inbound and outbound processing functions may include but are not limited to deciphering and ciphering functions. Additionally, data routing device may also include a number of other common or shared function units .

For the illustrated embodiment, common/shared function units include in particular a shared CRC generation function block, incorporated with the fast CRC generator of FIG. . Accordingly, the common/shared CRC generator may alternate between generating CRC values for different data packets of the different flows being processed by per flow inbound/outbound processing units /.

As a result, the amount of storage required for provisioning the CRC function for the various flows being processed in parallel is substantially reduced under the present invention. In turn, data routing device may be advantageously disposed on a single integrated circuit. Thus, data routing device is able to handle high speed line rate data packet switching for multiple data flows at the same time. In one embodiment, data routing device is an IC component for routing packets transmitted over an optical medium onto an electrical medium at very high speed.

Conclusion and Epilogue

Thus, it can be seen from the above descriptions, a novel highly efficient method and apparatus for generating CRC for data blocks or data packets has been described. While the present invention has been described in terms of the above described embodiments, those skilled in the art will recognize that the invention is not limited to the embodiments described. The present invention can be practiced with modification and alteration within the spirit and scope of the appended claims. Thus, the description is to be regarded as illustrative instead of restrictive on the present invention.

CLAIMS

1. 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. The apparatus of claim 1, wherein the plurality of CRC calculation assemblies comprise a first CRC calculation assembly coupled to the data word extractor to incrementally calculate the CRC value for said first plurality of data word groups for an iteration, whenever the data word extractor extracts a data word group of n/2 or less bytes for the iteration, where n is an even integer.

3. The apparatus of claim 2, wherein the first CRC calculation assembly comprises less than n/2 CRC calculators coupled to each other in a cascaded manner to be selectively employed in combination in at least some of the time to incrementally calculate the CRC value for said first plurality of data word groups for an iteration, whenever the data word extractor extracts a data word group of n/2 or less bytes for the iteration.

4. The apparatus of claim 2, wherein the first CRC calculation assembly comprises n/2 CRC calculators to be selectively employed exclusively to incrementally calculate the CRC value for said first plurality of data word groups for an iteration, whenever the data word extractor extracts a data word group of n/2 or less data bytes for the iteration.

5. The apparatus of claim 2, wherein the plurality of CRC calculation assemblies further comprise a second CRC calculation assembly coupled to the data word extractor to incrementally calculate the CRC value for said first plurality of data word groups for an iteration, whenever the data word extractor extracts a data word group of more than n/2 bytes for the iteration.

6. The apparatus of claim 5, wherein the second CRC calculation assembly comprises less than n/2 CRC calculators to be selectively employed in combination at least some of the times to incrementally calculate the CRC value for said first plurality of data word groups for an iteration, whenever the data word extractor extracts a data word group of more than n/2 bytes for the iteration.

7. The apparatus of claim 5, wherein the second CRC calculation assembly comprises n/2 CRC calculators to be selectively employed exclusively to incrementally calculate the CRC value for said first plurality of data word groups for an iteration, whenever the data word extractor extracts a data word group of more than n/2 bytes for the iteration.

8. The apparatus of claim 2, wherein the data word extractor also extracts a second plurality of data word groups, and the plurality of CRC calculation assemblies further comprise a second CRC calculation assembly coupled to the data word extractor to incrementally calculate a CRC value for the second plurality of data word groups, for an iteration, whenever the data word extractor extracts for the second plurality of data word groups, a data word group of n/2 or less bytes, where n is an even integer.

9. The apparatus of claim 1, wherein the plurality of selectors comprise a first selector coupled to the 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 a second selector coupled to the first selector to cooperate with the first selector to selectively output one of the stored results as the calculated CRC value at the end of the iterative calculation.

10. The apparatus of claim 1, wherein n equals 8.

11. The apparatus of claim 1, wherein the apparatus is disposed on an integrated circuit.

12. 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.

13. The method of claim 12, wherein said selective employment of a plurality of CRC calculation assemblies comprise selecting a first CRC calculation assembly to incrementally calculate the CRC value for said first plurality of data word groups for an iteration, whenever the data word extractor extracts a data word group of n/2 or less bytes for the iteration, where n is an even integer.

14. The method of claim 13, wherein said selective employment of the first CRC calculation assembly comprises selectively employing a combination of less than n/2 CRC calculators to incrementally calculate the CRC value for said first plurality of data word groups for an iteration, whenever the data word extractor extracts a data word group of n/2 or less bytes for the iteration.

15. The method of claim 13, wherein said selective employment of the first CRC calculation assembly comprises selectively employing one of n/2 CRC calculators to incrementally calculate the CRC value for said first plurality of data word groups for an iteration, whenever the data word extractor extracts a data word group of n/2 or less data bytes for the iteration.

16. The method of claim 13, wherein said selective employment of the plurality of CRC calculation assemblies further comprise selecting a second CRC calculation assembly to incrementally calculate the CRC value for said first plurality of data word groups for an iteration, whenever the data word extractor extracts a data word group of more than n/2 bytes for the iteration.

17. The method of claim 16, wherein said selective employment of the second CRC calculation assembly comprises selecting a combination of less than n/2 CRC calculators to incrementally calculate the CRC value for said first plurality of data word groups for an iteration, whenever the data word extractor extracts a data word group of more than n/2 bytes for the iteration.

18. The method of claim 16, wherein said selecting of the second CRC calculation assembly comprises selecting one of n/2 CRC calculators to incrementally calculate the CRC value for said first plurality of data word groups for an iteration, whenever the data word extractor extracts a data word group of more than n/2 bytes for the iteration.

19. The method of claim 13, wherein said extraction further comprises extracting a second plurality of data word groups, and said selective employment of the plurality of CRC calculation assemblies further comprise selecting a second CRC calculation assembly to incrementally calculate a CRC value for the second plurality of data word groups, for an iteration, whenever the data word extractor extracts for the second plurality of data word groups, a data word group of n/2 or less bytes for the iteration, where n is an even integer.

20. 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.

21. The apparatus of claim 20, wherein the plurality of CRC calculation assemblies comprise a first CRC calculation assembly coupled to the data word extractor to incrementally calculate the CRC value for said first plurality of data word groups for an iteration, whenever a group size of a data word group of said first plurality of data word groups is n/2 or less bytes for the iteration, where n is an even integer.

22. The apparatus of claim 21, wherein the first CRC calculation assembly comprises less than n/2 CRC calculators coupled to each other in a cascaded manner to be selectively employed in combination in at least some of the times to incrementally calculate the CRC value for said first plurality of data word groups for an iteration, whenever a group size of a data word group of said first plurality of data word groups is n/2 or less bytes for the iteration.

23. The apparatus of claim 21, wherein the first CRC calculation assembly comprises n/2 CRC calculators to be selectively employed exclusively to incrementally calculate the CRC value for said first plurality of data word groups for an iteration, whenever a group size of a data word group of said first plurality of data word groups is n/2 or less data bytes for the iteration.

24. The apparatus of claim 21, wherein the plurality of CRC calculation assemblies further comprise a second CRC calculation assembly coupled to the data word extractor to incrementally calculate the CRC value for said first plurality of data word groups for an iteration, whenever a group size of a data word group of said first plurality of data word groups is more than n/2 bytes for the iteration.

25. The apparatus of claim 24, wherein the second CRC calculation assembly comprises less than n/2 CRC calculators to be selectively employed in combination at least some of the times to incrementally calculate the CRC value for said first plurality of data word groups for an iteration, whenever a group size of a data word group of said first plurality of data word groups is more than n/2 bytes for the iteration.

26. The apparatus of claim 24, wherein the second CRC calculation assembly comprises n/2 CRC calculators to be selectively employed exclusively to incrementally calculate the CRC value for said first plurality of data word groups for an iteration, whenever a group size of a data word group of said first plurality of data word groups is more than n/2 bytes for the iteration.

27. The apparatus of claim 21, wherein the plurality of CRC calculation assemblies further comprise a second CRC calculation assembly to incrementally calculate a CRC value for a second plurality of data word groups, for an iteration, whenever a group size of a data word group of the second plurality of data word groups is n/2 or less bytes for the iteration, where n is an even integer.

COPYRIGHT

User acknowledges that Fairview Research and its third party providers retain all right, title and interest in and to this xml under applicable copyright laws. User acquires no ownership rights to this xml including but not limited to its format. User hereby accepts the terms and conditions of the License Agreement.