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