Back to results
US 6,310,563 B1Granted
Method and apparatus for enhanced decompressor parsing
AssigneeInternational Business Machines Corporation
InventorsDavid Har, Charles O. Schulz
Life of this patent
Estimating the term…
Abstract
In a high-speed computer system using multiple compression and decompression engines, a method and apparatus for coding and parsing compressed data in the decompressor in order to avoid bottlenecks within the decompressor that prevent it from achieving optimum latency and throughput acceptable to the system processor.
Claims46
A data compression/decompression system comprising:
- a compression engine for receiving uncompressed information units comprising raw characters and working strings and compressing them into compressed information units, said compressor engine having an associated dictionary table including entries comprising raw characters and reference strings, each reference string representing matched sequence of two or more bytes of data from an input working string;
- and,
- a decompression engine for receiving compressed information units and generating said uncompressed information units in decompression engine cycles, said decompression engine including a parser device for extracting consecutive data phrases of compressed information units, each data phrase comprising one of a predetermined set of characters, compressed strings or combinations thereof,
- wherein a data phrase includes a variable bit-length compression code for representing a matched sequence of bytes defining a compressed string, each variable bit-length compression code including a primary length field and a secondary length field for defining a string's length, and a position length field for encoding a starting address of the reference string in said dictionary to which a starting position of a working string refers, said parser device parsing said primary length fields and secondary length fields in different decompression engine cycles to enhance parser device throughput.
1 more element
A data decompression system for decompressing information units received in compressed form, said data decompression system comprising:
- a parser device for extracting consecutive data phrases of compressed information units at a parser device engine rate, each data phrase comprising one of a predetermined set of characters, compressed strings or combinations thereof;
- a tokenizer device associated with said parser device for receiving said data phrases and converting each data phrase into fixed bit-length tokens of shortened bit-length, each token including an indicator for identifying its corresponding phrase as comprising one of a raw character or a string;
- and,
- a decompression engine for receiving said tokens and generating corresponding uncompressed information units for output thereof at a predetermined data bus rate, whereby said parser device, tokenizer device and decompression engine operate at engine rates equal to or greater than said predetermined data bus rate for maximizing decompression throughput and reducing decompression time.
1 more element
A method for decompressing compressed data information units generated by a data compression engine, said method comprising the steps of:
- a) parsing said compressed information units and extracting consecutive data phrases at a parsing engine rate, each data phrase comprising one of a predetermined set of characters, compressed strings or combinations thereof;
- b) converting each extracted data phrase into fixed bit-length tokens of shortened bit-length, each said token including an indicator for identifying its corresponding phrase as comprising one of a compressed raw character or a compressed string;
- c) implementing a decompression engine for receiving said fixed bit-length tokens;
- and,
- d) processing said tokens at a decompression engine rate for outputting corresponding uncompressed information units at a predetermined data bus rate, wherein said parsing engine rate, tokenizing rate and decompression engine rate are equal to or greater than said predetermined data bus rate for maximizing decompression throughput and reducing decompression time.
2 more elements
Dependencies are inferred from the claim text.