Techniques to accelerate lossless compression

Patent metadata

Field	Value
Publication number	US-10158376-B2
Application number	US-201615053921-A
Country	US
Kind code	B2
Filing date	Feb 25, 2016
Priority date	Jun 29, 2012
Publication date	Dec 18, 2018
Grant date	Dec 18, 2018

Abstract

An embodiment may include circuitry that may be capable of performing compression-related operations that may include: (a) indicating, at least in part, in a data structure at least one position of at least one subset of characters that are to be encoded as a symbol, (b) comparing, at least in part, at least one pair of multi-byte data words that are of identical predetermined fixed size, (c) maintaining, at least in part, an array of pointers to potentially matching strings that are to be compared with at least one currently examined string, and/or (d) allocating, at least in part, a first buffer portion to store at least one portion of uncompressed data from an application buffer that is to be input for compression to produce a compressed data stream.

First claim

The invention claimed is:

1. An apparatus, comprising:
a memory to store multi-byte data words;
a circuitry for performing compression-related operations, the circuitry to:
receive a first pair of multi-byte data words of the multi-byte data words comprising a first multi-byte data word and a second multi-byte data word, the first multi-byte data word and the second multi-byte data word having an identical fixed size;
compare the first multi-byte data word and the second multi-byte data word based on an exclusive-or (XOR) operation; and
determine whether a result of the XOR operation indicates an occurrence of a mis-compare.

2. The apparatus of claim 1 , the circuitry to, in response to determining a mis-compare has occurred, determine a first location in one of the pair of multi-byte words at which the mis-compare occurs.

3. The apparatus of claim 2 , the circuitry to perform one or more bit search forward (BSF) instructions to determine the first location in one of the first pair of multi-byte words.

4. The apparatus of claim 1 , the circuitry to execute a single instruction to compare the first multi-byte data word and the second multi-byte data word based on the XOR operation.

5. The apparatus of claim 1 , the circuitry to:
receive a second pair of multi-byte data words comprising a third multi-byte data word and a fourth multi-byte data word, the third multi-byte data word and the fourth multi-byte data word having an identical fixed size;
compare the third multi-byte data word and the fourth multi-byte data word based on a second XOR operation; and
determine whether a result of the second XOR operation indicates an occurrence of a second mis-compare.

6. The apparatus of claim 5 , the circuitry to conduct the comparison of the first pair of multi-byte data words in parallel with the comparison of the second pair of multi-byte data words.

7. The apparatus of claim 5 , the circuitry to:
utilize a first thread to compare the first multi-byte data word and the second multi-byte data word; and
utilize a second thread to compare the third multi-byte data word and the fourth multi-byte data word.

8. The apparatus of claim 7 , comprising:
a host processor comprising the circuitry to utilize the first and second threads.

9. At least one non-transitory computer-readable storage medium comprising one or more instructions, that when executed, cause a circuitry to:
receive a first pair of multi-byte data words comprising a first multi-byte data word and a second multi-byte data word, the first multi-byte data word and the second multi-byte data word having an identical fixed size;
compare the first multi-byte data word and the second multi-byte data word based on an exclusive-or (XOR) operation; and
determine whether a result of the XOR operation indicates an occurrence of a mis-compare.

10. The at least one non-transitory computer-readable storage medium of claim 9 , comprising one or more instructions, that when executed, cause the circuitry to, in response to determining a mis-compare has occurred, determine a first location in one of the pair of multi-byte words at which the mis-compare occurs.

11. The at least one non-transitory computer-readable storage medium of claim 10 , comprising one or more instructions, that when executed, cause the circuitry to, perform one or more bit search forward (BSF) instructions to determine the first location in one of the first pair of multi-byte words.

12. The at least one non-transitory computer-readable storage medium of claim 9 , comprising one or more instructions, that when executed, cause the circuitry to execute a single instruction to compare the first multi-byte data word and the second multi-byte data word based on the XOR operation.

13. The at least one non-transitory computer-readable storage medium of claim 9 , comprising one or more instructions, that when executed, cause the circuitry to:
receive a second pair of multi-byte data words comprising a third multi-byte data word and a fourth multi-byte data word, the third multi-byte data word and the fourth multi-byte data word having an identical fixed size;
compare the third multi-byte data word and the fourth multi-byte data word based on a second XOR operation; and
determine when a second mis-compare occurs as a result of the second XOR operation.

14. The at least one non-transitory computer-readable storage medium of claim 13 , comprising one or more instructions, that when executed, cause the circuitry to conduct the comparison of the first pair of multi-byte data words in parallel with the comparison of the second pair of multi-byte data words.

15. The at least one non-transitory computer-readable storage medium of claim 13 , comprising one or more instructions, that when executed, cause the circuitry to:
utilize a first thread to compare the first multi-byte data word and the second multi-byte data word; and
utilize a second thread to compare the third multi-byte data word and the fourth multi-byte data word.

16. The at least one non-transitory computer-readable storage medium of claim 15 , comprising one or more instructions, that when executed, cause the circuitry to:
utilize the first thread on a first microprocessor of a host processor; and

utilize the second thread on a second microprocessor of the host processor.

17. A computer-implemented method, comprising:
receiving a first pair of multi-byte data words comprising a first multi-byte data word and a second multi-byte data word, the first multi-byte data word and the second multi-byte data word having an identical fixed size;
comparing the first multi-byte data word and the second multi-byte data word based on an exclusive-or (XOR) operation; and
determining whether a result of the XOR operation indicates an occurrence of a mis-compare.

18. The computer-implemented method of claim 17 , comprising, in response to determining a mis-compare has occurred, determining a first location in one of the pair of multi-byte words at which the mis-compare occurs.

19. The computer-implemented method of claim 18 , comprising performing one or more bit search forward (BSF) instructions to determine the first location in one of the first pair of multi-byte words.

20. The computer-implemented method of claim 17 , comprising executing a single instruction to compare the first multi-byte data word and the second multi-byte data word based on the XOR operation.

21. The computer-implemented method of claim 17 , comprising:
receiving a second pair of multi-byte data words comprising a third multi-byte data word and a fourth multi-byte data word, the third multi-byte data word and the fourth multi-byte data word having an identical fixed size;
comparing the third multi-byte data word and the fourth multi-byte data word based on a second XOR operation; and
determining whether a result of the second XOR operation indicates an occurrence of a second mis-compare.

22. The computer-implemented method of claim 21 , comprising conducting the comparison of the first pair of multi-byte data words in parallel with the comparison of the second pair of multi-byte data words.

23. The computer-implemented method of claim 21 , comprising:
utilizing a first thread to compare the first multi-byte data word and the second multi-byte data word; and
utilizing a second thread to compare the third multi-byte data word and the fourth multi-byte data word.

24. The computer-implem

Assignees

• Intel Corp

Inventors

• Guilford James D
• Gopal Vinodh
• Wolrich Gilbert M
• Ozturk Erdinc
• Feghali Wajdi K

Classifications

• G06F9/30029

  Logical and Boolean instructions, e.g. XOR, NOT · CPC title

• H03M7/60 Primary

  General implementation details not specific to a particular type of compression · CPC title

• H03M7/6058

  Saving memory space in the encoder or decoder · CPC title

• H03M7/3068 Primary

  Precoding preceding compression, e.g. Burrows-Wheeler transformation · CPC title