The Go Programming Language

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

release.r60.3. Except as noted, this content is licensed under a Creative Commons Attribution 3.0 License.