Home | History | Annotate | Download | only in doc
      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>
    240