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 5package 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 72const ( 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 78const ( 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. 88func (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. 145func 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. 153func 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. 159var 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 178var ( 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. 207func (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. 271func (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. 345func (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. 395func (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