Dynamic bitset coding

A method for decoding a bitset, each bit of the bitset corresponding to a respective value in a range of a minimum value to a maximum value, the method comprising:

• decoding, from a compressed bitstream, indexes of bits of the bitset, each bit of the bits having a first value, wherein decoding the indexes of the bits of the bitset comprises to:
• decoding, from the compressed bitstream, a number of the indexes of the bits of the bitset;
• decoding a first index of the indexes in a first range having a first lower bound and a first upper bound, wherein:
• the first lower bound is equal to the minimum value,
• the first upper bound is equal to the maximum value minus the number of the indexes of the bits of the bitset having the first value minus 1, and
• the first index corresponds to a first bit of the bitset having the first value;
• and
• decoding a last index of the indexes in a second range having a second lower bound and a second upper bound, wherein:
• the second lower bound is equal to the first index plus the number of the indexes minus one,
• the second upper bound is equal to the maximum value, and
• the last index corresponds to a last bit of the bitset having the first value;
• decrementing by one a number of remaining indexes after decoding an index from the compressed bitstream;
• and
• decoding, from the compressed bitstream, a next index immediately after decoding a previous index that was decoded immediately after decoding a next previous index, wherein decoding the next index comprises:
• setting a lower bound of a remaining range to the previous index plus the number of remaining indexes;
• setting an upper bound of the remaining range to the next previous index minus 1;
• and
• decoding, from the compressed bitstream, the next index in the remaining range;
• and
• setting all other bits of the bitset not decoded from the compressed bitstream to a second value.

A non-transitory computer-readable storage medium, comprising executable instructions that, when executed by a processor, facilitate performance of operations for decoding a bitset, each bit of the bitset corresponding to a respective value in a range of a minimum value to a maximum value, the operations comprising:

• decoding, from a compressed bitstream, indexes of bits of the bitset, each bit of the bits having a first value, wherein decoding the indexes of the bits of the bitset comprises to:
• decoding, from the compressed bitstream, a number of the indexes of the bits of the bitset;
• decoding a first index of the indexes in a first range having a first lower bound and a first upper bound, wherein:
• the first lower bound is equal to the minimum value,
• the first upper bound is equal to the maximum value minus the number of the indexes of the bits of the bitset having the first value minus 1, and
• the first index corresponds to a first bit of the bitset having the first value;
• and
• decoding a last index of the indexes in a second range having a second lower bound and a second upper bound, wherein:
• the second lower bound is equal to the first index plus the number of the indexes minus one,
• the second upper bound is equal to the maximum value, and
• the last index corresponds to a last bit of the bitset having the first value;
• decrementing by one a number of remaining indexes after decoding an index from the compressed bitstream;
• and
• decoding, from the compressed bitstream, a next index immediately after decoding a previous index that was decoded immediately after decoding a next previous index,
• wherein to decode the next index comprises to:
• setting a lower bound of a remaining range to the previous index plus the number of remaining indexes:
• setting an upper bound of the remaining range to the next previous index minus 1;
• and
• decoding, from the compressed bitstream, the next index in the remaining range;
• and
• setting all other bits of the bitset not decoded from the compressed bitstream to a second value.