Apparatus and method for two-stage lossless data compression, and two-stage lossless data decompression

Patent metadata

Field	Value
Publication number	US-11955995-B2
Application number	US-202016872144-A
Country	US
Kind code	B2
Filing date	May 11, 2020
Priority date	May 11, 2020
Publication date	Apr 9, 2024
Grant date	Apr 9, 2024

Abstract

A lossless data compressor of an aspect includes a first lossless data compressor circuitry coupled to receive input data. The first lossless data compressor circuitry is to apply a first lossless data compression approach to compress the input data to generate intermediate compressed data. The apparatus also includes a second lossless data compressor circuitry coupled with the first lossless data compressor circuitry to receive the intermediate compressed data. The second lossless data compressor circuitry is to apply a second lossless data compression approach to compress at least some of the intermediate compressed data to generate compressed data. The second lossless data compression approach different than the first lossless data compression approach. Lossless data decompressors are also disclosed, as are methods of lossless data compression and decompression.

First claim

What is claimed is:

1. An apparatus comprising:
a first lossless data compressor circuitry coupled to receive input data, the first lossless data compressor circuitry to apply a first lossless data compression approach to compress the input data to generate intermediate compressed data; and
a second lossless data compressor circuitry coupled with the first lossless data compressor circuitry to receive the intermediate compressed data, the second lossless data compressor circuitry to apply a second lossless data compression approach to compress at least some of the intermediate compressed data to generate compressed data, the second lossless data compression approach different than the first lossless data compression approach, wherein the second lossless data compression approach includes a first part and a second part, the first part to identify strings and matching strings in the intermediate compressed data, and to replace the matching strings with distances to the matching strings and lengths of the matching strings, the second part to encode the distances and lengths as part of generating the compressed data.

2. The apparatus of claim 1 , wherein a compression speed of the first lossless data compression approach per unit amount of the input data is faster than the compression speed of the second lossless data compression approach per unit amount of the input data.

3. The apparatus of claim 2 , wherein the second lossless data compression approach is a dictionary coder based approach, and the first lossless data compression approach is not a dictionary coder based approach.

4. The apparatus of claim 1 , wherein the first lossless data compression approach is selected from group consisting of zero compress approach, a run length encoding (RLE) approach, a frequent pattern compression (FPC) approach, and a Wilson-Kaplan direct-mapped (WKdm) approach.

5. The apparatus of claim 4 , wherein the second lossless data compression approach is a Deflate approach.

6. The apparatus of claim 5 , wherein the first lossless data compression approach is a zero compress approach.

7. An apparatus comprising:
a first lossless data compressor circuitry coupled to receive input data, the first lossless data compressor circuitry to apply a first lossless data compression approach to compress the input data to generate intermediate compressed data, wherein the first lossless data compression approach is a zero compress approach, wherein the first lossless data compressor circuitry to apply the first lossless data compression approach to the input data is to generate a bitmask and a concatenated sequence of non-zero-valued elements in the input data, the bitmask to indicate which elements of the input data are zero-valued elements and which are the non-zero-valued elements; and
a second lossless data compressor circuitry coupled with the first lossless data compressor circuitry to receive the intermediate compressed data, the second lossless data compressor circuitry to apply a second lossless data compression approach to compress at least some of the intermediate compressed data to generate compressed data, the second lossless data compression approach different than the first lossless data compression approach, wherein the second lossless data compressor circuitry is to apply the second lossless data compression approach to compress the concatenated sequence of the non-zero-valued elements but not the bitmask.

8. An apparatus comprising:
a first lossless data compressor circuitry coupled to receive input data, the first lossless data compressor circuitry to apply a first lossless data compression approach to compress the input data to generate intermediate compressed data, wherein the first lossless data compression approach is a zero compress approach, wherein the first lossless data compressor circuitry to apply the first lossless data compression approach to the input data is to generate a bitmask and a concatenated sequence of non-zero-valued elements in the input data, the bitmask to indicate which elements of the input data are zero-valued elements and which are the non-zero-valued elements; and
a second lossless data compressor circuitry coupled with the first lossless data compressor circuitry to receive the intermediate compressed data, the second lossless data compressor circuitry to apply a second lossless data compression approach to compress at least some of the intermediate compressed data to generate compressed data, the second lossless data compression approach different than the first lossless data compression approach, wherein the second lossless data compressor circuitry is to apply the second lossless data compression approach to compress both the bitmask and the concatenated sequence of the non-zero-valued elements.

9. The apparatus of claim 1 , wherein the first lossless data compressor circuitry comprises:
a first input structure coupled to receive the input data;
a first circuitry coupled with the first input structure to receive the input data, the first circuitry to apply the first lossless data compression approach to the input data to generate the intermediate compressed data; and
a first output structure coupled with the first circuitry to output the intermediate compressed data.

10. The apparatus of claim 9 , wherein the second lossless data compressor circuitry comprises:
a second input structure coupled with the first output structure to receive the intermediate compressed data;
a second circuitry coupled with the second input structure to receive the intermediate compressed data, the second circuitry to apply the second lossless data compression approach to the intermediate compressed data to generate the compressed data; and
a second output structure coupled with the second circuitry to output the compressed data.

11. The apparatus of claim 10 , wherein the first lossless data compressor circuitry comprises:
a third circuitry coupled with the first input structure, the third circuitry to apply a third lossless data compression approach to compress data, the third lossless data compression approach different than the first lossless data compression approach.

12. An apparatus comprising:
a first lossless data compressor circuitry coupled to receive input data, the first lossless data compressor circuitry to apply a first lossless data compression approach to compress the input data to generate intermediate compressed data, wherein the first lossless data compressor circuitry is operative to apply a third lossless data compression approach to additional data, the third lossless data compression approach different than the first lossless data compression approach; and
a second lossless data compressor circuitry coupled with the first lossless data compressor circuitry to receive the intermediate compressed data, the second lossless data compressor circuitry to apply a second lossless data compression approach to compress at least some of the intermediate compressed data to generate compressed data, the second lossless data compression approach different than the first lossless data compression approach.

13. The apparatus of claim 1 , wherein the first lossless data compressor circuitry and the second lossless data compressor circuitry are part of a same lossless data compression pipeline.

14. The apparatus of claim 1 , wherein the first lossless data compressor circuitry and the second lossless data compressor circuitry are to be controlled responsive to a single control primitive to said apply the first lossless data compression approach and said apply the second lossless data compression approach, respectively.

Assignees

• Intel Corp

Inventors

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

Classifications

• H03M7/607 Primary

  Selection between different types of compressors · CPC title

• H03M7/3066

  by means of a mask or a bit-map · CPC title

• H03M7/3084

  using adaptive string matching, e.g. the Lempel-Ziv method · CPC title

• H03M7/46

  Conversion to or from run-length codes, i.e. by representing the number of consecutive digits, or groups of digits, of the same kind by a code word and a digit indicative of that kind · CPC title

• H03M7/6029

  Pipelining · CPC title