Method and apparatus for efficient deflate decompression using content-addressable data structures

1. An apparatus comprising:

a decoder to decode one or more instructions;

execution circuitry to execute the one or more instructions, the execution circuitry including decompression acceleration circuitry to:

extract a sequence of tokens and corresponding length values from a header of a compression block, the tokens and corresponding length values associated with a type of compression used to compress a payload of the compression block; and

construct a content-addressable data structure based on the tokens and length values, the content-addressable data structure builder to write an entry in the content-addressable data structure comprising a length value and a count value, the count value indicating a number of times the length value was previously written to an entry in the content-addressable data structure.

2. The apparatus of claim 1 wherein the decompression acceleration circuitry includes a content-addressable data structure builder to write the rows of the content-addressable data structure in a sequence corresponding to the sequence of tokens and corresponding length values extracted from the header of the compression block.

3. The apparatus of claim 2 further comprising:

a plurality of counters to maintain current counts of the number of times corresponding length values were previously written to rows in the content-addressable data structure, the content-addressable data structure builder to write a count value from a first counter to a current row of the content-addressable data structure when a length value corresponding to the first counter is to be written to the row.

4. The apparatus of claim 3 wherein the content-addressable data structure builder is to increment the count value in the first counter.

5. The apparatus of claim 2 further comprising:

a speculative header parser to extract a second sequence of tokens and corresponding length values from the header; and

a speculative content-addressable data structure builder to construct speculative entries in the content-addressable data structure based on the second sequence of tokens and length values, the speculative content-addressable data structure builder to write a speculative entry in the content-addressable data structure comprising a second length value and a second count value, the second count value indicating a number of times the second length value was previously written to the content-addressable data structure.

6. The apparatus of claim 1 wherein the content-addressable data structure comprises a content-addressable memory (CAM).

7. The apparatus of claim 1 wherein the decompression acceleration circuitry further comprises:

decompression circuitry to decode the payload of the compression block using the content-addressable data structure.

8. The apparatus of claim 7 wherein the type of compression comprises Deflate compression and wherein the decompression circuitry comprises a Huffman decoder.

9. The apparatus of claim 8 wherein the Huffman decoder comprises:

a first decompression module to perform a non-speculative decompression of a first portion of the payload comprising a first plurality of tokens; and

a second decompression module to perform speculative decompression of a second portion of the payload comprising a second plurality of tokens concurrently with the non-speculative decompression performed by the first compression module.

10. The apparatus of claim 7 wherein the decompression circuitry comprises a plurality of arithmetic logic units (ALUs) to construct an index into the content-addressable data structure based on an ALU size corresponding to a length value in a corresponding row to be indexed.

11. The apparatus of claim 1 wherein each count value written to an entry of the content-addressable data structure is to be used as a portion of an index value to identify the corresponding row when performing a lookup into the content-addressable data structure.

12. The apparatus of claim 1 further comprising:

a decompression state manager to store the content-addressable data structure using a variable number of bits for at least some entries in the content-addressable data structure based on a number of non-trivial bits required to store a count value associated with the entries.

13. A method comprising:

extracting a sequence of tokens and corresponding length values from a header of a compression block, the tokens and corresponding length values associated with a type of compression used to compress a payload of the compression block; and

constructing a content-addressable data structure based on the tokens and length values by:

writing to an entry in the content-addressable data structure including writing a length value and a count value,

the count value indicating a number of times the length value was previously written to an entry in the content-addressable data structure.

14. The method of claim 13 wherein the rows of the content-addressable data structure are to be written in a sequence corresponding to the sequence of tokens and corresponding length values extracted from the header of the compression block.

15. The method of claim 13 further comprising:

counting the number of times corresponding length values were previously written to rows in the content-addressable data structure; and

writing a count value from a first counter to a current row of the content-addressable data structure when a length value corresponding to the first counter is to be written to the row.

16. The method of claim 15 further comprising:

incrementing the count value in the first counter.

17. The method of claim 13 wherein the content-addressable data structure comprises a content-addressable memory (CAM).

