[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