src/third_party/libvpx/source/libvpx/vp9/encoder/vp9_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 #include <assert.h>
  12 #include <math.h>
  13 #include <stdio.h>
  14 #include <string.h>
  15
  16 #include "vpx_mem/vpx_mem.h"
  17
  18 #include "vp9/common/vp9_entropy.h"
  19 #include "vp9/common/vp9_pred_common.h"
  20 #include "vp9/common/vp9_seg_common.h"
  21
  22 #include "vp9/encoder/vp9_cost.h"
  23 #include "vp9/encoder/vp9_encoder.h"
  24 #include "vp9/encoder/vp9_tokenize.h"
  25
  26 static TOKENVALUE dct_value_tokens[DCT_MAX_VALUE * 2];
  27 const TOKENVALUE *vp9_dct_value_tokens_ptr;
  28 static int16_t dct_value_cost[DCT_MAX_VALUE * 2];
  29 const int16_t *vp9_dct_value_cost_ptr;
  30
  31 #if CONFIG_VP9_HIGHBITDEPTH
  32 static TOKENVALUE dct_value_tokens_high10[DCT_MAX_VALUE_HIGH10 * 2];
  33 const TOKENVALUE *vp9_dct_value_tokens_high10_ptr;
  34 static int16_t dct_value_cost_high10[DCT_MAX_VALUE_HIGH10 * 2];
  35 const int16_t *vp9_dct_value_cost_high10_ptr;
  36
  37 static TOKENVALUE dct_value_tokens_high12[DCT_MAX_VALUE_HIGH12 * 2];
  38 const TOKENVALUE *vp9_dct_value_tokens_high12_ptr;
  39 static int16_t dct_value_cost_high12[DCT_MAX_VALUE_HIGH12 * 2];
  40 const int16_t *vp9_dct_value_cost_high12_ptr;
  41 #endif
  42
  43 // Array indices are identical to previously-existing CONTEXT_NODE indices
  44 const vp9_tree_index vp9_coef_tree[TREE_SIZE(ENTROPY_TOKENS)] = {
  45   -EOB_TOKEN, 2,                       // 0  = EOB
  46   -ZERO_TOKEN, 4,                      // 1  = ZERO
  47   -ONE_TOKEN, 6,                       // 2  = ONE
  48   8, 12,                               // 3  = LOW_VAL
  49   -TWO_TOKEN, 10,                      // 4  = TWO
  50   -THREE_TOKEN, -FOUR_TOKEN,           // 5  = THREE
  51   14, 16,                              // 6  = HIGH_LOW
  52   -CATEGORY1_TOKEN, -CATEGORY2_TOKEN,  // 7  = CAT_ONE
  53   18, 20,                              // 8  = CAT_THREEFOUR
  54   -CATEGORY3_TOKEN, -CATEGORY4_TOKEN,  // 9  = CAT_THREE
  55   -CATEGORY5_TOKEN, -CATEGORY6_TOKEN   // 10 = CAT_FIVE
  56 };
  57
  58 // Unconstrained Node Tree
  59 const vp9_tree_index vp9_coef_con_tree[TREE_SIZE(ENTROPY_TOKENS)] = {
  60   2, 6,                                // 0 = LOW_VAL
  61   -TWO_TOKEN, 4,                       // 1 = TWO
  62   -THREE_TOKEN, -FOUR_TOKEN,           // 2 = THREE
  63   8, 10,                               // 3 = HIGH_LOW
  64   -CATEGORY1_TOKEN, -CATEGORY2_TOKEN,  // 4 = CAT_ONE
  65   12, 14,                              // 5 = CAT_THREEFOUR
  66   -CATEGORY3_TOKEN, -CATEGORY4_TOKEN,  // 6 = CAT_THREE
  67   -CATEGORY5_TOKEN, -CATEGORY6_TOKEN   // 7 = CAT_FIVE
  68 };
  69
  70 static vp9_tree_index cat1[2], cat2[4], cat3[6], cat4[8], cat5[10], cat6[28];
  71
  72 #if CONFIG_VP9_HIGHBITDEPTH
  73 static vp9_tree_index cat1_high10[2];
  74 static vp9_tree_index cat2_high10[4];
  75 static vp9_tree_index cat3_high10[6];
  76 static vp9_tree_index cat4_high10[8];
  77 static vp9_tree_index cat5_high10[10];
  78 static vp9_tree_index cat6_high10[32];
  79 static vp9_tree_index cat1_high12[2];
  80 static vp9_tree_index cat2_high12[4];
  81 static vp9_tree_index cat3_high12[6];
  82 static vp9_tree_index cat4_high12[8];
  83 static vp9_tree_index cat5_high12[10];
  84 static vp9_tree_index cat6_high12[36];
  85 #endif
  86
  87 static void init_bit_tree(vp9_tree_index *p, int n) {
  88   int i = 0;
  89
  90   while (++i < n) {
  91     p[0] = p[1] = i << 1;
  92     p += 2;
  93   }
  94
  95   p[0] = p[1] = 0;
  96 }
  97
  98 static void init_bit_trees() {
  99   init_bit_tree(cat1, 1);
 100   init_bit_tree(cat2, 2);
 101   init_bit_tree(cat3, 3);
 102   init_bit_tree(cat4, 4);
 103   init_bit_tree(cat5, 5);
 104   init_bit_tree(cat6, 14);
 105 #if CONFIG_VP9_HIGHBITDEPTH
 106   init_bit_tree(cat1_high10, 1);
 107   init_bit_tree(cat2_high10, 2);
 108   init_bit_tree(cat3_high10, 3);
 109   init_bit_tree(cat4_high10, 4);
 110   init_bit_tree(cat5_high10, 5);
 111   init_bit_tree(cat6_high10, 16);
 112   init_bit_tree(cat1_high12, 1);
 113   init_bit_tree(cat2_high12, 2);
 114   init_bit_tree(cat3_high12, 3);
 115   init_bit_tree(cat4_high12, 4);
 116   init_bit_tree(cat5_high12, 5);
 117   init_bit_tree(cat6_high12, 18);
 118 #endif
 119 }
 120
 121 const vp9_extra_bit vp9_extra_bits[ENTROPY_TOKENS] = {
 122   {0, 0, 0, 0},                              // ZERO_TOKEN
 123   {0, 0, 0, 1},                              // ONE_TOKEN
 124   {0, 0, 0, 2},                              // TWO_TOKEN
 125   {0, 0, 0, 3},                              // THREE_TOKEN
 126   {0, 0, 0, 4},                              // FOUR_TOKEN
 127   {cat1, vp9_cat1_prob, 1,  CAT1_MIN_VAL},   // CATEGORY1_TOKEN
 128   {cat2, vp9_cat2_prob, 2,  CAT2_MIN_VAL},   // CATEGORY2_TOKEN
 129   {cat3, vp9_cat3_prob, 3,  CAT3_MIN_VAL},   // CATEGORY3_TOKEN
 130   {cat4, vp9_cat4_prob, 4,  CAT4_MIN_VAL},   // CATEGORY4_TOKEN
 131   {cat5, vp9_cat5_prob, 5,  CAT5_MIN_VAL},   // CATEGORY5_TOKEN
 132   {cat6, vp9_cat6_prob, 14, CAT6_MIN_VAL},   // CATEGORY6_TOKEN
 133   {0, 0, 0, 0}                               // EOB_TOKEN
 134 };
 135
 136 #if CONFIG_VP9_HIGHBITDEPTH
 137 const vp9_extra_bit vp9_extra_bits_high10[ENTROPY_TOKENS] = {
 138   {0, 0, 0, 0},                                            // ZERO_TOKEN
 139   {0, 0, 0, 1},                                            // ONE_TOKEN
 140   {0, 0, 0, 2},                                            // TWO_TOKEN
 141   {0, 0, 0, 3},                                            // THREE_TOKEN
 142   {0, 0, 0, 4},                                            // FOUR_TOKEN
 143   {cat1_high10, vp9_cat1_prob_high10, 1,  CAT1_MIN_VAL},   // CATEGORY1_TOKEN
 144   {cat2_high10, vp9_cat2_prob_high10, 2,  CAT2_MIN_VAL},   // CATEGORY2_TOKEN
 145   {cat3_high10, vp9_cat3_prob_high10, 3,  CAT3_MIN_VAL},   // CATEGORY3_TOKEN
 146   {cat4_high10, vp9_cat4_prob_high10, 4,  CAT4_MIN_VAL},   // CATEGORY4_TOKEN
 147   {cat5_high10, vp9_cat5_prob_high10, 5,  CAT5_MIN_VAL},   // CATEGORY5_TOKEN
 148   {cat6_high10, vp9_cat6_prob_high10, 16, CAT6_MIN_VAL},   // CATEGORY6_TOKEN
 149   {0, 0, 0, 0}                                             // EOB_TOKEN
 150 };
 151 const vp9_extra_bit vp9_extra_bits_high12[ENTROPY_TOKENS] = {
 152   {0, 0, 0, 0},                                            // ZERO_TOKEN
 153   {0, 0, 0, 1},                                            // ONE_TOKEN
 154   {0, 0, 0, 2},                                            // TWO_TOKEN
 155   {0, 0, 0, 3},                                            // THREE_TOKEN
 156   {0, 0, 0, 4},                                            // FOUR_TOKEN
 157   {cat1_high12, vp9_cat1_prob_high12, 1,  CAT1_MIN_VAL},   // CATEGORY1_TOKEN
 158   {cat2_high12, vp9_cat2_prob_high12, 2,  CAT2_MIN_VAL},   // CATEGORY2_TOKEN
 159   {cat3_high12, vp9_cat3_prob_high12, 3,  CAT3_MIN_VAL},   // CATEGORY3_TOKEN
 160   {cat4_high12, vp9_cat4_prob_high12, 4,  CAT4_MIN_VAL},   // CATEGORY4_TOKEN
 161   {cat5_high12, vp9_cat5_prob_high12, 5,  CAT5_MIN_VAL},   // CATEGORY5_TOKEN
 162   {cat6_high12, vp9_cat6_prob_high12, 18, CAT6_MIN_VAL},   // CATEGORY6_TOKEN
 163   {0, 0, 0, 0}                                             // EOB_TOKEN
 164 };
 165 #endif
 166
 167 struct vp9_token vp9_coef_encodings[ENTROPY_TOKENS];
 168
 169 void vp9_coef_tree_initialize() {
 170   init_bit_trees();
 171   vp9_tokens_from_tree(vp9_coef_encodings, vp9_coef_tree);
 172 }
 173
 174 static void tokenize_init_one(TOKENVALUE *t, const vp9_extra_bit *const e,
 175                               int16_t *value_cost, int max_value) {
 176   int i = -max_value;
 177   int sign = 1;
 178
 179   do {
 180     if (!i)
 181       sign = 0;
 182
 183     {
 184       const int a = sign ? -i : i;
 185       int eb = sign;
 186
 187       if (a > 4) {
 188         int j = 4;
 189
 190         while (++j < 11  &&  e[j].base_val <= a) {}
 191
 192         t[i].token = --j;
 193         eb |= (a - e[j].base_val) << 1;
 194       } else {
 195         t[i].token = a;
 196       }
 197       t[i].extra = eb;
 198     }
 199
 200     // initialize the cost for extra bits for all possible coefficient value.
 201     {
 202       int cost = 0;
 203       const vp9_extra_bit *p = &e[t[i].token];
 204
 205       if (p->base_val) {
 206         const int extra = t[i].extra;
 207         const int length = p->len;
 208
 209         if (length)
 210           cost += treed_cost(p->tree, p->prob, extra >> 1, length);
 211
 212         cost += vp9_cost_bit(vp9_prob_half, extra & 1); /* sign */
 213         value_cost[i] = cost;
 214       }
 215     }
 216   } while (++i < max_value);
 217 }
 218
 219 void vp9_tokenize_initialize() {
 220   vp9_dct_value_tokens_ptr = dct_value_tokens + DCT_MAX_VALUE;
 221   vp9_dct_value_cost_ptr = dct_value_cost + DCT_MAX_VALUE;
 222
 223   tokenize_init_one(dct_value_tokens + DCT_MAX_VALUE, vp9_extra_bits,
 224                     dct_value_cost + DCT_MAX_VALUE, DCT_MAX_VALUE);
 225 #if CONFIG_VP9_HIGHBITDEPTH
 226   vp9_dct_value_tokens_high10_ptr = dct_value_tokens_high10 +
 227       DCT_MAX_VALUE_HIGH10;
 228   vp9_dct_value_cost_high10_ptr = dct_value_cost_high10 + DCT_MAX_VALUE_HIGH10;
 229
 230   tokenize_init_one(dct_value_tokens_high10 + DCT_MAX_VALUE_HIGH10,
 231                     vp9_extra_bits_high10,
 232                     dct_value_cost_high10 + DCT_MAX_VALUE_HIGH10,
 233                     DCT_MAX_VALUE_HIGH10);
 234   vp9_dct_value_tokens_high12_ptr = dct_value_tokens_high12 +
 235       DCT_MAX_VALUE_HIGH12;
 236   vp9_dct_value_cost_high12_ptr = dct_value_cost_high12 + DCT_MAX_VALUE_HIGH12;
 237
 238   tokenize_init_one(dct_value_tokens_high12 + DCT_MAX_VALUE_HIGH12,
 239                     vp9_extra_bits_high12,
 240                     dct_value_cost_high12 + DCT_MAX_VALUE_HIGH12,
 241                     DCT_MAX_VALUE_HIGH12);
 242 #endif
 243 }
 244
 245 struct tokenize_b_args {
 246   VP9_COMP *cpi;
 247   MACROBLOCKD *xd;
 248   TOKENEXTRA **tp;
 249 };
 250
 251 static void set_entropy_context_b(int plane, int block, BLOCK_SIZE plane_bsize,
 252                                   TX_SIZE tx_size, void *arg) {
 253   struct tokenize_b_args* const args = arg;
 254   MACROBLOCKD *const xd = args->xd;
 255   struct macroblock_plane *p = &args->cpi->mb.plane[plane];
 256   struct macroblockd_plane *pd = &xd->plane[plane];
 257   int aoff, loff;
 258   txfrm_block_to_raster_xy(plane_bsize, tx_size, block, &aoff, &loff);
 259   vp9_set_contexts(xd, pd, plane_bsize, tx_size, p->eobs[block] > 0,
 260                    aoff, loff);
 261 }
 262
 263 static INLINE void add_token(TOKENEXTRA **t, const vp9_prob *context_tree,
 264                              int32_t extra, uint8_t token,
 265                              uint8_t skip_eob_node,
 266                              unsigned int *counts) {
 267   (*t)->token = token;
 268   (*t)->extra = extra;
 269   (*t)->context_tree = context_tree;
 270   (*t)->skip_eob_node = skip_eob_node;
 271   (*t)++;
 272   ++counts[token];
 273 }
 274
 275 static INLINE void add_token_no_extra(TOKENEXTRA **t,
 276                                       const vp9_prob *context_tree,
 277                                       uint8_t token,
 278                                       uint8_t skip_eob_node,
 279                                       unsigned int *counts) {
 280   (*t)->token = token;
 281   (*t)->context_tree = context_tree;
 282   (*t)->skip_eob_node = skip_eob_node;
 283   (*t)++;
 284   ++counts[token];
 285 }
 286
 287 static INLINE int get_tx_eob(const struct segmentation *seg, int segment_id,
 288                              TX_SIZE tx_size) {
 289   const int eob_max = 16 << (tx_size << 1);
 290   return vp9_segfeature_active(seg, segment_id, SEG_LVL_SKIP) ? 0 : eob_max;
 291 }
 292
 293 static void tokenize_b(int plane, int block, BLOCK_SIZE plane_bsize,
 294                        TX_SIZE tx_size, void *arg) {
 295   struct tokenize_b_args* const args = arg;
 296   VP9_COMP *cpi = args->cpi;
 297   MACROBLOCKD *xd = args->xd;
 298   TOKENEXTRA **tp = args->tp;
 299   uint8_t token_cache[32 * 32];
 300   struct macroblock_plane *p = &cpi->mb.plane[plane];
 301   struct macroblockd_plane *pd = &xd->plane[plane];
 302   MB_MODE_INFO *mbmi = &xd->mi[0].src_mi->mbmi;
 303   int pt; /* near block/prev token context index */
 304   int c;
 305   TOKENEXTRA *t = *tp;        /* store tokens starting here */
 306   int eob = p->eobs[block];
 307   const PLANE_TYPE type = pd->plane_type;
 308   const tran_low_t *qcoeff = BLOCK_OFFSET(p->qcoeff, block);
 309   const int segment_id = mbmi->segment_id;
 310   const int16_t *scan, *nb;
 311   const scan_order *so;
 312   const int ref = is_inter_block(mbmi);
 313   unsigned int (*const counts)[COEFF_CONTEXTS][ENTROPY_TOKENS] =
 314       cpi->coef_counts[tx_size][type][ref];
 315   vp9_prob (*const coef_probs)[COEFF_CONTEXTS][UNCONSTRAINED_NODES] =
 316       cpi->common.fc.coef_probs[tx_size][type][ref];
 317   unsigned int (*const eob_branch)[COEFF_CONTEXTS] =
 318       cpi->common.counts.eob_branch[tx_size][type][ref];
 319   const uint8_t *const band = get_band_translate(tx_size);
 320   const int seg_eob = get_tx_eob(&cpi->common.seg, segment_id, tx_size);
 321   const TOKENVALUE *dct_value_tokens;
 322
 323   int aoff, loff;
 324   txfrm_block_to_raster_xy(plane_bsize, tx_size, block, &aoff, &loff);
 325
 326   pt = get_entropy_context(tx_size, pd->above_context + aoff,
 327                            pd->left_context + loff);
 328   so = get_scan(xd, tx_size, type, block);
 329   scan = so->scan;
 330   nb = so->neighbors;
 331   c = 0;
 332 #if CONFIG_VP9_HIGHBITDEPTH
 333   if (cpi->common.profile >= PROFILE_2) {
 334     dct_value_tokens = (cpi->common.bit_depth == VPX_BITS_10 ?
 335                         vp9_dct_value_tokens_high10_ptr :
 336                         vp9_dct_value_tokens_high12_ptr);
 337   } else {
 338     dct_value_tokens = vp9_dct_value_tokens_ptr;
 339   }
 340 #else
 341   dct_value_tokens = vp9_dct_value_tokens_ptr;
 342 #endif
 343
 344   while (c < eob) {
 345     int v = 0;
 346     int skip_eob = 0;
 347     v = qcoeff[scan[c]];
 348
 349     while (!v) {
 350       add_token_no_extra(&t, coef_probs[band[c]][pt], ZERO_TOKEN, skip_eob,
 351                          counts[band[c]][pt]);
 352       eob_branch[band[c]][pt] += !skip_eob;
 353
 354       skip_eob = 1;
 355       token_cache[scan[c]] = 0;
 356       ++c;
 357       pt = get_coef_context(nb, token_cache, c);
 358       v = qcoeff[scan[c]];
 359     }
 360
 361     add_token(&t, coef_probs[band[c]][pt],
 362               dct_value_tokens[v].extra,
 363               (uint8_t)dct_value_tokens[v].token,
 364               (uint8_t)skip_eob,
 365               counts[band[c]][pt]);
 366     eob_branch[band[c]][pt] += !skip_eob;
 367
 368     token_cache[scan[c]] = vp9_pt_energy_class[dct_value_tokens[v].token];
 369     ++c;
 370     pt = get_coef_context(nb, token_cache, c);
 371   }
 372   if (c < seg_eob) {
 373     add_token_no_extra(&t, coef_probs[band[c]][pt], EOB_TOKEN, 0,
 374                        counts[band[c]][pt]);
 375     ++eob_branch[band[c]][pt];
 376   }
 377
 378   *tp = t;
 379
 380   vp9_set_contexts(xd, pd, plane_bsize, tx_size, c > 0, aoff, loff);
 381 }
 382
 383 struct is_skippable_args {
 384   MACROBLOCK *x;
 385   int *skippable;
 386 };
 387 static void is_skippable(int plane, int block,
 388                          BLOCK_SIZE plane_bsize, TX_SIZE tx_size,
 389                          void *argv) {
 390   struct is_skippable_args *args = argv;
 391   (void)plane_bsize;
 392   (void)tx_size;
 393   args->skippable[0] &= (!args->x->plane[plane].eobs[block]);
 394 }
 395
 396 // TODO(yaowu): rewrite and optimize this function to remove the usage of
 397 //              vp9_foreach_transform_block() and simplify is_skippable().
 398 int vp9_is_skippable_in_plane(MACROBLOCK *x, BLOCK_SIZE bsize, int plane) {
 399   int result = 1;
 400   struct is_skippable_args args = {x, &result};
 401   vp9_foreach_transformed_block_in_plane(&x->e_mbd, bsize, plane, is_skippable,
 402                                          &args);
 403   return result;
 404 }
 405
 406 static void has_high_freq_coeff(int plane, int block,
 407                                 BLOCK_SIZE plane_bsize, TX_SIZE tx_size,
 408                                 void *argv) {
 409   struct is_skippable_args *args = argv;
 410   int eobs = (tx_size == TX_4X4) ? 3 : 10;
 411   (void) plane_bsize;
 412
 413   *(args->skippable) |= (args->x->plane[plane].eobs[block] > eobs);
 414 }
 415
 416 int vp9_has_high_freq_in_plane(MACROBLOCK *x, BLOCK_SIZE bsize, int plane) {
 417   int result = 0;
 418   struct is_skippable_args args = {x, &result};
 419   vp9_foreach_transformed_block_in_plane(&x->e_mbd, bsize, plane,
 420                                          has_high_freq_coeff, &args);
 421   return result;
 422 }
 423
 424 void vp9_tokenize_sb(VP9_COMP *cpi, TOKENEXTRA **t, int dry_run,
 425                      BLOCK_SIZE bsize) {
 426   VP9_COMMON *const cm = &cpi->common;
 427   MACROBLOCKD *const xd = &cpi->mb.e_mbd;
 428   MB_MODE_INFO *const mbmi = &xd->mi[0].src_mi->mbmi;
 429   TOKENEXTRA *t_backup = *t;
 430   const int ctx = vp9_get_skip_context(xd);
 431   const int skip_inc = !vp9_segfeature_active(&cm->seg, mbmi->segment_id,
 432                                               SEG_LVL_SKIP);
 433   struct tokenize_b_args arg = {cpi, xd, t};
 434   if (mbmi->skip) {
 435     if (!dry_run)
 436       cm->counts.skip[ctx][1] += skip_inc;
 437     reset_skip_context(xd, bsize);
 438     if (dry_run)
 439       *t = t_backup;
 440     return;
 441   }
 442
 443   if (!dry_run) {
 444     cm->counts.skip[ctx][0] += skip_inc;
 445     vp9_foreach_transformed_block(xd, bsize, tokenize_b, &arg);
 446   } else {
 447     vp9_foreach_transformed_block(xd, bsize, set_entropy_context_b, &arg);
 448     *t = t_backup;
 449   }
 450 }