Source file src/pkg/image/jpeg/reader.go

     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 jpeg implements a JPEG image decoder and encoder.
     6	//
     7	// JPEG is defined in ITU-T T.81: http://www.w3.org/Graphics/JPEG/itu-t81.pdf.
     8	package jpeg
     9	
    10	import (
    11		"bufio"
    12		"image"
    13		"image/color"
    14		"io"
    15	)
    16	
    17	// TODO(nigeltao): fix up the doc comment style so that sentences start with
    18	// the name of the type or function that they annotate.
    19	
    20	// A FormatError reports that the input is not a valid JPEG.
    21	type FormatError string
    22	
    23	func (e FormatError) Error() string { return "invalid JPEG format: " + string(e) }
    24	
    25	// An UnsupportedError reports that the input uses a valid but unimplemented JPEG feature.
    26	type UnsupportedError string
    27	
    28	func (e UnsupportedError) Error() string { return "unsupported JPEG feature: " + string(e) }
    29	
    30	// Component specification, specified in section B.2.2.
    31	type component struct {
    32		h  int   // Horizontal sampling factor.
    33		v  int   // Vertical sampling factor.
    34		c  uint8 // Component identifier.
    35		tq uint8 // Quantization table destination selector.
    36	}
    37	
    38	type block [blockSize]int
    39	
    40	const (
    41		blockSize = 64 // A DCT block is 8x8.
    42	
    43		dcTable = 0
    44		acTable = 1
    45		maxTc   = 1
    46		maxTh   = 3
    47		maxTq   = 3
    48	
    49		// A grayscale JPEG image has only a Y component.
    50		nGrayComponent = 1
    51		// A color JPEG image has Y, Cb and Cr components.
    52		nColorComponent = 3
    53	
    54		// We only support 4:4:4, 4:2:2 and 4:2:0 downsampling, and therefore the
    55		// number of luma samples per chroma sample is at most 2 in the horizontal
    56		// and 2 in the vertical direction.
    57		maxH = 2
    58		maxV = 2
    59	)
    60	
    61	const (
    62		soiMarker   = 0xd8 // Start Of Image.
    63		eoiMarker   = 0xd9 // End Of Image.
    64		sof0Marker  = 0xc0 // Start Of Frame (Baseline).
    65		sof2Marker  = 0xc2 // Start Of Frame (Progressive).
    66		dhtMarker   = 0xc4 // Define Huffman Table.
    67		dqtMarker   = 0xdb // Define Quantization Table.
    68		sosMarker   = 0xda // Start Of Scan.
    69		driMarker   = 0xdd // Define Restart Interval.
    70		rst0Marker  = 0xd0 // ReSTart (0).
    71		rst7Marker  = 0xd7 // ReSTart (7).
    72		app0Marker  = 0xe0 // APPlication specific (0).
    73		app15Marker = 0xef // APPlication specific (15).
    74		comMarker   = 0xfe // COMment.
    75	)
    76	
    77	// Maps from the zig-zag ordering to the natural ordering.
    78	var unzig = [blockSize]int{
    79		0, 1, 8, 16, 9, 2, 3, 10,
    80		17, 24, 32, 25, 18, 11, 4, 5,
    81		12, 19, 26, 33, 40, 48, 41, 34,
    82		27, 20, 13, 6, 7, 14, 21, 28,
    83		35, 42, 49, 56, 57, 50, 43, 36,
    84		29, 22, 15, 23, 30, 37, 44, 51,
    85		58, 59, 52, 45, 38, 31, 39, 46,
    86		53, 60, 61, 54, 47, 55, 62, 63,
    87	}
    88	
    89	// If the passed in io.Reader does not also have ReadByte, then Decode will introduce its own buffering.
    90	type Reader interface {
    91		io.Reader
    92		ReadByte() (c byte, err error)
    93	}
    94	
    95	type decoder struct {
    96		r             Reader
    97		width, height int
    98		img1          *image.Gray
    99		img3          *image.YCbCr
   100		ri            int // Restart Interval.
   101		nComp         int
   102		comp          [nColorComponent]component
   103		huff          [maxTc + 1][maxTh + 1]huffman
   104		quant         [maxTq + 1]block
   105		b             bits
   106		tmp           [1024]byte
   107	}
   108	
   109	// Reads and ignores the next n bytes.
   110	func (d *decoder) ignore(n int) error {
   111		for n > 0 {
   112			m := len(d.tmp)
   113			if m > n {
   114				m = n
   115			}
   116			_, err := io.ReadFull(d.r, d.tmp[0:m])
   117			if err != nil {
   118				return err
   119			}
   120			n -= m
   121		}
   122		return nil
   123	}
   124	
   125	// Specified in section B.2.2.
   126	func (d *decoder) processSOF(n int) error {
   127		switch n {
   128		case 6 + 3*nGrayComponent:
   129			d.nComp = nGrayComponent
   130		case 6 + 3*nColorComponent:
   131			d.nComp = nColorComponent
   132		default:
   133			return UnsupportedError("SOF has wrong length")
   134		}
   135		_, err := io.ReadFull(d.r, d.tmp[:n])
   136		if err != nil {
   137			return err
   138		}
   139		// We only support 8-bit precision.
   140		if d.tmp[0] != 8 {
   141			return UnsupportedError("precision")
   142		}
   143		d.height = int(d.tmp[1])<<8 + int(d.tmp[2])
   144		d.width = int(d.tmp[3])<<8 + int(d.tmp[4])
   145		if int(d.tmp[5]) != d.nComp {
   146			return UnsupportedError("SOF has wrong number of image components")
   147		}
   148		for i := 0; i < d.nComp; i++ {
   149			hv := d.tmp[7+3*i]
   150			d.comp[i].h = int(hv >> 4)
   151			d.comp[i].v = int(hv & 0x0f)
   152			d.comp[i].c = d.tmp[6+3*i]
   153			d.comp[i].tq = d.tmp[8+3*i]
   154			if d.nComp == nGrayComponent {
   155				continue
   156			}
   157			// For color images, we only support 4:4:4, 4:2:2 or 4:2:0 chroma
   158			// downsampling ratios. This implies that the (h, v) values for the Y
   159			// component are either (1, 1), (2, 1) or (2, 2), and the (h, v)
   160			// values for the Cr and Cb components must be (1, 1).
   161			if i == 0 {
   162				if hv != 0x11 && hv != 0x21 && hv != 0x22 {
   163					return UnsupportedError("luma downsample ratio")
   164				}
   165			} else if hv != 0x11 {
   166				return UnsupportedError("chroma downsample ratio")
   167			}
   168		}
   169		return nil
   170	}
   171	
   172	// Specified in section B.2.4.1.
   173	func (d *decoder) processDQT(n int) error {
   174		const qtLength = 1 + blockSize
   175		for ; n >= qtLength; n -= qtLength {
   176			_, err := io.ReadFull(d.r, d.tmp[0:qtLength])
   177			if err != nil {
   178				return err
   179			}
   180			pq := d.tmp[0] >> 4
   181			if pq != 0 {
   182				return UnsupportedError("bad Pq value")
   183			}
   184			tq := d.tmp[0] & 0x0f
   185			if tq > maxTq {
   186				return FormatError("bad Tq value")
   187			}
   188			for i := range d.quant[tq] {
   189				d.quant[tq][i] = int(d.tmp[i+1])
   190			}
   191		}
   192		if n != 0 {
   193			return FormatError("DQT has wrong length")
   194		}
   195		return nil
   196	}
   197	
   198	// makeImg allocates and initializes the destination image.
   199	func (d *decoder) makeImg(h0, v0, mxx, myy int) {
   200		if d.nComp == nGrayComponent {
   201			m := image.NewGray(image.Rect(0, 0, 8*mxx, 8*myy))
   202			d.img1 = m.SubImage(image.Rect(0, 0, d.width, d.height)).(*image.Gray)
   203			return
   204		}
   205		var subsampleRatio image.YCbCrSubsampleRatio
   206		switch h0 * v0 {
   207		case 1:
   208			subsampleRatio = image.YCbCrSubsampleRatio444
   209		case 2:
   210			subsampleRatio = image.YCbCrSubsampleRatio422
   211		case 4:
   212			subsampleRatio = image.YCbCrSubsampleRatio420
   213		default:
   214			panic("unreachable")
   215		}
   216		m := image.NewYCbCr(image.Rect(0, 0, 8*h0*mxx, 8*v0*myy), subsampleRatio)
   217		d.img3 = m.SubImage(image.Rect(0, 0, d.width, d.height)).(*image.YCbCr)
   218	}
   219	
   220	// Specified in section B.2.3.
   221	func (d *decoder) processSOS(n int) error {
   222		if d.nComp == 0 {
   223			return FormatError("missing SOF marker")
   224		}
   225		if n != 4+2*d.nComp {
   226			return UnsupportedError("SOS has wrong length")
   227		}
   228		_, err := io.ReadFull(d.r, d.tmp[0:4+2*d.nComp])
   229		if err != nil {
   230			return err
   231		}
   232		if int(d.tmp[0]) != d.nComp {
   233			return UnsupportedError("SOS has wrong number of image components")
   234		}
   235		var scan [nColorComponent]struct {
   236			td uint8 // DC table selector.
   237			ta uint8 // AC table selector.
   238		}
   239		for i := 0; i < d.nComp; i++ {
   240			cs := d.tmp[1+2*i] // Component selector.
   241			if cs != d.comp[i].c {
   242				return UnsupportedError("scan components out of order")
   243			}
   244			scan[i].td = d.tmp[2+2*i] >> 4
   245			scan[i].ta = d.tmp[2+2*i] & 0x0f
   246		}
   247		// mxx and myy are the number of MCUs (Minimum Coded Units) in the image.
   248		h0, v0 := d.comp[0].h, d.comp[0].v // The h and v values from the Y components.
   249		mxx := (d.width + 8*h0 - 1) / (8 * h0)
   250		myy := (d.height + 8*v0 - 1) / (8 * v0)
   251		if d.img1 == nil && d.img3 == nil {
   252			d.makeImg(h0, v0, mxx, myy)
   253		}
   254	
   255		mcu, expectedRST := 0, uint8(rst0Marker)
   256		var (
   257			b  block
   258			dc [nColorComponent]int
   259		)
   260		for my := 0; my < myy; my++ {
   261			for mx := 0; mx < mxx; mx++ {
   262				for i := 0; i < d.nComp; i++ {
   263					qt := &d.quant[d.comp[i].tq]
   264					for j := 0; j < d.comp[i].h*d.comp[i].v; j++ {
   265						// TODO(nigeltao): make this a "var b block" once the compiler's escape
   266						// analysis is good enough to allocate it on the stack, not the heap.
   267						b = block{}
   268	
   269						// Decode the DC coefficient, as specified in section F.2.2.1.
   270						value, err := d.decodeHuffman(&d.huff[dcTable][scan[i].td])
   271						if err != nil {
   272							return err
   273						}
   274						if value > 16 {
   275							return UnsupportedError("excessive DC component")
   276						}
   277						dcDelta, err := d.receiveExtend(value)
   278						if err != nil {
   279							return err
   280						}
   281						dc[i] += dcDelta
   282						b[0] = dc[i] * qt[0]
   283	
   284						// Decode the AC coefficients, as specified in section F.2.2.2.
   285						for k := 1; k < blockSize; k++ {
   286							value, err := d.decodeHuffman(&d.huff[acTable][scan[i].ta])
   287							if err != nil {
   288								return err
   289							}
   290							val0 := value >> 4
   291							val1 := value & 0x0f
   292							if val1 != 0 {
   293								k += int(val0)
   294								if k > blockSize {
   295									return FormatError("bad DCT index")
   296								}
   297								ac, err := d.receiveExtend(val1)
   298								if err != nil {
   299									return err
   300								}
   301								b[unzig[k]] = ac * qt[k]
   302							} else {
   303								if val0 != 0x0f {
   304									break
   305								}
   306								k += 0x0f
   307							}
   308						}
   309	
   310						// Perform the inverse DCT and store the MCU component to the image.
   311						if d.nComp == nGrayComponent {
   312							idct(d.img1.Pix[8*(my*d.img1.Stride+mx):], d.img1.Stride, &b)
   313						} else {
   314							switch i {
   315							case 0:
   316								mx0 := h0*mx + (j % 2)
   317								my0 := v0*my + (j / 2)
   318								idct(d.img3.Y[8*(my0*d.img3.YStride+mx0):], d.img3.YStride, &b)
   319							case 1:
   320								idct(d.img3.Cb[8*(my*d.img3.CStride+mx):], d.img3.CStride, &b)
   321							case 2:
   322								idct(d.img3.Cr[8*(my*d.img3.CStride+mx):], d.img3.CStride, &b)
   323							}
   324						}
   325					} // for j
   326				} // for i
   327				mcu++
   328				if d.ri > 0 && mcu%d.ri == 0 && mcu < mxx*myy {
   329					// A more sophisticated decoder could use RST[0-7] markers to resynchronize from corrupt input,
   330					// but this one assumes well-formed input, and hence the restart marker follows immediately.
   331					_, err := io.ReadFull(d.r, d.tmp[0:2])
   332					if err != nil {
   333						return err
   334					}
   335					if d.tmp[0] != 0xff || d.tmp[1] != expectedRST {
   336						return FormatError("bad RST marker")
   337					}
   338					expectedRST++
   339					if expectedRST == rst7Marker+1 {
   340						expectedRST = rst0Marker
   341					}
   342					// Reset the Huffman decoder.
   343					d.b = bits{}
   344					// Reset the DC components, as per section F.2.1.3.1.
   345					dc = [nColorComponent]int{}
   346				}
   347			} // for mx
   348		} // for my
   349	
   350		return nil
   351	}
   352	
   353	// Specified in section B.2.4.4.
   354	func (d *decoder) processDRI(n int) error {
   355		if n != 2 {
   356			return FormatError("DRI has wrong length")
   357		}
   358		_, err := io.ReadFull(d.r, d.tmp[0:2])
   359		if err != nil {
   360			return err
   361		}
   362		d.ri = int(d.tmp[0])<<8 + int(d.tmp[1])
   363		return nil
   364	}
   365	
   366	// decode reads a JPEG image from r and returns it as an image.Image.
   367	func (d *decoder) decode(r io.Reader, configOnly bool) (image.Image, error) {
   368		if rr, ok := r.(Reader); ok {
   369			d.r = rr
   370		} else {
   371			d.r = bufio.NewReader(r)
   372		}
   373	
   374		// Check for the Start Of Image marker.
   375		_, err := io.ReadFull(d.r, d.tmp[0:2])
   376		if err != nil {
   377			return nil, err
   378		}
   379		if d.tmp[0] != 0xff || d.tmp[1] != soiMarker {
   380			return nil, FormatError("missing SOI marker")
   381		}
   382	
   383		// Process the remaining segments until the End Of Image marker.
   384		for {
   385			_, err := io.ReadFull(d.r, d.tmp[0:2])
   386			if err != nil {
   387				return nil, err
   388			}
   389			if d.tmp[0] != 0xff {
   390				return nil, FormatError("missing 0xff marker start")
   391			}
   392			marker := d.tmp[1]
   393			if marker == eoiMarker { // End Of Image.
   394				break
   395			}
   396	
   397			// Read the 16-bit length of the segment. The value includes the 2 bytes for the
   398			// length itself, so we subtract 2 to get the number of remaining bytes.
   399			_, err = io.ReadFull(d.r, d.tmp[0:2])
   400			if err != nil {
   401				return nil, err
   402			}
   403			n := int(d.tmp[0])<<8 + int(d.tmp[1]) - 2
   404			if n < 0 {
   405				return nil, FormatError("short segment length")
   406			}
   407	
   408			switch {
   409			case marker == sof0Marker: // Start Of Frame (Baseline).
   410				err = d.processSOF(n)
   411				if configOnly {
   412					return nil, err
   413				}
   414			case marker == sof2Marker: // Start Of Frame (Progressive).
   415				err = UnsupportedError("progressive mode")
   416			case marker == dhtMarker: // Define Huffman Table.
   417				err = d.processDHT(n)
   418			case marker == dqtMarker: // Define Quantization Table.
   419				err = d.processDQT(n)
   420			case marker == sosMarker: // Start Of Scan.
   421				err = d.processSOS(n)
   422			case marker == driMarker: // Define Restart Interval.
   423				err = d.processDRI(n)
   424			case marker >= app0Marker && marker <= app15Marker || marker == comMarker: // APPlication specific, or COMment.
   425				err = d.ignore(n)
   426			default:
   427				err = UnsupportedError("unknown marker")
   428			}
   429			if err != nil {
   430				return nil, err
   431			}
   432		}
   433		if d.img1 != nil {
   434			return d.img1, nil
   435		}
   436		if d.img3 != nil {
   437			return d.img3, nil
   438		}
   439		return nil, FormatError("missing SOS marker")
   440	}
   441	
   442	// Decode reads a JPEG image from r and returns it as an image.Image.
   443	func Decode(r io.Reader) (image.Image, error) {
   444		var d decoder
   445		return d.decode(r, false)
   446	}
   447	
   448	// DecodeConfig returns the color model and dimensions of a JPEG image without
   449	// decoding the entire image.
   450	func DecodeConfig(r io.Reader) (image.Config, error) {
   451		var d decoder
   452		if _, err := d.decode(r, true); err != nil {
   453			return image.Config{}, err
   454		}
   455		switch d.nComp {
   456		case nGrayComponent:
   457			return image.Config{
   458				ColorModel: color.GrayModel,
   459				Width:      d.width,
   460				Height:     d.height,
   461			}, nil
   462		case nColorComponent:
   463			return image.Config{
   464				ColorModel: color.YCbCrModel,
   465				Width:      d.width,
   466				Height:     d.height,
   467			}, nil
   468		}
   469		return image.Config{}, FormatError("missing SOF marker")
   470	}
   471	
   472	func init() {
   473		image.RegisterFormat("jpeg", "\xff\xd8", Decode, DecodeConfig)
   474	}