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