# US 10,120,609 B2 · Technologies for deterministic constant-time data compression

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

- Number: US 10,120,609 B2
- Document ID: US10120609B2
- Status: Granted
- Kind: B2
- Application number: 15/720,920
- Filed: 2017-09-29
- Published: 2018-05-31
- Granted: 2018-11-06
- Earliest claimed: 2016-11-29
- Assignees: Intel Corporation
- Applicants: Intel Corporation
- Inventors: James D. Guilford; Vinodh Gopal; Daniel F. Cutter
- Web page: https://patentgrep.com/patent/US10120609B2

## CPC

- G06F 3/0641: {De-duplication techniques}
- G06F 3/0604: {Improving or facilitating administration, e.g. storage management}
- G06F 3/065: {Replication mechanisms}
- G06F 3/067: {Distributed or networked storage systems, e.g. storage area networks [SAN], network attached storage [NAS]}
- G06F 3/0608: {Saving storage space on storage systems}
- G06F 3/0611: {in relation to response time}
- G06F 3/0613: {in relation to throughput}
- G06F 3/0617: {in relation to availability}
- G06F 3/0647: {Migration mechanisms}
- G06F 3/0653: {Monitoring storage devices or systems}
- G06F 7/06: Arrangements for sorting, selecting, merging, or comparing data on individual record carriers
- G06F 8/654: using techniques specially adapted for alterable solid state memories, e.g. for EEPROM or flash memories
- G06F 8/656: while running
- G06F 8/658: Incremental updates; Differential updates
- G06F 9/3851: {from multiple instruction streams, e.g. multistreaming}
- G06F 9/3891: {organised in groups of units sharing resources, e.g. clusters}
- G06F 9/4401: Bootstrapping (security arrangements therefor G06F21/57)
- G06F 9/4881: {Scheduling strategies for dispatcher, e.g. round robin, multi-level priority queues}
- G06F 9/505: {considering the load}
- G06F 9/5038: {considering the execution order of a plurality of tasks, e.g. taking priority or time dependency constraints into consideration (scheduling strategies G06F9/4881 and subgroups)}
- G06F 9/544: {Buffers; Shared memory; Pipes}
- G06F 11/079: {Root cause analysis, i.e. error or fault diagnosis (in a hardware test environment G06F11/22; in a software test environment G06F11/36)}
- G06F 11/0709: {in a distributed system consisting of a plurality of standalone computer nodes, e.g. clusters, client-server systems}
- G06F 11/0751: {Error or fault detection not based on redundancy (power supply failures G06F1/30; network fault management H04L41/06)}
- G06F 11/3006: {where the computing system is distributed, e.g. networked systems, clusters, multiprocessor systems (multiprogramming arrangements G06F9/46; allocation of resources G06F9/50)}
- G06F 11/3034: {where the computing system component is a storage system, e.g. DASD based or network based (digital input from or digital output to record carriers G06F3/06; digital recording or reproducing G11B20/18; for distributed storage of data in networks, e.g. transport arrangements for network file system [NFS], storage area networks [SAN] or network attached storage [NAS], H04L67/1097)}
- G06F 11/3055: {Monitoring arrangements for monitoring the status of the computing system or of the computing system component, e.g. monitoring if the computing system is on, off, available, not available (error or fault processing without redundancy G06F11/0703; error detection or correction by redundancy in data representation G06F11/08; error detection or correction of the data by redundancy in operations G06F11/14; error detection or correction by redundancy in hardware G06F11/16)}
- G06F 11/3409: {for performance assessment}
- G06F 12/0284: {Multiple user address space allocation, e.g. using different base addresses (interprocessor communication G06F15/163)}
- G06F 12/0692: {Multiconfiguration, e.g. local and global addressing}
- G06F 13/1652: {in a multiprocessor architecture (interprocessor communication using common memory G06F15/167)}
- G06F 17/30153
- G06F 21/57: Certifying or maintaining trusted computer platforms, e.g. secure boots or power-downs, version controls, system software checks, secure updates or assessing vulnerabilities
- G06F 21/6218: {to a system of files or objects, e.g. local or distributed file system or database}
- G06F 21/73: by creating or determining hardware identification, e.g. serial numbers
- G06F 21/76: in application-specific integrated circuits [ASIC] or field-programmable devices, e.g. field-programmable gate arrays [FPGA] or programmable logic devices [PLD]
- G06T 1/20: Processor architectures; Processor configuration, e.g. pipelining
- G06T 1/60: Memory management
- G06T 9/005: {Statistical coding, e.g. Huffman, run length coding}
- H01R 13/4538: {Covers sliding or withdrawing in the direction of engagement}
- H01R 13/631: for engagement only
- H03K 19/1731: {Optimisation thereof}
- H03M 7/3084: {using adaptive string matching, e.g. the Lempel-Ziv method}
- H03M 7/40: Conversion to or from variable length codes, e.g. Shannon-Fano code, Huffman code, Morse code
- H03M 7/42: using table look-up for the coding or decoding process, e.g. using read-only memory {(H03M7/4006 takes precedence)}
- H03M 7/60: {General implementation details not specific to a particular type of compression}
- H03M 7/6011: {Encoder aspects}
- H03M 7/6017: {Methods or arrangements to increase the throughput}
- H03M 7/6029: {Pipelining}
- H04L 9/0822: {using key encryption key}
- H04L 12/2881: {IP/Ethernet DSLAM}
- H04L 12/4633: {Interconnection of networks using encapsulation techniques, e.g. tunneling}
- H04L 41/044: comprising hierarchical management structures
- H04L 43/04: Processing captured monitoring data, e.g. for logfile generation
- H04L 43/06: Generation of reports
- H04L 43/08: Monitoring or testing based on specific metrics, e.g. QoS, energy consumption or environmental parameters
- H04L 43/0894: Packet rate
- H04L 47/20: Traffic policing
- H04L 47/2441: relying on flow classification, e.g. using integrated services [IntServ]
- H04L 49/104: Asynchronous transfer mode [ATM] switching fabrics
- H04L 61/2007
- H04L 67/1014: based on the content of a request
- H04L 67/327
- H04L 67/36
- H05K 7/1452: {Mounting of connectors; Switching; Reinforcing of back panels}
- H05K 7/1487: {Blade assemblies, e.g. blade cases or inner arrangements within a blade}
- G06F 11/1453: {using de-duplication of the data}
- G06F 12/023: {Free address space management}
- G06F 15/80: comprising an array of processing units with common control, e.g. single instruction multiple data processors (G06F15/82 takes precedence {; for correlation function computation G06F17/15})
- G06F 2212/401: Compressed data
- G06F 2212/402: Encrypted data
- G06F 2221/2107: File encryption
- H04L 41/046: comprising network management agents or mobile agents therefor
- H04L 41/0896: Bandwidth or capacity management, i.e. automatically increasing or decreasing capacities (flow or congestion control using dynamic resource allocation, e.g. in-call renegotiation, H04L47/76)
- H04L 41/142: using statistical or mathematical methods
- H04L 63/1425: {Traffic logging, e.g. anomaly detection}
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)
- G06T: IMAGE DATA PROCESSING OR GENERATION, IN GENERAL
- H01R: ELECTRICALLY-CONDUCTIVE CONNECTIONS; STRUCTURAL ASSOCIATIONS OF A PLURALITY OF MUTUALLY-INSULATED ELECTRICAL CONNECTING ELEMENTS; COUPLING DEVICES; CURRENT COLLECTORS
- H03K: PULSE TECHNIQUE (measuring pulse characteristics G01R; modulating sinusoidal oscillations with pulses H03C; transmission of digital information H04L; discriminator circuits detecting phase difference between two signals by counting or integrating cycles of oscillation H03D3/04; automatic control, starting, synchronisation or stabilisation of generators of electronic oscillations or pulses where the type of generator is irrelevant or unspecified H03L; coding, decoding or code conversion, in general H03M)
- 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)
- H04L: TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION (arrangements common to telegraphic and telephonic communication H04M)
- H05K: PRINTED CIRCUITS; CASINGS OR CONSTRUCTIONAL DETAILS OF ELECTRIC APPARATUS; MANUFACTURE OF ASSEMBLAGES OF ELECTRICAL COMPONENTS

