1 // Copyright 2011 Google Inc. All Rights Reserved. 2 // 3 // Use of this source code is governed by a BSD-style license 4 // that can be found in the COPYING file in the root of the source 5 // tree. An additional intellectual property rights grant can be found 6 // in the file PATENTS. All contributing project authors may 7 // be found in the AUTHORS file in the root of the source tree. 8 // ----------------------------------------------------------------------------- 9 // 10 // VP8Iterator: block iterator 11 // 12 // Author: Skal (pascal.massimino (at) gmail.com) 13 14 #include <string.h> 15 16 #include "./vp8enci.h" 17 18 //------------------------------------------------------------------------------ 19 // VP8Iterator 20 //------------------------------------------------------------------------------ 21 22 static void InitLeft(VP8EncIterator* const it) { 23 it->y_left_[-1] = it->u_left_[-1] = it->v_left_[-1] = 24 (it->y_ > 0) ? 129 : 127; 25 memset(it->y_left_, 129, 16); 26 memset(it->u_left_, 129, 8); 27 memset(it->v_left_, 129, 8); 28 it->left_nz_[8] = 0; 29 } 30 31 static void InitTop(VP8EncIterator* const it) { 32 const VP8Encoder* const enc = it->enc_; 33 const size_t top_size = enc->mb_w_ * 16; 34 memset(enc->y_top_, 127, 2 * top_size); 35 memset(enc->nz_, 0, enc->mb_w_ * sizeof(*enc->nz_)); 36 } 37 38 void VP8IteratorSetRow(VP8EncIterator* const it, int y) { 39 VP8Encoder* const enc = it->enc_; 40 it->x_ = 0; 41 it->y_ = y; 42 it->bw_ = &enc->parts_[y & (enc->num_parts_ - 1)]; 43 it->preds_ = enc->preds_ + y * 4 * enc->preds_w_; 44 it->nz_ = enc->nz_; 45 it->mb_ = enc->mb_info_ + y * enc->mb_w_; 46 it->y_top_ = enc->y_top_; 47 it->uv_top_ = enc->uv_top_; 48 InitLeft(it); 49 } 50 51 void VP8IteratorReset(VP8EncIterator* const it) { 52 VP8Encoder* const enc = it->enc_; 53 VP8IteratorSetRow(it, 0); 54 VP8IteratorSetCountDown(it, enc->mb_w_ * enc->mb_h_); // default 55 InitTop(it); 56 InitLeft(it); 57 memset(it->bit_count_, 0, sizeof(it->bit_count_)); 58 it->do_trellis_ = 0; 59 } 60 61 void VP8IteratorSetCountDown(VP8EncIterator* const it, int count_down) { 62 it->count_down_ = it->count_down0_ = count_down; 63 } 64 65 int VP8IteratorIsDone(const VP8EncIterator* const it) { 66 return (it->count_down_ <= 0); 67 } 68 69 void VP8IteratorInit(VP8Encoder* const enc, VP8EncIterator* const it) { 70 it->enc_ = enc; 71 it->y_stride_ = enc->pic_->y_stride; 72 it->uv_stride_ = enc->pic_->uv_stride; 73 it->yuv_in_ = (uint8_t*)WEBP_ALIGN(it->yuv_mem_); 74 it->yuv_out_ = it->yuv_in_ + YUV_SIZE_ENC; 75 it->yuv_out2_ = it->yuv_out_ + YUV_SIZE_ENC; 76 it->yuv_p_ = it->yuv_out2_ + YUV_SIZE_ENC; 77 it->lf_stats_ = enc->lf_stats_; 78 it->percent0_ = enc->percent_; 79 it->y_left_ = (uint8_t*)WEBP_ALIGN(it->yuv_left_mem_ + 1); 80 it->u_left_ = it->y_left_ + 16 + 16; 81 it->v_left_ = it->u_left_ + 16; 82 VP8IteratorReset(it); 83 } 84 85 int VP8IteratorProgress(const VP8EncIterator* const it, int delta) { 86 VP8Encoder* const enc = it->enc_; 87 if (delta && enc->pic_->progress_hook != NULL) { 88 const int done = it->count_down0_ - it->count_down_; 89 const int percent = (it->count_down0_ <= 0) 90 ? it->percent0_ 91 : it->percent0_ + delta * done / it->count_down0_; 92 return WebPReportProgress(enc->pic_, percent, &enc->percent_); 93 } 94 return 1; 95 } 96 97 //------------------------------------------------------------------------------ 98 // Import the source samples into the cache. Takes care of replicating 99 // boundary pixels if necessary. 100 101 static WEBP_INLINE int MinSize(int a, int b) { return (a < b) ? a : b; } 102 103 static void ImportBlock(const uint8_t* src, int src_stride, 104 uint8_t* dst, int w, int h, int size) { 105 int i; 106 for (i = 0; i < h; ++i) { 107 memcpy(dst, src, w); 108 if (w < size) { 109 memset(dst + w, dst[w - 1], size - w); 110 } 111 dst += BPS; 112 src += src_stride; 113 } 114 for (i = h; i < size; ++i) { 115 memcpy(dst, dst - BPS, size); 116 dst += BPS; 117 } 118 } 119 120 static void ImportLine(const uint8_t* src, int src_stride, 121 uint8_t* dst, int len, int total_len) { 122 int i; 123 for (i = 0; i < len; ++i, src += src_stride) dst[i] = *src; 124 for (; i < total_len; ++i) dst[i] = dst[len - 1]; 125 } 126 127 void VP8IteratorImport(VP8EncIterator* const it, uint8_t* tmp_32) { 128 const VP8Encoder* const enc = it->enc_; 129 const int x = it->x_, y = it->y_; 130 const WebPPicture* const pic = enc->pic_; 131 const uint8_t* const ysrc = pic->y + (y * pic->y_stride + x) * 16; 132 const uint8_t* const usrc = pic->u + (y * pic->uv_stride + x) * 8; 133 const uint8_t* const vsrc = pic->v + (y * pic->uv_stride + x) * 8; 134 const int w = MinSize(pic->width - x * 16, 16); 135 const int h = MinSize(pic->height - y * 16, 16); 136 const int uv_w = (w + 1) >> 1; 137 const int uv_h = (h + 1) >> 1; 138 139 ImportBlock(ysrc, pic->y_stride, it->yuv_in_ + Y_OFF_ENC, w, h, 16); 140 ImportBlock(usrc, pic->uv_stride, it->yuv_in_ + U_OFF_ENC, uv_w, uv_h, 8); 141 ImportBlock(vsrc, pic->uv_stride, it->yuv_in_ + V_OFF_ENC, uv_w, uv_h, 8); 142 143 if (tmp_32 == NULL) return; 144 145 // Import source (uncompressed) samples into boundary. 146 if (x == 0) { 147 InitLeft(it); 148 } else { 149 if (y == 0) { 150 it->y_left_[-1] = it->u_left_[-1] = it->v_left_[-1] = 127; 151 } else { 152 it->y_left_[-1] = ysrc[- 1 - pic->y_stride]; 153 it->u_left_[-1] = usrc[- 1 - pic->uv_stride]; 154 it->v_left_[-1] = vsrc[- 1 - pic->uv_stride]; 155 } 156 ImportLine(ysrc - 1, pic->y_stride, it->y_left_, h, 16); 157 ImportLine(usrc - 1, pic->uv_stride, it->u_left_, uv_h, 8); 158 ImportLine(vsrc - 1, pic->uv_stride, it->v_left_, uv_h, 8); 159 } 160 161 it->y_top_ = tmp_32 + 0; 162 it->uv_top_ = tmp_32 + 16; 163 if (y == 0) { 164 memset(tmp_32, 127, 32 * sizeof(*tmp_32)); 165 } else { 166 ImportLine(ysrc - pic->y_stride, 1, tmp_32, w, 16); 167 ImportLine(usrc - pic->uv_stride, 1, tmp_32 + 16, uv_w, 8); 168 ImportLine(vsrc - pic->uv_stride, 1, tmp_32 + 16 + 8, uv_w, 8); 169 } 170 } 171 172 //------------------------------------------------------------------------------ 173 // Copy back the compressed samples into user space if requested. 174 175 static void ExportBlock(const uint8_t* src, uint8_t* dst, int dst_stride, 176 int w, int h) { 177 while (h-- > 0) { 178 memcpy(dst, src, w); 179 dst += dst_stride; 180 src += BPS; 181 } 182 } 183 184 void VP8IteratorExport(const VP8EncIterator* const it) { 185 const VP8Encoder* const enc = it->enc_; 186 if (enc->config_->show_compressed) { 187 const int x = it->x_, y = it->y_; 188 const uint8_t* const ysrc = it->yuv_out_ + Y_OFF_ENC; 189 const uint8_t* const usrc = it->yuv_out_ + U_OFF_ENC; 190 const uint8_t* const vsrc = it->yuv_out_ + V_OFF_ENC; 191 const WebPPicture* const pic = enc->pic_; 192 uint8_t* const ydst = pic->y + (y * pic->y_stride + x) * 16; 193 uint8_t* const udst = pic->u + (y * pic->uv_stride + x) * 8; 194 uint8_t* const vdst = pic->v + (y * pic->uv_stride + x) * 8; 195 int w = (pic->width - x * 16); 196 int h = (pic->height - y * 16); 197 198 if (w > 16) w = 16; 199 if (h > 16) h = 16; 200 201 // Luma plane 202 ExportBlock(ysrc, ydst, pic->y_stride, w, h); 203 204 { // U/V planes 205 const int uv_w = (w + 1) >> 1; 206 const int uv_h = (h + 1) >> 1; 207 ExportBlock(usrc, udst, pic->uv_stride, uv_w, uv_h); 208 ExportBlock(vsrc, vdst, pic->uv_stride, uv_w, uv_h); 209 } 210 } 211 } 212 213 //------------------------------------------------------------------------------ 214 // Non-zero contexts setup/teardown 215 216 // Nz bits: 217 // 0 1 2 3 Y 218 // 4 5 6 7 219 // 8 9 10 11 220 // 12 13 14 15 221 // 16 17 U 222 // 18 19 223 // 20 21 V 224 // 22 23 225 // 24 DC-intra16 226 227 // Convert packed context to byte array 228 #define BIT(nz, n) (!!((nz) & (1 << (n)))) 229 230 void VP8IteratorNzToBytes(VP8EncIterator* const it) { 231 const int tnz = it->nz_[0], lnz = it->nz_[-1]; 232 int* const top_nz = it->top_nz_; 233 int* const left_nz = it->left_nz_; 234 235 // Top-Y 236 top_nz[0] = BIT(tnz, 12); 237 top_nz[1] = BIT(tnz, 13); 238 top_nz[2] = BIT(tnz, 14); 239 top_nz[3] = BIT(tnz, 15); 240 // Top-U 241 top_nz[4] = BIT(tnz, 18); 242 top_nz[5] = BIT(tnz, 19); 243 // Top-V 244 top_nz[6] = BIT(tnz, 22); 245 top_nz[7] = BIT(tnz, 23); 246 // DC 247 top_nz[8] = BIT(tnz, 24); 248 249 // left-Y 250 left_nz[0] = BIT(lnz, 3); 251 left_nz[1] = BIT(lnz, 7); 252 left_nz[2] = BIT(lnz, 11); 253 left_nz[3] = BIT(lnz, 15); 254 // left-U 255 left_nz[4] = BIT(lnz, 17); 256 left_nz[5] = BIT(lnz, 19); 257 // left-V 258 left_nz[6] = BIT(lnz, 21); 259 left_nz[7] = BIT(lnz, 23); 260 // left-DC is special, iterated separately 261 } 262 263 void VP8IteratorBytesToNz(VP8EncIterator* const it) { 264 uint32_t nz = 0; 265 const int* const top_nz = it->top_nz_; 266 const int* const left_nz = it->left_nz_; 267 // top 268 nz |= (top_nz[0] << 12) | (top_nz[1] << 13); 269 nz |= (top_nz[2] << 14) | (top_nz[3] << 15); 270 nz |= (top_nz[4] << 18) | (top_nz[5] << 19); 271 nz |= (top_nz[6] << 22) | (top_nz[7] << 23); 272 nz |= (top_nz[8] << 24); // we propagate the _top_ bit, esp. for intra4 273 // left 274 nz |= (left_nz[0] << 3) | (left_nz[1] << 7); 275 nz |= (left_nz[2] << 11); 276 nz |= (left_nz[4] << 17) | (left_nz[6] << 21); 277 278 *it->nz_ = nz; 279 } 280 281 #undef BIT 282 283 //------------------------------------------------------------------------------ 284 // Advance to the next position, doing the bookkeeping. 285 286 void VP8IteratorSaveBoundary(VP8EncIterator* const it) { 287 VP8Encoder* const enc = it->enc_; 288 const int x = it->x_, y = it->y_; 289 const uint8_t* const ysrc = it->yuv_out_ + Y_OFF_ENC; 290 const uint8_t* const uvsrc = it->yuv_out_ + U_OFF_ENC; 291 if (x < enc->mb_w_ - 1) { // left 292 int i; 293 for (i = 0; i < 16; ++i) { 294 it->y_left_[i] = ysrc[15 + i * BPS]; 295 } 296 for (i = 0; i < 8; ++i) { 297 it->u_left_[i] = uvsrc[7 + i * BPS]; 298 it->v_left_[i] = uvsrc[15 + i * BPS]; 299 } 300 // top-left (before 'top'!) 301 it->y_left_[-1] = it->y_top_[15]; 302 it->u_left_[-1] = it->uv_top_[0 + 7]; 303 it->v_left_[-1] = it->uv_top_[8 + 7]; 304 } 305 if (y < enc->mb_h_ - 1) { // top 306 memcpy(it->y_top_, ysrc + 15 * BPS, 16); 307 memcpy(it->uv_top_, uvsrc + 7 * BPS, 8 + 8); 308 } 309 } 310 311 int VP8IteratorNext(VP8EncIterator* const it) { 312 it->preds_ += 4; 313 it->mb_ += 1; 314 it->nz_ += 1; 315 it->y_top_ += 16; 316 it->uv_top_ += 16; 317 it->x_ += 1; 318 if (it->x_ == it->enc_->mb_w_) { 319 VP8IteratorSetRow(it, ++it->y_); 320 } 321 return (0 < --it->count_down_); 322 } 323 324 //------------------------------------------------------------------------------ 325 // Helper function to set mode properties 326 327 void VP8SetIntra16Mode(const VP8EncIterator* const it, int mode) { 328 uint8_t* preds = it->preds_; 329 int y; 330 for (y = 0; y < 4; ++y) { 331 memset(preds, mode, 4); 332 preds += it->enc_->preds_w_; 333 } 334 it->mb_->type_ = 1; 335 } 336 337 void VP8SetIntra4Mode(const VP8EncIterator* const it, const uint8_t* modes) { 338 uint8_t* preds = it->preds_; 339 int y; 340 for (y = 4; y > 0; --y) { 341 memcpy(preds, modes, 4 * sizeof(*modes)); 342 preds += it->enc_->preds_w_; 343 modes += 4; 344 } 345 it->mb_->type_ = 0; 346 } 347 348 void VP8SetIntraUVMode(const VP8EncIterator* const it, int mode) { 349 it->mb_->uv_mode_ = mode; 350 } 351 352 void VP8SetSkip(const VP8EncIterator* const it, int skip) { 353 it->mb_->skip_ = skip; 354 } 355 356 void VP8SetSegment(const VP8EncIterator* const it, int segment) { 357 it->mb_->segment_ = segment; 358 } 359 360 //------------------------------------------------------------------------------ 361 // Intra4x4 sub-blocks iteration 362 // 363 // We store and update the boundary samples into an array of 37 pixels. They 364 // are updated as we iterate and reconstructs each intra4x4 blocks in turn. 365 // The position of the samples has the following snake pattern: 366 // 367 // 16|17 18 19 20|21 22 23 24|25 26 27 28|29 30 31 32|33 34 35 36 <- Top-right 368 // --+-----------+-----------+-----------+-----------+ 369 // 15| 19| 23| 27| 31| 370 // 14| 18| 22| 26| 30| 371 // 13| 17| 21| 25| 29| 372 // 12|13 14 15 16|17 18 19 20|21 22 23 24|25 26 27 28| 373 // --+-----------+-----------+-----------+-----------+ 374 // 11| 15| 19| 23| 27| 375 // 10| 14| 18| 22| 26| 376 // 9| 13| 17| 21| 25| 377 // 8| 9 10 11 12|13 14 15 16|17 18 19 20|21 22 23 24| 378 // --+-----------+-----------+-----------+-----------+ 379 // 7| 11| 15| 19| 23| 380 // 6| 10| 14| 18| 22| 381 // 5| 9| 13| 17| 21| 382 // 4| 5 6 7 8| 9 10 11 12|13 14 15 16|17 18 19 20| 383 // --+-----------+-----------+-----------+-----------+ 384 // 3| 7| 11| 15| 19| 385 // 2| 6| 10| 14| 18| 386 // 1| 5| 9| 13| 17| 387 // 0| 1 2 3 4| 5 6 7 8| 9 10 11 12|13 14 15 16| 388 // --+-----------+-----------+-----------+-----------+ 389 390 // Array to record the position of the top sample to pass to the prediction 391 // functions in dsp.c. 392 static const uint8_t VP8TopLeftI4[16] = { 393 17, 21, 25, 29, 394 13, 17, 21, 25, 395 9, 13, 17, 21, 396 5, 9, 13, 17 397 }; 398 399 void VP8IteratorStartI4(VP8EncIterator* const it) { 400 const VP8Encoder* const enc = it->enc_; 401 int i; 402 403 it->i4_ = 0; // first 4x4 sub-block 404 it->i4_top_ = it->i4_boundary_ + VP8TopLeftI4[0]; 405 406 // Import the boundary samples 407 for (i = 0; i < 17; ++i) { // left 408 it->i4_boundary_[i] = it->y_left_[15 - i]; 409 } 410 for (i = 0; i < 16; ++i) { // top 411 it->i4_boundary_[17 + i] = it->y_top_[i]; 412 } 413 // top-right samples have a special case on the far right of the picture 414 if (it->x_ < enc->mb_w_ - 1) { 415 for (i = 16; i < 16 + 4; ++i) { 416 it->i4_boundary_[17 + i] = it->y_top_[i]; 417 } 418 } else { // else, replicate the last valid pixel four times 419 for (i = 16; i < 16 + 4; ++i) { 420 it->i4_boundary_[17 + i] = it->i4_boundary_[17 + 15]; 421 } 422 } 423 VP8IteratorNzToBytes(it); // import the non-zero context 424 } 425 426 int VP8IteratorRotateI4(VP8EncIterator* const it, 427 const uint8_t* const yuv_out) { 428 const uint8_t* const blk = yuv_out + VP8Scan[it->i4_]; 429 uint8_t* const top = it->i4_top_; 430 int i; 431 432 // Update the cache with 7 fresh samples 433 for (i = 0; i <= 3; ++i) { 434 top[-4 + i] = blk[i + 3 * BPS]; // store future top samples 435 } 436 if ((it->i4_ & 3) != 3) { // if not on the right sub-blocks #3, #7, #11, #15 437 for (i = 0; i <= 2; ++i) { // store future left samples 438 top[i] = blk[3 + (2 - i) * BPS]; 439 } 440 } else { // else replicate top-right samples, as says the specs. 441 for (i = 0; i <= 3; ++i) { 442 top[i] = top[i + 4]; 443 } 444 } 445 // move pointers to next sub-block 446 ++it->i4_; 447 if (it->i4_ == 16) { // we're done 448 return 0; 449 } 450 451 it->i4_top_ = it->i4_boundary_ + VP8TopLeftI4[it->i4_]; 452 return 1; 453 } 454 455 //------------------------------------------------------------------------------ 456 457