Decompression engine supporting large match offsets using external memory

Patent metadata

Field	Value
Publication number	US-12367142-B1
Application number	US-202418419630-A
Country	US
Kind code	B1
Filing date	Jan 23, 2024
Priority date	Jan 23, 2024
Publication date	Jul 22, 2025
Grant date	Jul 22, 2025

Abstract

A decompression apparatus includes a cache memory and a decoder. The decoder is to receive a compressed input data stream including literals and matches. Each literal represents a data value, and each match represents a respective sequence of literals by a respective offset pointing to a respective past occurrence of the sequence of literals. The decoder is to decompress the input data stream by replacing each match with the corresponding past occurrence, so as to produce an output data stream. In replacing a given match with the corresponding past occurrence, the decoder is to (i) when the offset indicates that the past occurrence is cached in the cache memory, retrieve the past occurrence from the cache memory, and (ii) when the offset indicates that the past occurrence is not contained in the cache memory, fetch the past occurrence from an external memory.

First claim

The invention claimed is:

1. A decompression method, comprising:
receiving a compressed input data stream comprising literals and matches, wherein (i) each literal represents a data value, and (ii) each match represents a respective sequence of literals by a respective offset pointing to a respective past occurrence of the sequence of literals;
decompressing the input data stream by replacing each match with the corresponding past occurrence so as to produce an output data stream; and
outputting, by a decompression engine, the output data stream to an external memory and to a cache memory,
wherein replacing a given match with the corresponding past occurrence comprises:
when the offset indicates that the past occurrence is cached in the cache memory, retrieving the past occurrence from the cache memory; and
when the offset indicates that the past occurrence is not contained in the cache memory, fetching the past occurrence from the external memory.

2. The method according to claim 1 , and comprising deciding whether or not the past occurrence is cached in the cache memory, by comparing the offset to a threshold.

3. The method according to claim 1 , wherein decompressing the input data stream comprises:
detecting the given match in the input data stream and sending a request for the corresponding past occurrence to the external memory;
delaying the input data stream at least by an access latency of the external memory; and
merging the past occurrence fetched from the external memory into the delayed input data stream, thereby producing the output data stream.

4. The method according to claim 1 , wherein fetching the past occurrence from the external memory comprises communicating with the external memory over a peripheral bus.

5. The method according to claim 1 , wherein fetching the past occurrence from the external memory comprises communicating with the external memory over a network connection.

6. A decompression apparatus, comprising:
a cache memory; and
a decoder, to:
receive a compressed input data stream comprising literals and matches, wherein (i) each literal represents a data value, and (ii) each match represents a respective sequence of literals by a respective offset pointing to a respective past occurrence of the sequence of literals;
decompress the input data stream by replacing each match with the corresponding past occurrence, so as to produce an output data stream; and
output the output data stream to an external memory and to the cache memory,
wherein, in replacing a given match with the corresponding past occurrence, the decoder is to:
when the offset indicates that the past occurrence is cached in the cache memory, retrieve the past occurrence from the cache memory; and
when the offset indicates that the past occurrence is not contained in the cache memory, fetch the past occurrence from the external memory.

7. The apparatus according to claim 6 , wherein the decoder is to decide whether or not the past occurrence is cached in the cache memory, by comparing the offset to a threshold.

8. The apparatus according to claim 6 , wherein the decoder comprises:
a match detector, to detect the given match in the input data stream and send a request for the corresponding past occurrence to the external memory;
a delay buffer, to delay the input data stream at least by an access latency of the external memory; and
a data merger coupled to an output of the delay buffer, the data merger to merge the past occurrence fetched from the external memory into the delayed input data stream, thereby producing the output data stream.

9. The apparatus according to claim 6 , wherein the decoder is to fetch the past occurrence from the external memory by communicating with the external memory over a peripheral bus.

10. The apparatus according to claim 6 , wherein the decoder is to fetch the past occurrence from the external memory by communicating with the external memory over a network connection.

11. A decompression apparatus, comprising:
a cache memory; and
a decoder, to:
receive a compressed input data stream comprising literals and matches, wherein (i) each literal represents a data value, and (ii) each match comprises an offset value pointing to a corresponding past occurrence of a respective sequence of literals;
decompress the input data stream by replacing each match with the corresponding past occurrence, so as to produce an output data stream; and
output the output data stream to an external memory and to the cache memory,
wherein, in replacing a given match with the corresponding past occurrence, the decoder is to:
when the offset indicates that the past occurrence is cached in the cache memory, retrieve the past occurrence from the cache memory; and
when the offset indicates that the past occurrence is not contained in the cache memory, fetch the past occurrence from the external memory.

12. A peripheral device, comprising:
a host interface, to communicate with a host; and
a decompression engine comprising a cache memory, the decompression engine to:
receive a compressed input data stream comprising literals and matches, wherein (i) each literal represents a data value, and (ii) each match represents a respective sequence of literals by a respective offset pointing to a respective past occurrence of the sequence of literals;
decompress the input data stream by replacing each match with the corresponding past occurrence, so as to produce an output data stream; and
output the output data stream to an external memory of the host and to the cache memory,
wherein, in replacing a given match with the corresponding past occurrence, the decompression engine is to:
when the offset indicates that the past occurrence is cached in the cache memory, retrieve the past occurrence from the cache memory; and
when the offset indicates that the past occurrence is not contained in the cache memory, fetch the past occurrence over the host interface from the external memory.

13. The peripheral device according to claim 12 , wherein the decompression engine is to decide whether or not the past occurrence is cached in the cache memory, by comparing the offset to a threshold.

14. The peripheral device according to claim 12 , wherein the decompression engine comprises:
a match detector, to detect the given match in the input data stream and send a request for the corresponding past occurrence to the external memory;
a delay buffer, to delay the input data stream at least by an access latency of the external memory; and
a data merger coupled to an output of the delay buffer, the data merger to merge the past occurrence fetched from the external memory into the delayed input data stream, thereby producing the output data stream.

15. The peripheral device according to claim 12 , wherein the decompression engine is to fetch the past occurrence from the external memory by communicating with the external memory over a peripheral bus.

16. The peripheral device according to claim 12 , wherein the decompression engine is to fetch the past occurrence from the external memory by communicating with the external memory over a network connection.

Assignees

• Mellanox Technologies Ltd

Inventors

• Chapman Hillel
• Bohsas Saleh

Classifications

• G06F2212/401

  Compressed data · CPC title

• G06F12/0875

  with dedicated cache, e.g. instruction or stack · CPC title

• H03M7/425

  for the decoding process only · CPC title

• H03M7/3086

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

• H03M7/6005 Primary

  Decoder aspects · CPC title