Fast data compressor with direct lookup table indexing into history buffer

Claim 3

The apparatus of claim 1, wherein target strings begin at target locations in the input data block and a current string begins at the current location, the apparatus further comprising: string comparison means for determining whether a target string at a target location identified by the given DLT entry matches the current string.

Claim 4

The apparatus of claim 2, further comprising: data compression means for compressing the input data block responsive to the string comparison means, to generate a compressed data block.

Claim 5

The apparatus of claim 3, wherein the data compression means comprises: literal means, responsive to a determination by the string comparison means that the target and current strings do not match, for outputting to the compressed data block a literal representing a datum at the current location; and vector means, responsive to a determination by the string comparison means that the target and current strings match, for outputting to the compressed data file a vector to the target string.

Claim 6

The apparatus of claim 1, wherein: the indexing means uses N bytes at the current location to index the DLT, where N is an integer; and the means for maintaining the DLT maintains the DLT to comprise 2 8 ×N DLT entries.

Claim 7

The apparatus of claim 5, wherein: the DLT comprises sixty-four kiloentries (2 2 ×8 DLT entries); and the indexing means uses a current byte at the current location and a next byte at a next subsequent location to index the DLT.

Claim 8

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.

Claim 9

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.

Claim 10

The data compressor of claim 7, further comprising: means for maintaining the input data block in a history buffer.

Claim 11

The data compressor of claim 7, wherein the literal comprises: a literal indicator; and the datum at the current location.

Claim 12

The data compressor of claim 9, wherein the literal indicator comprises: the bit 0 2 .

Claim 13

The data compressor of claim 7, wherein the vector comprises: a vector indicator; an offset from the current location to the target location; and a length of the current string which matches the target match string.

Claim 14

The data compressor of claim 11, wherein the vector indicator comprises: the bit 1 2 .

Claim 15

The data compressor of claim 11, wherein the offset comprises: one of a plurality of special case offsets.

Claim 16

The data compressor of claim 11, wherein the offset comprises: an offset length indicator indicating a number of offset value bits; and an offset value of the indicated number of bits.

Claim 17

The data compressor of claim 14, wherein the offset length indicator comprises: a short offset indicator; or a long offset indicator.

Claim 18

The data compressor of claim 15, wherein: the vector means is further for outputting a short offset vector when the offset from the current string to the matching string can be vectored with a short offset vector.

Claim 19

The data compressor of claim 15, wherein: the short offset indicator comprises the bit 0 2 and specifies an eight-bit offset; and the long offset indicator comprises the bit 1 2 and specifies a twelve-bit offset.

Claim 20

The data compressor of claim 11, wherein the length comprises: one of a plurality of special case length identifiers.

Claim 21

The data compressor of claim 11, wherein the length comprises: the bit 0 2 specifying a matching string length of two; the bits 100 2 specifying a matching string length of three; the bits 101 2 specifying a matching string length of four; or the bits 11 2 specifying a matching string length of greater-than-four, and a length specifier specifying how much greater than four the matching string length is.

Claim 22

The data compressor of claim 19, wherein the length specifier comprises: four bits in the range 0000 2 to 1111 2 for adding to five, to specify a matching string length in the range of five to twenty.

Claim 23

The data compressor of claim 7, further comprising: header means for outputting a block header to the compressed data block.

Claim 24

The data compressor of claim 21, wherein the block header comprises: an indication of a size of the input data block.

Claim 25

The data compressor of claim 21, wherein the header means further comprises: means for generating a checksum over the compressed data block.

Claim 26

The data compressor of claim 7, further comprising: means for pre-processing the input data block.

Claim 27

The data compressor of claim 24, wherein the means for pre-processing comprises: means for performing a D function on the input data block.

Claim 28

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.

Claim 29

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.

Claim 30

The data decompressor of claim 26, wherein the literal indicator comprises: the bit 0 2 .

Claim 31

The data decompressor of claim 26, wherein: the compressed data block includes a vector including the vector indicator and an offset indicator and a length indicator; the vector means is further for calculating an offset from the current location to the previous location according to the length indicator; the vector means is further for calculating a string length according to the length indicator; and the string copied by the vector means has the calculated string length.

Claim 32

The data decompressor of claim 28, wherein the vector indicator comprises: the bit 1 2 .

Claim 33

The data decompressor of claim 28, wherein the offset indicator comprises: an offset length indicator indicating a number of offset value bits; and an offset value of the indicated number of offset value bits.

