Data compression techniques using partitions and extraneous bit elimination

1. An encoding system, comprising:

a memory; and

a processor coupled to the memory and configured to:

receive partition information associated with one or more partitions in a sliding window;

receive an uncompressed value associated with a repeated sequence in the sliding window;

generate a compressed value that includes a set indicator and intra-set information using the uncompressed value, including by:

generating the set indicator based at least in part on the partition information and the uncompressed value;

determining, based at least in part on the partition information and the uncompressed value, whether the uncompressed value includes an extraneous bit; and

generating the intra-set information, including by: in the event it is determined that the uncompressed value includes the extraneous bit, excluding the extraneous bit in the uncompressed value from the intra-set information; and

output the compressed value that includes the set indicator and the intra-set information.

2. The encoding system of claim 1 , wherein:

a first partition in the sliding window is located at 2 w 1 ; and

in the event the uncompressed value is within a range of [2 w 1 , 2 (w 1 +1) −1]:

the uncompressed value is determined to include the extraneous bit; and

the extraneous bit in the uncompressed value that is excluded from the intra-set information includes a leading bit within the range of [2 w 1 , 2 (w 1 +1) −1].

3. The encoding system of claim 1 , wherein:

a first partition in the sliding window is located at 2 w 1 ;

a second partition in the sliding window is located at 2 w 2 ;

in the event the uncompressed value is within a range of [2 w 1 , 2 (w 1 +1) −1]:

the uncompressed value is determined to include the extraneous bit; and

the extraneous bit in the uncompressed value that is excluded from the intra-set information includes a leading bit within the range of [2 w 1 , 2 (w 1 +1) −1]; and

in the event the uncompressed value is within a range of [2 w 2 , 2 (w 2 +1) −1]:

the uncompressed value is determined to include the extraneous bit; and

the extraneous bit in the uncompressed value that is excluded from the intra-set information includes a leading bit within the range of [2 w 2 , 2 (w 2 +1) −1].

4. The encoding system of claim 1 , wherein the processor is further configured to:

receive uncompressed data;

identify a single run sequence, having a run length that is independent of the sliding window, within the uncompressed data;

generate a nominal offset and length pair for the single run sequence that includes a nominal offset that is set to the run length of the single run sequence and a length that is set to one; and

output the nominal offset and length pair for the single run sequence.

5. A method of encoding, comprising:

receiving partition information associated with one or more partitions in a sliding window;

receiving an uncompressed value associated with a repeated sequence in the sliding window;

generating a compressed value that includes a set indicator and intra-set information using the uncompressed value, including by:

generating the set indicator based at least in part on the partition information and the uncompressed value;

determining, based at least in part on the partition information and the uncompressed value, whether the uncompressed value includes an extraneous bit; and

generating the intra-set information, including by: in the event it is determined that the uncompressed value includes the extraneous bit, excluding the extraneous bit in the uncompressed value from the intra-set information; and

outputting the compressed value that includes the set indicator and the intra-set information.

6. The method of encoding of claim 5 , wherein:

a first partition in the sliding window is located at 2 w 1 ; and

in the event the uncompressed value is within a range of [2 w 1 , 2 (w 1 +1) −1]:

the uncompressed value is determined to include the extraneous bit; and

the extraneous bit in the uncompressed value that is excluded from the intra-set information includes a leading bit within the range of [2 w 1 , 2 (w 1 +1) −1].

7. The method of encoding of claim 5 , wherein:

a first partition in the sliding window is located at 2 w 1 ;

a second partition in the sliding window is located at 2 w 2 ;

in the event the uncompressed value is within a range of [2 w 1 , 2 (w 1 +1) −1]:

the uncompressed value is determined to include the extraneous bit; and

the extraneous bit in the uncompressed value that is excluded from the intra-set information includes a leading bit within the range of [2 w 1 , 2 (w 1 +1) −1]; and

in the event the uncompressed value is within a range of [2 w 2 , 2 (w 2 +1) −1]:

the uncompressed value is determined to include the extraneous bit; and

the extraneous bit in the uncompressed value that is excluded from the intra-set information includes a leading bit within the range of [2 w 2 , 2 (w 2 +1) −1].

8. The method of encoding of claim 5 , further comprising:

receiving uncompressed data;

identifying a single run sequence, having a run length that is independent of the sliding window, within the uncompressed data;

generating a nominal offset and length pair for the single run sequence that includes a nominal offset that is set to the run length of the single run sequence and a length that is set to one; and

outputting the nominal offset and length pair for the single run sequence.

9. A decoding system, comprising:

a memory; and

a processor coupled to the memory and configured to:

receive partition information associated with one or more partitions in a sliding window;

receive a compressed value that includes a set indicator and intra-set information;

generate an uncompressed value that is associated with a repeated sequence in the sliding window using the compressed value, including by:

determining, based at least in part on the set indicator and the intra-set information, whether an extraneous bit in the uncompressed value was excluded from the intra-set information during encoding; and

generating the uncompressed value, including by: in the event it is determined that the extraneous bit in the uncompressed value was excluded from the intra-set information during encoding, inserting a replacement bit into the intra-set information in order to obtain the uncompressed value; and

output the uncompressed value that is associated with the repeated sequence in the sliding window.

10. The decoding system of claim 9 , wherein:

a first partition in the sliding window is located at 2 w 1 ; and

generating the uncompressed value further includes:

determining which one of a plurality of sets is indicated by the set indicator; and

