Hardware friendly data compression
AssigneeNyquist Semiconductor Limited
InventorYuan-mao Chang
Life of this patent
Estimating the term…
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.
Claims20
A method, comprising:
- interleaving one or more literal length fields with one or more literal fields to an output, each of the one or more literal fields containing a part of a first data segment literally copied from an input stream of data to the output, and each of the one or more literal length fields containing a value representing a length of a succeeding literal field, the one or more literal length fields in combination containing a first total value representing a total length of the first data segment;
- determining a second data segment of the input stream of data 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 a value representing the match position, the one or more match length fields in combination containing a second total value representing a total length of the second data segment.
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;
- a hash calculator to generate a hash value for each of the one or more data snippets;
- a hash table to keep track of the one or more data snippets using their respective hash values;
- a match position searcher to search whether a data snippet has a match in already processed data based on entries in the hash table;
- a match position merger to merge two or more data snippets having found match in already processed data;
- and
- an output assembler configured to:
- interleave one or more literal length fields with one or more literal fields to an output, each of the one or more literal fields containing a part of a first data segment literally copied from the input stream of data to the output, and each of the one or more literal length fields containing a value representing a length of a succeeding literal field, the one or more literal length fields in combination containing a first total value representing a total length of the first data segment;
- determine a second data segment of the input stream of data being matched to a previously literally copied sequence of data and a match position;
- and
- write to the output one or more match length fields and a match position field containing a value representing the match position, the one or more match length fields in combination containing a second total value representing a total length of the second data segment.
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:
- interleave one or more literal length fields with one or more literal fields to an output, each of the one or more literal fields containing a part of a first data segment literally copied from an input stream of data to the output, and each of the one or more literal length fields containing a value representing a length of a succeeding literal field, the one or more literal length fields in combination containing a first total value representing a total length of the first data segment;
- determine a second data segment of the input stream of data being matched to a previously literally copied sequence of data and a match position;
- and
- write to the output one or more match length fields and a match position field containing a value representing the match position, the one or more match length fields in combination containing a second total value representing a total length of the second data segment.
Dependencies are inferred from the claim text.