Features of range asymmetric number system encoding and decoding

Abstract

Innovations 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.

1 .- 20 . (canceled) 
     
     
         21 . In a computer system, a method comprising:
 encoding input symbols using a range asymmetric number system (“RANS”) encoder, thereby generating encoded data for at least part of a bitstream, including:
 determining whether or not state of a RANS decoder is to be flushed/re-initialized for decoding of the encoded data for the at least part of the bitstream; 
 setting a syntax element that indicates whether or not the state of the RANS decoder is to be flushed/re-initialized for decoding of the encoded data for the at least part of the bitstream; and 
 performing RANS encoding; and 
   outputting the encoded data for the at least part of the bitstream, wherein a header in the at least part of the bitstream includes the syntax element that indicates whether or not the state of the RANS decoder is to be flushed/re-initialized for decoding of the encoded data for the at least part of the bitstream.   
     
     
         22 . The method of  claim 21 , wherein the syntax element indicates the state of the RANS decoder is to be flushed/re-initialized for decoding of the encoded data for the at least part of the bitstream, and wherein the encoding further includes determining initial state information for the encoded data for the at least part of the bitstream, the bitstream further including the initial state information for the encoded data for the at least part of the bitstream. 
     
     
         23 . The method of  claim 21 , wherein the syntax element indicates the state of the RANS decoder is not to be flushed/re-initialized for decoding of the encoded data for the at least part of the bitstream, and wherein the bitstream lacks initial state information for the encoded data for the at least part of the bitstream. 
     
     
         24 . The method of  claim 21 , further comprising repeating the encoding on a fragment-by-fragment basis for each of multiple fragments, each of the multiple fragments including its own header having a syntax element that indicates whether or not the state of the RANS decoder is to be flushed/re-initialized for decoding of encoded data for that fragment. 
     
     
         25 . The method of  claim 21 , wherein the determining whether or not the state of the RANS decoder is to be flushed/re-initialized for decoding of the encoded data for the at least part of the bitstream includes, for a fragment of the input symbols or an initial p input symbols of the fragment, evaluating compression efficiency with the state of the RANS decoder retained versus compression efficiency with the state of the RANS decoder flushed/re-initialized. 
     
     
         26 . The method of  claim 21 , wherein the encoding further includes:
 selecting a symbol width;   setting a syntax element that indicates the selected symbol width; and   configuring the RANS encoder to perform the RANS encoding at the selected symbol width, including selecting a set of pre-defined lookup tables having probability information for the selected symbol width.   
     
     
         27 . The method of  claim 21 , wherein the encoding further includes:
 selectively adjusting a default symbol width for the encoded data for the at least part of the bitstream;   setting a syntax element that indicates the selectively adjusted symbol width, the header in the at least part of the bitstream further including the syntax element that indicates the selectively adjusted symbol width; and   configuring the RANS encoder to perform the RANS encoding at the selectively adjusted symbol width, including selecting a set of pre-defined lookup tables having probability information for the selectively adjusted symbol width.   
     
     
         28 . The method of  claim 21 , wherein the encoding further includes:
 selecting a static probability model, for the encoded data for the at least part of the bitstream, from among multiple available static probability models;   setting a syntax element that indicates the selected static probability model, the header in the at least part of the bitstream further including the syntax element that indicates the selected static probability model; and   configuring the RANS encoder to perform the RANS encoding using the selected static probability model.   
     
     
         29 . The method of  claim 21 , further comprising storing the encoded data for the at least part of the bitstream on a computer-readable medium. 
     
     
         30 . A computer system comprising an encoded data buffer and a range asymmetric number system (“RANS”) decoder, the encoded data buffer being implemented in memory of the computer system, and the RANS decoder being implemented using one or more processors of the computer system, wherein:
 the encoded data buffer is configured to receive encoded data for at least part of a bitstream, wherein a header in the at least part of the bitstream includes a syntax element that indicates whether or not state of the RANS decoder is to be flushed/re-initialized for decoding of the encoded data for the at least part of the bitstream; and 
 the RANS decoder is configured to decode the encoded data for the at least part of the bitstream, thereby generating output symbols, by performing operations that include:
 reading the syntax element; 
 based at least in part on the syntax element, determining whether or not the state of the RANS decoder is to be flushed/re-initialized for decoding of the encoded data for the at least part of the bitstream; and 
 performing RANS decoding of the encoded data for the at least part of the bitstream. 
 
 
     
     
         31 . The computer system of  claim 30 , wherein the operations further include, when the syntax element indicates the state of the RANS decoder is to be flushed/re-initialized for decoding of the encoded data for the at least part of the bitstream:
 retrieving, from the bitstream, initial state information for the encoded data 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 the initial state information.   
     
     
         32 . The computer system of  claim 31 , wherein the initial state information is a 32-bit value. 
     
     
         33 . The computer system of  claim 30 , wherein the operations further include, when the syntax element indicates the state of the RANS decoder is to be flushed/re-initialized for decoding of the encoded data for the at least part of the bitstream:
 loading an initial state as the state of the RANS decoder.   
     
     
         34 . The computer system of  claim 30 , wherein, when the syntax element indicates the state of the RANS decoder is not to be flushed/re-initialized for decoding of the encoded data for the at least part of the bitstream, the operations further include:
 retaining the state of the RANS decoder.   
     
     
         35 . The computer system of  claim 30 , wherein the RANS decoder is configured to perform the operations on fragment-by-fragment basis for each of multiple fragments, each of the multiple fragments including its own header having a syntax element that indicates whether or not the state of the RANS decoder is to be flushed/re-initialized for decoding of encoded data for that fragment. 
     
     
         36 . The computer system of  claim 30 , wherein the performing the RANS decoding includes:
 as part of a first phase, selectively updating the state of the RANS decoder using probability information for an output symbol from a previous iteration;   as part of a second phase, selectively merging a portion of the encoded data for the at least part of the bitstream from the encoded data buffer into the state of the RANS decoder; and   as part of the second phase, selectively generating an output symbol for a current iteration using the state of the RANS decoder.   
     
     
         37 . The computer system of  claim 30 , wherein the operations further include:
 reading, from the header in the at least part of the bitstream, a syntax element that indicates a selection of a symbol width;   based on the syntax element that indicates the selection, selecting the symbol width; and   configuring the RANS decoder to perform the RANS decoding at the selected symbol width, including selecting a set of pre-defined lookup tables having probability information for output symbols of the selected symbol width.   
     
     
         38 . The computer system of  claim 30 , wherein the operations further include:
 reading, from the header in the at least part of the bitstream, a syntax element that indicates a selective adjustment of a default symbol width for the encoded data for the at least part of the bitstream;   based on the syntax element that indicates the selective adjustment, selectively adjusting the default symbol width for the encoded data for the at least part of the bitstream; and   configuring the RANS decoder to perform the RANS decoding at the selectively adjusted symbol width, including selecting a set of pre-defined lookup tables having probability information for output symbols of the selectively adjusted symbol width.   
     
     
         39 . The computer system of  claim 30 , wherein the operations further include:
 reading, from the header in the at least part of the bitstream, 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;   based on the syntax element that indicates the selection, selecting the static probability model for the encoded data for the at least part of the bitstream; and   configuring the RANS decoder to perform the RANS decoding using the selected static probability model.   
     
     
         40 . One or more computer-readable media having stored thereon encoded data for at least part of a bitstream, wherein a header in the at least part of the bitstream includes a syntax element that indicates whether or not state of a range asymmetric number system (“RANS”) decoder is to be flushed/re-initialized for decoding of the encoded data for the at least part of the bitstream, the encoded data for the at least part of the bitstream being organized to facilitate decoding by operations comprising:
 reading the syntax element; 
 based at least in part on the syntax element, determining whether or not the state of the RANS decoder is to be flushed/re-initialized for decoding of the encoded data for the at least part of the bitstream; and 
 performing RANS decoding of the encoded data for the at least part of the bitstream.