[Ffmpeg-devel] Re: [PATCH] QTRLE encoder

[Michael Niedermayer]

Hi

On Thu, Feb 15, 2007 at 01:23:20AM +0100, Baptiste Coudurier wrote:
> Hi
> 
> Clemens Fruhwirth wrote:
> > Thank you Michael for your very detailed reply. I read all your
> > suggestions and I agree with all of them.
> > 
> > I only infinitesimally favour to see this patch merged in contrast to
> > an unmerged patch. That's why I won't allocate a personal time slice
> > to play the merging game.
> > 
> > Thank you nonetheless as I'm sure this will be a great help for
> > anybody who has this objective.
> 
> Here is an updated patch. Issues should have been adressed, Michael if
> you see more simplification/optimization, I'll do it. 


> I'll add
> regression tests also, if wanted.

yes please do


[...] 
> +    s->max_buf_size=(s->avctx->width*s->avctx->height*s->pixel_size /* image base material */
> +                     + 15                                           /* header + footer */
> +                     + s->avctx->height*2                           /* skip code+rle end */
> +                     + s->avctx->width%MAX_RLE_BULK                 /* rle codes */);

this is wrong, it must be at least width / MAX_RLE_BULK + 1  instead of % 
but even then its too small for the current code, see my example below
either way this is a serious issue, max_buf_size must be set correctly or
we must check that the write index doesnt fall outside the allocated array
we could also simply allocate twice as much which will likely be enough ...


[...]

> +/** Dump line with skip codes */
> +static void dump_line_incremental(QtrleEncContext *s, AVFrame *p, int line, uint8_t **buf)
> +{
> +    uint8_t *this_line = p->data[0]+(line*p->linesize[0]);
> +    uint8_t *prev_line = s->previous_frame.data[0]+(line*p->linesize[0]);
> +    int i=s->avctx->width;
> +
> +    while(i) {
> +        int skip_pix;
> +        int encode_pix;
> +
> +	skip_pix=scan_equal(this_line, prev_line, i, s->pixel_size, 0);
> +        i-=skip_pix;
> +
> +	this_line+=skip_pix*s->pixel_size;
> +        prev_line+=skip_pix*s->pixel_size;
> +
> +	encode_pix=scan_equal(this_line, prev_line, i, s->pixel_size, 1);
> +        i-=encode_pix;
> +
> +        /* Output skip byte */
> +        /* special case optimization: nothing left to encode, hence
> +           choose minimal skip code as does not matter. */
> +        if(i==0 && encode_pix == 0)
> +            generate_skipcodes(buf, 1);
> +        else
> +            generate_skipcodes(buf, skip_pix);
> +
> +	/* Output RLE lines */
> +        encode_rle(s, this_line, buf, encode_pix);
> +
> +        this_line+=encode_pix*s->pixel_size;
> +        prev_line+=encode_pix*s->pixel_size;
> +
> +        bytestream_put_byte(buf, 0);             // RLE code 0: another skip code is coming.
> +    }
> +    (*buf)--;                                  // Remove last incorrect RLE code, announcing a skip code
> +    bytestream_put_byte(buf, -1); // end RLE line
> +}

i think this code is very suboptimal, for example:

prev: 00 01 00 01 00 01 00
cur:  00 00 00 00 00 00 00

this code: 2 1 00 0 2 1 00 0 2 1 00 0 2
sane: 1 -7 00

also the code is quite hard to read, writing half of the next code at the end

maybe something like the following is better, but i didnt think too
deeply about it so maybe ive missed something ...

for(i=0; i<width; i++){
    if(key frame) temp_equal=0;
    else          temp_equal= ...;
    hori_equal= ...;

    if(temp_equal >= hori_equal){
        put 0 unless first byte of line
        encode length (=temp_equal)
        i+= temp_equal
    }else if(hori_equal > 1){
        encode length (=-hori_equal)
        put pixel
        i+= hori_equal
    }else{
        find num of pixels until there are 2 equal horizontal or to the
            previous frame (or 1 equal to the previous frame and following 2
            equal horizontally)
        encode length
        put pixels
        i+= length
    }
}
put -1

this also avoids the dump_line_complete() special case

also note if you want the optimal encoding then this can be done using the
viterbi algorithm but i dont think there is much gain over a carefully
designed heuristic


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

Breaking DRM is a little like attempting to break through a door even
though the window is wide open and the only thing in the house is a bunch
of things you dont want and which you would get tomorrow for free anyway
-------------- next part --------------
A non-text attachment was scrubbed...
Name: not available
Type: application/pgp-signature
Size: 189 bytes
Desc: not available
URL: <http://lists.mplayerhq.hu/pipermail/ffmpeg-devel/attachments/20070217/aa79c070/attachment.pgp>