Adding upstream version 1.20.14.upstream/1.20.14upstream

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

1 files changed, 477 insertions, 0 deletions

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(),
+		},
+	})
+}