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 // Array indices are identical to previously-existing CONTEXT_NODE indices
  32 const vp9_tree_index vp9_coef_tree[TREE_SIZE(ENTROPY_TOKENS)] = {
  33   -EOB_TOKEN, 2,                       // 0  = EOB
  34   -ZERO_TOKEN, 4,                      // 1  = ZERO
  35   -ONE_TOKEN, 6,                       // 2  = ONE
  36   8, 12,                               // 3  = LOW_VAL
  37   -TWO_TOKEN, 10,                      // 4  = TWO
  38   -THREE_TOKEN, -FOUR_TOKEN,           // 5  = THREE
  39   14, 16,                              // 6  = HIGH_LOW
  40   -CATEGORY1_TOKEN, -CATEGORY2_TOKEN,  // 7  = CAT_ONE
  41   18, 20,                              // 8  = CAT_THREEFOUR
  42   -CATEGORY3_TOKEN, -CATEGORY4_TOKEN,  // 9  = CAT_THREE
  43   -CATEGORY5_TOKEN, -CATEGORY6_TOKEN   // 10 = CAT_FIVE
  44 };
  45
  46 // Unconstrained Node Tree
  47 const vp9_tree_index vp9_coef_con_tree[TREE_SIZE(ENTROPY_TOKENS)] = {
  48   2, 6,                                // 0 = LOW_VAL
  49   -TWO_TOKEN, 4,                       // 1 = TWO
  50   -THREE_TOKEN, -FOUR_TOKEN,           // 2 = THREE
  51   8, 10,                               // 3 = HIGH_LOW
  52   -CATEGORY1_TOKEN, -CATEGORY2_TOKEN,  // 4 = CAT_ONE
  53   12, 14,                              // 5 = CAT_THREEFOUR
  54   -CATEGORY3_TOKEN, -CATEGORY4_TOKEN,  // 6 = CAT_THREE
  55   -CATEGORY5_TOKEN, -CATEGORY6_TOKEN   // 7 = CAT_FIVE
  56 };
  57
  58 static const vp9_prob Pcat1[] = { 159};
  59 static const vp9_prob Pcat2[] = { 165, 145};
  60 static const vp9_prob Pcat3[] = { 173, 148, 140};
  61 static const vp9_prob Pcat4[] = { 176, 155, 140, 135};
  62 static const vp9_prob Pcat5[] = { 180, 157, 141, 134, 130};
  63 static const vp9_prob Pcat6[] = {
  64   254, 254, 254, 252, 249, 243, 230, 196, 177, 153, 140, 133, 130, 129
  65 };
  66
  67 static vp9_tree_index cat1[2], cat2[4], cat3[6], cat4[8], cat5[10], cat6[28];
  68
  69 static void init_bit_tree(vp9_tree_index *p, int n) {
  70   int i = 0;
  71
  72   while (++i < n) {
  73     p[0] = p[1] = i << 1;
  74     p += 2;
  75   }
  76
  77   p[0] = p[1] = 0;
  78 }
  79
  80 static void init_bit_trees() {
  81   init_bit_tree(cat1, 1);
  82   init_bit_tree(cat2, 2);
  83   init_bit_tree(cat3, 3);
  84   init_bit_tree(cat4, 4);
  85   init_bit_tree(cat5, 5);
  86   init_bit_tree(cat6, 14);
  87 }
  88
  89 const vp9_extra_bit vp9_extra_bits[ENTROPY_TOKENS] = {
  90   {0, 0, 0, 0},           // ZERO_TOKEN
  91   {0, 0, 0, 1},           // ONE_TOKEN
  92   {0, 0, 0, 2},           // TWO_TOKEN
  93   {0, 0, 0, 3},           // THREE_TOKEN
  94   {0, 0, 0, 4},           // FOUR_TOKEN
  95   {cat1, Pcat1, 1, 5},    // CATEGORY1_TOKEN
  96   {cat2, Pcat2, 2, 7},    // CATEGORY2_TOKEN
  97   {cat3, Pcat3, 3, 11},   // CATEGORY3_TOKEN
  98   {cat4, Pcat4, 4, 19},   // CATEGORY4_TOKEN
  99   {cat5, Pcat5, 5, 35},   // CATEGORY5_TOKEN
 100   {cat6, Pcat6, 14, 67},  // CATEGORY6_TOKEN
 101   {0, 0, 0, 0}            // EOB_TOKEN
 102 };
 103
 104 struct vp9_token vp9_coef_encodings[ENTROPY_TOKENS];
 105
 106 void vp9_coef_tree_initialize() {
 107   init_bit_trees();
 108   vp9_tokens_from_tree(vp9_coef_encodings, vp9_coef_tree);
 109 }
 110
 111 void vp9_tokenize_initialize() {
 112   TOKENVALUE *const t = dct_value_tokens + DCT_MAX_VALUE;
 113   const vp9_extra_bit *const e = vp9_extra_bits;
 114
 115   int i = -DCT_MAX_VALUE;
 116   int sign = 1;
 117
 118   do {
 119     if (!i)
 120       sign = 0;
 121
 122     {
 123       const int a = sign ? -i : i;
 124       int eb = sign;
 125
 126       if (a > 4) {
 127         int j = 4;
 128
 129         while (++j < 11  &&  e[j].base_val <= a) {}
 130
 131         t[i].token = --j;
 132         eb |= (a - e[j].base_val) << 1;
 133       } else {
 134         t[i].token = a;
 135       }
 136       t[i].extra = eb;
 137     }
 138
 139     // initialize the cost for extra bits for all possible coefficient value.
 140     {
 141       int cost = 0;
 142       const vp9_extra_bit *p = &vp9_extra_bits[t[i].token];
 143
 144       if (p->base_val) {
 145         const int extra = t[i].extra;
 146         const int length = p->len;
 147
 148         if (length)
 149           cost += treed_cost(p->tree, p->prob, extra >> 1, length);
 150
 151         cost += vp9_cost_bit(vp9_prob_half, extra & 1); /* sign */
 152         dct_value_cost[i + DCT_MAX_VALUE] = cost;
 153       }
 154     }
 155   } while (++i < DCT_MAX_VALUE);
 156
 157   vp9_dct_value_tokens_ptr = dct_value_tokens + DCT_MAX_VALUE;
 158   vp9_dct_value_cost_ptr = dct_value_cost + DCT_MAX_VALUE;
 159 }
 160
 161 struct tokenize_b_args {
 162   VP9_COMP *cpi;
 163   MACROBLOCKD *xd;
 164   TOKENEXTRA **tp;
 165 };
 166
 167 static void set_entropy_context_b(int plane, int block, BLOCK_SIZE plane_bsize,
 168                                   TX_SIZE tx_size, void *arg) {
 169   struct tokenize_b_args* const args = arg;
 170   MACROBLOCKD *const xd = args->xd;
 171   struct macroblock_plane *p = &args->cpi->mb.plane[plane];
 172   struct macroblockd_plane *pd = &xd->plane[plane];
 173   int aoff, loff;
 174   txfrm_block_to_raster_xy(plane_bsize, tx_size, block, &aoff, &loff);
 175   vp9_set_contexts(xd, pd, plane_bsize, tx_size, p->eobs[block] > 0,
 176                    aoff, loff);
 177 }
 178
 179 static INLINE void add_token(TOKENEXTRA **t, const vp9_prob *context_tree,
 180                              int16_t extra, uint8_t token,
 181                              uint8_t skip_eob_node,
 182                              unsigned int *counts) {
 183   (*t)->token = token;
 184   (*t)->extra = extra;
 185   (*t)->context_tree = context_tree;
 186   (*t)->skip_eob_node = skip_eob_node;
 187   (*t)++;
 188   ++counts[token];
 189 }
 190
 191 static INLINE void add_token_no_extra(TOKENEXTRA **t,
 192                                       const vp9_prob *context_tree,
 193                                       uint8_t token,
 194                                       uint8_t skip_eob_node,
 195                                       unsigned int *counts) {
 196   (*t)->token = token;
 197   (*t)->context_tree = context_tree;
 198   (*t)->skip_eob_node = skip_eob_node;
 199   (*t)++;
 200   ++counts[token];
 201 }
 202
 203 static INLINE int get_tx_eob(const struct segmentation *seg, int segment_id,
 204                              TX_SIZE tx_size) {
 205   const int eob_max = 16 << (tx_size << 1);
 206   return vp9_segfeature_active(seg, segment_id, SEG_LVL_SKIP) ? 0 : eob_max;
 207 }
 208
 209 static void tokenize_b(int plane, int block, BLOCK_SIZE plane_bsize,
 210                        TX_SIZE tx_size, void *arg) {
 211   struct tokenize_b_args* const args = arg;
 212   VP9_COMP *cpi = args->cpi;
 213   MACROBLOCKD *xd = args->xd;
 214   TOKENEXTRA **tp = args->tp;
 215   uint8_t token_cache[32 * 32];
 216   struct macroblock_plane *p = &cpi->mb.plane[plane];
 217   struct macroblockd_plane *pd = &xd->plane[plane];
 218   MB_MODE_INFO *mbmi = &xd->mi[0]->mbmi;
 219   int pt; /* near block/prev token context index */
 220   int c;
 221   TOKENEXTRA *t = *tp;        /* store tokens starting here */
 222   int eob = p->eobs[block];
 223   const PLANE_TYPE type = pd->plane_type;
 224   const int16_t *qcoeff = BLOCK_OFFSET(p->qcoeff, block);
 225   const int segment_id = mbmi->segment_id;
 226   const int16_t *scan, *nb;
 227   const scan_order *so;
 228   const int ref = is_inter_block(mbmi);
 229   unsigned int (*const counts)[COEFF_CONTEXTS][ENTROPY_TOKENS] =
 230       cpi->coef_counts[tx_size][type][ref];
 231   vp9_prob (*const coef_probs)[COEFF_CONTEXTS][UNCONSTRAINED_NODES] =
 232       cpi->common.fc.coef_probs[tx_size][type][ref];
 233   unsigned int (*const eob_branch)[COEFF_CONTEXTS] =
 234       cpi->common.counts.eob_branch[tx_size][type][ref];
 235
 236   const uint8_t *const band = get_band_translate(tx_size);
 237   const int seg_eob = get_tx_eob(&cpi->common.seg, segment_id, tx_size);
 238
 239   int aoff, loff;
 240   txfrm_block_to_raster_xy(plane_bsize, tx_size, block, &aoff, &loff);
 241
 242   pt = get_entropy_context(tx_size, pd->above_context + aoff,
 243                            pd->left_context + loff);
 244   so = get_scan(xd, tx_size, type, block);
 245   scan = so->scan;
 246   nb = so->neighbors;
 247   c = 0;
 248   while (c < eob) {
 249     int v = 0;
 250     int skip_eob = 0;
 251     v = qcoeff[scan[c]];
 252
 253     while (!v) {
 254       add_token_no_extra(&t, coef_probs[band[c]][pt], ZERO_TOKEN, skip_eob,
 255                          counts[band[c]][pt]);
 256       eob_branch[band[c]][pt] += !skip_eob;
 257
 258       skip_eob = 1;
 259       token_cache[scan[c]] = 0;
 260       ++c;
 261       pt = get_coef_context(nb, token_cache, c);
 262       v = qcoeff[scan[c]];
 263     }
 264
 265     add_token(&t, coef_probs[band[c]][pt],
 266               vp9_dct_value_tokens_ptr[v].extra,
 267               (uint8_t)vp9_dct_value_tokens_ptr[v].token,
 268               (uint8_t)skip_eob,
 269               counts[band[c]][pt]);
 270     eob_branch[band[c]][pt] += !skip_eob;
 271
 272     token_cache[scan[c]] =
 273         vp9_pt_energy_class[vp9_dct_value_tokens_ptr[v].token];
 274     ++c;
 275     pt = get_coef_context(nb, token_cache, c);
 276   }
 277   if (c < seg_eob) {
 278     add_token_no_extra(&t, coef_probs[band[c]][pt], EOB_TOKEN, 0,
 279                        counts[band[c]][pt]);
 280     ++eob_branch[band[c]][pt];
 281   }
 282
 283   *tp = t;
 284
 285   vp9_set_contexts(xd, pd, plane_bsize, tx_size, c > 0, aoff, loff);
 286 }
 287
 288 struct is_skippable_args {
 289   MACROBLOCK *x;
 290   int *skippable;
 291 };
 292
 293 static void is_skippable(int plane, int block,
 294                          BLOCK_SIZE plane_bsize, TX_SIZE tx_size,
 295                          void *argv) {
 296   struct is_skippable_args *args = argv;
 297   args->skippable[0] &= (!args->x->plane[plane].eobs[block]);
 298 }
 299
 300 int vp9_is_skippable_in_plane(MACROBLOCK *x, BLOCK_SIZE bsize, int plane) {
 301   int result = 1;
 302   struct is_skippable_args args = {x, &result};
 303   vp9_foreach_transformed_block_in_plane(&x->e_mbd, bsize, plane, is_skippable,
 304                                          &args);
 305   return result;
 306 }
 307
 308 void vp9_tokenize_sb(VP9_COMP *cpi, TOKENEXTRA **t, int dry_run,
 309                      BLOCK_SIZE bsize) {
 310   VP9_COMMON *const cm = &cpi->common;
 311   MACROBLOCKD *const xd = &cpi->mb.e_mbd;
 312   MB_MODE_INFO *const mbmi = &xd->mi[0]->mbmi;
 313   TOKENEXTRA *t_backup = *t;
 314   const int ctx = vp9_get_skip_context(xd);
 315   const int skip_inc = !vp9_segfeature_active(&cm->seg, mbmi->segment_id,
 316                                               SEG_LVL_SKIP);
 317   struct tokenize_b_args arg = {cpi, xd, t};
 318   if (mbmi->skip) {
 319     if (!dry_run)
 320       cm->counts.skip[ctx][1] += skip_inc;
 321     reset_skip_context(xd, bsize);
 322     if (dry_run)
 323       *t = t_backup;
 324     return;
 325   }
 326
 327   if (!dry_run) {
 328     cm->counts.skip[ctx][0] += skip_inc;
 329     vp9_foreach_transformed_block(xd, bsize, tokenize_b, &arg);
 330   } else {
 331     vp9_foreach_transformed_block(xd, bsize, set_entropy_context_b, &arg);
 332     *t = t_backup;
 333   }
 334 }