Fix rounding in bits2pulses search.
authorTimothy B. Terriberry <tterribe@xiph.org>
Tue, 4 Jan 2011 17:07:40 +0000 (09:07 -0800)
committerJean-Marc Valin <jean-marc.valin@usherbrooke.ca>
Sat, 8 Jan 2011 19:57:01 +0000 (14:57 -0500)
commit1cb32aa057d356ec4a0d2398e950aface7eaa5ec
tree8e67bf098cdf82709cbbe8795b9a63b48dcb46ed
parent845dfa19860c9e4806b6ad9bed0c8a8581626bce
Fix rounding in bits2pulses search.

The mid = (lo+hi)>>1 line in the binary search would allow hi to drop
 down to the same value as lo, meaning the rounding after the search
 would be choosing between the same two values.
This patch changes it to (lo+hi+1)>>1.
This will allow lo to increase up to the value hi, but only in the
 case that we can't possibly allocate enough pulses to meet the
 target number of bits (in which case the rounding doesn't matter).
To pay for the extra add, this moves the +1 in the comparison to bits
 to the other side, which can then be taken outside the loop.
The compiler can't normally do this because it might cause overflow
 which would change the results.

This rarely mattered, but gives a 0.01 PEAQ improvement on 12-byte
 120 sample frames.
It also makes the search process describable with a simple
 algorithm, rather than relying on this particular optimized
 implementation.
I.e., the binary search loop can now be replaced with
  for(lo=0;lo+1<cache[0]&&cache[lo+1]<bits;lo++);
  hi=lo+1;
 and it will give equivalent results.
This was not true before.
libcelt/rate.h