Dictionary reset performance enhancement for data compression applications

• US 5,175,543 A
• Filed: 09/25/1991
• Issued: 12/29/1992
• Est. Priority Date: 09/25/1991
• Status: Expired due to Term

• Current Assignee: Hewlett-Packard Company (HP Inc.)
• Original Assignee: Hewlett-Packard Company (HP Inc.)
• Inventors: Lantz, Carl B.
• Primary Examiner(s): Pellinen, A. D.
• Assistant Examiner(s): YOUNG, BRIAN K
• Application Number:
  US07/766,475
• Time in Patent Office: 461 Days
• Field of Search: 341/51, 341/106, 341/52, 341/55, 341/87, 341/94, 341/95, 341/90, 358/261.2, 358/261.4, 358/430
• US Class Current: 341/51
• CPC Class Codes: G06T 9/005 Statistical coding, e.g. Huffman, run length coding
• CPC Class Codes: H03M 7/3088 employing the use of a dictionary, e.g. LZ78

Abstract

A class of lossless data compression algorithms use a RAM-based dictionary to facilitate the compression and decompression of data. The dictionary is initialized or reset at various events, such as data file boundaries, or at specific compression ratio thresholds. The average time to perform the dictionary reset is decreased by using a dictionary reset optimizer (12) to reset the dictionary without writing the DICT_-- VALID fields (19) of all dictionary locations (1,2,3, . . . L) immediately upon each reset. The DICT_-- VALID field in static RAM (16) is set up as an N-bit field and the optimizer includes a counter (20) for generating an N-bit DICT_-- NUMBER field (22) under control of a controller (24) responsive to reset signals. During operation to compress/decompress data after a reset, the DICT_-- VALID field of a dictionary location is compared to the current DICT_-- NUMBER (1). If their values are equal, the DICT_-- ENTRY field (18) in such location is deemed valid. Otherwise, the DICT_-- ENTRY field is rewritten with new compression data and the DICT_-- VALID field is reset equal to the current DICT_-- NUMBER (1). Upon each reset, the counter is incremented to provide a new DICT_-- NUMBER (2) whose value will no longer match current DICT_-- VALID values stored in the dictionary locations.

Claims

1. A dictionary-based data compressor/decompressor system comprising:

a memory device having L dictionary locations, each location including a first data field for storing a dictionary compression data entry to use in compressing/decompressing input data and a corresponding second data field for storing a dictionary status word comprising at least two binary digits indicating whether the corresponding dictionary data entry is in a valid or reset state;

a data compression engine having data input and output ports and input/output ports for reading and writing to the first and second fields of a selected location in the memory device, the data compression engine including means for compressing/decompressing input data and reading/writing dictionary data entries in the dictionary locations in accordance with a predetermined compression algorithm; and

a dictionary reset optimizer coupled between the memory device and the data compression engine including;

means for generating a dictionary number comprising at least two binary digits; and

means for comparing the dictionary number to the dictionary status word in one of said dictionary locations to determine whether they match in accordance with a predetermined relationship and thereby determine whether the corresponding dictionary data entry is in either a valid or reset state;

the data compression engine being responsive to the comparing means to read the dictionary compression data entry stored in the corresponding first data field if a valid state is determined and to write a new dictionary compression data entry into the corresponding first data field if a reset state is determined.

2. A dictionary-based data compressor/decompressor system according to claim 1 in which the comparing means is a binary comparator wherein the generated dictionary number and the stored dictionary status word are compared to determine whether they are equal.

3. A dictionary-based data compressor/decompressor system comprising:

a memory device having L dictionary locations, each location including a first data field for storing a dictionary compression data entry to use in compressing/decompressing input data and a corresponding second data field for storing a dictionary status word comprising at least two binary digits indicating whether the corresponding dictionary data entry is in a valid or reset state;

