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

Michael Niedermayer michaelni
Mon Jan 18 23:38:00 CET 2010


On Thu, Jan 14, 2010 at 03:20:04PM +0100, Thilo Borgmann wrote:
> Am 13.01.10 00:00, schrieb Michael Niedermayer:
> > 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
> >>
> >> ...
> 
> Ok here is the approach with lookup (prediction...) tables then.
> 
> Speedup compared to full search i.e. not using any luts is about 12-15%:
> 
> 3580258 dezicycles in complete bgmc decoding using lut, 511 runs, 1 skips
> 4141277 dezicycles in complete bgmc decoding not using lut, 512 runs, 0
> skips
> 
> The size for the luts is tuneable. It might be easily added to use a
> #define to disable the use of luts completely, would this make sense?

probably not


> 
> The size of the luts might be further reduced if the shifted symbol
> would be stored and use a smaller type than uint for the luts. Then, the
> stored symbol would have to be shifted back before usage, but this again
> costs many << operations (one for each sample in the file). Useful?

maybe, depends on speed/size

> 
[...]
> +static unsigned int cf_tables_3[5][257] = {

static const

[...]
> +static unsigned int cf_lut       [LUT_BUFF + 1][16][LUT_SIZE];
> +static unsigned int cf_lut_status[LUT_BUFF + 1];
> +
> +
> +/** Initializes a given lookup table using a given delta
> + */
> +static void bgmc_lut_fill(unsigned int lut, unsigned int delta)
> +{
> +    unsigned int sx, i;
> +
> +    for (sx = 0; sx < 16; sx++)
> +        for (i = 0; i < LUT_SIZE; i++) {
> +            unsigned int target = (i + 1) << (FREQ_BITS - LUT_BITS);
> +            unsigned int symbol = 1 << delta;
> +
> +            while (cf_table[sx][symbol] > target)
> +                symbol += 1 << delta;
> +
> +            cf_lut[lut][sx][i] = symbol;
> +        }
> +
> +    cf_lut_status[lut] = delta;
> +}
> +
> +
> +/** Retunes the index of a suitable lookup table for a given delta
> + */
> +static unsigned int bgmc_lut_get(unsigned int delta)
> +{
> +    unsigned int lut = delta < LUT_BUFF ? delta : LUT_BUFF;
> +
> +    if (cf_lut_status[lut] != delta)
> +        bgmc_lut_fill(lut, delta);

this doesnt look thread safe


[...]
> @@ -120,6 +121,28 @@
>  };
>  
>  
> +/** Tail codes used in arithmetic coding using block Gilbert-Moore codes.
> + */
> +static unsigned int tail_code[16][6] = {

static const

[...]
> +                    if (res >= 0)
> +                        res += (max_msb    ) << cur_k;
> +                    else

{}

[...]
-- 
Michael     GnuPG fingerprint: 9FF2128B147EF6730BADF133611EC787040B0FAB

The real ebay dictionary, page 3
"Rare item" - "Common item with rare defect or maybe just a lie"
"Professional" - "'Toy' made in china, not functional except as doorstop"
"Experts will know" - "The seller hopes you are not an expert"
-------------- 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/20100118/7f83b5b5/attachment.pgp>



More information about the ffmpeg-devel mailing list