Source file src/image/gif/reader.go

     1	// Copyright 2011 The Go Authors. All rights reserved.
     2	// Use of this source code is governed by a BSD-style
     3	// license that can be found in the LICENSE file.
     4	
     5	// Package gif implements a GIF image decoder and encoder.
     6	//
     7	// The GIF specification is at https://www.w3.org/Graphics/GIF/spec-gif89a.txt.
     8	package gif
     9	
    10	import (
    11		"bufio"
    12		"compress/lzw"
    13		"errors"
    14		"fmt"
    15		"image"
    16		"image/color"
    17		"io"
    18	)
    19	
    20	var (
    21		errNotEnough = errors.New("gif: not enough image data")
    22		errTooMuch   = errors.New("gif: too much image data")
    23		errBadPixel  = errors.New("gif: invalid pixel value")
    24	)
    25	
    26	// If the io.Reader does not also have ReadByte, then decode will introduce its own buffering.
    27	type reader interface {
    28		io.Reader
    29		io.ByteReader
    30	}
    31	
    32	// Masks etc.
    33	const (
    34		// Fields.
    35		fColorTable         = 1 << 7
    36		fInterlace          = 1 << 6
    37		fColorTableBitsMask = 7
    38	
    39		// Graphic control flags.
    40		gcTransparentColorSet = 1 << 0
    41		gcDisposalMethodMask  = 7 << 2
    42	)
    43	
    44	// Disposal Methods.
    45	const (
    46		DisposalNone       = 0x01
    47		DisposalBackground = 0x02
    48		DisposalPrevious   = 0x03
    49	)
    50	
    51	// Section indicators.
    52	const (
    53		sExtension       = 0x21
    54		sImageDescriptor = 0x2C
    55		sTrailer         = 0x3B
    56	)
    57	
    58	// Extensions.
    59	const (
    60		eText           = 0x01 // Plain Text
    61		eGraphicControl = 0xF9 // Graphic Control
    62		eComment        = 0xFE // Comment
    63		eApplication    = 0xFF // Application
    64	)
    65	
    66	func readFull(r io.Reader, b []byte) error {
    67		_, err := io.ReadFull(r, b)
    68		if err == io.EOF {
    69			err = io.ErrUnexpectedEOF
    70		}
    71		return err
    72	}
    73	
    74	func readByte(r io.ByteReader) (byte, error) {
    75		b, err := r.ReadByte()
    76		if err == io.EOF {
    77			err = io.ErrUnexpectedEOF
    78		}
    79		return b, err
    80	}
    81	
    82	// decoder is the type used to decode a GIF file.
    83	type decoder struct {
    84		r reader
    85	
    86		// From header.
    87		vers            string
    88		width           int
    89		height          int
    90		loopCount       int
    91		delayTime       int
    92		backgroundIndex byte
    93		disposalMethod  byte
    94	
    95		// From image descriptor.
    96		imageFields byte
    97	
    98		// From graphics control.
    99		transparentIndex    byte
   100		hasTransparentIndex bool
   101	
   102		// Computed.
   103		globalColorTable color.Palette
   104	
   105		// Used when decoding.
   106		delay    []int
   107		disposal []byte
   108		image    []*image.Paletted
   109		tmp      [1024]byte // must be at least 768 so we can read color table
   110	}
   111	
   112	// blockReader parses the block structure of GIF image data, which comprises
   113	// (n, (n bytes)) blocks, with 1 <= n <= 255. It is the reader given to the
   114	// LZW decoder, which is thus immune to the blocking. After the LZW decoder
   115	// completes, there will be a 0-byte block remaining (0, ()), which is
   116	// consumed when checking that the blockReader is exhausted.
   117	//
   118	// To avoid the allocation of a bufio.Reader for the lzw Reader, blockReader
   119	// implements io.ReadByte and buffers blocks into the decoder's "tmp" buffer.
   120	type blockReader struct {
   121		d    *decoder
   122		i, j uint8 // d.tmp[i:j] contains the buffered bytes
   123		err  error
   124	}
   125	
   126	func (b *blockReader) fill() {
   127		if b.err != nil {
   128			return
   129		}
   130		b.j, b.err = readByte(b.d.r)
   131		if b.j == 0 && b.err == nil {
   132			b.err = io.EOF
   133		}
   134		if b.err != nil {
   135			return
   136		}
   137	
   138		b.i = 0
   139		b.err = readFull(b.d.r, b.d.tmp[:b.j])
   140		if b.err != nil {
   141			b.j = 0
   142		}
   143	}
   144	
   145	func (b *blockReader) ReadByte() (byte, error) {
   146		if b.i == b.j {
   147			b.fill()
   148			if b.err != nil {
   149				return 0, b.err
   150			}
   151		}
   152	
   153		c := b.d.tmp[b.i]
   154		b.i++
   155		return c, nil
   156	}
   157	
   158	// blockReader must implement io.Reader, but its Read shouldn't ever actually
   159	// be called in practice. The compress/lzw package will only call ReadByte.
   160	func (b *blockReader) Read(p []byte) (int, error) {
   161		if len(p) == 0 || b.err != nil {
   162			return 0, b.err
   163		}
   164		if b.i == b.j {
   165			b.fill()
   166			if b.err != nil {
   167				return 0, b.err
   168			}
   169		}
   170	
   171		n := copy(p, b.d.tmp[b.i:b.j])
   172		b.i += uint8(n)
   173		return n, nil
   174	}
   175	
   176	// close primarily detects whether or not a block terminator was encountered
   177	// after reading a sequence of data sub-blocks. It allows at most one trailing
   178	// sub-block worth of data. I.e., if some number of bytes exist in one sub-block
   179	// following the end of LZW data, the very next sub-block must be the block
   180	// terminator. If the very end of LZW data happened to fill one sub-block, at
   181	// most one more sub-block of length 1 may exist before the block-terminator.
   182	// These accommodations allow us to support GIFs created by less strict encoders.
   183	// See https://golang.org/issue/16146.
   184	func (b *blockReader) close() error {
   185		if b.err == io.EOF {
   186			// A clean block-sequence terminator was encountered while reading.
   187			return nil
   188		} else if b.err != nil {
   189			// Some other error was encountered while reading.
   190			return b.err
   191		}
   192	
   193		if b.i == b.j {
   194			// We reached the end of a sub block reading LZW data. We'll allow at
   195			// most one more sub block of data with a length of 1 byte.
   196			b.fill()
   197			if b.err == io.EOF {
   198				return nil
   199			} else if b.err != nil {
   200				return b.err
   201			} else if b.j > 1 {
   202				return errTooMuch
   203			}
   204		}
   205	
   206		// Part of a sub-block remains buffered. We expect that the next attempt to
   207		// buffer a sub-block will reach the block terminator.
   208		b.fill()
   209		if b.err == io.EOF {
   210			return nil
   211		} else if b.err != nil {
   212			return b.err
   213		}
   214	
   215		return errTooMuch
   216	}
   217	
   218	// decode reads a GIF image from r and stores the result in d.
   219	func (d *decoder) decode(r io.Reader, configOnly, keepAllFrames bool) error {
   220		// Add buffering if r does not provide ReadByte.
   221		if rr, ok := r.(reader); ok {
   222			d.r = rr
   223		} else {
   224			d.r = bufio.NewReader(r)
   225		}
   226	
   227		d.loopCount = -1
   228	
   229		err := d.readHeaderAndScreenDescriptor()
   230		if err != nil {
   231			return err
   232		}
   233		if configOnly {
   234			return nil
   235		}
   236	
   237		for {
   238			c, err := readByte(d.r)
   239			if err != nil {
   240				return fmt.Errorf("gif: reading frames: %v", err)
   241			}
   242			switch c {
   243			case sExtension:
   244				if err = d.readExtension(); err != nil {
   245					return err
   246				}
   247	
   248			case sImageDescriptor:
   249				if err = d.readImageDescriptor(keepAllFrames); err != nil {
   250					return err
   251				}
   252	
   253			case sTrailer:
   254				if len(d.image) == 0 {
   255					return fmt.Errorf("gif: missing image data")
   256				}
   257				return nil
   258	
   259			default:
   260				return fmt.Errorf("gif: unknown block type: 0x%.2x", c)
   261			}
   262		}
   263	}
   264	
   265	func (d *decoder) readHeaderAndScreenDescriptor() error {
   266		err := readFull(d.r, d.tmp[:13])
   267		if err != nil {
   268			return fmt.Errorf("gif: reading header: %v", err)
   269		}
   270		d.vers = string(d.tmp[:6])
   271		if d.vers != "GIF87a" && d.vers != "GIF89a" {
   272			return fmt.Errorf("gif: can't recognize format %q", d.vers)
   273		}
   274		d.width = int(d.tmp[6]) + int(d.tmp[7])<<8
   275		d.height = int(d.tmp[8]) + int(d.tmp[9])<<8
   276		if fields := d.tmp[10]; fields&fColorTable != 0 {
   277			d.backgroundIndex = d.tmp[11]
   278			// readColorTable overwrites the contents of d.tmp, but that's OK.
   279			if d.globalColorTable, err = d.readColorTable(fields); err != nil {
   280				return err
   281			}
   282		}
   283		// d.tmp[12] is the Pixel Aspect Ratio, which is ignored.
   284		return nil
   285	}
   286	
   287	func (d *decoder) readColorTable(fields byte) (color.Palette, error) {
   288		n := 1 << (1 + uint(fields&fColorTableBitsMask))
   289		err := readFull(d.r, d.tmp[:3*n])
   290		if err != nil {
   291			return nil, fmt.Errorf("gif: reading color table: %s", err)
   292		}
   293		j, p := 0, make(color.Palette, n)
   294		for i := range p {
   295			p[i] = color.RGBA{d.tmp[j+0], d.tmp[j+1], d.tmp[j+2], 0xFF}
   296			j += 3
   297		}
   298		return p, nil
   299	}
   300	
   301	func (d *decoder) readExtension() error {
   302		extension, err := readByte(d.r)
   303		if err != nil {
   304			return fmt.Errorf("gif: reading extension: %v", err)
   305		}
   306		size := 0
   307		switch extension {
   308		case eText:
   309			size = 13
   310		case eGraphicControl:
   311			return d.readGraphicControl()
   312		case eComment:
   313			// nothing to do but read the data.
   314		case eApplication:
   315			b, err := readByte(d.r)
   316			if err != nil {
   317				return fmt.Errorf("gif: reading extension: %v", err)
   318			}
   319			// The spec requires size be 11, but Adobe sometimes uses 10.
   320			size = int(b)
   321		default:
   322			return fmt.Errorf("gif: unknown extension 0x%.2x", extension)
   323		}
   324		if size > 0 {
   325			if err := readFull(d.r, d.tmp[:size]); err != nil {
   326				return fmt.Errorf("gif: reading extension: %v", err)
   327			}
   328		}
   329	
   330		// Application Extension with "NETSCAPE2.0" as string and 1 in data means
   331		// this extension defines a loop count.
   332		if extension == eApplication && string(d.tmp[:size]) == "NETSCAPE2.0" {
   333			n, err := d.readBlock()
   334			if err != nil {
   335				return fmt.Errorf("gif: reading extension: %v", err)
   336			}
   337			if n == 0 {
   338				return nil
   339			}
   340			if n == 3 && d.tmp[0] == 1 {
   341				d.loopCount = int(d.tmp[1]) | int(d.tmp[2])<<8
   342			}
   343		}
   344		for {
   345			n, err := d.readBlock()
   346			if err != nil {
   347				return fmt.Errorf("gif: reading extension: %v", err)
   348			}
   349			if n == 0 {
   350				return nil
   351			}
   352		}
   353	}
   354	
   355	func (d *decoder) readGraphicControl() error {
   356		if err := readFull(d.r, d.tmp[:6]); err != nil {
   357			return fmt.Errorf("gif: can't read graphic control: %s", err)
   358		}
   359		if d.tmp[0] != 4 {
   360			return fmt.Errorf("gif: invalid graphic control extension block size: %d", d.tmp[0])
   361		}
   362		flags := d.tmp[1]
   363		d.disposalMethod = (flags & gcDisposalMethodMask) >> 2
   364		d.delayTime = int(d.tmp[2]) | int(d.tmp[3])<<8
   365		if flags&gcTransparentColorSet != 0 {
   366			d.transparentIndex = d.tmp[4]
   367			d.hasTransparentIndex = true
   368		}
   369		if d.tmp[5] != 0 {
   370			return fmt.Errorf("gif: invalid graphic control extension block terminator: %d", d.tmp[5])
   371		}
   372		return nil
   373	}
   374	
   375	func (d *decoder) readImageDescriptor(keepAllFrames bool) error {
   376		m, err := d.newImageFromDescriptor()
   377		if err != nil {
   378			return err
   379		}
   380		useLocalColorTable := d.imageFields&fColorTable != 0
   381		if useLocalColorTable {
   382			m.Palette, err = d.readColorTable(d.imageFields)
   383			if err != nil {
   384				return err
   385			}
   386		} else {
   387			if d.globalColorTable == nil {
   388				return errors.New("gif: no color table")
   389			}
   390			m.Palette = d.globalColorTable
   391		}
   392		if d.hasTransparentIndex {
   393			if !useLocalColorTable {
   394				// Clone the global color table.
   395				m.Palette = append(color.Palette(nil), d.globalColorTable...)
   396			}
   397			if ti := int(d.transparentIndex); ti < len(m.Palette) {
   398				m.Palette[ti] = color.RGBA{}
   399			} else {
   400				// The transparentIndex is out of range, which is an error
   401				// according to the spec, but Firefox and Google Chrome
   402				// seem OK with this, so we enlarge the palette with
   403				// transparent colors. See golang.org/issue/15059.
   404				p := make(color.Palette, ti+1)
   405				copy(p, m.Palette)
   406				for i := len(m.Palette); i < len(p); i++ {
   407					p[i] = color.RGBA{}
   408				}
   409				m.Palette = p
   410			}
   411		}
   412		litWidth, err := readByte(d.r)
   413		if err != nil {
   414			return fmt.Errorf("gif: reading image data: %v", err)
   415		}
   416		if litWidth < 2 || litWidth > 8 {
   417			return fmt.Errorf("gif: pixel size in decode out of range: %d", litWidth)
   418		}
   419		// A wonderfully Go-like piece of magic.
   420		br := &blockReader{d: d}
   421		lzwr := lzw.NewReader(br, lzw.LSB, int(litWidth))
   422		defer lzwr.Close()
   423		if err = readFull(lzwr, m.Pix); err != nil {
   424			if err != io.ErrUnexpectedEOF {
   425				return fmt.Errorf("gif: reading image data: %v", err)
   426			}
   427			return errNotEnough
   428		}
   429		// In theory, both lzwr and br should be exhausted. Reading from them
   430		// should yield (0, io.EOF).
   431		//
   432		// The spec (Appendix F - Compression), says that "An End of
   433		// Information code... must be the last code output by the encoder
   434		// for an image". In practice, though, giflib (a widely used C
   435		// library) does not enforce this, so we also accept lzwr returning
   436		// io.ErrUnexpectedEOF (meaning that the encoded stream hit io.EOF
   437		// before the LZW decoder saw an explicit end code), provided that
   438		// the io.ReadFull call above successfully read len(m.Pix) bytes.
   439		// See https://golang.org/issue/9856 for an example GIF.
   440		if n, err := lzwr.Read(d.tmp[256:257]); n != 0 || (err != io.EOF && err != io.ErrUnexpectedEOF) {
   441			if err != nil {
   442				return fmt.Errorf("gif: reading image data: %v", err)
   443			}
   444			return errTooMuch
   445		}
   446	
   447		// In practice, some GIFs have an extra byte in the data sub-block
   448		// stream, which we ignore. See https://golang.org/issue/16146.
   449		if err := br.close(); err == errTooMuch {
   450			return errTooMuch
   451		} else if err != nil {
   452			return fmt.Errorf("gif: reading image data: %v", err)
   453		}
   454	
   455		// Check that the color indexes are inside the palette.
   456		if len(m.Palette) < 256 {
   457			for _, pixel := range m.Pix {
   458				if int(pixel) >= len(m.Palette) {
   459					return errBadPixel
   460				}
   461			}
   462		}
   463	
   464		// Undo the interlacing if necessary.
   465		if d.imageFields&fInterlace != 0 {
   466			uninterlace(m)
   467		}
   468	
   469		if keepAllFrames || len(d.image) == 0 {
   470			d.image = append(d.image, m)
   471			d.delay = append(d.delay, d.delayTime)
   472			d.disposal = append(d.disposal, d.disposalMethod)
   473		}
   474		// The GIF89a spec, Section 23 (Graphic Control Extension) says:
   475		// "The scope of this extension is the first graphic rendering block
   476		// to follow." We therefore reset the GCE fields to zero.
   477		d.delayTime = 0
   478		d.hasTransparentIndex = false
   479		return nil
   480	}
   481	
   482	func (d *decoder) newImageFromDescriptor() (*image.Paletted, error) {
   483		if err := readFull(d.r, d.tmp[:9]); err != nil {
   484			return nil, fmt.Errorf("gif: can't read image descriptor: %s", err)
   485		}
   486		left := int(d.tmp[0]) + int(d.tmp[1])<<8
   487		top := int(d.tmp[2]) + int(d.tmp[3])<<8
   488		width := int(d.tmp[4]) + int(d.tmp[5])<<8
   489		height := int(d.tmp[6]) + int(d.tmp[7])<<8
   490		d.imageFields = d.tmp[8]
   491	
   492		// The GIF89a spec, Section 20 (Image Descriptor) says: "Each image must
   493		// fit within the boundaries of the Logical Screen, as defined in the
   494		// Logical Screen Descriptor."
   495		//
   496		// This is conceptually similar to testing
   497		//	frameBounds := image.Rect(left, top, left+width, top+height)
   498		//	imageBounds := image.Rect(0, 0, d.width, d.height)
   499		//	if !frameBounds.In(imageBounds) { etc }
   500		// but the semantics of the Go image.Rectangle type is that r.In(s) is true
   501		// whenever r is an empty rectangle, even if r.Min.X > s.Max.X. Here, we
   502		// want something stricter.
   503		//
   504		// Note that, by construction, left >= 0 && top >= 0, so we only have to
   505		// explicitly compare frameBounds.Max (left+width, top+height) against
   506		// imageBounds.Max (d.width, d.height) and not frameBounds.Min (left, top)
   507		// against imageBounds.Min (0, 0).
   508		if left+width > d.width || top+height > d.height {
   509			return nil, errors.New("gif: frame bounds larger than image bounds")
   510		}
   511		return image.NewPaletted(image.Rectangle{
   512			Min: image.Point{left, top},
   513			Max: image.Point{left + width, top + height},
   514		}, nil), nil
   515	}
   516	
   517	func (d *decoder) readBlock() (int, error) {
   518		n, err := readByte(d.r)
   519		if n == 0 || err != nil {
   520			return 0, err
   521		}
   522		if err := readFull(d.r, d.tmp[:n]); err != nil {
   523			return 0, err
   524		}
   525		return int(n), nil
   526	}
   527	
   528	// interlaceScan defines the ordering for a pass of the interlace algorithm.
   529	type interlaceScan struct {
   530		skip, start int
   531	}
   532	
   533	// interlacing represents the set of scans in an interlaced GIF image.
   534	var interlacing = []interlaceScan{
   535		{8, 0}, // Group 1 : Every 8th. row, starting with row 0.
   536		{8, 4}, // Group 2 : Every 8th. row, starting with row 4.
   537		{4, 2}, // Group 3 : Every 4th. row, starting with row 2.
   538		{2, 1}, // Group 4 : Every 2nd. row, starting with row 1.
   539	}
   540	
   541	// uninterlace rearranges the pixels in m to account for interlaced input.
   542	func uninterlace(m *image.Paletted) {
   543		var nPix []uint8
   544		dx := m.Bounds().Dx()
   545		dy := m.Bounds().Dy()
   546		nPix = make([]uint8, dx*dy)
   547		offset := 0 // steps through the input by sequential scan lines.
   548		for _, pass := range interlacing {
   549			nOffset := pass.start * dx // steps through the output as defined by pass.
   550			for y := pass.start; y < dy; y += pass.skip {
   551				copy(nPix[nOffset:nOffset+dx], m.Pix[offset:offset+dx])
   552				offset += dx
   553				nOffset += dx * pass.skip
   554			}
   555		}
   556		m.Pix = nPix
   557	}
   558	
   559	// Decode reads a GIF image from r and returns the first embedded
   560	// image as an image.Image.
   561	func Decode(r io.Reader) (image.Image, error) {
   562		var d decoder
   563		if err := d.decode(r, false, false); err != nil {
   564			return nil, err
   565		}
   566		return d.image[0], nil
   567	}
   568	
   569	// GIF represents the possibly multiple images stored in a GIF file.
   570	type GIF struct {
   571		Image []*image.Paletted // The successive images.
   572		Delay []int             // The successive delay times, one per frame, in 100ths of a second.
   573		// LoopCount controls the number of times an animation will be
   574		// restarted during display.
   575		// A LoopCount of 0 means to loop forever.
   576		// A LoopCount of -1 means to show each frame only once.
   577		// Otherwise, the animation is looped LoopCount+1 times.
   578		LoopCount int
   579		// Disposal is the successive disposal methods, one per frame. For
   580		// backwards compatibility, a nil Disposal is valid to pass to EncodeAll,
   581		// and implies that each frame's disposal method is 0 (no disposal
   582		// specified).
   583		Disposal []byte
   584		// Config is the global color table (palette), width and height. A nil or
   585		// empty-color.Palette Config.ColorModel means that each frame has its own
   586		// color table and there is no global color table. Each frame's bounds must
   587		// be within the rectangle defined by the two points (0, 0) and
   588		// (Config.Width, Config.Height).
   589		//
   590		// For backwards compatibility, a zero-valued Config is valid to pass to
   591		// EncodeAll, and implies that the overall GIF's width and height equals
   592		// the first frame's bounds' Rectangle.Max point.
   593		Config image.Config
   594		// BackgroundIndex is the background index in the global color table, for
   595		// use with the DisposalBackground disposal method.
   596		BackgroundIndex byte
   597	}
   598	
   599	// DecodeAll reads a GIF image from r and returns the sequential frames
   600	// and timing information.
   601	func DecodeAll(r io.Reader) (*GIF, error) {
   602		var d decoder
   603		if err := d.decode(r, false, true); err != nil {
   604			return nil, err
   605		}
   606		gif := &GIF{
   607			Image:     d.image,
   608			LoopCount: d.loopCount,
   609			Delay:     d.delay,
   610			Disposal:  d.disposal,
   611			Config: image.Config{
   612				ColorModel: d.globalColorTable,
   613				Width:      d.width,
   614				Height:     d.height,
   615			},
   616			BackgroundIndex: d.backgroundIndex,
   617		}
   618		return gif, nil
   619	}
   620	
   621	// DecodeConfig returns the global color model and dimensions of a GIF image
   622	// without decoding the entire image.
   623	func DecodeConfig(r io.Reader) (image.Config, error) {
   624		var d decoder
   625		if err := d.decode(r, true, false); err != nil {
   626			return image.Config{}, err
   627		}
   628		return image.Config{
   629			ColorModel: d.globalColorTable,
   630			Width:      d.width,
   631			Height:     d.height,
   632		}, nil
   633	}
   634	
   635	func init() {
   636		image.RegisterFormat("gif", "GIF8?a", Decode, DecodeConfig)
   637	}
   638	

View as plain text