18. The method of claim 13 further comprising:

decoding the payload of the compression block using the content-addressable data structure.

19. The method of claim 18 wherein the type of compression comprises Deflate compression and wherein decoding is performed by a Huffman decoder.

20. The method of claim 19 further comprising:

performing non-speculative decompression of a first portion of the payload comprising a first plurality of tokens; and

performing speculative decompression of a second portion of the payload comprising a second plurality of tokens concurrently with the non-speculative decompression.

21. The method of claim 18 wherein decoding the payload is performed by a plurality of arithmetic logic units (ALUs), an index into the content-addressable data structure to be constructed using an ALU size corresponding to a length value in a corresponding row to be indexed.

22. The method of claim 13 wherein each count value written to an entry of the content-addressable data structure is to be used as a portion of an index value to identify the corresponding row when performing a lookup into the content-addressable data structure.

23. The method of claim 13 further comprising:

storing the content-addressable data structure using a variable number of bits for at least some entries in the content-addressable data structure based on a number of non-trivial bits required to store a count value associated with the entries.

24. The method of claim 13 further comprising:

speculatively extracting a second sequence of tokens and corresponding length values from the header; and

constructing speculative entries in the content-addressable data structure based on the second sequence of tokens and length values including writing a speculative entry in the content-addressable data structure comprising a second length value and a second count value, the second count value indicating a number of times the second length value was previously written to the content-addressable data structure.

25. A machine-readable medium having program code stored thereon which, when executed by a machine, causes the machine to perform the operations of:

extracting a sequence of tokens and corresponding length values from a header of a compression block, the tokens and corresponding length values associated with a type of compression used to compress a payload of the compression block; and

constructing a content-addressable data structure based on the tokens and length values by:

writing to an entry in the content-addressable data structure including writing a length value and a count value,

the count value indicating a number of times the length value was previously written to an entry in the content-addressable data structure.

26. The machine-readable medium of claim 25 wherein the rows of the content-addressable data structure are to be written in a sequence corresponding to the sequence of tokens and corresponding length values extracted from the header of the compression block.

27. The machine-readable medium of claim 25 further comprising:

counting the number of times corresponding length values were previously written to rows in the content-addressable data structure; and

writing a count value from a first counter to a current row of the content-addressable data structure when a length value corresponding to the first counter is to be written to the row.

28. The machine-readable medium of claim 27 further comprising:

incrementing the count value in the first counter.

29. The machine-readable medium of claim 25 wherein the content-addressable data structure comprises a content-addressable memory (CAM).

30. The machine-readable medium of claim 25 further comprising:

decoding the payload of the compression block using the content- addressable data structure.

31. The machine-readable medium of claim 30 wherein the type of compression comprises Deflate compression and wherein decoding is performed by a Huffman decoder.

32. The machine-readable medium of claim 30 further comprising:

performing non-speculative decompression of a first portion of the payload comprising a first plurality of tokens; and

performing speculative decompression of a second portion of the payload comprising a second plurality of tokens concurrently with the non- speculative decompression.

33. The method of claim 25 wherein each count value written to an entry of the content-addressable data structure is to be used as a portion of an index value to identify the corresponding row when performing a lookup into the content-addressable data structure.

34. The method of claim 30 wherein decoding the payload is performed by a plurality of arithmetic logic units (ALUs), an index into the content-addressable data structure to be constructed using an ALU size corresponding to a length value in a corresponding row to be indexed.

35. The method of claim 25 further comprising:

storing the content-addressable data structure using a variable number of bits for at least some entries in the content-addressable data structure based on a number of non-trivial bits required to store a count value associated with the entries.

36. The method of claim 25 further comprising:

speculatively extracting a second sequence of tokens and corresponding length values from the header; and

constructing speculative entries in the content-addressable data structure based on the second sequence of tokens and length values including writing a speculative entry in the content-addressable data structure comprising a second length value and a second count value, the second count value indicating a number of times the second length value was previously written to the content-addressable data structure.