Efficient remainder calculation for even divisors
In general, in one aspect, the invention features a circuit, method, and computer-readable media for calculating xmody, wherein x and y are binary numbers, and wherein y is an even number. The circuit comprises a power of two calculator adapted to receive signals representing binary number y and to provide signals representing binary numbers r and m, wherein y=r2 m ; a vector splitter adapted to receive signals representing binary number x and signals representing the binary number m, and to provide signals representing binary numbers x[w:m] and x[m−1:0], wherein the binary number x[m−1:0] comprises the m least-significant bits of the binary number x and the binary number x[w:m] comprises the w−m+1 most-significant bits of the binary number x; and a remainder calculator adapted to receive the signals representing the binary numbers x[w:m] and r, and to provide a binary number x[w:m]modr, wherein the binary number x[w:m]modr is a remainder of a quotient of the binary number x[w:m] divided by the binary number r; wherein the binary number x[w:m]modr comprises the most-significant bits of a binary number representing xmody and the binary number x[m−1:0] comprises the least-significant bits of the binary number representing xmody.
1. A circuit for calculating xmody, wherein x and y are binary numbers, and wherein y is an even number, comprising:
a power of two calculator adapted to receive signals representing binary number y and to provide signals representing binary numbers r and m, wherein y=r2 m ;
a vector splitter adapted to receive signals representing binary number x and signals representing the binary number m, and to provide signals representing binary numbers x[w:m] and x[m−1:0], wherein the binary number x[m−1:0] comprises m least-significant bits of the binary number x and the binary number x[w:m] comprises w−m+1 most-significant bits of the binary number x; and
a remainder calculator adapted to receive the signals representing the binary numbers x[w:m] and r, and to provide a binary number x[w:m]modr, wherein the binary number x[w:m]modr is a remainder of a quotient of the binary number x[w:m] divided by the binary number r;
wherein the binary number x[w:m]modr comprises most-significant bits of a binary number representing xmody, the binary number x[m−1:0] comprises least-significant bits of the binary number representing xmody, and the circuit outputs the binary number x[w:m]modr to a network communications device to perform at least one of hashing Internet Protocol addresses, masking destination port vectors, and calculating a pointer to a memory location based at least in part on the binary number x[w:m]modr.
2. The circuit of claim 1 , wherein m is a maximum power of two by which the binary number y is divisible with no remainder.
3. The circuit of claim 1 , further comprising:
a buffer adapted to receive signals representing the binary number x[w:m]modr and the binary number x[m−1:0], and to provide the binary number xmody.
4. The circuit of claim 3 , further comprising:
a second buffer adapted to store the binary number y, and to provide the signals representing the binary number y; and
a third buffer adapted to store the binary number x, and to provide the signals representing the binary number x.
5. The circuit of claim 1 , wherein the power of two calculator comprises a memory.
6. The circuit of claim 1 , wherein the vector splitter comprises a memory.
7. The circuit of claim 1 , wherein the remainder calculator comprises a memory.
8. A circuit for calculating xmody, wherein x and y are binary numbers, and wherein y is an even number, comprising:
power of two calculator means for receiving signals representing binary number y, and for providing signals representing binary numbers r and m, wherein y=r2 m ;
vector splitter means for receiving signals representing binary number x and signals representing the binary number m, and for providing signals representing binary numbers x[w:m] and x[m−1:0], wherein the binary number x[m−1:0] comprises m least-significant bits of the binary number x and the binary number x[w:m] comprises w−m+1 most-significant bits of the binary number x; and
remainder calculator means for receiving the signals representing the binary numbers x[w:m] and r, and for providing a binary number x[w:m]modr, wherein the binary number x[w:m]modr is a remainder of a quotient of the binary number x[w:m] divided by the binary number r;
wherein the binary number x[w:m]modr comprises the most-significant bits of a binary number representing xmody, the binary number x[m−1:0] comprises the least-significant bits of the binary number representing xmody, and the circuit outputs the binary number x[w:m]modr to a network communications device to perform at least one of hashing Internet Protocol addresses, masking destination port vectors, and calculating a pointer to a memory location based at least in part on the binary number x[w:m]modr.
9. The circuit of claim 8 , wherein m is maximum power of two by which the binary number y is divisible with no remainder.
10. The circuit of claim 8 , further comprising:
buffer means for receiving signals representing the binary number x[w:m]modr and the binary number x[m−1:0], and for providing the binary number xmody.
11. The circuit of claim 10 , further comprising:
second buffer means for storing the binary number y, and for providing the signals representing the binary number y; and
third buffer means for storing the binary number x, and for providing the signals representing the binary number x.
12. The circuit of claim 8 , wherein the power of two calculator means comprises memory means.
13. The circuit of claim 8 , wherein the vector splitter means comprises memory means.
14. The circuit of claim 8 , wherein the remainder calculator means comprises memory means.