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.
diff --git a/libcelt/rate.h b/libcelt/rate.h
index 0e6391a..4b4a878 100644
--- 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;