doc/08-residue.tex

   1 % -*- mode: latex; TeX-master: "Vorbis_I_spec"; -*-
   2 %!TEX root = Vorbis_I_spec.tex
   3 % $Id$
   4 \section{Residue setup and decode} \label{vorbis:spec:residue}
   5
   6 \subsection{Overview}
   7
   8 A residue vector represents the fine detail of the audio spectrum of
   9 one channel in an audio frame after the encoder subtracts the floor
  10 curve and performs any channel coupling.  A residue vector may
  11 represent spectral lines, spectral magnitude, spectral phase or
  12 hybrids as mixed by channel coupling.  The exact semantic content of
  13 the vector does not matter to the residue abstraction.
  14
  15 Whatever the exact qualities, the Vorbis residue abstraction codes the
  16 residue vectors into the bitstream packet, and then reconstructs the
  17 vectors during decode.  Vorbis makes use of three different encoding
  18 variants (numbered 0, 1 and 2) of the same basic vector encoding
  19 abstraction.
  20
  21
  22
  23 \subsection{Residue format}
  24
  25 Residue format partitions each vector in the vector bundle into chunks,
  26 classifies each chunk, encodes the chunk classifications and finally
  27 encodes the chunks themselves using the the specific VQ arrangement
  28 defined for each selected classification.
  29 The exact interleaving and partitioning vary by residue encoding number,
  30 however the high-level process used to classify and encode the residue
  31 vector is the same in all three variants.
  32
  33 A set of coded residue vectors are all of the same length.  High level
  34 coding structure, ignoring for the moment exactly how a partition is
  35 encoded and simply trusting that it is, is as follows:
  36
  37 \begin{itemize}
  38 \item Each vector is partitioned into multiple equal sized chunks
  39 according to configuration specified.  If we have a vector size of
  40 \emph{n}, a partition size \emph{residue_partition_size}, and a total
  41 of \emph{ch} residue vectors, the total number of partitioned chunks
  42 coded is \emph{n}/\emph{residue_partition_size}*\emph{ch}.  It is
  43 important to note that the integer division truncates.  In the below
  44 example, we assume an example \emph{residue_partition_size} of 8.
  45
  46 \item Each partition in each vector has a classification number that
  47 specifies which of multiple configured VQ codebook setups are used to
  48 decode that partition.  The classification numbers of each partition
  49 can be thought of as forming a vector in their own right, as in the
  50 illustration below.  Just as the residue vectors are coded in grouped
  51 partitions to increase encoding efficiency, the classification vector
  52 is also partitioned into chunks.  The integer elements of each scalar
  53 in a classification chunk are built into a single scalar that
  54 represents the classification numbers in that chunk.  In the below
  55 example, the classification codeword encodes two classification
  56 numbers.
  57
  58 \item The values in a residue vector may be encoded monolithically in a
  59 single pass through the residue vector, but more often efficient
  60 codebook design dictates that each vector is encoded as the additive
  61 sum of several passes through the residue vector using more than one
  62 VQ codebook.  Thus, each residue value potentially accumulates values
  63 from multiple decode passes.  The classification value associated with
  64 a partition is the same in each pass, thus the classification codeword
  65 is coded only in the first pass.
  66
  67 \end{itemize}
  68
  69
  70 \begin{center}
  71 \includegraphics[width=\textwidth]{residue-pack}
  72 \captionof{figure}{illustration of residue vector format}
  73 \end{center}
  74
  75
  76
  77 \subsection{residue 0}
  78
  79 Residue 0 and 1 differ only in the way the values within a residue
  80 partition are interleaved during partition encoding (visually treated
  81 as a black box--or cyan box or brown box--in the above figure).
  82
  83 Residue encoding 0 interleaves VQ encoding according to the
  84 dimension of the codebook used to encode a partition in a specific
  85 pass.  The dimension of the codebook need not be the same in multiple
  86 passes, however the partition size must be an even multiple of the
  87 codebook dimension.
  88
  89 As an example, assume a partition vector of size eight, to be encoded
  90 by residue 0 using codebook sizes of 8, 4, 2 and 1:
  91
  92 \begin{programlisting}
  93
  94             original residue vector: [ 0 1 2 3 4 5 6 7 ]
  95
  96 codebook dimensions = 8  encoded as: [ 0 1 2 3 4 5 6 7 ]
  97
  98 codebook dimensions = 4  encoded as: [ 0 2 4 6 ], [ 1 3 5 7 ]
  99
 100 codebook dimensions = 2  encoded as: [ 0 4 ], [ 1 5 ], [ 2 6 ], [ 3 7 ]
 101
 102 codebook dimensions = 1  encoded as: [ 0 ], [ 1 ], [ 2 ], [ 3 ], [ 4 ], [ 5 ], [ 6 ], [ 7 ]
 103
 104 \end{programlisting}
 105
 106 It is worth mentioning at this point that no configurable value in the
 107 residue coding setup is restricted to a power of two.
 108
 109
 110
 111 \subsection{residue 1}
 112
 113 Residue 1 does not interleave VQ encoding.  It represents partition
 114 vector scalars in order.  As with residue 0, however, partition length
 115 must be an integer multiple of the codebook dimension, although
 116 dimension may vary from pass to pass.
 117
 118 As an example, assume a partition vector of size eight, to be encoded
 119 by residue 0 using codebook sizes of 8, 4, 2 and 1:
 120
 121 \begin{programlisting}
 122
 123             original residue vector: [ 0 1 2 3 4 5 6 7 ]
 124
 125 codebook dimensions = 8  encoded as: [ 0 1 2 3 4 5 6 7 ]
 126
 127 codebook dimensions = 4  encoded as: [ 0 1 2 3 ], [ 4 5 6 7 ]
 128
 129 codebook dimensions = 2  encoded as: [ 0 1 ], [ 2 3 ], [ 4 5 ], [ 6 7 ]
 130
 131 codebook dimensions = 1  encoded as: [ 0 ], [ 1 ], [ 2 ], [ 3 ], [ 4 ], [ 5 ], [ 6 ], [ 7 ]
 132
 133 \end{programlisting}
 134
 135
 136
 137 \subsection{residue 2}
 138
 139 Residue type two can be thought of as a variant of residue type 1.
 140 Rather than encoding multiple passed-in vectors as in residue type 1,
 141 the \emph{ch} passed in vectors of length \emph{n} are first
 142 interleaved and flattened into a single vector of length
 143 \emph{ch}*\emph{n}.  Encoding then proceeds as in type 1. Decoding is
 144 as in type 1 with decode interleave reversed. If operating on a single
 145 vector to begin with, residue type 1 and type 2 are equivalent.
 146
 147 \begin{center}
 148 \includegraphics[width=\textwidth]{residue2}
 149 \captionof{figure}{illustration of residue type 2}
 150 \end{center}
 151
 152
 153 \subsection{Residue decode}
 154
 155 \subsubsection{header decode}
 156
 157 Header decode for all three residue types is identical.
 158 \begin{programlisting}
 159   1) [residue_begin] = read 24 bits as unsigned integer
 160   2) [residue_end] = read 24 bits as unsigned integer
 161   3) [residue_partition_size] = read 24 bits as unsigned integer and add one
 162   4) [residue_classifications] = read 6 bits as unsigned integer and add one
 163   5) [residue_classbook] = read 8 bits as unsigned integer
 164 \end{programlisting}
 165
 166 \varname{[residue_begin]} and
 167 \varname{[residue_end]} select the specific sub-portion of
 168 each vector that is actually coded; it implements akin to a bandpass
 169 where, for coding purposes, the vector effectively begins at element
 170 \varname{[residue_begin]} and ends at
 171 \varname{[residue_end]}.  Preceding and following values in
 172 the unpacked vectors are zeroed.  Note that for residue type 2, these
 173 values as well as \varname{[residue_partition_size]}apply to
 174 the interleaved vector, not the individual vectors before interleave.
 175 \varname{[residue_partition_size]} is as explained above,
 176 \varname{[residue_classifications]} is the number of possible
 177 classification to which a partition can belong and
 178 \varname{[residue_classbook]} is the codebook number used to
 179 code classification codewords.  The number of dimensions in book
 180 \varname{[residue_classbook]} determines how many
 181 classification values are grouped into a single classification
 182 codeword.  Note that the number of entries and dimensions in book
 183 \varname{[residue_classbook]}, along with
 184 \varname{[residue_classifications]}, overdetermines to
 185 possible number of classification codewords.
 186 If \varname{[residue_classifications]}\^{}\varname{[residue_classbook]}.dimensions
 187 exceeds \varname{[residue_classbook]}.entries, the
 188 bitstream should be regarded to be undecodable.
 189
 190 Next we read a bitmap pattern that specifies which partition classes
 191 code values in which passes.
 192
 193 \begin{programlisting}
 194   1) iterate [i] over the range 0 ... [residue_classifications]-1 {
 195
 196        2) [high_bits] = 0
 197        3) [low_bits] = read 3 bits as unsigned integer
 198        4) [bitflag] = read one bit as boolean
 199        5) if ( [bitflag] is set ) then [high_bits] = read five bits as unsigned integer
 200        6) vector [residue_cascade] element [i] = [high_bits] * 8 + [low_bits]
 201      }
 202   7) done
 203 \end{programlisting}
 204
 205 Finally, we read in a list of book numbers, each corresponding to
 206 specific bit set in the cascade bitmap.  We loop over the possible
 207 codebook classifications and the maximum possible number of encoding
 208 stages (8 in Vorbis I, as constrained by the elements of the cascade
 209 bitmap being eight bits):
 210
 211 \begin{programlisting}
 212   1) iterate [i] over the range 0 ... [residue_classifications]-1 {
 213
 214        2) iterate [j] over the range 0 ... 7 {
 215
 216             3) if ( vector [residue_cascade] element [i] bit [j] is set ) {
 217
 218                  4) array [residue_books] element [i][j] = read 8 bits as unsigned integer
 219
 220                } else {
 221
 222                  5) array [residue_books] element [i][j] = unused
 223
 224                }
 225           }
 226       }
 227
 228   6) done
 229 \end{programlisting}
 230
 231 An end-of-packet condition at any point in header decode renders the
 232 stream undecodable.  In addition, any codebook number greater than the
 233 maximum numbered codebook set up in this stream also renders the
 234 stream undecodable.
 235
 236
 237
 238 \subsubsection{packet decode}
 239
 240 Format 0 and 1 packet decode is identical except for specific
 241 partition interleave.  Format 2 packet decode can be built out of the
 242 format 1 decode process.  Thus we describe first the decode
 243 infrastructure identical to all three formats.
 244
 245 In addition to configuration information, the residue decode process
 246 is passed the number of vectors in the submap bundle and a vector of
 247 flags indicating if any of the vectors are not to be decoded.  If the
 248 passed in number of vectors is 3 and vector number 1 is marked 'do not
 249 decode', decode skips vector 1 during the decode loop.  However, even
 250 'do not decode' vectors are allocated and zeroed.
 251
 252 Depending on the values of \varname{[residue_begin]} and
 253 \varname{[residue_end]}, it is obvious that the encoded
 254 portion of a residue vector may be the entire possible residue vector
 255 or some other strict subset of the actual residue vector size with
 256 zero padding at either uncoded end.  However, it is also possible to
 257 set \varname{[residue_begin]} and
 258 \varname{[residue_end]} to specify a range partially or
 259 wholly beyond the maximum vector size.  Before beginning residue
 260 decode, limit \varname{[residue_begin]} and
 261 \varname{[residue_end]} to the maximum possible vector size
 262 as follows.  We assume that the number of vectors being encoded,
 263 \varname{[ch]} is provided by the higher level decoding
 264 process.
 265
 266 \begin{programlisting}
 267   1) [actual_size] = current blocksize/2;
 268   2) if residue encoding is format 2
 269        3) [actual_size] = [actual_size] * [ch];
 270   4) [limit_residue_begin] = maximum of ([residue_begin],[actual_size]);
 271   5) [limit_residue_end] = maximum of ([residue_end],[actual_size]);
 272 \end{programlisting}
 273
 274 The following convenience values are conceptually useful to clarifying
 275 the decode process:
 276
 277 \begin{programlisting}
 278   1) [classwords_per_codeword] = [codebook_dimensions] value of codebook [residue_classbook]
 279   2) [n_to_read] = [limit_residue_end] - [limit_residue_begin]
 280   3) [partitions_to_read] = [n_to_read] / [residue_partition_size]
 281 \end{programlisting}
 282
 283 Packet decode proceeds as follows, matching the description offered earlier in the document.
 284 \begin{programlisting}
 285   1) allocate and zero all vectors that will be returned.
 286   2) if ([n_to_read] is zero), stop; there is no residue to decode.
 287   3) iterate [pass] over the range 0 ... 7 {
 288
 289        4) [partition_count] = 0
 290
 291        5) while [partition_count] is less than [partitions_to_read]
 292
 293             6) if ([pass] is zero) {
 294
 295                  7) iterate [j] over the range 0 .. [ch]-1 {
 296
 297                       8) if vector [j] is not marked 'do not decode' {
 298
 299                            9) [temp] = read from packet using codebook [residue_classbook] in scalar context
 300                           10) iterate [i] descending over the range [classwords_per_codeword]-1 ... 0 {
 301
 302                                11) array [classifications] element [j],([i]+[partition_count]) =
 303                                    [temp] integer modulo [residue_classifications]
 304                                12) [temp] = [temp] / [residue_classifications] using integer division
 305
 306                               }
 307
 308                          }
 309
 310                     }
 311
 312                }
 313
 314            13) iterate [i] over the range 0 .. ([classwords_per_codeword] - 1) while [partition_count]
 315                is also less than [partitions_to_read] {
 316
 317                  14) iterate [j] over the range 0 .. [ch]-1 {
 318
 319                       15) if vector [j] is not marked 'do not decode' {
 320
 321                            16) [vqclass] = array [classifications] element [j],[partition_count]
 322                            17) [vqbook] = array [residue_books] element [vqclass],[pass]
 323                            18) if ([vqbook] is not 'unused') {
 324
 325                                 19) decode partition into output vector number [j], starting at scalar
 326                                     offset [limit_residue_begin]+[partition_count]*[residue_partition_size] using
 327                                     codebook number [vqbook] in VQ context
 328                           }
 329                      }
 330
 331                  20) increment [partition_count] by one
 332
 333                }
 334           }
 335      }
 336
 337  21) done
 338
 339 \end{programlisting}
 340
 341 An end-of-packet condition during packet decode is to be considered a
 342 nominal occurrence.  Decode returns the result of vector decode up to
 343 that point.
 344
 345
 346
 347 \subsubsection{format 0 specifics}
 348
 349 Format zero decodes partitions exactly as described earlier in the
 350 'Residue Format: residue 0' section.  The following pseudocode
 351 presents the same algorithm. Assume:
 352
 353 \begin{itemize}
 354 \item  \varname{[n]} is the value in \varname{[residue_partition_size]}
 355 \item \varname{[v]} is the residue vector
 356 \item \varname{[offset]} is the beginning read offset in [v]
 357 \end{itemize}
 358
 359
 360 \begin{programlisting}
 361  1) [step] = [n] / [codebook_dimensions]
 362  2) iterate [i] over the range 0 ... [step]-1 {
 363
 364       3) vector [entry_temp] = read vector from packet using current codebook in VQ context
 365       4) iterate [j] over the range 0 ... [codebook_dimensions]-1 {
 366
 367            5) vector [v] element ([offset]+[i]+[j]*[step]) =
 368                 vector [v] element ([offset]+[i]+[j]*[step]) +
 369                 vector [entry_temp] element [j]
 370
 371          }
 372
 373     }
 374
 375   6) done
 376
 377 \end{programlisting}
 378
 379
 380
 381 \subsubsection{format 1 specifics}
 382
 383 Format 1 decodes partitions exactly as described earlier in the
 384 'Residue Format: residue 1' section.  The following pseudocode
 385 presents the same algorithm. Assume:
 386
 387 \begin{itemize}
 388 \item  \varname{[n]} is the value in
 389 \varname{[residue_partition_size]}
 390 \item \varname{[v]} is the residue vector
 391 \item \varname{[offset]} is the beginning read offset in [v]
 392 \end{itemize}
 393
 394
 395 \begin{programlisting}
 396  1) [i] = 0
 397  2) vector [entry_temp] = read vector from packet using current codebook in VQ context
 398  3) iterate [j] over the range 0 ... [codebook_dimensions]-1 {
 399
 400       4) vector [v] element ([offset]+[i]) =
 401           vector [v] element ([offset]+[i]) +
 402           vector [entry_temp] element [j]
 403       5) increment [i]
 404
 405     }
 406
 407   6) if ( [i] is less than [n] ) continue at step 2
 408   7) done
 409 \end{programlisting}
 410
 411
 412
 413 \subsubsection{format 2 specifics}
 414
 415 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.
 416
 417
 418 Format 2 handles 'do not decode' vectors differently than residue 0 or
 419 1; if all vectors are marked 'do not decode', no decode occurrs.
 420 However, if at least one vector is to be decoded, all the vectors are
 421 decoded.  We then request normal format 1 to decode a single vector
 422 representing all output channels, rather than a vector for each
 423 channel.  After decode, deinterleave the vector into independent vectors, one for each output channel.  That is:
 424
 425 \begin{enumerate}
 426  \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.
 427  \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}.
 428  \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:
 429   \begin{programlisting}
 430   1) iterate [i] over the range 0 ... [n]-1 {
 431
 432        2) iterate [j] over the range 0 ... [ch]-1 {
 433
 434             3) output vector number [j] element [i] = vector [v] element ([i] * [ch] + [j])
 435
 436           }
 437      }
 438
 439   4) done
 440   \end{programlisting}
 441
 442 \end{enumerate}
 443
 444
 445
 446
 447
 448
 449