More cleanups to compute_allocation().
authorTimothy B. Terriberry <tterribe@xiph.org>
Fri, 17 Dec 2010 00:50:16 +0000 (16:50 -0800)
committerJean-Marc Valin <jean-marc.valin@usherbrooke.ca>
Fri, 17 Dec 2010 01:20:09 +0000 (20:20 -0500)
The bisection search in compute_allocation() was not using the same
 method to count psum as interp_bits2pulses, i.e., it did not
 include the 64*C<<BITRES<<LM allocation ceiling (this adds at most
 84 max operations/frame, and so should have a trivial CPU cost).
Again, I wouldn't want to try to explain why these are different in
 a spec, so let's make them the same.

In addition, the procedure used to fill in bits1 and bits2 after the
 bisection search was not the same as the one used during the
 bisection search.
I.e., the
      if (bits1[j] > 0)
               bits1[j] += trim_offset[j];
 step was not also done for bits2, so bits1[j] + bits2[j] would not
 be equal to what was computed earlier for the hi line, and would
 not be guaranteed to be larger than total.
We now compute both allocation lines in the same manner, and then
 obtain bits2 by subtracting them, instead of trying to compute the
 offset from bits1 up front.

Finally, there was nothing to stop a bitstream from boosting a band
 beyond the number of bits remaining, which means that bits1 would
 not produce an allocation less than or equal to total, which means
 that some bands would receive a negative allocation in the decoder
 when the "left over" negative bits were redistributed to other
 bands.
This patch only adds the dynalloc offset to allocation lines greater
 than 0, so that an all-zeros floor still exists; the effect is that
 a dynalloc boost gets linearly scaled between allocation lines 0 and
 1, and is constant (like it was before) after that.
We don't have to add the extra condition to the bisection search,
 because it never examines allocation line 0.
This re-writes the indexing in the search to make that explicit;
 it was tested and gives exactly the same results in exactly the
 same number of iterations as the old search.

libcelt/rate.c

index c711fb4..ba9b8cf 100644 (file)
@@ -395,9 +395,9 @@ int compute_allocation(const CELTMode *m, int start, int end, const int *offsets
       trim_offset[j] = C*(m->eBands[j+1]-m->eBands[j])*(alloc_trim-5-LM)*(m->nbEBands-j-1)
             <<(LM+BITRES)>>6;
 
-   lo = 0;
-   hi = m->nbAllocVectors - 1;
-   while (hi-lo != 1)
+   lo = 1;
+   hi = m->nbAllocVectors - 2;
+   do
    {
       int psum = 0;
       int mid = (lo+hi) >> 1;
@@ -406,12 +406,10 @@ int compute_allocation(const CELTMode *m, int start, int end, const int *offsets
          int N = m->eBands[j+1]-m->eBands[j];
          bits1[j] = C*N*m->allocVectors[mid*len+j]<<LM>>2;
          if (bits1[j] > 0)
-            bits1[j] += trim_offset[j];
-         if (bits1[j] < 0)
-            bits1[j] = 0;
+            bits1[j] = IMAX(0, bits1[j] + trim_offset[j]);
          bits1[j] += offsets[j];
          if (bits1[j] >= thresh[j])
-            psum += bits1[j];
+            psum += IMIN(bits1[j], 64*C<<BITRES<<LM);
          else if (bits1[j] >= C<<BITRES)
             psum += C<<BITRES;
 
@@ -419,24 +417,29 @@ int compute_allocation(const CELTMode *m, int start, int end, const int *offsets
       }
       /*printf ("\n");*/
       if (psum > total)
-         hi = mid;
+         hi = mid - 1;
       else
-         lo = mid;
+         lo = mid + 1;
       /*printf ("lo = %d, hi = %d\n", lo, hi);*/
    }
+   while (lo <= hi);
+   hi = lo--;
    /*printf ("interp between %d and %d\n", lo, hi);*/
    for (j=start;j<end;j++)
    {
       int N = m->eBands[j+1]-m->eBands[j];
-      bits1[j] = (C*N*m->allocVectors[lo*len+j]<<LM>>2);
-      bits2[j] = (C*N*m->allocVectors[hi*len+j]<<LM>>2) - bits1[j];
+      bits1[j] = C*N*m->allocVectors[lo*len+j]<<LM>>2;
+      bits2[j] = C*N*m->allocVectors[hi*len+j]<<LM>>2;
       if (bits1[j] > 0)
-         bits1[j] += trim_offset[j];
-      if (bits1[j] < 0)
-         bits1[j] = 0;
-      bits1[j] += offsets[j];
+         bits1[j] = IMAX(0, bits1[j] + trim_offset[j]);
+      if (bits2[j] > 0)
+         bits2[j] = IMAX(0, bits2[j] + trim_offset[j]);
+      if (lo > 0)
+         bits1[j] += offsets[j];
+      bits2[j] += offsets[j];
       if (offsets[j]>0)
          skip_start = j;
+      bits2[j] -= bits1[j];
    }
    codedBands = interp_bits2pulses(m, start, end, skip_start, bits1, bits2, thresh,
          total, skip_rsv, pulses, ebits, fine_priority, len, C, LM, ec, encode, prev);