third_party/libwebp/enc/frame.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 //   frame coding and analysis
  11 //
  12 // Author: Skal (pascal.massimino@gmail.com)
  13
  14 #include <string.h>
  15 #include <math.h>
  16
  17 #include "./vp8enci.h"
  18 #include "./cost.h"
  19 #include "../webp/format_constants.h"  // RIFF constants
  20
  21 #define SEGMENT_VISU 0
  22 #define DEBUG_SEARCH 0    // useful to track search convergence
  23
  24 //------------------------------------------------------------------------------
  25 // multi-pass convergence
  26
  27 #define HEADER_SIZE_ESTIMATE (RIFF_HEADER_SIZE + CHUNK_HEADER_SIZE +  \
  28                               VP8_FRAME_HEADER_SIZE)
  29 #define DQ_LIMIT 0.4  // convergence is considered reached if dq < DQ_LIMIT
  30 // we allow 2k of extra head-room in PARTITION0 limit.
  31 #define PARTITION0_SIZE_LIMIT ((VP8_MAX_PARTITION0_SIZE - 2048ULL) << 11)
  32
  33 typedef struct {  // struct for organizing convergence in either size or PSNR
  34   int is_first;
  35   float dq;
  36   float q, last_q;
  37   double value, last_value;   // PSNR or size
  38   double target;
  39   int do_size_search;
  40 } PassStats;
  41
  42 static int InitPassStats(const VP8Encoder* const enc, PassStats* const s) {
  43   const uint64_t target_size = (uint64_t)enc->config_->target_size;
  44   const int do_size_search = (target_size != 0);
  45   const float target_PSNR = enc->config_->target_PSNR;
  46
  47   s->is_first = 1;
  48   s->dq = 10.f;
  49   s->q = s->last_q = enc->config_->quality;
  50   s->target = do_size_search ? (double)target_size
  51             : (target_PSNR > 0.) ? target_PSNR
  52             : 40.;   // default, just in case
  53   s->value = s->last_value = 0.;
  54   s->do_size_search = do_size_search;
  55   return do_size_search;
  56 }
  57
  58 static float Clamp(float v, float min, float max) {
  59   return (v < min) ? min : (v > max) ? max : v;
  60 }
  61
  62 static float ComputeNextQ(PassStats* const s) {
  63   float dq;
  64   if (s->is_first) {
  65     dq = (s->value > s->target) ? -s->dq : s->dq;
  66     s->is_first = 0;
  67   } else if (s->value != s->last_value) {
  68     const double slope = (s->target - s->value) / (s->last_value - s->value);
  69     dq = (float)(slope * (s->last_q - s->q));
  70   } else {
  71     dq = 0.;  // we're done?!
  72   }
  73   // Limit variable to avoid large swings.
  74   s->dq = Clamp(dq, -30.f, 30.f);
  75   s->last_q = s->q;
  76   s->last_value = s->value;
  77   s->q = Clamp(s->q + s->dq, 0.f, 100.f);
  78   return s->q;
  79 }
  80
  81 //------------------------------------------------------------------------------
  82 // Tables for level coding
  83
  84 const uint8_t VP8EncBands[16 + 1] = {
  85   0, 1, 2, 3, 6, 4, 5, 6, 6, 6, 6, 6, 6, 6, 6, 7,
  86   0  // sentinel
  87 };
  88
  89 const uint8_t VP8Cat3[] = { 173, 148, 140 };
  90 const uint8_t VP8Cat4[] = { 176, 155, 140, 135 };
  91 const uint8_t VP8Cat5[] = { 180, 157, 141, 134, 130 };
  92 const uint8_t VP8Cat6[] =
  93     { 254, 254, 243, 230, 196, 177, 153, 140, 133, 130, 129 };
  94
  95 //------------------------------------------------------------------------------
  96 // Reset the statistics about: number of skips, token proba, level cost,...
  97
  98 static void ResetStats(VP8Encoder* const enc) {
  99   VP8Proba* const proba = &enc->proba_;
 100   VP8CalculateLevelCosts(proba);
 101   proba->nb_skip_ = 0;
 102 }
 103
 104 //------------------------------------------------------------------------------
 105 // Skip decision probability
 106
 107 #define SKIP_PROBA_THRESHOLD 250  // value below which using skip_proba is OK.
 108
 109 static int CalcSkipProba(uint64_t nb, uint64_t total) {
 110   return (int)(total ? (total - nb) * 255 / total : 255);
 111 }
 112
 113 // Returns the bit-cost for coding the skip probability.
 114 static int FinalizeSkipProba(VP8Encoder* const enc) {
 115   VP8Proba* const proba = &enc->proba_;
 116   const int nb_mbs = enc->mb_w_ * enc->mb_h_;
 117   const int nb_events = proba->nb_skip_;
 118   int size;
 119   proba->skip_proba_ = CalcSkipProba(nb_events, nb_mbs);
 120   proba->use_skip_proba_ = (proba->skip_proba_ < SKIP_PROBA_THRESHOLD);
 121   size = 256;   // 'use_skip_proba' bit
 122   if (proba->use_skip_proba_) {
 123     size +=  nb_events * VP8BitCost(1, proba->skip_proba_)
 124          + (nb_mbs - nb_events) * VP8BitCost(0, proba->skip_proba_);
 125     size += 8 * 256;   // cost of signaling the skip_proba_ itself.
 126   }
 127   return size;
 128 }
 129
 130 // Collect statistics and deduce probabilities for next coding pass.
 131 // Return the total bit-cost for coding the probability updates.
 132 static int CalcTokenProba(int nb, int total) {
 133   assert(nb <= total);
 134   return nb ? (255 - nb * 255 / total) : 255;
 135 }
 136
 137 // Cost of coding 'nb' 1's and 'total-nb' 0's using 'proba' probability.
 138 static int BranchCost(int nb, int total, int proba) {
 139   return nb * VP8BitCost(1, proba) + (total - nb) * VP8BitCost(0, proba);
 140 }
 141
 142 static void ResetTokenStats(VP8Encoder* const enc) {
 143   VP8Proba* const proba = &enc->proba_;
 144   memset(proba->stats_, 0, sizeof(proba->stats_));
 145 }
 146
 147 static int FinalizeTokenProbas(VP8Proba* const proba) {
 148   int has_changed = 0;
 149   int size = 0;
 150   int t, b, c, p;
 151   for (t = 0; t < NUM_TYPES; ++t) {
 152     for (b = 0; b < NUM_BANDS; ++b) {
 153       for (c = 0; c < NUM_CTX; ++c) {
 154         for (p = 0; p < NUM_PROBAS; ++p) {
 155           const proba_t stats = proba->stats_[t][b][c][p];
 156           const int nb = (stats >> 0) & 0xffff;
 157           const int total = (stats >> 16) & 0xffff;
 158           const int update_proba = VP8CoeffsUpdateProba[t][b][c][p];
 159           const int old_p = VP8CoeffsProba0[t][b][c][p];
 160           const int new_p = CalcTokenProba(nb, total);
 161           const int old_cost = BranchCost(nb, total, old_p)
 162                              + VP8BitCost(0, update_proba);
 163           const int new_cost = BranchCost(nb, total, new_p)
 164                              + VP8BitCost(1, update_proba)
 165                              + 8 * 256;
 166           const int use_new_p = (old_cost > new_cost);
 167           size += VP8BitCost(use_new_p, update_proba);
 168           if (use_new_p) {  // only use proba that seem meaningful enough.
 169             proba->coeffs_[t][b][c][p] = new_p;
 170             has_changed |= (new_p != old_p);
 171             size += 8 * 256;
 172           } else {
 173             proba->coeffs_[t][b][c][p] = old_p;
 174           }
 175         }
 176       }
 177     }
 178   }
 179   proba->dirty_ = has_changed;
 180   return size;
 181 }
 182
 183 //------------------------------------------------------------------------------
 184 // Finalize Segment probability based on the coding tree
 185
 186 static int GetProba(int a, int b) {
 187   const int total = a + b;
 188   return (total == 0) ? 255     // that's the default probability.
 189                       : (255 * a + total / 2) / total;  // rounded proba
 190 }
 191
 192 static void SetSegmentProbas(VP8Encoder* const enc) {
 193   int p[NUM_MB_SEGMENTS] = { 0 };
 194   int n;
 195
 196   for (n = 0; n < enc->mb_w_ * enc->mb_h_; ++n) {
 197     const VP8MBInfo* const mb = &enc->mb_info_[n];
 198     p[mb->segment_]++;
 199   }
 200   if (enc->pic_->stats != NULL) {
 201     for (n = 0; n < NUM_MB_SEGMENTS; ++n) {
 202       enc->pic_->stats->segment_size[n] = p[n];
 203     }
 204   }
 205   if (enc->segment_hdr_.num_segments_ > 1) {
 206     uint8_t* const probas = enc->proba_.segments_;
 207     probas[0] = GetProba(p[0] + p[1], p[2] + p[3]);
 208     probas[1] = GetProba(p[0], p[1]);
 209     probas[2] = GetProba(p[2], p[3]);
 210
 211     enc->segment_hdr_.update_map_ =
 212         (probas[0] != 255) || (probas[1] != 255) || (probas[2] != 255);
 213     enc->segment_hdr_.size_ =
 214         p[0] * (VP8BitCost(0, probas[0]) + VP8BitCost(0, probas[1])) +
 215         p[1] * (VP8BitCost(0, probas[0]) + VP8BitCost(1, probas[1])) +
 216         p[2] * (VP8BitCost(1, probas[0]) + VP8BitCost(0, probas[2])) +
 217         p[3] * (VP8BitCost(1, probas[0]) + VP8BitCost(1, probas[2]));
 218   } else {
 219     enc->segment_hdr_.update_map_ = 0;
 220     enc->segment_hdr_.size_ = 0;
 221   }
 222 }
 223
 224 //------------------------------------------------------------------------------
 225 // Coefficient coding
 226
 227 static int PutCoeffs(VP8BitWriter* const bw, int ctx, const VP8Residual* res) {
 228   int n = res->first;
 229   // should be prob[VP8EncBands[n]], but it's equivalent for n=0 or 1
 230   const uint8_t* p = res->prob[n][ctx];
 231   if (!VP8PutBit(bw, res->last >= 0, p[0])) {
 232     return 0;
 233   }
 234
 235   while (n < 16) {
 236     const int c = res->coeffs[n++];
 237     const int sign = c < 0;
 238     int v = sign ? -c : c;
 239     if (!VP8PutBit(bw, v != 0, p[1])) {
 240       p = res->prob[VP8EncBands[n]][0];
 241       continue;
 242     }
 243     if (!VP8PutBit(bw, v > 1, p[2])) {
 244       p = res->prob[VP8EncBands[n]][1];
 245     } else {
 246       if (!VP8PutBit(bw, v > 4, p[3])) {
 247         if (VP8PutBit(bw, v != 2, p[4]))
 248           VP8PutBit(bw, v == 4, p[5]);
 249       } else if (!VP8PutBit(bw, v > 10, p[6])) {
 250         if (!VP8PutBit(bw, v > 6, p[7])) {
 251           VP8PutBit(bw, v == 6, 159);
 252         } else {
 253           VP8PutBit(bw, v >= 9, 165);
 254           VP8PutBit(bw, !(v & 1), 145);
 255         }
 256       } else {
 257         int mask;
 258         const uint8_t* tab;
 259         if (v < 3 + (8 << 1)) {          // VP8Cat3  (3b)
 260           VP8PutBit(bw, 0, p[8]);
 261           VP8PutBit(bw, 0, p[9]);
 262           v -= 3 + (8 << 0);
 263           mask = 1 << 2;
 264           tab = VP8Cat3;
 265         } else if (v < 3 + (8 << 2)) {   // VP8Cat4  (4b)
 266           VP8PutBit(bw, 0, p[8]);
 267           VP8PutBit(bw, 1, p[9]);
 268           v -= 3 + (8 << 1);
 269           mask = 1 << 3;
 270           tab = VP8Cat4;
 271         } else if (v < 3 + (8 << 3)) {   // VP8Cat5  (5b)
 272           VP8PutBit(bw, 1, p[8]);
 273           VP8PutBit(bw, 0, p[10]);
 274           v -= 3 + (8 << 2);
 275           mask = 1 << 4;
 276           tab = VP8Cat5;
 277         } else {                         // VP8Cat6 (11b)
 278           VP8PutBit(bw, 1, p[8]);
 279           VP8PutBit(bw, 1, p[10]);
 280           v -= 3 + (8 << 3);
 281           mask = 1 << 10;
 282           tab = VP8Cat6;
 283         }
 284         while (mask) {
 285           VP8PutBit(bw, !!(v & mask), *tab++);
 286           mask >>= 1;
 287         }
 288       }
 289       p = res->prob[VP8EncBands[n]][2];
 290     }
 291     VP8PutBitUniform(bw, sign);
 292     if (n == 16 || !VP8PutBit(bw, n <= res->last, p[0])) {
 293       return 1;   // EOB
 294     }
 295   }
 296   return 1;
 297 }
 298
 299 static void CodeResiduals(VP8BitWriter* const bw, VP8EncIterator* const it,
 300                           const VP8ModeScore* const rd) {
 301   int x, y, ch;
 302   VP8Residual res;
 303   uint64_t pos1, pos2, pos3;
 304   const int i16 = (it->mb_->type_ == 1);
 305   const int segment = it->mb_->segment_;
 306   VP8Encoder* const enc = it->enc_;
 307
 308   VP8IteratorNzToBytes(it);
 309
 310   pos1 = VP8BitWriterPos(bw);
 311   if (i16) {
 312     VP8InitResidual(0, 1, enc, &res);
 313     VP8SetResidualCoeffs(rd->y_dc_levels, &res);
 314     it->top_nz_[8] = it->left_nz_[8] =
 315       PutCoeffs(bw, it->top_nz_[8] + it->left_nz_[8], &res);
 316     VP8InitResidual(1, 0, enc, &res);
 317   } else {
 318     VP8InitResidual(0, 3, enc, &res);
 319   }
 320
 321   // luma-AC
 322   for (y = 0; y < 4; ++y) {
 323     for (x = 0; x < 4; ++x) {
 324       const int ctx = it->top_nz_[x] + it->left_nz_[y];
 325       VP8SetResidualCoeffs(rd->y_ac_levels[x + y * 4], &res);
 326       it->top_nz_[x] = it->left_nz_[y] = PutCoeffs(bw, ctx, &res);
 327     }
 328   }
 329   pos2 = VP8BitWriterPos(bw);
 330
 331   // U/V
 332   VP8InitResidual(0, 2, enc, &res);
 333   for (ch = 0; ch <= 2; ch += 2) {
 334     for (y = 0; y < 2; ++y) {
 335       for (x = 0; x < 2; ++x) {
 336         const int ctx = it->top_nz_[4 + ch + x] + it->left_nz_[4 + ch + y];
 337         VP8SetResidualCoeffs(rd->uv_levels[ch * 2 + x + y * 2], &res);
 338         it->top_nz_[4 + ch + x] = it->left_nz_[4 + ch + y] =
 339             PutCoeffs(bw, ctx, &res);
 340       }
 341     }
 342   }
 343   pos3 = VP8BitWriterPos(bw);
 344   it->luma_bits_ = pos2 - pos1;
 345   it->uv_bits_ = pos3 - pos2;
 346   it->bit_count_[segment][i16] += it->luma_bits_;
 347   it->bit_count_[segment][2] += it->uv_bits_;
 348   VP8IteratorBytesToNz(it);
 349 }
 350
 351 // Same as CodeResiduals, but doesn't actually write anything.
 352 // Instead, it just records the event distribution.
 353 static void RecordResiduals(VP8EncIterator* const it,
 354                             const VP8ModeScore* const rd) {
 355   int x, y, ch;
 356   VP8Residual res;
 357   VP8Encoder* const enc = it->enc_;
 358
 359   VP8IteratorNzToBytes(it);
 360
 361   if (it->mb_->type_ == 1) {   // i16x16
 362     VP8InitResidual(0, 1, enc, &res);
 363     VP8SetResidualCoeffs(rd->y_dc_levels, &res);
 364     it->top_nz_[8] = it->left_nz_[8] =
 365       VP8RecordCoeffs(it->top_nz_[8] + it->left_nz_[8], &res);
 366     VP8InitResidual(1, 0, enc, &res);
 367   } else {
 368     VP8InitResidual(0, 3, enc, &res);
 369   }
 370
 371   // luma-AC
 372   for (y = 0; y < 4; ++y) {
 373     for (x = 0; x < 4; ++x) {
 374       const int ctx = it->top_nz_[x] + it->left_nz_[y];
 375       VP8SetResidualCoeffs(rd->y_ac_levels[x + y * 4], &res);
 376       it->top_nz_[x] = it->left_nz_[y] = VP8RecordCoeffs(ctx, &res);
 377     }
 378   }
 379
 380   // U/V
 381   VP8InitResidual(0, 2, enc, &res);
 382   for (ch = 0; ch <= 2; ch += 2) {
 383     for (y = 0; y < 2; ++y) {
 384       for (x = 0; x < 2; ++x) {
 385         const int ctx = it->top_nz_[4 + ch + x] + it->left_nz_[4 + ch + y];
 386         VP8SetResidualCoeffs(rd->uv_levels[ch * 2 + x + y * 2], &res);
 387         it->top_nz_[4 + ch + x] = it->left_nz_[4 + ch + y] =
 388             VP8RecordCoeffs(ctx, &res);
 389       }
 390     }
 391   }
 392
 393   VP8IteratorBytesToNz(it);
 394 }
 395
 396 //------------------------------------------------------------------------------
 397 // Token buffer
 398
 399 #if !defined(DISABLE_TOKEN_BUFFER)
 400
 401 static int RecordTokens(VP8EncIterator* const it, const VP8ModeScore* const rd,
 402                         VP8TBuffer* const tokens) {
 403   int x, y, ch;
 404   VP8Residual res;
 405   VP8Encoder* const enc = it->enc_;
 406
 407   VP8IteratorNzToBytes(it);
 408   if (it->mb_->type_ == 1) {   // i16x16
 409     const int ctx = it->top_nz_[8] + it->left_nz_[8];
 410     VP8InitResidual(0, 1, enc, &res);
 411     VP8SetResidualCoeffs(rd->y_dc_levels, &res);
 412     it->top_nz_[8] = it->left_nz_[8] =
 413         VP8RecordCoeffTokens(ctx, 1,
 414                              res.first, res.last, res.coeffs, tokens);
 415     VP8RecordCoeffs(ctx, &res);
 416     VP8InitResidual(1, 0, enc, &res);
 417   } else {
 418     VP8InitResidual(0, 3, enc, &res);
 419   }
 420
 421   // luma-AC
 422   for (y = 0; y < 4; ++y) {
 423     for (x = 0; x < 4; ++x) {
 424       const int ctx = it->top_nz_[x] + it->left_nz_[y];
 425       VP8SetResidualCoeffs(rd->y_ac_levels[x + y * 4], &res);
 426       it->top_nz_[x] = it->left_nz_[y] =
 427           VP8RecordCoeffTokens(ctx, res.coeff_type,
 428                                res.first, res.last, res.coeffs, tokens);
 429       VP8RecordCoeffs(ctx, &res);
 430     }
 431   }
 432
 433   // U/V
 434   VP8InitResidual(0, 2, enc, &res);
 435   for (ch = 0; ch <= 2; ch += 2) {
 436     for (y = 0; y < 2; ++y) {
 437       for (x = 0; x < 2; ++x) {
 438         const int ctx = it->top_nz_[4 + ch + x] + it->left_nz_[4 + ch + y];
 439         VP8SetResidualCoeffs(rd->uv_levels[ch * 2 + x + y * 2], &res);
 440         it->top_nz_[4 + ch + x] = it->left_nz_[4 + ch + y] =
 441             VP8RecordCoeffTokens(ctx, 2,
 442                                  res.first, res.last, res.coeffs, tokens);
 443         VP8RecordCoeffs(ctx, &res);
 444       }
 445     }
 446   }
 447   VP8IteratorBytesToNz(it);
 448   return !tokens->error_;
 449 }
 450
 451 #endif    // !DISABLE_TOKEN_BUFFER
 452
 453 //------------------------------------------------------------------------------
 454 // ExtraInfo map / Debug function
 455
 456 #if SEGMENT_VISU
 457 static void SetBlock(uint8_t* p, int value, int size) {
 458   int y;
 459   for (y = 0; y < size; ++y) {
 460     memset(p, value, size);
 461     p += BPS;
 462   }
 463 }
 464 #endif
 465
 466 static void ResetSSE(VP8Encoder* const enc) {
 467   enc->sse_[0] = 0;
 468   enc->sse_[1] = 0;
 469   enc->sse_[2] = 0;
 470   // Note: enc->sse_[3] is managed by alpha.c
 471   enc->sse_count_ = 0;
 472 }
 473
 474 static void StoreSSE(const VP8EncIterator* const it) {
 475   VP8Encoder* const enc = it->enc_;
 476   const uint8_t* const in = it->yuv_in_;
 477   const uint8_t* const out = it->yuv_out_;
 478   // Note: not totally accurate at boundary. And doesn't include in-loop filter.
 479   enc->sse_[0] += VP8SSE16x16(in + Y_OFF, out + Y_OFF);
 480   enc->sse_[1] += VP8SSE8x8(in + U_OFF, out + U_OFF);
 481   enc->sse_[2] += VP8SSE8x8(in + V_OFF, out + V_OFF);
 482   enc->sse_count_ += 16 * 16;
 483 }
 484
 485 static void StoreSideInfo(const VP8EncIterator* const it) {
 486   VP8Encoder* const enc = it->enc_;
 487   const VP8MBInfo* const mb = it->mb_;
 488   WebPPicture* const pic = enc->pic_;
 489
 490   if (pic->stats != NULL) {
 491     StoreSSE(it);
 492     enc->block_count_[0] += (mb->type_ == 0);
 493     enc->block_count_[1] += (mb->type_ == 1);
 494     enc->block_count_[2] += (mb->skip_ != 0);
 495   }
 496
 497   if (pic->extra_info != NULL) {
 498     uint8_t* const info = &pic->extra_info[it->x_ + it->y_ * enc->mb_w_];
 499     switch (pic->extra_info_type) {
 500       case 1: *info = mb->type_; break;
 501       case 2: *info = mb->segment_; break;
 502       case 3: *info = enc->dqm_[mb->segment_].quant_; break;
 503       case 4: *info = (mb->type_ == 1) ? it->preds_[0] : 0xff; break;
 504       case 5: *info = mb->uv_mode_; break;
 505       case 6: {
 506         const int b = (int)((it->luma_bits_ + it->uv_bits_ + 7) >> 3);
 507         *info = (b > 255) ? 255 : b; break;
 508       }
 509       case 7: *info = mb->alpha_; break;
 510       default: *info = 0; break;
 511     }
 512   }
 513 #if SEGMENT_VISU  // visualize segments and prediction modes
 514   SetBlock(it->yuv_out_ + Y_OFF, mb->segment_ * 64, 16);
 515   SetBlock(it->yuv_out_ + U_OFF, it->preds_[0] * 64, 8);
 516   SetBlock(it->yuv_out_ + V_OFF, mb->uv_mode_ * 64, 8);
 517 #endif
 518 }
 519
 520 static double GetPSNR(uint64_t mse, uint64_t size) {
 521   return (mse > 0 && size > 0) ? 10. * log10(255. * 255. * size / mse) : 99;
 522 }
 523
 524 //------------------------------------------------------------------------------
 525 //  StatLoop(): only collect statistics (number of skips, token usage, ...).
 526 //  This is used for deciding optimal probabilities. It also modifies the
 527 //  quantizer value if some target (size, PSNR) was specified.
 528
 529 static void SetLoopParams(VP8Encoder* const enc, float q) {
 530   // Make sure the quality parameter is inside valid bounds
 531   q = Clamp(q, 0.f, 100.f);
 532
 533   VP8SetSegmentParams(enc, q);      // setup segment quantizations and filters
 534   SetSegmentProbas(enc);            // compute segment probabilities
 535
 536   ResetStats(enc);
 537   ResetSSE(enc);
 538 }
 539
 540 static uint64_t OneStatPass(VP8Encoder* const enc, VP8RDLevel rd_opt,
 541                             int nb_mbs, int percent_delta,
 542                             PassStats* const s) {
 543   VP8EncIterator it;
 544   uint64_t size = 0;
 545   uint64_t size_p0 = 0;
 546   uint64_t distortion = 0;
 547   const uint64_t pixel_count = nb_mbs * 384;
 548
 549   VP8IteratorInit(enc, &it);
 550   SetLoopParams(enc, s->q);
 551   do {
 552     VP8ModeScore info;
 553     VP8IteratorImport(&it, NULL);
 554     if (VP8Decimate(&it, &info, rd_opt)) {
 555       // Just record the number of skips and act like skip_proba is not used.
 556       enc->proba_.nb_skip_++;
 557     }
 558     RecordResiduals(&it, &info);
 559     size += info.R + info.H;
 560     size_p0 += info.H;
 561     distortion += info.D;
 562     if (percent_delta && !VP8IteratorProgress(&it, percent_delta))
 563       return 0;
 564     VP8IteratorSaveBoundary(&it);
 565   } while (VP8IteratorNext(&it) && --nb_mbs > 0);
 566
 567   size_p0 += enc->segment_hdr_.size_;
 568   if (s->do_size_search) {
 569     size += FinalizeSkipProba(enc);
 570     size += FinalizeTokenProbas(&enc->proba_);
 571     size = ((size + size_p0 + 1024) >> 11) + HEADER_SIZE_ESTIMATE;
 572     s->value = (double)size;
 573   } else {
 574     s->value = GetPSNR(distortion, pixel_count);
 575   }
 576   return size_p0;
 577 }
 578
 579 static int StatLoop(VP8Encoder* const enc) {
 580   const int method = enc->method_;
 581   const int do_search = enc->do_search_;
 582   const int fast_probe = ((method == 0 || method == 3) && !do_search);
 583   int num_pass_left = enc->config_->pass;
 584   const int task_percent = 20;
 585   const int percent_per_pass =
 586       (task_percent + num_pass_left / 2) / num_pass_left;
 587   const int final_percent = enc->percent_ + task_percent;
 588   const VP8RDLevel rd_opt =
 589       (method >= 3 || do_search) ? RD_OPT_BASIC : RD_OPT_NONE;
 590   int nb_mbs = enc->mb_w_ * enc->mb_h_;
 591   PassStats stats;
 592
 593   InitPassStats(enc, &stats);
 594   ResetTokenStats(enc);
 595
 596   // Fast mode: quick analysis pass over few mbs. Better than nothing.
 597   if (fast_probe) {
 598     if (method == 3) {  // we need more stats for method 3 to be reliable.
 599       nb_mbs = (nb_mbs > 200) ? nb_mbs >> 1 : 100;
 600     } else {
 601       nb_mbs = (nb_mbs > 200) ? nb_mbs >> 2 : 50;
 602     }
 603   }
 604
 605   while (num_pass_left-- > 0) {
 606     const int is_last_pass = (fabs(stats.dq) <= DQ_LIMIT) ||
 607                              (num_pass_left == 0) ||
 608                              (enc->max_i4_header_bits_ == 0);
 609     const uint64_t size_p0 =
 610         OneStatPass(enc, rd_opt, nb_mbs, percent_per_pass, &stats);
 611     if (size_p0 == 0) return 0;
 612 #if (DEBUG_SEARCH > 0)
 613     printf("#%d value:%.1lf -> %.1lf   q:%.2f -> %.2f\n",
 614            num_pass_left, stats.last_value, stats.value, stats.last_q, stats.q);
 615 #endif
 616     if (enc->max_i4_header_bits_ > 0 && size_p0 > PARTITION0_SIZE_LIMIT) {
 617       ++num_pass_left;
 618       enc->max_i4_header_bits_ >>= 1;  // strengthen header bit limitation...
 619       continue;                        // ...and start over
 620     }
 621     if (is_last_pass) {
 622       break;
 623     }
 624     // If no target size: just do several pass without changing 'q'
 625     if (do_search) {
 626       ComputeNextQ(&stats);
 627       if (fabs(stats.dq) <= DQ_LIMIT) break;
 628     }
 629   }
 630   if (!do_search || !stats.do_size_search) {
 631     // Need to finalize probas now, since it wasn't done during the search.
 632     FinalizeSkipProba(enc);
 633     FinalizeTokenProbas(&enc->proba_);
 634   }
 635   VP8CalculateLevelCosts(&enc->proba_);  // finalize costs
 636   return WebPReportProgress(enc->pic_, final_percent, &enc->percent_);
 637 }
 638
 639 //------------------------------------------------------------------------------
 640 // Main loops
 641 //
 642
 643 static const int kAverageBytesPerMB[8] = { 50, 24, 16, 9, 7, 5, 3, 2 };
 644
 645 static int PreLoopInitialize(VP8Encoder* const enc) {
 646   int p;
 647   int ok = 1;
 648   const int average_bytes_per_MB = kAverageBytesPerMB[enc->base_quant_ >> 4];
 649   const int bytes_per_parts =
 650       enc->mb_w_ * enc->mb_h_ * average_bytes_per_MB / enc->num_parts_;
 651   // Initialize the bit-writers
 652   for (p = 0; ok && p < enc->num_parts_; ++p) {
 653     ok = VP8BitWriterInit(enc->parts_ + p, bytes_per_parts);
 654   }
 655   if (!ok) {
 656     VP8EncFreeBitWriters(enc);  // malloc error occurred
 657     WebPEncodingSetError(enc->pic_, VP8_ENC_ERROR_OUT_OF_MEMORY);
 658   }
 659   return ok;
 660 }
 661
 662 static int PostLoopFinalize(VP8EncIterator* const it, int ok) {
 663   VP8Encoder* const enc = it->enc_;
 664   if (ok) {      // Finalize the partitions, check for extra errors.
 665     int p;
 666     for (p = 0; p < enc->num_parts_; ++p) {
 667       VP8BitWriterFinish(enc->parts_ + p);
 668       ok &= !enc->parts_[p].error_;
 669     }
 670   }
 671
 672   if (ok) {      // All good. Finish up.
 673     if (enc->pic_->stats != NULL) {  // finalize byte counters...
 674       int i, s;
 675       for (i = 0; i <= 2; ++i) {
 676         for (s = 0; s < NUM_MB_SEGMENTS; ++s) {
 677           enc->residual_bytes_[i][s] = (int)((it->bit_count_[s][i] + 7) >> 3);
 678         }
 679       }
 680     }
 681     VP8AdjustFilterStrength(it);     // ...and store filter stats.
 682   } else {
 683     // Something bad happened -> need to do some memory cleanup.
 684     VP8EncFreeBitWriters(enc);
 685   }
 686   return ok;
 687 }
 688
 689 //------------------------------------------------------------------------------
 690 //  VP8EncLoop(): does the final bitstream coding.
 691
 692 static void ResetAfterSkip(VP8EncIterator* const it) {
 693   if (it->mb_->type_ == 1) {
 694     *it->nz_ = 0;  // reset all predictors
 695     it->left_nz_[8] = 0;
 696   } else {
 697     *it->nz_ &= (1 << 24);  // preserve the dc_nz bit
 698   }
 699 }
 700
 701 int VP8EncLoop(VP8Encoder* const enc) {
 702   VP8EncIterator it;
 703   int ok = PreLoopInitialize(enc);
 704   if (!ok) return 0;
 705
 706   StatLoop(enc);  // stats-collection loop
 707
 708   VP8IteratorInit(enc, &it);
 709   VP8InitFilter(&it);
 710   do {
 711     VP8ModeScore info;
 712     const int dont_use_skip = !enc->proba_.use_skip_proba_;
 713     const VP8RDLevel rd_opt = enc->rd_opt_level_;
 714
 715     VP8IteratorImport(&it, NULL);
 716     // Warning! order is important: first call VP8Decimate() and
 717     // *then* decide how to code the skip decision if there's one.
 718     if (!VP8Decimate(&it, &info, rd_opt) || dont_use_skip) {
 719       CodeResiduals(it.bw_, &it, &info);
 720     } else {   // reset predictors after a skip
 721       ResetAfterSkip(&it);
 722     }
 723     StoreSideInfo(&it);
 724     VP8StoreFilterStats(&it);
 725     VP8IteratorExport(&it);
 726     ok = VP8IteratorProgress(&it, 20);
 727     VP8IteratorSaveBoundary(&it);
 728   } while (ok && VP8IteratorNext(&it));
 729
 730   return PostLoopFinalize(&it, ok);
 731 }
 732
 733 //------------------------------------------------------------------------------
 734 // Single pass using Token Buffer.
 735
 736 #if !defined(DISABLE_TOKEN_BUFFER)
 737
 738 #define MIN_COUNT 96  // minimum number of macroblocks before updating stats
 739
 740 int VP8EncTokenLoop(VP8Encoder* const enc) {
 741   // Roughly refresh the proba eight times per pass
 742   int max_count = (enc->mb_w_ * enc->mb_h_) >> 3;
 743   int num_pass_left = enc->config_->pass;
 744   const int do_search = enc->do_search_;
 745   VP8EncIterator it;
 746   VP8Proba* const proba = &enc->proba_;
 747   const VP8RDLevel rd_opt = enc->rd_opt_level_;
 748   const uint64_t pixel_count = enc->mb_w_ * enc->mb_h_ * 384;
 749   PassStats stats;
 750   int ok;
 751
 752   InitPassStats(enc, &stats);
 753   ok = PreLoopInitialize(enc);
 754   if (!ok) return 0;
 755
 756   if (max_count < MIN_COUNT) max_count = MIN_COUNT;
 757
 758   assert(enc->num_parts_ == 1);
 759   assert(enc->use_tokens_);
 760   assert(proba->use_skip_proba_ == 0);
 761   assert(rd_opt >= RD_OPT_BASIC);   // otherwise, token-buffer won't be useful
 762   assert(num_pass_left > 0);
 763
 764   while (ok && num_pass_left-- > 0) {
 765     const int is_last_pass = (fabs(stats.dq) <= DQ_LIMIT) ||
 766                              (num_pass_left == 0) ||
 767                              (enc->max_i4_header_bits_ == 0);
 768     uint64_t size_p0 = 0;
 769     uint64_t distortion = 0;
 770     int cnt = max_count;
 771     VP8IteratorInit(enc, &it);
 772     SetLoopParams(enc, stats.q);
 773     if (is_last_pass) {
 774       ResetTokenStats(enc);
 775       VP8InitFilter(&it);  // don't collect stats until last pass (too costly)
 776     }
 777     VP8TBufferClear(&enc->tokens_);
 778     do {
 779       VP8ModeScore info;
 780       VP8IteratorImport(&it, NULL);
 781       if (--cnt < 0) {
 782         FinalizeTokenProbas(proba);
 783         VP8CalculateLevelCosts(proba);  // refresh cost tables for rd-opt
 784         cnt = max_count;
 785       }
 786       VP8Decimate(&it, &info, rd_opt);
 787       ok = RecordTokens(&it, &info, &enc->tokens_);
 788       if (!ok) {
 789         WebPEncodingSetError(enc->pic_, VP8_ENC_ERROR_OUT_OF_MEMORY);
 790         break;
 791       }
 792       size_p0 += info.H;
 793       distortion += info.D;
 794       if (is_last_pass) {
 795         StoreSideInfo(&it);
 796         VP8StoreFilterStats(&it);
 797         VP8IteratorExport(&it);
 798         ok = VP8IteratorProgress(&it, 20);
 799       }
 800       VP8IteratorSaveBoundary(&it);
 801     } while (ok && VP8IteratorNext(&it));
 802     if (!ok) break;
 803
 804     size_p0 += enc->segment_hdr_.size_;
 805     if (stats.do_size_search) {
 806       uint64_t size = FinalizeTokenProbas(&enc->proba_);
 807       size += VP8EstimateTokenSize(&enc->tokens_,
 808                                    (const uint8_t*)proba->coeffs_);
 809       size = (size + size_p0 + 1024) >> 11;  // -> size in bytes
 810       size += HEADER_SIZE_ESTIMATE;
 811       stats.value = (double)size;
 812     } else {  // compute and store PSNR
 813       stats.value = GetPSNR(distortion, pixel_count);
 814     }
 815
 816 #if (DEBUG_SEARCH > 0)
 817     printf("#%2d metric:%.1lf -> %.1lf   last_q=%.2lf q=%.2lf dq=%.2lf\n",
 818            num_pass_left, stats.last_value, stats.value,
 819            stats.last_q, stats.q, stats.dq);
 820 #endif
 821     if (size_p0 > PARTITION0_SIZE_LIMIT) {
 822       ++num_pass_left;
 823       enc->max_i4_header_bits_ >>= 1;  // strengthen header bit limitation...
 824       continue;                        // ...and start over
 825     }
 826     if (is_last_pass) {
 827       break;   // done
 828     }
 829     if (do_search) {
 830       ComputeNextQ(&stats);  // Adjust q
 831     }
 832   }
 833   if (ok) {
 834     if (!stats.do_size_search) {
 835       FinalizeTokenProbas(&enc->proba_);
 836     }
 837     ok = VP8EmitTokens(&enc->tokens_, enc->parts_ + 0,
 838                        (const uint8_t*)proba->coeffs_, 1);
 839   }
 840   ok = ok && WebPReportProgress(enc->pic_, enc->percent_ + 20, &enc->percent_);
 841   return PostLoopFinalize(&it, ok);
 842 }
 843
 844 #else
 845
 846 int VP8EncTokenLoop(VP8Encoder* const enc) {
 847   (void)enc;
 848   return 0;   // we shouldn't be here.
 849 }
 850
 851 #endif    // DISABLE_TOKEN_BUFFER
 852
 853 //------------------------------------------------------------------------------
 854