[FFmpeg-devel] [PATCH] Optimize QTRLE encoding

[Michael Niedermayer]

On Fri, Feb 22, 2013 at 12:57:29PM -0500, Malcolm Bechard wrote:
> On Thu, Feb 21, 2013 at 8:22 PM, Michael Niedermayer <michaelni at gmx.at>wrote:
> 
> > > +    /* Initial values */
> > > +    lowest_bulk_cost = INT_MAX;
> > > +    lowest_bulk_cost_index = width;
> > > +    sec_lowest_bulk_cost = INT_MAX;
> > > +    sec_lowest_bulk_cost_index = width;
> > > +
> > > +    base_bulk_cost = 1 + s->pixel_size;
> > > +
> > >      for (i = width - 1; i >= 0; i--) {
> > >
> > > +        int prev_bulk_cost;
> > > +        int bulk_limit;
> > > +
> >
> > > +        int prev = i + 1;
> >
> > is it faster with this variable instead of using i+1 ?
> >
> >
> > > +
> > > +        bulk_limit = FFMIN(width - i, MAX_RLE_BULK);
> > > +
> > > +        /* If our lowest bulk cost index is too far away, replace it
> > > +         * with the next lowest bulk cost */
> > > +        if (i + bulk_limit < lowest_bulk_cost_index) {
> >
> > could be simplified with
> > if (FFMIN(width, i + MAX_RLE_BULK) < lowest_bulk_cost_index) {
> >
> >
> > > +            lowest_bulk_cost = sec_lowest_bulk_cost;
> > > +            lowest_bulk_cost_index = sec_lowest_bulk_cost_index;
> > > +
> > > +            sec_lowest_bulk_cost = INT_MAX;
> > > +            sec_lowest_bulk_cost_index = width;
> > > +        }
> > > +
> > > +        /* Deal with the first pixel's bulk cost */
> > > +        if (!i) {
> > > +            base_bulk_cost++;
> >
> > > +            if (lowest_bulk_cost < INT_MAX)
> > > +                lowest_bulk_cost++;
> > > +            if (sec_lowest_bulk_cost < INT_MAX)
> > > +                sec_lowest_bulk_cost++;
> >
> > these checks can be avoided by using INT_MAX/2 as the maximum
> >
> >
> > > +        }
> > > +
> > > +        /* Look at the bulk cost of the previous loop and see if it is
> > > +         * a new lower bulk cost */
> > > +        prev_bulk_cost = s->length_table[prev] + base_bulk_cost;
> > > +        if (prev_bulk_cost <= sec_lowest_bulk_cost) {
> > > +            /* If it's lower than the 2nd lowest, then it may be lower
> > > +             * than the lowest */
> >
> > > +            if (prev_bulk_cost <= lowest_bulk_cost) {
> >
> > if i add && 0 here then i get:
> >
> > --- ./tests/ref/vsynth/vsynth1-qtrlegray    2013-02-21 11:47:19.510165592
> > +0100
> > +++ tests/data/fate/vsynth1-qtrlegray   2013-02-22 02:17:14.399265196 +0100
> > @@ -1,4 +1,4 @@
> > -d010ff7be190f4cd053d79ee7f601ce2 *tests/data/fate/vsynth1-qtrlegray.mov
> > -5113294 tests/data/fate/vsynth1-qtrlegray.mov
> > +603068506cc77726f6cfb79e9575b12f *tests/data/fate/vsynth1-qtrlegray.mov
> > +5113095 tests/data/fate/vsynth1-qtrlegray.mov
> >  29def4aed035ed65d3a89f7d382fccbe
> > *tests/data/fate/vsynth1-qtrlegray.out.rawvideo
> >  stddev:   25.95 PSNR: 19.85 MAXDIFF:  122 bytes:  7603200/  7603200
> > Test vsynth1-qtrlegray failed. Look at
> > tests/data/fate/vsynth1-qtrlegray.err for details.
> > make: *** [fate-vsynth1-qtrlegray] Error 1
> >
> > If i dont misread this then that would be a 200 byte smaller file
> > i did not investigate this further though
> >
> > [...]
> >
> > --
> > Michael     GnuPG fingerprint: 9FF2128B147EF6730BADF133611EC787040B0FAB
> >
> > Dictatorship naturally arises out of democracy, and the most aggravated
> > form of tyranny and slavery out of the most extreme liberty. -- Plato
> >
> > _______________________________________________
> > ffmpeg-devel mailing list
> > ffmpeg-devel at ffmpeg.org
> > http://ffmpeg.org/mailman/listinfo/ffmpeg-devel
> >
> >
> The first two notes I find more readable in the original form, but I've
> changed them to what you requested. the prev variable was purely for
> readability, not speed.
> I've applied the 3rd note as well.

> I'm not entirely sure what you mean by the 4th note. Are you saying there
> is a more optimal file size possible? My intention wasn't to change the
> output at all, merely speed up the existing algorithm.

I dont know, it looked like that random change made the file smaller
i did not investigate why


> So I think that
> should be left for another patch right?

yes, i thought as you already work on this and use the code you might
be interrested in looking into this too


> 
> Updated patch attached.

patch applied

thanks

[...]

-- 
Michael     GnuPG fingerprint: 9FF2128B147EF6730BADF133611EC787040B0FAB

Opposition brings concord. Out of discord comes the fairest harmony.
-- Heraclitus
-------------- next part --------------
A non-text attachment was scrubbed...
Name: not available
Type: application/pgp-signature
Size: 198 bytes
Desc: Digital signature
URL: <http://ffmpeg.org/pipermail/ffmpeg-devel/attachments/20130222/70c5c22b/attachment.asc>