Processing system using bitmap array to compress deterministic finite automation state table allowing direct indexing

US7305383B1 · kind B1 · utility

Assignee

• Cisco Technology, Inc. · US

Inventors

• Blaine Kubesh · Austin, US
• Gerald S. Lathem · Elgin, US
• Mohit Jaggi · Sunnyvale, US
• Amit Sinha · San Jose, US
• Michael L. Hall · Austin, US

Key dates

• Filing date: Jun 10, 2004
• Grant date: Dec 4, 2007
• Expiry date: Jul 18, 2025

Classification

• Technology area (CPC Y): Emerging Cross-Sectional Technologies
• CPC primary: Y10S707/99945
• WIPO field: Control
• WIPO sector: Instruments

Abstract

A processing system wherein a bitmap array is first used to obtain an index. The index is used to obtain a value from an array. A predefined default value is used to improve compression and speed in cases where a single default value is often encountered. In this embodiment the size of each entry in the bitmap array is one bit. In another approach, a bitmap array having two bit entries is provided. The use of two bits allows four different entry values. Two values are used to indicate two different default values. A third value is used for a “repeat” indicator to when the last-used next-state value should be re-used. The fourth value is used to indicate indexing into a pointer table, similarly to the embodiment using single-bit entries in the bitmap array.