Method and apparatus for high performance compression and decompression

Patent metadata

Field	Value
Publication number	US-10270464-B1
Application number	US-201815941968-A
Country	US
Kind code	B1
Filing date	Mar 30, 2018
Priority date	Mar 30, 2018
Publication date	Apr 23, 2019
Grant date	Apr 23, 2019

Abstract

An apparatus and method for performing efficient lossless compression. For example, one embodiment of an apparatus comprises: first compression circuitry to identify and replace one or more repeated bit strings from an input data stream with distances to the one or more repeated bit strings, the first compression circuitry to generate a first compressed data stream comprising literal-length data identifying a first instance of each repeated bit string and distance data comprising distances from the first instance to each repeated instance of the repeated bit string; second compression circuitry to perform sorting, tree generation, and length calculations for literal-length values and distance values of the first compressed data stream, the second compression circuitry comprising: variable length code mapping circuitry to map each literal-length value and distance value to a variable length code; header generation circuitry to generate a header for a final compressed bit stream using the length calculations; and a transcoder to substitute the variable length codes in place of the literal-length and distance values to generate a compressed bit stream body, wherein the transcoder operates in parallel with the header generation circuitry; and bit stream merge circuitry to combine the header with the compressed bit stream body to generate a final lossless compressed bitstream.

First claim

What is claimed is:

1. An apparatus comprising:
first compression circuitry to identify and replace one or more repeated bit strings from an input data stream with distances to the one or more repeated bit strings, the first compression circuitry to generate a first compressed data stream comprising literal-length data identifying a first instance of each repeated bit string and distance data comprising distances from the first instance to each repeated instance of the repeated bit string;
second compression circuitry to perform sorting, tree generation, and length calculations for literal-length values and distance values of the first compressed data stream, the second compression circuitry comprising:
variable length code mapping circuitry to map each literal-length value and distance value to a variable length code;
header generation circuitry to generate a header for a final compressed bit stream using the length calculations; and
a transcoder to substitute the variable length codes in place of the literal-length and distance values to generate a compressed bit stream body, wherein the transcoder operates in parallel with the header generation circuitry; and
bit stream merge circuitry to combine the header with the compressed bit stream body to generate a final lossless compressed bitstream.

2. The apparatus of claim 1 wherein the second compression circuitry comprises a first pipeline to perform the sorting, tree generation, and length calculations on the literal-length values and a second pipeline to perform the sorting, tree generation, and length calculations on the distance values.

3. The apparatus of claim 1 wherein the first pipeline operates in parallel with the second pipeline.

4. The apparatus of claim 1 further comprising:
variable length code generation circuitry to generate or identify the variable length codes to be substituted for the literal-length and distance values.

5. The apparatus of claim 4 wherein the header generator is to begin generating the header as soon as the length calculations have been performed.

6. The apparatus of claim 5 wherein the transcoder is to begin performing the substitutions using the literal-length and distance values and variable length codes as soon as the variable length codes have been generated.

7. The apparatus of claim 1 wherein the first compression circuitry performs Lempel-Ziv (LZ) compression to generate the first compressed data stream.

8. The apparatus of claim 7 wherein the second compression circuitry comprises Huffman compression circuitry operating on the first compressed data stream to generate the final lossless compressed bit stream.

9. The apparatus of claim 1 further comprising:
a plurality of ping-pong registers or other storage devices coupled between the first compression circuitry and the second compression circuitry, the bit stream merge circuitry and the transcoder, and/or the variable length code mapping circuitry and the header generation circuitry, wherein the ping-pong registers or other storage devices are to store data for a different number of contexts based, at least in part, on a required throughput and/or latency.

10. The apparatus of claim 1 wherein the first compression circuitry and the second compression circuitry are integrated in a super-scalar encoder to generate a lossless compression bitstream.

11. The apparatus of claim 1 wherein the compressed bit stream body comprises a compression symbol, wherein the bit stream merge circuitry is to independently merge headers and bit stream bodies for odd and even compression symbols.

12. A method comprising:
identifying and replacing one or more repeated bit strings from an input data stream with distances to the one or more repeated bit strings;
generating a first compressed data stream comprising literal-length data identifying a first instance of each repeated bit string and distance data comprising distances from the first instance to each repeated instance of the repeated bit string;
performing sorting, tree generation, and length calculations for literal-length values and distance values of the first compressed data stream:
mapping each literal-length value and distance value to a variable length code;
generating a header for a final compressed bit stream using the length calculations; and
substituting the variable length codes in place of the literal-length and distance values to generate a compressed bit stream body, wherein the generating of the header operates in parallel with the substituting of the variable length codes; and
combining the header with the compressed bit stream body to generate a final lossless compressed bitstream.

13. The method of claim 12 first sorting, tree generation, and length calculations are performed on the literal-length values and second sorting, tree generation, and length calculations are performed on the distance values.

14. The method of claim 12 wherein the first sorting, tree generation, and length calculations are performed in parallel with the second sorting, tree generation, and length calculations.

15. The method of claim 12 further comprising:
generating or identifying the variable length codes to be substituted for the literal-length and distance values.

16. The method of claim 15 wherein generating the header is initiated as soon as the length calculations have been performed.

17. The method of claim 16 wherein the performing the substitutions is to be initiated using the literal-length and distance values and variable length codes as soon as the variable length codes have been generated.

18. The method of claim 12 wherein the generating the first compressed data stream is performed in accordance with Lempel-Ziv (LZ) compression.

19. The method of claim 18 wherein operations performed to generate the final lossless compressed bitstream using the first compressed data stream are performed in accordance with Huffman compression.

20. A machine-readable medium having program code stored thereon which, when executed by a machine, causes the machine to perform the operations of:
identifying and replacing one or more repeated bit strings from an input data stream with distances to the one or more repeated bit strings;
generating a first compressed data stream comprising literal-length data identifying a first instance of each repeated bit string and distance data comprising distances from the first instance to each repeated instance of the repeated bit string;
performing sorting, tree generation, and length calculations for literal-length values and distance values of the first compressed data stream:
mapping each literal-length value and distance value to a variable length code;
generating a header for a final compressed bit stream using the length calculations; and
substituting the variable length codes in place of the literal-length and distance values to generate a compressed bit stream body, wherein the generating of the header operates in parallel with the substituting of the variable length codes; and
combining the header with the compressed bit stream body to generate a final lossless compressed bitstream.

21. The machine-readable medium of claim 20 first sorting, tree generation, and length calculations are performed on the literal-length values and second sorting, tree generation, and length calculations are performed on the distance values.

22. The machine-readable medium of claim 20 wherein the first sorting, tree generation, and length calcul

Assignees

• Intel Corp

Inventors

• Guilford James
• Yap Kirk
• Gopal Vinodh
• Cutter Daniel
• Feghali Wajdi

Classifications

• H03M7/40

  Conversion to or from variable length codes, e.g. Shannon-Fano code, Huffman code, Morse code · CPC title

• H03M7/3086 Primary

  employing a sliding window, e.g. LZ77 · CPC title

• H03M7/6011

  Encoder aspects · CPC title

• H03M7/6029

  Pipelining · CPC title

• H03M7/6017

  Methods or arrangements to increase the throughput · CPC title