a data compression engine having data input and output ports and input/output ports for reading and writing to the first and second fields of a selected location in the memory device, the data compression engine including means for compressing/decompressing input data and reading/writing dictionary data entries in the dictionary locations in accordance with a predetermined compression algorithm; and

a dictionary reset optimizer coupled between the memory device and the data compression engine including;

means for generating a dictionary number comprising at least two binary digits;

means for comparing the dictionary number to the dictionary status word in one of said dictionary locations to determine whether the corresponding dictionary data entry is in either a valid or reset state; and

controller means responsive to a reset signal for causing the generating means to generate a new dictionary number so that the comparing means subsequently determines by comparison of the new dictionary number to a prior dictionary number stored in each dictionary location that the dictionary compression data entry stored in such location is in a reset state and causes the data compression engine to write a new dictionary compression data entry into the corresponding first data field and the new dictionary number into the second data field

the data compression engine being responsive to the comparing means to read the dictionary compression data entry stored in the corresponding first data field if a valid state is determined and to write a new dictionary compression data entry into the corresponding first data field if a reset state is determined.

4. A dictionary-based data compressor/decompressor system according to claim 3 in which the data compression engine includes means for outputting the reset signal to the dictionary reset optimizer.

5. A dictionary-based data compressor/decompressor system according to claim 3 in which:

the memory device includes read, write and address inputs;

the data compression engine includes first write and address outputs;

the controller means includes second write and address outputs; and

the dictionary reset optimizer includes means responsive to the controller means for selecting between the first and the second write and address outputs.

6. A dictionary-based data compressor/decompressor system

comprising:

a memory device having L dictionary locations, each location including a first data field for storing a dictionary compression data entry to use in compressing/decompressing input data and a corresponding second data field for storing a dictionary status word comprising at least two binary digits indicating whether the corresponding dictionary data entry is in a valid or reset state;

a data compression engine having data input and output ports and input/output ports for reading and writing to the first and second fields of a selected location in the memory device, and a single-bit output/input for transmitting/receiving a dictionary status signal to/from the memory device, the data compression engine including means for compressing/decompressing input data and reading/writing dictionary data entries in the dictionary locations in accordance with a predetermined compression algorithm; and

a dictionary reset optimizer coupled between the memory device and the data compression engine including;

means for generating a dictionary number comprising at least two binary digits;

means for comparing the dictionary number to the dictionary status word in one of said dictionary locations to determine whether the corresponding dictionary data entry is in either a valid or reset state; and

means interposed between the data compression engine and the memory device for translating between said single-bit output/input and said dictionary status word comprising at least two binary digits;

the data compression engine being responsive to the comparing means to read the dictionary compression data entry stored in the corresponding first data field if a valid state is determined and to write a new dictionary compression data entry into the corresponding first data field if a reset state is determined.

7. A dictionary reset optimizer for a resettable dictionary-based data compressor/decompressor system which includes a memory device having L dictionary locations, each location storing a dictionary data entry and an N-bit dictionary status word, and a data compression engine for reading/writing dictionary data entries in the dictionary locations to compress/decompress input data in accordance with a predetermined compression algorithm, the dictionary reset optimizer comprising:

a dictionary number generator for generating an N-bit dictionary number, N being an integer equal to or greater than 2;

a dictionary-valid determining means including a binary comparator for comparing the N-bit dictionary number to the N-bit dictionary status word in one of said dictionary locations to determine whether or not the dictionary number and the dictionary status word match in accordance with a predetermined relationship and providing an output signal to indicate to the data compression engine whether the data entry in said one location is valid based on whether the dictionary number and the dictionary status word match; and

controller means responsive to a reset condition for causing the generating means to generate a new dictionary number so that the new dictionary number does not match a prior dictionary number stored in each dictionary location.

8. A dictionary reset optimizer according to claim 7 in which the dictionary number generator includes a binary sequencer which outputs the N-bit dictionary number.

9. A dictionary reset optimizer according to claim 8 in which the controller means includes an output to the dictionary number generator which causes the binary sequencer to sequence the N-bit dictionary number.