in the event (1) it is determined that the extraneous bit in the uncompressed value was excluded from the intra-set information during encoding and (2) it is determined that the set indicator indicates a first set, inserting the replacement bit includes adding 2 w 1 to the intra-set information.

11. The decoding system of claim 9 , wherein:

a first partition in the sliding window is located at 2 w 1 ;

a second partition in the sliding window is located at 2 w 2 ; and

generating the uncompressed value further includes:

determining which one of a plurality of sets is indicated by the set indicator;

in the event (1) it is determined that the extraneous bit in the uncompressed value was excluded from the intra-set information during encoding and (2) it is determined that the set indicator indicates a first set, inserting the replacement bit includes adding 2 w 1 to the intra-set information; and

in the event (1) it is determined that the extraneous bit in the uncompressed value was excluded from the intra-set information during encoding and (2) it is determined that the set indicator indicates a second set, inserting the replacement bit includes adding 2 w 2 to the intra-set information.

12. The decoding system of claim 9 , wherein:

a first partition in the sliding window is located at 2 w 1 ; and

generating the uncompressed value further includes:

determining which one of a plurality of sets is indicated by the set indicator; and

in the event it is determined that the set indicator indicates a first set, reading out w 1 bits corresponding to the intra-set information from a storage that stores at least the intra-set information.

13. The decoding system of claim 9 , wherein:

the sliding window has a size of 2 w ;

is a first partition in the sliding window is located at 2 w 1 ;

there are two sets in the sliding window; and

generating the uncompressed value further includes:

determining which one of a plurality of sets is indicated by the set indicator;

in the event it is determined that the set indicator indicates a first set, reading out w 1 bits corresponding to the intra-set information from a storage that stores at least the intra-set information; and

in the event it is determined that the set indicator indicates a second set and the intra-set information is less than or equal to 2 w 1 −1, reading out w−1 bits corresponding to the intra-set information from the memory.

14. The decoding system of claim 9 , wherein the processor is further configured to:

receive a nominal offset and length pair that includes a nominal offset that is set to a run length of a single run sequence and a length that is set to one;

in response to the length in the nominal offset and length pair equaling one, generate the single run sequence, including by repeating a preceding symbol using the run length and without accessing the sliding window; and

output uncompressed data that includes the single run sequence.

15. A method of decoding, comprising:

receiving partition information associated with one or more partitions in a sliding window;

receiving a compressed value that includes a set indicator and intra-set information;

generating an uncompressed value that is associated with a repeated sequence in the sliding window using the compressed value, including by:

determining, based at least in part on the set indicator and the intra-set information, whether an extraneous bit in the uncompressed value was excluded from the intra-set information during encoding; and

generating the uncompressed value, including by: in the event it is determined that the extraneous bit in the uncompressed value was excluded from the intra-set information during encoding, inserting a replacement bit into the intra-set information in order to obtain the uncompressed value; and

outputting the uncompressed value that is associated with the repeated sequence in the sliding window.

16. The method of decoding of claim 15 , wherein:

a first partition in the sliding window is located at 2 w 1 ; and

generating the uncompressed value further includes:

determining which one of a plurality of sets is indicated by the set indicator; and

in the event (1) it is determined that the extraneous bit in the uncompressed value was excluded from the intra-set information during encoding and (2) it is determined that the set indicator indicates a first set, inserting the replacement bit includes adding 2 w 1 to the intra-set information.

17. The method of decoding of claim 15 , wherein:

a first partition in the sliding window is located at 2 w 1 ;

a second partition in the sliding window is located at 2 w 2 ; and

generating the uncompressed value further includes:

determining which one of a plurality of sets is indicated by the set indicator;

in the event (1) it is determined that the extraneous bit in the uncompressed value was excluded from the intra-set information during encoding and (2) it is determined that the set indicator indicates a first set, inserting the replacement bit includes adding 2 w 1 to the intra-set information; and

in the event (1) it is determined that the extraneous bit in the uncompressed value was excluded from the intra-set information during encoding and (2) it is determined that the set indicator indicates a second set, inserting the replacement bit includes adding 2 w 2 to the intra-set information.

18. The method of decoding of claim 15 , wherein:

a first partition in the sliding window is located at 2 w 1 ; and

generating the uncompressed value further includes:

determining which one of a plurality of sets is indicated by the set indicator; and

in the event it is determined that the set indicator indicates a first set, reading out w 1 bits corresponding to the intra-set information from a storage that stores at least the intra-set information.

19. The method of decoding of claim 15 , wherein:

the sliding window has a size of 2 w ;

a first partition in the sliding window is located at 2 w 1 ;

there are two sets in the sliding window; and

generating the uncompressed value further includes:

determining which one of a plurality of sets is indicated by the set indicator;

in the event it is determined that the set indicator indicates a first set, reading out w 1 bits corresponding to the intra-set information from a storage that stores at least the intra-set information; and

in the event it is determined that the set indicator indicates a second set and the intra-set information is less than or equal to 2 w 1 −1, reading out w−1 bits corresponding to the intra-set information from the memory.

20. The method of decoding of claim 15 , further comprising:

receiving a nominal offset and length pair that includes a nominal offset that is set to a run length of a single run sequence and a length that is set to one;

in response to the length in the nominal offset and length pair equaling one, generating the single run sequence, including by repeating a preceding symbol using the run length and without accessing the sliding window; and

outputting uncompressed data that includes the single run sequence.