tech-invite   World Map     

IETF     RFCs     Groups     SIP     ABNFs    |    3GPP     Specs     Gloss.     Arch.     IMS     UICC    |    Misc.    |    search     info

RFC 6716


Definition of the Opus Audio Codec

Part 2 of 14, p. 13 to 31
Prev RFC Part       Next RFC Part


prevText      Top      Up      ToC       Page 13 
3.  Internal Framing

   The Opus encoder produces "packets", which are each a contiguous set
   of bytes meant to be transmitted as a single unit.  The packets
   described here do not include such things as IP, UDP, or RTP headers,
   which are normally found in a transport-layer packet.  A single
   packet may contain multiple audio frames, so long as they share a
   common set of parameters, including the operating mode, audio
   bandwidth, frame size, and channel count (mono vs. stereo).  This
   section describes the possible combinations of these parameters and
   the internal framing used to pack multiple frames into a single
   packet.  This framing is not self-delimiting.  Instead, it assumes
   that a lower layer (such as UDP or RTP [RFC3550] or Ogg [RFC3533] or
   Matroska [MATROSKA-WEBSITE]) will communicate the length, in bytes,
   of the packet, and it uses this information to reduce the framing
   overhead in the packet itself.  A decoder implementation MUST support
   the framing described in this section.  An alternative, self-
   delimiting variant of the framing is described in Appendix B.
   Support for that variant is OPTIONAL.

   All bit diagrams in this document number the bits so that bit 0 is
   the most significant bit of the first byte, and bit 7 is the least
   significant.  Bit 8 is thus the most significant bit of the second
   byte, etc.  Well-formed Opus packets obey certain requirements,
   marked [R1] through [R7] below.  These are summarized in Section 3.4
   along with appropriate means of handling malformed packets.

3.1.  The TOC Byte

   A well-formed Opus packet MUST contain at least one byte [R1].  This
   byte forms a table-of-contents (TOC) header that signals which of the
   various modes and configurations a given packet uses.  It is composed
   of a configuration number, "config", a stereo flag, "s", and a frame
   count code, "c", arranged as illustrated in Figure 1.  A description
   of each of these fields follows.

Top      Up      ToC       Page 14 
                              0 1 2 3 4 5 6 7
                             | config  |s| c |

                          Figure 1: The TOC Byte

   The top five bits of the TOC byte, labeled "config", encode one of 32
   possible configurations of operating mode, audio bandwidth, and frame
   size.  As described, the LP (SILK) layer and MDCT (CELT) layer can be
   combined in three possible operating modes:

   1.  A SILK-only mode for use in low bitrate connections with an audio
       bandwidth of WB or less,

   2.  A Hybrid (SILK+CELT) mode for SWB or FB speech at medium
       bitrates, and

   3.  A CELT-only mode for very low delay speech transmission as well
       as music transmission (NB to FB).

   The 32 possible configurations each identify which one of these
   operating modes the packet uses, as well as the audio bandwidth and
   the frame size.  Table 2 lists the parameters for each configuration.

Top      Up      ToC       Page 15 
   | Configuration         | Mode      | Bandwidth | Frame Sizes       |
   | Number(s)             |           |           |                   |
   | 0...3                 | SILK-only | NB        | 10, 20, 40, 60 ms |
   |                       |           |           |                   |
   | 4...7                 | SILK-only | MB        | 10, 20, 40, 60 ms |
   |                       |           |           |                   |
   | 8...11                | SILK-only | WB        | 10, 20, 40, 60 ms |
   |                       |           |           |                   |
   | 12...13               | Hybrid    | SWB       | 10, 20 ms         |
   |                       |           |           |                   |
   | 14...15               | Hybrid    | FB        | 10, 20 ms         |
   |                       |           |           |                   |
   | 16...19               | CELT-only | NB        | 2.5, 5, 10, 20 ms |
   |                       |           |           |                   |
   | 20...23               | CELT-only | WB        | 2.5, 5, 10, 20 ms |
   |                       |           |           |                   |
   | 24...27               | CELT-only | SWB       | 2.5, 5, 10, 20 ms |
   |                       |           |           |                   |
   | 28...31               | CELT-only | FB        | 2.5, 5, 10, 20 ms |

                Table 2: TOC Byte Configuration Parameters

   The configuration numbers in each range (e.g., 0...3 for NB SILK-
   only) correspond to the various choices of frame size, in the same
   order.  For example, configuration 0 has a 10 ms frame size and
   configuration 3 has a 60 ms frame size.

   One additional bit, labeled "s", signals mono vs. stereo, with 0
   indicating mono and 1 indicating stereo.

   The remaining two bits of the TOC byte, labeled "c", code the number
   of frames per packet (codes 0 to 3) as follows:

   o  0: 1 frame in the packet

   o  1: 2 frames in the packet, each with equal compressed size

   o  2: 2 frames in the packet, with different compressed sizes

   o  3: an arbitrary number of frames in the packet

   This document refers to a packet as a code 0 packet, code 1 packet,
   etc., based on the value of "c".

