scan.go

Documentation: image/jpeg

		 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  				// A more sophisticated decoder could use RST[0-7] markers to resynchronize from corrupt input,
	 309  				// but this one assumes well-formed input, and hence the restart marker follows immediately.
	 310  				if err := d.readFull(d.tmp[:2]); err != nil {
	 311  					return err
	 312  				}
	 313  
	 314  				// Section F.1.2.3 says that "Byte alignment of markers is
	 315  				// achieved by padding incomplete bytes with 1-bits. If padding
	 316  				// with 1-bits creates a X’FF’ value, a zero byte is stuffed
	 317  				// before adding the marker."
	 318  				//
	 319  				// Seeing "\xff\x00" here is not spec compliant, as we are not
	 320  				// expecting an *incomplete* byte (that needed padding). Still,
	 321  				// some real world encoders (see golang.org/issue/28717) insert
	 322  				// it, so we accept it and re-try the 2 byte read.
	 323  				//
	 324  				// libjpeg issues a warning (but not an error) for this:
	 325  				// https://github.com/LuaDist/libjpeg/blob/6c0fcb8ddee365e7abc4d332662b06900612e923/jdmarker.c#L1041-L1046
	 326  				if d.tmp[0] == 0xff && d.tmp[1] == 0x00 {
	 327  					if err := d.readFull(d.tmp[:2]); err != nil {
	 328  						return err
	 329  					}
	 330  				}
	 331  
	 332  				if d.tmp[0] != 0xff || d.tmp[1] != expectedRST {
	 333  					return FormatError("bad RST marker")
	 334  				}
	 335  				expectedRST++
	 336  				if expectedRST == rst7Marker+1 {
	 337  					expectedRST = rst0Marker
	 338  				}
	 339  				// Reset the Huffman decoder.
	 340  				d.bits = bits{}
	 341  				// Reset the DC components, as per section F.2.1.3.1.
	 342  				dc = [maxComponents]int32{}
	 343  				// Reset the progressive decoder state, as per section G.1.2.2.
	 344  				d.eobRun = 0
	 345  			}
	 346  		} // for mx
	 347  	} // for my
	 348  
	 349  	return nil
	 350  }
	 351  
	 352  // refine decodes a successive approximation refinement block, as specified in
	 353  // section G.1.2.
	 354  func (d *decoder) refine(b *block, h *huffman, zigStart, zigEnd, delta int32) error {
	 355  	// Refining a DC component is trivial.
	 356  	if zigStart == 0 {
	 357  		if zigEnd != 0 {
	 358  			panic("unreachable")
	 359  		}
	 360  		bit, err := d.decodeBit()
	 361  		if err != nil {
	 362  			return err
	 363  		}
	 364  		if bit {
	 365  			b[0] |= delta
	 366  		}
	 367  		return nil
	 368  	}
	 369  
	 370  	// Refining AC components is more complicated; see sections G.1.2.2 and G.1.2.3.
	 371  	zig := zigStart
	 372  	if d.eobRun == 0 {
	 373  	loop:
	 374  		for ; zig <= zigEnd; zig++ {
	 375  			z := int32(0)
	 376  			value, err := d.decodeHuffman(h)
	 377  			if err != nil {
	 378  				return err
	 379  			}
	 380  			val0 := value >> 4
	 381  			val1 := value & 0x0f
	 382  
	 383  			switch val1 {
	 384  			case 0:
	 385  				if val0 != 0x0f {
	 386  					d.eobRun = uint16(1 << val0)
	 387  					if val0 != 0 {
	 388  						bits, err := d.decodeBits(int32(val0))
	 389  						if err != nil {
	 390  							return err
	 391  						}
	 392  						d.eobRun |= uint16(bits)
	 393  					}
	 394  					break loop
	 395  				}
	 396  			case 1:
	 397  				z = delta
	 398  				bit, err := d.decodeBit()
	 399  				if err != nil {
	 400  					return err
	 401  				}
	 402  				if !bit {
	 403  					z = -z
	 404  				}
	 405  			default:
	 406  				return FormatError("unexpected Huffman code")
	 407  			}
	 408  
	 409  			zig, err = d.refineNonZeroes(b, zig, zigEnd, int32(val0), delta)
	 410  			if err != nil {
	 411  				return err
	 412  			}
	 413  			if zig > zigEnd {
	 414  				return FormatError("too many coefficients")
	 415  			}
	 416  			if z != 0 {
	 417  				b[unzig[zig]] = z
	 418  			}
	 419  		}
	 420  	}
	 421  	if d.eobRun > 0 {
	 422  		d.eobRun--
	 423  		if _, err := d.refineNonZeroes(b, zig, zigEnd, -1, delta); err != nil {
	 424  			return err
	 425  		}
	 426  	}
	 427  	return nil
	 428  }
	 429  
	 430  // refineNonZeroes refines non-zero entries of b in zig-zag order. If nz >= 0,
	 431  // the first nz zero entries are skipped over.
	 432  func (d *decoder) refineNonZeroes(b *block, zig, zigEnd, nz, delta int32) (int32, error) {
	 433  	for ; zig <= zigEnd; zig++ {
	 434  		u := unzig[zig]
	 435  		if b[u] == 0 {
	 436  			if nz == 0 {
	 437  				break
	 438  			}
	 439  			nz--
	 440  			continue
	 441  		}
	 442  		bit, err := d.decodeBit()
	 443  		if err != nil {
	 444  			return 0, err
	 445  		}
	 446  		if !bit {
	 447  			continue
	 448  		}
	 449  		if b[u] >= 0 {
	 450  			b[u] += delta
	 451  		} else {
	 452  			b[u] -= delta
	 453  		}
	 454  	}
	 455  	return zig, nil
	 456  }
	 457  
	 458  func (d *decoder) reconstructProgressiveImage() error {
	 459  	// The h0, mxx, by and bx variables have the same meaning as in the
	 460  	// processSOS method.
	 461  	h0 := d.comp[0].h
	 462  	mxx := (d.width + 8*h0 - 1) / (8 * h0)
	 463  	for i := 0; i < d.nComp; i++ {
	 464  		if d.progCoeffs[i] == nil {
	 465  			continue
	 466  		}
	 467  		v := 8 * d.comp[0].v / d.comp[i].v
	 468  		h := 8 * d.comp[0].h / d.comp[i].h
	 469  		stride := mxx * d.comp[i].h
	 470  		for by := 0; by*v < d.height; by++ {
	 471  			for bx := 0; bx*h < d.width; bx++ {
	 472  				if err := d.reconstructBlock(&d.progCoeffs[i][by*stride+bx], bx, by, i); err != nil {
	 473  					return err
	 474  				}
	 475  			}
	 476  		}
	 477  	}
	 478  	return nil
	 479  }
	 480  
	 481  // reconstructBlock dequantizes, performs the inverse DCT and stores the block
	 482  // to the image.
	 483  func (d *decoder) reconstructBlock(b *block, bx, by, compIndex int) error {
	 484  	qt := &d.quant[d.comp[compIndex].tq]
	 485  	for zig := 0; zig < blockSize; zig++ {
	 486  		b[unzig[zig]] *= qt[zig]
	 487  	}
	 488  	idct(b)
	 489  	dst, stride := []byte(nil), 0
	 490  	if d.nComp == 1 {
	 491  		dst, stride = d.img1.Pix[8*(by*d.img1.Stride+bx):], d.img1.Stride
	 492  	} else {
	 493  		switch compIndex {
	 494  		case 0:
	 495  			dst, stride = d.img3.Y[8*(by*d.img3.YStride+bx):], d.img3.YStride
	 496  		case 1:
	 497  			dst, stride = d.img3.Cb[8*(by*d.img3.CStride+bx):], d.img3.CStride
	 498  		case 2:
	 499  			dst, stride = d.img3.Cr[8*(by*d.img3.CStride+bx):], d.img3.CStride
	 500  		case 3:
	 501  			dst, stride = d.blackPix[8*(by*d.blackStride+bx):], d.blackStride
	 502  		default:
	 503  			return UnsupportedError("too many components")
	 504  		}
	 505  	}
	 506  	// Level shift by +128, clip to [0, 255], and write to dst.
	 507  	for y := 0; y < 8; y++ {
	 508  		y8 := y * 8
	 509  		yStride := y * stride
	 510  		for x := 0; x < 8; x++ {
	 511  			c := b[y8+x]
	 512  			if c < -128 {
	 513  				c = 0
	 514  			} else if c > 127 {
	 515  				c = 255
	 516  			} else {
	 517  				c += 128
	 518  			}
	 519  			dst[yStride+x] = uint8(c)
	 520  		}
	 521  	}
	 522  	return nil
	 523  }
	 524
View as plain text