Hardware-based, LZW data compression co-processor

• US 6,624,762 B1
• Filed: 04/11/2002
• Issued: 09/23/2003
• Est. Priority Date: 04/11/2002
• Status: Active Grant

• Current Assignee: Unisys Corporation
• Original Assignee: Unisys Corporation
• Inventors: End, Joseph H III
• Primary Examiner(s): WAMSLEY, PATRICK G
• Application Number:
  US10/120,467
• Time in Patent Office: 530 Days
• Field of Search: 341/51, 341/55, 341/63, 341/67, 341/79, 341/95, 341/106, 341/107, 341/50, 341/87, 358/1.15, 382/232, 707/10, 707/101, 708/203
• US Class Current: 341/51
• CPC Class Codes: H03M 7/3088 employing the use of a dictionary, e.g. LZ78

Abstract

The present invention is directed to an improved system for creating LZW compressed files by executing the LZW data compression algorithm on a plurality of special-purposed pipelined processing units, each of which contains hardware-embedded control algorithms. The data paths of the plurality of processors, together with the state machines that control the flow of data through them, provide pipelined execution of the LZW algorithm. For example, at the same instant, processor three can be processing a first input byte, processor two can be processing a second input byte, and processor one can be processing a third input byte.

Claims

1. A system for executing an LZW compression algorithm, the system comprising a plurality of processors each comprising a data path and an associated state machine that controls the flow of data through the data path, the data paths of said plurality of processors being coupled to provide simultaneous execution of different steps of the LZW compression algorithm by different ones of the processors on successive bytes of an input stream, said plurality of processors comprising:

a first processor that performs a hashing function to calculate an index value based upon a byte string value from an input data stream, the index value being used as a hash table address to assign a location in a hash table data structure to a code word representing the byte string value and retrieve the code word value from the assigned location;

a second processor coupled to the first processor that stores in a dictionary data structure a linked list of byte strings from the input data stream, each byte string stored in the dictionary data structure being associated with a code word, the second processor comparing byte string values and their associated code words received from the first processor with the stored byte string values associated with those code words in the dictionary data structure, the second processor providing at its output, based on at least some of said comparisons, code words representing byte string values that are repeated in the input data stream; and

a third processor coupled to the second processor that assembles the code words output by the second processor to form a compressed output stream.

2. The system of claim 1, wherein the data paths of each of said plurality of processors comprise a plurality of storage registers that enable multiple bytes of an input data stream to be processed by different ones of said plurality of processors simultaneously.

3. The system of claim 2, wherein said storage registers enable selected results of the processing of previous bytes of the input data stream to be available to complete processing of a current data byte, as needed.

4. The system of claim 3, wherein the data paths and storage registers thereof are arranged such that the selected results of the processing of said previous bytes of the input data stream can be accessed within one clock cycle of said respective processors, at any point in the processing flow of said processors.

5. The system of claim 3, wherein the data paths of the different processors are interconnected such that the data paths represent different levels of a data pipeline formed by that interconnection.

6. The system of claim 2, each processor has a respective input and output and wherein data output from one of said plurality of processors is immediately registered on the input of another of said processors.

7. The system of claim 1, wherein the hash table and dictionary data structures are implemented in separate memory devices thereby enabling simultaneous access to both the hash table and the dictionary data structure by different ones of the first, second, and third processors.

8. The system of claim 7, wherein the separate memory devices each comprise a static random access memory device (SRAM).

9. The system of claim 1, wherein the hash table and dictionary data structures are initialized substantially simultaneously by the first and second processors, respectively.

10. The system of claim 9, wherein initialization data for the hash table is pre-processed and stored in independent read only memory devices associated with the hash table.

11. The system of claim 1, wherein each of said plurality of processors is not programmable, the data paths and respective state machines that comprise each of said processors being hard-coded.

12. The system recited in claim 1 further comprising a forth processor that coordinates and directs the operations of the first, second, and third processors.

13. A system for executing an LZW compression algorithm, the system comprising:

a first processor that performs a hashing function to calculate an index value based upon a byte string value from an input data stream, the index value being used as a hash table address to assign a location in a hash table data structure to a code word representing the byte string value and retrieve the code word value from the assigned location;

