Source file src/image/jpeg/scan.go

     1  // Copyright 2012 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
     6  
     7  import (
     8  	"image"
     9  )
    10  
    11  // makeImg allocates and initializes the destination image.
    12  func (d *decoder) makeImg(mxx, myy int) {
    13  	if d.nComp == 1 {
    14  		m := image.NewGray(image.Rect(0, 0, 8*mxx, 8*myy))
    15  		d.img1 = m.SubImage(image.Rect(0, 0, d.width, d.height)).(*image.Gray)
    16  		return
    17  	}
    18  
    19  	// Determine if we need flex mode for non-standard subsampling.
    20  	// Flex mode is needed when:
    21  	// - Cb and Cr have different sampling factors, or
    22  	// - The Y component doesn't have the maximum sampling factors, or
    23  	// - The ratio doesn't match any standard YCbCrSubsampleRatio.
    24  	subsampleRatio := image.YCbCrSubsampleRatio444
    25  	if d.comp[1].h != d.comp[2].h || d.comp[1].v != d.comp[2].v ||
    26  		d.maxH != d.comp[0].h || d.maxV != d.comp[0].v {
    27  		d.flex = true
    28  	} else {
    29  		hRatio := d.maxH / d.comp[1].h
    30  		vRatio := d.maxV / d.comp[1].v
    31  		switch hRatio<<4 | vRatio {
    32  		case 0x11:
    33  			subsampleRatio = image.YCbCrSubsampleRatio444
    34  		case 0x12:
    35  			subsampleRatio = image.YCbCrSubsampleRatio440
    36  		case 0x21:
    37  			subsampleRatio = image.YCbCrSubsampleRatio422
    38  		case 0x22:
    39  			subsampleRatio = image.YCbCrSubsampleRatio420
    40  		case 0x41:
    41  			subsampleRatio = image.YCbCrSubsampleRatio411
    42  		case 0x42:
    43  			subsampleRatio = image.YCbCrSubsampleRatio410
    44  		default:
    45  			d.flex = true
    46  		}
    47  	}
    48  
    49  	m := image.NewYCbCr(image.Rect(0, 0, 8*d.maxH*mxx, 8*d.maxV*myy), subsampleRatio)
    50  	d.img3 = m.SubImage(image.Rect(0, 0, d.width, d.height)).(*image.YCbCr)
    51  
    52  	if d.nComp == 4 {
    53  		h3, v3 := d.comp[3].h, d.comp[3].v
    54  		d.blackPix = make([]byte, 8*h3*mxx*8*v3*myy)
    55  		d.blackStride = 8 * h3 * mxx
    56  	}
    57  }
    58  
    59  // Specified in section B.2.3.
    60  func (d *decoder) processSOS(n int) error {
    61  	if d.nComp == 0 {
    62  		return FormatError("missing SOF marker")
    63  	}
    64  	if n < 6 || 4+2*d.nComp < n || n%2 != 0 {
    65  		return FormatError("SOS has wrong length")
    66  	}
    67  	if err := d.readFull(d.tmp[:n]); err != nil {
    68  		return err
    69  	}
    70  	nComp := int(d.tmp[0])
    71  	if n != 4+2*nComp {
    72  		return FormatError("SOS length inconsistent with number of components")
    73  	}
    74  	var scan [maxComponents]struct {
    75  		compIndex uint8
    76  		td        uint8 // DC table selector.
    77  		ta        uint8 // AC table selector.
    78  	}
    79  	totalHV := 0
    80  	for i := 0; i < nComp; i++ {
    81  		cs := d.tmp[1+2*i] // Component selector.
    82  		compIndex := -1
    83  		for j, comp := range d.comp[:d.nComp] {
    84  			if cs == comp.c {
    85  				compIndex = j
    86  			}
    87  		}
    88  		if compIndex < 0 {
    89  			return FormatError("unknown component selector")
    90  		}
    91  		scan[i].compIndex = uint8(compIndex)
    92  		// Section B.2.3 states that "the value of Cs_j shall be different from
    93  		// the values of Cs_1 through Cs_(j-1)". Since we have previously
    94  		// verified that a frame's component identifiers (C_i values in section
    95  		// B.2.2) are unique, it suffices to check that the implicit indexes
    96  		// into d.comp are unique.
    97  		for j := 0; j < i; j++ {
    98  			if scan[i].compIndex == scan[j].compIndex {
    99  				return FormatError("repeated component selector")
   100  			}
   101  		}
   102  		totalHV += d.comp[compIndex].h * d.comp[compIndex].v
   103  
   104  		// The baseline t <= 1 restriction is specified in table B.3.
   105  		scan[i].td = d.tmp[2+2*i] >> 4
   106  		if t := scan[i].td; t > maxTh || (d.baseline && t > 1) {
   107  			return FormatError("bad Td value")
   108  		}
   109  		scan[i].ta = d.tmp[2+2*i] & 0x0f
   110  		if t := scan[i].ta; t > maxTh || (d.baseline && t > 1) {
   111  			return FormatError("bad Ta value")
   112  		}
   113  	}
   114  	// Section B.2.3 states that if there is more than one component then the
   115  	// total H*V values in a scan must be <= 10.
   116  	if d.nComp > 1 && totalHV > 10 {
   117  		return FormatError("total sampling factors too large")
   118  	}
   119  
   120  	// zigStart and zigEnd are the spectral selection bounds.
   121  	// ah and al are the successive approximation high and low values.
   122  	// The spec calls these values Ss, Se, Ah and Al.
   123  	//
   124  	// For progressive JPEGs, these are the two more-or-less independent
   125  	// aspects of progression. Spectral selection progression is when not
   126  	// all of a block's 64 DCT coefficients are transmitted in one pass.
   127  	// For example, three passes could transmit coefficient 0 (the DC
   128  	// component), coefficients 1-5, and coefficients 6-63, in zig-zag
   129  	// order. Successive approximation is when not all of the bits of a
   130  	// band of coefficients are transmitted in one pass. For example,
   131  	// three passes could transmit the 6 most significant bits, followed
   132  	// by the second-least significant bit, followed by the least
   133  	// significant bit.
   134  	//
   135  	// For sequential JPEGs, these parameters are hard-coded to 0/63/0/0, as
   136  	// per table B.3.
   137  	zigStart, zigEnd, ah, al := int32(0), int32(blockSize-1), uint32(0), uint32(0)
   138  	if d.progressive {
   139  		zigStart = int32(d.tmp[1+2*nComp])
   140  		zigEnd = int32(d.tmp[2+2*nComp])
   141  		ah = uint32(d.tmp[3+2*nComp] >> 4)
   142  		al = uint32(d.tmp[3+2*nComp] & 0x0f)
   143  		if (zigStart == 0 && zigEnd != 0) || zigStart > zigEnd || blockSize <= zigEnd {
   144  			return FormatError("bad spectral selection bounds")
   145  		}
   146  		if zigStart != 0 && nComp != 1 {
   147  			return FormatError("progressive AC coefficients for more than one component")
   148  		}
   149  		if ah != 0 && ah != al+1 {
   150  			return FormatError("bad successive approximation values")
   151  		}
   152  	}
   153  
   154  	// mxx and myy are the number of MCUs (Minimum Coded Units) in the image.
   155  	// The MCU dimensions are based on the maximum sampling factors.
   156  	// For standard subsampling, maxH/maxV equals h0/v0 (Y's factors).
   157  	// For flex mode, Y may not have the maximum factors.
   158  	mxx := (d.width + 8*d.maxH - 1) / (8 * d.maxH)
   159  	myy := (d.height + 8*d.maxV - 1) / (8 * d.maxV)
   160  	if d.img1 == nil && d.img3 == nil {
   161  		d.makeImg(mxx, myy)
   162  	}
   163  	if d.progressive {
   164  		for i := 0; i < nComp; i++ {
   165  			compIndex := scan[i].compIndex
   166  			if d.progCoeffs[compIndex] == nil {
   167  				d.progCoeffs[compIndex] = make([]block, mxx*myy*d.comp[compIndex].h*d.comp[compIndex].v)
   168  			}
   169  		}
   170  	}
   171  
   172  	d.bits = bits{}
   173  	mcu, expectedRST := 0, uint8(rst0Marker)
   174  	var (
   175  		// b is the decoded coefficients, in natural (not zig-zag) order.
   176  		b  block
   177  		dc [maxComponents]int32
   178  		// bx and by are the location of the current block, in units of 8x8
   179  		// blocks: the third block in the first row has (bx, by) = (2, 0).
   180  		bx, by     int
   181  		blockCount int
   182  	)
   183  	for my := 0; my < myy; my++ {
   184  		for mx := 0; mx < mxx; mx++ {
   185  			for i := 0; i < nComp; i++ {
   186  				compIndex := scan[i].compIndex
   187  				hi := d.comp[compIndex].h
   188  				vi := d.comp[compIndex].v
   189  				for j := 0; j < hi*vi; j++ {
   190  					// The blocks are traversed one MCU at a time. For 4:2:0 chroma
   191  					// subsampling, there are four Y 8x8 blocks in every 16x16 MCU.
   192  					//
   193  					// For a sequential 32x16 pixel image, the Y blocks visiting order is:
   194  					//	0 1 4 5
   195  					//	2 3 6 7
   196  					//
   197  					// For progressive images, the interleaved scans (those with nComp > 1)
   198  					// are traversed as above, but non-interleaved scans are traversed left
   199  					// to right, top to bottom:
   200  					//	0 1 2 3
   201  					//	4 5 6 7
   202  					// Only DC scans (zigStart == 0) can be interleaved. AC scans must have
   203  					// only one component.
   204  					//
   205  					// To further complicate matters, for non-interleaved scans, there is no
   206  					// data for any blocks that are inside the image at the MCU level but
   207  					// outside the image at the pixel level. For example, a 24x16 pixel 4:2:0
   208  					// progressive image consists of two 16x16 MCUs. The interleaved scans
   209  					// will process 8 Y blocks:
   210  					//	0 1 4 5
   211  					//	2 3 6 7
   212  					// The non-interleaved scans will process only 6 Y blocks:
   213  					//	0 1 2
   214  					//	3 4 5
   215  					if nComp != 1 {
   216  						bx = hi*mx + j%hi
   217  						by = vi*my + j/hi
   218  					} else {
   219  						q := mxx * hi
   220  						bx = blockCount % q
   221  						by = blockCount / q
   222  						blockCount++
   223  						if bx*8 >= d.width || by*8 >= d.height {
   224  							continue
   225  						}
   226  					}
   227  
   228  					// Load the previous partially decoded coefficients, if applicable.
   229  					if d.progressive {
   230  						b = d.progCoeffs[compIndex][by*mxx*hi+bx]
   231  					} else {
   232  						b = block{}
   233  					}
   234  
   235  					if ah != 0 {
   236  						if err := d.refine(&b, &d.huff[acTable][scan[i].ta], zigStart, zigEnd, 1<<al); err != nil {
   237  							return err
   238  						}
   239  					} else {
   240  						zig := zigStart
   241  						if zig == 0 {
   242  							zig++
   243  							// Decode the DC coefficient, as specified in section F.2.2.1.
   244  							value, err := d.decodeHuffman(&d.huff[dcTable][scan[i].td])
   245  							if err != nil {
   246  								return err
   247  							}
   248  							if value > 16 {
   249  								return UnsupportedError("excessive DC component")
   250  							}
   251  							dcDelta, err := d.receiveExtend(value)
   252  							if err != nil {
   253  								return err
   254  							}
   255  							dc[compIndex] += dcDelta
   256  							b[0] = dc[compIndex] << al
   257  						}
   258  
   259  						if zig <= zigEnd && d.eobRun > 0 {
   260  							d.eobRun--
   261  						} else {
   262  							// Decode the AC coefficients, as specified in section F.2.2.2.
   263  							huff := &d.huff[acTable][scan[i].ta]
   264  							for ; zig <= zigEnd; zig++ {
   265  								value, err := d.decodeHuffman(huff)
   266  								if err != nil {
   267  									return err
   268  								}
   269  								val0 := value >> 4
   270  								val1 := value & 0x0f
   271  								if val1 != 0 {
   272  									zig += int32(val0)
   273  									if zig > zigEnd {
   274  										break
   275  									}
   276  									ac, err := d.receiveExtend(val1)
   277  									if err != nil {
   278  										return err
   279  									}
   280  									b[unzig[zig]] = ac << al
   281  								} else {
   282  									if val0 != 0x0f {
   283  										d.eobRun = uint16(1 << val0)
   284  										if val0 != 0 {
   285  											bits, err := d.decodeBits(int32(val0))
   286  											if err != nil {
   287  												return err
   288  											}
   289  											d.eobRun |= uint16(bits)
   290  										}
   291  										d.eobRun--
   292  										break
   293  									}
   294  									zig += 0x0f
   295  								}
   296  							}
   297  						}
   298  					}
   299  
   300  					if d.progressive {
   301  						// Save the coefficients.
   302  						d.progCoeffs[compIndex][by*mxx*hi+bx] = b
   303  						// At this point, we could call reconstructBlock to dequantize and perform the
   304  						// inverse DCT, to save early stages of a progressive image to the *image.YCbCr
   305  						// buffers (the whole point of progressive encoding), but in Go, the jpeg.Decode
   306  						// function does not return until the entire image is decoded, so we "continue"
   307  						// here to avoid wasted computation. Instead, reconstructBlock is called on each
   308  						// accumulated block by the reconstructProgressiveImage method after all of the
   309  						// SOS markers are processed.
   310  						continue
   311  					}
   312  					if err := d.reconstructBlock(&b, bx, by, int(compIndex)); err != nil {
   313  						return err
   314  					}
   315  				} // for j
   316  			} // for i
   317  			mcu++
   318  			if d.ri > 0 && mcu%d.ri == 0 && mcu < mxx*myy {
   319  				// For well-formed input, the RST[0-7] restart marker follows
   320  				// immediately. For corrupt input, call findRST to try to
   321  				// resynchronize.
   322  				if err := d.readFull(d.tmp[:2]); err != nil {
   323  					return err
   324  				} else if d.tmp[0] != 0xff || d.tmp[1] != expectedRST {
   325  					if err := d.findRST(expectedRST); err != nil {
   326  						return err
   327  					}
   328  				}
   329  				expectedRST++
   330  				if expectedRST == rst7Marker+1 {
   331  					expectedRST = rst0Marker
   332  				}
   333  				// Reset the Huffman decoder.
   334  				d.bits = bits{}
   335  				// Reset the DC components, as per section F.2.1.3.1.
   336  				dc = [maxComponents]int32{}
   337  				// Reset the progressive decoder state, as per section G.1.2.2.
   338  				d.eobRun = 0
   339  			}
   340  		} // for mx
   341  	} // for my
   342  
   343  	return nil
   344  }
   345  
   346  // refine decodes a successive approximation refinement block, as specified in
   347  // section G.1.2.
   348  func (d *decoder) refine(b *block, h *huffman, zigStart, zigEnd, delta int32) error {
   349  	// Refining a DC component is trivial.
   350  	if zigStart == 0 {
   351  		if zigEnd != 0 {
   352  			panic("unreachable")
   353  		}
   354  		bit, err := d.decodeBit()
   355  		if err != nil {
   356  			return err
   357  		}
   358  		if bit {
   359  			b[0] |= delta
   360  		}
   361  		return nil
   362  	}
   363  
   364  	// Refining AC components is more complicated; see sections G.1.2.2 and G.1.2.3.
   365  	zig := zigStart
   366  	if d.eobRun == 0 {
   367  	loop:
   368  		for ; zig <= zigEnd; zig++ {
   369  			z := int32(0)
   370  			value, err := d.decodeHuffman(h)
   371  			if err != nil {
   372  				return err
   373  			}
   374  			val0 := value >> 4
   375  			val1 := value & 0x0f
   376  
   377  			switch val1 {
   378  			case 0:
   379  				if val0 != 0x0f {
   380  					d.eobRun = uint16(1 << val0)
   381  					if val0 != 0 {
   382  						bits, err := d.decodeBits(int32(val0))
   383  						if err != nil {
   384  							return err
   385  						}
   386  						d.eobRun |= uint16(bits)
   387  					}
   388  					break loop
   389  				}
   390  			case 1:
   391  				z = delta
   392  				bit, err := d.decodeBit()
   393  				if err != nil {
   394  					return err
   395  				}
   396  				if !bit {
   397  					z = -z
   398  				}
   399  			default:
   400  				return FormatError("unexpected Huffman code")
   401  			}
   402  
   403  			zig, err = d.refineNonZeroes(b, zig, zigEnd, int32(val0), delta)
   404  			if err != nil {
   405  				return err
   406  			}
   407  			if zig > zigEnd {
   408  				return FormatError("too many coefficients")
   409  			}
   410  			if z != 0 {
   411  				b[unzig[zig]] = z
   412  			}
   413  		}
   414  	}
   415  	if d.eobRun > 0 {
   416  		d.eobRun--
   417  		if _, err := d.refineNonZeroes(b, zig, zigEnd, -1, delta); err != nil {
   418  			return err
   419  		}
   420  	}
   421  	return nil
   422  }
   423  
   424  // refineNonZeroes refines non-zero entries of b in zig-zag order. If nz >= 0,
   425  // the first nz zero entries are skipped over.
   426  func (d *decoder) refineNonZeroes(b *block, zig, zigEnd, nz, delta int32) (int32, error) {
   427  	for ; zig <= zigEnd; zig++ {
   428  		u := unzig[zig]
   429  		if b[u] == 0 {
   430  			if nz == 0 {
   431  				break
   432  			}
   433  			nz--
   434  			continue
   435  		}
   436  		bit, err := d.decodeBit()
   437  		if err != nil {
   438  			return 0, err
   439  		}
   440  		if !bit {
   441  			continue
   442  		}
   443  		if b[u] >= 0 {
   444  			b[u] += delta
   445  		} else {
   446  			b[u] -= delta
   447  		}
   448  	}
   449  	return zig, nil
   450  }
   451  
   452  func (d *decoder) reconstructProgressiveImage() error {
   453  	// The mxx, by and bx variables have the same meaning as in the
   454  	// processSOS method.
   455  	mxx := (d.width + 8*d.maxH - 1) / (8 * d.maxH)
   456  	for i := 0; i < d.nComp; i++ {
   457  		if d.progCoeffs[i] == nil {
   458  			continue
   459  		}
   460  		v := 8 * d.maxV / d.comp[i].v
   461  		h := 8 * d.maxH / d.comp[i].h
   462  		stride := mxx * d.comp[i].h
   463  		for by := 0; by*v < d.height; by++ {
   464  			for bx := 0; bx*h < d.width; bx++ {
   465  				if err := d.reconstructBlock(&d.progCoeffs[i][by*stride+bx], bx, by, i); err != nil {
   466  					return err
   467  				}
   468  			}
   469  		}
   470  	}
   471  	return nil
   472  }
   473  
   474  // reconstructBlock dequantizes, performs the inverse DCT and stores the block
   475  // to the image.
   476  func (d *decoder) reconstructBlock(b *block, bx, by, compIndex int) error {
   477  	qt := &d.quant[d.comp[compIndex].tq]
   478  	for zig := 0; zig < blockSize; zig++ {
   479  		b[unzig[zig]] *= qt[zig]
   480  	}
   481  	idct(b)
   482  
   483  	var h, v int
   484  	if d.flex {
   485  		// Flex mode: scale bx and by according to the component's sampling factors.
   486  		h = d.comp[compIndex].expandH
   487  		v = d.comp[compIndex].expandV
   488  		bx, by = bx*h, by*v
   489  	}
   490  
   491  	dst, stride := []byte(nil), 0
   492  	if d.nComp == 1 {
   493  		dst, stride = d.img1.Pix[8*(by*d.img1.Stride+bx):], d.img1.Stride
   494  	} else {
   495  		switch compIndex {
   496  		case 0:
   497  			dst, stride = d.img3.Y[8*(by*d.img3.YStride+bx):], d.img3.YStride
   498  		case 1:
   499  			dst, stride = d.img3.Cb[8*(by*d.img3.CStride+bx):], d.img3.CStride
   500  		case 2:
   501  			dst, stride = d.img3.Cr[8*(by*d.img3.CStride+bx):], d.img3.CStride
   502  		case 3:
   503  			dst, stride = d.blackPix[8*(by*d.blackStride+bx):], d.blackStride
   504  		default:
   505  			return UnsupportedError("too many components")
   506  		}
   507  	}
   508  
   509  	if d.flex {
   510  		// Flex mode: expand each source pixel to h×v destination pixels.
   511  		for y := 0; y < 8; y++ {
   512  			y8 := y * 8
   513  			yv := y * v
   514  			for x := 0; x < 8; x++ {
   515  				val := uint8(max(0, min(255, b[y8+x]+128)))
   516  				xh := x * h
   517  				for yy := 0; yy < v; yy++ {
   518  					for xx := 0; xx < h; xx++ {
   519  						dst[(yv+yy)*stride+xh+xx] = val
   520  					}
   521  				}
   522  			}
   523  		}
   524  		return nil
   525  	}
   526  
   527  	// Level shift by +128, clip to [0, 255], and write to dst.
   528  	for y := 0; y < 8; y++ {
   529  		y8 := y * 8
   530  		yStride := y * stride
   531  		for x := 0; x < 8; x++ {
   532  			dst[yStride+x] = uint8(max(0, min(255, b[y8+x]+128)))
   533  		}
   534  	}
   535  	return nil
   536  }
   537  
   538  // findRST advances past the next RST restart marker that matches expectedRST.
   539  // Other than I/O errors, it is also an error if we encounter an {0xFF, M}
   540  // two-byte marker sequence where M is not 0x00, 0xFF or the expectedRST.
   541  //
   542  // This is similar to libjpeg's jdmarker.c's next_marker function.
   543  // https://github.com/libjpeg-turbo/libjpeg-turbo/blob/2dfe6c0fe9e18671105e94f7cbf044d4a1d157e6/jdmarker.c#L892-L935
   544  //
   545  // Precondition: d.tmp[:2] holds the next two bytes of JPEG-encoded input
   546  // (input in the d.readFull sense).
   547  func (d *decoder) findRST(expectedRST uint8) error {
   548  	for {
   549  		// i is the index such that, at the bottom of the loop, we read 2-i
   550  		// bytes into d.tmp[i:2], maintaining the invariant that d.tmp[:2]
   551  		// holds the next two bytes of JPEG-encoded input. It is either 0 or 1,
   552  		// so that each iteration advances by 1 or 2 bytes (or returns).
   553  		i := 0
   554  
   555  		if d.tmp[0] == 0xff {
   556  			if d.tmp[1] == expectedRST {
   557  				return nil
   558  			} else if d.tmp[1] == 0xff {
   559  				i = 1
   560  			} else if d.tmp[1] != 0x00 {
   561  				// libjpeg's jdmarker.c's jpeg_resync_to_restart does something
   562  				// fancy here, treating RST markers within two (modulo 8) of
   563  				// expectedRST differently from RST markers that are 'more
   564  				// distant'. Until we see evidence that recovering from such
   565  				// cases is frequent enough to be worth the complexity, we take
   566  				// a simpler approach for now. Any marker that's not 0x00, 0xff
   567  				// or expectedRST is a fatal FormatError.
   568  				return FormatError("bad RST marker")
   569  			}
   570  
   571  		} else if d.tmp[1] == 0xff {
   572  			d.tmp[0] = 0xff
   573  			i = 1
   574  		}
   575  
   576  		if err := d.readFull(d.tmp[i:2]); err != nil {
   577  			return err
   578  		}
   579  	}
   580  }
   581  

View as plain text