frame.c revision 228b1b1f024974d7832b51a3f266e5edc9110c02
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) 21extern "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. 29typedef 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 43const 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 48static const uint8_t kCat3[] = { 173, 148, 140 }; 49static const uint8_t kCat4[] = { 176, 155, 140, 135 }; 50static const uint8_t kCat5[] = { 180, 157, 141, 134, 130 }; 51static const uint8_t kCat6[] = 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 57static 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 68static 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. 73static 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 92static 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 98static 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. 114static int RecordCoeffs(int ctx, const VP8Residual* const res) { 115 int n = res->first; 116 proba_t* s = res->stats[VP8EncBands[n]][ctx]; 117 if (res->last < 0) { 118 Record(0, s + 0); 119 return 0; 120 } 121 while (n <= res->last) { 122 int v; 123 Record(1, s + 0); 124 while ((v = res->coeffs[n++]) == 0) { 125 Record(0, s + 1); 126 s = res->stats[VP8EncBands[n]][0]; 127 } 128 Record(1, s + 1); 129 if (!Record(2u < (unsigned int)(v + 1), s + 2)) { // v = -1 or 1 130 s = res->stats[VP8EncBands[n]][1]; 131 } else { 132 v = abs(v); 133#if !defined(USE_LEVEL_CODE_TABLE) 134 if (!Record(v > 4, s + 3)) { 135 if (Record(v != 2, s + 4)) 136 Record(v == 4, s + 5); 137 } else if (!Record(v > 10, s + 6)) { 138 Record(v > 6, s + 7); 139 } else if (!Record((v >= 3 + (8 << 2)), s + 8)) { 140 Record((v >= 3 + (8 << 1)), s + 9); 141 } else { 142 Record((v >= 3 + (8 << 3)), s + 10); 143 } 144#else 145 if (v > MAX_VARIABLE_LEVEL) 146 v = MAX_VARIABLE_LEVEL; 147 148 { 149 const int bits = VP8LevelCodes[v - 1][1]; 150 int pattern = VP8LevelCodes[v - 1][0]; 151 int i; 152 for (i = 0; (pattern >>= 1) != 0; ++i) { 153 const int mask = 2 << i; 154 if (pattern & 1) Record(!!(bits & mask), s + 3 + i); 155 } 156 } 157#endif 158 s = res->stats[VP8EncBands[n]][2]; 159 } 160 } 161 if (n < 16) Record(0, s + 0); 162 return 1; 163} 164 165// Collect statistics and deduce probabilities for next coding pass. 166// Return the total bit-cost for coding the probability updates. 167static int CalcTokenProba(int nb, int total) { 168 assert(nb <= total); 169 return nb ? (255 - nb * 255 / total) : 255; 170} 171 172// Cost of coding 'nb' 1's and 'total-nb' 0's using 'proba' probability. 173static int BranchCost(int nb, int total, int proba) { 174 return nb * VP8BitCost(1, proba) + (total - nb) * VP8BitCost(0, proba); 175} 176 177static int FinalizeTokenProbas(VP8Encoder* const enc) { 178 VP8Proba* const proba = &enc->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// helper functions for residuals struct VP8Residual. 216 217static void InitResidual(int first, int coeff_type, 218 VP8Encoder* const enc, VP8Residual* const res) { 219 res->coeff_type = coeff_type; 220 res->prob = enc->proba_.coeffs_[coeff_type]; 221 res->stats = enc->proba_.stats_[coeff_type]; 222 res->cost = enc->proba_.level_cost_[coeff_type]; 223 res->first = first; 224} 225 226static void SetResidualCoeffs(const int16_t* const coeffs, 227 VP8Residual* const res) { 228 int n; 229 res->last = -1; 230 for (n = 15; n >= res->first; --n) { 231 if (coeffs[n]) { 232 res->last = n; 233 break; 234 } 235 } 236 res->coeffs = coeffs; 237} 238 239//------------------------------------------------------------------------------ 240// Mode costs 241 242static int GetResidualCost(int ctx, const VP8Residual* const res) { 243 int n = res->first; 244 int p0 = res->prob[VP8EncBands[n]][ctx][0]; 245 const uint16_t* t = res->cost[VP8EncBands[n]][ctx]; 246 int cost; 247 248 if (res->last < 0) { 249 return VP8BitCost(0, p0); 250 } 251 cost = 0; 252 while (n <= res->last) { 253 const int v = res->coeffs[n]; 254 const int b = VP8EncBands[n + 1]; 255 ++n; 256 if (v == 0) { 257 // short-case for VP8LevelCost(t, 0) (note: VP8LevelFixedCosts[0] == 0): 258 cost += t[0]; 259 t = res->cost[b][0]; 260 continue; 261 } 262 cost += VP8BitCost(1, p0); 263 if (2u >= (unsigned int)(v + 1)) { // v = -1 or 1 264 // short-case for "VP8LevelCost(t, 1)" (256 is VP8LevelFixedCosts[1]): 265 cost += 256 + t[1]; 266 p0 = res->prob[b][1][0]; 267 t = res->cost[b][1]; 268 } else { 269 cost += VP8LevelCost(t, abs(v)); 270 p0 = res->prob[b][2][0]; 271 t = res->cost[b][2]; 272 } 273 } 274 if (n < 16) cost += VP8BitCost(0, p0); 275 return cost; 276} 277 278int VP8GetCostLuma4(VP8EncIterator* const it, const int16_t levels[16]) { 279 const int x = (it->i4_ & 3), y = (it->i4_ >> 2); 280 VP8Residual res; 281 VP8Encoder* const enc = it->enc_; 282 int R = 0; 283 int ctx; 284 285 InitResidual(0, 3, enc, &res); 286 ctx = it->top_nz_[x] + it->left_nz_[y]; 287 SetResidualCoeffs(levels, &res); 288 R += GetResidualCost(ctx, &res); 289 return R; 290} 291 292int VP8GetCostLuma16(VP8EncIterator* const it, const VP8ModeScore* const rd) { 293 VP8Residual res; 294 VP8Encoder* const enc = it->enc_; 295 int x, y; 296 int R = 0; 297 298 VP8IteratorNzToBytes(it); // re-import the non-zero context 299 300 // DC 301 InitResidual(0, 1, enc, &res); 302 SetResidualCoeffs(rd->y_dc_levels, &res); 303 R += GetResidualCost(it->top_nz_[8] + it->left_nz_[8], &res); 304 305 // AC 306 InitResidual(1, 0, enc, &res); 307 for (y = 0; y < 4; ++y) { 308 for (x = 0; x < 4; ++x) { 309 const int ctx = it->top_nz_[x] + it->left_nz_[y]; 310 SetResidualCoeffs(rd->y_ac_levels[x + y * 4], &res); 311 R += GetResidualCost(ctx, &res); 312 it->top_nz_[x] = it->left_nz_[y] = (res.last >= 0); 313 } 314 } 315 return R; 316} 317 318int VP8GetCostUV(VP8EncIterator* const it, const VP8ModeScore* const rd) { 319 VP8Residual res; 320 VP8Encoder* const enc = it->enc_; 321 int ch, x, y; 322 int R = 0; 323 324 VP8IteratorNzToBytes(it); // re-import the non-zero context 325 326 InitResidual(0, 2, enc, &res); 327 for (ch = 0; ch <= 2; ch += 2) { 328 for (y = 0; y < 2; ++y) { 329 for (x = 0; x < 2; ++x) { 330 const int ctx = it->top_nz_[4 + ch + x] + it->left_nz_[4 + ch + y]; 331 SetResidualCoeffs(rd->uv_levels[ch * 2 + x + y * 2], &res); 332 R += GetResidualCost(ctx, &res); 333 it->top_nz_[4 + ch + x] = it->left_nz_[4 + ch + y] = (res.last >= 0); 334 } 335 } 336 } 337 return R; 338} 339 340//------------------------------------------------------------------------------ 341// Coefficient coding 342 343static int PutCoeffs(VP8BitWriter* const bw, int ctx, const VP8Residual* res) { 344 int n = res->first; 345 const uint8_t* p = res->prob[VP8EncBands[n]][ctx]; 346 if (!VP8PutBit(bw, res->last >= 0, p[0])) { 347 return 0; 348 } 349 350 while (n < 16) { 351 const int c = res->coeffs[n++]; 352 const int sign = c < 0; 353 int v = sign ? -c : c; 354 if (!VP8PutBit(bw, v != 0, p[1])) { 355 p = res->prob[VP8EncBands[n]][0]; 356 continue; 357 } 358 if (!VP8PutBit(bw, v > 1, p[2])) { 359 p = res->prob[VP8EncBands[n]][1]; 360 } else { 361 if (!VP8PutBit(bw, v > 4, p[3])) { 362 if (VP8PutBit(bw, v != 2, p[4])) 363 VP8PutBit(bw, v == 4, p[5]); 364 } else if (!VP8PutBit(bw, v > 10, p[6])) { 365 if (!VP8PutBit(bw, v > 6, p[7])) { 366 VP8PutBit(bw, v == 6, 159); 367 } else { 368 VP8PutBit(bw, v >= 9, 165); 369 VP8PutBit(bw, !(v & 1), 145); 370 } 371 } else { 372 int mask; 373 const uint8_t* tab; 374 if (v < 3 + (8 << 1)) { // kCat3 (3b) 375 VP8PutBit(bw, 0, p[8]); 376 VP8PutBit(bw, 0, p[9]); 377 v -= 3 + (8 << 0); 378 mask = 1 << 2; 379 tab = kCat3; 380 } else if (v < 3 + (8 << 2)) { // kCat4 (4b) 381 VP8PutBit(bw, 0, p[8]); 382 VP8PutBit(bw, 1, p[9]); 383 v -= 3 + (8 << 1); 384 mask = 1 << 3; 385 tab = kCat4; 386 } else if (v < 3 + (8 << 3)) { // kCat5 (5b) 387 VP8PutBit(bw, 1, p[8]); 388 VP8PutBit(bw, 0, p[10]); 389 v -= 3 + (8 << 2); 390 mask = 1 << 4; 391 tab = kCat5; 392 } else { // kCat6 (11b) 393 VP8PutBit(bw, 1, p[8]); 394 VP8PutBit(bw, 1, p[10]); 395 v -= 3 + (8 << 3); 396 mask = 1 << 10; 397 tab = kCat6; 398 } 399 while (mask) { 400 VP8PutBit(bw, !!(v & mask), *tab++); 401 mask >>= 1; 402 } 403 } 404 p = res->prob[VP8EncBands[n]][2]; 405 } 406 VP8PutBitUniform(bw, sign); 407 if (n == 16 || !VP8PutBit(bw, n <= res->last, p[0])) { 408 return 1; // EOB 409 } 410 } 411 return 1; 412} 413 414static void CodeResiduals(VP8BitWriter* const bw, 415 VP8EncIterator* const it, 416 const VP8ModeScore* const rd) { 417 int x, y, ch; 418 VP8Residual res; 419 uint64_t pos1, pos2, pos3; 420 const int i16 = (it->mb_->type_ == 1); 421 const int segment = it->mb_->segment_; 422 VP8Encoder* const enc = it->enc_; 423 424 VP8IteratorNzToBytes(it); 425 426 pos1 = VP8BitWriterPos(bw); 427 if (i16) { 428 InitResidual(0, 1, enc, &res); 429 SetResidualCoeffs(rd->y_dc_levels, &res); 430 it->top_nz_[8] = it->left_nz_[8] = 431 PutCoeffs(bw, it->top_nz_[8] + it->left_nz_[8], &res); 432 InitResidual(1, 0, enc, &res); 433 } else { 434 InitResidual(0, 3, enc, &res); 435 } 436 437 // luma-AC 438 for (y = 0; y < 4; ++y) { 439 for (x = 0; x < 4; ++x) { 440 const int ctx = it->top_nz_[x] + it->left_nz_[y]; 441 SetResidualCoeffs(rd->y_ac_levels[x + y * 4], &res); 442 it->top_nz_[x] = it->left_nz_[y] = PutCoeffs(bw, ctx, &res); 443 } 444 } 445 pos2 = VP8BitWriterPos(bw); 446 447 // U/V 448 InitResidual(0, 2, enc, &res); 449 for (ch = 0; ch <= 2; ch += 2) { 450 for (y = 0; y < 2; ++y) { 451 for (x = 0; x < 2; ++x) { 452 const int ctx = it->top_nz_[4 + ch + x] + it->left_nz_[4 + ch + y]; 453 SetResidualCoeffs(rd->uv_levels[ch * 2 + x + y * 2], &res); 454 it->top_nz_[4 + ch + x] = it->left_nz_[4 + ch + y] = 455 PutCoeffs(bw, ctx, &res); 456 } 457 } 458 } 459 pos3 = VP8BitWriterPos(bw); 460 it->luma_bits_ = pos2 - pos1; 461 it->uv_bits_ = pos3 - pos2; 462 it->bit_count_[segment][i16] += it->luma_bits_; 463 it->bit_count_[segment][2] += it->uv_bits_; 464 VP8IteratorBytesToNz(it); 465} 466 467// Same as CodeResiduals, but doesn't actually write anything. 468// Instead, it just records the event distribution. 469static void RecordResiduals(VP8EncIterator* const it, 470 const VP8ModeScore* const rd) { 471 int x, y, ch; 472 VP8Residual res; 473 VP8Encoder* const enc = it->enc_; 474 475 VP8IteratorNzToBytes(it); 476 477 if (it->mb_->type_ == 1) { // i16x16 478 InitResidual(0, 1, enc, &res); 479 SetResidualCoeffs(rd->y_dc_levels, &res); 480 it->top_nz_[8] = it->left_nz_[8] = 481 RecordCoeffs(it->top_nz_[8] + it->left_nz_[8], &res); 482 InitResidual(1, 0, enc, &res); 483 } else { 484 InitResidual(0, 3, enc, &res); 485 } 486 487 // luma-AC 488 for (y = 0; y < 4; ++y) { 489 for (x = 0; x < 4; ++x) { 490 const int ctx = it->top_nz_[x] + it->left_nz_[y]; 491 SetResidualCoeffs(rd->y_ac_levels[x + y * 4], &res); 492 it->top_nz_[x] = it->left_nz_[y] = RecordCoeffs(ctx, &res); 493 } 494 } 495 496 // U/V 497 InitResidual(0, 2, enc, &res); 498 for (ch = 0; ch <= 2; ch += 2) { 499 for (y = 0; y < 2; ++y) { 500 for (x = 0; x < 2; ++x) { 501 const int ctx = it->top_nz_[4 + ch + x] + it->left_nz_[4 + ch + y]; 502 SetResidualCoeffs(rd->uv_levels[ch * 2 + x + y * 2], &res); 503 it->top_nz_[4 + ch + x] = it->left_nz_[4 + ch + y] = 504 RecordCoeffs(ctx, &res); 505 } 506 } 507 } 508 509 VP8IteratorBytesToNz(it); 510} 511 512//------------------------------------------------------------------------------ 513// Token buffer 514 515#ifdef USE_TOKEN_BUFFER 516 517void VP8TBufferInit(VP8TBuffer* const b) { 518 b->rows_ = NULL; 519 b->tokens_ = NULL; 520 b->last_ = &b->rows_; 521 b->left_ = 0; 522 b->error_ = 0; 523} 524 525int VP8TBufferNewPage(VP8TBuffer* const b) { 526 VP8Tokens* const page = b->error_ ? NULL : (VP8Tokens*)malloc(sizeof(*page)); 527 if (page == NULL) { 528 b->error_ = 1; 529 return 0; 530 } 531 *b->last_ = page; 532 b->last_ = &page->next_; 533 b->left_ = MAX_NUM_TOKEN; 534 b->tokens_ = page->tokens_; 535 return 1; 536} 537 538void VP8TBufferClear(VP8TBuffer* const b) { 539 if (b != NULL) { 540 const VP8Tokens* p = b->rows_; 541 while (p != NULL) { 542 const VP8Tokens* const next = p->next_; 543 free((void*)p); 544 p = next; 545 } 546 VP8TBufferInit(b); 547 } 548} 549 550int VP8EmitTokens(const VP8TBuffer* const b, VP8BitWriter* const bw, 551 const uint8_t* const probas) { 552 VP8Tokens* p = b->rows_; 553 if (b->error_) return 0; 554 while (p != NULL) { 555 const int N = (p->next_ == NULL) ? b->left_ : 0; 556 int n = MAX_NUM_TOKEN; 557 while (n-- > N) { 558 VP8PutBit(bw, (p->tokens_[n] >> 15) & 1, probas[p->tokens_[n] & 0x7fff]); 559 } 560 p = p->next_; 561 } 562 return 1; 563} 564 565#define TOKEN_ID(b, ctx, p) ((p) + NUM_PROBAS * ((ctx) + (b) * NUM_CTX)) 566 567static int RecordCoeffTokens(int ctx, const VP8Residual* const res, 568 VP8TBuffer* tokens) { 569 int n = res->first; 570 int b = VP8EncBands[n]; 571 if (!VP8AddToken(tokens, res->last >= 0, TOKEN_ID(b, ctx, 0))) { 572 return 0; 573 } 574 575 while (n < 16) { 576 const int c = res->coeffs[n++]; 577 const int sign = c < 0; 578 int v = sign ? -c : c; 579 const int base_id = TOKEN_ID(b, ctx, 0); 580 if (!VP8AddToken(tokens, v != 0, base_id + 1)) { 581 b = VP8EncBands[n]; 582 ctx = 0; 583 continue; 584 } 585 if (!VP8AddToken(tokens, v > 1, base_id + 2)) { 586 b = VP8EncBands[n]; 587 ctx = 1; 588 } else { 589 if (!VP8AddToken(tokens, v > 4, base_id + 3)) { 590 if (VP8AddToken(tokens, v != 2, base_id + 4)) 591 VP8AddToken(tokens, v == 4, base_id + 5); 592 } else if (!VP8AddToken(tokens, v > 10, base_id + 6)) { 593 if (!VP8AddToken(tokens, v > 6, base_id + 7)) { 594// VP8AddToken(tokens, v == 6, 159); 595 } else { 596// VP8AddToken(tokens, v >= 9, 165); 597// VP8AddToken(tokens, !(v & 1), 145); 598 } 599 } else { 600 int mask; 601 const uint8_t* tab; 602 if (v < 3 + (8 << 1)) { // kCat3 (3b) 603 VP8AddToken(tokens, 0, base_id + 8); 604 VP8AddToken(tokens, 0, base_id + 9); 605 v -= 3 + (8 << 0); 606 mask = 1 << 2; 607 tab = kCat3; 608 } else if (v < 3 + (8 << 2)) { // kCat4 (4b) 609 VP8AddToken(tokens, 0, base_id + 8); 610 VP8AddToken(tokens, 1, base_id + 9); 611 v -= 3 + (8 << 1); 612 mask = 1 << 3; 613 tab = kCat4; 614 } else if (v < 3 + (8 << 3)) { // kCat5 (5b) 615 VP8AddToken(tokens, 1, base_id + 8); 616 VP8AddToken(tokens, 0, base_id + 10); 617 v -= 3 + (8 << 2); 618 mask = 1 << 4; 619 tab = kCat5; 620 } else { // kCat6 (11b) 621 VP8AddToken(tokens, 1, base_id + 8); 622 VP8AddToken(tokens, 1, base_id + 10); 623 v -= 3 + (8 << 3); 624 mask = 1 << 10; 625 tab = kCat6; 626 } 627 while (mask) { 628 // VP8AddToken(tokens, !!(v & mask), *tab++); 629 mask >>= 1; 630 } 631 } 632 ctx = 2; 633 } 634 b = VP8EncBands[n]; 635 // VP8PutBitUniform(bw, sign); 636 if (n == 16 || !VP8AddToken(tokens, n <= res->last, TOKEN_ID(b, ctx, 0))) { 637 return 1; // EOB 638 } 639 } 640 return 1; 641} 642 643static void RecordTokens(VP8EncIterator* const it, 644 const VP8ModeScore* const rd, VP8TBuffer tokens[2]) { 645 int x, y, ch; 646 VP8Residual res; 647 VP8Encoder* const enc = it->enc_; 648 649 VP8IteratorNzToBytes(it); 650 if (it->mb_->type_ == 1) { // i16x16 651 InitResidual(0, 1, enc, &res); 652 SetResidualCoeffs(rd->y_dc_levels, &res); 653// TODO(skal): FIX -> it->top_nz_[8] = it->left_nz_[8] = 654 RecordCoeffTokens(it->top_nz_[8] + it->left_nz_[8], &res, &tokens[0]); 655 InitResidual(1, 0, enc, &res); 656 } else { 657 InitResidual(0, 3, enc, &res); 658 } 659 660 // luma-AC 661 for (y = 0; y < 4; ++y) { 662 for (x = 0; x < 4; ++x) { 663 const int ctx = it->top_nz_[x] + it->left_nz_[y]; 664 SetResidualCoeffs(rd->y_ac_levels[x + y * 4], &res); 665 it->top_nz_[x] = it->left_nz_[y] = 666 RecordCoeffTokens(ctx, &res, &tokens[0]); 667 } 668 } 669 670 // U/V 671 InitResidual(0, 2, enc, &res); 672 for (ch = 0; ch <= 2; ch += 2) { 673 for (y = 0; y < 2; ++y) { 674 for (x = 0; x < 2; ++x) { 675 const int ctx = it->top_nz_[4 + ch + x] + it->left_nz_[4 + ch + y]; 676 SetResidualCoeffs(rd->uv_levels[ch * 2 + x + y * 2], &res); 677 it->top_nz_[4 + ch + x] = it->left_nz_[4 + ch + y] = 678 RecordCoeffTokens(ctx, &res, &tokens[1]); 679 } 680 } 681 } 682} 683 684#endif // USE_TOKEN_BUFFER 685 686//------------------------------------------------------------------------------ 687// ExtraInfo map / Debug function 688 689#if SEGMENT_VISU 690static void SetBlock(uint8_t* p, int value, int size) { 691 int y; 692 for (y = 0; y < size; ++y) { 693 memset(p, value, size); 694 p += BPS; 695 } 696} 697#endif 698 699static void ResetSSE(VP8Encoder* const enc) { 700 memset(enc->sse_, 0, sizeof(enc->sse_)); 701 enc->sse_count_ = 0; 702} 703 704static void StoreSSE(const VP8EncIterator* const it) { 705 VP8Encoder* const enc = it->enc_; 706 const uint8_t* const in = it->yuv_in_; 707 const uint8_t* const out = it->yuv_out_; 708 // Note: not totally accurate at boundary. And doesn't include in-loop filter. 709 enc->sse_[0] += VP8SSE16x16(in + Y_OFF, out + Y_OFF); 710 enc->sse_[1] += VP8SSE8x8(in + U_OFF, out + U_OFF); 711 enc->sse_[2] += VP8SSE8x8(in + V_OFF, out + V_OFF); 712 enc->sse_count_ += 16 * 16; 713} 714 715static void StoreSideInfo(const VP8EncIterator* const it) { 716 VP8Encoder* const enc = it->enc_; 717 const VP8MBInfo* const mb = it->mb_; 718 WebPPicture* const pic = enc->pic_; 719 720 if (pic->stats != NULL) { 721 StoreSSE(it); 722 enc->block_count_[0] += (mb->type_ == 0); 723 enc->block_count_[1] += (mb->type_ == 1); 724 enc->block_count_[2] += (mb->skip_ != 0); 725 } 726 727 if (pic->extra_info != NULL) { 728 uint8_t* const info = &pic->extra_info[it->x_ + it->y_ * enc->mb_w_]; 729 switch (pic->extra_info_type) { 730 case 1: *info = mb->type_; break; 731 case 2: *info = mb->segment_; break; 732 case 3: *info = enc->dqm_[mb->segment_].quant_; break; 733 case 4: *info = (mb->type_ == 1) ? it->preds_[0] : 0xff; break; 734 case 5: *info = mb->uv_mode_; break; 735 case 6: { 736 const int b = (int)((it->luma_bits_ + it->uv_bits_ + 7) >> 3); 737 *info = (b > 255) ? 255 : b; break; 738 } 739 default: *info = 0; break; 740 }; 741 } 742#if SEGMENT_VISU // visualize segments and prediction modes 743 SetBlock(it->yuv_out_ + Y_OFF, mb->segment_ * 64, 16); 744 SetBlock(it->yuv_out_ + U_OFF, it->preds_[0] * 64, 8); 745 SetBlock(it->yuv_out_ + V_OFF, mb->uv_mode_ * 64, 8); 746#endif 747} 748 749//------------------------------------------------------------------------------ 750// Main loops 751// 752// VP8EncLoop(): does the final bitstream coding. 753 754static void ResetAfterSkip(VP8EncIterator* const it) { 755 if (it->mb_->type_ == 1) { 756 *it->nz_ = 0; // reset all predictors 757 it->left_nz_[8] = 0; 758 } else { 759 *it->nz_ &= (1 << 24); // preserve the dc_nz bit 760 } 761} 762 763int VP8EncLoop(VP8Encoder* const enc) { 764 int i, s, p; 765 int ok = 1; 766 VP8EncIterator it; 767 VP8ModeScore info; 768 const int dont_use_skip = !enc->proba_.use_skip_proba_; 769 const int rd_opt = enc->rd_opt_level_; 770 const int kAverageBytesPerMB = 5; // TODO: have a kTable[quality/10] 771 const int bytes_per_parts = 772 enc->mb_w_ * enc->mb_h_ * kAverageBytesPerMB / enc->num_parts_; 773 774 // Initialize the bit-writers 775 for (p = 0; p < enc->num_parts_; ++p) { 776 VP8BitWriterInit(enc->parts_ + p, bytes_per_parts); 777 } 778 779 ResetStats(enc); 780 ResetSSE(enc); 781 782 VP8IteratorInit(enc, &it); 783 VP8InitFilter(&it); 784 do { 785 VP8IteratorImport(&it); 786 // Warning! order is important: first call VP8Decimate() and 787 // *then* decide how to code the skip decision if there's one. 788 if (!VP8Decimate(&it, &info, rd_opt) || dont_use_skip) { 789 CodeResiduals(it.bw_, &it, &info); 790 } else { // reset predictors after a skip 791 ResetAfterSkip(&it); 792 } 793#ifdef WEBP_EXPERIMENTAL_FEATURES 794 if (enc->use_layer_) { 795 VP8EncCodeLayerBlock(&it); 796 } 797#endif 798 StoreSideInfo(&it); 799 VP8StoreFilterStats(&it); 800 VP8IteratorExport(&it); 801 ok = VP8IteratorProgress(&it, 20); 802 } while (ok && VP8IteratorNext(&it, it.yuv_out_)); 803 804 if (ok) { // Finalize the partitions, check for extra errors. 805 for (p = 0; p < enc->num_parts_; ++p) { 806 VP8BitWriterFinish(enc->parts_ + p); 807 ok &= !enc->parts_[p].error_; 808 } 809 } 810 811 if (ok) { // All good. Finish up. 812 if (enc->pic_->stats) { // finalize byte counters... 813 for (i = 0; i <= 2; ++i) { 814 for (s = 0; s < NUM_MB_SEGMENTS; ++s) { 815 enc->residual_bytes_[i][s] = (int)((it.bit_count_[s][i] + 7) >> 3); 816 } 817 } 818 } 819 VP8AdjustFilterStrength(&it); // ...and store filter stats. 820 } else { 821 // Something bad happened -> need to do some memory cleanup. 822 VP8EncFreeBitWriters(enc); 823 } 824 825 return ok; 826} 827 828//------------------------------------------------------------------------------ 829// VP8StatLoop(): only collect statistics (number of skips, token usage, ...) 830// This is used for deciding optimal probabilities. It also 831// modifies the quantizer value if some target (size, PNSR) 832// was specified. 833 834#define kHeaderSizeEstimate (15 + 20 + 10) // TODO: fix better 835 836static int OneStatPass(VP8Encoder* const enc, float q, int rd_opt, int nb_mbs, 837 float* const PSNR, int percent_delta) { 838 VP8EncIterator it; 839 uint64_t size = 0; 840 uint64_t distortion = 0; 841 const uint64_t pixel_count = nb_mbs * 384; 842 843 // Make sure the quality parameter is inside valid bounds 844 if (q < 0.) { 845 q = 0; 846 } else if (q > 100.) { 847 q = 100; 848 } 849 850 VP8SetSegmentParams(enc, q); // setup segment quantizations and filters 851 852 ResetStats(enc); 853 ResetTokenStats(enc); 854 855 VP8IteratorInit(enc, &it); 856 do { 857 VP8ModeScore info; 858 VP8IteratorImport(&it); 859 if (VP8Decimate(&it, &info, rd_opt)) { 860 // Just record the number of skips and act like skip_proba is not used. 861 enc->proba_.nb_skip_++; 862 } 863 RecordResiduals(&it, &info); 864 size += info.R; 865 distortion += info.D; 866 if (percent_delta && !VP8IteratorProgress(&it, percent_delta)) 867 return 0; 868 } while (VP8IteratorNext(&it, it.yuv_out_) && --nb_mbs > 0); 869 size += FinalizeSkipProba(enc); 870 size += FinalizeTokenProbas(enc); 871 size += enc->segment_hdr_.size_; 872 size = ((size + 1024) >> 11) + kHeaderSizeEstimate; 873 874 if (PSNR) { 875 *PSNR = (float)(10.* log10(255. * 255. * pixel_count / distortion)); 876 } 877 return (int)size; 878} 879 880// successive refinement increments. 881static const int dqs[] = { 20, 15, 10, 8, 6, 4, 2, 1, 0 }; 882 883int VP8StatLoop(VP8Encoder* const enc) { 884 const int do_search = 885 (enc->config_->target_size > 0 || enc->config_->target_PSNR > 0); 886 const int fast_probe = (enc->method_ < 2 && !do_search); 887 float q = enc->config_->quality; 888 const int max_passes = enc->config_->pass; 889 const int task_percent = 20; 890 const int percent_per_pass = (task_percent + max_passes / 2) / max_passes; 891 const int final_percent = enc->percent_ + task_percent; 892 int pass; 893 int nb_mbs; 894 895 // Fast mode: quick analysis pass over few mbs. Better than nothing. 896 nb_mbs = enc->mb_w_ * enc->mb_h_; 897 if (fast_probe && nb_mbs > 100) nb_mbs = 100; 898 899 // No target size: just do several pass without changing 'q' 900 if (!do_search) { 901 for (pass = 0; pass < max_passes; ++pass) { 902 const int rd_opt = (enc->method_ > 2); 903 if (!OneStatPass(enc, q, rd_opt, nb_mbs, NULL, percent_per_pass)) { 904 return 0; 905 } 906 } 907 } else { 908 // binary search for a size close to target 909 for (pass = 0; pass < max_passes && (dqs[pass] > 0); ++pass) { 910 const int rd_opt = 1; 911 float PSNR; 912 int criterion; 913 const int size = OneStatPass(enc, q, rd_opt, nb_mbs, &PSNR, 914 percent_per_pass); 915#if DEBUG_SEARCH 916 printf("#%d size=%d PSNR=%.2f q=%.2f\n", pass, size, PSNR, q); 917#endif 918 if (!size) return 0; 919 if (enc->config_->target_PSNR > 0) { 920 criterion = (PSNR < enc->config_->target_PSNR); 921 } else { 922 criterion = (size < enc->config_->target_size); 923 } 924 // dichotomize 925 if (criterion) { 926 q += dqs[pass]; 927 } else { 928 q -= dqs[pass]; 929 } 930 } 931 } 932 return WebPReportProgress(enc->pic_, final_percent, &enc->percent_); 933} 934 935//------------------------------------------------------------------------------ 936 937#if defined(__cplusplus) || defined(c_plusplus) 938} // extern "C" 939#endif 940