compute_sorted_huffman()

static void fl::third_party::vorbis::compute_sorted_huffman ( Codebook * c, uint8 * lengths, uint32 * values )

static

Definition at line 903 of file stb_vorbis.cpp.hpp.

{
   int32_t i, len;
   // build a list of all the entries
   // OPTIMIZATION: don't include the short ones, since they'll be caught by FAST_HUFFMAN.
   // this is kind of a frivolous optimization--I don't see any performance improvement,
   // but it's like 4 extra lines of code, so.
   if (!c->sparse) {
      int32_t k = 0;
      for (i=0; i < c->entries; ++i)
         if (include_in_sort(c, lengths[i]))
            c->sorted_codewords[k++] = bit_reverse(c->codewords[i]);
      FL_ASSERT(k == c->sorted_entries, "k must equal sorted_entries");
   } else {
      for (i=0; i < c->sorted_entries; ++i)
         c->sorted_codewords[i] = bit_reverse(c->codewords[i]);
   }
 
   fl::qsort(c->sorted_codewords, c->sorted_entries, sizeof(c->sorted_codewords[0]), uint32_compare);
   c->sorted_codewords[c->sorted_entries] = 0xffffffff;
 
   len = c->sparse ? c->sorted_entries : c->entries;
   // now we need to indicate how they correspond; we could either
   //   #1: sort a different data structure that says who they correspond to
   //   #2: for each sorted entry, search the original list to find who corresponds
   //   #3: for each original entry, find the sorted entry
   // #1 requires extra storage, #2 is slow, #3 can use binary search!
   for (i=0; i < len; ++i) {
      int32_t huff_len = c->sparse ? lengths[values[i]] : lengths[i];
      if (include_in_sort(c,huff_len)) {
         uint32 code = bit_reverse(c->codewords[i]);
         int32_t x=0, n=c->sorted_entries;
         while (n > 1) {
            // invariant: sc[x] <= code < sc[x+n]
            int32_t m = x + (n >> 1);
            if (c->sorted_codewords[m] <= code) {
               x = m;
               n -= (n>>1);
            } else {
               n >>= 1;
            }
         }
         FL_ASSERT(c->sorted_codewords[x] == code, "sorted_codewords must match code");
         if (c->sparse) {
            c->sorted_values[x] = values[i];
            c->codeword_lengths[x] = huff_len;
         } else {
            c->sorted_values[x] = i;
         }
      }
   }
}

References bit_reverse(), FL_ASSERT, fl::FL_NO_EXCEPT, include_in_sort(), lengths, fl::qsort(), uint32_compare(), and fl::x.

Referenced by start_decoder().

Here is the call graph for this function:

Here is the caller graph for this function: