System and method for deflate processing within a compression engine

• US 7,538,695 B2
• Filed: 06/29/2007
• Issued: 05/26/2009
• Est. Priority Date: 06/29/2007
• Status: Expired due to Fees

• Current Assignee: Avago Technologies General IP PTE Limited (Broadcom, Inc.)
• Original Assignee: RMI Corporation (Broadcom, Inc.)
• Inventors: Hass, David T, Laker, Robert William
• Primary Examiner(s): Jeanglaude; Jean B
• Application Number:
  US11/824,501
• Publication Number:
  US 20090006510A1
• Time in Patent Office: 697 Days
• Field of Search: 341/50, 341/51, 341/55, 341/67, 341/82
• US Class Current: 341/51
• CPC Class Codes: H03M 7/3086 employing a sliding window, e.g. LZ77

Abstract

An apparatus to implement a deflate process in a compression engine. An embodiment of the apparatus includes a hash table, a dictionary, comparison logic, and encoding logic. The hash table is configured to hash a plurality of characters of an input data stream to provide a hash address. The dictionary is configured to provide a plurality of distance values in parallel based on the hash address. The distance values are stored in the dictionary. The comparison logic is configured to identify a corresponding length for each matching distance value from the plurality of distance values. The encoding logic is configured to encode the longest length and the matching distance value as a portion of a LZ77 code stream.

Claims

1. A method for deflate processing within a compression engine, the method comprising:

hashing a plurality of characters of an input data stream to provide a hash address into a dictionary;

reading a plurality of distance values in parallel from the dictionary based on the hash address, wherein the distance values are stored in the dictionary;

identifying a matching distance value from the plurality of distance values; and

encoding the matching distance value with a length value as a portion of a LZ77 code stream.

2. The method according to claim 1, wherein identifying the matching distance value further comprises:

comparing the input data stream in parallel with a plurality of byte streams from a byte buffer, the plurality of byte streams corresponding to the plurality of distance values from the dictionary; and

identifying a longest matching byte stream of the plurality of byte streams.

3. The method according to claim 2, further comprising deriving the length value from the longest matching byte stream of the plurality of byte streams.

4. The method according to claim 2, wherein comparing the input data stream with the plurality of byte streams further comprises comparing a plurality of bytes per cycle from each byte stream with corresponding bytes of the input data stream.

5. The method of claim 4, wherein comparing the plurality of bytes per cycle from each byte stream further comprises comparing up to 16 bytes per cycle from each byte stream with the corresponding bytes of the input data stream.

6. The method according to claim 2, wherein if two or more of the plurality of byte streams are a same length, choosing a byte stream with a shortest distance value.

7. The method according to claim 1, wherein the reading includes reading the plurality of distance values in parallel from the dictionary based on a single hash address.

8. The method according to claim 1, further comprising updating the dictionary at the end of a match operation to identify a longest matching byte stream from a byte buffer.

9. The method according to claim 1, further comprising updating the dictionary in response to an operation to output a literal, wherein the literal comprises another character of the input data stream.

10. The method according to claim 1, further comprising storing approximately 2K entries in the dictionary, wherein each entry comprises a plurality of possible match entries.

11. The method according to claim 10, wherein each entry comprises up to four possible match entries.

12. The method according to claim 10, wherein each possible match entry comprises:

a possible distance value corresponding to a byte stream in a byte buffer;

a valid bit to indicate a valid status of the byte stream in the byte buffer; and

at least one initial character from the byte stream in the byte buffer.

13. The method according to claim 12, wherein each possible match entry comprises two initial characters from the byte stream in the byte buffer.

14. The method according to claim 1, further comprising:

reading at least one byte stream character from the dictionary, the at least one byte stream character corresponding to at least one of the plurality of characters used to compute the hash address; and

comparing the at least one byte stream character with the plurality of characters of the input data stream.

15. The method according to claim 14, further comprising discarding the distance value corresponding to the at least one byte stream character in response to a determination that the at least one byte stream character is different from the plurality of characters of the input data stream.

16. An apparatus to implement a deflate process in a compression engine, the apparatus comprising:

a hash table to hash a plurality of characters of an input data stream to provide a hash address;

a dictionary coupled to the hash table, the dictionary to provide a plurality of distance values in parallel based on the hash address, wherein the distance values are stored in the dictionary;

comparison logic coupled to the dictionary, the comparison logic to identify a matching distance value from the plurality of distance values; and

encoding logic coupled to the comparison logic, the encoding logic to encode the matching distance value with a length value as a portion of a LZ77 code stream.

17. The apparatus according to claim 16, further comprising a byte buffer coupled to the dictionary and the comparison logic, the byte buffer to store a plurality of previous bytes of the input data stream, wherein the comparison logic is further configured to compare the input data stream in parallel with a plurality of byte streams from the byte buffer, the plurality of byte streams from the byte buffer corresponding to the plurality of distance values from the dictionary.

18. The apparatus according to claim 17, wherein the comparison logic is further configured to identify a longest matching byte stream of the plurality of byte streams.

19. The apparatus according to claim 18, wherein the comparison logic is further configured to compare about 16 bytes per cycle from each byte stream with corresponding bytes of the input data stream.

20. The apparatus according to claim 18, wherein the comparison logic is further configured to derive the length value from the longest matching byte stream of the plurality of byte streams.

21. The apparatus according to claim 18, further comprising a counter coupled to the comparison logic, the counter to count a number of matching bytes to identify the longest matching byte stream.

22. The apparatus according to claim 16, wherein the dictionary is further configured to update at least one dictionary entry at the end of a match operation to identify a longest matching byte stream from a byte buffer.

23. The apparatus according to claim 16, wherein the dictionary is further configured to update at least one dictionary entry in response to an operation to output a literal, wherein the literal comprises another character of the input data stream.

24. The apparatus according to claim 16, wherein the dictionary comprises approximately 2K dictionary entries, wherein each dictionary entry comprises a plurality of possible match entries.

25. The apparatus according to claim 16, wherein each possible match entry comprises:

a possible distance value corresponding to a byte stream in a byte buffer;

a valid bit to indicate a valid status of the byte stream in the byte buffer; and

a plurality of initial characters from the byte stream in the byte buffer;

26. The apparatus according to claim 16, further comprising an input buffer coupled to the hash table, the input buffer to store the plurality of characters of the input data stream.

27. The apparatus according to claim 26, further comprising a Huffman encoder coupled to the encoding logic, the Huffman encoder to compress the LZ77 code stream according to a Huffman coding algorithm.

28. The apparatus according to claim 27, further comprising an output buffer coupled to the Huffman encoder, the output buffer to store the LZ77 code stream compressed according to the Huffman coding algorithm.

29. The apparatus according to claim 16, wherein the dictionary comprises a single-ported dictionary random access memory (RAM).

30. The apparatus according to claim 16, further comprising distance logic coupled to the dictionary, the distance logic to read at least one byte stream character from the dictionary and to compare the at least one byte stream character with the plurality of characters of the input data stream, wherein the at least one byte stream character corresponds to at least one of the plurality of characters used to compute the hash address.

31. The apparatus according to claim 30, wherein the distance logic is further configured to discard the distance value corresponding to the at least one byte stream character in response to a determination that the at least one byte stream character is different from the plurality of characters of the input data stream.

32. A computer program product comprising a computer useable storage medium to store a computer readable program that, when executed on a computer, causes the computer to perform operations comprising:

hash a plurality of characters of an input data stream to provide a hash address into a dictionary;

read a plurality of distance values in parallel from the dictionary based on the hash address, wherein the distance values are stored in the dictionary;

identify a matching distance value from the plurality of distance values; and

encode the matching distance value with a length value as a portion of a LZ77 code stream.

33. The computer program product of claim 32, wherein the computer readable program, when executed on the computer, causes the computer to perform operations to:

compare the input data stream in parallel with a plurality of byte streams from a byte buffer, the plurality of byte streams corresponding to the plurality of distance values from the dictionary; and

identify a longest matching byte stream of the plurality of byte streams.

34. The computer program product of claim 33, wherein the computer readable program, when executed on the computer, causes the computer to perform an operation to derive the length value from the longest matching byte stream of the plurality of byte streams.

35. The computer program product of claim 33, wherein the computer readable program, when executed on the computer, causes the computer to perform an operation to compare a plurality of bytes per cycle from each byte stream with corresponding bytes of the input data stream.

36. The computer program product of claim 35, wherein the computer readable program, when executed on the computer, causes the computer to perform an operation to compare up to 16 bytes per cycle from each byte stream with the corresponding bytes of the input data stream.

37. The computer program product of claim 32, wherein the computer readable program, when executed on the computer, causes the computer to perform an operation to update the dictionary at the end of a match operation to identify a longest matching byte stream from a byte buffer.

38. The computer program product of claim 32, wherein the computer readable program, when executed on the computer, causes the computer to perform an operation to update the dictionary in response to an operation to output a literal, wherein the literal comprises another character of the input data stream.

39. The computer program product of claim 32, wherein the computer readable program, when executed on the computer, causes the computer to perform an operation to store approximately 2K entries in the dictionary, wherein each entry comprises a plurality of possible match entries.

40. The computer program product of claim 32, wherein the computer readable program, when executed on the computer, causes the computer to perform operations to:

read at least one byte stream character from the dictionary, the at least one byte stream character corresponding to at least one of the plurality of characters used to compute the hash address; and

compare the at least one byte stream character with the plurality of characters of the input data stream.

41. The computer program product of claim 40, wherein the computer readable program, when executed on the computer, causes the computer to perform an operation to discard the distance value corresponding to the at least one byte stream character in response to a determination that the at least one byte stream character is different from the plurality of characters of the input data stream.

42. An apparatus for deflate processing within a compression engine, the apparatus comprising:

means for accessing a dictionary entry in a dictionary, wherein the dictionary entry comprises a plurality of possible match entries corresponding to a combination of characters of an input data stream;

means for identifying a matching distance value from the plurality of possible match entries in the dictionary entry; and

means for encoding the matching distance value with a length value as a portion of a LZ77 code stream.