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