image/gif: try harder to use global color table

The GIF format allows for an image to contain a global color table which
might be used for some or every frame in an animated GIF.  This palette
contains 24-bit opaque RGB values.  An individual frame may use the
global palette and enable transparency by picking one number to be
transparent, instead of the color value in the palette.

image/gif decodes a GIF, which contains an []*image.Paletted that holds
each frame.  When decoded, if a frame has a transparent color and uses
the global palette, a copy of the global []color.Color is made, and the
transparency color index is replaced with color.RGBA{}.

When encoding a GIF, each frame's palette is encoded to the form it
might exist in a GIF, up to 768 bytes "RGBRGBRGBRGB...". If a frame's
encoded palette is equal to the encoded global color table, the frame
will be encoded with the flag set to use the global color table,
otherwise the frame's palette will be included.

So, if the color in the global color table that matches the transparent
index of one frame wasn't black (and it frequently is not), reencoding a
GIF will likely result in a larger file because each frame's palette
will have to be encoded inline.

This commit takes a frame's transparent color index into account when
comparing an individual image.Paletted's encoded color table to the
global color table.

Fixes #22137

Change-Id: I5460021da6e4d7ce19198d5f94a8ce714815bc08
Reviewed-on: https://go-review.googlesource.com/68313
Reviewed-by: Nigel Tao <nigeltao@golang.org>

2 files changed, 84 insertions, 26 deletions

