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