Intel NETWORK PROCESSOR IXP2800 - Manual (Page 240)

240 Hardware Reference Manual
Intel
®
IXP2800 Network Processor
SHaC — Unit Expansion
Equation 7. (48-bit hash operation)
Equation 8. (64-bit hash operation)
Equation 9. (128-bit hash operation)
The division results in a quotient Q(x), a polynomial of order-46, order-62, or order-126, and a
remainder R(x), and a polynomial of order-47, order-63, or order-127. The operands are related by
the equation:
Equation 10.
The generator polynomial has the property of irreducibility. As a result, for a fixed multiplier M(x),
there is a unique remainder R(x) for every input A(x). The quotient Q(x), can then be discarded,
since input A(x) can be derived from its corresponding remainder R(x). A given bounded set of
input values A(x) — for example, 8K or 16K table entries — with bit weights of an arbitrary
density function can be mapped one-to-one into a set of remainders R(x) such that the bit weights
of the resulting Hashed Arguments (a subset of all values of R(x) polynomials) are all
approximately equal.
In other words, there is a high likelihood that the low-order set of bits from the Hash Arguments are
unique, so they can be used to build an index into the table. If the hash algorithm does not provide
a uniform hash distribution for a given set of data, the programmable hash multiplier (M(x)) may
be modified to provide better results.
G
48
x ( ) 1 x
10
x
25
x
36
x
48
+ + + + =
G
64
x ( ) 1 x
17
x
35
x
54
x
64
+ + + + =
G
128
x ( ) 1 x
33
x
69
x
98
x
128
+ + + + =
A x ( ) M x ( ) Q x ( ) G x ( ) R x ( ) + =