diff options
Diffstat (limited to 'contrib/vorbis/doc/08-residue.tex')
| -rw-r--r-- | contrib/vorbis/doc/08-residue.tex | 451 |
1 files changed, 451 insertions, 0 deletions
diff --git a/contrib/vorbis/doc/08-residue.tex b/contrib/vorbis/doc/08-residue.tex new file mode 100644 index 0000000..ea38243 --- /dev/null +++ b/contrib/vorbis/doc/08-residue.tex @@ -0,0 +1,451 @@ +% -*- mode: latex; TeX-master: "Vorbis_I_spec"; -*- +%!TEX root = Vorbis_I_spec.tex +\section{Residue setup and decode} \label{vorbis:spec:residue} + +\subsection{Overview} + +A residue vector represents the fine detail of the audio spectrum of +one channel in an audio frame after the encoder subtracts the floor +curve and performs any channel coupling. A residue vector may +represent spectral lines, spectral magnitude, spectral phase or +hybrids as mixed by channel coupling. The exact semantic content of +the vector does not matter to the residue abstraction. + +Whatever the exact qualities, the Vorbis residue abstraction codes the +residue vectors into the bitstream packet, and then reconstructs the +vectors during decode. Vorbis makes use of three different encoding +variants (numbered 0, 1 and 2) of the same basic vector encoding +abstraction. + + + +\subsection{Residue format} + +Residue format partitions each vector in the vector bundle into chunks, +classifies each chunk, encodes the chunk classifications and finally +encodes the chunks themselves using the the specific VQ arrangement +defined for each selected classification. +The exact interleaving and partitioning vary by residue encoding number, +however the high-level process used to classify and encode the residue +vector is the same in all three variants. + +A set of coded residue vectors are all of the same length. High level +coding structure, ignoring for the moment exactly how a partition is +encoded and simply trusting that it is, is as follows: + +\begin{itemize} +\item Each vector is partitioned into multiple equal sized chunks +according to configuration specified. If we have a vector size of +\emph{n}, a partition size \emph{residue\_partition\_size}, and a total +of \emph{ch} residue vectors, the total number of partitioned chunks +coded is \emph{n}/\emph{residue\_partition\_size}*\emph{ch}. It is +important to note that the integer division truncates. In the below +example, we assume an example \emph{residue\_partition\_size} of 8. + +\item Each partition in each vector has a classification number that +specifies which of multiple configured VQ codebook setups are used to +decode that partition. The classification numbers of each partition +can be thought of as forming a vector in their own right, as in the +illustration below. Just as the residue vectors are coded in grouped +partitions to increase encoding efficiency, the classification vector +is also partitioned into chunks. The integer elements of each scalar +in a classification chunk are built into a single scalar that +represents the classification numbers in that chunk. In the below +example, the classification codeword encodes two classification +numbers. + +\item The values in a residue vector may be encoded monolithically in a +single pass through the residue vector, but more often efficient +codebook design dictates that each vector is encoded as the additive +sum of several passes through the residue vector using more than one +VQ codebook. Thus, each residue value potentially accumulates values +from multiple decode passes. The classification value associated with +a partition is the same in each pass, thus the classification codeword +is coded only in the first pass. + +\end{itemize} + + +\begin{center} +\includegraphics[width=\textwidth]{residue-pack} +\captionof{figure}{illustration of residue vector format} +\end{center} + + + +\subsection{residue 0} + +Residue 0 and 1 differ only in the way the values within a residue +partition are interleaved during partition encoding (visually treated +as a black box--or cyan box or brown box--in the above figure). + +Residue encoding 0 interleaves VQ encoding according to the +dimension of the codebook used to encode a partition in a specific +pass. The dimension of the codebook need not be the same in multiple +passes, however the partition size must be an even multiple of the +codebook dimension. + +As an example, assume a partition vector of size eight, to be encoded +by residue 0 using codebook sizes of 8, 4, 2 and 1: + +\begin{programlisting} + + original residue vector: [ 0 1 2 3 4 5 6 7 ] + +codebook dimensions = 8 encoded as: [ 0 1 2 3 4 5 6 7 ] + +codebook dimensions = 4 encoded as: [ 0 2 4 6 ], [ 1 3 5 7 ] + +codebook dimensions = 2 encoded as: [ 0 4 ], [ 1 5 ], [ 2 6 ], [ 3 7 ] + +codebook dimensions = 1 encoded as: [ 0 ], [ 1 ], [ 2 ], [ 3 ], [ 4 ], [ 5 ], [ 6 ], [ 7 ] + +\end{programlisting} + +It is worth mentioning at this point that no configurable value in the +residue coding setup is restricted to a power of two. + + + +\subsection{residue 1} + +Residue 1 does not interleave VQ encoding. It represents partition +vector scalars in order. As with residue 0, however, partition length +must be an integer multiple of the codebook dimension, although +dimension may vary from pass to pass. + +As an example, assume a partition vector of size eight, to be encoded +by residue 0 using codebook sizes of 8, 4, 2 and 1: + +\begin{programlisting} + + original residue vector: [ 0 1 2 3 4 5 6 7 ] + +codebook dimensions = 8 encoded as: [ 0 1 2 3 4 5 6 7 ] + +codebook dimensions = 4 encoded as: [ 0 1 2 3 ], [ 4 5 6 7 ] + +codebook dimensions = 2 encoded as: [ 0 1 ], [ 2 3 ], [ 4 5 ], [ 6 7 ] + +codebook dimensions = 1 encoded as: [ 0 ], [ 1 ], [ 2 ], [ 3 ], [ 4 ], [ 5 ], [ 6 ], [ 7 ] + +\end{programlisting} + + + +\subsection{residue 2} + +Residue type two can be thought of as a variant of residue type 1. +Rather than encoding multiple passed-in vectors as in residue type 1, +the \emph{ch} passed in vectors of length \emph{n} are first +interleaved and flattened into a single vector of length +\emph{ch}*\emph{n}. Encoding then proceeds as in type 1. Decoding is +as in type 1 with decode interleave reversed. If operating on a single +vector to begin with, residue type 1 and type 2 are equivalent. + +\begin{center} +\includegraphics[width=\textwidth]{residue2} +\captionof{figure}{illustration of residue type 2} +\end{center} + + +\subsection{Residue decode} + +\subsubsection{header decode} + +Header decode for all three residue types is identical. +\begin{programlisting} + 1) [residue\_begin] = read 24 bits as unsigned integer + 2) [residue\_end] = read 24 bits as unsigned integer + 3) [residue\_partition\_size] = read 24 bits as unsigned integer and add one + 4) [residue\_classifications] = read 6 bits as unsigned integer and add one + 5) [residue\_classbook] = read 8 bits as unsigned integer +\end{programlisting} + +\varname{[residue\_begin]} and +\varname{[residue\_end]} select the specific sub-portion of +each vector that is actually coded; it implements akin to a bandpass +where, for coding purposes, the vector effectively begins at element +\varname{[residue\_begin]} and ends at +\varname{[residue\_end]}. Preceding and following values in +the unpacked vectors are zeroed. Note that for residue type 2, these +values as well as \varname{[residue\_partition\_size]}apply to +the interleaved vector, not the individual vectors before interleave. +\varname{[residue\_partition\_size]} is as explained above, +\varname{[residue\_classifications]} is the number of possible +classification to which a partition can belong and +\varname{[residue\_classbook]} is the codebook number used to +code classification codewords. The number of dimensions in book +\varname{[residue\_classbook]} determines how many +classification values are grouped into a single classification +codeword. Note that the number of entries and dimensions in book +\varname{[residue\_classbook]}, along with +\varname{[residue\_classifications]}, overdetermines to +possible number of classification codewords. +If \varname{[residue\_classifications]}\^{}\varname{[residue\_classbook]}.dimensions +exceeds \varname{[residue\_classbook]}.entries, the +bitstream should be regarded to be undecodable. + +Next we read a bitmap pattern that specifies which partition classes +code values in which passes. + +\begin{programlisting} + 1) iterate [i] over the range 0 ... [residue\_classifications]-1 { + + 2) [high\_bits] = 0 + 3) [low\_bits] = read 3 bits as unsigned integer + 4) [bitflag] = read one bit as boolean + 5) if ( [bitflag] is set ) then [high\_bits] = read five bits as unsigned integer + 6) vector [residue\_cascade] element [i] = [high\_bits] * 8 + [low\_bits] + } + 7) done +\end{programlisting} + +Finally, we read in a list of book numbers, each corresponding to +specific bit set in the cascade bitmap. We loop over the possible +codebook classifications and the maximum possible number of encoding +stages (8 in Vorbis I, as constrained by the elements of the cascade +bitmap being eight bits): + +\begin{programlisting} + 1) iterate [i] over the range 0 ... [residue\_classifications]-1 { + + 2) iterate [j] over the range 0 ... 7 { + + 3) if ( vector [residue\_cascade] element [i] bit [j] is set ) { + + 4) array [residue\_books] element [i][j] = read 8 bits as unsigned integer + + } else { + + 5) array [residue\_books] element [i][j] = unused + + } + } + } + + 6) done +\end{programlisting} + +An end-of-packet condition at any point in header decode renders the +stream undecodable. In addition, any codebook number greater than the +maximum numbered codebook set up in this stream also renders the +stream undecodable. All codebooks in array [residue\_books] are +required to have a value mapping. The presence of codebook in array +[residue\_books] without a value mapping (maptype equals zero) renders +the stream undecodable. + + + +\subsubsection{packet decode} + +Format 0 and 1 packet decode is identical except for specific +partition interleave. Format 2 packet decode can be built out of the +format 1 decode process. Thus we describe first the decode +infrastructure identical to all three formats. + +In addition to configuration information, the residue decode process +is passed the number of vectors in the submap bundle and a vector of +flags indicating if any of the vectors are not to be decoded. If the +passed in number of vectors is 3 and vector number 1 is marked 'do not +decode', decode skips vector 1 during the decode loop. However, even +'do not decode' vectors are allocated and zeroed. + +Depending on the values of \varname{[residue\_begin]} and +\varname{[residue\_end]}, it is obvious that the encoded +portion of a residue vector may be the entire possible residue vector +or some other strict subset of the actual residue vector size with +zero padding at either uncoded end. However, it is also possible to +set \varname{[residue\_begin]} and +\varname{[residue\_end]} to specify a range partially or +wholly beyond the maximum vector size. Before beginning residue +decode, limit \varname{[residue\_begin]} and +\varname{[residue\_end]} to the maximum possible vector size +as follows. We assume that the number of vectors being encoded, +\varname{[ch]} is provided by the higher level decoding +process. + +\begin{programlisting} + 1) [actual\_size] = current blocksize/2; + 2) if residue encoding is format 2 + 3) [actual\_size] = [actual\_size] * [ch]; + 4) [limit\_residue\_begin] = minimum of ([residue\_begin],[actual\_size]); + 5) [limit\_residue\_end] = minimum of ([residue\_end],[actual\_size]); +\end{programlisting} + +The following convenience values are conceptually useful to clarifying +the decode process: + +\begin{programlisting} + 1) [classwords\_per\_codeword] = [codebook\_dimensions] value of codebook [residue\_classbook] + 2) [n\_to\_read] = [limit\_residue\_end] - [limit\_residue\_begin] + 3) [partitions\_to\_read] = [n\_to\_read] / [residue\_partition\_size] +\end{programlisting} + +Packet decode proceeds as follows, matching the description offered earlier in the document. +\begin{programlisting} + 1) allocate and zero all vectors that will be returned. + 2) if ([n\_to\_read] is zero), stop; there is no residue to decode. + 3) iterate [pass] over the range 0 ... 7 { + + 4) [partition\_count] = 0 + + 5) while [partition\_count] is less than [partitions\_to\_read] + + 6) if ([pass] is zero) { + + 7) iterate [j] over the range 0 .. [ch]-1 { + + 8) if vector [j] is not marked 'do not decode' { + + 9) [temp] = read from packet using codebook [residue\_classbook] in scalar context + 10) iterate [i] descending over the range [classwords\_per\_codeword]-1 ... 0 { + + 11) array [classifications] element [j],([i]+[partition\_count]) = + [temp] integer modulo [residue\_classifications] + 12) [temp] = [temp] / [residue\_classifications] using integer division + + } + + } + + } + + } + + 13) iterate [i] over the range 0 .. ([classwords\_per\_codeword] - 1) while [partition\_count] + is also less than [partitions\_to\_read] { + + 14) iterate [j] over the range 0 .. [ch]-1 { + + 15) if vector [j] is not marked 'do not decode' { + + 16) [vqclass] = array [classifications] element [j],[partition\_count] + 17) [vqbook] = array [residue\_books] element [vqclass],[pass] + 18) if ([vqbook] is not 'unused') { + + 19) decode partition into output vector number [j], starting at scalar + offset [limit\_residue\_begin]+[partition\_count]*[residue\_partition\_size] using + codebook number [vqbook] in VQ context + } + } + + 20) increment [partition\_count] by one + + } + } + } + + 21) done + +\end{programlisting} + +An end-of-packet condition during packet decode is to be considered a +nominal occurrence. Decode returns the result of vector decode up to +that point. + + + +\subsubsection{format 0 specifics} + +Format zero decodes partitions exactly as described earlier in the +'Residue Format: residue 0' section. The following pseudocode +presents the same algorithm. Assume: + +\begin{itemize} +\item \varname{[n]} is the value in \varname{[residue\_partition\_size]} +\item \varname{[v]} is the residue vector +\item \varname{[offset]} is the beginning read offset in [v] +\end{itemize} + + +\begin{programlisting} + 1) [step] = [n] / [codebook\_dimensions] + 2) iterate [i] over the range 0 ... [step]-1 { + + 3) vector [entry\_temp] = read vector from packet using current codebook in VQ context + 4) iterate [j] over the range 0 ... [codebook\_dimensions]-1 { + + 5) vector [v] element ([offset]+[i]+[j]*[step]) = + vector [v] element ([offset]+[i]+[j]*[step]) + + vector [entry\_temp] element [j] + + } + + } + + 6) done + +\end{programlisting} + + + +\subsubsection{format 1 specifics} + +Format 1 decodes partitions exactly as described earlier in the +'Residue Format: residue 1' section. The following pseudocode +presents the same algorithm. Assume: + +\begin{itemize} +\item \varname{[n]} is the value in +\varname{[residue\_partition\_size]} +\item \varname{[v]} is the residue vector +\item \varname{[offset]} is the beginning read offset in [v] +\end{itemize} + + +\begin{programlisting} + 1) [i] = 0 + 2) vector [entry\_temp] = read vector from packet using current codebook in VQ context + 3) iterate [j] over the range 0 ... [codebook\_dimensions]-1 { + + 4) vector [v] element ([offset]+[i]) = + vector [v] element ([offset]+[i]) + + vector [entry\_temp] element [j] + 5) increment [i] + + } + + 6) if ( [i] is less than [n] ) continue at step 2 + 7) done +\end{programlisting} + + + +\subsubsection{format 2 specifics} + +Format 2 is reducible to format 1. It may be implemented as an additional step prior to and an additional post-decode step after a normal format 1 decode. + + +Format 2 handles 'do not decode' vectors differently than residue 0 or +1; if all vectors are marked 'do not decode', no decode occurrs. +However, if at least one vector is to be decoded, all the vectors are +decoded. We then request normal format 1 to decode a single vector +representing all output channels, rather than a vector for each +channel. After decode, deinterleave the vector into independent vectors, one for each output channel. That is: + +\begin{enumerate} + \item If all vectors 0 through \emph{ch}-1 are marked 'do not decode', allocate and clear a single vector \varname{[v]}of length \emph{ch*n} and skip step 2 below; proceed directly to the post-decode step. + \item Rather than performing format 1 decode to produce \emph{ch} vectors of length \emph{n} each, call format 1 decode to produce a single vector \varname{[v]} of length \emph{ch*n}. + \item Post decode: Deinterleave the single vector \varname{[v]} returned by format 1 decode as described above into \emph{ch} independent vectors, one for each outputchannel, according to: + \begin{programlisting} + 1) iterate [i] over the range 0 ... [n]-1 { + + 2) iterate [j] over the range 0 ... [ch]-1 { + + 3) output vector number [j] element [i] = vector [v] element ([i] * [ch] + [j]) + + } + } + + 4) done + \end{programlisting} + +\end{enumerate} + + + + + + + |