Techniques to accelerate lossless compression

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. Other embodiments are described and claimed.

1 . An apparatus, comprising:
 circuitry capable of performing compression-related operations that comprise at least one of the following subparagraphs (a) to (d):   (a) indicating in a data structure at least one position of a first subset of characters from a set of characters within one or more portions of an input data buffer, while a position of a second subset of characters remains unindicated in the data structure, the set of characters to be encoded as a symbol through compression encoding;   (b) comparing at least one pair of multi-byte data words of an identical fixed size based upon an exclusive-or (XOR) operation, and when a mis-compare occurs as a result of the at least one XOR operation, the comparing comprises determining a first location in one of the pair of multi-byte words at which the mis-compare occurs;   (c) maintaining an array of pointers to potentially matching strings to be compared by the circuitry with at least one currently examined string until a longest match in bytes is found between a potentially matching string and the at least one currently examined string; and   (d) allocating a first buffer portion to store one portion of uncompressed data from an application buffer that is input for compression to produce a compressed data stream, the one portion of uncompressed data having been most recently previously input for the compression, and a second buffer portion to store one other portion of the uncompressed data that is input for the compression, corresponding strings in the first buffer portion and the second buffer portion to be compared to determine presence of at least one reference to be used in generating the compressed data stream, the first buffer portion and the second buffer portion comprising a single buffer.   
     
     
         2 . The apparatus of  claim 1 , wherein:
 the set of characters comprises at least four bytes;   the first subset of characters comprises at most three respective bytes of a beginning portion of the characters; and   the second subset of characters comprises at least one respective byte that follows the beginning portion of the characters.   
     
     
         3 . The apparatus of  claim 1 , wherein:
 the determining of the first location comprises execution of at least one bit search forward instruction;   the at least one pair of multi-byte data words comprises a plurality of pairs of the multi-byte data words, at least two of the pairs to be compared in parallel by the circuitry; and   the circuitry comprises a processor, the comparing resulting from execution of a single instruction by the processor.   
     
     
         4 . The apparatus of  claim 1 , wherein a number of potentially matching strings is less than 9. 
     
     
         5 . The apparatus of  claim 1 , wherein the single buffer has a size capable of storage in a contiguous memory space of a level 1 processor cache. 
     
     
         6 . The apparatus of  claim 1 , wherein the compression-related operations also comprise performing a plurality of fixed-length comparisons involving all but a final portion of the uncompressed data from the application buffer, the final portion comprising a predetermined guard size supported by a compression-related standard, the final portion to be compared in a final variable-length comparison. 
     
     
         7 . The apparatus of  claim 1 , wherein:
 the circuitry is to perform one or more folding operations involving one or more subsets of the uncompressed data from the application buffer, the one or more folding operations to produce one or more fixed-length data blocks; and   the circuitry is to perform a single reduction involving a final fixed-length data block to produce a final cyclic redundancy check (CRC) value.   
     
     
         8 . The apparatus of  claim 1 , wherein:
 the compression-related operations result, at least in part, from execution of iterations of a main program loop;   the compressed data stream comprises respective variable-size tokens;   during each of the iterations, a respective subset of the tokens is accumulated in an accumulator; and   after each of the iterations, the respective subset is copied from the accumulator.   
     
     
         9 . Computer-readable memory storing one or more instructions that when executed by a machine results in circuitry performing operations comprising at least one of the following subparagraphs (a) to (d):
 (a) indicating, at least in part, in a data structure, at least one position of at least one subset of characters, the characters to be encoded as a symbol as a result of compression encoding, the at least one position being within one or more portions of an input data buffer, the at least one subset comprising less than an entirety of the characters, a respective position of a remaining portion of the characters being unindicated in the data structure, the remaining portion being other than the at least one subset of the characters;   (b) comparing, at least in part, at least one pair of multi-byte data words, each of the multi-byte words being of identical predetermined fixed size, the comparing being based at least in part upon at least one exclusive-or (XOR) operation involving the at least one pair of the two multi-byte data words, and if at least one mis-compare occurs as a result, at least in part, of the at least one XOR operation, the comparing comprises determining, at least in part, a first location in one of the two multi-byte words at which the at least one mis-compare occurs;   (c) maintaining, at least in part, an array of pointers to potentially matching strings, the potentially matching strings to be compared by the circuitry with at least one currently examined string until a longest match in bytes is found between a potentially matching string and the at least one currently examined string; and   (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, the at least one portion of the uncompressed data having been most recently previously input for the compression, a second buffer portion being to store at least one other portion of the uncompressed data that currently is being input for the compression, corresponding strings in the first buffer portion and the second buffer portion to be compared, at least in part, to determine presence of at least one reference to be used, at least in part, in generating the compressed data stream, the first buffer portion and the second buffer portion being comprised in a single buffer.   
     
     
         10 . The computer-readable memory of  claim 9 , wherein:
 the characters comprise at least four bytes;   the at least one subset comprises at most three respective bytes of a beginning portion of the characters; and   the remaining portion of the characters comprises at least one respective byte that follows the beginning portion of the characters.   
     
     
         11 . The computer-readable memory of  claim 9 , wherein:
 the determining, at least in part, of the first location comprises execution, at least in part, of at least one bit search forward instruction;   the at least one pair of multi-byte data words comprises a plurality of pairs of the multi-byte data words, at least two of the pairs to be compared in parallel, at least in part, by the circuitry; and   the circuitry comprises a processor, the comparing resulting from execution of a single instruction by the processor.   
     
     
         12 . The computer-readable memory of  claim 9 , wherein a number of potentially matching strings is less than 9. 
     
     
         13 . The computer-readable memory of  claim 9 , wherein the single buffer has a size that is chosen to permit the single buffer to be stored in a contiguous memory space in a level 1 processor cache. 
     
     
         14 . The computer-readable memory of  claim 9 , wherein the compression-related operations also comprise performing a plurality of fixed-length comparisons involving all but a final portion of the uncompressed data from the application buffer, the final portion comprising a predetermined guard size supported by a compression-related standard, the final portion to be compared in a final variable-length comparison. 
     
     
         15 . The computer-readable memory of  claim 9 , wherein:
 the circuitry is to perform one or more folding operations involving one or more subsets of the uncompressed data from the application buffer, the one or more folding operations being to produce one or more fixed-length data blocks; and   the circuitry is to perform a single reduction involving one or more fixed-length data blocks to produce final CRC value.   
     
     
         16 . The computer-readable memory of  claim 9 , wherein:
 the compression-related operations result, at least in part, from execution of iterations of a main program loop;   the compressed data stream comprises respective variable-size tokens;   during each of the iterations, a respective subset of the tokens is accumulated in an accumulator; and   after each of the iterations, the respective subset is copied from the accumulator.   
     
     
         17 . A method implemented, at least in part, using circuitry, the method comprising at least one of the following subparagraphs (a) to (d):
 (a) indicating in a data structure at least one position of a first subset of characters from a set of characters within one or more portions of an input data buffer, while a position of a second subset of characters remains unindicated in the data structure, the set of characters to be encoded as a symbol through compression encoding;   (b) comparing at least one pair of multi-byte data words of an identical fixed size based upon an exclusive-or (XOR) operation, and when a mis-compare occurs as a result of the at least one XOR operation, the comparing comprises determining a first location in one of the pair of multi-byte words at which the mis-compare occurs;   (c) maintaining an array of pointers to potentially matching strings to be compared by the circuitry with at least one currently examined string until a longest match in bytes is found between a potentially matching string and the at least one currently examined string; and   (d) allocating a first buffer portion to store one portion of uncompressed data from an application buffer that is input for compression to produce a compressed data stream, the one portion of uncompressed data having been most recently previously input for the compression, and a second buffer portion to store one other portion of the uncompressed data that is input for the compression, corresponding strings in the first buffer portion and the second buffer portion to be compared to determine presence of at least one reference to be used in generating the compressed data stream, the first buffer portion and the second buffer portion comprising a single buffer.   
     
     
         18 . The method of  claim 17 , wherein:
 the set of characters comprises at least four bytes;   the first subset of characters comprises at most three respective bytes of a beginning portion of the set of characters; and   the second subset of characters comprises at least one respective byte that follows the beginning portion of the characters.   
     
     
         19 . The method of  claim 17 , wherein:
 the determining of the first location comprises execution of at least one bit search forward instruction;   the pair of multi-byte data words comprises a plurality of pairs of the multi-byte data words, at least two of the pairs to be compared in parallel, at least in part, by the circuitry; and   the circuitry comprises a processor, the comparing resulting from execution of a single instruction by the processor.   
     
     
         20 . The method of  claim 17 , wherein a number of potentially matching strings is less than 9. 
     
     
         21 . The method of  claim 17 , wherein the single buffer has a size capable of storage in a contiguous memory space in a level 1 processor cache. 
     
     
         22 . The method of  claim 17 , wherein the compression-related operations also comprise performing a plurality of fixed-length comparisons involving all but a final portion of the uncompressed data from the application buffer, the final portion comprising a predetermined guard size supported by a compression-related standard, the final portion to be compared in a final variable-length comparison. 
     
     
         23 . The method of  claim 17 , wherein:
 the circuitry is to perform one or more folding operations involving one or more subsets of the uncompressed data from the application buffer, the one or more folding operations to produce one or more fixed-length data blocks; and   after all of the uncompressed data from the application buffer has been processed in producing the compressed data stream, the circuitry is to perform a single reduction involving the one or more fixed-length data blocks to produce a residue as a final cyclic redundancy check (CRC) value.   
     
     
         24 . The method of  claim 17 , wherein:
 the compression-related operations result, at least in part, from execution of iterations of a main program loop;   the compressed data stream comprises respective variable-size tokens;   during each of the iterations, a respective subset of the tokens is accumulated in an accumulator; and   after each of the iterations, the respective subset is copied from the accumulator.