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