Fast data compressor with direct lookup table indexing into history buffer

• US 5,155,484 A
• Filed: 09/13/1991
• Issued: 10/13/1992
• Est. Priority Date: 09/13/1991
• Status: Expired due to Term

• Current Assignee: Symantec Corporation (NortonLifeLock Inc.)
• Original Assignee: Salient Software, Inc.
• Inventors: Chambers, Lloyd L. IV
• Primary Examiner(s): Logan, Sharon D.
• Application Number:
  US07/759,226
• Time in Patent Office: 396 Days
• Field of Search: 341/55, 341/106, 341/50
• US Class Current: 341/55
• CPC Class Codes: G06F 12/0802 Addressing of a memory level in which the access to the desired data or data block requires associative addressing means, e.g. caches
• CPC Class Codes: G06F 16/90344 by using string matching techniques
• CPC Class Codes: G06F 18/00 Pattern recognition
• CPC Class Codes: G06F 40/12 Use of codes for handling textual entities
• CPC Class Codes: G06F 40/194 Calculation of difference between files
• CPC Class Codes: G06T 9/005 Statistical coding, e.g. Huffman, run length coding
• CPC Class Codes: G06T 9/008 Vector quantisation
• CPC Class Codes: G06V 10/768 using context analysis, e.g. recognition aided by known co-occurring patterns
• CPC Class Codes: H03M 7/3084 using adaptive string matching, e.g. the Lempel-Ziv method
• CPC Class Codes: H03M 7/3086 employing a sliding window, e.g. LZ77

Abstract

A cooperating data compressor, compressed data format, and data decompressor. The compressor compresses an input data block (HB) to a compressed data block having the format. The decompressor decompresses the compressed data block to restore the original data block. The compressor has a direct lookup table (DLT) of 2⁸×N entries, each indexable by N bytes at a current HB location and identifying a target HB location. The compressor determines whether a target string at the target HB location matches a current string at the current HB location. If they do not match, the compressor outputs a literal representing a datum at the current location. If they match, the compressor outputs a vector from the current location to the target string. Compression speed is maximized by the direct addressing of the DLT by the current N bytes in the HB. Decompression speed is maximized by state machine operation according to literal/vector indicators, special case string length codes, and special case offset codes in the compressed data format.

Claims

1. An apparatus operating upon an input data block, the apparatus 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; and

indexing means for using one or more bytes 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.

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

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

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

5. 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⁸×

N DLT entries.

6. The apparatus of claim 5, wherein:

