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