vp8/encoder/tokenize.c

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