From patchwork Thu Feb 4 16:50:16 2021 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Derek Buitenhuis X-Patchwork-Id: 25392 Return-Path: X-Original-To: patchwork@ffaux-bg.ffmpeg.org Delivered-To: patchwork@ffaux-bg.ffmpeg.org Received: from ffbox0-bg.mplayerhq.hu (ffbox0-bg.ffmpeg.org [79.124.17.100]) by ffaux.localdomain (Postfix) with ESMTP id 9938644ADE2 for ; Thu, 4 Feb 2021 18:56:43 +0200 (EET) Received: from [127.0.1.1] (localhost [127.0.0.1]) by ffbox0-bg.mplayerhq.hu (Postfix) with ESMTP id 6AB07689A12; Thu, 4 Feb 2021 18:56:43 +0200 (EET) X-Original-To: ffmpeg-devel@ffmpeg.org Delivered-To: ffmpeg-devel@ffmpeg.org Received: from mail-wr1-f50.google.com (mail-wr1-f50.google.com [209.85.221.50]) by ffbox0-bg.mplayerhq.hu (Postfix) with ESMTPS id 605AD68804B for ; Thu, 4 Feb 2021 18:56:36 +0200 (EET) Received: by mail-wr1-f50.google.com with SMTP id q7so4289395wre.13 for ; Thu, 04 Feb 2021 08:56:36 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20161025; h=from:to:subject:date:message-id:mime-version :content-transfer-encoding; bh=I8p+yX1DG12/P9Scby/usG9tJGTzzh4UeXXtIAuEYVU=; b=RIoCzz1Q7W9aFFUnFT//13bOs55Y5ICNQLCza9qS2HC51+mCN8sAbUTG/HpTye2uzq LPydJyY+S9/4J3Pbgo8sNJs0j9HfMif/SwZXupN3HC+EydgvblS4r6tZv9j1TBzzQZb0 hqNQ4mm4koZm/EB3FB6bN+o0xaVaEpoI/QoqrR9zS92bKvvn4rDKGWwW3gEvMAzwaTIW tPzAkhd64tZtxrcUyDoJ7XFN6oyVPuNKYa7DNa+HCiRuChj7ilY7Nq96RJuu5CnTvFJd Pzx4KVlNArWd9il/J1uaN4O/MCt2je5l1TsaN5h1BFfDvc3UwgGaeFpIuXsnJgtLRazg L15w== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:from:to:subject:date:message-id:mime-version :content-transfer-encoding; bh=I8p+yX1DG12/P9Scby/usG9tJGTzzh4UeXXtIAuEYVU=; b=YyMUvy695IMZPa2d+Auh0fqP/wJe+2fbpJnkwfX0bDL2qvq4gYQhzh1fxpwufVkBQ4 /ubzpNIIRByg19GgCi1TtXatwukWej4lzjHPf93cXi8vfZXJH+3A+ID/C1b0aLjJH2el N+LBCytzpC8FAmCAw3kcxCjbM/9XyM1hQxTajiX6kSMqbN4Sj1Z4mvAAgboW4nwy8Dzb jazeh53YniuBuf+JKUusRdT01+AoU3oJlvdGxg+UmwTZbiFzWj7KL2CHkDDmAMzjTBRu AjfL03Zi0okuw9Guy6O0z5fFnQW1IG7gTIqKjElIVl2ppJq63P3r/S1OjcXdjQEz/ASv IgYQ== X-Gm-Message-State: AOAM531AsBPmfG2ePnEkpoLpSxVKKyNeacZJeSL33RDNggi1a5syW7N3 JUuhcPypAiX96/5NHqVxfcnbOt8Q/6o= X-Google-Smtp-Source: ABdhPJzn3vSvqq+gJ+RwSZtS4ZnyT934WtGwW6YwFqd9gQo5s4hx4MDtTn4l3Hd1tH1JQHfqMLpbsQ== X-Received: by 2002:a5d:4ccb:: with SMTP id c11mr248235wrt.324.1612457427149; Thu, 04 Feb 2021 08:50:27 -0800 (PST) Received: from localhost.localdomain ([82.129.110.36]) by smtp.gmail.com with ESMTPSA id r25sm9423201wrr.64.2021.02.04.08.50.25 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Thu, 04 Feb 2021 08:50:26 -0800 (PST) From: Derek Buitenhuis To: ffmpeg-devel@ffmpeg.org Date: Thu, 4 Feb 2021 16:50:16 +0000 Message-Id: <20210204165016.1028474-1-derek.buitenhuis@gmail.com> X-Mailer: git-send-email 2.30.0 MIME-Version: 1.0 Subject: [FFmpeg-devel] [PATCH] libavcodec/gifenc: Only write palette entries that actually used X-BeenThere: ffmpeg-devel@ffmpeg.org X-Mailman-Version: 2.1.20 Precedence: list List-Id: FFmpeg development discussions and patches List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Reply-To: FFmpeg development discussions and patches Errors-To: ffmpeg-devel-bounces@ffmpeg.org Sender: "ffmpeg-devel" 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: 77901 bytes Signed-off-by: Derek Buitenhuis --- libavcodec/gif.c | 81 +++++++++++++++++++++++++++++++++++++++++------- 1 file changed, 69 insertions(+), 12 deletions(-) diff --git a/libavcodec/gif.c b/libavcodec/gif.c index de41992851..c52db57edd 100644 --- a/libavcodec/gif.c +++ b/libavcodec/gif.c @@ -52,6 +52,7 @@ typedef struct GIFContext { int flags; int image; uint32_t palette[AVPALETTE_COUNT]; ///< local reference palette for !pal8 + size_t palette_count; int palette_loaded; int transparent_index; uint8_t *tmpl; ///< temporary line buffer @@ -62,6 +63,27 @@ enum { GF_TRANSDIFF = 1<<1, }; +static void shrink_palette(const uint32_t *src, 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]; + colors_seen++; + } + } + + *palette_count = colors_seen; +} + static int is_image_translucent(AVCodecContext *avctx, const uint8_t *buf, const int linesize) { @@ -83,7 +105,7 @@ static int is_image_translucent(AVCodecContext *avctx, return 0; } -static int get_palette_transparency_index(const uint32_t *palette) +static int get_palette_transparency_index(const uint32_t *palette, int palette_count) { int transparent_color_index = -1; unsigned i, smallest_alpha = 0xff; @@ -91,7 +113,7 @@ static int get_palette_transparency_index(const uint32_t *palette) if (!palette) return -1; - for (i = 0; i < AVPALETTE_COUNT; i++) { + for (i = 0; i < palette_count; i++) { const uint32_t v = palette[i]; if (v >> 24 < smallest_alpha) { smallest_alpha = v >> 24; @@ -266,6 +288,10 @@ 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] = { 0 }; + size_t shrunk_palette_count; + + 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); @@ -277,10 +303,21 @@ static int gif_image_write_image(AVCodecContext *avctx, } if (s->image || !avctx->frame_number) { /* GIF header */ - const uint32_t *global_palette = palette ? palette : s->palette; + uint32_t *global_palette; + uint32_t shrunk_global_palette[AVPALETTE_COUNT]; + size_t global_palette_count; + unsigned pow2_global_palette_count; const AVRational sar = avctx->sample_aspect_ratio; int64_t aspect = 0; + if (palette) { + shrink_palette(palette, shrunk_global_palette, &global_palette_count); + global_palette = shrunk_global_palette; + } else { + global_palette = s->palette; + global_palette_count = s->palette_count; + } + if (sar.num > 0 && sar.den > 0) { aspect = sar.num * 64LL / sar.den - 15; if (aspect < 0 || aspect > 255) @@ -291,17 +328,22 @@ static int gif_image_write_image(AVCodecContext *avctx, bytestream_put_le16(bytestream, avctx->width); bytestream_put_le16(bytestream, avctx->height); - bcid = get_palette_transparency_index(global_palette); + bcid = get_palette_transparency_index(global_palette, global_palette_count); - bytestream_put_byte(bytestream, 0xf7); /* flags: global clut, 256 entries */ + pow2_global_palette_count = av_log2(global_palette_count - 1); + + bytestream_put_byte(bytestream, 0xf0 | pow2_global_palette_count); /* flags: global clut, 256 entries */ bytestream_put_byte(bytestream, bcid < 0 ? DEFAULT_TRANSPARENCY_INDEX : bcid); /* background color index */ bytestream_put_byte(bytestream, aspect); - for (int i = 0; i < 256; i++) { + for (int i = 0; i < 1 << (pow2_global_palette_count + 1); i++) { const uint32_t v = global_palette[i] & 0xffffff; bytestream_put_be24(bytestream, v); } } + if (palette) + shrink_palette(palette, shrunk_palette, &shrunk_palette_count); + if (honor_transparency && trans < 0) { trans = pick_palette_entry(buf + y_start*linesize + x_start, linesize, width, height); @@ -312,7 +354,7 @@ static int gif_image_write_image(AVCodecContext *avctx, if (trans < 0) honor_transparency = 0; - bcid = honor_transparency || disposal == GCE_DISPOSAL_BACKGROUND ? trans : get_palette_transparency_index(palette); + bcid = honor_transparency || disposal == GCE_DISPOSAL_BACKGROUND ? trans : get_palette_transparency_index(palette ? shrunk_palette : NULL, shrunk_palette_count); /* graphic control extension */ bytestream_put_byte(bytestream, GIF_EXTENSION_INTRODUCER); @@ -334,8 +376,9 @@ static int gif_image_write_image(AVCodecContext *avctx, bytestream_put_byte(bytestream, 0x00); /* flags */ } else { unsigned i; - bytestream_put_byte(bytestream, 1<<7 | 0x7); /* flags */ - for (i = 0; i < AVPALETTE_COUNT; i++) { + unsigned 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 = palette[i]; bytestream_put_be24(bytestream, v); } @@ -402,6 +445,7 @@ static av_cold int gif_encode_init(AVCodecContext *avctx) if (avpriv_set_systematic_pal2(s->palette, avctx->pix_fmt) < 0) av_assert0(avctx->pix_fmt == AV_PIX_FMT_PAL8); + s->palette_count = AVPALETTE_COUNT; return 0; } @@ -420,13 +464,26 @@ static int gif_encode_frame(AVCodecContext *avctx, AVPacket *pkt, end = pkt->data + pkt->size; if (avctx->pix_fmt == AV_PIX_FMT_PAL8) { + uint32_t shrunk_palette[AVPALETTE_COUNT]; + size_t shrunk_palette_count; + palette = (uint32_t*)pict->data[1]; + /* + * 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); + shrink_palette(palette, shrunk_palette, &shrunk_palette_count); + if (!s->palette_loaded) { - memcpy(s->palette, palette, AVPALETTE_SIZE); - s->transparent_index = get_palette_transparency_index(palette); + memcpy(s->palette, shrunk_palette, AVPALETTE_SIZE); + s->palette_count = shrunk_palette_count; + s->transparent_index = get_palette_transparency_index(s->palette, s->palette_count); s->palette_loaded = 1; - } else if (!memcmp(s->palette, palette, AVPALETTE_SIZE)) { + } else if (!memcmp(s->palette, shrunk_palette, AVPALETTE_SIZE)) { palette = NULL; } }