[FFmpeg-devel] [PATCH]Lagarith decoder.

[Loren Merritt]

On Sat, 24 Oct 2009, Michael Niedermayer wrote:
> On Thu, Oct 15, 2009 at 08:42:54PM -0600, Nathan Caldwell wrote:
>
>> +    if (l->low >= range_scaled * l->prob[255]) {
>> +        val = 255;
>> +        l->range -= range_scaled * l->prob[255];
>> +    } else {
>> +        /* val = 0 is frequent enough to deserve a shortcut */
>> +        if (l->low < range_scaled * l->prob[1]) {
>> +            val = 0;
>
> isnt 0 more common than 255? and should thus be checked before on a
> shorter code path?

Yes.

>> +            shift &= 31;
>> +            low_scaled = (low_scaled << shift) | (low_scaled >> (32 - shift));
>> +            /* low_scaled is now a lower bound of low/range_scaled */
>> +            val = l->range_hash[(uint8_t) low_scaled];
>>
>> +            while (l->low >= range_scaled * l->prob[val + 1])
>> +                val++;
>
> is there some (small) bound on the number of iterations of this?
> if so it could be replaced by a if() or 2 ...

No. Amortized cost is bounded at 1 iteration, but the max for any given 
call can be up to 254. i.e. range_hash can be very wrong, but only for 
low-probability symbols.

--Loren Merritt