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.ByteReader 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 [blockReader.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  			if !keepAllFrames && len(d.image) == 1 {
   254  				return nil
   255  			}
   256  
   257  		case sTrailer:
   258  			if len(d.image) == 0 {
   259  				return fmt.Errorf("gif: missing image data")
   260  			}
   261  			return nil
   262  
   263  		default:
   264  			return fmt.Errorf("gif: unknown block type: 0x%.2x", c)
   265  		}
   266  	}
   267  }
   268  
   269  func (d *decoder) readHeaderAndScreenDescriptor() error {
   270  	err := readFull(d.r, d.tmp[:13])
   271  	if err != nil {
   272  		return fmt.Errorf("gif: reading header: %v", err)
   273  	}
   274  	d.vers = string(d.tmp[:6])
   275  	if d.vers != "GIF87a" && d.vers != "GIF89a" {
   276  		return fmt.Errorf("gif: can't recognize format %q", d.vers)
   277  	}
   278  	d.width = int(d.tmp[6]) + int(d.tmp[7])<<8
   279  	d.height = int(d.tmp[8]) + int(d.tmp[9])<<8
   280  	if fields := d.tmp[10]; fields&fColorTable != 0 {
   281  		d.backgroundIndex = d.tmp[11]
   282  		// readColorTable overwrites the contents of d.tmp, but that's OK.
   283  		if d.globalColorTable, err = d.readColorTable(fields); err != nil {
   284  			return err
   285  		}
   286  	}
   287  	// d.tmp[12] is the Pixel Aspect Ratio, which is ignored.
   288  	return nil
   289  }
   290  
   291  func (d *decoder) readColorTable(fields byte) (color.Palette, error) {
   292  	n := 1 << (1 + uint(fields&fColorTableBitsMask))
   293  	err := readFull(d.r, d.tmp[:3*n])
   294  	if err != nil {
   295  		return nil, fmt.Errorf("gif: reading color table: %s", err)
   296  	}
   297  	j, p := 0, make(color.Palette, n)
   298  	for i := range p {
   299  		p[i] = color.RGBA{d.tmp[j+0], d.tmp[j+1], d.tmp[j+2], 0xFF}
   300  		j += 3
   301  	}
   302  	return p, nil
   303  }
   304  
   305  func (d *decoder) readExtension() error {
   306  	extension, err := readByte(d.r)
   307  	if err != nil {
   308  		return fmt.Errorf("gif: reading extension: %v", err)
   309  	}
   310  	size := 0
   311  	switch extension {
   312  	case eText:
   313  		size = 13
   314  	case eGraphicControl:
   315  		return d.readGraphicControl()
   316  	case eComment:
   317  		// nothing to do but read the data.
   318  	case eApplication:
   319  		b, err := readByte(d.r)
   320  		if err != nil {
   321  			return fmt.Errorf("gif: reading extension: %v", err)
   322  		}
   323  		// The spec requires size be 11, but Adobe sometimes uses 10.
   324  		size = int(b)
   325  	default:
   326  		return fmt.Errorf("gif: unknown extension 0x%.2x", extension)
   327  	}
   328  	if size > 0 {
   329  		if err := readFull(d.r, d.tmp[:size]); err != nil {
   330  			return fmt.Errorf("gif: reading extension: %v", err)
   331  		}
   332  	}
   333  
   334  	// Application Extension with "NETSCAPE2.0" as string and 1 in data means
   335  	// this extension defines a loop count.
   336  	if extension == eApplication && string(d.tmp[:size]) == "NETSCAPE2.0" {
   337  		n, err := d.readBlock()
   338  		if err != nil {
   339  			return fmt.Errorf("gif: reading extension: %v", err)
   340  		}
   341  		if n == 0 {
   342  			return nil
   343  		}
   344  		if n == 3 && d.tmp[0] == 1 {
   345  			d.loopCount = int(d.tmp[1]) | int(d.tmp[2])<<8
   346  		}
   347  	}
   348  	for {
   349  		n, err := d.readBlock()
   350  		if err != nil {
   351  			return fmt.Errorf("gif: reading extension: %v", err)
   352  		}
   353  		if n == 0 {
   354  			return nil
   355  		}
   356  	}
   357  }
   358  
   359  func (d *decoder) readGraphicControl() error {
   360  	if err := readFull(d.r, d.tmp[:6]); err != nil {
   361  		return fmt.Errorf("gif: can't read graphic control: %s", err)
   362  	}
   363  	if d.tmp[0] != 4 {
   364  		return fmt.Errorf("gif: invalid graphic control extension block size: %d", d.tmp[0])
   365  	}
   366  	flags := d.tmp[1]
   367  	d.disposalMethod = (flags & gcDisposalMethodMask) >> 2
   368  	d.delayTime = int(d.tmp[2]) | int(d.tmp[3])<<8
   369  	if flags&gcTransparentColorSet != 0 {
   370  		d.transparentIndex = d.tmp[4]
   371  		d.hasTransparentIndex = true
   372  	}
   373  	if d.tmp[5] != 0 {
   374  		return fmt.Errorf("gif: invalid graphic control extension block terminator: %d", d.tmp[5])
   375  	}
   376  	return nil
   377  }
   378  
   379  func (d *decoder) readImageDescriptor(keepAllFrames bool) error {
   380  	m, err := d.newImageFromDescriptor()
   381  	if err != nil {
   382  		return err
   383  	}
   384  	useLocalColorTable := d.imageFields&fColorTable != 0
   385  	if useLocalColorTable {
   386  		m.Palette, err = d.readColorTable(d.imageFields)
   387  		if err != nil {
   388  			return err
   389  		}
   390  	} else {
   391  		if d.globalColorTable == nil {
   392  			return errors.New("gif: no color table")
   393  		}
   394  		m.Palette = d.globalColorTable
   395  	}
   396  	if d.hasTransparentIndex {
   397  		if !useLocalColorTable {
   398  			// Clone the global color table.
   399  			m.Palette = append(color.Palette(nil), d.globalColorTable...)
   400  		}
   401  		if ti := int(d.transparentIndex); ti < len(m.Palette) {
   402  			m.Palette[ti] = color.RGBA{}
   403  		} else {
   404  			// The transparentIndex is out of range, which is an error
   405  			// according to the spec, but Firefox and Google Chrome
   406  			// seem OK with this, so we enlarge the palette with
   407  			// transparent colors. See golang.org/issue/15059.
   408  			p := make(color.Palette, ti+1)
   409  			copy(p, m.Palette)
   410  			for i := len(m.Palette); i < len(p); i++ {
   411  				p[i] = color.RGBA{}
   412  			}
   413  			m.Palette = p
   414  		}
   415  	}
   416  	litWidth, err := readByte(d.r)
   417  	if err != nil {
   418  		return fmt.Errorf("gif: reading image data: %v", err)
   419  	}
   420  	if litWidth < 2 || litWidth > 8 {
   421  		return fmt.Errorf("gif: pixel size in decode out of range: %d", litWidth)
   422  	}
   423  	// A wonderfully Go-like piece of magic.
   424  	br := &blockReader{d: d}
   425  	lzwr := lzw.NewReader(br, lzw.LSB, int(litWidth))
   426  	defer lzwr.Close()
   427  	if err = readFull(lzwr, m.Pix); err != nil {
   428  		if err != io.ErrUnexpectedEOF {
   429  			return fmt.Errorf("gif: reading image data: %v", err)
   430  		}
   431  		return errNotEnough
   432  	}
   433  	// In theory, both lzwr and br should be exhausted. Reading from them
   434  	// should yield (0, io.EOF).
   435  	//
   436  	// The spec (Appendix F - Compression), says that "An End of
   437  	// Information code... must be the last code output by the encoder
   438  	// for an image". In practice, though, giflib (a widely used C
   439  	// library) does not enforce this, so we also accept lzwr returning
   440  	// io.ErrUnexpectedEOF (meaning that the encoded stream hit io.EOF
   441  	// before the LZW decoder saw an explicit end code), provided that
   442  	// the io.ReadFull call above successfully read len(m.Pix) bytes.
   443  	// See https://golang.org/issue/9856 for an example GIF.
   444  	if n, err := lzwr.Read(d.tmp[256:257]); n != 0 || (err != io.EOF && err != io.ErrUnexpectedEOF) {
   445  		if err != nil {
   446  			return fmt.Errorf("gif: reading image data: %v", err)
   447  		}
   448  		return errTooMuch
   449  	}
   450  
   451  	// In practice, some GIFs have an extra byte in the data sub-block
   452  	// stream, which we ignore. See https://golang.org/issue/16146.
   453  	if err := br.close(); err == errTooMuch {
   454  		return errTooMuch
   455  	} else if err != nil {
   456  		return fmt.Errorf("gif: reading image data: %v", err)
   457  	}
   458  
   459  	// Check that the color indexes are inside the palette.
   460  	if len(m.Palette) < 256 {
   461  		for _, pixel := range m.Pix {
   462  			if int(pixel) >= len(m.Palette) {
   463  				return errBadPixel
   464  			}
   465  		}
   466  	}
   467  
   468  	// Undo the interlacing if necessary.
   469  	if d.imageFields&fInterlace != 0 {
   470  		uninterlace(m)
   471  	}
   472  
   473  	if keepAllFrames || len(d.image) == 0 {
   474  		d.image = append(d.image, m)
   475  		d.delay = append(d.delay, d.delayTime)
   476  		d.disposal = append(d.disposal, d.disposalMethod)
   477  	}
   478  	// The GIF89a spec, Section 23 (Graphic Control Extension) says:
   479  	// "The scope of this extension is the first graphic rendering block
   480  	// to follow." We therefore reset the GCE fields to zero.
   481  	d.delayTime = 0
   482  	d.hasTransparentIndex = false
   483  	return nil
   484  }
   485  
   486  func (d *decoder) newImageFromDescriptor() (*image.Paletted, error) {
   487  	if err := readFull(d.r, d.tmp[:9]); err != nil {
   488  		return nil, fmt.Errorf("gif: can't read image descriptor: %s", err)
   489  	}
   490  	left := int(d.tmp[0]) + int(d.tmp[1])<<8
   491  	top := int(d.tmp[2]) + int(d.tmp[3])<<8
   492  	width := int(d.tmp[4]) + int(d.tmp[5])<<8
   493  	height := int(d.tmp[6]) + int(d.tmp[7])<<8
   494  	d.imageFields = d.tmp[8]
   495  
   496  	// The GIF89a spec, Section 20 (Image Descriptor) says: "Each image must
   497  	// fit within the boundaries of the Logical Screen, as defined in the
   498  	// Logical Screen Descriptor."
   499  	//
   500  	// This is conceptually similar to testing
   501  	//	frameBounds := image.Rect(left, top, left+width, top+height)
   502  	//	imageBounds := image.Rect(0, 0, d.width, d.height)
   503  	//	if !frameBounds.In(imageBounds) { etc }
   504  	// but the semantics of the Go image.Rectangle type is that r.In(s) is true
   505  	// whenever r is an empty rectangle, even if r.Min.X > s.Max.X. Here, we
   506  	// want something stricter.
   507  	//
   508  	// Note that, by construction, left >= 0 && top >= 0, so we only have to
   509  	// explicitly compare frameBounds.Max (left+width, top+height) against
   510  	// imageBounds.Max (d.width, d.height) and not frameBounds.Min (left, top)
   511  	// against imageBounds.Min (0, 0).
   512  	if left+width > d.width || top+height > d.height {
   513  		return nil, errors.New("gif: frame bounds larger than image bounds")
   514  	}
   515  	return image.NewPaletted(image.Rectangle{
   516  		Min: image.Point{left, top},
   517  		Max: image.Point{left + width, top + height},
   518  	}, nil), nil
   519  }
   520  
   521  func (d *decoder) readBlock() (int, error) {
   522  	n, err := readByte(d.r)
   523  	if n == 0 || err != nil {
   524  		return 0, err
   525  	}
   526  	if err := readFull(d.r, d.tmp[:n]); err != nil {
   527  		return 0, err
   528  	}
   529  	return int(n), nil
   530  }
   531  
   532  // interlaceScan defines the ordering for a pass of the interlace algorithm.
   533  type interlaceScan struct {
   534  	skip, start int
   535  }
   536  
   537  // interlacing represents the set of scans in an interlaced GIF image.
   538  var interlacing = []interlaceScan{
   539  	{8, 0}, // Group 1 : Every 8th. row, starting with row 0.
   540  	{8, 4}, // Group 2 : Every 8th. row, starting with row 4.
   541  	{4, 2}, // Group 3 : Every 4th. row, starting with row 2.
   542  	{2, 1}, // Group 4 : Every 2nd. row, starting with row 1.
   543  }
   544  
   545  // uninterlace rearranges the pixels in m to account for interlaced input.
   546  func uninterlace(m *image.Paletted) {
   547  	var nPix []uint8
   548  	dx := m.Bounds().Dx()
   549  	dy := m.Bounds().Dy()
   550  	nPix = make([]uint8, dx*dy)
   551  	offset := 0 // steps through the input by sequential scan lines.
   552  	for _, pass := range interlacing {
   553  		nOffset := pass.start * dx // steps through the output as defined by pass.
   554  		for y := pass.start; y < dy; y += pass.skip {
   555  			copy(nPix[nOffset:nOffset+dx], m.Pix[offset:offset+dx])
   556  			offset += dx
   557  			nOffset += dx * pass.skip
   558  		}
   559  	}
   560  	m.Pix = nPix
   561  }
   562  
   563  // Decode reads a GIF image from r and returns the first embedded
   564  // image as an [image.Image].
   565  func Decode(r io.Reader) (image.Image, error) {
   566  	var d decoder
   567  	if err := d.decode(r, false, false); err != nil {
   568  		return nil, err
   569  	}
   570  	return d.image[0], nil
   571  }
   572  
   573  // GIF represents the possibly multiple images stored in a GIF file.
   574  type GIF struct {
   575  	Image []*image.Paletted // The successive images.
   576  	Delay []int             // The successive delay times, one per frame, in 100ths of a second.
   577  	// LoopCount controls the number of times an animation will be
   578  	// restarted during display.
   579  	// A LoopCount of 0 means to loop forever.
   580  	// A LoopCount of -1 means to show each frame only once.
   581  	// Otherwise, the animation is looped LoopCount+1 times.
   582  	LoopCount int
   583  	// Disposal is the successive disposal methods, one per frame. For
   584  	// backwards compatibility, a nil Disposal is valid to pass to EncodeAll,
   585  	// and implies that each frame's disposal method is 0 (no disposal
   586  	// specified).
   587  	Disposal []byte
   588  	// Config is the global color table (palette), width and height. A nil or
   589  	// empty-color.Palette Config.ColorModel means that each frame has its own
   590  	// color table and there is no global color table. Each frame's bounds must
   591  	// be within the rectangle defined by the two points (0, 0) and
   592  	// (Config.Width, Config.Height).
   593  	//
   594  	// For backwards compatibility, a zero-valued Config is valid to pass to
   595  	// EncodeAll, and implies that the overall GIF's width and height equals
   596  	// the first frame's bounds' Rectangle.Max point.
   597  	Config image.Config
   598  	// BackgroundIndex is the background index in the global color table, for
   599  	// use with the DisposalBackground disposal method.
   600  	BackgroundIndex byte
   601  }
   602  
   603  // DecodeAll reads a GIF image from r and returns the sequential frames
   604  // and timing information.
   605  func DecodeAll(r io.Reader) (*GIF, error) {
   606  	var d decoder
   607  	if err := d.decode(r, false, true); err != nil {
   608  		return nil, err
   609  	}
   610  	gif := &GIF{
   611  		Image:     d.image,
   612  		LoopCount: d.loopCount,
   613  		Delay:     d.delay,
   614  		Disposal:  d.disposal,
   615  		Config: image.Config{
   616  			ColorModel: d.globalColorTable,
   617  			Width:      d.width,
   618  			Height:     d.height,
   619  		},
   620  		BackgroundIndex: d.backgroundIndex,
   621  	}
   622  	return gif, nil
   623  }
   624  
   625  // DecodeConfig returns the global color model and dimensions of a GIF image
   626  // without decoding the entire image.
   627  func DecodeConfig(r io.Reader) (image.Config, error) {
   628  	var d decoder
   629  	if err := d.decode(r, true, false); err != nil {
   630  		return image.Config{}, err
   631  	}
   632  	return image.Config{
   633  		ColorModel: d.globalColorTable,
   634  		Width:      d.width,
   635  		Height:     d.height,
   636  	}, nil
   637  }
   638  
   639  func init() {
   640  	image.RegisterFormat("gif", "GIF8?a", Decode, DecodeConfig)
   641  }
   642
View as plain text