...
Run Format

Source file src/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		"image"
    12		"image/color"
    13		"io"
    14	)
    15	
    16	// TODO(nigeltao): fix up the doc comment style so that sentences start with
    17	// the name of the type or function that they annotate.
    18	
    19	// A FormatError reports that the input is not a valid JPEG.
    20	type FormatError string
    21	
    22	func (e FormatError) Error() string { return "invalid JPEG format: " + string(e) }
    23	
    24	// An UnsupportedError reports that the input uses a valid but unimplemented JPEG feature.
    25	type UnsupportedError string
    26	
    27	func (e UnsupportedError) Error() string { return "unsupported JPEG feature: " + string(e) }
    28	
    29	// Component specification, specified in section B.2.2.
    30	type component struct {
    31		h  int   // Horizontal sampling factor.
    32		v  int   // Vertical sampling factor.
    33		c  uint8 // Component identifier.
    34		tq uint8 // Quantization table destination selector.
    35	}
    36	
    37	const (
    38		dcTable = 0
    39		acTable = 1
    40		maxTc   = 1
    41		maxTh   = 3
    42		maxTq   = 3
    43	
    44		// A grayscale JPEG image has only a Y component.
    45		nGrayComponent = 1
    46		// A color JPEG image has Y, Cb and Cr components.
    47		nColorComponent = 3
    48	
    49		// We only support 4:4:4, 4:4:0, 4:2:2 and 4:2:0 downsampling, and therefore the
    50		// number of luma samples per chroma sample is at most 2 in the horizontal
    51		// and 2 in the vertical direction.
    52		maxH = 2
    53		maxV = 2
    54	)
    55	
    56	const (
    57		soiMarker   = 0xd8 // Start Of Image.
    58		eoiMarker   = 0xd9 // End Of Image.
    59		sof0Marker  = 0xc0 // Start Of Frame (Baseline).
    60		sof2Marker  = 0xc2 // Start Of Frame (Progressive).
    61		dhtMarker   = 0xc4 // Define Huffman Table.
    62		dqtMarker   = 0xdb // Define Quantization Table.
    63		sosMarker   = 0xda // Start Of Scan.
    64		driMarker   = 0xdd // Define Restart Interval.
    65		rst0Marker  = 0xd0 // ReSTart (0).
    66		rst7Marker  = 0xd7 // ReSTart (7).
    67		app0Marker  = 0xe0 // APPlication specific (0).
    68		app15Marker = 0xef // APPlication specific (15).
    69		comMarker   = 0xfe // COMment.
    70	)
    71	
    72	// unzig maps from the zig-zag ordering to the natural ordering. For example,
    73	// unzig[3] is the column and row of the fourth element in zig-zag order. The
    74	// value is 16, which means first column (16%8 == 0) and third row (16/8 == 2).
    75	var unzig = [blockSize]int{
    76		0, 1, 8, 16, 9, 2, 3, 10,
    77		17, 24, 32, 25, 18, 11, 4, 5,
    78		12, 19, 26, 33, 40, 48, 41, 34,
    79		27, 20, 13, 6, 7, 14, 21, 28,
    80		35, 42, 49, 56, 57, 50, 43, 36,
    81		29, 22, 15, 23, 30, 37, 44, 51,
    82		58, 59, 52, 45, 38, 31, 39, 46,
    83		53, 60, 61, 54, 47, 55, 62, 63,
    84	}
    85	
    86	// Reader is deprecated.
    87	type Reader interface {
    88		io.ByteReader
    89		io.Reader
    90	}
    91	
    92	// bits holds the unprocessed bits that have been taken from the byte-stream.
    93	// The n least significant bits of a form the unread bits, to be read in MSB to
    94	// LSB order.
    95	type bits struct {
    96		a uint32 // accumulator.
    97		m uint32 // mask. m==1<<(n-1) when n>0, with m==0 when n==0.
    98		n int32  // the number of unread bits in a.
    99	}
   100	
   101	type decoder struct {
   102		r    io.Reader
   103		bits bits
   104		// bytes is a byte buffer, similar to a bufio.Reader, except that it
   105		// has to be able to unread more than 1 byte, due to byte stuffing.
   106		// Byte stuffing is specified in section F.1.2.3.
   107		bytes struct {
   108			// buf[i:j] are the buffered bytes read from the underlying
   109			// io.Reader that haven't yet been passed further on.
   110			buf  [4096]byte
   111			i, j int
   112			// nUnreadable is the number of bytes to back up i after
   113			// overshooting. It can be 0, 1 or 2.
   114			nUnreadable int
   115		}
   116		width, height int
   117		img1          *image.Gray
   118		img3          *image.YCbCr
   119		ri            int // Restart Interval.
   120		nComp         int
   121		progressive   bool
   122		eobRun        uint16 // End-of-Band run, specified in section G.1.2.2.
   123		comp          [nColorComponent]component
   124		progCoeffs    [nColorComponent][]block // Saved state between progressive-mode scans.
   125		huff          [maxTc + 1][maxTh + 1]huffman
   126		quant         [maxTq + 1]block // Quantization tables, in zig-zag order.
   127		tmp           [blockSize + 1]byte
   128	}
   129	
   130	// fill fills up the d.bytes.buf buffer from the underlying io.Reader. It
   131	// should only be called when there are no unread bytes in d.bytes.
   132	func (d *decoder) fill() error {
   133		if d.bytes.i != d.bytes.j {
   134			panic("jpeg: fill called when unread bytes exist")
   135		}
   136		// Move the last 2 bytes to the start of the buffer, in case we need
   137		// to call unreadByteStuffedByte.
   138		if d.bytes.j > 2 {
   139			d.bytes.buf[0] = d.bytes.buf[d.bytes.j-2]
   140			d.bytes.buf[1] = d.bytes.buf[d.bytes.j-1]
   141			d.bytes.i, d.bytes.j = 2, 2
   142		}
   143		// Fill in the rest of the buffer.
   144		n, err := d.r.Read(d.bytes.buf[d.bytes.j:])
   145		d.bytes.j += n
   146		if n > 0 {
   147			err = nil
   148		}
   149		return err
   150	}
   151	
   152	// unreadByteStuffedByte undoes the most recent readByteStuffedByte call,
   153	// giving a byte of data back from d.bits to d.bytes. The Huffman look-up table
   154	// requires at least 8 bits for look-up, which means that Huffman decoding can
   155	// sometimes overshoot and read one or two too many bytes. Two-byte overshoot
   156	// can happen when expecting to read a 0xff 0x00 byte-stuffed byte.
   157	func (d *decoder) unreadByteStuffedByte() {
   158		if d.bytes.nUnreadable == 0 {
   159			panic("jpeg: unreadByteStuffedByte call cannot be fulfilled")
   160		}
   161		d.bytes.i -= d.bytes.nUnreadable
   162		d.bytes.nUnreadable = 0
   163		if d.bits.n >= 8 {
   164			d.bits.a >>= 8
   165			d.bits.n -= 8
   166			d.bits.m >>= 8
   167		}
   168	}
   169	
   170	// readByte returns the next byte, whether buffered or not buffered. It does
   171	// not care about byte stuffing.
   172	func (d *decoder) readByte() (x byte, err error) {
   173		for d.bytes.i == d.bytes.j {
   174			if err = d.fill(); err != nil {
   175				return 0, err
   176			}
   177		}
   178		x = d.bytes.buf[d.bytes.i]
   179		d.bytes.i++
   180		d.bytes.nUnreadable = 0
   181		return x, nil
   182	}
   183	
   184	// errMissingFF00 means that readByteStuffedByte encountered an 0xff byte (a
   185	// marker byte) that wasn't the expected byte-stuffed sequence 0xff, 0x00.
   186	var errMissingFF00 = FormatError("missing 0xff00 sequence")
   187	
   188	// readByteStuffedByte is like readByte but is for byte-stuffed Huffman data.
   189	func (d *decoder) readByteStuffedByte() (x byte, err error) {
   190		// Take the fast path if d.bytes.buf contains at least two bytes.
   191		if d.bytes.i+2 <= d.bytes.j {
   192			x = d.bytes.buf[d.bytes.i]
   193			d.bytes.i++
   194			d.bytes.nUnreadable = 1
   195			if x != 0xff {
   196				return x, err
   197			}
   198			if d.bytes.buf[d.bytes.i] != 0x00 {
   199				return 0, errMissingFF00
   200			}
   201			d.bytes.i++
   202			d.bytes.nUnreadable = 2
   203			return 0xff, nil
   204		}
   205	
   206		x, err = d.readByte()
   207		if err != nil {
   208			return 0, err
   209		}
   210		if x != 0xff {
   211			d.bytes.nUnreadable = 1
   212			return x, nil
   213		}
   214	
   215		x, err = d.readByte()
   216		if err != nil {
   217			d.bytes.nUnreadable = 1
   218			return 0, err
   219		}
   220		d.bytes.nUnreadable = 2
   221		if x != 0x00 {
   222			return 0, errMissingFF00
   223		}
   224		return 0xff, nil
   225	}
   226	
   227	// readFull reads exactly len(p) bytes into p. It does not care about byte
   228	// stuffing.
   229	func (d *decoder) readFull(p []byte) error {
   230		// Unread the overshot bytes, if any.
   231		if d.bytes.nUnreadable != 0 {
   232			if d.bits.n >= 8 {
   233				d.unreadByteStuffedByte()
   234			}
   235			d.bytes.nUnreadable = 0
   236		}
   237	
   238		for {
   239			n := copy(p, d.bytes.buf[d.bytes.i:d.bytes.j])
   240			p = p[n:]
   241			d.bytes.i += n
   242			if len(p) == 0 {
   243				break
   244			}
   245			if err := d.fill(); err != nil {
   246				if err == io.EOF {
   247					err = io.ErrUnexpectedEOF
   248				}
   249				return err
   250			}
   251		}
   252		return nil
   253	}
   254	
   255	// ignore ignores the next n bytes.
   256	func (d *decoder) ignore(n int) error {
   257		// Unread the overshot bytes, if any.
   258		if d.bytes.nUnreadable != 0 {
   259			if d.bits.n >= 8 {
   260				d.unreadByteStuffedByte()
   261			}
   262			d.bytes.nUnreadable = 0
   263		}
   264	
   265		for {
   266			m := d.bytes.j - d.bytes.i
   267			if m > n {
   268				m = n
   269			}
   270			d.bytes.i += m
   271			n -= m
   272			if n == 0 {
   273				break
   274			}
   275			if err := d.fill(); err != nil {
   276				if err == io.EOF {
   277					err = io.ErrUnexpectedEOF
   278				}
   279				return err
   280			}
   281		}
   282		return nil
   283	}
   284	
   285	// Specified in section B.2.2.
   286	func (d *decoder) processSOF(n int) error {
   287		switch n {
   288		case 6 + 3*nGrayComponent:
   289			d.nComp = nGrayComponent
   290		case 6 + 3*nColorComponent:
   291			d.nComp = nColorComponent
   292		default:
   293			return UnsupportedError("SOF has wrong length")
   294		}
   295		if err := d.readFull(d.tmp[:n]); err != nil {
   296			return err
   297		}
   298		// We only support 8-bit precision.
   299		if d.tmp[0] != 8 {
   300			return UnsupportedError("precision")
   301		}
   302		d.height = int(d.tmp[1])<<8 + int(d.tmp[2])
   303		d.width = int(d.tmp[3])<<8 + int(d.tmp[4])
   304		if int(d.tmp[5]) != d.nComp {
   305			return UnsupportedError("SOF has wrong number of image components")
   306		}
   307		for i := 0; i < d.nComp; i++ {
   308			d.comp[i].c = d.tmp[6+3*i]
   309			d.comp[i].tq = d.tmp[8+3*i]
   310			if d.nComp == nGrayComponent {
   311				// If a JPEG image has only one component, section A.2 says "this data
   312				// is non-interleaved by definition" and section A.2.2 says "[in this
   313				// case...] the order of data units within a scan shall be left-to-right
   314				// and top-to-bottom... regardless of the values of H_1 and V_1". Section
   315				// 4.8.2 also says "[for non-interleaved data], the MCU is defined to be
   316				// one data unit". Similarly, section A.1.1 explains that it is the ratio
   317				// of H_i to max_j(H_j) that matters, and similarly for V. For grayscale
   318				// images, H_1 is the maximum H_j for all components j, so that ratio is
   319				// always 1. The component's (h, v) is effectively always (1, 1): even if
   320				// the nominal (h, v) is (2, 1), a 20x5 image is encoded in three 8x8
   321				// MCUs, not two 16x8 MCUs.
   322				d.comp[i].h = 1
   323				d.comp[i].v = 1
   324				continue
   325			}
   326			hv := d.tmp[7+3*i]
   327			d.comp[i].h = int(hv >> 4)
   328			d.comp[i].v = int(hv & 0x0f)
   329			// For color images, we only support 4:4:4, 4:4:0, 4:2:2 or 4:2:0 chroma
   330			// downsampling ratios. This implies that the (h, v) values for the Y
   331			// component are either (1, 1), (1, 2), (2, 1) or (2, 2), and the (h, v)
   332			// values for the Cr and Cb components must be (1, 1).
   333			if i == 0 {
   334				if hv != 0x11 && hv != 0x21 && hv != 0x22 && hv != 0x12 {
   335					return UnsupportedError("luma/chroma downsample ratio")
   336				}
   337			} else if hv != 0x11 {
   338				return UnsupportedError("luma/chroma downsample ratio")
   339			}
   340		}
   341		return nil
   342	}
   343	
   344	// Specified in section B.2.4.1.
   345	func (d *decoder) processDQT(n int) error {
   346		const qtLength = 1 + blockSize
   347		for ; n >= qtLength; n -= qtLength {
   348			if err := d.readFull(d.tmp[:qtLength]); err != nil {
   349				return err
   350			}
   351			pq := d.tmp[0] >> 4
   352			if pq != 0 {
   353				return UnsupportedError("bad Pq value")
   354			}
   355			tq := d.tmp[0] & 0x0f
   356			if tq > maxTq {
   357				return FormatError("bad Tq value")
   358			}
   359			for i := range d.quant[tq] {
   360				d.quant[tq][i] = int32(d.tmp[i+1])
   361			}
   362		}
   363		if n != 0 {
   364			return FormatError("DQT has wrong length")
   365		}
   366		return nil
   367	}
   368	
   369	// Specified in section B.2.4.4.
   370	func (d *decoder) processDRI(n int) error {
   371		if n != 2 {
   372			return FormatError("DRI has wrong length")
   373		}
   374		if err := d.readFull(d.tmp[:2]); err != nil {
   375			return err
   376		}
   377		d.ri = int(d.tmp[0])<<8 + int(d.tmp[1])
   378		return nil
   379	}
   380	
   381	// decode reads a JPEG image from r and returns it as an image.Image.
   382	func (d *decoder) decode(r io.Reader, configOnly bool) (image.Image, error) {
   383		d.r = r
   384	
   385		// Check for the Start Of Image marker.
   386		if err := d.readFull(d.tmp[:2]); 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 := d.readFull(d.tmp[:2])
   396			if err != nil {
   397				return nil, err
   398			}
   399			for d.tmp[0] != 0xff {
   400				// Strictly speaking, this is a format error. However, libjpeg is
   401				// liberal in what it accepts. As of version 9, next_marker in
   402				// jdmarker.c treats this as a warning (JWRN_EXTRANEOUS_DATA) and
   403				// continues to decode the stream. Even before next_marker sees
   404				// extraneous data, jpeg_fill_bit_buffer in jdhuff.c reads as many
   405				// bytes as it can, possibly past the end of a scan's data. It
   406				// effectively puts back any markers that it overscanned (e.g. an
   407				// "\xff\xd9" EOI marker), but it does not put back non-marker data,
   408				// and thus it can silently ignore a small number of extraneous
   409				// non-marker bytes before next_marker has a chance to see them (and
   410				// print a warning).
   411				//
   412				// We are therefore also liberal in what we accept. Extraneous data
   413				// is silently ignored.
   414				//
   415				// This is similar to, but not exactly the same as, the restart
   416				// mechanism within a scan (the RST[0-7] markers).
   417				//
   418				// Note that extraneous 0xff bytes in e.g. SOS data are escaped as
   419				// "\xff\x00", and so are detected a little further down below.
   420				d.tmp[0] = d.tmp[1]
   421				d.tmp[1], err = d.readByte()
   422				if err != nil {
   423					return nil, err
   424				}
   425			}
   426			marker := d.tmp[1]
   427			if marker == 0 {
   428				// Treat "\xff\x00" as extraneous data.
   429				continue
   430			}
   431			for marker == 0xff {
   432				// Section B.1.1.2 says, "Any marker may optionally be preceded by any
   433				// number of fill bytes, which are bytes assigned code X'FF'".
   434				marker, err = d.readByte()
   435				if err != nil {
   436					return nil, err
   437				}
   438			}
   439			if marker == eoiMarker { // End Of Image.
   440				break
   441			}
   442			if rst0Marker <= marker && marker <= rst7Marker {
   443				// Figures B.2 and B.16 of the specification suggest that restart markers should
   444				// only occur between Entropy Coded Segments and not after the final ECS.
   445				// However, some encoders may generate incorrect JPEGs with a final restart
   446				// marker. That restart marker will be seen here instead of inside the processSOS
   447				// method, and is ignored as a harmless error. Restart markers have no extra data,
   448				// so we check for this before we read the 16-bit length of the segment.
   449				continue
   450			}
   451	
   452			// Read the 16-bit length of the segment. The value includes the 2 bytes for the
   453			// length itself, so we subtract 2 to get the number of remaining bytes.
   454			if err = d.readFull(d.tmp[:2]); err != nil {
   455				return nil, err
   456			}
   457			n := int(d.tmp[0])<<8 + int(d.tmp[1]) - 2
   458			if n < 0 {
   459				return nil, FormatError("short segment length")
   460			}
   461	
   462			switch {
   463			case marker == sof0Marker || marker == sof2Marker: // Start Of Frame.
   464				d.progressive = marker == sof2Marker
   465				err = d.processSOF(n)
   466				if configOnly {
   467					return nil, err
   468				}
   469			case marker == dhtMarker: // Define Huffman Table.
   470				err = d.processDHT(n)
   471			case marker == dqtMarker: // Define Quantization Table.
   472				err = d.processDQT(n)
   473			case marker == sosMarker: // Start Of Scan.
   474				err = d.processSOS(n)
   475			case marker == driMarker: // Define Restart Interval.
   476				err = d.processDRI(n)
   477			case app0Marker <= marker && marker <= app15Marker || marker == comMarker: // APPlication specific, or COMment.
   478				err = d.ignore(n)
   479			default:
   480				err = UnsupportedError("unknown marker")
   481			}
   482			if err != nil {
   483				return nil, err
   484			}
   485		}
   486		if d.img1 != nil {
   487			return d.img1, nil
   488		}
   489		if d.img3 != nil {
   490			return d.img3, nil
   491		}
   492		return nil, FormatError("missing SOS marker")
   493	}
   494	
   495	// Decode reads a JPEG image from r and returns it as an image.Image.
   496	func Decode(r io.Reader) (image.Image, error) {
   497		var d decoder
   498		return d.decode(r, false)
   499	}
   500	
   501	// DecodeConfig returns the color model and dimensions of a JPEG image without
   502	// decoding the entire image.
   503	func DecodeConfig(r io.Reader) (image.Config, error) {
   504		var d decoder
   505		if _, err := d.decode(r, true); err != nil {
   506			return image.Config{}, err
   507		}
   508		switch d.nComp {
   509		case nGrayComponent:
   510			return image.Config{
   511				ColorModel: color.GrayModel,
   512				Width:      d.width,
   513				Height:     d.height,
   514			}, nil
   515		case nColorComponent:
   516			return image.Config{
   517				ColorModel: color.YCbCrModel,
   518				Width:      d.width,
   519				Height:     d.height,
   520			}, nil
   521		}
   522		return image.Config{}, FormatError("missing SOF marker")
   523	}
   524	
   525	func init() {
   526		image.RegisterFormat("jpeg", "\xff\xd8", Decode, DecodeConfig)
   527	}
   528	

View as plain text