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 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 tmp1 = vp8_block2above[block]; 217 tmp2 = vp8_block2left[block]; 218 qcoeff_ptr = b->qcoeff; 219 a = (ENTROPY_CONTEXT *)xd->above_context + tmp1; 220 l = (ENTROPY_CONTEXT *)xd->left_context + tmp2; 221 222 VP8_COMBINEENTROPYCONTEXTS(pt, *a, *l); 223 224 c = type ? 0 : 1; 225 226 if(c >= *b->eob) 227 { 228 /* c = band for this case */ 229 t->Token = DCT_EOB_TOKEN; 230 t->context_tree = cpi->common.fc.coef_probs [type] [c] [pt]; 231 t->skip_eob_node = 0; 232 233 ++x->coef_counts [type] [c] [pt] [DCT_EOB_TOKEN]; 234 t++; 235 *tp = t; 236 *a = *l = 0; 237 continue; 238 } 239 240 v = qcoeff_ptr[c]; 241 242 t->Extra = vp8_dct_value_tokens_ptr[v].Extra; 243 token = vp8_dct_value_tokens_ptr[v].Token; 244 t->Token = token; 245 246 t->context_tree = cpi->common.fc.coef_probs [type] [c] [pt]; 247 t->skip_eob_node = 0; 248 ++x->coef_counts [type] [c] [pt] [token]; 249 pt = vp8_prev_token_class[token]; 250 t++; 251 c++; 252 253 for (; c < *b->eob; c++) 254 { 255 rc = vp8_default_zig_zag1d[c]; 256 band = vp8_coef_bands[c]; 257 v = qcoeff_ptr[rc]; 258 259 t->Extra = vp8_dct_value_tokens_ptr[v].Extra; 260 token = vp8_dct_value_tokens_ptr[v].Token; 261 262 t->Token = token; 263 t->context_tree = cpi->common.fc.coef_probs [type] [band] [pt]; 264 265 t->skip_eob_node = (pt == 0); 266 ++x->coef_counts [type] [band] [pt] [token]; 267 268 pt = vp8_prev_token_class[token]; 269 t++; 270 } 271 if (c < 16) 272 { 273 band = vp8_coef_bands[c]; 274 t->Token = DCT_EOB_TOKEN; 275 t->context_tree = cpi->common.fc.coef_probs [type] [band] [pt]; 276 277 t->skip_eob_node = 0; 278 ++x->coef_counts [type] [band] [pt] [DCT_EOB_TOKEN]; 279 280 t++; 281 } 282 *tp = t; 283 *a = *l = 1; 284 } 285 286 /* Chroma */ 287 for (block = 16; block < 24; block++, b++) 288 { 289 tmp1 = vp8_block2above[block]; 290 tmp2 = vp8_block2left[block]; 291 qcoeff_ptr = b->qcoeff; 292 a = (ENTROPY_CONTEXT *)xd->above_context + tmp1; 293 l = (ENTROPY_CONTEXT *)xd->left_context + tmp2; 294 295 VP8_COMBINEENTROPYCONTEXTS(pt, *a, *l); 296 297 if(!(*b->eob)) 298 { 299 /* c = band for this case */ 300 t->Token = DCT_EOB_TOKEN; 301 t->context_tree = cpi->common.fc.coef_probs [2] [0] [pt]; 302 t->skip_eob_node = 0; 303 304 ++x->coef_counts [2] [0] [pt] [DCT_EOB_TOKEN]; 305 t++; 306 *tp = t; 307 *a = *l = 0; 308 continue; 309 } 310 311 v = qcoeff_ptr[0]; 312 313 t->Extra = vp8_dct_value_tokens_ptr[v].Extra; 314 token = vp8_dct_value_tokens_ptr[v].Token; 315 t->Token = token; 316 317 t->context_tree = cpi->common.fc.coef_probs [2] [0] [pt]; 318 t->skip_eob_node = 0; 319 ++x->coef_counts [2] [0] [pt] [token]; 320 pt = vp8_prev_token_class[token]; 321 t++; 322 c = 1; 323 324 for (; c < *b->eob; c++) 325 { 326 rc = vp8_default_zig_zag1d[c]; 327 band = vp8_coef_bands[c]; 328 v = qcoeff_ptr[rc]; 329 330 t->Extra = vp8_dct_value_tokens_ptr[v].Extra; 331 token = vp8_dct_value_tokens_ptr[v].Token; 332 333 t->Token = token; 334 t->context_tree = cpi->common.fc.coef_probs [2] [band] [pt]; 335 336 t->skip_eob_node = (pt == 0); 337 338 ++x->coef_counts [2] [band] [pt] [token]; 339 340 pt = vp8_prev_token_class[token]; 341 t++; 342 } 343 if (c < 16) 344 { 345 band = vp8_coef_bands[c]; 346 t->Token = DCT_EOB_TOKEN; 347 t->context_tree = cpi->common.fc.coef_probs [2] [band] [pt]; 348 349 t->skip_eob_node = 0; 350 351 ++x->coef_counts [2] [band] [pt] [DCT_EOB_TOKEN]; 352 353 t++; 354 } 355 *tp = t; 356 *a = *l = 1; 357 } 358 } 359 360 361 static int mb_is_skippable(MACROBLOCKD *x, int has_y2_block) 362 { 363 int skip = 1; 364 int i = 0; 365 366 if (has_y2_block) 367 { 368 for (i = 0; i < 16; i++) 369 skip &= (x->eobs[i] < 2); 370 } 371 372 for (; i < 24 + has_y2_block; i++) 373 skip &= (!x->eobs[i]); 374 375 return skip; 376 } 377 378 379 void vp8_tokenize_mb(VP8_COMP *cpi, MACROBLOCK *x, TOKENEXTRA **t) 380 { 381 MACROBLOCKD *xd = &x->e_mbd; 382 int plane_type; 383 int has_y2_block; 384 385 has_y2_block = (xd->mode_info_context->mbmi.mode != B_PRED 386 && xd->mode_info_context->mbmi.mode != SPLITMV); 387 388 xd->mode_info_context->mbmi.mb_skip_coeff = 389 mb_is_skippable(xd, has_y2_block); 390 if (xd->mode_info_context->mbmi.mb_skip_coeff) 391 { 392 if (!cpi->common.mb_no_coeff_skip) 393 { 394 vp8_stuff_mb(cpi, x, t); 395 } 396 else 397 { 398 vp8_fix_contexts(xd); 399 x->skip_true_count++; 400 } 401 402 return; 403 } 404 405 plane_type = 3; 406 if(has_y2_block) 407 { 408 tokenize2nd_order_b(x, t, cpi); 409 plane_type = 0; 410 } 411 412 tokenize1st_order_b(x, t, plane_type, cpi); 413 } 414 415 416 #ifdef ENTROPY_STATS 417 418 void init_context_counters(void) 419 { 420 vpx_memset(context_counters, 0, sizeof(context_counters)); 421 } 422 423 void print_context_counters() 424 { 425 426 int type, band, pt, t; 427 428 FILE *const f = fopen("context.c", "w"); 429 430 fprintf(f, "#include \"entropy.h\"\n"); 431 432 fprintf(f, "\n/* *** GENERATED FILE: DO NOT EDIT *** */\n\n"); 433 434 fprintf(f, "int Contexts[BLOCK_TYPES] [COEF_BANDS] [PREV_COEF_CONTEXTS] [MAX_ENTROPY_TOKENS];\n\n"); 435 436 fprintf(f, "const int default_contexts[BLOCK_TYPES] [COEF_BANDS] [PREV_COEF_CONTEXTS] [MAX_ENTROPY_TOKENS] = {"); 437 438 # define Comma( X) (X? ",":"") 439 440 type = 0; 441 442 do 443 { 444 fprintf(f, "%s\n { /* block Type %d */", Comma(type), type); 445 446 band = 0; 447 448 do 449 { 450 fprintf(f, "%s\n { /* Coeff Band %d */", Comma(band), band); 451 452 pt = 0; 453 454 do 455 { 456 fprintf(f, "%s\n {", Comma(pt)); 457 458 t = 0; 459 460 do 461 { 462 const _int64 x = context_counters [type] [band] [pt] [t]; 463 const int y = (int) x; 464 465 assert(x == (_int64) y); /* no overflow handling yet */ 466 fprintf(f, "%s %d", Comma(t), y); 467 468 } 469 while (++t < MAX_ENTROPY_TOKENS); 470 471 fprintf(f, "}"); 472 } 473 while (++pt < PREV_COEF_CONTEXTS); 474 475 fprintf(f, "\n }"); 476 477 } 478 while (++band < COEF_BANDS); 479 480 fprintf(f, "\n }"); 481 } 482 while (++type < BLOCK_TYPES); 483 484 fprintf(f, "\n};\n"); 485 fclose(f); 486 } 487 #endif 488 489 490 static void stuff2nd_order_b 491 ( 492 TOKENEXTRA **tp, 493 ENTROPY_CONTEXT *a, 494 ENTROPY_CONTEXT *l, 495 VP8_COMP *cpi, 496 MACROBLOCK *x 497 ) 498 { 499 int pt; /* near block/prev token context index */ 500 TOKENEXTRA *t = *tp; /* store tokens starting here */ 501 VP8_COMBINEENTROPYCONTEXTS(pt, *a, *l); 502 503 t->Token = DCT_EOB_TOKEN; 504 t->context_tree = cpi->common.fc.coef_probs [1] [0] [pt]; 505 t->skip_eob_node = 0; 506 ++x->coef_counts [1] [0] [pt] [DCT_EOB_TOKEN]; 507 ++t; 508 509 *tp = t; 510 pt = 0; 511 *a = *l = pt; 512 } 513 514 static void stuff1st_order_b 515 ( 516 TOKENEXTRA **tp, 517 ENTROPY_CONTEXT *a, 518 ENTROPY_CONTEXT *l, 519 int type, 520 VP8_COMP *cpi, 521 MACROBLOCK *x 522 ) 523 { 524 int pt; /* near block/prev token context index */ 525 int band; 526 TOKENEXTRA *t = *tp; /* store tokens starting here */ 527 VP8_COMBINEENTROPYCONTEXTS(pt, *a, *l); 528 band = type ? 0 : 1; 529 t->Token = DCT_EOB_TOKEN; 530 t->context_tree = cpi->common.fc.coef_probs [type] [band] [pt]; 531 t->skip_eob_node = 0; 532 ++x->coef_counts [type] [band] [pt] [DCT_EOB_TOKEN]; 533 ++t; 534 *tp = t; 535 pt = 0; /* 0 <-> all coeff data is zero */ 536 *a = *l = pt; 537 } 538 539 static 540 void stuff1st_order_buv 541 ( 542 TOKENEXTRA **tp, 543 ENTROPY_CONTEXT *a, 544 ENTROPY_CONTEXT *l, 545 VP8_COMP *cpi, 546 MACROBLOCK *x 547 ) 548 { 549 int pt; /* near block/prev token context index */ 550 TOKENEXTRA *t = *tp; /* store tokens starting here */ 551 VP8_COMBINEENTROPYCONTEXTS(pt, *a, *l); 552 553 t->Token = DCT_EOB_TOKEN; 554 t->context_tree = cpi->common.fc.coef_probs [2] [0] [pt]; 555 t->skip_eob_node = 0; 556 ++x->coef_counts[2] [0] [pt] [DCT_EOB_TOKEN]; 557 ++t; 558 *tp = t; 559 pt = 0; /* 0 <-> all coeff data is zero */ 560 *a = *l = pt; 561 } 562 563 void vp8_stuff_mb(VP8_COMP *cpi, MACROBLOCK *x, TOKENEXTRA **t) 564 { 565 MACROBLOCKD *xd = &x->e_mbd; 566 ENTROPY_CONTEXT * A = (ENTROPY_CONTEXT *)xd->above_context; 567 ENTROPY_CONTEXT * L = (ENTROPY_CONTEXT *)xd->left_context; 568 int plane_type; 569 int b; 570 plane_type = 3; 571 if((xd->mode_info_context->mbmi.mode != B_PRED 572 && xd->mode_info_context->mbmi.mode != SPLITMV)) 573 { 574 stuff2nd_order_b(t, 575 A + vp8_block2above[24], L + vp8_block2left[24], cpi, x); 576 plane_type = 0; 577 } 578 579 for (b = 0; b < 16; b++) 580 stuff1st_order_b(t, 581 A + vp8_block2above[b], 582 L + vp8_block2left[b], plane_type, cpi, x); 583 584 for (b = 16; b < 24; b++) 585 stuff1st_order_buv(t, 586 A + vp8_block2above[b], 587 L + vp8_block2left[b], cpi, x); 588 589 } 590 void vp8_fix_contexts(MACROBLOCKD *x) 591 { 592 /* Clear entropy contexts for Y2 blocks */ 593 if (x->mode_info_context->mbmi.mode != B_PRED && x->mode_info_context->mbmi.mode != SPLITMV) 594 { 595 vpx_memset(x->above_context, 0, sizeof(ENTROPY_CONTEXT_PLANES)); 596 vpx_memset(x->left_context, 0, sizeof(ENTROPY_CONTEXT_PLANES)); 597 } 598 else 599 { 600 vpx_memset(x->above_context, 0, sizeof(ENTROPY_CONTEXT_PLANES)-1); 601 vpx_memset(x->left_context, 0, sizeof(ENTROPY_CONTEXT_PLANES)-1); 602 } 603 604 } 605