vp9_tokenize.c 10.1 KB
Newer Older
John Koleszar's avatar
John Koleszar committed
1
/*
2
 *  Copyright (c) 2010 The WebM project authors. All Rights Reserved.
John Koleszar's avatar
John Koleszar committed
3
 *
4
 *  Use of this source code is governed by a BSD-style license
5 6
 *  that can be found in the LICENSE file in the root of the source
 *  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.
John Koleszar's avatar
John Koleszar committed
9 10 11 12 13 14 15
 */


#include <math.h>
#include <stdio.h>
#include <string.h>
#include <assert.h>
16 17
#include "vp9/encoder/vp9_onyx_int.h"
#include "vp9/encoder/vp9_tokenize.h"
John Koleszar's avatar
John Koleszar committed
18 19
#include "vpx_mem/vpx_mem.h"

20 21 22
#include "vp9/common/vp9_pred_common.h"
#include "vp9/common/vp9_seg_common.h"
#include "vp9/common/vp9_entropy.h"
23

John Koleszar's avatar
John Koleszar committed
24
static TOKENVALUE dct_value_tokens[DCT_MAX_VALUE * 2];
25
const TOKENVALUE *vp9_dct_value_tokens_ptr;
John Koleszar's avatar
John Koleszar committed
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 31 32 33 34 35 36 37 38 39 40 41
const vp9_tree_index vp9_coef_tree[TREE_SIZE(ENTROPY_TOKENS)] = {
  -EOB_TOKEN, 2,                       // 0  = EOB
  -ZERO_TOKEN, 4,                      // 1  = ZERO
  -ONE_TOKEN, 6,                       // 2  = ONE
  8, 12,                               // 3  = LOW_VAL
  -TWO_TOKEN, 10,                      // 4  = TWO
  -THREE_TOKEN, -FOUR_TOKEN,           // 5  = THREE
  14, 16,                              // 6  = HIGH_LOW
  -CATEGORY1_TOKEN, -CATEGORY2_TOKEN,  // 7  = CAT_ONE
  18, 20,                              // 8  = CAT_THREEFOUR
  -CATEGORY3_TOKEN, -CATEGORY4_TOKEN,  // 9  = CAT_THREE
  -CATEGORY5_TOKEN, -CATEGORY6_TOKEN   // 10 = CAT_FIVE
42 43 44
};

// Unconstrained Node Tree
45 46 47 48 49 50 51 52 53
const vp9_tree_index vp9_coef_con_tree[TREE_SIZE(ENTROPY_TOKENS)] = {
  2, 6,                                // 0 = LOW_VAL
  -TWO_TOKEN, 4,                       // 1 = TWO
  -THREE_TOKEN, -FOUR_TOKEN,           // 2 = THREE
  8, 10,                               // 3 = HIGH_LOW
  -CATEGORY1_TOKEN, -CATEGORY2_TOKEN,  // 4 = CAT_ONE
  12, 14,                              // 5 = CAT_THREEFOUR
  -CATEGORY3_TOKEN, -CATEGORY4_TOKEN,  // 6 = CAT_THREE
  -CATEGORY5_TOKEN, -CATEGORY6_TOKEN   // 7 = CAT_FIVE
54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86
};

static const vp9_prob Pcat1[] = { 159};
static const vp9_prob Pcat2[] = { 165, 145};
static const vp9_prob Pcat3[] = { 173, 148, 140};
static const vp9_prob Pcat4[] = { 176, 155, 140, 135};
static const vp9_prob Pcat5[] = { 180, 157, 141, 134, 130};
static const vp9_prob Pcat6[] = {
  254, 254, 254, 252, 249, 243, 230, 196, 177, 153, 140, 133, 130, 129
};

static vp9_tree_index cat1[2], cat2[4], cat3[6], cat4[8], cat5[10], cat6[28];

static void init_bit_tree(vp9_tree_index *p, int n) {
  int i = 0;

  while (++i < n) {
    p[0] = p[1] = i << 1;
    p += 2;
  }

  p[0] = p[1] = 0;
}

static void init_bit_trees() {
  init_bit_tree(cat1, 1);
  init_bit_tree(cat2, 2);
  init_bit_tree(cat3, 3);
  init_bit_tree(cat4, 4);
  init_bit_tree(cat5, 5);
  init_bit_tree(cat6, 14);
}

