System and method for Huffman decoding within a compression engine

• US 7,538,696 B2
• Filed: 08/31/2007
• Issued: 05/26/2009
• Est. Priority Date: 08/31/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 BRUNER
• Application Number:
  US11/849,166
• Publication Number:
  US 20090058693A1
• Time in Patent Office: 634 Days
• Field of Search: 341/50, 341/51, 341/55, 341/67, 341/82, 382/242, 382/232, 370/469
• US Class Current: 341/51
• CPC Class Codes: H03M 7/3086 employing a sliding window, e.g. LZ77
• CPC Class Codes: H03M 7/40 Conversion to or from variable length codes, e.g. Shannon-Fano code, Huffman code, Morse code

Abstract

An apparatus to implement Huffman decoding in an INFLATE process in a compression engine. An embodiment of the apparatus includes a bit buffer, a set of comparators, and a lookup table. The bit buffer stores a portion of a compressed data stream. The set of comparators compares the portion of the compressed data stream with a plurality of predetermined values. The lookup table stores a plurality of LZ77 code segments and outputs one of the LZ77 code segments corresponding to an index at least partially derived from a comparison result from the set of comparators.

Claims

1. A method for Huffman decoding within a compression engine, the method comprising:

receiving a compressed data stream;

comparing a portion of the compressed data stream with a plurality of predetermined values using a plurality of comparators;

outputting a LZ77 code value based on the portion of the compressed data stream and a comparison result from comparing the portion of the compressed data stream with the plurality of predetermined values; and

generating a bit selection value based on the comparison of the portion of the compressed data stream with the plurality of the predetermined values; and

generating an index based on the portion of the compressed data stream and the bit selection value.

2. The method according to claim 1, wherein the LZ77 code value comprises a LZ77 length code segment.

3. The method according to claim 1, wherein the LZ77 code value comprises a LZ77 distance code segment.

4. The method according to claim 1, wherein the LZ77 code value comprises a literal value.

5. The method according to claim 1, further comprising adding a start value to the portion of the compressed data stream to generate the index.

6. The method according to claim 1, further comprising adding an index offset to the portion of the compressed data stream to generate the index.

7. The method according to claim 1, further comprising adding a pre-computed value to the portion of compressed data stream to generate the index.

8. The method according to claim 7, wherein the pre-computed value comprises a start value and an index offset.

9. The method according to claim 1, further comprising looking up the LZ77 code value in a lookup table based on the index.

10. The method according to claim 9, further comprising:

looking up a first LZ77 code value in a first lookup table based on the index; and

looking up a second LZ77 code value in a second lookup table based on a subsequent value of the index.

11. An apparatus to implement Huffman decoding in an INFLATE process in a compression engine, the apparatus comprising:

a bit buffer to store a portion of a compressed data stream;

a set of comparators coupled to the bit buffer, the set of comparators to compare the portion of the compressed data stream with a plurality of predetermined values;

a lookup table coupled to the set of comparators, the lookup table to store a plurality of LZ77 code segments and to output one of the LZ77 code segments corresponding to an index at least partially derived from a comparison result from the set of comparators; and

a bit selector coupled to the set of comparators, the bit selector to receive the comparison result and to identify a value to be added to the portion of the compressed data stream.

12. The apparatus according to claim 11, wherein the lookup table comprises a single combined lookup table comprising both LZ77 length code segments and LZ77 distance code segments.

13. The apparatus according to claim 11, wherein the LZ77 code value comprises a LZ77 length code segment.

14. The apparatus according to claim 11, wherein the LZ77 code value comprises a LZ77 distance code segment.

15. The apparatus according to claim 11, wherein the LZ77 code value comprises a literal value.

16. The apparatus according to claim 11, further comprising an index adder to add the value to the portion of the compressed data stream according to the bit selector.

17. The apparatus according to claim 11, wherein the value to be added to the portion of the compressed data stream comprises an index offset minus a start value.

18. The apparatus according to claim 11, wherein the value to be added to the portion of the compressed data stream comprises a pre-computed value comprising a start value and an index offset.

19. The apparatus according to claim 11, further comprising an index adder to add the value to the portion of the compressed data stream according to the bit selector.

20. The apparatus according to claim 11, wherein the lookup table comprises a plurality of LZ77 length code segments, the apparatus further comprising a second lookup table coupled to the bit buffer, the second lookup table comprising a plurality of LZ77 distance code segments.

21. The apparatus according to claim 20 further comprising a demultiplexor coupled between an index adder and the lookup tables, the demultiplexor to direct the index value to one of the lookup tables.

22. An apparatus to implement Huffman decoding in an INFLATE process in a compression engine, the apparatus comprising:

means for receiving a compressed data stream;

means for comparing a portion of the compressed data stream with a plurality of predetermined values using a plurality of comparators;

means for outputting a LZ77 code value based on the portion of the compressed data stream and a comparison result from comparing the portion of the compressed data stream with the plurality of predetermined values; and

means for generating a bit selection value based on the comparison of the portion of the compressed data stream with the plurality of the predetermined values.

23. The apparatus according to claim 22, further comprising means for generating an index based on portion of the compressed data stream and the bit selection value.

24. The apparatus according to claim 23, further comprising means for adding an index value minus a start value to the portion of the compressed data stream to generate the index.

25. The apparatus according to claim 23, further comprising:

means for pre-computing a sum value of a least a start value and an index offset; and

means for adding the pre-computed value to the portion of the compressed data stream to generate the index.

26. The apparatus according to claim 22, further comprising means for looking up the LZ77 code value in a lookup table based on the index.

27. The apparatus according to claim 22, further comprising:

means for looking up a first LZ77 code value in a first lookup table based on the index; and

means for looking up a second LZ77 code value in a second lookup table based on a subsequent value of the index.