# US 2017/0285960 A1 · Hardware apparatuses and methods for memory compression and decompression

> Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt

- Number: US 2017/0285960 A1
- Document ID: US20170285960A1
- Status: Published application
- Kind: A1
- Application number: 15/089,456
- Filed: 2016-04-01
- Published: 2017-10-05
- Earliest claimed: 2016-04-01
- Assignees: Intel Corporation
- Inventors: Kirk S. Yap; Vinodh Gopal; James D. Guilford; Sean M. Gulley
- Web page: https://patentgrep.com/patent/US20170285960A1

## CPC

- G06F 3/064: {Management of blocks}
- G06F 12/00: Accessing, addressing or allocating within memory systems or architectures (digital input from, or digital output to record carriers, e.g. to disk storage units, G06F3/06)
- H03M 7/30: Compression (speech analysis-synthesis for redundancy reduction G10L19/00; for image communication H04N); Expansion; Suppression of unnecessary data, e.g. redundancy reduction
- H03M 7/3084: {using adaptive string matching, e.g. the Lempel-Ziv method}
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)
- H03M: CODING; DECODING; CODE CONVERSION IN GENERAL (using fluidic means F15C4/00; optical analogue/digital converters G02F7/00; coding, decoding or code conversion, specially adapted for particular applications, see the relevant subclasses, e.g. G01D, G01R, G06F, G06T, G09G, G10L, G11B, G11C, H04B, H04L, H04M, H04N; ciphering or deciphering for cryptography or other purposes involving the need for secrecy G09C)

## Abstract

Methods and apparatuses relating to memory compression and decompression are described. In one embodiment, a hardware compression engine is to determine when each section of a plurality of sections of a block of data is a zero value, a full match or a partial match to an entry in a dictionary, or a no match to any entry in the dictionary, encode a tag for each section to indicate the one of the zero value, the full match, the partial match, and the no match, encode a literal when the section is the no match, an index to the entry in the dictionary when the section is the full match, and an index to the entry in the dictionary and non-matching bits when the section is the partial match, and update an entry in the dictionary with a value of a section when the section is the no match.

## Claims

### Claim 1

A memory controller comprising:
a connection to a memory; and
a hardware compression engine to:
receive a plurality of sections of a block of data from the memory to compress,
determine when each section of the plurality of sections is one of a zero value, a full match to an entry in a dictionary comprising a plurality of entries with a value and an index, a partial match to an entry in the dictionary, and a no match to any entry in the dictionary,
encode a tag for each section to indicate the one of the zero value, the full match, the partial match, and the no match,
encode a literal when the section is the no match, an index to the entry in the dictionary when the section is the full match, and an index to the entry in the dictionary and non-matching bits when the section is the partial match, and
update an entry in the dictionary with a value of a section when the section is the no match.

### Claim 2 (depends on 1)

The memory controller of claim 1, wherein the tag is an only output from the hardware compression engine for the zero value.

### Claim 3 (depends on 1)

The memory controller of claim 1, wherein tags for the plurality of sections are to be output from the hardware compression engine in a single field.

### Claim 4 (depends on 3)

The memory controller of claim 3, wherein literals for the plurality of sections are to be output from the hardware compression engine in a single field, indexes for the plurality of sections are to be output from the hardware compression engine in a single field, and non-matching bits for the plurality of sections are to be output from the hardware compression engine in a single field.

### Claim 5 (depends on 1)

The memory controller of claim 1, wherein literals for the plurality of sections are to be output from the hardware compression engine in a single field in a same order as in the block of data.

### Claim 6 (depends on 1)

The memory controller of claim 1, wherein the hardware compression engine is to generate a hash for each of the plurality of sections of a block of data to use as an index in the dictionary.

### Claim 7 (depends on 1)

The memory controller of claim 1, wherein the hardware compression engine is to, when indices for multiple of the plurality of sections are the same, update the entry in the dictionary with the value of the section that is most recent in a same order as in the block of data.

### Claim 8 (depends on 1)

