// 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 (
	
	
	
	
	
	
	
	
	
)

// Graphic control extension fields.
const (
	gcLabel     = 0xF9
	gcBlockSize = 0x04
)

var log2Lookup = [8]int{2, 4, 8, 16, 32, 64, 128, 256}

func log2( int) int {
	for ,  := range log2Lookup {
		if  <=  {
			return 
		}
	}
	return -1
}

// Little-endian.
func writeUint16( []uint8,  uint16) {
	[0] = uint8()
	[1] = uint8( >> 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 ( blockWriter) () {
	.e.buf[0] = 0
}

func ( blockWriter) () error {
	return .e.err
}

func ( blockWriter) ( byte) error {
	if .e.err != nil {
		return .e.err
	}

	// Append c to buffered sub-block.
	.e.buf[0]++
	.e.buf[.e.buf[0]] = 
	if .e.buf[0] < 255 {
		return nil
	}

	// Flush block
	.e.write(.e.buf[:256])
	.e.buf[0] = 0
	return .e.err
}

// blockWriter must be an io.Writer for lzw.NewWriter, but this is never
// actually called.
func ( blockWriter) ( []byte) (int, error) {
	for ,  := range  {
		if  := .WriteByte();  != nil {
			return , 
		}
	}
	return len(), nil
}

func ( blockWriter) () {
	// Write the block terminator (0x00), either by itself, or along with a
	// pending sub-block.
	if .e.buf[0] == 0 {
		.e.writeByte(0)
	} else {
		 := uint(.e.buf[0])
		.e.buf[+1] = 0
		.e.write(.e.buf[:+2])
	}
	.e.flush()
}

func ( *encoder) () {
	if .err != nil {
		return
	}
	.err = .w.Flush()
}

func ( *encoder) ( []byte) {
	if .err != nil {
		return
	}
	_, .err = .w.Write()
}

func ( *encoder) ( byte) {
	if .err != nil {
		return
	}
	.err = .w.WriteByte()
}

func ( *encoder) () {
	if .err != nil {
		return
	}
	_, .err = io.WriteString(.w, "GIF89a")
	if .err != nil {
		return
	}

	// Logical screen width and height.
	writeUint16(.buf[0:2], uint16(.g.Config.Width))
	writeUint16(.buf[2:4], uint16(.g.Config.Height))
	.write(.buf[:4])

	if ,  := .g.Config.ColorModel.(color.Palette);  && len() > 0 {
		 := log2(len()) // Size of Global Color Table: 2^(1+n).
		.buf[0] = fColorTable | uint8()
		.buf[1] = .g.BackgroundIndex
		.buf[2] = 0x00 // Pixel Aspect Ratio.
		.write(.buf[:3])
		var  error
		.globalCT,  = encodeColorTable(.globalColorTable[:], , )
		if  != nil && .err == nil {
			.err = 
			return
		}
		.write(.globalColorTable[:.globalCT])
	} else {
		// All frames have a local color table, so a global color table
		// is not needed.
		.buf[0] = 0x00
		.buf[1] = 0x00 // Background Color Index.
		.buf[2] = 0x00 // Pixel Aspect Ratio.
		.write(.buf[:3])
	}

	// Add animation info if necessary.
	if len(.g.Image) > 1 && .g.LoopCount >= 0 {
		.buf[0] = 0x21 // Extension Introducer.
		.buf[1] = 0xff // Application Label.
		.buf[2] = 0x0b // Block Size.
		.write(.buf[:3])
		,  := io.WriteString(.w, "NETSCAPE2.0") // Application Identifier.
		if  != nil && .err == nil {
			.err = 
			return
		}
		.buf[0] = 0x03 // Block Size.
		.buf[1] = 0x01 // Sub-block Index.
		writeUint16(.buf[2:4], uint16(.g.LoopCount))
		.buf[4] = 0x00 // Block Terminator.
		.write(.buf[:5])
	}
}

func encodeColorTable( []byte,  color.Palette,  int) (int, error) {
	if uint() >= uint(len(log2Lookup)) {
		return 0, errors.New("gif: cannot encode color table with more than 256 entries")
	}
	for ,  := range  {
		if  == nil {
			return 0, errors.New("gif: cannot encode color table with nil entries")
		}
		var , ,  uint8
		// It is most likely that the palette is full of color.RGBAs, so they
		// get a fast path.
		if ,  := .(color.RGBA);  {
			, ,  = .R, .G, .B
		} else {
			, , ,  := .RGBA()
			, ,  = uint8(>>8), uint8(>>8), uint8(>>8)
		}
		[3*+0] = 
		[3*+1] = 
		[3*+2] = 
	}
	 := log2Lookup[]
	if  > len() {
		// Pad with black.
		 := [3*len() : 3*]
		for  := range  {
			[] = 0
		}
	}
	return 3 * , nil
}

func ( *encoder) (,  int) bool {
	 := 3 * 
	if  >= 0 {
		 := 3 * 
		return bytes.Equal(.globalColorTable[:], .localColorTable[:]) &&
			bytes.Equal(.globalColorTable[+3:], .localColorTable[+3:])
	}
	return bytes.Equal(.globalColorTable[:], .localColorTable[:])
}

func ( *encoder) ( *image.Paletted,  int,  byte) {
	if .err != nil {
		return
	}

	if len(.Palette) == 0 {
		.err = errors.New("gif: cannot encode image block with empty palette")
		return
	}

	 := .Bounds()
	if .Min.X < 0 || .Max.X >= 1<<16 || .Min.Y < 0 || .Max.Y >= 1<<16 {
		.err = errors.New("gif: image block is too large to encode")
		return
	}
	if !.In(image.Rectangle{Max: image.Point{.g.Config.Width, .g.Config.Height}}) {
		.err = errors.New("gif: image block is out of bounds")
		return
	}

	 := -1
	for ,  := range .Palette {
		if  == nil {
			.err = errors.New("gif: cannot encode color table with nil entries")
			return
		}
		if , , ,  := .RGBA();  == 0 {
			 = 
			break
		}
	}

	if  > 0 ||  != 0 ||  != -1 {
		.buf[0] = sExtension  // Extension Introducer.
		.buf[1] = gcLabel     // Graphic Control Label.
		.buf[2] = gcBlockSize // Block Size.
		if  != -1 {
			.buf[3] = 0x01 | <<2
		} else {
			.buf[3] = 0x00 | <<2
		}
		writeUint16(.buf[4:6], uint16()) // Delay Time (1/100ths of a second)

		// Transparent color index.
		if  != -1 {
			.buf[6] = uint8()
		} else {
			.buf[6] = 0x00
		}
		.buf[7] = 0x00 // Block Terminator.
		.write(.buf[:8])
	}
	.buf[0] = sImageDescriptor
	writeUint16(.buf[1:3], uint16(.Min.X))
	writeUint16(.buf[3:5], uint16(.Min.Y))
	writeUint16(.buf[5:7], uint16(.Dx()))
	writeUint16(.buf[7:9], uint16(.Dy()))
	.write(.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...
	 := log2(len(.Palette)) // Size of Local Color Table: 2^(1+n).
	if ,  := .g.Config.ColorModel.(color.Palette);  && len(.Palette) <= len() && &[0] == &.Palette[0] {
		.writeByte(0) // Use the global color table.
	} else {
		,  := encodeColorTable(.localColorTable[:], .Palette, )
		if  != nil {
			if .err == nil {
				.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  <= .globalCT && .colorTablesMatch(len(.Palette), ) {
			.writeByte(0) // Use the global color table.
		} else {
			// Use a local color table.
			.writeByte(fColorTable | uint8())
			.write(.localColorTable[:])
		}
	}

	 :=  + 1
	if  < 2 {
		 = 2
	}
	.writeByte(uint8()) // LZW Minimum Code Size.

	 := blockWriter{e: }
	.setup()
	 := lzw.NewWriter(, lzw.LSB, )
	if  := .Dx();  == .Stride {
		_, .err = .Write(.Pix[:*.Dy()])
		if .err != nil {
			.Close()
			return
		}
	} else {
		for ,  := 0, .Min.Y;  < .Max.Y; ,  = +.Stride, +1 {
			_, .err = .Write(.Pix[ : +])
			if .err != nil {
				.Close()
				return
			}
		}
	}
	.Close() // flush to 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 ( io.Writer,  *GIF) error {
	if len(.Image) == 0 {
		return errors.New("gif: must provide at least one image")
	}

	if len(.Image) != len(.Delay) {
		return errors.New("gif: mismatched image and delay lengths")
	}

	 := encoder{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 .g.Disposal != nil && len(.g.Image) != len(.g.Disposal) {
		return errors.New("gif: mismatched image and disposal lengths")
	}
	if .g.Config == (image.Config{}) {
		 := .Image[0].Bounds().Max
		.g.Config.Width = .X
		.g.Config.Height = .Y
	} else if .g.Config.ColorModel != nil {
		if ,  := .g.Config.ColorModel.(color.Palette); ! {
			return errors.New("gif: GIF color model must be a color.Palette")
		}
	}

	if ,  := .(writer);  {
		.w = 
	} else {
		.w = bufio.NewWriter()
	}

	.writeHeader()
	for ,  := range .Image {
		 := uint8(0)
		if .Disposal != nil {
			 = .Disposal[]
		}
		.writeImageBlock(, .Delay[], )
	}
	.writeByte(sTrailer)
	.flush()
	return .err
}

// Encode writes the Image m to w in GIF format.
func ( io.Writer,  image.Image,  *Options) error {
	// Check for bounds and size restrictions.
	 := .Bounds()
	if .Dx() >= 1<<16 || .Dy() >= 1<<16 {
		return errors.New("gif: image is too large to encode")
	}

	 := Options{}
	if  != nil {
		 = *
	}
	if .NumColors < 1 || 256 < .NumColors {
		.NumColors = 256
	}
	if .Drawer == nil {
		.Drawer = draw.FloydSteinberg
	}

	,  := .(*image.Paletted)
	if  == nil {
		if ,  := .ColorModel().(color.Palette);  {
			 = image.NewPaletted(, )
			for  := .Min.Y;  < .Max.Y; ++ {
				for  := .Min.X;  < .Max.X; ++ {
					.Set(, , .Convert(.At(, )))
				}
			}
		}
	}
	if  == nil || len(.Palette) > .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.
		 = image.NewPaletted(, palette.Plan9[:.NumColors])
		if .Quantizer != nil {
			.Palette = .Quantizer.Quantize(make(color.Palette, 0, .NumColors), )
		}
		.Drawer.Draw(, , , .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 .Rect.Min != (image.Point{}) {
		 := *
		.Rect = .Rect.Sub(.Rect.Min)
		 = &
	}

	return EncodeAll(, &GIF{
		Image: []*image.Paletted{},
		Delay: []int{0},
		Config: image.Config{
			ColorModel: .Palette,
			Width:      .Dx(),
			Height:     .Dy(),
		},
	})
}