[FFmpeg-devel] [PATCH] Arithmetic decoding in ALS

Michael Niedermayer michaelni
Wed Jan 13 00:00:40 CET 2010

On Tue, Jan 12, 2010 at 08:50:27PM +0100, Thilo Borgmann wrote:
> Am 12.01.10 00:33, schrieb Michael Niedermayer:
> > On Mon, Jan 11, 2010 at 09:15:05PM +0100, Thilo Borgmann wrote:
> >> ...
> > 
> >> +    while (cf_table[sx][(symbol + 1) << delta] > target)
> >> +        symbol++;
> > 
> > this probably can be speed up by a LUT of some of the MSBs
> I thought a bit about that but I'm still lacking an idea of how to
> generate suitable lookup tables.
> What I've tried and benchmarked as an alternative is to use a bisection
> method to search through cf_table[sx] but its slower than the existing
> solution - most likely because the number of iterations is small enough
> in almost all cases. Iterations are less than 10 in almost all cases and
> just about 900 dezicycles are spend within this loop (~1350 using
> bisection).
> So I don't know if it really needs to be optimized?

unsigned int symbol = 0;

while (cf_table[sx][(symbol + 1) << delta] > target)

can be improved to
unsigned int symbol = 1 << delta;

while (cf_table[sx][symbol] > target)
    symbol += 1<<delta;
symbol= (symbol>>delta)-1;

now with LUT:
unsigned int symbol = (LUT[sx][target>>8]>>delta)<<delta;

while (cf_table[sx][symbol] > target)
    symbol += 1<<delta;
symbol= (symbol>>delta)-1;

the lut can be generated for this by just trying all target values
and setting the LUT to the smallest symbol found by that, this isnt
efficient but its easy to understand

there are of course many other ways to do this

Michael     GnuPG fingerprint: 9FF2128B147EF6730BADF133611EC787040B0FAB

Old school: Use the lowest level language in which you can solve the problem
New school: Use the highest level language in which the latest supercomputer
            can solve the problem without the user falling asleep waiting.
-------------- next part --------------
A non-text attachment was scrubbed...
Name: not available
Type: application/pgp-signature
Size: 189 bytes
Desc: Digital signature
URL: <http://lists.mplayerhq.hu/pipermail/ffmpeg-devel/attachments/20100113/d3e072be/attachment.pgp>

More information about the ffmpeg-devel mailing list