Claim 34

The data decompressor of claim 30, wherein the offset length indicator comprises: a short offset indicator; or a long offset indicator.

Claim 35

The data decompressor of claim 31, wherein: the short offset indicator comprises the bit 0 2 and specifies an eight-bit offset; and the long offset indicator comprises the bit 1 2 and specifies a twelve-bit offset.

Claim 36

The data decompressor of claim 28, wherein: the length indicator comprises the bit 0 2 , and the vector means copies a string of length two responsive thereto; the length indicator comprises the bits 100 2 , and the vector means copies a string of length three responsive thereto; the length indicator comprises the bits 101 2 , and the vector means copies a string of length four response thereto; or the length indicator comprises the bits 11 2 and a plurality of additional length indicator bits, and the vector means copies a string of length greater than four in response thereto.

Claim 37

The data decompressor of claim 26, wherein: the means for maintaining the output data block maintains the output data block in a history buffer.

Claim 38

The data decompressor of claim 32, wherein the compressed data block includes a header specifying a decompressed size of the compressed data block, and wherein: the means for maintaining the output data block selects a size of the history buffer according to the decompressed size specified in the header.

Claim 39

The data decompressor of claim 35, wherein the header further specifies a pre-processing technique, the data decompressor further comprising: means for performing the specified pre-processing technique upon the compressed data block before operation of the means for reading, means for determining, literal means, vector means, and means for updating operate upon the compressed data block.

Claim 40

The data decompressor of claim 36, wherein: the specified pre-processing technique is a D function.

Claim 41

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.

Claim 42

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.

Claim 43

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).

Claim 44

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).

Claim 45

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.

Claim 46

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.

Claim 47

The compressed data file of claim 40, wherein said offset comprises: an offset size indicator; and an offset indicator.

Claim 48

The compressed data file of claim 41, wherein: said offset size indicator comprises a short offset indicator; and said offset indicator comprises a short offset.

Claim 49

The compressed data file of claim 42, wherein: said short offset indicator comprises the bit 0 2 ; and said short offset comprises eight bits.

Claim 50

The compressed data file of claim 41, wherein: said offset size indicator comprises a long offset indicator; and said offset indicator comprises a long offset.

Claim 51

The compressed data file of claim 44, wherein: said long offset indicator comprises the bit 1 2 ; and said long offset comprises twelve bits.

Claim 52

The compressed data file of claim 40, wherein: said length comprises one of a plurality of special case length indicators.

Claim 53

The compressed data file of claim 46, wherein said plurality of special case length indicators comprises: a length two indicator; a length three indicator; a length four indicator; and a length greater-than-four indicator.

Claim 54

The compressed data file of claim 47 wherein said length greater-than-four indicator includes: a length specifier.

Claim 55

The compressed data file of claim 47, wherein said length two indicator comprises: the bit 0 2 .

Claim 56

The compressed data file of claim 47, wherein said length three indicator comprises: the bits 100 2 .

Claim 57

The compressed data file of claim 47, wherein said length four indicator comprises: the bits 101 2 .

Claim 58

The compressed data file of claim 47, wherein said length greater-than-four indicator comprises: the bits 11 2 ; and a length specifier including four bits.

Claim 59

The compressed data file of claim 40, wherein: said lateral indicator comprises the bit 0 2 ; and said literal datum comprises eight bits.

Claim 60

Compressed data according to a format, said format comprising, in Backus Normal Form (BNF): ______________________________________ <compressed data> ::= <item> {<item>} <item> ::= <literal> | <vector> <literal> ::= <literal indicator> <literal datum> <vector> ::= <vector indicator> <offset> <length> ______________________________________

Claim 61

Compressed data according to a format, said format comprising, in Backus Normal Form (BNF): ______________________________________ <compressed data> ::= <item> {<item>} <item> ::= <literal> | <vector> <literal> ::= <literal indicator> <literal datum> <vector> ::= <vector indicator> <offset> <length> ______________________________________

Claim 62

The compressed data of claim 54, wherein said format further comprises, in BNF: ______________________________________ <offset> ::= <short size offset> | <long size offset> <short size offset> ::= <short offset indicator> <short offset> <long size offset> ::= <long offset indicator> <long offset> ______________________________________

Claim 63

The compressed data of claim 54, wherein said format further comprises, in BNF: ______________________________________ <length> ::= <length two indicator> | <length three indicator> | <length four indicator> | <length greater than four indicator> <length specifier> ______________________________________