Evaluating Alternative Encoding Solutions During Data Compression

• US 20110102207A1
• Filed: 11/03/2009
• Published: 05/05/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: Sluiter, David Orrin, Matthews, Donald Preston JR.
• Granted Patent: US 8,013,762 B2
• Time in Patent Office: Days
• 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 input string of data bits arranged into fixed-sized chunks;

comparing multiple 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; 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 the previously received chunks are stored in a history buffer and the comparing step further comprises appending the multiple successive chunks to the history buffer at the conclusion of the single clock cycle.

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 matches obtained by the match module, 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, wherein the match module and the encoding module are realized as programming stored in a second memory and executed by a programmable controller.

17. The apparatus of claim 16, wherein the programmable controller is characterized as a multi-core processor comprising a plurality of processing cores, each core operating to respectively search for a different one of the n chunks in the memory.

18. The apparatus of claim 10, wherein the encoding logic separately generates a first encoding solution and a second encoding solution for the same bits in the input string, where the first encoding solution comprises an index and a first total number of bits, the second encoding solution comprises an index and a second total number of bits less than the first total number of bits, and the encoding module selects the second encoding solution.

19. The apparatus of claim 10, further comprising a multi-stage decompression engine comprising an input shift register which receives the compressed data string, a combinatorial logic stage which decodes a plurality of indexes and literals in said compressed data string during a single clock cycle, a second shift register which stores decoded values from the combinatorial logic into fixed size chunks, and a reconstruction module which performs memory look-ups for indexes and shifts bytes for literals to output the input string.

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