87
const vp9_extra_bit vp9_extra_bits[ENTROPY_TOKENS] = {
88 89 90 91 92
  {0, 0, 0, 0},           // ZERO_TOKEN
  {0, 0, 0, 1},           // ONE_TOKEN
  {0, 0, 0, 2},           // TWO_TOKEN
  {0, 0, 0, 3},           // THREE_TOKEN
  {0, 0, 0, 4},           // FOUR_TOKEN
93 94 95 96 97 98 99
  {cat1, Pcat1, 1, 5},    // CATEGORY1_TOKEN
  {cat2, Pcat2, 2, 7},    // CATEGORY2_TOKEN
  {cat3, Pcat3, 3, 11},   // CATEGORY3_TOKEN
  {cat4, Pcat4, 4, 19},   // CATEGORY4_TOKEN
  {cat5, Pcat5, 5, 35},   // CATEGORY5_TOKEN
  {cat6, Pcat6, 14, 67},  // CATEGORY6_TOKEN
  {0, 0, 0, 0}            // EOB_TOKEN
100 101
};

102
struct vp9_token vp9_coef_encodings[ENTROPY_TOKENS];
103 104 105 106 107 108

void vp9_coef_tree_initialize() {
  init_bit_trees();
  vp9_tokens_from_tree(vp9_coef_encodings, vp9_coef_tree);
}

John Koleszar's avatar
John Koleszar committed
109 110
static void fill_value_tokens() {
  TOKENVALUE *const t = dct_value_tokens + DCT_MAX_VALUE;
111
  const vp9_extra_bit *const e = vp9_extra_bits;
John Koleszar's avatar
John Koleszar committed
112

John Koleszar's avatar
John Koleszar committed
113 114
  int i = -DCT_MAX_VALUE;
  int sign = 1;
John Koleszar's avatar
John Koleszar committed
115

John Koleszar's avatar
John Koleszar committed
116 117 118
  do {
    if (!i)
      sign = 0;
John Koleszar's avatar
John Koleszar committed
119

John Koleszar's avatar
John Koleszar committed
120 121 122
    {
      const int a = sign ? -i : i;
      int eb = sign;
John Koleszar's avatar
John Koleszar committed
123

John Koleszar's avatar
John Koleszar committed
124 125
      if (a > 4) {
        int j = 4;
John Koleszar's avatar
John Koleszar committed
126

John Koleszar's avatar
John Koleszar committed
127
        while (++j < 11  &&  e[j].base_val <= a) {}
John Koleszar's avatar
John Koleszar committed
128

129
        t[i].token = --j;
John Koleszar's avatar
John Koleszar committed
130
        eb |= (a - e[j].base_val) << 1;
131
      } else {
132
        t[i].token = a;
133
      }
134
      t[i].extra = eb;
John Koleszar's avatar
John Koleszar committed
135
    }
John Koleszar's avatar
John Koleszar committed
136

John Koleszar's avatar
John Koleszar committed
137 138 139
    // initialize the cost for extra bits for all possible coefficient value.
    {
      int cost = 0;
140
      const vp9_extra_bit *p = &vp9_extra_bits[t[i].token];
John Koleszar's avatar
John Koleszar committed
141

John Koleszar's avatar
John Koleszar committed
142
      if (p->base_val) {
143
        const int extra = t[i].extra;
144
        const int length = p->len;
John Koleszar's avatar
John Koleszar committed
145

146 147
        if (length)
          cost += treed_cost(p->tree, p->prob, extra >> 1, length);
John Koleszar's avatar
John Koleszar committed
148

149
        cost += vp9_cost_bit(vp9_prob_half, extra & 1); /* sign */
John Koleszar's avatar
John Koleszar committed
150 151
        dct_value_cost[i + DCT_MAX_VALUE] = cost;
      }
John Koleszar's avatar
John Koleszar committed
152
    }
John Koleszar's avatar
John Koleszar committed
153 154
  } while (++i < DCT_MAX_VALUE);

155
  vp9_dct_value_tokens_ptr = dct_value_tokens + DCT_MAX_VALUE;
156
  vp9_dct_value_cost_ptr = dct_value_cost + DCT_MAX_VALUE;
John Koleszar's avatar
John Koleszar committed
157
}
158

