[FFmpeg-devel] [PATCH][RFC] Lagarith Decoder.

[Loren Merritt]

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
> methods).

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.

--Loren Merritt