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

• US 7,305,383 B1
• Filed: 06/10/2004
• Issued: 12/04/2007
• Est. Priority Date: 06/10/2004
• Status: Active Grant

• Current Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Original Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Inventors: Hall, Michael, Sinha, Amit, Jaggi, Mohit, Lathem, Gerald, Kubesh, Blaine
• Primary Examiner(s): Mofiz; Apu
• Assistant Examiner(s): Le; Jessica N
• Application Number:
  US10/866,377
• Time in Patent Office: 1,272 Days
• Field of Search: 707 3- 6, 707/104.1, 717/152, 341/107
• US Class Current: 1/1
• CPC Class Codes: G05B 19/045 using logic state machines, consisting only of a memory or a programmable logic device containing the logic for the controlled machine and in which the state of its outputs is dependent on the state of its inputs or part of its own output states, e.g. binary decision controllers, finite state controllers
• CPC Class Codes: G05B 2219/23284 Eliminate redundant states in finite state machine
• CPC Class Codes: G05B 2219/23289 State logic control, finite state, tasks, machine, fsm
• CPC Class Codes: Y10S 707/99933 Query processing, i.e. searching
• CPC Class Codes: Y10S 707/99934 Query formulation, input preparation, or translation
• CPC Class Codes: Y10S 707/99936 Pattern matching access
• CPC Class Codes: Y10S 707/99945 Object-oriented database structure processing

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.

Claims

1. 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.

2. The method of claim 1, further comprising

using the next state in a deterministic finite automaton.

3. The method of claim 1, further comprising

using the next state in a finite state machine.

4. The method of claim 1, further comprising using the next state in a string matching operation.

5. The method of claim 1, wherein a plurality of bits are used for one or more entries in the bitmap array, the method further comprising

storing a second most frequently occurring next state value in a second position for the second most frequently occurring next state in the pointer array;

if a bit entry is of a second value then determining the second most frequently occurring next state value to obtain the next state.

6. The method of claim 5, wherein two bits are used for bit entries in the bitmap array, wherein the most frequently occurring next state value and the second most frequently occurring next state value correspond to two different default pointer values for obtaining states.

7. The method of claim 1, wherein at least one entry in the bitmap array includes a plurality of bits, the method further comprising

determining one of a plurality of most frequently occurring next state values to obtain a next state depending upon the value of a bitmap entry.

8. The method of claim 1, further comprising

adding the index value to a base table to obtain a value for a next state.

19. The method of claim 1, wherein the most frequently occurring next state value is stored once in the position for the most frequently occurring next state and redundant occurrences are removed from the plurality of next state values and not stored in the pointer array.

20. The method of claim 19, wherein the non-default values are stored in the other positions in the pointer array, wherein the non-default values include values that occur multiple times.

9. An apparatus for obtaining next state information in a digital process, the apparatus comprising:

one or more digital processors;

a machine readable storage medium including instructions executable by the digital processors, comprising

one or more instructions for parsing a plurality of next state values for state transitions;

one or more instructions for 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;

one or more instructions for 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;

one or more instructions for 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;

one or more instructions for checking if a bit entry is of a first value and, if so, then determining the most frequently occurring next state value as the next state;

one or more instructions for checking if the bit entry is not of the first value and, if so, 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 a next state.

10. A machine-readable storage medium including instructions executable by a processor for obtaining next state information in a digital process, the machine-readable medium comprising:

one or more instructions for parsing a plurality of next state values for state transitions;

one or more instructions for 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;

one or more instructions for 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;

one or more instructions for 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;

one or more instructions for checking if a bit entry is of a first value and, if so, then determining the most frequently occurring next state value as the next state;

one or more instructions for checking if the bit entry is not of the first value and, if so, 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 a next state.

11. An apparatus for obtaining next state information in a digital process, the apparatus comprising:

means for parsing a plurality of next state values for state transitions;

means for 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;

means for 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;

means for 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;

means for determining the most frequently occurring next state value as the next state if a bit entry is of a first value;

means for counting a number of occurrences of a bit value in the bitmap array to achieve an index value, if the bit entry is not of the first value; and

means for using the index value to access the pointer array to obtain a non-default next state value for the next state.

12. The apparatus of claim 11, further comprising:

means for using the next state in deterministic finite automaton.

13. The apparatus of claim 11, further comprising:

means for using the next state in a finite state machine.

14. The apparatus of claim 11, further comprising:

means for using the next state in a string matching operation.

15. The apparatus of claim 11, wherein a plurality of bits are used for one or more entries in the bitmap array, the apparatus further comprising

means for storing a second most frequently occurring next state value in a second position for the second most frequently occurring next state in the pointer array;

means for determining the second most frequently occurring next state value to obtain the next state if a bit entry is of a second value.

16. The apparatus of claim 15, wherein two bits are used for bit entries in the bitmap array, wherein the most frequently occurring next state value and the second most frequently occurring next state value correspond to two different default pointer values for obtaining states.

17. The apparatus of claim 11, wherein at least one entry in the bitmap array includes a plurality of bits, the apparatus further comprising:

means for determining one of a plurality of most frequently occurring next state values to obtain a next state depending upon the value of a bitmap entry.

18. The apparatus of claim 11, further comprising:

means for adding the index value to a base table to obtain a value for a next state.