Top      Up      ToC       Page 16 
3.2.  Frame Packing

   This section describes how frames are packed according to each
   possible value of "c" in the TOC byte.

3.2.1.  Frame Length Coding

   When a packet contains multiple VBR frames (i.e., code 2 or 3), the
   compressed length of one or more of these frames is indicated with a
   one- or two-byte sequence, with the meaning of the first byte as

   o  0: No frame (Discontinuous Transmission (DTX) or lost packet)

   o  1...251: Length of the frame in bytes

   o  252...255: A second byte is needed.  The total length is

   The special length 0 indicates that no frame is available, either
   because it was dropped during transmission by some intermediary or
   because the encoder chose not to transmit it.  Any Opus frame in any
   mode MAY have a length of 0.

   The maximum representable length is 255*4+255=1275 bytes.  For 20 ms
   frames, this represents a bitrate of 510 kbit/s, which is
   approximately the highest useful rate for lossily compressed fullband
   stereo music.  Beyond this point, lossless codecs are more
   appropriate.  It is also roughly the maximum useful rate of the MDCT
   layer as, shortly thereafter, quality no longer improves with
   additional bits due to limitations on the codebook sizes.

   No length is transmitted for the last frame in a VBR packet, or for
   any of the frames in a CBR packet, as it can be inferred from the
   total size of the packet and the size of all other data in the
   packet.  However, the length of any individual frame MUST NOT exceed
   1275 bytes [R2] to allow for repacketization by gateways, conference
   bridges, or other software.

3.2.2.  Code 0: One Frame in the Packet

   For code 0 packets, the TOC byte is immediately followed by N-1 bytes
   of compressed data for a single frame (where N is the size of the
   packet), as illustrated in Figure 2.

Top      Up      ToC       Page 17 
      0                   1                   2                   3
      0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
     | config  |s|0|0|                                               |
     +-+-+-+-+-+-+-+-+                                               |
     |                    Compressed frame 1 (N-1 bytes)...          :
     :                                                               |
     |                                                               |

                         Figure 2: A Code 0 Packet

3.2.3.  Code 1: Two Frames in the Packet, Each with Equal Compressed

   For code 1 packets, the TOC byte is immediately followed by the
   (N-1)/2 bytes of compressed data for the first frame, followed by
   (N-1)/2 bytes of compressed data for the second frame, as illustrated
   in Figure 3.  The number of payload bytes available for compressed
   data, N-1, MUST be even for all code 1 packets [R3].

      0                   1                   2                   3
      0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
     | config  |s|0|1|                                               |
     +-+-+-+-+-+-+-+-+                                               :
     |             Compressed frame 1 ((N-1)/2 bytes)...             |
     :                               +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
     |                               |                               |
     +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+                               :
     |             Compressed frame 2 ((N-1)/2 bytes)...             |
     :                                               +-+-+-+-+-+-+-+-+
     |                                               |

                         Figure 3: A Code 1 Packet

3.2.4.  Code 2: Two Frames in the Packet, with Different Compressed

   For code 2 packets, the TOC byte is followed by a one- or two-byte
   sequence indicating the length of the first frame (marked N1 in
   Figure 4), followed by N1 bytes of compressed data for the first
   frame.  The remaining N-N1-2 or N-N1-3 bytes are the compressed data
   for the second frame.  This is illustrated in Figure 4.  A code 2
   packet MUST contain enough bytes to represent a valid length.  For
   example, a 1-byte code 2 packet is always invalid, and a 2-byte code
   2 packet whose second byte is in the range 252...255 is also invalid.

