reader.mx raw
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 []byte
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 = append([]byte(nil), 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 && 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 = []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