Adding upstream version 1.20.14.upstream/1.20.14upstream

Signed-off-by: Daniel Baumann <daniel.baumann@progress-linux.org>

5 files changed, 2358 insertions, 0 deletions

diff --git a/src/image/gif/fuzz_test.go b/src/image/gif/fuzz_test.go
new file mode 100644
index 0000000..a4bc06e
--- /dev/null
+++ b/src/image/gif/fuzz_test.go
@@ -0,0 +1,65 @@
+// Copyright 2021 The Go Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style
+// license that can be found in the LICENSE file.
+
+package gif
+
+import (
+	"bytes"
+	"image"
+	"os"
+	"path/filepath"
+	"strings"
+	"testing"
+)
+
+func FuzzDecode(f *testing.F) {
+	if testing.Short() {
+		f.Skip("Skipping in short mode")
+	}
+
+	testdata, err := os.ReadDir("../testdata")
+	if err != nil {
+		f.Fatalf("failed to read testdata directory: %s", err)
+	}
+	for _, de := range testdata {
+		if de.IsDir() || !strings.HasSuffix(de.Name(), ".gif") {
+			continue
+		}
+		b, err := os.ReadFile(filepath.Join("../testdata", de.Name()))
+		if err != nil {
+			f.Fatalf("failed to read testdata: %s", err)
+		}
+		f.Add(b)
+	}
+
+	f.Fuzz(func(t *testing.T, b []byte) {
+		cfg, _, err := image.DecodeConfig(bytes.NewReader(b))
+		if err != nil {
+			return
+		}
+		if cfg.Width*cfg.Height > 1e6 {
+			return
+		}
+		img, typ, err := image.Decode(bytes.NewReader(b))
+		if err != nil || typ != "gif" {
+			return
+		}
+		for q := 1; q <= 256; q++ {
+			var w bytes.Buffer
+			err := Encode(&w, img, &Options{NumColors: q})
+			if err != nil {
+				t.Fatalf("failed to encode valid image: %s", err)
+			}
+			img1, err := Decode(&w)
+			if err != nil {
+				t.Fatalf("failed to decode roundtripped image: %s", err)
+			}
+			got := img1.Bounds()
+			want := img.Bounds()
+			if !got.Eq(want) {
+				t.Fatalf("roundtripped image bounds have changed, got: %v, want: %v", got, want)
+			}
+		}
+	})
+}
diff --git a/src/image/gif/reader.go b/src/image/gif/reader.go
new file mode 100644
index 0000000..0867b10
--- /dev/null
+++ b/src/image/gif/reader.go
@@ -0,0 +1,641 @@
+// Copyright 2011 The Go Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style
+// license that can be found in the LICENSE file.
+
+// Package gif implements a GIF image decoder and encoder.
+//
+// The GIF specification is at https://www.w3.org/Graphics/GIF/spec-gif89a.txt.
+package gif
+
+import (
+	"bufio"
+	"compress/lzw"
+	"errors"
+	"fmt"
+	"image"
+	"image/color"
+	"io"
+)
+
+var (
+	errNotEnough = errors.New("gif: not enough image data")
+	errTooMuch   = errors.New("gif: too much image data")
+	errBadPixel  = errors.New("gif: invalid pixel value")
+)
+
+// If the io.Reader does not also have ReadByte, then decode will introduce its own buffering.
+type reader interface {
+	io.Reader
+	io.ByteReader
+}
+
+// Masks etc.
+const (
+	// Fields.
+	fColorTable         = 1 << 7
+	fInterlace          = 1 << 6
+	fColorTableBitsMask = 7
+
+	// Graphic control flags.
+	gcTransparentColorSet = 1 << 0
+	gcDisposalMethodMask  = 7 << 2
+)
+
+// Disposal Methods.
+const (
+	DisposalNone       = 0x01
+	DisposalBackground = 0x02
+	DisposalPrevious   = 0x03
+)
+
+// Section indicators.
+const (
+	sExtension       = 0x21
+	sImageDescriptor = 0x2C
+	sTrailer         = 0x3B
+)
+
+// Extensions.
+const (
+	eText           = 0x01 // Plain Text
+	eGraphicControl = 0xF9 // Graphic Control
+	eComment        = 0xFE // Comment
+	eApplication    = 0xFF // Application
+)
+
+func readFull(r io.Reader, b []byte) error {
+	_, err := io.ReadFull(r, b)
+	if err == io.EOF {
+		err = io.ErrUnexpectedEOF
+	}
+	return err
+}
+
+func readByte(r io.ByteReader) (byte, error) {
+	b, err := r.ReadByte()
+	if err == io.EOF {
+		err = io.ErrUnexpectedEOF
+	}
+	return b, err
+}
+
+// decoder is the type used to decode a GIF file.
+type decoder struct {
+	r reader
+
+	// From header.
+	vers            string
+	width           int
+	height          int
+	loopCount       int
+	delayTime       int
+	backgroundIndex byte
+	disposalMethod  byte
+
+	// From image descriptor.
+	imageFields byte
+
+	// From graphics control.
+	transparentIndex    byte
+	hasTransparentIndex bool
+
+	// Computed.
+	globalColorTable color.Palette
+
+	// Used when decoding.
+	delay    []int
+	disposal []byte
+	image    []*image.Paletted
+	tmp      [1024]byte // must be at least 768 so we can read color table
+}
+
+// blockReader parses the block structure of GIF image data, which comprises
+// (n, (n bytes)) blocks, with 1 <= n <= 255. It is the reader given to the
+// LZW decoder, which is thus immune to the blocking. After the LZW decoder
+// completes, there will be a 0-byte block remaining (0, ()), which is
+// consumed when checking that the blockReader is exhausted.
+//
+// To avoid the allocation of a bufio.Reader for the lzw Reader, blockReader
+// implements io.ByteReader and buffers blocks into the decoder's "tmp" buffer.
+type blockReader struct {
+	d    *decoder
+	i, j uint8 // d.tmp[i:j] contains the buffered bytes
+	err  error
+}
+
+func (b *blockReader) fill() {
+	if b.err != nil {
+		return
+	}
+	b.j, b.err = readByte(b.d.r)
+	if b.j == 0 && b.err == nil {
+		b.err = io.EOF
+	}
+	if b.err != nil {
+		return
+	}
+
+	b.i = 0
+	b.err = readFull(b.d.r, b.d.tmp[:b.j])
+	if b.err != nil {
+		b.j = 0
+	}
+}
+
+func (b *blockReader) ReadByte() (byte, error) {
+	if b.i == b.j {
+		b.fill()
+		if b.err != nil {
+			return 0, b.err
+		}
+	}
+
+	c := b.d.tmp[b.i]
+	b.i++
+	return c, nil
+}
+
+// blockReader must implement io.Reader, but its Read shouldn't ever actually
+// be called in practice. The compress/lzw package will only call ReadByte.
+func (b *blockReader) Read(p []byte) (int, error) {
+	if len(p) == 0 || b.err != nil {
+		return 0, b.err
+	}
+	if b.i == b.j {
+		b.fill()
+		if b.err != nil {
+			return 0, b.err
+		}
+	}
+
+	n := copy(p, b.d.tmp[b.i:b.j])
+	b.i += uint8(n)
+	return n, nil
+}
+
+// close primarily detects whether or not a block terminator was encountered
+// after reading a sequence of data sub-blocks. It allows at most one trailing
+// sub-block worth of data. I.e., if some number of bytes exist in one sub-block
+// following the end of LZW data, the very next sub-block must be the block
+// terminator. If the very end of LZW data happened to fill one sub-block, at
+// most one more sub-block of length 1 may exist before the block-terminator.
+// These accommodations allow us to support GIFs created by less strict encoders.
+// See https://golang.org/issue/16146.
+func (b *blockReader) close() error {
+	if b.err == io.EOF {
+		// A clean block-sequence terminator was encountered while reading.
+		return nil
+	} else if b.err != nil {
+		// Some other error was encountered while reading.
+		return b.err
+	}
+
+	if b.i == b.j {
+		// We reached the end of a sub block reading LZW data. We'll allow at
+		// most one more sub block of data with a length of 1 byte.
+		b.fill()
+		if b.err == io.EOF {
+			return nil
+		} else if b.err != nil {
+			return b.err
+		} else if b.j > 1 {
+			return errTooMuch
+		}
+	}
+
+	// Part of a sub-block remains buffered. We expect that the next attempt to
+	// buffer a sub-block will reach the block terminator.
+	b.fill()
+	if b.err == io.EOF {
+		return nil
+	} else if b.err != nil {
+		return b.err
+	}
+
+	return errTooMuch
+}
+
+// decode reads a GIF image from r and stores the result in d.
+func (d *decoder) decode(r io.Reader, configOnly, keepAllFrames bool) error {
+	// Add buffering if r does not provide ReadByte.
+	if rr, ok := r.(reader); ok {
+		d.r = rr
+	} else {
+		d.r = bufio.NewReader(r)
+	}
+
+	d.loopCount = -1
+
+	err := d.readHeaderAndScreenDescriptor()
+	if err != nil {
+		return err
+	}
+	if configOnly {
+		return nil
+	}
+
+	for {
+		c, err := readByte(d.r)
+		if err != nil {
+			return fmt.Errorf("gif: reading frames: %v", err)
+		}
+		switch c {
+		case sExtension:
+			if err = d.readExtension(); err != nil {
+				return err
+			}
+
+		case sImageDescriptor:
+			if err = d.readImageDescriptor(keepAllFrames); err != nil {
+				return err
+			}
+
+			if !keepAllFrames && len(d.image) == 1 {
+				return nil
+			}
+
+		case sTrailer:
+			if len(d.image) == 0 {
+				return fmt.Errorf("gif: missing image data")
+			}
+			return nil
+
+		default:
+			return fmt.Errorf("gif: unknown block type: 0x%.2x", c)
+		}
+	}
+}
+
+func (d *decoder) readHeaderAndScreenDescriptor() error {
+	err := readFull(d.r, d.tmp[:13])
+	if err != nil {
+		return fmt.Errorf("gif: reading header: %v", err)
+	}
+	d.vers = string(d.tmp[:6])
+	if d.vers != "GIF87a" && d.vers != "GIF89a" {
+		return fmt.Errorf("gif: can't recognize format %q", d.vers)
+	}
+	d.width = int(d.tmp[6]) + int(d.tmp[7])<<8
+	d.height = int(d.tmp[8]) + int(d.tmp[9])<<8
+	if fields := d.tmp[10]; fields&fColorTable != 0 {
+		d.backgroundIndex = d.tmp[11]
+		// readColorTable overwrites the contents of d.tmp, but that's OK.
+		if d.globalColorTable, err = d.readColorTable(fields); err != nil {
+			return err
+		}
+	}
+	// d.tmp[12] is the Pixel Aspect Ratio, which is ignored.
+	return nil
+}
+
+func (d *decoder) readColorTable(fields byte) (color.Palette, error) {
+	n := 1 << (1 + uint(fields&fColorTableBitsMask))
+	err := readFull(d.r, d.tmp[:3*n])
+	if err != nil {
+		return nil, fmt.Errorf("gif: reading color table: %s", err)
+	}
+	j, p := 0, make(color.Palette, n)
+	for i := range p {
+		p[i] = color.RGBA{d.tmp[j+0], d.tmp[j+1], d.tmp[j+2], 0xFF}
+		j += 3
+	}
+	return p, nil
+}
+
+func (d *decoder) readExtension() error {
+	extension, err := readByte(d.r)
+	if err != nil {
+		return fmt.Errorf("gif: reading extension: %v", err)
+	}
+	size := 0
+	switch extension {
+	case eText:
+		size = 13
+	case eGraphicControl:
+		return d.readGraphicControl()
+	case eComment:
+		// nothing to do but read the data.
+	case eApplication:
+		b, err := readByte(d.r)
+		if err != nil {
+			return fmt.Errorf("gif: reading extension: %v", err)
+		}
+		// The spec requires size be 11, but Adobe sometimes uses 10.
+		size = int(b)
+	default:
+		return fmt.Errorf("gif: unknown extension 0x%.2x", extension)
+	}
+	if size > 0 {
+		if err := readFull(d.r, d.tmp[:size]); err != nil {
+			return fmt.Errorf("gif: reading extension: %v", err)
+		}
+	}
+
+	// Application Extension with "NETSCAPE2.0" as string and 1 in data means
+	// this extension defines a loop count.
+	if extension == eApplication && string(d.tmp[:size]) == "NETSCAPE2.0" {
+		n, err := d.readBlock()
+		if err != nil {
+			return fmt.Errorf("gif: reading extension: %v", err)
+		}
+		if n == 0 {
+			return nil
+		}
+		if n == 3 && d.tmp[0] == 1 {
+			d.loopCount = int(d.tmp[1]) | int(d.tmp[2])<<8
+		}
+	}
+	for {
+		n, err := d.readBlock()
+		if err != nil {
+			return fmt.Errorf("gif: reading extension: %v", err)
+		}
+		if n == 0 {
+			return nil
+		}
+	}
+}
+
+func (d *decoder) readGraphicControl() error {
+	if err := readFull(d.r, d.tmp[:6]); err != nil {
+		return fmt.Errorf("gif: can't read graphic control: %s", err)
+	}
+	if d.tmp[0] != 4 {
+		return fmt.Errorf("gif: invalid graphic control extension block size: %d", d.tmp[0])
+	}
+	flags := d.tmp[1]
+	d.disposalMethod = (flags & gcDisposalMethodMask) >> 2
+	d.delayTime = int(d.tmp[2]) | int(d.tmp[3])<<8
+	if flags&gcTransparentColorSet != 0 {
+		d.transparentIndex = d.tmp[4]
+		d.hasTransparentIndex = true
+	}
+	if d.tmp[5] != 0 {
+		return fmt.Errorf("gif: invalid graphic control extension block terminator: %d", d.tmp[5])
+	}
+	return nil
+}
+
+func (d *decoder) readImageDescriptor(keepAllFrames bool) error {
+	m, err := d.newImageFromDescriptor()
+	if err != nil {
+		return err
+	}
+	useLocalColorTable := d.imageFields&fColorTable != 0
+	if useLocalColorTable {
+		m.Palette, err = d.readColorTable(d.imageFields)
+		if err != nil {
+			return err
+		}
+	} else {
+		if d.globalColorTable == nil {
+			return errors.New("gif: no color table")
+		}
+		m.Palette = d.globalColorTable
+	}
+	if d.hasTransparentIndex {
+		if !useLocalColorTable {
+			// Clone the global color table.
+			m.Palette = append(color.Palette(nil), d.globalColorTable...)
+		}
+		if ti := int(d.transparentIndex); ti < len(m.Palette) {
+			m.Palette[ti] = color.RGBA{}
+		} else {
+			// The transparentIndex is out of range, which is an error
+			// according to the spec, but Firefox and Google Chrome
+			// seem OK with this, so we enlarge the palette with
+			// transparent colors. See golang.org/issue/15059.
+			p := make(color.Palette, ti+1)
+			copy(p, m.Palette)
+			for i := len(m.Palette); i < len(p); i++ {
+				p[i] = color.RGBA{}
+			}
+			m.Palette = p
+		}
+	}
+	litWidth, err := readByte(d.r)
+	if err != nil {
+		return fmt.Errorf("gif: reading image data: %v", err)
+	}
+	if litWidth < 2 || litWidth > 8 {
+		return fmt.Errorf("gif: pixel size in decode out of range: %d", litWidth)
+	}
+	// A wonderfully Go-like piece of magic.
+	br := &blockReader{d: d}
+	lzwr := lzw.NewReader(br, lzw.LSB, int(litWidth))
+	defer lzwr.Close()
+	if err = readFull(lzwr, m.Pix); err != nil {
+		if err != io.ErrUnexpectedEOF {
+			return fmt.Errorf("gif: reading image data: %v", err)
+		}
+		return errNotEnough
+	}
+	// In theory, both lzwr and br should be exhausted. Reading from them
+	// should yield (0, io.EOF).
+	//
+	// The spec (Appendix F - Compression), says that "An End of
+	// Information code... must be the last code output by the encoder
+	// for an image". In practice, though, giflib (a widely used C
+	// library) does not enforce this, so we also accept lzwr returning
+	// io.ErrUnexpectedEOF (meaning that the encoded stream hit io.EOF
+	// before the LZW decoder saw an explicit end code), provided that
+	// the io.ReadFull call above successfully read len(m.Pix) bytes.
+	// See https://golang.org/issue/9856 for an example GIF.
+	if n, err := lzwr.Read(d.tmp[256:257]); n != 0 || (err != io.EOF && err != io.ErrUnexpectedEOF) {
+		if err != nil {
+			return fmt.Errorf("gif: reading image data: %v", err)
+		}
+		return errTooMuch
+	}
+
+	// In practice, some GIFs have an extra byte in the data sub-block
+	// stream, which we ignore. See https://golang.org/issue/16146.
+	if err := br.close(); err == errTooMuch {
+		return errTooMuch
+	} else if err != nil {
+		return fmt.Errorf("gif: reading image data: %v", err)
+	}
+
+	// Check that the color indexes are inside the palette.
+	if len(m.Palette) < 256 {
+		for _, pixel := range m.Pix {
+			if int(pixel) >= len(m.Palette) {
+				return errBadPixel
+			}
+		}
+	}
+
+	// Undo the interlacing if necessary.
+	if d.imageFields&fInterlace != 0 {
+		uninterlace(m)
+	}
+
+	if keepAllFrames || len(d.image) == 0 {
+		d.image = append(d.image, m)
+		d.delay = append(d.delay, d.delayTime)
+		d.disposal = append(d.disposal, d.disposalMethod)
+	}
+	// The GIF89a spec, Section 23 (Graphic Control Extension) says:
+	// "The scope of this extension is the first graphic rendering block
+	// to follow." We therefore reset the GCE fields to zero.
+	d.delayTime = 0
+	d.hasTransparentIndex = false
+	return nil
+}
+
+func (d *decoder) newImageFromDescriptor() (*image.Paletted, error) {
+	if err := readFull(d.r, d.tmp[:9]); err != nil {
+		return nil, fmt.Errorf("gif: can't read image descriptor: %s", err)
+	}
+	left := int(d.tmp[0]) + int(d.tmp[1])<<8
+	top := int(d.tmp[2]) + int(d.tmp[3])<<8
+	width := int(d.tmp[4]) + int(d.tmp[5])<<8
+	height := int(d.tmp[6]) + int(d.tmp[7])<<8
+	d.imageFields = d.tmp[8]
+
+	// The GIF89a spec, Section 20 (Image Descriptor) says: "Each image must
+	// fit within the boundaries of the Logical Screen, as defined in the
+	// Logical Screen Descriptor."
+	//
+	// This is conceptually similar to testing
+	//	frameBounds := image.Rect(left, top, left+width, top+height)
+	//	imageBounds := image.Rect(0, 0, d.width, d.height)
+	//	if !frameBounds.In(imageBounds) { etc }
+	// but the semantics of the Go image.Rectangle type is that r.In(s) is true
+	// whenever r is an empty rectangle, even if r.Min.X > s.Max.X. Here, we
+	// want something stricter.
+	//
+	// Note that, by construction, left >= 0 && top >= 0, so we only have to
+	// explicitly compare frameBounds.Max (left+width, top+height) against
+	// imageBounds.Max (d.width, d.height) and not frameBounds.Min (left, top)
+	// against imageBounds.Min (0, 0).
+	if left+width > d.width || top+height > d.height {
+		return nil, errors.New("gif: frame bounds larger than image bounds")
+	}
+	return image.NewPaletted(image.Rectangle{
+		Min: image.Point{left, top},
+		Max: image.Point{left + width, top + height},
+	}, nil), nil
+}
+
+func (d *decoder) readBlock() (int, error) {
+	n, err := readByte(d.r)
+	if n == 0 || err != nil {
+		return 0, err
+	}
+	if err := readFull(d.r, d.tmp[:n]); err != nil {
+		return 0, err
+	}
+	return int(n), nil
+}
+
+// interlaceScan defines the ordering for a pass of the interlace algorithm.
+type interlaceScan struct {
+	skip, start int
+}
+
+// interlacing represents the set of scans in an interlaced GIF image.
+var interlacing = []interlaceScan{
+	{8, 0}, // Group 1 : Every 8th. row, starting with row 0.
+	{8, 4}, // Group 2 : Every 8th. row, starting with row 4.
+	{4, 2}, // Group 3 : Every 4th. row, starting with row 2.
+	{2, 1}, // Group 4 : Every 2nd. row, starting with row 1.
+}
+
+// uninterlace rearranges the pixels in m to account for interlaced input.
+func uninterlace(m *image.Paletted) {
+	var nPix []uint8
+	dx := m.Bounds().Dx()
+	dy := m.Bounds().Dy()
+	nPix = make([]uint8, dx*dy)
+	offset := 0 // steps through the input by sequential scan lines.
+	for _, pass := range interlacing {
+		nOffset := pass.start * dx // steps through the output as defined by pass.
+		for y := pass.start; y < dy; y += pass.skip {
+			copy(nPix[nOffset:nOffset+dx], m.Pix[offset:offset+dx])
+			offset += dx
+			nOffset += dx * pass.skip
+		}
+	}
+	m.Pix = nPix
+}
+
+// Decode reads a GIF image from r and returns the first embedded
+// image as an image.Image.
+func Decode(r io.Reader) (image.Image, error) {
+	var d decoder
+	if err := d.decode(r, false, false); err != nil {
+		return nil, err
+	}
+	return d.image[0], nil
+}
+
+// GIF represents the possibly multiple images stored in a GIF file.
+type GIF struct {
+	Image []*image.Paletted // The successive images.
+	Delay []int             // The successive delay times, one per frame, in 100ths of a second.
+	// LoopCount controls the number of times an animation will be
+	// restarted during display.
+	// A LoopCount of 0 means to loop forever.
+	// A LoopCount of -1 means to show each frame only once.
+	// Otherwise, the animation is looped LoopCount+1 times.
+	LoopCount int
+	// Disposal is the successive disposal methods, one per frame. For
+	// backwards compatibility, a nil Disposal is valid to pass to EncodeAll,
+	// and implies that each frame's disposal method is 0 (no disposal
+	// specified).
+	Disposal []byte
+	// Config is the global color table (palette), width and height. A nil or
+	// empty-color.Palette Config.ColorModel means that each frame has its own
+	// color table and there is no global color table. Each frame's bounds must
+	// be within the rectangle defined by the two points (0, 0) and
+	// (Config.Width, Config.Height).
+	//
+	// For backwards compatibility, a zero-valued Config is valid to pass to
+	// EncodeAll, and implies that the overall GIF's width and height equals
+	// the first frame's bounds' Rectangle.Max point.
+	Config image.Config
+	// BackgroundIndex is the background index in the global color table, for
+	// use with the DisposalBackground disposal method.
+	BackgroundIndex byte
+}
+
+// DecodeAll reads a GIF image from r and returns the sequential frames
+// and timing information.
+func DecodeAll(r io.Reader) (*GIF, error) {
+	var d decoder
+	if err := d.decode(r, false, true); err != nil {
+		return nil, err
+	}
+	gif := &GIF{
+		Image:     d.image,
+		LoopCount: d.loopCount,
+		Delay:     d.delay,
+		Disposal:  d.disposal,
+		Config: image.Config{
+			ColorModel: d.globalColorTable,
+			Width:      d.width,
+			Height:     d.height,
+		},
+		BackgroundIndex: d.backgroundIndex,
+	}
+	return gif, nil
+}
+
+// DecodeConfig returns the global color model and dimensions of a GIF image
+// without decoding the entire image.
+func DecodeConfig(r io.Reader) (image.Config, error) {
+	var d decoder
+	if err := d.decode(r, true, false); err != nil {
+		return image.Config{}, err
+	}
+	return image.Config{
+		ColorModel: d.globalColorTable,
+		Width:      d.width,
+		Height:     d.height,
+	}, nil
+}
+
+func init() {
+	image.RegisterFormat("gif", "GIF8?a", Decode, DecodeConfig)
+}
diff --git a/src/image/gif/reader_test.go b/src/image/gif/reader_test.go
new file mode 100644
index 0000000..a7f943a
--- /dev/null
+++ b/src/image/gif/reader_test.go
@@ -0,0 +1,441 @@
+// Copyright 2013 The Go Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style
+// license that can be found in the LICENSE file.
+
+package gif
+
+import (
+	"bytes"
+	"compress/lzw"
+	"image"
+	"image/color"
+	"image/color/palette"
+	"io"
+	"os"
+	"reflect"
+	"runtime"
+	"runtime/debug"
+	"strings"
+	"testing"
+)
+
+// header, palette and trailer are parts of a valid 2x1 GIF image.
+const (
+	headerStr = "GIF89a" +
+		"\x02\x00\x01\x00" + // width=2, height=1
+		"\x80\x00\x00" // headerFields=(a color table of 2 pixels), backgroundIndex, aspect
+	paletteStr = "\x10\x20\x30\x40\x50\x60" // the color table, also known as a palette
+	trailerStr = "\x3b"
+)
+
+// lzw.NewReader wants a io.ByteReader, this ensures we're compatible.
+var _ io.ByteReader = (*blockReader)(nil)
+
+// lzwEncode returns an LZW encoding (with 2-bit literals) of in.
+func lzwEncode(in []byte) []byte {
+	b := &bytes.Buffer{}
+	w := lzw.NewWriter(b, lzw.LSB, 2)
+	if _, err := w.Write(in); err != nil {
+		panic(err)
+	}
+	if err := w.Close(); err != nil {
+		panic(err)
+	}
+	return b.Bytes()
+}
+
+func TestDecode(t *testing.T) {
+	// extra contains superfluous bytes to inject into the GIF, either at the end
+	// of an existing data sub-block (past the LZW End of Information code) or in
+	// a separate data sub-block. The 0x02 values are arbitrary.
+	const extra = "\x02\x02\x02\x02"
+
+	testCases := []struct {
+		nPix int // The number of pixels in the image data.
+		// If non-zero, write this many extra bytes inside the data sub-block
+		// containing the LZW end code.
+		extraExisting int
+		// If non-zero, write an extra block of this many bytes.
+		extraSeparate int
+		wantErr       error
+	}{
+		{0, 0, 0, errNotEnough},
+		{1, 0, 0, errNotEnough},
+		{2, 0, 0, nil},
+		// An extra data sub-block after the compressed section with 1 byte which we
+		// silently skip.
+		{2, 0, 1, nil},
+		// An extra data sub-block after the compressed section with 2 bytes. In
+		// this case we complain that there is too much data.
+		{2, 0, 2, errTooMuch},
+		// Too much pixel data.
+		{3, 0, 0, errTooMuch},
+		// An extra byte after LZW data, but inside the same data sub-block.
+		{2, 1, 0, nil},
+		// Two extra bytes after LZW data, but inside the same data sub-block.
+		{2, 2, 0, nil},
+		// Extra data exists in the final sub-block with LZW data, AND there is
+		// a bogus sub-block following.
+		{2, 1, 1, errTooMuch},
+	}
+	for _, tc := range testCases {
+		b := &bytes.Buffer{}
+		b.WriteString(headerStr)
+		b.WriteString(paletteStr)
+		// Write an image with bounds 2x1 but tc.nPix pixels. If tc.nPix != 2
+		// then this should result in an invalid GIF image. First, write a
+		// magic 0x2c (image descriptor) byte, bounds=(0,0)-(2,1), a flags
+		// byte, and 2-bit LZW literals.
+		b.WriteString("\x2c\x00\x00\x00\x00\x02\x00\x01\x00\x00\x02")
+		if tc.nPix > 0 {
+			enc := lzwEncode(make([]byte, tc.nPix))
+			if len(enc)+tc.extraExisting > 0xff {
+				t.Errorf("nPix=%d, extraExisting=%d, extraSeparate=%d: compressed length %d is too large",
+					tc.nPix, tc.extraExisting, tc.extraSeparate, len(enc))
+				continue
+			}
+
+			// Write the size of the data sub-block containing the LZW data.
+			b.WriteByte(byte(len(enc) + tc.extraExisting))
+
+			// Write the LZW data.
+			b.Write(enc)
+
+			// Write extra bytes inside the same data sub-block where LZW data
+			// ended. Each arbitrarily 0x02.
+			b.WriteString(extra[:tc.extraExisting])
+		}
+
+		if tc.extraSeparate > 0 {
+			// Data sub-block size. This indicates how many extra bytes follow.
+			b.WriteByte(byte(tc.extraSeparate))
+			b.WriteString(extra[:tc.extraSeparate])
+		}
+		b.WriteByte(0x00) // An empty block signifies the end of the image data.
+		b.WriteString(trailerStr)
+
+		got, err := Decode(b)
+		if err != tc.wantErr {
+			t.Errorf("nPix=%d, extraExisting=%d, extraSeparate=%d\ngot  %v\nwant %v",
+				tc.nPix, tc.extraExisting, tc.extraSeparate, err, tc.wantErr)
+		}
+
+		if tc.wantErr != nil {
+			continue
+		}
+		want := &image.Paletted{
+			Pix:    []uint8{0, 0},
+			Stride: 2,
+			Rect:   image.Rect(0, 0, 2, 1),
+			Palette: color.Palette{
+				color.RGBA{0x10, 0x20, 0x30, 0xff},
+				color.RGBA{0x40, 0x50, 0x60, 0xff},
+			},
+		}
+		if !reflect.DeepEqual(got, want) {
+			t.Errorf("nPix=%d, extraExisting=%d, extraSeparate=%d\ngot  %v\nwant %v",
+				tc.nPix, tc.extraExisting, tc.extraSeparate, got, want)
+		}
+	}
+}
+
+func TestTransparentIndex(t *testing.T) {
+	b := &bytes.Buffer{}
+	b.WriteString(headerStr)
+	b.WriteString(paletteStr)
+	for transparentIndex := 0; transparentIndex < 3; transparentIndex++ {
+		if transparentIndex < 2 {
+			// Write the graphic control for the transparent index.
+			b.WriteString("\x21\xf9\x04\x01\x00\x00")
+			b.WriteByte(byte(transparentIndex))
+			b.WriteByte(0)
+		}
+		// Write an image with bounds 2x1, as per TestDecode.
+		b.WriteString("\x2c\x00\x00\x00\x00\x02\x00\x01\x00\x00\x02")
+		enc := lzwEncode([]byte{0x00, 0x00})
+		if len(enc) > 0xff {
+			t.Fatalf("compressed length %d is too large", len(enc))
+		}
+		b.WriteByte(byte(len(enc)))
+		b.Write(enc)
+		b.WriteByte(0x00)
+	}
+	b.WriteString(trailerStr)
+
+	g, err := DecodeAll(b)
+	if err != nil {
+		t.Fatalf("DecodeAll: %v", err)
+	}
+	c0 := color.RGBA{paletteStr[0], paletteStr[1], paletteStr[2], 0xff}
+	c1 := color.RGBA{paletteStr[3], paletteStr[4], paletteStr[5], 0xff}
+	cz := color.RGBA{}
+	wants := []color.Palette{
+		{cz, c1},
+		{c0, cz},
+		{c0, c1},
+	}
+	if len(g.Image) != len(wants) {
+		t.Fatalf("got %d images, want %d", len(g.Image), len(wants))
+	}
+	for i, want := range wants {
+		got := g.Image[i].Palette
+		if !reflect.DeepEqual(got, want) {
+			t.Errorf("palette #%d:\ngot  %v\nwant %v", i, got, want)
+		}
+	}
+}
+
+// testGIF is a simple GIF that we can modify to test different scenarios.
+var testGIF = []byte{
+	'G', 'I', 'F', '8', '9', 'a',
+	1, 0, 1, 0, // w=1, h=1 (6)
+	128, 0, 0, // headerFields, bg, aspect (10)
+	0, 0, 0, 1, 1, 1, // color table and graphics control (13)
+	0x21, 0xf9, 0x04, 0x00, 0x00, 0x00, 0xff, 0x00, // (19)
+	// frame 1 (0,0 - 1,1)
+	0x2c,
+	0x00, 0x00, 0x00, 0x00,
+	0x01, 0x00, 0x01, 0x00, // (32)
+	0x00,
+	0x02, 0x02, 0x4c, 0x01, 0x00, // lzw pixels
+	// trailer
+	0x3b,
+}
+
+func try(t *testing.T, b []byte, want string) {
+	_, err := DecodeAll(bytes.NewReader(b))
+	var got string
+	if err != nil {
+		got = err.Error()
+	}
+	if got != want {
+		t.Fatalf("got %v, want %v", got, want)
+	}
+}
+
+func TestBounds(t *testing.T) {
+	// Make a local copy of testGIF.
+	gif := make([]byte, len(testGIF))
+	copy(gif, testGIF)
+	// Make the bounds too big, just by one.
+	gif[32] = 2
+	want := "gif: frame bounds larger than image bounds"
+	try(t, gif, want)
+
+	// Make the bounds too small; does not trigger bounds
+	// check, but now there's too much data.
+	gif[32] = 0
+	want = "gif: too much image data"
+	try(t, gif, want)
+	gif[32] = 1
+
+	// Make the bounds really big, expect an error.
+	want = "gif: frame bounds larger than image bounds"
+	for i := 0; i < 4; i++ {
+		gif[32+i] = 0xff
+	}
+	try(t, gif, want)
+}
+
+func TestNoPalette(t *testing.T) {
+	b := &bytes.Buffer{}
+
+	// Manufacture a GIF with no palette, so any pixel at all
+	// will be invalid.
+	b.WriteString(headerStr[:len(headerStr)-3])
+	b.WriteString("\x00\x00\x00") // No global palette.
+
+	// Image descriptor: 2x1, no local palette, and 2-bit LZW literals.
+	b.WriteString("\x2c\x00\x00\x00\x00\x02\x00\x01\x00\x00\x02")
+
+	// Encode the pixels: neither is in range, because there is no palette.
+	enc := lzwEncode([]byte{0x00, 0x03})
+	b.WriteByte(byte(len(enc)))
+	b.Write(enc)
+	b.WriteByte(0x00) // An empty block signifies the end of the image data.
+
+	b.WriteString(trailerStr)
+
+	try(t, b.Bytes(), "gif: no color table")
+}
+
+func TestPixelOutsidePaletteRange(t *testing.T) {
+	for _, pval := range []byte{0, 1, 2, 3} {
+		b := &bytes.Buffer{}
+
+		// Manufacture a GIF with a 2 color palette.
+		b.WriteString(headerStr)
+		b.WriteString(paletteStr)
+
+		// Image descriptor: 2x1, no local palette, and 2-bit LZW literals.
+		b.WriteString("\x2c\x00\x00\x00\x00\x02\x00\x01\x00\x00\x02")
+
+		// Encode the pixels; some pvals trigger the expected error.
+		enc := lzwEncode([]byte{pval, pval})
+		b.WriteByte(byte(len(enc)))
+		b.Write(enc)
+		b.WriteByte(0x00) // An empty block signifies the end of the image data.
+
+		b.WriteString(trailerStr)
+
+		// No error expected, unless the pixels are beyond the 2 color palette.
+		want := ""
+		if pval >= 2 {
+			want = "gif: invalid pixel value"
+		}
+		try(t, b.Bytes(), want)
+	}
+}
+
+func TestTransparentPixelOutsidePaletteRange(t *testing.T) {
+	b := &bytes.Buffer{}
+
+	// Manufacture a GIF with a 2 color palette.
+	b.WriteString(headerStr)
+	b.WriteString(paletteStr)
+
+	// Graphic Control Extension: transparency, transparent color index = 3.
+	//
+	// This index, 3, is out of range of the global palette and there is no
+	// local palette in the subsequent image descriptor. This is an error
+	// according to the spec, but Firefox and Google Chrome seem OK with this.
+	//
+	// See golang.org/issue/15059.
+	b.WriteString("\x21\xf9\x04\x01\x00\x00\x03\x00")
+
+	// Image descriptor: 2x1, no local palette, and 2-bit LZW literals.
+	b.WriteString("\x2c\x00\x00\x00\x00\x02\x00\x01\x00\x00\x02")
+
+	// Encode the pixels.
+	enc := lzwEncode([]byte{0x03, 0x03})
+	b.WriteByte(byte(len(enc)))
+	b.Write(enc)
+	b.WriteByte(0x00) // An empty block signifies the end of the image data.
+
+	b.WriteString(trailerStr)
+
+	try(t, b.Bytes(), "")
+}
+
+func TestLoopCount(t *testing.T) {
+	testCases := []struct {
+		name      string
+		data      []byte
+		loopCount int
+	}{
+		{
+			"loopcount-missing",
+			[]byte("GIF89a000\x00000" +
+				",0\x00\x00\x00\n\x00\n\x00\x80000000" + // image 0 descriptor & color table
+				"\x02\b\xf01u\xb9\xfdal\x05\x00;"), // image 0 image data & trailer
+			-1,
+		},
+		{
+			"loopcount-0",
+			[]byte("GIF89a000\x00000" +
+				"!\xff\vNETSCAPE2.0\x03\x01\x00\x00\x00" + // loop count = 0
+				",0\x00\x00\x00\n\x00\n\x00\x80000000" + // image 0 descriptor & color table
+				"\x02\b\xf01u\xb9\xfdal\x05\x00" + // image 0 image data
+				",0\x00\x00\x00\n\x00\n\x00\x80000000" + // image 1 descriptor & color table
+				"\x02\b\xf01u\xb9\xfdal\x05\x00;"), // image 1 image data & trailer
+			0,
+		},
+		{
+			"loopcount-1",
+			[]byte("GIF89a000\x00000" +
+				"!\xff\vNETSCAPE2.0\x03\x01\x01\x00\x00" + // loop count = 1
+				",0\x00\x00\x00\n\x00\n\x00\x80000000" + // image 0 descriptor & color table
+				"\x02\b\xf01u\xb9\xfdal\x05\x00" + // image 0 image data
+				",0\x00\x00\x00\n\x00\n\x00\x80000000" + // image 1 descriptor & color table
+				"\x02\b\xf01u\xb9\xfdal\x05\x00;"), // image 1 image data & trailer
+			1,
+		},
+	}
+
+	for _, tc := range testCases {
+		t.Run(tc.name, func(t *testing.T) {
+			img, err := DecodeAll(bytes.NewReader(tc.data))
+			if err != nil {
+				t.Fatal("DecodeAll:", err)
+			}
+			w := new(bytes.Buffer)
+			err = EncodeAll(w, img)
+			if err != nil {
+				t.Fatal("EncodeAll:", err)
+			}
+			img1, err := DecodeAll(w)
+			if err != nil {
+				t.Fatal("DecodeAll:", err)
+			}
+			if img.LoopCount != tc.loopCount {
+				t.Errorf("loop count mismatch: %d vs %d", img.LoopCount, tc.loopCount)
+			}
+			if img.LoopCount != img1.LoopCount {
+				t.Errorf("loop count failed round-trip: %d vs %d", img.LoopCount, img1.LoopCount)
+			}
+		})
+	}
+}
+
+func TestUnexpectedEOF(t *testing.T) {
+	for i := len(testGIF) - 1; i >= 0; i-- {
+		_, err := DecodeAll(bytes.NewReader(testGIF[:i]))
+		if err == errNotEnough {
+			continue
+		}
+		text := ""
+		if err != nil {
+			text = err.Error()
+		}
+		if !strings.HasPrefix(text, "gif:") || !strings.HasSuffix(text, ": unexpected EOF") {
+			t.Errorf("Decode(testGIF[:%d]) = %v, want gif: ...: unexpected EOF", i, err)
+		}
+	}
+}
+
+// See golang.org/issue/22237
+func TestDecodeMemoryConsumption(t *testing.T) {
+	const frames = 3000
+	img := image.NewPaletted(image.Rectangle{Max: image.Point{1, 1}}, palette.WebSafe)
+	hugeGIF := &GIF{
+		Image:    make([]*image.Paletted, frames),
+		Delay:    make([]int, frames),
+		Disposal: make([]byte, frames),
+	}
+	for i := 0; i < frames; i++ {
+		hugeGIF.Image[i] = img
+		hugeGIF.Delay[i] = 60
+	}
+	buf := new(bytes.Buffer)
+	if err := EncodeAll(buf, hugeGIF); err != nil {
+		t.Fatal("EncodeAll:", err)
+	}
+	s0, s1 := new(runtime.MemStats), new(runtime.MemStats)
+	runtime.GC()
+	defer debug.SetGCPercent(debug.SetGCPercent(5))
+	runtime.ReadMemStats(s0)
+	if _, err := Decode(buf); err != nil {
+		t.Fatal("Decode:", err)
+	}
+	runtime.ReadMemStats(s1)
+	if heapDiff := int64(s1.HeapAlloc - s0.HeapAlloc); heapDiff > 30<<20 {
+		t.Fatalf("Decode of %d frames increased heap by %dMB", frames, heapDiff>>20)
+	}
+}
+
+func BenchmarkDecode(b *testing.B) {
+	data, err := os.ReadFile("../testdata/video-001.gif")
+	if err != nil {
+		b.Fatal(err)
+	}
+	cfg, err := DecodeConfig(bytes.NewReader(data))
+	if err != nil {
+		b.Fatal(err)
+	}
+	b.SetBytes(int64(cfg.Width * cfg.Height))
+	b.ReportAllocs()
+	b.ResetTimer()
+	for i := 0; i < b.N; i++ {
+		Decode(bytes.NewReader(data))
+	}
+}
diff --git a/src/image/gif/writer.go b/src/image/gif/writer.go
new file mode 100644
index 0000000..7220446
--- /dev/null
+++ b/src/image/gif/writer.go
@@ -0,0 +1,477 @@
+// Copyright 2013 The Go Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style
+// license that can be found in the LICENSE file.
+
+package gif
+
+import (
+	"bufio"
+	"bytes"
+	"compress/lzw"
+	"errors"
+	"image"
+	"image/color"
+	"image/color/palette"
+	"image/draw"
+	"io"
+)
+
+// Graphic control extension fields.
+const (
+	gcLabel     = 0xF9
+	gcBlockSize = 0x04
+)
+
+var log2Lookup = [8]int{2, 4, 8, 16, 32, 64, 128, 256}
+
+func log2(x int) int {
+	for i, v := range log2Lookup {
+		if x <= v {
+			return i
+		}
+	}
+	return -1
+}
+
+// Little-endian.
+func writeUint16(b []uint8, u uint16) {
+	b[0] = uint8(u)
+	b[1] = uint8(u >> 8)
+}
+
+// writer is a buffered writer.
+type writer interface {
+	Flush() error
+	io.Writer
+	io.ByteWriter
+}
+
+// encoder encodes an image to the GIF format.
+type encoder struct {
+	// w is the writer to write to. err is the first error encountered during
+	// writing. All attempted writes after the first error become no-ops.
+	w   writer
+	err error
+	// g is a reference to the data that is being encoded.
+	g GIF
+	// globalCT is the size in bytes of the global color table.
+	globalCT int
+	// buf is a scratch buffer. It must be at least 256 for the blockWriter.
+	buf              [256]byte
+	globalColorTable [3 * 256]byte
+	localColorTable  [3 * 256]byte
+}
+
+// blockWriter writes the block structure of GIF image data, which
+// comprises (n, (n bytes)) blocks, with 1 <= n <= 255. It is the
+// writer given to the LZW encoder, which is thus immune to the
+// blocking.
+type blockWriter struct {
+	e *encoder
+}
+
+func (b blockWriter) setup() {
+	b.e.buf[0] = 0
+}
+
+func (b blockWriter) Flush() error {
+	return b.e.err
+}
+
+func (b blockWriter) WriteByte(c byte) error {
+	if b.e.err != nil {
+		return b.e.err
+	}
+
+	// Append c to buffered sub-block.
+	b.e.buf[0]++
+	b.e.buf[b.e.buf[0]] = c
+	if b.e.buf[0] < 255 {
+		return nil
+	}
+
+	// Flush block
+	b.e.write(b.e.buf[:256])
+	b.e.buf[0] = 0
+	return b.e.err
+}
+
+// blockWriter must be an io.Writer for lzw.NewWriter, but this is never
+// actually called.
+func (b blockWriter) Write(data []byte) (int, error) {
+	for i, c := range data {
+		if err := b.WriteByte(c); err != nil {
+			return i, err
+		}
+	}
+	return len(data), nil
+}
+
+func (b blockWriter) close() {
+	// Write the block terminator (0x00), either by itself, or along with a
+	// pending sub-block.
+	if b.e.buf[0] == 0 {
+		b.e.writeByte(0)
+	} else {
+		n := uint(b.e.buf[0])
+		b.e.buf[n+1] = 0
+		b.e.write(b.e.buf[:n+2])
+	}
+	b.e.flush()
+}
+
+func (e *encoder) flush() {
+	if e.err != nil {
+		return
+	}
+	e.err = e.w.Flush()
+}
+
+func (e *encoder) write(p []byte) {
+	if e.err != nil {
+		return
+	}
+	_, e.err = e.w.Write(p)
+}
+
+func (e *encoder) writeByte(b byte) {
+	if e.err != nil {
+		return
+	}
+	e.err = e.w.WriteByte(b)
+}
+
+func (e *encoder) writeHeader() {
+	if e.err != nil {
+		return
+	}
+	_, e.err = io.WriteString(e.w, "GIF89a")
+	if e.err != nil {
+		return
+	}
+
+	// Logical screen width and height.
+	writeUint16(e.buf[0:2], uint16(e.g.Config.Width))
+	writeUint16(e.buf[2:4], uint16(e.g.Config.Height))
+	e.write(e.buf[:4])
+
+	if p, ok := e.g.Config.ColorModel.(color.Palette); ok && len(p) > 0 {
+		paddedSize := log2(len(p)) // Size of Global Color Table: 2^(1+n).
+		e.buf[0] = fColorTable | uint8(paddedSize)
+		e.buf[1] = e.g.BackgroundIndex
+		e.buf[2] = 0x00 // Pixel Aspect Ratio.
+		e.write(e.buf[:3])
+		var err error
+		e.globalCT, err = encodeColorTable(e.globalColorTable[:], p, paddedSize)
+		if err != nil && e.err == nil {
+			e.err = err
+			return
+		}
+		e.write(e.globalColorTable[:e.globalCT])
+	} else {
+		// All frames have a local color table, so a global color table
+		// is not needed.
+		e.buf[0] = 0x00
+		e.buf[1] = 0x00 // Background Color Index.
+		e.buf[2] = 0x00 // Pixel Aspect Ratio.
+		e.write(e.buf[:3])
+	}
+
+	// Add animation info if necessary.
+	if len(e.g.Image) > 1 && e.g.LoopCount >= 0 {
+		e.buf[0] = 0x21 // Extension Introducer.
+		e.buf[1] = 0xff // Application Label.
+		e.buf[2] = 0x0b // Block Size.
+		e.write(e.buf[:3])
+		_, err := io.WriteString(e.w, "NETSCAPE2.0") // Application Identifier.
+		if err != nil && e.err == nil {
+			e.err = err
+			return
+		}
+		e.buf[0] = 0x03 // Block Size.
+		e.buf[1] = 0x01 // Sub-block Index.
+		writeUint16(e.buf[2:4], uint16(e.g.LoopCount))
+		e.buf[4] = 0x00 // Block Terminator.
+		e.write(e.buf[:5])
+	}
+}
+
+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")
+	}
+	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 {
+			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
+	}
+
+	if len(pm.Palette) == 0 {
+		e.err = errors.New("gif: cannot encode image block with empty palette")
+		return
+	}
+
+	b := pm.Bounds()
+	if b.Min.X < 0 || b.Max.X >= 1<<16 || b.Min.Y < 0 || b.Max.Y >= 1<<16 {
+		e.err = errors.New("gif: image block is too large to encode")
+		return
+	}
+	if !b.In(image.Rectangle{Max: image.Point{e.g.Config.Width, e.g.Config.Height}}) {
+		e.err = errors.New("gif: image block is out of bounds")
+		return
+	}
+
+	transparentIndex := -1
+	for i, c := range pm.Palette {
+		if c == nil {
+			e.err = errors.New("gif: cannot encode color table with nil entries")
+			return
+		}
+		if _, _, _, a := c.RGBA(); a == 0 {
+			transparentIndex = i
+			break
+		}
+	}
+
+	if delay > 0 || disposal != 0 || transparentIndex != -1 {
+		e.buf[0] = sExtension  // Extension Introducer.
+		e.buf[1] = gcLabel     // Graphic Control Label.
+		e.buf[2] = gcBlockSize // Block Size.
+		if transparentIndex != -1 {
+			e.buf[3] = 0x01 | disposal<<2
+		} else {
+			e.buf[3] = 0x00 | disposal<<2
+		}
+		writeUint16(e.buf[4:6], uint16(delay)) // Delay Time (1/100ths of a second)
+
+		// Transparent color index.
+		if transparentIndex != -1 {
+			e.buf[6] = uint8(transparentIndex)
+		} else {
+			e.buf[6] = 0x00
+		}
+		e.buf[7] = 0x00 // Block Terminator.
+		e.write(e.buf[:8])
+	}
+	e.buf[0] = sImageDescriptor
+	writeUint16(e.buf[1:3], uint16(b.Min.X))
+	writeUint16(e.buf[3:5], uint16(b.Min.Y))
+	writeUint16(e.buf[5:7], uint16(b.Dx()))
+	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 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 {
+		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
+	if litWidth < 2 {
+		litWidth = 2
+	}
+	e.writeByte(uint8(litWidth)) // LZW Minimum Code Size.
+
+	bw := blockWriter{e: e}
+	bw.setup()
+	lzww := lzw.NewWriter(bw, lzw.LSB, litWidth)
+	if dx := b.Dx(); dx == pm.Stride {
+		_, e.err = lzww.Write(pm.Pix[:dx*b.Dy()])
+		if e.err != nil {
+			lzww.Close()
+			return
+		}
+	} else {
+		for i, y := 0, b.Min.Y; y < b.Max.Y; i, y = i+pm.Stride, y+1 {
+			_, e.err = lzww.Write(pm.Pix[i : i+dx])
+			if e.err != nil {
+				lzww.Close()
+				return
+			}
+		}
+	}
+	lzww.Close() // flush to bw
+	bw.close()   // flush to e.w
+}
+
+// Options are the encoding parameters.
+type Options struct {
+	// NumColors is the maximum number of colors used in the image.
+	// It ranges from 1 to 256.
+	NumColors int
+
+	// Quantizer is used to produce a palette with size NumColors.
+	// palette.Plan9 is used in place of a nil Quantizer.
+	Quantizer draw.Quantizer
+
+	// Drawer is used to convert the source image to the desired palette.
+	// draw.FloydSteinberg is used in place of a nil Drawer.
+	Drawer draw.Drawer
+}
+
+// EncodeAll writes the images in g to w in GIF format with the
+// given loop count and delay between frames.
+func EncodeAll(w io.Writer, g *GIF) error {
+	if len(g.Image) == 0 {
+		return errors.New("gif: must provide at least one image")
+	}
+
+	if len(g.Image) != len(g.Delay) {
+		return errors.New("gif: mismatched image and delay lengths")
+	}
+
+	e := encoder{g: *g}
+	// The GIF.Disposal, GIF.Config and GIF.BackgroundIndex fields were added
+	// in Go 1.5. Valid Go 1.4 code, such as when the Disposal field is omitted
+	// in a GIF struct literal, should still produce valid GIFs.
+	if e.g.Disposal != nil && len(e.g.Image) != len(e.g.Disposal) {
+		return errors.New("gif: mismatched image and disposal lengths")
+	}
+	if e.g.Config == (image.Config{}) {
+		p := g.Image[0].Bounds().Max
+		e.g.Config.Width = p.X
+		e.g.Config.Height = p.Y
+	} else if e.g.Config.ColorModel != nil {
+		if _, ok := e.g.Config.ColorModel.(color.Palette); !ok {
+			return errors.New("gif: GIF color model must be a color.Palette")
+		}
+	}
+
+	if ww, ok := w.(writer); ok {
+		e.w = ww
+	} else {
+		e.w = bufio.NewWriter(w)
+	}
+
+	e.writeHeader()
+	for i, pm := range g.Image {
+		disposal := uint8(0)
+		if g.Disposal != nil {
+			disposal = g.Disposal[i]
+		}
+		e.writeImageBlock(pm, g.Delay[i], disposal)
+	}
+	e.writeByte(sTrailer)
+	e.flush()
+	return e.err
+}
+
+// Encode writes the Image m to w in GIF format.
+func Encode(w io.Writer, m image.Image, o *Options) error {
+	// Check for bounds and size restrictions.
+	b := m.Bounds()
+	if b.Dx() >= 1<<16 || b.Dy() >= 1<<16 {
+		return errors.New("gif: image is too large to encode")
+	}
+
+	opts := Options{}
+	if o != nil {
+		opts = *o
+	}
+	if opts.NumColors < 1 || 256 < opts.NumColors {
+		opts.NumColors = 256
+	}
+	if opts.Drawer == nil {
+		opts.Drawer = draw.FloydSteinberg
+	}
+
+	pm, _ := m.(*image.Paletted)
+	if pm == nil {
+		if cp, ok := m.ColorModel().(color.Palette); ok {
+			pm = image.NewPaletted(b, cp)
+			for y := b.Min.Y; y < b.Max.Y; y++ {
+				for x := b.Min.X; x < b.Max.X; x++ {
+					pm.Set(x, y, cp.Convert(m.At(x, y)))
+				}
+			}
+		}
+	}
+	if pm == nil || len(pm.Palette) > opts.NumColors {
+		// Set pm to be a palettedized copy of m, including its bounds, which
+		// might not start at (0, 0).
+		//
+		// TODO: Pick a better sub-sample of the Plan 9 palette.
+		pm = image.NewPaletted(b, palette.Plan9[:opts.NumColors])
+		if opts.Quantizer != nil {
+			pm.Palette = opts.Quantizer.Quantize(make(color.Palette, 0, opts.NumColors), m)
+		}
+		opts.Drawer.Draw(pm, b, m, b.Min)
+	}
+
+	// When calling Encode instead of EncodeAll, the single-frame image is
+	// translated such that its top-left corner is (0, 0), so that the single
+	// frame completely fills the overall GIF's bounds.
+	if pm.Rect.Min != (image.Point{}) {
+		dup := *pm
+		dup.Rect = dup.Rect.Sub(dup.Rect.Min)
+		pm = &dup
+	}
+
+	return EncodeAll(w, &GIF{
+		Image: []*image.Paletted{pm},
+		Delay: []int{0},
+		Config: image.Config{
+			ColorModel: pm.Palette,
+			Width:      b.Dx(),
+			Height:     b.Dy(),
+		},
+	})
+}
diff --git a/src/image/gif/writer_test.go b/src/image/gif/writer_test.go
new file mode 100644
index 0000000..8dd2890
--- /dev/null
+++ b/src/image/gif/writer_test.go
@@ -0,0 +1,734 @@
+// Copyright 2013 The Go Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style
+// license that can be found in the LICENSE file.
+
+package gif
+
+import (
+	"bytes"
+	"image"
+	"image/color"
+	"image/color/palette"
+	"image/draw"
+	_ "image/png"
+	"io"
+	"math/rand"
+	"os"
+	"reflect"
+	"testing"
+)
+
+func readImg(filename string) (image.Image, error) {
+	f, err := os.Open(filename)
+	if err != nil {
+		return nil, err
+	}
+	defer f.Close()
+	m, _, err := image.Decode(f)
+	return m, err
+}
+
+func readGIF(filename string) (*GIF, error) {
+	f, err := os.Open(filename)
+	if err != nil {
+		return nil, err
+	}
+	defer f.Close()
+	return DecodeAll(f)
+}
+
+func delta(u0, u1 uint32) int64 {
+	d := int64(u0) - int64(u1)
+	if d < 0 {
+		return -d
+	}
+	return d
+}
+
+// averageDelta returns the average delta in RGB space. The two images must
+// have the same bounds.
+func averageDelta(m0, m1 image.Image) int64 {
+	b := m0.Bounds()
+	return averageDeltaBound(m0, m1, b, b)
+}
+
+// averageDeltaBounds returns the average delta in RGB space. The average delta is
+// calculated in the specified bounds.
+func averageDeltaBound(m0, m1 image.Image, b0, b1 image.Rectangle) int64 {
+	var sum, n int64
+	for y := b0.Min.Y; y < b0.Max.Y; y++ {
+		for x := b0.Min.X; x < b0.Max.X; x++ {
+			c0 := m0.At(x, y)
+			c1 := m1.At(x-b0.Min.X+b1.Min.X, y-b0.Min.Y+b1.Min.Y)
+			r0, g0, b0, _ := c0.RGBA()
+			r1, g1, b1, _ := c1.RGBA()
+			sum += delta(r0, r1)
+			sum += delta(g0, g1)
+			sum += delta(b0, b1)
+			n += 3
+		}
+	}
+	return sum / n
+}
+
+// lzw.NewWriter wants an interface which is basically the same thing as gif's
+// writer interface.  This ensures we're compatible.
+var _ writer = blockWriter{}
+
+var testCase = []struct {
+	filename  string
+	tolerance int64
+}{
+	{"../testdata/video-001.png", 1 << 12},
+	{"../testdata/video-001.gif", 0},
+	{"../testdata/video-001.interlaced.gif", 0},
+}
+
+func TestWriter(t *testing.T) {
+	for _, tc := range testCase {
+		m0, err := readImg(tc.filename)
+		if err != nil {
+			t.Error(tc.filename, err)
+			continue
+		}
+		var buf bytes.Buffer
+		err = Encode(&buf, m0, nil)
+		if err != nil {
+			t.Error(tc.filename, err)
+			continue
+		}
+		m1, err := Decode(&buf)
+		if err != nil {
+			t.Error(tc.filename, err)
+			continue
+		}
+		if m0.Bounds() != m1.Bounds() {
+			t.Errorf("%s, bounds differ: %v and %v", tc.filename, m0.Bounds(), m1.Bounds())
+			continue
+		}
+		// Compare the average delta to the tolerance level.
+		avgDelta := averageDelta(m0, m1)
+		if avgDelta > tc.tolerance {
+			t.Errorf("%s: average delta is too high. expected: %d, got %d", tc.filename, tc.tolerance, avgDelta)
+			continue
+		}
+	}
+}
+
+func TestSubImage(t *testing.T) {
+	m0, err := readImg("../testdata/video-001.gif")
+	if err != nil {
+		t.Fatalf("readImg: %v", err)
+	}
+	m0 = m0.(*image.Paletted).SubImage(image.Rect(0, 0, 50, 30))
+	var buf bytes.Buffer
+	err = Encode(&buf, m0, nil)
+	if err != nil {
+		t.Fatalf("Encode: %v", err)
+	}
+	m1, err := Decode(&buf)
+	if err != nil {
+		t.Fatalf("Decode: %v", err)
+	}
+	if m0.Bounds() != m1.Bounds() {
+		t.Fatalf("bounds differ: %v and %v", m0.Bounds(), m1.Bounds())
+	}
+	if averageDelta(m0, m1) != 0 {
+		t.Fatalf("images differ")
+	}
+}
+
+// palettesEqual reports whether two color.Palette values are equal, ignoring
+// any trailing opaque-black palette entries.
+func palettesEqual(p, q color.Palette) bool {
+	n := len(p)
+	if n > len(q) {
+		n = len(q)
+	}
+	for i := 0; i < n; i++ {
+		if p[i] != q[i] {
+			return false
+		}
+	}
+	for i := n; i < len(p); i++ {
+		r, g, b, a := p[i].RGBA()
+		if r != 0 || g != 0 || b != 0 || a != 0xffff {
+			return false
+		}
+	}
+	for i := n; i < len(q); i++ {
+		r, g, b, a := q[i].RGBA()
+		if r != 0 || g != 0 || b != 0 || a != 0xffff {
+			return false
+		}
+	}
+	return true
+}
+
+var frames = []string{
+	"../testdata/video-001.gif",
+	"../testdata/video-005.gray.gif",
+}
+
+func testEncodeAll(t *testing.T, go1Dot5Fields bool, useGlobalColorModel bool) {
+	const width, height = 150, 103
+
+	g0 := &GIF{
+		Image:     make([]*image.Paletted, len(frames)),
+		Delay:     make([]int, len(frames)),
+		LoopCount: 5,
+	}
+	for i, f := range frames {
+		g, err := readGIF(f)
+		if err != nil {
+			t.Fatal(f, err)
+		}
+		m := g.Image[0]
+		if m.Bounds().Dx() != width || m.Bounds().Dy() != height {
+			t.Fatalf("frame %d had unexpected bounds: got %v, want width/height = %d/%d",
+				i, m.Bounds(), width, height)
+		}
+		g0.Image[i] = m
+	}
+	// The GIF.Disposal, GIF.Config and GIF.BackgroundIndex fields were added
+	// in Go 1.5. Valid Go 1.4 or earlier code should still produce valid GIFs.
+	//
+	// On the following line, color.Model is an interface type, and
+	// color.Palette is a concrete (slice) type.
+	globalColorModel, backgroundIndex := color.Model(color.Palette(nil)), uint8(0)
+	if useGlobalColorModel {
+		globalColorModel, backgroundIndex = color.Palette(palette.WebSafe), uint8(1)
+	}
+	if go1Dot5Fields {
+		g0.Disposal = make([]byte, len(g0.Image))
+		for i := range g0.Disposal {
+			g0.Disposal[i] = DisposalNone
+		}
+		g0.Config = image.Config{
+			ColorModel: globalColorModel,
+			Width:      width,
+			Height:     height,
+		}
+		g0.BackgroundIndex = backgroundIndex
+	}
+
+	var buf bytes.Buffer
+	if err := EncodeAll(&buf, g0); err != nil {
+		t.Fatal("EncodeAll:", err)
+	}
+	encoded := buf.Bytes()
+	config, err := DecodeConfig(bytes.NewReader(encoded))
+	if err != nil {
+		t.Fatal("DecodeConfig:", err)
+	}
+	g1, err := DecodeAll(bytes.NewReader(encoded))
+	if err != nil {
+		t.Fatal("DecodeAll:", err)
+	}
+
+	if !reflect.DeepEqual(config, g1.Config) {
+		t.Errorf("DecodeConfig inconsistent with DecodeAll")
+	}
+	if !palettesEqual(g1.Config.ColorModel.(color.Palette), globalColorModel.(color.Palette)) {
+		t.Errorf("unexpected global color model")
+	}
+	if w, h := g1.Config.Width, g1.Config.Height; w != width || h != height {
+		t.Errorf("got config width * height = %d * %d, want %d * %d", w, h, width, height)
+	}
+
+	if g0.LoopCount != g1.LoopCount {
+		t.Errorf("loop counts differ: %d and %d", g0.LoopCount, g1.LoopCount)
+	}
+	if backgroundIndex != g1.BackgroundIndex {
+		t.Errorf("background indexes differ: %d and %d", backgroundIndex, g1.BackgroundIndex)
+	}
+	if len(g0.Image) != len(g1.Image) {
+		t.Fatalf("image lengths differ: %d and %d", len(g0.Image), len(g1.Image))
+	}
+	if len(g1.Image) != len(g1.Delay) {
+		t.Fatalf("image and delay lengths differ: %d and %d", len(g1.Image), len(g1.Delay))
+	}
+	if len(g1.Image) != len(g1.Disposal) {
+		t.Fatalf("image and disposal lengths differ: %d and %d", len(g1.Image), len(g1.Disposal))
+	}
+
+	for i := range g0.Image {
+		m0, m1 := g0.Image[i], g1.Image[i]
+		if m0.Bounds() != m1.Bounds() {
+			t.Errorf("frame %d: bounds differ: %v and %v", i, m0.Bounds(), m1.Bounds())
+		}
+		d0, d1 := g0.Delay[i], g1.Delay[i]
+		if d0 != d1 {
+			t.Errorf("frame %d: delay values differ: %d and %d", i, d0, d1)
+		}
+		p0, p1 := uint8(0), g1.Disposal[i]
+		if go1Dot5Fields {
+			p0 = DisposalNone
+		}
+		if p0 != p1 {
+			t.Errorf("frame %d: disposal values differ: %d and %d", i, p0, p1)
+		}
+	}
+}
+
+func TestEncodeAllGo1Dot4(t *testing.T)                 { testEncodeAll(t, false, false) }
+func TestEncodeAllGo1Dot5(t *testing.T)                 { testEncodeAll(t, true, false) }
+func TestEncodeAllGo1Dot5GlobalColorModel(t *testing.T) { testEncodeAll(t, true, true) }
+
+func TestEncodeMismatchDelay(t *testing.T) {
+	images := make([]*image.Paletted, 2)
+	for i := range images {
+		images[i] = image.NewPaletted(image.Rect(0, 0, 5, 5), palette.Plan9)
+	}
+
+	g0 := &GIF{
+		Image: images,
+		Delay: make([]int, 1),
+	}
+	if err := EncodeAll(io.Discard, g0); err == nil {
+		t.Error("expected error from mismatched delay and image slice lengths")
+	}
+
+	g1 := &GIF{
+		Image:    images,
+		Delay:    make([]int, len(images)),
+		Disposal: make([]byte, 1),
+	}
+	for i := range g1.Disposal {
+		g1.Disposal[i] = DisposalNone
+	}
+	if err := EncodeAll(io.Discard, g1); err == nil {
+		t.Error("expected error from mismatched disposal and image slice lengths")
+	}
+}
+
+func TestEncodeZeroGIF(t *testing.T) {
+	if err := EncodeAll(io.Discard, &GIF{}); err == nil {
+		t.Error("expected error from providing empty gif")
+	}
+}
+
+func TestEncodeAllFramesOutOfBounds(t *testing.T) {
+	images := []*image.Paletted{
+		image.NewPaletted(image.Rect(0, 0, 5, 5), palette.Plan9),
+		image.NewPaletted(image.Rect(2, 2, 8, 8), palette.Plan9),
+		image.NewPaletted(image.Rect(3, 3, 4, 4), palette.Plan9),
+	}
+	for _, upperBound := range []int{6, 10} {
+		g := &GIF{
+			Image:    images,
+			Delay:    make([]int, len(images)),
+			Disposal: make([]byte, len(images)),
+			Config: image.Config{
+				Width:  upperBound,
+				Height: upperBound,
+			},
+		}
+		err := EncodeAll(io.Discard, g)
+		if upperBound >= 8 {
+			if err != nil {
+				t.Errorf("upperBound=%d: %v", upperBound, err)
+			}
+		} else {
+			if err == nil {
+				t.Errorf("upperBound=%d: got nil error, want non-nil", upperBound)
+			}
+		}
+	}
+}
+
+func TestEncodeNonZeroMinPoint(t *testing.T) {
+	points := []image.Point{
+		{-8, -9},
+		{-4, -4},
+		{-3, +3},
+		{+0, +0},
+		{+2, +2},
+	}
+	for _, p := range points {
+		src := image.NewPaletted(image.Rectangle{
+			Min: p,
+			Max: p.Add(image.Point{6, 6}),
+		}, palette.Plan9)
+		var buf bytes.Buffer
+		if err := Encode(&buf, src, nil); err != nil {
+			t.Errorf("p=%v: Encode: %v", p, err)
+			continue
+		}
+		m, err := Decode(&buf)
+		if err != nil {
+			t.Errorf("p=%v: Decode: %v", p, err)
+			continue
+		}
+		if got, want := m.Bounds(), image.Rect(0, 0, 6, 6); got != want {
+			t.Errorf("p=%v: got %v, want %v", p, got, want)
+		}
+	}
+
+	// Also test having a source image (gray on the diagonal) that has a
+	// non-zero Bounds().Min, but isn't an image.Paletted.
+	{
+		p := image.Point{+2, +2}
+		src := image.NewRGBA(image.Rectangle{
+			Min: p,
+			Max: p.Add(image.Point{6, 6}),
+		})
+		src.SetRGBA(2, 2, color.RGBA{0x22, 0x22, 0x22, 0xFF})
+		src.SetRGBA(3, 3, color.RGBA{0x33, 0x33, 0x33, 0xFF})
+		src.SetRGBA(4, 4, color.RGBA{0x44, 0x44, 0x44, 0xFF})
+		src.SetRGBA(5, 5, color.RGBA{0x55, 0x55, 0x55, 0xFF})
+		src.SetRGBA(6, 6, color.RGBA{0x66, 0x66, 0x66, 0xFF})
+		src.SetRGBA(7, 7, color.RGBA{0x77, 0x77, 0x77, 0xFF})
+
+		var buf bytes.Buffer
+		if err := Encode(&buf, src, nil); err != nil {
+			t.Errorf("gray-diagonal: Encode: %v", err)
+			return
+		}
+		m, err := Decode(&buf)
+		if err != nil {
+			t.Errorf("gray-diagonal: Decode: %v", err)
+			return
+		}
+		if got, want := m.Bounds(), image.Rect(0, 0, 6, 6); got != want {
+			t.Errorf("gray-diagonal: got %v, want %v", got, want)
+			return
+		}
+
+		rednessAt := func(x int, y int) uint32 {
+			r, _, _, _ := m.At(x, y).RGBA()
+			// Shift by 8 to convert from 16 bit color to 8 bit color.
+			return r >> 8
+		}
+
+		// Round-tripping a still (non-animated) image.Image through
+		// Encode+Decode should shift the origin to (0, 0).
+		if got, want := rednessAt(0, 0), uint32(0x22); got != want {
+			t.Errorf("gray-diagonal: rednessAt(0, 0): got 0x%02x, want 0x%02x", got, want)
+		}
+		if got, want := rednessAt(5, 5), uint32(0x77); got != want {
+			t.Errorf("gray-diagonal: rednessAt(5, 5): got 0x%02x, want 0x%02x", got, want)
+		}
+	}
+}
+
+func TestEncodeImplicitConfigSize(t *testing.T) {
+	// For backwards compatibility for Go 1.4 and earlier code, the Config
+	// field is optional, and if zero, the width and height is implied by the
+	// first (and in this case only) frame's width and height.
+	//
+	// A Config only specifies a width and height (two integers) while an
+	// image.Image's Bounds method returns an image.Rectangle (four integers).
+	// For a gif.GIF, the overall bounds' top-left point is always implicitly
+	// (0, 0), and any frame whose bounds have a negative X or Y will be
+	// outside those overall bounds, so encoding should fail.
+	for _, lowerBound := range []int{-1, 0, 1} {
+		images := []*image.Paletted{
+			image.NewPaletted(image.Rect(lowerBound, lowerBound, 4, 4), palette.Plan9),
+		}
+		g := &GIF{
+			Image: images,
+			Delay: make([]int, len(images)),
+		}
+		err := EncodeAll(io.Discard, g)
+		if lowerBound >= 0 {
+			if err != nil {
+				t.Errorf("lowerBound=%d: %v", lowerBound, err)
+			}
+		} else {
+			if err == nil {
+				t.Errorf("lowerBound=%d: got nil error, want non-nil", lowerBound)
+			}
+		}
+	}
+}
+
+func TestEncodePalettes(t *testing.T) {
+	const w, h = 5, 5
+	pals := []color.Palette{{
+		color.RGBA{0x00, 0x00, 0x00, 0xff},
+		color.RGBA{0x01, 0x00, 0x00, 0xff},
+		color.RGBA{0x02, 0x00, 0x00, 0xff},
+	}, {
+		color.RGBA{0x00, 0x00, 0x00, 0xff},
+		color.RGBA{0x00, 0x01, 0x00, 0xff},
+	}, {
+		color.RGBA{0x00, 0x00, 0x03, 0xff},
+		color.RGBA{0x00, 0x00, 0x02, 0xff},
+		color.RGBA{0x00, 0x00, 0x01, 0xff},
+		color.RGBA{0x00, 0x00, 0x00, 0xff},
+	}, {
+		color.RGBA{0x10, 0x07, 0xf0, 0xff},
+		color.RGBA{0x20, 0x07, 0xf0, 0xff},
+		color.RGBA{0x30, 0x07, 0xf0, 0xff},
+		color.RGBA{0x40, 0x07, 0xf0, 0xff},
+		color.RGBA{0x50, 0x07, 0xf0, 0xff},
+	}}
+	g0 := &GIF{
+		Image: []*image.Paletted{
+			image.NewPaletted(image.Rect(0, 0, w, h), pals[0]),
+			image.NewPaletted(image.Rect(0, 0, w, h), pals[1]),
+			image.NewPaletted(image.Rect(0, 0, w, h), pals[2]),
+			image.NewPaletted(image.Rect(0, 0, w, h), pals[3]),
+		},
+		Delay:    make([]int, len(pals)),
+		Disposal: make([]byte, len(pals)),
+		Config: image.Config{
+			ColorModel: pals[2],
+			Width:      w,
+			Height:     h,
+		},
+	}
+
+	var buf bytes.Buffer
+	if err := EncodeAll(&buf, g0); err != nil {
+		t.Fatalf("EncodeAll: %v", err)
+	}
+	g1, err := DecodeAll(&buf)
+	if err != nil {
+		t.Fatalf("DecodeAll: %v", err)
+	}
+	if len(g0.Image) != len(g1.Image) {
+		t.Fatalf("image lengths differ: %d and %d", len(g0.Image), len(g1.Image))
+	}
+	for i, m := range g1.Image {
+		if got, want := m.Palette, pals[i]; !palettesEqual(got, want) {
+			t.Errorf("frame %d:\ngot  %v\nwant %v", i, got, want)
+		}
+	}
+}
+
+func TestEncodeBadPalettes(t *testing.T) {
+	const w, h = 5, 5
+	for _, n := range []int{256, 257} {
+		for _, nilColors := range []bool{false, true} {
+			pal := make(color.Palette, n)
+			if !nilColors {
+				for i := range pal {
+					pal[i] = color.Black
+				}
+			}
+
+			err := EncodeAll(io.Discard, &GIF{
+				Image: []*image.Paletted{
+					image.NewPaletted(image.Rect(0, 0, w, h), pal),
+				},
+				Delay:    make([]int, 1),
+				Disposal: make([]byte, 1),
+				Config: image.Config{
+					ColorModel: pal,
+					Width:      w,
+					Height:     h,
+				},
+			})
+
+			got := err != nil
+			want := n > 256 || nilColors
+			if got != want {
+				t.Errorf("n=%d, nilColors=%t: err != nil: got %t, want %t", n, nilColors, got, want)
+			}
+		}
+	}
+}
+
+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.
+	whole := image.NewPaletted(image.Rect(0, 0, 100, 100), palette.Plan9)
+	subImages := []image.Rectangle{
+		image.Rect(0, 0, 50, 50),
+		image.Rect(50, 0, 100, 50),
+		image.Rect(0, 50, 50, 50),
+		image.Rect(50, 50, 100, 100),
+		image.Rect(25, 25, 75, 75),
+		image.Rect(0, 0, 100, 50),
+		image.Rect(0, 50, 100, 100),
+		image.Rect(0, 0, 50, 100),
+		image.Rect(50, 0, 100, 100),
+	}
+	for _, sr := range subImages {
+		si := whole.SubImage(sr)
+		buf := bytes.NewBuffer(nil)
+		if err := Encode(buf, si, nil); err != nil {
+			t.Errorf("Encode: sr=%v: %v", sr, err)
+			continue
+		}
+		if _, err := Decode(buf); err != nil {
+			t.Errorf("Decode: sr=%v: %v", sr, err)
+		}
+	}
+}
+
+type offsetImage struct {
+	image.Image
+	Rect image.Rectangle
+}
+
+func (i offsetImage) Bounds() image.Rectangle {
+	return i.Rect
+}
+
+func TestEncodeWrappedImage(t *testing.T) {
+	m0, err := readImg("../testdata/video-001.gif")
+	if err != nil {
+		t.Fatalf("readImg: %v", err)
+	}
+
+	// Case 1: Encode a wrapped image.Image
+	buf := new(bytes.Buffer)
+	w0 := offsetImage{m0, m0.Bounds()}
+	err = Encode(buf, w0, nil)
+	if err != nil {
+		t.Fatalf("Encode: %v", err)
+	}
+	w1, err := Decode(buf)
+	if err != nil {
+		t.Fatalf("Dencode: %v", err)
+	}
+	avgDelta := averageDelta(m0, w1)
+	if avgDelta > 0 {
+		t.Fatalf("Wrapped: average delta is too high. expected: 0, got %d", avgDelta)
+	}
+
+	// Case 2: Encode a wrapped image.Image with offset
+	b0 := image.Rectangle{
+		Min: image.Point{
+			X: 128,
+			Y: 64,
+		},
+		Max: image.Point{
+			X: 256,
+			Y: 128,
+		},
+	}
+	w0 = offsetImage{m0, b0}
+	buf = new(bytes.Buffer)
+	err = Encode(buf, w0, nil)
+	if err != nil {
+		t.Fatalf("Encode: %v", err)
+	}
+	w1, err = Decode(buf)
+	if err != nil {
+		t.Fatalf("Dencode: %v", err)
+	}
+
+	b1 := image.Rectangle{
+		Min: image.Point{
+			X: 0,
+			Y: 0,
+		},
+		Max: image.Point{
+			X: 128,
+			Y: 64,
+		},
+	}
+	avgDelta = averageDeltaBound(m0, w1, b0, b1)
+	if avgDelta > 0 {
+		t.Fatalf("Wrapped and offset: average delta is too high. expected: 0, got %d", avgDelta)
+	}
+}
+
+func BenchmarkEncodeRandomPaletted(b *testing.B) {
+	paletted := image.NewPaletted(image.Rect(0, 0, 640, 480), palette.Plan9)
+	rnd := rand.New(rand.NewSource(123))
+	for i := range paletted.Pix {
+		paletted.Pix[i] = uint8(rnd.Intn(256))
+	}
+
+	b.SetBytes(640 * 480 * 1)
+	b.ReportAllocs()
+	b.ResetTimer()
+	for i := 0; i < b.N; i++ {
+		Encode(io.Discard, paletted, nil)
+	}
+}
+
+func BenchmarkEncodeRandomRGBA(b *testing.B) {
+	rgba := image.NewRGBA(image.Rect(0, 0, 640, 480))
+	bo := rgba.Bounds()
+	rnd := rand.New(rand.NewSource(123))
+	for y := bo.Min.Y; y < bo.Max.Y; y++ {
+		for x := bo.Min.X; x < bo.Max.X; x++ {
+			rgba.SetRGBA(x, y, color.RGBA{
+				uint8(rnd.Intn(256)),
+				uint8(rnd.Intn(256)),
+				uint8(rnd.Intn(256)),
+				255,
+			})
+		}
+	}
+
+	b.SetBytes(640 * 480 * 4)
+	b.ReportAllocs()
+	b.ResetTimer()
+	for i := 0; i < b.N; i++ {
+		Encode(io.Discard, rgba, nil)
+	}
+}
+
+func BenchmarkEncodeRealisticPaletted(b *testing.B) {
+	img, err := readImg("../testdata/video-001.png")
+	if err != nil {
+		b.Fatalf("readImg: %v", err)
+	}
+	bo := img.Bounds()
+	paletted := image.NewPaletted(bo, palette.Plan9)
+	draw.Draw(paletted, bo, img, bo.Min, draw.Src)
+
+	b.SetBytes(int64(bo.Dx() * bo.Dy() * 1))
+	b.ReportAllocs()
+	b.ResetTimer()
+	for i := 0; i < b.N; i++ {
+		Encode(io.Discard, paletted, nil)
+	}
+}
+
+func BenchmarkEncodeRealisticRGBA(b *testing.B) {
+	img, err := readImg("../testdata/video-001.png")
+	if err != nil {
+		b.Fatalf("readImg: %v", err)
+	}
+	bo := img.Bounds()
+	// Converting img to rgba is redundant for video-001.png, which is already
+	// in the RGBA format, but for those copy/pasting this benchmark (but
+	// changing the source image), the conversion ensures that we're still
+	// benchmarking encoding an RGBA image.
+	rgba := image.NewRGBA(bo)
+	draw.Draw(rgba, bo, img, bo.Min, draw.Src)
+
+	b.SetBytes(int64(bo.Dx() * bo.Dy() * 4))
+	b.ReportAllocs()
+	b.ResetTimer()
+	for i := 0; i < b.N; i++ {
+		Encode(io.Discard, rgba, nil)
+	}
+}