Top      Up      ToC       Page 18 
   The length of the first frame, N1, MUST also be no larger than the
   size of the payload remaining after decoding that length for all code
   2 packets [R4].  This makes, for example, a 2-byte code 2 packet with
   a second byte in the range 1...251 invalid as well (the only valid
   2-byte code 2 packet is one where the length of both frames is zero).

      0                   1                   2                   3
      0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
     | config  |s|1|0| N1 (1-2 bytes):                               |
     +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+                               :
     |               Compressed frame 1 (N1 bytes)...                |
     :                               +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
     |                               |                               |
     +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+                               |
     |                     Compressed frame 2...                     :
     :                                                               |
     |                                                               |

                         Figure 4: A Code 2 Packet

3.2.5.  Code 3: A Signaled Number of Frames in the Packet

   Code 3 packets signal the number of frames, as well as additional
   padding, called "Opus padding" to indicate that this padding is added
   at the Opus layer rather than at the transport layer.  Code 3 packets
   MUST have at least 2 bytes [R6,R7].  The TOC byte is followed by a
   byte encoding the number of frames in the packet in bits 2 to 7
   (marked "M" in Figure 5), with bit 1 indicating whether or not Opus
   padding is inserted (marked "p" in Figure 5), and bit 0 indicating
   VBR (marked "v" in Figure 5).  M MUST NOT be zero, and the audio
   duration contained within a packet MUST NOT exceed 120 ms [R5].  This
   limits the maximum frame count for any frame size to 48 (for 2.5 ms
   frames), with lower limits for longer frame sizes.  Figure 5
   illustrates the layout of the frame count byte.

                              0 1 2 3 4 5 6 7
                             |v|p|     M     |

                      Figure 5: The frame count byte

   When Opus padding is used, the number of bytes of padding is encoded
   in the bytes following the frame count byte.  Values from 0...254
   indicate that 0...254 bytes of padding are included, in addition to

Top      Up      ToC       Page 19 
   the byte(s) used to indicate the size of the padding.  If the value
   is 255, then the size of the additional padding is 254 bytes, plus
   the padding value encoded in the next byte.  There MUST be at least
   one more byte in the packet in this case [R6,R7].  The additional
   padding bytes appear at the end of the packet and MUST be set to zero
   by the encoder to avoid creating a covert channel.  The decoder MUST
   accept any value for the padding bytes, however.

   Although this encoding provides multiple ways to indicate a given
   number of padding bytes, each uses a different number of bytes to
   indicate the padding size and thus will increase the total packet
   size by a different amount.  For example, to add 255 bytes to a
   packet, set the padding bit, p, to 1, insert a single byte after the
   frame count byte with a value of 254, and append 254 padding bytes
   with the value zero to the end of the packet.  To add 256 bytes to a
   packet, set the padding bit to 1, insert two bytes after the frame
   count byte with the values 255 and 0, respectively, and append 254
   padding bytes with the value zero to the end of the packet.  By using
   the value 255 multiple times, it is possible to create a packet of
   any specific, desired size.  Let P be the number of header bytes used
   to indicate the padding size plus the number of padding bytes
   themselves (i.e., P is the total number of bytes added to the
   packet).  Then, P MUST be no more than N-2 [R6,R7].

   In the CBR case, let R=N-2-P be the number of bytes remaining in the
   packet after subtracting the (optional) padding.  Then, the
   compressed length of each frame in bytes is equal to R/M.  The value
   R MUST be a non-negative integer multiple of M [R6].  The compressed
   data for all M frames follows, each of size R/M bytes, as illustrated
   in Figure 6.

Top      Up      ToC       Page 20 
      0                   1                   2                   3
      0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
     | config  |s|1|1|0|p|     M     |  Padding length (Optional)    :
     |                                                               |
     :               Compressed frame 1 (R/M bytes)...               :
     |                                                               |
     |                                                               |
     :               Compressed frame 2 (R/M bytes)...               :
     |                                                               |
     |                                                               |
     :                              ...                              :
     |                                                               |
     |                                                               |
     :               Compressed frame M (R/M bytes)...               :
     |                                                               |
     :                  Opus Padding (Optional)...                   |

                       Figure 6: A CBR Code 3 Packet

   In the VBR case, the (optional) padding length is followed by M-1
   frame lengths (indicated by "N1" to "N[M-1]" in Figure 7), each
   encoded in a one- or two-byte sequence as described above.  The
   packet MUST contain enough data for the M-1 lengths after removing
   the (optional) padding, and the sum of these lengths MUST be no
   larger than the number of bytes remaining in the packet after
   decoding them [R7].  The compressed data for all M frames follows,
   each frame consisting of the indicated number of bytes, with the
   final frame consuming any remaining bytes before the final padding,
   as illustrated in Figure 6.  The number of header bytes (TOC byte,
   frame count byte, padding length bytes, and frame length bytes), plus
   the signaled length of the first M-1 frames themselves, plus the
   signaled length of the padding MUST be no larger than N, the total
   size of the packet.