the DLT comprises sixty-four kiloentries (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.

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

8. The data compressor of claim 7, further comprising:

means for maintaining the input data block in a history buffer.

9. The data compressor of claim 7, wherein the literal comprises:

a literal indicator; and

the datum at the current location.

10. The data compressor of claim 9, wherein the literal indicator comprises:

the bit 0₂.

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

12. The data compressor of claim 11, wherein the vector indicator comprises:

the bit 1₂.

13. The data compressor of claim 11, wherein the offset comprises:

one of a plurality of special case offsets.

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

15. The data compressor of claim 14, wherein the offset length indicator comprises:

a short offset indicator;

or

a long offset indicator.

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

17. The data compressor of claim 15, wherein:

the short offset indicator comprises the bit 0₂ and specifies an eight-bit offset; and

the long offset indicator comprises the bit 1₂ and specifies a twelve-bit offset.

18. The data compressor of claim 11, wherein the length comprises:

one of a plurality of special case length identifiers.

19. The data compressor of claim 11, wherein the length comprises:

the bit 0₂ specifying a matching string length of two;

the bits 100₂ specifying a matching string length of three;

the bits 101₂ specifying a matching string length of four;

or

the bits 11₂ specifying a matching string length of greater-than-four, and a length specifier specifying how much greater than four the matching string length is.

20. The data compressor of claim 19, wherein the length specifier comprises:

four bits in the range 0000₂ to 1111₂ for adding to five, to specify a matching string length in the range of five to twenty.

21. The data compressor of claim 7, further comprising:

header means for outputting a block header to the compressed data block.

22. The data compressor of claim 21, wherein the block header comprises:

an indication of a size of the input data block.

23. The data compressor of claim 21, wherein the header means further comprises:

means for generating a checksum over the compressed data block.

24. The data compressor of claim 7, further comprising:

means for pre-processing the input data block.

25. The data compressor of claim 24, wherein the means for pre-processing comprises:

means for performing a D function on the input data block.

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

27. The data decompressor of claim 26, wherein the literal indicator comprises:

the bit 0₂.

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

29. The data decompressor of claim 28, wherein the vector indicator comprises:

the bit 1₂.

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

31. The data decompressor of claim 30, wherein the offset length indicator comprises:

a short offset indicator;

or

a long offset indicator.

32. The data decompressor of claim 31, wherein:

the short offset indicator comprises the bit 0₂ and specifies an eight-bit offset; and

the long offset indicator comprises the bit 1₂ and specifies a twelve-bit offset.

33. The data decompressor of claim 28, wherein:

the length indicator comprises the bit 0₂, and the vector means copies a string of length two responsive thereto;

the length indicator comprises the bits 100₂, and the vector means copies a string of length three responsive thereto;

the length indicator comprises the bits 101₂, and the vector means copies a string of length four response thereto;

or

the length indicator comprises the bits 11₂ and a plurality of additional length indicator bits, and the vector means copies a string of length greater than four in response thereto.

34. The data decompressor of claim 26, wherein:

the means for maintaining the output data block maintains the output data block in a history buffer.

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

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

37. The data decompressor of claim 36, wherein:

the specified pre-processing technique is a D function.

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

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

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

41. The compressed data file of claim 40, wherein said offset comprises:

an offset size indicator; and

an offset indicator.

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

43. The compressed data file of claim 42, wherein:

said short offset indicator comprises the bit 0₂ ; and

said short offset comprises eight bits.

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

45. The compressed data file of claim 44, wherein:

said long offset indicator comprises the bit 1₂ ; and

said long offset comprises twelve bits.

46. The compressed data file of claim 40, wherein:

said length comprises one of a plurality of special case length indicators.

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

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

a length specifier.

49. The compressed data file of claim 47, wherein said length two indicator comprises:

the bit 0₂.

50. The compressed data file of claim 47, wherein said length three indicator comprises:

the bits 100₂.

51. The compressed data file of claim 47, wherein said length four indicator comprises:

the bits 101₂.

52. The compressed data file of claim 47, wherein said length greater-than-four indicator comprises:

the bits 11₂ ; and

a length specifier including four bits.

53. The compressed data file of claim 40, wherein:

said lateral indicator comprises the bit 0₂ ; and

said literal datum comprises eight bits.

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

space="preserve" listing-type="tabular">______________________________________ <

compressed data>

;

;

= <

item>

{<

item>

} <

item>

;

;

= <

literal>

| <

vector>

<

literal>

;

;

= <

literal indicator>

<

literal datum>

<

vector>

;

;

= <

vector indicator>

<

offset>

<

length>

______________________________________

55. The compressed data of claim 54, wherein said format further comprises, in BNF:

space="preserve" listing-type="tabular">______________________________________ <

offset>

;

;

= <

short size offset>

| <

long size offset>

<

short size offset>

;

;

= <

short offset indicator>

<

short offset>

<

long size offset>

;

;

= <

long offset indicator>

<

long offset>

______________________________________

56. The compressed data of claim 54, wherein said format further comprises, in BNF:

space="preserve" listing-type="tabular">______________________________________ <

length>

;

;

= <

length two indicator>

| <

length three indicator>

| <

length four indicator>

| <

length greater than four indicator>

<

length specifier>

______________________________________