Hardware parser accelerator

• US 20040083466A1
• Filed: 12/31/2002
• Published: 04/29/2004
• Est. Priority Date: 10/29/2002
• Status: Abandoned Application

• Current Assignee: Lockheed Martin Corporation (Martin Marietta Corporation)
• Original Assignee: Lockheed Martin Corporation (Martin Marietta Corporation)
• Inventors: Dapp, Michael C., Lett, Eric C.
• Application Number:
  US10/331,315
• Publication Number:
  US 20040083466A1
• Time in Patent Office: Days
• US Class Current: 717/143
• CPC Class Codes: G06F 40/143 Markup, e.g. Standard Generalized Markup Language [SGML] or Document Type Definition [DTD]
• CPC Class Codes: G06F 40/221 Parsing markup language streams streaming G06F40/149
• CPC Class Codes: G06F 8/427 Parsing

Abstract

Dedicated hardware is employed to perform parsing of documents such as XML™ documents in much reduced time while removing a substantial processing burden from the host CPU. The conventional use of a state table is divided into a character palette, a state table in abbreviated form, and a next state palette. The palettes may be implemented in dedicated high speed memory and a cache arrangement may be used to accelerate accesses to the abbreviated state table. Processing is performed in parallel pipelines which may be partially concurrent. dedicated registers may be updated in parallel as well and strings of special characters of arbitrary length accommodated by a character palette skip feature under control of a flag bit to further accelerate parsing of a document.

Claims

1. A parser accelerator including

a document memory,

a character pallette containing addresses corresponding to characters in said document,

a state table containing a plurality of entries corresponding to a said character,

a next state pallette including a state address or offset, and

a token buffer, wherein

said entries in said state table include at least one of an address into said next state pallette and a token.

2. The parser accelerator as recited in claim 1 wherein said character pallette, said state table and said next state pallette form a pipeline.

3. The parser accelerator as recited in claim 2, wherein each of said character pallette, said state table and said next state pallette each contain a respective portion of state table information in compressed form.

4. The parser accelerator as recited in claim 1, wherein the next state palette contains the next state address portion of the address into entries in said state table and a token value to be stored.

5. The parser accelerator as recited in claim 1, further including

means for detecting a character in a string which does not result in a change of state.

6. The parser accelerator as recited in claim 5, further including

means for immediate processing of the next character without a further memory operation for state table access.

7. The parser accelerator as recited in claim 2, wherein said pipeline is implemented in hardware.

8. The parser accelerator of claim 2, wherein said pipeline forms a loop including means for combining a next state address with a state table index from said character pallette.

9. A method of parsing an electronic file for identifying strings of interest, said method including steps of

storing respective portions of state table information in a character pallette, a state table and a next state pallette forming a looped pipeline to detect portions of said '"'"'string of interest,

obtaining token information from said state table, and

storing said token information in parallel with said detecting of portions of said string of interest.

10. A method as recited in claim 9, including the further step of

detecting sequences of strings of interest, and

issuing a special token responsive to said step of detecting sequences for controlling processing.

11. A method as recited in claim 10, wherein a said sequence of strings of interest includes a nested string.

12. A method as recited in claim 10, wherein a said sequence of strings of interest correspond to words or phrases of text in a document.

13. A method as recited in claim 10, wherein said further processing performs blocking of a message.

14. A method as recited in claim 10, wherein said further processing performs content based routing.