Documentation
¶
Overview ¶
Package rangecoding provides a Range coder for the Opus bitstream
Index ¶
- type Decoder
- func (r *Decoder) DecodeCumulative(total uint32) uint32
- func (r *Decoder) DecodeLaplace(fs0 uint32, decay uint32) int
- func (r *Decoder) DecodeRawBits(n uint) uint32
- func (r *Decoder) DecodeSymbolLogP(logp uint) uint32
- func (r *Decoder) DecodeSymbolWithICDF(cumulativeDistributionTable []uint) uint32
- func (r *Decoder) DecodeUniform(total uint32) (uint32, bool)
- func (r *Decoder) FinalRange() uint32
- func (r *Decoder) Init(data []byte)
- func (r *Decoder) RemainingBits() int
- func (r *Decoder) SetInternalValues(data []byte, bitsRead uint, rangeSize uint32, highAndCodedDifference uint32)
- func (r *Decoder) SetStorageSize(size int)
- func (r *Decoder) Tell() uint
- func (r *Decoder) TellFrac() uint
- func (r *Decoder) UpdateCumulative(low, high, total uint32)
- type Encoder
- func (e *Encoder) Done() []byte
- func (e *Encoder) EncodeCumulative(low, high, total uint32)
- func (e *Encoder) EncodeLaplace(fs0, decay uint32, value int) int
- func (e *Encoder) EncodeRawBits(n uint, value uint32)
- func (e *Encoder) EncodeSymbolLogP(logp uint, symbol uint32)
- func (e *Encoder) EncodeSymbolWithICDF(cumulativeDistributionTable []uint, symbol uint32)
- func (e *Encoder) EncodeUniform(total, symbol uint32)
- func (e *Encoder) FinalRange() uint32
- func (e *Encoder) FlushInto(dst []byte) int
- func (e *Encoder) FlushIntoPadded(dst []byte, size int) int
- func (e *Encoder) Init()
- func (e *Encoder) PatchInitialBits(value uint32, bitCount uint) bool
- func (e *Encoder) Restore(s *State)
- func (e *Encoder) SaveInto(dst *State)
- func (e *Encoder) Tell() uint
- func (e *Encoder) TellFrac() uint
- type State
Constants ¶
This section is empty.
Variables ¶
This section is empty.
Functions ¶
This section is empty.
Types ¶
type Decoder ¶
type Decoder struct {
// contains filtered or unexported fields
}
Decoder implements rfc6716#section-4.1 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 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) |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
Legend:
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:
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 values.
func (*Decoder) DecodeCumulative ¶
DecodeCumulative decodes the cumulative frequency index used by CELT's custom range-coded symbols. Call UpdateCumulative with the selected interval.
func (*Decoder) DecodeLaplace ¶
DecodeLaplace decodes the ec_laplace_decode() symbol used by the CELT layer.
RFC 6716 Section 4.3.2.1 describes coarse energy deltas as Laplace-distributed prediction errors; the reference implementation decodes them with this helper.
func (*Decoder) DecodeRawBits ¶
DecodeRawBits decodes raw bits packed from the end of the frame. RFC 6716 Section 4.1.4 defines this LSB-first tail packing for CELT.
func (*Decoder) DecodeSymbolLogP ¶
DecodeSymbolLogP decodes a single binary symbol. 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".
https://datatracker.ietf.org/doc/html/rfc6716#section-4.1.3.2
func (*Decoder) DecodeSymbolWithICDF ¶
DecodeSymbolWithICDF decodes a single symbol with a table-based context of up to 8 bits.
https://datatracker.ietf.org/doc/html/rfc6716#section-4.1.3.3
func (*Decoder) DecodeUniform ¶
DecodeUniform decodes an RFC 6716 Section 4.1.5 ec_dec_uint() symbol.
It returns false when the decoded raw-bit suffix produces a value outside [0,total), in which case the saturated value matches the reference decoder.
func (*Decoder) FinalRange ¶
FinalRange exposes the current range coder range state for tests.
func (*Decoder) Init ¶
Init sets the state of the Decoder 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 4.1.2.1, which the decoder invokes immediately after initialization to read additional bits and establish the invariant that rng > 2**23.
func (*Decoder) RemainingBits ¶
RemainingBits reports a conservative estimate of the unread payload bits. RFC 6716 Section 4.1.4 allows range and raw-bit cursor overlap.
func (*Decoder) SetInternalValues ¶
func (r *Decoder) SetInternalValues(data []byte, bitsRead uint, rangeSize uint32, highAndCodedDifference uint32)
SetInternalValues is used when using the RangeDecoder when testing.
func (*Decoder) SetStorageSize ¶
SetStorageSize adjusts the logical frame size without resetting decoder state. Opus hybrid redundancy removes tail bytes from the CELT range coder after the shared decoder has already consumed SILK symbols.
func (*Decoder) Tell ¶
Tell returns a conservative upper bound, in whole bits, of how many bits have been consumed from the current frame, per RFC 6716 Section 4.1.6.1.
func (*Decoder) TellFrac ¶
TellFrac returns a conservative upper bound in 1/8 bit units. This follows the ec_tell_frac() construction in RFC 6716 Section 4.1.6.2.
func (*Decoder) UpdateCumulative ¶
UpdateCumulative commits a custom cumulative interval previously selected from DecodeCumulative.
type Encoder ¶
type Encoder struct {
// contains filtered or unexported fields
}
Encoder implements the range encoder defined in RFC 6716 Section 5.1.
The range coder acts as the bit-packer for Opus. It is used in three different ways: to encode
Entropy-coded symbols with a fixed probability model using ec_encode() (entenc.c),
Integers from 0 to (2**M - 1) using ec_enc_uint() or ec_enc_bits() (entenc.c),
Integers from 0 to (ft - 1) (where ft is not a power of two) using ec_enc_uint() (entenc.c).
The range encoder maintains an internal state vector composed of the four-tuple (val, rng, rem, ext) representing the low end of the current range, the size of the current range, a single buffered output byte, and a count of additional carry-propagating output bytes. Both val and rng are 32-bit unsigned integer values, rem is a byte value less than 255 or the special value -1, and ext is an unsigned integer with at least 11 bits. This state vector is initialized at the start of each frame to the value (0, 2**31, -1, 0). After encoding a sequence of symbols, the value of rng in the encoder should exactly match the value of rng in the decoder after decoding the same sequence of symbols. This is a powerful tool for detecting errors in either an encoder or decoder implementation. The value of val, on the other hand, represents different things in the encoder and decoder, and is not expected to match.
The decoder has no analog for rem and ext. These are used to perform carry propagation in the renormalization loop below. Each iteration of this loop produces 9 bits of output, consisting of 8 data bits and a carry flag. The encoder cannot determine the final value of the output bytes until it propagates these carry flags. Therefore, the reference implementation buffers a single non-propagating output byte (i.e., one less than 255) in rem and keeps a count of additional propagating (i.e., 255) output bytes in ext.
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 of RFC 6716. This reduces complexity and makes the stream more resilient to bit errors. 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) |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
Legend:
LSB = Least Significant Bit
MSB = Most Significant Bit
Figure 12: Illustrative Example of Packing Range Coder
and Raw Bits Data
https://datatracker.ietf.org/doc/html/rfc6716#section-5.1
func (*Encoder) Done ¶
Done flushes the range coder and raw bits into a single output frame, implementing ec_enc_done() (entenc.c).
RFC 6716 Section 5.1.5 describes the finalization procedure:
Find the unsigned integer end in [val, val+rng) with the largest number of trailing zero bits b such that (end + (1<<b) - 1) is also in [val, val+rng). Flush the remaining bytes of end through the carry buffer.
If the buffered output byte rem is neither zero nor -1, or the carry count ext is greater than zero, flush 9 zero bits to drain the carry buffer.
Merge the last range-coder byte and the first raw-bits byte into one byte if the range coder did not consume all bits in its final byte. Any space between the range coder data and the raw bits is zero-padded.
https://datatracker.ietf.org/doc/html/rfc6716#section-5.1.5 Done finalizes the frame and returns the encoded bytes as a new slice. Use FlushInto when the caller can provide the destination buffer to avoid the allocation.
func (*Encoder) EncodeCumulative ¶
EncodeCumulative encodes a pre-selected cumulative interval (low, high) out of total equally weighted bins.
This is the main encoding function ec_encode() (entenc.c) defined in RFC 6716 Section 5.1.1. It encodes symbol k described by the three-tuple (fl[k], fh[k], ft) using the same semantics as the decoder's ec_decode().
If fl[k] (low) is greater than zero:
val = val + rng - (rng / ft) * (ft - fl) rng = (rng / ft) * (fh - fl)
Otherwise val is unchanged and:
rng = rng - (rng / ft) * (ft - fh)
func (*Encoder) EncodeLaplace ¶
EncodeLaplace encodes a Laplace-distributed integer value using the same probability model as Decoder.DecodeLaplace.
RFC 6716 Section 4.3.2.1 describes coarse energy deltas as Laplace-distributed prediction errors. The distribution is parameterized by fs0 (the frequency of the zero symbol, in units of 1/32768) and decay (the geometric decay rate of adjacent-magnitude frequencies, Q15).
https://datatracker.ietf.org/doc/html/rfc6716#section-4.3.2.1 EncodeLaplace encodes a Laplace-distributed value and returns the value the decoder will recover, which differs from the input when the tail of the distribution cannot represent it (see laplaceInterval).
func (*Encoder) EncodeRawBits ¶
EncodeRawBits appends n bits of value to the raw-bits region at the end of the frame, packed in LSB-first order.
RFC 6716 Section 5.1.3 specifies that raw bits used by the CELT layer are packed at the end of the buffer using ec_enc_bits() (entenc.c). Because the raw bits may continue into the last byte output by the range coder if there is room in the low-order bits, Done() merges the two regions into a single byte when they meet.
func (*Encoder) EncodeSymbolLogP ¶
EncodeSymbolLogP encodes a single binary symbol with probability 1/(1<<logp) for symbol 1.
This implements ec_enc_bit_logp() (entenc.c), which is mathematically equivalent to calling ec_encode() with the 3-tuple (fl[k] = 0, fh[k] = (1<<logp) - 1, ft = (1<<logp)) if k is 0 and with (fl[k] = (1<<logp) - 1, fh[k] = ft = (1<<logp)) if k is 1. The implementation requires no multiplications or divisions.
func (*Encoder) EncodeSymbolWithICDF ¶
EncodeSymbolWithICDF encodes a symbol using the same inverse cumulative distribution table format consumed by Decoder.DecodeSymbolWithICDF.
This implements ec_enc_icdf() (entenc.c), which is mathematically equivalent to calling ec_encode() with fl[k] = (1<<ftb) - icdf[k-1], fh[k] = (1<<ftb) - icdf[k], and ft = (1<<ftb). It allows the encoder to use the same icdf tables as the decoder.
func (*Encoder) EncodeUniform ¶
EncodeUniform encodes one of ft equiprobable symbols in the range [0, ft), implementing ec_enc_uint() (entenc.c).
RFC 6716 Section 5.1.4 splits the value into a range-coded prefix of up to 8 high bits and, if ft requires more than 8 bits, a raw-bit suffix:
If ftb = ilog(ft - 1) <= 8, encode t directly via ec_encode(). If ftb > 8, encode t>>(ftb-8) via ec_encode() and the remaining (ftb - 8) bits of t via ec_enc_bits().
func (*Encoder) FinalRange ¶
FinalRange exposes the current range coder range state for tests.
RFC 6716 Section 5.1 states that after encoding a sequence of symbols the value of rng in the encoder should exactly match the value of rng in the decoder after decoding the same sequence of symbols. This is a powerful tool for detecting errors in either an encoder or decoder implementation.
func (*Encoder) FlushInto ¶
FlushInto finalizes the frame and writes the encoded bytes into dst without allocating. dst must have length >= frameBytes. Returns the number of bytes written.
func (*Encoder) FlushIntoPadded ¶
FlushIntoPadded finalizes the frame into dst and zero-fills the result out to size bytes when the coded data is shorter.
CELT derives its bit allocation from the frame size the encoder was asked for, and the decoder re-derives it from the size of the packet it receives. Emitting a shorter packet makes the two sides compute different allocations, so they disagree on how many raw bits each band's fine energy occupies and the decoder reads that region at the wrong offsets. libopus avoids this by initializing the range coder with the target size up front and clearing the unused middle in ec_enc_done (celt/entenc.c).
func (*Encoder) Init ¶
func (e *Encoder) Init()
Init resets the Encoder state for a new frame.
RFC 6716 Section 5.1 specifies that the encoder state vector (val, rng, rem, ext) is initialized at the start of each frame to (0, 2**31, -1, 0). nbitsTotal is set to codeBits + 1 so that Tell() returns 1 after initialization, matching the decoder's post-Init value (the decoder consumes one bit of bootstrap input during Init).
func (*Encoder) PatchInitialBits ¶
PatchInitialBits replaces the first bitCount coded bits with the MSB-first bit pattern value. It is the Go equivalent of ec_enc_patch_initial_bits().
SILK delays its per-frame VAD/LBRR flags until the packet has been analyzed. Depending on how far encoding has progressed, the initial bits may already be in the first finalized byte, in the pending carry byte, or still in low. Patching must not change the current range or the bit count.
It reports whether the request is representable in the current state; patching zero bits is a successful no-op.
func (*Encoder) Restore ¶
Restore rewinds to a state taken by SaveInto. Only states from the same frame are meaningful.
func (*Encoder) SaveInto ¶
SaveInto captures the encoder state so a speculative encode can be undone. It reuses dst's buffers, so a caller that snapshots in a loop allocates once.
func (*Encoder) Tell ¶
Tell returns a conservative upper bound, in whole bits, of the number of bits encoded into the current frame so far.
This implements ec_tell() (entcode.h) from RFC 6716 Section 5.1.6. The bit allocation routines in Opus use this value to track budget consumption and prevent the range coder from overflowing the output buffer. After encoding the same symbols, the encoder and decoder must produce identical Tell() values.
func (*Encoder) TellFrac ¶
TellFrac returns a conservative upper bound in 1/8-bit units.
This implements ec_tell_frac() (entcode.c) from RFC 6716 Section 5.1.6. It refines the Tell() estimate by squaring down the fractional part of the range size three times to obtain three additional sub-bit fractions. The encoder and decoder must produce identical TellFrac() values after encoding and decoding the same symbols.
type State ¶
type State struct {
// contains filtered or unexported fields
}
State is a snapshot of the encoder taken mid-frame. Rewinding needs the output bytes as well as the scalars: a speculative encode that is rolled back leaves the next one writing over the same positions, so the first one's bytes are gone by the time we might want them again.
Source Files