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