ref: 1cb32aa057d356ec4a0d2398e950aface7eaa5ec
parent: 845dfa19860c9e4806b6ad9bed0c8a8581626bce
author: Timothy B. Terriberry <[email protected]>
date: Tue Jan 4 04:07:40 EST 2011
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.
--- a/libcelt/rate.h
+++ b/libcelt/rate.h
@@ -66,16 +66,17 @@
lo = 0;
hi = cache[0];
+ bits--;
for (i=0;i<LOG_MAX_PSEUDO;i++)
{- int mid = (lo+hi)>>1;
+ int mid = (lo+hi+1)>>1;
/* OPT: Make sure this is implemented with a conditional move */
- if (cache[mid]+1 >= bits)
+ if (cache[mid] >= bits)
hi = mid;
else
lo = mid;
}
- if (bits- (lo == 0 ? 0 : cache[lo]+1) <= cache[hi]+1-bits)
+ if (bits- (lo == 0 ? -1 : cache[lo]) <= cache[hi]-bits)
return lo;
else
return hi;