Deflate decompressor

• US 8,125,357 B1
• Filed: 03/23/2010
• Issued: 02/28/2012
• Est. Priority Date: 03/23/2010
• Status: Active Grant

• Current Assignee: National Technology & Engineering Solutions Of Sandia LLC (Honeywell International Inc.)
• Original Assignee: Sandia Corporation (Martin Marietta Corporation)
• Inventors: Robertson, Perry J., Pierson, Lyndon G., Hamlet, Jason R., Olsberg, Ronald R.
• Primary Examiner(s): JEANGLAUDE, JEAN BRUNER
• Application Number:
  US12/729,816
• Time in Patent Office: 707 Days
• Field of Search: 341/50, 341/51
• US Class Current: 341/51
• CPC Class Codes: H03M 7/3086 employing a sliding window, e.g. LZ77
• CPC Class Codes: H03M 7/4043 Adaptive prefix coding
• CPC Class Codes: H03M 7/4081 Static prefix coding
• CPC Class Codes: H03M 7/607 Selection between different types of compressors

Abstract

A deflate decompressor includes at least one decompressor unit, a memory access controller, a feedback path, and an output buffer unit. The memory access controller is coupled to the decompressor unit via a data path and includes a data buffer to receive the data stream and temporarily buffer a first portion the data stream. The memory access controller transfers fixed length data units of the data stream from the data buffer to the decompressor unit with reference to a memory pointer pointing into the memory buffer. The feedback path couples the decompressor unit to the memory access controller to feed back decrement values to the memory access controller for updating the memory pointer. The decrement values each indicate a number of bits unused by the decompressor unit when decoding the fixed length data units. The output buffer unit buffers a second portion of the data stream after decompression.

Claims

1. A deflate decompressor apparatus, comprising:

at least one decompressor unit for decompressing a data stream compressed according to a compression algorithm;

a memory access controller coupled to the at least one decompressor unit via a data path, the memory access controller including a data buffer to receive the data stream and temporarily buffer the data stream, wherein the memory access controller transfers fixed length data units of the data stream from the data buffer to the at least one decompressor unit with reference to a memory pointer pointing into the memory buffer;

a feedback path coupled between the at least one decompressor unit and the memory access controller, wherein the at least one decompressor unit feeds back decrement values to the memory access controller for updating the memory pointer, the decrement values each indicating a number of bits unused by the at least one decompressor unit when decoding the fixed length data units; and

an output buffer unit coupled to the at least one decompressor unit.

2. The deflate decompressor apparatus of claim 1, wherein the output buffer unit comprises:

a sliding window buffer having dual data ports and dual address ports for simultaneous reading from or writing to two locations within the sliding window buffer; and

a buffer controller coupled to receive the data stream from the at least one decompressor unit and coupled to generate address signals and control signals for reading from or writing to the sliding window buffer.

3. The deflate decompressor apparatus of claim 2, wherein the at least one decompressor unit includes an uncompressed data unit for processing uncompressed data, wherein the buffer controller is coupled to use both of the dual data ports of the sliding window buffer for writing the uncompressed data into the sliding window buffer.

4. The deflate decompressor apparatus of claim 3, wherein the uncompressed data unit includes:

a counter for tracking a number of remaining data words of a data block to be written into the sliding window buffer; and

logic for feeding back a single word decrement signal on the feedback path, if the counter indicates only one data word was written into the sliding window buffer.

5. The deflate decompressor apparatus of claim 1, wherein the at least one decompressor unit comprises a static decompressor unit for decompressing data compressed using static Huffman tables, the static decompressor unit comprising:

a length-literal lookup table (“

LUT”

) coupled to receive the fixed length data units and output length or literal values and output one of the decrement values; and

a distance LUT coupled to receive the fixed length data units and output distance values and output one of the decrement values,

wherein the literal values, length values, and distance values comprise Lempel-Ziv codes.

6. The deflate decompressor apparatus of claim 5, wherein the static decompressor unit further comprises:

a plurality of distance LUTs each coupled to receive the fixed length data units and output distance values each commuted from a different offset within the fixed length data units; and

a multiplexor unit coupled to each of the distance LUTs and having a selector input coupled to receive the decrement values output from the length-literal LUT.

7. The deflate decompressor apparatus of claim 1, wherein the at least one decompressor unit comprises a dynamic decompressor unit for decompressing data compressed using dynamic Huffman tables, the dynamic decompressor unit including:

a length-literal decompressor coupled to receive the fixed length data units and output length or literal values and output one of the decrement values; and

a distance decompressor coupled to receive the fixed length data units and output distance values and output one of the decrement values,

wherein the literal values, length values, and distance values comprise Lempel-Ziv codes.

8. The deflate decompressor apparatus of claim 7, wherein the dynamic decompressor unit further comprises:

a codelength decoder to generate a codelength Huffman table based on a first portion of the data stream; and

a table generator coupled to access the codelength Huffman table generated by the codelength decoder and decode length-literal code lengths and decode distance code lengths based on the codelength Huffman table and a second portion of the data stream.

9. The deflate decompressor apparatus of claim 8, wherein the dynamic decompressor unit further comprises:

a first memory for storing the length-literal code lengths;

a second memory for storing length-literal nonzero values indicating which entries within the first memory are nonzero values;

a third memory for storing the distance code lengths; and

a fourth memory for storing distance nonzero values indicating which entries within the third memory are nonzero values,