Top      Up      ToC       Page 21 
      0                   1                   2                   3
      0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
     | config  |s|1|1|1|p|     M     | Padding length (Optional)     :
     : N1 (1-2 bytes): N2 (1-2 bytes):     ...       :     N[M-1]    |
     |                                                               |
     :               Compressed frame 1 (N1 bytes)...                :
     |                                                               |
     |                                                               |
     :               Compressed frame 2 (N2 bytes)...                :
     |                                                               |
     |                                                               |
     :                              ...                              :
     |                                                               |
     |                                                               |
     :                     Compressed frame M...                     :
     |                                                               |
     :                  Opus Padding (Optional)...                   |

                       Figure 7: A VBR Code 3 Packet

3.3.  Examples

   Simplest case, one NB mono 20 ms SILK frame:

    0                   1                   2                   3
    0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
   |    1    |0|0|0|               compressed data...              :

                                 Figure 8

Top      Up      ToC       Page 22 
   Two FB mono 5 ms CELT frames of the same compressed size:

    0                   1                   2                   3
    0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
   |   29    |0|0|1|               compressed data...              :

                                 Figure 9

   Two FB mono 20 ms Hybrid frames of different compressed size:

    0                   1                   2                   3
    0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
   |   15    |0|1|1|1|0|     2     |      N1       |               |
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+               |
   |                       compressed data...                      :

                                 Figure 10

   Four FB stereo 20 ms CELT frames of the same compressed size:

    0                   1                   2                   3
    0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
   |   31    |1|1|1|0|0|     4     |      compressed data...       :

                                 Figure 11

3.4.  Receiving Malformed Packets

   A receiver MUST NOT process packets that violate any of the rules
   above as normal Opus packets.  They are reserved for future
   applications, such as in-band headers (containing metadata, etc.).
   Packets that violate these constraints may cause implementations of
   _this_ specification to treat them as malformed and discard them.

   These constraints are summarized here for reference:

   [R1]  Packets are at least one byte.

   [R2]  No implicit frame length is larger than 1275 bytes.

   [R3]  Code 1 packets have an odd total length, N, so that (N-1)/2 is
         an integer.

Top      Up      ToC       Page 23 
   [R4]  Code 2 packets have enough bytes after the TOC for a valid
         frame length, and that length is no larger than the number of
         bytes remaining in the packet.

   [R5]  Code 3 packets contain at least one frame, but no more than
         120 ms of audio total.

   [R6]  The length of a CBR code 3 packet, N, is at least two bytes,
         the number of bytes added to indicate the padding size plus the
         trailing padding bytes themselves, P, is no more than N-2, and
         the frame count, M, satisfies the constraint that (N-2-P) is a
         non-negative integer multiple of M.

   [R7]  VBR code 3 packets are large enough to contain all the header
         bytes (TOC byte, frame count byte, any padding length bytes,
         and any frame length bytes), plus the length of the first M-1
         frames, plus any trailing padding bytes.

4.  Opus Decoder

   The Opus decoder consists of two main blocks: the SILK decoder and
   the CELT decoder.  At any given time, one or both of the SILK and
   CELT decoders may be active.  The output of the Opus decode is the
   sum of the outputs from the SILK and CELT decoders with proper sample
   rate conversion and delay compensation on the SILK side, and optional
   decimation (when decoding to sample rates less than 48 kHz) on the
   CELT side, as illustrated in the block diagram below.

                            +---------+    +------------+
                            |  SILK   |    |   Sample   |
                         +->| Decoder |--->|    Rate    |----+
   Bit-    +---------+   |  |         |    | Conversion |    v
   stream  |  Range  |---+  +---------+    +------------+  /---\  Audio
   ------->| Decoder |                                     | + |------>
           |         |---+  +---------+    +------------+  \---/
           +---------+   |  |  CELT   |    | Decimation |    ^
                         +->| Decoder |--->| (Optional) |----+
                            |         |    |            |
                            +---------+    +------------+

