Method to shorten hash chains in lempel-ziv compression of data with repetitive symbols
AssigneeSeagate Technology LLC
InventorNing Chen
Life of this patent
Estimating the term…
Abstract
An apparatus having a circuit is disclosed. The circuit may be configured to (i) generate a sequence of hash values in a table from a stream of data values with repetitive values, (ii) find two consecutive ones of the hash values in the sequence that have a common value and (iii) create a shortened hash chain by generating a pointer in the table at an intermediate location that corresponds to a second of the two consecutive hash values. The pointer generally points forward in the table to an end location that corresponds to a last of the data values in a run of the data values.
Claims20
An apparatus comprising:
- an interface configured to process a plurality of read/write operations to/from a memory;
- and
- a control circuit configured to generate each of a plurality of mapped values by mapping two or more data values at two or more consecutive positions in a run of data, store the plurality of mapped values in a local memory, find two or more consecutively located mapped values among the plurality of mapped values that have a common value, and set a forward pointer associated with an intermediate location in the local memory to point to an end location in the local memory that corresponds to an end of the run of data, wherein the intermediate location in the local memory stores a second of the two or more consecutively located mapped values that have the common value.
A method for creating a chain, comprising the steps of:
- generating each of a plurality of mapped values by mapping two or more data values at two or more consecutive positions in a run of data;
- storing the plurality of mapped values in a local memory;
- finding two or more consecutively located mapped values among the plurality of mapped values that have a common value;
- and
- setting a forward pointer associated with an intermediate location in the local memory to point to an end location in the local memory that corresponds to an end of the run of data, wherein the intermediate location in the local memory stores a second of the two or more consecutively located mapped values that have the common value.
An apparatus comprising:
- a memory configured to store data;
- and
- a controller configured to generate each of a plurality of mapped values by mapping two or more data values at two or more consecutive positions in a run of data, store the plurality of mapped values in a local memory, find two or more consecutively located mapped values among the plurality of mapped values that have a common value, and set a forward pointer associated with an intermediate location in the local memory to point to an end location in the local memory that corresponds to an end of the run of data, wherein the intermediate location in the local memory stores a second of the two or more consecutively located mapped values that have the common value.
Dependencies are inferred from the claim text.