diff mbox series

[FFmpeg-devel,V2,RFC] GSoC: FLIF16 Image format parser

Message ID 6af86c528bc57b914bd407a864349f48@teknik.io
State Superseded
Headers show
Series [FFmpeg-devel,V2,RFC] GSoC: FLIF16 Image format parser
Related show

Checks

Context Check Description
andriy/ffmpeg-patchwork pending
andriy/ffmpeg-patchwork success Applied patch
andriy/ffmpeg-patchwork success Configure finished
andriy/ffmpeg-patchwork warning New warnings during build
andriy/ffmpeg-patchwork success Make finished
andriy/ffmpeg-patchwork success Make fate finished

Commit Message

Anamitra Ghorui March 1, 2020, 6:29 p.m. UTC
Hello,
The parser can now deduce the structure of the format upto the point where the
compressed bitstream actually starts. It also includes functions for handling
the variable integers (varints). The parsing code has not been tested yet and
I'll be doing that later. I am posting this now just to verify whether this is
going in the right direction or not. The comments probably need some cleanup.

On my computer, the reference implementation of FLIF takes a lot of time to both
encode GIFs and view the GIFs, especially large ones. Though I believe that's 
mostly an optimization issue in the case of the viewer.

I still need to go through the reference implementation.

One more thing, from a cursory glance I think that the RAC decoder is going to
require a buffer to handle the lesser significant bytes, and probably will treat
it as such. The job will become much easier if there was a size field for the 
maniac tree. I still haven't really invested time over all of this yet so maybe
I'm wrong.

(I have checked and the following code does build without failure.)
---
 Changelog                  |   1 +
 libavcodec/Makefile        |   1 +
 libavcodec/avcodec.h       |   1 +
 libavcodec/flif16.c        |  97 ++++++++++++++++++++++
 libavcodec/flif16.h        |  89 ++++++++++++++++++++
 libavcodec/flif16_parser.c | 161 +++++++++++++++++++++++++++++++++++++
 libavcodec/parsers.c       |   1 +
 libavformat/img2.c         |   1 +
 8 files changed, 352 insertions(+)
 create mode 100644 libavcodec/flif16.c
 create mode 100644 libavcodec/flif16.h
 create mode 100644 libavcodec/flif16_parser.c

Comments

Nicolas George March 1, 2020, 6:59 p.m. UTC | #1
Anamitra Ghorui (12020-03-01):
> Hello,
> The parser can now deduce the structure of the format upto the point where the
> compressed bitstream actually starts. It also includes functions for handling
> the variable integers (varints). The parsing code has not been tested yet and
> I'll be doing that later. I am posting this now just to verify whether this is
> going in the right direction or not. The comments probably need some cleanup.
> 
> On my computer, the reference implementation of FLIF takes a lot of time to both
> encode GIFs and view the GIFs, especially large ones. Though I believe that's 
> mostly an optimization issue in the case of the viewer.
> 
> I still need to go through the reference implementation.
> 
> One more thing, from a cursory glance I think that the RAC decoder is going to
> require a buffer to handle the lesser significant bytes, and probably will treat
> it as such. The job will become much easier if there was a size field for the 
> maniac tree. I still haven't really invested time over all of this yet so maybe
> I'm wrong.
> 
> (I have checked and the following code does build without failure.)
> ---
>  Changelog                  |   1 +
>  libavcodec/Makefile        |   1 +
>  libavcodec/avcodec.h       |   1 +
>  libavcodec/flif16.c        |  97 ++++++++++++++++++++++
>  libavcodec/flif16.h        |  89 ++++++++++++++++++++
>  libavcodec/flif16_parser.c | 161 +++++++++++++++++++++++++++++++++++++
>  libavcodec/parsers.c       |   1 +
>  libavformat/img2.c         |   1 +
>  8 files changed, 352 insertions(+)
>  create mode 100644 libavcodec/flif16.c
>  create mode 100644 libavcodec/flif16.h
>  create mode 100644 libavcodec/flif16_parser.c

Hi.

See comments below.