4.1.  Range Decoder

   Opus uses an entropy coder based on range coding [RANGE-CODING]
   [MARTIN79], which is itself a rediscovery of the FIFO arithmetic code
   introduced by [CODING-THESIS].  It is very similar to arithmetic
   encoding, except that encoding is done with digits in any base

Top      Up      ToC       Page 24 
   instead of with bits, so it is faster when using larger bases (i.e.,
   a byte).  All of the calculations in the range coder must use bit-
   exact integer arithmetic.

   Symbols may also be coded as "raw bits" packed directly into the
   bitstream, bypassing the range coder.  These are packed backwards
   starting at the end of the frame, as illustrated in Figure 12.  This
   reduces complexity and makes the stream more resilient to bit errors,
   as corruption in the raw bits will not desynchronize the decoding
   process, unlike corruption in the input to the range decoder.  Raw
   bits are only used in the CELT layer.

      0                   1                   2                   3
      0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
     | Range coder data (packed MSB to LSB) ->                       :
     +                                                               +
     :                                                               :
     +     +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
     :     | <- Boundary occurs at an arbitrary bit position         :
     +-+-+-+                                                         +
     :                          <- Raw bits data (packed LSB to MSB) |


     LSB = Least Significant Bit
     MSB = Most Significant Bit

          Figure 12: Illustrative Example of Packing Range Coder
                             and Raw Bits Data

   Each symbol coded by the range coder is drawn from a finite alphabet
   and coded in a separate "context", which describes the size of the
   alphabet and the relative frequency of each symbol in that alphabet.

   Suppose there is a context with n symbols, identified with an index
   that ranges from 0 to n-1.  The parameters needed to encode or decode
   symbol k in this context are represented by a three-tuple
   (fl[k], fh[k], ft), all 16-bit unsigned integers, with
   0 <= fl[k] < fh[k] <= ft <= 65535.  The values of this tuple are
   derived from the probability model for the symbol, represented by
   traditional "frequency counts".  Because Opus uses static contexts,
   those are not updated as symbols are decoded.  Let f[i] be the
   frequency of symbol i.  Then, the three-tuple corresponding to symbol
   k is given by the following:

Top      Up      ToC       Page 25 
                   k-1                                   n-1
                   __                                    __
           fl[k] = \  f[i],  fh[k] = fl[k] + f[k],  ft = \  f[i]
                   /_                                    /_
                   i=0                                   i=0

   The range decoder extracts the symbols and integers encoded using the
   range encoder in Section 5.1.  The range decoder maintains an
   internal state vector composed of the two-tuple (val, rng), where val
   represents the difference between the high end of the current range
   and the actual coded value, minus one, and rng represents the size of
   the current range.  Both val and rng are 32-bit unsigned integer

4.1.1.  Range Decoder Initialization

   Let b0 be an 8-bit unsigned integer containing first input byte (or
   containing zero if there are no bytes in this Opus frame).  The
   decoder initializes rng to 128 and initializes val to (127 -
    (b0>>1)), where (b0>>1) is the top 7 bits of the first input byte.
   It saves the remaining bit, (b0&1), for use in the renormalization
   procedure described in Section, which the decoder invokes
   immediately after initialization to read additional bits and
   establish the invariant that rng > 2**23.

4.1.2.  Decoding Symbols

   Decoding a symbol is a two-step process.  The first step determines a
   16-bit unsigned value fs, which lies within the range of some symbol
   in the current context.  The second step updates the range decoder
   state with the three-tuple (fl[k], fh[k], ft) corresponding to that

   The first step is implemented by ec_decode() (entdec.c), which

                       fs = ft - min(------ + 1, ft)

   The divisions here are integer division.

   The decoder then identifies the symbol in the current context
   corresponding to fs; i.e., the value of k whose three-tuple
   (fl[k], fh[k], ft) satisfies fl[k] <= fs < fh[k].  It uses this tuple
   to update val according to