wherein the table generator is coupled to reference the second and fourth memories to reduce a number of accesses to the first and third memories when building a dynamic length-literal Huffman table and a dynamic distance Huffman table for decoding a third portion of the data stream.

10. The deflate decompressor apparatus of claim 1, wherein the at least one decompressor unit includes a static decompressor unit for decompressing data compressed using static Huffman tables and a dynamic decompressor unit for decompressing data compressed using dynamic Huffman tables, wherein the deflate decompressor apparatus further comprises:

a deflate header unit coupled to a memory access controller to determine whether the data stream is compressed using the static Huffman tables or the dynamic Huffman tables.

11. The deflate decompressor apparatus of claim 10, wherein the memory access controller comprises:

a memory access state-machine for controlling a location of the memory pointer; and

a decrement multiplexor coupled to multiplex multiple feedback paths for carrying the decrement values generated by the deflate header unit, the static decompressor unit, and the dynamic decompressor unit.

12. The deflate decompressor apparatus of claim 11, further comprising a multiplexor to selectively couple outputs from the static decompressor unit and the dynamic decompressor unit to the output buffer unit under control of the deflate header unit.

13. A method for decompressing a dataset compressed using variable length codes, the method comprising:

buffering the dataset within a data buffer;

transferring fixed length portions of the dataset from the data buffer to a decompressor unit with reference to a memory pointer;

decoding each of the variable length codes of the dataset based on a corresponding one of the fixed length portions;

feeding back decrement values from the decompressor unit each indicating how many bits of one of the fixed length portions was unused by the decompressor unit to decode one of the variable length codes;

updating a location of the memory pointer using the decrement values between transferring consecutive ones of the fixed length portions to realign the memory pointer with a start of a next variable length code; and

outputting the dataset in an uncompressed format.

14. The method of claim 13, wherein the dataset comprises data compressed using static Huffman tables and wherein decoding each of the variable length codes of the dataset based on the corresponding one of the fixed length portions comprises:

decoding length values and literal values from the dataset using a first lookup table;

decoding distance values from the dataset using a plurality of second lookup tables; and

selecting one of the plurality of second lookup tables for a given decompression cycle using an output generated from the first lookup table.

15. The method of claim 13, wherein the dataset comprises data compressed using dynamic Huffman tables, and wherein the method further comprises recreating the dynamic Huffman tables by:

decoding length-literal code lengths from the dataset;

decoding distance code lengths from the dataset;

generating a first list indicating which of the length-literal code lengths are nonzero;

generating a second list indicating which of the distance code lengths are nonzero; and

referencing the first and second lists to reduce a number of memory accesses to the length-literal code lengths and the distance code lengths when recreating the dynamic Huffman tables.

16. The method of claim 13, wherein decoding each of the variable length codes of the dataset generates Lempel-Ziv coded data having literal values and length-distance pairs, the method further comprising decoding the length-distance pairs using a dual port sliding window buffer by:

reading a first data word from the dual port sliding window buffer using a first port;

writing the first data word back into the dual port sliding window buffer using a second port while reading a second data word using the first port; and

writing the second data word back into the dual port sliding window buffer using the second port while reading a third data word using the first data port.

17. The method of claim 13, wherein the dataset comprises a dataset compressed using the Deflate algorithm.

18. A computer-readable storage medium that provides instructions that, when executed by a computer, will cause the computer to perform operations for decompressing a dataset, the operations comprising:

buffering the dataset compressed using variable length codes within a data buffer;

transferring fixed length portions of the dataset from the data buffer to a decompressor unit with reference to a memory pointer;

decoding each of the variable length codes of the dataset based on a corresponding one of the fixed length portions;

feeding back decrement values from the decompressor unit each indicating how many bits of one of the fixed length portions was unused by the decompressor unit to decode one of the variable length codes;

updating a location of the memory pointer using the decrement values between transferring consecutive ones of the fixed length portions to realign the memory pointer with a start of a next variable length code; and

outputting the dataset in an uncompressed format.

19. The computer-readable storage medium of claim 18, wherein the dataset comprises data compressed using static Huffman tables and wherein decoding each of the variable length codes of the dataset based on the corresponding one of the fixed length portions comprises:

decoding length values and literal values from the dataset using a first lookup table;

decoding distance values from the dataset using a plurality of second lookup tables; and

selecting one of the plurality of second lookup tables for a given decompression cycle using an output generated from the first lookup table.

20. The computer-readable storage medium of claim 18, wherein the dataset comprises data compressed using dynamic Huffman tables, and wherein the computer-readable storage medium further provides instructions that, when executed by the computer, will cause the computer to perform further operations comprising recreating the dynamic Huffman tables by:

decoding length-literal code lengths from the dataset;

decoding distance code lengths from the dataset;

generating a first list indicating which of the length-literal code lengths are nonzero;

generating a second list indicating which of the distance code lengths are nonzero; and

referencing the first and second lists to reduce a number of memory accesses to the length-literal code lengths and the distance code lengths when recreating the dynamic Huffman tables.

21. The computer-readable storage medium of claim 18, wherein decoding each of the variable length codes of the dataset generates Lempel-Ziv coded data having literal values and length-distance pairs, and wherein the computer-readable storage medium further provides instructions that, when executed by the computer, will cause the computer to perform further operations comprising decoding the length-distance pairs using a dual port sliding window buffer by:

reading a first data word from the dual port sliding window buffer using a first port;

writing the first data word back into the dual port sliding window buffer using a second port while reading a second data word using the first port; and

writing the second data word back into the dual port sliding window buffer using the second port while reading a third data word using the first data port.