10. A dictionary reset optimizer according to claim 7 in which the dictionary-valid determining means is operable in two states:

a write state in which the N-bit dictionary number is written into the N-bit dictionary status word in one of said dictionary locations and a read state in which the N-bit dictionary status word of a selected location in the dictionary is read and input to the binary comparator.

11. A dictionary reset optimizer according to claim 7 in which the dictionary-valid determining means includes switching circuitry selectably operable to read and input the N-bit dictionary status word stored in a selected dictionary location and the N-bit dictionary number to the binary comparator, and to write the N-bit dictionary number into the N-bit dictionary status word in the selected dictionary location if the dictionary number does not match the stored dictionary status word.

12. A dictionary reset optimizer according to claim 11 including write-selection means having an output controllably coupled to the switching circuitry.

13. A dictionary reset optimizer according to claim 7 including write-selection means having a first write input from the data compression engine and a second write input from the controller means for providing one of said write inputs as an output signal selectable by the controller means.

14. A dictionary reset optimizer according to claim 7 including address-selection means having a first address input from the data compression engine and a second address input from the controller means for providing one of said address inputs as an output signal selectable by the controller means.

15. A dictionary reset optimization method for resetting a dictionary-based data compressor/decompressor system which includes a memory having L dictionary locations each including a multibit dictionary data entry field, and a data compression engine for reading/writing dictionary data entries in the dictionary locations to compress/decompress input data in accordance with a predetermined compression algorithm, the optimization method comprising:

allocating storage in each of the L dictionary locations to include an N-bit dictionary status field, N being an integer equal to or greater than 2;

generating a first N-bit dictionary number;

storing the dictionary number as a dictionary status word in association with a compression data entry in one or more of the L dictionary locations;

reading a dictionary status word stored in the dictionary status field of a selected one of the L dictionary locations;

comparing the dictionary number to the dictionary status word to determine whether or not the dictionary number and the dictionary status word match in accordance with a predetermined relationship;

signalling to the data compression engine whether the data entry in said one location is valid based on whether the dictionary number and the dictionary status word match; and

responsive to a reset condition, generating a second N-bit dictionary number so that the second dictionary number does not match the stored first dictionary number.

16. A method according to claim 15 wherein the dictionary number and the dictionary status word of a selected one of the L dictionary locations match in the comparing step, including:

reading the compression data entry stored in the data entry field of the selected dictionary location; and

using the stored data entry to compress/decompress input data in accordance with said predetermined compression algorithm.

17. A method according to claim 15 wherein the dictionary number and the dictionary status word of a selected one of the L dictionary locations do not match in the comparing step, including:

writing a new compression data entry in the data entry field of the selected dictionary location for subsequent use in compressing/decompressing input data in accordance with said predetermined compression algorithm; and

writing the second dictionary number dictionary status word in the dictionary status field of the selected dictionary location.

18. A method according to claim 17 including, immediately following generation of a second N-bit dictionary number, repeating the storing, reading, comparing and writing steps using the second N-bit dictionary number so that the dictionary is rebuilt.

19. A method according to claim 15 including:

repeating the reading and comparing steps using the first N-bit dictionary number until a reset condition has occurred; and

immediately following occurrence of a reset condition and generation of a second N-bit dictionary number, repeating the storing, reading and comparing steps using the second N-bit dictionary number without first writing the second N-bit dictionary number in each of the L dictionary locations.

20. A method according to claim 15, responsive to each of 2ⁿ -1 reset conditions, including sequencing through 2ⁿ -1 values of the N-bit dictionary number and repeating the storing, reading and comparing steps using each sequential dictionary number.

21. A method according to claim 20, responsive to a 2ⁿ th reset condition, including sequencing the N-bit dictionary number to a default value of the dictionary number and writing said default value as the dictionary status word in the dictionary status field in each of the L dictionary locations.