a second processor interfaced to the first processor that stores in a dictionary data structure a linked list of byte strings from the input data stream, each byte string stored in the dictionary data structure being associated with a code word, the second processor comparing byte string values and their associated code words received from the first processor with the stored byte string values associated with those code words in the dictionary data structure, the second processor providing at its output, based on at least some of said comparisons, code words representing byte string values that are repeated in the input data stream;

a third processor interfaced to the second processor that assembles the code words output by the second processor to form a compressed output stream;

each of the first, second, and third processors comprising a data path and an associated state machine that controls the flow of data through the data path;

the data paths, under control of the respective state machines, being arranged to provide simultaneous execution of different steps of the LZW compression algorithm on successive bytes of an input stream; and

a fourth processor that coordinates and directs the operations of the first, second, and third processors.

14. The system of claim 13, wherein the hash table and dictionary data structures are implemented in separate memory devices thereby enabling simultaneous access to both the hash table and the dictionary data structure by different ones of the first, second, and third processors.

15. The system of claim 14, wherein the separate memory devices each comprise a static random access memory device (SRAM).

16. The system of claim 13, wherein the data paths of the first, second and third processors comprise a plurality of storage registers that enable multiple bytes of the input data stream to be processed by different ones of the first, second, and third processors simultaneously.

17. The system of claim 16, wherein data output from one of the first, second, and third data processors is immediately registered on the input of the next processor.

18. The system of claim 13, wherein said storage registers enable selected results of the processing of previous bytes of the input data stream to be available to complete processing of a current data byte, as needed.

19. The system of claim 18, wherein the data paths and storage registers thereof are arranged such that the selected results of the processing of said previous bytes of the input data stream can be accessed within one clock cycle of said first, second, and third processors, at any point in the processing flow of said processors.

20. The system of claim 13, wherein the hash table and dictionary data structures are initialized substantially simultaneously by the first and second processors, respectively.

21. The system of claim 20, wherein initialization data for the hash table is pre-processed and stored in independent read only memory devices associated with the hash table.

22. The system of claim 13, wherein the interfaces between each of the first, second, and third processors represent different levels of the data pipeline formed by the data paths of the respective processors.

23. The system of claim 22, wherein the data path of each of the first second and third processor defines at least one level of the data pipeline.

24. The system of claim 13, wherein the fourth processor receives commands from an associated microprocessor.

25. The system of claim 24, wherein the commands received from the associated microprocessor comprise one of a software controlled restart command, a command to clear a latched status within the fourth processor and a command to designate one of a software controlled mode or a hardware controlled mode.

26. The system of claim 13, wherein the fourth processor returns a status to a microprocessor.

27. The system of claim 26, wherein the status comprises one of an idle status or an error status.

28. The system of claim 13, wherein the fourth processor outputs a command to one of the first processor, the second processor and the third processor.

29. The system of claim 28, wherein in response to receiving a string compare command from the fourth processor, the first processor, in response to receiving a string byte, determines a hash value for the string byte, and in response to determining that a hash table location associated with the hash value for the string byte is assigned, retrieves a code word for the string byte stored at the hash table location and presents the code word and the byte to the second processor.

30. The system of claim 28, wherein in response to receiving a new hash command from the fourth processor, the first processor calculates the hash index of the next input byte using a specified default value as the initial hash index.

31. The system of claim 28, wherein in response to receiving a rehash command from the fourth processor, the first processor further calculates the hash index of the current input byte using a rehash algorithm.

32. The system of claim 28, wherein in response to receiving a new prefix write command from the fourth processor, the second processor writes a byte received from the first processor and a code word for a current string prefix received from the second processor into the dictionary data structure, returns an newly assigned code word value to the first processor and outputs the code word for a current string prefix to the third processor.

33. The system of claim 28, wherein when a current byte has hashed to an available location in the hash table and the dictionary data structure is not full, a new code word is assigned to a current string prefix and the code word for the current string prefix is output to the third processor.

34. The system of claim 14, wherein the first, second, and third processors are not programmable, the data paths and respective state machines that comprise each of the first, second, and third processors being hard-coded.

35. The system of claim 13, wherein assembling the code words output by the second processor to form a compressed output stream further comprises concatenating the code words into a continuous output stream and segmenting the output data stream into uniform bytes to produce an output file.