# US 10,374,628 B2 · In-place data compression with small working memory

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

- Number: US 10,374,628 B2
- Document ID: US10374628B2
- Status: Granted
- Kind: B2
- Application number: 15/480,302
- Filed: 2017-04-05
- Published: 2018-10-11
- Granted: 2019-08-06
- Earliest claimed: 2017-04-05
- Assignees: International Business Machines Corporation
- Applicants: International Business Machines Corporation
- Inventors: Bulent Abali; Bartholomew Blaner; Paul G. Crumley; Hubertus Franke
- Web page: https://patentgrep.com/patent/US10374628B2

## CPC

- 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
- G06F 3/0604: {Improving or facilitating administration, e.g. storage management}
- G06F 3/0605: {by facilitating the interaction with a user or administrator}
- G06F 3/064: {Management of blocks}
- G06F 3/0679: {Non-volatile semiconductor memory device, e.g. flash memory, one time programmable memory [OTP]}
- G06F 13/1694: {Configuration of memory controller to different memory types}
- G11C 7/10: Input/output [I/O] data interface arrangements, e.g. I/O data control circuits, I/O data buffers
- H03M 7/3091: {Data deduplication}
- 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)
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)
- G11C: STATIC STORES (semiconductor memory devices H10B)

## Abstract

Method and apparatus for performing in-place compression is provided. The in-place compression system transfers source data from a partition of a memory to a data buffer based on a read address. Compressed data is created by referencing the source data stored in the data buffer. The system writes the compressed data to the memory partition based on a write address. When the write address points at an address location that stores source data that has not been transferred to the data buffer, the system overwrites the compressed data stored in the memory partition with the source data stored in the data buffer.

## Claims

### Claim 1

A computer-implemented method comprising:
transferring source data from a partition of a memory to a data buffer based on a read address;
creating compressed data by referencing the source data stored in the data buffer;
writing the compressed data to the memory partition based on a write address;
overwriting the compressed data stored in the memory partition with the source data stored in the data buffer when the write address points to an address location that stores source data that has not been transferred to the data buffer.

### Claim 2 (depends on 1)

The computer-implemented method of claim 1, wherein the write address points to an address location that stores source data that has not been transferred to the data buffer when the write address and the read address are the same.

### Claim 3 (depends on 1)

The computer-implemented method of claim 1, wherein the data buffer is equal in size to the memory partition.

### Claim 4 (depends on 1)

The computer-implemented method of claim 1, further comprising:
generating a compression header prior to retrieving data from the memory partition;
storing the compression header in an overflow buffer;
transferring the compression header from the overflow buffer to the memory partition after enough source data has been transferred to the data buffer from the memory partition.

### Claim 5 (depends on 4)

The computer-implemented method of claim 4, wherein a size of the overflow is based on a size of a compression header.

### Claim 6 (depends on 4)

The computer-implemented method of claim 4, wherein the overflow buffer and the data buffer reside in a free area of the memory.

### Claim 7 (depends on 1)

The computer-implemented method of claim 1, wherein writing the compressed data to the memory partition comprises:
writing the compressed data into the memory partition when the write address lags behind the read address;
writing the compressed data at an overflow buffer instead of the memory partition when the write address is equal to the read address; and
transferring the data stored in the overflow buffer to the memory partition when the write address lags behind the read address.

### Claim 8 (depends on 1)

The computer-implemented method of claim 1, further comprising overwriting the compressed data stored in the memory partition with the data stored in the data buffer when, upon completion of the compress data into the memory partition, a compression ratio between a size of the compressed data and a size of the source data of the memory partition is more than a threshold ratio.

### Claim 9 (depends on 8)

The computer-implemented method of claim 8, wherein the compression ratio is determined based on the read address and the write address.

### Claim 10

A computing device comprising:
a set of one or more processing units; and
a storage device storing a set of instructions, wherein an execution of the set of instructions by the set of processing units configures the computing device to perform acts comprising:
transferring source data from a partition of a memory to a data buffer based on a read address;
creating compressed data by referencing the source data stored in the data buffer;
writing the compressed data to the memory partition based on a write address; and
overwriting the compressed data stored in the memory partition with the source data stored in the data buffer when the write address points to an address location that stores source data that has not been transferred to the data buffer.

### Claim 11 (depends on 10)

The computing device of claim 10, wherein the write address points to an address location that stores source data that has not been transferred to the data buffer when the write address and the read address are the same.

### Claim 12 (depends on 10)

The computing device of claim 10, wherein the execution of the set of instructions further configures the computer device to perform acts comprising:
generating a compression header prior to retrieving data from the memory partition;
storing the compression header in an overflow buffer;
transferring the compression header from the overflow buffer to the memory partition after enough source data has been transferred to the data buffer from the memory partition.

### Claim 13 (depends on 12)

The computing device of claim 12, wherein the overflow buffer and the data buffer reside in a free area of the memory.

### Claim 14 (depends on 10)

The computing device of claim 10, wherein writing the compressed data to the memory partition comprises:
writing the compressed data into the memory partition when the write address lags behind the read address;
writing the compressed data at an overflow buffer instead of the memory partition when the write address is equal to the read address; and
transferring the data stored in the overflow buffer to the memory partition when the write address lags behind the read address.

### Claim 15 (depends on 14)

The computing device of claim 14, wherein the overflow buffer is smaller in size than the data buffer.

### Claim 16 (depends on 10)

The computing device of claim 10, wherein the execution of the set of instructions further configures the computer device to perform acts comprising overwriting the compressed version of the data stored in the memory partition with the data stored in the data buffer when, upon completion of the compress data into the memory partition, a compression ratio between a size of the compressed data and a size of the source data of the memory partition is more than a threshold ratio, wherein the compression ratio is determined based on the read address and the write address.

### Claim 17

A computer program product comprising:
one or more non-transitory computer-readable storage device and program instructions stored on at least one of the one or more non-transitory storage devices, the program instructions executable by a processor, the program instructions comprising sets of instructions for:
transferring source data from a partition of a memory to a data buffer based on a read address;
creating compressed data by referencing the source data stored in the data buffer;
writing the compressed data to the memory partition based on a write address; and
overwriting the compressed data stored in the memory partition with the source data stored in the data buffer when the write address points at an address location that stores source data that has not been transferred to the data buffer.

### Claim 18 (depends on 17)

The computer-implemented method of claim 17, wherein writing the compressed data to the memory partition comprises:
writing the compressed data into the memory partition when the write address lags behind the read address;
writing the compressed data at an overflow buffer and not the memory partition when the write address is equal to the read address; and
transferring the data stored in the overflow buffer to the memory partition when the write address lags behind the read address.

### Claim 19 (depends on 18)

The computer-implemented method of claim 18, further comprising:
generating a compression header prior to retrieving data from the memory partition;
storing the compression header in an overflow buffer;
transferring the compression header from the overflow buffer to the memory partition after enough source data has been transferred to the data buffer from the memory partition.

### Claim 20 (depends on 17)

The computer-implemented method of claim 17, further comprising overwriting the compressed version of the data stored in the memory partition with the data stored in the data buffer when, upon completion of the compress data into the memory partition, a compression ratio between a size of the compressed data and a size of the source data of the memory partition is more than a threshold ratio, wherein the compression ratio is determined based on the read address and the write address.