The memory controller of claim 1, wherein the hardware compression engine is to initially populate the dictionary with a plurality of most common values of sections of the block of data other than zero values.

### Claim 9

A method comprising:
receiving a plurality of sections of a block of data from a memory to compress with a hardware compression engine;
determining with the hardware compression engine when each section of the plurality of sections is one of a zero value, a full match to an entry in a dictionary comprising a plurality of entries with a value and an index, a partial match to an entry in the dictionary, and a no match to any entry in the dictionary;
encoding with the hardware compression engine a tag for each section to indicate the one of the zero value, the full match, the partial match, and the no match;
encoding with the hardware compression engine a literal when the section is the no match, an index to the entry in the dictionary when the section is the full match, and an index to the entry in the dictionary and non-matching bits when the section is the partial match; and
updating with the hardware compression engine an entry in the dictionary with a value of a section when the section is the no match.

### Claim 10 (depends on 9)

The method of claim 9, further comprising only outputting the tag for the zero value.

### Claim 11 (depends on 9)

The method of claim 9, further comprising outputting tags for the plurality of sections in a single field.

### Claim 12 (depends on 11)

The method of claim 11, further comprising outputting literals for the plurality of sections in a single field, indexes for the plurality of sections in a single field, and non-matching bits for the plurality of sections in a single field.

### Claim 13 (depends on 9)

The method of claim 9, further comprising outputting literals for the plurality of sections in a single field in a same order as in the block of data.

### Claim 14 (depends on 9)

The method of claim 9, further comprising generating a hash for each of the plurality of sections of a block of data to use as an index in the dictionary.

### Claim 15 (depends on 9)

The method of claim 9, further comprising, when indices for multiple of the plurality of sections are the same, updating the entry in the dictionary with the value of the section that is most recent in a same order as in the block of data.

### Claim 16 (depends on 9)

The method of claim 9, further comprising initially populating the dictionary with a plurality of most common values of sections of the block of data other than zero values.

### Claim 17

A non-transitory machine readable medium that stores code that when executed by a machine causes the machine to perform a method comprising:
receiving a plurality of sections of a block of data from a memory to compress with a hardware compression engine;
determining with the hardware compression engine when each section of the plurality of sections is one of a zero value, a full match to an entry in a dictionary comprising a plurality of entries with a value and an index, a partial match to an entry in the dictionary, and a no match to any entry in the dictionary;
encoding with the hardware compression engine a tag for each section to indicate the one of the zero value, the full match, the partial match, and the no match;
encoding with the hardware compression engine a literal when the section is the no match, an index to the entry in the dictionary when the section is the full match, and an index to the entry in the dictionary and non-matching bits when the section is the partial match; and
updating with the hardware compression engine an entry in the dictionary with a value of a section when the section is the no match.

### Claim 18 (depends on 17)

The non-transitory machine readable medium of claim 17, wherein the method further comprises only outputting the tag for the zero value.

### Claim 19 (depends on 17)

The non-transitory machine readable medium of claim 17, wherein the method further comprises outputting tags for the plurality of sections in a single field.

### Claim 20 (depends on 19)

The non-transitory machine readable medium of claim 19, wherein the method further comprises outputting literals for the plurality of sections in a single field, indexes for the plurality of sections in a single field, and non-matching bits for the plurality of sections in a single field.

### Claim 21 (depends on 17)

The non-transitory machine readable medium of claim 17, wherein the method further comprises outputting literals for the plurality of sections in a single field in a same order as in the block of data.

### Claim 22 (depends on 17)

The non-transitory machine readable medium of claim 17, wherein the method further comprises generating a hash for each of the plurality of sections of a block of data to use as an index in the dictionary.

### Claim 23 (depends on 17)

The non-transitory machine readable medium of claim 17, wherein the method further comprises, when indices for multiple of the plurality of sections are the same, updating the entry in the dictionary with the value of the section that is most recent in a same order as in the block of data.

### Claim 24 (depends on 17)

The non-transitory machine readable medium of claim 17, wherein the method further comprises initially populating the dictionary with a plurality of most common values of sections of the block of data other than zero values.