00001 <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.68.1"></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="id2405333"></a>Vorbis I specification</h1></div><div><h3 class="corpauthor">Xiph.org Foundation</h3></div></div><hr></div><div class="toc"><p><b>Table of Contents</b></p><dl><dt><span class="section"><a href="#vorbis-spec-intro">1. Introduction and Description</a></span></dt><dd><dl><dt><span class="section"><a href="#id2519516">1.1. Overview</a></span></dt><dt><span class="section"><a href="#id2518126">1.2. Decoder Configuration</a></span></dt><dt><span class="section"><a href="#id2449172">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="#id2524173">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="#id2523292">3.1. Overview</a></span></dt><dt><span class="section"><a href="#id2509016">3.2. Packed codebook format</a></span></dt><dt><span class="section"><a href="#id2450655">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="#id2512199">4.1. Overview</a></span></dt><dt><span class="section"><a href="#id2531940">4.2. Header decode and decode setup</a></span></dt><dt><span class="section"><a href="#id2545699">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="#id2541891">5.1. Overview</a></span></dt><dt><span class="section"><a href="#id2541925">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="#id2512128">6.1. Overview</a></span></dt><dt><span class="section"><a href="#id2505686">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="#id2541060">7.1. Overview</a></span></dt><dt><span class="section"><a href="#id2540135">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="#id2524422">8.1. Overview</a></span></dt><dt><span class="section"><a href="#id2517330">8.2. Residue format</a></span></dt><dt><span class="section"><a href="#id2506346">8.3. residue 0</a></span></dt><dt><span class="section"><a href="#id2517602">8.4. residue 1</a></span></dt><dt><span class="section"><a href="#id2517633">8.5. residue 2</a></span></dt><dt><span class="section"><a href="#id2538870">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="#id2507758">9.1. Overview</a></span></dt><dt><span class="section"><a href="#id2512257">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="#id2520211">A.1. Overview</a></span></dt><dd><dl><dt><span class="section"><a href="#id2530380">A.1.1. Restrictions</a></span></dt><dt><span class="section"><a href="#id2512176">A.1.2. MIME type</a></span></dt></dl></dd><dt><span class="section"><a href="#id2520628">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">
00002 $Id: 01-introduction.xml 7186 2004-07-20 07:19:25Z xiphmont $
00003 </p></div></div></div><div class="section" lang="en"><div class="titlepage"><div><div><h3 class="title"><a name="id2519516"></a>1.1. Overview</h3></div></div></div><p>
00004 This document provides a high level description of the Vorbis codec's
00005 construction. A bit-by-bit specification appears beginning in
00006 <a href="#vorbis-spec-codec" title="4. Codec Setup and Packet Decode">Section 4, “Codec Setup and Packet Decode”</a>.
00007 The later sections assume a high-level
00008 understanding of the Vorbis decode process, which is
00009 provided here.</p><div class="section" lang="en"><div class="titlepage"><div><div><h4 class="title"><a name="id2528250"></a>1.1.1. Application</h4></div></div></div><p>
00010 Vorbis is a general purpose perceptual audio CODEC intended to allow
00011 maximum encoder flexibility, thus allowing it to scale competitively
00012 over an exceptionally wide range of bitrates. At the high
00013 quality/bitrate end of the scale (CD or DAT rate stereo, 16/24 bits)
00014 it is in the same league as MPEG-2 and MPC. Similarly, the 1.0
00015 encoder can encode high-quality CD and DAT rate stereo at below 48kbps
00016 without resampling to a lower rate. Vorbis is also intended for
00017 lower and higher sample rates (from 8kHz telephony to 192kHz digital
00018 masters) and a range of channel representations (monaural,
00019 polyphonic, stereo, quadraphonic, 5.1, ambisonic, or up to 255
00020 discrete channels).
00021 </p></div><div class="section" lang="en"><div class="titlepage"><div><div><h4 class="title"><a name="id2525977"></a>1.1.2. Classification</h4></div></div></div><p>
00022 Vorbis I is a forward-adaptive monolithic transform CODEC based on the
00023 Modified Discrete Cosine Transform. The codec is structured to allow
00024 addition of a hybrid wavelet filterbank in Vorbis II to offer better
00025 transient response and reproduction using a transform better suited to
00026 localized time events.
00027 </p></div><div class="section" lang="en"><div class="titlepage"><div><div><h4 class="title"><a name="id2517154"></a>1.1.3. Assumptions</h4></div></div></div><p>
00028 The Vorbis CODEC design assumes a complex, psychoacoustically-aware
00029 encoder and simple, low-complexity decoder. Vorbis decode is
00030 computationally simpler than mp3, although it does require more
00031 working memory as Vorbis has no static probability model; the vector
00032 codebooks used in the first stage of decoding from the bitstream are
00033 packed in their entirety into the Vorbis bitstream headers. In
00034 packed form, these codebooks occupy only a few kilobytes; the extent
00035 to which they are pre-decoded into a cache is the dominant factor in
00036 decoder memory usage.
00037 </p><p>
00038 Vorbis provides none of its own framing, synchronization or protection
00039 against errors; it is solely a method of accepting input audio,
00040 dividing it into individual frames and compressing these frames into
00041 raw, unformatted 'packets'. The decoder then accepts these raw
00042 packets in sequence, decodes them, synthesizes audio frames from
00043 them, and reassembles the frames into a facsimile of the original
00044 audio stream. Vorbis is a free-form variable bit rate (VBR) codec and packets have no
00045 minimum size, maximum size, or fixed/expected size. Packets
00046 are designed that they may be truncated (or padded) and remain
00047 decodable; this is not to be considered an error condition and is used
00048 extensively in bitrate management in peeling. Both the transport
00049 mechanism and decoder must allow that a packet may be any size, or
00050 end before or after packet decode expects.</p><p>
00051 Vorbis packets are thus intended to be used with a transport mechanism
00052 that provides free-form framing, sync, positioning and error correction
00053 in accordance with these design assumptions, such as Ogg (for file
00054 transport) or RTP (for network multicast). For purposes of a few
00055 examples in this document, we will assume that Vorbis is to be
00056 embedded in an Ogg stream specifically, although this is by no means a
00057 requirement or fundamental assumption in the Vorbis design.</p><p>
00058 The specification for embedding Vorbis into
00059 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>.
00060 </p></div><div class="section" lang="en"><div class="titlepage"><div><div><h4 class="title"><a name="id2518614"></a>1.1.4. Codec Setup and Probability Model</h4></div></div></div><p>
00061 Vorbis' heritage is as a research CODEC and its current design
00062 reflects a desire to allow multiple decades of continuous encoder
00063 improvement before running out of room within the codec specification.
00064 For these reasons, configurable aspects of codec setup intentionally
00065 lean toward the extreme of forward adaptive.</p><p>
00066 The single most controversial design decision in Vorbis (and the most
00067 unusual for a Vorbis developer to keep in mind) is that the entire
00068 probability model of the codec, the Huffman and VQ codebooks, is
00069 packed into the bitstream header along with extensive CODEC setup
00070 parameters (often several hundred fields). This makes it impossible,
00071 as it would be with MPEG audio layers, to embed a simple frame type
00072 flag in each audio packet, or begin decode at any frame in the stream
00073 without having previously fetched the codec setup header.
00074 </p><div class="note" style="margin-left: 0.5in; margin-right: 0.5in;"><h3 class="title">Note</h3><p>
00075 Vorbis <span class="emphasis"><em>can</em></span> initiate decode at any arbitrary packet within a
00076 bitstream so long as the codec has been initialized/setup with the
00077 setup headers.</p></div><p>
00078 Thus, Vorbis headers are both required for decode to begin and
00079 relatively large as bitstream headers go. The header size is
00080 unbounded, although for streaming a rule-of-thumb of 4kB or less is
00081 recommended (and Xiph.Org's Vorbis encoder follows this suggestion).</p><p>
00082 Our own design work indicates the primary liability of the
00083 required header is in mindshare; it is an unusual design and thus
00084 causes some amount of complaint among engineers as this runs against
00085 current design trends (and also points out limitations in some
00086 existing software/interface designs, such as Windows' ACM codec
00087 framework). However, we find that it does not fundamentally limit
00088 Vorbis' suitable application space.</p></div><div class="section" lang="en"><div class="titlepage"><div><div><h4 class="title"><a name="id2518094"></a>1.1.5. Format Specification</h4></div></div></div><p>
00089 The Vorbis format is well-defined by its decode specification; any
00090 encoder that produces packets that are correctly decoded by the
00091 reference Vorbis decoder described below may be considered a proper
00092 Vorbis encoder. A decoder must faithfully and completely implement
00093 the specification defined below (except where noted) to be considered
00094 a proper Vorbis decoder.</p></div><div class="section" lang="en"><div class="titlepage"><div><div><h4 class="title"><a name="id2518110"></a>1.1.6. Hardware Profile</h4></div></div></div><p>
00095 Although Vorbis decode is computationally simple, it may still run
00096 into specific limitations of an embedded design. For this reason,
00097 embedded designs are allowed to deviate in limited ways from the
00098 'full' decode specification yet still be certified compliant. These
00099 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="id2518126"></a>1.2. Decoder Configuration</h3></div></div></div><p>
00100 Decoder setup consists of configuration of multiple, self-contained
00101 component abstractions that perform specific functions in the decode
00102 pipeline. Each different component instance of a specific type is
00103 semantically interchangeable; decoder configuration consists both of
00104 internal component configuration, as well as arrangement of specific
00105 instances into a decode pipeline. Componentry arrangement is roughly
00106 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="id2518164"></a>1.2.1. Global Config</h4></div></div></div><p>
00107 Global codec configuration consists of a few audio related fields
00108 (sample rate, channels), Vorbis version (always '0' in Vorbis I),
00109 bitrate hints, and the lists of component instances. All other
00110 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="id2518178"></a>1.2.2. Mode</h4></div></div></div><p>
00111 Each Vorbis frame is coded according to a master 'mode'. A bitstream
00112 may use one or many modes.</p><p>
00113 The mode mechanism is used to encode a frame according to one of
00114 multiple possible methods with the intention of choosing a method best
00115 suited to that frame. Different modes are, e.g. how frame size
00116 is changed from frame to frame. The mode number of a frame serves as a
00117 top level configuration switch for all other specific aspects of frame
00118 decode.</p><p>
00119 A 'mode' configuration consists of a frame size setting, window type
00120 (always 0, the Vorbis window, in Vorbis I), transform type (always
00121 type 0, the MDCT, in Vorbis I) and a mapping number. The mapping
00122 number specifies which mapping configuration instance to use for
00123 low-level packet decode and synthesis.</p></div><div class="section" lang="en"><div class="titlepage"><div><div><h4 class="title"><a name="id2518208"></a>1.2.3. Mapping</h4></div></div></div><p>
00124 A mapping contains a channel coupling description and a list of
00125 'submaps' that bundle sets of channel vectors together for grouped
00126 encoding and decoding. These submaps are not references to external
00127 components; the submap list is internal and specific to a mapping.</p><p>
00128 A 'submap' is a configuration/grouping that applies to a subset of
00129 floor and residue vectors within a mapping. The submap functions as a
00130 last layer of indirection such that specific special floor or residue
00131 settings can be applied not only to all the vectors in a given mode,
00132 but also specific vectors in a specific mode. Each submap specifies
00133 the proper floor and residue instance number to use for decoding that
00134 submap's spectral floor and spectral residue vectors.</p><p>
00135 As an example:</p><p>
00136 Assume a Vorbis stream that contains six channels in the standard 5.1
00137 format. The sixth channel, as is normal in 5.1, is bass only.
00138 Therefore it would be wasteful to encode a full-spectrum version of it
00139 as with the other channels. The submapping mechanism can be used to
00140 apply a full range floor and residue encoding to channels 0 through 4,
00141 and a bass-only representation to the bass channel, thus saving space.
00142 In this example, channels 0-4 belong to submap 0 (which indicates use
00143 of a full-range floor) and channel 5 belongs to submap 1, which uses a
00144 bass-only representation.</p></div><div class="section" lang="en"><div class="titlepage"><div><div><h4 class="title"><a name="id2462918"></a>1.2.4. Floor</h4></div></div></div><p>
00145 Vorbis encodes a spectral 'floor' vector for each PCM channel. This
00146 vector is a low-resolution representation of the audio spectrum for
00147 the given channel in the current frame, generally used akin to a
00148 whitening filter. It is named a 'floor' because the Xiph.Org
00149 reference encoder has historically used it as a unit-baseline for
00150 spectral resolution.</p><p>
00151 A floor encoding may be of two types. Floor 0 uses a packed LSP
00152 representation on a dB amplitude scale and Bark frequency scale.
00153 Floor 1 represents the curve as a piecewise linear interpolated
00154 representation on a dB amplitude scale and linear frequency scale.
00155 The two floors are semantically interchangeable in
00156 encoding/decoding. However, floor type 1 provides more stable
00157 inter-frame behavior, and so is the preferred choice in all
00158 coupled-stereo and high bitrate modes. Floor 1 is also considerably
00159 less expensive to decode than floor 0.</p><p>
00160 Floor 0 is not to be considered deprecated, but it is of limited
00161 modern use. No known Vorbis encoder past Xiph.org's own beta 4 makes
00162 use of floor 0.</p><p>
00163 The values coded/decoded by a floor are both compactly formatted and
00164 make use of entropy coding to save space. For this reason, a floor
00165 configuration generally refers to multiple codebooks in the codebook
00166 component list. Entropy coding is thus provided as an abstraction,
00167 and each floor instance may choose from any and all available
00168 codebooks when coding/decoding.</p></div><div class="section" lang="en"><div class="titlepage"><div><div><h4 class="title"><a name="id2518290"></a>1.2.5. Residue</h4></div></div></div><p>
00169 The spectral residue is the fine structure of the audio spectrum
00170 once the floor curve has been subtracted out. In simplest terms, it
00171 is coded in the bitstream using cascaded (multi-pass) vector
00172 quantization according to one of three specific packing/coding
00173 algorithms numbered 0 through 2. The packing algorithm details are
00174 configured by residue instance. As with the floor components, the
00175 final VQ/entropy encoding is provided by external codebook instances
00176 and each residue instance may choose from any and all available
00177 codebooks.</p></div><div class="section" lang="en"><div class="titlepage"><div><div><h4 class="title"><a name="id2518309"></a>1.2.6. Codebooks</h4></div></div></div><p>
00178 Codebooks are a self-contained abstraction that perform entropy
00179 decoding and, optionally, use the entropy-decoded integer value as an
00180 offset into an index of output value vectors, returning the indicated
00181 vector of values.</p><p>
00182 The entropy coding in a Vorbis I codebook is provided by a standard
00183 Huffman binary tree representation. This tree is tightly packed using
00184 one of several methods, depending on whether codeword lengths are
00185 ordered or unordered, or the tree is sparse.</p><p>
00186 The codebook vector index is similarly packed according to index
00187 characteristic. Most commonly, the vector index is encoded as a
00188 single list of values of possible values that are then permuted into
00189 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="id2449172"></a>1.3. High-level Decode Process</h3></div></div></div><div class="section" lang="en"><div class="titlepage"><div><div><h4 class="title"><a name="id2449178"></a>1.3.1. Decode Setup</h4></div></div></div><p>
00190 Before decoding can begin, a decoder must initialize using the
00191 bitstream headers matching the stream to be decoded. Vorbis uses
00192 three header packets; all are required, in-order, by this
00193 specification. Once set up, decode may begin at any audio packet
00194 belonging to the Vorbis stream. In Vorbis I, all packets after the
00195 three initial headers are audio packets. </p><p>
00196 The header packets are, in order, the identification
00197 header, the comments header, and the setup header.</p><div class="section" lang="en"><div class="titlepage"><div><div><h5 class="title"><a name="id2449199"></a>1.3.1.1. Identification Header</h5></div></div></div><p>
00198 The identification header identifies the bitstream as Vorbis, Vorbis
00199 version, and the simple audio characteristics of the stream such as
00200 sample rate and number of channels.</p></div><div class="section" lang="en"><div class="titlepage"><div><div><h5 class="title"><a name="id2449212"></a>1.3.1.2. Comment Header</h5></div></div></div><p>
00201 The comment header includes user text comments ("tags") and a vendor
00202 string for the application/library that produced the bitstream. The
00203 encoding and proper use of the comment header is described in
00204 <a href="#vorbis-spec-comment" title="5. comment field and header specification">Section 5, “comment field and header specification”</a>.</p></div><div class="section" lang="en"><div class="titlepage"><div><div><h5 class="title"><a name="id2449230"></a>1.3.1.3. Setup Header</h5></div></div></div><p>
00205 The setup header includes extensive CODEC setup information as well as
00206 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="id2449243"></a>1.3.2. Decode Procedure</h4></div></div></div><div class="highlights"><p>
00207 The decoding and synthesis procedure for all audio packets is
00208 fundamentally the same.
00209 </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>
00210 </p></div><p>
00211 Note that clever rearrangement of the synthesis arithmetic is
00212 possible; as an example, one can take advantage of symmetries in the
00213 MDCT to store the right-hand transform data of a partial MDCT for a
00214 50% inter-frame buffer space savings, and then complete the transform
00215 later before overlap/add with the next frame. This optimization
00216 produces entirely equivalent output and is naturally perfectly legal.
00217 The decoder must be <span class="emphasis"><em>entirely mathematically equivalent</em></span> to the
00218 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="id2449344"></a>1.3.2.1. Packet type decode</h5></div></div></div><p>
00219 Vorbis I uses four packet types. The first three packet types mark each
00220 of the three Vorbis headers described above. The fourth packet type
00221 marks an audio packet. All other packet types are reserved; packets
00222 marked with a reserved type should be ignored.</p><p>
00223 Following the three header packets, all packets in a Vorbis I stream
00224 are audio. The first step of audio packet decode is to read and
00225 verify the packet type; <span class="emphasis"><em>a non-audio packet when audio is expected
00226 indicates stream corruption or a non-compliant stream. The decoder
00227 must ignore the packet and not attempt decoding it to
00228 audio</em></span>.</p></div><div class="section" lang="en"><div class="titlepage"><div><div><h5 class="title"><a name="id2449370"></a>1.3.2.2. Mode decode</h5></div></div></div><p>
00229 Vorbis allows an encoder to set up multiple, numbered packet 'modes',
00230 as described earlier, all of which may be used in a given Vorbis
00231 stream. The mode is encoded as an integer used as a direct offset into
00232 the mode instance index. </p></div><div class="section" lang="en"><div class="titlepage"><div><div><h5 class="title"><a name="vorbis-spec-window"></a>1.3.2.3. Window shape decode (long windows only)</h5></div></div></div><p>
00233 Vorbis frames may be one of two PCM sample sizes specified during
00234 codec setup. In Vorbis I, legal frame sizes are powers of two from 64
00235 to 8192 samples. Aside from coupling, Vorbis handles channels as
00236 independent vectors and these frame sizes are in samples per channel.</p><p>
00237 Vorbis uses an overlapping transform, namely the MDCT, to blend one
00238 frame into the next, avoiding most inter-frame block boundary
00239 artifacts. The MDCT output of one frame is windowed according to MDCT
00240 requirements, overlapped 50% with the output of the previous frame and
00241 added. The window shape assures seamless reconstruction. </p><p>
00242 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>
00243 And slightly more complex in the case of overlapping unequal sized
00244 windows:</p><div class="mediaobject"><img src="window2.png" alt="overlap of a long and a short window"></div><p>
00245 In the unequal-sized window case, the window shape of the long window
00246 must be modified for seamless lapping as above. It is possible to
00247 correctly infer window shape to be applied to the current window from
00248 knowing the sizes of the current, previous and next window. It is
00249 legal for a decoder to use this method. However, in the case of a long
00250 window (short windows require no modification), Vorbis also codes two
00251 flag bits to specify pre- and post- window shape. Although not
00252 strictly necessary for function, this minor redundancy allows a packet
00253 to be fully decoded to the point of lapping entirely independently of
00254 any other packet, allowing easier abstraction of decode layers as well
00255 as allowing a greater level of easy parallelism in encode and
00256 decode.</p><p>
00257 A description of valid window functions for use with an inverse MDCT
00258 can be found in the paper
00259 “<span class="citetitle">
00260 <a href="http://www.iocon.com/resource/docs/ps/eusipco_corrected.ps" target="_top">
00261 The use of multirate filter banks for coding of high quality digital
00262 audio</a></span>”, by T. Sporer, K. Brandenburg and B. Edler. Vorbis windows
00263 all use the slope function
00264 <span class="inlinemediaobject"></span>.
00265 </p></div><div class="section" lang="en"><div class="titlepage"><div><div><h5 class="title"><a name="id2450128"></a>1.3.2.4. floor decode</h5></div></div></div><p>
00266 Each floor is encoded/decoded in channel order, however each floor
00267 belongs to a 'submap' that specifies which floor configuration to
00268 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="id2450140"></a>1.3.2.5. residue decode</h5></div></div></div><p>
00269 Although the number of residue vectors equals the number of channels,
00270 channel coupling may mean that the raw residue vectors extracted
00271 during decode do not map directly to specific channels. When channel
00272 coupling is in use, some vectors will correspond to coupled magnitude
00273 or angle. The coupling relationships are described in the codec setup
00274 and may differ from frame to frame, due to different mode numbers.</p><p>
00275 Vorbis codes residue vectors in groups by submap; the coding is done
00276 in submap order from submap 0 through n-1. This differs from floors
00277 which are coded using a configuration provided by submap number, but
00278 are coded individually in channel order.</p></div><div class="section" lang="en"><div class="titlepage"><div><div><h5 class="title"><a name="id2450165"></a>1.3.2.6. inverse channel coupling</h5></div></div></div><p>
00279 A detailed discussion of stereo in the Vorbis codec can be found in
00280 the document <a href="stereo.html" target="_top"><em class="citetitle">Stereo Channel Coupling in the
00281 Vorbis CODEC</em></a>. Vorbis is not limited to only stereo coupling, but
00282 the stereo document also gives a good overview of the generic coupling
00283 mechanism.</p><p>
00284 Vorbis coupling applies to pairs of residue vectors at a time;
00285 decoupling is done in-place a pair at a time in the order and using
00286 the vectors specified in the current mapping configuration. The
00287 decoupling operation is the same for all pairs, converting square
00288 polar representation (where one vector is magnitude and the second
00289 angle) back to Cartesian representation.</p><p>
00290 After decoupling, in order, each pair of vectors on the coupling list,
00291 the resulting residue vectors represent the fine spectral detail
00292 of each output channel.</p></div><div class="section" lang="en"><div class="titlepage"><div><div><h5 class="title"><a name="id2450201"></a>1.3.2.7. generate floor curve</h5></div></div></div><p>
00293 The decoder may choose to generate the floor curve at any appropriate
00294 time. It is reasonable to generate the output curve when the floor
00295 data is decoded from the raw packet, or it can be generated after
00296 inverse coupling and applied to the spectral residue directly,
00297 combining generation and the dot product into one step and eliminating
00298 some working space.</p><p>
00299 Both floor 0 and floor 1 generate a linear-range, linear-domain output
00300 vector to be multiplied (dot product) by the linear-range,
00301 linear-domain spectral residue.</p></div><div class="section" lang="en"><div class="titlepage"><div><div><h5 class="title"><a name="id2450222"></a>1.3.2.8. compute floor/residue dot product</h5></div></div></div><p>
00302 This step is straightforward; for each output channel, the decoder
00303 multiplies the floor curve and residue vectors element by element,
00304 producing the finished audio spectrum of each channel.</p><p>
00305 One point is worth mentioning about this dot product; a common mistake
00306 in a fixed point implementation might be to assume that a 32 bit
00307 fixed-point representation for floor and residue and direct
00308 multiplication of the vectors is sufficient for acceptable spectral
00309 depth in all cases because it happens to mostly work with the current
00310 Xiph.Org reference encoder.</p><p>
00311 However, floor vector values can span ~140dB (~24 bits unsigned), and
00312 the audio spectrum vector should represent a minimum of 120dB (~21
00313 bits with sign), even when output is to a 16 bit PCM device. For the
00314 residue vector to represent full scale if the floor is nailed to
00315 -140dB, it must be able to span 0 to +140dB. For the residue vector
00316 to reach full scale if the floor is nailed at 0dB, it must be able to
00317 represent -140dB to +0dB. Thus, in order to handle full range
00318 dynamics, a residue vector may span -140dB to +140dB entirely within
00319 spec. A 280dB range is approximately 48 bits with sign; thus the
00320 residue vector must be able to represent a 48 bit range and the dot
00321 product must be able to handle an effective 48 bit times 24 bit
00322 multiplication. This range may be achieved using large (64 bit or
00323 larger) integers, or implementing a movable binary point
00324 representation.</p></div><div class="section" lang="en"><div class="titlepage"><div><div><h5 class="title"><a name="id2450264"></a>1.3.2.9. inverse monolithic transform (MDCT)</h5></div></div></div><p>
00325 The audio spectrum is converted back into time domain PCM audio via an
00326 inverse Modified Discrete Cosine Transform (MDCT). A detailed
00327 description of the MDCT is available in the paper <a href="http://www.iocon.com/resource/docs/ps/eusipco_corrected.ps" target="_top">“<span class="citetitle">The use of multirate filter banks for coding of high quality digital
00328 audio</span>”</a>, by T. Sporer, K. Brandenburg and B. Edler.</p><p>
00329 Note that the PCM produced directly from the MDCT is not yet finished
00330 audio; it must be lapped with surrounding frames using an appropriate
00331 window (such as the Vorbis window) before the MDCT can be considered
00332 orthogonal.</p></div><div class="section" lang="en"><div class="titlepage"><div><div><h5 class="title"><a name="id2450296"></a>1.3.2.10. overlap/add data</h5></div></div></div><p>
00333 Windowed MDCT output is overlapped and added with the right hand data
00334 of the previous window such that the 3/4 point of the previous window
00335 is aligned with the 1/4 point of the current window (as illustrated in
00336 the window overlap diagram). At this point, the audio data between the
00337 center of the previous frame and the center of the current frame is
00338 now finished and ready to be returned. </p></div><div class="section" lang="en"><div class="titlepage"><div><div><h5 class="title"><a name="id2450312"></a>1.3.2.11. cache right hand data</h5></div></div></div><p>
00339 The decoder must cache the right hand portion of the current frame to
00340 be lapped with the left hand portion of the next frame.
00341 </p></div><div class="section" lang="en"><div class="titlepage"><div><div><h5 class="title"><a name="id2542059"></a>1.3.2.12. return finished audio data</h5></div></div></div><p>
00342 The overlapped portion produced from overlapping the previous and
00343 current frame data is finished data to be returned by the decoder.
00344 This data spans from the center of the previous window to the center
00345 of the current window. In the case of same-sized windows, the amount
00346 of data to return is one-half block consisting of and only of the
00347 overlapped portions. When overlapping a short and long window, much of
00348 the returned range is not actually overlap. This does not damage
00349 transform orthogonality. Pay attention however to returning the
00350 correct data range; the amount of data to be returned is:
00351
00352 </p><pre class="programlisting">
00353 window_blocksize(previous_window)/4+window_blocksize(current_window)/4
00354 </pre><p>
00355
00356 from the center of the previous window to the center of the current
00357 window.</p><p>
00358 Data is not returned from the first frame; it must be used to 'prime'
00359 the decode engine. The encoder accounts for this priming when
00360 calculating PCM offsets; after the first frame, the proper PCM output
00361 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">
00362 $Id: 02-bitpacking.xml 7186 2004-07-20 07:19:25Z xiphmont $
00363 </p></div></div></div><div class="section" lang="en"><div class="titlepage"><div><div><h3 class="title"><a name="id2524173"></a>2.1. Overview</h3></div></div></div><p>
00364 The Vorbis codec uses relatively unstructured raw packets containing
00365 arbitrary-width binary integer fields. Logically, these packets are a
00366 bitstream in which bits are coded one-by-one by the encoder and then
00367 read one-by-one in the same monotonically increasing order by the
00368 decoder. Most current binary storage arrangements group bits into a
00369 native word size of eight bits (octets), sixteen bits, thirty-two bits
00370 or, less commonly other fixed word sizes. The Vorbis bitpacking
00371 convention specifies the correct mapping of the logical packet
00372 bitstream into an actual representation in fixed-width words.
00373 </p><div class="section" lang="en"><div class="titlepage"><div><div><h4 class="title"><a name="id2498786"></a>2.1.1. octets, bytes and words</h4></div></div></div><p>
00374 In most contemporary architectures, a 'byte' is synonymous with an
00375 'octet', that is, eight bits. This has not always been the case;
00376 seven, ten, eleven and sixteen bit 'bytes' have been used. For
00377 purposes of the bitpacking convention, a byte implies the native,
00378 smallest integer storage representation offered by a platform. On
00379 modern platforms, this is generally assumed to be eight bits (not
00380 necessarily because of the processor but because of the
00381 filesystem/memory architecture. Modern filesystems invariably offer
00382 bytes as the fundamental atom of storage). A 'word' is an integer
00383 size that is a grouped multiple of this smallest size.</p><p>
00384 The most ubiquitous architectures today consider a 'byte' to be an
00385 octet (eight bits) and a word to be a group of two, four or eight
00386 bytes (16, 32 or 64 bits). Note however that the Vorbis bitpacking
00387 convention is still well defined for any native byte size; Vorbis uses
00388 the native bit-width of a given storage system. This document assumes
00389 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="id2516522"></a>2.1.2. bit order</h4></div></div></div><p>
00390 A byte has a well-defined 'least significant' bit (LSb), which is the
00391 only bit set when the byte is storing the two's complement integer
00392 value +1. A byte's 'most significant' bit (MSb) is at the opposite
00393 end of the byte. Bits in a byte are numbered from zero at the LSb to
00394 <span class="emphasis"><em>n</em></span> (<span class="emphasis"><em>n</em></span>=7 in an octet) for the
00395 MSb.</p></div><div class="section" lang="en"><div class="titlepage"><div><div><h4 class="title"><a name="id2483456"></a>2.1.3. byte order</h4></div></div></div><p>
00396 Words are native groupings of multiple bytes. Several byte orderings
00397 are possible in a word; the common ones are 3-2-1-0 ('big endian' or
00398 'most significant byte first' in which the highest-valued byte comes
00399 first), 0-1-2-3 ('little endian' or 'least significant byte first' in
00400 which the lowest value byte comes first) and less commonly 3-1-2-0 and
00401 0-2-1-3 ('mixed endian').</p><p>
00402 The Vorbis bitpacking convention specifies storage and bitstream
00403 manipulation at the byte, not word, level, thus host word ordering is
00404 of a concern only during optimization when writing high performance
00405 code that operates on a word of storage at a time rather than by byte.
00406 Logically, bytes are always coded and decoded in order from byte zero
00407 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="id2513509"></a>2.1.4. coding bits into byte sequences</h4></div></div></div><p>
00408 The Vorbis codec has need to code arbitrary bit-width integers, from
00409 zero to 32 bits wide, into packets. These integer fields are not
00410 aligned to the boundaries of the byte representation; the next field
00411 is written at the bit position at which the previous field ends.</p><p>
00412 The encoder logically packs integers by writing the LSb of a binary
00413 integer to the logical bitstream first, followed by next least
00414 significant bit, etc, until the requested number of bits have been
00415 coded. When packing the bits into bytes, the encoder begins by
00416 placing the LSb of the integer to be written into the least
00417 significant unused bit position of the destination byte, followed by
00418 the next-least significant bit of the source integer and so on up to
00419 the requested number of bits. When all bits of the destination byte
00420 have been filled, encoding continues by zeroing all bits of the next
00421 byte and writing the next bit into the bit position 0 of that byte.
00422 Decoding follows the same process as encoding, but by reading bits
00423 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="id2537805"></a>2.1.5. signedness</h4></div></div></div><p>
00424 The signedness of a specific number resulting from decode is to be
00425 interpreted by the decoder given decode context. That is, the three
00426 bit binary pattern 'b111' can be taken to represent either 'seven' as
00427 an unsigned integer, or '-1' as a signed, two's complement integer.
00428 The encoder and decoder are responsible for knowing if fields are to
00429 be treated as signed or unsigned.</p></div><div class="section" lang="en"><div class="titlepage"><div><div><h4 class="title"><a name="id2513546"></a>2.1.6. coding example</h4></div></div></div><p>
00430 Code the 4 bit integer value '12' [b1100] into an empty bytestream.
00431 Bytestream result:
00432
00433 </p><pre class="screen">
00434 |
00435 V
00436
00437 7 6 5 4 3 2 1 0
00438 byte 0 [0 0 0 0 1 1 0 0] <-
00439 byte 1 [ ]
00440 byte 2 [ ]
00441 byte 3 [ ]
00442 ...
00443 byte n [ ] bytestream length == 1 byte
00444
00445 </pre><p>
00446 </p><p>
00447 Continue by coding the 3 bit integer value '-1' [b111]:
00448
00449 </p><pre class="screen">
00450 |
00451 V
00452
00453 7 6 5 4 3 2 1 0
00454 byte 0 [0 1 1 1 1 1 0 0] <-
00455 byte 1 [ ]
00456 byte 2 [ ]
00457 byte 3 [ ]
00458 ...
00459 byte n [ ] bytestream length == 1 byte
00460 </pre><p>
00461 </p><p>
00462 Continue by coding the 7 bit integer value '17' [b0010001]:
00463
00464 </p><pre class="screen">
00465 |
00466 V
00467
00468 7 6 5 4 3 2 1 0
00469 byte 0 [1 1 1 1 1 1 0 0]
00470 byte 1 [0 0 0 0 1 0 0 0] <-
00471 byte 2 [ ]
00472 byte 3 [ ]
00473 ...
00474 byte n [ ] bytestream length == 2 bytes
00475 bit cursor == 6
00476 </pre><p>
00477 </p><p>
00478 Continue by coding the 13 bit integer value '6969' [b110 11001110 01]:
00479
00480 </p><pre class="screen">
00481 |
00482 V
00483
00484 7 6 5 4 3 2 1 0
00485 byte 0 [1 1 1 1 1 1 0 0]
00486 byte 1 [0 1 0 0 1 0 0 0]
00487 byte 2 [1 1 0 0 1 1 1 0]
00488 byte 3 [0 0 0 0 0 1 1 0] <-
00489 ...
00490 byte n [ ] bytestream length == 4 bytes
00491
00492 </pre><p>
00493 </p></div><div class="section" lang="en"><div class="titlepage"><div><div><h4 class="title"><a name="id2513617"></a>2.1.7. decoding example</h4></div></div></div><p>
00494 Reading from the beginning of the bytestream encoded in the above example:
00495
00496 </p><pre class="screen">
00497 |
00498 V
00499
00500 7 6 5 4 3 2 1 0
00501 byte 0 [1 1 1 1 1 1 0 0] <-
00502 byte 1 [0 1 0 0 1 0 0 0]
00503 byte 2 [1 1 0 0 1 1 1 0]
00504 byte 3 [0 0 0 0 0 1 1 0] bytestream length == 4 bytes
00505
00506 </pre><p>
00507 </p><p>
00508 We read two, two-bit integer fields, resulting in the returned numbers
00509 'b00' and 'b11'. Two things are worth noting here:
00510
00511 </p><div class="itemizedlist"><ul type="disc"><li><p>Although these four bits were originally written as a single
00512 four-bit integer, reading some other combination of bit-widths from the
00513 bitstream is well defined. There are no artificial alignment
00514 boundaries maintained in the bitstream.</p></li><li><p>The second value is the
00515 two-bit-wide integer 'b11'. This value may be interpreted either as
00516 the unsigned value '3', or the signed value '-1'. Signedness is
00517 dependent on decode context.</p></li></ul></div><p>
00518 </p></div><div class="section" lang="en"><div class="titlepage"><div><div><h4 class="title"><a name="id2513669"></a>2.1.8. end-of-packet alignment</h4></div></div></div><p>
00519 The typical use of bitpacking is to produce many independent
00520 byte-aligned packets which are embedded into a larger byte-aligned
00521 container structure, such as an Ogg transport bitstream. Externally,
00522 each bytestream (encoded bitstream) must begin and end on a byte
00523 boundary. Often, the encoded bitstream is not an integer number of
00524 bytes, and so there is unused (uncoded) space in the last byte of a
00525 packet.</p><p>
00526 Unused space in the last byte of a bytestream is always zeroed during
00527 the coding process. Thus, should this unused space be read, it will
00528 return binary zeroes.</p><p>
00529 Attempting to read past the end of an encoded packet results in an
00530 'end-of-packet' condition. End-of-packet is not to be considered an
00531 error; it is merely a state indicating that there is insufficient
00532 remaining data to fulfill the desired read size. Vorbis uses truncated
00533 packets as a normal mode of operation, and as such, decoders must
00534 handle reading past the end of a packet as a typical mode of
00535 operation. Any further read operations after an 'end-of-packet'
00536 condition shall also return 'end-of-packet'.</p></div><div class="section" lang="en"><div class="titlepage"><div><div><h4 class="title"><a name="id2520883"></a>2.1.9. reading zero bits</h4></div></div></div><p>
00537 Reading a zero-bit-wide integer returns the value '0' and does not
00538 increment the stream cursor. Reading to the end of the packet (but
00539 not past, such that an 'end-of-packet' condition has not triggered)
00540 and then reading a zero bit integer shall succeed, returning 0, and
00541 not trigger an end-of-packet condition. Reading a zero-bit-wide
00542 integer after a previous read sets 'end-of-packet' shall also fail
00543 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">
00544 $Id: 03-codebook.xml 7186 2004-07-20 07:19:25Z xiphmont $
00545 </p></div></div></div><div class="section" lang="en"><div class="titlepage"><div><div><h3 class="title"><a name="id2523292"></a>3.1. Overview</h3></div></div></div><p>
00546 Unlike practically every other mainstream audio codec, Vorbis has no
00547 statically configured probability model, instead packing all entropy
00548 decoding configuration, VQ and Huffman, into the bitstream itself in
00549 the third header, the codec setup header. This packed configuration
00550 consists of multiple 'codebooks', each containing a specific
00551 Huffman-equivalent representation for decoding compressed codewords as
00552 well as an optional lookup table of output vector values to which a
00553 decoded Huffman value is applied as an offset, generating the final
00554 decoded output corresponding to a given compressed codeword.</p><div class="section" lang="en"><div class="titlepage"><div><div><h4 class="title"><a name="id2497985"></a>3.1.1. Bitwise operation</h4></div></div></div><p>
00555 The codebook mechanism is built on top of the vorbis bitpacker. Both
00556 the codebooks themselves and the codewords they decode are unrolled
00557 from a packet as a series of arbitrary-width values read from the
00558 stream according to <a href="#vorbis-spec-bitpacking" title="2. Bitpacking Convention">Section 2, “Bitpacking Convention”</a>.</p></div></div><div class="section" lang="en"><div class="titlepage"><div><div><h3 class="title"><a name="id2509016"></a>3.2. Packed codebook format</h3></div></div></div><p>
00559 For purposes of the examples below, we assume that the storage
00560 system's native byte width is eight bits. This is not universally
00561 true; see <a href="#vorbis-spec-bitpacking" title="2. Bitpacking Convention">Section 2, “Bitpacking Convention”</a> for discussion
00562 relating to non-eight-bit bytes.</p><div class="section" lang="en"><div class="titlepage"><div><div><h4 class="title"><a name="id2450934"></a>3.2.1. codebook decode</h4></div></div></div><p>
00563 A codebook begins with a 24 bit sync pattern, 0x564342:
00564
00565 </p><pre class="screen">
00566 byte 0: [ 0 1 0 0 0 0 1 0 ] (0x42)
00567 byte 1: [ 0 1 0 0 0 0 1 1 ] (0x43)
00568 byte 2: [ 0 1 0 1 0 1 1 0 ] (0x56)
00569 </pre><p>
00570 16 bit <code class="varname">[codebook_dimensions]</code> and 24 bit <code class="varname">[codebook_entries]</code> fields:
00571
00572 </p><pre class="screen">
00573
00574 byte 3: [ X X X X X X X X ]
00575 byte 4: [ X X X X X X X X ] [codebook_dimensions] (16 bit unsigned)
00576
00577 byte 5: [ X X X X X X X X ]
00578 byte 6: [ X X X X X X X X ]
00579 byte 7: [ X X X X X X X X ] [codebook_entries] (24 bit unsigned)
00580
00581 </pre><p>
00582 Next is the <code class="varname">[ordered]</code> bit flag:
00583
00584 </p><pre class="screen">
00585
00586 byte 8: [ X ] [ordered] (1 bit)
00587
00588 </pre><p>
00589 Each entry, numbering a
00590 total of <code class="varname">[codebook_entries]</code>, is assigned a codeword length.
00591 We now read the list of codeword lengths and store these lengths in
00592 the array <code class="varname">[codebook_codeword_lengths]</code>. Decode of lengths is
00593 according to whether the <code class="varname">[ordered]</code> flag is set or unset.
00594
00595 </p><div class="itemizedlist"><ul type="disc"><li><p>If the <code class="varname">[ordered]</code> flag is unset, the codeword list is not
00596 length ordered and the decoder needs to read each codeword length
00597 one-by-one.</p><p>The decoder first reads one additional bit flag, the
00598 <code class="varname">[sparse]</code> flag. This flag determines whether or not the
00599 codebook contains unused entries that are not to be included in the
00600 codeword decode tree:
00601
00602 </p><pre class="screen">
00603 byte 8: [ X 1 ] [sparse] flag (1 bit)
00604 </pre><p>
00605 The decoder now performs for each of the <code class="varname">[codebook_entries]</code>
00606 codebook entries:
00607
00608 </p><pre class="screen">
00609
00610 1) if([sparse] is set){
00611
00612 2) [flag] = read one bit;
00613 3) if([flag] is set){
00614
00615 4) [length] = read a five bit unsigned integer;
00616 5) codeword length for this entry is [length]+1;
00617
00618 } else {
00619
00620 6) this entry is unused. mark it as such.
00621
00622 }
00623
00624 } else the sparse flag is not set {
00625
00626 7) [length] = read a five bit unsigned integer;
00627 8) the codeword length for this entry is [length]+1;
00628
00629 }
00630
00631 </pre></li><li><p>If the <code class="varname">[ordered]</code> flag is set, the codeword list for this
00632 codebook is encoded in ascending length order. Rather than reading
00633 a length for every codeword, the encoder reads the number of
00634 codewords per length. That is, beginning at entry zero:
00635
00636 </p><pre class="screen">
00637 1) [current_entry] = 0;
00638 2) [current_length] = read a five bit unsigned integer and add 1;
00639 3) [number] = read <a href="#vorbis-spec-ilog" title="9.2.1. ilog">ilog</a>([codebook_entries] - [current_entry]) bits as an unsigned integer
00640 4) set the entries [current_entry] through [current_entry]+[number]-1, inclusive,
00641 of the [codebook_codeword_lengths] array to [current_length]
00642 5) set [current_entry] to [number] + [current_entry]
00643 6) increment [current_length] by 1
00644 7) if [current_entry] is greater than [codebook_entries] ERROR CONDITION;
00645 the decoder will not be able to read this stream.
00646 8) if [current_entry] is less than [codebook_entries], repeat process starting at 3)
00647 9) done.
00648 </pre></li></ul></div><p>
00649
00650 After all codeword lengths have been decoded, the decoder reads the
00651 vector lookup table. Vorbis I supports three lookup types:
00652 </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'
00653 VQ)</li></ol></div><p>
00654 </p><p>
00655 The lookup table type is read as a four bit unsigned integer:
00656 </p><pre class="screen">
00657 1) [codebook_lookup_type] = read four bits as an unsigned integer
00658 </pre><p>
00659 Codebook decode precedes according to <code class="varname">[codebook_lookup_type]</code>:
00660 </p><div class="itemizedlist"><ul type="disc"><li><p>Lookup type zero indicates no lookup to be read. Proceed past
00661 lookup decode.</p></li><li><p>Lookup types one and two are similar, differing only in the
00662 number of lookup values to be read. Lookup type one reads a list of
00663 values that are permuted in a set pattern to build a list of vectors,
00664 each vector of order <code class="varname">[codebook_dimensions]</code> scalars. Lookup
00665 type two builds the same vector list, but reads each scalar for each
00666 vector explicitly, rather than building vectors from a smaller list of
00667 possible scalar values. Lookup decode proceeds as follows:
00668
00669 </p><pre class="screen">
00670 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)
00671 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)
00672 3) [codebook_value_bits] = read 4 bits as an unsigned integer and add 1
00673 4) [codebook_sequence_p] = read 1 bit as a boolean flag
00674
00675 if ( [codebook_lookup_type] is 1 ) {
00676
00677 5) [codebook_lookup_values] = <a href="#vorbis-spec-lookup1_values" title="9.2.3. lookup1_values">lookup1_values</a>(<code class="varname">[codebook_entries]</code>, <code class="varname">[codebook_dimensions]</code> )
00678
00679 } else {
00680
00681 6) [codebook_lookup_values] = <code class="varname">[codebook_entries]</code> * <code class="varname">[codebook_dimensions]</code>
00682
00683 }
00684
00685 7) read a total of [codebook_lookup_values] unsigned integers of [codebook_value_bits] each;
00686 store these in order in the array [codebook_multiplicands]
00687 </pre></li><li><p>A <code class="varname">[codebook_lookup_type]</code> of greater than two is reserved
00688 and indicates a stream that is not decodable by the specification in this
00689 document.</p></li></ul></div><p>
00690 </p><p>
00691 An 'end of packet' during any read operation in the above steps is
00692 considered an error condition rendering the stream undecodable.</p><div class="section" lang="en"><div class="titlepage"><div><div><h5 class="title"><a name="id2519623"></a>3.2.1.1. Huffman decision tree representation</h5></div></div></div><p>
00693 The <code class="varname">[codebook_codeword_lengths]</code> array and
00694 <code class="varname">[codebook_entries]</code> value uniquely define the Huffman decision
00695 tree used for entropy decoding.</p><p>
00696 Briefly, each used codebook entry (recall that length-unordered
00697 codebooks support unused codeword entries) is assigned, in order, the
00698 lowest valued unused binary Huffman codeword possible. Assume the
00699 following codeword length list:
00700
00701 </p><pre class="screen">
00702 entry 0: length 2
00703 entry 1: length 4
00704 entry 2: length 4
00705 entry 3: length 4
00706 entry 4: length 4
00707 entry 5: length 2
00708 entry 6: length 3
00709 entry 7: length 3
00710 </pre><p>
00711 Assigning codewords in order (lowest possible value of the appropriate
00712 length to highest) results in the following codeword list:
00713
00714 </p><pre class="screen">
00715 entry 0: length 2 codeword 00
00716 entry 1: length 4 codeword 0100
00717 entry 2: length 4 codeword 0101
00718 entry 3: length 4 codeword 0110
00719 entry 4: length 4 codeword 0111
00720 entry 5: length 2 codeword 10
00721 entry 6: length 3 codeword 110
00722 entry 7: length 3 codeword 111
00723 </pre><div class="note" style="margin-left: 0.5in; margin-right: 0.5in;"><h3 class="title">Note</h3><p>
00724 Unlike most binary numerical values in this document, we
00725 intend the above codewords to be read and used bit by bit from left to
00726 right, thus the codeword '001' is the bit string 'zero, zero, one'.
00727 When determining 'lowest possible value' in the assignment definition
00728 above, the leftmost bit is the MSb.</p></div><p>
00729 It is clear that the codeword length list represents a Huffman
00730 decision tree with the entry numbers equivalent to the leaves numbered
00731 left-to-right:
00732
00733 </p><div class="mediaobject"><img src="hufftree.png" alt="[huffman tree illustration]"></div><p>
00734 </p><p>
00735 As we assign codewords in order, we see that each choice constructs a
00736 new leaf in the leftmost possible position.</p><p>
00737 Note that it's possible to underspecify or overspecify a Huffman tree
00738 via the length list. In the above example, if codeword seven were
00739 eliminated, it's clear that the tree is unfinished:
00740
00741 </p><div class="mediaobject"><img src="hufftree-under.png" alt="[underspecified huffman tree illustration]"></div><p>
00742 </p><p>
00743 Similarly, in the original codebook, it's clear that the tree is fully
00744 populated and a ninth codeword is impossible. Both underspecified and
00745 overspecified trees are an error condition rendering the stream
00746 undecodable.</p><p>
00747 Codebook entries marked 'unused' are simply skipped in the assigning
00748 process. They have no codeword and do not appear in the decision
00749 tree, thus it's impossible for any bit pattern read from the stream to
00750 decode to that entry number.</p></div><div class="section" lang="en"><div class="titlepage"><div><div><h5 class="title"><a name="id2450540"></a>3.2.1.2. VQ lookup table vector representation</h5></div></div></div><p>
00751 Unpacking the VQ lookup table vectors relies on the following values:
00752 </p><pre class="programlisting">
00753 the [codebook_multiplicands] array
00754 [codebook_minimum_value]
00755 [codebook_delta_value]
00756 [codebook_sequence_p]
00757 [codebook_lookup_type]
00758 [codebook_entries]
00759 [codebook_dimensions]
00760 [codebook_lookup_values]
00761 </pre><p>
00762 </p><p>
00763 Decoding (unpacking) a specific vector in the vector lookup table
00764 proceeds according to <code class="varname">[codebook_lookup_type]</code>. The unpacked
00765 vector values are what a codebook would return during audio packet
00766 decode in a VQ context.</p><div class="section" lang="en"><div class="titlepage"><div><div><h6 class="title"><a name="id2450569"></a>3.2.1.2.1. Vector value decode: Lookup type 1</h6></div></div></div><p>
00767 Lookup type one specifies a lattice VQ lookup table built
00768 algorithmically from a list of scalar values. Calculate (unpack) the
00769 final values of a codebook entry vector from the entries in
00770 <code class="varname">[codebook_multiplicands]</code> as follows (<code class="varname">[value_vector]</code>
00771 is the output vector representing the vector of values for entry number
00772 <code class="varname">[lookup_offset]</code> in this codebook):
00773
00774 </p><pre class="screen">
00775 1) [last] = 0;
00776 2) [index_divisor] = 1;
00777 3) iterate [i] over the range 0 ... [codebook_dimensions]-1 (once for each scalar value in the value vector) {
00778
00779 4) [multiplicand_offset] = ( [lookup_offset] divided by [index_divisor] using integer
00780 division ) integer modulo [codebook_lookup_values]
00781
00782 5) vector [value_vector] element [i] =
00783 ( [codebook_multiplicands] array element number [multiplicand_offset] ) *
00784 [codebook_delta_value] + [codebook_minimum_value] + [last];
00785
00786 6) if ( [codebook_sequence_p] is set ) then set [last] = vector [value_vector] element [i]
00787
00788 7) [index_divisor] = [index_divisor] * [codebook_lookup_values]
00789
00790 }
00791
00792 8) vector calculation completed.
00793 </pre></div><div class="section" lang="en"><div class="titlepage"><div><div><h6 class="title"><a name="id2450608"></a>3.2.1.2.2. Vector value decode: Lookup type 2</h6></div></div></div><p>
00794 Lookup type two specifies a VQ lookup table in which each scalar in
00795 each vector is explicitly set by the <code class="varname">[codebook_multiplicands]</code>
00796 array in a one-to-one mapping. Calculate [unpack] the
00797 final values of a codebook entry vector from the entries in
00798 <code class="varname">[codebook_multiplicands]</code> as follows (<code class="varname">[value_vector]</code>
00799 is the output vector representing the vector of values for entry number
00800 <code class="varname">[lookup_offset]</code> in this codebook):
00801
00802 </p><pre class="screen">
00803 1) [last] = 0;
00804 2) [multiplicand_offset] = [lookup_offset] * [codebook_dimensions]
00805 3) iterate [i] over the range 0 ... [codebook_dimensions]-1 (once for each scalar value in the value vector) {
00806
00807 4) vector [value_vector] element [i] =
00808 ( [codebook_multiplicands] array element number [multiplicand_offset] ) *
00809 [codebook_delta_value] + [codebook_minimum_value] + [last];
00810
00811 5) if ( [codebook_sequence_p] is set ) then set [last] = vector [value_vector] element [i]
00812
00813 6) increment [multiplicand_offset]
00814
00815 }
00816
00817 7) vector calculation completed.
00818 </pre></div></div></div></div><div class="section" lang="en"><div class="titlepage"><div><div><h3 class="title"><a name="id2450655"></a>3.3. Use of the codebook abstraction</h3></div></div></div><p>
00819 The decoder uses the codebook abstraction much as it does the
00820 bit-unpacking convention; a specific codebook reads a
00821 codeword from the bitstream, decoding it into an entry number, and then
00822 returns that entry number to the decoder (when used in a scalar
00823 entropy coding context), or uses that entry number as an offset into
00824 the VQ lookup table, returning a vector of values (when used in a context
00825 desiring a VQ value). Scalar or VQ context is always explicit; any call
00826 to the codebook mechanism requests either a scalar entry number or a
00827 lookup vector.</p><p>
00828 Note that VQ lookup type zero indicates that there is no lookup table;
00829 requesting decode using a codebook of lookup type 0 in any context
00830 expecting a vector return value (even in a case where a vector of
00831 dimension one) is forbidden. If decoder setup or decode requests such
00832 an action, that is an error condition rendering the packet
00833 undecodable.</p><p>
00834 Using a codebook to read from the packet bitstream consists first of
00835 reading and decoding the next codeword in the bitstream. The decoder
00836 reads bits until the accumulated bits match a codeword in the
00837 codebook. This process can be though of as logically walking the
00838 Huffman decode tree by reading one bit at a time from the bitstream,
00839 and using the bit as a decision boolean to take the 0 branch (left in
00840 the above examples) or the 1 branch (right in the above examples).
00841 Walking the tree finishes when the decode process hits a leaf in the
00842 decision tree; the result is the entry number corresponding to that
00843 leaf. Reading past the end of a packet propagates the 'end-of-stream'
00844 condition to the decoder.</p><p>
00845 When used in a scalar context, the resulting codeword entry is the
00846 desired return value.</p><p>
00847 When used in a VQ context, the codeword entry number is used as an
00848 offset into the VQ lookup table. The value returned to the decoder is
00849 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">
00850 $Id: 04-codec.xml 10466 2005-11-28 00:34:44Z giles $
00851 </p></div></div></div><div class="section" lang="en"><div class="titlepage"><div><div><h3 class="title"><a name="id2512199"></a>4.1. Overview</h3></div></div></div><p>
00852 This document serves as the top-level reference document for the
00853 bit-by-bit decode specification of Vorbis I. This document assumes a
00854 high-level understanding of the Vorbis decode process, which is
00855 provided in <a href="#vorbis-spec-intro" title="1. Introduction and Description">Section 1, “Introduction and Description”</a>. <a href="#vorbis-spec-bitpacking" title="2. Bitpacking Convention">Section 2, “Bitpacking Convention”</a> covers reading and writing bit fields from
00856 and to bitstream packets.</p></div><div class="section" lang="en"><div class="titlepage"><div><div><h3 class="title"><a name="id2531940"></a>4.2. Header decode and decode setup</h3></div></div></div><p>
00857 A Vorbis bitstream begins with three header packets. The header
00858 packets are, in order, the identification header, the comments header,
00859 and the setup header. All are required for decode compliance. An
00860 end-of-packet condition during decoding the first or third header
00861 packet renders the stream undecodable. End-of-packet decoding the
00862 comment header is a non-fatal error condition.</p><div class="section" lang="en"><div class="titlepage"><div><div><h4 class="title"><a name="id2531581"></a>4.2.1. Common header decode</h4></div></div></div><p>
00863 Each header packet begins with the same header fields.
00864 </p><pre class="screen">
00865 1) [packet_type] : 8 bit value
00866 2) 0x76, 0x6f, 0x72, 0x62, 0x69, 0x73: the characters 'v','o','r','b','i','s' as six octets
00867 </pre><p>
00868 Decode continues according to packet type; the identification header
00869 is type 1, the comment header type 3 and the setup header type 5
00870 (these types are all odd as a packet with a leading single bit of '0'
00871 is an audio packet). The packets must occur in the order of
00872 identification, comment, setup.</p></div><div class="section" lang="en"><div class="titlepage"><div><div><h4 class="title"><a name="id2522768"></a>4.2.2. Identification header</h4></div></div></div><p>
00873 The identification header is a short header of only a few fields used
00874 to declare the stream definitively as Vorbis, and provide a few externally
00875 relevant pieces of information about the audio stream. The
00876 identification header is coded as follows:</p><pre class="screen">
00877 1) [vorbis_version] = read 32 bits as unsigned integer
00878 2) [audio_channels] = read 8 bit integer as unsigned
00879 3) [audio_sample_rate] = read 32 bits as unsigned integer
00880 4) [bitrate_maximum] = read 32 bits as signed integer
00881 5) [bitrate_nominal] = read 32 bits as signed integer
00882 6) [bitrate_minimum] = read 32 bits as signed integer
00883 7) [blocksize_0] = 2 exponent (read 4 bits as unsigned integer)
00884 8) [blocksize_1] = 2 exponent (read 4 bits as unsigned integer)
00885 9) [framing_flag] = read one bit
00886 </pre><p>
00887 <code class="varname">[vorbis_version]</code> is to read '0' in order to be compatible
00888 with this document. Both <code class="varname">[audio_channels]</code> and
00889 <code class="varname">[audio_sample_rate]</code> must read greater than zero. Allowed final
00890 blocksize values are 64, 128, 256, 512, 1024, 2048, 4096 and 8192 in
00891 Vorbis I. <code class="varname">[blocksize_0]</code> must be less than or equal to
00892 <code class="varname">[blocksize_1]</code>. The framing bit must be nonzero. Failure to
00893 meet any of these conditions renders a stream undecodable.</p><p>
00894 The bitrate fields above are used only as hints. The nominal bitrate
00895 field especially may be considerably off in purely VBR streams. The
00896 fields are meaningful only when greater than zero.</p><p>
00897 </p><div class="itemizedlist"><ul type="disc"><li>All three fields set to the same value implies a fixed rate, or tightly bounded, nearly fixed-rate bitstream</li><li>Only nominal set implies a VBR or ABR stream that averages the nominal bitrate</li><li>Maximum and or minimum set implies a VBR bitstream that obeys the bitrate limits</li><li>None set indicates the encoder does not care to speculate.</li></ul></div><p>
00898 </p></div><div class="section" lang="en"><div class="titlepage"><div><div><h4 class="title"><a name="id2505902"></a>4.2.3. Comment header</h4></div></div></div><p>
00899 Comment header decode and data specification is covered in
00900 <a href="#vorbis-spec-comment" title="5. comment field and header specification">Section 5, “comment field and header specification”</a>.</p></div><div class="section" lang="en"><div class="titlepage"><div><div><h4 class="title"><a name="id2505916"></a>4.2.4. Setup header</h4></div></div></div><p>
00901 Vorbis codec setup is configurable to an extreme degree:
00902
00903 </p><div class="mediaobject"><img src="components.png" alt="[decoder pipeline configuration]"></div><p>
00904 </p><p>
00905 The setup header contains the bulk of the codec setup information
00906 needed for decode. The setup header contains, in order, the lists of
00907 codebook configurations, time-domain transform configurations
00908 (placeholders in Vorbis I), floor configurations, residue
00909 configurations, channel mapping configurations and mode
00910 configurations. It finishes with a framing bit of '1'. Header decode
00911 proceeds in the following order:</p><div class="section" lang="en"><div class="titlepage"><div><div><h5 class="title"><a name="id2524640"></a>4.2.4.1. Codebooks</h5></div></div></div><div class="orderedlist"><ol type="1"><li><code class="varname">[vorbis_codebook_count]</code> = read eight bits as unsigned integer and add one</li><li>Decode <code class="varname">[vorbis_codebook_count]</code> codebooks in order as defined
00912 in <a href="#vorbis-spec-codebook" title="3. Probability Model and Codebooks">Section 3, “Probability Model and Codebooks”</a>. Save each configuration, in
00913 order, in an array of
00914 codebook configurations <code class="varname">[vorbis_codebook_configurations]</code>.</li></ol></div></div><div class="section" lang="en"><div class="titlepage"><div><div><h5 class="title"><a name="id2524679"></a>4.2.4.2. Time domain transforms</h5></div></div></div><p>
00915 These hooks are placeholders in Vorbis I. Nevertheless, the
00916 configuration placeholder values must be read to maintain bitstream
00917 sync.</p><div class="orderedlist"><ol type="1"><li><code class="varname">[vorbis_time_count]</code> = read 6 bits as unsigned integer and add one</li><li>read <code class="varname">[vorbis_time_count]</code> 16 bit values; each value should be zero. If any value is nonzero, this is an error condition and the stream is undecodable.</li></ol></div></div><div class="section" lang="en"><div class="titlepage"><div><div><h5 class="title"><a name="id2524718"></a>4.2.4.3. Floors</h5></div></div></div><p>
00918 Vorbis uses two floor types; header decode is handed to the decode
00919 abstraction of the appropriate type.</p><div class="orderedlist"><ol type="1"><li><code class="varname">[vorbis_floor_count]</code> = read 6 bits as unsigned integer and add one</li><li><p>For each <code class="varname">[i]</code> of <code class="varname">[vorbis_floor_count]</code> floor numbers:
00920 </p><div class="orderedlist"><ol type="a"><li>read the floor type: vector <code class="varname">[vorbis_floor_types]</code> element <code class="varname">[i]</code> =
00921 read 16 bits as unsigned integer</li><li>If the floor type is zero, decode the floor
00922 configuration as defined in <a href="#vorbis-spec-floor0" title="6. Floor type 0 setup and decode">Section 6, “Floor type 0 setup and decode”</a>; save
00923 this
00924 configuration in slot <code class="varname">[i]</code> of the floor configuration array <code class="varname">[vorbis_floor_configurations]</code>.</li><li>If the floor type is one,
00925 decode the floor configuration as defined in <a href="#vorbis-spec-floor1" title="7. Floor type 1 setup and decode">Section 7, “Floor type 1 setup and decode”</a>; save this configuration in slot <code class="varname">[i]</code> of the floor configuration array <code class="varname">[vorbis_floor_configurations]</code>.</li><li>If the the floor type is greater than one, this stream is undecodable; ERROR CONDITION</li></ol></div><p>
00926 </p></li></ol></div></div><div class="section" lang="en"><div class="titlepage"><div><div><h5 class="title"><a name="id2510370"></a>4.2.4.4. Residues</h5></div></div></div><p>
00927 Vorbis uses three residue types; header decode of each type is identical.
00928 </p><div class="orderedlist"><ol type="1"><li><code class="varname">[vorbis_residue_count]</code> = read 6 bits as unsigned integer and add one
00929 </li><li><p>For each of <code class="varname">[vorbis_residue_count]</code> residue numbers:
00930 </p><div class="orderedlist"><ol type="a"><li>read the residue type; vector <code class="varname">[vorbis_residue_types]</code> element <code class="varname">[i]</code> = read 16 bits as unsigned integer</li><li>If the residue type is zero,
00931 one or two, decode the residue configuration as defined in <a href="#vorbis-spec-residue" title="8. Residue setup and decode">Section 8, “Residue setup and decode”</a>; save this configuration in slot <code class="varname">[i]</code> of the residue configuration array <code class="varname">[vorbis_residue_configurations]</code>.</li><li>If the the residue type is greater than two, this stream is undecodable; ERROR CONDITION</li></ol></div><p>
00932 </p></li></ol></div></div><div class="section" lang="en"><div class="titlepage"><div><div><h5 class="title"><a name="id2510452"></a>4.2.4.5. Mappings</h5></div></div></div><p>
00933 Mappings are used to set up specific pipelines for encoding
00934 multichannel audio with varying channel mapping applications. Vorbis I
00935 uses a single mapping type (0), with implicit PCM channel mappings.</p><div class="orderedlist"><ol type="1"><li><code class="varname">[vorbis_mapping_count]</code> = read 6 bits as unsigned integer and add one</li><li><p>For each <code class="varname">[i]</code> of <code class="varname">[vorbis_mapping_count]</code> mapping numbers:
00936 </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:
00937 </p><div class="orderedlist"><ol type="i"><li><p>read 1 bit as a boolean flag
00938 </p><div class="orderedlist"><ol type="A"><li>if set, <code class="varname">[vorbis_mapping_submaps]</code> = read 4 bits as unsigned integer and add one</li><li>if unset, <code class="varname">[vorbis_mapping_submaps]</code> = 1</li></ol></div><p>
00939 </p></li><li><p>read 1 bit as a boolean flag
00940 </p><div class="orderedlist"><ol type="A"><li><p>if set, square polar channel mapping is in use:
00941 </p><div class="orderedlist"><ol type="I"><li><code class="varname">[vorbis_mapping_coupling_steps]</code> = read 8 bits as unsigned integer and add one</li><li><p>for <code class="varname">[j]</code> each of <code class="varname">[vorbis_mapping_coupling_steps]</code> steps:
00942 </p><div class="orderedlist"><ol type="1"><li>vector <code class="varname">[vorbis_mapping_magnitude]</code> element <code class="varname">[j]</code>= read <a href="#vorbis-spec-ilog" title="9.2.1. ilog">ilog</a>(<code class="varname">[audio_channels]</code> - 1) bits as unsigned integer</li><li>vector <code class="varname">[vorbis_mapping_angle]</code> element <code class="varname">[j]</code>= read <a href="#vorbis-spec-ilog" title="9.2.1. ilog">ilog</a>(<code class="varname">[audio_channels]</code> - 1) bits as unsigned integer</li><li>the numbers read in the above two steps are channel numbers representing the channel to treat as magnitude and the channel to treat as angle, respectively. If for any coupling step the angle channel number equals the magnitude channel number, the magnitude channel number is greater than <code class="varname">[audio_channels]</code>-1, or the angle channel is greater than <code class="varname">[audio_channels]</code>-1, the stream is undecodable.</li></ol></div><p>
00943 </p></li></ol></div><p>
00944 </p></li><li>if unset, <code class="varname">[vorbis_mapping_coupling_steps]</code> = 0</li></ol></div><p>
00945 </p></li><li>read 2 bits (reserved field); if the value is nonzero, the stream is undecodable</li><li><p>if <code class="varname">[vorbis_mapping_submaps]</code> is greater than one, we read channel multiplex settings. For each <code class="varname">[j]</code> of <code class="varname">[audio_channels]</code> channels:</p><div class="orderedlist"><ol type="A"><li>vector <code class="varname">[vorbis_mapping_mux]</code> element <code class="varname">[j]</code> = read 4 bits as unsigned integer</li><li>if the value is greater than the highest numbered submap (<code class="varname">[vorbis_mapping_submaps]</code> - 1), this in an error condition rendering the stream undecodable</li></ol></div></li><li><p>for each submap <code class="varname">[j]</code> of <code class="varname">[vorbis_mapping_submaps]</code> submaps, read the floor and residue numbers for use in decoding that submap:</p><div class="orderedlist"><ol type="A"><li>read and discard 8 bits (the unused time configuration placeholder)</li><li>read 8 bits as unsigned integer for the floor number; save in vector <code class="varname">[vorbis_mapping_submap_floor]</code> element <code class="varname">[j]</code></li><li>verify the floor number is not greater than the highest number floor configured for the bitstream. If it is, the bitstream is undecodable</li><li>read 8 bits as unsigned integer for the residue number; save in vector <code class="varname">[vorbis_mapping_submap_residue]</code> element <code class="varname">[j]</code></li><li>verify the residue number is not greater than the highest number residue configured for the bitstream. If it is, the bitstream is undecodable</li></ol></div></li><li>save this mapping configuration in slot <code class="varname">[i]</code> of the mapping configuration array <code class="varname">[vorbis_mapping_configurations]</code>.</li></ol></div></li></ol></div><p>
00946 </p></li></ol></div></div><div class="section" lang="en"><div class="titlepage"><div><div><h5 class="title"><a name="id2528009"></a>4.2.4.6. Modes</h5></div></div></div><div class="orderedlist"><ol type="1"><li><code class="varname">[vorbis_mode_count]</code> = read 6 bits as unsigned integer and add one</li><li><p>For each of <code class="varname">[vorbis_mode_count]</code> mode numbers:</p><div class="orderedlist"><ol type="a"><li><code class="varname">[vorbis_mode_blockflag]</code> = read 1 bit</li><li><code class="varname">[vorbis_mode_windowtype]</code> = read 16 bits as unsigned integer</li><li><code class="varname">[vorbis_mode_transformtype]</code> = read 16 bits as unsigned integer</li><li><code class="varname">[vorbis_mode_mapping]</code> = read 8 bits as unsigned integer</li><li>verify ranges; zero is the only legal value in Vorbis I for
00947 <code class="varname">[vorbis_mode_windowtype]</code>
00948 and <code class="varname">[vorbis_mode_transformtype]</code>. <code class="varname">[vorbis_mode_mapping]</code> must not be greater than the highest number mapping in use. Any illegal values render the stream undecodable.</li><li>save this mode configuration in slot <code class="varname">[i]</code> of the mode configuration array
00949 <code class="varname">[vorbis_mode_configurations]</code>.</li></ol></div></li><li>read 1 bit as a framing flag. If unset, a framing error occurred and the stream is not
00950 decodable.</li></ol></div><p>
00951 After reading mode descriptions, setup header decode is complete.
00952 </p></div></div></div><div class="section" lang="en"><div class="titlepage"><div><div><h3 class="title"><a name="id2545699"></a>4.3. Audio packet decode and synthesis</h3></div></div></div><p>
00953 Following the three header packets, all packets in a Vorbis I stream
00954 are audio. The first step of audio packet decode is to read and
00955 verify the packet type. <span class="emphasis"><em>A non-audio packet when audio is expected
00956 indicates stream corruption or a non-compliant stream. The decoder
00957 must ignore the packet and not attempt decoding it to audio</em></span>.
00958 </p><div class="section" lang="en"><div class="titlepage"><div><div><h4 class="title"><a name="id2545717"></a>4.3.1. packet type, mode and window decode</h4></div></div></div><div class="orderedlist"><ol type="1"><li>read 1 bit <code class="varname">[packet_type]</code>; check that packet type is 0 (audio)</li><li>read <a href="#vorbis-spec-ilog" title="9.2.1. ilog">ilog</a>([vorbis_mode_count]-1) bits
00959 <code class="varname">[mode_number]</code></li><li>decode blocksize <code class="varname">[n]</code> is equal to <code class="varname">[blocksize_0]</code> if
00960 <code class="varname">[vorbis_mode_blockflag]</code> is 0, else <code class="varname">[n]</code> is equal to <code class="varname">[blocksize_1]</code>.</li><li><p>perform window selection and setup; this window is used later by the inverse MDCT:</p><div class="orderedlist"><ol type="a"><li><p>if this is a long window (the <code class="varname">[vorbis_mode_blockflag]</code> flag of this mode is
00961 set):</p><div class="orderedlist"><ol type="i"><li>read 1 bit for <code class="varname">[previous_window_flag]</code></li><li>read 1 bit for <code class="varname">[next_window_flag]</code></li><li>if <code class="varname">[previous_window_flag]</code> is not set, the left half
00962 of the window will be a hybrid window for lapping with a
00963 short block. See <a href="#vorbis-spec-window" title="1.3.2.3. Window shape decode (long windows only)">Section 1.3.2.3, “Window shape decode (long windows only)”</a> for an illustration of overlapping
00964 dissimilar
00965 windows. Else, the left half window will have normal long
00966 shape.</li><li>if <code class="varname">[next_window_flag]</code> is not set, the right half of
00967 the window will be a hybrid window for lapping with a short
00968 block. See <a href="#vorbis-spec-window" title="1.3.2.3. Window shape decode (long windows only)">Section 1.3.2.3, “Window shape decode (long windows only)”</a> for an
00969 illustration of overlapping dissimilar
00970 windows. Else, the left right window will have normal long
00971 shape.</li></ol></div></li><li> if this is a short window, the window is always the same
00972 short-window shape.</li></ol></div></li></ol></div><p>
00973 Vorbis windows all use the slope function y=sin(0.5 * π * sin^2((x+.5)/n * π)),
00974 where n is window size and x ranges 0...n-1, but dissimilar
00975 lapping requirements can affect overall shape. Window generation
00976 proceeds as follows:</p><div class="orderedlist"><ol type="1"><li> <code class="varname">[window_center]</code> = <code class="varname">[n]</code> / 2</li><li><p> if (<code class="varname">[vorbis_mode_blockflag]</code> is set and <code class="varname">[previous_window_flag]</code> is
00977 not set) then
00978 </p><div class="orderedlist"><ol type="a"><li><code class="varname">[left_window_start]</code> = <code class="varname">[n]</code>/4 -
00979 <code class="varname">[blocksize_0]</code>/4</li><li><code class="varname">[left_window_end]</code> = <code class="varname">[n]</code>/4 + <code class="varname">[blocksize_0]</code>/4</li><li><code class="varname">[left_n]</code> = <code class="varname">[blocksize_0]</code>/2</li></ol></div><p>
00980 else
00981 </p><div class="orderedlist"><ol type="a"><li><code class="varname">[left_window_start]</code> = 0</li><li><code class="varname">[left_window_end]</code> = <code class="varname">[window_center]</code></li><li><code class="varname">[left_n]</code> = <code class="varname">[n]</code>/2</li></ol></div></li><li><p> if (<code class="varname">[vorbis_mode_blockflag]</code> is set and <code class="varname">[next_window_flag]</code> is not
00982 set) then
00983 </p><div class="orderedlist"><ol type="a"><li><code class="varname">[right_window_start]</code> = <code class="varname">[n]*3</code>/4 -
00984 <code class="varname">[blocksize_0]</code>/4</li><li><code class="varname">[right_window_end]</code> = <code class="varname">[n]*3</code>/4 +
00985 <code class="varname">[blocksize_0]</code>/4</li><li><code class="varname">[right_n]</code> = <code class="varname">[blocksize_0]</code>/2</li></ol></div><p>
00986 else
00987 </p><div class="orderedlist"><ol type="a"><li><code class="varname">[right_window_start]</code> = <code class="varname">[window_center]</code></li><li><code class="varname">[right_window_end]</code> = <code class="varname">[n]</code></li><li><code class="varname">[right_n]</code> = <code class="varname">[n]</code>/2</li></ol></div></li><li> window from range 0 ... <code class="varname">[left_window_start]</code>-1 inclusive is zero</li><li> for <code class="varname">[i]</code> in range <code class="varname">[left_window_start]</code> ...
00988 <code class="varname">[left_window_end]</code>-1, window(<code class="varname">[i]</code>) = sin(.5 * π * sin^2( (<code class="varname">[i]</code>-<code class="varname">[left_window_start]</code>+.5) / <code class="varname">[left_n]</code> * .5 * π) )</li><li> window from range <code class="varname">[left_window_end]</code> ... <code class="varname">[right_window_start]</code>-1
00989 inclusive is one</li><li> for <code class="varname">[i]</code> in range <code class="varname">[right_window_start]</code> ... <code class="varname">[right_window_end]</code>-1, window(<code class="varname">[i]</code>) = sin(.5 * π * sin^2( (<code class="varname">[i]</code>-<code class="varname">[right_window_start]</code>+.5) / <code class="varname">[right_n]</code> * .5 * π + .5 * π) )</li><li> window from range <code class="varname">[right_window_start]</code> ... <code class="varname">[n]</code>-1 is
00990 zero</li></ol></div><p>
00991 An end-of-packet condition up to this point should be considered an
00992 error that discards this packet from the stream. An end of packet
00993 condition past this point is to be considered a possible nominal
00994 occurrence.</p></div><div class="section" lang="en"><div class="titlepage"><div><div><h4 class="title"><a name="id2546181"></a>4.3.2. floor curve decode</h4></div></div></div><p>
00995 From this point on, we assume out decode context is using mode number
00996 <code class="varname">[mode_number]</code> from configuration array
00997 <code class="varname">[vorbis_mode_configurations]</code> and the map number
00998 <code class="varname">[vorbis_mode_mapping]</code> (specified by the current mode) taken
00999 from the mapping configuration array
01000 <code class="varname">[vorbis_mapping_configurations]</code>.</p><p>
01001 Floor curves are decoded one-by-one in channel order.</p><p>
01002 For each floor <code class="varname">[i]</code> of <code class="varname">[audio_channels]</code>
01003 </p><div class="orderedlist"><ol type="1"><li><code class="varname">[submap_number]</code> = element <code class="varname">[i]</code> of vector [vorbis_mapping_mux]</li><li><code class="varname">[floor_number]</code> = element <code class="varname">[submap_number]</code> of vector
01004 [vorbis_submap_floor]</li><li>if the floor type of this
01005 floor (vector <code class="varname">[vorbis_floor_types]</code> element
01006 <code class="varname">[floor_number]</code>) is zero then decode the floor for
01007 channel <code class="varname">[i]</code> according to the
01008 <a href="#vorbis-spec-floor0-decode" title="6.2.2. packet decode">Section 6.2.2, “packet decode”</a></li><li>if the type of this floor
01009 is one then decode the floor for channel <code class="varname">[i]</code> according
01010 to the <a href="#vorbis-spec-floor1-decode" title="7.2.2.1. packet decode">Section 7.2.2.1, “packet decode”</a></li><li>save the needed decoded floor information for channel for later synthesis</li><li>if the decoded floor returned 'unused', set vector <code class="varname">[no_residue]</code> element
01011 <code class="varname">[i]</code> to true, else set vector <code class="varname">[no_residue]</code> element <code class="varname">[i]</code> to
01012 false</li></ol></div><p>
01013 </p><p>
01014 An end-of-packet condition during floor decode shall result in packet
01015 decode zeroing all channel output vectors and skipping to the
01016 add/overlap output stage.</p></div><div class="section" lang="en"><div class="titlepage"><div><div><h4 class="title"><a name="id2546321"></a>4.3.3. nonzero vector propagate</h4></div></div></div><p>
01017 A possible result of floor decode is that a specific vector is marked
01018 'unused' which indicates that that final output vector is all-zero
01019 values (and the floor is zero). The residue for that vector is not
01020 coded in the stream, save for one complication. If some vectors are
01021 used and some are not, channel coupling could result in mixing a
01022 zeroed and nonzeroed vector to produce two nonzeroed vectors.</p><p>
01023 for each <code class="varname">[i]</code> from 0 ... <code class="varname">[vorbis_mapping_coupling_steps]</code>-1
01024
01025 </p><div class="orderedlist"><ol type="1"><li>if either <code class="varname">[no_residue]</code> entry for channel
01026 (<code class="varname">[vorbis_mapping_magnitude]</code> element <code class="varname">[i]</code>)
01027 or channel
01028 (<code class="varname">[vorbis_mapping_angle]</code> element <code class="varname">[i]</code>)
01029 are set to false, then both must be set to false. Note that an 'unused'
01030 floor has no decoded floor information; it is important that this is
01031 remembered at floor curve synthesis time.</li></ol></div><p>
01032 </p></div><div class="section" lang="en"><div class="titlepage"><div><div><h4 class="title"><a name="id2546383"></a>4.3.4. residue decode</h4></div></div></div><p>
01033 Unlike floors, which are decoded in channel order, the residue vectors
01034 are decoded in submap order.</p><p>
01035 for each submap <code class="varname">[i]</code> in order from 0 ... <code class="varname">[vorbis_mapping_submaps]</code>-1</p><div class="orderedlist"><ol type="1"><li><code class="varname">[ch]</code> = 0</li><li><p>for each channel <code class="varname">[j]</code> in order from 0 ... <code class="varname">[audio_channels]</code> - 1</p><div class="orderedlist"><ol type="a"><li><p>if channel <code class="varname">[j]</code> in submap <code class="varname">[i]</code> (vector <code class="varname">[vorbis_mapping_mux]</code> element <code class="varname">[j]</code> is equal to <code class="varname">[i]</code>)</p><div class="orderedlist"><ol type="i"><li><p>if vector <code class="varname">[no_residue]</code> element <code class="varname">[j]</code> is true
01036 </p><div class="orderedlist"><ol type="A"><li>vector <code class="varname">[do_not_decode_flag]</code> element <code class="varname">[ch]</code> is set</li></ol></div><p>
01037 else
01038 </p><div class="orderedlist"><ol type="A"><li>vector <code class="varname">[do_not_decode_flag]</code> element <code class="varname">[ch]</code> is unset</li></ol></div></li><li>increment <code class="varname">[ch]</code></li></ol></div></li></ol></div></li><li><code class="varname">[residue_number]</code> = vector <code class="varname">[vorbis_mapping_submap_residue]</code> element <code class="varname">[i]</code></li><li><code class="varname">[residue_type]</code> = vector <code class="varname">[vorbis_residue_types]</code> element <code class="varname">[residue_number]</code></li><li>decode <code class="varname">[ch]</code> vectors using residue <code class="varname">[residue_number]</code>, according to type <code class="varname">[residue_type]</code>, also passing vector <code class="varname">[do_not_decode_flag]</code> to indicate which vectors in the bundle should not be decoded. Correct per-vector decode length is <code class="varname">[n]</code>/2.</li><li><code class="varname">[ch]</code> = 0</li><li><p>for each channel <code class="varname">[j]</code> in order from 0 ... <code class="varname">[audio_channels]</code></p><div class="orderedlist"><ol type="a"><li><p>if channel <code class="varname">[j]</code> is in submap <code class="varname">[i]</code> (vector <code class="varname">[vorbis_mapping_mux]</code> element <code class="varname">[j]</code> is equal to <code class="varname">[i]</code>)</p><div class="orderedlist"><ol type="i"><li>residue vector for channel <code class="varname">[j]</code> is set to decoded residue vector <code class="varname">[ch]</code></li><li>increment <code class="varname">[ch]</code></li></ol></div></li></ol></div></li></ol></div></div><div class="section" lang="en"><div class="titlepage"><div><div><h4 class="title"><a name="id2546633"></a>4.3.5. inverse coupling</h4></div></div></div><p>
01039 for each <code class="varname">[i]</code> from <code class="varname">[vorbis_mapping_coupling_steps]</code>-1 descending to 0
01040
01041 </p><div class="orderedlist"><ol type="1"><li><code class="varname">[magnitude_vector]</code> = the residue vector for channel
01042 (vector <code class="varname">[vorbis_mapping_magnitude]</code> element <code class="varname">[i]</code>)</li><li><code class="varname">[angle_vector]</code> = the residue vector for channel (vector
01043 <code class="varname">[vorbis_mapping_angle]</code> element <code class="varname">[i]</code>)</li><li><p>for each scalar value <code class="varname">[M]</code> in vector <code class="varname">[magnitude_vector]</code> and the corresponding scalar value <code class="varname">[A]</code> in vector <code class="varname">[angle_vector]</code>:</p><div class="orderedlist"><ol type="a"><li><p>if (<code class="varname">[M]</code> is greater than zero)
01044 </p><div class="orderedlist"><ol type="i"><li><p>if (<code class="varname">[A]</code> is greater than zero)
01045 </p><div class="orderedlist"><ol type="A"><li><code class="varname">[new_M]</code> = <code class="varname">[M]</code></li><li><code class="varname">[new_A]</code> = <code class="varname">[M]</code>-<code class="varname">[A]</code></li></ol></div><p>
01046 else
01047 </p><div class="orderedlist"><ol type="A"><li><code class="varname">[new_A]</code> = <code class="varname">[M]</code></li><li><code class="varname">[new_M]</code> = <code class="varname">[M]</code>+<code class="varname">[A]</code></li></ol></div><p>
01048 </p></li></ol></div><p>
01049 else
01050 </p><div class="orderedlist"><ol type="i"><li><p>if (<code class="varname">[A]</code> is greater than zero)
01051 </p><div class="orderedlist"><ol type="A"><li><code class="varname">[new_M]</code> = <code class="varname">[M]</code></li><li><code class="varname">[new_A]</code> = <code class="varname">[M]</code>+<code class="varname">[A]</code></li></ol></div><p>
01052 else
01053 </p><div class="orderedlist"><ol type="A"><li><code class="varname">[new_A]</code> = <code class="varname">[M]</code></li><li><code class="varname">[new_M]</code> = <code class="varname">[M]</code>-<code class="varname">[A]</code></li></ol></div><p>
01054 </p></li></ol></div><p>
01055 </p></li><li>set scalar value <code class="varname">[M]</code> in vector <code class="varname">[magnitude_vector]</code> to <code class="varname">[new_M]</code></li><li>set scalar value <code class="varname">[A]</code> in vector <code class="varname">[angle_vector]</code> to <code class="varname">[new_A]</code></li></ol></div></li></ol></div><p>
01056 </p></div><div class="section" lang="en"><div class="titlepage"><div><div><h4 class="title"><a name="id2546883"></a>4.3.6. dot product</h4></div></div></div><p>
01057 For each channel, synthesize the floor curve from the decoded floor
01058 information, according to packet type. Note that the vector synthesis
01059 length for floor computation is <code class="varname">[n]</code>/2.</p><p>
01060 For each channel, multiply each element of the floor curve by each
01061 element of that channel's residue vector. The result is the dot
01062 product of the floor and residue vectors for each channel; the produced
01063 vectors are the length <code class="varname">[n]</code>/2 audio spectrum for each
01064 channel.</p><p>
01065 One point is worth mentioning about this dot product; a common mistake
01066 in a fixed point implementation might be to assume that a 32 bit
01067 fixed-point representation for floor and residue and direct
01068 multiplication of the vectors is sufficient for acceptable spectral
01069 depth in all cases because it happens to mostly work with the current
01070 Xiph.Org reference encoder. </p><p>
01071 However, floor vector values can span ~140dB (~24 bits unsigned), and
01072 the audio spectrum vector should represent a minimum of 120dB (~21
01073 bits with sign), even when output is to a 16 bit PCM device. For the
01074 residue vector to represent full scale if the floor is nailed to
01075 -140dB, it must be able to span 0 to +140dB. For the residue vector
01076 to reach full scale if the floor is nailed at 0dB, it must be able to
01077 represent -140dB to +0dB. Thus, in order to handle full range
01078 dynamics, a residue vector may span -140dB to +140dB entirely within
01079 spec. A 280dB range is approximately 48 bits with sign; thus the
01080 residue vector must be able to represent a 48 bit range and the dot
01081 product must be able to handle an effective 48 bit times 24 bit
01082 multiplication. This range may be achieved using large (64 bit or
01083 larger) integers, or implementing a movable binary point
01084 representation.</p></div><div class="section" lang="en"><div class="titlepage"><div><div><h4 class="title"><a name="id2546936"></a>4.3.7. inverse MDCT</h4></div></div></div><p>
01085 Convert the audio spectrum vector of each channel back into time
01086 domain PCM audio via an inverse Modified Discrete Cosine Transform
01087 (MDCT). A detailed description of the MDCT is available in the paper
01088 <a href="http:
01089 use of multirate filter banks for coding of high quality digital
01090 audio</span>”</a>, by T. Sporer, K. Brandenburg and B. Edler. The window
01091 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="id2546961"></a>4.3.8. overlap_add</h4></div></div></div><p>
01092 Windowed MDCT output is overlapped and added with the right hand data
01093 of the previous window such that the 3/4 point of the previous window
01094 is aligned with the 1/4 point of the current window (as illustrated in
01095 <a href="#vorbis-spec-window" title="1.3.2.3. Window shape decode (long windows only)">Section 1.3.2.3, “Window shape decode (long windows only)”</a>). The overlapped portion
01096 produced from overlapping the previous and current frame data is
01097 finished data to be returned by the decoder. This data spans from the
01098 center of the previous window to the center of the current window. In
01099 the case of same-sized windows, the amount of data to return is
01100 one-half block consisting of and only of the overlapped portions. When
01101 overlapping a short and long window, much of the returned range does not
01102 actually overlap. This does not damage transform orthogonality. Pay
01103 attention however to returning the correct data range; the amount of
01104 data to be returned is:
01105
01106 </p><pre class="programlisting">
01107 window_blocksize(previous_window)/4+window_blocksize(current_window)/4
01108 </pre><p>
01109
01110 from the center (element windowsize/2) of the previous window to the
01111 center (element windowsize/2-1, inclusive) of the current window.</p><p>
01112 Data is not returned from the first frame; it must be used to 'prime'
01113 the decode engine. The encoder accounts for this priming when
01114 calculating PCM offsets; after the first frame, the proper PCM output
01115 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="id2547004"></a>4.3.9. output channel order</h4></div></div></div><p>
01116 Vorbis I specifies only a channel mapping type 0. In mapping type 0,
01117 channel mapping is implicitly defined as follows for standard audio
01118 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,
01119 center, right</dd><dt><span class="term">four channels</span></dt><dd>the stream is quadraphonic surround. channel order: front left,
01120 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,
01121 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
01122 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>
01123 Applications using Vorbis for dedicated purposes may define channel
01124 mapping as seen fit. Future channel mappings (such as three and four
01125 channel <a href="http:
01126 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">
01127 $Id: 05-comment.xml 10465 2005-11-28 00:33:05Z giles $
01128 </p></div></div></div><div class="section" lang="en"><div class="titlepage"><div><div><h3 class="title"><a name="id2541891"></a>5.1. Overview</h3></div></div></div><p>The Vorbis text comment header is the second (of three) header
01129 packets that begin a Vorbis bitstream. It is meant for short text
01130 comments, not arbitrary metadata; arbitrary metadata belongs in a
01131 separate logical bitstream (usually an XML stream type) that provides
01132 greater structure and machine parseability.</p><p>The comment field is meant to be used much like someone jotting a
01133 quick note on the bottom of a CDR. It should be a little information to
01134 remember the disc by and explain it to others; a short, to-the-point
01135 text note that need not only be a couple words, but isn't going to be
01136 more than a short paragraph. The essentials, in other words, whatever
01137 they turn out to be, eg:
01138
01139 </p><div class="blockquote"><blockquote class="blockquote"><p>Honest Bob and the Factory-to-Dealer-Incentives, <em class="citetitle">I'm Still
01140 Around</em>, opening for Moxy Früvous, 1997.</p></blockquote></div><p>
01141 </p></div><div class="section" lang="en"><div class="titlepage"><div><div><h3 class="title"><a name="id2541925"></a>5.2. Comment encoding</h3></div></div></div><div class="section" lang="en"><div class="titlepage"><div><div><h4 class="title"><a name="id2541929"></a>5.2.1. Structure</h4></div></div></div><p>
01142 The comment header is logically a list of eight-bit-clean vectors; the
01143 number of vectors is bounded to 2^32-1 and the length of each vector
01144 is limited to 2^32-1 bytes. The vector length is encoded; the vector
01145 contents themselves are not null terminated. In addition to the vector
01146 list, there is a single vector for vendor name (also 8 bit clean,
01147 length encoded in 32 bits). For example, the 1.0 release of libvorbis
01148 set the vendor string to "Xiph.Org libVorbis I 20020717".</p><p>The comment header is decoded as follows:
01149
01150 </p><pre class="programlisting">
01151 1) [vendor_length] = read an unsigned integer of 32 bits
01152 2) [vendor_string] = read a UTF-8 vector as [vendor_length] octets
01153 3) [user_comment_list_length] = read an unsigned integer of 32 bits
01154 4) iterate [user_comment_list_length] times {
01155 5) [length] = read an unsigned integer of 32 bits
01156 6) this iteration's user comment = read a UTF-8 vector as [length] octets
01157 }
01158 7) [framing_bit] = read a single bit as boolean
01159 8) if ( [framing_bit] unset or end-of-packet ) then ERROR
01160 9) done.
01161 </pre><p>
01162 </p></div><div class="section" lang="en"><div class="titlepage"><div><div><h4 class="title"><a name="id2498376"></a>5.2.2. Content vector format</h4></div></div></div><p>
01163 The comment vectors are structured similarly to a UNIX environment variable.
01164 That is, comment fields consist of a field name and a corresponding value and
01165 look like:</p><div class="blockquote"><blockquote class="blockquote"><pre class="programlisting">
01166 comment[0]="ARTIST=me";
01167 comment[1]="TITLE=the sound of Vorbis";
01168 </pre></blockquote></div><p>
01169 The field name is case-insensitive and may consist of ASCII 0x20
01170 through 0x7D, 0x3D ('=') excluded. ASCII 0x41 through 0x5A inclusive
01171 (characters A-Z) is to be considered equivalent to ASCII 0x61 through
01172 0x7A inclusive (characters a-z).
01173 </p><p>
01174 The field name is immediately followed by ASCII 0x3D ('=');
01175 this equals sign is used to terminate the field name.
01176 </p><p>
01177 0x3D is followed by 8 bit clean UTF-8 encoded value of the
01178 field contents to the end of the field.
01179 </p><div class="section" lang="en"><div class="titlepage"><div><div><h5 class="title"><a name="id2529464"></a>5.2.2.1. Field names</h5></div></div></div><p>Below is a proposed, minimal list of standard field names with a
01180 description of intended use. No single or group of field names is
01181 mandatory; a comment header may contain one, all or none of the names
01182 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
01183 differentiate multiple
01184 versions of the same track title in a single collection. (e.g. remix
01185 info)
01186 </dd><dt><span class="term">ALBUM</span></dt><dd>The collection name to which this track belongs
01187 </dd><dt><span class="term">TRACKNUMBER</span></dt><dd>The track number of this piece if part of a specific larger collection or album
01188 </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.
01189 </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.
01190 </dd><dt><span class="term">COPYRIGHT</span></dt><dd>Copyright attribution, e.g., '2001 Nobody's Band' or '1999 Jack Moffitt'
01191 </dd><dt><span class="term">LICENSE</span></dt><dd>License information, eg, 'All Rights Reserved', 'Any
01192 Use Permitted', a URL to a license such as a Creative Commons license
01193 ("www.creativecommons.org/blahblah/license.html") or the EFF Open
01194 Audio License ('distributed under the terms of the Open Audio
01195 License. see http:
01196 details'), etc.
01197 </dd><dt><span class="term">ORGANIZATION</span></dt><dd>Name of the organization producing the track (i.e.
01198 the 'record label')
01199 </dd><dt><span class="term">DESCRIPTION</span></dt><dd>A short text description of the contents
01200 </dd><dt><span class="term">GENRE</span></dt><dd>A short text indication of music genre
01201 </dd><dt><span class="term">DATE</span></dt><dd>Date the track was recorded
01202 </dd><dt><span class="term">LOCATION</span></dt><dd>Location where track was recorded
01203 </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.
01204 </dd><dt><span class="term">ISRC</span></dt><dd>International Standard Recording Code for the
01205 track; see <a href="http:
01206 intro page</a> for more information on ISRC numbers.
01207 </dd></dl></div></div><div class="section" lang="en"><div class="titlepage"><div><div><h5 class="title"><a name="id2527296"></a>5.2.2.2. Implications</h5></div></div></div><p>Field names should not be 'internationalized'; this is a
01208 concession to simplicity not an attempt to exclude the majority of
01209 the world that doesn't speak English. Field <span class="emphasis"><em>contents</em></span>
01210 however, use the UTF-8 character encoding to allow easy representation of any
01211 language.</p><p>We have the length of the entirety of the field and restrictions on
01212 the field name so that the field name is bounded in a known way. Thus
01213 we also have the length of the field contents.</p><p>Individual 'vendors' may use non-standard field names within
01214 reason. The proper use of comment fields should be clear through
01215 context at this point. Abuse will be discouraged.</p><p>There is no vendor-specific prefix to 'nonstandard' field names.
01216 Vendors should make some effort to avoid arbitrarily polluting the
01217 common namespace. We will generally collect the more useful tags
01218 here to help with standardization.</p><p>Field names are not required to be unique (occur once) within a
01219 comment header. As an example, assume a track was recorded by three
01220 well know artists; the following is permissible, and encouraged:
01221
01222 </p><div class="blockquote"><blockquote class="blockquote"><pre class="programlisting">
01223 ARTIST=Dizzy Gillespie
01224 ARTIST=Sonny Rollins
01225 ARTIST=Sonny Stitt
01226 </pre></blockquote></div><p>
01227
01228 </p></div></div><div class="section" lang="en"><div class="titlepage"><div><div><h4 class="title"><a name="id2525558"></a>5.2.3. Encoding</h4></div></div></div><p>
01229 The comment header comprises the entirety of the second bitstream
01230 header packet. Unlike the first bitstream header packet, it is not
01231 generally the only packet on the second page and may not be restricted
01232 to within the second bitstream page. The length of the comment header
01233 packet is (practically) unbounded. The comment header packet is not
01234 optional; it must be present in the bitstream even if it is
01235 effectively empty.</p><p>
01236 The comment header is encoded as follows (as per Ogg's standard
01237 bitstream mapping which renders least-significant-bit of the word to be
01238 coded into the least significant available bit of the current
01239 bitstream octet first):
01240
01241 </p><div class="orderedlist"><ol type="1"><li>
01242 Vendor string length (32 bit unsigned quantity specifying number of octets)
01243 </li><li>
01244 Vendor string ([vendor string length] octets coded from beginning of string to end of string, not null terminated)
01245 </li><li>
01246 Number of comment fields (32 bit unsigned quantity specifying number of fields)
01247 </li><li>
01248 Comment field 0 length (if [Number of comment fields]>0; 32 bit unsigned quantity specifying number of octets)
01249 </li><li>
01250 Comment field 0 ([Comment field 0 length] octets coded from beginning of string to end of string, not null terminated)
01251 </li><li>
01252 Comment field 1 length (if [Number of comment fields]>1...)...
01253 </li></ol></div><p>
01254 </p><p>
01255 This is actually somewhat easier to describe in code; implementation of the above can be found in <code class="filename">vorbis/lib/info.c</code>, <code class="function">_vorbis_pack_comment()</code> and <code class="function">_vorbis_unpack_comment()</code>.
01256 </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">
01257 $Id: 06-floor0.xml 10424 2005-11-23 08:44:18Z xiphmont $
01258 </p></div></div></div><div class="section" lang="en"><div class="titlepage"><div><div><h3 class="title"><a name="id2512128"></a>6.1. Overview</h3></div></div></div><p>
01259 Vorbis floor type zero uses Line Spectral Pair (LSP, also alternately
01260 known as Line Spectral Frequency or LSF) representation to encode a
01261 smooth spectral envelope curve as the frequency response of the LSP
01262 filter. This representation is equivalent to a traditional all-pole
01263 infinite impulse response filter as would be used in linear predictive
01264 coding; LSP representation may be converted to LPC representation and
01265 vice-versa.</p></div><div class="section" lang="en"><div class="titlepage"><div><div><h3 class="title"><a name="id2505686"></a>6.2. Floor 0 format</h3></div></div></div><p>
01266 Floor zero configuration consists of six integer fields and a list of
01267 VQ codebooks for use in coding/decoding the LSP filter coefficient
01268 values used by each frame. </p><div class="section" lang="en"><div class="titlepage"><div><div><h4 class="title"><a name="id2515774"></a>6.2.1. header decode</h4></div></div></div><p>
01269 Configuration information for instances of floor zero decodes from the
01270 codec setup header (third packet). configuration decode proceeds as
01271 follows:</p><pre class="screen">
01272 1) [floor0_order] = read an unsigned integer of 8 bits
01273 2) [floor0_rate] = read an unsigned integer of 16 bits
01274 3) [floor0_bark_map_size] = read an unsigned integer of 16 bits
01275 4) [floor0_amplitude_bits] = read an unsigned integer of six bits
01276 5) [floor0_amplitude_offset] = read an unsigned integer of eight bits
01277 6) [floor0_number_of_books] = read an unsigned integer of four bits and add 1
01278 7) if any of [floor0_order], [floor0_rate], [floor0_bark_map_size], [floor0_amplitude_bits],
01279 [floor0_amplitude_offset] or [floor0_number_of_books] are less than zero, the stream is not decodable
01280 8) array [floor0_book_list] = read a list of [floor0_number_of_books] unsigned integers of eight bits each;
01281 </pre><p>
01282 An end-of-packet condition during any of these bitstream reads renders
01283 this stream undecodable. In addition, any element of the array
01284 <code class="varname">[floor0_book_list]</code> that is greater than the maximum codebook
01285 number for this bitstream is an error condition that also renders the
01286 stream undecodable.</p></div><div class="section" lang="en"><div class="titlepage"><div><div><h4 class="title"><a name="vorbis-spec-floor0-decode"></a>6.2.2. packet decode</h4></div></div></div><p>
01287 Extracting a floor0 curve from an audio packet consists of first
01288 decoding the curve amplitude and <code class="varname">[floor0_order]</code> LSP
01289 coefficient values from the bitstream, and then computing the floor
01290 curve, which is defined as the frequency response of the decoded LSP
01291 filter.</p><p>
01292 Packet decode proceeds as follows:</p><pre class="screen">
01293 1) [amplitude] = read an unsigned integer of [floor0_amplitude_bits] bits
01294 2) if ( [amplitude] is greater than zero ) {
01295 3) [coefficients] is an empty, zero length vector
01296 4) [booknumber] = read an unsigned integer of <a href="#vorbis-spec-ilog" title="9.2.1. ilog">ilog</a>( [floor0_number_of_books] ) bits
01297 5) if ( [booknumber] is greater than the highest number decode codebook ) then packet is undecodable
01298 6) [last] = zero;
01299 7) vector [temp_vector] = read vector from bitstream using codebook number [floor0_book_list] element [booknumber] in VQ context.
01300 8) add the scalar value [last] to each scalar in vector [temp_vector]
01301 9) [last] = the value of the last scalar in vector [temp_vector]
01302 10) concatenate [temp_vector] onto the end of the [coefficients] vector
01303 11) if (length of vector [coefficients] is less than [floor0_order], continue at step 6
01304
01305 }
01306
01307 12) done.
01308
01309 </pre><p>
01310 Take note of the following properties of decode:
01311 </p><div class="itemizedlist"><ul type="disc"><li>An <code class="varname">[amplitude]</code> value of zero must result in a return code that indicates this channel is unused in this frame (the output of the channel will be all-zeroes in synthesis). Several later stages of decode don't occur for an unused channel.</li><li>An end-of-packet condition during decode should be considered a
01312 nominal occruence; if end-of-packet is reached during any read
01313 operation above, floor decode is to return 'unused' status as if the
01314 <code class="varname">[amplitude]</code> value had read zero at the beginning of decode.</li><li>The book number used for decode
01315 can, in fact, be stored in the bitstream in <a href="#vorbis-spec-ilog" title="9.2.1. ilog">ilog</a>( <code class="varname">[floor0_number_of_books]</code> -
01316 1 ) bits. Nevertheless, the above specification is correct and values
01317 greater than the maximum possible book value are reserved.</li><li>The number of scalars read into the vector <code class="varname">[coefficients]</code>
01318 may be greater than <code class="varname">[floor0_order]</code>, the number actually
01319 required for curve computation. For example, if the VQ codebook used
01320 for the floor currently being decoded has a
01321 <code class="varname">[codebook_dimensions]</code> value of three and
01322 <code class="varname">[floor0_order]</code> is ten, the only way to fill all the needed
01323 scalars in <code class="varname">[coefficients]</code> is to to read a total of twelve
01324 scalars as four vectors of three scalars each. This is not an error
01325 condition, and care must be taken not to allow a buffer overflow in
01326 decode. The extra values are not used and may be ignored or discarded.</li></ul></div><p>
01327 </p></div><div class="section" lang="en"><div class="titlepage"><div><div><h4 class="title"><a name="vorbis-spec-floor0-synth"></a>6.2.3. curve computation</h4></div></div></div><p>
01328 Given an <code class="varname">[amplitude]</code> integer and <code class="varname">[coefficients]</code>
01329 vector from packet decode as well as the [floor0_order],
01330 [floor0_rate], [floor0_bark_map_size], [floor0_amplitude_bits] and
01331 [floor0_amplitude_offset] values from floor setup, and an output
01332 vector size <code class="varname">[n]</code> specified by the decode process, we compute a
01333 floor output vector.</p><p>
01334 If the value <code class="varname">[amplitude]</code> is zero, the return value is a
01335 length <code class="varname">[n]</code> vector with all-zero scalars. Otherwise, begin by
01336 assuming the following definitions for the given vector to be
01337 synthesized:</p><div class="informalequation"><div class="mediaobject"><img src="lspmap.png" alt="[lsp map equation]"></div></div><p>
01338 The above is used to synthesize the LSP curve on a Bark-scale frequency
01339 axis, then map the result to a linear-scale frequency axis.
01340 Similarly, the below calculation synthesizes the output LSP curve <code class="varname">[output]</code> on a log
01341 (dB) amplitude scale, mapping it to linear amplitude in the last step:</p><div class="orderedlist"><ol type="1"><li> <code class="varname">[i]</code> = 0 </li><li><p>if ( <code class="varname">[floor0_order]</code> is odd ) {
01342 </p><div class="orderedlist"><ol type="a"><li><p>calculate <code class="varname">[p]</code> and <code class="varname">[q]</code> according to:
01343 </p><div class="informalequation"><div class="mediaobject"><img src="oddlsp.png" alt="[equation for odd lsp]"></div></div><p>
01344 </p></li></ol></div><p>
01345 } else <code class="varname">[floor0_order]</code> is even {
01346 </p><div class="orderedlist"><ol type="a"><li><p>calculate <code class="varname">[p]</code> and <code class="varname">[q]</code> according to:
01347 </p><div class="informalequation"><div class="mediaobject"><img src="evenlsp.png" alt="[equation for even lsp]"></div></div><p>
01348 </p></li></ol></div><p>
01349 }
01350 </p></li><li><p>calculate <code class="varname">[linear_floor_value]</code> according to:
01351 </p><div class="informalequation"><div class="mediaobject"><img src="floorval.png" alt="[expression for floorval]"></div></div><p>
01352 </p></li><li><code class="varname">[iteration_condition]</code> = map element <code class="varname">[i]</code></li><li><code class="varname">[output]</code> element <code class="varname">[i]</code> = <code class="varname">[linear_floor_value]</code></li><li>increment <code class="varname">[i]</code></li><li>if ( map element <code class="varname">[i]</code> is equal to <code class="varname">[iteration_condition]</code> ) continue at step 5</li><li>if ( <code class="varname">[i]</code> is less than <code class="varname">[n]</code> ) continue at step 2</li><li>done</li></ol></div></div></div></div><div class="section" lang="en"><div class="titlepage"><div><div><h2 class="title" style="clear: both"><a name="vorbis-spec-floor1"></a>7. Floor type 1 setup and decode</h2></div><div><p class="releaseinfo">
01353 $Id: 07-floor1.xml 10466 2005-11-28 00:34:44Z giles $
01354 </p></div></div></div><div class="section" lang="en"><div class="titlepage"><div><div><h3 class="title"><a name="id2541060"></a>7.1. Overview</h3></div></div></div><p>
01355 Vorbis floor type one uses a piecewise straight-line representation to
01356 encode a spectral envelope curve. The representation plots this curve
01357 mechanically on a linear frequency axis and a logarithmic (dB)
01358 amplitude axis. The integer plotting algorithm used is similar to
01359 Bresenham's algorithm.</p></div><div class="section" lang="en"><div class="titlepage"><div><div><h3 class="title"><a name="id2540135"></a>7.2. Floor 1 format</h3></div></div></div><div class="section" lang="en"><div class="titlepage"><div><div><h4 class="title"><a name="id2451267"></a>7.2.1. model</h4></div></div></div><p>
01360 Floor type one represents a spectral curve as a series of
01361 line segments. Synthesis constructs a floor curve using iterative
01362 prediction in a process roughly equivalent to the following simplified
01363 description:</p><p>
01364 </p><div class="itemizedlist"><ul type="disc"><li> the first line segment (base case) is a logical line spanning
01365 from x_0,y_0 to x_1,y_1 where in the base case x_0=0 and x_1=[n], the
01366 full range of the spectral floor to be computed.</li><li>the induction step chooses a point x_new within an existing
01367 logical line segment and produces a y_new value at that point computed
01368 from the existing line's y value at x_new (as plotted by the line) and
01369 a difference value decoded from the bitstream packet.</li><li>floor computation produces two new line segments, one running from
01370 x_0,y_0 to x_new,y_new and from x_new,y_new to x_1,y_1. This step is
01371 performed logically even if y_new represents no change to the
01372 amplitude value at x_new so that later refinement is additionally
01373 bounded at x_new.</li><li>the induction step repeats, using a list of x values specified in
01374 the codec setup header at floor 1 initialization time. Computation
01375 is completed at the end of the x value list.</li></ul></div><p>
01376 </p><p>
01377 Consider the following example, with values chosen for ease of
01378 understanding rather than representing typical configuration:</p><p>
01379 For the below example, we assume a floor setup with an [n] of 128.
01380 The list of selected X values in increasing order is
01381 0,16,32,48,64,80,96,112 and 128. In list order, the values interleave
01382 as 0, 128, 64, 32, 96, 16, 48, 80 and 112. The corresponding
01383 list-order Y values as decoded from an example packet are 110, 20, -5,
01384 -45, 0, -25, -10, 30 and -10. We compute the floor in the following
01385 way, beginning with the first line:</p><div class="mediaobject"><img src="floor1-1.png" alt="[graph of example floor]"></div><p>
01386 We now draw new logical lines to reflect the correction to new_Y, and
01387 iterate for X positions 32 and 96:</p><div class="mediaobject"><img src="floor1-2.png" alt="[graph of example floor]"></div><p>
01388 Although the new Y value at X position 96 is unchanged, it is still
01389 used later as an endpoint for further refinement. From here on, the
01390 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>
01391 A more efficient algorithm with carefully defined integer rounding
01392 behavior is used for actual decode, as described later. The actual
01393 algorithm splits Y value computation and line plotting into two steps
01394 with modifications to the above algorithm to eliminate noise
01395 accumulation through integer roundoff/truncation. </p></div><div class="section" lang="en"><div class="titlepage"><div><div><h4 class="title"><a name="id2516615"></a>7.2.2. header decode</h4></div></div></div><p>
01396 A list of floor X values is stored in the packet header in interleaved
01397 format (used in list order during packet decode and synthesis). This
01398 list is split into partitions, and each partition is assigned to a
01399 partition class. X positions 0 and [n] are implicit and do not belong
01400 to an explicit partition or partition class.</p><p>
01401 A partition class consists of a representation vector width (the
01402 number of Y values which the partition class encodes at once), a
01403 'subclass' value representing the number of alternate entropy books
01404 the partition class may use in representing Y values, the list of
01405 [subclass] books and a master book used to encode which alternate
01406 books were chosen for representation in a given packet. The
01407 master/subclass mechanism is meant to be used as a flexible
01408 representation cascade while still using codebooks only in a scalar
01409 context.</p><pre class="screen">
01410
01411 1) [floor1_partitions] = read 5 bits as unsigned integer
01412 2) [maximum_class] = -1
01413 3) iterate [i] over the range 0 ... [floor1_partitions]-1 {
01414
01415 4) vector [floor1_partition_class_list] element [i] = read 4 bits as unsigned integer
01416
01417 }
01418
01419 5) [maximum_class] = largest integer scalar value in vector [floor1_partition_class_list]
01420 6) iterate [i] over the range 0 ... [maximum_class] {
01421
01422 7) vector [floor1_class_dimensions] element [i] = read 3 bits as unsigned integer and add 1
01423 8) vector [floor1_class_subclasses] element [i] = read 2 bits as unsigned integer
01424 9) if ( vector [floor1_class_subclasses] element [i] is nonzero ) {
01425
01426 10) vector [floor1_class_masterbooks] element [i] = read 8 bits as unsigned integer
01427
01428 }
01429
01430 11) iterate [j] over the range 0 ... (2 exponent [floor1_class_subclasses] element [i]) - 1 {
01431
01432 12) array [floor1_subclass_books] element [i],[j] =
01433 read 8 bits as unsigned integer and subtract one
01434 }
01435 }
01436
01437 13) [floor1_multiplier] = read 2 bits as unsigned integer and add one
01438 14) [rangebits] = read 4 bits as unsigned integer
01439 15) vector [floor1_X_list] element [0] = 0
01440 16) vector [floor1_X_list] element [1] = 2 exponent [rangebits];
01441 17) [floor1_values] = 2
01442 18) iterate [i] over the range 0 ... [floor1_partitions]-1 {
01443
01444 19) [current_class_number] = vector [floor1_partition_class_list] element [i]
01445 20) iterate [j] over the range 0 ... ([floor1_class_dimensions] element [current_class_number])-1 {
01446 21) vector [floor1_X_list] element ([floor1_values]) =
01447 read [rangebits] bits as unsigned integer
01448 22) increment [floor1_values] by one
01449 }
01450 }
01451
01452 23) done
01453 </pre><p>
01454 An end-of-packet condition while reading any aspect of a floor 1
01455 configuration during setup renders a stream undecodable. In
01456 addition, a <code class="varname">[floor1_class_masterbooks]</code> or
01457 <code class="varname">[floor1_subclass_books]</code> scalar element greater than the
01458 highest numbered codebook configured in this stream is an error
01459 condition that renders the stream undecodable.</p><div class="section" lang="en"><div class="titlepage"><div><div><h5 class="title"><a name="vorbis-spec-floor1-decode"></a>7.2.2.1. packet decode</h5></div></div></div><p>
01460 Packet decode begins by checking the <code class="varname">[nonzero]</code> flag:</p><pre class="screen">
01461 1) [nonzero] = read 1 bit as boolean
01462 </pre><p>
01463 If <code class="varname">[nonzero]</code> is unset, that indicates this channel contained
01464 no audio energy in this frame. Decode immediately returns a status
01465 indicating this floor curve (and thus this channel) is unused this
01466 frame. (A return status of 'unused' is different from decoding a
01467 floor that has all points set to minimum representation amplitude,
01468 which happens to be approximately -140dB).
01469 </p><p>
01470 Assuming <code class="varname">[nonzero]</code> is set, decode proceeds as follows:</p><pre class="screen">
01471 1) [range] = vector { 256, 128, 86, 64 } element ([floor1_multiplier]-1)
01472 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
01473 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
01474 4) [offset] = 2;
01475 5) iterate [i] over the range 0 ... [floor1_partitions]-1 {
01476
01477 6) [class] = vector [floor1_partition_class] element [i]
01478 7) [cdim] = vector [floor1_class_dimensions] element [class]
01479 8) [cbits] = vector [floor1_class_subclasses] element [class]
01480 9) [csub] = (2 exponent [cbits])-1
01481 10) [cval] = 0
01482 11) if ( [cbits] is greater than zero ) {
01483
01484 12) [cval] = read from packet using codebook number
01485 (vector [floor1_class_masterbooks] element [class]) in scalar context
01486 }
01487
01488 13) iterate [j] over the range 0 ... [cdim]-1 {
01489
01490 14) [book] = array [floor1_subclass_books] element [class],([cval] bitwise AND [csub])
01491 15) [cval] = [cval] right shifted [cbits] bits
01492 16) if ( [book] is not less than zero ) {
01493
01494 17) vector [floor1_Y] element ([j]+[offset]) = read from packet using codebook
01495 [book] in scalar context
01496
01497 } else [book] is less than zero {
01498
01499 18) vector [floor1_Y] element ([j]+[offset]) = 0
01500
01501 }
01502 }
01503
01504 19) [offset] = [offset] + [cdim]
01505
01506 }
01507
01508 20) done
01509 </pre><p>
01510 An end-of-packet condition during curve decode should be considered a
01511 nominal occurrence; if end-of-packet is reached during any read
01512 operation above, floor decode is to return 'unused' status as if the
01513 <code class="varname">[nonzero]</code> flag had been unset at the beginning of decode.
01514 </p><p>
01515 Vector <code class="varname">[floor1_Y]</code> contains the values from packet decode
01516 needed for floor 1 synthesis.</p></div><div class="section" lang="en"><div class="titlepage"><div><div><h5 class="title"><a name="vorbis-spec-floor1-synth"></a>7.2.2.2. curve computation</h5></div></div></div><p>
01517 Curve computation is split into two logical steps; the first step
01518 derives final Y amplitude values from the encoded, wrapped difference
01519 values taken from the bitstream. The second step plots the curve
01520 lines. Also, although zero-difference values are used in the
01521 iterative prediction to find final Y values, these points are
01522 conditionally skipped during final line computation in step two.
01523 Skipping zero-difference values allows a smoother line fit. </p><p>
01524 Although some aspects of the below algorithm look like inconsequential
01525 optimizations, implementors are warned to follow the details closely.
01526 Deviation from implementing a strictly equivalent algorithm can result
01527 in serious decoding errors.</p><div class="section" lang="en"><div class="titlepage"><div><div><h6 class="title"><a name="id2521765"></a>7.2.2.2.1. step 1: amplitude value synthesis</h6></div></div></div><p>
01528 Unwrap the always-positive-or-zero values read from the packet into
01529 +/- difference values, then apply to line prediction.</p><pre class="screen">
01530 1) [range] = vector { 256, 128, 86, 64 } element ([floor1_multiplier]-1)
01531 2) vector [floor1_step2_flag] element [0] = set
01532 3) vector [floor1_step2_flag] element [1] = set
01533 4) vector [floor1_final_Y] element [0] = vector [floor1_Y] element [0]
01534 5) vector [floor1_final_Y] element [1] = vector [floor1_Y] element [1]
01535 6) iterate [i] over the range 2 ... [floor1_values]-1 {
01536
01537 7) [low_neighbor_offset] = <a href="#vorbis-spec-low_neighbor" title="9.2.4. low_neighbor">low_neighbor</a>([floor1_X_list],[i])
01538 8) [high_neighbor_offset] = <a href="#vorbis-spec-high_neighbor" title="9.2.4.1. high_neighbor">high_neighbor</a>([floor1_X_list],[i])
01539
01540 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],
01541 vector [floor1_final_Y] element [low_neighbor_offset],
01542 vector [floor1_X_list] element [high_neighbor_offset],
01543 vector [floor1_final_Y] element [high_neighbor_offset],
01544 vector [floor1_X_list] element [i] )
01545
01546 10) [val] = vector [floor1_Y] element [i]
01547 11) [highroom] = [range] - [predicted]
01548 12) [lowroom] = [predicted]
01549 13) if ( [highroom] is less than [lowroom] ) {
01550
01551 14) [room] = [highroom] * 2
01552
01553 } else [highroom] is not less than [lowroom] {
01554
01555 15) [room] = [lowroom] * 2
01556
01557 }
01558
01559 16) if ( [val] is nonzero ) {
01560
01561 17) vector [floor1_step2_flag] element [low_neighbor_offset] = set
01562 18) vector [floor1_step2_flag] element [high_neighbor_offset] = set
01563 19) vector [floor1_step2_flag] element [i] = set
01564 20) if ( [val] is greater than or equal to [room] ) {
01565
01566 21) if ( [highroom] is greater than [lowroom] ) {
01567
01568 22) vector [floor1_final_Y] element [i] = [val] - [lowroom] + [predicted]
01569
01570 } else [highroom] is not greater than [lowroom] {
01571
01572 23) vector [floor1_final_Y] element [i] = [predicted] - [val] + [highroom] - 1
01573
01574 }
01575
01576 } else [val] is less than [room] {
01577
01578 24) if ([val] is odd) {
01579
01580 25) vector [floor1_final_Y] element [i] =
01581 [predicted] - (([val] + 1) divided by 2 using integer division)
01582
01583 } else [val] is even {
01584
01585 26) vector [floor1_final_Y] element [i] =
01586 [predicted] + ([val] / 2 using integer division)
01587
01588 }
01589
01590 }
01591
01592 } else [val] is zero {
01593
01594 27) vector [floor1_step2_flag] element [i] = unset
01595 28) vector [floor1_final_Y] element [i] = [predicted]
01596
01597 }
01598
01599 }
01600
01601 29) done
01602
01603 </pre></div><div class="section" lang="en"><div class="titlepage"><div><div><h6 class="title"><a name="id2521846"></a>7.2.2.2.2. step 2: curve synthesis</h6></div></div></div><p>
01604 Curve synthesis generates a return vector <code class="varname">[floor]</code> of length
01605 <code class="varname">[n]</code> (where <code class="varname">[n]</code> is provided by the decode process
01606 calling to floor decode). Floor 1 curve synthesis makes use of the
01607 <code class="varname">[floor1_X_list]</code>, <code class="varname">[floor1_final_Y]</code> and
01608 <code class="varname">[floor1_step2_flag]</code> vectors, as well as [floor1_multiplier]
01609 and [floor1_values] values.</p><p>
01610 Decode begins by sorting the scalars from vectors
01611 <code class="varname">[floor1_X_list]</code>, <code class="varname">[floor1_final_Y]</code> and
01612 <code class="varname">[floor1_step2_flag]</code> together into new vectors
01613 <code class="varname">[floor1_X_list]'</code>, <code class="varname">[floor1_final_Y]'</code> and
01614 <code class="varname">[floor1_step2_flag]'</code> according to ascending sort order of the
01615 values in <code class="varname">[floor1_X_list]</code>. That is, sort the values of
01616 <code class="varname">[floor1_X_list]</code> and then apply the same permutation to
01617 elements of the other two vectors so that the X, Y and step2_flag
01618 values still match.</p><p>
01619 Then compute the final curve in one pass:</p><pre class="screen">
01620 1) [hx] = 0
01621 2) [lx] = 0
01622 3) [ly] = vector [floor1_final_Y]' element [0] * [floor1_multiplier]
01623 4) iterate [i] over the range 1 ... [floor1_values]-1 {
01624
01625 5) if ( [floor1_step2_flag]' element [i] is set ) {
01626
01627 6) [hy] = [floor1_final_Y]' element [i] * [floor1_multiplier]
01628 7) [hx] = [floor1_X_list]' element [i]
01629 8) <a href="#vorbis-spec-render_line" title="9.2.4.3. render_line">render_line</a>( [lx], [ly], [hx], [hy], [floor] )
01630 9) [lx] = [hx]
01631 10) [ly] = [hy]
01632 }
01633 }
01634
01635 11) if ( [hx] is less than [n] ) {
01636
01637 12) <a href="#vorbis-spec-render_line" title="9.2.4.3. render_line">render_line</a>( [hx], [hy], [n], [hy], [floor] )
01638
01639 }
01640
01641 13) if ( [hx] is greater than [n] ) {
01642
01643 14) truncate vector [floor] to [n] elements
01644
01645 }
01646
01647 15) for each scalar in vector [floor], perform a lookup substitution using
01648 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>
01649
01650 16) done
01651
01652 </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">
01653 $Id: 08-residue.xml 10466 2005-11-28 00:34:44Z giles $
01654 </p></div></div></div><div class="section" lang="en"><div class="titlepage"><div><div><h3 class="title"><a name="id2524422"></a>8.1. Overview</h3></div></div></div><p>
01655 A residue vector represents the fine detail of the audio spectrum of
01656 one channel in an audio frame after the encoder subtracts the floor
01657 curve and performs any channel coupling. A residue vector may
01658 represent spectral lines, spectral magnitude, spectral phase or
01659 hybrids as mixed by channel coupling. The exact semantic content of
01660 the vector does not matter to the residue abstraction.</p><p>
01661 Whatever the exact qualities, the Vorbis residue abstraction codes the
01662 residue vectors into the bitstream packet, and then reconstructs the
01663 vectors during decode. Vorbis makes use of three different encoding
01664 variants (numbered 0, 1 and 2) of the same basic vector encoding
01665 abstraction.</p></div><div class="section" lang="en"><div class="titlepage"><div><div><h3 class="title"><a name="id2517330"></a>8.2. Residue format</h3></div></div></div><p>
01666 Residue format partitions each vector in the vector bundle into chunks,
01667 classifies each chunk, encodes the chunk classifications and finally
01668 encodes the chunks themselves using the the specific VQ arrangement
01669 defined for each selected classification.
01670 The exact interleaving and partitioning vary by residue encoding number,
01671 however the high-level process used to classify and encode the residue
01672 vector is the same in all three variants.</p><p>
01673 A set of coded residue vectors are all of the same length. High level
01674 coding structure, ignoring for the moment exactly how a partition is
01675 encoded and simply trusting that it is, is as follows:</p><p>
01676 </p><div class="itemizedlist"><ul type="disc"><li><p>Each vector is partitioned into multiple equal sized chunks
01677 according to configuration specified. If we have a vector size of
01678 <span class="emphasis"><em>n</em></span>, a partition size <span class="emphasis"><em>residue_partition_size</em></span>, and a total
01679 of <span class="emphasis"><em>ch</em></span> residue vectors, the total number of partitioned chunks
01680 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
01681 important to note that the integer division truncates. In the below
01682 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
01683 specifies which of multiple configured VQ codebook setups are used to
01684 decode that partition. The classification numbers of each partition
01685 can be thought of as forming a vector in their own right, as in the
01686 illustration below. Just as the residue vectors are coded in grouped
01687 partitions to increase encoding efficiency, the classification vector
01688 is also partitioned into chunks. The integer elements of each scalar
01689 in a classification chunk are built into a single scalar that
01690 represents the classification numbers in that chunk. In the below
01691 example, the classification codeword encodes two classification
01692 numbers.</p></li><li><p>The values in a residue vector may be encoded monolithically in a
01693 single pass through the residue vector, but more often efficient
01694 codebook design dictates that each vector is encoded as the additive
01695 sum of several passes through the residue vector using more than one
01696 VQ codebook. Thus, each residue value potentially accumulates values
01697 from multiple decode passes. The classification value associated with
01698 a partition is the same in each pass, thus the classification codeword
01699 is coded only in the first pass.</p></li></ul></div><p>
01700 </p><div class="mediaobject"><img src="residue-pack.png" alt="[illustration of residue vector format]"></div></div><div class="section" lang="en"><div class="titlepage"><div><div><h3 class="title"><a name="id2506346"></a>8.3. residue 0</h3></div></div></div><p>
01701 Residue 0 and 1 differ only in the way the values within a residue
01702 partition are interleaved during partition encoding (visually treated
01703 as a black box--or cyan box or brown box--in the above figure).</p><p>
01704 Residue encoding 0 interleaves VQ encoding according to the
01705 dimension of the codebook used to encode a partition in a specific
01706 pass. The dimension of the codebook need not be the same in multiple
01707 passes, however the partition size must be an even multiple of the
01708 codebook dimension.</p><p>
01709 As an example, assume a partition vector of size eight, to be encoded
01710 by residue 0 using codebook sizes of 8, 4, 2 and 1:</p><pre class="programlisting">
01711
01712 original residue vector: [ 0 1 2 3 4 5 6 7 ]
01713
01714 codebook dimensions = 8 encoded as: [ 0 1 2 3 4 5 6 7 ]
01715
01716 codebook dimensions = 4 encoded as: [ 0 2 4 6 ], [ 1 3 5 7 ]
01717
01718 codebook dimensions = 2 encoded as: [ 0 4 ], [ 1 5 ], [ 2 6 ], [ 3 7 ]
01719
01720 codebook dimensions = 1 encoded as: [ 0 ], [ 1 ], [ 2 ], [ 3 ], [ 4 ], [ 5 ], [ 6 ], [ 7 ]
01721
01722 </pre><p>
01723 It is worth mentioning at this point that no configurable value in the
01724 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="id2517602"></a>8.4. residue 1</h3></div></div></div><p>
01725 Residue 1 does not interleave VQ encoding. It represents partition
01726 vector scalars in order. As with residue 0, however, partition length
01727 must be an integer multiple of the codebook dimension, although
01728 dimension may vary from pass to pass.</p><p>
01729 As an example, assume a partition vector of size eight, to be encoded
01730 by residue 0 using codebook sizes of 8, 4, 2 and 1:</p><pre class="programlisting">
01731
01732 original residue vector: [ 0 1 2 3 4 5 6 7 ]
01733
01734 codebook dimensions = 8 encoded as: [ 0 1 2 3 4 5 6 7 ]
01735
01736 codebook dimensions = 4 encoded as: [ 0 1 2 3 ], [ 4 5 6 7 ]
01737
01738 codebook dimensions = 2 encoded as: [ 0 1 ], [ 2 3 ], [ 4 5 ], [ 6 7 ]
01739
01740 codebook dimensions = 1 encoded as: [ 0 ], [ 1 ], [ 2 ], [ 3 ], [ 4 ], [ 5 ], [ 6 ], [ 7 ]
01741
01742 </pre></div><div class="section" lang="en"><div class="titlepage"><div><div><h3 class="title"><a name="id2517633"></a>8.5. residue 2</h3></div></div></div><p>
01743 Residue type two can be thought of as a variant of residue type 1.
01744 Rather than encoding multiple passed-in vectors as in residue type 1,
01745 the <span class="emphasis"><em>ch</em></span> passed in vectors of length <span class="emphasis"><em>n</em></span> are first
01746 interleaved and flattened into a single vector of length
01747 <span class="emphasis"><em>ch</em></span>*<span class="emphasis"><em>n</em></span>. Encoding then proceeds as in type 1. Decoding is
01748 as in type 1 with decode interleave reversed. If operating on a single
01749 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="id2538870"></a>8.6. Residue decode</h3></div></div></div><div class="section" lang="en"><div class="titlepage"><div><div><h4 class="title"><a name="id2538876"></a>8.6.1. header decode</h4></div></div></div><p>
01750 Header decode for all three residue types is identical.</p><pre class="programlisting">
01751 1) [residue_begin] = read 24 bits as unsigned integer
01752 2) [residue_end] = read 24 bits as unsigned integer
01753 3) [residue_partition_size] = read 24 bits as unsigned integer and add one
01754 4) [residue_classifications] = read 6 bits as unsigned integer and add one
01755 5) [residue_classbook] = read 8 bits as unsigned integer
01756 </pre><p>
01757 <code class="varname">[residue_begin]</code> and <code class="varname">[residue_end]</code> select the specific
01758 sub-portion of each vector that is actually coded; it implements akin
01759 to a bandpass where, for coding purposes, the vector effectively
01760 begins at element <code class="varname">[residue_begin]</code> and ends at
01761 <code class="varname">[residue_end]</code>. Preceding and following values in the unpacked
01762 vectors are zeroed. Note that for residue type 2, these values as
01763 well as <code class="varname">[residue_partition_size]</code>apply to the interleaved
01764 vector, not the individual vectors before interleave.
01765 <code class="varname">[residue_partition_size]</code> is as explained above,
01766 <code class="varname">[residue_classifications]</code> is the number of possible
01767 classification to which a partition can belong and
01768 <code class="varname">[residue_classbook]</code> is the codebook number used to code
01769 classification codewords. The number of dimensions in book
01770 <code class="varname">[residue_classbook]</code> determines how many classification values
01771 are grouped into a single classification codeword.</p><p>
01772 Next we read a bitmap pattern that specifies which partition classes
01773 code values in which passes.</p><pre class="programlisting">
01774 1) iterate [i] over the range 0 ... [residue_classifications]-1 {
01775
01776 2) [high_bits] = 0
01777 3) [low_bits] = read 3 bits as unsigned integer
01778 4) [bitflag] = read one bit as boolean
01779 5) if ( [bitflag] is set ) then [high_bits] = read five bits as unsigned integer
01780 6) vector [residue_cascade] element [i] = [high_bits] * 8 + [low_bits]
01781 }
01782 7) done
01783 </pre><p>
01784 Finally, we read in a list of book numbers, each corresponding to
01785 specific bit set in the cascade bitmap. We loop over the possible
01786 codebook classifications and the maximum possible number of encoding
01787 stages (8 in Vorbis I, as constrained by the elements of the cascade
01788 bitmap being eight bits):</p><pre class="programlisting">
01789 1) iterate [i] over the range 0 ... [residue_classifications]-1 {
01790
01791 2) iterate [j] over the range 0 ... 7 {
01792
01793 3) if ( vector [residue_cascade] element [i] bit [j] is set ) {
01794
01795 4) array [residue_books] element [i][j] = read 8 bits as unsigned integer
01796
01797 } else {
01798
01799 5) array [residue_books] element [i][j] = unused
01800
01801 }
01802 }
01803 }
01804
01805 6) done
01806 </pre><p>
01807 An end-of-packet condition at any point in header decode renders the
01808 stream undecodable. In addition, any codebook number greater than the
01809 maximum numbered codebook set up in this stream also renders the
01810 stream undecodable.</p></div><div class="section" lang="en"><div class="titlepage"><div><div><h4 class="title"><a name="id2538992"></a>8.6.2. packet decode</h4></div></div></div><p>
01811 Format 0 and 1 packet decode is identical except for specific
01812 partition interleave. Format 2 packet decode can be built out of the
01813 format 1 decode process. Thus we describe first the decode
01814 infrastructure identical to all three formats.</p><p>
01815 In addition to configuration information, the residue decode process
01816 is passed the number of vectors in the submap bundle and a vector of
01817 flags indicating if any of the vectors are not to be decoded. If the
01818 passed in number of vectors is 3 and vector number 1 is marked 'do not
01819 decode', decode skips vector 1 during the decode loop. However, even
01820 'do not decode' vectors are allocated and zeroed.</p><p>
01821 The following convenience values are conceptually useful to clarifying
01822 the decode process:</p><pre class="programlisting">
01823 1) [classwords_per_codeword] = [codebook_dimensions] value of codebook [residue_classbook]
01824 2) [n_to_read] = [residue_end] - [residue_begin]
01825 3) [partitions_to_read] = [n_to_read] / [residue_partition_size]
01826 </pre><p>
01827 Packet decode proceeds as follows, matching the description offered earlier in the document. We assume that the number of vectors being encoded, <code class="varname">[ch]</code> is provided by the higher level decoding process.</p><pre class="programlisting">
01828 1) allocate and zero all vectors that will be returned.
01829 2) iterate [pass] over the range 0 ... 7 {
01830
01831 3) [partition_count] = 0
01832
01833 4) while [partition_count] is less than [partitions_to_read]
01834
01835 5) if ([pass] is zero) {
01836
01837 6) iterate [j] over the range 0 .. [ch]-1 {
01838
01839 7) if vector [j] is not marked 'do not decode' {
01840
01841 8) [temp] = read from packet using codebook [residue_classbook] in scalar context
01842 9) iterate [i] descending over the range [classwords_per_codeword]-1 ... 0 {
01843
01844 10) array [classifications] element [j],([i]+[partition_count]) =
01845 [temp] integer modulo [residue_classifications]
01846 11) [temp] = [temp] / [residue_classifications] using integer division
01847
01848 }
01849
01850 }
01851
01852 }
01853
01854 }
01855
01856 12) iterate [i] over the range 0 .. ([classwords_per_codeword] - 1) while [partition_count]
01857 is also less than [partitions_to_read] {
01858
01859 13) iterate [j] over the range 0 .. [ch]-1 {
01860
01861 14) if vector [j] is not marked 'do not decode' {
01862
01863 15) [vqclass] = array [classifications] element [j],[partition_count]
01864 16) [vqbook] = array [residue_books] element [vqclass],[pass]
01865 17) if ([vqbook] is not 'unused') {
01866
01867 18) decode partition into output vector number [j], starting at scalar
01868 offset [residue_begin]+[partition_count]*[residue_partition_size] using
01869 codebook number [vqbook] in VQ context
01870 }
01871 }
01872
01873 19) increment [partition_count] by one
01874
01875 }
01876 }
01877 }
01878
01879 20) done
01880
01881 </pre><p>
01882 An end-of-packet condition during packet decode is to be considered a
01883 nominal occurrence. Decode returns the result of vector decode up to
01884 that point.</p></div><div class="section" lang="en"><div class="titlepage"><div><div><h4 class="title"><a name="id2498601"></a>8.6.3. format 0 specifics</h4></div></div></div><p>
01885 Format zero decodes partitions exactly as described earlier in the
01886 'Residue Format: residue 0' section. The following pseudocode
01887 presents the same algorithm. Assume:</p><p>
01888 </p><div class="itemizedlist"><ul type="disc"><li> <code class="varname">[n]</code> is the value in <code class="varname">[residue_partition_size]</code></li><li><code class="varname">[v]</code> is the residue vector</li><li><code class="varname">[offset]</code> is the beginning read offset in [v]</li></ul></div><p>
01889 </p><pre class="programlisting">
01890 1) [step] = [n] / [codebook_dimensions]
01891 2) iterate [i] over the range 0 ... [step]-1 {
01892
01893 3) vector [entry_temp] = read vector from packet using current codebook in VQ context
01894 4) iterate [j] over the range 0 ... [codebook_dimensions]-1 {
01895
01896 5) vector [v] element ([offset]+[i]+[j]*[step]) =
01897 vector [v] element ([offset]+[i]+[j]*[step]) +
01898 vector [entry_temp] element [j]
01899
01900 }
01901
01902 }
01903
01904 6) done
01905
01906 </pre></div><div class="section" lang="en"><div class="titlepage"><div><div><h4 class="title"><a name="id2498659"></a>8.6.4. format 1 specifics</h4></div></div></div><p>
01907 Format 1 decodes partitions exactly as described earlier in the
01908 'Residue Format: residue 1' section. The following pseudocode
01909 presents the same algorithm. Assume:</p><p>
01910 </p><div class="itemizedlist"><ul type="disc"><li> <code class="varname">[n]</code> is the value in
01911 <code class="varname">[residue_partition_size]</code></li><li><code class="varname">[v]</code> is the residue vector</li><li><code class="varname">[offset]</code> is the beginning read offset in [v]</li></ul></div><p>
01912 </p><pre class="programlisting">
01913 1) [i] = 0
01914 2) vector [entry_temp] = read vector from packet using current codebook in VQ context
01915 3) iterate [j] over the range 0 ... [codebook_dimensions]-1 {
01916
01917 4) vector [v] element ([offset]+[i]) =
01918 vector [v] element ([offset]+[i]) +
01919 vector [entry_temp] element [j]
01920 5) increment [i]
01921
01922 }
01923
01924 6) if ( [i] is less than [n] ) continue at step 2
01925 7) done
01926 </pre></div><div class="section" lang="en"><div class="titlepage"><div><div><h4 class="title"><a name="id2498716"></a>8.6.5. format 2 specifics</h4></div></div></div><p>
01927 Format 2 is reducible to format 1. It may be implemented as an additional step prior to and an additional post-decode step after a normal format 1 decode.
01928 </p><p>
01929 Format 2 handles 'do not decode' vectors differently than residue 0 or
01930 1; if all vectors are marked 'do not decode', no decode occurrs.
01931 However, if at least one vector is to be decoded, all the vectors are
01932 decoded. We then request normal format 1 to decode a single vector
01933 representing all output channels, rather than a vector for each
01934 channel. After decode, deinterleave the vector into independent vectors, one for each output channel. That is:</p><div class="orderedlist"><ol type="1"><li>If all vectors 0 through <span class="emphasis"><em>ch</em></span>-1 are marked 'do not decode', allocate and clear a single vector <code class="varname">[v]</code>of length <span class="emphasis"><em>ch*n</em></span> and skip step 2 below; proceed directly to the post-decode step.</li><li>Rather than performing format 1 decode to produce <span class="emphasis"><em>ch</em></span> vectors of length <span class="emphasis"><em>n</em></span> each, call format 1 decode to produce a single vector <code class="varname">[v]</code> of length <span class="emphasis"><em>ch*n</em></span>. </li><li><p>Post decode: Deinterleave the single vector <code class="varname">[v]</code> returned by format 1 decode as described above into <span class="emphasis"><em>ch</em></span> independent vectors, one for each outputchannel, according to:
01935 </p><pre class="programlisting">
01936 1) iterate [i] over the range 0 ... [n]-1 {
01937
01938 2) iterate [j] over the range 0 ... [ch]-1 {
01939
01940 3) output vector number [j] element [i] = vector [v] element ([i] * [ch] + [j])
01941
01942 }
01943 }
01944
01945 4) done
01946 </pre><p>
01947 </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">
01948 $Id: 09-helper.xml 7186 2004-07-20 07:19:25Z xiphmont $
01949 </p></div></div></div><div class="section" lang="en"><div class="titlepage"><div><div><h3 class="title"><a name="id2507758"></a>9.1. Overview</h3></div></div></div><p>
01950 The equations below are used in multiple places by the Vorbis codec
01951 specification. Rather than cluttering up the main specification
01952 documents, they are defined here and referenced where appropriate.
01953 </p></div><div class="section" lang="en"><div class="titlepage"><div><div><h3 class="title"><a name="id2512257"></a>9.2. Functions</h3></div></div></div><div class="section" lang="en"><div class="titlepage"><div><div><h4 class="title"><a name="vorbis-spec-ilog"></a>9.2.1. ilog</h4></div></div></div><p>
01954 The "ilog(x)" function returns the position number (1 through n) of the highest set bit in the two's complement integer value
01955 <code class="varname">[x]</code>. Values of <code class="varname">[x]</code> less than zero are defined to return zero.</p><pre class="programlisting">
01956 1) [return_value] = 0;
01957 2) if ( [x] is greater than zero ){
01958
01959 3) increment [return_value];
01960 4) logical shift [x] one bit to the right, padding the MSb with zero
01961 5) repeat at step 2)
01962
01963 }
01964
01965 6) done
01966 </pre><p>
01967 Examples:
01968
01969 </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>
01970 </p></div><div class="section" lang="en"><div class="titlepage"><div><div><h4 class="title"><a name="vorbis-spec-float32_unpack"></a>9.2.2. float32_unpack</h4></div></div></div><p>
01971 "float32_unpack(x)" is intended to translate the packed binary
01972 representation of a Vorbis codebook float value into the
01973 representation used by the decoder for floating point numbers. For
01974 purposes of this example, we will unpack a Vorbis float32 into a
01975 host-native floating point number.</p><pre class="programlisting">
01976 1) [mantissa] = [x] bitwise AND 0x1fffff (unsigned result)
01977 2) [sign] = [x] bitwise AND 0x80000000 (unsigned result)
01978 3) [exponent] = ( [x] bitwise AND 0x7fe00000) shifted right 21 bits (unsigned result)
01979 4) if ( [sign] is nonzero ) then negate [mantissa]
01980 5) return [mantissa] * ( 2 ^ ( [exponent] - 788 ) )
01981 </pre></div><div class="section" lang="en"><div class="titlepage"><div><div><h4 class="title"><a name="vorbis-spec-lookup1_values"></a>9.2.3. lookup1_values</h4></div></div></div><p>
01982 "lookup1_values(codebook_entries,codebook_dimensions)" is used to
01983 compute the correct length of the value index for a codebook VQ lookup
01984 table of lookup type 1. The values on this list are permuted to
01985 construct the VQ vector lookup table of size
01986 <code class="varname">[codebook_entries]</code>.</p><p>
01987 The return value for this function is defined to be 'the greatest
01988 integer value for which <code class="varname">[return_value] to the power of
01989 [codebook_dimensions] is less than or equal to
01990 [codebook_entries]</code>'.</p></div><div class="section" lang="en"><div class="titlepage"><div><div><h4 class="title"><a name="vorbis-spec-low_neighbor"></a>9.2.4. low_neighbor</h4></div></div></div><p>
01991 "low_neighbor(v,x)" finds the position <code class="varname">n</code> in vector <code class="varname">[v]</code> of
01992 the greatest value scalar element for which <code class="varname">n</code> is less than
01993 <code class="varname">[x]</code> and vector <code class="varname">[v]</code> element <code class="varname">n</code> is less
01994 than vector <code class="varname">[v]</code> element <code class="varname">[x]</code>.</p><div class="section" lang="en"><div class="titlepage"><div><div><h5 class="title"><a name="vorbis-spec-high_neighbor"></a>9.2.4.1. high_neighbor</h5></div></div></div><p>
01995 "high_neighbor(v,x)" finds the position <code class="varname">n</code> in vector [v] of
01996 the lowest value scalar element for which <code class="varname">n</code> is less than
01997 <code class="varname">[x]</code> and vector <code class="varname">[v]</code> element <code class="varname">n</code> is greater
01998 than vector <code class="varname">[v]</code> element <code class="varname">[x]</code>.</p></div><div class="section" lang="en"><div class="titlepage"><div><div><h5 class="title"><a name="vorbis-spec-render_point"></a>9.2.4.2. render_point</h5></div></div></div><p>
01999 "render_point(x0,y0,x1,y1,X)" is used to find the Y value at point X
02000 along the line specified by x0, x1, y0 and y1. This function uses an
02001 integer algorithm to solve for the point directly without calculating
02002 intervening values along the line.</p><pre class="programlisting">
02003 1) [dy] = [y1] - [y0]
02004 2) [adx] = [x1] - [x0]
02005 3) [ady] = absolute value of [dy]
02006 4) [err] = [ady] * ([X] - [x0])
02007 5) [off] = [err] / [adx] using integer division
02008 6) if ( [dy] is less than zero ) {
02009
02010 7) [Y] = [y0] - [off]
02011
02012 } else {
02013
02014 8) [Y] = [y0] + [off]
02015
02016 }
02017
02018 9) done
02019 </pre></div><div class="section" lang="en"><div class="titlepage"><div><div><h5 class="title"><a name="vorbis-spec-render_line"></a>9.2.4.3. render_line</h5></div></div></div><p>
02020 Floor decode type one uses the integer line drawing algorithm of
02021 "render_line(x0, y0, x1, y1, v)" to construct an integer floor
02022 curve for contiguous piecewise line segments. Note that it has not
02023 been relevant elsewhere, but here we must define integer division as
02024 rounding division of both positive and negative numbers toward zero.
02025 </p><pre class="programlisting">
02026 1) [dy] = [y1] - [y0]
02027 2) [adx] = [x1] - [x0]
02028 3) [ady] = absolute value of [dy]
02029 4) [base] = [dy] / [adx] using integer division
02030 5) [x] = [x0]
02031 6) [y] = [y0]
02032 7) [err] = 0
02033
02034 8) if ( [dy] is less than 0 ) {
02035
02036 9) [sy] = [base] - 1
02037
02038 } else {
02039
02040 10) [sy] = [base] + 1
02041
02042 }
02043
02044 11) [ady] = [ady] - (absolute value of [base]) * [adx]
02045 12) vector [v] element [x] = [y]
02046
02047 13) iterate [x] over the range [x0]+1 ... [x1]-1 {
02048
02049 14) [err] = [err] + [ady];
02050 15) if ( [err] >= [adx] ) {
02051
02052 16) [err] = [err] - [adx]
02053 17) [y] = [y] + [sy]
02054
02055 } else {
02056
02057 18) [y] = [y] + [base]
02058
02059 }
02060
02061 19) vector [v] element [x] = [y]
02062
02063 }
02064 </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">
02065 $Id: 10-tables.xml 7186 2004-07-20 07:19:25Z xiphmont $
02066 </p></div></div></div><div class="section" lang="en"><div class="titlepage"><div><div><h3 class="title"><a name="vorbis-spec-floor1_inverse_dB_table"></a>10.1. floor1_inverse_dB_table</h3></div></div></div><p>
02067 The vector <code class="varname">[floor1_inverse_dB_table]</code> is a 256 element static
02068 lookup table consiting of the following values (read left to right
02069 then top to bottom):</p><pre class="screen">
02070 1.0649863e-07, 1.1341951e-07, 1.2079015e-07, 1.2863978e-07,
02071 1.3699951e-07, 1.4590251e-07, 1.5538408e-07, 1.6548181e-07,
02072 1.7623575e-07, 1.8768855e-07, 1.9988561e-07, 2.1287530e-07,
02073 2.2670913e-07, 2.4144197e-07, 2.5713223e-07, 2.7384213e-07,
02074 2.9163793e-07, 3.1059021e-07, 3.3077411e-07, 3.5226968e-07,
02075 3.7516214e-07, 3.9954229e-07, 4.2550680e-07, 4.5315863e-07,
02076 4.8260743e-07, 5.1396998e-07, 5.4737065e-07, 5.8294187e-07,
02077 6.2082472e-07, 6.6116941e-07, 7.0413592e-07, 7.4989464e-07,
02078 7.9862701e-07, 8.5052630e-07, 9.0579828e-07, 9.6466216e-07,
02079 1.0273513e-06, 1.0941144e-06, 1.1652161e-06, 1.2409384e-06,
02080 1.3215816e-06, 1.4074654e-06, 1.4989305e-06, 1.5963394e-06,
02081 1.7000785e-06, 1.8105592e-06, 1.9282195e-06, 2.0535261e-06,
02082 2.1869758e-06, 2.3290978e-06, 2.4804557e-06, 2.6416497e-06,
02083 2.8133190e-06, 2.9961443e-06, 3.1908506e-06, 3.3982101e-06,
02084 3.6190449e-06, 3.8542308e-06, 4.1047004e-06, 4.3714470e-06,
02085 4.6555282e-06, 4.9580707e-06, 5.2802740e-06, 5.6234160e-06,
02086 5.9888572e-06, 6.3780469e-06, 6.7925283e-06, 7.2339451e-06,
02087 7.7040476e-06, 8.2047000e-06, 8.7378876e-06, 9.3057248e-06,
02088 9.9104632e-06, 1.0554501e-05, 1.1240392e-05, 1.1970856e-05,
02089 1.2748789e-05, 1.3577278e-05, 1.4459606e-05, 1.5399272e-05,
02090 1.6400004e-05, 1.7465768e-05, 1.8600792e-05, 1.9809576e-05,
02091 2.1096914e-05, 2.2467911e-05, 2.3928002e-05, 2.5482978e-05,
02092 2.7139006e-05, 2.8902651e-05, 3.0780908e-05, 3.2781225e-05,
02093 3.4911534e-05, 3.7180282e-05, 3.9596466e-05, 4.2169667e-05,
02094 4.4910090e-05, 4.7828601e-05, 5.0936773e-05, 5.4246931e-05,
02095 5.7772202e-05, 6.1526565e-05, 6.5524908e-05, 6.9783085e-05,
02096 7.4317983e-05, 7.9147585e-05, 8.4291040e-05, 8.9768747e-05,
02097 9.5602426e-05, 0.00010181521, 0.00010843174, 0.00011547824,
02098 0.00012298267, 0.00013097477, 0.00013948625, 0.00014855085,
02099 0.00015820453, 0.00016848555, 0.00017943469, 0.00019109536,
02100 0.00020351382, 0.00021673929, 0.00023082423, 0.00024582449,
02101 0.00026179955, 0.00027881276, 0.00029693158, 0.00031622787,
02102 0.00033677814, 0.00035866388, 0.00038197188, 0.00040679456,
02103 0.00043323036, 0.00046138411, 0.00049136745, 0.00052329927,
02104 0.00055730621, 0.00059352311, 0.00063209358, 0.00067317058,
02105 0.00071691700, 0.00076350630, 0.00081312324, 0.00086596457,
02106 0.00092223983, 0.00098217216, 0.0010459992, 0.0011139742,
02107 0.0011863665, 0.0012634633, 0.0013455702, 0.0014330129,
02108 0.0015261382, 0.0016253153, 0.0017309374, 0.0018434235,
02109 0.0019632195, 0.0020908006, 0.0022266726, 0.0023713743,
02110 0.0025254795, 0.0026895994, 0.0028643847, 0.0030505286,
02111 0.0032487691, 0.0034598925, 0.0036847358, 0.0039241906,
02112 0.0041792066, 0.0044507950, 0.0047400328, 0.0050480668,
02113 0.0053761186, 0.0057254891, 0.0060975636, 0.0064938176,
02114 0.0069158225, 0.0073652516, 0.0078438871, 0.0083536271,
02115 0.0088964928, 0.009474637, 0.010090352, 0.010746080,
02116 0.011444421, 0.012188144, 0.012980198, 0.013823725,
02117 0.014722068, 0.015678791, 0.016697687, 0.017782797,
02118 0.018938423, 0.020169149, 0.021479854, 0.022875735,
02119 0.024362330, 0.025945531, 0.027631618, 0.029427276,
02120 0.031339626, 0.033376252, 0.035545228, 0.037855157,
02121 0.040315199, 0.042935108, 0.045725273, 0.048696758,
02122 0.051861348, 0.055231591, 0.058820850, 0.062643361,
02123 0.066714279, 0.071049749, 0.075666962, 0.080584227,
02124 0.085821044, 0.091398179, 0.097337747, 0.10366330,
02125 0.11039993, 0.11757434, 0.12521498, 0.13335215,
02126 0.14201813, 0.15124727, 0.16107617, 0.17154380,
02127 0.18269168, 0.19456402, 0.20720788, 0.22067342,
02128 0.23501402, 0.25028656, 0.26655159, 0.28387361,
02129 0.30232132, 0.32196786, 0.34289114, 0.36517414,
02130 0.38890521, 0.41417847, 0.44109412, 0.46975890,
02131 0.50028648, 0.53279791, 0.56742212, 0.60429640,
02132 0.64356699, 0.68538959, 0.72993007, 0.77736504,
02133 0.82788260, 0.88168307, 0.9389798, 1.
02134 </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="id2520211"></a>A.1. Overview</h3></div></div></div><p>
02135 This document describes using Ogg logical and physical transport
02136 streams to encapsulate Vorbis compressed audio packet data into file
02137 form.</p><p>
02138 The <a href="#vorbis-spec-intro" title="1. Introduction and Description">Section 1, “Introduction and Description”</a> provides an overview of the construction
02139 of Vorbis audio packets.</p><p>
02140 The <a href="oggstream.html" target="_top">Ogg
02141 bitstream overview</a> and <a href="framing.html" target="_top">Ogg logical
02142 bitstream and framing spec</a> provide detailed descriptions of Ogg
02143 transport streams. This specification document assumes a working
02144 knowledge of the concepts covered in these named backround
02145 documents. Please read them first.</p><div class="section" lang="en"><div class="titlepage"><div><div><h4 class="title"><a name="id2530380"></a>A.1.1. Restrictions</h4></div></div></div><p>
02146 The Ogg/Vorbis I specification currently dictates that Ogg/Vorbis
02147 streams use Ogg transport streams in degenerate, unmultiplexed
02148 form only. That is:
02149
02150 </p><div class="itemizedlist"><ul type="disc"><li>
02151 A meta-headerless Ogg file encapsulates the Vorbis I packets
02152 </li><li>
02153 The Ogg stream may be chained, i.e. contain multiple, contigous logical streams (links).
02154 </li><li>
02155 The Ogg stream must be unmultiplexed (only one stream, a Vorbis audio stream, per link)
02156 </li></ul></div><p>
02157 </p><p>
02158 This is not to say that it is not currently possible to multiplex
02159 Vorbis with other media types into a multi-stream Ogg file. At the
02160 time this document was written, Ogg was becoming a popular container
02161 for low-bitrate movies consisting of DiVX video and Vorbis audio.
02162 However, a 'Vorbis I audio file' is taken to imply Vorbis audio
02163 existing alone within a degenerate Ogg stream. A compliant 'Vorbis
02164 audio player' is not required to implement Ogg support beyond the
02165 specific support of Vorbis within a degenrate ogg stream (naturally,
02166 application authors are encouraged to support full multiplexed Ogg
02167 handling).
02168 </p></div><div class="section" lang="en"><div class="titlepage"><div><div><h4 class="title"><a name="id2512176"></a>A.1.2. MIME type</h4></div></div></div><p>
02169 The correct MIME type of any Ogg file is <code class="literal">application/ogg</code>.
02170 However, if a file is a Vorbis I audio file (which implies a
02171 degenerate Ogg stream including only unmultiplexed Vorbis audio), the
02172 mime type <code class="literal">audio/x-vorbis</code> is also allowed.</p></div></div><div class="section" lang="en"><div class="titlepage"><div><div><h3 class="title"><a name="id2520628"></a>A.2. Encapsulation</h3></div></div></div><p>
02173 Ogg encapsulation of a Vorbis packet stream is straightforward.</p><div class="itemizedlist"><ul type="disc"><li>
02174 The first Vorbis packet (the identification header), which
02175 uniquely identifies a stream as Vorbis audio, is placed alone in the
02176 first page of the logical Ogg stream. This results in a first Ogg
02177 page of exactly 58 bytes at the very beginning of the logical stream.
02178 </li><li>
02179 This first page is marked 'beginning of stream' in the page flags.
02180 </li><li>
02181 The second and third vorbis packets (comment and setup
02182 headers) may span one or more pages beginning on the second page of
02183 the logical stream. However many pages they span, the third header
02184 packet finishes the page on which it ends. The next (first audio) packet
02185 must begin on a fresh page.
02186 </li><li>
02187 The granule position of these first pages containing only headers is zero.
02188 </li><li>
02189 The first audio packet of the logical stream begins a fresh Ogg page.
02190 </li><li>
02191 Packets are placed into ogg pages in order until the end of stream.
02192 </li><li>
02193 The last page is marked 'end of stream' in the page flags.
02194 </li><li>
02195 Vorbis packets may span page boundaries.
02196 </li><li>
02197 The granule position of pages containing Vorbis audio is in units
02198 of PCM audio samples (per channel; a stereo stream's granule position
02199 does not increment at twice the speed of a mono stream).
02200 </li><li>
02201 The granule position of a page represents the end PCM sample
02202 position of the last packet <span class="emphasis"><em>completed</em></span> on that page.
02203 A page that is entirely spanned by a single packet (that completes on a
02204 subsequent page) has no granule position, and the granule position is
02205 set to '-1'.
02206 </li><li><p>
02207 The granule (PCM) position of the first page need not indicate
02208 that the stream started at position zero. Although the granule
02209 position belongs to the last completed packet on the page and a
02210 valid granule position must be positive, by
02211 inference it may indicate that the PCM position of the beginning
02212 of audio is positive or negative.
02213 </p><div class="itemizedlist"><ul type="circle"><li>
02214 A positive starting value simply indicates that this stream begins at
02215 some positive time offset, potentially within a larger
02216 program. This is a common case when connecting to the middle
02217 of broadcast stream.
02218 </li><li>
02219 A negative value indicates that
02220 output samples preceeding time zero should be discarded during
02221 decoding; this technique is used to allow sample-granularity
02222 editing of the stream start time of already-encoded Vorbis
02223 streams. The number of samples to be discarded must not exceed
02224 the overlap-add span of the first two audio packets.
02225 </li></ul></div><p>
02226 In both of these cases in which the initial audio PCM starting
02227 offset is nonzero, the second finished audio packet must flush the
02228 page on which it appears and the third packet begin a fresh page.
02229 This allows the decoder to always be able to perform PCM position
02230 adjustments before needing to return any PCM data from synthesis,
02231 resulting in correct positioning information without any aditional
02232 seeking logic.
02233 </p><div class="note" style="margin-left: 0.5in; margin-right: 0.5in;"><h3 class="title">Note</h3><p>
02234 Failure to do so should, at worst, cause a
02235 decoder implementation to return incorrect positioning information
02236 for seeking operations at the very beginning of the stream.
02237 </p></div></li><li>
02238 A granule position on the final page in a stream that indicates
02239 less audio data than the final packet would normally return is used to
02240 end the stream on other than even frame boundaries. The difference
02241 between the actual available data returned and the declared amount
02242 indicates how many trailing samples to discard from the decoding
02243 process.
02244 </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">
02245
02246
02247
02248 <p>Please consult the internet draft <em class="citetitle">RTP Payload Format for Vorbis Encoded
02249 Audio</em> for description of how to embed Vorbis audio in an RTP stream.</p>
02250
02251 </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>
02252 Ogg is a <a href="http://www.xiph.org/" target="_top">Xiph.org Foundation</a> effort
02253 to protect essential tenets of Internet multimedia from corporate
02254 hostage-taking; Open Source is the net's greatest tool to keep
02255 everyone honest. See <a href="http://www.xiph.org/about.html" target="_top">About
02256 the Xiph.org Foundation</a> for details.
02257 </p><p>
02258 Ogg Vorbis is the first Ogg audio CODEC. Anyone may freely use and
02259 distribute the Ogg and Vorbis specification, whether in a private,
02260 public or corporate capacity. However, the Xiph.org Foundation and
02261 the Ogg project (xiph.org) reserve the right to set the Ogg Vorbis
02262 specification and certify specification compliance.</p><p>
02263 Xiph.org's Vorbis software CODEC implementation is distributed under a
02264 BSD-like license. This does not restrict third parties from
02265 distributing independent implementations of Vorbis software under
02266 other licenses.</p><p>
02267 Ogg, Vorbis, Xiph.org Foundation and their logos are trademarks (tm)
02268 of the <a href="http:
02269 pages are copyright (C) 1994-2004 Xiph.org Foundation. All rights
02270 reserved.</p><p>
02271 This document is set in DocBook XML.
02272 </p></div></div></body></html>