> 
> diff --git a/Changelog b/Changelog
> index cb310a3abc..4f88dbaadb 100644
> --- a/Changelog
> +++ b/Changelog
> @@ -43,6 +43,7 @@ version <next>:
>  - Rayman 2 ADPCM decoder
>  - Rayman 2 APM demuxer
>  - cas video filter
> +- FLIF16 decoder
>  
>  
>  version 4.2:
> diff --git a/libavcodec/Makefile b/libavcodec/Makefile
> index f1c032b456..7f08a0c7a4 100644
> --- a/libavcodec/Makefile
> +++ b/libavcodec/Makefile
> @@ -1046,6 +1046,7 @@ OBJS-$(CONFIG_DVD_NAV_PARSER)          += dvd_nav_parser.o
>  OBJS-$(CONFIG_DVDSUB_PARSER)           += dvdsub_parser.o
>  OBJS-$(CONFIG_FLAC_PARSER)             += flac_parser.o flacdata.o flac.o \
>                                            vorbis_data.o
> +OBJS-$(CONFIG_FLIF16_PARSER)           += flif16_parser.o flif16.o
>  OBJS-$(CONFIG_G723_1_PARSER)           += g723_1_parser.o
>  OBJS-$(CONFIG_G729_PARSER)             += g729_parser.o
>  OBJS-$(CONFIG_GIF_PARSER)              += gif_parser.o
> diff --git a/libavcodec/avcodec.h b/libavcodec/avcodec.h
> index 894a9e5565..4e2af45dd0 100644
> --- a/libavcodec/avcodec.h
> +++ b/libavcodec/avcodec.h
> @@ -461,6 +461,7 @@ enum AVCodecID {
>      AV_CODEC_ID_MVDV,
>      AV_CODEC_ID_MVHA,
>      AV_CODEC_ID_CDTOONS,
> +    AV_CODEC_ID_FLIF16,
>  
>      /* various PCM "codecs" */
>      AV_CODEC_ID_FIRST_AUDIO = 0x10000,     ///< A dummy id pointing at the start of audio codecs
> diff --git a/libavcodec/flif16.c b/libavcodec/flif16.c
> new file mode 100644
> index 0000000000..2201951d91
> --- /dev/null
> +++ b/libavcodec/flif16.c
> @@ -0,0 +1,97 @@
> +/*
> + * FLIF16 Component functions
> + * Copyright (c) 2020 Anamitra Ghorui
> + *
> + * This file is part of FFmpeg.
> + *
> + * FFmpeg is free software; you can redistribute it and/or
> + * modify it under the terms of the GNU Lesser General Public
> + * License as published by the Free Software Foundation; either
> + * version 2.1 of the License, or (at your option) any later version.
> + *
> + * FFmpeg is distributed in the hope that it will be useful,
> + * but WITHOUT ANY WARRANTY; without even the implied warranty of
> + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
> + * Lesser General Public License for more details.
> + *
> + * You should have received a copy of the GNU Lesser General Public
> + * License along with FFmpeg; if not, write to the Free Software
> + * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
> + */
> +
> +/* Varints are unsigned integers of variable number of bytes in big endian order.
> + * size. MSB of each byte of the varint is zero except for the last one in
> + * sequence. All the bits aside from the MSB of each byte contribute to the

Is there an upper bound for the size of these integers? In my
experience, varints in multimedia code are used to save a few bits in
the file than to allow very large integers. You could make the code much
simpler if you had an upper bound.

Also, there is probably already similar code, because it is a common
feature.

> + * magnitude of the varint, similar to UTF-8 encoding.

This is not how UTF-8 works.

> + * 
> + * At any point of time, we are only performing 3 operations on varints:
> + * 1. Incrementing a varint
> + * 2. Comparing a varint against another varint, which may be less than or
> + *    equal to the first varint
> + * 3. Reading a varint from a buffer 
> + * 
> + * Hence, these functions should be sufficient.
> + * 
> + * Here, the MSB bit of each segment is always set to 0. That is, value of each
> + * segment can never be greater than 127 decimal.
> + */
> +
> +#include "flif16.h"
> +#include "libavutil/avassert.h"
> +#include "libavutil/mem.h"
> +
> +varint_t *flif16_varint_alloc(unsigned int pad, uint8_t lsbval)
> +{
> +    varint_t *v = av_mallocz(sizeof(varint_t));

When possible, prefer sizeof(*var) to sizeof(type).

> +    if(!v)

Our coding style mandates spaces after if, for, etc.

> +        return v;

return NULL is more idiomatic.

> +    v->buf = av_mallocz(sizeof(uint8_t) * (pad + 1));

sizeof(uint8_t) is guaranteed to be 1 on supported platforms.

Missing malloc check. Better make it:

	v = av_mallocz(sizeof(*v) + pad);

to allocate both at the same time: more efficient.

> +    v->buf[pad] = lsbval & 127;
> +    v->buf_size = pad + 1;
> +    return v;
> +}
> +
> +void flif16_varint_free(varint_t *v)
> +{
> +    av_free(v->buf);
> +    av_free(v);
> +}
> +
> +// May be made faster by providing MSByte as a parameter.
> +unsigned int flif16_varint_inc(varint_t *v)
> +{
> +    unsigned int msb;

> +    av_assert0(v->buf_size);

If speed is a concern, use av_assert1().

> +    msb = v->buf_size - 1;
> +    
> +    for(; msb > 0; --msb) {

> +        if(v->buf[msb] == 127) {
> +            v->buf[msb] = 0;
> +        } else {
> +            ++v->buf[msb];
> +            return msb;
> +        }

Did you test this code for varint { 127, 127, 127 }?

> +    }
> +    
> +    ++v->buf[msb];
> +    return msb;
> +}
> +

> +void flif16_varint_append(varint_t *v, uint8_t vs)
> +{
> +    av_fast_realloc(v->buf, &v->buf_size, v->buf_size + 1);

> +    av_assert0(v->buf);

An assert cannot be used to check for a memory allocation failure.

> +    v->buf[v->buf_size - 1] = vs & 127; 
> +}

Increasing a buffer one by one is inefficient. Please consider doubling
the size.

> +
> +uint8_t flif16_varint_cmp(varint_t *v1, varint_t *v2)
> +{
> +    if(v1->buf_size != v2->buf_size)
> +        return 1;
> +    
> +    for(int i = 0; i < v1->buf_size; ++i)
> +        if(v1->buf[i] != v2->buf[i])
> +            return 1;
> +    
> +    return 0;
> +}
> diff --git a/libavcodec/flif16.h b/libavcodec/flif16.h
> new file mode 100644
> index 0000000000..82daacb032
> --- /dev/null
> +++ b/libavcodec/flif16.h
> @@ -0,0 +1,89 @@
> +/*
> + * FLIF16 Image Format Definitions
> + * Copyright (c) 2020 Anamitra Ghorui
> + *
> + * This file is part of FFmpeg.
> + *
> + * FFmpeg is free software; you can redistribute it and/or
> + * modify it under the terms of the GNU Lesser General Public
> + * License as published by the Free Software Foundation; either
> + * version 2.1 of the License, or (at your option) any later version.
> + *
> + * FFmpeg is distributed in the hope that it will be useful,
> + * but WITHOUT ANY WARRANTY; without even the implied warranty of
> + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
> + * Lesser General Public License for more details.
> + *
> + * You should have received a copy of the GNU Lesser General Public
> + * License along with FFmpeg; if not, write to the Free Software
> + * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
> + */
> +
> +/**
> + * @file
> + * FLIF16 format definitions and functions.
> + */
> +
> +#ifndef AVCODEC_FLIF16_H
> +#define AVCODEC_FLIF16_H
> +
> +#include <stdint.h>
> +#include <stdlib.h>
> +
> +static const uint8_t flif16_header[4] = "FLIF";
> +
> +/* WIP
> +void flif16_read_rac(b, chance);
> +void flif16_read_uni_int();
> +void flif16_read_nz_int();
> +void flif16_read_gnz_int();
> +*/
> +
> +/**
> + * The type of the variable integer (varint) representation used in FLIF.
> + */

> +typedef struct varint_t {
> +    uint8_t *buf;

To avoid the indirection and extra malloc, you can make it
uint8_t buf[1] at the end of the structure.

> +    unsigned int buf_size; // Assuming that no one will try to make an image of
> +                           // dimensions greater than 2^32x2^32

unsigned is enough. Same everywhere.

I suppose size_t would be way overkill for this case.

> +} varint_t;

Names ending in _t are reserved by the C standard. FFmpeg uses types
with capitals and FF prefix for private APIs.

> +
> +/**
> + * Allocates an empty varint.
> + * Note the 'pad' parameter here. This can be used to pad the number with 
> + * preceeding bytes if we already know the number of bytes in the number.
> + * @param pad The number of chars to pad the varint with.
> + * @param lsbval The value to put in the least significant BYTE
> + * @return The pointer to the allocated varint.
> + */

> +varint_t *flif16_varint_alloc(unsigned int pad, uint8_t lsbval);

All global functions are required to have the ff_ prefix (unless they
are public, then avsomething_).

> +
> +/**
> + * Frees a varint
> + * @param v The varint to free.
> + */
> +void flif16_varint_free(varint_t *v);
> +

> +/**
> + * Increments a varint.
> + * @param v The varint to increment.
> + * @return The position of the most significant BYTE starting from 0.This
> + *         can be used to avoid using the comparison function.
> + */
> +unsigned int flif16_varint_inc(varint_t *v);

Please document the API constraint that the buffer must need to be large
enough.

> +
> +/**
> + * Appends a character (a segment of the varint) to the end of the array.
> + * Used to read a varint from a given file.
> + * @param v The varint to add the segment to.
> + * @param vs the segment to add.
> + */
> +void flif16_varint_append(varint_t *v, uint8_t vs);
> +

> +/**
> + * Compare 2 varints.
> + * @return zero if equal, nonzero otherwise.
> + */
> +uint8_t flif16_varint_cmp(varint_t *v1, varint_t *v2);
> +
> +#endif /* AVCODEC_FLIF16_H */
> diff --git a/libavcodec/flif16_parser.c b/libavcodec/flif16_parser.c
> new file mode 100644
> index 0000000000..3012cbf2ad
> --- /dev/null
> +++ b/libavcodec/flif16_parser.c
> @@ -0,0 +1,161 @@
> +/*
> + * FLIF16 parser
> + * Copyright (c) 2020 Anamitra Ghorui
> + *
> + * This file is part of FFmpeg.
> + *
> + * FFmpeg is free software; you can redistribute it and/or
> + * modify it under the terms of the GNU Lesser General Public
> + * License as published by the Free Software Foundation; either
> + * version 2.1 of the License, or (at your option) any later version.
> + *
> + * FFmpeg is distributed in the hope that it will be useful,
> + * but WITHOUT ANY WARRANTY; without even the implied warranty of
> + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
> + * Lesser General Public License for more details.
> + *
> + * You should have received a copy of the GNU Lesser General Public
> + * License along with FFmpeg; if not, write to the Free Software
> + * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
> + */
> +
> + /**
> +  * @file
> +  * FLIF16 parser
> +  */
> +
> +#include "flif16.h"
> +#include "parser.h"
> +#include "libavutil/avassert.h"
> +#include <stdint.h>
> +#include <stdlib.h>
> +
> +typedef enum FLIF16ParseStates {
> +    FLIF16_HEADER = 1,
> +    FLIF16_METADATA,
> +    FLIF16_BITSTREAM,
> +    // FLIF16_TRANSFORM,
> +    FLIF16_PIXELDATA,
> +    FLIF16_CHECKSUM,
> +    FLIF16_VARINT
> +} flif16_states;

We usually name the enum and the corresponding types the same way.

> +
> +typedef struct FLIF16ParseContext {
> +    ParseContext pc;
> +    int state;              ///< The section of the file the parser is in currently.
> +    int index;              ///< An index based on the current state. 
> +    uint8_t iac;            ///< Interlaced, animated, color palette info
> +    uint8_t varint;         ///< number of varints to process in sequence
> +} FLIF16ParseContext;
> +
> +static int flif16_find_frame(FLIF16ParseContext *f, const uint8_t *buf,
> +                             int buf_size)
> +{
> +    int next = END_NOT_FOUND;
> +    int index;
> +    uint8_t metaname[4]; // Not needed.
> +    varint_t *vcur = NULL, *vinc = NULL; // current vint, increment vint
> +    size_t msb;
> +    
> +    for (index = 0; index < buf_size; ++index) {
> +        if(!f->state) {
> +            if(!memcmp(flif16_header, buf + index, 4)) {
> +                f->state = FLIF16_HEADER;
> +            }
> +        } else if (f->state == FLIF16_HEADER) {
> +            if(f->index == 3 + 1) { // Interlaced/animated/color palette info
> +                f->iac = buf[index];
> +            } else if(f->index == 3 + 1 + 1) { // Start - 1 of the first varint
> +                f->varint = 1;
> +            } else if(f->varint) {
> +                if(buf[index] > 127) { // Is MSB zero? (end condition)
> +                    // We will count upto 2 + (1 if animated) varints, then stop
> +                    if(f->varint <= 2 + ((f->iac >> 4) > 4)?1:0) {
> +                        ++f->varint;
> +                    } else {
> +                        f->state = FLIF16_METADATA;
> +                        f->varint = 0;
> +                        f->index = 0;
> +                    }
> +                }
> +            }
> +            ++f->index;
> +        } else if(f->state == FLIF16_METADATA) {
> +            if(f->index == 0) {
> +                // Identifier for the bitstream chunk is a null byte.
> +                if(buf[index] == 0) {
> +                    f->state = FLIF16_BITSTREAM;
> +                }
> +            } else if(f->index == 4) {
> +                // Handle the size varint
> +                vcur = flif16_varint_alloc(0, buf[index]);

> +                av_assert0(vcur);

Same as above, and same below: av_assert0() can only be used for
conditions that can be proven statically.

> +                f->varint = 1;
> +            } else if(f->varint) {
> +                if(buf[index] > 127)
> +                   f->varint = 0;
> +                flif16_varint_append(vcur, buf[index]);
> +            } else if(vinc) {
> +                // increment varint until equal to size
> +                msb = flif16_varint_inc(vinc);
> +                if(!msb) {
> +                    if(flif16_varint_cmp(vcur, vinc)) {
> +                        flif16_varint_free(vcur);
> +                        flif16_varint_free(vinc);
> +                        f->index = 0;
> +                        continue;
> +                    }
> +                }
> +            } else {
> +                if(vcur->buf[vcur->buf_size] > 0) {// Check whether block size > 0 
> +                    vinc = flif16_varint_alloc(vcur->buf_size - 1, 1);
> +                    av_assert0(vinc);
> +                } else {
> +                    f->index = 0;
> +                    continue;
> +                }
> +            }
> +            ++f->index;
> +        } else if(f->state == FLIF16_BITSTREAM) {
> +            /* The real stuff starts here. */
> +            return index; // Currently here for testing purposes.
> +            ++f->index;
> +        } else if(f->state == FLIF16_PIXELDATA) {
> +            /* 
> +             * Total uncompressed size will be equal to:
> +             * nchannels * nframes * nwidth * nheight
> +             */
> +            return index; // Currently here for testing purposes.
> +        }
> +    }
> +    
> +    return next;
> +}
> +

> +static int flif16_parse(AVCodecParserContext *s, AVCodecContext *avctx,
> +                     const uint8_t **poutbuf, int *poutbuf_size,
> +                     const uint8_t *buf, int buf_size)

Alignment is off.

> +{
> +    FLIF16ParseContext *fpc = s->priv_data;
> +    int next;
> +    
> +    next = flif16_find_frame(fpc, buf, buf_size);
> +    
> +    if (ff_combine_frame(&fpc->pc, next, &buf, &buf_size) < 0) {
> +        *poutbuf      = NULL;
> +        *poutbuf_size = 0;
> +        return buf_size;
> +    }
> +
> +    *poutbuf      = buf;
> +    *poutbuf_size = buf_size;
> +    return next;
> +}
> +
> +AVCodecParser ff_flif16_parser = {
> +    .codec_ids      = { AV_CODEC_ID_FLIF16 },
> +    .priv_data_size = sizeof(FLIF16ParseContext),
> +    .parser_parse   = flif16_parse,
> +    .parser_close   = ff_parse_close,
> +};
> +
> diff --git a/libavcodec/parsers.c b/libavcodec/parsers.c
> index 33a71de8a0..8b6eb954b3 100644
> --- a/libavcodec/parsers.c
> +++ b/libavcodec/parsers.c
> @@ -40,6 +40,7 @@ extern AVCodecParser ff_dvbsub_parser;
>  extern AVCodecParser ff_dvdsub_parser;
>  extern AVCodecParser ff_dvd_nav_parser;
>  extern AVCodecParser ff_flac_parser;
> +extern AVCodecParser ff_flif16_parser;
>  extern AVCodecParser ff_g723_1_parser;
>  extern AVCodecParser ff_g729_parser;
>  extern AVCodecParser ff_gif_parser;
> diff --git a/libavformat/img2.c b/libavformat/img2.c
> index 16bc9d2abd..14c11d0c82 100644
> --- a/libavformat/img2.c
> +++ b/libavformat/img2.c
> @@ -81,6 +81,7 @@ const IdStrMap ff_img_tags[] = {
>      { AV_CODEC_ID_XPM,        "xpm"      },
>      { AV_CODEC_ID_XFACE,      "xface"    },
>      { AV_CODEC_ID_XWD,        "xwd"      },
> +    { AV_CODEC_ID_FLIF16,     "flif16"   },
>      { AV_CODEC_ID_NONE,       NULL       }
>  };
>  

Regards,
Anton Khirnov March 2, 2020, 10:06 a.m. UTC | #2
Quoting Nicolas George (2020-03-01 19:59:11)
> 
> > +} varint_t;
> 
> Names ending in _t are reserved by the C standard. FFmpeg uses types
> with capitals and FF prefix for private APIs.

