Logical operations encoded by a function table for compressing index bits in multi-level compressed look-up tables

• US 7,921,088 B1
• Filed: 03/07/2007
• Issued: 04/05/2011
• Est. Priority Date: 07/22/2005
• Status: Expired due to Fees

• Current Assignee: Gula Consulting Limited Liability Company (Intellectual Ventures LLC)
• Original Assignee: X-Engines Incorporated
• Inventors: Mittal, Millind
• Primary Examiner(s): LeRoux, Etienne P
• Assistant Examiner(s): NGUYEN, THU N
• Application Number:
  US11/683,157
• Time in Patent Office: 1,490 Days
• Field of Search: 707/693
• US Class Current: 707/693
• CPC Class Codes: G06F 16/9027 Trees

Abstract

Compressed stride tables in a multi-bit Trie structure perform lookups. An input lookup key is divided into strides including a current stride of S bits. A valid entry in a current stride table is located by compressing the S bits, forming a compressed index of D bits into the current stride table. A compression function logically combines the S bits to generate the D compressed index bits. An entry in a prior-level table points to the current stride table and has an opcode field indicating which compression function and mask to use. Compression functions can include counts of leading-repeated bits, and very complex functions such as hashes, CRC, encryption. A function table stores results of the complex functions that are addressed by the S bits of the current stride. The opcode field in the stride entry selects from among several tables, each storing results for a different function.

Claims

1. A lookup structure comprising:

a plurality of stride tables that form a multi-bit Trie structure for performing lookups, wherein the stride tables are arranged into a plurality of levels;

a lookup input for receiving an input lookup key dividable into a plurality of strides, wherein the plurality of strides correspond to the plurality of levels, wherein at least two of the strides have multiple bits each, wherein a stride is for locating an entry in a stride table at a level in the plurality of levels;

a compressed stride table in the plurality of stride tables at an intermediate level in the plurality of levels, wherein the compressed stride table is pointed to by a table pointer in a prior-level selected entry in a prior stride table at a prior level in the plurality of levels, the prior-level selected entry being selected by a prior stride;

a plurality of valid entries in the compressed stride table, wherein a selected valid entry in the compressed stride table is selected with compressed index bits, the compressed index bits being fewer bits than a current stride in the plurality of stride, the current stride for the compressed stride table;

an index compressor, receiving current stride bits from the lookup input for the current stride of the input lookup key, the index compressor generating the compressed index bits; and

pointer fields stored in the plurality of valid entries, the pointer fields containing pointers to stride tables in a next level in the plurality of levels or pointers to lookup results;

wherein the lookup structure is embodied on a non-transitory computer-readable storage medium;

wherein the index compressor comprises a function table and a final masker;

wherein the function table comprises a plurality of addressable entries each storing a function-result value, wherein the current stride bits form an address into the function table to select a selected entry with an output function-result value, wherein the output function-result value is a table-defined function of the current stride bits;

wherein the final masker comprises a selector for selecting a subset of bits in the output function-result value selected by the function table to generate the compressed index bits;

wherein the selector selects the subset of bits in response to a final mask value stored in the plurality of valid entries in the compressed stride table,

whereby the function table implements the table-defined function of the index compressor;

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 function tables store function results for different table-defined functions and whereby 2^S-2^D entries have been removed to form the compressed stride table,

whereby stride bits are compressed by table-defined functions before locating entries in compressed stride tables.

2. The lookup structure of claim 1 further comprising:

a compression opcode field stored in the prior-level selected entry, the compression opcode field specifying the table-defined function;

whereby table-defined functions for compression are specified by compression opcode fields stored in the prior-level selected entry.

3. The lookup structure of claim 2 wherein the function table further comprises:

a plurality of result tables, each result table containing function-result values for a different table-defined function, each result table having a plurality of addressable entries selectable by the current stride bits;

a multiplexer, coupled to outputs from the plurality of result tables, and responsive to the compression opcode field, for selecting one of the function-result values output by a selected result table in the plurality of tables, wherein the compression opcode field selects the selected result table having a selected table-defined function indicated by the compression opcode field,

whereby multiple table-defined functions are stored in multiple result tables in the function table.

4. The lookup structure of claim 2 wherein the table-defined function for is a hash function.

5. The lookup structure of claim 2 wherein the table-defined function is a cyclical-redundancy-check (CRC), a MD5 hash, or a DES encryption.

6. The lookup structure of claim 2 wherein the table-defined function is a leading-repeat count function that indicates a repeat count of a leading bit in the current stride bits.

7. The lookup structure of claim 1 wherein the function-result values contain a first subset of bit-positions and a second subset of bit-positions;

wherein the function-result values contain results of a first function in the first subset of bit-positions;

wherein the function-result values contain results of a second function in the second subset of bit-positions.

