[FFmpeg-devel] [PATCH 2/2 v2] avcodec/gifenc: Only write frame palette entries that actually used

[Andreas Rheinhardt]

Derek Buitenhuis:
> GIF palette entries are not compressed, and writing 256 entries,
> which can be up to every frame, uses a significant amount of
> space, especially in extreme cases, where palettes can be very
> small.
> 
> Example, first six seconds of Tears of Steel, palette generated
> with libimagequant, 320x240 resolution, and with transparency
> optimization + per frame palette:
> 
>     * Before patch: 186765 bytes
>     * After patch: 77895 bytes
> 
> Signed-off-by: Derek Buitenhuis <derek.buitenhuis at gmail.com>
> ---
> The global palette, if used, is no longer ever shrunk in v2 of this
> patch. This is because just because any given frame doesn't reference
> an index, doesn't mean a future frame won't.
> ---
>  libavcodec/gif.c | 72 ++++++++++++++++++++++++++++++++++++++++++++++--
>  1 file changed, 69 insertions(+), 3 deletions(-)
> 
> diff --git a/libavcodec/gif.c b/libavcodec/gif.c
> index 8c07ee2769..420a1f523e 100644
> --- a/libavcodec/gif.c
> +++ b/libavcodec/gif.c
> @@ -63,6 +63,44 @@ enum {
>      GF_TRANSDIFF  = 1<<1,
>  };
>  
> +static void shrink_palette(const uint32_t *src, uint8_t *map,
> +                           uint32_t *dst, size_t *palette_count)
> +{
> +    size_t colors_seen = 0;
> +
> +    for (size_t i = 0; i < AVPALETTE_COUNT; i++) {
> +        int seen = 0;
> +        for (size_t c = 0; c < colors_seen; c++) {
> +            if (src[i] == dst[c]) {
> +                seen = 1;
> +                break;
> +            }
> +        }
> +        if (!seen) {
> +            dst[colors_seen] = src[i];
> +            map[i] = colors_seen;
> +            colors_seen++;
> +        }
> +    }
> +
> +    *palette_count = colors_seen;
> +}
> +
> +static void remap_frame_to_palette(const uint8_t *src, int src_linesize,
> +                                   uint8_t *dst, int dst_linesize,
> +                                   int w, int h, uint8_t *map)
> +{
> +    uint8_t *sptr = (uint8_t *) src;

Casting const away here is completely unnecessary as sptr is not used to
modify what it points to; and actually sptr and dptr are completely
unnecessary, too.

> +    uint8_t *dptr = dst;
> +
> +    for (int i = 0; i < h; i++) {
> +        for (int j = 0; j < w; j++)
> +            dptr[j] = map[sptr[j]];
> +        dptr += dst_linesize;
> +        sptr += src_linesize;
> +    }
> +}
> +
>  static int is_image_translucent(AVCodecContext *avctx,
>                                  const uint8_t *buf, const int linesize)
>  {
> @@ -267,6 +305,18 @@ static int gif_image_write_image(AVCodecContext *avctx,
>      int x_start = 0, y_start = 0, trans = s->transparent_index;
>      int bcid = -1, honor_transparency = (s->flags & GF_TRANSDIFF) && s->last_frame && !palette;
>      const uint8_t *ptr;
> +    uint32_t shrunk_palette[AVPALETTE_COUNT];
> +    uint8_t map[AVPALETTE_COUNT] = { 0 };
> +    size_t shrunk_palette_count = 0;
> +    uint8_t *shrunk_buf = NULL;
> +
> +    /*
> +     * We memset to 0xff instead of 0x00 so that the transparency detection
> +     * doesn't pick anything after the palette entries as the transparency
> +     * index, and because GIF89a requires us to always write a power-of-2
> +     * number of palette entries.
> +     */
> +    memset(shrunk_palette, 0xff, AVPALETTE_SIZE);
>  
>      if (!s->image && is_image_translucent(avctx, buf, linesize)) {
>          gif_crop_translucent(avctx, buf, linesize, &width, &height, &x_start, &y_start);
> @@ -335,9 +385,14 @@ static int gif_image_write_image(AVCodecContext *avctx,
>  
>      if (palette || !s->use_global_palette) {
>          const uint32_t *pal = palette ? palette : s->palette;
> +        unsigned pow2_count;
>          unsigned i;
> -        bytestream_put_byte(bytestream, 1<<7 | 0x7); /* flags */
> -        for (i = 0; i < AVPALETTE_COUNT; i++) {
> +
> +        shrink_palette(pal, map, shrunk_palette, &shrunk_palette_count);
> +        pow2_count = av_log2(shrunk_palette_count - 1);
> +
> +        bytestream_put_byte(bytestream, 1<<7 | pow2_count); /* flags */
> +        for (i = 0; i < 1 << (pow2_count + 1); i++) {
>              const uint32_t v = pal[i];
>              bytestream_put_be24(bytestream, v);
>          }
> @@ -350,7 +405,17 @@ static int gif_image_write_image(AVCodecContext *avctx,
>      ff_lzw_encode_init(s->lzw, s->buf, s->buf_size,
>                         12, FF_LZW_GIF, 1);
>  
> -    ptr = buf + y_start*linesize + x_start;
> +    if (shrunk_palette_count) {
> +        shrunk_buf = av_malloc(avctx->height * linesize);
> +        if (!shrunk_buf) {
> +            av_log(avctx, AV_LOG_ERROR, "Could not allocated remapped frame buffer.\n");
> +            return AVERROR(ENOMEM);
> +        }
> +        remap_frame_to_palette(buf, linesize, shrunk_buf, linesize, avctx->width, avctx->height, map);
> +        ptr = shrunk_buf + y_start*linesize + x_start;
> +    } else {
> +        ptr = buf + y_start*linesize + x_start;
> +    }
>      if (honor_transparency) {
>          const int ref_linesize = s->last_frame->linesize[0];
>          const uint8_t *ref = s->last_frame->data[0] + y_start*ref_linesize + x_start;
> @@ -383,6 +448,7 @@ static int gif_image_write_image(AVCodecContext *avctx,
>          len -= size;
>      }
>      bytestream_put_byte(bytestream, 0x00); /* end of image block */
> +    av_freep(&shrunk_buf);
>      return 0;
>  }
>  
>