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 (™) of Xiph.Org.<br/> 234 235 These pages © 1994 - 2005 Xiph.Org. All rights reserved. 236</div> 237 238</body> 239</html> 240
