Planet
navi homePPSaboutscreenshotsdownloaddevelopmentforum

source: downloads/libvorbis-1.2.0/doc/Vorbis_I_spec.html @ 16

Last change on this file since 16 was 16, checked in by landauf, 17 years ago

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