## Abstract

A compute device to generate deterministic compressed streams receives a current string to be matched to one or more prior instances of the current string, the current string being located within an input buffer and the one or more prior instances located within a history buffer. The compute device identifies a limited subset of index memory designated for storing pointers to the prior instances, identifying a reserved slop region in the index memory, and compares the current string to a prior instance, locating the at least one prior instance using at least one pointer to the at least one prior instance. The at least one pointer is stored within the limited subset of the index memory, and the compute device also prohibits use of any pointers stored in the reserved slop region of the index memory. Other embodiments are described and claimed.

## Claims

### Claim 1

A compute device to generate deterministic compressed streams, the compute device comprising:
a compare engine to:
receive a current string to be matched to one or more prior instances of the current string, the current string located within an input buffer and the one or more prior instances located within a history buffer;
identify a limited subset of an index memory of the compare engine designated for storing pointers to the one or more prior instances, wherein to identify the limited subset is to identify a reserved slop region in the index memory; and
compare the current string to at least one prior instance of the one or more prior instances, wherein to compare the current string is to locate the at least one prior instance using at least one pointer to the at least one prior instance, wherein the at least one pointer is stored within the limited subset of the index memory, and wherein to compare the current string is further to prohibit use of any pointers stored in the reserved slop region of the index memory.

### Claim 2 (depends on 1)

The compute device of claim 1, wherein the compare engine comprises a hardware accelerator.

### Claim 3 (depends on 1)

The compute device of claim 1, wherein to compare the current string comprises to traverse in an order that is a reverse of an initialization order and to stop the traverse in response to entering the reserved slop region.

### Claim 4 (depends on 1)

The compute device of claim 1, further comprising a table updater to index the input buffer at positions from the current string up to a pre-advance limit, wherein the reserved slop region has a length determined as a function of to the pre-advance limit.

### Claim 5 (depends on 4)

