1// Copyright 2009 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 png implements a PNG image decoder and encoder.
6//
7// The PNG specification is at http://www.w3.org/TR/PNG/.
8package png
9
10import (
11	"compress/zlib"
12	"encoding/binary"
13	"fmt"
14	"hash"
15	"hash/crc32"
16	"image"
17	"image/color"
18	"io"
19)
20
21// Color type, as per the PNG spec.
22const (
23	ctGrayscale      = 0
24	ctTrueColor      = 2
25	ctPaletted       = 3
26	ctGrayscaleAlpha = 4
27	ctTrueColorAlpha = 6
28)
29
30// A cb is a combination of color type and bit depth.
31const (
32	cbInvalid = iota
33	cbG1
34	cbG2
35	cbG4
36	cbG8
37	cbGA8
38	cbTC8
39	cbP1
40	cbP2
41	cbP4
42	cbP8
43	cbTCA8
44	cbG16
45	cbGA16
46	cbTC16
47	cbTCA16
48)
49
50func cbPaletted(cb int) bool {
51	return cbP1 <= cb && cb <= cbP8
52}
53
54// Filter type, as per the PNG spec.
55const (
56	ftNone    = 0
57	ftSub     = 1
58	ftUp      = 2
59	ftAverage = 3
60	ftPaeth   = 4
61	nFilter   = 5
62)
63
64// Interlace type.
65const (
66	itNone  = 0
67	itAdam7 = 1
68)
69
70// interlaceScan defines the placement and size of a pass for Adam7 interlacing.
71type interlaceScan struct {
72	xFactor, yFactor, xOffset, yOffset int
73}
74
75// interlacing defines Adam7 interlacing, with 7 passes of reduced images.
76// See http://www.w3.org/TR/PNG/#8Interlace
77var interlacing = []interlaceScan{
78	{8, 8, 0, 0},
79	{8, 8, 4, 0},
80	{4, 8, 0, 4},
81	{4, 4, 2, 0},
82	{2, 4, 0, 2},
83	{2, 2, 1, 0},
84	{1, 2, 0, 1},
85}
86
87// Decoding stage.
88// The PNG specification says that the IHDR, PLTE (if present), tRNS (if
89// present), IDAT and IEND chunks must appear in that order. There may be
90// multiple IDAT chunks, and IDAT chunks must be sequential (i.e. they may not
91// have any other chunks between them).
92// http://www.w3.org/TR/PNG/#5ChunkOrdering
93const (
94	dsStart = iota
95	dsSeenIHDR
96	dsSeenPLTE
97	dsSeentRNS
98	dsSeenIDAT
99	dsSeenIEND
100)
101
102const pngHeader = "\x89PNG\r\n\x1a\n"
103
104type decoder struct {
105	r             io.Reader
106	img           image.Image
107	crc           hash.Hash32
108	width, height int
109	depth         int
110	palette       color.Palette
111	cb            int
112	stage         int
113	idatLength    uint32
114	tmp           [3 * 256]byte
115	interlace     int
116
117	// useTransparent and transparent are used for grayscale and truecolor
118	// transparency, as opposed to palette transparency.
119	useTransparent bool
120	transparent    [6]byte
121}
122
123// A FormatError reports that the input is not a valid PNG.
124type FormatError string
125
126func (e FormatError) Error() string { return "png: invalid format: " + string(e) }
127
128var chunkOrderError = FormatError("chunk out of order")
129
130// An UnsupportedError reports that the input uses a valid but unimplemented PNG feature.
131type UnsupportedError string
132
133func (e UnsupportedError) Error() string { return "png: unsupported feature: " + string(e) }
134
135func min(a, b int) int {
136	if a < b {
137		return a
138	}
139	return b
140}
141
142func (d *decoder) parseIHDR(length uint32) error {
143	if length != 13 {
144		return FormatError("bad IHDR length")
145	}
146	if _, err := io.ReadFull(d.r, d.tmp[:13]); err != nil {
147		return err
148	}
149	d.crc.Write(d.tmp[:13])
150	if d.tmp[10] != 0 {
151		return UnsupportedError("compression method")
152	}
153	if d.tmp[11] != 0 {
154		return UnsupportedError("filter method")
155	}
156	if d.tmp[12] != itNone && d.tmp[12] != itAdam7 {
157		return FormatError("invalid interlace method")
158	}
159	d.interlace = int(d.tmp[12])
160
161	w := int32(binary.BigEndian.Uint32(d.tmp[0:4]))
162	h := int32(binary.BigEndian.Uint32(d.tmp[4:8]))
163	if w <= 0 || h <= 0 {
164		return FormatError("non-positive dimension")
165	}
166	nPixels := int64(w) * int64(h)
167	if nPixels != int64(int(nPixels)) {
168		return UnsupportedError("dimension overflow")
169	}
170	// There can be up to 8 bytes per pixel, for 16 bits per channel RGBA.
171	if nPixels != (nPixels*8)/8 {
172		return UnsupportedError("dimension overflow")
173	}
174
175	d.cb = cbInvalid
176	d.depth = int(d.tmp[8])
177	switch d.depth {
178	case 1:
179		switch d.tmp[9] {
180		case ctGrayscale:
181			d.cb = cbG1
182		case ctPaletted:
183			d.cb = cbP1
184		}
185	case 2:
186		switch d.tmp[9] {
187		case ctGrayscale:
188			d.cb = cbG2
189		case ctPaletted:
190			d.cb = cbP2
191		}
192	case 4:
193		switch d.tmp[9] {
194		case ctGrayscale:
195			d.cb = cbG4
196		case ctPaletted:
197			d.cb = cbP4
198		}
199	case 8:
200		switch d.tmp[9] {
201		case ctGrayscale:
202			d.cb = cbG8
203		case ctTrueColor:
204			d.cb = cbTC8
205		case ctPaletted:
206			d.cb = cbP8
207		case ctGrayscaleAlpha:
208			d.cb = cbGA8
209		case ctTrueColorAlpha:
210			d.cb = cbTCA8
211		}
212	case 16:
213		switch d.tmp[9] {
214		case ctGrayscale:
215			d.cb = cbG16
216		case ctTrueColor:
217			d.cb = cbTC16
218		case ctGrayscaleAlpha:
219			d.cb = cbGA16
220		case ctTrueColorAlpha:
221			d.cb = cbTCA16
222		}
223	}
224	if d.cb == cbInvalid {
225		return UnsupportedError(fmt.Sprintf("bit depth %d, color type %d", d.tmp[8], d.tmp[9]))
226	}
227	d.width, d.height = int(w), int(h)
228	return d.verifyChecksum()
229}
230
231func (d *decoder) parsePLTE(length uint32) error {
232	np := int(length / 3) // The number of palette entries.
233	if length%3 != 0 || np <= 0 || np > 256 || np > 1<<uint(d.depth) {
234		return FormatError("bad PLTE length")
235	}
236	n, err := io.ReadFull(d.r, d.tmp[:3*np])
237	if err != nil {
238		return err
239	}
240	d.crc.Write(d.tmp[:n])
241	switch d.cb {
242	case cbP1, cbP2, cbP4, cbP8:
243		d.palette = make(color.Palette, 256)
244		for i := 0; i < np; i++ {
245			d.palette[i] = color.RGBA{d.tmp[3*i+0], d.tmp[3*i+1], d.tmp[3*i+2], 0xff}
246		}
247		for i := np; i < 256; i++ {
248			// Initialize the rest of the palette to opaque black. The spec (section
249			// 11.2.3) says that "any out-of-range pixel value found in the image data
250			// is an error", but some real-world PNG files have out-of-range pixel
251			// values. We fall back to opaque black, the same as libpng 1.5.13;
252			// ImageMagick 6.5.7 returns an error.
253			d.palette[i] = color.RGBA{0x00, 0x00, 0x00, 0xff}
254		}
255		d.palette = d.palette[:np]
256	case cbTC8, cbTCA8, cbTC16, cbTCA16:
257		// As per the PNG spec, a PLTE chunk is optional (and for practical purposes,
258		// ignorable) for the ctTrueColor and ctTrueColorAlpha color types (section 4.1.2).
259	default:
260		return FormatError("PLTE, color type mismatch")
261	}
262	return d.verifyChecksum()
263}
264
265func (d *decoder) parsetRNS(length uint32) error {
266	switch d.cb {
267	case cbG1, cbG2, cbG4, cbG8, cbG16:
268		if length != 2 {
269			return FormatError("bad tRNS length")
270		}
271		n, err := io.ReadFull(d.r, d.tmp[:length])
272		if err != nil {
273			return err
274		}
275		d.crc.Write(d.tmp[:n])
276
277		copy(d.transparent[:], d.tmp[:length])
278		switch d.cb {
279		case cbG1:
280			d.transparent[1] *= 0xff
281		case cbG2:
282			d.transparent[1] *= 0x55
283		case cbG4:
284			d.transparent[1] *= 0x11
285		}
286		d.useTransparent = true
287
288	case cbTC8, cbTC16:
289		if length != 6 {
290			return FormatError("bad tRNS length")
291		}
292		n, err := io.ReadFull(d.r, d.tmp[:length])
293		if err != nil {
294			return err
295		}
296		d.crc.Write(d.tmp[:n])
297
298		copy(d.transparent[:], d.tmp[:length])
299		d.useTransparent = true
300
301	case cbP1, cbP2, cbP4, cbP8:
302		if length > 256 {
303			return FormatError("bad tRNS length")
304		}
305		n, err := io.ReadFull(d.r, d.tmp[:length])
306		if err != nil {
307			return err
308		}
309		d.crc.Write(d.tmp[:n])
310
311		if len(d.palette) < n {
312			d.palette = d.palette[:n]
313		}
314		for i := 0; i < n; i++ {
315			rgba := d.palette[i].(color.RGBA)
316			d.palette[i] = color.NRGBA{rgba.R, rgba.G, rgba.B, d.tmp[i]}
317		}
318
319	default:
320		return FormatError("tRNS, color type mismatch")
321	}
322	return d.verifyChecksum()
323}
324
325// Read presents one or more IDAT chunks as one continuous stream (minus the
326// intermediate chunk headers and footers). If the PNG data looked like:
327//   ... len0 IDAT xxx crc0 len1 IDAT yy crc1 len2 IEND crc2
328// then this reader presents xxxyy. For well-formed PNG data, the decoder state
329// immediately before the first Read call is that d.r is positioned between the
330// first IDAT and xxx, and the decoder state immediately after the last Read
331// call is that d.r is positioned between yy and crc1.
332func (d *decoder) Read(p []byte) (int, error) {
333	if len(p) == 0 {
334		return 0, nil
335	}
336	for d.idatLength == 0 {
337		// We have exhausted an IDAT chunk. Verify the checksum of that chunk.
338		if err := d.verifyChecksum(); err != nil {
339			return 0, err
340		}
341		// Read the length and chunk type of the next chunk, and check that
342		// it is an IDAT chunk.
343		if _, err := io.ReadFull(d.r, d.tmp[:8]); err != nil {
344			return 0, err
345		}
346		d.idatLength = binary.BigEndian.Uint32(d.tmp[:4])
347		if string(d.tmp[4:8]) != "IDAT" {
348			return 0, FormatError("not enough pixel data")
349		}
350		d.crc.Reset()
351		d.crc.Write(d.tmp[4:8])
352	}
353	if int(d.idatLength) < 0 {
354		return 0, UnsupportedError("IDAT chunk length overflow")
355	}
356	n, err := d.r.Read(p[:min(len(p), int(d.idatLength))])
357	d.crc.Write(p[:n])
358	d.idatLength -= uint32(n)
359	return n, err
360}
361
362// decode decodes the IDAT data into an image.
363func (d *decoder) decode() (image.Image, error) {
364	r, err := zlib.NewReader(d)
365	if err != nil {
366		return nil, err
367	}
368	defer r.Close()
369	var img image.Image
370	if d.interlace == itNone {
371		img, err = d.readImagePass(r, 0, false)
372		if err != nil {
373			return nil, err
374		}
375	} else if d.interlace == itAdam7 {
376		// Allocate a blank image of the full size.
377		img, err = d.readImagePass(nil, 0, true)
378		if err != nil {
379			return nil, err
380		}
381		for pass := 0; pass < 7; pass++ {
382			imagePass, err := d.readImagePass(r, pass, false)
383			if err != nil {
384				return nil, err
385			}
386			if imagePass != nil {
387				d.mergePassInto(img, imagePass, pass)
388			}
389		}
390	}
391
392	// Check for EOF, to verify the zlib checksum.
393	n := 0
394	for i := 0; n == 0 && err == nil; i++ {
395		if i == 100 {
396			return nil, io.ErrNoProgress
397		}
398		n, err = r.Read(d.tmp[:1])
399	}
400	if err != nil && err != io.EOF {
401		return nil, FormatError(err.Error())
402	}
403	if n != 0 || d.idatLength != 0 {
404		return nil, FormatError("too much pixel data")
405	}
406
407	return img, nil
408}
409
410// readImagePass reads a single image pass, sized according to the pass number.
411func (d *decoder) readImagePass(r io.Reader, pass int, allocateOnly bool) (image.Image, error) {
412	bitsPerPixel := 0
413	pixOffset := 0
414	var (
415		gray     *image.Gray
416		rgba     *image.RGBA
417		paletted *image.Paletted
418		nrgba    *image.NRGBA
419		gray16   *image.Gray16
420		rgba64   *image.RGBA64
421		nrgba64  *image.NRGBA64
422		img      image.Image
423	)
424	width, height := d.width, d.height
425	if d.interlace == itAdam7 && !allocateOnly {
426		p := interlacing[pass]
427		// Add the multiplication factor and subtract one, effectively rounding up.
428		width = (width - p.xOffset + p.xFactor - 1) / p.xFactor
429		height = (height - p.yOffset + p.yFactor - 1) / p.yFactor
430		// A PNG image can't have zero width or height, but for an interlaced
431		// image, an individual pass might have zero width or height. If so, we
432		// shouldn't even read a per-row filter type byte, so return early.
433		if width == 0 || height == 0 {
434			return nil, nil
435		}
436	}
437	switch d.cb {
438	case cbG1, cbG2, cbG4, cbG8:
439		bitsPerPixel = d.depth
440		if d.useTransparent {
441			nrgba = image.NewNRGBA(image.Rect(0, 0, width, height))
442			img = nrgba
443		} else {
444			gray = image.NewGray(image.Rect(0, 0, width, height))
445			img = gray
446		}
447	case cbGA8:
448		bitsPerPixel = 16
449		nrgba = image.NewNRGBA(image.Rect(0, 0, width, height))
450		img = nrgba
451	case cbTC8:
452		bitsPerPixel = 24
453		if d.useTransparent {
454			nrgba = image.NewNRGBA(image.Rect(0, 0, width, height))
455			img = nrgba
456		} else {
457			rgba = image.NewRGBA(image.Rect(0, 0, width, height))
458			img = rgba
459		}
460	case cbP1, cbP2, cbP4, cbP8:
461		bitsPerPixel = d.depth
462		paletted = image.NewPaletted(image.Rect(0, 0, width, height), d.palette)
463		img = paletted
464	case cbTCA8:
465		bitsPerPixel = 32
466		nrgba = image.NewNRGBA(image.Rect(0, 0, width, height))
467		img = nrgba
468	case cbG16:
469		bitsPerPixel = 16
470		if d.useTransparent {
471			nrgba64 = image.NewNRGBA64(image.Rect(0, 0, width, height))
472			img = nrgba64
473		} else {
474			gray16 = image.NewGray16(image.Rect(0, 0, width, height))
475			img = gray16
476		}
477	case cbGA16:
478		bitsPerPixel = 32
479		nrgba64 = image.NewNRGBA64(image.Rect(0, 0, width, height))
480		img = nrgba64
481	case cbTC16:
482		bitsPerPixel = 48
483		if d.useTransparent {
484			nrgba64 = image.NewNRGBA64(image.Rect(0, 0, width, height))
485			img = nrgba64
486		} else {
487			rgba64 = image.NewRGBA64(image.Rect(0, 0, width, height))
488			img = rgba64
489		}
490	case cbTCA16:
491		bitsPerPixel = 64
492		nrgba64 = image.NewNRGBA64(image.Rect(0, 0, width, height))
493		img = nrgba64
494	}
495	if allocateOnly {
496		return img, nil
497	}
498	bytesPerPixel := (bitsPerPixel + 7) / 8
499
500	// The +1 is for the per-row filter type, which is at cr[0].
501	rowSize := 1 + (bitsPerPixel*width+7)/8
502	// cr and pr are the bytes for the current and previous row.
503	cr := make([]uint8, rowSize)
504	pr := make([]uint8, rowSize)
505
506	for y := 0; y < height; y++ {
507		// Read the decompressed bytes.
508		_, err := io.ReadFull(r, cr)
509		if err != nil {
510			if err == io.EOF || err == io.ErrUnexpectedEOF {
511				return nil, FormatError("not enough pixel data")
512			}
513			return nil, err
514		}
515
516		// Apply the filter.
517		cdat := cr[1:]
518		pdat := pr[1:]
519		switch cr[0] {
520		case ftNone:
521			// No-op.
522		case ftSub:
523			for i := bytesPerPixel; i < len(cdat); i++ {
524				cdat[i] += cdat[i-bytesPerPixel]
525			}
526		case ftUp:
527			for i, p := range pdat {
528				cdat[i] += p
529			}
530		case ftAverage:
531			// The first column has no column to the left of it, so it is a
532			// special case. We know that the first column exists because we
533			// check above that width != 0, and so len(cdat) != 0.
534			for i := 0; i < bytesPerPixel; i++ {
535				cdat[i] += pdat[i] / 2
536			}
537			for i := bytesPerPixel; i < len(cdat); i++ {
538				cdat[i] += uint8((int(cdat[i-bytesPerPixel]) + int(pdat[i])) / 2)
539			}
540		case ftPaeth:
541			filterPaeth(cdat, pdat, bytesPerPixel)
542		default:
543			return nil, FormatError("bad filter type")
544		}
545
546		// Convert from bytes to colors.
547		switch d.cb {
548		case cbG1:
549			if d.useTransparent {
550				ty := d.transparent[1]
551				for x := 0; x < width; x += 8 {
552					b := cdat[x/8]
553					for x2 := 0; x2 < 8 && x+x2 < width; x2++ {
554						ycol := (b >> 7) * 0xff
555						acol := uint8(0xff)
556						if ycol == ty {
557							acol = 0x00
558						}
559						nrgba.SetNRGBA(x+x2, y, color.NRGBA{ycol, ycol, ycol, acol})
560						b <<= 1
561					}
562				}
563			} else {
564				for x := 0; x < width; x += 8 {
565					b := cdat[x/8]
566					for x2 := 0; x2 < 8 && x+x2 < width; x2++ {
567						gray.SetGray(x+x2, y, color.Gray{(b >> 7) * 0xff})
568						b <<= 1
569					}
570				}
571			}
572		case cbG2:
573			if d.useTransparent {
574				ty := d.transparent[1]
575				for x := 0; x < width; x += 4 {
576					b := cdat[x/4]
577					for x2 := 0; x2 < 4 && x+x2 < width; x2++ {
578						ycol := (b >> 6) * 0x55
579						acol := uint8(0xff)
580						if ycol == ty {
581							acol = 0x00
582						}
583						nrgba.SetNRGBA(x+x2, y, color.NRGBA{ycol, ycol, ycol, acol})
584						b <<= 2
585					}
586				}
587			} else {
588				for x := 0; x < width; x += 4 {
589					b := cdat[x/4]
590					for x2 := 0; x2 < 4 && x+x2 < width; x2++ {
591						gray.SetGray(x+x2, y, color.Gray{(b >> 6) * 0x55})
592						b <<= 2
593					}
594				}
595			}
596		case cbG4:
597			if d.useTransparent {
598				ty := d.transparent[1]
599				for x := 0; x < width; x += 2 {
600					b := cdat[x/2]
601					for x2 := 0; x2 < 2 && x+x2 < width; x2++ {
602						ycol := (b >> 4) * 0x11
603						acol := uint8(0xff)
604						if ycol == ty {
605							acol = 0x00
606						}
607						nrgba.SetNRGBA(x+x2, y, color.NRGBA{ycol, ycol, ycol, acol})
608						b <<= 4
609					}
610				}
611			} else {
612				for x := 0; x < width; x += 2 {
613					b := cdat[x/2]
614					for x2 := 0; x2 < 2 && x+x2 < width; x2++ {
615						gray.SetGray(x+x2, y, color.Gray{(b >> 4) * 0x11})
616						b <<= 4
617					}
618				}
619			}
620		case cbG8:
621			if d.useTransparent {
622				ty := d.transparent[1]
623				for x := 0; x < width; x++ {
624					ycol := cdat[x]
625					acol := uint8(0xff)
626					if ycol == ty {
627						acol = 0x00
628					}
629					nrgba.SetNRGBA(x, y, color.NRGBA{ycol, ycol, ycol, acol})
630				}
631			} else {
632				copy(gray.Pix[pixOffset:], cdat)
633				pixOffset += gray.Stride
634			}
635		case cbGA8:
636			for x := 0; x < width; x++ {
637				ycol := cdat[2*x+0]
638				nrgba.SetNRGBA(x, y, color.NRGBA{ycol, ycol, ycol, cdat[2*x+1]})
639			}
640		case cbTC8:
641			if d.useTransparent {
642				pix, i, j := nrgba.Pix, pixOffset, 0
643				tr, tg, tb := d.transparent[1], d.transparent[3], d.transparent[5]
644				for x := 0; x < width; x++ {
645					r := cdat[j+0]
646					g := cdat[j+1]
647					b := cdat[j+2]
648					a := uint8(0xff)
649					if r == tr && g == tg && b == tb {
650						a = 0x00
651					}
652					pix[i+0] = r
653					pix[i+1] = g
654					pix[i+2] = b
655					pix[i+3] = a
656					i += 4
657					j += 3
658				}
659				pixOffset += nrgba.Stride
660			} else {
661				pix, i, j := rgba.Pix, pixOffset, 0
662				for x := 0; x < width; x++ {
663					pix[i+0] = cdat[j+0]
664					pix[i+1] = cdat[j+1]
665					pix[i+2] = cdat[j+2]
666					pix[i+3] = 0xff
667					i += 4
668					j += 3
669				}
670				pixOffset += rgba.Stride
671			}
672		case cbP1:
673			for x := 0; x < width; x += 8 {
674				b := cdat[x/8]
675				for x2 := 0; x2 < 8 && x+x2 < width; x2++ {
676					idx := b >> 7
677					if len(paletted.Palette) <= int(idx) {
678						paletted.Palette = paletted.Palette[:int(idx)+1]
679					}
680					paletted.SetColorIndex(x+x2, y, idx)
681					b <<= 1
682				}
683			}
684		case cbP2:
685			for x := 0; x < width; x += 4 {
686				b := cdat[x/4]
687				for x2 := 0; x2 < 4 && x+x2 < width; x2++ {
688					idx := b >> 6
689					if len(paletted.Palette) <= int(idx) {
690						paletted.Palette = paletted.Palette[:int(idx)+1]
691					}
692					paletted.SetColorIndex(x+x2, y, idx)
693					b <<= 2
694				}
695			}
696		case cbP4:
697			for x := 0; x < width; x += 2 {
698				b := cdat[x/2]
699				for x2 := 0; x2 < 2 && x+x2 < width; x2++ {
700					idx := b >> 4
701					if len(paletted.Palette) <= int(idx) {
702						paletted.Palette = paletted.Palette[:int(idx)+1]
703					}
704					paletted.SetColorIndex(x+x2, y, idx)
705					b <<= 4
706				}
707			}
708		case cbP8:
709			if len(paletted.Palette) != 255 {
710				for x := 0; x < width; x++ {
711					if len(paletted.Palette) <= int(cdat[x]) {
712						paletted.Palette = paletted.Palette[:int(cdat[x])+1]
713					}
714				}
715			}
716			copy(paletted.Pix[pixOffset:], cdat)
717			pixOffset += paletted.Stride
718		case cbTCA8:
719			copy(nrgba.Pix[pixOffset:], cdat)
720			pixOffset += nrgba.Stride
721		case cbG16:
722			if d.useTransparent {
723				ty := uint16(d.transparent[0])<<8 | uint16(d.transparent[1])
724				for x := 0; x < width; x++ {
725					ycol := uint16(cdat[2*x+0])<<8 | uint16(cdat[2*x+1])
726					acol := uint16(0xffff)
727					if ycol == ty {
728						acol = 0x0000
729					}
730					nrgba64.SetNRGBA64(x, y, color.NRGBA64{ycol, ycol, ycol, acol})
731				}
732			} else {
733				for x := 0; x < width; x++ {
734					ycol := uint16(cdat[2*x+0])<<8 | uint16(cdat[2*x+1])
735					gray16.SetGray16(x, y, color.Gray16{ycol})
736				}
737			}
738		case cbGA16:
739			for x := 0; x < width; x++ {
740				ycol := uint16(cdat[4*x+0])<<8 | uint16(cdat[4*x+1])
741				acol := uint16(cdat[4*x+2])<<8 | uint16(cdat[4*x+3])
742				nrgba64.SetNRGBA64(x, y, color.NRGBA64{ycol, ycol, ycol, acol})
743			}
744		case cbTC16:
745			if d.useTransparent {
746				tr := uint16(d.transparent[0])<<8 | uint16(d.transparent[1])
747				tg := uint16(d.transparent[2])<<8 | uint16(d.transparent[3])
748				tb := uint16(d.transparent[4])<<8 | uint16(d.transparent[5])
749				for x := 0; x < width; x++ {
750					rcol := uint16(cdat[6*x+0])<<8 | uint16(cdat[6*x+1])
751					gcol := uint16(cdat[6*x+2])<<8 | uint16(cdat[6*x+3])
752					bcol := uint16(cdat[6*x+4])<<8 | uint16(cdat[6*x+5])
753					acol := uint16(0xffff)
754					if rcol == tr && gcol == tg && bcol == tb {
755						acol = 0x0000
756					}
757					nrgba64.SetNRGBA64(x, y, color.NRGBA64{rcol, gcol, bcol, acol})
758				}
759			} else {
760				for x := 0; x < width; x++ {
761					rcol := uint16(cdat[6*x+0])<<8 | uint16(cdat[6*x+1])
762					gcol := uint16(cdat[6*x+2])<<8 | uint16(cdat[6*x+3])
763					bcol := uint16(cdat[6*x+4])<<8 | uint16(cdat[6*x+5])
764					rgba64.SetRGBA64(x, y, color.RGBA64{rcol, gcol, bcol, 0xffff})
765				}
766			}
767		case cbTCA16:
768			for x := 0; x < width; x++ {
769				rcol := uint16(cdat[8*x+0])<<8 | uint16(cdat[8*x+1])
770				gcol := uint16(cdat[8*x+2])<<8 | uint16(cdat[8*x+3])
771				bcol := uint16(cdat[8*x+4])<<8 | uint16(cdat[8*x+5])
772				acol := uint16(cdat[8*x+6])<<8 | uint16(cdat[8*x+7])
773				nrgba64.SetNRGBA64(x, y, color.NRGBA64{rcol, gcol, bcol, acol})
774			}
775		}
776
777		// The current row for y is the previous row for y+1.
778		pr, cr = cr, pr
779	}
780
781	return img, nil
782}
783
784// mergePassInto merges a single pass into a full sized image.
785func (d *decoder) mergePassInto(dst image.Image, src image.Image, pass int) {
786	p := interlacing[pass]
787	var (
788		srcPix        []uint8
789		dstPix        []uint8
790		stride        int
791		rect          image.Rectangle
792		bytesPerPixel int
793	)
794	switch target := dst.(type) {
795	case *image.Alpha:
796		srcPix = src.(*image.Alpha).Pix
797		dstPix, stride, rect = target.Pix, target.Stride, target.Rect
798		bytesPerPixel = 1
799	case *image.Alpha16:
800		srcPix = src.(*image.Alpha16).Pix
801		dstPix, stride, rect = target.Pix, target.Stride, target.Rect
802		bytesPerPixel = 2
803	case *image.Gray:
804		srcPix = src.(*image.Gray).Pix
805		dstPix, stride, rect = target.Pix, target.Stride, target.Rect
806		bytesPerPixel = 1
807	case *image.Gray16:
808		srcPix = src.(*image.Gray16).Pix
809		dstPix, stride, rect = target.Pix, target.Stride, target.Rect
810		bytesPerPixel = 2
811	case *image.NRGBA:
812		srcPix = src.(*image.NRGBA).Pix
813		dstPix, stride, rect = target.Pix, target.Stride, target.Rect
814		bytesPerPixel = 4
815	case *image.NRGBA64:
816		srcPix = src.(*image.NRGBA64).Pix
817		dstPix, stride, rect = target.Pix, target.Stride, target.Rect
818		bytesPerPixel = 8
819	case *image.Paletted:
820		srcPix = src.(*image.Paletted).Pix
821		dstPix, stride, rect = target.Pix, target.Stride, target.Rect
822		bytesPerPixel = 1
823	case *image.RGBA:
824		srcPix = src.(*image.RGBA).Pix
825		dstPix, stride, rect = target.Pix, target.Stride, target.Rect
826		bytesPerPixel = 4
827	case *image.RGBA64:
828		srcPix = src.(*image.RGBA64).Pix
829		dstPix, stride, rect = target.Pix, target.Stride, target.Rect
830		bytesPerPixel = 8
831	}
832	s, bounds := 0, src.Bounds()
833	for y := bounds.Min.Y; y < bounds.Max.Y; y++ {
834		dBase := (y*p.yFactor+p.yOffset-rect.Min.Y)*stride + (p.xOffset-rect.Min.X)*bytesPerPixel
835		for x := bounds.Min.X; x < bounds.Max.X; x++ {
836			d := dBase + x*p.xFactor*bytesPerPixel
837			copy(dstPix[d:], srcPix[s:s+bytesPerPixel])
838			s += bytesPerPixel
839		}
840	}
841}
842
843func (d *decoder) parseIDAT(length uint32) (err error) {
844	d.idatLength = length
845	d.img, err = d.decode()
846	if err != nil {
847		return err
848	}
849	return d.verifyChecksum()
850}
851
852func (d *decoder) parseIEND(length uint32) error {
853	if length != 0 {
854		return FormatError("bad IEND length")
855	}
856	return d.verifyChecksum()
857}
858
859func (d *decoder) parseChunk() error {
860	// Read the length and chunk type.
861	n, err := io.ReadFull(d.r, d.tmp[:8])
862	if err != nil {
863		return err
864	}
865	length := binary.BigEndian.Uint32(d.tmp[:4])
866	d.crc.Reset()
867	d.crc.Write(d.tmp[4:8])
868
869	// Read the chunk data.
870	switch string(d.tmp[4:8]) {
871	case "IHDR":
872		if d.stage != dsStart {
873			return chunkOrderError
874		}
875		d.stage = dsSeenIHDR
876		return d.parseIHDR(length)
877	case "PLTE":
878		if d.stage != dsSeenIHDR {
879			return chunkOrderError
880		}
881		d.stage = dsSeenPLTE
882		return d.parsePLTE(length)
883	case "tRNS":
884		if cbPaletted(d.cb) {
885			if d.stage != dsSeenPLTE {
886				return chunkOrderError
887			}
888		} else if d.stage != dsSeenIHDR {
889			return chunkOrderError
890		}
891		d.stage = dsSeentRNS
892		return d.parsetRNS(length)
893	case "IDAT":
894		if d.stage < dsSeenIHDR || d.stage > dsSeenIDAT || (d.stage == dsSeenIHDR && cbPaletted(d.cb)) {
895			return chunkOrderError
896		} else if d.stage == dsSeenIDAT {
897			// Ignore trailing zero-length or garbage IDAT chunks.
898			//
899			// This does not affect valid PNG images that contain multiple IDAT
900			// chunks, since the first call to parseIDAT below will consume all
901			// consecutive IDAT chunks required for decoding the image.
902			break
903		}
904		d.stage = dsSeenIDAT
905		return d.parseIDAT(length)
906	case "IEND":
907		if d.stage != dsSeenIDAT {
908			return chunkOrderError
909		}
910		d.stage = dsSeenIEND
911		return d.parseIEND(length)
912	}
913	if length > 0x7fffffff {
914		return FormatError(fmt.Sprintf("Bad chunk length: %d", length))
915	}
916	// Ignore this chunk (of a known length).
917	var ignored [4096]byte
918	for length > 0 {
919		n, err = io.ReadFull(d.r, ignored[:min(len(ignored), int(length))])
920		if err != nil {
921			return err
922		}
923		d.crc.Write(ignored[:n])
924		length -= uint32(n)
925	}
926	return d.verifyChecksum()
927}
928
929func (d *decoder) verifyChecksum() error {
930	if _, err := io.ReadFull(d.r, d.tmp[:4]); err != nil {
931		return err
932	}
933	if binary.BigEndian.Uint32(d.tmp[:4]) != d.crc.Sum32() {
934		return FormatError("invalid checksum")
935	}
936	return nil
937}
938
939func (d *decoder) checkHeader() error {
940	_, err := io.ReadFull(d.r, d.tmp[:len(pngHeader)])
941	if err != nil {
942		return err
943	}
944	if string(d.tmp[:len(pngHeader)]) != pngHeader {
945		return FormatError("not a PNG file")
946	}
947	return nil
948}
949
950// Decode reads a PNG image from r and returns it as an image.Image.
951// The type of Image returned depends on the PNG contents.
952func Decode(r io.Reader) (image.Image, error) {
953	d := &decoder{
954		r:   r,
955		crc: crc32.NewIEEE(),
956	}
957	if err := d.checkHeader(); err != nil {
958		if err == io.EOF {
959			err = io.ErrUnexpectedEOF
960		}
961		return nil, err
962	}
963	for d.stage != dsSeenIEND {
964		if err := d.parseChunk(); err != nil {
965			if err == io.EOF {
966				err = io.ErrUnexpectedEOF
967			}
968			return nil, err
969		}
970	}
971	return d.img, nil
972}
973
974// DecodeConfig returns the color model and dimensions of a PNG image without
975// decoding the entire image.
976func DecodeConfig(r io.Reader) (image.Config, error) {
977	d := &decoder{
978		r:   r,
979		crc: crc32.NewIEEE(),
980	}
981	if err := d.checkHeader(); err != nil {
982		if err == io.EOF {
983			err = io.ErrUnexpectedEOF
984		}
985		return image.Config{}, err
986	}
987	for {
988		if err := d.parseChunk(); err != nil {
989			if err == io.EOF {
990				err = io.ErrUnexpectedEOF
991			}
992			return image.Config{}, err
993		}
994		paletted := cbPaletted(d.cb)
995		if d.stage == dsSeenIHDR && !paletted {
996			break
997		}
998		if d.stage == dsSeenPLTE && paletted {
999			break
1000		}
1001	}
1002	var cm color.Model
1003	switch d.cb {
1004	case cbG1, cbG2, cbG4, cbG8:
1005		cm = color.GrayModel
1006	case cbGA8:
1007		cm = color.NRGBAModel
1008	case cbTC8:
1009		cm = color.RGBAModel
1010	case cbP1, cbP2, cbP4, cbP8:
1011		cm = d.palette
1012	case cbTCA8:
1013		cm = color.NRGBAModel
1014	case cbG16:
1015		cm = color.Gray16Model
1016	case cbGA16:
1017		cm = color.NRGBA64Model
1018	case cbTC16:
1019		cm = color.RGBA64Model
1020	case cbTCA16:
1021		cm = color.NRGBA64Model
1022	}
1023	return image.Config{
1024		ColorModel: cm,
1025		Width:      d.width,
1026		Height:     d.height,
1027	}, nil
1028}
1029
1030func init() {
1031	image.RegisterFormat("png", pngHeader, Decode, DecodeConfig)
1032}
1033