Optimizing compression engine throughput via run pre-processing

• US 9,035,809 B2
• Filed: 10/15/2012
• Issued: 05/19/2015
• Est. Priority Date: 10/15/2012
• Status: Active Grant

• Current Assignee: Seagate Technology LLC (Seagate Technology Holdings Plc)
• Original Assignee: Seagate Technology LLC (Seagate Technology Holdings Plc)
• Inventors: Cohen, Earl T.
• Primary Examiner(s): JEAN PIERRE, PEGUY
• Application Number:
  US13/651,655
• Publication Number:
  US 20140104085A1
• Time in Patent Office: 946 Days
• Field of Search: 341/50, 341/51, 341/65, 341/67, 341/59, 341/87
• US Class Current: 341/87
• CPC Class Codes: H03M 7/3086 employing a sliding window, e.g. LZ77

Abstract

An apparatus includes a first circuit and a second circuit. The first circuit may be configured to generate a reduced representation of an input sequence of characters by replacing a repetition of a sequence of one or more characters by a code representing the repetition of the sequence of one or more characters. The second circuit may be configured to generate a compressed representation of the input sequence of characters in response to the reduced representation of the input sequence of characters. The second circuit is generally configured to recognize the code representing the repetition of the sequence of one or more characters and take into account the repetition of the sequence of one or more characters during a compression operation.

Claims

1. An apparatus comprising:

a first circuit configured to generate a reduced representation of an input sequence of characters by replacing a portion of the input sequence of characters containing a repetition of a sequence of one or more characters by a code representing the repetition of the sequence of one or more characters; and

a second circuit configured to generate a compressed representation of the input sequence of characters using the reduced representation wherein the second circuit (i) interprets the code replacing the portion of the input sequence of characters containing the repetition of the sequence of one or more characters as representing the portion of the input sequence of characters containing the repetition of the sequence of one or more characters, (ii) takes into account all or part of the portion of the input sequence of characters containing the repetition of the sequence of one or more characters represented by the code during search operations, and (iii) does not include the code from the reduced representation in the compressed representation of the input sequence of characters.

2. The apparatus according to claim 1, wherein the first circuit is configured to replace the repetition of the sequence of one or more characters by an encoding comprising one occurrence of the sequence of one or more characters and a corresponding length according to a number of the repetition.

3. The apparatus according to claim 2, wherein the second circuit is configured to perform a modified Lempel-Ziv (LZ) compression that processes each instance of the encoding in an amount of time that is independent of the corresponding length.

4. The apparatus according to claim 3, wherein the compressed representation of the input sequence of characters is compatible with an unmodified LZ decompression.

5. The apparatus according to claim 1, wherein the repetition of the sequence of one or more characters is a repetition of a single character and the number of the repetition is at least three.

6. The apparatus according to claim 1, wherein the repetition of the sequence of one or more characters is a repetition of a pair of characters and the number of the repetition is at least two.

7. The apparatus according to claim 1, wherein the first circuit is configured to perform a run length encoding.

8. The apparatus according to claim 1, wherein the second circuit is configured to perform a modified Lempel-Ziv (LZ) compression.

9. The apparatus according to claim 1, wherein the second circuit is configured to perform a modified LZ77 compression.

10. The apparatus according to claim 1, wherein the compressed representation of the input sequence of characters comprises literals and copy instructions generated by the second circuit, and at least one of the copy instructions references a number of characters less than all of one of the repetitions.

11. The apparatus according to claim 1, wherein the first circuit and the second circuit are part of a compression unit of a solid state disk (SSD).

12. The apparatus according to claim 1, wherein the second circuit comprises one or more compression engines.

13. The apparatus according to claim 1, wherein the second circuit comprises a plurality of compression engines arranged in parallel.

14. The apparatus according to claim 1, wherein the second circuit is further configured to generate a compressed bitstream that is a loss-less representation of the input sequence of characters.

15. The apparatus according to claim 1, wherein the first circuit is configured to reduce the input sequence of characters by replacing each repetition of a sequence of one or more characters by a hole and the second circuit is further configured to skip the hole during the search operations.

16. The apparatus according to claim 1, wherein:

the first circuit is further configured to generate a chain table indicating all occurrences of n-character strings in the input sequence, where n is a predetermined integer value; and

the second circuit uses the chain table during the search operations.

18. The apparatus according to claim 1, wherein the first circuit is configured to reduce the input sequence of characters by replacing each repetition of a sequence of one or more characters by (i) a flag bit indicating a run of repeated characters, (ii) one character providing the repeated character itself, and two characters encoding a length of the run.

17. A method of optimizing compression engine throughput comprising:

generating a reduced representation of an input sequence of characters by replacing a portion of the input sequence of characters containing a repetition of a sequence of one or more characters by a code representing the repetition of the sequence of one or more characters; and

generating a compressed representation of the input sequence of characters using the reduced representation, wherein (i) the code replacing the portion of the input sequence of characters containing the repetition of the sequence of one or more characters is interpreted as representing the portion of the input sequence of characters containing the repetition of the sequence of one or more characters, (ii) all or part of the portion of the input sequence of characters containing the repetition of the sequence of one or more characters represented by the code is taken into account during search operations, and the code from the reduced representation is not included in the compressed representation of the input sequence of characters.

19. An apparatus comprising:

a first circuit configured to generate a reduced representation of an input sequence of characters by replacing a portion of the input sequence of characters containing a repetition of a sequence of one or more characters by a code representing the repetition of the sequence of one or more characters; and

a second circuit configured to generate a compressed representation of the input sequence of characters in response to the reduced representation of the input sequence of characters, wherein

(i) the second circuit is configured to recognize the code replacing the repetition of the sequence of one or more characters as representing the portion of the input sequence of characters containing the repetition of the sequence of one or more characters and take into account all or part of the portion of the input sequence of characters containing the repetition of the sequence of one or more characters during a compression operation, and

(ii) the compressed representation of the input sequence of characters comprises literals and copy instructions generated by the second circuit, and at least one of the copy instructions references a number of characters less than all of one of the repetitions.

20. The apparatus according to claim 19, wherein the second circuit is further configured to generate a compressed bitstream that is a loss-less representation of the input sequence of characters.