The compute device of claim 4, wherein the length of the reserved slop region equals one pointer for each position of the pre-advance limit.

### Claim 6 (depends on 1)

The compute device of claim 1, wherein the compare engine is further to compare a plurality of instances and retire the comparisons in a natural order.

### Claim 7 (depends on 6)

The compute device of claim 6, wherein the natural order is a function of an input byte order.

### Claim 8 (depends on 6)

The compute device of claim 6, wherein the natural order is further a function of one or more heuristic matching rules.

### Claim 9 (depends on 1)

The compute device of claim 1, further comprising a table updater to generate a hash of an n-byte prefix string of the current string.

### Claim 10 (depends on 9)

The compute device of claim 9, wherein the table updater is further to:
look up a hash table entry in a hash table using the hash, wherein the hash table entry holds one or more pointers to the one or more prior instances;
determine whether the hash table entry is full; and
write the hash table entry to a spill table in response to a determination that the hash table entry is full.

### Claim 11 (depends on 10)

The compute device of claim 10, wherein the table updater is to overwrite an oldest spill table entry in the spill table using the hash table entry.

### Claim 12

A method for data compression, the method comprising:
receiving, by a compare engine of a computing device, a current string to be matched to one or more prior instances of the current string, the current string located within an input buffer and the one or more prior instances located within a history buffer;
identifying, by the compare engine, a limited subset of an index memory of the compare engine designated for storing pointers to the one or more prior instances, further comprising identifying a reserved slop region in the index memory; and
comparing, by the compare engine, the current string to at least one prior instance of the one or more prior instances, wherein comparing the current string further comprises locating the at least one prior instance using at least one pointer to the at least one prior instance, wherein the at least one pointer is stored within the limited subset of the index memory, and wherein comparing the current string includes prohibiting use of any pointers stored in the reserved slop region of the index memory.

### Claim 13 (depends on 12)

The method of claim 12, wherein the compare engine comprises a hardware accelerator.

### Claim 14 (depends on 12)

The method of claim 12, wherein comparing the current string comprises traversing in an order that is a reverse of an initialization order and stopping the traverse in response to entering the reserved slop region.

### Claim 15 (depends on 12)

The method of claim 12, further comprising indexing, by the computing device, the input buffer at positions from the current string up to a pre-advance limit, wherein the reserved slop region has a length determined as a function of to the pre-advance limit.

### Claim 16 (depends on 15)

The method of claim 15, wherein the length of the reserved slop region equals one pointer for each position of the pre-advance limit.

### Claim 17 (depends on 12)

The method of claim 12, wherein comparing the current string to the at least one prior instance comprises comparing the current string to a plurality of instances, the method further comprising retiring, by the compare engine, the plurality of comparisons in a natural order.

### Claim 18 (depends on 12)

The method of claim 12, further comprising generating, by a table updater of the computing device, a hash of an n-byte prefix string of the current string.

### Claim 19

One or more non-transitory computer-readable storage media comprising a plurality of instructions stored thereon that, when executed by a computing device cause the computing device to:
receive, by a compare engine of the computing device, a current string to be matched to one or more prior instances of the current string, the current string located within an input buffer and the one or more prior instances located within a history buffer;
identify, by the compare engine, a limited subset of an index memory of the compare engine designated for storing pointers to the one or more prior instances, further comprising identifying a reserved slop region in the index memory; and
compare, by the compare engine, the current string to at least one prior instance of the one or more prior instances, wherein comparing the current string further comprises locating the at least one prior instance using at least one pointer to the at least one prior instance, wherein the at least one pointer is stored within the limited subset of the index memory, and wherein comparing the current string includes prohibiting use of any pointers stored in the reserved slop region of the index memory.

### Claim 20 (depends on 19)

The one or more computer-readable storage media of claim 19, wherein the compare engine comprises a hardware accelerator.

### Claim 21 (depends on 19)

The one or more computer-readable storage media of claim 19, wherein to compare the current string comprises traversing in an order that is a reverse of an initialization order and to stop the traverse in response to entering the reserved slop region.

### Claim 22 (depends on 19)

The one or more computer-readable storage media of claim 19, further comprising a plurality of instructions stored thereon that, when executed by the computing device cause the computing device to index the input buffer at positions from the current string up to a pre-advance limit, wherein the reserved slop region has a length determined as a function of to the pre-advance limit.

### Claim 23 (depends on 22)

The one or more computer-readable storage media of claim 22, wherein the length of the reserved slop region equals one pointer for each position of the pre-advance limit.

### Claim 24 (depends on 19)

The one or more computer-readable storage media of claim 19, wherein to compare the current string to the at least one prior instance comprises to compare the current string to a plurality of instances, the computer-readable storage media further comprising a plurality of instructions stored thereon that, when executed by the computing device cause the computing device to retire, by the compare engine, the plurality of comparisons in a natural order.

### Claim 25 (depends on 19)

The one or more computer-readable storage media of claim 19, further comprising a plurality of instructions stored thereon that, when executed by the computing device cause the computing device to generate, by a table updater of the computing device, a hash of an n-byte prefix string of the current string.