doc/helper.html

   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">
   9 body {
  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
  17 a {
  18   color: #3366cc;
  19 }
  20
  21 img {
  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
  33 h1, h1 a, h2, h2 a, h3, h3 a {
  34   font-weight: bold;
  35   color: #ff9900;
  36   margin: 1.3em 0 8px 0;
  37 }
  38
  39 h1 {
  40   font-size: 1.3em;
  41 }
  42
  43 h2 {
  44   font-size: 1.2em;
  45 }
  46
  47 h3 {
  48   font-size: 1.1em;
  49 }
  50
  51 li {
  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
  78 specification. Rather than cluttering up the main specification
  79 documents, they are defined here and linked in the main documents
  80 where 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
  85 highest 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
 116 representation of a Vorbis codebook float value into the
 117 representation used by the decoder for floating point numbers. For
 118 purposes of this example, we will unpack a Vorbis float32 into a
 119 host-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
 132 compute the correct length of the value index for a codebook VQ lookup
 133 table of lookup type 1. The values on this list are permuted to
 134 construct 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
 138 integer 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
 145 the 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
 147 than 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
 152 the 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
 154 than 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
 159 along the line specified by x0, x1, y0 and y1. This function uses an
 160 integer algorithm to solve for the point directly without calculating
 161 intervening 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
 186 curve for contiguous piecewise line segments. Note that it has not
 187 been relevant elsewhere, but here we must define integer division as
 188 rounding 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>