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