• Home
  • Line#
  • Scopes#
  • Navigate#
  • Raw
  • Download
1 // Copyright 2011 Google Inc. All Rights Reserved.
2 //
3 // Use of this source code is governed by a BSD-style license
4 // that can be found in the COPYING file in the root of the source
5 // tree. An additional intellectual property rights grant can be found
6 // in the file PATENTS. All contributing project authors may
7 // be found in the AUTHORS file in the root of the source tree.
8 // -----------------------------------------------------------------------------
9 //
10 //   frame coding and analysis
11 //
12 // Author: Skal (pascal.massimino@gmail.com)
13 
14 #include <string.h>
15 #include <math.h>
16 
17 #include "./vp8enci.h"
18 #include "./cost.h"
19 #include "webp/format_constants.h"  // RIFF constants
20 
21 #define SEGMENT_VISU 0
22 #define DEBUG_SEARCH 0    // useful to track search convergence
23 
24 //------------------------------------------------------------------------------
25 // multi-pass convergence
26 
27 #define HEADER_SIZE_ESTIMATE (RIFF_HEADER_SIZE + CHUNK_HEADER_SIZE +  \
28                               VP8_FRAME_HEADER_SIZE)
29 #define DQ_LIMIT 0.4  // convergence is considered reached if dq < DQ_LIMIT
30 // we allow 2k of extra head-room in PARTITION0 limit.
31 #define PARTITION0_SIZE_LIMIT ((VP8_MAX_PARTITION0_SIZE - 2048ULL) << 11)
32 
33 typedef struct {  // struct for organizing convergence in either size or PSNR
34   int is_first;
35   float dq;
36   float q, last_q;
37   double value, last_value;   // PSNR or size
38   double target;
39   int do_size_search;
40 } PassStats;
41 
InitPassStats(const VP8Encoder * const enc,PassStats * const s)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 
Clamp(float v,float min,float max)58 static float Clamp(float v, float min, float max) {
59   return (v < min) ? min : (v > max) ? max : v;
60 }
61 
ComputeNextQ(PassStats * const s)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 
ResetStats(VP8Encoder * const enc)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 
CalcSkipProba(uint64_t nb,uint64_t total)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.
FinalizeSkipProba(VP8Encoder * const enc)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.
CalcTokenProba(int nb,int total)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.
BranchCost(int nb,int total,int proba)138 static int BranchCost(int nb, int total, int proba) {
139   return nb * VP8BitCost(1, proba) + (total - nb) * VP8BitCost(0, proba);
140 }
141 
ResetTokenStats(VP8Encoder * const enc)142 static void ResetTokenStats(VP8Encoder* const enc) {
143   VP8Proba* const proba = &enc->proba_;
144   memset(proba->stats_, 0, sizeof(proba->stats_));
145 }
146 
FinalizeTokenProbas(VP8Proba * const proba)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 
GetProba(int a,int b)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 
SetSegmentProbas(VP8Encoder * const enc)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 
PutCoeffs(VP8BitWriter * const bw,int ctx,const VP8Residual * res)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 
CodeResiduals(VP8BitWriter * const bw,VP8EncIterator * const it,const VP8ModeScore * const rd)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.
RecordResiduals(VP8EncIterator * const it,const VP8ModeScore * const rd)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 
RecordTokens(VP8EncIterator * const it,const VP8ModeScore * const rd,VP8TBuffer * const tokens)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
SetBlock(uint8_t * p,int value,int size)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 
ResetSSE(VP8Encoder * const enc)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 
StoreSSE(const VP8EncIterator * const it)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 
StoreSideInfo(const VP8EncIterator * const it)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 
GetPSNR(uint64_t mse,uint64_t size)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 
SetLoopParams(VP8Encoder * const enc,float q)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 
OneStatPass(VP8Encoder * const enc,VP8RDLevel rd_opt,int nb_mbs,int percent_delta,PassStats * const s)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 
StatLoop(VP8Encoder * const enc)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 
PreLoopInitialize(VP8Encoder * const enc)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 
PostLoopFinalize(VP8EncIterator * const it,int ok)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 
ResetAfterSkip(VP8EncIterator * const it)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 
VP8EncLoop(VP8Encoder * const enc)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 
VP8EncTokenLoop(VP8Encoder * const enc)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 
VP8EncTokenLoop(VP8Encoder * const enc)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