Top      Up      ToC       Page 26 
                       val = val - --- * (ft - fh[k])

   If fl[k] is greater than zero, then the decoder updates rng using

                        rng = --- * (fh[k] - fl[k])

   Otherwise, it updates rng using

                       rng = rng - --- * (ft - fh[k])

   Using a special case for the first symbol (rather than the last
   symbol, as is commonly done in other arithmetic coders) ensures that
   all the truncation error from the finite precision arithmetic
   accumulates in symbol 0.  This makes the cost of coding a 0 slightly
   smaller, on average, than its estimated probability indicates and
   makes the cost of coding any other symbol slightly larger.  When
   contexts are designed so that 0 is the most probable symbol, which is
   often the case, this strategy minimizes the inefficiency introduced
   by the finite precision.  It also makes some of the special-case
   decoding routines in Section 4.1.3 particularly simple.

   After the updates, implemented by ec_dec_update() (entdec.c), the
   decoder normalizes the range using the procedure in the next section,
   and returns the index k.  Renormalization

   To normalize the range, the decoder repeats the following process,
   implemented by ec_dec_normalize() (entdec.c), until rng > 2**23.  If
   rng is already greater than 2**23, the entire process is skipped.
   First, it sets rng to (rng<<8).  Then, it reads the next byte of the
   Opus frame and forms an 8-bit value sym, using the leftover bit
   buffered from the previous byte as the high bit and the top 7 bits of
   the byte just read as the other 7 bits of sym.  The remaining bit in
   the byte just read is buffered for use in the next iteration.  If no
   more input bytes remain, it uses zero bits instead.  See
   Section 4.1.1 for the initialization used to process the first byte.
   Then, it sets

                 val = ((val<<8) + (255-sym)) & 0x7FFFFFFF

Top      Up      ToC       Page 27 
   It is normal and expected that the range decoder will read several
   bytes into the data of the raw bits (if any) at the end of the frame
   by the time the frame is completely decoded, as illustrated in
   Figure 13.  This same data MUST also be returned as raw bits when
   requested.  The encoder is expected to terminate the stream in such a
   way that the range decoder will decode the intended values regardless
   of the data contained in the raw bits.  Section 5.1.5 describes a
   procedure for doing this.  If the range decoder consumes all of the
   bytes belonging to the current frame, it MUST continue to use zero
   when any further input bytes are required, even if there is
   additional data in the current packet from padding or other frames.

      n              n+1             n+2             n+3
      0 1 2 3 4 5 6 7 0 1 2 3 4 5 6 7 0 1 2 3 4 5 6 7 0 1 2 3 4 5 6 7
     :     | <----------- Overlap region ------------> |             :
           ^                                           ^
           |   End of data buffered by the range coder |
           | End of data consumed by raw bits

          Figure 13: Illustrative Example of Raw Bits Overlapping
                             Range Coder Data

4.1.3.  Alternate Decoding Methods

   The reference implementation uses three additional decoding methods
   that are exactly equivalent to the above but make assumptions and
   simplifications that allow for a more efficient implementation.  ec_decode_bin()

   The first is ec_decode_bin() (entdec.c), defined using the parameter
   ftb instead of ft.  It is mathematically equivalent to calling
   ec_decode() with ft = (1<<ftb), but it avoids one of the divisions.  ec_dec_bit_logp()

   The next is ec_dec_bit_logp() (entdec.c), which decodes a single
   binary symbol, replacing both the ec_decode() and ec_dec_update()
   steps.  The context is described by a single parameter, logp, which
   is the absolute value of the base-2 logarithm of the probability of a
   "1".  It is mathematically equivalent to calling ec_decode() with
   ft = (1<<logp), followed by ec_dec_update() with the 3-tuple
   (fl[k] = 0, fh[k] = (1<<logp) - 1, ft = (1<<logp)) if the returned

