Hi, I&#39;m looking at speed optimization options for the Tremor lowmem version of the Ogg Vorbis decoder.  One area I am looking at closely is the codebook search.  Specifically, the Huffman tree traversal (the set of for loops inside vorbis_book_decodevv_add commented with things like 8/8, 8/16, etc).  I thought I could potentially remove the for loop entirely and just check for valid data at the leaf of the tree.  However, it seems that this doesn&#39;t work because the encoder doesn&#39;t set the MSb to 1 when the leaf is at the maximum tree depth, so it&#39;s using the termination condition from the for loop rather than the test inside the loop to exit.  My thought was that I could change the codebook initialization routine to add a 1 to the MSb of all leaf locations, including those at the end of the tree.  That should remove one additional test as I can just keep shifting lok by 1 until I find my data.<br>
<br>My questions are:<br><br>1.  Is my understanding of the tree traversal correct?<br>2.  Is there a reason why this optimization wouldn&#39;t work?  It&#39;s a little baffling to me why the encoder wouldn&#39;t indicate valid data at the maximum depth by setting the MSb, but there might be something I&#39;m missing.<br>
3.  Is there an efficient way to identify all the leaf locations?  My first thought was to replicate the codebook search code and feed in all valid values for lok, see if I reach the maximum depth in the search, and if I do set the MSb to 1.  However, this is a pretty dumb exhaustive search while will add a fair bit of delay in the initialization of the codec.  Also, I&#39;m not sure if all trees are valid for all values of lok.  Would this work/is there a better way?<br>
<br>If anyone has any thoughts on where else to focus optimization time I&#39;d appreciate it.  I&#39;ve already done some work reordering the codebook search code to optimize for mono/stereo files, and that was quite helpful.<br>
<br>Thanks!<br><br>Ethan<br>