src/third_party/libvpx/source/libvpx/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 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 }