Method to shorten hash chains in Lempel-Ziv compression of data with repetitive symbols

1. An apparatus comprising:

a buffer configured to store a stream of data values having a run of three or more consecutive repeated data values;

a table configured to store a plurality of pointers and associated hash values; and

a circuit configured to (i) generate each of the hash values from two or more of the data values at two or more consecutive positions within the stream as stored in the buffer, (ii) find two or more of the hash values that have a common value and are consecutively located in the table, (iii) create a hash chain by setting the pointer at an intermediate location in the table to point forward to an end location in the table that corresponds to an end of the run, wherein the intermediate location stores a second of the two or more consecutively located hash values with the common value, and (iv) set the pointer at another location in the table that stores a fourth consecutive common value to point backward to the intermediate location in the table.

2. The apparatus according to claim 1 , further comprising a compressor configured to compress the data values in the run using the pointer at the intermediate location in the table to identify both (i) a starting location of the run and (ii) the end location of the run.

3. The apparatus according to claim 2 , wherein the compression comprises a Lempel-Ziv compression.

4. The apparatus according to claim 1 , wherein the circuit is further configured to set the pointer at an additional location in the table that corresponds to another run that hashes to the common value to point backward to the intermediate location in the table.

5. The apparatus according to claim 4 , wherein at least one of the hash values between the run and the another run is different than the common value.

6. The apparatus according to claim 1 , wherein the circuit is further configured to calculate the end location in the table as a predetermined offset from a last location in the table that stores a last of the hash values in the run that has the common value.

7. The apparatus according to claim 1 , wherein the intermediate location in the table stores the pointer and no more than one of the hash values.

8. The apparatus according to claim 1 , wherein the circuit is further configured to compare the run with another run by aligning the end location of the run with another end location of the another run.

9. The apparatus according to claim 1 , wherein the apparatus is implemented as one or more integrated circuits.

10. A method for creating a shortened hash chain, comprising the steps of:

storing in a buffer a stream of data values having a run of three or more consecutive repeated data values;

storing in a table a plurality of pointers and associated hash values;

generating each of the hash values from two or more of the data values at two or more consecutive positions within the stream as stored in the buffer;

finding two or more of the hash values that have a common value and are consecutively located in the table;

creating the hash chain by setting the pointer at an intermediate location in the table to point forward to an end location in the table that corresponds to an end of the run, wherein the intermediate location stores a second of the two or more consecutively located hash values with the common value; and

setting the pointer at another location in the table that stores a fourth consecutive common value to point backward to the intermediate location in the table.

11. The method according to claim 10 , further comprising the step of:

compressing the data values in the run using the pointer at the intermediate location in the table to identify both (i) a starting location of the run and (ii) the end location of the run.

12. The method according to claim 11 , wherein the compressing comprises a Lempel-Ziv compression.

13. The method according to claim 10 , further comprising the step of:

setting the pointer at an additional location in the table that corresponds to another run that hashes to the common value to point backward to the intermediate location in the table.

14. The method according to claim 13 , wherein at least one of the hash values between the run and the another run is different than the common value.

15. The method according to claim 10 , further comprising the step of:

calculating the end location in the table as a predetermined offset from a last location in the table that stores a last of the hash values in the run that has the common value.

16. The method according to claim 10 , wherein the intermediate location in the table stores the pointer and no more than one of the hash values.

17. The method according to claim 10 , further comprising the step of:

comparing the run with another run by aligning the end location of the run with another end location of the another run.

18. An apparatus comprising:

an interface configured to process a plurality of read/write operations to/from a nonvolatile memory;

and a circuit configured to (i) store in a buffer a stream of data values having a run of three or more consecutive repeated data values (ii) store in a table a plurality of pointers and associated hash values, (iii) generate each of the hash values from two or more of the data values at two or more consecutive positions within the stream as stored in the buffer, (iv) find two of more of the hash values that have a common value and are consecutively located in the table and (v) create a hash chain by setting the pointer at an intermediate location in the table to point forward to an end location in the table that corresponds to an end of the run, wherein the intermediate location stores a second of the two or more consecutively located hash values with the common value, and (vi) set the pointer at another location in the table that stores a fourth consecutive common value to point backward to the intermediate location in the table.