FF prefix is not needed for structs.
Anamitra Ghorui March 2, 2020, 10:51 a.m. UTC | #3
Hello,

> Is there an upper bound for the size of these integers? In my
> experience, varints in multimedia code are used to save a few bits in
> the file than to allow very large integers. You could make the code much
> simpler if you had an upper bound.
> 
> Also, there is probably already similar code, because it is a common
> feature.

According to the specification of the file format, there is no mention of an
upper bound for the integer: https://flif.info/spec.html#_part_1_main_header

 
>> + * magnitude of the varint, similar to UTF-8 encoding.
> 
> This is not how UTF-8 works.

I was talking about it in the context of the 'prefix coding' it uses. UTF-8
uses the MSB bits to indicate how many successive bits aside from the starting
bit are included in a character. The varint does a similar thing in the manner
that it also uses an MSB bit to indicate that a successive bit is included in
the number. Hovever aside from this superficial similarity there is not much
in common.


>> +varint_t *flif16_varint_alloc(unsigned int pad, uint8_t lsbval)
>> +{
>> +    varint_t *v = av_mallocz(sizeof(varint_t));
>
>When possible, prefer sizeof(*var) to sizeof(type).

Okay


>> + if(!v)
> 
> Our coding style mandates spaces after if, for, etc.

Yes. There are several other non-uniformities in the code.


>> + return v;
> 
> return NULL is more idiomatic.

True. I was looking through the AVpacket functions and in the av_packet_alloc
function: https://ffmpeg.org/doxygen/trunk/avpacket_8c_source.html#l00051 (line 51)
there's a similar pattern followed:

    AVPacket *pkt = av_mallocz(sizeof(AVPacket));
    if (!pkt)
        return pkt;

Is there a special reason for this?

 
>> +    v->buf = av_mallocz(sizeof(uint8_t) * (pad + 1));
>
>sizeof(uint8_t) is guaranteed to be 1 on supported platforms.
>
>Missing malloc check. Better make it:
>
>	v = av_mallocz(sizeof(*v) + pad);
>
>to allocate both at the same time: more efficient.

I see. the stucture should therefore be defined with buf after buf_size
(hence putting pad + 1 bytes in contiguous storage but there may be a problem
with the byte padding of the struct), or should buf point to v + sizeof(*v)?
(* See follow-up content below)


>> +    v->buf[pad] = lsbval & 127;
>> +    v->buf_size = pad + 1;
>> +    return v;
>> +}
>> +
>> +void flif16_varint_free(varint_t *v)
>> +{
>> +    av_free(v->buf);
>> +    av_free(v);
>> +}
>> +
>> +// May be made faster by providing MSByte as a parameter.
>> +unsigned int flif16_varint_inc(varint_t *v)
>> +{
>> +    unsigned int msb;
>
>> +    av_assert0(v->buf_size);
>
>If speed is a concern, use av_assert1().

Okay

 
>> +    msb = v->buf_size - 1;
>> +    
>> +    for(; msb > 0; --msb) {
>
>> +        if(v->buf[msb] == 127) {
>> +            v->buf[msb] = 0;
>> +        } else {
>> +            ++v->buf[msb];
>> +            return msb;
>> +        }
>
>Did you test this code for varint { 127, 127, 127 }?

I have tested it separately. In the given code, the function will set the value 
to { 128, 0, 0 }, which is an incorrect representation. But for the puropses of 
the parser and the decoder where we are only concerned with bound checking with 
an existing number, such a situation will never occur. However I can see that 
there will be issues when the encoder will be written since then we will have 
to make the varint and write the varint to a file.


>> +    }
>> +    
>> +    ++v->buf[msb];
>> +    return msb;
>> +}
>> +
>> 
>> +void flif16_varint_append(varint_t *v, uint8_t vs)
>> +{
>> +    av_fast_realloc(v->buf, &v->buf_size, v->buf_size + 1);
>
>> +    av_assert0(v->buf);
>
>An assert cannot be used to check for a memory allocation failure.

I think I have to use av_log then.


>> + v->buf[v->buf_size - 1] = vs & 127;
>> +}
> 
> Increasing a buffer one by one is inefficient. Please consider doubling
> the size.

