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