doc/Vorbis_I_spec.html

   1 <html><head><meta http-equiv="Content-Type" content="text/html; charset=ISO-8859-1"><title>Vorbis I specification</title><meta name="generator" content="DocBook XSL Stylesheets V1.72.0"></head><body bgcolor="white" text="black" link="#0000FF" vlink="#840084" alink="#0000FF"><div class="article" lang="en"><div class="titlepage"><div><div><h1 class="title"><a name="id209753"></a>Vorbis I specification</h1></div><div><h3 class="corpauthor">Xiph.org Foundation</h3></div></div><hr></div><div class="toc"><p><b>Table of Contents</b></p><dl><dt><span class="section"><a href="#vorbis-spec-intro">1. Introduction and Description</a></span></dt><dd><dl><dt><span class="section"><a href="#id322780">1.1. Overview</a></span></dt><dt><span class="section"><a href="#id256749">1.2. Decoder Configuration</a></span></dt><dt><span class="section"><a href="#id257049">1.3. High-level Decode Process</a></span></dt></dl></dd><dt><span class="section"><a href="#vorbis-spec-bitpacking">2. Bitpacking Convention</a></span></dt><dd><dl><dt><span class="section"><a href="#id316853">2.1. Overview</a></span></dt></dl></dd><dt><span class="section"><a href="#vorbis-spec-codebook">3. Probability Model and Codebooks</a></span></dt><dd><dl><dt><span class="section"><a href="#id326636">3.1. Overview</a></span></dt><dt><span class="section"><a href="#id329366">3.2. Packed codebook format</a></span></dt><dt><span class="section"><a href="#id320654">3.3. Use of the codebook abstraction</a></span></dt></dl></dd><dt><span class="section"><a href="#vorbis-spec-codec">4. Codec Setup and Packet Decode</a></span></dt><dd><dl><dt><span class="section"><a href="#id332455">4.1. Overview</a></span></dt><dt><span class="section"><a href="#id332825">4.2. Header decode and decode setup</a></span></dt><dt><span class="section"><a href="#id341314">4.3. Audio packet decode and synthesis</a></span></dt></dl></dd><dt><span class="section"><a href="#vorbis-spec-comment">5. comment field and header specification</a></span></dt><dd><dl><dt><span class="section"><a href="#id333629">5.1. Overview</a></span></dt><dt><span class="section"><a href="#id333657">5.2. Comment encoding</a></span></dt></dl></dd><dt><span class="section"><a href="#vorbis-spec-floor0">6. Floor type 0 setup and decode</a></span></dt><dd><dl><dt><span class="section"><a href="#id320318">6.1. Overview</a></span></dt><dt><span class="section"><a href="#id324407">6.2. Floor 0 format</a></span></dt></dl></dd><dt><span class="section"><a href="#vorbis-spec-floor1">7. Floor type 1 setup and decode</a></span></dt><dd><dl><dt><span class="section"><a href="#id321969">7.1. Overview</a></span></dt><dt><span class="section"><a href="#id315653">7.2. Floor 1 format</a></span></dt></dl></dd><dt><span class="section"><a href="#vorbis-spec-residue">8. Residue setup and decode</a></span></dt><dd><dl><dt><span class="section"><a href="#id333002">8.1. Overview</a></span></dt><dt><span class="section"><a href="#id327769">8.2. Residue format</a></span></dt><dt><span class="section"><a href="#id318469">8.3. residue 0</a></span></dt><dt><span class="section"><a href="#id343071">8.4. residue 1</a></span></dt><dt><span class="section"><a href="#id343096">8.5. residue 2</a></span></dt><dt><span class="section"><a href="#id343145">8.6. Residue decode</a></span></dt></dl></dd><dt><span class="section"><a href="#vorbis-spec-helper">9. Helper equations</a></span></dt><dd><dl><dt><span class="section"><a href="#id325073">9.1. Overview</a></span></dt><dt><span class="section"><a href="#id306980">9.2. Functions</a></span></dt></dl></dd><dt><span class="section"><a href="#vorbis-spec-tables">10. Tables</a></span></dt><dd><dl><dt><span class="section"><a href="#vorbis-spec-floor1_inverse_dB_table">10.1. floor1_inverse_dB_table</a></span></dt></dl></dd><dt><span class="appendix"><a href="#vorbis-over-ogg">1. Embedding Vorbis into an Ogg stream</a></span></dt><dd><dl><dt><span class="section"><a href="#id312362">1.1. Overview</a></span></dt><dd><dl><dt><span class="section"><a href="#id336032">1.1.1. Restrictions</a></span></dt><dt><span class="section"><a href="#id319459">1.1.2. MIME type</a></span></dt></dl></dd><dt><span class="section"><a href="#id317588">1.2. Encapsulation</a></span></dt></dl></dd><dt><span class="appendix"><a href="#vorbis-over-rtp">2. Vorbis encapsulation in RTP</a></span></dt><dt><span class="appendix"><a href="#footer">3. Colophon</a></span></dt></dl></div><div class="section" lang="en"><div class="titlepage"><div><div><h2 class="title" style="clear: both"><a name="vorbis-spec-intro"></a>1. Introduction and Description</h2></div><div><p class="releaseinfo">
   2  $Id: 01-introduction.xml 7186 2004-07-20 07:19:25Z xiphmont $
   3 </p></div></div></div><div class="section" lang="en"><div class="titlepage"><div><div><h3 class="title"><a name="id322780"></a>1.1. Overview</h3></div></div></div><p>
   4 This document provides a high level description of the Vorbis codec's
   5 construction.  A bit-by-bit specification appears beginning in
   6 <a href="#vorbis-spec-codec" title="4. Codec Setup and Packet Decode">Section 4, &#8220;Codec Setup and Packet Decode&#8221;</a>.
   7 The later sections assume a high-level
   8 understanding of the Vorbis decode process, which is
   9 provided here.</p><div class="section" lang="en"><div class="titlepage"><div><div><h4 class="title"><a name="id315215"></a>1.1.1. Application</h4></div></div></div><p>
  10 Vorbis is a general purpose perceptual audio CODEC intended to allow
  11 maximum encoder flexibility, thus allowing it to scale competitively
  12 over an exceptionally wide range of bitrates.  At the high
  13 quality/bitrate end of the scale (CD or DAT rate stereo, 16/24 bits)
  14 it is in the same league as MPEG-2 and MPC.  Similarly, the 1.0
  15 encoder can encode high-quality CD and DAT rate stereo at below 48kbps
  16 without resampling to a lower rate.  Vorbis is also intended for
  17 lower and higher sample rates (from 8kHz telephony to 192kHz digital
  18 masters) and a range of channel representations (monaural,
  19 polyphonic, stereo, quadraphonic, 5.1, ambisonic, or up to 255
  20 discrete channels).
  21 </p></div><div class="section" lang="en"><div class="titlepage"><div><div><h4 class="title"><a name="id323065"></a>1.1.2. Classification</h4></div></div></div><p>
  22 Vorbis I is a forward-adaptive monolithic transform CODEC based on the
  23 Modified Discrete Cosine Transform.  The codec is structured to allow
  24 addition of a hybrid wavelet filterbank in Vorbis II to offer better
  25 transient response and reproduction using a transform better suited to
  26 localized time events.
  27 </p></div><div class="section" lang="en"><div class="titlepage"><div><div><h4 class="title"><a name="id322056"></a>1.1.3. Assumptions</h4></div></div></div><p>
  28 The Vorbis CODEC design assumes a complex, psychoacoustically-aware
  29 encoder and simple, low-complexity decoder. Vorbis decode is
  30 computationally simpler than mp3, although it does require more
  31 working memory as Vorbis has no static probability model; the vector
  32 codebooks used in the first stage of decoding from the bitstream are
  33 packed in their entirety into the Vorbis bitstream headers. In
  34 packed form, these codebooks occupy only a few kilobytes; the extent
  35 to which they are pre-decoded into a cache is the dominant factor in
  36 decoder memory usage.
  37 </p><p>
  38 Vorbis provides none of its own framing, synchronization or protection
  39 against errors; it is solely a method of accepting input audio,
  40 dividing it into individual frames and compressing these frames into
  41 raw, unformatted 'packets'. The decoder then accepts these raw
  42 packets in sequence, decodes them, synthesizes audio frames from
  43 them, and reassembles the frames into a facsimile of the original
  44 audio stream. Vorbis is a free-form variable bit rate (VBR) codec and packets have no
  45 minimum size, maximum size, or fixed/expected size.  Packets
  46 are designed that they may be truncated (or padded) and remain
  47 decodable; this is not to be considered an error condition and is used
  48 extensively in bitrate management in peeling.  Both the transport
  49 mechanism and decoder must allow that a packet may be any size, or
  50 end before or after packet decode expects.</p><p>
  51 Vorbis packets are thus intended to be used with a transport mechanism
  52 that provides free-form framing, sync, positioning and error correction
  53 in accordance with these design assumptions, such as Ogg (for file
  54 transport) or RTP (for network multicast).  For purposes of a few
  55 examples in this document, we will assume that Vorbis is to be
  56 embedded in an Ogg stream specifically, although this is by no means a
  57 requirement or fundamental assumption in the Vorbis design.</p><p>
  58 The specification for embedding Vorbis into
  59 an Ogg transport stream is in <a href="#vorbis-over-ogg" title="1. Embedding Vorbis into an Ogg stream">Appendix 1, <i>Embedding Vorbis into an Ogg stream</i></a>.
  60 </p></div><div class="section" lang="en"><div class="titlepage"><div><div><h4 class="title"><a name="id337302"></a>1.1.4. Codec Setup and Probability Model</h4></div></div></div><p>
  61 Vorbis' heritage is as a research CODEC and its current design
  62 reflects a desire to allow multiple decades of continuous encoder
  63 improvement before running out of room within the codec specification.
  64 For these reasons, configurable aspects of codec setup intentionally
  65 lean toward the extreme of forward adaptive.</p><p>
  66 The single most controversial design decision in Vorbis (and the most
  67 unusual for a Vorbis developer to keep in mind) is that the entire
  68 probability model of the codec, the Huffman and VQ codebooks, is
  69 packed into the bitstream header along with extensive CODEC setup
  70 parameters (often several hundred fields).  This makes it impossible,
  71 as it would be with MPEG audio layers, to embed a simple frame type
  72 flag in each audio packet, or begin decode at any frame in the stream
  73 without having previously fetched the codec setup header.
  74 </p><div class="note" style="margin-left: 0.5in; margin-right: 0.5in;"><h3 class="title">Note</h3><p>
  75 Vorbis <span class="emphasis"><em>can</em></span> initiate decode at any arbitrary packet within a
  76 bitstream so long as the codec has been initialized/setup with the
  77 setup headers.</p></div><p>
  78 Thus, Vorbis headers are both required for decode to begin and
  79 relatively large as bitstream headers go.  The header size is
  80 unbounded, although for streaming a rule-of-thumb of 4kB or less is
  81 recommended (and Xiph.Org's Vorbis encoder follows this suggestion).</p><p>
  82 Our own design work indicates the primary liability of the
  83 required header is in mindshare; it is an unusual design and thus
  84 causes some amount of complaint among engineers as this runs against
  85 current design trends (and also points out limitations in some
  86 existing software/interface designs, such as Windows' ACM codec
  87 framework).  However, we find that it does not fundamentally limit
  88 Vorbis' suitable application space.</p></div><div class="section" lang="en"><div class="titlepage"><div><div><h4 class="title"><a name="id256723"></a>1.1.5. Format Specification</h4></div></div></div><p>
  89 The Vorbis format is well-defined by its decode specification; any
  90 encoder that produces packets that are correctly decoded by the
  91 reference Vorbis decoder described below may be considered a proper
  92 Vorbis encoder.  A decoder must faithfully and completely implement
  93 the specification defined below (except where noted) to be considered
  94 a proper Vorbis decoder.</p></div><div class="section" lang="en"><div class="titlepage"><div><div><h4 class="title"><a name="id256735"></a>1.1.6. Hardware Profile</h4></div></div></div><p>
  95 Although Vorbis decode is computationally simple, it may still run
  96 into specific limitations of an embedded design.  For this reason,
  97 embedded designs are allowed to deviate in limited ways from the
  98 'full' decode specification yet still be certified compliant.  These
  99 optional omissions are labelled in the spec where relevant.</p></div></div><div class="section" lang="en"><div class="titlepage"><div><div><h3 class="title"><a name="id256749"></a>1.2. Decoder Configuration</h3></div></div></div><p>
 100 Decoder setup consists of configuration of multiple, self-contained
 101 component abstractions that perform specific functions in the decode
 102 pipeline.  Each different component instance of a specific type is
 103 semantically interchangeable; decoder configuration consists both of
 104 internal component configuration, as well as arrangement of specific
 105 instances into a decode pipeline.  Componentry arrangement is roughly
 106 as follows:</p><div class="mediaobject"><img src="components.png" alt="decoder pipeline configuration"></div><div class="section" lang="en"><div class="titlepage"><div><div><h4 class="title"><a name="id322835"></a>1.2.1. Global Config</h4></div></div></div><p>
 107 Global codec configuration consists of a few audio related fields
 108 (sample rate, channels), Vorbis version (always '0' in Vorbis I),
 109 bitrate hints, and the lists of component instances.  All other
 110 configuration is in the context of specific components.</p></div><div class="section" lang="en"><div class="titlepage"><div><div><h4 class="title"><a name="id323931"></a>1.2.2. Mode</h4></div></div></div><p>
 111 Each Vorbis frame is coded according to a master 'mode'.  A bitstream
 112 may use one or many modes.</p><p>
 113 The mode mechanism is used to encode a frame according to one of
 114 multiple possible methods with the intention of choosing a method best
 115 suited to that frame.  Different modes are, e.g. how frame size
 116 is changed from frame to frame. The mode number of a frame serves as a
 117 top level configuration switch for all other specific aspects of frame
 118 decode.</p><p>
 119 A 'mode' configuration consists of a frame size setting, window type
 120 (always 0, the Vorbis window, in Vorbis I), transform type (always
 121 type 0, the MDCT, in Vorbis I) and a mapping number.  The mapping
 122 number specifies which mapping configuration instance to use for
 123 low-level packet decode and synthesis.</p></div><div class="section" lang="en"><div class="titlepage"><div><div><h4 class="title"><a name="id256947"></a>1.2.3. Mapping</h4></div></div></div><p>
 124 A mapping contains a channel coupling description and a list of
 125 'submaps' that bundle sets of channel vectors together for grouped
 126 encoding and decoding. These submaps are not references to external
 127 components; the submap list is internal and specific to a mapping.</p><p>
 128 A 'submap' is a configuration/grouping that applies to a subset of
 129 floor and residue vectors within a mapping.  The submap functions as a
 130 last layer of indirection such that specific special floor or residue
 131 settings can be applied not only to all the vectors in a given mode,
 132 but also specific vectors in a specific mode.  Each submap specifies
 133 the proper floor and residue instance number to use for decoding that
 134 submap's spectral floor and spectral residue vectors.</p><p>
 135 As an example:</p><p>
 136 Assume a Vorbis stream that contains six channels in the standard 5.1
 137 format.  The sixth channel, as is normal in 5.1, is bass only.
 138 Therefore it would be wasteful to encode a full-spectrum version of it
 139 as with the other channels.  The submapping mechanism can be used to
 140 apply a full range floor and residue encoding to channels 0 through 4,
 141 and a bass-only representation to the bass channel, thus saving space.
 142 In this example, channels 0-4 belong to submap 0 (which indicates use
 143 of a full-range floor) and channel 5 belongs to submap 1, which uses a
 144 bass-only representation.</p></div><div class="section" lang="en"><div class="titlepage"><div><div><h4 class="title"><a name="id256978"></a>1.2.4. Floor</h4></div></div></div><p>
 145 Vorbis encodes a spectral 'floor' vector for each PCM channel.  This
 146 vector is a low-resolution representation of the audio spectrum for
 147 the given channel in the current frame, generally used akin to a
 148 whitening filter.  It is named a 'floor' because the Xiph.Org
 149 reference encoder has historically used it as a unit-baseline for
 150 spectral resolution.</p><p>
 151 A floor encoding may be of two types.  Floor 0 uses a packed LSP
 152 representation on a dB amplitude scale and Bark frequency scale.
 153 Floor 1 represents the curve as a piecewise linear interpolated
 154 representation on a dB amplitude scale and linear frequency scale.
 155 The two floors are semantically interchangeable in
 156 encoding/decoding. However, floor type 1 provides more stable
 157 inter-frame behavior, and so is the preferred choice in all
 158 coupled-stereo and high bitrate modes.  Floor 1 is also considerably
 159 less expensive to decode than floor 0.</p><p>
 160 Floor 0 is not to be considered deprecated, but it is of limited
 161 modern use.  No known Vorbis encoder past Xiph.org's own beta 4 makes
 162 use of floor 0.</p><p>
 163 The values coded/decoded by a floor are both compactly formatted and
 164 make use of entropy coding to save space.  For this reason, a floor
 165 configuration generally refers to multiple codebooks in the codebook
 166 component list.  Entropy coding is thus provided as an abstraction,
 167 and each floor instance may choose from any and all available
 168 codebooks when coding/decoding.</p></div><div class="section" lang="en"><div class="titlepage"><div><div><h4 class="title"><a name="id257011"></a>1.2.5. Residue</h4></div></div></div><p>
 169 The spectral residue is the fine structure of the audio spectrum
 170 once the floor curve has been subtracted out.  In simplest terms, it
 171 is coded in the bitstream using cascaded (multi-pass) vector
 172 quantization according to one of three specific packing/coding
 173 algorithms numbered 0 through 2.  The packing algorithm details are
 174 configured by residue instance.  As with the floor components, the
 175 final VQ/entropy encoding is provided by external codebook instances
 176 and each residue instance may choose from any and all available
 177 codebooks.</p></div><div class="section" lang="en"><div class="titlepage"><div><div><h4 class="title"><a name="id257025"></a>1.2.6. Codebooks</h4></div></div></div><p>
 178 Codebooks are a self-contained abstraction that perform entropy
 179 decoding and, optionally, use the entropy-decoded integer value as an
 180 offset into an index of output value vectors, returning the indicated
 181 vector of values.</p><p>
 182 The entropy coding in a Vorbis I codebook is provided by a standard
 183 Huffman binary tree representation.  This tree is tightly packed using
 184 one of several methods, depending on whether codeword lengths are
 185 ordered or unordered, or the tree is sparse.</p><p>
 186 The codebook vector index is similarly packed according to index
 187 characteristic.  Most commonly, the vector index is encoded as a
 188 single list of values of possible values that are then permuted into
 189 a list of n-dimensional rows (lattice VQ).</p></div></div><div class="section" lang="en"><div class="titlepage"><div><div><h3 class="title"><a name="id257049"></a>1.3. High-level Decode Process</h3></div></div></div><div class="section" lang="en"><div class="titlepage"><div><div><h4 class="title"><a name="id257055"></a>1.3.1. Decode Setup</h4></div></div></div><p>
 190 Before decoding can begin, a decoder must initialize using the
 191 bitstream headers matching the stream to be decoded.  Vorbis uses
 192 three header packets; all are required, in-order, by this
 193 specification. Once set up, decode may begin at any audio packet
 194 belonging to the Vorbis stream. In Vorbis I, all packets after the
 195 three initial headers are audio packets. </p><p>
 196 The header packets are, in order, the identification
 197 header, the comments header, and the setup header.</p><div class="section" lang="en"><div class="titlepage"><div><div><h5 class="title"><a name="id312627"></a>1.3.1.1. Identification Header</h5></div></div></div><p>
 198 The identification header identifies the bitstream as Vorbis, Vorbis
 199 version, and the simple audio characteristics of the stream such as
 200 sample rate and number of channels.</p></div><div class="section" lang="en"><div class="titlepage"><div><div><h5 class="title"><a name="id312638"></a>1.3.1.2. Comment Header</h5></div></div></div><p>
 201 The comment header includes user text comments ("tags") and a vendor
 202 string for the application/library that produced the bitstream.  The
 203 encoding and proper use of the comment header is described in
 204 <a href="#vorbis-spec-comment" title="5. comment field and header specification">Section 5, &#8220;comment field and header specification&#8221;</a>.</p></div><div class="section" lang="en"><div class="titlepage"><div><div><h5 class="title"><a name="id312653"></a>1.3.1.3. Setup Header</h5></div></div></div><p>
 205 The setup header includes extensive CODEC setup information as well as
 206 the complete VQ and Huffman codebooks needed for decode.</p></div></div><div class="section" lang="en"><div class="titlepage"><div><div><h4 class="title"><a name="id312666"></a>1.3.2. Decode Procedure</h4></div></div></div><div class="highlights"><p>
 207 The decoding and synthesis procedure for all audio packets is
 208 fundamentally the same.
 209 </p><div class="orderedlist"><ol type="1"><li>decode packet type flag</li><li>decode mode number</li><li>decode window shape (long windows only)</li><li>decode floor</li><li>decode residue into residue vectors</li><li>inverse channel coupling of residue vectors</li><li>generate floor curve from decoded floor data</li><li>compute dot product of floor and residue, producing audio spectrum vector</li><li>inverse monolithic transform of audio spectrum vector, always an MDCT in Vorbis I</li><li>overlap/add left-hand output of transform with right-hand output of previous frame</li><li>store right hand-data from transform of current frame for future lapping</li><li>if not first frame, return results of overlap/add as audio result of current frame</li></ol></div><p>
 210 </p></div><p>
 211 Note that clever rearrangement of the synthesis arithmetic is
 212 possible; as an example, one can take advantage of symmetries in the
 213 MDCT to store the right-hand transform data of a partial MDCT for a
 214 50% inter-frame buffer space savings, and then complete the transform
 215 later before overlap/add with the next frame.  This optimization
 216 produces entirely equivalent output and is naturally perfectly legal.
 217 The decoder must be <span class="emphasis"><em>entirely mathematically equivalent</em></span> to the
 218 specification, it need not be a literal semantic implementation.</p><div class="section" lang="en"><div class="titlepage"><div><div><h5 class="title"><a name="id312754"></a>1.3.2.1. Packet type decode</h5></div></div></div><p>
 219 Vorbis I uses four packet types. The first three packet types mark each
 220 of the three Vorbis headers described above. The fourth packet type
 221 marks an audio packet. All other packet types are reserved; packets
 222 marked with a reserved type should be ignored.</p><p>
 223 Following the three header packets, all packets in a Vorbis I stream
 224 are audio.  The first step of audio packet decode is to read and
 225 verify the packet type; <span class="emphasis"><em>a non-audio packet when audio is expected
 226 indicates stream corruption or a non-compliant stream. The decoder
 227 must ignore the packet and not attempt decoding it to
 228 audio</em></span>.</p></div><div class="section" lang="en"><div class="titlepage"><div><div><h5 class="title"><a name="id312776"></a>1.3.2.2. Mode decode</h5></div></div></div><p>
 229 Vorbis allows an encoder to set up multiple, numbered packet 'modes',
 230 as described earlier, all of which may be used in a given Vorbis
 231 stream. The mode is encoded as an integer used as a direct offset into
 232 the mode instance index. </p></div><div class="section" lang="en"><div class="titlepage"><div><div><h5 class="title"><a name="vorbis-spec-window"></a>1.3.2.3. Window shape decode (long windows only)</h5></div></div></div><p>
 233 Vorbis frames may be one of two PCM sample sizes specified during
 234 codec setup.  In Vorbis I, legal frame sizes are powers of two from 64
 235 to 8192 samples.  Aside from coupling, Vorbis handles channels as
 236 independent vectors and these frame sizes are in samples per channel.</p><p>
 237 Vorbis uses an overlapping transform, namely the MDCT, to blend one
 238 frame into the next, avoiding most inter-frame block boundary
 239 artifacts.  The MDCT output of one frame is windowed according to MDCT
 240 requirements, overlapped 50% with the output of the previous frame and
 241 added.  The window shape assures seamless reconstruction.  </p><p>
 242 This is easy to visualize in the case of equal sized-windows:</p><div class="mediaobject"><img src="window1.png" alt="overlap of two equal-sized windows"></div><p>
 243 And slightly more complex in the case of overlapping unequal sized
 244 windows:</p><div class="mediaobject"><img src="window2.png" alt="overlap of a long and a short window"></div><p>
 245 In the unequal-sized window case, the window shape of the long window
 246 must be modified for seamless lapping as above.  It is possible to
 247 correctly infer window shape to be applied to the current window from
 248 knowing the sizes of the current, previous and next window.  It is
 249 legal for a decoder to use this method. However, in the case of a long
 250 window (short windows require no modification), Vorbis also codes two
 251 flag bits to specify pre- and post- window shape.  Although not
 252 strictly necessary for function, this minor redundancy allows a packet
 253 to be fully decoded to the point of lapping entirely independently of
 254 any other packet, allowing easier abstraction of decode layers as well
 255 as allowing a greater level of easy parallelism in encode and
 256 decode.</p><p>
 257 A description of valid window functions for use with an inverse MDCT
 258 can be found in the paper
 259 &#8220;<span class="citetitle">
 260 <a href="http://www.iocon.com/resource/docs/ps/eusipco_corrected.ps" target="_top">
 261 The use of multirate filter banks for coding of high quality digital
 262 audio</a></span>&#8221;, by T. Sporer, K. Brandenburg and B. Edler.  Vorbis windows
 263 all use the slope function
 264   <span class="inlinemediaobject"><span>$y = \sin(.5*\pi \, \sin^2((x+.5)/n*\pi))$</span></span>.
 265 </p></div><div class="section" lang="en"><div class="titlepage"><div><div><h5 class="title"><a name="id337723"></a>1.3.2.4. floor decode</h5></div></div></div><p>
 266 Each floor is encoded/decoded in channel order, however each floor
 267 belongs to a 'submap' that specifies which floor configuration to
 268 use.  All floors are decoded before residue decode begins.</p></div><div class="section" lang="en"><div class="titlepage"><div><div><h5 class="title"><a name="id337733"></a>1.3.2.5. residue decode</h5></div></div></div><p>
 269 Although the number of residue vectors equals the number of channels,
 270 channel coupling may mean that the raw residue vectors extracted
 271 during decode do not map directly to specific channels.  When channel
 272 coupling is in use, some vectors will correspond to coupled magnitude
 273 or angle.  The coupling relationships are described in the codec setup
 274 and may differ from frame to frame, due to different mode numbers.</p><p>
 275 Vorbis codes residue vectors in groups by submap; the coding is done
 276 in submap order from submap 0 through n-1.  This differs from floors
 277 which are coded using a configuration provided by submap number, but
 278 are coded individually in channel order.</p></div><div class="section" lang="en"><div class="titlepage"><div><div><h5 class="title"><a name="id337751"></a>1.3.2.6. inverse channel coupling</h5></div></div></div><p>
 279 A detailed discussion of stereo in the Vorbis codec can be found in
 280 the document <a href="stereo.html" target="_top"><em class="citetitle">Stereo Channel Coupling in the
 281 Vorbis CODEC</em></a>.  Vorbis is not limited to only stereo coupling, but
 282 the stereo document also gives a good overview of the generic coupling
 283 mechanism.</p><p>
 284 Vorbis coupling applies to pairs of residue vectors at a time;
 285 decoupling is done in-place a pair at a time in the order and using
 286 the vectors specified in the current mapping configuration.  The
 287 decoupling operation is the same for all pairs, converting square
 288 polar representation (where one vector is magnitude and the second
 289 angle) back to Cartesian representation.</p><p>
 290 After decoupling, in order, each pair of vectors on the coupling list,
 291 the resulting residue vectors represent the fine spectral detail
 292 of each output channel.</p></div><div class="section" lang="en"><div class="titlepage"><div><div><h5 class="title"><a name="id337779"></a>1.3.2.7. generate floor curve</h5></div></div></div><p>
 293 The decoder may choose to generate the floor curve at any appropriate
 294 time.  It is reasonable to generate the output curve when the floor
 295 data is decoded from the raw packet, or it can be generated after
 296 inverse coupling and applied to the spectral residue directly,
 297 combining generation and the dot product into one step and eliminating
 298 some working space.</p><p>
 299 Both floor 0 and floor 1 generate a linear-range, linear-domain output
 300 vector to be multiplied (dot product) by the linear-range,
 301 linear-domain spectral residue.</p></div><div class="section" lang="en"><div class="titlepage"><div><div><h5 class="title"><a name="id337795"></a>1.3.2.8. compute floor/residue dot product</h5></div></div></div><p>
 302 This step is straightforward; for each output channel, the decoder
 303 multiplies the floor curve and residue vectors element by element,
 304 producing the finished audio spectrum of each channel.</p><p>
 305 One point is worth mentioning about this dot product; a common mistake
 306 in a fixed point implementation might be to assume that a 32 bit
 307 fixed-point representation for floor and residue and direct
 308 multiplication of the vectors is sufficient for acceptable spectral
 309 depth in all cases because it happens to mostly work with the current
 310 Xiph.Org reference encoder.</p><p>
 311 However, floor vector values can span ~140dB (~24 bits unsigned), and
 312 the audio spectrum vector should represent a minimum of 120dB (~21
 313 bits with sign), even when output is to a 16 bit PCM device.  For the
 314 residue vector to represent full scale if the floor is nailed to
 315 -140dB, it must be able to span 0 to +140dB.  For the residue vector
 316 to reach full scale if the floor is nailed at 0dB, it must be able to
 317 represent -140dB to +0dB.  Thus, in order to handle full range
 318 dynamics, a residue vector may span -140dB to +140dB entirely within
 319 spec.  A 280dB range is approximately 48 bits with sign; thus the
 320 residue vector must be able to represent a 48 bit range and the dot
 321 product must be able to handle an effective 48 bit times 24 bit
 322 multiplication.  This range may be achieved using large (64 bit or
 323 larger) integers, or implementing a movable binary point
 324 representation.</p></div><div class="section" lang="en"><div class="titlepage"><div><div><h5 class="title"><a name="id337822"></a>1.3.2.9. inverse monolithic transform (MDCT)</h5></div></div></div><p>
 325 The audio spectrum is converted back into time domain PCM audio via an
 326 inverse Modified Discrete Cosine Transform (MDCT).  A detailed
 327 description of the MDCT is available in the paper <a href="http://www.iocon.com/resource/docs/ps/eusipco_corrected.ps" target="_top">&#8220;<span class="citetitle">The use of multirate filter banks for coding of high quality digital
 328 audio</span>&#8221;</a>, by T. Sporer, K. Brandenburg and B. Edler.</p><p>
 329 Note that the PCM produced directly from the MDCT is not yet finished
 330 audio; it must be lapped with surrounding frames using an appropriate
 331 window (such as the Vorbis window) before the MDCT can be considered
 332 orthogonal.</p></div><div class="section" lang="en"><div class="titlepage"><div><div><h5 class="title"><a name="id337847"></a>1.3.2.10. overlap/add data</h5></div></div></div><p>
 333 Windowed MDCT output is overlapped and added with the right hand data
 334 of the previous window such that the 3/4 point of the previous window
 335 is aligned with the 1/4 point of the current window (as illustrated in
 336 the window overlap diagram). At this point, the audio data between the
 337 center of the previous frame and the center of the current frame is
 338 now finished and ready to be returned. </p></div><div class="section" lang="en"><div class="titlepage"><div><div><h5 class="title"><a name="id337859"></a>1.3.2.11. cache right hand data</h5></div></div></div><p>
 339 The decoder must cache the right hand portion of the current frame to
 340 be lapped with the left hand portion of the next frame.
 341 </p></div><div class="section" lang="en"><div class="titlepage"><div><div><h5 class="title"><a name="id337869"></a>1.3.2.12. return finished audio data</h5></div></div></div><p>
 342 The overlapped portion produced from overlapping the previous and
 343 current frame data is finished data to be returned by the decoder.
 344 This data spans from the center of the previous window to the center
 345 of the current window.  In the case of same-sized windows, the amount
 346 of data to return is one-half block consisting of and only of the
 347 overlapped portions. When overlapping a short and long window, much of
 348 the returned range is not actually overlap.  This does not damage
 349 transform orthogonality.  Pay attention however to returning the
 350 correct data range; the amount of data to be returned is:
 351
 352 </p><pre class="programlisting">
 353 window_blocksize(previous_window)/4+window_blocksize(current_window)/4
 354 </pre><p>
 355
 356 from the center of the previous window to the center of the current
 357 window.</p><p>
 358 Data is not returned from the first frame; it must be used to 'prime'
 359 the decode engine.  The encoder accounts for this priming when
 360 calculating PCM offsets; after the first frame, the proper PCM output
 361 offset is '0' (as no data has been returned yet).</p></div></div></div></div><div class="section" lang="en"><div class="titlepage"><div><div><h2 class="title" style="clear: both"><a name="vorbis-spec-bitpacking"></a>2. Bitpacking Convention</h2></div><div><p class="releaseinfo">
 362  $Id: 02-bitpacking.xml 7186 2004-07-20 07:19:25Z xiphmont $
 363 </p></div></div></div><div class="section" lang="en"><div class="titlepage"><div><div><h3 class="title"><a name="id316853"></a>2.1. Overview</h3></div></div></div><p>
 364 The Vorbis codec uses relatively unstructured raw packets containing
 365 arbitrary-width binary integer fields.  Logically, these packets are a
 366 bitstream in which bits are coded one-by-one by the encoder and then
 367 read one-by-one in the same monotonically increasing order by the
 368 decoder.  Most current binary storage arrangements group bits into a
 369 native word size of eight bits (octets), sixteen bits, thirty-two bits
 370 or, less commonly other fixed word sizes.  The Vorbis bitpacking
 371 convention specifies the correct mapping of the logical packet
 372 bitstream into an actual representation in fixed-width words.
 373 </p><div class="section" lang="en"><div class="titlepage"><div><div><h4 class="title"><a name="id318012"></a>2.1.1. octets, bytes and words</h4></div></div></div><p>
 374 In most contemporary architectures, a 'byte' is synonymous with an
 375 'octet', that is, eight bits.  This has not always been the case;
 376 seven, ten, eleven and sixteen bit 'bytes' have been used.  For
 377 purposes of the bitpacking convention, a byte implies the native,
 378 smallest integer storage representation offered by a platform.  On
 379 modern platforms, this is generally assumed to be eight bits (not
 380 necessarily because of the processor but because of the
 381 filesystem/memory architecture.  Modern filesystems invariably offer
 382 bytes as the fundamental atom of storage).  A 'word' is an integer
 383 size that is a grouped multiple of this smallest size.</p><p>
 384 The most ubiquitous architectures today consider a 'byte' to be an
 385 octet (eight bits) and a word to be a group of two, four or eight
 386 bytes (16, 32 or 64 bits).  Note however that the Vorbis bitpacking
 387 convention is still well defined for any native byte size; Vorbis uses
 388 the native bit-width of a given storage system. This document assumes
 389 that a byte is one octet for purposes of example.</p></div><div class="section" lang="en"><div class="titlepage"><div><div><h4 class="title"><a name="id326209"></a>2.1.2. bit order</h4></div></div></div><p>
 390 A byte has a well-defined 'least significant' bit (LSb), which is the
 391 only bit set when the byte is storing the two's complement integer
 392 value +1.  A byte's 'most significant' bit (MSb) is at the opposite
 393 end of the byte. Bits in a byte are numbered from zero at the LSb to
 394 <span class="emphasis"><em>n</em></span> (<span class="emphasis"><em>n</em></span>=7 in an octet) for the
 395 MSb.</p></div><div class="section" lang="en"><div class="titlepage"><div><div><h4 class="title"><a name="id323175"></a>2.1.3. byte order</h4></div></div></div><p>
 396 Words are native groupings of multiple bytes.  Several byte orderings
 397 are possible in a word; the common ones are 3-2-1-0 ('big endian' or
 398 'most significant byte first' in which the highest-valued byte comes
 399 first), 0-1-2-3 ('little endian' or 'least significant byte first' in
 400 which the lowest value byte comes first) and less commonly 3-1-2-0 and
 401 0-2-1-3 ('mixed endian').</p><p>
 402 The Vorbis bitpacking convention specifies storage and bitstream
 403 manipulation at the byte, not word, level, thus host word ordering is
 404 of a concern only during optimization when writing high performance
 405 code that operates on a word of storage at a time rather than by byte.
 406 Logically, bytes are always coded and decoded in order from byte zero
 407 through byte <span class="emphasis"><em>n</em></span>.</p></div><div class="section" lang="en"><div class="titlepage"><div><div><h4 class="title"><a name="id323198"></a>2.1.4. coding bits into byte sequences</h4></div></div></div><p>
 408 The Vorbis codec has need to code arbitrary bit-width integers, from
 409 zero to 32 bits wide, into packets.  These integer fields are not
 410 aligned to the boundaries of the byte representation; the next field
 411 is written at the bit position at which the previous field ends.</p><p>
 412 The encoder logically packs integers by writing the LSb of a binary
 413 integer to the logical bitstream first, followed by next least
 414 significant bit, etc, until the requested number of bits have been
 415 coded.  When packing the bits into bytes, the encoder begins by
 416 placing the LSb of the integer to be written into the least
 417 significant unused bit position of the destination byte, followed by
 418 the next-least significant bit of the source integer and so on up to
 419 the requested number of bits.  When all bits of the destination byte
 420 have been filled, encoding continues by zeroing all bits of the next
 421 byte and writing the next bit into the bit position 0 of that byte.
 422 Decoding follows the same process as encoding, but by reading bits
 423 from the byte stream and reassembling them into integers.</p></div><div class="section" lang="en"><div class="titlepage"><div><div><h4 class="title"><a name="id312415"></a>2.1.5. signedness</h4></div></div></div><p>
 424 The signedness of a specific number resulting from decode is to be
 425 interpreted by the decoder given decode context.  That is, the three
 426 bit binary pattern 'b111' can be taken to represent either 'seven' as
 427 an unsigned integer, or '-1' as a signed, two's complement integer.
 428 The encoder and decoder are responsible for knowing if fields are to
 429 be treated as signed or unsigned.</p></div><div class="section" lang="en"><div class="titlepage"><div><div><h4 class="title"><a name="id312428"></a>2.1.6. coding example</h4></div></div></div><p>
 430 Code the 4 bit integer value '12' [b1100] into an empty bytestream.
 431 Bytestream result:
 432
 433 </p><pre class="screen">
 434               |
 435               V
 436
 437         7 6 5 4 3 2 1 0
 438 byte 0 [0 0 0 0 1 1 0 0]  &lt;-
 439 byte 1 [               ]
 440 byte 2 [               ]
 441 byte 3 [               ]
 442              ...
 443 byte n [               ]  bytestream length == 1 byte
 444
 445 </pre><p>
 446 </p><p>
 447 Continue by coding the 3 bit integer value '-1' [b111]:
 448
 449 </p><pre class="screen">
 450         |
 451         V
 452
 453         7 6 5 4 3 2 1 0
 454 byte 0 [0 1 1 1 1 1 0 0]  &lt;-
 455 byte 1 [               ]
 456 byte 2 [               ]
 457 byte 3 [               ]
 458              ...
 459 byte n [               ]  bytestream length == 1 byte
 460 </pre><p>
 461 </p><p>
 462 Continue by coding the 7 bit integer value '17' [b0010001]:
 463
 464 </p><pre class="screen">
 465           |
 466           V
 467
 468         7 6 5 4 3 2 1 0
 469 byte 0 [1 1 1 1 1 1 0 0]
 470 byte 1 [0 0 0 0 1 0 0 0]  &lt;-
 471 byte 2 [               ]
 472 byte 3 [               ]
 473              ...
 474 byte n [               ]  bytestream length == 2 bytes
 475                           bit cursor == 6
 476 </pre><p>
 477 </p><p>
 478 Continue by coding the 13 bit integer value '6969' [b110 11001110 01]:
 479
 480 </p><pre class="screen">
 481                 |
 482                 V
 483
 484         7 6 5 4 3 2 1 0
 485 byte 0 [1 1 1 1 1 1 0 0]
 486 byte 1 [0 1 0 0 1 0 0 0]
 487 byte 2 [1 1 0 0 1 1 1 0]
 488 byte 3 [0 0 0 0 0 1 1 0]  &lt;-
 489              ...
 490 byte n [               ]  bytestream length == 4 bytes
 491
 492 </pre><p>
 493 </p></div><div class="section" lang="en"><div class="titlepage"><div><div><h4 class="title"><a name="id317084"></a>2.1.7. decoding example</h4></div></div></div><p>
 494 Reading from the beginning of the bytestream encoded in the above example:
 495
 496 </p><pre class="screen">
 497                       |
 498                       V
 499
 500         7 6 5 4 3 2 1 0
 501 byte 0 [1 1 1 1 1 1 0 0]  &lt;-
 502 byte 1 [0 1 0 0 1 0 0 0]
 503 byte 2 [1 1 0 0 1 1 1 0]
 504 byte 3 [0 0 0 0 0 1 1 0]  bytestream length == 4 bytes
 505
 506 </pre><p>
 507 </p><p>
 508 We read two, two-bit integer fields, resulting in the returned numbers
 509 'b00' and 'b11'.  Two things are worth noting here:
 510
 511 </p><div class="itemizedlist"><ul type="disc"><li><p>Although these four bits were originally written as a single
 512 four-bit integer, reading some other combination of bit-widths from the
 513 bitstream is well defined.  There are no artificial alignment
 514 boundaries maintained in the bitstream.</p></li><li><p>The second value is the
 515 two-bit-wide integer 'b11'.  This value may be interpreted either as
 516 the unsigned value '3', or the signed value '-1'.  Signedness is
 517 dependent on decode context.</p></li></ul></div><p>
 518 </p></div><div class="section" lang="en"><div class="titlepage"><div><div><h4 class="title"><a name="id322995"></a>2.1.8. end-of-packet alignment</h4></div></div></div><p>
 519 The typical use of bitpacking is to produce many independent
 520 byte-aligned packets which are embedded into a larger byte-aligned
 521 container structure, such as an Ogg transport bitstream.  Externally,
 522 each bytestream (encoded bitstream) must begin and end on a byte
 523 boundary.  Often, the encoded bitstream is not an integer number of
 524 bytes, and so there is unused (uncoded) space in the last byte of a
 525 packet.</p><p>
 526 Unused space in the last byte of a bytestream is always zeroed during
 527 the coding process.  Thus, should this unused space be read, it will
 528 return binary zeroes.</p><p>
 529 Attempting to read past the end of an encoded packet results in an
 530 'end-of-packet' condition.  End-of-packet is not to be considered an
 531 error; it is merely a state indicating that there is insufficient
 532 remaining data to fulfill the desired read size.  Vorbis uses truncated
 533 packets as a normal mode of operation, and as such, decoders must
 534 handle reading past the end of a packet as a typical mode of
 535 operation. Any further read operations after an 'end-of-packet'
 536 condition shall also return 'end-of-packet'.</p></div><div class="section" lang="en"><div class="titlepage"><div><div><h4 class="title"><a name="id323021"></a>2.1.9.  reading zero bits</h4></div></div></div><p>
 537 Reading a zero-bit-wide integer returns the value '0' and does not
 538 increment the stream cursor.  Reading to the end of the packet (but
 539 not past, such that an 'end-of-packet' condition has not triggered)
 540 and then reading a zero bit integer shall succeed, returning 0, and
 541 not trigger an end-of-packet condition.  Reading a zero-bit-wide
 542 integer after a previous read sets 'end-of-packet' shall also fail
 543 with 'end-of-packet'.</p></div></div></div><div class="section" lang="en"><div class="titlepage"><div><div><h2 class="title" style="clear: both"><a name="vorbis-spec-codebook"></a>3. Probability Model and Codebooks</h2></div><div><p class="releaseinfo">
 544  $Id: 03-codebook.xml 7186 2004-07-20 07:19:25Z xiphmont $
 545 </p></div></div></div><div class="section" lang="en"><div class="titlepage"><div><div><h3 class="title"><a name="id326636"></a>3.1. Overview</h3></div></div></div><p>
 546 Unlike practically every other mainstream audio codec, Vorbis has no
 547 statically configured probability model, instead packing all entropy
 548 decoding configuration, VQ and Huffman, into the bitstream itself in
 549 the third header, the codec setup header.  This packed configuration
 550 consists of multiple 'codebooks', each containing a specific
 551 Huffman-equivalent representation for decoding compressed codewords as
 552 well as an optional lookup table of output vector values to which a
 553 decoded Huffman value is applied as an offset, generating the final
 554 decoded output corresponding to a given compressed codeword.</p><div class="section" lang="en"><div class="titlepage"><div><div><h4 class="title"><a name="id331970"></a>3.1.1. Bitwise operation</h4></div></div></div><p>
 555 The codebook mechanism is built on top of the vorbis bitpacker. Both
 556 the codebooks themselves and the codewords they decode are unrolled
 557 from a packet as a series of arbitrary-width values read from the
 558 stream according to <a href="#vorbis-spec-bitpacking" title="2. Bitpacking Convention">Section 2, &#8220;Bitpacking Convention&#8221;</a>.</p></div></div><div class="section" lang="en"><div class="titlepage"><div><div><h3 class="title"><a name="id329366"></a>3.2. Packed codebook format</h3></div></div></div><p>
 559 For purposes of the examples below, we assume that the storage
 560 system's native byte width is eight bits.  This is not universally
 561 true; see <a href="#vorbis-spec-bitpacking" title="2. Bitpacking Convention">Section 2, &#8220;Bitpacking Convention&#8221;</a> for discussion
 562 relating to non-eight-bit bytes.</p><div class="section" lang="en"><div class="titlepage"><div><div><h4 class="title"><a name="id310869"></a>3.2.1. codebook decode</h4></div></div></div><p>
 563 A codebook begins with a 24 bit sync pattern, 0x564342:
 564
 565 </p><pre class="screen">
 566 byte 0: [ 0 1 0 0 0 0 1 0 ] (0x42)
 567 byte 1: [ 0 1 0 0 0 0 1 1 ] (0x43)
 568 byte 2: [ 0 1 0 1 0 1 1 0 ] (0x56)
 569 </pre><p>
 570 16 bit <code class="varname">[codebook_dimensions]</code> and 24 bit <code class="varname">[codebook_entries]</code> fields:
 571
 572 </p><pre class="screen">
 573
 574 byte 3: [ X X X X X X X X ]
 575 byte 4: [ X X X X X X X X ] [codebook_dimensions] (16 bit unsigned)
 576
 577 byte 5: [ X X X X X X X X ]
 578 byte 6: [ X X X X X X X X ]
 579 byte 7: [ X X X X X X X X ] [codebook_entries] (24 bit unsigned)
 580
 581 </pre><p>
 582 Next is the <code class="varname">[ordered]</code> bit flag:
 583
 584 </p><pre class="screen">
 585
 586 byte 8: [               X ] [ordered] (1 bit)
 587
 588 </pre><p>
 589 Each entry, numbering a
 590 total of <code class="varname">[codebook_entries]</code>, is assigned a codeword length.
 591 We now read the list of codeword lengths and store these lengths in
 592 the array <code class="varname">[codebook_codeword_lengths]</code>. Decode of lengths is
 593 according to whether the <code class="varname">[ordered]</code> flag is set or unset.
 594
 595 </p><div class="itemizedlist"><ul type="disc"><li><p>If the <code class="varname">[ordered]</code> flag is unset, the codeword list is not
 596   length ordered and the decoder needs to read each codeword length
 597   one-by-one.</p><p>The decoder first reads one additional bit flag, the
 598   <code class="varname">[sparse]</code> flag.  This flag determines whether or not the
 599   codebook contains unused entries that are not to be included in the
 600   codeword decode tree:
 601
 602 </p><pre class="screen">
 603 byte 8: [             X 1 ] [sparse] flag (1 bit)
 604 </pre><p>
 605   The decoder now performs for each of the <code class="varname">[codebook_entries]</code>
 606   codebook entries:
 607
 608 </p><pre class="screen">
 609
 610   1) if([sparse] is set){
 611
 612          2) [flag] = read one bit;
 613          3) if([flag] is set){
 614
 615               4) [length] = read a five bit unsigned integer;
 616               5) codeword length for this entry is [length]+1;
 617
 618             } else {
 619
 620               6) this entry is unused.  mark it as such.
 621
 622             }
 623
 624      } else the sparse flag is not set {
 625
 626         7) [length] = read a five bit unsigned integer;
 627         8) the codeword length for this entry is [length]+1;
 628
 629      }
 630
 631 </pre></li><li><p>If the <code class="varname">[ordered]</code> flag is set, the codeword list for this
 632   codebook is encoded in ascending length order.  Rather than reading
 633   a length for every codeword, the encoder reads the number of
 634   codewords per length.  That is, beginning at entry zero:
 635
 636 </p><pre class="screen">
 637   1) [current_entry] = 0;
 638   2) [current_length] = read a five bit unsigned integer and add 1;
 639   3) [number] = read <a href="#vorbis-spec-ilog" title="9.2.1. ilog">ilog</a>([codebook_entries] - [current_entry]) bits as an unsigned integer
 640   4) set the entries [current_entry] through [current_entry]+[number]-1, inclusive,
 641     of the [codebook_codeword_lengths] array to [current_length]
 642   5) set [current_entry] to [number] + [current_entry]
 643   6) increment [current_length] by 1
 644   7) if [current_entry] is greater than [codebook_entries] ERROR CONDITION;
 645     the decoder will not be able to read this stream.
 646   8) if [current_entry] is less than [codebook_entries], repeat process starting at 3)
 647   9) done.
 648 </pre></li></ul></div><p>
 649
 650 After all codeword lengths have been decoded, the decoder reads the
 651 vector lookup table.  Vorbis I supports three lookup types:
 652 </p><div class="orderedlist"><ol type="1"><li>No lookup</li><li>Implicitly populated value mapping (lattice VQ)</li><li>Explicitly populated value mapping (tessellated or 'foam'
 653 VQ)</li></ol></div><p>
 654 </p><p>
 655 The lookup table type is read as a four bit unsigned integer:
 656 </p><pre class="screen">
 657   1) [codebook_lookup_type] = read four bits as an unsigned integer
 658 </pre><p>
 659 Codebook decode precedes according to <code class="varname">[codebook_lookup_type]</code>:
 660 </p><div class="itemizedlist"><ul type="disc"><li><p>Lookup type zero indicates no lookup to be read.  Proceed past
 661 lookup decode.</p></li><li><p>Lookup types one and two are similar, differing only in the
 662 number of lookup values to be read.  Lookup type one reads a list of
 663 values that are permuted in a set pattern to build a list of vectors,
 664 each vector of order <code class="varname">[codebook_dimensions]</code> scalars.  Lookup
 665 type two builds the same vector list, but reads each scalar for each
 666 vector explicitly, rather than building vectors from a smaller list of
 667 possible scalar values.  Lookup decode proceeds as follows:
 668
 669 </p><pre class="screen">
 670   1) [codebook_minimum_value] = <a href="#vorbis-spec-float32_unpack" title="9.2.2. float32_unpack">float32_unpack</a>( read 32 bits as an unsigned integer)
 671   2) [codebook_delta_value] = <a href="#vorbis-spec-float32_unpack" title="9.2.2. float32_unpack">float32_unpack</a>( read 32 bits as an unsigned integer)
 672   3) [codebook_value_bits] = read 4 bits as an unsigned integer and add 1
 673   4) [codebook_sequence_p] = read 1 bit as a boolean flag
 674
 675   if ( [codebook_lookup_type] is 1 ) {
 676
 677      5) [codebook_lookup_values] = <a href="#vorbis-spec-lookup1_values" title="9.2.3. lookup1_values">lookup1_values</a>(<code class="varname">[codebook_entries]</code>, <code class="varname">[codebook_dimensions]</code> )
 678
 679   } else {
 680
 681      6) [codebook_lookup_values] = <code class="varname">[codebook_entries]</code> * <code class="varname">[codebook_dimensions]</code>
 682
 683   }
 684
 685   7) read a total of [codebook_lookup_values] unsigned integers of [codebook_value_bits] each;
 686      store these in order in the array [codebook_multiplicands]
 687 </pre></li><li><p>A <code class="varname">[codebook_lookup_type]</code> of greater than two is reserved
 688 and indicates a stream that is not decodable by the specification in this
 689 document.</p></li></ul></div><p>
 690 </p><p>
 691 An 'end of packet' during any read operation in the above steps is
 692 considered an error condition rendering the stream undecodable.</p><div class="section" lang="en"><div class="titlepage"><div><div><h5 class="title"><a name="id257433"></a>3.2.1.1. Huffman decision tree representation</h5></div></div></div><p>
 693 The <code class="varname">[codebook_codeword_lengths]</code> array and
 694 <code class="varname">[codebook_entries]</code> value uniquely define the Huffman decision
 695 tree used for entropy decoding.</p><p>
 696 Briefly, each used codebook entry (recall that length-unordered
 697 codebooks support unused codeword entries) is assigned, in order, the
 698 lowest valued unused binary Huffman codeword possible.  Assume the
 699 following codeword length list:
 700
 701 </p><pre class="screen">
 702 entry 0: length 2
 703 entry 1: length 4
 704 entry 2: length 4
 705 entry 3: length 4
 706 entry 4: length 4
 707 entry 5: length 2
 708 entry 6: length 3
 709 entry 7: length 3
 710 </pre><p>
 711 Assigning codewords in order (lowest possible value of the appropriate
 712 length to highest) results in the following codeword list:
 713
 714 </p><pre class="screen">
 715 entry 0: length 2 codeword 00
 716 entry 1: length 4 codeword 0100
 717 entry 2: length 4 codeword 0101
 718 entry 3: length 4 codeword 0110
 719 entry 4: length 4 codeword 0111
 720 entry 5: length 2 codeword 10
 721 entry 6: length 3 codeword 110
 722 entry 7: length 3 codeword 111
 723 </pre><div class="note" style="margin-left: 0.5in; margin-right: 0.5in;"><h3 class="title">Note</h3><p>
 724 Unlike most binary numerical values in this document, we
 725 intend the above codewords to be read and used bit by bit from left to
 726 right, thus the codeword '001' is the bit string 'zero, zero, one'.
 727 When determining 'lowest possible value' in the assignment definition
 728 above, the leftmost bit is the MSb.</p></div><p>
 729 It is clear that the codeword length list represents a Huffman
 730 decision tree with the entry numbers equivalent to the leaves numbered
 731 left-to-right:
 732
 733 </p><div class="mediaobject"><img src="hufftree.png" alt="[huffman tree illustration]"></div><p>
 734 </p><p>
 735 As we assign codewords in order, we see that each choice constructs a
 736 new leaf in the leftmost possible position.</p><p>
 737 Note that it's possible to underspecify or overspecify a Huffman tree
 738 via the length list.  In the above example, if codeword seven were
 739 eliminated, it's clear that the tree is unfinished:
 740
 741 </p><div class="mediaobject"><img src="hufftree-under.png" alt="[underspecified huffman tree illustration]"></div><p>
 742 </p><p>
 743 Similarly, in the original codebook, it's clear that the tree is fully
 744 populated and a ninth codeword is impossible.  Both underspecified and
 745 overspecified trees are an error condition rendering the stream
 746 undecodable.</p><p>
 747 Codebook entries marked 'unused' are simply skipped in the assigning
 748 process.  They have no codeword and do not appear in the decision
 749 tree, thus it's impossible for any bit pattern read from the stream to
 750 decode to that entry number.</p></div><div class="section" lang="en"><div class="titlepage"><div><div><h5 class="title"><a name="id320556"></a>3.2.1.2. VQ lookup table vector representation</h5></div></div></div><p>
 751 Unpacking the VQ lookup table vectors relies on the following values:
 752 </p><pre class="programlisting">
 753 the [codebook_multiplicands] array
 754 [codebook_minimum_value]
 755 [codebook_delta_value]
 756 [codebook_sequence_p]
 757 [codebook_lookup_type]
 758 [codebook_entries]
 759 [codebook_dimensions]
 760 [codebook_lookup_values]
 761 </pre><p>
 762 </p><p>
 763 Decoding (unpacking) a specific vector in the vector lookup table
 764 proceeds according to <code class="varname">[codebook_lookup_type]</code>.  The unpacked
 765 vector values are what a codebook would return during audio packet
 766 decode in a VQ context.</p><div class="section" lang="en"><div class="titlepage"><div><div><h6 class="title"><a name="id320581"></a>3.2.1.2.1. Vector value decode: Lookup type 1</h6></div></div></div><p>
 767 Lookup type one specifies a lattice VQ lookup table built
 768 algorithmically from a list of scalar values.  Calculate (unpack) the
 769 final values of a codebook entry vector from the entries in
 770 <code class="varname">[codebook_multiplicands]</code> as follows (<code class="varname">[value_vector]</code>
 771 is the output vector representing the vector of values for entry number
 772 <code class="varname">[lookup_offset]</code> in this codebook):
 773
 774 </p><pre class="screen">
 775   1) [last] = 0;
 776   2) [index_divisor] = 1;
 777   3) iterate [i] over the range 0 ... [codebook_dimensions]-1 (once for each scalar value in the value vector) {
 778
 779        4) [multiplicand_offset] = ( [lookup_offset] divided by [index_divisor] using integer
 780           division ) integer modulo [codebook_lookup_values]
 781
 782        5) vector [value_vector] element [i] =
 783             ( [codebook_multiplicands] array element number [multiplicand_offset] ) *
 784             [codebook_delta_value] + [codebook_minimum_value] + [last];
 785
 786        6) if ( [codebook_sequence_p] is set ) then set [last] = vector [value_vector] element [i]
 787
 788        7) [index_divisor] = [index_divisor] * [codebook_lookup_values]
 789
 790      }
 791
 792   8) vector calculation completed.
 793 </pre></div><div class="section" lang="en"><div class="titlepage"><div><div><h6 class="title"><a name="id320614"></a>3.2.1.2.2. Vector value decode: Lookup type 2</h6></div></div></div><p>
 794 Lookup type two specifies a VQ lookup table in which each scalar in
 795 each vector is explicitly set by the <code class="varname">[codebook_multiplicands]</code>
 796 array in a one-to-one mapping.  Calculate [unpack] the
 797 final values of a codebook entry vector from the entries in
 798 <code class="varname">[codebook_multiplicands]</code> as follows (<code class="varname">[value_vector]</code>
 799 is the output vector representing the vector of values for entry number
 800 <code class="varname">[lookup_offset]</code> in this codebook):
 801
 802 </p><pre class="screen">
 803   1) [last] = 0;
 804   2) [multiplicand_offset] = [lookup_offset] * [codebook_dimensions]
 805   3) iterate [i] over the range 0 ... [codebook_dimensions]-1 (once for each scalar value in the value vector) {
 806
 807        4) vector [value_vector] element [i] =
 808             ( [codebook_multiplicands] array element number [multiplicand_offset] ) *
 809             [codebook_delta_value] + [codebook_minimum_value] + [last];
 810
 811        5) if ( [codebook_sequence_p] is set ) then set [last] = vector [value_vector] element [i]
 812
 813        6) increment [multiplicand_offset]
 814
 815      }
 816
 817   7) vector calculation completed.
 818 </pre></div></div></div></div><div class="section" lang="en"><div class="titlepage"><div><div><h3 class="title"><a name="id320654"></a>3.3. Use of the codebook abstraction</h3></div></div></div><p>
 819 The decoder uses the codebook abstraction much as it does the
 820 bit-unpacking convention; a specific codebook reads a
 821 codeword from the bitstream, decoding it into an entry number, and then
 822 returns that entry number to the decoder (when used in a scalar
 823 entropy coding context), or uses that entry number as an offset into
 824 the VQ lookup table, returning a vector of values (when used in a context
 825 desiring a VQ value). Scalar or VQ context is always explicit; any call
 826 to the codebook mechanism requests either a scalar entry number or a
 827 lookup vector.</p><p>
 828 Note that VQ lookup type zero indicates that there is no lookup table;
 829 requesting decode using a codebook of lookup type 0 in any context
 830 expecting a vector return value (even in a case where a vector of
 831 dimension one) is forbidden.  If decoder setup or decode requests such
 832 an action, that is an error condition rendering the packet
 833 undecodable.</p><p>
 834 Using a codebook to read from the packet bitstream consists first of
 835 reading and decoding the next codeword in the bitstream. The decoder
 836 reads bits until the accumulated bits match a codeword in the
 837 codebook.  This process can be though of as logically walking the
 838 Huffman decode tree by reading one bit at a time from the bitstream,
 839 and using the bit as a decision boolean to take the 0 branch (left in
 840 the above examples) or the 1 branch (right in the above examples).
 841 Walking the tree finishes when the decode process hits a leaf in the
 842 decision tree; the result is the entry number corresponding to that
 843 leaf.  Reading past the end of a packet propagates the 'end-of-stream'
 844 condition to the decoder.</p><p>
 845 When used in a scalar context, the resulting codeword entry is the
 846 desired return value.</p><p>
 847 When used in a VQ context, the codeword entry number is used as an
 848 offset into the VQ lookup table.  The value returned to the decoder is
 849 the vector of scalars corresponding to this offset.</p></div></div><div class="section" lang="en"><div class="titlepage"><div><div><h2 class="title" style="clear: both"><a name="vorbis-spec-codec"></a>4. Codec Setup and Packet Decode</h2></div><div><p class="releaseinfo">
 850  $Id: 04-codec.xml 10466 2005-11-28 00:34:44Z giles $
 851 </p></div></div></div><div class="section" lang="en"><div class="titlepage"><div><div><h3 class="title"><a name="id332455"></a>4.1. Overview</h3></div></div></div><p>
 852 This document serves as the top-level reference document for the
 853 bit-by-bit decode specification of Vorbis I.  This document assumes a
 854 high-level understanding of the Vorbis decode process, which is
 855 provided in <a href="#vorbis-spec-intro" title="1. Introduction and Description">Section 1, &#8220;Introduction and Description&#8221;</a>.  <a href="#vorbis-spec-bitpacking" title="2. Bitpacking Convention">Section 2, &#8220;Bitpacking Convention&#8221;</a> covers reading and writing bit fields from
 856 and to bitstream packets.</p></div><div class="section" lang="en"><div class="titlepage"><div><div><h3 class="title"><a name="id332825"></a>4.2. Header decode and decode setup</h3></div></div></div><p>
 857 A Vorbis bitstream begins with three header packets. The header
 858 packets are, in order, the identification header, the comments header,
 859 and the setup header. All are required for decode compliance.  An
 860 end-of-packet condition during decoding the first or third header
 861 packet renders the stream undecodable.  End-of-packet decoding the
 862 comment header is a non-fatal error condition.</p><div class="section" lang="en"><div class="titlepage"><div><div><h4 class="title"><a name="id313589"></a>4.2.1. Common header decode</h4></div></div></div><p>
 863 Each header packet begins with the same header fields.
 864 </p><pre class="screen">
 865   1) [packet_type] : 8 bit value
 866   2) 0x76, 0x6f, 0x72, 0x62, 0x69, 0x73: the characters 'v','o','r','b','i','s' as six octets
 867 </pre><p>
 868 Decode continues according to packet type; the identification header
 869 is type 1, the comment header type 3 and the setup header type 5
 870 (these types are all odd as a packet with a leading single bit of '0'
 871 is an audio packet).  The packets must occur in the order of
 872 identification, comment, setup.</p></div><div class="section" lang="en"><div class="titlepage"><div><div><h4 class="title"><a name="id339332"></a>4.2.2. Identification header</h4></div></div></div><p>
 873 The identification header is a short header of only a few fields used
 874 to declare the stream definitively as Vorbis, and provide a few externally
 875 relevant pieces of information about the audio stream. The
 876 identification header is coded as follows:</p><pre class="screen">
 877  1) [vorbis_version] = read 32 bits as unsigned integer
 878  2) [audio_channels] = read 8 bit integer as unsigned
 879  3) [audio_sample_rate] = read 32 bits as unsigned integer
 880  4) [bitrate_maximum] = read 32 bits as signed integer
 881  5) [bitrate_nominal] = read 32 bits as signed integer
 882  6) [bitrate_minimum] = read 32 bits as signed integer
 883  7) [blocksize_0] = 2 exponent (read 4 bits as unsigned integer)
 884  8) [blocksize_1] = 2 exponent (read 4 bits as unsigned integer)
 885  9) [framing_flag] = read one bit
 886 </pre><p>
 887 <code class="varname">[vorbis_version]</code> is to read '0' in order to be compatible
 888 with this document.  Both <code class="varname">[audio_channels]</code> and
 889 <code class="varname">[audio_sample_rate]</code> must read greater than zero.  Allowed final
 890 blocksize values are 64, 128, 256, 512, 1024, 2048, 4096 and 8192 in
 891 Vorbis I.  <code class="varname">[blocksize_0]</code> must be less than or equal to
 892 <code class="varname">[blocksize_1]</code>.  The framing bit must be nonzero.  Failure to
 893 meet any of these conditions renders a stream undecodable.</p><p>
 894 The bitrate fields above are used only as hints. The nominal bitrate
 895 field especially may be considerably off in purely VBR streams.  The
 896 fields are meaningful only when greater than zero.</p><p>
 897 </p><div class="itemizedlist"><ul type="disc"><li>All three fields set to the same value implies a fixed rate, or tightly bounded, nearly fixed-rate bitstream</li><li>Only nominal set implies a VBR or ABR stream that averages the nominal bitrate</li><li>Maximum and or minimum set implies a VBR bitstream that obeys the bitrate limits</li><li>None set indicates the encoder does not care to speculate.</li></ul></div><p>
 898 </p></div><div class="section" lang="en"><div class="titlepage"><div><div><h4 class="title"><a name="id320761"></a>4.2.3. Comment header</h4></div></div></div><p>
 899 Comment header decode and data specification is covered in
 900 <a href="#vorbis-spec-comment" title="5. comment field and header specification">Section 5, &#8220;comment field and header specification&#8221;</a>.</p></div><div class="section" lang="en"><div class="titlepage"><div><div><h4 class="title"><a name="id317509"></a>4.2.4. Setup header</h4></div></div></div><p>
 901 Vorbis codec setup is configurable to an extreme degree:
 902
 903 </p><div class="mediaobject"><img src="components.png" alt="[decoder pipeline configuration]"></div><p>
 904 </p><p>
 905 The setup header contains the bulk of the codec setup information
 906 needed for decode.  The setup header contains, in order, the lists of
 907 codebook configurations, time-domain transform configurations
 908 (placeholders in Vorbis I), floor configurations, residue
 909 configurations, channel mapping configurations and mode
 910 configurations. It finishes with a framing bit of '1'.  Header decode
 911 proceeds in the following order:</p><div class="section" lang="en"><div class="titlepage"><div><div><h5 class="title"><a name="id317547"></a>4.2.4.1. Codebooks</h5></div></div></div><div class="orderedlist"><ol type="1"><li><code class="varname">[vorbis_codebook_count]</code> = read eight bits as unsigned integer and add one</li><li>Decode <code class="varname">[vorbis_codebook_count]</code> codebooks in order as defined
 912 in <a href="#vorbis-spec-codebook" title="3. Probability Model and Codebooks">Section 3, &#8220;Probability Model and Codebooks&#8221;</a>.  Save each configuration, in
 913 order, in an array of
 914 codebook configurations <code class="varname">[vorbis_codebook_configurations]</code>.</li></ol></div></div><div class="section" lang="en"><div class="titlepage"><div><div><h5 class="title"><a name="id309581"></a>4.2.4.2. Time domain transforms</h5></div></div></div><p>
 915 These hooks are placeholders in Vorbis I.  Nevertheless, the
 916 configuration placeholder values must be read to maintain bitstream
 917 sync.</p><div class="orderedlist"><ol type="1"><li><code class="varname">[vorbis_time_count]</code> = read 6 bits as unsigned integer and add one</li><li>read <code class="varname">[vorbis_time_count]</code> 16 bit values; each value should be zero.  If any value is nonzero, this is an error condition and the stream is undecodable.</li></ol></div></div><div class="section" lang="en"><div class="titlepage"><div><div><h5 class="title"><a name="id309616"></a>4.2.4.3. Floors</h5></div></div></div><p>
 918 Vorbis uses two floor types; header decode is handed to the decode
 919 abstraction of the appropriate type.</p><div class="orderedlist"><ol type="1"><li><code class="varname">[vorbis_floor_count]</code> = read 6 bits as unsigned integer and add one</li><li><p>For each <code class="varname">[i]</code> of <code class="varname">[vorbis_floor_count]</code> floor numbers:
 920   </p><div class="orderedlist"><ol type="a"><li>read the floor type: vector <code class="varname">[vorbis_floor_types]</code> element <code class="varname">[i]</code> =
 921 read 16 bits as unsigned integer</li><li>If the floor type is zero, decode the floor
 922 configuration as defined in <a href="#vorbis-spec-floor0" title="6. Floor type 0 setup and decode">Section 6, &#8220;Floor type 0 setup and decode&#8221;</a>; save
 923 this
 924 configuration in slot <code class="varname">[i]</code> of the floor configuration array <code class="varname">[vorbis_floor_configurations]</code>.</li><li>If the floor type is one,
 925 decode the floor configuration as defined in <a href="#vorbis-spec-floor1" title="7. Floor type 1 setup and decode">Section 7, &#8220;Floor type 1 setup and decode&#8221;</a>; save this configuration in slot <code class="varname">[i]</code> of the floor configuration array <code class="varname">[vorbis_floor_configurations]</code>.</li><li>If the the floor type is greater than one, this stream is undecodable; ERROR CONDITION</li></ol></div><p>
 926  </p></li></ol></div></div><div class="section" lang="en"><div class="titlepage"><div><div><h5 class="title"><a name="id273566"></a>4.2.4.4. Residues</h5></div></div></div><p>
 927 Vorbis uses three residue types; header decode of each type is identical.
 928 </p><div class="orderedlist"><ol type="1"><li><code class="varname">[vorbis_residue_count]</code> = read 6 bits as unsigned integer and add one
 929 </li><li><p>For each of <code class="varname">[vorbis_residue_count]</code> residue numbers:
 930  </p><div class="orderedlist"><ol type="a"><li>read the residue type; vector <code class="varname">[vorbis_residue_types]</code> element <code class="varname">[i]</code> = read 16 bits as unsigned integer</li><li>If the residue type is zero,
 931 one or two, decode the residue configuration as defined in <a href="#vorbis-spec-residue" title="8. Residue setup and decode">Section 8, &#8220;Residue setup and decode&#8221;</a>; save this configuration in slot <code class="varname">[i]</code> of the residue configuration array <code class="varname">[vorbis_residue_configurations]</code>.</li><li>If the the residue type is greater than two, this stream is undecodable; ERROR CONDITION</li></ol></div><p>
 932 </p></li></ol></div></div><div class="section" lang="en"><div class="titlepage"><div><div><h5 class="title"><a name="id273643"></a>4.2.4.5. Mappings</h5></div></div></div><p>
 933 Mappings are used to set up specific pipelines for encoding
 934 multichannel audio with varying channel mapping applications. Vorbis I
 935 uses a single mapping type (0), with implicit PCM channel mappings.</p><div class="orderedlist"><ol type="1"><li><code class="varname">[vorbis_mapping_count]</code> = read 6 bits as unsigned integer and add one</li><li><p>For each <code class="varname">[i]</code> of <code class="varname">[vorbis_mapping_count]</code> mapping numbers:
 936   </p><div class="orderedlist"><ol type="a"><li>read the mapping type: 16 bits as unsigned integer.  There's no reason to save the mapping type in Vorbis I.</li><li>If the mapping type is nonzero, the stream is undecodable</li><li><p>If the mapping type is zero:
 937     </p><div class="orderedlist"><ol type="i"><li><p>read 1 bit as a boolean flag
 938       </p><div class="orderedlist"><ol type="A"><li>if set, <code class="varname">[vorbis_mapping_submaps]</code> = read 4 bits as unsigned integer and add one</li><li>if unset, <code class="varname">[vorbis_mapping_submaps]</code> = 1</li></ol></div><p>
 939       </p></li><li><p>read 1 bit as a boolean flag
 940        </p><div class="orderedlist"><ol type="A"><li><p>if set, square polar channel mapping is in use:
 941            </p><div class="orderedlist"><ol type="I"><li><code class="varname">[vorbis_mapping_coupling_steps]</code> = read 8 bits as unsigned integer and add one</li><li><p>for <code class="varname">[j]</code> each of <code class="varname">[vorbis_mapping_coupling_steps]</code> steps:
 942                </p><div class="orderedlist"><ol type="1"><li>vector <code class="varname">[vorbis_mapping_magnitude]</code> element <code class="varname">[j]</code>= read <a href="#vorbis-spec-ilog" title="9.2.1. ilog">ilog</a>(<code class="varname">[audio_channels]</code> - 1) bits as unsigned integer</li><li>vector <code class="varname">[vorbis_mapping_angle]</code> element <code class="varname">[j]</code>= read <a href="#vorbis-spec-ilog" title="9.2.1. ilog">ilog</a>(<code class="varname">[audio_channels]</code> - 1) bits as unsigned integer</li><li>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 <code class="varname">[audio_channels]</code>-1, or the angle channel is greater than <code class="varname">[audio_channels]</code>-1, the stream is undecodable.</li></ol></div><p>
 943                </p></li></ol></div><p>
 944            </p></li><li>if unset, <code class="varname">[vorbis_mapping_coupling_steps]</code> = 0</li></ol></div><p>
 945        </p></li><li>read 2 bits (reserved field); if the value is nonzero, the stream is undecodable</li><li><p>if <code class="varname">[vorbis_mapping_submaps]</code> is greater than one, we read channel multiplex settings. For each <code class="varname">[j]</code> of <code class="varname">[audio_channels]</code> channels:</p><div class="orderedlist"><ol type="A"><li>vector <code class="varname">[vorbis_mapping_mux]</code> element <code class="varname">[j]</code> = read 4 bits as unsigned integer</li><li>if the value is greater than the highest numbered submap (<code class="varname">[vorbis_mapping_submaps]</code> - 1), this in an error condition rendering the stream undecodable</li></ol></div></li><li><p>for each submap <code class="varname">[j]</code> of <code class="varname">[vorbis_mapping_submaps]</code> submaps, read the floor and residue numbers for use in decoding that submap:</p><div class="orderedlist"><ol type="A"><li>read and discard 8 bits (the unused time configuration placeholder)</li><li>read 8 bits as unsigned integer for the floor number; save in vector <code class="varname">[vorbis_mapping_submap_floor]</code> element <code class="varname">[j]</code></li><li>verify the floor number is not greater than the highest number floor configured for the bitstream. If it is, the bitstream is undecodable</li><li>read 8 bits as unsigned integer for the residue number; save in vector <code class="varname">[vorbis_mapping_submap_residue]</code> element <code class="varname">[j]</code></li><li>verify the residue number is not greater than the highest number residue configured for the bitstream.  If it is, the bitstream is undecodable</li></ol></div></li><li>save this mapping configuration in slot <code class="varname">[i]</code> of the mapping configuration array <code class="varname">[vorbis_mapping_configurations]</code>.</li></ol></div></li></ol></div><p>
 946  </p></li></ol></div></div><div class="section" lang="en"><div class="titlepage"><div><div><h5 class="title"><a name="id341202"></a>4.2.4.6. Modes</h5></div></div></div><div class="orderedlist"><ol type="1"><li><code class="varname">[vorbis_mode_count]</code> = read 6 bits as unsigned integer and add one</li><li><p>For each of <code class="varname">[vorbis_mode_count]</code> mode numbers:</p><div class="orderedlist"><ol type="a"><li><code class="varname">[vorbis_mode_blockflag]</code> = read 1 bit</li><li><code class="varname">[vorbis_mode_windowtype]</code> = read 16 bits as unsigned integer</li><li><code class="varname">[vorbis_mode_transformtype]</code> = read 16 bits as unsigned integer</li><li><code class="varname">[vorbis_mode_mapping]</code> = read 8 bits as unsigned integer</li><li>verify ranges; zero is the only legal value in Vorbis I for
 947 <code class="varname">[vorbis_mode_windowtype]</code>
 948 and <code class="varname">[vorbis_mode_transformtype]</code>.  <code class="varname">[vorbis_mode_mapping]</code> must not be greater than the highest number mapping in use.  Any illegal values render the stream undecodable.</li><li>save this mode configuration in slot <code class="varname">[i]</code> of the mode configuration array
 949 <code class="varname">[vorbis_mode_configurations]</code>.</li></ol></div></li><li>read 1 bit as a framing flag.  If unset, a framing error occurred and the stream is not
 950 decodable.</li></ol></div><p>
 951 After reading mode descriptions, setup header decode is complete.
 952 </p></div></div></div><div class="section" lang="en"><div class="titlepage"><div><div><h3 class="title"><a name="id341314"></a>4.3. Audio packet decode and synthesis</h3></div></div></div><p>
 953 Following the three header packets, all packets in a Vorbis I stream
 954 are audio.  The first step of audio packet decode is to read and
 955 verify the packet type. <span class="emphasis"><em>A non-audio packet when audio is expected
 956 indicates stream corruption or a non-compliant stream. The decoder
 957 must ignore the packet and not attempt decoding it to audio</em></span>.
 958 </p><div class="section" lang="en"><div class="titlepage"><div><div><h4 class="title"><a name="id341330"></a>4.3.1. packet type, mode and window decode</h4></div></div></div><div class="orderedlist"><ol type="1"><li>read 1 bit <code class="varname">[packet_type]</code>; check that packet type is 0 (audio)</li><li>read <a href="#vorbis-spec-ilog" title="9.2.1. ilog">ilog</a>([vorbis_mode_count]-1) bits
 959 <code class="varname">[mode_number]</code></li><li>decode blocksize <code class="varname">[n]</code> is equal to <code class="varname">[blocksize_0]</code> if
 960 <code class="varname">[vorbis_mode_blockflag]</code> is 0, else <code class="varname">[n]</code> is equal to <code class="varname">[blocksize_1]</code>.</li><li><p>perform window selection and setup; this window is used later by the inverse MDCT:</p><div class="orderedlist"><ol type="a"><li><p>if this is a long window (the <code class="varname">[vorbis_mode_blockflag]</code> flag of this mode is
 961 set):</p><div class="orderedlist"><ol type="i"><li>read 1 bit for <code class="varname">[previous_window_flag]</code></li><li>read 1 bit for <code class="varname">[next_window_flag]</code></li><li>if <code class="varname">[previous_window_flag]</code> is not set, the left half
 962          of the window will be a hybrid window for lapping with a
 963          short block.  See <a href="#vorbis-spec-window" title="1.3.2.3. Window shape decode (long windows only)">Section 1.3.2.3, &#8220;Window shape decode (long windows only)&#8221;</a> for an illustration of overlapping
 964 dissimilar
 965          windows. Else, the left half window will have normal long
 966          shape.</li><li>if <code class="varname">[next_window_flag]</code> is not set, the right half of
 967          the window will be a hybrid window for lapping with a short
 968          block.  See <a href="#vorbis-spec-window" title="1.3.2.3. Window shape decode (long windows only)">Section 1.3.2.3, &#8220;Window shape decode (long windows only)&#8221;</a> for an
 969 illustration of overlapping dissimilar
 970          windows. Else, the left right window will have normal long
 971          shape.</li></ol></div></li><li> if this is a short window, the window is always the same
 972        short-window shape.</li></ol></div></li></ol></div><p>
 973 Vorbis windows all use the slope function y=sin(0.5 * &#960; * sin^2((x+.5)/n * &#960;)),
 974 where n is window size and x ranges 0...n-1, but dissimilar
 975 lapping requirements can affect overall shape.  Window generation
 976 proceeds as follows:</p><div class="orderedlist"><ol type="1"><li> <code class="varname">[window_center]</code> = <code class="varname">[n]</code> / 2</li><li><p> if (<code class="varname">[vorbis_mode_blockflag]</code> is set and <code class="varname">[previous_window_flag]</code> is
 977 not set) then
 978   </p><div class="orderedlist"><ol type="a"><li><code class="varname">[left_window_start]</code> = <code class="varname">[n]</code>/4 -
 979 <code class="varname">[blocksize_0]</code>/4</li><li><code class="varname">[left_window_end]</code> = <code class="varname">[n]</code>/4 + <code class="varname">[blocksize_0]</code>/4</li><li><code class="varname">[left_n]</code> = <code class="varname">[blocksize_0]</code>/2</li></ol></div><p>
 980  else
 981   </p><div class="orderedlist"><ol type="a"><li><code class="varname">[left_window_start]</code> = 0</li><li><code class="varname">[left_window_end]</code> = <code class="varname">[window_center]</code></li><li><code class="varname">[left_n]</code> = <code class="varname">[n]</code>/2</li></ol></div></li><li><p> if (<code class="varname">[vorbis_mode_blockflag]</code> is set and <code class="varname">[next_window_flag]</code> is not
 982 set) then
 983   </p><div class="orderedlist"><ol type="a"><li><code class="varname">[right_window_start]</code> = <code class="varname">[n]*3</code>/4 -
 984 <code class="varname">[blocksize_0]</code>/4</li><li><code class="varname">[right_window_end]</code> = <code class="varname">[n]*3</code>/4 +
 985 <code class="varname">[blocksize_0]</code>/4</li><li><code class="varname">[right_n]</code> = <code class="varname">[blocksize_0]</code>/2</li></ol></div><p>
 986  else
 987   </p><div class="orderedlist"><ol type="a"><li><code class="varname">[right_window_start]</code> = <code class="varname">[window_center]</code></li><li><code class="varname">[right_window_end]</code> = <code class="varname">[n]</code></li><li><code class="varname">[right_n]</code> = <code class="varname">[n]</code>/2</li></ol></div></li><li> window from range 0 ... <code class="varname">[left_window_start]</code>-1 inclusive is zero</li><li> for <code class="varname">[i]</code> in range <code class="varname">[left_window_start]</code> ...
 988 <code class="varname">[left_window_end]</code>-1, window(<code class="varname">[i]</code>) = sin(.5 * &#960; * sin^2( (<code class="varname">[i]</code>-<code class="varname">[left_window_start]</code>+.5) / <code class="varname">[left_n]</code> * .5 * &#960;) )</li><li> window from range <code class="varname">[left_window_end]</code> ... <code class="varname">[right_window_start]</code>-1
 989 inclusive is one</li><li> for <code class="varname">[i]</code> in range <code class="varname">[right_window_start]</code> ... <code class="varname">[right_window_end]</code>-1, window(<code class="varname">[i]</code>) = sin(.5 * &#960; * sin^2( (<code class="varname">[i]</code>-<code class="varname">[right_window_start]</code>+.5) / <code class="varname">[right_n]</code> * .5 * &#960; + .5 * &#960;) )</li><li> window from range <code class="varname">[right_window_start]</code> ... <code class="varname">[n]</code>-1 is
 990 zero</li></ol></div><p>
 991 An end-of-packet condition up to this point should be considered an
 992 error that discards this packet from the stream.  An end of packet
 993 condition past this point is to be considered a possible nominal
 994 occurrence.</p></div><div class="section" lang="en"><div class="titlepage"><div><div><h4 class="title"><a name="id341794"></a>4.3.2. floor curve decode</h4></div></div></div><p>
 995 From this point on, we assume out decode context is using mode number
 996 <code class="varname">[mode_number]</code> from configuration array
 997 <code class="varname">[vorbis_mode_configurations]</code> and the map number
 998 <code class="varname">[vorbis_mode_mapping]</code> (specified by the current mode) taken
 999 from the mapping configuration array
1000 <code class="varname">[vorbis_mapping_configurations]</code>.</p><p>
1001 Floor curves are decoded one-by-one in channel order.</p><p>
1002 For each floor <code class="varname">[i]</code> of <code class="varname">[audio_channels]</code>
1003  </p><div class="orderedlist"><ol type="1"><li><code class="varname">[submap_number]</code> = element <code class="varname">[i]</code> of vector [vorbis_mapping_mux]</li><li><code class="varname">[floor_number]</code> = element <code class="varname">[submap_number]</code> of vector
1004 [vorbis_submap_floor]</li><li>if the floor type of this
1005 floor (vector <code class="varname">[vorbis_floor_types]</code> element
1006 <code class="varname">[floor_number]</code>) is zero then decode the floor for
1007 channel <code class="varname">[i]</code> according to the
1008 <a href="#vorbis-spec-floor0-decode" title="6.2.2. packet decode">Section 6.2.2, &#8220;packet decode&#8221;</a></li><li>if the type of this floor
1009 is one then decode the floor for channel <code class="varname">[i]</code> according
1010 to the <a href="#vorbis-spec-floor1-decode" title="7.2.2.1. packet decode">Section 7.2.2.1, &#8220;packet decode&#8221;</a></li><li>save the needed decoded floor information for channel for later synthesis</li><li>if the decoded floor returned 'unused', set vector <code class="varname">[no_residue]</code> element
1011 <code class="varname">[i]</code> to true, else set vector <code class="varname">[no_residue]</code> element <code class="varname">[i]</code> to
1012 false</li></ol></div><p>
1013 </p><p>
1014 An end-of-packet condition during floor decode shall result in packet
1015 decode zeroing all channel output vectors and skipping to the
1016 add/overlap output stage.</p></div><div class="section" lang="en"><div class="titlepage"><div><div><h4 class="title"><a name="id341927"></a>4.3.3. nonzero vector propagate</h4></div></div></div><p>
1017 A possible result of floor decode is that a specific vector is marked
1018 'unused' which indicates that that final output vector is all-zero
1019 values (and the floor is zero).  The residue for that vector is not
1020 coded in the stream, save for one complication.  If some vectors are
1021 used and some are not, channel coupling could result in mixing a
1022 zeroed and nonzeroed vector to produce two nonzeroed vectors.</p><p>
1023 for each <code class="varname">[i]</code> from 0 ... <code class="varname">[vorbis_mapping_coupling_steps]</code>-1
1024
1025 </p><div class="orderedlist"><ol type="1"><li>if either <code class="varname">[no_residue]</code> entry for channel
1026 (<code class="varname">[vorbis_mapping_magnitude]</code> element <code class="varname">[i]</code>)
1027 or channel
1028 (<code class="varname">[vorbis_mapping_angle]</code> element <code class="varname">[i]</code>)
1029 are set to false, then both must be set to false.  Note that an 'unused'
1030 floor has no decoded floor information; it is important that this is
1031 remembered at floor curve synthesis time.</li></ol></div><p>
1032 </p></div><div class="section" lang="en"><div class="titlepage"><div><div><h4 class="title"><a name="id341985"></a>4.3.4. residue decode</h4></div></div></div><p>
1033 Unlike floors, which are decoded in channel order, the residue vectors
1034 are decoded in submap order.</p><p>
1035 for each submap <code class="varname">[i]</code> in order from 0 ... <code class="varname">[vorbis_mapping_submaps]</code>-1</p><div class="orderedlist"><ol type="1"><li><code class="varname">[ch]</code> = 0</li><li><p>for each channel <code class="varname">[j]</code> in order from 0 ... <code class="varname">[audio_channels]</code> - 1</p><div class="orderedlist"><ol type="a"><li><p>if channel <code class="varname">[j]</code> in submap <code class="varname">[i]</code> (vector <code class="varname">[vorbis_mapping_mux]</code> element <code class="varname">[j]</code> is equal to <code class="varname">[i]</code>)</p><div class="orderedlist"><ol type="i"><li><p>if vector <code class="varname">[no_residue]</code> element <code class="varname">[j]</code> is true
1036       </p><div class="orderedlist"><ol type="A"><li>vector <code class="varname">[do_not_decode_flag]</code> element <code class="varname">[ch]</code> is set</li></ol></div><p>
1037      else
1038       </p><div class="orderedlist"><ol type="A"><li>vector <code class="varname">[do_not_decode_flag]</code> element <code class="varname">[ch]</code> is unset</li></ol></div></li><li>increment <code class="varname">[ch]</code></li></ol></div></li></ol></div></li><li><code class="varname">[residue_number]</code> = vector <code class="varname">[vorbis_mapping_submap_residue]</code> element <code class="varname">[i]</code></li><li><code class="varname">[residue_type]</code> = vector <code class="varname">[vorbis_residue_types]</code> element <code class="varname">[residue_number]</code></li><li>decode <code class="varname">[ch]</code> vectors using residue <code class="varname">[residue_number]</code>, according to type <code class="varname">[residue_type]</code>, also passing vector <code class="varname">[do_not_decode_flag]</code> to indicate which vectors in the bundle should not be decoded. Correct per-vector decode length is <code class="varname">[n]</code>/2.</li><li><code class="varname">[ch]</code> = 0</li><li><p>for each channel <code class="varname">[j]</code> in order from 0 ... <code class="varname">[audio_channels]</code></p><div class="orderedlist"><ol type="a"><li><p>if channel <code class="varname">[j]</code> is in submap <code class="varname">[i]</code> (vector <code class="varname">[vorbis_mapping_mux]</code> element <code class="varname">[j]</code> is equal to <code class="varname">[i]</code>)</p><div class="orderedlist"><ol type="i"><li>residue vector for channel <code class="varname">[j]</code> is set to decoded residue vector <code class="varname">[ch]</code></li><li>increment <code class="varname">[ch]</code></li></ol></div></li></ol></div></li></ol></div></div><div class="section" lang="en"><div class="titlepage"><div><div><h4 class="title"><a name="id342218"></a>4.3.5. inverse coupling</h4></div></div></div><p>
1039 for each <code class="varname">[i]</code> from <code class="varname">[vorbis_mapping_coupling_steps]</code>-1 descending to 0
1040
1041 </p><div class="orderedlist"><ol type="1"><li><code class="varname">[magnitude_vector]</code> = the residue vector for channel
1042 (vector <code class="varname">[vorbis_mapping_magnitude]</code> element <code class="varname">[i]</code>)</li><li><code class="varname">[angle_vector]</code> = the residue vector for channel (vector
1043 <code class="varname">[vorbis_mapping_angle]</code> element <code class="varname">[i]</code>)</li><li><p>for each scalar value <code class="varname">[M]</code> in vector <code class="varname">[magnitude_vector]</code> and the corresponding scalar value <code class="varname">[A]</code> in vector <code class="varname">[angle_vector]</code>:</p><div class="orderedlist"><ol type="a"><li><p>if (<code class="varname">[M]</code> is greater than zero)
1044     </p><div class="orderedlist"><ol type="i"><li><p>if (<code class="varname">[A]</code> is greater than zero)
1045       </p><div class="orderedlist"><ol type="A"><li><code class="varname">[new_M]</code> = <code class="varname">[M]</code></li><li><code class="varname">[new_A]</code> = <code class="varname">[M]</code>-<code class="varname">[A]</code></li></ol></div><p>
1046      else
1047       </p><div class="orderedlist"><ol type="A"><li><code class="varname">[new_A]</code> = <code class="varname">[M]</code></li><li><code class="varname">[new_M]</code> = <code class="varname">[M]</code>+<code class="varname">[A]</code></li></ol></div><p>
1048      </p></li></ol></div><p>
1049    else
1050     </p><div class="orderedlist"><ol type="i"><li><p>if (<code class="varname">[A]</code> is greater than zero)
1051       </p><div class="orderedlist"><ol type="A"><li><code class="varname">[new_M]</code> = <code class="varname">[M]</code></li><li><code class="varname">[new_A]</code> = <code class="varname">[M]</code>+<code class="varname">[A]</code></li></ol></div><p>
1052      else
1053       </p><div class="orderedlist"><ol type="A"><li><code class="varname">[new_A]</code> = <code class="varname">[M]</code></li><li><code class="varname">[new_M]</code> = <code class="varname">[M]</code>-<code class="varname">[A]</code></li></ol></div><p>
1054      </p></li></ol></div><p>
1055    </p></li><li>set scalar value <code class="varname">[M]</code> in vector <code class="varname">[magnitude_vector]</code> to <code class="varname">[new_M]</code></li><li>set scalar value <code class="varname">[A]</code> in vector <code class="varname">[angle_vector]</code> to <code class="varname">[new_A]</code></li></ol></div></li></ol></div><p>
1056 </p></div><div class="section" lang="en"><div class="titlepage"><div><div><h4 class="title"><a name="id342463"></a>4.3.6. dot product</h4></div></div></div><p>
1057 For each channel, synthesize the floor curve from the decoded floor
1058 information, according to packet type. Note that the vector synthesis
1059 length for floor computation is <code class="varname">[n]</code>/2.</p><p>
1060 For each channel, multiply each element of the floor curve by each
1061 element of that channel's residue vector.  The result is the dot
1062 product of the floor and residue vectors for each channel; the produced
1063 vectors are the length <code class="varname">[n]</code>/2 audio spectrum for each
1064 channel.</p><p>
1065 One point is worth mentioning about this dot product; a common mistake
1066 in a fixed point implementation might be to assume that a 32 bit
1067 fixed-point representation for floor and residue and direct
1068 multiplication of the vectors is sufficient for acceptable spectral
1069 depth in all cases because it happens to mostly work with the current
1070 Xiph.Org reference encoder. </p><p>
1071 However, floor vector values can span ~140dB (~24 bits unsigned), and
1072 the audio spectrum vector should represent a minimum of 120dB (~21
1073 bits with sign), even when output is to a 16 bit PCM device.  For the
1074 residue vector to represent full scale if the floor is nailed to
1075 -140dB, it must be able to span 0 to +140dB.  For the residue vector
1076 to reach full scale if the floor is nailed at 0dB, it must be able to
1077 represent -140dB to +0dB.  Thus, in order to handle full range
1078 dynamics, a residue vector may span -140dB to +140dB entirely within
1079 spec.  A 280dB range is approximately 48 bits with sign; thus the
1080 residue vector must be able to represent a 48 bit range and the dot
1081 product must be able to handle an effective 48 bit times 24 bit
1082 multiplication.  This range may be achieved using large (64 bit or
1083 larger) integers, or implementing a movable binary point
1084 representation.</p></div><div class="section" lang="en"><div class="titlepage"><div><div><h4 class="title"><a name="id342502"></a>4.3.7. inverse MDCT</h4></div></div></div><p>
1085 Convert the audio spectrum vector of each channel back into time
1086 domain PCM audio via an inverse Modified Discrete Cosine Transform
1087 (MDCT).  A detailed description of the MDCT is available in the paper
1088 <a href="http://www.iocon.com/resource/docs/ps/eusipco_corrected.ps" target="_top">&#8220;<span class="citetitle">The
1089 use of multirate filter banks for coding of high quality digital
1090 audio</span>&#8221;</a>, by T. Sporer, K. Brandenburg and B. Edler.  The window
1091 function used for the MDCT is the function described earlier.</p></div><div class="section" lang="en"><div class="titlepage"><div><div><h4 class="title"><a name="id342523"></a>4.3.8. overlap_add</h4></div></div></div><p>
1092 Windowed MDCT output is overlapped and added with the right hand data
1093 of the previous window such that the 3/4 point of the previous window
1094 is aligned with the 1/4 point of the current window (as illustrated in
1095 <a href="#vorbis-spec-window" title="1.3.2.3. Window shape decode (long windows only)">Section 1.3.2.3, &#8220;Window shape decode (long windows only)&#8221;</a>).  The overlapped portion
1096 produced from overlapping the previous and current frame data is
1097 finished data to be returned by the decoder.  This data spans from the
1098 center of the previous window to the center of the current window.  In
1099 the case of same-sized windows, the amount of data to return is
1100 one-half block consisting of and only of the overlapped portions. When
1101 overlapping a short and long window, much of the returned range does not
1102 actually overlap.  This does not damage transform orthogonality.  Pay
1103 attention however to returning the correct data range; the amount of
1104 data to be returned is:
1105
1106 </p><pre class="programlisting">
1107 window_blocksize(previous_window)/4+window_blocksize(current_window)/4
1108 </pre><p>
1109
1110 from the center (element windowsize/2) of the previous window to the
1111 center (element windowsize/2-1, inclusive) of the current window.</p><p>
1112 Data is not returned from the first frame; it must be used to 'prime'
1113 the decode engine.  The encoder accounts for this priming when
1114 calculating PCM offsets; after the first frame, the proper PCM output
1115 offset is '0' (as no data has been returned yet).</p></div><div class="section" lang="en"><div class="titlepage"><div><div><h4 class="title"><a name="id342556"></a>4.3.9. output channel order</h4></div></div></div><p>
1116 Vorbis I specifies only a channel mapping type 0.  In mapping type 0,
1117 channel mapping is implicitly defined as follows for standard audio
1118 applications:</p><div class="variablelist"><dl><dt><span class="term">one channel</span></dt><dd>the stream is monophonic</dd><dt><span class="term">two channels</span></dt><dd>the stream is stereo.  channel order: left, right</dd><dt><span class="term">three channels</span></dt><dd>the stream is a 1d-surround encoding.  channel order: left,
1119 center, right</dd><dt><span class="term">four channels</span></dt><dd>the stream is quadraphonic surround.  channel order: front left,
1120 front right, rear left, rear right</dd><dt><span class="term">five channels</span></dt><dd>the stream is five-channel surround.  channel order: front left,
1121 front center, front right, rear left, rear right</dd><dt><span class="term">six channels</span></dt><dd>the stream is 5.1 surround.  channel order: front left, front
1122 center, front right, rear left, rear right, LFE</dd><dt><span class="term">greater than six channels</span></dt><dd>channel use and order is defined by the application</dd></dl></div><p>
1123 Applications using Vorbis for dedicated purposes may define channel
1124 mapping as seen fit.  Future channel mappings (such as three and four
1125 channel <a href="http://www.ambisonic.net/" target="_top">Ambisonics</a>) will
1126 make use of channel mappings other than mapping 0.</p></div></div></div><div class="section" lang="en"><div class="titlepage"><div><div><h2 class="title" style="clear: both"><a name="vorbis-spec-comment"></a>5. comment field and header specification</h2></div><div><p class="releaseinfo">
1127  $Id: 05-comment.xml 11703 2006-07-17 16:33:17Z giles $
1128 </p></div></div></div><div class="section" lang="en"><div class="titlepage"><div><div><h3 class="title"><a name="id333629"></a>5.1. Overview</h3></div></div></div><p>The Vorbis text comment header is the second (of three) header
1129 packets that begin a Vorbis bitstream. It is meant for short text
1130 comments, not arbitrary metadata; arbitrary metadata belongs in a
1131 separate logical bitstream (usually an XML stream type) that provides
1132 greater structure and machine parseability.</p><p>The comment field is meant to be used much like someone jotting a
1133 quick note on the bottom of a CDR. It should be a little information to
1134 remember the disc by and explain it to others; a short, to-the-point
1135 text note that need not only be a couple words, but isn't going to be
1136 more than a short paragraph.  The essentials, in other words, whatever
1137 they turn out to be, eg:
1138
1139 </p><div class="blockquote"><blockquote class="blockquote"><p>Honest Bob and the Factory-to-Dealer-Incentives, <em class="citetitle">I'm Still
1140 Around</em>, opening for Moxy Früvous, 1997.</p></blockquote></div><p>
1141 </p></div><div class="section" lang="en"><div class="titlepage"><div><div><h3 class="title"><a name="id333657"></a>5.2. Comment encoding</h3></div></div></div><div class="section" lang="en"><div class="titlepage"><div><div><h4 class="title"><a name="id334902"></a>5.2.1. Structure</h4></div></div></div><p>
1142 The comment header is logically a list of eight-bit-clean vectors; the
1143 number of vectors is bounded to 2^32-1 and the length of each vector
1144 is limited to 2^32-1 bytes. The vector length is encoded; the vector
1145 contents themselves are not null terminated. In addition to the vector
1146 list, there is a single vector for vendor name (also 8 bit clean,
1147 length encoded in 32 bits). For example, the 1.0 release of libvorbis
1148 set the vendor string to "Xiph.Org libVorbis I 20020717".</p><p>The comment header is decoded as follows:
1149
1150 </p><pre class="programlisting">
1151   1) [vendor_length] = read an unsigned integer of 32 bits
1152   2) [vendor_string] = read a UTF-8 vector as [vendor_length] octets
1153   3) [user_comment_list_length] = read an unsigned integer of 32 bits
1154   4) iterate [user_comment_list_length] times {
1155        5) [length] = read an unsigned integer of 32 bits
1156        6) this iteration's user comment = read a UTF-8 vector as [length] octets
1157      }
1158   7) [framing_bit] = read a single bit as boolean
1159   8) if ( [framing_bit] unset or end-of-packet ) then ERROR
1160   9) done.
1161 </pre><p>
1162 </p></div><div class="section" lang="en"><div class="titlepage"><div><div><h4 class="title"><a name="id334926"></a>5.2.2. Content vector format</h4></div></div></div><p>
1163 The comment vectors are structured similarly to a UNIX environment variable.
1164 That is, comment fields consist of a field name and a corresponding value and
1165 look like:</p><div class="blockquote"><blockquote class="blockquote"><pre class="programlisting">
1166 comment[0]="ARTIST=me";
1167 comment[1]="TITLE=the sound of Vorbis";
1168 </pre></blockquote></div><p>
1169 The field name is case-insensitive and may consist of ASCII 0x20
1170 through 0x7D, 0x3D ('=') excluded. ASCII 0x41 through 0x5A inclusive
1171 (characters A-Z) is to be considered equivalent to ASCII 0x61 through
1172 0x7A inclusive (characters a-z).
1173 </p><p>
1174 The field name is immediately followed by ASCII 0x3D ('=');
1175 this equals sign is used to terminate the field name.
1176 </p><p>
1177 0x3D is followed by 8 bit clean UTF-8 encoded value of the
1178 field contents to the end of the field.
1179 </p><div class="section" lang="en"><div class="titlepage"><div><div><h5 class="title"><a name="id334955"></a>5.2.2.1. Field names</h5></div></div></div><p>Below is a proposed, minimal list of standard field names with a
1180 description of intended use.  No single or group of field names is
1181 mandatory; a comment header may contain one, all or none of the names
1182 in this list.</p><div class="variablelist"><dl><dt><span class="term">TITLE</span></dt><dd>Track/Work name</dd><dt><span class="term">VERSION</span></dt><dd>The version field may be used to
1183 differentiate multiple
1184 versions of the same track title in a single collection. (e.g. remix
1185 info)
1186 </dd><dt><span class="term">ALBUM</span></dt><dd>The collection name to which this track belongs
1187 </dd><dt><span class="term">TRACKNUMBER</span></dt><dd>The track number of this piece if part of a specific larger collection or album
1188 </dd><dt><span class="term">ARTIST</span></dt><dd>The artist generally considered responsible for the work. In popular music this is usually the performing band or singer. For classical music it would be the composer. For an audio book it would be the author of the original text.
1189 </dd><dt><span class="term">PERFORMER</span></dt><dd>The artist(s) who performed the work. In classical music this would be the conductor, orchestra, soloists. In an audio book it would be the actor who did the reading. In popular music this is typically the same as the ARTIST and is omitted.
1190 </dd><dt><span class="term">COPYRIGHT</span></dt><dd>Copyright attribution, e.g., '2001 Nobody's Band' or '1999 Jack Moffitt'
1191 </dd><dt><span class="term">LICENSE</span></dt><dd>License information, eg, 'All Rights Reserved', 'Any
1192 Use Permitted', a URL to a license such as a Creative Commons license
1193 ("www.creativecommons.org/blahblah/license.html") or the EFF Open
1194 Audio License ('distributed under the terms of the Open Audio
1195 License. see http://www.eff.org/IP/Open_licenses/eff_oal.html for
1196 details'), etc.
1197 </dd><dt><span class="term">ORGANIZATION</span></dt><dd>Name of the organization producing the track (i.e.
1198 the 'record label')
1199 </dd><dt><span class="term">DESCRIPTION</span></dt><dd>A short text description of the contents
1200 </dd><dt><span class="term">GENRE</span></dt><dd>A short text indication of music genre
1201 </dd><dt><span class="term">DATE</span></dt><dd>Date the track was recorded
1202 </dd><dt><span class="term">LOCATION</span></dt><dd>Location where track was recorded
1203 </dd><dt><span class="term">CONTACT</span></dt><dd>Contact information for the creators or distributors of the track. This could be a URL, an email address, the physical address of the producing label.
1204 </dd><dt><span class="term">ISRC</span></dt><dd>International Standard Recording Code for the
1205 track; see <a href="http://www.ifpi.org/isrc/" target="_top">the ISRC
1206 intro page</a> for more information on ISRC numbers.
1207 </dd></dl></div></div><div class="section" lang="en"><div class="titlepage"><div><div><h5 class="title"><a name="id311698"></a>5.2.2.2. Implications</h5></div></div></div><p>Field names should not be 'internationalized'; this is a
1208 concession to simplicity not an attempt to exclude the majority of
1209 the world that doesn't speak English. Field <span class="emphasis"><em>contents</em></span>,
1210 however, use the UTF-8 character encoding to allow easy representation
1211 of any language.</p><p>We have the length of the entirety of the field and restrictions on
1212 the field name so that the field name is bounded in a known way. Thus
1213 we also have the length of the field contents.</p><p>Individual 'vendors' may use non-standard field names within
1214 reason. The proper use of comment fields should be clear through
1215 context at this point.  Abuse will be discouraged.</p><p>There is no vendor-specific prefix to 'nonstandard' field names.
1216 Vendors should make some effort to avoid arbitrarily polluting the
1217 common namespace. We will generally collect the more useful tags
1218 here to help with standardization.</p><p>Field names are not required to be unique (occur once) within a
1219 comment header.  As an example, assume a track was recorded by three
1220 well know artists; the following is permissible, and encouraged:
1221
1222 </p><div class="blockquote"><blockquote class="blockquote"><pre class="programlisting">
1223 ARTIST=Dizzy Gillespie
1224 ARTIST=Sonny Rollins
1225 ARTIST=Sonny Stitt
1226 </pre></blockquote></div><p>
1227
1228 </p></div></div><div class="section" lang="en"><div class="titlepage"><div><div><h4 class="title"><a name="id301005"></a>5.2.3. Encoding</h4></div></div></div><p>
1229 The comment header comprises the entirety of the second bitstream
1230 header packet.  Unlike the first bitstream header packet, it is not
1231 generally the only packet on the second page and may not be restricted
1232 to within the second bitstream page.  The length of the comment header
1233 packet is (practically) unbounded.  The comment header packet is not
1234 optional; it must be present in the bitstream even if it is
1235 effectively empty.</p><p>
1236 The comment header is encoded as follows (as per Ogg's standard
1237 bitstream mapping which renders least-significant-bit of the word to be
1238 coded into the least significant available bit of the current
1239 bitstream octet first):
1240
1241 </p><div class="orderedlist"><ol type="1"><li>
1242   Vendor string length (32 bit unsigned quantity specifying number of octets)
1243  </li><li>
1244   Vendor string ([vendor string length] octets coded from beginning of string to end of string, not null terminated)
1245  </li><li>
1246   Number of comment fields (32 bit unsigned quantity specifying number of fields)
1247  </li><li>
1248   Comment field 0 length (if [Number of comment fields]&gt;0; 32 bit unsigned quantity specifying number of octets)
1249  </li><li>
1250   Comment field 0 ([Comment field 0 length] octets coded from beginning of string to end of string, not null terminated)
1251  </li><li>
1252   Comment field 1 length (if [Number of comment fields]&gt;1...)...
1253  </li></ol></div><p>
1254 </p><p>
1255 This is actually somewhat easier to describe in code; implementation of the above can be found in <code class="filename">vorbis/lib/info.c</code>, <code class="function">_vorbis_pack_comment()</code> and <code class="function">_vorbis_unpack_comment()</code>.
1256 </p></div></div></div><div class="section" lang="en"><div class="titlepage"><div><div><h2 class="title" style="clear: both"><a name="vorbis-spec-floor0"></a>6. Floor type 0 setup and decode</h2></div><div><p class="releaseinfo">
1257   $Id: 06-floor0.xml 14529 2008-02-19 10:15:13Z xiphmont $
1258 </p></div></div></div><div class="section" lang="en"><div class="titlepage"><div><div><h3 class="title"><a name="id320318"></a>6.1. Overview</h3></div></div></div><p>
1259 Vorbis floor type zero uses Line Spectral Pair (LSP, also alternately
1260 known as Line Spectral Frequency or LSF) representation to encode a
1261 smooth spectral envelope curve as the frequency response of the LSP
1262 filter.  This representation is equivalent to a traditional all-pole
1263 infinite impulse response filter as would be used in linear predictive
1264 coding; LSP representation may be converted to LPC representation and
1265 vice-versa.</p></div><div class="section" lang="en"><div class="titlepage"><div><div><h3 class="title"><a name="id324407"></a>6.2. Floor 0 format</h3></div></div></div><p>
1266 Floor zero configuration consists of six integer fields and a list of
1267 VQ codebooks for use in coding/decoding the LSP filter coefficient
1268 values used by each frame. </p><div class="section" lang="en"><div class="titlepage"><div><div><h4 class="title"><a name="id322051"></a>6.2.1. header decode</h4></div></div></div><p>
1269 Configuration information for instances of floor zero decodes from the
1270 codec setup header (third packet).  configuration decode proceeds as
1271 follows:</p><pre class="screen">
1272   1) [floor0_order] = read an unsigned integer of 8 bits
1273   2) [floor0_rate] = read an unsigned integer of 16 bits
1274   3) [floor0_bark_map_size] = read an unsigned integer of 16 bits
1275   4) [floor0_amplitude_bits] = read an unsigned integer of six bits
1276   5) [floor0_amplitude_offset] = read an unsigned integer of eight bits
1277   6) [floor0_number_of_books] = read an unsigned integer of four bits and add 1
1278   7) array [floor0_book_list] = read a list of [floor0_number_of_books] unsigned integers of eight bits each;
1279 </pre><p>
1280 An end-of-packet condition during any of these bitstream reads renders
1281 this stream undecodable.  In addition, any element of the array
1282 <code class="varname">[floor0_book_list]</code> that is greater than the maximum codebook
1283 number for this bitstream is an error condition that also renders the
1284 stream undecodable.</p></div><div class="section" lang="en"><div class="titlepage"><div><div><h4 class="title"><a name="vorbis-spec-floor0-decode"></a>6.2.2. packet decode</h4></div></div></div><p>
1285 Extracting a floor0 curve from an audio packet consists of first
1286 decoding the curve amplitude and <code class="varname">[floor0_order]</code> LSP
1287 coefficient values from the bitstream, and then computing the floor
1288 curve, which is defined as the frequency response of the decoded LSP
1289 filter.</p><p>
1290 Packet decode proceeds as follows:</p><pre class="screen">
1291   1) [amplitude] = read an unsigned integer of [floor0_amplitude_bits] bits
1292   2) if ( [amplitude] is greater than zero ) {
1293        3) [coefficients] is an empty, zero length vector
1294        4) [booknumber] = read an unsigned integer of <a href="#vorbis-spec-ilog" title="9.2.1. ilog">ilog</a>( [floor0_number_of_books] ) bits
1295        5) if ( [booknumber] is greater than the highest number decode codebook ) then packet is undecodable
1296        6) [last] = zero;
1297        7) vector [temp_vector] = read vector from bitstream using codebook number [floor0_book_list] element [booknumber] in VQ context.
1298        8) add the scalar value [last] to each scalar in vector [temp_vector]
1299        9) [last] = the value of the last scalar in vector [temp_vector]
1300       10) concatenate [temp_vector] onto the end of the [coefficients] vector
1301       11) if (length of vector [coefficients] is less than [floor0_order], continue at step 6
1302
1303      }
1304
1305  12) done.
1306
1307 </pre><p>
1308 Take note of the following properties of decode:
1309 </p><div class="itemizedlist"><ul type="disc"><li>An <code class="varname">[amplitude]</code> value of zero must result in a return code that indicates this channel is unused in this frame (the output of the channel will be all-zeroes in synthesis).  Several later stages of decode don't occur for an unused channel.</li><li>An end-of-packet condition during decode should be considered a
1310 nominal occruence; if end-of-packet is reached during any read
1311 operation above, floor decode is to return 'unused' status as if the
1312 <code class="varname">[amplitude]</code> value had read zero at the beginning of decode.</li><li>The book number used for decode
1313 can, in fact, be stored in the bitstream in <a href="#vorbis-spec-ilog" title="9.2.1. ilog">ilog</a>( <code class="varname">[floor0_number_of_books]</code> -
1314 1 ) bits.  Nevertheless, the above specification is correct and values
1315 greater than the maximum possible book value are reserved.</li><li>The number of scalars read into the vector <code class="varname">[coefficients]</code>
1316 may be greater than <code class="varname">[floor0_order]</code>, the number actually
1317 required for curve computation.  For example, if the VQ codebook used
1318 for the floor currently being decoded has a
1319 <code class="varname">[codebook_dimensions]</code> value of three and
1320 <code class="varname">[floor0_order]</code> is ten, the only way to fill all the needed
1321 scalars in <code class="varname">[coefficients]</code> is to to read a total of twelve
1322 scalars as four vectors of three scalars each.  This is not an error
1323 condition, and care must be taken not to allow a buffer overflow in
1324 decode. The extra values are not used and may be ignored or discarded.</li></ul></div><p>
1325 </p></div><div class="section" lang="en"><div class="titlepage"><div><div><h4 class="title"><a name="vorbis-spec-floor0-synth"></a>6.2.3. curve computation</h4></div></div></div><p>
1326 Given an <code class="varname">[amplitude]</code> integer and <code class="varname">[coefficients]</code>
1327 vector from packet decode as well as the [floor0_order],
1328 [floor0_rate], [floor0_bark_map_size], [floor0_amplitude_bits] and
1329 [floor0_amplitude_offset] values from floor setup, and an output
1330 vector size <code class="varname">[n]</code> specified by the decode process, we compute a
1331 floor output vector.</p><p>
1332 If the value <code class="varname">[amplitude]</code> is zero, the return value is a
1333 length <code class="varname">[n]</code> vector with all-zero scalars.  Otherwise, begin by
1334 assuming the following definitions for the given vector to be
1335 synthesized:</p><div class="informalequation"><div class="mediaobject"><img src="lspmap.png" alt="[lsp map equation]"></div></div><p>
1336 The above is used to synthesize the LSP curve on a Bark-scale frequency
1337 axis, then map the result to a linear-scale frequency axis.
1338 Similarly, the below calculation synthesizes the output LSP curve <code class="varname">[output]</code> on a log
1339 (dB) amplitude scale, mapping it to linear amplitude in the last step:</p><div class="orderedlist"><ol type="1"><li> <code class="varname">[i]</code> = 0 </li><li> <code class="varname">[&#969;]</code> = &#960; * map element <code class="varname">[i]</code> / <code class="varname">[floor0_bark_map_size]</code></li><li><p>if ( <code class="varname">[floor0_order]</code> is odd ) {
1340   </p><div class="orderedlist"><ol type="a"><li><p>calculate <code class="varname">[p]</code> and <code class="varname">[q]</code> according to:
1341         </p><div class="informalequation"><div class="mediaobject"><img src="oddlsp.png" alt="[equation for odd lsp]"></div></div><p>
1342    </p></li></ol></div><p>
1343   } else <code class="varname">[floor0_order]</code> is even {
1344   </p><div class="orderedlist"><ol type="a"><li><p>calculate <code class="varname">[p]</code> and <code class="varname">[q]</code> according to:
1345         </p><div class="informalequation"><div class="mediaobject"><img src="evenlsp.png" alt="[equation for even lsp]"></div></div><p>
1346    </p></li></ol></div><p>
1347   }
1348  </p></li><li><p>calculate <code class="varname">[linear_floor_value]</code> according to:
1349      </p><div class="informalequation"><div class="mediaobject"><img src="floorval.png" alt="[expression for floorval]"></div></div><p>
1350  </p></li><li><code class="varname">[iteration_condition]</code> = map element <code class="varname">[i]</code></li><li><code class="varname">[output]</code> element <code class="varname">[i]</code> = <code class="varname">[linear_floor_value]</code></li><li>increment <code class="varname">[i]</code></li><li>if ( map element <code class="varname">[i]</code> is equal to <code class="varname">[iteration_condition]</code> ) continue at step 5</li><li>if ( <code class="varname">[i]</code> is less than <code class="varname">[n]</code> ) continue at step 2</li><li>done</li></ol></div></div></div></div><div class="section" lang="en"><div class="titlepage"><div><div><h2 class="title" style="clear: both"><a name="vorbis-spec-floor1"></a>7. Floor type 1 setup and decode</h2></div><div><p class="releaseinfo">
1351  $Id: 07-floor1.xml 10466 2005-11-28 00:34:44Z giles $
1352 </p></div></div></div><div class="section" lang="en"><div class="titlepage"><div><div><h3 class="title"><a name="id321969"></a>7.1. Overview</h3></div></div></div><p>
1353 Vorbis floor type one uses a piecewise straight-line representation to
1354 encode a spectral envelope curve. The representation plots this curve
1355 mechanically on a linear frequency axis and a logarithmic (dB)
1356 amplitude axis. The integer plotting algorithm used is similar to
1357 Bresenham's algorithm.</p></div><div class="section" lang="en"><div class="titlepage"><div><div><h3 class="title"><a name="id315653"></a>7.2. Floor 1 format</h3></div></div></div><div class="section" lang="en"><div class="titlepage"><div><div><h4 class="title"><a name="id317058"></a>7.2.1. model</h4></div></div></div><p>
1358 Floor type one represents a spectral curve as a series of
1359 line segments.  Synthesis constructs a floor curve using iterative
1360 prediction in a process roughly equivalent to the following simplified
1361 description:</p><p>
1362 </p><div class="itemizedlist"><ul type="disc"><li> the first line segment (base case) is a logical line spanning
1363 from x_0,y_0 to x_1,y_1 where in the base case x_0=0 and x_1=[n], the
1364 full range of the spectral floor to be computed.</li><li>the induction step chooses a point x_new within an existing
1365 logical line segment and produces a y_new value at that point computed
1366 from the existing line's y value at x_new (as plotted by the line) and
1367 a difference value decoded from the bitstream packet.</li><li>floor computation produces two new line segments, one running from
1368 x_0,y_0 to x_new,y_new and from x_new,y_new to x_1,y_1. This step is
1369 performed logically even if y_new represents no change to the
1370 amplitude value at x_new so that later refinement is additionally
1371 bounded at x_new.</li><li>the induction step repeats, using a list of x values specified in
1372 the codec setup header at floor 1 initialization time.  Computation
1373 is completed at the end of the x value list.</li></ul></div><p>
1374 </p><p>
1375 Consider the following example, with values chosen for ease of
1376 understanding rather than representing typical configuration:</p><p>
1377 For the below example, we assume a floor setup with an [n] of 128.
1378 The list of selected X values in increasing order is
1379 0,16,32,48,64,80,96,112 and 128.  In list order, the values interleave
1380 as 0, 128, 64, 32, 96, 16, 48, 80 and 112.  The corresponding
1381 list-order Y values as decoded from an example packet are 110, 20, -5,
1382 -45, 0, -25, -10, 30 and -10.  We compute the floor in the following
1383 way, beginning with the first line:</p><div class="mediaobject"><img src="floor1-1.png" alt="[graph of example floor]"></div><p>
1384 We now draw new logical lines to reflect the correction to new_Y, and
1385 iterate for X positions 32 and 96:</p><div class="mediaobject"><img src="floor1-2.png" alt="[graph of example floor]"></div><p>
1386 Although the new Y value at X position 96 is unchanged, it is still
1387 used later as an endpoint for further refinement.  From here on, the
1388 pattern should be clear; we complete the floor computation as follows:</p><div class="mediaobject"><img src="floor1-3.png" alt="[graph of example floor]"></div><div class="mediaobject"><img src="floor1-4.png" alt="[graph of example floor]"></div><p>
1389 A more efficient algorithm with carefully defined integer rounding
1390 behavior is used for actual decode, as described later.  The actual
1391 algorithm splits Y value computation and line plotting into two steps
1392 with modifications to the above algorithm to eliminate noise
1393 accumulation through integer roundoff/truncation. </p></div><div class="section" lang="en"><div class="titlepage"><div><div><h4 class="title"><a name="id334215"></a>7.2.2. header decode</h4></div></div></div><p>
1394 A list of floor X values is stored in the packet header in interleaved
1395 format (used in list order during packet decode and synthesis).  This
1396 list is split into partitions, and each partition is assigned to a
1397 partition class.  X positions 0 and [n] are implicit and do not belong
1398 to an explicit partition or partition class.</p><p>
1399 A partition class consists of a representation vector width (the
1400 number of Y values which the partition class encodes at once), a
1401 'subclass' value representing the number of alternate entropy books
1402 the partition class may use in representing Y values, the list of
1403 [subclass] books and a master book used to encode which alternate
1404 books were chosen for representation in a given packet.  The
1405 master/subclass mechanism is meant to be used as a flexible
1406 representation cascade while still using codebooks only in a scalar
1407 context.</p><pre class="screen">
1408
1409   1) [floor1_partitions] = read 5 bits as unsigned integer
1410   2) [maximum_class] = -1
1411   3) iterate [i] over the range 0 ... [floor1_partitions]-1 {
1412
1413         4) vector [floor1_partition_class_list] element [i] = read 4 bits as unsigned integer
1414
1415      }
1416
1417   5) [maximum_class] = largest integer scalar value in vector [floor1_partition_class_list]
1418   6) iterate [i] over the range 0 ... [maximum_class] {
1419
1420         7) vector [floor1_class_dimensions] element [i] = read 3 bits as unsigned integer and add 1
1421         8) vector [floor1_class_subclasses] element [i] = read 2 bits as unsigned integer
1422         9) if ( vector [floor1_class_subclasses] element [i] is nonzero ) {
1423
1424              10) vector [floor1_class_masterbooks] element [i] = read 8 bits as unsigned integer
1425
1426            }
1427
1428        11) iterate [j] over the range 0 ... (2 exponent [floor1_class_subclasses] element [i]) - 1  {
1429
1430              12) array [floor1_subclass_books] element [i],[j] =
1431                  read 8 bits as unsigned integer and subtract one
1432            }
1433       }
1434
1435  13) [floor1_multiplier] = read 2 bits as unsigned integer and add one
1436  14) [rangebits] = read 4 bits as unsigned integer
1437  15) vector [floor1_X_list] element [0] = 0
1438  16) vector [floor1_X_list] element [1] = 2 exponent [rangebits];
1439  17) [floor1_values] = 2
1440  18) iterate [i] over the range 0 ... [floor1_partitions]-1 {
1441
1442        19) [current_class_number] = vector [floor1_partition_class_list] element [i]
1443        20) iterate [j] over the range 0 ... ([floor1_class_dimensions] element [current_class_number])-1 {
1444              21) vector [floor1_X_list] element ([floor1_values]) =
1445                  read [rangebits] bits as unsigned integer
1446              22) increment [floor1_values] by one
1447            }
1448      }
1449
1450  23) done
1451 </pre><p>
1452 An end-of-packet condition while reading any aspect of a floor 1
1453 configuration during setup renders a stream undecodable.  In
1454 addition, a <code class="varname">[floor1_class_masterbooks]</code> or
1455 <code class="varname">[floor1_subclass_books]</code> scalar element greater than the
1456 highest numbered codebook configured in this stream is an error
1457 condition that renders the stream undecodable.</p><div class="section" lang="en"><div class="titlepage"><div><div><h5 class="title"><a name="vorbis-spec-floor1-decode"></a>7.2.2.1. packet decode</h5></div></div></div><p>
1458 Packet decode begins by checking the <code class="varname">[nonzero]</code> flag:</p><pre class="screen">
1459   1) [nonzero] = read 1 bit as boolean
1460 </pre><p>
1461 If <code class="varname">[nonzero]</code> is unset, that indicates this channel contained
1462 no audio energy in this frame.  Decode immediately returns a status
1463 indicating this floor curve (and thus this channel) is unused this
1464 frame.  (A return status of 'unused' is different from decoding a
1465 floor that has all points set to minimum representation amplitude,
1466 which happens to be approximately -140dB).
1467 </p><p>
1468 Assuming <code class="varname">[nonzero]</code> is set, decode proceeds as follows:</p><pre class="screen">
1469   1) [range] = vector { 256, 128, 86, 64 } element ([floor1_multiplier]-1)
1470   2) vector [floor1_Y] element [0] = read <a href="#vorbis-spec-ilog" title="9.2.1. ilog">ilog</a>([range]-1) bits as unsigned integer
1471   3) vector [floor1_Y] element [1] = read <a href="#vorbis-spec-ilog" title="9.2.1. ilog">ilog</a>([range]-1) bits as unsigned integer
1472   4) [offset] = 2;
1473   5) iterate [i] over the range 0 ... [floor1_partitions]-1 {
1474
1475        6) [class] = vector [floor1_partition_class]  element [i]
1476        7) [cdim]  = vector [floor1_class_dimensions] element [class]
1477        8) [cbits] = vector [floor1_class_subclasses] element [class]
1478        9) [csub]  = (2 exponent [cbits])-1
1479       10) [cval]  = 0
1480       11) if ( [cbits] is greater than zero ) {
1481
1482              12) [cval] = read from packet using codebook number
1483                  (vector [floor1_class_masterbooks] element [class]) in scalar context
1484           }
1485
1486       13) iterate [j] over the range 0 ... [cdim]-1 {
1487
1488              14) [book] = array [floor1_subclass_books] element [class],([cval] bitwise AND [csub])
1489              15) [cval] = [cval] right shifted [cbits] bits
1490              16) if ( [book] is not less than zero ) {
1491
1492                    17) vector [floor1_Y] element ([j]+[offset]) = read from packet using codebook
1493                        [book] in scalar context
1494
1495                  } else [book] is less than zero {
1496
1497                    18) vector [floor1_Y] element ([j]+[offset]) = 0
1498
1499                  }
1500           }
1501
1502       19) [offset] = [offset] + [cdim]
1503
1504      }
1505
1506  20) done
1507 </pre><p>
1508 An end-of-packet condition during curve decode should be considered a
1509 nominal occurrence; if end-of-packet is reached during any read
1510 operation above, floor decode is to return 'unused' status as if the
1511 <code class="varname">[nonzero]</code> flag had been unset at the beginning of decode.
1512 </p><p>
1513 Vector <code class="varname">[floor1_Y]</code> contains the values from packet decode
1514 needed for floor 1 synthesis.</p></div><div class="section" lang="en"><div class="titlepage"><div><div><h5 class="title"><a name="vorbis-spec-floor1-synth"></a>7.2.2.2. curve computation</h5></div></div></div><p>
1515 Curve computation is split into two logical steps; the first step
1516 derives final Y amplitude values from the encoded, wrapped difference
1517 values taken from the bitstream.  The second step plots the curve
1518 lines.  Also, although zero-difference values are used in the
1519 iterative prediction to find final Y values, these points are
1520 conditionally skipped during final line computation in step two.
1521 Skipping zero-difference values allows a smoother line fit.  </p><p>
1522 Although some aspects of the below algorithm look like inconsequential
1523 optimizations, implementors are warned to follow the details closely.
1524 Deviation from implementing a strictly equivalent algorithm can result
1525 in serious decoding errors.</p><div class="section" lang="en"><div class="titlepage"><div><div><h6 class="title"><a name="id309087"></a>7.2.2.2.1. step 1: amplitude value synthesis</h6></div></div></div><p>
1526 Unwrap the always-positive-or-zero values read from the packet into
1527 +/- difference values, then apply to line prediction.</p><pre class="screen">
1528   1) [range] = vector { 256, 128, 86, 64 } element ([floor1_multiplier]-1)
1529   2) vector [floor1_step2_flag] element [0] = set
1530   3) vector [floor1_step2_flag] element [1] = set
1531   4) vector [floor1_final_Y] element [0] = vector [floor1_Y] element [0]
1532   5) vector [floor1_final_Y] element [1] = vector [floor1_Y] element [1]
1533   6) iterate [i] over the range 2 ... [floor1_values]-1 {
1534
1535        7) [low_neighbor_offset] = <a href="#vorbis-spec-low_neighbor" title="9.2.4. low_neighbor">low_neighbor</a>([floor1_X_list],[i])
1536        8) [high_neighbor_offset] = <a href="#vorbis-spec-high_neighbor" title="9.2.4.1. high_neighbor">high_neighbor</a>([floor1_X_list],[i])
1537
1538        9) [predicted] = <a href="#vorbis-spec-render_point" title="9.2.4.2. render_point">render_point</a>( vector [floor1_X_list] element [low_neighbor_offset],
1539                                       vector [floor1_final_Y] element [low_neighbor_offset],
1540                                       vector [floor1_X_list] element [high_neighbor_offset],
1541                                       vector [floor1_final_Y] element [high_neighbor_offset],
1542                                       vector [floor1_X_list] element [i] )
1543
1544       10) [val] = vector [floor1_Y] element [i]
1545       11) [highroom] = [range] - [predicted]
1546       12) [lowroom]  = [predicted]
1547       13) if ( [highroom] is less than [lowroom] ) {
1548
1549             14) [room] = [highroom] * 2
1550
1551           } else [highroom] is not less than [lowroom] {
1552
1553             15) [room] = [lowroom] * 2
1554
1555           }
1556
1557       16) if ( [val] is nonzero ) {
1558
1559             17) vector [floor1_step2_flag] element [low_neighbor_offset] = set
1560             18) vector [floor1_step2_flag] element [high_neighbor_offset] = set
1561             19) vector [floor1_step2_flag] element [i] = set
1562             20) if ( [val] is greater than or equal to [room] ) {
1563
1564                   21) if ( [highroom] is greater than [lowroom] ) {
1565
1566                         22) vector [floor1_final_Y] element [i] = [val] - [lowroom] + [predicted]
1567
1568                       } else [highroom] is not greater than [lowroom] {
1569
1570                         23) vector [floor1_final_Y] element [i] = [predicted] - [val] + [highroom] - 1
1571
1572                       }
1573
1574                 } else [val] is less than [room] {
1575
1576                   24) if ([val] is odd) {
1577
1578                         25) vector [floor1_final_Y] element [i] =
1579                             [predicted] - (([val] + 1) divided by  2 using integer division)
1580
1581                       } else [val] is even {
1582
1583                         26) vector [floor1_final_Y] element [i] =
1584                             [predicted] + ([val] / 2 using integer division)
1585
1586                       }
1587
1588                 }
1589
1590           } else [val] is zero {
1591
1592             27) vector [floor1_step2_flag] element [i] = unset
1593             28) vector [floor1_final_Y] element [i] = [predicted]
1594
1595           }
1596
1597      }
1598
1599  29) done
1600
1601 </pre></div><div class="section" lang="en"><div class="titlepage"><div><div><h6 class="title"><a name="id309123"></a>7.2.2.2.2. step 2: curve synthesis</h6></div></div></div><p>
1602 Curve synthesis generates a return vector <code class="varname">[floor]</code> of length
1603 <code class="varname">[n]</code> (where <code class="varname">[n]</code> is provided by the decode process
1604 calling to floor decode).  Floor 1 curve synthesis makes use of the
1605 <code class="varname">[floor1_X_list]</code>, <code class="varname">[floor1_final_Y]</code> and
1606 <code class="varname">[floor1_step2_flag]</code> vectors, as well as [floor1_multiplier]
1607 and [floor1_values] values.</p><p>
1608 Decode begins by sorting the scalars from vectors
1609 <code class="varname">[floor1_X_list]</code>, <code class="varname">[floor1_final_Y]</code> and
1610 <code class="varname">[floor1_step2_flag]</code> together into new vectors
1611 <code class="varname">[floor1_X_list]'</code>, <code class="varname">[floor1_final_Y]'</code> and
1612 <code class="varname">[floor1_step2_flag]'</code> according to ascending sort order of the
1613 values in <code class="varname">[floor1_X_list]</code>.  That is, sort the values of
1614 <code class="varname">[floor1_X_list]</code> and then apply the same permutation to
1615 elements of the other two vectors so that the X, Y and step2_flag
1616 values still match.</p><p>
1617 Then compute the final curve in one pass:</p><pre class="screen">
1618   1) [hx] = 0
1619   2) [lx] = 0
1620   3) [ly] = vector [floor1_final_Y]' element [0] * [floor1_multiplier]
1621   4) iterate [i] over the range 1 ... [floor1_values]-1 {
1622
1623        5) if ( [floor1_step2_flag]' element [i] is set ) {
1624
1625              6) [hy] = [floor1_final_Y]' element [i] * [floor1_multiplier]
1626              7) [hx] = [floor1_X_list]' element [i]
1627              8) <a href="#vorbis-spec-render_line" title="9.2.4.3. render_line">render_line</a>( [lx], [ly], [hx], [hy], [floor] )
1628              9) [lx] = [hx]
1629             10) [ly] = [hy]
1630           }
1631      }
1632
1633  11) if ( [hx] is less than [n] ) {
1634
1635         12) <a href="#vorbis-spec-render_line" title="9.2.4.3. render_line">render_line</a>( [hx], [hy], [n], [hy], [floor] )
1636
1637      }
1638
1639  13) if ( [hx] is greater than [n] ) {
1640
1641             14) truncate vector [floor] to [n] elements
1642
1643      }
1644
1645  15) for each scalar in vector [floor], perform a lookup substitution using
1646      the scalar value from [floor] as an offset into the vector <a href="#vorbis-spec-floor1_inverse_dB_table" title="10.1. floor1_inverse_dB_table">[floor1_inverse_dB_static_table]</a>
1647
1648  16) done
1649
1650 </pre></div></div></div></div></div><div class="section" lang="en"><div class="titlepage"><div><div><h2 class="title" style="clear: both"><a name="vorbis-spec-residue"></a>8. Residue setup and decode</h2></div><div><p class="releaseinfo">
1651   $Id: 08-residue.xml 14598 2008-03-18 15:39:43Z xiphmont $
1652  </p></div></div></div><div class="section" lang="en"><div class="titlepage"><div><div><h3 class="title"><a name="id333002"></a>8.1. Overview</h3></div></div></div><p>
1653 A residue vector represents the fine detail of the audio spectrum of
1654 one channel in an audio frame after the encoder subtracts the floor
1655 curve and performs any channel coupling.  A residue vector may
1656 represent spectral lines, spectral magnitude, spectral phase or
1657 hybrids as mixed by channel coupling.  The exact semantic content of
1658 the vector does not matter to the residue abstraction.</p><p>
1659 Whatever the exact qualities, the Vorbis residue abstraction codes the
1660 residue vectors into the bitstream packet, and then reconstructs the
1661 vectors during decode.  Vorbis makes use of three different encoding
1662 variants (numbered 0, 1 and 2) of the same basic vector encoding
1663 abstraction.</p></div><div class="section" lang="en"><div class="titlepage"><div><div><h3 class="title"><a name="id327769"></a>8.2. Residue format</h3></div></div></div><p>
1664 Residue format partitions each vector in the vector bundle into chunks,
1665 classifies each chunk, encodes the chunk classifications and finally
1666 encodes the chunks themselves using the the specific VQ arrangement
1667 defined for each selected classification.
1668 The exact interleaving and partitioning vary by residue encoding number,
1669 however the high-level process used to classify and encode the residue
1670 vector is the same in all three variants.</p><p>
1671 A set of coded residue vectors are all of the same length.  High level
1672 coding structure, ignoring for the moment exactly how a partition is
1673 encoded and simply trusting that it is, is as follows:</p><p>
1674 </p><div class="itemizedlist"><ul type="disc"><li><p>Each vector is partitioned into multiple equal sized chunks
1675 according to configuration specified.  If we have a vector size of
1676 <span class="emphasis"><em>n</em></span>, a partition size <span class="emphasis"><em>residue_partition_size</em></span>, and a total
1677 of <span class="emphasis"><em>ch</em></span> residue vectors, the total number of partitioned chunks
1678 coded is <span class="emphasis"><em>n</em></span>/<span class="emphasis"><em>residue_partition_size</em></span>*<span class="emphasis"><em>ch</em></span>.  It is
1679 important to note that the integer division truncates.  In the below
1680 example, we assume an example <span class="emphasis"><em>residue_partition_size</em></span> of 8.</p></li><li><p>Each partition in each vector has a classification number that
1681 specifies which of multiple configured VQ codebook setups are used to
1682 decode that partition.  The classification numbers of each partition
1683 can be thought of as forming a vector in their own right, as in the
1684 illustration below.  Just as the residue vectors are coded in grouped
1685 partitions to increase encoding efficiency, the classification vector
1686 is also partitioned into chunks.  The integer elements of each scalar
1687 in a classification chunk are built into a single scalar that
1688 represents the classification numbers in that chunk.  In the below
1689 example, the classification codeword encodes two classification
1690 numbers.</p></li><li><p>The values in a residue vector may be encoded monolithically in a
1691 single pass through the residue vector, but more often efficient
1692 codebook design dictates that each vector is encoded as the additive
1693 sum of several passes through the residue vector using more than one
1694 VQ codebook.  Thus, each residue value potentially accumulates values
1695 from multiple decode passes.  The classification value associated with
1696 a partition is the same in each pass, thus the classification codeword
1697 is coded only in the first pass.</p></li></ul></div><p>
1698 </p><div class="mediaobject"><img src="residue-pack.png" alt="[illustration of residue vector format]"></div></div><div class="section" lang="en"><div class="titlepage"><div><div><h3 class="title"><a name="id318469"></a>8.3. residue 0</h3></div></div></div><p>
1699 Residue 0 and 1 differ only in the way the values within a residue
1700 partition are interleaved during partition encoding (visually treated
1701 as a black box--or cyan box or brown box--in the above figure).</p><p>
1702 Residue encoding 0 interleaves VQ encoding according to the
1703 dimension of the codebook used to encode a partition in a specific
1704 pass.  The dimension of the codebook need not be the same in multiple
1705 passes, however the partition size must be an even multiple of the
1706 codebook dimension.</p><p>
1707 As an example, assume a partition vector of size eight, to be encoded
1708 by residue 0 using codebook sizes of 8, 4, 2 and 1:</p><pre class="programlisting">
1709
1710             original residue vector: [ 0 1 2 3 4 5 6 7 ]
1711
1712 codebook dimensions = 8  encoded as: [ 0 1 2 3 4 5 6 7 ]
1713
1714 codebook dimensions = 4  encoded as: [ 0 2 4 6 ], [ 1 3 5 7 ]
1715
1716 codebook dimensions = 2  encoded as: [ 0 4 ], [ 1 5 ], [ 2 6 ], [ 3 7 ]
1717
1718 codebook dimensions = 1  encoded as: [ 0 ], [ 1 ], [ 2 ], [ 3 ], [ 4 ], [ 5 ], [ 6 ], [ 7 ]
1719
1720 </pre><p>
1721 It is worth mentioning at this point that no configurable value in the
1722 residue coding setup is restricted to a power of two.</p></div><div class="section" lang="en"><div class="titlepage"><div><div><h3 class="title"><a name="id343071"></a>8.4. residue 1</h3></div></div></div><p>
1723 Residue 1 does not interleave VQ encoding.  It represents partition
1724 vector scalars in order.  As with residue 0, however, partition length
1725 must be an integer multiple of the codebook dimension, although
1726 dimension may vary from pass to pass.</p><p>
1727 As an example, assume a partition vector of size eight, to be encoded
1728 by residue 0 using codebook sizes of 8, 4, 2 and 1:</p><pre class="programlisting">
1729
1730             original residue vector: [ 0 1 2 3 4 5 6 7 ]
1731
1732 codebook dimensions = 8  encoded as: [ 0 1 2 3 4 5 6 7 ]
1733
1734 codebook dimensions = 4  encoded as: [ 0 1 2 3 ], [ 4 5 6 7 ]
1735
1736 codebook dimensions = 2  encoded as: [ 0 1 ], [ 2 3 ], [ 4 5 ], [ 6 7 ]
1737
1738 codebook dimensions = 1  encoded as: [ 0 ], [ 1 ], [ 2 ], [ 3 ], [ 4 ], [ 5 ], [ 6 ], [ 7 ]
1739
1740 </pre></div><div class="section" lang="en"><div class="titlepage"><div><div><h3 class="title"><a name="id343096"></a>8.5. residue 2</h3></div></div></div><p>
1741 Residue type two can be thought of as a variant of residue type 1.
1742 Rather than encoding multiple passed-in vectors as in residue type 1,
1743 the <span class="emphasis"><em>ch</em></span> passed in vectors of length <span class="emphasis"><em>n</em></span> are first
1744 interleaved and flattened into a single vector of length
1745 <span class="emphasis"><em>ch</em></span>*<span class="emphasis"><em>n</em></span>.  Encoding then proceeds as in type 1. Decoding is
1746 as in type 1 with decode interleave reversed. If operating on a single
1747 vector to begin with, residue type 1 and type 2 are equivalent.</p><div class="mediaobject"><img src="residue2.png" alt="[illustration of residue type 2]"></div></div><div class="section" lang="en"><div class="titlepage"><div><div><h3 class="title"><a name="id343145"></a>8.6. Residue decode</h3></div></div></div><div class="section" lang="en"><div class="titlepage"><div><div><h4 class="title"><a name="id343151"></a>8.6.1. header decode</h4></div></div></div><p>
1748 Header decode for all three residue types is identical.</p><pre class="programlisting">
1749   1) [residue_begin] = read 24 bits as unsigned integer
1750   2) [residue_end] = read 24 bits as unsigned integer
1751   3) [residue_partition_size] = read 24 bits as unsigned integer and add one
1752   4) [residue_classifications] = read 6 bits as unsigned integer and add one
1753   5) [residue_classbook] = read 8 bits as unsigned integer
1754 </pre><p>
1755 <code class="varname">[residue_begin]</code> and
1756 <code class="varname">[residue_end]</code> select the specific sub-portion of
1757 each vector that is actually coded; it implements akin to a bandpass
1758 where, for coding purposes, the vector effectively begins at element
1759 <code class="varname">[residue_begin]</code> and ends at
1760 <code class="varname">[residue_end]</code>.  Preceding and following values in
1761 the unpacked vectors are zeroed.  Note that for residue type 2, these
1762 values as well as <code class="varname">[residue_partition_size]</code>apply to
1763 the interleaved vector, not the individual vectors before interleave.
1764 <code class="varname">[residue_partition_size]</code> is as explained above,
1765 <code class="varname">[residue_classifications]</code> is the number of possible
1766 classification to which a partition can belong and
1767 <code class="varname">[residue_classbook]</code> is the codebook number used to
1768 code classification codewords.  The number of dimensions in book
1769 <code class="varname">[residue_classbook]</code> determines how many
1770 classification values are grouped into a single classification
1771 codeword.  Note that the number of entries and dimensions in book
1772 <code class="varname">[residue_classbook]</code>, along with
1773 <code class="varname">[residue_classifications]</code>, overdetermines to
1774 possible number of classification codewords.  If
1775 <code class="varname">[residue_classifications]</code>^<code class="varname">[residue_classbook]</code>.dimensions
1776 does not equal <code class="varname">[residue_classbook]</code>.entries, the
1777 bitstream should be regarded to be undecodable. </p><p>
1778 Next we read a bitmap pattern that specifies which partition classes
1779 code values in which passes.</p><pre class="programlisting">
1780   1) iterate [i] over the range 0 ... [residue_classifications]-1 {
1781
1782        2) [high_bits] = 0
1783        3) [low_bits] = read 3 bits as unsigned integer
1784        4) [bitflag] = read one bit as boolean
1785        5) if ( [bitflag] is set ) then [high_bits] = read five bits as unsigned integer
1786        6) vector [residue_cascade] element [i] = [high_bits] * 8 + [low_bits]
1787      }
1788   7) done
1789 </pre><p>
1790 Finally, we read in a list of book numbers, each corresponding to
1791 specific bit set in the cascade bitmap.  We loop over the possible
1792 codebook classifications and the maximum possible number of encoding
1793 stages (8 in Vorbis I, as constrained by the elements of the cascade
1794 bitmap being eight bits):</p><pre class="programlisting">
1795   1) iterate [i] over the range 0 ... [residue_classifications]-1 {
1796
1797        2) iterate [j] over the range 0 ... 7 {
1798
1799             3) if ( vector [residue_cascade] element [i] bit [j] is set ) {
1800
1801                  4) array [residue_books] element [i][j] = read 8 bits as unsigned integer
1802
1803                } else {
1804
1805                  5) array [residue_books] element [i][j] = unused
1806
1807                }
1808           }
1809       }
1810
1811   6) done
1812 </pre><p>
1813 An end-of-packet condition at any point in header decode renders the
1814 stream undecodable.  In addition, any codebook number greater than the
1815 maximum numbered codebook set up in this stream also renders the
1816 stream undecodable.</p></div><div class="section" lang="en"><div class="titlepage"><div><div><h4 class="title"><a name="id304464"></a>8.6.2. packet decode</h4></div></div></div><p>
1817 Format 0 and 1 packet decode is identical except for specific
1818 partition interleave.  Format 2 packet decode can be built out of the
1819 format 1 decode process.  Thus we describe first the decode
1820 infrastructure identical to all three formats.</p><p>
1821 In addition to configuration information, the residue decode process
1822 is passed the number of vectors in the submap bundle and a vector of
1823 flags indicating if any of the vectors are not to be decoded.  If the
1824 passed in number of vectors is 3 and vector number 1 is marked 'do not
1825 decode', decode skips vector 1 during the decode loop.  However, even
1826 'do not decode' vectors are allocated and zeroed.</p><p>
1827 Depending on the values of <code class="varname">[residue_begin]</code> and
1828 <code class="varname">[residue_end]</code>, it is obvious that the encoded
1829 portion of a residue vector may be the entire possible residue vector
1830 or some other strict subset of the actual residue vector size with
1831 zero padding at either uncoded end.  However, it is also possible to
1832 set <code class="varname">[residue_begin]</code> and
1833 <code class="varname">[residue_end]</code> to specify a range partially or
1834 wholly beyond the maximum vector size.  Before beginning residue
1835 decode, limit <code class="varname">[residue_begin]</code> and
1836 <code class="varname">[residue_end]</code> to the maximum possible vector size
1837 as follows.  We assume that the number of vectors being encoded,
1838 <code class="varname">[ch]</code> is provided by the higher level decoding
1839 process.</p><pre class="programlisting">
1840   1) [actual_size] = current blocksize/2;
1841   2) if residue encoding is format 2
1842        3) [actual_size] = [actual_size] * [ch];
1843   4) [limit_residue_begin] = maximum of ([residue_begin],[actual_size]);
1844   5) [limit_residue_end] = maximum of ([residue_end],[actual_size]);
1845 </pre><p>
1846 The following convenience values are conceptually useful to clarifying
1847 the decode process:</p><pre class="programlisting">
1848   1) [classwords_per_codeword] = [codebook_dimensions] value of codebook [residue_classbook]
1849   2) [n_to_read] = [limit_residue_end] - [limit_residue_begin]
1850   3) [partitions_to_read] = [n_to_read] / [residue_partition_size]
1851 </pre><p>
1852 Packet decode proceeds as follows, matching the description offered earlier in the document. </p><pre class="programlisting">
1853   1) allocate and zero all vectors that will be returned.
1854   2) if ([n_to_read] is zero), stop; there is no residue to decode.
1855   3) iterate [pass] over the range 0 ... 7 {
1856
1857        4) [partition_count] = 0
1858
1859        5) while [partition_count] is less than [partitions_to_read]
1860
1861             6) if ([pass] is zero) {
1862
1863                  7) iterate [j] over the range 0 .. [ch]-1 {
1864
1865                       8) if vector [j] is not marked 'do not decode' {
1866
1867                            9) [temp] = read from packet using codebook [residue_classbook] in scalar context
1868                           10) iterate [i] descending over the range [classwords_per_codeword]-1 ... 0 {
1869
1870                                11) array [classifications] element [j],([i]+[partition_count]) =
1871                                    [temp] integer modulo [residue_classifications]
1872                                12) [temp] = [temp] / [residue_classifications] using integer division
1873
1874                               }
1875
1876                          }
1877
1878                     }
1879
1880                }
1881
1882            13) iterate [i] over the range 0 .. ([classwords_per_codeword] - 1) while [partition_count]
1883                is also less than [partitions_to_read] {
1884
1885                  14) iterate [j] over the range 0 .. [ch]-1 {
1886
1887                       15) if vector [j] is not marked 'do not decode' {
1888
1889                            16) [vqclass] = array [classifications] element [j],[partition_count]
1890                            17) [vqbook] = array [residue_books] element [vqclass],[pass]
1891                            18) if ([vqbook] is not 'unused') {
1892
1893                                 19) decode partition into output vector number [j], starting at scalar
1894                                     offset [limit_residue_begin]+[partition_count]*[residue_partition_size] using
1895                                     codebook number [vqbook] in VQ context
1896                           }
1897                      }
1898
1899                  20) increment [partition_count] by one
1900
1901                }
1902           }
1903      }
1904
1905  21) done
1906
1907 </pre><p>
1908 An end-of-packet condition during packet decode is to be considered a
1909 nominal occurrence.  Decode returns the result of vector decode up to
1910 that point.</p></div><div class="section" lang="en"><div class="titlepage"><div><div><h4 class="title"><a name="id326098"></a>8.6.3. format 0 specifics</h4></div></div></div><p>
1911 Format zero decodes partitions exactly as described earlier in the
1912 'Residue Format: residue 0' section.  The following pseudocode
1913 presents the same algorithm. Assume:</p><p>
1914 </p><div class="itemizedlist"><ul type="disc"><li> <code class="varname">[n]</code> is the value in <code class="varname">[residue_partition_size]</code></li><li><code class="varname">[v]</code> is the residue vector</li><li><code class="varname">[offset]</code> is the beginning read offset in [v]</li></ul></div><p>
1915 </p><pre class="programlisting">
1916  1) [step] = [n] / [codebook_dimensions]
1917  2) iterate [i] over the range 0 ... [step]-1 {
1918
1919       3) vector [entry_temp] = read vector from packet using current codebook in VQ context
1920       4) iterate [j] over the range 0 ... [codebook_dimensions]-1 {
1921
1922            5) vector [v] element ([offset]+[i]+[j]*[step]) =
1923                 vector [v] element ([offset]+[i]+[j]*[step]) +
1924                 vector [entry_temp] element [j]
1925
1926          }
1927
1928     }
1929
1930   6) done
1931
1932 </pre></div><div class="section" lang="en"><div class="titlepage"><div><div><h4 class="title"><a name="id307089"></a>8.6.4. format 1 specifics</h4></div></div></div><p>
1933 Format 1 decodes partitions exactly as described earlier in the
1934 'Residue Format: residue 1' section.  The following pseudocode
1935 presents the same algorithm. Assume:</p><p>
1936 </p><div class="itemizedlist"><ul type="disc"><li> <code class="varname">[n]</code> is the value in
1937 <code class="varname">[residue_partition_size]</code></li><li><code class="varname">[v]</code> is the residue vector</li><li><code class="varname">[offset]</code> is the beginning read offset in [v]</li></ul></div><p>
1938 </p><pre class="programlisting">
1939  1) [i] = 0
1940  2) vector [entry_temp] = read vector from packet using current codebook in VQ context
1941  3) iterate [j] over the range 0 ... [codebook_dimensions]-1 {
1942
1943       4) vector [v] element ([offset]+[i]) =
1944           vector [v] element ([offset]+[i]) +
1945           vector [entry_temp] element [j]
1946       5) increment [i]
1947
1948     }
1949
1950   6) if ( [i] is less than [n] ) continue at step 2
1951   7) done
1952 </pre></div><div class="section" lang="en"><div class="titlepage"><div><div><h4 class="title"><a name="id307141"></a>8.6.5. format 2 specifics</h4></div></div></div><p>
1953 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.
1954 </p><p>
1955 Format 2 handles 'do not decode' vectors differently than residue 0 or
1956 1; if all vectors are marked 'do not decode', no decode occurrs.
1957 However, if at least one vector is to be decoded, all the vectors are
1958 decoded.  We then request normal format 1 to decode a single vector
1959 representing all output channels, rather than a vector for each
1960 channel.  After decode, deinterleave the vector into independent vectors, one for each output channel.  That is:</p><div class="orderedlist"><ol type="1"><li>If all vectors 0 through <span class="emphasis"><em>ch</em></span>-1 are marked 'do not decode', allocate and clear a single vector <code class="varname">[v]</code>of length <span class="emphasis"><em>ch*n</em></span> and skip step 2 below; proceed directly to the post-decode step.</li><li>Rather than performing format 1 decode to produce <span class="emphasis"><em>ch</em></span> vectors of length <span class="emphasis"><em>n</em></span> each, call format 1 decode to produce a single vector <code class="varname">[v]</code> of length <span class="emphasis"><em>ch*n</em></span>. </li><li><p>Post decode: Deinterleave the single vector <code class="varname">[v]</code> returned by format 1 decode as described above into <span class="emphasis"><em>ch</em></span> independent vectors, one for each outputchannel, according to:
1961   </p><pre class="programlisting">
1962   1) iterate [i] over the range 0 ... [n]-1 {
1963
1964        2) iterate [j] over the range 0 ... [ch]-1 {
1965
1966             3) output vector number [j] element [i] = vector [v] element ([i] * [ch] + [j])
1967
1968           }
1969      }
1970
1971   4) done
1972   </pre><p>
1973  </p></li></ol></div></div></div></div><div class="section" lang="en"><div class="titlepage"><div><div><h2 class="title" style="clear: both"><a name="vorbis-spec-helper"></a>9. Helper equations</h2></div><div><p class="releaseinfo">
1974  $Id: 09-helper.xml 7186 2004-07-20 07:19:25Z xiphmont $
1975 </p></div></div></div><div class="section" lang="en"><div class="titlepage"><div><div><h3 class="title"><a name="id325073"></a>9.1. Overview</h3></div></div></div><p>
1976 The equations below are used in multiple places by the Vorbis codec
1977 specification.  Rather than cluttering up the main specification
1978 documents, they are defined here and referenced where appropriate.
1979 </p></div><div class="section" lang="en"><div class="titlepage"><div><div><h3 class="title"><a name="id306980"></a>9.2. Functions</h3></div></div></div><div class="section" lang="en"><div class="titlepage"><div><div><h4 class="title"><a name="vorbis-spec-ilog"></a>9.2.1. ilog</h4></div></div></div><p>
1980 The "ilog(x)" function returns the position number (1 through n) of the highest set bit in the two's complement integer value
1981 <code class="varname">[x]</code>.  Values of <code class="varname">[x]</code> less than zero are defined to return zero.</p><pre class="programlisting">
1982   1) [return_value] = 0;
1983   2) if ( [x] is greater than zero ){
1984
1985        3) increment [return_value];
1986        4) logical shift [x] one bit to the right, padding the MSb with zero
1987        5) repeat at step 2)
1988
1989      }
1990
1991    6) done
1992 </pre><p>
1993 Examples:
1994
1995 </p><div class="itemizedlist"><ul type="disc"><li>ilog(0) = 0;</li><li>ilog(1) = 1;</li><li>ilog(2) = 2;</li><li>ilog(3) = 2;</li><li>ilog(4) = 3;</li><li>ilog(7) = 3;</li><li>ilog(negative number) = 0;</li></ul></div><p>
1996 </p></div><div class="section" lang="en"><div class="titlepage"><div><div><h4 class="title"><a name="vorbis-spec-float32_unpack"></a>9.2.2. float32_unpack</h4></div></div></div><p>
1997 "float32_unpack(x)" is intended to translate the packed binary
1998 representation of a Vorbis codebook float value into the
1999 representation used by the decoder for floating point numbers.  For
2000 purposes of this example, we will unpack a Vorbis float32 into a
2001 host-native floating point number.</p><pre class="programlisting">
2002   1) [mantissa] = [x] bitwise AND 0x1fffff (unsigned result)
2003   2) [sign] = [x] bitwise AND 0x80000000 (unsigned result)
2004   3) [exponent] = ( [x] bitwise AND 0x7fe00000) shifted right 21 bits (unsigned result)
2005   4) if ( [sign] is nonzero ) then negate [mantissa]
2006   5) return [mantissa] * ( 2 ^ ( [exponent] - 788 ) )
2007 </pre></div><div class="section" lang="en"><div class="titlepage"><div><div><h4 class="title"><a name="vorbis-spec-lookup1_values"></a>9.2.3. lookup1_values</h4></div></div></div><p>
2008 "lookup1_values(codebook_entries,codebook_dimensions)" is used to
2009 compute the correct length of the value index for a codebook VQ lookup
2010 table of lookup type 1.  The values on this list are permuted to
2011 construct the VQ vector lookup table of size
2012 <code class="varname">[codebook_entries]</code>.</p><p>
2013 The return value for this function is defined to be 'the greatest
2014 integer value for which <code class="varname">[return_value] to the power of
2015 [codebook_dimensions] is less than or equal to
2016 [codebook_entries]</code>'.</p></div><div class="section" lang="en"><div class="titlepage"><div><div><h4 class="title"><a name="vorbis-spec-low_neighbor"></a>9.2.4. low_neighbor</h4></div></div></div><p>
2017 "low_neighbor(v,x)" finds the position <code class="varname">n</code> in vector <code class="varname">[v]</code> of
2018 the greatest value scalar element for which <code class="varname">n</code> is less than
2019 <code class="varname">[x]</code> and vector <code class="varname">[v]</code> element <code class="varname">n</code> is less
2020 than vector <code class="varname">[v]</code> element <code class="varname">[x]</code>.</p><div class="section" lang="en"><div class="titlepage"><div><div><h5 class="title"><a name="vorbis-spec-high_neighbor"></a>9.2.4.1. high_neighbor</h5></div></div></div><p>
2021 "high_neighbor(v,x)" finds the position <code class="varname">n</code> in vector [v] of
2022 the lowest value scalar element for which <code class="varname">n</code> is less than
2023 <code class="varname">[x]</code> and vector <code class="varname">[v]</code> element <code class="varname">n</code> is greater
2024 than vector <code class="varname">[v]</code> element <code class="varname">[x]</code>.</p></div><div class="section" lang="en"><div class="titlepage"><div><div><h5 class="title"><a name="vorbis-spec-render_point"></a>9.2.4.2. render_point</h5></div></div></div><p>
2025 "render_point(x0,y0,x1,y1,X)" is used to find the Y value at point X
2026 along the line specified by x0, x1, y0 and y1.  This function uses an
2027 integer algorithm to solve for the point directly without calculating
2028 intervening values along the line.</p><pre class="programlisting">
2029   1)  [dy] = [y1] - [y0]
2030   2) [adx] = [x1] - [x0]
2031   3) [ady] = absolute value of [dy]
2032   4) [err] = [ady] * ([X] - [x0])
2033   5) [off] = [err] / [adx] using integer division
2034   6) if ( [dy] is less than zero ) {
2035
2036        7) [Y] = [y0] - [off]
2037
2038      } else {
2039
2040        8) [Y] = [y0] + [off]
2041
2042      }
2043
2044   9) done
2045 </pre></div><div class="section" lang="en"><div class="titlepage"><div><div><h5 class="title"><a name="vorbis-spec-render_line"></a>9.2.4.3. render_line</h5></div></div></div><p>
2046 Floor decode type one uses the integer line drawing algorithm of
2047 "render_line(x0, y0, x1, y1, v)" to construct an integer floor
2048 curve for contiguous piecewise line segments. Note that it has not
2049 been relevant elsewhere, but here we must define integer division as
2050 rounding division of both positive and negative numbers toward zero.
2051 </p><pre class="programlisting">
2052   1)   [dy] = [y1] - [y0]
2053   2)  [adx] = [x1] - [x0]
2054   3)  [ady] = absolute value of [dy]
2055   4) [base] = [dy] / [adx] using integer division
2056   5)    [x] = [x0]
2057   6)    [y] = [y0]
2058   7)  [err] = 0
2059
2060   8) if ( [dy] is less than 0 ) {
2061
2062         9) [sy] = [base] - 1
2063
2064      } else {
2065
2066        10) [sy] = [base] + 1
2067
2068      }
2069
2070  11) [ady] = [ady] - (absolute value of [base]) * [adx]
2071  12) vector [v] element [x] = [y]
2072
2073  13) iterate [x] over the range [x0]+1 ... [x1]-1 {
2074
2075        14) [err] = [err] + [ady];
2076        15) if ( [err] &gt;= [adx] ) {
2077
2078              16) [err] = [err] - [adx]
2079              17)   [y] = [y] + [sy]
2080
2081            } else {
2082
2083              18) [y] = [y] + [base]
2084
2085            }
2086
2087        19) vector [v] element [x] = [y]
2088
2089      }
2090 </pre></div></div></div></div><div class="section" lang="en"><div class="titlepage"><div><div><h2 class="title" style="clear: both"><a name="vorbis-spec-tables"></a>10. Tables</h2></div><div><p class="releaseinfo">
2091   $Id: 10-tables.xml 7186 2004-07-20 07:19:25Z xiphmont $
2092  </p></div></div></div><div class="section" lang="en"><div class="titlepage"><div><div><h3 class="title"><a name="vorbis-spec-floor1_inverse_dB_table"></a>10.1. floor1_inverse_dB_table</h3></div></div></div><p>
2093 The vector <code class="varname">[floor1_inverse_dB_table]</code> is a 256 element static
2094 lookup table consiting of the following values (read left to right
2095 then top to bottom):</p><pre class="screen">
2096   1.0649863e-07, 1.1341951e-07, 1.2079015e-07, 1.2863978e-07,
2097   1.3699951e-07, 1.4590251e-07, 1.5538408e-07, 1.6548181e-07,
2098   1.7623575e-07, 1.8768855e-07, 1.9988561e-07, 2.1287530e-07,
2099   2.2670913e-07, 2.4144197e-07, 2.5713223e-07, 2.7384213e-07,
2100   2.9163793e-07, 3.1059021e-07, 3.3077411e-07, 3.5226968e-07,
2101   3.7516214e-07, 3.9954229e-07, 4.2550680e-07, 4.5315863e-07,
2102   4.8260743e-07, 5.1396998e-07, 5.4737065e-07, 5.8294187e-07,
2103   6.2082472e-07, 6.6116941e-07, 7.0413592e-07, 7.4989464e-07,
2104   7.9862701e-07, 8.5052630e-07, 9.0579828e-07, 9.6466216e-07,
2105   1.0273513e-06, 1.0941144e-06, 1.1652161e-06, 1.2409384e-06,
2106   1.3215816e-06, 1.4074654e-06, 1.4989305e-06, 1.5963394e-06,
2107   1.7000785e-06, 1.8105592e-06, 1.9282195e-06, 2.0535261e-06,
2108   2.1869758e-06, 2.3290978e-06, 2.4804557e-06, 2.6416497e-06,
2109   2.8133190e-06, 2.9961443e-06, 3.1908506e-06, 3.3982101e-06,
2110   3.6190449e-06, 3.8542308e-06, 4.1047004e-06, 4.3714470e-06,
2111   4.6555282e-06, 4.9580707e-06, 5.2802740e-06, 5.6234160e-06,
2112   5.9888572e-06, 6.3780469e-06, 6.7925283e-06, 7.2339451e-06,
2113   7.7040476e-06, 8.2047000e-06, 8.7378876e-06, 9.3057248e-06,
2114   9.9104632e-06, 1.0554501e-05, 1.1240392e-05, 1.1970856e-05,
2115   1.2748789e-05, 1.3577278e-05, 1.4459606e-05, 1.5399272e-05,
2116   1.6400004e-05, 1.7465768e-05, 1.8600792e-05, 1.9809576e-05,
2117   2.1096914e-05, 2.2467911e-05, 2.3928002e-05, 2.5482978e-05,
2118   2.7139006e-05, 2.8902651e-05, 3.0780908e-05, 3.2781225e-05,
2119   3.4911534e-05, 3.7180282e-05, 3.9596466e-05, 4.2169667e-05,
2120   4.4910090e-05, 4.7828601e-05, 5.0936773e-05, 5.4246931e-05,
2121   5.7772202e-05, 6.1526565e-05, 6.5524908e-05, 6.9783085e-05,
2122   7.4317983e-05, 7.9147585e-05, 8.4291040e-05, 8.9768747e-05,
2123   9.5602426e-05, 0.00010181521, 0.00010843174, 0.00011547824,
2124   0.00012298267, 0.00013097477, 0.00013948625, 0.00014855085,
2125   0.00015820453, 0.00016848555, 0.00017943469, 0.00019109536,
2126   0.00020351382, 0.00021673929, 0.00023082423, 0.00024582449,
2127   0.00026179955, 0.00027881276, 0.00029693158, 0.00031622787,
2128   0.00033677814, 0.00035866388, 0.00038197188, 0.00040679456,
2129   0.00043323036, 0.00046138411, 0.00049136745, 0.00052329927,
2130   0.00055730621, 0.00059352311, 0.00063209358, 0.00067317058,
2131   0.00071691700, 0.00076350630, 0.00081312324, 0.00086596457,
2132   0.00092223983, 0.00098217216, 0.0010459992,  0.0011139742,
2133   0.0011863665,  0.0012634633,  0.0013455702,  0.0014330129,
2134   0.0015261382,  0.0016253153,  0.0017309374,  0.0018434235,
2135   0.0019632195,  0.0020908006,  0.0022266726,  0.0023713743,
2136   0.0025254795,  0.0026895994,  0.0028643847,  0.0030505286,
2137   0.0032487691,  0.0034598925,  0.0036847358,  0.0039241906,
2138   0.0041792066,  0.0044507950,  0.0047400328,  0.0050480668,
2139   0.0053761186,  0.0057254891,  0.0060975636,  0.0064938176,
2140   0.0069158225,  0.0073652516,  0.0078438871,  0.0083536271,
2141   0.0088964928,  0.009474637,   0.010090352,   0.010746080,
2142   0.011444421,   0.012188144,   0.012980198,   0.013823725,
2143   0.014722068,   0.015678791,   0.016697687,   0.017782797,
2144   0.018938423,   0.020169149,   0.021479854,   0.022875735,
2145   0.024362330,   0.025945531,   0.027631618,   0.029427276,
2146   0.031339626,   0.033376252,   0.035545228,   0.037855157,
2147   0.040315199,   0.042935108,   0.045725273,   0.048696758,
2148   0.051861348,   0.055231591,   0.058820850,   0.062643361,
2149   0.066714279,   0.071049749,   0.075666962,   0.080584227,
2150   0.085821044,   0.091398179,   0.097337747,   0.10366330,
2151   0.11039993,    0.11757434,    0.12521498,    0.13335215,
2152   0.14201813,    0.15124727,    0.16107617,    0.17154380,
2153   0.18269168,    0.19456402,    0.20720788,    0.22067342,
2154   0.23501402,    0.25028656,    0.26655159,    0.28387361,
2155   0.30232132,    0.32196786,    0.34289114,    0.36517414,
2156   0.38890521,    0.41417847,    0.44109412,    0.46975890,
2157   0.50028648,    0.53279791,    0.56742212,    0.60429640,
2158   0.64356699,    0.68538959,    0.72993007,    0.77736504,
2159   0.82788260,    0.88168307,    0.9389798,     1.
2160 </pre></div></div><div class="appendix" lang="en"><h2 class="title" style="clear: both"><a name="vorbis-over-ogg"></a>1. Embedding Vorbis into an Ogg stream</h2><div class="section" lang="en"><div class="titlepage"><div><div><h3 class="title"><a name="id312362"></a>1.1. Overview</h3></div></div></div><p>
2161 This document describes using Ogg logical and physical transport
2162 streams to encapsulate Vorbis compressed audio packet data into file
2163 form.</p><p>
2164 The <a href="#vorbis-spec-intro" title="1. Introduction and Description">Section 1, &#8220;Introduction and Description&#8221;</a> provides an overview of the construction
2165 of Vorbis audio packets.</p><p>
2166 The <a href="oggstream.html" target="_top">Ogg
2167 bitstream overview</a> and <a href="framing.html" target="_top">Ogg logical
2168 bitstream and framing spec</a> provide detailed descriptions of Ogg
2169 transport streams. This specification document assumes a working
2170 knowledge of the concepts covered in these named backround
2171 documents.  Please read them first.</p><div class="section" lang="en"><div class="titlepage"><div><div><h4 class="title"><a name="id336032"></a>1.1.1. Restrictions</h4></div></div></div><p>
2172 The Ogg/Vorbis I specification currently dictates that Ogg/Vorbis
2173 streams use Ogg transport streams in degenerate, unmultiplexed
2174 form only. That is:
2175
2176 </p><div class="itemizedlist"><ul type="disc"><li>
2177   A meta-headerless Ogg file encapsulates the Vorbis I packets
2178  </li><li>
2179   The Ogg stream may be chained, i.e. contain multiple, contigous logical streams (links).
2180  </li><li>
2181   The Ogg stream must be unmultiplexed (only one stream, a Vorbis audio stream, per link)
2182  </li></ul></div><p>
2183 </p><p>
2184 This is not to say that it is not currently possible to multiplex
2185 Vorbis with other media types into a multi-stream Ogg file.  At the
2186 time this document was written, Ogg was becoming a popular container
2187 for low-bitrate movies consisting of DiVX video and Vorbis audio.
2188 However, a 'Vorbis I audio file' is taken to imply Vorbis audio
2189 existing alone within a degenerate Ogg stream.  A compliant 'Vorbis
2190 audio player' is not required to implement Ogg support beyond the
2191 specific support of Vorbis within a degenrate ogg stream (naturally,
2192 application authors are encouraged to support full multiplexed Ogg
2193 handling).
2194 </p></div><div class="section" lang="en"><div class="titlepage"><div><div><h4 class="title"><a name="id319459"></a>1.1.2. MIME type</h4></div></div></div><p>
2195 The correct MIME type of any Ogg file is <code class="literal">application/ogg</code>.
2196 However, if a file is a Vorbis I audio file (which implies a
2197 degenerate Ogg stream including only unmultiplexed Vorbis audio), the
2198 mime type <code class="literal">audio/x-vorbis</code> is also allowed.</p></div></div><div class="section" lang="en"><div class="titlepage"><div><div><h3 class="title"><a name="id317588"></a>1.2. Encapsulation</h3></div></div></div><p>
2199 Ogg encapsulation of a Vorbis packet stream is straightforward.</p><div class="itemizedlist"><ul type="disc"><li>
2200   The first Vorbis packet (the identification header), which
2201   uniquely identifies a stream as Vorbis audio, is placed alone in the
2202   first page of the logical Ogg stream.  This results in a first Ogg
2203   page of exactly 58 bytes at the very beginning of the logical stream.
2204 </li><li>
2205   This first page is marked 'beginning of stream' in the page flags.
2206 </li><li>
2207   The second and third vorbis packets (comment and setup
2208   headers) may span one or more pages beginning on the second page of
2209   the logical stream.  However many pages they span, the third header
2210   packet finishes the page on which it ends.  The next (first audio) packet
2211   must begin on a fresh page.
2212 </li><li>
2213   The granule position of these first pages containing only headers is zero.
2214 </li><li>
2215   The first audio packet of the logical stream begins a fresh Ogg page.
2216 </li><li>
2217   Packets are placed into ogg pages in order until the end of stream.
2218 </li><li>
2219   The last page is marked 'end of stream' in the page flags.
2220 </li><li>
2221   Vorbis packets may span page boundaries.
2222 </li><li>
2223   The granule position of pages containing Vorbis audio is in units
2224   of PCM audio samples (per channel; a stereo stream's granule position
2225   does not increment at twice the speed of a mono stream).
2226 </li><li><p>
2227   The granule position of a page represents the end PCM sample
2228   position of the last packet <span class="emphasis"><em>completed</em></span> on that
2229   page.  The 'last PCM sample' is the last complete sample returned by
2230   decode, not an internal sample awaiting lapping with a
2231   subsequent block.  A page that is entirely spanned by a single
2232   packet (that completes on a subsequent page) has no granule
2233   position, and the granule position is set to '-1'.  </p><p>
2234   Note that the last decoded (fully lapped) PCM sample from a packet
2235   is not necessarily the middle sample from that block. If, eg, the
2236   current Vorbis packet encodes a "long block" and the next Vorbis
2237   packet encodes a "short block", the last decodable sample from the
2238   current packet be at position (3*long_block_length/4) -
2239   (short_block_length/4).
2240 </p></li><li><p>
2241     The granule (PCM) position of the first page need not indicate
2242     that the stream started at position zero.  Although the granule
2243     position belongs to the last completed packet on the page and a
2244     valid granule position must be positive, by
2245     inference it may indicate that the PCM position of the beginning
2246     of audio is positive or negative.
2247   </p><div class="itemizedlist"><ul type="circle"><li>
2248         A positive starting value simply indicates that this stream begins at
2249         some positive time offset, potentially within a larger
2250         program. This is a common case when connecting to the middle
2251         of broadcast stream.
2252     </li><li>
2253         A negative value indicates that
2254         output samples preceeding time zero should be discarded during
2255         decoding; this technique is used to allow sample-granularity
2256         editing of the stream start time of already-encoded Vorbis
2257         streams.  The number of samples to be discarded must not exceed
2258         the overlap-add span of the first two audio packets.
2259     </li></ul></div><p>
2260     In both of these cases in which the initial audio PCM starting
2261     offset is nonzero, the second finished audio packet must flush the
2262     page on which it appears and the third packet begin a fresh page.
2263     This allows the decoder to always be able to perform PCM position
2264     adjustments before needing to return any PCM data from synthesis,
2265     resulting in correct positioning information without any aditional
2266     seeking logic.
2267   </p><div class="note" style="margin-left: 0.5in; margin-right: 0.5in;"><h3 class="title">Note</h3><p>
2268     Failure to do so should, at worst, cause a
2269     decoder implementation to return incorrect positioning information
2270     for seeking operations at the very beginning of the stream.
2271   </p></div></li><li>
2272   A granule position on the final page in a stream that indicates
2273   less audio data than the final packet would normally return is used to
2274   end the stream on other than even frame boundaries.  The difference
2275   between the actual available data returned and the declared amount
2276   indicates how many trailing samples to discard from the decoding
2277   process.
2278  </li></ul></div></div></div><div class="appendix" lang="en"><h2 class="title" style="clear: both"><a name="vorbis-over-rtp"></a>2. Vorbis encapsulation in RTP</h2><pre class="literallayout">
2279
2280
2281
2282     <p>Please consult RFC 5215 <em class="citetitle">RTP Payload Format for Vorbis Encoded Audio</em> for description of how to embed Vorbis audio in an RTP stream.</p>
2283
2284 </pre></div><div class="appendix" lang="en"><h2 class="title" style="clear: both"><a name="footer"></a>3. Colophon</h2><div class="mediaobject"><img src="white-xifish.png" alt="[Xiph.org logo]"></div><p>
2285 Ogg is a <a href="http://www.xiph.org/" target="_top">Xiph.Org Foundation</a> effort
2286 to protect essential tenets of Internet multimedia from corporate
2287 hostage-taking; Open Source is the net's greatest tool to keep
2288 everyone honest. See <a href="http://www.xiph.org/about.html" target="_top">About
2289 the Xiph.org Foundation</a> for details.
2290 </p><p>
2291 Ogg Vorbis is the first Ogg audio CODEC.  Anyone may freely use and
2292 distribute the Ogg and Vorbis specification, whether in a private,
2293 public or corporate capacity.  However, the Xiph.org Foundation and
2294 the Ogg project (xiph.org) reserve the right to set the Ogg Vorbis
2295 specification and certify specification compliance.</p><p>
2296 Xiph.org's Vorbis software CODEC implementation is distributed under a
2297 BSD-like license.  This does not restrict third parties from
2298 distributing independent implementations of Vorbis software under
2299 other licenses.</p><p>
2300 Ogg, Vorbis, Xiph.org Foundation and their logos are trademarks (tm)
2301 of the <a href="http://www.xiph.org/" target="_top">Xiph.org Foundation</a>.  These
2302 pages are copyright (C) 1994-2007 Xiph.org Foundation. All rights
2303 reserved.</p><p>
2304 This document is set in DocBook XML.
2305 </p></div></div></body></html>