Top      Up      ToC       Page 28 
   value of fs is less than (1<<logp) - 1 (a "0" was decoded), and with
   (fl[k] = (1<<logp) - 1, fh[k] = ft = (1<<logp)) otherwise (a "1" was
   decoded).  The implementation requires no multiplications or
   divisions.  ec_dec_icdf()

   The last is ec_dec_icdf() (entdec.c), which decodes a single symbol
   with a table-based context of up to 8 bits, also replacing both the
   ec_decode() and ec_dec_update() steps, as well as the search for the
   decoded symbol in between.  The context is described by two
   parameters, an icdf ("inverse" cumulative distribution function)
   table and ftb.  As with ec_decode_bin(), (1<<ftb) is equivalent to
   ft. idcf[k], on the other hand, stores (1<<ftb)-fh[k], which is equal
   to (1<<ftb) - fl[k+1]. fl[0] is assumed to be 0, and the table is
   terminated by a value of 0 (where fh[k] == ft).

   The function is mathematically equivalent to calling ec_decode() with
   ft = (1<<ftb), using the returned value fs to search the table for
   the first entry where fs < (1<<ftb)-icdf[k], and calling
   ec_dec_update() with fl[k] = (1<<ftb) - icdf[k-1] (or 0 if k == 0),
   fh[k] = (1<<ftb) - idcf[k], and ft = (1<<ftb).  Combining the search
   with the update allows the division to be replaced by a series of
   multiplications (which are usually much cheaper), and using an
   inverse CDF allows the use of an ftb as large as 8 in an 8-bit table
   without any special cases.  This is the primary interface with the
   range decoder in the SILK layer, though it is used in a few places in
   the CELT layer as well.

   Although icdf[k] is more convenient for the code, the frequency
   counts, f[k], are a more natural representation of the probability
   distribution function (PDF) for a given symbol.  Therefore, this
   document lists the latter, not the former, when describing the
   context in which a symbol is coded as a list, e.g., {4, 4, 4, 4}/16
   for a uniform context with four possible values and ft = 16.  The
   value of ft after the slash is always the sum of the entries in the
   PDF, but is included for convenience.  Contexts with identical
   probabilities, f[k]/ft, but different values of ft (or equivalently,
   ftb) are not the same, and cannot, in general, be used in place of
   one another.  An icdf table is also not capable of representing a PDF
   where the first symbol has 0 probability.  In such contexts,
   ec_dec_icdf() can decode the symbol by using a table that drops the
   entries for any initial zero-probability values and by adding the
   constant offset of the first value with a non-zero probability to its
   return value.

Top      Up      ToC       Page 29 
4.1.4.  Decoding Raw Bits

   The raw bits used by the CELT layer are packed at the end of the
   frame, with the least significant bit of the first value packed in
   the least significant bit of the last byte, filling up to the most
   significant bit in the last byte, continuing on to the least
   significant bit of the penultimate byte, and so on.  The reference
   implementation reads them using ec_dec_bits() (entdec.c).  Because
   the range decoder must read several bytes ahead in the stream, as
   described in Section, the input consumed by the raw bits may
   overlap with the input consumed by the range coder, and a decoder
   MUST allow this.  The format should render it impossible to attempt
   to read more raw bits than there are actual bits in the frame, though
   a decoder may wish to check for this and report an error.

4.1.5.  Decoding Uniformly Distributed Integers

   The function ec_dec_uint() (entdec.c) decodes one of ft equiprobable
   values in the range 0 to (ft - 1), inclusive, each with a frequency
   of 1, where ft may be as large as (2**32 - 1).  Because ec_decode()
   is limited to a total frequency of (2**16 - 1), it splits up the
   value into a range coded symbol representing up to 8 of the high
   bits, and, if necessary, raw bits representing the remainder of the
   value.  The limit of 8 bits in the range coded symbol is a trade-off
   between implementation complexity, modeling error (since the symbols
   no longer truly have equal coding cost), and rounding error
   introduced by the range coder itself (which gets larger as more bits
   are included).  Using raw bits reduces the maximum number of
   divisions required in the worst case, but means that it may be
   possible to decode a value outside the range 0 to (ft - 1),

   ec_dec_uint() takes a single, positive parameter, ft, which is not
   necessarily a power of two, and returns an integer, t, whose value
   lies between 0 and (ft - 1), inclusive.  Let ftb = ilog(ft - 1),
   i.e., the number of bits required to store (ft - 1) in two's
   complement notation.  If ftb is 8 or less, then t is decoded with
   t = ec_decode(ft), and the range coder state is updated using the
   three-tuple (t, t + 1, ft).

   If ftb is greater than 8, then the top 8 bits of t are decoded using

                 t = ec_decode(((ft - 1) >> (ftb - 8)) + 1)

   the decoder state is updated using the three-tuple (t, t + 1, ((ft -
    1) >> (ftb - 8)) + 1), and the remaining bits are decoded as raw
   bits, setting

