Fast data compressor with direct lookup table indexing into history buffer

A data compressor for compressing an input data block into a compressed data block, the data compressor comprising:

• means for maintaining a direct lookup table (DLT) array of DLT entries, each DLT entry being indexable in the DLT by a unique integer and identifying a location in the input data block;
• indexing means for using data at a current location in the input data block as an integer to directly access a given DLT entry, contents of the given DLT entry identifying a target location in the input data block;
• string comparison means for determining whether a target data string at the target location matches a current data string at the current location;
• literal means, responsive to a determination by the string comparison means that the data strings do not match, for outputting to the compressed data block a literal representing a datum at the current location;
• vector means, responsive to a determination by the string comparison means that the data strings match, for outputting to the compressed data file a vector to the target string;
• and
• means for updating the given DLT entry to identify the current location.

A data decompressor for decompressing a compressed data block, the data decompressor comprising:

• means for maintaining an output data block, the output data block including a current location;
• means for reading an indicator from the compressed data block;
• means for determining whether the indicator is a literal indicator or a vector indicator;
• literal means, responsive to a determination that the indicator is a literal indicator, for copying a literal datum from the compressed data block to the current location;
• vector means, responsive to a determination that the indicator is a vector indicator, for copying a string from a previous location in the output data block to the current location;
• and
• means for updating the current location to a new current location beyond the literal datum copied by the literal means or the string copied by the vector means.

A data compression method for compressing an input data block into a compressed data block, the data compression method comprising the steps of:

• A) maintaining a direct lookup table (DLT) of entries, each entry identifying a location in the input data block;
• B) selecting a current location in the input data block, a current data string existing at the current location;
• C) indexing an entry in the DLT with data at the current location to identify a target location in the input data block, a target data string existing at the target location;
• D) comparing the target data string to the current data string to determine whether the data strings match;
• E) responsive to a determination by the comparing step that the data strings do not match,
• E1) outputting the current data string as literal data to the compressed data block, and
• E2) updating the entry in the DLT indexed by the indexing step to identify the current location;
• F) responsive to a determination by the comparing step that the data strings match,
• F1) calculating an offset from the current location to the target location,
• F2) determining a length of the matching current data string, and
• F3) outputting the offset calculated in the calculating step and the length determined in the determining step as a vector to the compressed data block;
• G) advancing the current location past the current data string;
• and
• H) repeating steps C) to G) until the current location is not within the input data buffer, to compress the entire input data buffer.

A data decompression method of decompressing a compressed data block to form an output block, the compressed data block including literal data having literal indicators and further including vectors having vector indicators, a vector including an offset and a length, the method comprising the steps of:

• A) reading an indicator from the compressed data block;
• B) determining whether the indicator read is a literal indicator or a vector indicator;
• if the indicator read is a literal indicator,
• C) copying a literal datum from the compressed data block to a current location in the output block;
• if the indicator read is a vector indicator,
• D) reading an offset from the compressed data block;
• E) reading a length from the compressed data block;
• F) copying the read length of data from the output block at a location indicated by the read offset to a current location in the output block;
• and
• G) updating the current location in the output block to a location beyond the literal datum copied in step C) or the data copied in step F).

A compressed data file including one or more compressed data blocks, a compressed data block comprising:

• a literal including,
• a literal indicator, and
• a literal datum;
• and
• a vector including,
• a vector indicator,
• an offset, and
• a length.

Compressed data according to a format, said format comprising, in Backus Normal Form (BNF):

• ______________________________________ <compressed data>
• ::= <item>
• {<item>} <item>
• ::= <literal>
• .vertline. <vector>
• <literal>
• ::= <literal indicator>
• <literal datum>
• <vector>
• ::= <vector indicator>
• <offset>
• <length>
• ______________________________________