Logical operations encoded by a function table for compressing index bits in multi-level compressed look-up tables
US7921088B1 · kind B1 · utility
Assignee
Inventor
Key dates
| Filing date | Mar 7, 2007 |
| Grant date | Apr 5, 2011 |
| Priority date | — |
| Expiry date | Sep 9, 2028 |
Classification
- Technology area (CPC G)Physics
- CPC primaryG06F16/9027
- WIPO fieldComputer technology
- WIPO sectorElectrical engineering
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.
Source: USPTO / EPO open patent data. Objective bibliographic and citation counts.