diff mbox series

[FFmpeg-devel] libavcodec/gifenc: Only write palette entries that actually used

Message ID 20210204165016.1028474-1-derek.buitenhuis@gmail.com
State New
Headers show
Series [FFmpeg-devel] libavcodec/gifenc: Only write palette entries that actually used
Related show

Checks

Context Check Description
andriy/x86_make success Make finished
andriy/x86_make_fate success Make fate finished
andriy/PPC64_make success Make finished
andriy/PPC64_make_fate success Make fate finished

Commit Message

Derek Buitenhuis Feb. 4, 2021, 4:50 p.m. UTC
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 <derek.buitenhuis@gmail.com>
---
 libavcodec/gif.c | 81 +++++++++++++++++++++++++++++++++++++++++-------
 1 file changed, 69 insertions(+), 12 deletions(-)

Comments

Paul B Mahol Feb. 4, 2021, 5:07 p.m. UTC | #1
On Thu, Feb 4, 2021 at 5:57 PM Derek Buitenhuis <derek.buitenhuis@gmail.com>
wrote:

> 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 <derek.buitenhuis@gmail.com>
> ---
>  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);
>

You first init array to 0 and than use memset?


>
>      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;
>          }
>      }
> --
> 2.30.0
>
> _______________________________________________
> ffmpeg-devel mailing list
> ffmpeg-devel@ffmpeg.org
> https://ffmpeg.org/mailman/listinfo/ffmpeg-devel
>
> To unsubscribe, visit link above, or email
> ffmpeg-devel-request@ffmpeg.org with subject "unsubscribe".
Derek Buitenhuis Feb. 4, 2021, 5:09 p.m. UTC | #2
On 04/02/2021 17:07, Paul B Mahol wrote:
> You first init array to 0 and than use memset?

Accidentally left it in, removed it now.

Further, I forgot to add re-mapping of the frame values
for the case where the user-provided palette is not
front-loaded (e.g. it has gaps), so I'll send a v2.

- Derek
Derek Buitenhuis Feb. 4, 2021, 5:15 p.m. UTC | #3
On 04/02/2021 17:09, Derek Buitenhuis wrote:
> Accidentally left it in, removed it now.
> 
> Further, I forgot to add re-mapping of the frame values
> for the case where the user-provided palette is not
> front-loaded (e.g. it has gaps), so I'll send a v2.

Another case to consider is that we should not shrink the
global palette at all because later frames may reference
indicies not used in the first frame.

That however, loses us compression efficiency for cases
where it doesn't, or where each frame has a its own
palette anyway.

How do we feel about adding an AVOption to force the
use or not-use of a global palette?

- Derek
Paul B Mahol Feb. 4, 2021, 5:26 p.m. UTC | #4
On Thu, Feb 4, 2021 at 6:15 PM Derek Buitenhuis <derek.buitenhuis@gmail.com>
wrote:

> On 04/02/2021 17:09, Derek Buitenhuis wrote:
> > Accidentally left it in, removed it now.
> >
> > Further, I forgot to add re-mapping of the frame values
> > for the case where the user-provided palette is not
> > front-loaded (e.g. it has gaps), so I'll send a v2.
>
> Another case to consider is that we should not shrink the
> global palette at all because later frames may reference
> indicies not used in the first frame.
>
> That however, loses us compression efficiency for cases
> where it doesn't, or where each frame has a its own
> palette anyway.
>
> How do we feel about adding an AVOption to force the
> use or not-use of a global palette?
>

How would that work?
I'm not against if that does not break existing usage.


>
> - Derek
> _______________________________________________
> ffmpeg-devel mailing list
> ffmpeg-devel@ffmpeg.org
> https://ffmpeg.org/mailman/listinfo/ffmpeg-devel
>
> To unsubscribe, visit link above, or email
> ffmpeg-devel-request@ffmpeg.org with subject "unsubscribe".
Derek Buitenhuis Feb. 4, 2021, 6:42 p.m. UTC | #5
On 04/02/2021 17:26, Paul B Mahol wrote:
> How would that work?
> I'm not against if that does not break existing usage.

Somethng like '-no_global_paltte 1' to not use a global
palette, and write a palette each frame. Default would be
off, so curent behavior is maintained.

- Derek
Andreas Rheinhardt Feb. 5, 2021, 1:54 a.m. UTC | #6
Derek Buitenhuis:
> On 04/02/2021 17:26, Paul B Mahol wrote:
>> How would that work?
>> I'm not against if that does not break existing usage.
> 
> Somethng like '-no_global_paltte 1' to not use a global
> palette, and write a palette each frame. Default would be
> off, so curent behavior is maintained.
> 
> - Derek

Could AV_CODEC_FLAG_GLOBAL_HEADER be used for this?

- Andreas
Derek Buitenhuis Feb. 5, 2021, 4:07 p.m. UTC | #7
On 05/02/2021 01:54, Andreas Rheinhardt wrote:
> Could AV_CODEC_FLAG_GLOBAL_HEADER be used for this?

It could, but I don't think it should.

The global header is still written, just not with a global palette.
I think it would be, at best, confusing, especially in terms of
intent.

- Derek
Jean First Feb. 5, 2021, 11:41 p.m. UTC | #8
Derek Buitenhuis wrote on 04.02.21 19:42:
> On 04/02/2021 17:26, Paul B Mahol wrote:
>> How would that work?
>> I'm not against if that does not break existing usage.
> Somethng like '-no_global_paltte 1' to not use a global
> palette, and write a palette each frame. Default would be
> off, so curent behavior is maintained.

Please do not negate options. So instead of  '-no_global_palette' just 
use '-global_palette'.
Nuo Mi Feb. 6, 2021, 4:02 a.m. UTC | #9
On Fri, Feb 5, 2021 at 12:57 AM Derek Buitenhuis <derek.buitenhuis@gmail.com>
wrote:

> 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 <derek.buitenhuis@gmail.com>
> ---
>  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);

This will memset each frame. Could we avoid it?
Is memset memory between [global_palette_count, 1<<(
av_log2(global_palette_count - 1) + 1)]  enough?




>      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 */
>
The comment may be misleading, it's not 256 anymore.

>          bytestream_put_byte(bytestream, bcid < 0 ?
> DEFAULT_TRANSPARENCY_INDEX : bcid); /* background color index */
>
>
> _______________________________________________
> ffmpeg-devel mailing list
> ffmpeg-devel@ffmpeg.org
> https://ffmpeg.org/mailman/listinfo/ffmpeg-devel
>
> To unsubscribe, visit link above, or email
> ffmpeg-devel-request@ffmpeg.org with subject "unsubscribe".
diff mbox series

Patch

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