159 160 161 162 163
struct tokenize_b_args {
  VP9_COMP *cpi;
  MACROBLOCKD *xd;
  TOKENEXTRA **tp;
  TX_SIZE tx_size;
164
  uint8_t *token_cache;
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 174
  int aoff, loff;
  txfrm_block_to_raster_xy(plane_bsize, tx_size, block, &aoff, &loff);
175
  set_contexts(xd, pd, plane_bsize, tx_size, p->eobs[block] > 0, aoff, loff);
176 177
}

Jim Bankoski's avatar
Jim Bankoski committed
178 179 180 181 182 183 184 185 186 187 188 189
static INLINE void add_token(TOKENEXTRA **t, const vp9_prob *context_tree,
                             int16_t extra, uint8_t token,
                             uint8_t skip_eob_node,
                             unsigned int *counts) {
  (*t)->token = token;
  (*t)->extra = extra;
  (*t)->context_tree = context_tree;
  (*t)->skip_eob_node = skip_eob_node;
  (*t)++;
  ++counts[token];
}

190
static void tokenize_b(int plane, int block, BLOCK_SIZE plane_bsize,
191
                       TX_SIZE tx_size, void *arg) {
192 193 194 195
  struct tokenize_b_args* const args = arg;
  VP9_COMP *cpi = args->cpi;
  MACROBLOCKD *xd = args->xd;
  TOKENEXTRA **tp = args->tp;
196
  uint8_t *token_cache = args->token_cache;
197
  struct macroblock_plane *p = &cpi->mb.plane[plane];
198
  struct macroblockd_plane *pd = &xd->plane[plane];
199
  MB_MODE_INFO *mbmi = &xd->mi_8x8[0]->mbmi;
Daniel Kang's avatar
Daniel Kang committed
200
  int pt; /* near block/prev token context index */
Jim Bankoski's avatar
Jim Bankoski committed
201
  int c = 0;
Daniel Kang's avatar
Daniel Kang committed
202
  TOKENEXTRA *t = *tp;        /* store tokens starting here */
Jim Bankoski's avatar
Jim Bankoski committed
203
  int eob = p->eobs[block];
204
  const PLANE_TYPE type = pd->plane_type;
205
  const int16_t *qcoeff_ptr = BLOCK_OFFSET(p->qcoeff, block);
206
  const int segment_id = mbmi->segment_id;
207
  const int16_t *scan, *nb;
208
  const scan_order *so;
209 210
  vp9_coeff_count *const counts = cpi->coef_counts[tx_size];
  vp9_coeff_probs_model *const coef_probs = cpi->common.fc.coef_probs[tx_size];
211
  const int ref = is_inter_block(mbmi);
Jim Bankoski's avatar
Jim Bankoski committed
212
  const uint8_t *const band = get_band_translate(tx_size);
213
  const int seg_eob = get_tx_eob(&cpi->common.seg, segment_id, tx_size);
214

215 216 217
  int aoff, loff;
  txfrm_block_to_raster_xy(plane_bsize, tx_size, block, &aoff, &loff);

218
  pt = get_entropy_context(tx_size, pd->above_context + aoff,
Jim Bankoski's avatar
Jim Bankoski committed
219
                           pd->left_context + loff);
220 221 222
  so = get_scan(xd, tx_size, type, block);
  scan = so->scan;
  nb = so->neighbors;
223
  c = 0;
Jim Bankoski's avatar
Jim Bankoski committed
224
  while (c < eob) {
225
    int v = 0;
Jim Bankoski's avatar
Jim Bankoski committed
226 227 228 229 230 231
    int skip_eob = 0;
    v = qcoeff_ptr[scan[c]];

    while (!v) {
      add_token(&t, coef_probs[type][ref][band[c]][pt], 0, ZERO_TOKEN, skip_eob,
                counts[type][ref][band[c]][pt]);
John Koleszar's avatar
John Koleszar committed
232

Jim Bankoski's avatar
Jim Bankoski committed
233 234
      cpi->common.counts.eob_branch[tx_size][type][ref][band[c]][pt] +=
          !skip_eob;
235

Jim Bankoski's avatar
Jim Bankoski committed
236 237 238 239 240 241 242 243 244 245
      skip_eob = 1;
      token_cache[scan[c]] = 0;
      ++c;
      pt = get_coef_context(nb, token_cache, c);
      v = qcoeff_ptr[scan[c]];
    }
    add_token(&t, coef_probs[type][ref][band[c]][pt],
              vp9_dct_value_tokens_ptr[v].extra,
              vp9_dct_value_tokens_ptr[v].token, skip_eob,
              counts[type][ref][band[c]][pt]);
246

Jim Bankoski's avatar
Jim Bankoski committed
247
    cpi->common.counts.eob_branch[tx_size][type][ref][band[c]][pt] += !skip_eob;
248

Jim Bankoski's avatar
Jim Bankoski committed
249 250 251 252 253 254 255 256 257 258
    token_cache[scan[c]] =
        vp9_pt_energy_class[vp9_dct_value_tokens_ptr[v].token];
    ++c;
    pt = get_coef_context(nb, token_cache, c);
  }
  if (c < seg_eob) {
    add_token(&t, coef_probs[type][ref][band[c]][pt], 0, EOB_TOKEN, 0,
              counts[type][ref][band[c]][pt]);
    ++cpi->common.counts.eob_branch[tx_size][type][ref][band[c]][pt];
  }
259 260

  *tp = t;
261 262

  set_contexts(xd, pd, plane_bsize, tx_size, c > 0, aoff, loff);
John Koleszar's avatar
John Koleszar committed
263 264
}

