[FFmpeg-devel] [PATCH][RFC] Lagarith Decoder.
Fri Aug 21 14:24:35 CEST 2009
On Fri, 21 Aug 2009, Reimar D?ffinger wrote:
> On Thu, Aug 20, 2009 at 11:45:53PM -0600, Nathan Caldwell wrote:
>> + while ((l->prob[val + 1] <= low_scaled) && (val < 255))
>> + val++;
Increase the array size by one, add a sentinel bigger than any possible
value of low_scaled, and omit the (val < 255).
> Since I think prob is monotonous you could use a binary search the 8
> steps of which could be completely unrolled. It might well be slower
> though (if low_scaled is usually small - to avoid this you could
> try to precalculate a low_scaled threshold to switch between the two
That's what range_hash is for. The linear part of the search should
terminate after an average of about 2 iterations. Large discrepancies are
possible, but they should be so rare as to not be worth even checking for
any method other than linear search. (That's a strict bound on amortized
cost, not just an average case, as long as the encoder chose a probability
table that's close the the actual pixel frequencies.)
You might still want to unroll a little, so that there are no branches in
the frequently executed part.
More information about the ffmpeg-devel