Patent ID: 7430560

Claim:
A table lookup method comprising: receiving an input lookup key and dividing the input lookup key into a plurality of strides of stride bits, including a first stride, a second stride, and a third stride; using the first stride to locate a first entry in a first-level stride table; locating a second-level stride table in a plurality of second-level stride tables using a table pointer in the first entry; compressing stride bits in the second stride using a function indicated by a compression-type field in the first entry to generate compressed second stride bits; wherein the function is in a plurality of functions that include XOR functions that combine two or more stride bits to generate a compressed stride bit using an XOR logical function, wherein the compression-type field indicates which function in the plurality of functions to perform to generate the compressed second stride bits; using the compressed second stride bits to locate a second entry in the second-level stride table; locating a third-level stride table in a plurality of third-level stride tables using a table pointer in the second entry; compressing stride bits in the third stride using a second function indicted by a compression-type field in the second entry to generate compressed third stride bits; wherein the second function is in the plurality of functions that include XOR functions that combine two or more stride bits to generate a compressed stride bit using an XOR logical function; using the compressed third stride bits to locate a third entry in the third-level stride table; continuing for any other strides in the input lookup key until a final entry in a final-level stride table is located; returning a lookup result stored in or pointed to by the final entry in the final-level stride table; wherein the second-level stride table and the third-level stride table are compressed stride tables that have been compressed to remove invalid and empty entries, wherein a compressed stride table has 2 D entries locatable by D compressed stride bits that are compressed from S stride bits from the input lookup key; whereby 2 S−D entries have been removed to form the compressed stride table, whereby stride bits are compressed by functions including XOR functions before locating entries in compressed stride tables.