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