265
struct is_skippable_args {
266
  MACROBLOCK *x;
267 268
  int *skippable;
};
269

270
static void is_skippable(int plane, int block,
271
                         BLOCK_SIZE plane_bsize, TX_SIZE tx_size,
272
                         void *argv) {
273
  struct is_skippable_args *args = argv;
274
  args->skippable[0] &= (!args->x->plane[plane].eobs[block]);
Deb Mukherjee's avatar
Deb Mukherjee committed
275 276
}

277
static int sb_is_skippable(MACROBLOCK *x, BLOCK_SIZE bsize) {
278
  int result = 1;
279 280
  struct is_skippable_args args = {x, &result};
  foreach_transformed_block(&x->e_mbd, bsize, is_skippable, &args);
281
  return result;
282 283
}

284
int vp9_is_skippable_in_plane(MACROBLOCK *x, BLOCK_SIZE bsize, int plane) {
285
  int result = 1;
286 287 288
  struct is_skippable_args args = {x, &result};
  foreach_transformed_block_in_plane(&x->e_mbd, bsize, plane, is_skippable,
                                     &args);
289
  return result;
290 291
}

292
void vp9_tokenize_sb(VP9_COMP *cpi, TOKENEXTRA **t, int dry_run,
293
                     BLOCK_SIZE bsize) {
294 295
  VP9_COMMON *const cm = &cpi->common;
  MACROBLOCKD *const xd = &cpi->mb.e_mbd;
296
  MB_MODE_INFO *const mbmi = &xd->mi_8x8[0]->mbmi;
297
  TOKENEXTRA *t_backup = *t;
298
  const int ctx = vp9_get_skip_context(xd);
299
  const int skip_inc = !vp9_segfeature_active(&cm->seg, mbmi->segment_id,
300
                                              SEG_LVL_SKIP);
301
  struct tokenize_b_args arg = {cpi, xd, t, mbmi->tx_size, cpi->mb.token_cache};
Paul Wilkins's avatar
Paul Wilkins committed
302
  if (mbmi->skip_coeff) {
303
    if (!dry_run)
304
      cm->counts.mbskip[ctx][1] += skip_inc;
305
    reset_skip_context(xd, bsize);
306 307 308 309 310
    if (dry_run)
      *t = t_backup;
    return;
  }

311
  if (!dry_run) {
312
    cm->counts.mbskip[ctx][0] += skip_inc;
313 314 315
    foreach_transformed_block(xd, bsize, tokenize_b, &arg);
  } else {
    foreach_transformed_block(xd, bsize, set_entropy_context_b, &arg);
316
    *t = t_backup;
317
  }
318 319
}

320
void vp9_tokenize_initialize() {
John Koleszar's avatar
John Koleszar committed
321
  fill_value_tokens();
John Koleszar's avatar
John Koleszar committed
322
}