Should I double the size everytime v->buf_size becomes
equal to the actual number of byte-segments of the varint?


>> +typedef struct varint_t {
>> + uint8_t *buf;
> 
> To avoid the indirection and extra malloc, you can make it
> uint8_t buf[1] at the end of the structure.

If I add it to the end of the struct, the compiler will likely add padding
bits to it, but I don't think its a problem since the padding bits will be set
to zero anyway and therefore can be used in the buffer.


>> + unsigned int buf_size; // Assuming that no one will try to make an image of
>> + // dimensions greater than 2^32x2^32
> 
> unsigned is enough. Same everywhere.
> 
> I suppose size_t would be way overkill for this case.

Ok


>> +} varint_t;
> 
> Names ending in _t are reserved by the C standard. FFmpeg uses types
> with capitals and FF prefix for private APIs.

FLIF16Varint should be fine then?


>> +
>> +/**
>> + * Allocates an empty varint.
>> + * Note the 'pad' parameter here. This can be used to pad the number with 
>> + * preceeding bytes if we already know the number of bytes in the number.
>> + * @param pad The number of chars to pad the varint with.
>> + * @param lsbval The value to put in the least significant BYTE
>> + * @return The pointer to the allocated varint.
>> + */
>
>> +varint_t *flif16_varint_alloc(unsigned int pad, uint8_t lsbval);
>
> All global functions are required to have the ff_ prefix (unless they
> are public, then avsomething_).

