third_party/libwebp/enc/iterator.c

   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@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*)DO_ALIGN(it->yuv_mem_);
  74   it->yuv_out_  = it->yuv_in_ + YUV_SIZE;
  75   it->yuv_out2_ = it->yuv_out_ + YUV_SIZE;
  76   it->yuv_p_    = it->yuv_out2_ + YUV_SIZE;
  77   it->lf_stats_ = enc->lf_stats_;
  78   it->percent0_ = enc->percent_;
  79   it->y_left_ = (uint8_t*)DO_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, w, h, 16);
 140   ImportBlock(usrc, pic->uv_stride, it->yuv_in_ + U_OFF, uv_w, uv_h, 8);
 141   ImportBlock(vsrc, pic->uv_stride, it->yuv_in_ + V_OFF, 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;
 189     const uint8_t* const usrc = it->yuv_out_ + U_OFF;
 190     const uint8_t* const vsrc = it->yuv_out_ + V_OFF;
 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;
 290   const uint8_t* const uvsrc = it->yuv_out_ + U_OFF;
 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