reconstruct.go

Documentation: golang.org/x/image/vp8

     1  // Copyright 2011 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 vp8
     6  
     7  // This file implements decoding DCT/WHT residual coefficients and
     8  // reconstructing YCbCr data equal to predicted values plus residuals.
     9  //
    10  // There are 1*16*16 + 2*8*8 + 1*4*4 coefficients per macroblock:
    11  //	- 1*16*16 luma DCT coefficients,
    12  //	- 2*8*8 chroma DCT coefficients, and
    13  //	- 1*4*4 luma WHT coefficients.
    14  // Coefficients are read in lots of 16, and the later coefficients in each lot
    15  // are often zero.
    16  //
    17  // The YCbCr data consists of 1*16*16 luma values and 2*8*8 chroma values,
    18  // plus previously decoded values along the top and left borders. The combined
    19  // values are laid out as a [1+16+1+8][32]uint8 so that vertically adjacent
    20  // samples are 32 bytes apart. In detail, the layout is:
    21  //
    22  //	0 1 2 3 4 5 6 7  8 9 0 1 2 3 4 5  6 7 8 9 0 1 2 3  4 5 6 7 8 9 0 1
    23  //	. . . . . . . a  b b b b b b b b  b b b b b b b b  c c c c . . . .	0
    24  //	. . . . . . . d  Y Y Y Y Y Y Y Y  Y Y Y Y Y Y Y Y  . . . . . . . .	1
    25  //	. . . . . . . d  Y Y Y Y Y Y Y Y  Y Y Y Y Y Y Y Y  . . . . . . . .	2
    26  //	. . . . . . . d  Y Y Y Y Y Y Y Y  Y Y Y Y Y Y Y Y  . . . . . . . .	3
    27  //	. . . . . . . d  Y Y Y Y Y Y Y Y  Y Y Y Y Y Y Y Y  c c c c . . . .	4
    28  //	. . . . . . . d  Y Y Y Y Y Y Y Y  Y Y Y Y Y Y Y Y  . . . . . . . .	5
    29  //	. . . . . . . d  Y Y Y Y Y Y Y Y  Y Y Y Y Y Y Y Y  . . . . . . . .	6
    30  //	. . . . . . . d  Y Y Y Y Y Y Y Y  Y Y Y Y Y Y Y Y  . . . . . . . .	7
    31  //	. . . . . . . d  Y Y Y Y Y Y Y Y  Y Y Y Y Y Y Y Y  c c c c . . . .	8
    32  //	. . . . . . . d  Y Y Y Y Y Y Y Y  Y Y Y Y Y Y Y Y  . . . . . . . .	9
    33  //	. . . . . . . d  Y Y Y Y Y Y Y Y  Y Y Y Y Y Y Y Y  . . . . . . . .	10
    34  //	. . . . . . . d  Y Y Y Y Y Y Y Y  Y Y Y Y Y Y Y Y  . . . . . . . .	11
    35  //	. . . . . . . d  Y Y Y Y Y Y Y Y  Y Y Y Y Y Y Y Y  c c c c . . . .	12
    36  //	. . . . . . . d  Y Y Y Y Y Y Y Y  Y Y Y Y Y Y Y Y  . . . . . . . .	13
    37  //	. . . . . . . d  Y Y Y Y Y Y Y Y  Y Y Y Y Y Y Y Y  . . . . . . . .	14
    38  //	. . . . . . . d  Y Y Y Y Y Y Y Y  Y Y Y Y Y Y Y Y  . . . . . . . .	15
    39  //	. . . . . . . d  Y Y Y Y Y Y Y Y  Y Y Y Y Y Y Y Y  . . . . . . . .	16
    40  //	. . . . . . . e  f f f f f f f f  . . . . . . . g  h h h h h h h h	17
    41  //	. . . . . . . i  B B B B B B B B  . . . . . . . j  R R R R R R R R	18
    42  //	. . . . . . . i  B B B B B B B B  . . . . . . . j  R R R R R R R R	19
    43  //	. . . . . . . i  B B B B B B B B  . . . . . . . j  R R R R R R R R	20
    44  //	. . . . . . . i  B B B B B B B B  . . . . . . . j  R R R R R R R R	21
    45  //	. . . . . . . i  B B B B B B B B  . . . . . . . j  R R R R R R R R	22
    46  //	. . . . . . . i  B B B B B B B B  . . . . . . . j  R R R R R R R R	23
    47  //	. . . . . . . i  B B B B B B B B  . . . . . . . j  R R R R R R R R	24
    48  //	. . . . . . . i  B B B B B B B B  . . . . . . . j  R R R R R R R R	25
    49  //
    50  // Y, B and R are the reconstructed luma (Y) and chroma (B, R) values.
    51  // The Y values are predicted (either as one 16x16 region or 16 4x4 regions)
    52  // based on the row above's Y values (some combination of {abc} or {dYC}) and
    53  // the column left's Y values (either {ad} or {bY}). Similarly, B and R values
    54  // are predicted on the row above and column left of their respective 8x8
    55  // region: {efi} for B, {ghj} for R.
    56  //
    57  // For uppermost macroblocks (i.e. those with mby == 0), the {abcefgh} values
    58  // are initialized to 0x81. Otherwise, they are copied from the bottom row of
    59  // the macroblock above. The {c} values are then duplicated from row 0 to rows
    60  // 4, 8 and 12 of the ybr workspace.
    61  // Similarly, for leftmost macroblocks (i.e. those with mbx == 0), the {adeigj}
    62  // values are initialized to 0x7f. Otherwise, they are copied from the right
    63  // column of the macroblock to the left.
    64  // For the top-left macroblock (with mby == 0 && mbx == 0), {aeg} is 0x81.
    65  //
    66  // When moving from one macroblock to the next horizontally, the {adeigj}
    67  // values can simply be copied from the workspace to itself, shifted by 8 or
    68  // 16 columns. When moving from one macroblock to the next vertically,
    69  // filtering can occur and hence the row values have to be copied from the
    70  // post-filtered image instead of the pre-filtered workspace.
    71  
    72  const (
    73  	bCoeffBase   = 1*16*16 + 0*8*8
    74  	rCoeffBase   = 1*16*16 + 1*8*8
    75  	whtCoeffBase = 1*16*16 + 2*8*8
    76  )
    77  
    78  const (
    79  	ybrYX = 8
    80  	ybrYY = 1
    81  	ybrBX = 8
    82  	ybrBY = 18
    83  	ybrRX = 24
    84  	ybrRY = 18
    85  )
    86  
    87  // prepareYBR prepares the {abcdefghij} elements of ybr.
    88  func (d *Decoder) prepareYBR(mbx, mby int) {
    89  	if mbx == 0 {
    90  		for y := 0; y < 17; y++ {
    91  			d.ybr[y][7] = 0x81
    92  		}
    93  		for y := 17; y < 26; y++ {
    94  			d.ybr[y][7] = 0x81
    95  			d.ybr[y][23] = 0x81
    96  		}
    97  	} else {
    98  		for y := 0; y < 17; y++ {
    99  			d.ybr[y][7] = d.ybr[y][7+16]
   100  		}
   101  		for y := 17; y < 26; y++ {
   102  			d.ybr[y][7] = d.ybr[y][15]
   103  			d.ybr[y][23] = d.ybr[y][31]
   104  		}
   105  	}
   106  	if mby == 0 {
   107  		for x := 7; x < 28; x++ {
   108  			d.ybr[0][x] = 0x7f
   109  		}
   110  		for x := 7; x < 16; x++ {
   111  			d.ybr[17][x] = 0x7f
   112  		}
   113  		for x := 23; x < 32; x++ {
   114  			d.ybr[17][x] = 0x7f
   115  		}
   116  	} else {
   117  		for i := 0; i < 16; i++ {
   118  			d.ybr[0][8+i] = d.img.Y[(16*mby-1)*d.img.YStride+16*mbx+i]
   119  		}
   120  		for i := 0; i < 8; i++ {
   121  			d.ybr[17][8+i] = d.img.Cb[(8*mby-1)*d.img.CStride+8*mbx+i]
   122  		}
   123  		for i := 0; i < 8; i++ {
   124  			d.ybr[17][24+i] = d.img.Cr[(8*mby-1)*d.img.CStride+8*mbx+i]
   125  		}
   126  		if mbx == d.mbw-1 {
   127  			for i := 16; i < 20; i++ {
   128  				d.ybr[0][8+i] = d.img.Y[(16*mby-1)*d.img.YStride+16*mbx+15]
   129  			}
   130  		} else {
   131  			for i := 16; i < 20; i++ {
   132  				d.ybr[0][8+i] = d.img.Y[(16*mby-1)*d.img.YStride+16*mbx+i]
   133  			}
   134  		}
   135  	}
   136  	for y := 4; y < 16; y += 4 {
   137  		d.ybr[y][24] = d.ybr[0][24]
   138  		d.ybr[y][25] = d.ybr[0][25]
   139  		d.ybr[y][26] = d.ybr[0][26]
   140  		d.ybr[y][27] = d.ybr[0][27]
   141  	}
   142  }
   143  
   144  // btou converts a bool to a 0/1 value.
   145  func btou(b bool) uint8 {
   146  	if b {
   147  		return 1
   148  	}
   149  	return 0
   150  }
   151  
   152  // pack packs four 0/1 values into four bits of a uint32.
   153  func pack(x [4]uint8, shift int) uint32 {
   154  	u := uint32(x[0])<<0 | uint32(x[1])<<1 | uint32(x[2])<<2 | uint32(x[3])<<3
   155  	return u << uint(shift)
   156  }
   157  
   158  // unpack unpacks four 0/1 values from a four-bit value.
   159  var unpack = [16][4]uint8{
   160  	{0, 0, 0, 0},
   161  	{1, 0, 0, 0},
   162  	{0, 1, 0, 0},
   163  	{1, 1, 0, 0},
   164  	{0, 0, 1, 0},
   165  	{1, 0, 1, 0},
   166  	{0, 1, 1, 0},
   167  	{1, 1, 1, 0},
   168  	{0, 0, 0, 1},
   169  	{1, 0, 0, 1},
   170  	{0, 1, 0, 1},
   171  	{1, 1, 0, 1},
   172  	{0, 0, 1, 1},
   173  	{1, 0, 1, 1},
   174  	{0, 1, 1, 1},
   175  	{1, 1, 1, 1},
   176  }
   177  
   178  var (
   179  	// The mapping from 4x4 region position to band is specified in section 13.3.
   180  	bands = [17]uint8{0, 1, 2, 3, 6, 4, 5, 6, 6, 6, 6, 6, 6, 6, 6, 7, 0}
   181  	// Category probabilties are specified in section 13.2.
   182  	// Decoding categories 1 and 2 are done inline.
   183  	cat3456 = [4][12]uint8{
   184  		{173, 148, 140, 0, 0, 0, 0, 0, 0, 0, 0, 0},
   185  		{176, 155, 140, 135, 0, 0, 0, 0, 0, 0, 0, 0},
   186  		{180, 157, 141, 134, 130, 0, 0, 0, 0, 0, 0, 0},
   187  		{254, 254, 243, 230, 196, 177, 153, 140, 133, 130, 129, 0},
   188  	}
   189  	// The zigzag order is:
   190  	//	0  1  5  6
   191  	//	2  4  7 12
   192  	//	3  8 11 13
   193  	//	9 10 14 15
   194  	zigzag = [16]uint8{0, 1, 4, 8, 5, 2, 3, 6, 9, 12, 13, 10, 7, 11, 14, 15}
   195  )
   196  
   197  // parseResiduals4 parses a 4x4 region of residual coefficients, as specified
   198  // in section 13.3, and returns a 0/1 value indicating whether there was at
   199  // least one non-zero coefficient.
   200  // r is the partition to read bits from.
   201  // plane and context describe which token probability table to use. context is
   202  // either 0, 1 or 2, and equals how many of the macroblock left and macroblock
   203  // above have non-zero coefficients.
   204  // quant are the DC/AC quantization factors.
   205  // skipFirstCoeff is whether the DC coefficient has already been parsed.
   206  // coeffBase is the base index of d.coeff to write to.
   207  func (d *Decoder) parseResiduals4(r *partition, plane int, context uint8, quant [2]uint16, skipFirstCoeff bool, coeffBase int) uint8 {
   208  	prob, n := &d.tokenProb[plane], 0
   209  	if skipFirstCoeff {
   210  		n = 1
   211  	}
   212  	p := prob[bands[n]][context]
   213  	if !r.readBit(p[0]) {
   214  		return 0
   215  	}
   216  	for n != 16 {
   217  		n++
   218  		if !r.readBit(p[1]) {
   219  			p = prob[bands[n]][0]
   220  			continue
   221  		}
   222  		var v uint32
   223  		if !r.readBit(p[2]) {
   224  			v = 1
   225  			p = prob[bands[n]][1]
   226  		} else {
   227  			if !r.readBit(p[3]) {
   228  				if !r.readBit(p[4]) {
   229  					v = 2
   230  				} else {
   231  					v = 3 + r.readUint(p[5], 1)
   232  				}
   233  			} else if !r.readBit(p[6]) {
   234  				if !r.readBit(p[7]) {
   235  					// Category 1.
   236  					v = 5 + r.readUint(159, 1)
   237  				} else {
   238  					// Category 2.
   239  					v = 7 + 2*r.readUint(165, 1) + r.readUint(145, 1)
   240  				}
   241  			} else {
   242  				// Categories 3, 4, 5 or 6.
   243  				b1 := r.readUint(p[8], 1)
   244  				b0 := r.readUint(p[9+b1], 1)
   245  				cat := 2*b1 + b0
   246  				tab := &cat3456[cat]
   247  				v = 0
   248  				for i := 0; tab[i] != 0; i++ {
   249  					v *= 2
   250  					v += r.readUint(tab[i], 1)
   251  				}
   252  				v += 3 + (8 << cat)
   253  			}
   254  			p = prob[bands[n]][2]
   255  		}
   256  		z := zigzag[n-1]
   257  		c := int32(v) * int32(quant[btou(z > 0)])
   258  		if r.readBit(uniformProb) {
   259  			c = -c
   260  		}
   261  		d.coeff[coeffBase+int(z)] = int16(c)
   262  		if n == 16 || !r.readBit(p[0]) {
   263  			return 1
   264  		}
   265  	}
   266  	return 1
   267  }
   268  
   269  // parseResiduals parses the residuals and returns whether inner loop filtering
   270  // should be skipped for this macroblock.
   271  func (d *Decoder) parseResiduals(mbx, mby int) (skip bool) {
   272  	partition := &d.op[mby&(d.nOP-1)]
   273  	plane := planeY1SansY2
   274  	quant := &d.quant[d.segment]
   275  
   276  	// Parse the DC coefficient of each 4x4 luma region.
   277  	if d.usePredY16 {
   278  		nz := d.parseResiduals4(partition, planeY2, d.leftMB.nzY16+d.upMB[mbx].nzY16, quant.y2, false, whtCoeffBase)
   279  		d.leftMB.nzY16 = nz
   280  		d.upMB[mbx].nzY16 = nz
   281  		d.inverseWHT16()
   282  		plane = planeY1WithY2
   283  	}
   284  
   285  	var (
   286  		nzDC, nzAC         [4]uint8
   287  		nzDCMask, nzACMask uint32
   288  		coeffBase          int
   289  	)
   290  
   291  	// Parse the luma coefficients.
   292  	lnz := unpack[d.leftMB.nzMask&0x0f]
   293  	unz := unpack[d.upMB[mbx].nzMask&0x0f]
   294  	for y := 0; y < 4; y++ {
   295  		nz := lnz[y]
   296  		for x := 0; x < 4; x++ {
   297  			nz = d.parseResiduals4(partition, plane, nz+unz[x], quant.y1, d.usePredY16, coeffBase)
   298  			unz[x] = nz
   299  			nzAC[x] = nz
   300  			nzDC[x] = btou(d.coeff[coeffBase] != 0)
   301  			coeffBase += 16
   302  		}
   303  		lnz[y] = nz
   304  		nzDCMask |= pack(nzDC, y*4)
   305  		nzACMask |= pack(nzAC, y*4)
   306  	}
   307  	lnzMask := pack(lnz, 0)
   308  	unzMask := pack(unz, 0)
   309  
   310  	// Parse the chroma coefficients.
   311  	lnz = unpack[d.leftMB.nzMask>>4]
   312  	unz = unpack[d.upMB[mbx].nzMask>>4]
   313  	for c := 0; c < 4; c += 2 {
   314  		for y := 0; y < 2; y++ {
   315  			nz := lnz[y+c]
   316  			for x := 0; x < 2; x++ {
   317  				nz = d.parseResiduals4(partition, planeUV, nz+unz[x+c], quant.uv, false, coeffBase)
   318  				unz[x+c] = nz
   319  				nzAC[y*2+x] = nz
   320  				nzDC[y*2+x] = btou(d.coeff[coeffBase] != 0)
   321  				coeffBase += 16
   322  			}
   323  			lnz[y+c] = nz
   324  		}
   325  		nzDCMask |= pack(nzDC, 16+c*2)
   326  		nzACMask |= pack(nzAC, 16+c*2)
   327  	}
   328  	lnzMask |= pack(lnz, 4)
   329  	unzMask |= pack(unz, 4)
   330  
   331  	// Save decoder state.
   332  	d.leftMB.nzMask = uint8(lnzMask)
   333  	d.upMB[mbx].nzMask = uint8(unzMask)
   334  	d.nzDCMask = nzDCMask
   335  	d.nzACMask = nzACMask
   336  
   337  	// Section 15.1 of the spec says that "Steps 2 and 4 [of the loop filter]
   338  	// are skipped... [if] there is no DCT coefficient coded for the whole
   339  	// macroblock."
   340  	return nzDCMask == 0 && nzACMask == 0
   341  }
   342  
   343  // reconstructMacroblock applies the predictor functions and adds the inverse-
   344  // DCT transformed residuals to recover the YCbCr data.
   345  func (d *Decoder) reconstructMacroblock(mbx, mby int) {
   346  	if d.usePredY16 {
   347  		p := checkTopLeftPred(mbx, mby, d.predY16)
   348  		predFunc16[p](d, 1, 8)
   349  		for j := 0; j < 4; j++ {
   350  			for i := 0; i < 4; i++ {
   351  				n := 4*j + i
   352  				y := 4*j + 1
   353  				x := 4*i + 8
   354  				mask := uint32(1) << uint(n)
   355  				if d.nzACMask&mask != 0 {
   356  					d.inverseDCT4(y, x, 16*n)
   357  				} else if d.nzDCMask&mask != 0 {
   358  					d.inverseDCT4DCOnly(y, x, 16*n)
   359  				}
   360  			}
   361  		}
   362  	} else {
   363  		for j := 0; j < 4; j++ {
   364  			for i := 0; i < 4; i++ {
   365  				n := 4*j + i
   366  				y := 4*j + 1
   367  				x := 4*i + 8
   368  				predFunc4[d.predY4[j][i]](d, y, x)
   369  				mask := uint32(1) << uint(n)
   370  				if d.nzACMask&mask != 0 {
   371  					d.inverseDCT4(y, x, 16*n)
   372  				} else if d.nzDCMask&mask != 0 {
   373  					d.inverseDCT4DCOnly(y, x, 16*n)
   374  				}
   375  			}
   376  		}
   377  	}
   378  	p := checkTopLeftPred(mbx, mby, d.predC8)
   379  	predFunc8[p](d, ybrBY, ybrBX)
   380  	if d.nzACMask&0x0f0000 != 0 {
   381  		d.inverseDCT8(ybrBY, ybrBX, bCoeffBase)
   382  	} else if d.nzDCMask&0x0f0000 != 0 {
   383  		d.inverseDCT8DCOnly(ybrBY, ybrBX, bCoeffBase)
   384  	}
   385  	predFunc8[p](d, ybrRY, ybrRX)
   386  	if d.nzACMask&0xf00000 != 0 {
   387  		d.inverseDCT8(ybrRY, ybrRX, rCoeffBase)
   388  	} else if d.nzDCMask&0xf00000 != 0 {
   389  		d.inverseDCT8DCOnly(ybrRY, ybrRX, rCoeffBase)
   390  	}
   391  }
   392  
   393  // reconstruct reconstructs one macroblock and returns whether inner loop
   394  // filtering should be skipped for it.
   395  func (d *Decoder) reconstruct(mbx, mby int) (skip bool) {
   396  	if d.segmentHeader.updateMap {
   397  		if !d.fp.readBit(d.segmentHeader.prob[0]) {
   398  			d.segment = int(d.fp.readUint(d.segmentHeader.prob[1], 1))
   399  		} else {
   400  			d.segment = int(d.fp.readUint(d.segmentHeader.prob[2], 1)) + 2
   401  		}
   402  	}
   403  	if d.useSkipProb {
   404  		skip = d.fp.readBit(d.skipProb)
   405  	}
   406  	// Prepare the workspace.
   407  	for i := range d.coeff {
   408  		d.coeff[i] = 0
   409  	}
   410  	d.prepareYBR(mbx, mby)
   411  	// Parse the predictor modes.
   412  	d.usePredY16 = d.fp.readBit(145)
   413  	if d.usePredY16 {
   414  		d.parsePredModeY16(mbx)
   415  	} else {
   416  		d.parsePredModeY4(mbx)
   417  	}
   418  	d.parsePredModeC8()
   419  	// Parse the residuals.
   420  	if !skip {
   421  		skip = d.parseResiduals(mbx, mby)
   422  	} else {
   423  		if d.usePredY16 {
   424  			d.leftMB.nzY16 = 0
   425  			d.upMB[mbx].nzY16 = 0
   426  		}
   427  		d.leftMB.nzMask = 0
   428  		d.upMB[mbx].nzMask = 0
   429  		d.nzDCMask = 0
   430  		d.nzACMask = 0
   431  	}
   432  	// Reconstruct the YCbCr data and copy it to the image.
   433  	d.reconstructMacroblock(mbx, mby)
   434  	for i, y := (mby*d.img.YStride+mbx)*16, 0; y < 16; i, y = i+d.img.YStride, y+1 {
   435  		copy(d.img.Y[i:i+16], d.ybr[ybrYY+y][ybrYX:ybrYX+16])
   436  	}
   437  	for i, y := (mby*d.img.CStride+mbx)*8, 0; y < 8; i, y = i+d.img.CStride, y+1 {
   438  		copy(d.img.Cb[i:i+8], d.ybr[ybrBY+y][ybrBX:ybrBX+8])
   439  		copy(d.img.Cr[i:i+8], d.ybr[ybrRY+y][ybrRX:ybrRX+8])
   440  	}
   441  	return skip
   442  }
   443
View as plain text