1 /* 2 * Copyright (c) 2010 The WebM project authors. All Rights Reserved. 3 * 4 * Use of this source code is governed by a BSD-style license 5 * that can be found in the LICENSE file in the root of the source 6 * tree. An additional intellectual property rights grant can be found 7 * in the file PATENTS. All contributing project authors may 8 * be found in the AUTHORS file in the root of the source tree. 9 */ 10 11 12 #include <math.h> 13 #include <stdio.h> 14 #include <string.h> 15 #include <assert.h> 16 #include "onyx_int.h" 17 #include "tokenize.h" 18 #include "vpx_mem/vpx_mem.h" 19 20 /* Global event counters used for accumulating statistics across several 21 compressions, then generating context.c = initial stats. */ 22 23 #ifdef VP8_ENTROPY_STATS 24 _int64 context_counters[BLOCK_TYPES] [COEF_BANDS] [PREV_COEF_CONTEXTS] [MAX_ENTROPY_TOKENS]; 25 #endif 26 void vp8_stuff_mb(VP8_COMP *cpi, MACROBLOCK *x, TOKENEXTRA **t) ; 27 void vp8_fix_contexts(MACROBLOCKD *x); 28 29 #include "dct_value_tokens.h" 30 #include "dct_value_cost.h" 31 32 const TOKENVALUE *const vp8_dct_value_tokens_ptr = dct_value_tokens + 33 DCT_MAX_VALUE; 34 const short *const vp8_dct_value_cost_ptr = dct_value_cost + DCT_MAX_VALUE; 35 36 #if 0 37 int skip_true_count = 0; 38 int skip_false_count = 0; 39 #endif 40 41 /* function used to generate dct_value_tokens and dct_value_cost tables */ 42 /* 43 static void fill_value_tokens() 44 { 45 46 TOKENVALUE *t = dct_value_tokens + DCT_MAX_VALUE; 47 const vp8_extra_bit_struct *e = vp8_extra_bits; 48 49 int i = -DCT_MAX_VALUE; 50 int sign = 1; 51 52 do 53 { 54 if (!i) 55 sign = 0; 56 57 { 58 const int a = sign ? -i : i; 59 int eb = sign; 60 61 if (a > 4) 62 { 63 int j = 4; 64 65 while (++j < 11 && e[j].base_val <= a) {} 66 67 t[i].Token = --j; 68 eb |= (a - e[j].base_val) << 1; 69 } 70 else 71 t[i].Token = a; 72 73 t[i].Extra = eb; 74 } 75 76 // initialize the cost for extra bits for all possible coefficient value. 77 { 78 int cost = 0; 79 const vp8_extra_bit_struct *p = vp8_extra_bits + t[i].Token; 80 81 if (p->base_val) 82 { 83 const int extra = t[i].Extra; 84 const int Length = p->Len; 85 86 if (Length) 87 cost += vp8_treed_cost(p->tree, p->prob, extra >> 1, Length); 88 89 cost += vp8_cost_bit(vp8_prob_half, extra & 1); // sign 90 dct_value_cost[i + DCT_MAX_VALUE] = cost; 91 } 92 93 } 94 95 } 96 while (++i < DCT_MAX_VALUE); 97 98 vp8_dct_value_tokens_ptr = dct_value_tokens + DCT_MAX_VALUE; 99 vp8_dct_value_cost_ptr = dct_value_cost + DCT_MAX_VALUE; 100 } 101 */ 102 103 static void tokenize2nd_order_b 104 ( 105 MACROBLOCK *x, 106 TOKENEXTRA **tp, 107 VP8_COMP *cpi 108 ) 109 { 110 MACROBLOCKD *xd = &x->e_mbd; 111 int pt; /* near block/prev token context index */ 112 int c; /* start at DC */ 113 TOKENEXTRA *t = *tp;/* store tokens starting here */ 114 const BLOCKD *b; 115 const short *qcoeff_ptr; 116 ENTROPY_CONTEXT * a; 117 ENTROPY_CONTEXT * l; 118 int band, rc, v, token; 119 int eob; 120 121 b = xd->block + 24; 122 qcoeff_ptr = b->qcoeff; 123 a = (ENTROPY_CONTEXT *)xd->above_context + 8; 124 l = (ENTROPY_CONTEXT *)xd->left_context + 8; 125 eob = xd->eobs[24]; 126 VP8_COMBINEENTROPYCONTEXTS(pt, *a, *l); 127 128 if(!eob) 129 { 130 /* c = band for this case */ 131 t->Token = DCT_EOB_TOKEN; 132 t->context_tree = cpi->common.fc.coef_probs [1] [0] [pt]; 133 t->skip_eob_node = 0; 134 135 ++x->coef_counts [1] [0] [pt] [DCT_EOB_TOKEN]; 136 t++; 137 *tp = t; 138 *a = *l = 0; 139 return; 140 } 141 142 v = qcoeff_ptr[0]; 143 t->Extra = vp8_dct_value_tokens_ptr[v].Extra; 144 token = vp8_dct_value_tokens_ptr[v].Token; 145 t->Token = token; 146 147 t->context_tree = cpi->common.fc.coef_probs [1] [0] [pt]; 148 t->skip_eob_node = 0; 149 ++x->coef_counts [1] [0] [pt] [token]; 150 pt = vp8_prev_token_class[token]; 151 t++; 152 c = 1; 153 154 for (; c < eob; c++) 155 { 156 rc = vp8_default_zig_zag1d[c]; 157 band = vp8_coef_bands[c]; 158 v = qcoeff_ptr[rc]; 159 160 t->Extra = vp8_dct_value_tokens_ptr[v].Extra; 161 token = vp8_dct_value_tokens_ptr[v].Token; 162 163 t->Token = token; 164 t->context_tree = cpi->common.fc.coef_probs [1] [band] [pt]; 165 166 t->skip_eob_node = ((pt == 0)); 167 168 ++x->coef_counts [1] [band] [pt] [token]; 169 170 pt = vp8_prev_token_class[token]; 171 t++; 172 } 173 if (c < 16) 174 { 175 band = vp8_coef_bands[c]; 176 t->Token = DCT_EOB_TOKEN; 177 t->context_tree = cpi->common.fc.coef_probs [1] [band] [pt]; 178 179 t->skip_eob_node = 0; 180 181 ++x->coef_counts [1] [band] [pt] [DCT_EOB_TOKEN]; 182 183 t++; 184 } 185 186 *tp = t; 187 *a = *l = 1; 188 189 } 190 191 static void tokenize1st_order_b 192 ( 193 MACROBLOCK *x, 194 TOKENEXTRA **tp, 195 int type, /* which plane: 0=Y no DC, 1=Y2, 2=UV, 3=Y with DC */ 196 VP8_COMP *cpi 197 ) 198 { 199 MACROBLOCKD *xd = &x->e_mbd; 200 unsigned int block; 201 const BLOCKD *b; 202 int pt; /* near block/prev token context index */ 203 int c; 204 int token; 205 TOKENEXTRA *t = *tp;/* store tokens starting here */ 206 const short *qcoeff_ptr; 207 ENTROPY_CONTEXT * a; 208 ENTROPY_CONTEXT * l; 209 int band, rc, v; 210 int tmp1, tmp2; 211 212 b = xd->block; 213 /* Luma */ 214 for (block = 0; block < 16; block++, b++) 215 { 216 const int eob = *b->eob; 217 tmp1 = vp8_block2above[block]; 218 tmp2 = vp8_block2left[block]; 219 qcoeff_ptr = b->qcoeff; 220 a = (ENTROPY_CONTEXT *)xd->above_context + tmp1; 221 l = (ENTROPY_CONTEXT *)xd->left_context + tmp2; 222 223 VP8_COMBINEENTROPYCONTEXTS(pt, *a, *l); 224 225 c = type ? 0 : 1; 226 227 if(c >= eob) 228 { 229 /* c = band for this case */ 230 t->Token = DCT_EOB_TOKEN; 231 t->context_tree = cpi->common.fc.coef_probs [type] [c] [pt]; 232 t->skip_eob_node = 0; 233 234 ++x->coef_counts [type] [c] [pt] [DCT_EOB_TOKEN]; 235 t++; 236 *tp = t; 237 *a = *l = 0; 238 continue; 239 } 240 241 v = qcoeff_ptr[c]; 242 243 t->Extra = vp8_dct_value_tokens_ptr[v].Extra; 244 token = vp8_dct_value_tokens_ptr[v].Token; 245 t->Token = token; 246 247 t->context_tree = cpi->common.fc.coef_probs [type] [c] [pt]; 248 t->skip_eob_node = 0; 249 ++x->coef_counts [type] [c] [pt] [token]; 250 pt = vp8_prev_token_class[token]; 251 t++; 252 c++; 253 254 assert(eob <= 16); 255 for (; c < eob; c++) 256 { 257 rc = vp8_default_zig_zag1d[c]; 258 band = vp8_coef_bands[c]; 259 v = qcoeff_ptr[rc]; 260 261 t->Extra = vp8_dct_value_tokens_ptr[v].Extra; 262 token = vp8_dct_value_tokens_ptr[v].Token; 263 264 t->Token = token; 265 t->context_tree = cpi->common.fc.coef_probs [type] [band] [pt]; 266 267 t->skip_eob_node = (pt == 0); 268 ++x->coef_counts [type] [band] [pt] [token]; 269 270 pt = vp8_prev_token_class[token]; 271 t++; 272 } 273 if (c < 16) 274 { 275 band = vp8_coef_bands[c]; 276 t->Token = DCT_EOB_TOKEN; 277 t->context_tree = cpi->common.fc.coef_probs [type] [band] [pt]; 278 279 t->skip_eob_node = 0; 280 ++x->coef_counts [type] [band] [pt] [DCT_EOB_TOKEN]; 281 282 t++; 283 } 284 *tp = t; 285 *a = *l = 1; 286 } 287 288 /* Chroma */ 289 for (block = 16; block < 24; block++, b++) 290 { 291 const int eob = *b->eob; 292 tmp1 = vp8_block2above[block]; 293 tmp2 = vp8_block2left[block]; 294 qcoeff_ptr = b->qcoeff; 295 a = (ENTROPY_CONTEXT *)xd->above_context + tmp1; 296 l = (ENTROPY_CONTEXT *)xd->left_context + tmp2; 297 298 VP8_COMBINEENTROPYCONTEXTS(pt, *a, *l); 299 300 if(!eob) 301 { 302 /* c = band for this case */ 303 t->Token = DCT_EOB_TOKEN; 304 t->context_tree = cpi->common.fc.coef_probs [2] [0] [pt]; 305 t->skip_eob_node = 0; 306 307 ++x->coef_counts [2] [0] [pt] [DCT_EOB_TOKEN]; 308 t++; 309 *tp = t; 310 *a = *l = 0; 311 continue; 312 } 313 314 v = qcoeff_ptr[0]; 315 316 t->Extra = vp8_dct_value_tokens_ptr[v].Extra; 317 token = vp8_dct_value_tokens_ptr[v].Token; 318 t->Token = token; 319 320 t->context_tree = cpi->common.fc.coef_probs [2] [0] [pt]; 321 t->skip_eob_node = 0; 322 ++x->coef_counts [2] [0] [pt] [token]; 323 pt = vp8_prev_token_class[token]; 324 t++; 325 c = 1; 326 327 assert(eob <= 16); 328 for (; c < eob; c++) 329 { 330 rc = vp8_default_zig_zag1d[c]; 331 band = vp8_coef_bands[c]; 332 v = qcoeff_ptr[rc]; 333 334 t->Extra = vp8_dct_value_tokens_ptr[v].Extra; 335 token = vp8_dct_value_tokens_ptr[v].Token; 336 337 t->Token = token; 338 t->context_tree = cpi->common.fc.coef_probs [2] [band] [pt]; 339 340 t->skip_eob_node = (pt == 0); 341 342 ++x->coef_counts [2] [band] [pt] [token]; 343 344 pt = vp8_prev_token_class[token]; 345 t++; 346 } 347 if (c < 16) 348 { 349 band = vp8_coef_bands[c]; 350 t->Token = DCT_EOB_TOKEN; 351 t->context_tree = cpi->common.fc.coef_probs [2] [band] [pt]; 352 353 t->skip_eob_node = 0; 354 355 ++x->coef_counts [2] [band] [pt] [DCT_EOB_TOKEN]; 356 357 t++; 358 } 359 *tp = t; 360 *a = *l = 1; 361 } 362 } 363 364 365 static int mb_is_skippable(MACROBLOCKD *x, int has_y2_block) 366 { 367 int skip = 1; 368 int i = 0; 369 370 if (has_y2_block) 371 { 372 for (i = 0; i < 16; i++) 373 skip &= (x->eobs[i] < 2); 374 } 375 376 for (; i < 24 + has_y2_block; i++) 377 skip &= (!x->eobs[i]); 378 379 return skip; 380 } 381 382 383 void vp8_tokenize_mb(VP8_COMP *cpi, MACROBLOCK *x, TOKENEXTRA **t) 384 { 385 MACROBLOCKD *xd = &x->e_mbd; 386 int plane_type; 387 int has_y2_block; 388 389 has_y2_block = (xd->mode_info_context->mbmi.mode != B_PRED 390 && xd->mode_info_context->mbmi.mode != SPLITMV); 391 392 xd->mode_info_context->mbmi.mb_skip_coeff = 393 mb_is_skippable(xd, has_y2_block); 394 if (xd->mode_info_context->mbmi.mb_skip_coeff) 395 { 396 if (!cpi->common.mb_no_coeff_skip) 397 { 398 vp8_stuff_mb(cpi, x, t); 399 } 400 else 401 { 402 vp8_fix_contexts(xd); 403 x->skip_true_count++; 404 } 405 406 return; 407 } 408 409 plane_type = 3; 410 if(has_y2_block) 411 { 412 tokenize2nd_order_b(x, t, cpi); 413 plane_type = 0; 414 } 415 416 tokenize1st_order_b(x, t, plane_type, cpi); 417 } 418 419 420 #ifdef VP8_ENTROPY_STATS 421 422 void init_context_counters(void) 423 { 424 vpx_memset(context_counters, 0, sizeof(context_counters)); 425 } 426 427 void print_context_counters() 428 { 429 430 int type, band, pt, t; 431 432 FILE *const f = fopen("context.c", "w"); 433 434 fprintf(f, "#include \"entropy.h\"\n"); 435 436 fprintf(f, "\n/* *** GENERATED FILE: DO NOT EDIT *** */\n\n"); 437 438 fprintf(f, "int Contexts[BLOCK_TYPES] [COEF_BANDS] [PREV_COEF_CONTEXTS] [MAX_ENTROPY_TOKENS];\n\n"); 439 440 fprintf(f, "const int default_contexts[BLOCK_TYPES] [COEF_BANDS] [PREV_COEF_CONTEXTS] [MAX_ENTROPY_TOKENS] = {"); 441 442 # define Comma( X) (X? ",":"") 443 444 type = 0; 445 446 do 447 { 448 fprintf(f, "%s\n { /* block Type %d */", Comma(type), type); 449 450 band = 0; 451 452 do 453 { 454 fprintf(f, "%s\n { /* Coeff Band %d */", Comma(band), band); 455 456 pt = 0; 457 458 do 459 { 460 fprintf(f, "%s\n {", Comma(pt)); 461 462 t = 0; 463 464 do 465 { 466 const _int64 x = context_counters [type] [band] [pt] [t]; 467 const int y = (int) x; 468 469 assert(x == (_int64) y); /* no overflow handling yet */ 470 fprintf(f, "%s %d", Comma(t), y); 471 472 } 473 while (++t < MAX_ENTROPY_TOKENS); 474 475 fprintf(f, "}"); 476 } 477 while (++pt < PREV_COEF_CONTEXTS); 478 479 fprintf(f, "\n }"); 480 481 } 482 while (++band < COEF_BANDS); 483 484 fprintf(f, "\n }"); 485 } 486 while (++type < BLOCK_TYPES); 487 488 fprintf(f, "\n};\n"); 489 fclose(f); 490 } 491 #endif 492 493 494 static void stuff2nd_order_b 495 ( 496 TOKENEXTRA **tp, 497 ENTROPY_CONTEXT *a, 498 ENTROPY_CONTEXT *l, 499 VP8_COMP *cpi, 500 MACROBLOCK *x 501 ) 502 { 503 int pt; /* near block/prev token context index */ 504 TOKENEXTRA *t = *tp; /* store tokens starting here */ 505 VP8_COMBINEENTROPYCONTEXTS(pt, *a, *l); 506 507 t->Token = DCT_EOB_TOKEN; 508 t->context_tree = cpi->common.fc.coef_probs [1] [0] [pt]; 509 t->skip_eob_node = 0; 510 ++x->coef_counts [1] [0] [pt] [DCT_EOB_TOKEN]; 511 ++t; 512 513 *tp = t; 514 pt = 0; 515 *a = *l = pt; 516 } 517 518 static void stuff1st_order_b 519 ( 520 TOKENEXTRA **tp, 521 ENTROPY_CONTEXT *a, 522 ENTROPY_CONTEXT *l, 523 int type, 524 VP8_COMP *cpi, 525 MACROBLOCK *x 526 ) 527 { 528 int pt; /* near block/prev token context index */ 529 int band; 530 TOKENEXTRA *t = *tp; /* store tokens starting here */ 531 VP8_COMBINEENTROPYCONTEXTS(pt, *a, *l); 532 band = type ? 0 : 1; 533 t->Token = DCT_EOB_TOKEN; 534 t->context_tree = cpi->common.fc.coef_probs [type] [band] [pt]; 535 t->skip_eob_node = 0; 536 ++x->coef_counts [type] [band] [pt] [DCT_EOB_TOKEN]; 537 ++t; 538 *tp = t; 539 pt = 0; /* 0 <-> all coeff data is zero */ 540 *a = *l = pt; 541 } 542 543 static 544 void stuff1st_order_buv 545 ( 546 TOKENEXTRA **tp, 547 ENTROPY_CONTEXT *a, 548 ENTROPY_CONTEXT *l, 549 VP8_COMP *cpi, 550 MACROBLOCK *x 551 ) 552 { 553 int pt; /* near block/prev token context index */ 554 TOKENEXTRA *t = *tp; /* store tokens starting here */ 555 VP8_COMBINEENTROPYCONTEXTS(pt, *a, *l); 556 557 t->Token = DCT_EOB_TOKEN; 558 t->context_tree = cpi->common.fc.coef_probs [2] [0] [pt]; 559 t->skip_eob_node = 0; 560 ++x->coef_counts[2] [0] [pt] [DCT_EOB_TOKEN]; 561 ++t; 562 *tp = t; 563 pt = 0; /* 0 <-> all coeff data is zero */ 564 *a = *l = pt; 565 } 566 567 void vp8_stuff_mb(VP8_COMP *cpi, MACROBLOCK *x, TOKENEXTRA **t) 568 { 569 MACROBLOCKD *xd = &x->e_mbd; 570 ENTROPY_CONTEXT * A = (ENTROPY_CONTEXT *)xd->above_context; 571 ENTROPY_CONTEXT * L = (ENTROPY_CONTEXT *)xd->left_context; 572 int plane_type; 573 int b; 574 plane_type = 3; 575 if((xd->mode_info_context->mbmi.mode != B_PRED 576 && xd->mode_info_context->mbmi.mode != SPLITMV)) 577 { 578 stuff2nd_order_b(t, 579 A + vp8_block2above[24], L + vp8_block2left[24], cpi, x); 580 plane_type = 0; 581 } 582 583 for (b = 0; b < 16; b++) 584 stuff1st_order_b(t, 585 A + vp8_block2above[b], 586 L + vp8_block2left[b], plane_type, cpi, x); 587 588 for (b = 16; b < 24; b++) 589 stuff1st_order_buv(t, 590 A + vp8_block2above[b], 591 L + vp8_block2left[b], cpi, x); 592 593 } 594 void vp8_fix_contexts(MACROBLOCKD *x) 595 { 596 /* Clear entropy contexts for Y2 blocks */ 597 if (x->mode_info_context->mbmi.mode != B_PRED && x->mode_info_context->mbmi.mode != SPLITMV) 598 { 599 vpx_memset(x->above_context, 0, sizeof(ENTROPY_CONTEXT_PLANES)); 600 vpx_memset(x->left_context, 0, sizeof(ENTROPY_CONTEXT_PLANES)); 601 } 602 else 603 { 604 vpx_memset(x->above_context, 0, sizeof(ENTROPY_CONTEXT_PLANES)-1); 605 vpx_memset(x->left_context, 0, sizeof(ENTROPY_CONTEXT_PLANES)-1); 606 } 607 608 } 609
