1<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Strict//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-strict.dtd">
2<html>
3<head>
4
5<meta http-equiv="Content-Type" content="text/html; charset=iso-8859-15"/>
6<title>Ogg Vorbis Documentation</title>
7
8<style type="text/css">
9body {
10  margin: 0 18px 0 18px;
11  padding-bottom: 30px;
12  font-family: Verdana, Arial, Helvetica, sans-serif;
13  color: #333333;
14  font-size: .8em;
15}
16
17a {
18  color: #3366cc;
19}
20
21img {
22  border: 0;
23}
24
25#xiphlogo {
26  margin: 30px 0 16px 0;
27}
28
29#content p {
30  line-height: 1.4;
31}
32
33h1, h1 a, h2, h2 a, h3, h3 a {
34  font-weight: bold;
35  color: #ff9900;
36  margin: 1.3em 0 8px 0;
37}
38
39h1 {
40  font-size: 1.3em;
41}
42
43h2 {
44  font-size: 1.2em;
45}
46
47h3 {
48  font-size: 1.1em;
49}
50
51li {
52  line-height: 1.4;
53}
54
55#copyright {
56  margin-top: 30px;
57  line-height: 1.5em;
58  text-align: center;
59  font-size: .8em;
60  color: #888888;
61  clear: both;
62}
63</style>
64
65</head>
66
67<body>
68
69<div id="xiphlogo">
70  <a href="http://www.xiph.org/"><img src="fish_xiph_org.png" alt="Fish Logo and Xiph.org"/></a>
71</div>
72
73<h1>Ogg Vorbis I format specification: helper equations</h1>
74
75<h1>Overview</h1>
76
77<p>The equations below are used in multiple places by the Vorbis codec
78specification. Rather than cluttering up the main specification
79documents, they are defined here and linked in the main documents
80where appropriate.</p>
81
82<h2><a name="log">ilog</a></h2>
83
84<p>The "ilog(x)" function returns the position number (1 through n) of the
85highest set bit in the two's complement integer value
86<tt>[x]</tt>. Values of <tt>[x]</tt> less than zero are defined to return zero.</p>
87
88<pre>
89  1) [return_value] = 0;
90  2) if ( [x] is greater than zero ){
91
92       3) increment [return_value];
93       4) logical shift [x] one bit to the right, padding the MSb with zero
94       5) repeat at step 2)
95
96     }
97
98   6) done
99</pre>
100
101<p>Examples:</p>
102
103<ul>
104<li>ilog(0) = 0;</li>
105<li>ilog(1) = 1;</li>
106<li>ilog(2) = 2;</li>
107<li>ilog(3) = 2;</li>
108<li>ilog(4) = 3;</li>
109<li>ilog(7) = 3;</li>
110<li>ilog(negative number) = 0;</li>
111</ul>
112
113<h2><a name="float32_unpack">float32_unpack</a></h2>
114
115<p>"float32_unpack(x)" is intended to translate the packed binary
116representation of a Vorbis codebook float value into the
117representation used by the decoder for floating point numbers. For
118purposes of this example, we will unpack a Vorbis float32 into a
119host-native floating point number.</p>
120
121<pre>
122  1) [mantissa] = [x] bitwise AND 0x1fffff (unsigned result)
123  2) [sign] = [x] bitwise AND 0x80000000 (unsigned result)
124  3) [exponent] = ( [x] bitwise AND 0x7fe00000) shifted right 21 bits (unsigned result)
125  4) if ( [sign] is nonzero ) then negate [mantissa]
126  5) return [mantissa] * ( 2 ^ ( [exponent] - 788 ) )
127</pre>
128
129<h2><a name="lookup1_values">lookup1_values</a></h2>
130
131<p>"lookup1_values(codebook_entries,codebook_dimensions)" is used to
132compute the correct length of the value index for a codebook VQ lookup
133table of lookup type 1. The values on this list are permuted to
134construct the VQ vector lookup table of size
135<tt>[codebook_entries]</tt>.</p>
136
137<p>The return value for this function is defined to be 'the greatest
138integer value for which <tt>[return_value] to the power of
139[codebook_dimensions] is less than or equal to
140[codebook_entries]</tt>'.</p>
141
142<h2><a name="low_neighbor">low_neighbor</a></h2>
143
144<p>"low_neighbor(v,x)" finds the position <i>n</i> in vector [v] of
145the greatest value scalar element for which <i>n</i> is less than
146<tt>[x]</tt> and <tt>vector [v] element <i>n</i> is less
147than vector [v] element [x]</tt>.</p>
148
149<h2><a name="high_neighbor">high_neighbor</a></h2>
150
151<p>"high_neighbor(v,x)" finds the position <i>n</i> in vector [v] of
152the lowest value scalar element for which <i>n</i> is less than
153<tt>[x]</tt> and <tt>vector [v] element <i>n</i> is greater
154than vector [v] element [x]</tt>.</p>
155
156<h2><a name="render_point">render_point</a></h2>
157
158<p>"render_point(x0,y0,x1,y1,X)" is used to find the Y value at point X
159along the line specified by x0, x1, y0 and y1. This function uses an
160integer algorithm to solve for the point directly without calculating
161intervening values along the line.</p>
162
163<pre>
164  1)  [dy] = [y1] - [y0]
165  2) [adx] = [x1] - [x0]
166  3) [ady] = absolute value of [dy]
167  4) [err] = [ady] * ([X] - [x0])
168  5) [off] = [err] / [adx] using integer division
169  6) if ( [dy] is less than zero ) {
170
171       7) [Y] = [y0] - [off]
172
173     } else {
174
175       8) [Y] = [y0] + [off]
176
177     }
178
179  9) done
180</pre>
181
182<h2><a name="render_line">render_line</a></h2>
183
184<p>Floor decode type one uses the integer line drawing algorithm of
185"render_line(x0, y0, x1, y1, v)" to construct an integer floor
186curve for contiguous piecewise line segments. Note that it has not
187been relevant elsewhere, but here we must define integer division as
188rounding division of both positive and negative numbers toward zero.</p>
189
190<pre>
191  1)   [dy] = [y1] - [y0]
192  2)  [adx] = [x1] - [x0]
193  3)  [ady] = absolute value of [dy]
194  4) [base] = [dy] / [adx] using integer division
195  5)    [x] = [x0]
196  6)    [y] = [y0]
197  7)  [err] = 0
198
199  8) if ( [dy] is less than 0 ) {
200
201        9) [sy] = [base] - 1
202
203     } else {
204
205       10) [sy] = [base] + 1
206
207     }
208
209 11) [ady] = [ady] - (absolute value of [base]) * [adx]
210 12) vector [v] element [x] = [y]
211
212 13) iterate [x] over the range [x0]+1 ... [x1]-1 {
213
214       14) [err] = [err] + [ady];
215       15) if ( [err] >= [adx] ) {
216
217             15) [err] = [err] - [adx]
218             16)   [y] = [y] + [sy]
219
220           } else {
221
222             17) [y] = [y] + [base]
223
224           }
225
226       18) vector [v] element [x] = [y]
227
228     }
229</pre>
230
231<div id="copyright">
232  The Xiph Fish Logo is a
233  trademark (&trade;) of Xiph.Org.<br/>
234
235  These pages &copy; 1994 - 2005 Xiph.Org. All rights reserved.
236</div>
237
238</body>
239</html>
240