US 7,305,383 B1Granted

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

AssigneeCisco Technology, Inc.

InventorsBlaine Kubesh, Gerald Lathem, Mohit Jaggi, Amit Sinha, Michael Hall

Life of this patent

Estimating the term…

Loading patent…

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.

Claims20

Dependent claims

A method for obtaining next state information in a digital process, the method comprising the following steps performed by a digital processor:

parsing a plurality of next state values for state transitions;
determining a most frequently occurring next state value in the plurality of next state values for state transitions, the most frequently occurring next state value being a next state value that occurs the most frequently in the next state values and non-default values being other values in the plurality of next state values;
storing the most frequently occurring next state value in a position for the most frequently occurring next state in an pointer array and storing non-default next state values in a plurality of other positions in the pointer array;
parsing a bitmap array to determine a transition from a present state to a next state, wherein the bitmap array includes bit entries having values;
if a bit entry is of a first value then determining the most frequently occurring next state value as the next state;
if the bit entry is not of the first value then counting a number of occurrences of a bit value in the bitmap array to achieve an index value;
and
using the index value to access the pointer array to obtain a non-default next state value for the next state.

5 more elements

Dependencies are inferred from the claim text.