Source file src/pkg/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		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					if d.tmp[0] != 0xff || d.tmp[1] != expectedRST {
   314						return FormatError("bad RST marker")
   315					}
   316					expectedRST++
   317					if expectedRST == rst7Marker+1 {
   318						expectedRST = rst0Marker
   319					}
   320					// Reset the Huffman decoder.
   321					d.bits = bits{}
   322					// Reset the DC components, as per section F.2.1.3.1.
   323					dc = [maxComponents]int32{}
   324					// Reset the progressive decoder state, as per section G.1.2.2.
   325					d.eobRun = 0
   326				}
   327			} // for mx
   328		} // for my
   329	
   330		return nil
   331	}
   332	
   333	// refine decodes a successive approximation refinement block, as specified in
   334	// section G.1.2.
   335	func (d *decoder) refine(b *block, h *huffman, zigStart, zigEnd, delta int32) error {
   336		// Refining a DC component is trivial.
   337		if zigStart == 0 {
   338			if zigEnd != 0 {
   339				panic("unreachable")
   340			}
   341			bit, err := d.decodeBit()
   342			if err != nil {
   343				return err
   344			}
   345			if bit {
   346				b[0] |= delta
   347			}
   348			return nil
   349		}
   350	
   351		// Refining AC components is more complicated; see sections G.1.2.2 and G.1.2.3.
   352		zig := zigStart
   353		if d.eobRun == 0 {
   354		loop:
   355			for ; zig <= zigEnd; zig++ {
   356				z := int32(0)
   357				value, err := d.decodeHuffman(h)
   358				if err != nil {
   359					return err
   360				}
   361				val0 := value >> 4
   362				val1 := value & 0x0f
   363	
   364				switch val1 {
   365				case 0:
   366					if val0 != 0x0f {
   367						d.eobRun = uint16(1 << val0)
   368						if val0 != 0 {
   369							bits, err := d.decodeBits(int32(val0))
   370							if err != nil {
   371								return err
   372							}
   373							d.eobRun |= uint16(bits)
   374						}
   375						break loop
   376					}
   377				case 1:
   378					z = delta
   379					bit, err := d.decodeBit()
   380					if err != nil {
   381						return err
   382					}
   383					if !bit {
   384						z = -z
   385					}
   386				default:
   387					return FormatError("unexpected Huffman code")
   388				}
   389	
   390				zig, err = d.refineNonZeroes(b, zig, zigEnd, int32(val0), delta)
   391				if err != nil {
   392					return err
   393				}
   394				if zig > zigEnd {
   395					return FormatError("too many coefficients")
   396				}
   397				if z != 0 {
   398					b[unzig[zig]] = z
   399				}
   400			}
   401		}
   402		if d.eobRun > 0 {
   403			d.eobRun--
   404			if _, err := d.refineNonZeroes(b, zig, zigEnd, -1, delta); err != nil {
   405				return err
   406			}
   407		}
   408		return nil
   409	}
   410	
   411	// refineNonZeroes refines non-zero entries of b in zig-zag order. If nz >= 0,
   412	// the first nz zero entries are skipped over.
   413	func (d *decoder) refineNonZeroes(b *block, zig, zigEnd, nz, delta int32) (int32, error) {
   414		for ; zig <= zigEnd; zig++ {
   415			u := unzig[zig]
   416			if b[u] == 0 {
   417				if nz == 0 {
   418					break
   419				}
   420				nz--
   421				continue
   422			}
   423			bit, err := d.decodeBit()
   424			if err != nil {
   425				return 0, err
   426			}
   427			if !bit {
   428				continue
   429			}
   430			if b[u] >= 0 {
   431				b[u] += delta
   432			} else {
   433				b[u] -= delta
   434			}
   435		}
   436		return zig, nil
   437	}
   438	
   439	func (d *decoder) reconstructProgressiveImage() error {
   440		// The h0, mxx, by and bx variables have the same meaning as in the
   441		// processSOS method.
   442		h0 := d.comp[0].h
   443		mxx := (d.width + 8*h0 - 1) / (8 * h0)
   444		for i := 0; i < d.nComp; i++ {
   445			if d.progCoeffs[i] == nil {
   446				continue
   447			}
   448			v := 8 * d.comp[0].v / d.comp[i].v
   449			h := 8 * d.comp[0].h / d.comp[i].h
   450			stride := mxx * d.comp[i].h
   451			for by := 0; by*v < d.height; by++ {
   452				for bx := 0; bx*h < d.width; bx++ {
   453					if err := d.reconstructBlock(&d.progCoeffs[i][by*stride+bx], bx, by, i); err != nil {
   454						return err
   455					}
   456				}
   457			}
   458		}
   459		return nil
   460	}
   461	
   462	// reconstructBlock dequantizes, performs the inverse DCT and stores the block
   463	// to the image.
   464	func (d *decoder) reconstructBlock(b *block, bx, by, compIndex int) error {
   465		qt := &d.quant[d.comp[compIndex].tq]
   466		for zig := 0; zig < blockSize; zig++ {
   467			b[unzig[zig]] *= qt[zig]
   468		}
   469		idct(b)
   470		dst, stride := []byte(nil), 0
   471		if d.nComp == 1 {
   472			dst, stride = d.img1.Pix[8*(by*d.img1.Stride+bx):], d.img1.Stride
   473		} else {
   474			switch compIndex {
   475			case 0:
   476				dst, stride = d.img3.Y[8*(by*d.img3.YStride+bx):], d.img3.YStride
   477			case 1:
   478				dst, stride = d.img3.Cb[8*(by*d.img3.CStride+bx):], d.img3.CStride
   479			case 2:
   480				dst, stride = d.img3.Cr[8*(by*d.img3.CStride+bx):], d.img3.CStride
   481			case 3:
   482				dst, stride = d.blackPix[8*(by*d.blackStride+bx):], d.blackStride
   483			default:
   484				return UnsupportedError("too many components")
   485			}
   486		}
   487		// Level shift by +128, clip to [0, 255], and write to dst.
   488		for y := 0; y < 8; y++ {
   489			y8 := y * 8
   490			yStride := y * stride
   491			for x := 0; x < 8; x++ {
   492				c := b[y8+x]
   493				if c < -128 {
   494					c = 0
   495				} else if c > 127 {
   496					c = 255
   497				} else {
   498					c += 128
   499				}
   500				dst[yStride+x] = uint8(c)
   501			}
   502		}
   503		return nil
   504	}
   505	

View as plain text