[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