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