Features of range asymmetric number system encoding and decoding
AbstractInnovations in range asymmetric number system (“RANS”) coding and decoding are described herein. Some of the innovations relate to hardware implementations of RANS decoding that organize operations in two phases, which can improve the computational efficiency of RANS decoding. Other innovations relate to adapting RANS encoding/decoding for different distributions or patterns of values for symbols. For example, RANS encoding/decoding can adapt by switching a default symbol width (the number of bits per symbol), adjusting symbol width on a fragment-by-fragment basis for different fragments of symbols, switching between different static probability models on a fragment-by-fragment basis for different fragments of symbols, and/or selectively flushing (or retaining) the state of a RANS decoder on a fragment-by-fragment basis for different fragments of symbols. In many cases, such innovations can improve compression efficiency while also providing computationally efficient performance.
Claims:
1. A computer system comprising: an encoded data buffer configured to store encoded data for at least part of a bitstream; and
a range asymmetric number system (“RANS”) decoder configured to perform operations using a two-phase structure, the operations comprising: as part of a first phase of the two-phase structure, selectively updating state of the RANS decoder using probability information for an output symbol from a previous iteration, the state of the RANS decoder being tracked using a value;
as part of a second phase of the two-phase structure, selectively merging a portion of the encoded data from an input buffer into the state of the RANS decoder; and
as part of the second phase of the two-phase structure, selectively generating an output symbol for a current iteration using the state of the RANS decoder.
2. The computer system of claim 1, wherein the operations further comprise initializing the RANS decoder, wherein the initializing the RANS decoder includes: reading one or more syntax elements from a header for the at least part of the bitstream; and
configuring the RANS decoder based at least in part on the one or more syntax elements.
3. The computer system of claim 2, wherein the initializing the RANS decoder further includes: retrieving initial state information for the at least part of the bitstream; and
loading an initial state, as the state of the RANS decoder, based at least in part on initial state information.
4. The computer system of claim 2, wherein the one or more syntax elements include: a syntax element that indicates whether or not the state of the RANS decoder is to be flushed and re-initialized for decoding of the encoded data for the at least part of the bitstream;
a syntax element that indicates an adjustment to symbol width for the encoded data for the at least part of the bitstream; and/or
a syntax element that indicates a selection of a static probability model, for the encoded data for the at least part of the bitstream, from among multiple available static probability models.
5. The computer system of claim 1, wherein the output symbols are for residual data for media, wherein the first phase and the second phase are logical phases, wherein the first phase and the second phase are performed in different clock cycles or in the same clock cycle, and wherein the output symbols are from a single data stream or multiple different data streams.
6. The computer system of claim 1, wherein the selectively updating the state of the RANS decoder includes: determining whether the output symbol from the previous iteration was generated;
if so: determining the probability information for the output symbol from the previous iteration; and
adjusting the state of the RANS decoder using the probability information, thereby consuming at least some of the state of the RANS decoder; and
otherwise, skipping the adjusting the state of the RANS decoder.
7. The computer system of claim 6, wherein the determining the probability information for the output symbol from the previous iteration includes performing one or more lookup operations in one or more lookup tables.
8. The computer system of claim 6, wherein the probability information includes a sub-range size fwd_f for the output symbol from the previous iteration and a cumulative sub-range threshold fwd_cf for the output symbol from the previous iteration, and wherein the adjusting the state of the RANS decoder includes performing adjustments mathematically equivalent to:
x=fwd_f×x[upper]+x[lower]−fwd_cf,
wherein x represents the state of the RANS decoder after the adjusting, x[upper] represents an upper portion of the state of the RANS decoder before the adjusting, and x[lower] represents a lower portion of the state of the RANS decoder before the adjusting.
9. The computer system of claim 1, wherein the selectively merging the portion of the encoded data includes: determining whether the state of the RANS decoder satisfies a threshold;
if so, combining the portion of the encoded data and the state of the RANS decoder; and
otherwise, skipping the combining the portion of the encoded data and the state of the RANS decoder.
10. The computer system of claim 9, wherein the combining the portion of the encoded data and the state of the RANS decoder includes: shifting the state of the RANS decoder by a given number of bits; and
adding the portion of the encoded data, which has the given number of bits.
11. The computer system of claim 9, wherein the determining whether the state of the RANS decoder satisfies the threshold include comparing the state of the RANS decoder to the threshold, and wherein the state of the RANS decoder satisfies the threshold if the state of the RANS decoder is less than the threshold.
12. The computer system of claim 1, wherein the input buffer is configured to store one byte of the encoded data at a time, wherein the portion of the encoded data from the input buffer is one byte, and wherein the value that tracks the state of the RANS decoder is a 32-bit value.
13. The computer system of claim 1, wherein the probability information used to selectively update the state of the RANS decoder is forward probability information, and wherein the selectively generating the output symbol for the current iteration includes: determining whether the state of the RANS decoder includes sufficient information to generate the output symbol for the current iteration, the state of the RANS decoder including sufficient information to generate the output symbol for the current iteration if the state of the RANS decoder is greater than a threshold;
if so, determining inverse probability information and finding the output symbol for the current iteration using the inverse probability information and the state of the RANS decoder; and
otherwise, skipping the finding the output symbol for the current iteration.
14. The computer system of claim 13, wherein the determining the inverse probability information includes performing one or more lookup operations in one or more lookup tables.
15. The computer system of claim 13, wherein the finding the output symbol for the current iteration includes determining a sub-range of the state of the RANS decoder that is associated with the output symbol for the current iteration.
16. The computer system of claim 1, wherein the operations further comprise repeating the selectively updating, the selectively merging, and the selectively generating in successive iterations, until there are no more output symbols to decode in the encoded data for the at least part of the bitstream.
17. The computer system of claim 1, wherein the RANS decoder is implemented with special-purpose hardware including: the input buffer;
an output buffer configured to store the output symbol from the previous iteration, if any, until replacement with the output symbol for the current iteration, if any;
a state register configured to store the value that tracks the state of the RANS decoder;
logic, coupled to the output buffer and to the state register, configured to perform the selectively updating;
logic, coupled to the state register and the input buffer, configured to perform the selectively merging; and
logic, coupled to the state register and the output buffer, configured to perform the selectively generating.
18. The computer system of claim 1, wherein the operations further include, as part of the first phase: selectively re-filling the input buffer from the encoded data buffer; and/or
selectively writing the output symbol from the previous iteration to a symbol vector buffer.
19. In a computer system, a method comprising: receiving encoded data for at least part of a bitstream;
decoding the encoded data using a range asymmetric number system (“RANS”) decoder, including: as part of a first phase of a two-phase structure, selectively updating state of the RANS decoder using probability information for an output symbol from a previous iteration, the state of the RANS decoder being tracked using a value;
as part of a second phase of the two-phase structure, selectively merging a portion of the encoded data from an input buffer into the state of the RANS decoder; and
as part of the second phase of the two-phase structure, selectively generating an output symbol for a current iteration using the state of the RANS decoder.
20. One or more computer-readable media storing computer-executable instructions for causing one or more processors, when programmed thereby, to cause a range asymmetric number system (“RANS”) decoder to perform operations using a two-phase structure, the operations comprising: as part of a first phase of the two-phase structure, selectively updating state of the RANS decoder using probability information for an output symbol from a previous iteration, the state of the RANS decoder being tracked using a value;
as part of a second phase of the two-phase structure, selectively merging a portion of encoded data, for at least part of a bitstream, from an input buffer into the state of the RANS decoder; and
as part of the second phase of the two-phase structure, selectively generating an output symbol for a current iteration using the state of the RANS decoder.
21. The one or more computer-readable media of claim 20, wherein the operations further comprise initializing the RANS decoder, wherein the initializing the RANS decoder includes: reading one or more syntax elements from a header for the at least part of the bitstream; and
configuring the RANS decoder based at least in part on the one or more syntax elements.
22. The one or more computer-readable media of claim 20, wherein the selectively updating the state of the RANS decoder includes: determining whether the output symbol from the previous iteration was generated;
if so: determining the probability information for the output symbol from the previous iteration; and
adjusting the state of the RANS decoder using the probability information, thereby consuming at least some of the state of the RANS decoder; and
otherwise, skipping the adjusting the state of the RANS decoder.
23. The one or more computer-readable media of claim 20, wherein the selectively merging the portion of the encoded data includes: determining whether the state of the RANS decoder satisfies a threshold;
if so, combining the portion of the encoded data and the state of the RANS decoder; and
otherwise, skipping the combining the portion of the encoded data and the state of the RANS decoder.
24. The one or more computer-readable media of claim 20, wherein the probability information used to selectively update the state of the RANS decoder is forward probability information, and wherein the selectively generating the output symbol for the current iteration includes: determining whether the state of the RANS decoder includes sufficient information to generate the output symbol for the current iteration, the state of the RANS decoder including sufficient information to generate the output symbol for the current iteration if the state of the RANS decoder is greater than a threshold;
if so, determining inverse probability information and finding the output symbol for the current iteration using the inverse probability information and the state of the RANS decoder; and
otherwise, skipping the finding the output symbol for the current iteration.
25. The method of claim 19, further comprising initializing the RANS decoder, wherein the initializing the RANS decoder includes: reading one or more syntax elements from a header for the at least part of the bitstream; and
configuring the RANS decoder based at least in part on the one or more syntax elements.
26. The method of claim 19, wherein the selectively updating the state of the RANS decoder includes: determining whether the output symbol from the previous iteration was generated;
if so: determining the probability information for the output symbol from the previous iteration; and
adjusting the state of the RANS decoder using the probability information, thereby consuming at least some of the state of the RANS decoder; and
otherwise, skipping the adjusting the state of the RANS decoder.
27. The method of claim 19, wherein the selectively merging the portion of the encoded data includes: determining whether the state of the RANS decoder satisfies a threshold;
if so, combining the portion of the encoded data and the state of the RANS decoder; and
otherwise, skipping the combining the portion of the encoded data and the state of the RANS decoder.
28. The method of claim 19, wherein the probability information used to selectively update the state of the RANS decoder is forward probability information, and wherein the selectively generating the output symbol for the current iteration includes: determining whether the state of the RANS decoder includes sufficient information to generate the output symbol for the current iteration, the state of the RANS decoder including sufficient information to generate the output symbol for the current iteration if the state of the RANS decoder is greater than a threshold;
if so, determining inverse probability information and finding the output symbol for the current iteration using the inverse probability information and the state of the RANS decoder; and
otherwise, skipping the finding the output symbol for the current iteration.