Method and apparatus for compressing and decompressing data

• US 5,572,209 A
• Filed: 08/16/1994
• Issued: 11/05/1996
• Est. Priority Date: 08/16/1994
• Status: Expired due to Fees

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Farmer, Henry R., Wilson, Anne A.
• Primary Examiner(s): Young, Brian K.
• Application Number:
  US08/291,694
• Time in Patent Office: 812 Days
• Field of Search: 341/67, 341/50, 341/87, 395/162, 395/163, 395/164, 395/165, 395/166
• US Class Current: 341/67
• CPC Class Codes: G06F 16/1744 using compression, e.g. sparse files
• CPC Class Codes: G06T 9/005 Statistical coding, e.g. Huffman, run length coding
• CPC Class Codes: H03M 7/3086 employing a sliding window, e.g. LZ77

Abstract

A data processing system having a compression and decompression apparatus based on the Lempel-Ziv algorithm. The compression apparatus includes a history RAM unit for receiving and storing one or more data elements and a coding unit for determining whether received data elements previously have been stored in the history RAM unit and are a candidate for compression. If a received data element matches at least one of the stored data elements, an address of the matching stored data element is generated. The compression apparatus generates a compression token comprising an identification of whether a data element is compressed, the length of the coded data within a plurality of predetermined data length categories and an address. The decompression apparatus also includes a history RAM unit for storing received data elements and includes a circuit for receiving a compression token and determining the storage addresses of the next data element from the length and address information contained in the token. The apparatus can identify the next address at high speed by a parallel processing using the predetermined length categories.

Claims

1. An apparatus for processing compressed, variable length data items in a data compression system, said apparatus comprising:

code storing means for storing variable length code items, each code item representing a corresponding variable length data item and comprising a corresponding number of code bits which are within one of a predetermined number of possible variable length code cases;

means for decoding said stored code bits and outputting a signal identifying a length case within one of said possible variable length code cases;

means for concurrently generating the sums of the number of code bits in each of said variable length code bit cases and a starting address of a first code item in order to generate a plurality of possible starting addresses for a second code item; and

means for selecting one of said plurality of possible starting addresses for said second code item on the basis of the signal output by said decoding means.

2. A processing apparatus as set forth in claim 1 further comprising:

data item storing means for storing variable length data items, said data item storing means having a plurality of addresses and being of a predetermined size, wherein each data item necessarily has an actual length value, said actual length value being within one of a predetermined number of possible length cases and being represented by code bits which are within one of said predetermined number of possible variable length code cases; and

wherein the number of code bits provided for each code case by said concurrent generating means relates to the size of said data item storing means.

3. A processing apparatus as set forth in claim 1 further comprising:

code length storing means for storing each of said variable length possibilities and outputting a plurality of said possibilities in parallel;

adder means for receiving each of said outputted variable length possibilities and said starting address for a first code item, said adder means providing in parallel said plurality of possible starting addresses for said second code item.

4. An apparatus for processing a plurality of sequentially arranged compressed code tokens representing original data, each code token having one of a plurality of possible variable lengths and comprising compression information and code length information, said apparatus comprising:

a) means for storing code tokens, said means being of sufficient size to store each of a first code token and a second code token, each said stored tokens being any one of said possible variable lengths;

b) means for aligning said stored code tokens for providing aligned storage locations for said first and second code tokens irrespective of code token length;

c) means for decoding said code length information for said first stored code token and identifying one of said plurality of code lengths;

d) means for providing a current address, said current address being used to determine the location of said first code token in said token storing means;

e) means for concurrently providing all of said plurality of possible variable code length values;

f) means responsive to said plurality of possible variable code length values and said current address for generating a plurality of possible next addresses for said second code token; and

g) means responsive to said decoding means for selecting a next address in said token storing means for said second code token.

5. The processing apparatus as set forth in claim 4 wherein said length providing means comprises fixed length means for generating a predetermined plurality of variable fixed length values, and a plurality of adder means each for receiving a current address value and corresponding variable address size for generating a plurality of possible next addresses.

6. The processing apparatus as set forth in claim 4 wherein said alignment means comprises a barrel shifter memory operative to receive each of said code tokens separately.

7. The processing apparatus as set forth in claim 6 wherein said barrel shifter memory provides left-adjustment for received tokens.

8. The processing apparatus as set forth in claim 4 further comprising means for receiving at least part of each variable length code token and assembling said parts in said storage means as a complete token.

9. The processing apparatus as set forth in claim 4 further comprising means for determining if said entire current code token is stored in said storing means by comparing each said possible next address with available segment data.

10. The processing apparatus as set forth in claim 9 further comprising output means for storing an entire adjusted code word from said adjusting means in response to said determining means.

11. The processing apparatus as set forth in claim 10 further comprising means responsive to said current address and available segment data for delaying the introduction of a new code token until a current code token is decompressed.

12. A data compression and decompression system comprising:

a) a data compressor for receiving variable length data elements and generating variable length codes comprising raw data tokens, comprising raw data and a length code, and compressed word tokens for data elements that match previously received data elements, said compressed word tokens comprising a compression code, an address and a variable length code representing one of a predetermined number of variable length possibilities; and

b) a data decompressor comprising;

i) means for storing variable length tokens, said storage means having a plurality of addresses;

ii) means for decoding said length code of a first variable length code and outputting a signal identifying one of said length possibilities;

iii) means for adding in parallel all variable length possibilities of said first variable length code to its starting address to generate plural possible next addresses; and

iv) means for selecting one of said possible next addresses as the starting addresses for a subsequent variable length code on the basis of the output of said decoding means.

13. A compression and decompression system as set forth in claim 12 wherein said adding means comprises means for storing a predetermined plurality of variable fixed length values, and a plurality of adders each for receiving a common starting address value and a respective variable address size for generating said plurality of possible next addresses.

14. A compression and decompression system as set forth in claim 12 further comprising in said decompressor a means for determining if said entire current code token is stored in said storing means by comparing each said possible next address with available segment data.

15. A compression and decompression system as set forth in claim 12, said decompressor further comprising:

history buffer means for storing decompressed raw data;

output means for storing an entire code word position-adjusted in common with respect to all other code words and outputting said code word in response to said selecting means; and

decode means for decoding said output code word and controlling storage of variable length data elements in said history buffer means.

16. A method of decompressing compressed data, said compressed data being represented by a code token comprising a status code indicating its status as compressed data, a length code indicating its length within a predetermined plurality of length value cases and an address in a history memory, comprising:

a) decoding said length code and identifying one of said plurality of length value cases,

b) concurrently with said decoding step, determining an identity between a plurality of possible next code token addresses and an available code token storage area by

(i) adding all possible code lengths to a current code token address for generating plural possible next addresses, and

(ii) determining for said plural possible next code token addresses on the basis of an available storage segment an identity of values; and

c) selecting a next code token address on the basis of said identified length value cases and said determined identity of values.

17. The method as set forth in claim 16, further comprising:

selecting said length code value on the basis of the size of said history memory.

18. The method as set forth in claim 16, further comprising:

aligning said stored code tokens for providing aligned storage locations for said first and second code tokens irrespective of code token length.

19. The method as set forth in claim 18, wherein said aligning step comprises barrel shifting each of said code tokens separately.

20. The method as set forth in claim 16, comprising:

receiving at least part of each variable length code token and assembling said parts in said storage means as a complete token; and

determining if said entire current code token is stored in said storing means by comparing each said possible next address with available segment data.