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

Anamitra Ghorui aghorui at teknik.io
Sun Mar 1 20:29:06 EET 2020


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

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       }
 };
 
-- 
2.17.1

Thank you



More information about the ffmpeg-devel mailing list