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