8. The lookup structure of claim 7 wherein the first function is a function of upper unmasked bits in the current stride bits;

wherein the second function is a function of upper unmasked bits and of lower masked bits in the current stride bits;

wherein the upper unmasked bits are for upper bit-positions in the current stride having no masked bits for entries in the compressed stride table;

wherein the lower masked bits are for lower bit-positions in the current stride having a masked bit for at least one regional entry in the compressed stride table;

wherein the regional entry matches at least two values of the current stride bits due to the masked bit matching both a 1 and a 0,

whereby upper unmasked bits participate in the first function and lower masked bits do not participate in the first function.

9. The lookup structure of claim 8 further comprising:

a least-significant unmasked bit position in the current stride bits;

wherein the upper unmasked bits are for bit positions of equal or greater significance than the least-significant unmasked bit position;

wherein the lower masked bits are for bit positions of lesser significance than the least-significant unmasked bit position,

whereby the least-significant unmasked bit position separates the upper unmasked bits from the lower masked bits.

10. The lookup structure of claim 9 further comprising:

a lower subset of entries in the compressed stride table, wherein entries in the lower subset are distinguishable from each other using the second function generated from the lower masked bits,

wherein the lower masked bits distinguish entries in the lower subset;

wherein the index compressor outputs a third subset of the current stride bits, together with the function-result values containing results of the first function in the first subset of bit-positions, and the function-result values containing results of the second function in the second subset of bit-positions;

wherein the third subset of the current stride bits are for middle bit-positions between the first subset of bit-positions and the second sub-set of bit-positions.

11. The lookup structure of claim 10 wherein the lower subset contains exact-match entries having no masked bits;

wherein regional entries that are not in the lower subset contain masked bits;

wherein the second function distinguishes the exact-match entries in the lower subset having no masked bits.

12. The lookup structure of claim 9 wherein the first function is a leading-repeat count function that indicates a repeat count of a leading bit in the current stride bits when the least-significant unmasked bit position is within two bit-positions of a most-significant-bit (MSB) position.

13. The lookup structure of claim 9 further comprising:

a regional entry in the compressed stride table, the regional entry containing a series of masked bits that are encoded as a series of binary bits;

wherein the series of binary bits comprises a first binary bit of a first polarity followed by a plurality of binary bits all having a second polarity that is opposite to the first polarity;

wherein the regional entry matches at least two values of the current stride bits due to each masked bit in the series of masked bits matching both a 1 and a 0,

whereby masked bits are encoded as binary bits for regional entries.

14. The lookup structure of claim 9 wherein the current stride bits from the lookup input for the current stride of the input lookup key are completely replaced by the compressed index bits from the index compressor,

wherein the compressed index bits contain only bits from the index compressor.

15. The lookup structure of claim 9 wherein the first function is a hash function, an encryption function, or a cyclical-redundancy-check (CRC) function when the least-significant unmasked bit position is at least two bit-positions less significant than a most-significant-bit (MSB) position.

16. 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, and a second 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;

applying the stride bits in the second stride as an address into a function table to select a first selected entry in the function table, and reading a first function result from the first selected entry;

generating compressed second stride bits from the first function result read from the function table;

using the compressed second stride bits to locate a second entry in the second-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 is a compressed stride table that has 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;

reading a first function selector from the first entry;

using the first function selector to select a first selected function table in a plurality of function tables, wherein each function table in the plurality of functions tables store function results for different table-defined functions;

wherein the first function result is read from the first selected function table in the plurality of function tables addressed by the stride bits in the second stride;

reading a second function selector from the second entry; and

using the second function selector to select a second selected function table in the plurality of function tables;

wherein the second function result is read from the second selected function table in the plurality of function tables addressed by the stride bits in the second stride;

reading a final mask from the first entry;

using the final mask to select a subset of bits in the first function result or in the second function result to generate compressed stride bits,

whereby function tables store function results for different table-defined functions and whereby 2^S-2^D entries have been removed to form the compressed stride table

whereby stride bits are compressed by table-defined functions before locating entries in compressed stride tables.

17. The table lookup method of claim 16 further comprising:

comparing a second tag value stored in the second entry with the second stride to determine when a valid match has occurred;

decoding mask-encoded bits in the second tag value to generate second masked bit-positions when a second mask flag stored in the second entry is set

masking uncompressed stride bits in the second stride indicated by the second masked bit-positions when comparing the second tag when the second mask flag is set;

whereby masked comparisons allow for a partial stride match to determine when a valid mask has occurred.

18. The table lookup method of claim 17 further comprising:

when a masked comparison generates a partial stride mask in a current-level stride table at an intermediate level, the current-level stride table operates as the final-level stride table with the final entry;

returning the lookup result stored in or pointed to by the final entry in the final-level stride table,

whereby intermediate levels generating partial stride matches return the lookup result before any remaining levels of stride tables are accessed.