Multi-level compressed lock-up tables formed by logical operations to compress selected index bits
US7430560B1 · kind B1 · utility
Assignee
Inventor
Key dates
| Filing date | Jul 3, 2006 |
| Grant date | Sep 30, 2008 |
| Priority date | — |
| Expiry date | Oct 22, 2026 |
Classification
- Technology area (CPC Y)Emerging Cross-Sectional Technologies
- CPC primaryY10S707/99943
- WIPO fieldComputer technology
- WIPO sectorElectrical engineering
Abstract
A lookup is performed using multiple levels of compressed stride tables in a multi-bit Trie structure. An input lookup key is divided into several strides including a current stride of S bits. A valid entry in a current stride table is located by compressing the S bits to form 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 a field indicating which compression function and mask to use. Compression functions can include XOR, shifts, rotates, and multi-bit averaging. Rather than store all 2S entries, the current stride table is compressed to store only 2D entries. Ideally, the number of valid entries in the current stride table is between 2D−1 and 2D for maximum compression. Storage requirements are reduced.
Source: USPTO / EPO open patent data. Objective bibliographic and citation counts.