Dynamic history multistream long range compression
Dynamic history multistream long range compression (DHC) techniques are described for efficiently compressing multiple, prioritized data streams received over a channel. A history buffer is associated with each received stream and a DHC compressor dynamically allocates fixed sized history sections to and from each history buffer. In implementations, the DHC compressor makes stream history size adjustments prior to compressing a block of data and sends information identifying the change in history size to a DHC decompressor. The DHC decompressor sends signaling information to the DHC compressor that is used to ensure that the DHC decompressor can operate with a fixed amount of total history memory.
1. A method for compressing data blocks associated with a plurality of prioritized data streams, the method comprising:
receiving a data block associated with a first data stream of the plurality of prioritized data streams, wherein each of the plurality of prioritized data streams is associated with a history buffer comprising one or more allocated history sections;
determining if a history size increase is permitted for the history buffer of the first data stream based on a count of a number of history size increases previously granted to the plurality of prioritized data streams, wherein a history size increase is permitted for the history buffer of the first data stream if a predetermined maximum history size is greater than a difference between the count of the number of history size increases previously granted and a maximum of all history section decrease counts received from a decompressor; and
compressing the data block using a long range compressor associated with the first data stream.
2. The method of claim 1 , further comprising:
determining that a history size increase is permitted for the history buffer of the first data stream;
in response to determining that a history size increase is permitted, allocating an additional history section to the history buffer of the first data stream; and
inserting the allocated additional history section into the history buffer of the first data stream.
3. The method of claim 1 , further comprising: determining if a history size increase is desirable for the history buffer of the first data stream based on a determination of whether the received data block would fit in a most recently used history section of the history buffer of the first data stream.
4. A method for compressing data blocks associated with a plurality of prioritized data streams, the method comprising:
receiving a data block associated with a first data stream of the plurality of prioritized data streams, wherein each of the plurality of prioritized data streams is associated with a history buffer comprising one or more allocated history sections;
determining if a history size increase is permitted for the history buffer of the first data stream based on a count of a number of history size increases previously granted to the plurality of prioritized data streams;
compressing the data block using a long range compressor associated with the first data stream;
insert an allocated additional history section into the history buffer of the first data stream;
copying the compressed data block into the allocated additional history section of the history buffer;
tagging the compressed data block with a history size increase; and
transmitting the tagged compressed data block over a network.
5. The method of claim 4 , further comprising: compressing the data block using a short range compressor associated with the first data stream.
6. A method for compressing data blocks associated with a plurality of prioritized data streams, the method comprising:
receiving a data block associated with a first data stream of the plurality of prioritized data streams, wherein each of the plurality of prioritized data streams is associated with a history buffer comprising one or more allocated history sections;
determining if a history size increase is permitted for the history buffer of the first data stream based on a count of a number of history size increases previously granted to the plurality of prioritized data streams;
compressing the data block using a long range compressor associated with the first data stream;
determining if a history size decrease is desirable for a history buffer of any one of the plurality of prioritized data streams;
in response to determining that a history size decrease is desirable, determining which of the plurality of prioritized data streams are eligible for a reduction in history size; and
deallocating a history section from the history buffer of one of the plurality of prioritized data streams that are eligible for a reduction in history size.
7. The method of claim 6 , further comprising: after deallocating a history section, transmitting a history decrease signaling block to a decompressor before transmitting a subsequent compressed data block for the data stream with the history buffer that was deallocated a history section.
8. The method of claim 6 , wherein the determination of whether a history size decrease is desirable is made in response to a determination that a history size increase is desirable for the history buffer of the first data stream.
9. The method of claim 6 , wherein deallocating a history section from the history buffer of one of the plurality of prioritized data streams comprises:
selecting a stream among the plurality of prioritized data streams eligible for a reduction in history size that has a least recently compressed block of data; and
deallocating a least recently used history section from the history buffer of the selected stream.
10. A compressor for compressing data blocks associated with a plurality of prioritized data streams, the compressor comprising:
a processor; and
a non-transitory computer-readable operatively coupled to the processor, and having instructions stored therein that when executed by the processor cause the compressor to:
receive a data block associated with a first data stream of the plurality of prioritized data streams, wherein each of the plurality of prioritized data streams is associated with a history buffer comprising one or more allocated history sections;
determine if a history size increase is permitted for the history buffer of the first data stream based on a count of a number of history size increases previously granted to the plurality of prioritized data streams, wherein a history size increase is permitted for the history buffer of the first data stream if a predetermined maximum history size is greater than a difference between the count of the number of history size increases previously granted and a maximum of all history section decrease counts received from a decompressor; and
compress the data block using a long range compressor associated with the first data stream.
11. The compressor of claim 10 , wherein the instructions, when executed by the processor, further cause the compressor to:
determine that a history size increase is permitted for the history buffer of the first data stream;
in response to determining that a history size increase is permitted, allocating an additional history section to the history buffer of the first data stream; and
insert the allocated additional history section into the history buffer of the first data stream.
12. The compressor of claim 10 , wherein the instructions, when executed by the processor, further cause the compressor to: determine if a history size increase is desirable for the history buffer of the first data stream based on a determination of whether the received data block would fit in a most recently used history section of the history buffer of the first data stream.
13. A compressor for compressing data blocks associated with a plurality of prioritized data streams, the compressor comprising:
a processor; and
a non-transitory computer-readable operatively coupled to the processor, and having instructions stored therein that when executed by the processor cause the compressor to:
receive a data block associated with a first data stream of the plurality of prioritized data streams, wherein each of the plurality of prioritized data streams is associated with a history buffer comprising one or more allocated history sections;
determine if a history size increase is permitted for the history buffer of the first data stream based on a count of a number of history size increases previously granted to the plurality of prioritized data streams;
compress the data block using a long range compressor associated with the first data stream;
insert an allocated additional history section into the history buffer of the first data stream;
copy the compressed data block into the allocated additional history section of the history buffer;
tag the compressed data block with a history size increase; and
transmit the tagged compressed data block over a network.
14. The compressor of claim 13 , wherein the instructions, when executed by the processor, further cause the compressor to: compress the data block using a short range compressor associated with the first data stream.
15. A compressor for compressing data blocks associated with a plurality of prioritized data streams, the compressor comprising:
a processor; and
a non-transitory computer-readable operatively coupled to the processor, and having instructions stored therein that when executed by the processor cause the compressor to:
receive a data block associated with a first data stream of the plurality of prioritized data streams, wherein each of the plurality of prioritized data streams is associated with a history buffer comprising one or more allocated history sections;
determine if a history size increase is permitted for the history buffer of the first data stream based on a count of a number of history size increases previously granted to the plurality of prioritized data streams;
compress the data block using a long range compressor associated with the first data stream;
determine if a history size decrease is desirable for a history buffer of any one of the plurality of prioritized data streams;
in response to determining that a history size decrease is desirable, determine which of the plurality of prioritized data streams are eligible for a reduction in history size; and
deallocate a history section from the history buffer of one of the plurality of prioritized data streams that are eligible for a reduction in history size.
16. The compressor of claim 15 , wherein the instructions, when executed by the processor, further cause the compressor to: after deallocating a history section, transmit a history decrease signaling block to a decompressor before transmitting a subsequent compressed data block for the data stream with the history buffer that was deallocated a history section.
17. The compressor of claim 15 , wherein the determination of whether a history size decrease is desirable is made in response to a determination that a history size increase is desirable for the history buffer of the first data stream.
18. The compressor of claim 15 , wherein deallocating a history section from the history buffer of one of the plurality of prioritized data streams comprises:
selecting a stream among the plurality of prioritized data streams eligible for a reduction in history size that has a least recently compressed block of data; and
deallocating a least recently used history section from the history buffer of the selected stream.