BITSTREAM PROCESSING USING COALESCED BUFFERS AND DELAYED MATCHING AND ENHANCED MEMORY WRITES

摘要

Methods and apparatus for processing bitstreams and byte streams. According to one aspect, bitstream data is compressed using coalesced string match tokens with delayed matching. A matcher is employed to perform search string match operations using a shortened maximum string length search criteria, resulting in generation of a token stream having data and literal data. A distance match operation is performed on sequentially adjacent tokens to determine if they contain the same distance data. If they do, the len values of the tokens are added through use of a coalesce buffer. Upon detection of a distance non-match, a final coalesced length of a matching string is calculated and output along with the prior matching distance as a coalesced token. Also disclosed is a scheme for writing variable-length tokens into a bitstream under which token data is input into a bit accumulator and written to memory (or cache to be subsequently written to memory) as each token is processed in a manner that eliminates branch mispredict operations associated with detecting whether the bit accumulator is full or close to full.

主权项

1. A method, comprising:
receiving an original token stream comprising a plurality of original tokens generated by a sliding-window string match search scheme, the original tokens including tokens comprising original len and distance data; and processing the original token stream to generate a coalesced token stream in which a portion of the original tokens are replaced with coalesced tokens including coalesced len and distance data.