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