System and method for long range and short range data compression

Abstract

A system and method are provided for use with streaming blocks of data, each of the streaming blocks of data including a number bits of data. The system includes a first compressor and a second compressor. The first compressor can receive and store a number n blocks of the streaming blocks of data, can receive and store a block of data to be compressed of the streaming blocks of data, can compress consecutive bits within the block of data to be compressed based on the n blocks of the streaming blocks of data, can output a match descriptor and a literal segment. The match descriptor is based on the compressed consecutive bits. The literal segment is based on a remainder of the number of bits of the data to be compressed not including the consecutive bits. The second compressor can compress the literal segment and can output a compressed data block including the match descriptor and a compressed string of data based on the compressed literal segment.

1 . A system for use with streaming blocks of data, each of the streaming blocks of data comprising a number of bits of data, said system comprising:
 a first compressor operable to receive and store a number n blocks of the streaming blocks of data, to receive and store a block of data to be compressed of the streaming blocks of data, to compress consecutive bits within the block of data to be compressed based on the n blocks of the streaming blocks of data, to output a match descriptor and a literal segment, the match descriptor being based on the compressed consecutive bits, the literal segment being based on a remainder of the number of bits of the data to be compressed not including the consecutive bits;   a second compressor operable to compress the literal segment and to output a compressed data block including the match descriptor and a compressed string of data based on the compressed literal segment.   
     
     
         2 . The system of  claim 1 , further comprising:
 a fingerprint hash computation portion; and   a cache;   wherein said first compressor comprises a fingerprint computation portion, a fingerprint matching portion and an output block forming portion,   wherein said fingerprint computation portion is operable to establish a first window of one of the number n blocks of the streaming blocks of data, to compute a first fingerprint based on a plurality of bits of data within the first window, to establish a second window of the block of data to be compressed and to compute a second fingerprint based on a plurality of bits of data within the second window,   wherein said cache is operable to store a first window literal segment of bits corresponding to the first window, and   wherein said fingerprint hash computation portion is operable to create a first hash index based on the first fingerprint and to create a second hash index based on the second fingerprint,   wherein said fingerprint matching portion is operable to determine whether the first fingerprint matches the second fingerprint based on the second hash index, and   wherein said output block forming portion is operable to output the literal segment when said fingerprint matching portion determines that the first fingerprint does not match the second fingerprint and to output the match descriptor when said fingerprint matching portion determines that the first fingerprint does match the second fingerprint.   
     
     
         3 . The system of  claim 2 , wherein said fingerprint matching portion is further operable to expand the first window across the n blocks of the streaming blocks of data, to expand the second window of the block of data to be compressed and to generate the match descriptor based on the expanded first window and the expanded second window. 
     
     
         4 . The system of  claim 2 ,
 wherein said cache comprises a contiguous circular buffer structure operable to store blocks in a first-in first-out manner,   wherein said cache is operable to store a block at the beginning of said contiguous circular buffer structure when the entire block cannot be contiguously inserted at the next insert position, and   wherein an amount of data that is usable in said contiguous circular buffer structure for finding matches against the block of data to be compressed is based on a position of a last valid byte at the end of said contiguous circular buffer structure.   
     
     
         5 . The system of  claim 1 , wherein said second compressor comprises;
 a parsing portion operable to parse a number of bits of the literal segment;   a grammar transform portion operable to assign a symbol to the parsed number of bits of the literal segment; and   an adaptive arithmetic coding portion operable to represent the parsed symbols using a minimum number of bits based on the frequency of occurrence of the symbols.   
     
     
         6 . The system of  claim 1 , wherein said second compressor is operable to provide a feedback signal to said first compressor to affect operation of said first compressor. 
     
     
         7 . A system for use with a number n blocks of streaming blocks of compressed data and a compressed block of data to be decompressed, the compressed block of data to be decompressed comprising a match descriptor and a compressed string of data, the compressed string of data being based on a literal segment of data, said system comprising:
 a first decompressor operable to decompress the compressed string as the literal segment of data and to output the match descriptor and the literal segment of data;   a second decompressor operable to operable to receive the match descriptor and the literal segment of data and to output decompressed data.   
     
     
         8 . The system of  claim 7 , further comprising:
 a cache having stored therein a string of bits associated with the match descriptor,   wherein said second decompressor comprises an output block forming portion and is further operable to receive the string of bits from said cache, and to output decompressed data including the first literal segment and associated string of bits,   wherein said cache is operable to store the decompressed data, and   wherein said output block forming portion is operable to output the decompressed data.   
     
     
         9 . The system of  claim 8 ,
 wherein said cache comprises a contiguous circular buffer structure operable to store blocks in a first-in first-out manner,   wherein said cache is operable to store a block at the beginning of said contiguous circular buffer structure when the entire block cannot be contiguously inserted at the next insert position, and   wherein an amount of data that is usable in said contiguous circular buffer structure for finding matches against the block of data to be compressed is based on a position of a last valid byte at the end of said contiguous circular buffer structure.   
     
     
         10 . The system of  claim 7 , wherein said first decompressor comprises;
 an adaptive arithmetic decoding portion operable to decode parsed symbols of the compressed block of data to be decompressed based on the frequency of occurrence of the symbols;   a grammar transform portion operable to update decompressor grammar based on the parsed symbol; and   an assembly portion operable to map the decoded symbols to decompressed data.   
     
     
         11 . A method of compressing streaming blocks of data, each of the streaming blocks of data comprising a number bits of data, said method comprising:
 receiving and storing, via a first compressor, a number n blocks of the streaming blocks of data;   receiving and storing, via the first compressor, a block of data to be compressed of the streaming blocks of data;   compressing, via the first compressor, consecutive bits within the block of data to be compressed based on the n blocks of the streaming blocks of data;   outputting, via the first compressor, a match descriptor and a literal segment, the match descriptor being based on the compressed consecutive bits, the literal segment being based on a remainder of the number of bits of the data to be compressed not including the consecutive bits;   compressing, via a second compressor, the literal segment; and   outputting, via the second compressor, a compressed data block including the match descriptor and a compressed string of data based on the compressed literal segment.   
     
     
         12 . The method of  claim 11 , further comprising:
 establishing, via a fingerprint computation portion within the first compressor, a first window of one of the number n blocks of the streaming blocks of data;   establishing, via the fingerprint computation portion, a second window of the block of data to be compressed;   computing, via the fingerprint computation portion, a second fingerprint based on a plurality of bits of data within the second window;   storing, via a cache, a first window literal segment of bits corresponding to the first window;   creating, via a fingerprint hash computation portion, a first hash index based on the first fingerprint;   creating, via the fingerprint hash computation portion, a second hash index based on the second fingerprint;   determining, via a fingerprint matching portion within the first compressor, whether the first fingerprint matches the second fingerprint based on the second hash index;   outputting, via an output block forming portion within the first compressor, the literal segment when the fingerprint matching portion determines that the first fingerprint does not match the second fingerprint; and   outputting, via the output block forming portion, the match descriptor when the fingerprint matching portion determines that the first fingerprint does match the second fingerprint.   
     
     
         13 . The method of  claim 12 , further comprising:
 expanding, via the fingerprint matching portion, the first window across the n blocks of the streaming blocks of data;   expanding, via the fingerprint matching portion, the second window of the block of data to be compressed; and   generating, via the fingerprint matching portion, the match descriptor based on the expanded first window and the expanded second window.   
     
     
         14 . The system of  claim 12 ,
 wherein said storing, via a cache, a first window literal segment of bits corresponding to the first window comprises storing blocks in a contiguous circular buffer structure in a first-in first-out manner,   wherein when the entire block cannot be contiguously inserted at the next insert position, the cache is operable to store a block at the beginning of the contiguous circular buffer structure, and   wherein an amount of data that is usable in the contiguous circular buffer structure for finding matches against the block of data to be compressed is based on a position of a last valid byte at the end of the contiguous circular buffer structure.   
     
     
         15 . The method of  claim 11 , further comprising:
 parsing, via a parsing portion within the second compressor, a number of bits of the literal segment;   assigning, via a grammar transform portion within the second compressor, a symbol to the parsed number of bits of the literal segment; and   representing, via an adaptive arithmetic coding portion within the second compressor, the parsed symbols using a minimum number of bits based on the frequency of occurrence of the symbols.   
     
     
         16 . The method of  claim 11 , further comprising providing, via the second compressor, a feedback signal to the first compressor to affect operation of the first compressor. 
     
     
         17 . A method of decompressing a number n blocks of streaming blocks of compressed data and a compressed block of data to be decompressed, the compressed block of data to be decompressed comprising a match descriptor and a compressed string of data, the compressed string of data being based on a literal segment of data, said method comprising:
 decompressing, via a first decompressor, the compressed string as the literal segment of data;   outputting, via the first decompressor, the match descriptor and the literal segment of data;   receiving, via a second decompressor, the match descriptor and the literal segment of data; and   outputting, via the second decompressor, decompressed data.   
     
     
         18 . The method of  claim 17 , further comprising:
 storing, via a cache, a string of bits associated with the match descriptor;   receiving, via the second decompressor, the string of bits from the cache;   outputting, via the second decompressor, decompressed data including the first literal segment and associated string of bits;   storing, via the cache, decompressed data; and   outputting, via and output block forming portion, the decompressed data.   
     
     
         19 . The method of  claim 18 ,
 wherein said storing, via a cache, a first window literal segment of bits corresponding to the first window comprises storing, via a contiguous circular buffer structure, blocks in a first-in first-out manner,   wherein the cache is operable to store a block at the beginning of the contiguous circular buffer structure when the entire block cannot be contiguously inserted at the next insert position, and   wherein an amount of data that is usable in the contiguous circular buffer structure for finding matches against the block of data to be compressed is based on a position of a last valid byte at the end of the contiguous circular buffer structure.   
     
     
         20 . The method of  claim 17 , further comprising:
 decoding, via an adaptive arithmetic decoding portion in the first decompressor, parsed symbols of the compressed block of data to be decompressed based on the frequency of occurrence of the symbols;   updating, via a grammar transform portion in the first decompressor, decompressor grammar based on the decoded parsed symbol; and   mapping, via an assembly portion in the first decompressor, the decoded symbols to decompressed data.