Decompression accelerator for flash memory
View Patent ↗A hardware accelerator for improving the decompression performance when decompressing data in Lempel-Ziv-Huffman compressed data format. The use of a Huffman encoding second stage in the popular and widely-used Lempel-Ziv-Huffman standard improves the compression ratio but complicates the decompression, because the Huffman encoding is applied selectively only to certain pails of the Lempel-Ziv tokens, and thus Huffman decoding must also be applied selectively during decompression. The present invention features a variable-length token decoder which is able to selectively decode the Huffman-encoded portions of the compressed data, and therefore enables high-performance decompression for compressed data having a very good compression ratio. Such an accelerator is well-suited for use in data processors which are to be loaded with pre-compressed data and software applications, particularly those employing flash memory.
1. A decompression accelerator for decompressing Lempel-Ziv-Huffman compressed data from an input stream and sending decompressed data corresponding thereto to an output stream, the decompression accelerator comprising:
(a) a variable-length token decoder for selectively decoding Huffman-encoded code portions of Lempel-Ziv tokens and for selectively retrieving and passing extra bit portions of said Lempel-Ziv tokens without Huffman decoding; and
(b) a Lempel-Ziv decoder for decompressing Lempel-Ziv tokens obtained from said variable-length token decoder.
2. The decompression accelerator as recited in claim 1 , wherein said variable-length token decoder includes:
i) a bit buffer, for breaking fixed-length words from the input bit stream into variable-length words for Huffman decoding and for retrieving extra bits, said bit buffer having a variable-length output;
ii) a token analyzer, for determining characteristics of a Lempel-Ziv token, for coordinating said selective Huffman decoding of said code portion of each said Lempel-Ziv token, and, if said each Lempel-Ziv token includes said extra bit portion, for coordinating said selective passing of said extra bit portion without Huffman decoding; and
iii) a Huffman decoder for effecting said selective Huffman decoding.
3. A decompression accelerator as recited in claim 2 , wherein said Huffman decoder is operative to perform dynamic Huffman decoding.
4. A decompression accelerator as recited in claim 2 , further comprising at least one component selected from the group consisting of:
(c) an input buffer, for buffering input data words between the input stream and said bit buffer;
(d) a bit buffer controller, for controlling operation of said bit buffer;
(e) an output selector, for selecting output of said Huffman decoder and for selectively passing said variable-length output of said bit buffer; and
(f) a token constructor, for, for each said Lempel-Ziv token that includes said extra bit portion, assembling said code portion of said each Lempel-Ziv token as decoded by said Huffman decoder and said extra bit portion so as to reproduce said each Lempel-Ziv token.
5. A decompression accelerator as recited in claim 1 , further comprising at least one component selected from the group consisting of:
(c) a token buffer for buffering said Lempel-Ziv tokens from said variable-length token decoder and from said Lempel-Ziv decoder; and
(d) an output buffer, for buffering decompressed output from said Lempel-Ziv decoder to the output stream.
6. A data processor comprising a decompression accelerator as recited in claim 1 .
7. A data processor as recited in claim 6 , further comprising flash memory.
8. A memory controller comprising a decompression accelerator as recited in claim 1 .
9. The memory controller recited in claim 8 , wherein the memory controller is a flash memory controller.
10. A memory device comprising the memory controller recited in claim 8 .
11. A memory device comprising a decompression accelerator as recited in claim 1 .
12. The memory device as recited in claim 11 , wherein the memory device is a flash memory device.