doc/04-codec.tex

   1
   2 % -*- mode: latex; TeX-master: "Vorbis_I_spec"; -*-
   3 %!TEX root = Vorbis_I_spec.tex
   4 \section{Codec Setup and Packet Decode} \label{vorbis:spec:codec}
   5
   6 \subsection{Overview}
   7
   8 This document serves as the top-level reference document for the
   9 bit-by-bit decode specification of Vorbis I.  This document assumes a
  10 high-level understanding of the Vorbis decode process, which is
  11 provided in \xref{vorbis:spec:intro}.  \xref{vorbis:spec:bitpacking} covers reading and writing bit fields from
  12 and to bitstream packets.
  13
  14
  15
  16 \subsection{Header decode and decode setup}
  17
  18 A Vorbis bitstream begins with three header packets. The header
  19 packets are, in order, the identification header, the comments header,
  20 and the setup header. All are required for decode compliance.  An
  21 end-of-packet condition during decoding the first or third header
  22 packet renders the stream undecodable.  End-of-packet decoding the
  23 comment header is a non-fatal error condition.
  24
  25 \subsubsection{Common header decode}
  26
  27 Each header packet begins with the same header fields.
  28
  29
  30 \begin{Verbatim}[commandchars=\\\{\}]
  31   1) [packet\_type] : 8 bit value
  32   2) 0x76, 0x6f, 0x72, 0x62, 0x69, 0x73: the characters 'v','o','r','b','i','s' as six octets
  33 \end{Verbatim}
  34
  35 Decode continues according to packet type; the identification header
  36 is type 1, the comment header type 3 and the setup header type 5
  37 (these types are all odd as a packet with a leading single bit of '0'
  38 is an audio packet).  The packets must occur in the order of
  39 identification, comment, setup.
  40
  41
  42
  43 \subsubsection{Identification header}
  44
  45 The identification header is a short header of only a few fields used
  46 to declare the stream definitively as Vorbis, and provide a few externally
  47 relevant pieces of information about the audio stream. The
  48 identification header is coded as follows:
  49
  50 \begin{Verbatim}[commandchars=\\\{\}]
  51  1) [vorbis\_version] = read 32 bits as unsigned integer
  52  2) [audio\_channels] = read 8 bit integer as unsigned
  53  3) [audio\_sample\_rate] = read 32 bits as unsigned integer
  54  4) [bitrate\_maximum] = read 32 bits as signed integer
  55  5) [bitrate\_nominal] = read 32 bits as signed integer
  56  6) [bitrate\_minimum] = read 32 bits as signed integer
  57  7) [blocksize\_0] = 2 exponent (read 4 bits as unsigned integer)
  58  8) [blocksize\_1] = 2 exponent (read 4 bits as unsigned integer)
  59  9) [framing\_flag] = read one bit
  60 \end{Verbatim}
  61
  62 \varname{[vorbis\_version]} is to read '0' in order to be compatible
  63 with this document.  Both \varname{[audio\_channels]} and
  64 \varname{[audio\_sample\_rate]} must read greater than zero.  Allowed final
  65 blocksize values are 64, 128, 256, 512, 1024, 2048, 4096 and 8192 in
  66 Vorbis I.  \varname{[blocksize\_0]} must be less than or equal to
  67 \varname{[blocksize\_1]}.  The framing bit must be nonzero.  Failure to
  68 meet any of these conditions renders a stream undecodable.
  69
  70 The bitrate fields above are used only as hints. The nominal bitrate
  71 field especially may be considerably off in purely VBR streams.  The
  72 fields are meaningful only when greater than zero.
  73
  74 \begin{itemize}
  75   \item All three fields set to the same value implies a fixed rate, or tightly bounded, nearly fixed-rate bitstream
  76   \item Only nominal set implies a VBR or ABR stream that averages the nominal bitrate
  77   \item Maximum and or minimum set implies a VBR bitstream that obeys the bitrate limits
  78   \item None set indicates the encoder does not care to speculate.
  79 \end{itemize}
  80
  81
  82
  83
  84 \subsubsection{Comment header}
  85 Comment header decode and data specification is covered in
  86 \xref{vorbis:spec:comment}.
  87
  88
  89 \subsubsection{Setup header}
  90
  91 Vorbis codec setup is configurable to an extreme degree:
  92
  93 \begin{center}
  94 \includegraphics[width=\textwidth]{components}
  95 \captionof{figure}{decoder pipeline configuration}
  96 \end{center}
  97
  98
  99 The setup header contains the bulk of the codec setup information
 100 needed for decode.  The setup header contains, in order, the lists of
 101 codebook configurations, time-domain transform configurations
 102 (placeholders in Vorbis I), floor configurations, residue
 103 configurations, channel mapping configurations and mode
 104 configurations. It finishes with a framing bit of '1'.  Header decode
 105 proceeds in the following order:
 106
 107 \paragraph{Codebooks}
 108
 109 \begin{enumerate}
 110 \item \varname{[vorbis\_codebook\_count]} = read eight bits as unsigned integer and add one
 111 \item Decode \varname{[vorbis\_codebook\_count]} codebooks in order as defined
 112 in \xref{vorbis:spec:codebook}.  Save each configuration, in
 113 order, in an array of
 114 codebook configurations \varname{[vorbis\_codebook\_configurations]}.
 115 \end{enumerate}
 116
 117
 118
 119 \paragraph{Time domain transforms}
 120
 121 These hooks are placeholders in Vorbis I.  Nevertheless, the
 122 configuration placeholder values must be read to maintain bitstream
 123 sync.
 124
 125 \begin{enumerate}
 126 \item \varname{[vorbis\_time\_count]} = read 6 bits as unsigned integer and add one
 127 \item read \varname{[vorbis\_time\_count]} 16 bit values; each value should be zero.  If any value is nonzero, this is an error condition and the stream is undecodable.
 128 \end{enumerate}
 129
 130
 131
 132 \paragraph{Floors}
 133
 134 Vorbis uses two floor types; header decode is handed to the decode
 135 abstraction of the appropriate type.
 136
 137 \begin{enumerate}
 138  \item \varname{[vorbis\_floor\_count]} = read 6 bits as unsigned integer and add one
 139  \item For each \varname{[i]} of \varname{[vorbis\_floor\_count]} floor numbers:
 140   \begin{enumerate}
 141    \item read the floor type: vector \varname{[vorbis\_floor\_types]} element \varname{[i]} =
 142 read 16 bits as unsigned integer
 143    \item If the floor type is zero, decode the floor
 144 configuration as defined in \xref{vorbis:spec:floor0}; save
 145 this
 146 configuration in slot \varname{[i]} of the floor configuration array \varname{[vorbis\_floor\_configurations]}.
 147    \item If the floor type is one,
 148 decode the floor configuration as defined in \xref{vorbis:spec:floor1}; save this configuration in slot \varname{[i]} of the floor configuration array \varname{[vorbis\_floor\_configurations]}.
 149    \item If the the floor type is greater than one, this stream is undecodable; ERROR CONDITION
 150   \end{enumerate}
 151
 152 \end{enumerate}
 153
 154
 155
 156 \paragraph{Residues}
 157
 158 Vorbis uses three residue types; header decode of each type is identical.
 159
 160
 161 \begin{enumerate}
 162 \item \varname{[vorbis\_residue\_count]} = read 6 bits as unsigned integer and add one
 163
 164 \item For each of \varname{[vorbis\_residue\_count]} residue numbers:
 165  \begin{enumerate}
 166   \item read the residue type; vector \varname{[vorbis\_residue\_types]} element \varname{[i]} = read 16 bits as unsigned integer
 167   \item If the residue type is zero,
 168 one or two, decode the residue configuration as defined in \xref{vorbis:spec:residue}; save this configuration in slot \varname{[i]} of the residue configuration array \varname{[vorbis\_residue\_configurations]}.
 169   \item If the the residue type is greater than two, this stream is undecodable; ERROR CONDITION
 170  \end{enumerate}
 171
 172 \end{enumerate}
 173
 174
 175
 176 \paragraph{Mappings}
 177
 178 Mappings are used to set up specific pipelines for encoding
 179 multichannel audio with varying channel mapping applications. Vorbis I
 180 uses a single mapping type (0), with implicit PCM channel mappings.
 181
 182 % FIXME/TODO: LaTeX cannot nest enumerate that deeply, so I have to use
 183 % itemize at the innermost level. However, it would be much better to
 184 % rewrite this pseudocode using listings or algoritmicx or some other
 185 % package geared towards this.
 186 \begin{enumerate}
 187  \item \varname{[vorbis\_mapping\_count]} = read 6 bits as unsigned integer and add one
 188  \item For each \varname{[i]} of \varname{[vorbis\_mapping\_count]} mapping numbers:
 189   \begin{enumerate}
 190    \item read the mapping type: 16 bits as unsigned integer.  There's no reason to save the mapping type in Vorbis I.
 191    \item If the mapping type is nonzero, the stream is undecodable
 192    \item If the mapping type is zero:
 193     \begin{enumerate}
 194      \item read 1 bit as a boolean flag
 195       \begin{enumerate}
 196        \item if set, \varname{[vorbis\_mapping\_submaps]} = read 4 bits as unsigned integer and add one
 197        \item if unset, \varname{[vorbis\_mapping\_submaps]} = 1
 198       \end{enumerate}
 199
 200
 201      \item read 1 bit as a boolean flag
 202        \begin{enumerate}
 203          \item if set, square polar channel mapping is in use:
 204            \begin{itemize}
 205              \item \varname{[vorbis\_mapping\_coupling\_steps]} = read 8 bits as unsigned integer and add one
 206              \item for \varname{[j]} each of \varname{[vorbis\_mapping\_coupling\_steps]} steps:
 207                \begin{itemize}
 208                  \item vector \varname{[vorbis\_mapping\_magnitude]} element \varname{[j]}= read \link{vorbis:spec:ilog}{ilog}(\varname{[audio\_channels]} - 1) bits as unsigned integer
 209                  \item vector \varname{[vorbis\_mapping\_angle]} element \varname{[j]}= read \link{vorbis:spec:ilog}{ilog}(\varname{[audio\_channels]} - 1) bits as unsigned integer
 210                  \item the numbers read in the above two steps are channel numbers representing the channel to treat as magnitude and the channel to treat as angle, respectively.  If for any coupling step the angle channel number equals the magnitude channel number, the magnitude channel number is greater than \varname{[audio\_channels]}-1, or the angle channel is greater than \varname{[audio\_channels]}-1, the stream is undecodable.
 211                \end{itemize}
 212
 213
 214            \end{itemize}
 215
 216
 217          \item if unset, \varname{[vorbis\_mapping\_coupling\_steps]} = 0
 218        \end{enumerate}
 219
 220
 221      \item read 2 bits (reserved field); if the value is nonzero, the stream is undecodable
 222      \item if \varname{[vorbis\_mapping\_submaps]} is greater than one, we read channel multiplex settings. For each \varname{[j]} of \varname{[audio\_channels]} channels:
 223       \begin{enumerate}
 224        \item vector \varname{[vorbis\_mapping\_mux]} element \varname{[j]} = read 4 bits as unsigned integer
 225        \item if the value is greater than the highest numbered submap (\varname{[vorbis\_mapping\_submaps]} - 1), this in an error condition rendering the stream undecodable
 226       \end{enumerate}
 227
 228      \item for each submap \varname{[j]} of \varname{[vorbis\_mapping\_submaps]} submaps, read the floor and residue numbers for use in decoding that submap:
 229       \begin{enumerate}
 230        \item read and discard 8 bits (the unused time configuration placeholder)
 231        \item read 8 bits as unsigned integer for the floor number; save in vector \varname{[vorbis\_mapping\_submap\_floor]} element \varname{[j]}
 232        \item verify the floor number is not greater than the highest number floor configured for the bitstream. If it is, the bitstream is undecodable
 233        \item read 8 bits as unsigned integer for the residue number; save in vector \varname{[vorbis\_mapping\_submap\_residue]} element \varname{[j]}
 234        \item verify the residue number is not greater than the highest number residue configured for the bitstream.  If it is, the bitstream is undecodable
 235       \end{enumerate}
 236
 237      \item save this mapping configuration in slot \varname{[i]} of the mapping configuration array \varname{[vorbis\_mapping\_configurations]}.
 238     \end{enumerate}
 239
 240   \end{enumerate}
 241
 242 \end{enumerate}
 243
 244
 245
 246 \paragraph{Modes}
 247
 248 \begin{enumerate}
 249  \item \varname{[vorbis\_mode\_count]} = read 6 bits as unsigned integer and add one
 250  \item For each of \varname{[vorbis\_mode\_count]} mode numbers:
 251   \begin{enumerate}
 252   \item \varname{[vorbis\_mode\_blockflag]} = read 1 bit
 253   \item \varname{[vorbis\_mode\_windowtype]} = read 16 bits as unsigned integer
 254   \item \varname{[vorbis\_mode\_transformtype]} = read 16 bits as unsigned integer
 255   \item \varname{[vorbis\_mode\_mapping]} = read 8 bits as unsigned integer
 256   \item verify ranges; zero is the only legal value in Vorbis I for
 257 \varname{[vorbis\_mode\_windowtype]}
 258 and \varname{[vorbis\_mode\_transformtype]}.  \varname{[vorbis\_mode\_mapping]} must not be greater than the highest number mapping in use.  Any illegal values render the stream undecodable.
 259   \item save this mode configuration in slot \varname{[i]} of the mode configuration array
 260 \varname{[vorbis\_mode\_configurations]}.
 261  \end{enumerate}
 262
 263 \item read 1 bit as a framing flag.  If unset, a framing error occurred and the stream is not
 264 decodable.
 265 \end{enumerate}
 266
 267 After reading mode descriptions, setup header decode is complete.
 268
 269
 270
 271
 272
 273
 274
 275
 276 \subsection{Audio packet decode and synthesis}
 277
 278 Following the three header packets, all packets in a Vorbis I stream
 279 are audio.  The first step of audio packet decode is to read and
 280 verify the packet type. \emph{A non-audio packet when audio is expected
 281 indicates stream corruption or a non-compliant stream. The decoder
 282 must ignore the packet and not attempt decoding it to audio}.
 283
 284
 285 \subsubsection{packet type, mode and window decode}
 286
 287 \begin{enumerate}
 288  \item read 1 bit \varname{[packet\_type]}; check that packet type is 0 (audio)
 289  \item read \link{vorbis:spec:ilog}{ilog}([vorbis\_mode\_count]-1) bits
 290 \varname{[mode\_number]}
 291  \item decode blocksize \varname{[n]} is equal to \varname{[blocksize\_0]} if
 292 \varname{[vorbis\_mode\_blockflag]} is 0, else \varname{[n]} is equal to \varname{[blocksize\_1]}.
 293  \item perform window selection and setup; this window is used later by the inverse MDCT:
 294   \begin{enumerate}
 295    \item if this is a long window (the \varname{[vorbis\_mode\_blockflag]} flag of this mode is
 296 set):
 297     \begin{enumerate}
 298      \item read 1 bit for \varname{[previous\_window\_flag]}
 299      \item read 1 bit for \varname{[next\_window\_flag]}
 300      \item if \varname{[previous\_window\_flag]} is not set, the left half
 301          of the window will be a hybrid window for lapping with a
 302          short block.  See \xref{vorbis:spec:window} for an illustration of overlapping
 303 dissimilar
 304          windows. Else, the left half window will have normal long
 305          shape.
 306      \item if \varname{[next\_window\_flag]} is not set, the right half of
 307          the window will be a hybrid window for lapping with a short
 308          block.  See \xref{vorbis:spec:window} for an
 309 illustration of overlapping dissimilar
 310          windows. Else, the left right window will have normal long
 311          shape.
 312     \end{enumerate}
 313
 314    \item  if this is a short window, the window is always the same
 315        short-window shape.
 316   \end{enumerate}
 317
 318 \end{enumerate}
 319
 320 Vorbis windows all use the slope function $y=\sin(\frac{\pi}{2} * \sin^2((x+0.5)/n * \pi))$,
 321 where $n$ is window size and $x$ ranges $0 \ldots n-1$, but dissimilar
 322 lapping requirements can affect overall shape.  Window generation
 323 proceeds as follows:
 324
 325 \begin{enumerate}
 326  \item  \varname{[window\_center]} = \varname{[n]} / 2
 327  \item  if (\varname{[vorbis\_mode\_blockflag]} is set and \varname{[previous\_window\_flag]} is
 328 not set) then
 329   \begin{enumerate}
 330    \item \varname{[left\_window\_start]} = \varname{[n]}/4 -
 331 \varname{[blocksize\_0]}/4
 332    \item \varname{[left\_window\_end]} = \varname{[n]}/4 + \varname{[blocksize\_0]}/4
 333    \item \varname{[left\_n]} = \varname{[blocksize\_0]}/2
 334   \end{enumerate}
 335  else
 336   \begin{enumerate}
 337    \item \varname{[left\_window\_start]} = 0
 338    \item \varname{[left\_window\_end]} = \varname{[window\_center]}
 339    \item \varname{[left\_n]} = \varname{[n]}/2
 340   \end{enumerate}
 341
 342  \item  if (\varname{[vorbis\_mode\_blockflag]} is set and \varname{[next\_window\_flag]} is not
 343 set) then
 344   \begin{enumerate}
 345    \item \varname{[right\_window\_start]} = \varname{[n]*3}/4 -
 346 \varname{[blocksize\_0]}/4
 347    \item \varname{[right\_window\_end]} = \varname{[n]*3}/4 +
 348 \varname{[blocksize\_0]}/4
 349    \item \varname{[right\_n]} = \varname{[blocksize\_0]}/2
 350   \end{enumerate}
 351  else
 352   \begin{enumerate}
 353    \item \varname{[right\_window\_start]} = \varname{[window\_center]}
 354    \item \varname{[right\_window\_end]} = \varname{[n]}
 355    \item \varname{[right\_n]} = \varname{[n]}/2
 356   \end{enumerate}
 357
 358  \item  window from range 0 ... \varname{[left\_window\_start]}-1 inclusive is zero
 359  \item  for \varname{[i]} in range \varname{[left\_window\_start]} ...
 360 \varname{[left\_window\_end]}-1, window(\varname{[i]}) = $\sin(\frac{\pi}{2} * \sin^2($ (\varname{[i]}-\varname{[left\_window\_start]}+0.5) / \varname{[left\_n]} $* \frac{\pi}{2})$ )
 361  \item  window from range \varname{[left\_window\_end]} ... \varname{[right\_window\_start]}-1
 362 inclusive is one\item  for \varname{[i]} in range \varname{[right\_window\_start]} ... \varname{[right\_window\_end]}-1, window(\varname{[i]}) = $\sin(\frac{\pi}{2} * \sin^2($ (\varname{[i]}-\varname{[right\_window\_start]}+0.5) / \varname{[right\_n]} $ * \frac{\pi}{2} + \frac{\pi}{2})$ )
 363 \item  window from range \varname{[right\_window\_start]} ... \varname{[n]}-1 is
 364 zero
 365 \end{enumerate}
 366
 367 An end-of-packet condition up to this point should be considered an
 368 error that discards this packet from the stream.  An end of packet
 369 condition past this point is to be considered a possible nominal
 370 occurrence.
 371
 372
 373
 374 \subsubsection{floor curve decode}
 375
 376 From this point on, we assume out decode context is using mode number
 377 \varname{[mode\_number]} from configuration array
 378 \varname{[vorbis\_mode\_configurations]} and the map number
 379 \varname{[vorbis\_mode\_mapping]} (specified by the current mode) taken
 380 from the mapping configuration array
 381 \varname{[vorbis\_mapping\_configurations]}.
 382
 383 Floor curves are decoded one-by-one in channel order.
 384
 385 For each floor \varname{[i]} of \varname{[audio\_channels]}
 386  \begin{enumerate}
 387   \item \varname{[submap\_number]} = element \varname{[i]} of vector [vorbis\_mapping\_mux]
 388   \item \varname{[floor\_number]} = element \varname{[submap\_number]} of vector
 389 [vorbis\_submap\_floor]
 390   \item if the floor type of this
 391 floor (vector \varname{[vorbis\_floor\_types]} element
 392 \varname{[floor\_number]}) is zero then decode the floor for
 393 channel \varname{[i]} according to the
 394 \xref{vorbis:spec:floor0-decode}
 395   \item if the type of this floor
 396 is one then decode the floor for channel \varname{[i]} according
 397 to the \xref{vorbis:spec:floor1-decode}
 398   \item save the needed decoded floor information for channel for later synthesis
 399   \item if the decoded floor returned 'unused', set vector \varname{[no\_residue]} element
 400 \varname{[i]} to true, else set vector \varname{[no\_residue]} element \varname{[i]} to
 401 false
 402  \end{enumerate}
 403
 404
 405 An end-of-packet condition during floor decode shall result in packet
 406 decode zeroing all channel output vectors and skipping to the
 407 add/overlap output stage.
 408
 409
 410
 411 \subsubsection{nonzero vector propagate}
 412
 413 A possible result of floor decode is that a specific vector is marked
 414 'unused' which indicates that that final output vector is all-zero
 415 values (and the floor is zero).  The residue for that vector is not
 416 coded in the stream, save for one complication.  If some vectors are
 417 used and some are not, channel coupling could result in mixing a
 418 zeroed and nonzeroed vector to produce two nonzeroed vectors.
 419
 420 for each \varname{[i]} from 0 ... \varname{[vorbis\_mapping\_coupling\_steps]}-1
 421
 422 \begin{enumerate}
 423  \item if either \varname{[no\_residue]} entry for channel
 424 (\varname{[vorbis\_mapping\_magnitude]} element \varname{[i]})
 425 or channel
 426 (\varname{[vorbis\_mapping\_angle]} element \varname{[i]})
 427 are set to false, then both must be set to false.  Note that an 'unused'
 428 floor has no decoded floor information; it is important that this is
 429 remembered at floor curve synthesis time.
 430 \end{enumerate}
 431
 432
 433
 434
 435 \subsubsection{residue decode}
 436
 437 Unlike floors, which are decoded in channel order, the residue vectors
 438 are decoded in submap order.
 439
 440 for each submap \varname{[i]} in order from 0 ... \varname{[vorbis\_mapping\_submaps]}-1
 441
 442 \begin{enumerate}
 443  \item \varname{[ch]} = 0
 444  \item for each channel \varname{[j]} in order from 0 ... \varname{[audio\_channels]} - 1
 445   \begin{enumerate}
 446    \item if channel \varname{[j]} in submap \varname{[i]} (vector \varname{[vorbis\_mapping\_mux]} element \varname{[j]} is equal to \varname{[i]})
 447     \begin{enumerate}
 448      \item if vector \varname{[no\_residue]} element \varname{[j]} is true
 449       \begin{enumerate}
 450        \item vector \varname{[do\_not\_decode\_flag]} element \varname{[ch]} is set
 451       \end{enumerate}
 452      else
 453       \begin{enumerate}
 454        \item vector \varname{[do\_not\_decode\_flag]} element \varname{[ch]} is unset
 455       \end{enumerate}
 456
 457      \item increment \varname{[ch]}
 458     \end{enumerate}
 459
 460   \end{enumerate}
 461  \item \varname{[residue\_number]} = vector \varname{[vorbis\_mapping\_submap\_residue]} element \varname{[i]}
 462  \item \varname{[residue\_type]} = vector \varname{[vorbis\_residue\_types]} element \varname{[residue\_number]}
 463  \item decode \varname{[ch]} vectors using residue \varname{[residue\_number]}, according to type \varname{[residue\_type]}, also passing vector \varname{[do\_not\_decode\_flag]} to indicate which vectors in the bundle should not be decoded. Correct per-vector decode length is \varname{[n]}/2.
 464  \item \varname{[ch]} = 0
 465  \item for each channel \varname{[j]} in order from 0 ... \varname{[audio\_channels]}
 466   \begin{enumerate}
 467    \item if channel \varname{[j]} is in submap \varname{[i]} (vector \varname{[vorbis\_mapping\_mux]} element \varname{[j]} is equal to \varname{[i]})
 468     \begin{enumerate}
 469      \item residue vector for channel \varname{[j]} is set to decoded residue vector \varname{[ch]}
 470      \item increment \varname{[ch]}
 471     \end{enumerate}
 472
 473   \end{enumerate}
 474
 475 \end{enumerate}
 476
 477
 478
 479 \subsubsection{inverse coupling}
 480
 481 for each \varname{[i]} from \varname{[vorbis\_mapping\_coupling\_steps]}-1 descending to 0
 482
 483 \begin{enumerate}
 484  \item \varname{[magnitude\_vector]} = the residue vector for channel
 485 (vector \varname{[vorbis\_mapping\_magnitude]} element \varname{[i]})
 486  \item \varname{[angle\_vector]} = the residue vector for channel (vector
 487 \varname{[vorbis\_mapping\_angle]} element \varname{[i]})
 488  \item for each scalar value \varname{[M]} in vector \varname{[magnitude\_vector]} and the corresponding scalar value \varname{[A]} in vector \varname{[angle\_vector]}:
 489   \begin{enumerate}
 490    \item if (\varname{[M]} is greater than zero)
 491     \begin{enumerate}
 492      \item if (\varname{[A]} is greater than zero)
 493       \begin{enumerate}
 494        \item \varname{[new\_M]} = \varname{[M]}
 495        \item \varname{[new\_A]} = \varname{[M]}-\varname{[A]}
 496       \end{enumerate}
 497      else
 498       \begin{enumerate}
 499        \item \varname{[new\_A]} = \varname{[M]}
 500        \item \varname{[new\_M]} = \varname{[M]}+\varname{[A]}
 501       \end{enumerate}
 502
 503     \end{enumerate}
 504    else
 505     \begin{enumerate}
 506      \item if (\varname{[A]} is greater than zero)
 507       \begin{enumerate}
 508        \item \varname{[new\_M]} = \varname{[M]}
 509        \item \varname{[new\_A]} = \varname{[M]}+\varname{[A]}
 510       \end{enumerate}
 511      else
 512       \begin{enumerate}
 513        \item \varname{[new\_A]} = \varname{[M]}
 514        \item \varname{[new\_M]} = \varname{[M]}-\varname{[A]}
 515       \end{enumerate}
 516
 517     \end{enumerate}
 518
 519    \item set scalar value \varname{[M]} in vector \varname{[magnitude\_vector]} to \varname{[new\_M]}
 520    \item set scalar value \varname{[A]} in vector \varname{[angle\_vector]} to \varname{[new\_A]}
 521   \end{enumerate}
 522
 523 \end{enumerate}
 524
 525
 526
 527
 528 \subsubsection{dot product}
 529
 530 For each channel, synthesize the floor curve from the decoded floor
 531 information, according to packet type. Note that the vector synthesis
 532 length for floor computation is \varname{[n]}/2.
 533
 534 For each channel, multiply each element of the floor curve by each
 535 element of that channel's residue vector.  The result is the dot
 536 product of the floor and residue vectors for each channel; the produced
 537 vectors are the length \varname{[n]}/2 audio spectrum for each
 538 channel.
 539
 540 % TODO/FIXME: The following two paragraphs have identical twins
 541 %   in section 1 (under "compute floor/residue dot product")
 542 One point is worth mentioning about this dot product; a common mistake
 543 in a fixed point implementation might be to assume that a 32 bit
 544 fixed-point representation for floor and residue and direct
 545 multiplication of the vectors is sufficient for acceptable spectral
 546 depth in all cases because it happens to mostly work with the current
 547 Xiph.Org reference encoder.
 548
 549 However, floor vector values can span \~140dB (\~24 bits unsigned), and
 550 the audio spectrum vector should represent a minimum of 120dB (\~21
 551 bits with sign), even when output is to a 16 bit PCM device.  For the
 552 residue vector to represent full scale if the floor is nailed to
 553 $-140$dB, it must be able to span 0 to $+140$dB.  For the residue vector
 554 to reach full scale if the floor is nailed at 0dB, it must be able to
 555 represent $-140$dB to $+0$dB.  Thus, in order to handle full range
 556 dynamics, a residue vector may span $-140$dB to $+140$dB entirely within
 557 spec.  A 280dB range is approximately 48 bits with sign; thus the
 558 residue vector must be able to represent a 48 bit range and the dot
 559 product must be able to handle an effective 48 bit times 24 bit
 560 multiplication.  This range may be achieved using large (64 bit or
 561 larger) integers, or implementing a movable binary point
 562 representation.
 563
 564
 565
 566 \subsubsection{inverse MDCT}
 567
 568 Convert the audio spectrum vector of each channel back into time
 569 domain PCM audio via an inverse Modified Discrete Cosine Transform
 570 (MDCT).  A detailed description of the MDCT is available in \cite{Sporer/Brandenburg/Edler}.  The window
 571 function used for the MDCT is the function described earlier.
 572
 573
 574
 575 \subsubsection{overlap\_add}
 576
 577 Windowed MDCT output is overlapped and added with the right hand data
 578 of the previous window such that the 3/4 point of the previous window
 579 is aligned with the 1/4 point of the current window (as illustrated in
 580 \xref{vorbis:spec:window}).  The overlapped portion
 581 produced from overlapping the previous and current frame data is
 582 finished data to be returned by the decoder.  This data spans from the
 583 center of the previous window to the center of the current window.  In
 584 the case of same-sized windows, the amount of data to return is
 585 one-half block consisting of and only of the overlapped portions. When
 586 overlapping a short and long window, much of the returned range does not
 587 actually overlap.  This does not damage transform orthogonality.  Pay
 588 attention however to returning the correct data range; the amount of
 589 data to be returned is:
 590
 591 \begin{programlisting}
 592 window_blocksize(previous_window)/4+window_blocksize(current_window)/4
 593 \end{programlisting}
 594
 595 from the center (element windowsize/2) of the previous window to the
 596 center (element windowsize/2-1, inclusive) of the current window.
 597
 598 Data is not returned from the first frame; it must be used to 'prime'
 599 the decode engine.  The encoder accounts for this priming when
 600 calculating PCM offsets; after the first frame, the proper PCM output
 601 offset is '0' (as no data has been returned yet).
 602
 603
 604
 605 \subsubsection{output channel order}
 606
 607 Vorbis I specifies only a channel mapping type 0.  In mapping type 0,
 608 channel mapping is implicitly defined as follows for standard audio
 609 applications. As of revision 16781 (20100113), the specification adds
 610 defined channel locations for 6.1 and 7.1 surround.  Ordering/location
 611 for greater-than-eight channels remains 'left to the implementation'.
 612
 613 These channel orderings refer to order within the encoded stream.  It
 614 is naturally possible for a decoder to produce output with channels in
 615 any order. Any such decoder should explicitly document channel
 616 reordering behavior.
 617
 618 \begin{description} %[style=nextline]
 619  \item[one channel]
 620         the stream is monophonic
 621
 622 \item[two channels]
 623         the stream is stereo.  channel order: left, right
 624
 625 \item[three channels]
 626         the stream is a 1d-surround encoding.  channel order: left,
 627 center, right
 628
 629 \item[four channels]
 630         the stream is quadraphonic surround.  channel order: front left,
 631 front right, rear left, rear right
 632
 633 \item[five channels]
 634         the stream is five-channel surround.  channel order: front left,
 635 center, front right, rear left, rear right
 636
 637 \item[six channels]
 638         the stream is 5.1 surround.  channel order: front left, center,
 639 front right, rear left, rear right, LFE
 640
 641 \item[seven channels]
 642         the stream is 6.1 surround.  channel order: front left, center,
 643 front right, side left, side right, rear center, LFE
 644
 645 \item[eight channels]
 646         the stream is 7.1 surround.  channel order: front left, center,
 647 front right, side left, side right, rear left, rear right,
 648 LFE
 649
 650 \item[greater than eight channels]
 651         channel use and order is defined by the application
 652
 653 \end{description}
 654
 655 Applications using Vorbis for dedicated purposes may define channel
 656 mapping as seen fit.  Future channel mappings (such as three and four
 657 channel \href{http://www.ambisonic.net/}{Ambisonics}) will
 658 make use of channel mappings other than mapping 0.
 659
 660