[FFmpeg-devel] [PATCH] Optimize QTRLE encoding

Michael Niedermayer michaelni at gmx.at
Fri Feb 22 02:22:56 CET 2013


On Wed, Feb 20, 2013 at 04:59:41PM -0500, Malcolm Bechard wrote:
> On Sun, Feb 17, 2013 at 12:06 PM, Malcolm Bechard <malcolm.bechard at gmail.com
> > wrote:
> 
> > > Ok, here's an update with that removed.
> >> >
> >> > Malcolm
> >>
> >> >  qtrleenc.c |   87
> >> ++++++++++++++++++++++++++++++++++++++++++++++---------------
> >> >  1 file changed, 67 insertions(+), 20 deletions(-)
> >> > c88603b1c5e1ec4a7ec66add209069e03c66b662
> >>  0001-Improve-QTRLE-encoding-performance-no-change-to-outp.patch
> >> > From 0af76909ff8bc12264451ad2df74f02df65ab5ce Mon Sep 17 00:00:00 2001
> >> > From: Malcolm Bechard <malcolm.bechard at gmail.com>
> >> > Date: Fri, 15 Feb 2013 10:53:27 -0500
> >> > Subject: [PATCH] Improve QTRLE encoding performance, no change to
> >> output file
> >> >  size/content.
> >> >
> >> > Avoid searching for the lowest bulk cost for each pixel that isn't a
> >> repeat/skip. Instead store the lowest cost as we go along each pixel, and
> >> use it as needed.
> >>
> >> this patch breaks make fate
> >>
> >> --- ./tests/ref/vsynth/vsynth2-qtrle    2013-02-17 13:57:19.199049065+0100
> >> +++ tests/data/fate/vsynth2-qtrle   2013-02-17 17:18:05.771302853 +0100
> >> @@ -1,4 +1,4 @@
> >> -f2aea57de225cccadb936bba4086a836 *tests/data/fate/vsynth2-qtrle.mov
> >> -14798345 tests/data/fate/vsynth2-qtrle.mov
> >> +c63c8c5e96bd0103c8494f0081fde689 *tests/data/fate/vsynth2-qtrle.mov
> >> +14798495 tests/data/fate/vsynth2-qtrle.mov
> >>  98d0e2854731472c5bf13d8638502d0a
> >> *tests/data/fate/vsynth2-qtrle.out.rawvideo
> >>  stddev:    1.26 PSNR: 46.10 MAXDIFF:   13 bytes:  7603200/  7603200
> >>
> >>
> >> [...]
> >> --
> >> Michael     GnuPG fingerprint: 9FF2128B147EF6730BADF133611EC787040B0FAB
> >>
> >> What does censorship reveal? It reveals fear. -- Julian Assange
> >>
> >> _______________________________________________
> >> ffmpeg-devel mailing list
> >> ffmpeg-devel at ffmpeg.org
> >> http://ffmpeg.org/mailman/listinfo/ffmpeg-devel
> >>
> >>
> > I'll get my environment sorted out so I can run make fate and fix this.
> >
> > Malcolm
> >
> 
> Ok this is now fixed, was Integer overflow bug. No change to the
> performance increase. Sorry about that.
> 
> Malcolm

>  qtrleenc.c |   90 ++++++++++++++++++++++++++++++++++++++++++++++---------------
>  1 file changed, 69 insertions(+), 21 deletions(-)
> a0c77b3398ea9358b0fea674ac1adab98f2ae7eb  0001-Improve-QTRLE-encoding-performance-no-change-to-outp.patch
> From bc5c798a7549e9a1a61732263cbaa7c48b0eb741 Mon Sep 17 00:00:00 2001
> From: Malcolm Bechard <malcolm.bechard at gmail.com>
> Date: Wed, 20 Feb 2013 15:50:34 -0500
> Subject: [PATCH] Improve QTRLE encoding performance, no change to output file size/content.
> 
> Avoid searching for the lowest bulk cost for each pixel that isn't a repeat/skip. Instead store the lowest cost as we go along each pixel, and use it as needed.
> 
> Signed-off-by: Malcolm Bechard <malcolm.bechard at gmail.com>
> ---
>  libavcodec/qtrleenc.c |   90 +++++++++++++++++++++++++++++++++++++-----------
>  1 files changed, 69 insertions(+), 21 deletions(-)
> 
> diff --git a/libavcodec/qtrleenc.c b/libavcodec/qtrleenc.c
> index e151c9e..a346d89 100644
> --- a/libavcodec/qtrleenc.c
> +++ b/libavcodec/qtrleenc.c
> @@ -121,8 +121,6 @@ static void qtrle_encode_line(QtrleEncContext *s, const AVFrame *p, int line, ui
>      int i;
>      signed char rlecode;
>  
> -    /* We will use it to compute the best bulk copy sequence */
> -    unsigned int av_uninit(bulkcount);
>      /* This will be the number of pixels equal to the preivous frame one's
>       * starting from the ith pixel */
>      unsigned int skipcount;
> @@ -131,12 +129,14 @@ static void qtrle_encode_line(QtrleEncContext *s, const AVFrame *p, int line, ui
>      unsigned int av_uninit(repeatcount);
>  
>      /* The cost of the three different possibilities */
> -    int total_bulk_cost;
>      int total_skip_cost;
>      int total_repeat_cost;
>  
> -    int temp_cost;
> -    int j;
> +    int base_bulk_cost;
> +    int lowest_bulk_cost;
> +    int lowest_bulk_cost_index;
> +    int sec_lowest_bulk_cost;
> +    int sec_lowest_bulk_cost_index;
>  
>      uint8_t *this_line = p->               data[0] + line*p->               linesize[0] +
>          (width - 1)*s->pixel_size;
> @@ -146,8 +146,64 @@ static void qtrle_encode_line(QtrleEncContext *s, const AVFrame *p, int line, ui
>      s->length_table[width] = 0;
>      skipcount = 0;
>  
> +    /* 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
-------------- 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/fc5a0123/attachment.asc>


More information about the ffmpeg-devel mailing list