Okay


>> +/**
>> + * Increments a varint.
>> + * @param v The varint to increment.
>> + * @return The position of the most significant BYTE starting from 0.This
>> + *         can be used to avoid using the comparison function.
>> + */
>> +unsigned int flif16_varint_inc(varint_t *v);
>
> Please document the API constraint that the buffer must need to be large
> enough.

Okay


>> +typedef enum FLIF16ParseStates {
>> +    FLIF16_HEADER = 1,
>> +    FLIF16_METADATA,
>> +    FLIF16_BITSTREAM,
>> +    // FLIF16_TRANSFORM,
>> +    FLIF16_PIXELDATA,
>> +    FLIF16_CHECKSUM,
>> +    FLIF16_VARINT
>> +} flif16_states;
>
> We usually name the enum and the corresponding types the same way.

I had modelled most of the code after the GIF parser, and it names the enum
values in the same manner:
https://ffmpeg.org/doxygen/trunk/gif__parser_8c_source.html
I will probably prefix them with 'FLIF16_STATE_' then.


>> +            } else if(f->index == 4) {
>> +                // Handle the size varint
>> +                vcur = flif16_varint_alloc(0, buf[index]);
>
>> +                av_assert0(vcur);
>
> Same as above, and same below: av_assert0() can only be used for
> conditions that can be proven statically.

Ok

>> +static int flif16_parse(AVCodecParserContext *s, AVCodecContext *avctx,
>> +                     const uint8_t **poutbuf, int *poutbuf_size,
>> +                     const uint8_t *buf, int buf_size)
>
> Alignment is off.

I'll fix it (If you were talking about the textual alignment).

> 
> Regards,
> 
> --
> Nicolas George

Thanks.
Nicolas George March 2, 2020, 7:58 p.m. UTC | #4
Anamitra Ghorui (12020-03-02):
> According to the specification of the file format, there is no mention of an
> upper bound for the integer: https://flif.info/spec.html#_part_1_main_header

But they are mapped to FFmpeg values: width and height are ints, frame
counts are uint64_t at best. Therefore, I think you should drop the
varint_t structure entirely, and just read varints into uint64_t,
returning an error (INVALIDDATA) if it exceeds.

> >> + * magnitude of the varint, similar to UTF-8 encoding.
> > This is not how UTF-8 works.
> I was talking about it in the context of the 'prefix coding' it uses. UTF-8
> uses the MSB bits to indicate how many successive bits aside from the starting
> bit are included in a character. The varint does a similar thing in the manner
> that it also uses an MSB bit to indicate that a successive bit is included in
> the number. Hovever aside from this superficial similarity there is not much
> in common.

I'd prefer if there is no mention of UTF-8 rather than a misleading one.
Actually, this particular coding of integers seems quite common, it must
have a name.

>     AVPacket *pkt = av_mallocz(sizeof(AVPacket));
>     if (!pkt)
>         return pkt;
> 
> Is there a special reason for this?

I don't think so.

> I see. the stucture should therefore be defined with buf after buf_size
> (hence putting pad + 1 bytes in contiguous storage but there may be a problem
> with the byte padding of the struct), or should buf point to v + sizeof(*v)?
> (* See follow-up content below)

See below.

> I have tested it separately. In the given code, the function will set the value 
> to { 128, 0, 0 }, which is an incorrect representation. But for the puropses of 
> the parser and the decoder where we are only concerned with bound checking with 
> an existing number, such a situation will never occur. However I can see that 
> there will be issues when the encoder will be written since then we will have 
> to make the varint and write the varint to a file.

Either fix the function to make it work correctly, or document that it
has an unusual behavior.

> >An assert cannot be used to check for a memory allocation failure.
> I think I have to use av_log then.

No, not av_log() either, because it does not prevent the code from
continuing and dereferencing NULL (the asserts do, unless they are
disabled at build time). You need to add an error return, and return
AVERROR(ENOMEM).

> Should I double the size everytime v->buf_size becomes
> equal to the actual number of byte-segments of the varint?

Double the size every time you need to increase it, every time what you
need to put in the buffer does not fit.

> If I add it to the end of the struct, the compiler will likely add padding
> bits to it, but I don't think its a problem since the padding bits will be set
> to zero anyway and therefore can be used in the buffer.

Exactly. You could even make a sizeof() expression to avoid allocating
bytes if there is already room enough in the padding. It is quite a
common pattern. Modern C even allows 0-sized arrays at the end of
structs to make it more elegant, but we don't use it in FFmpeg.

Note: all these considerations about allocation, incrementation, etc.,
would be moot if you decide, as I think you should, to just drop
varint_t and use a large enough integer instead.


> FLIF16Varint should be fine then?

I think so; as Anton points, the FF prefix is not mandatory for
structures, only the ff_ prefix for functions.

> >> +typedef enum FLIF16ParseStates {
> >> +    FLIF16_HEADER = 1,
> >> +    FLIF16_METADATA,
> >> +    FLIF16_BITSTREAM,
> >> +    // FLIF16_TRANSFORM,
> >> +    FLIF16_PIXELDATA,
> >> +    FLIF16_CHECKSUM,
> >> +    FLIF16_VARINT
> >> +} flif16_states;
> > We usually name the enum and the corresponding types the same way.
> I had modelled most of the code after the GIF parser, and it names the enum
> values in the same manner:
> https://ffmpeg.org/doxygen/trunk/gif__parser_8c_source.html
> I will probably prefix them with 'FLIF16_STATE_' then.

The name of the values are fine. I meant the name of the enum itself,
FLIF16ParseStates compared to the name of the type, flif16_states.

By the way, the name of enums is usually singular.

Regards,
diff mbox series

Patch

diff --git a/Changelog b/Changelog
index cb310a3abc..4f88dbaadb 100644
--- a/Changelog
+++ b/Changelog
@@ -43,6 +43,7 @@  version <next>:
 - Rayman 2 ADPCM decoder
 - Rayman 2 APM demuxer
 - cas video filter
+- FLIF16 decoder
 
 
 version 4.2:
diff --git a/libavcodec/Makefile b/libavcodec/Makefile
index f1c032b456..7f08a0c7a4 100644
--- a/libavcodec/Makefile
+++ b/libavcodec/Makefile
@@ -1046,6 +1046,7 @@  OBJS-$(CONFIG_DVD_NAV_PARSER)          += dvd_nav_parser.o
 OBJS-$(CONFIG_DVDSUB_PARSER)           += dvdsub_parser.o
 OBJS-$(CONFIG_FLAC_PARSER)             += flac_parser.o flacdata.o flac.o \
                                           vorbis_data.o
+OBJS-$(CONFIG_FLIF16_PARSER)           += flif16_parser.o flif16.o
 OBJS-$(CONFIG_G723_1_PARSER)           += g723_1_parser.o
 OBJS-$(CONFIG_G729_PARSER)             += g729_parser.o
 OBJS-$(CONFIG_GIF_PARSER)              += gif_parser.o
diff --git a/libavcodec/avcodec.h b/libavcodec/avcodec.h
index 894a9e5565..4e2af45dd0 100644
--- a/libavcodec/avcodec.h
+++ b/libavcodec/avcodec.h
@@ -461,6 +461,7 @@  enum AVCodecID {
     AV_CODEC_ID_MVDV,
     AV_CODEC_ID_MVHA,
     AV_CODEC_ID_CDTOONS,
+    AV_CODEC_ID_FLIF16,
 
     /* various PCM "codecs" */
     AV_CODEC_ID_FIRST_AUDIO = 0x10000,     ///< A dummy id pointing at the start of audio codecs
diff --git a/libavcodec/flif16.c b/libavcodec/flif16.c
new file mode 100644
index 0000000000..2201951d91
--- /dev/null
+++ b/libavcodec/flif16.c
@@ -0,0 +1,97 @@ 
+/*
+ * FLIF16 Component functions
+ * Copyright (c) 2020 Anamitra Ghorui
+ *
+ * This file is part of FFmpeg.
+ *
+ * FFmpeg is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU Lesser General Public
+ * License as published by the Free Software Foundation; either
+ * version 2.1 of the License, or (at your option) any later version.
+ *
+ * FFmpeg is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
+ * Lesser General Public License for more details.
+ *
+ * You should have received a copy of the GNU Lesser General Public
+ * License along with FFmpeg; if not, write to the Free Software
+ * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
+ */
+
+/* Varints are unsigned integers of variable number of bytes in big endian order.
+ * size. MSB of each byte of the varint is zero except for the last one in
+ * sequence. All the bits aside from the MSB of each byte contribute to the
+ * magnitude of the varint, similar to UTF-8 encoding.
+ * 
+ * At any point of time, we are only performing 3 operations on varints:
+ * 1. Incrementing a varint
+ * 2. Comparing a varint against another varint, which may be less than or
+ *    equal to the first varint
+ * 3. Reading a varint from a buffer 
+ * 
+ * Hence, these functions should be sufficient.
+ * 
+ * Here, the MSB bit of each segment is always set to 0. That is, value of each
+ * segment can never be greater than 127 decimal.
+ */
+
+#include "flif16.h"
+#include "libavutil/avassert.h"
+#include "libavutil/mem.h"
+
+varint_t *flif16_varint_alloc(unsigned int pad, uint8_t lsbval)
+{
+    varint_t *v = av_mallocz(sizeof(varint_t));
+    if(!v)
+        return v;
+    v->buf = av_mallocz(sizeof(uint8_t) * (pad + 1));
+    v->buf[pad] = lsbval & 127;
+    v->buf_size = pad + 1;
+    return v;
+}
+
+void flif16_varint_free(varint_t *v)
+{
+    av_free(v->buf);
+    av_free(v);
+}
+
+// May be made faster by providing MSByte as a parameter.
+unsigned int flif16_varint_inc(varint_t *v)
+{
+    unsigned int msb;
+    av_assert0(v->buf_size);
+    msb = v->buf_size - 1;
+    
+    for(; msb > 0; --msb) {
+        if(v->buf[msb] == 127) {
+            v->buf[msb] = 0;
+        } else {
+            ++v->buf[msb];
+            return msb;
+        }
+    }
+    
+    ++v->buf[msb];
+    return msb;
+}
+
+void flif16_varint_append(varint_t *v, uint8_t vs)
+{
+    av_fast_realloc(v->buf, &v->buf_size, v->buf_size + 1);
+    av_assert0(v->buf);
+    v->buf[v->buf_size - 1] = vs & 127; 
+}
+
+uint8_t flif16_varint_cmp(varint_t *v1, varint_t *v2)
+{
+    if(v1->buf_size != v2->buf_size)
+        return 1;
+    
+    for(int i = 0; i < v1->buf_size; ++i)
+        if(v1->buf[i] != v2->buf[i])
+            return 1;
+    
+    return 0;
+}
diff --git a/libavcodec/flif16.h b/libavcodec/flif16.h
new file mode 100644
index 0000000000..82daacb032
--- /dev/null
+++ b/libavcodec/flif16.h
@@ -0,0 +1,89 @@ 
+/*
+ * FLIF16 Image Format Definitions
+ * Copyright (c) 2020 Anamitra Ghorui
+ *
+ * This file is part of FFmpeg.
+ *
+ * FFmpeg is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU Lesser General Public
+ * License as published by the Free Software Foundation; either
+ * version 2.1 of the License, or (at your option) any later version.
+ *
+ * FFmpeg is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
+ * Lesser General Public License for more details.
+ *
+ * You should have received a copy of the GNU Lesser General Public
+ * License along with FFmpeg; if not, write to the Free Software
+ * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
+ */
+
+/**
+ * @file
+ * FLIF16 format definitions and functions.
+ */
+
+#ifndef AVCODEC_FLIF16_H
+#define AVCODEC_FLIF16_H
+
+#include <stdint.h>
+#include <stdlib.h>
+
+static const uint8_t flif16_header[4] = "FLIF";
+
+/* WIP
+void flif16_read_rac(b, chance);
+void flif16_read_uni_int();
+void flif16_read_nz_int();
+void flif16_read_gnz_int();
+*/
+
+/**
+ * The type of the variable integer (varint) representation used in FLIF.
+ */
+typedef struct varint_t {
+    uint8_t *buf;
+    unsigned int buf_size; // Assuming that no one will try to make an image of
+                           // dimensions greater than 2^32x2^32
+} varint_t;
+
+/**
+ * Allocates an empty varint.
+ * Note the 'pad' parameter here. This can be used to pad the number with 
+ * preceeding bytes if we already know the number of bytes in the number.
+ * @param pad The number of chars to pad the varint with.
+ * @param lsbval The value to put in the least significant BYTE
+ * @return The pointer to the allocated varint.
+ */
+varint_t *flif16_varint_alloc(unsigned int pad, uint8_t lsbval);
+
+/**
+ * Frees a varint
+ * @param v The varint to free.
+ */
+void flif16_varint_free(varint_t *v);
+
+/**
+ * Increments a varint.
+ * @param v The varint to increment.
+ * @return The position of the most significant BYTE starting from 0.This
+ *         can be used to avoid using the comparison function.
+ */
+unsigned int flif16_varint_inc(varint_t *v);
+
+/**
+ * Appends a character (a segment of the varint) to the end of the array.
+ * Used to read a varint from a given file.
+ * @param v The varint to add the segment to.
+ * @param vs the segment to add.
+ */
+void flif16_varint_append(varint_t *v, uint8_t vs);
+
+/**
+ * Compare 2 varints.
+ * @return zero if equal, nonzero otherwise.
+ */
+uint8_t flif16_varint_cmp(varint_t *v1, varint_t *v2);
+
+#endif /* AVCODEC_FLIF16_H */
diff --git a/libavcodec/flif16_parser.c b/libavcodec/flif16_parser.c
new file mode 100644
index 0000000000..3012cbf2ad
--- /dev/null
+++ b/libavcodec/flif16_parser.c
@@ -0,0 +1,161 @@ 
+/*
+ * FLIF16 parser
+ * Copyright (c) 2020 Anamitra Ghorui
+ *
+ * This file is part of FFmpeg.
+ *
+ * FFmpeg is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU Lesser General Public
+ * License as published by the Free Software Foundation; either
+ * version 2.1 of the License, or (at your option) any later version.
+ *
+ * FFmpeg is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
+ * Lesser General Public License for more details.
+ *
+ * You should have received a copy of the GNU Lesser General Public
+ * License along with FFmpeg; if not, write to the Free Software
+ * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
+ */
+
+ /**
+  * @file
+  * FLIF16 parser
+  */
+
+#include "flif16.h"
+#include "parser.h"
+#include "libavutil/avassert.h"
+#include <stdint.h>
+#include <stdlib.h>
+
+typedef enum FLIF16ParseStates {
+    FLIF16_HEADER = 1,
+    FLIF16_METADATA,
+    FLIF16_BITSTREAM,
+    // FLIF16_TRANSFORM,
+    FLIF16_PIXELDATA,
+    FLIF16_CHECKSUM,
+    FLIF16_VARINT
+} flif16_states;
+
+typedef struct FLIF16ParseContext {
+    ParseContext pc;
+    int state;              ///< The section of the file the parser is in currently.
+    int index;              ///< An index based on the current state. 
+    uint8_t iac;            ///< Interlaced, animated, color palette info
+    uint8_t varint;         ///< number of varints to process in sequence
+} FLIF16ParseContext;
+
+static int flif16_find_frame(FLIF16ParseContext *f, const uint8_t *buf,
+                             int buf_size)
+{
+    int next = END_NOT_FOUND;
+    int index;
+    uint8_t metaname[4]; // Not needed.
+    varint_t *vcur = NULL, *vinc = NULL; // current vint, increment vint
+    size_t msb;
+    
+    for (index = 0; index < buf_size; ++index) {
+        if(!f->state) {
+            if(!memcmp(flif16_header, buf + index, 4)) {
+                f->state = FLIF16_HEADER;
+            }
+        } else if (f->state == FLIF16_HEADER) {
+            if(f->index == 3 + 1) { // Interlaced/animated/color palette info
+                f->iac = buf[index];
+            } else if(f->index == 3 + 1 + 1) { // Start - 1 of the first varint
+                f->varint = 1;
+            } else if(f->varint) {
+                if(buf[index] > 127) { // Is MSB zero? (end condition)
+                    // We will count upto 2 + (1 if animated) varints, then stop
+                    if(f->varint <= 2 + ((f->iac >> 4) > 4)?1:0) {
+                        ++f->varint;
+                    } else {
+                        f->state = FLIF16_METADATA;
+                        f->varint = 0;
+                        f->index = 0;
+                    }
+                }
+            }
+            ++f->index;
+        } else if(f->state == FLIF16_METADATA) {
+            if(f->index == 0) {
+                // Identifier for the bitstream chunk is a null byte.
+                if(buf[index] == 0) {
+                    f->state = FLIF16_BITSTREAM;
+                }
+            } else if(f->index == 4) {
+                // Handle the size varint
+                vcur = flif16_varint_alloc(0, buf[index]);
+                av_assert0(vcur);
+                f->varint = 1;
+            } else if(f->varint) {
+                if(buf[index] > 127)
+                   f->varint = 0;
+                flif16_varint_append(vcur, buf[index]);
+            } else if(vinc) {
+                // increment varint until equal to size
+                msb = flif16_varint_inc(vinc);
+                if(!msb) {
+                    if(flif16_varint_cmp(vcur, vinc)) {
+                        flif16_varint_free(vcur);
+                        flif16_varint_free(vinc);
+                        f->index = 0;
+                        continue;
+                    }
+                }
+            } else {
+                if(vcur->buf[vcur->buf_size] > 0) {// Check whether block size > 0 
+                    vinc = flif16_varint_alloc(vcur->buf_size - 1, 1);
+                    av_assert0(vinc);
+                } else {
+                    f->index = 0;
+                    continue;
+                }
+            }
+            ++f->index;
+        } else if(f->state == FLIF16_BITSTREAM) {
+            /* The real stuff starts here. */
+            return index; // Currently here for testing purposes.
+            ++f->index;
+        } else if(f->state == FLIF16_PIXELDATA) {
+            /* 
+             * Total uncompressed size will be equal to:
+             * nchannels * nframes * nwidth * nheight
+             */
+            return index; // Currently here for testing purposes.
+        }
+    }
+    
+    return next;
+}
+
+static int flif16_parse(AVCodecParserContext *s, AVCodecContext *avctx,
+                     const uint8_t **poutbuf, int *poutbuf_size,
+                     const uint8_t *buf, int buf_size)
+{
+    FLIF16ParseContext *fpc = s->priv_data;
+    int next;
+    
+    next = flif16_find_frame(fpc, buf, buf_size);
+    
+    if (ff_combine_frame(&fpc->pc, next, &buf, &buf_size) < 0) {
+        *poutbuf      = NULL;
+        *poutbuf_size = 0;
+        return buf_size;
+    }
+
+    *poutbuf      = buf;
+    *poutbuf_size = buf_size;
+    return next;
+}
+
+AVCodecParser ff_flif16_parser = {
+    .codec_ids      = { AV_CODEC_ID_FLIF16 },
+    .priv_data_size = sizeof(FLIF16ParseContext),
+    .parser_parse   = flif16_parse,
+    .parser_close   = ff_parse_close,
+};
+
diff --git a/libavcodec/parsers.c b/libavcodec/parsers.c
index 33a71de8a0..8b6eb954b3 100644
--- a/libavcodec/parsers.c
+++ b/libavcodec/parsers.c
@@ -40,6 +40,7 @@  extern AVCodecParser ff_dvbsub_parser;
 extern AVCodecParser ff_dvdsub_parser;
 extern AVCodecParser ff_dvd_nav_parser;
 extern AVCodecParser ff_flac_parser;
+extern AVCodecParser ff_flif16_parser;
 extern AVCodecParser ff_g723_1_parser;
 extern AVCodecParser ff_g729_parser;
 extern AVCodecParser ff_gif_parser;
diff --git a/libavformat/img2.c b/libavformat/img2.c
index 16bc9d2abd..14c11d0c82 100644
--- a/libavformat/img2.c
+++ b/libavformat/img2.c
@@ -81,6 +81,7 @@  const IdStrMap ff_img_tags[] = {
     { AV_CODEC_ID_XPM,        "xpm"      },
     { AV_CODEC_ID_XFACE,      "xface"    },
     { AV_CODEC_ID_XWD,        "xwd"      },
+    { AV_CODEC_ID_FLIF16,     "flif16"   },
     { AV_CODEC_ID_NONE,       NULL       }
 };