Evaluating alternative encoding solutions during data compression

• US 8,013,762 B2
• Filed: 11/03/2009
• Issued: 09/06/2011
• Est. Priority Date: 11/03/2009
• Status: Active Grant

• Current Assignee: Seagate Technology LLC (Seagate Technology Holdings Plc)
• Original Assignee: Seagate Technology LLC (Seagate Technology Holdings Plc)
• Inventors: Matthews, Donald Preston Jr., Sluiter, David Orrin
• Primary Examiner(s): Nguyen; Khai M
• Application Number:
  US12/611,572
• Publication Number:
  US 20110102207A1
• Time in Patent Office: 672 Days
• Field of Search: 341/51, 341/87
• US Class Current: 341/51
• CPC Class Codes: H03M 7/3086 employing a sliding window, e.g. LZ77

Abstract

Method and apparatus for compressing data. In accordance with various embodiments, an input string of data bits is received and arranged into fixed-sized chunks. Multiple successive chunks of the input string are compared to previously received chunks of the input string during a single clock cycle. At least two alternative encoding solutions are identified based on matches obtained during said comparison. The input string is compressed to form a compressed output string using a selected one of the at least two alternative encoding solutions that achieves a fewer number of bits in said output string.

Claims

1. A method comprising:

receiving an uncompressed input string of data bits arranged into fixed-sized chunks;

comparing a multiple number of successive chunks of the input string to previously received chunks of the input string during a single clock cycle;

identifying at least two alternative encoding solutions based on matches obtained during the comparing step, each solution having a different number of indexes and a different number of literals; and

compressing the input string to form a compressed output string using a selected one of the at least two alternative encoding solutions that achieves a fewer number of bits in said output string.

2. The method of claim 1, wherein each of the at least two alternative encoding solutions of the identifying step comprises an index that encodes an associated address value and an associated length value based on a previous occurrence of a chunk in the input string, and wherein each of the at least two alternative encoding solutions encode the same set of data bits in the input string.

3. The method of claim 1, wherein at least one of the two alternative encoding solutions uses at least one literal to express the multiple number of successive chunks in a compressed form, and at least one other of the plurality of alternative encoding solutions does not use a literal to express the selected set of successive chunks in a compressed form.

4. The method of claim 1, wherein the comparing step further comprises comparing each selected one of the multiple successive chunks to each remaining one of the multiple successive chunks.

5. The method of claim 1, further comprising storing the previously received chunks in at least one associative memory and using match logic to concurrently search the previously received chunks in said at least one associative memory for matches with the multiple successive chunks.

6. The method of claim 1, wherein the multiple successive chunks of the comparing step constitute n chunks where n is greater than 1, and wherein the method further comprises concurrently storing duplicate copies of the previously received chunks in n associative memories and carrying out a concurrent search of each of the n chunks in a separate one of the n associated memories.

7. The method of claim 6, wherein the multiple successive chunks of the comparing step constitute n chunks where n is greater than 1, and wherein the method further comprises an n core processor with n processing cores with each processing core concurrently searching for matches of a selected one of the n chunks.

8. The method of claim 1, wherein each chunk constitutes an 8-bit byte of the input string of data bits.

9. The method of claim 1, further comprising decompressing the compressed output string.

10. An apparatus comprising:

a memory which stores previously received chunks of an input string of data bits;

a match module which compares multiple successive chunks of the input string to the previously received chunks during a single clock cycle; and

an encoding module which identifies at least two alternative encoding solutions based on different combinations of matches obtained by the match module for a common set of said chunks, and compresses the input string to form a compressed output string using a selected one of the at least two alternative encoding solutions that achieves a fewer number of bits in said output string.

11. The apparatus of claim 10, wherein the memory is an associative memory with match lines concurrently searchable by the match module, the memory storing a rolling history of the input string, and wherein the apparatus further comprises a write module which appends the multiple successive chunks to the rolling history.

12. The apparatus of claim 10, wherein the encoding module generates a match vector and a run length vector each having an overall depth equal to an overall depth of the memory.

13. The apparatus of claim 10, wherein each of the at least two alternative encoding solutions identified by the encoding module comprises an index that encodes an associated address value and an associated length value based on a previous occurrence of a chunk in the input string.

14. The apparatus of claim 10, wherein the match module further compares each selected one of the multiple successive chunks to each remaining one of the multiple successive chunks.

15. The apparatus of claim 10, wherein the multiple successive chunks constitute n chunks where n is greater than 1, and wherein the memory comprises n associative memories which store duplicate copies of the previously received chunks, and wherein the match module respectively searches each of the n associative memories for a different one of the n chunks.

16. The apparatus of claim 10, characterized as a solid state drive which stores the compressed output string to a page of non-volatile memory.

17. An apparatus comprising a data compression engine adapted to identify a plurality of alternative lossless data encoding solutions available to encode a selected set of successive chunks of uncompressed input data resident in a first memory, and to employ a selected one of said plurality of available encoding solutions to generate a compressed data set in a second memory, each solution having a different total number of indexes, each index having a starting address and a run length.

18. The apparatus of claim 17, in which the data compression engine is further adapted to calculate an overall total number of bits for each of said plurality of alternative encoding solutions, and to identify the selected one of said plurality that provides a fewer total number of bits in the compressed data set.

19. The apparatus of claim 17, in which at least one of the plurality of alternative encoding solutions includes at least one literal to express the selected set of successive chunks in a compressed form, and at least one other of the plurality of alternative encoding solutions provides a sequence that does not include a literal to express the selected set of successive chunks in a compressed form.

20. The apparatus of claim 17, in which the selected one of said plurality of alternate encoding solutions comprises an ongoing match run in the input data.