Top      Up      ToC       Page 30 
                t = (t << (ftb - 8)) | ec_dec_bits(ftb - 8)

   If, at this point, t >= ft, then the current frame is corrupt.  In
   that case, the decoder should assume there has been an error in the
   coding, decoding, or transmission and SHOULD take measures to conceal
   the error (e.g., saturate to ft-1 or use the Packet Loss Concealment
   (PLC)) and/or report to the application that the error has occurred.

4.1.6.  Current Bit Usage

   The bit allocation routines in the CELT decoder need a conservative
   upper bound on the number of bits that have been used from the
   current frame thus far, including both range coder bits and raw bits.
   This drives allocation decisions that must match those made in the
   encoder.  The upper bound is computed in the reference implementation
   to whole-bit precision by the function ec_tell() (entcode.h) and to
   fractional 1/8th bit precision by the function ec_tell_frac()
   (entcode.c).  Like all operations in the range coder, it must be
   implemented in a bit-exact manner, and it must produce exactly the
   same value returned by the same functions in the encoder after
   encoding the same symbols.

   ec_tell() is guaranteed to return ceil(ec_tell_frac()/8.0).  In
   various places, the codec will check to ensure there is enough room
   to contain a symbol before attempting to decode it.  In practice,
   although the number of bits used so far is an upper bound, decoding a
   symbol whose probability model suggests it has a worst-case cost of p
   1/8th bits may actually advance the return value of ec_tell_frac() by
   p-1, p, or p+1 1/8th bits, due to approximation error in that upper
   bound, truncation error in the range coder, and for large values of
   ft, modeling error in ec_dec_uint().

   However, this error is bounded, and periodic calls to ec_tell() or
   ec_tell_frac() at precisely defined points in the decoding process
   prevent it from accumulating.  For a range coder symbol that requires
   a whole number of bits (i.e., for which ft/(fh[k] - fl[k]) is a power
   of two), where there are at least p 1/8th bits available, decoding
   the symbol will never cause ec_tell() or ec_tell_frac() to exceed the
   size of the frame ("bust the budget").  In this case, the return
   value of ec_tell_frac() will only advance by more than p 1/8th bits
   if there were an additional, fractional number of bits remaining, and
   it will never advance beyond the next whole-bit boundary, which is
   safe, since frames always contain a whole number of bits.  However,
   when p is not a whole number of bits, an extra 1/8th bit is required
   to ensure that decoding the symbol will not bust the budget.

Top      Up      ToC       Page 31 
   The reference implementation keeps track of the total number of whole
   bits that have been processed by the decoder so far in the variable
   nbits_total, including the (possibly fractional) number of bits that
   are currently buffered, but not consumed, inside the range coder.
   nbits_total is initialized to 9 just before the initial range
   renormalization process completes (or equivalently, it can be
   initialized to 33 after the first renormalization).  The extra two
   bits over the actual amount buffered by the range coder guarantees
   that it is an upper bound and that there is enough room for the
   encoder to terminate the stream.  Each iteration through the range
   coder's renormalization loop increases nbits_total by 8.  Reading raw
   bits increases nbits_total by the number of raw bits read.  ec_tell()

   The whole number of bits buffered in rng may be estimated via
   lg = ilog(rng). ec_tell() then becomes a simple matter of removing
   these bits from the total.  It returns (nbits_total - lg).

   In a newly initialized decoder, before any symbols have been read,
   this reports that 1 bit has been used.  This is the bit reserved for
   termination of the encoder.  ec_tell_frac()

   ec_tell_frac() estimates the number of bits buffered in rng to
   fractional precision.  Since rng must be greater than 2**23 after
   renormalization, lg must be at least 24.  Let

                           r_Q15 = rng >> (lg-16)

   so that 32768 <= r_Q15 < 65536, an unsigned Q15 value representing
   the fractional part of rng.  Then, the following procedure can be
   used to add one bit of precision to lg.  First, update

                        r_Q15 = (r_Q15*r_Q15) >> 15

   Then, add the 16th bit of r_Q15 to lg via

                         lg = 2*lg + (r_Q15 >> 16)

   Finally, if this bit was a 1, reduce r_Q15 by a factor of two via

                             r_Q15 = r_Q15 >> 1

   so that it once again lies in the range 32768 <= r_Q15 < 65536.  This
   procedure is repeated three times to extend lg to 1/8th bit
   precision. ec_tell_frac() then returns (nbits_total*8 - lg).

Next RFC Part