Microsoft Corporation
HIGH-PERFORMANCE MICROCODED TEXT PARSER

Abstract:

The performance of a text parser implemented with a state machine is improved by reducing a critical dependence path. In one aspect, all possible current states for a given text input are read from a state table circuit, and the correct next state and output are then selected therefrom by an output multiplexer based on the current state, removing dependence on the current state from the table read, and allowing the read(s) to be pipelined. Further, multiple input units are configured to operate on multiple text characters in parallel, with each input unit propagating outputs for its state table circuit to the next downstream input unit. Each downstream input unit is configured to use the propagated states to provide the proper outputs to appropriates multiplexer inputs. The number of possible output states may be dynamically reduced, thereby reducing the size of the output multiplexer needed to select the next state.