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 #include <math.h> 12 #include <stdio.h> 13 #include <string.h> 14 #include <assert.h> 15 #include "onyx_int.h" 16 #include "tokenize.h" 17 #include "vpx_mem/vpx_mem.h" 18 19 /* Global event counters used for accumulating statistics across several 20 compressions, then generating context.c = initial stats. */ 21 22 #ifdef VP8_ENTROPY_STATS 23 _int64 context_counters[BLOCK_TYPES][COEF_BANDS][PREV_COEF_CONTEXTS] 24 [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 = 33 dct_value_tokens + 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 77 value. 78 { 79 int cost = 0; 80 const vp8_extra_bit_struct *p = vp8_extra_bits + t[i].Token; 81 82 if (p->base_val) 83 { 84 const int extra = t[i].Extra; 85 const int Length = p->Len; 86 87 if (Length) 88 cost += vp8_treed_cost(p->tree, p->prob, extra >> 1, 89 Length); 90 91 cost += vp8_cost_bit(vp8_prob_half, extra & 1); // sign 92 dct_value_cost[i + DCT_MAX_VALUE] = cost; 93 } 94 95 } 96 97 } 98 while (++i < DCT_MAX_VALUE); 99 100 vp8_dct_value_tokens_ptr = dct_value_tokens + DCT_MAX_VALUE; 101 vp8_dct_value_cost_ptr = dct_value_cost + DCT_MAX_VALUE; 102 } 103 */ 104 105 static void tokenize2nd_order_b(MACROBLOCK *x, TOKENEXTRA **tp, VP8_COMP *cpi) { 106 MACROBLOCKD *xd = &x->e_mbd; 107 int pt; /* near block/prev token context index */ 108 int c; /* start at DC */ 109 TOKENEXTRA *t = *tp; /* store tokens starting here */ 110 const BLOCKD *b; 111 const short *qcoeff_ptr; 112 ENTROPY_CONTEXT *a; 113 ENTROPY_CONTEXT *l; 114 int band, rc, v, token; 115 int eob; 116 117 b = xd->block + 24; 118 qcoeff_ptr = b->qcoeff; 119 a = (ENTROPY_CONTEXT *)xd->above_context + 8; 120 l = (ENTROPY_CONTEXT *)xd->left_context + 8; 121 eob = xd->eobs[24]; 122 VP8_COMBINEENTROPYCONTEXTS(pt, *a, *l); 123 124 if (!eob) { 125 /* c = band for this case */ 126 t->Token = DCT_EOB_TOKEN; 127 t->context_tree = cpi->common.fc.coef_probs[1][0][pt]; 128 t->skip_eob_node = 0; 129 130 ++x->coef_counts[1][0][pt][DCT_EOB_TOKEN]; 131 t++; 132 *tp = t; 133 *a = *l = 0; 134 return; 135 } 136 137 v = qcoeff_ptr[0]; 138 t->Extra = vp8_dct_value_tokens_ptr[v].Extra; 139 token = vp8_dct_value_tokens_ptr[v].Token; 140 t->Token = token; 141 142 t->context_tree = cpi->common.fc.coef_probs[1][0][pt]; 143 t->skip_eob_node = 0; 144 ++x->coef_counts[1][0][pt][token]; 145 pt = vp8_prev_token_class[token]; 146 t++; 147 c = 1; 148 149 for (; c < eob; ++c) { 150 rc = vp8_default_zig_zag1d[c]; 151 band = vp8_coef_bands[c]; 152 v = qcoeff_ptr[rc]; 153 154 t->Extra = vp8_dct_value_tokens_ptr[v].Extra; 155 token = vp8_dct_value_tokens_ptr[v].Token; 156 157 t->Token = token; 158 t->context_tree = cpi->common.fc.coef_probs[1][band][pt]; 159 160 t->skip_eob_node = ((pt == 0)); 161 162 ++x->coef_counts[1][band][pt][token]; 163 164 pt = vp8_prev_token_class[token]; 165 t++; 166 } 167 if (c < 16) { 168 band = vp8_coef_bands[c]; 169 t->Token = DCT_EOB_TOKEN; 170 t->context_tree = cpi->common.fc.coef_probs[1][band][pt]; 171 172 t->skip_eob_node = 0; 173 174 ++x->coef_counts[1][band][pt][DCT_EOB_TOKEN]; 175 176 t++; 177 } 178 179 *tp = t; 180 *a = *l = 1; 181 } 182 183 static void tokenize1st_order_b( 184 MACROBLOCK *x, TOKENEXTRA **tp, 185 int type, /* which plane: 0=Y no DC, 1=Y2, 2=UV, 3=Y with DC */ 186 VP8_COMP *cpi) { 187 MACROBLOCKD *xd = &x->e_mbd; 188 unsigned int block; 189 const BLOCKD *b; 190 int pt; /* near block/prev token context index */ 191 int c; 192 int token; 193 TOKENEXTRA *t = *tp; /* store tokens starting here */ 194 const short *qcoeff_ptr; 195 ENTROPY_CONTEXT *a; 196 ENTROPY_CONTEXT *l; 197 int band, rc, v; 198 int tmp1, tmp2; 199 200 b = xd->block; 201 /* Luma */ 202 for (block = 0; block < 16; block++, b++) { 203 const int eob = *b->eob; 204 tmp1 = vp8_block2above[block]; 205 tmp2 = vp8_block2left[block]; 206 qcoeff_ptr = b->qcoeff; 207 a = (ENTROPY_CONTEXT *)xd->above_context + tmp1; 208 l = (ENTROPY_CONTEXT *)xd->left_context + tmp2; 209 210 VP8_COMBINEENTROPYCONTEXTS(pt, *a, *l); 211 212 c = type ? 0 : 1; 213 214 if (c >= eob) { 215 /* c = band for this case */ 216 t->Token = DCT_EOB_TOKEN; 217 t->context_tree = cpi->common.fc.coef_probs[type][c][pt]; 218 t->skip_eob_node = 0; 219 220 ++x->coef_counts[type][c][pt][DCT_EOB_TOKEN]; 221 t++; 222 *tp = t; 223 *a = *l = 0; 224 continue; 225 } 226 227 v = qcoeff_ptr[c]; 228 229 t->Extra = vp8_dct_value_tokens_ptr[v].Extra; 230 token = vp8_dct_value_tokens_ptr[v].Token; 231 t->Token = token; 232 233 t->context_tree = cpi->common.fc.coef_probs[type][c][pt]; 234 t->skip_eob_node = 0; 235 ++x->coef_counts[type][c][pt][token]; 236 pt = vp8_prev_token_class[token]; 237 t++; 238 c++; 239 240 assert(eob <= 16); 241 for (; c < eob; ++c) { 242 rc = vp8_default_zig_zag1d[c]; 243 band = vp8_coef_bands[c]; 244 v = qcoeff_ptr[rc]; 245 246 t->Extra = vp8_dct_value_tokens_ptr[v].Extra; 247 token = vp8_dct_value_tokens_ptr[v].Token; 248 249 t->Token = token; 250 t->context_tree = cpi->common.fc.coef_probs[type][band][pt]; 251 252 t->skip_eob_node = (pt == 0); 253 ++x->coef_counts[type][band][pt][token]; 254 255 pt = vp8_prev_token_class[token]; 256 t++; 257 } 258 if (c < 16) { 259 band = vp8_coef_bands[c]; 260 t->Token = DCT_EOB_TOKEN; 261 t->context_tree = cpi->common.fc.coef_probs[type][band][pt]; 262 263 t->skip_eob_node = 0; 264 ++x->coef_counts[type][band][pt][DCT_EOB_TOKEN]; 265 266 t++; 267 } 268 *tp = t; 269 *a = *l = 1; 270 } 271 272 /* Chroma */ 273 for (block = 16; block < 24; block++, b++) { 274 const int eob = *b->eob; 275 tmp1 = vp8_block2above[block]; 276 tmp2 = vp8_block2left[block]; 277 qcoeff_ptr = b->qcoeff; 278 a = (ENTROPY_CONTEXT *)xd->above_context + tmp1; 279 l = (ENTROPY_CONTEXT *)xd->left_context + tmp2; 280 281 VP8_COMBINEENTROPYCONTEXTS(pt, *a, *l); 282 283 if (!eob) { 284 /* c = band for this case */ 285 t->Token = DCT_EOB_TOKEN; 286 t->context_tree = cpi->common.fc.coef_probs[2][0][pt]; 287 t->skip_eob_node = 0; 288 289 ++x->coef_counts[2][0][pt][DCT_EOB_TOKEN]; 290 t++; 291 *tp = t; 292 *a = *l = 0; 293 continue; 294 } 295 296 v = qcoeff_ptr[0]; 297 298 t->Extra = vp8_dct_value_tokens_ptr[v].Extra; 299 token = vp8_dct_value_tokens_ptr[v].Token; 300 t->Token = token; 301 302 t->context_tree = cpi->common.fc.coef_probs[2][0][pt]; 303 t->skip_eob_node = 0; 304 ++x->coef_counts[2][0][pt][token]; 305 pt = vp8_prev_token_class[token]; 306 t++; 307 c = 1; 308 309 assert(eob <= 16); 310 for (; c < eob; ++c) { 311 rc = vp8_default_zig_zag1d[c]; 312 band = vp8_coef_bands[c]; 313 v = qcoeff_ptr[rc]; 314 315 t->Extra = vp8_dct_value_tokens_ptr[v].Extra; 316 token = vp8_dct_value_tokens_ptr[v].Token; 317 318 t->Token = token; 319 t->context_tree = cpi->common.fc.coef_probs[2][band][pt]; 320 321 t->skip_eob_node = (pt == 0); 322 323 ++x->coef_counts[2][band][pt][token]; 324 325 pt = vp8_prev_token_class[token]; 326 t++; 327 } 328 if (c < 16) { 329 band = vp8_coef_bands[c]; 330 t->Token = DCT_EOB_TOKEN; 331 t->context_tree = cpi->common.fc.coef_probs[2][band][pt]; 332 333 t->skip_eob_node = 0; 334 335 ++x->coef_counts[2][band][pt][DCT_EOB_TOKEN]; 336 337 t++; 338 } 339 *tp = t; 340 *a = *l = 1; 341 } 342 } 343 344 static int mb_is_skippable(MACROBLOCKD *x, int has_y2_block) { 345 int skip = 1; 346 int i = 0; 347 348 if (has_y2_block) { 349 for (i = 0; i < 16; ++i) skip &= (x->eobs[i] < 2); 350 } 351 352 for (; i < 24 + has_y2_block; ++i) skip &= (!x->eobs[i]); 353 354 return skip; 355 } 356 357 void vp8_tokenize_mb(VP8_COMP *cpi, MACROBLOCK *x, TOKENEXTRA **t) { 358 MACROBLOCKD *xd = &x->e_mbd; 359 int plane_type; 360 int has_y2_block; 361 362 has_y2_block = (xd->mode_info_context->mbmi.mode != B_PRED && 363 xd->mode_info_context->mbmi.mode != SPLITMV); 364 365 xd->mode_info_context->mbmi.mb_skip_coeff = mb_is_skippable(xd, has_y2_block); 366 if (xd->mode_info_context->mbmi.mb_skip_coeff) { 367 if (!cpi->common.mb_no_coeff_skip) { 368 vp8_stuff_mb(cpi, x, t); 369 } else { 370 vp8_fix_contexts(xd); 371 x->skip_true_count++; 372 } 373 374 return; 375 } 376 377 plane_type = 3; 378 if (has_y2_block) { 379 tokenize2nd_order_b(x, t, cpi); 380 plane_type = 0; 381 } 382 383 tokenize1st_order_b(x, t, plane_type, cpi); 384 } 385 386 #ifdef VP8_ENTROPY_STATS 387 388 void init_context_counters(void) { 389 memset(context_counters, 0, sizeof(context_counters)); 390 } 391 392 void print_context_counters() { 393 int type, band, pt, t; 394 395 FILE *const f = fopen("context.c", "w"); 396 397 fprintf(f, "#include \"entropy.h\"\n"); 398 399 fprintf(f, "\n/* *** GENERATED FILE: DO NOT EDIT *** */\n\n"); 400 401 fprintf(f, 402 "int Contexts[BLOCK_TYPES] [COEF_BANDS] [PREV_COEF_CONTEXTS] " 403 "[MAX_ENTROPY_TOKENS];\n\n"); 404 405 fprintf(f, 406 "const int default_contexts[BLOCK_TYPES] [COEF_BANDS] " 407 "[PREV_COEF_CONTEXTS] [MAX_ENTROPY_TOKENS] = {"); 408 409 #define Comma(X) (X ? "," : "") 410 411 type = 0; 412 413 do { 414 fprintf(f, "%s\n { /* block Type %d */", Comma(type), type); 415 416 band = 0; 417 418 do { 419 fprintf(f, "%s\n { /* Coeff Band %d */", Comma(band), band); 420 421 pt = 0; 422 423 do { 424 fprintf(f, "%s\n {", Comma(pt)); 425 426 t = 0; 427 428 do { 429 const _int64 x = context_counters[type][band][pt][t]; 430 const int y = (int)x; 431 432 assert(x == (_int64)y); /* no overflow handling yet */ 433 fprintf(f, "%s %d", Comma(t), y); 434 435 } while (++t < MAX_ENTROPY_TOKENS); 436 437 fprintf(f, "}"); 438 } while (++pt < PREV_COEF_CONTEXTS); 439 440 fprintf(f, "\n }"); 441 442 } while (++band < COEF_BANDS); 443 444 fprintf(f, "\n }"); 445 } while (++type < BLOCK_TYPES); 446 447 fprintf(f, "\n};\n"); 448 fclose(f); 449 } 450 #endif 451 452 static void stuff2nd_order_b(TOKENEXTRA **tp, ENTROPY_CONTEXT *a, 453 ENTROPY_CONTEXT *l, VP8_COMP *cpi, MACROBLOCK *x) { 454 int pt; /* near block/prev token context index */ 455 TOKENEXTRA *t = *tp; /* store tokens starting here */ 456 VP8_COMBINEENTROPYCONTEXTS(pt, *a, *l); 457 458 t->Token = DCT_EOB_TOKEN; 459 t->context_tree = cpi->common.fc.coef_probs[1][0][pt]; 460 t->skip_eob_node = 0; 461 ++x->coef_counts[1][0][pt][DCT_EOB_TOKEN]; 462 ++t; 463 464 *tp = t; 465 pt = 0; 466 *a = *l = pt; 467 } 468 469 static void stuff1st_order_b(TOKENEXTRA **tp, ENTROPY_CONTEXT *a, 470 ENTROPY_CONTEXT *l, int type, VP8_COMP *cpi, 471 MACROBLOCK *x) { 472 int pt; /* near block/prev token context index */ 473 int band; 474 TOKENEXTRA *t = *tp; /* store tokens starting here */ 475 VP8_COMBINEENTROPYCONTEXTS(pt, *a, *l); 476 band = type ? 0 : 1; 477 t->Token = DCT_EOB_TOKEN; 478 t->context_tree = cpi->common.fc.coef_probs[type][band][pt]; 479 t->skip_eob_node = 0; 480 ++x->coef_counts[type][band][pt][DCT_EOB_TOKEN]; 481 ++t; 482 *tp = t; 483 pt = 0; /* 0 <-> all coeff data is zero */ 484 *a = *l = pt; 485 } 486 487 static void stuff1st_order_buv(TOKENEXTRA **tp, ENTROPY_CONTEXT *a, 488 ENTROPY_CONTEXT *l, VP8_COMP *cpi, 489 MACROBLOCK *x) { 490 int pt; /* near block/prev token context index */ 491 TOKENEXTRA *t = *tp; /* store tokens starting here */ 492 VP8_COMBINEENTROPYCONTEXTS(pt, *a, *l); 493 494 t->Token = DCT_EOB_TOKEN; 495 t->context_tree = cpi->common.fc.coef_probs[2][0][pt]; 496 t->skip_eob_node = 0; 497 ++x->coef_counts[2][0][pt][DCT_EOB_TOKEN]; 498 ++t; 499 *tp = t; 500 pt = 0; /* 0 <-> all coeff data is zero */ 501 *a = *l = pt; 502 } 503 504 void vp8_stuff_mb(VP8_COMP *cpi, MACROBLOCK *x, TOKENEXTRA **t) { 505 MACROBLOCKD *xd = &x->e_mbd; 506 ENTROPY_CONTEXT *A = (ENTROPY_CONTEXT *)xd->above_context; 507 ENTROPY_CONTEXT *L = (ENTROPY_CONTEXT *)xd->left_context; 508 int plane_type; 509 int b; 510 plane_type = 3; 511 if ((xd->mode_info_context->mbmi.mode != B_PRED && 512 xd->mode_info_context->mbmi.mode != SPLITMV)) { 513 stuff2nd_order_b(t, A + vp8_block2above[24], L + vp8_block2left[24], cpi, 514 x); 515 plane_type = 0; 516 } 517 518 for (b = 0; b < 16; ++b) { 519 stuff1st_order_b(t, A + vp8_block2above[b], L + vp8_block2left[b], 520 plane_type, cpi, x); 521 } 522 523 for (b = 16; b < 24; ++b) { 524 stuff1st_order_buv(t, A + vp8_block2above[b], L + vp8_block2left[b], cpi, 525 x); 526 } 527 } 528 void vp8_fix_contexts(MACROBLOCKD *x) { 529 /* Clear entropy contexts for Y2 blocks */ 530 if (x->mode_info_context->mbmi.mode != B_PRED && 531 x->mode_info_context->mbmi.mode != SPLITMV) { 532 memset(x->above_context, 0, sizeof(ENTROPY_CONTEXT_PLANES)); 533 memset(x->left_context, 0, sizeof(ENTROPY_CONTEXT_PLANES)); 534 } else { 535 memset(x->above_context, 0, sizeof(ENTROPY_CONTEXT_PLANES) - 1); 536 memset(x->left_context, 0, sizeof(ENTROPY_CONTEXT_PLANES) - 1); 537 } 538 } 539