diff --git a/src/image/gif/writer.go b/src/image/gif/writer.go
index 493c7549eb..fd8463ed08 100644
--- a/src/image/gif/writer.go
+++ b/src/image/gif/writer.go
@@ -171,27 +171,44 @@ func encodeColorTable(dst []byte, p color.Palette, size int) (int, error) {
 	if uint(size) >= uint(len(log2Lookup)) {
 		return 0, errors.New("gif: cannot encode color table with more than 256 entries")
 	}
-	n := log2Lookup[size]
-	for i := 0; i < n; i++ {
-		if i < len(p) {
-			c := p[i]
-			if c == nil {
-				return 0, errors.New("gif: cannot encode color table with nil entries")
-			}
-			r, g, b, _ := c.RGBA()
-			dst[3*i+0] = uint8(r >> 8)
-			dst[3*i+1] = uint8(g >> 8)
-			dst[3*i+2] = uint8(b >> 8)
+	for i, c := range p {
+		if c == nil {
+			return 0, errors.New("gif: cannot encode color table with nil entries")
+		}
+		var r, g, b uint8
+		// It is most likely that the palette is full of color.RGBAs, so they
+		// get a fast path.
+		if rgba, ok := c.(color.RGBA); ok {
+			r, g, b = rgba.R, rgba.G, rgba.B
 		} else {
-			// Pad with black.
-			dst[3*i+0] = 0x00
-			dst[3*i+1] = 0x00
-			dst[3*i+2] = 0x00
+			rr, gg, bb, _ := c.RGBA()
+			r, g, b = uint8(rr>>8), uint8(gg>>8), uint8(bb>>8)
+		}
+		dst[3*i+0] = r
+		dst[3*i+1] = g
+		dst[3*i+2] = b
+	}
+	n := log2Lookup[size]
+	if n > len(p) {
+		// Pad with black.
+		fill := dst[3*len(p) : 3*n]
+		for i := range fill {
+			fill[i] = 0
 		}
 	}
 	return 3 * n, nil
 }
 
+func (e *encoder) colorTablesMatch(localLen, transparentIndex int) bool {
+	localSize := 3 * localLen
+	if transparentIndex >= 0 {
+		trOff := 3 * transparentIndex
+		return bytes.Equal(e.globalColorTable[:trOff], e.localColorTable[:trOff]) &&
+			bytes.Equal(e.globalColorTable[trOff+3:localSize], e.localColorTable[trOff+3:localSize])
+	}
+	return bytes.Equal(e.globalColorTable[:localSize], e.localColorTable[:localSize])
+}
+
 func (e *encoder) writeImageBlock(pm *image.Paletted, delay int, disposal byte) {
 	if e.err != nil {
 		return
@@ -251,19 +268,31 @@ func (e *encoder) writeImageBlock(pm *image.Paletted, delay int, disposal byte)
 	writeUint16(e.buf[7:9], uint16(b.Dy()))
 	e.write(e.buf[:9])
 
+	// To determine whether or not this frame's palette is the same as the
+	// global palette, we can check a couple things. First, do they actually
+	// point to the same []color.Color? If so, they are equal so long as the
+	// frame's palette is not longer than the global palette...
 	paddedSize := log2(len(pm.Palette)) // Size of Local Color Table: 2^(1+n).
-	if ct, err := encodeColorTable(e.localColorTable[:], pm.Palette, paddedSize); err != nil {
-		if e.err == nil {
-			e.err = err
-		}
-		return
-	} else if ct != e.globalCT || !bytes.Equal(e.globalColorTable[:ct], e.localColorTable[:ct]) {
-		// Use a local color table.
-		e.writeByte(fColorTable | uint8(paddedSize))
-		e.write(e.localColorTable[:ct])
+	if gp, ok := e.g.Config.ColorModel.(color.Palette); ok && len(pm.Palette) <= len(gp) && &gp[0] == &pm.Palette[0] {
+		e.writeByte(0) // Use the global color table.
 	} else {
-		// Use the global color table.
-		e.writeByte(0)
+		ct, err := encodeColorTable(e.localColorTable[:], pm.Palette, paddedSize)
+		if err != nil {
+			if e.err == nil {
+				e.err = err
+			}
+			return
+		}
+		// This frame's palette is not the very same slice as the global
+		// palette, but it might be a copy, possibly with one value turned into
+		// transparency by DecodeAll.
+		if ct <= e.globalCT && e.colorTablesMatch(len(pm.Palette), transparentIndex) {
+			e.writeByte(0) // Use the global color table.
+		} else {
+			// Use a local color table.
+			e.writeByte(fColorTable | uint8(paddedSize))
+			e.write(e.localColorTable[:ct])
+		}
 	}
 
 	litWidth := paddedSize + 1
diff --git a/src/image/gif/writer_test.go b/src/image/gif/writer_test.go
index eb17cf28ed..b48e53272e 100644
--- a/src/image/gif/writer_test.go
+++ b/src/image/gif/writer_test.go
@@ -471,6 +471,35 @@ func TestEncodeBadPalettes(t *testing.T) {
 	}
 }
 
+func TestColorTablesMatch(t *testing.T) {
+	const trIdx = 100
+	global := color.Palette(palette.Plan9)
+	if rgb := global[trIdx].(color.RGBA); rgb.R == 0 && rgb.G == 0 && rgb.B == 0 {
+		t.Fatalf("trIdx (%d) is already black", trIdx)
+	}
+
+	// Make a copy of the palette, substituting trIdx's slot with transparent,
+	// just like decoder.decode.
+	local := append(color.Palette(nil), global...)
+	local[trIdx] = color.RGBA{}
+
+	const testLen = 3 * 256
+	const padded = 7
+	e := new(encoder)
+	if l, err := encodeColorTable(e.globalColorTable[:], global, padded); err != nil || l != testLen {
+		t.Fatalf("Failed to encode global color table: got %d, %v; want nil, %d", l, err, testLen)
+	}
+	if l, err := encodeColorTable(e.localColorTable[:], local, padded); err != nil || l != testLen {
+		t.Fatalf("Failed to encode local color table: got %d, %v; want nil, %d", l, err, testLen)
+	}
+	if bytes.Equal(e.globalColorTable[:testLen], e.localColorTable[:testLen]) {
+		t.Fatal("Encoded color tables are equal, expected mismatch")
+	}
+	if !e.colorTablesMatch(len(local), trIdx) {
+		t.Fatal("colorTablesMatch() == false, expected true")
+	}
+}
+
 func TestEncodeCroppedSubImages(t *testing.T) {
 	// This test means to ensure that Encode honors the Bounds and Strides of
 	// images correctly when encoding.