Home | History | Annotate | Download | only in enc
      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 (at) 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 
    855