Hardware friendly data compression

• US 10,587,285 B1
• Filed: 10/03/2019
• Issued: 03/10/2020
• Est. Priority Date: 12/06/2018
• Status: Active Grant

• Current Assignee: InnoGrit Technologies Co., Ltd.
• Original Assignee: Nyquist Semiconductor Limited
• Inventors: Chang, Yuan-mao
• Primary Examiner(s): Young, Brian K
• Application Number:
  US16/591,737
• Time in Patent Office: 159 Days
• Field of Search: 341 51, 341 67, 341106, 341107
• CPC Class Codes: G06F 16/2255 Hash tables
• CPC Class Codes: H03M 7/3086 employing a sliding window, e.g. LZ77
• CPC Class Codes: H03M 7/3088 employing the use of a dictionary, e.g. LZ78
• CPC Class Codes: H03M 7/48 alternating with other codes during the code conversion process, e.g. run-length coding being performed only as long as sufficientlylong runs of digits of the same kind are present
• CPC Class Codes: H03M 7/6005 Decoder aspects
• CPC Class Codes: H03M 7/6011 Encoder aspects

Abstract

Systems, apparatus and methods are provided for compressing data. An exemplary method may comprise interleaving one or more literal length fields with one or more literal fields to an output. The literal fields may contain a first data segment literally copied to the output, and each of the one or more literal length fields may contain a value representing a length of a succeeding literal field. The method may further comprise determining a second data segment being matched to a previously literally copied sequence of data and a match position and writing to the output one or more match length fields and a match position field containing the match position. The literal length fields may contain a total length of the first data segment and the match length fields may contain a total length of the second data segment.

Claims

1. A method, comprising:

packaging an input stream of data into a plurality of data snippets, each data snippet having a length of a minimum match length, with a first data snippet of the plurality of data snippets starting at a beginning data unit of the input stream of data and each data snippet after the first data snippet starting at a second data unit of a preceding data snippet;

determining whether each of the plurality of data snippets has a match in already processed data; and

outputting a stream of compressed data that begins with a literal segment, wherein the literal segment includes one or more literal length fields each followed by a respective succeeding literal field, each of the one or more literal length fields containing a value representing a length of the respective succeeding literal field, wherein the one or more literal fields in combination include data copied from one data snippet of the plurality of data snippets that has no match in the already processed data or from a series of data snippets in succession of the plurality of data snippets that have no match in the already processed data.

2. The method of claim 1, wherein the stream of compressed data further includes a matched segment that includes one or more match length fields and a match position field, and the match position field contains a value representing a match position.

3. The method of claim 2, further comprising obtaining the matched segment by merging two or more matched data snippets, wherein the match position is a position of a first matched data snippets of the two or more matched data snippets.

4. The method of claim 2, further comprising obtaining the matched segment by merging at least two matched data snippets separated by an index difference that is equal to a match position value difference, wherein the index difference is the minimum match length or less.

5. The method of claim 2, wherein the match position is an absolute index from a beginning of the input stream of data.

6. The method of claim 2, wherein the match position is an offset from a current position of a data snippet being processed.

7. The method of claim 1, further comprising calculating a hash value for each of the plurality of data snippets, wherein determining whether each of the plurality of data snippets has a match in the already processed data is based on respective hash values.

8. The method of claim 7, further comprising keeping track of hash values of the already processed data in a hash table.

9. The method of claim 8, wherein the hash table is a dictionary with the hash values as indices and each entry pointed to by an index stores a data snippet corresponding to a respective hash value and a position of the data snippet.

10. The method of claim 1, further comprising:

determining that there is a repeat pattern; and

generating one or more repeat length fields in the stream of compressed data.

11. The method of claim 1, wherein the data copied from the series of data snippets in succession of the plurality of data snippets that have no match in the already processed data does not repeat overlapping data sequence(s).

12. An apparatus, comprising:

an encoder comprising;

a data packager to generate one or more data snippets from an input stream of data, each of the one or more data snippets having a length of a minimum match length, with a first data snippet of the plurality of data snippets starting at a beginning data unit of the input stream of data and each data snippet after the first data snippet starting at a second data unit of a preceding data snippet;

a match position searcher to search whether a data snippet has a match in already processed data; and

an output assembler configured to output a stream of compressed data that begins with a literal segment, wherein the literal segment includes one or more literal length fields each followed by a respective succeeding literal field, each of the one or more literal length fields containing a value representing a length of the respective succeeding literal field, wherein the one or more literal fields in combination include data copied from one data snippet of the plurality of data snippets that has no match in the already processed data or from a series of data snippets in succession of the plurality of data snippets that have no match in the already processed data.

13. The apparatus of claim 12, wherein the stream of compressed data further includes a matched segment that includes one or more match length fields and a match position field, and the match position field contains a value representing a match position.

14. The apparatus of claim 13, wherein the match position is an absolute index from a beginning of the input stream of data.

15. The apparatus of claim 13, wherein the match position is an offset from a current position of a data snippet being processed.

16. The apparatus of claim 12, further comprising a hash calculator to generate a hash value for each of the one or more data snippets, wherein the match position searcher is configured to use the hash value for each of the one or more data snippets to search whether a data snippet has a match in the already processed data.

17. The apparatus of claim 16, further comprising a hash table to keep track of hash values of the already processed data.

18. The apparatus of claim 17, wherein the hash table is a dictionary with the hash values as indices and each entry pointed to by an index stores a data snippet corresponding to a respective hash value and a position of the data snippet.

19. A non-transitory machine-readable medium having executable instructions, wherein the executable instructions, when executed by a processor of a computer system, causes the computing system to:

package an input stream of data into a plurality of data snippets, each data snippet having a length of a minimum match length, with a first data snippet of the plurality of data snippets starting at a beginning data unit of the input stream of data and each data snippet after the first data snippet starting at a second data unit of a preceding data snippet;

determine whether each of the plurality of data snippets has a match in already processed data; and

output a stream of compressed data that begins with a literal segment, wherein the literal segment includes one or more literal length fields each followed by a respective succeeding literal field, each of the one or more literal length fields containing a value representing a length of the respective succeeding literal field, wherein the one or more literal fields in combination include data copied from one data snippet of the plurality of data snippets that has no match in the already processed data or from a series of data snippets in succession of the plurality of data snippets that have no match in the already processed data.

20. The non-transitory machine-readable medium of claim 19, wherein the executable instructions, when executed by the processor, further causes the computing system to:

include a matched segment in the stream of compressed data, wherein the matched segment includes one or more match length fields and a match position field, and the match position field contains a value representing a match position;

determine whether there is a repeat pattern; and

generate one or more repeat length fields.