1. A cyclic redundancy check (CRC) pipeline comprising:
a first stage configured to receive a data block and calculate a first CRC value for a first portion of the data block; and
a plurality of subsequent stages configured to calculate a plurality of sequential CRC values representing overlapping portions of the data block, wherein each of the plurality of subsequent stages comprises at least one CRC calculator and CRC shifter configured to modify the first CRC value such that an effect of a sub-portion of the first portion is removed from the first CRC value to yield a temporary CRC value and an effect of a second portion of the data block neighboring the first portion of the data block is added to the temporary CRC value to yield a second, offset CRC value, wherein a data size of the sub-portion and the second portion is the same and defines a predetermined offset value.
2. The CRC pipeline of claim 1, wherein at least one of the plurality of subsequent stages includes a first CRC calculator and a first CRC shifter in a first phase and a second CRC calculator and second CRC shifter in a second phase, wherein the first phase is configured to calculate the second CRC value and the second phase is configured to modify the second CRC value such that an effect of a sub-portion of the data represented by the second CRC value is removed and an effect of a third portion of the data block neighboring the data represented by the second CRC value is added to yield a third, offset CRC value, wherein a data size of the sub-portion of the data represented by the second CRC value and the third portion of the data block is the same as the predetermined offset value.
3. The CRC pipeline of claim 1, wherein each of the subsequent stages includes at least two CRC calculators,
wherein a first one of the at least two CRC calculators is configured to output a first intermediate CRC value representing a third portion of the data block padded with trailing zeros, the first intermediate CRC value is combined with a received CRC value to remove an effect of the third portion from the received CRC value and yield a second intermediate CRC value which is inputted into the CRC shifter,
wherein a second one of the at least two CRC calculators is configured to output a third intermediate CRC value representing a fourth portion of the data block neighboring data represented by the received CRC value, the third intermediate CRC value is combined with an output of the CRC shifter to add the effect of the fourth portion of the data block and yield an offset CRC value.
4. The CRC pipeline of claim 1, wherein at least one of the plurality of subsequent stages includes a plurality of independent parallel circuit paths, each of the independent parallel circuit paths comprises a respective CRC calculator and a respective CRC shifter, each of the independent parallel circuit paths is configured to calculate CRC values using an obtained CRC value received from a previous stage in the CRC pipeline.
5. The CRC pipeline of claim 4, wherein each of the plurality of independent circuit paths include at least two phases, wherein each of the at least two phases comprises at least one CRC calculator and at least one CRC shifter, and wherein the at least two phases are daisy chained such that an output CRC value calculated by a first one of the at least two phases is used by a second one of the at least two phases to calculate a different output CRC value, wherein both the output CRC value and the different output CRC value are one of the sequential CRC values.
6. The CRC pipeline of claim 1, wherein each of the plurality of subsequent stages calculates at least two of the plurality of sequential CRC values using a respective predetermined offset value, wherein the respective predetermined offset value for each stage in the CRC pipeline is less than the respective predetermined offset values used in previous stages in the CRC pipeline.
7. The CRC pipeline of claim 1, where each stage in CRC pipeline completes execution in one clock cycle.
8. The CRC pipeline of claim 1, wherein the CRC pipeline is disposed on an integrated circuit.
9. The CRC pipeline of claim 1, wherein each of the overlapping portions represented by the sequential CRC values contains data shared by at least one other overlapping portion of the data block and each of the overlapping portions are offset by a same data offset value.
10. The CRC pipeline of claim 1, wherein the at least one CRC calculator in each of the plurality of subsequent stages contain less circuitry than one or more CRC calculators used in a previous stage.
11. A method comprising:
(i) calculating, at a first stage in a CRC pipeline, a first CRC value for a first portion of a received data block;
(ii) calculating, at a second stage in the CRC pipeline, a second CRC value using at least one CRC calculator and CRC shifter by:
modifying the first CRC value such that an effect of a sub-portion of the first portion is removed from the first CRC value to yield a temporary CRC value, and
adding an effect of a second portion of the received data block neighboring the first portion of the received data block to the temporary CRC value to yield the second CRC value, wherein a data size of the sub-portion and the second portion is the same and defines a predetermined offset value; and
(iii) repeating, in one or more subsequent stages in the CRC pipeline, the calculation performed in step (ii) using a progressively smaller predetermined offset value to calculate a plurality of sequential CRC values representing overlapping portions of the received data block.
12. The method of claim 11, wherein at least one of the subsequent stages includes a first CRC calculator and a first CRC shifter in a first phase and a second CRC calculator and second CRC shifter in a second phase, wherein the calculation in step (ii) is repeated in both the first phase and second phase using a same predetermined offset value, wherein the first phase uses the first CRC value to perform the calculation in step (ii) but the second phase uses a CRC value outputted from the first phase.
13. The method of claim 11, wherein the second stage includes at least two CRC calculators, and wherein calculating the second CRC value at the second stage in the CRC pipeline comprises:
calculating, using a first one of the at least two CRC calculators, a first intermediate CRC value representing the sub-portion of the first portion of the received data block padded with trailing zeros;
combining the first intermediate CRC value with the first CRC value to remove an effect of the sub-portion from the first CRC value and yield a second intermediate CRC value;
calculating a shifted CRC value of the second intermediate CRC value using the CRC shifter;
calculating, using a second one of the at least two CRC calculators, a third intermediate CRC value representing the second portion of the received data block; and
combining the shifted CRC value and third intermediate CRC value to add the effect of the second portion of the data block and yield the second CRC value.
14. The method of claim 11, wherein at least one the subsequent stages includes a plurality of independent parallel circuit paths, each of the independent parallel circuit paths comprises a respective CRC calculator and a respective CRC shifter, each of the independent parallel circuit paths calculates CRC values using at least two CRC values received from a previous stage in the CRC pipeline.
15. The method of claim 14, wherein each of the independent parallel circuit paths comprises at least two daisy chained phases, where an output CRC value from a first of the phases is used as an input to a second one of the phases.
16. The method of claim 11, wherein the first stage, the second stage, and the one or more subsequent stages complete execution in one clock cycle.
17. The method of claim 16, further comprising:
receiving, at the first stage, one of a plurality of sequential data blocks of a data stream each clock cycle; and
outputting a set of sequential CRCs values for each of the sequential data blocks each clock cycle in a plurality of sequential clock cycles.
18. The method of claim 11, wherein each of the overlapping portions represented by the sequential CRC values contains data shared by at least one other overlapping portion of the received data block, and each of the overlapping portions are offset by a same data offset value.
19. The method of claim 11, further comprising, before adding the effect of the second portion to the temporary CRC value, altering the temporary CRC value using the CRC shifter such that the temporary CRC value represents a different sub-portion of the first portion with trailing zeros instead of representing the different sub-portion of the first portion with leading zeros.
20. An integrated circuit comprising a CRC pipeline, the integrated circuit comprising:
a first stage configured to receive a data block and calculate a first CRC value for a first portion of the data block; and
a plurality of subsequent stages configured to calculate a plurality of sequential CRC values representing overlapping portions of the data block, wherein each of the plurality of subsequent stages comprises at least one CRC calculator and CRC shifter configured to modify the first CRC value such that an effect of a sub-portion of the first portion is removed from the first CRC value to yield a temporary CRC value and an effect of a second portion of the data block neighboring the first portion of the data block is added to the temporary CRC value to yield a second, offset CRC value, wherein a data size of the sub-portion and the second portion is the same and defines a predetermined offset value.
The claims below are in addition to those above.
All refrences to claim(s) which appear below refer to the numbering after this setence.
1. At a receiving computing device in a distributed environment running one or more services for processing messages, a method of efficiently determining those registered endpoints for which at least a portion of a message is destined, without having to compare each message header with each address header for each endpoint within each service, the method comprising:
an act of receiving a message that includes a set of message headers comprising information used in determining those endpoints for which at least a portion of the message is destined for processing;
a step for creating a message header bit array by comparing at least a portion of one or more of the set of message headers with a list of address headers within a header-to-bit conversion table, wherein each bit set true in the message header bit array represents a match and appropriate bit placement corresponding to an address header within the list;
an act of receiving one or more endpoint bit masks, wherein each bit set true within the one or more endpoint bit masks represents a header from the list of address headers that the message needs to have in order to satisfy criteria for a particular endpoint receiver; and
an act of comparing the message header bit array to the one or more endpoint address bit masks for determining those endpoints for which at least a portion of the message is destined.
2. The method of claim 1, wherein one of the set of message headers includes a primary uniform resource identifier corresponding to the receiving computing device, and wherein the method further comprises:
using the primary uniform resource identifier to identify one or more endpoints such that only bit masks for the identified one or more endpoints are used for the comparison with the message header bit array.
3. The method of claim 2, wherein the list of address headers are in normalized form, and wherein prior to creating the message header bit array the method further comprises:
normalizing the at least a portion of one or more of the set of message headers using a set of rules that when implemented produce identical unique data strings for equivalent portions of headers, which without normalization appear different.
4. The method of claim 3, wherein prior to normalizing the at least a portion of one or more of the set of message headers the method further comprises:
identifying a namespace prefix, local name, or both, for each of the set of message headers to produce a list of qualified names for the set of message headers;
identifying a namespace prefix, local name, or both, for each address header of the identified one or more endpoints to produce a list of qualified names for the each address header;
comparing the list of qualified names for the set of message headers with the qualified names for the each address header; and
based on the comparison of the qualified names, determining a list of candidates representing the at least a portion of one more of the set of messages headers to normalize and compare with the header-to-bit conversion table when creating the message header bit array.
5. The method of claim 4, wherein a hash table is used to identify the one or more endpoints.
6. The method of claim 5, wherein a hash table is used to identify the namespace prefix, local name, or both, for each address header of the identified one or more endpoints.
7. The method of claim 1, wherein the one or more endpoint address bit masks are pre-computed.
8. The method of claim 1, wherein a bitwise AND operator is used to compare the message header bit array to the one or more endpoint bit masks such that if a result of ANDing the message header bit array to one of the one or more endpoint bit masks equals the one of the one or more endpoint bit masks, it is determined that at least a portion of the message is destined for the endpoint corresponding to the one of the one or more endpoint bit masks.
9. The method of claim 1, wherein the header-to-bit conversion table is a hash table.
10. The method of claim 1, wherein a first endpoint requires at least two copies of an address header, and wherein a first endpoint bit mask from the one or more endpoint bit masks corresponds to the first endpoint such that it includes two bits set true representing the at least two copies.
11. At a computing device in a distributed environment, a method of creating a header-to-bit conversion table, which is used in converting headers within a message to an array of bits for efficiently determining those registered endpoints for which at least a portion of a message is destined, the method comprising acts of:
collecting a list of address headers corresponding to one or more endpoints, wherein each address header within the list represents information a message needs for satisfying at least a portion of criteria for the one or more endpoints;
assigning a bit placement to each address header within the list to produce an array of bits representing each of the address headers;
mapping the bit placement of the address headers to their corresponding address header information in order to create a header-to-bit conversion table; and
storing the header-to-bit conversion table for subsequent use in creating a message header bit array used in determining which of the one or more endpoints to send at least a portion of a message to, wherein each bit set true in the message header bit array represents a match and appropriate bit placement corresponding to an address header within the list.
12. The method of claim 11, wherein prior to assigning the bit placement to each address header within the list, the method further comprises:
determining if duplicate address headers exist within the list of address headers across different endpoints for eliminating such duplicates from the list.
13. The method of claim 11 further comprising:
using the header-to-bit conversion table to create a bit mask for each of the one or more endpoints by setting true each bit representing a address header needed to satisfy that particular endpoint’s criteria; and
storing the bit masks for each of the one or more endpoints for subsequent comparison with the message header bit array, wherein if the message header bit array has bits set true corresponding to address headers needed to satisfy a particular endpoint’s criteria, at least a portion of the message is sent to that endpoint.
14. The method of claim 11, wherein one or more endpoints’ criteria require two copies of a first address header, and wherein two bits are assigned and mapped to the first address header within the header-to-bit conversion table.
15. At a receiving computing device in a distributed environment running one or more services for processing messages, a computer program product for implementing a method of efficiently determining those registered endpoints for which at least a portion of a message is destined, without having to compare each message header with each address header for each endpoint within each service, the computer program product comprising one or more computer readable media having stored thereon computer executable instructions that, when executed by a processor, can cause the computing device to perform the following:
receive a message that includes a set of message headers comprising information used in determining those endpoints for which at least a portion of the message is destined for processing;
create a message header bit array by comparing at least a portion of one or more of the set of message headers with a list of address headers within a header-to-bit conversion table, wherein each bit set true in the message header bit array represents a match and appropriate bit placement corresponding to an address header within the list;
receive one or more endpoint bit masks, wherein each bit set true within the one or more endpoint bit masks represents a header from the list of address headers that the message needs to have in order to satisfy criteria for a particular endpoint receiver; and
compare the message header bit array to the one or more endpoint address bit masks for determining those endpoints for which at least a portion of the message is destined.
16. The computer program product of claim 15, wherein one of the set of message headers includes a primary uniform resource identifier corresponding to the receiving computing device, and wherein the computer program product further comprises computer executable instructions that can cause the computing device to perform the following:
use the primary uniform resource identifier to identify one or more endpoints such that only bit masks for the identified one or more endpoints are used for the comparison with the message header bit array.
17. The computer program product of claim 16, wherein the list of address headers are in normalized form, and wherein prior to creating the message header bit array, and wherein the computer program product further comprises computer executable instructions that can cause the computing device to perform the following:
normalize the at least a portion of one or more of the set of message headers using a set of rules that when implemented produce identical unique data strings for equivalent portions of headers, which without normalization appear different.
18. The compute program product of claim 17, wherein prior to normalizing the at least a portion of one or more of the set of message headers, and wherein the computer program product further comprises computer executable instructions that can cause the distributed computing system to perform the following:
identify a namespace prefix, local name, or both, for each of the set of message headers to produce a list of qualified names for the set of message headers;
identify a namespace prefix, local name, or both, for each address header of the identified one or more endpoints to produce a list of qualified names for the each address header;
compare the list of qualified names for the set of message headers with the qualified names for the each address header; and
based on the comparison of the qualified names, determine a list of candidates representing the at least a portion of one more of the set of messages headers to normalize and compare with the header-to-bit conversion table when creating the message header bit array.
19. The computer program product of claim 15, wherein a bitwise AND operator is used to compare the message header bit array to the one or more endpoint bit masks such that if a result of ANDing the message header bit array to one of the one or more endpoint bit masks equals the one of the one or more endpoint bit masks, it is determined that at least a portion of the message is destined for the endpoint corresponding to the one of the one or more endpoint bit masks.
20. The computer program product of claim 15, wherein a first endpoint requires at least two copies of an address header, and wherein a first endpoint bit mask from the one or more endpoint bit masks corresponds to the first endpoint such that it includes two bits set true representing the at least two copies.