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

[Nathan Caldwell]

2009/8/14 Reimar D?ffinger <Reimar.Doeffinger at gmx.de>:
> On Fri, Aug 14, 2009 at 02:25:44PM -0600, Nathan Caldwell wrote:
>> On Wed, Aug 12, 2009 at 8:34 AM, Reimar
>> D?ffinger<Reimar.Doeffinger at gmx.de> wrote:
>> > On Mon, Aug 10, 2009 at 11:42:19PM -0600, Nathan Caldwell wrote:
>> >> + ? ?/* Scale probabilities so cumulative probability is an even power of 2. */
>> >> + ? ?cumulative_target = clp2(cumul_prob);
>> >> +
>> >> + ? ?scale_factor = cumulative_target / (double) cumul_prob;
>> >> +
>> >> + ? ?for (i = 1; i < 257; i++) {
>> >> + ? ? ? ?rac->prob[i] = (unsigned int) (rac->prob[i] * scale_factor);
>> >
>> > I think a 32x32 -> 64 bit multiply + right shift is a more reliable way
>> > to calculate this. floating-point IMO is usually misplaced in
>> > anything that claims to be lossless (yes, you can do it and even have
>> > it work cross-platform, but it's a real effort).
>>
>> I tried this earlier, but it doesn't retain enough precision. It was
>> right most of the time, but not all the time. I'm open to any other
>> suggestions.
>
> Please show the code you used.
> I admit I confused cumulative_target and cumul_prob in the scale_factor
> calculation, so it would be harder than I thought.
> Particularly since the code lacks some information on the limits of
> the values (and relatedly also lacks some necessary checks, e.g. all-0
> probabilities seem to trigger an endless loop, in addition to the
> possible crash/endless loop in lag_decode_prob).
> So the first question would be: what would be valid values for the
> probabilities?

In theory, 0 to UINT_MAX. Although in reality depends on the size of
the data being decoded. The probabilities are just a count of the
number of times each byte appears in the uncompressed data. However,
there are a few checks in the reference source to make sure the target
cumulative probability isn't greater than 0x80000000, but there isn't
really anything to prevent that large of a value from getting written
to the bitstream.

What I used was just naive fixed point.

uint64_t scale_factor;
scale_factor = ((uint64_t) cumulative_target << 32) / cumul_prob;

for (i = 1; i < 257; i++) {
    rac->prob[i] = (unsigned int) ((rac->prob[i] * scale_factor) >> 32);



-- 
-Nathan Caldwell