vp9_tokenize.c 33 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
/* Global event counters used for accumulating statistics across several
25
   compressions, then generating vp9_context.c = initial stats. */
John Koleszar's avatar
John Koleszar committed
26 27

#ifdef ENTROPY_STATS
28
INT64 context_counters[BLOCK_TYPES] [COEF_BANDS] [PREV_COEF_CONTEXTS] [MAX_ENTROPY_TOKENS];
29 30
INT64 hybrid_context_counters[BLOCK_TYPES] [COEF_BANDS] [PREV_COEF_CONTEXTS] [MAX_ENTROPY_TOKENS];

31
INT64 context_counters_8x8[BLOCK_TYPES_8X8] [COEF_BANDS] [PREV_COEF_CONTEXTS] [MAX_ENTROPY_TOKENS];
32 33
INT64 hybrid_context_counters_8x8[BLOCK_TYPES_8X8] [COEF_BANDS] [PREV_COEF_CONTEXTS] [MAX_ENTROPY_TOKENS];

Daniel Kang's avatar
Daniel Kang committed
34
INT64 context_counters_16x16[BLOCK_TYPES_16X16] [COEF_BANDS] [PREV_COEF_CONTEXTS] [MAX_ENTROPY_TOKENS];
35 36
INT64 hybrid_context_counters_16x16[BLOCK_TYPES_16X16] [COEF_BANDS] [PREV_COEF_CONTEXTS] [MAX_ENTROPY_TOKENS];

Daniel Kang's avatar
Daniel Kang committed
37 38
extern unsigned int tree_update_hist[BLOCK_TYPES][COEF_BANDS]
                    [PREV_COEF_CONTEXTS][ENTROPY_NODES][2];
39 40
extern unsigned int hybrid_tree_update_hist[BLOCK_TYPES][COEF_BANDS]
                    [PREV_COEF_CONTEXTS][ENTROPY_NODES][2];
Daniel Kang's avatar
Daniel Kang committed
41 42
extern unsigned int tree_update_hist_8x8[BLOCK_TYPES_8X8][COEF_BANDS]
                    [PREV_COEF_CONTEXTS][ENTROPY_NODES] [2];
43 44
extern unsigned int hybrid_tree_update_hist_8x8[BLOCK_TYPES_8X8][COEF_BANDS]
                    [PREV_COEF_CONTEXTS][ENTROPY_NODES] [2];
Daniel Kang's avatar
Daniel Kang committed
45 46
extern unsigned int tree_update_hist_16x16[BLOCK_TYPES_16X16][COEF_BANDS]
                    [PREV_COEF_CONTEXTS][ENTROPY_NODES] [2];
47 48
extern unsigned int hybrid_tree_update_hist_16x16[BLOCK_TYPES_16X16][COEF_BANDS]
                    [PREV_COEF_CONTEXTS][ENTROPY_NODES] [2];
49 50
#endif  /* ENTROPY_STATS */

John Koleszar's avatar
John Koleszar committed
51
static TOKENVALUE dct_value_tokens[DCT_MAX_VALUE * 2];
52
const TOKENVALUE *vp9_dct_value_tokens_ptr;
John Koleszar's avatar
John Koleszar committed
53
static int dct_value_cost[DCT_MAX_VALUE * 2];
54
const int *vp9_dct_value_cost_ptr;
55

John Koleszar's avatar
John Koleszar committed
56
static void fill_value_tokens() {
John Koleszar's avatar
John Koleszar committed
57

John Koleszar's avatar
John Koleszar committed
58
  TOKENVALUE *const t = dct_value_tokens + DCT_MAX_VALUE;
59
  vp9_extra_bit_struct *const e = vp9_extra_bits;
John Koleszar's avatar
John Koleszar committed
60

John Koleszar's avatar
John Koleszar committed
61 62
  int i = -DCT_MAX_VALUE;
  int sign = 1;
John Koleszar's avatar
John Koleszar committed
63

John Koleszar's avatar
John Koleszar committed
64 65 66
  do {
    if (!i)
      sign = 0;
John Koleszar's avatar
John Koleszar committed
67

John Koleszar's avatar
John Koleszar committed
68 69 70
    {
      const int a = sign ? -i : i;
      int eb = sign;
John Koleszar's avatar
John Koleszar committed
71

John Koleszar's avatar
John Koleszar committed
72 73
      if (a > 4) {
        int j = 4;
John Koleszar's avatar
John Koleszar committed
74

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

John Koleszar's avatar
John Koleszar committed
77 78 79 80
        t[i].Token = --j;
        eb |= (a - e[j].base_val) << 1;
      } else
        t[i].Token = a;
John Koleszar's avatar
John Koleszar committed
81

John Koleszar's avatar
John Koleszar committed
82 83
      t[i].Extra = eb;
    }
John Koleszar's avatar
John Koleszar committed
84

John Koleszar's avatar
John Koleszar committed
85 86 87
    // initialize the cost for extra bits for all possible coefficient value.
    {
      int cost = 0;
88
      vp9_extra_bit_struct *p = vp9_extra_bits + t[i].Token;
John Koleszar's avatar
John Koleszar committed
89

John Koleszar's avatar
John Koleszar committed
90 91 92
      if (p->base_val) {
        const int extra = t[i].Extra;
        const int Length = p->Len;
John Koleszar's avatar
John Koleszar committed
93

John Koleszar's avatar
John Koleszar committed
94
        if (Length)
95
          cost += treed_cost(p->tree, p->prob, extra >> 1, Length);
John Koleszar's avatar
John Koleszar committed
96

97
        cost += vp9_cost_bit(vp9_prob_half, extra & 1); /* sign */
John Koleszar's avatar
John Koleszar committed
98 99
        dct_value_cost[i + DCT_MAX_VALUE] = cost;
      }
John Koleszar's avatar
John Koleszar committed
100 101 102

    }

John Koleszar's avatar
John Koleszar committed
103 104
  } while (++i < DCT_MAX_VALUE);

105 106
  vp9_dct_value_tokens_ptr = dct_value_tokens + DCT_MAX_VALUE;
  vp9_dct_value_cost_ptr   = dct_value_cost + DCT_MAX_VALUE;
John Koleszar's avatar
John Koleszar committed
107 108
}

109
static void tokenize_b(VP9_COMP *cpi,
110 111 112 113 114 115 116 117
                       MACROBLOCKD *xd,
                       const BLOCKD * const b,
                       TOKENEXTRA **tp,
                       PLANE_TYPE type,
                       ENTROPY_CONTEXT *a,
                       ENTROPY_CONTEXT *l,
                       TX_SIZE tx_size,
                       int dry_run) {
Daniel Kang's avatar
Daniel Kang committed
118
  int pt; /* near block/prev token context index */
119
  int c = (type == PLANE_TYPE_Y_NO_DC) ? 1 : 0;
120
  int eob = b->eob;     /* one beyond last nonzero coeff */
Daniel Kang's avatar
Daniel Kang committed
121 122
  TOKENEXTRA *t = *tp;        /* store tokens starting here */
  const short *qcoeff_ptr = b->qcoeff;
123
  int seg_eob;
Daniel Kang's avatar
Daniel Kang committed
124
  int segment_id = xd->mode_info_context->mbmi.segment_id;
125 126
  const int *bands, *scan;
  unsigned int (*counts)[COEF_BANDS][PREV_COEF_CONTEXTS][MAX_ENTROPY_TOKENS];
127
  vp9_prob (*probs)[COEF_BANDS][PREV_COEF_CONTEXTS][ENTROPY_NODES];
128 129
  const TX_TYPE tx_type = (type == PLANE_TYPE_Y_WITH_DC) ?
                          get_tx_type(xd, b) : DCT_DCT;
Daniel Kang's avatar
Daniel Kang committed
130

131
  VP9_COMBINEENTROPYCONTEXTS(pt, *a, *l);
132 133 134 135
  switch (tx_size) {
    default:
    case TX_4X4:
      seg_eob = 16;
136 137
      bands = vp9_coef_bands;
      scan = vp9_default_zig_zag1d;
138 139 140 141
      if (tx_type != DCT_DCT) {
        counts = cpi->hybrid_coef_counts;
        probs = cpi->common.fc.hybrid_coef_probs;
        if (tx_type == ADST_DCT) {
142
          scan = vp9_row_scan;
143
        } else if (tx_type == DCT_ADST) {
144
          scan = vp9_col_scan;
145 146 147 148 149 150 151 152 153
        }
      } else {
        counts = cpi->coef_counts;
        probs = cpi->common.fc.coef_probs;
      }
      break;
    case TX_8X8:
      if (type == PLANE_TYPE_Y2) {
        seg_eob = 4;
154 155
        bands = vp9_coef_bands;
        scan = vp9_default_zig_zag1d;
156 157
      } else {
        seg_eob = 64;
158 159
        bands = vp9_coef_bands_8x8;
        scan = vp9_default_zig_zag1d_8x8;
160 161 162 163 164 165 166 167 168 169 170
      }
      if (tx_type != DCT_DCT) {
        counts = cpi->hybrid_coef_counts_8x8;
        probs = cpi->common.fc.hybrid_coef_probs_8x8;
      } else {
        counts = cpi->coef_counts_8x8;
        probs = cpi->common.fc.coef_probs_8x8;
      }
      break;
    case TX_16X16:
      seg_eob = 256;
171 172
      bands = vp9_coef_bands_16x16;
      scan = vp9_default_zig_zag1d_16x16;
173 174 175 176 177 178 179
      if (tx_type != DCT_DCT) {
        counts = cpi->hybrid_coef_counts_16x16;
        probs = cpi->common.fc.hybrid_coef_probs_16x16;
      } else {
        counts = cpi->coef_counts_16x16;
        probs = cpi->common.fc.coef_probs_16x16;
      }
180 181 182 183 184 185 186 187 188 189 190 191 192 193 194
#if CONFIG_SUPERBLOCKS && CONFIG_TX32X32
      if (type == PLANE_TYPE_UV) {
        int uv_idx = (((int) (b - xd->block)) - 16) >> 2;
        qcoeff_ptr = xd->sb_coeff_data.qcoeff + 1024 + 256 * uv_idx;
      }
#endif
      break;
#if CONFIG_TX32X32 && CONFIG_SUPERBLOCKS
    case TX_32X32:
      seg_eob = 1024;
      bands = vp9_coef_bands_32x32;
      scan = vp9_default_zig_zag1d_32x32;
      counts = cpi->coef_counts_32x32;
      probs = cpi->common.fc.coef_probs_32x32;
      qcoeff_ptr = xd->sb_coeff_data.qcoeff;
195
      break;
196
#endif
John Koleszar's avatar
John Koleszar committed
197 198
  }

199 200
  if (vp9_segfeature_active(xd, segment_id, SEG_LVL_EOB))
    seg_eob = vp9_get_segdata(xd, segment_id, SEG_LVL_EOB);
John Koleszar's avatar
John Koleszar committed
201

202
  do {
203
    const int band = bands[c];
204 205 206
    int token;

    if (c < eob) {
207
      const int rc = scan[c];
208
      const int v = qcoeff_ptr[rc];
John Koleszar's avatar
John Koleszar committed
209

210 211
      assert(-DCT_MAX_VALUE <= v  &&  v < DCT_MAX_VALUE);

212 213
      t->Extra = vp9_dct_value_tokens_ptr[v].Extra;
      token    = vp9_dct_value_tokens_ptr[v].Token;
214 215 216
    } else {
      token = DCT_EOB_TOKEN;
    }
John Koleszar's avatar
John Koleszar committed
217 218

    t->Token = token;
219 220 221
    t->context_tree = probs[type][band][pt];
    t->skip_eob_node = (pt == 0) && ((band > 0 && type != PLANE_TYPE_Y_NO_DC) ||
                                     (band > 1 && type == PLANE_TYPE_Y_NO_DC));
222
    assert(vp9_coef_encodings[t->Token].Len - t->skip_eob_node > 0);
223
    if (!dry_run) {
224
      ++counts[type][band][pt][token];
225
    }
226
    pt = vp9_prev_token_class[token];
227
    ++t;
228 229 230
  } while (c < eob && ++c < seg_eob);

  *tp = t;
231
  *a = *l = (c > !type); /* 0 <-> all coeff data is zero */
John Koleszar's avatar
John Koleszar committed
232 233
}

234
int vp9_mby_is_skippable_4x4(MACROBLOCKD *xd, int has_2nd_order) {
John Koleszar's avatar
John Koleszar committed
235 236
  int skip = 1;
  int i = 0;
237

238
  if (has_2nd_order) {
John Koleszar's avatar
John Koleszar committed
239
    for (i = 0; i < 16; i++)
Paul Wilkins's avatar
Paul Wilkins committed
240 241
      skip &= (xd->block[i].eob < 2);
    skip &= (!xd->block[24].eob);
John Koleszar's avatar
John Koleszar committed
242 243
  } else {
    for (i = 0; i < 16; i++)
Paul Wilkins's avatar
Paul Wilkins committed
244
      skip &= (!xd->block[i].eob);
John Koleszar's avatar
John Koleszar committed
245 246
  }
  return skip;
247
}
248

249
int vp9_mbuv_is_skippable_4x4(MACROBLOCKD *xd) {
John Koleszar's avatar
John Koleszar committed
250 251
  int skip = 1;
  int i;
252

John Koleszar's avatar
John Koleszar committed
253
  for (i = 16; i < 24; i++)
Paul Wilkins's avatar
Paul Wilkins committed
254
    skip &= (!xd->block[i].eob);
John Koleszar's avatar
John Koleszar committed
255
  return skip;
256 257
}

258 259
static int mb_is_skippable_4x4(MACROBLOCKD *xd, int has_2nd_order) {
  return (vp9_mby_is_skippable_4x4(xd, has_2nd_order) &
260
          vp9_mbuv_is_skippable_4x4(xd));
261
}
Yaowu Xu's avatar
Yaowu Xu committed
262

263
int vp9_mby_is_skippable_8x8(MACROBLOCKD *xd, int has_2nd_order) {
John Koleszar's avatar
John Koleszar committed
264 265
  int skip = 1;
  int i = 0;
266

267
  if (has_2nd_order) {
Deb Mukherjee's avatar
Deb Mukherjee committed
268 269 270 271 272 273 274
    for (i = 0; i < 16; i += 4)
      skip &= (xd->block[i].eob < 2);
    skip &= (!xd->block[24].eob);
  } else {
    for (i = 0; i < 16; i += 4)
      skip &= (!xd->block[i].eob);
  }
John Koleszar's avatar
John Koleszar committed
275
  return skip;
276
}
277

278
int vp9_mbuv_is_skippable_8x8(MACROBLOCKD *xd) {
Paul Wilkins's avatar
Paul Wilkins committed
279
  return (!xd->block[16].eob) & (!xd->block[20].eob);
280
}
281

282 283
static int mb_is_skippable_8x8(MACROBLOCKD *xd, int has_2nd_order) {
  return (vp9_mby_is_skippable_8x8(xd, has_2nd_order) &
284
          vp9_mbuv_is_skippable_8x8(xd));
Deb Mukherjee's avatar
Deb Mukherjee committed
285 286
}

287 288
static int mb_is_skippable_8x8_4x4uv(MACROBLOCKD *xd, int has_2nd_order) {
  return (vp9_mby_is_skippable_8x8(xd, has_2nd_order) &
289
          vp9_mbuv_is_skippable_4x4(xd));
290
}
Yaowu Xu's avatar
Yaowu Xu committed
291

292
int vp9_mby_is_skippable_16x16(MACROBLOCKD *xd) {
Daniel Kang's avatar
Daniel Kang committed
293
  int skip = 1;
Paul Wilkins's avatar
Paul Wilkins committed
294
  skip &= !xd->block[0].eob;
Daniel Kang's avatar
Daniel Kang committed
295 296 297
  return skip;
}

298 299
static int mb_is_skippable_16x16(MACROBLOCKD *xd) {
  return (vp9_mby_is_skippable_16x16(xd) & vp9_mbuv_is_skippable_8x8(xd));
Daniel Kang's avatar
Daniel Kang committed
300
}
301

302 303 304 305 306 307 308 309 310 311 312 313 314 315 316 317 318 319 320 321 322 323 324 325 326 327 328 329 330 331 332 333 334 335 336 337 338 339 340 341 342 343 344 345 346 347 348 349 350 351 352 353 354 355 356 357 358 359 360 361 362 363 364 365 366 367 368 369 370 371 372 373 374
#if CONFIG_TX32X32 && CONFIG_SUPERBLOCKS
int vp9_sby_is_skippable_32x32(MACROBLOCKD *xd) {
  int skip = 1;
  skip &= !xd->block[0].eob;
  return skip;
}

int vp9_sbuv_is_skippable_16x16(MACROBLOCKD *xd) {
  return (!xd->block[16].eob) & (!xd->block[20].eob);
}

static int sb_is_skippable_32x32(MACROBLOCKD *xd) {
  return vp9_sby_is_skippable_32x32(xd) &&
         vp9_sbuv_is_skippable_16x16(xd);
}

void vp9_tokenize_sb(VP9_COMP *cpi,
                     MACROBLOCKD *xd,
                     TOKENEXTRA **t,
                     int dry_run) {
  VP9_COMMON * const cm = &cpi->common;
  MB_MODE_INFO * const mbmi = &xd->mode_info_context->mbmi;
  TOKENEXTRA *t_backup = *t;
  ENTROPY_CONTEXT *A[2] = { (ENTROPY_CONTEXT *) (xd->above_context + 0),
                            (ENTROPY_CONTEXT *) (xd->above_context + 1), };
  ENTROPY_CONTEXT *L[2] = { (ENTROPY_CONTEXT *) (xd->left_context + 0),
                            (ENTROPY_CONTEXT *) (xd->left_context + 1), };
  const int mb_skip_context = vp9_get_pred_context(cm, xd, PRED_MBSKIP);
  const int segment_id = mbmi->segment_id;
  const int skip_inc =  !vp9_segfeature_active(xd, segment_id, SEG_LVL_EOB) ||
                        (vp9_get_segdata(xd, segment_id, SEG_LVL_EOB) != 0);
  int b;

  mbmi->mb_skip_coeff = sb_is_skippable_32x32(xd);

  if (mbmi->mb_skip_coeff) {
    if (!dry_run)
      cpi->skip_true_count[mb_skip_context] += skip_inc;
    if (!cm->mb_no_coeff_skip) {
      vp9_stuff_sb(cpi, xd, t, dry_run);
    } else {
      vp9_fix_contexts_sb(xd);
    }
    if (dry_run)
      *t = t_backup;
    return;
  }

  if (!dry_run)
    cpi->skip_false_count[mb_skip_context] += skip_inc;

  tokenize_b(cpi, xd, xd->block, t, PLANE_TYPE_Y_WITH_DC,
             A[0], L[0], TX_32X32, dry_run);
  A[0][1] = A[0][2] = A[0][3] = A[0][0];
  L[0][1] = L[0][2] = L[0][3] = L[0][0];

  for (b = 16; b < 24; b += 4) {
    tokenize_b(cpi, xd, xd->block + b, t, PLANE_TYPE_UV,
               A[0] + vp9_block2above_8x8[b], L[0] + vp9_block2left_8x8[b],
               TX_16X16, dry_run);
    A[0][vp9_block2above_8x8[b] + 1] = A[0][vp9_block2above_8x8[b]];
    L[0][vp9_block2left_8x8[b] + 1]  = L[0][vp9_block2left_8x8[b]];
  }
  vpx_memset(&A[0][8], 0, sizeof(A[0][8]));
  vpx_memset(&L[0][8], 0, sizeof(L[0][8]));
  vpx_memcpy(A[1], A[0], sizeof(ENTROPY_CONTEXT_PLANES));
  vpx_memcpy(L[1], L[0], sizeof(ENTROPY_CONTEXT_PLANES));

  if (dry_run)
    *t = t_backup;
}
#endif

375
void vp9_tokenize_mb(VP9_COMP *cpi,
Paul Wilkins's avatar
Paul Wilkins committed
376
                     MACROBLOCKD *xd,
377 378
                     TOKENEXTRA **t,
                     int dry_run) {
379
  PLANE_TYPE plane_type;
380
  int has_2nd_order;
John Koleszar's avatar
John Koleszar committed
381
  int b;
382
  int tx_size = xd->mode_info_context->mbmi.txfm_size;
Paul Wilkins's avatar
Paul Wilkins committed
383
  int mb_skip_context = vp9_get_pred_context(&cpi->common, xd, PRED_MBSKIP);
384
  TOKENEXTRA *t_backup = *t;
385 386
  ENTROPY_CONTEXT * A = (ENTROPY_CONTEXT *) xd->above_context;
  ENTROPY_CONTEXT * L = (ENTROPY_CONTEXT *) xd->left_context;
Paul Wilkins's avatar
Paul Wilkins committed
387

John Koleszar's avatar
John Koleszar committed
388 389 390 391
  // If the MB is going to be skipped because of a segment level flag
  // exclude this from the skip count stats used to calculate the
  // transmitted skip probability;
  int skip_inc;
Paul Wilkins's avatar
Paul Wilkins committed
392
  int segment_id = xd->mode_info_context->mbmi.segment_id;
393

394 395
  if (!vp9_segfeature_active(xd, segment_id, SEG_LVL_EOB) ||
      (vp9_get_segdata(xd, segment_id, SEG_LVL_EOB) != 0)) {
John Koleszar's avatar
John Koleszar committed
396 397 398
    skip_inc = 1;
  } else
    skip_inc = 0;
399

400
  has_2nd_order = get_2nd_order_usage(xd);
John Koleszar's avatar
John Koleszar committed
401

402
  switch (tx_size) {
Daniel Kang's avatar
Daniel Kang committed
403
    case TX_16X16:
Daniel Kang's avatar
Daniel Kang committed
404
      xd->mode_info_context->mbmi.mb_skip_coeff = mb_is_skippable_16x16(xd);
Daniel Kang's avatar
Daniel Kang committed
405 406
      break;
    case TX_8X8:
407 408
      if (xd->mode_info_context->mbmi.mode == I8X8_PRED ||
          xd->mode_info_context->mbmi.mode == SPLITMV)
409 410
        xd->mode_info_context->mbmi.mb_skip_coeff =
            mb_is_skippable_8x8_4x4uv(xd, 0);
Deb Mukherjee's avatar
Deb Mukherjee committed
411
      else
412 413
        xd->mode_info_context->mbmi.mb_skip_coeff =
            mb_is_skippable_8x8(xd, has_2nd_order);
Daniel Kang's avatar
Daniel Kang committed
414
      break;
Deb Mukherjee's avatar
Deb Mukherjee committed
415

Daniel Kang's avatar
Daniel Kang committed
416
    default:
417 418
      xd->mode_info_context->mbmi.mb_skip_coeff =
          mb_is_skippable_4x4(xd, has_2nd_order);
Daniel Kang's avatar
Daniel Kang committed
419 420
      break;
  }
421

Paul Wilkins's avatar
Paul Wilkins committed
422
  if (xd->mode_info_context->mbmi.mb_skip_coeff) {
423 424
    if (!dry_run)
      cpi->skip_true_count[mb_skip_context] += skip_inc;
John Koleszar's avatar
John Koleszar committed
425
    if (!cpi->common.mb_no_coeff_skip) {
426
      vp9_stuff_mb(cpi, xd, t, dry_run);
John Koleszar's avatar
John Koleszar committed
427
    } else {
428
      vp9_fix_contexts(xd);
John Koleszar's avatar
John Koleszar committed
429
    }
430 431
    if (dry_run)
      *t = t_backup;
John Koleszar's avatar
John Koleszar committed
432 433 434
    return;
  }

435 436
  if (!dry_run)
    cpi->skip_false_count[mb_skip_context] += skip_inc;
437

438
  if (has_2nd_order) {
439
    if (tx_size == TX_8X8) {
440
      tokenize_b(cpi, xd, xd->block + 24, t, PLANE_TYPE_Y2,
441
                 A + vp9_block2above_8x8[24], L + vp9_block2left_8x8[24],
442 443 444
                 TX_8X8, dry_run);
    } else {
      tokenize_b(cpi, xd, xd->block + 24, t, PLANE_TYPE_Y2,
445
                 A + vp9_block2above[24], L + vp9_block2left[24],
446 447
                 TX_4X4, dry_run);
    }
John Koleszar's avatar
John Koleszar committed
448

449
    plane_type = PLANE_TYPE_Y_NO_DC;
Yaowu Xu's avatar
Yaowu Xu committed
450 451 452
  } else {
    xd->above_context->y2 = 1;
    xd->left_context->y2 = 1;
453
    plane_type = PLANE_TYPE_Y_WITH_DC;
Yaowu Xu's avatar
Yaowu Xu committed
454
  }
John Koleszar's avatar
John Koleszar committed
455

456
  if (tx_size == TX_16X16) {
457 458
    tokenize_b(cpi, xd, xd->block, t, PLANE_TYPE_Y_WITH_DC,
               A, L, TX_16X16, dry_run);
459 460
    A[1] = A[2] = A[3] = A[0];
    L[1] = L[2] = L[3] = L[0];
461

Daniel Kang's avatar
Daniel Kang committed
462
    for (b = 16; b < 24; b += 4) {
463
      tokenize_b(cpi, xd, xd->block + b, t, PLANE_TYPE_UV,
464
                 A + vp9_block2above_8x8[b], L + vp9_block2left_8x8[b],
465
                 TX_8X8, dry_run);
466 467
      A[vp9_block2above_8x8[b] + 1] = A[vp9_block2above_8x8[b]];
      L[vp9_block2left_8x8[b] + 1]  = L[vp9_block2left_8x8[b]];
Daniel Kang's avatar
Daniel Kang committed
468
    }
469 470
    A[8] = 0;
    L[8] = 0;
471
  } else if (tx_size == TX_8X8) {
John Koleszar's avatar
John Koleszar committed
472
    for (b = 0; b < 16; b += 4) {
473
      tokenize_b(cpi, xd, xd->block + b, t, plane_type,
474
                 A + vp9_block2above_8x8[b], L + vp9_block2left_8x8[b],
475
                 TX_8X8, dry_run);
476 477
      A[vp9_block2above_8x8[b] + 1] = A[vp9_block2above_8x8[b]];
      L[vp9_block2left_8x8[b] + 1]  = L[vp9_block2left_8x8[b]];
John Koleszar's avatar
John Koleszar committed
478
    }
479 480
    if (xd->mode_info_context->mbmi.mode == I8X8_PRED ||
        xd->mode_info_context->mbmi.mode == SPLITMV) {
481 482
      for (b = 16; b < 24; b++) {
        tokenize_b(cpi, xd, xd->block + b, t, PLANE_TYPE_UV,
483
                   A + vp9_block2above[b], L + vp9_block2left[b],
484 485
                   TX_4X4, dry_run);
      }
486
    } else {
Deb Mukherjee's avatar
Deb Mukherjee committed
487
      for (b = 16; b < 24; b += 4) {
488
        tokenize_b(cpi, xd, xd->block + b, t, PLANE_TYPE_UV,
489
                   A + vp9_block2above_8x8[b], L + vp9_block2left_8x8[b],
490
                   TX_8X8, dry_run);
491 492
        A[vp9_block2above_8x8[b] + 1] = A[vp9_block2above_8x8[b]];
        L[vp9_block2left_8x8[b] + 1]  = L[vp9_block2left_8x8[b]];
Deb Mukherjee's avatar
Deb Mukherjee committed
493
      }
494
    }
Jingning Han's avatar
Jingning Han committed
495
  } else {
496 497
    for (b = 0; b < 16; b++) {
      tokenize_b(cpi, xd, xd->block + b, t, plane_type,
498
                 A + vp9_block2above[b], L + vp9_block2left[b],
499 500 501 502 503
                 TX_4X4, dry_run);
    }

    for (b = 16; b < 24; b++) {
      tokenize_b(cpi, xd, xd->block + b, t, PLANE_TYPE_UV,
504
                 A + vp9_block2above[b], L + vp9_block2left[b],
505 506
                 TX_4X4, dry_run);
    }
Jingning Han's avatar
Jingning Han committed
507
  }
508 509
  if (dry_run)
    *t = t_backup;
John Koleszar's avatar
John Koleszar committed
510
}
511

John Koleszar's avatar
John Koleszar committed
512 513

#ifdef ENTROPY_STATS
John Koleszar's avatar
John Koleszar committed
514 515 516 517 518
void init_context_counters(void) {
  FILE *f = fopen("context.bin", "rb");
  if (!f) {
    vpx_memset(context_counters, 0, sizeof(context_counters));
    vpx_memset(context_counters_8x8, 0, sizeof(context_counters_8x8));
Daniel Kang's avatar
Daniel Kang committed
519
    vpx_memset(context_counters_16x16, 0, sizeof(context_counters_16x16));
John Koleszar's avatar
John Koleszar committed
520 521 522
  } else {
    fread(context_counters, sizeof(context_counters), 1, f);
    fread(context_counters_8x8, sizeof(context_counters_8x8), 1, f);
Daniel Kang's avatar
Daniel Kang committed
523
    fread(context_counters_16x16, sizeof(context_counters_16x16), 1, f);
John Koleszar's avatar
John Koleszar committed
524 525 526 527 528 529 530
    fclose(f);
  }

  f = fopen("treeupdate.bin", "rb");
  if (!f) {
    vpx_memset(tree_update_hist, 0, sizeof(tree_update_hist));
    vpx_memset(tree_update_hist_8x8, 0, sizeof(tree_update_hist_8x8));
Daniel Kang's avatar
Daniel Kang committed
531
    vpx_memset(tree_update_hist_16x16, 0, sizeof(tree_update_hist_16x16));
John Koleszar's avatar
John Koleszar committed
532 533 534
  } else {
    fread(tree_update_hist, sizeof(tree_update_hist), 1, f);
    fread(tree_update_hist_8x8, sizeof(tree_update_hist_8x8), 1, f);
Daniel Kang's avatar
Daniel Kang committed
535
    fread(tree_update_hist_16x16, sizeof(tree_update_hist_16x16), 1, f);
John Koleszar's avatar
John Koleszar committed
536 537
    fclose(f);
  }
John Koleszar's avatar
John Koleszar committed
538 539
}

John Koleszar's avatar
John Koleszar committed
540 541
void print_context_counters() {
  int type, band, pt, t;
542
  FILE *f = fopen("vp9_context.c", "w");
John Koleszar's avatar
John Koleszar committed
543

544
  fprintf(f, "#include \"vp9_entropy.h\"\n");
John Koleszar's avatar
John Koleszar committed
545 546
  fprintf(f, "\n/* *** GENERATED FILE: DO NOT EDIT *** */\n\n");
  fprintf(f, "static const unsigned int\n"
547
          "vp9_default_coef_counts[BLOCK_TYPES]\n"
John Koleszar's avatar
John Koleszar committed
548 549 550
          "                      [COEF_BANDS]\n"
          "                      [PREV_COEF_CONTEXTS]\n"
          "                      [MAX_ENTROPY_TOKENS]={\n");
John Koleszar's avatar
John Koleszar committed
551 552

# define Comma( X) (X? ",":"")
John Koleszar's avatar
John Koleszar committed
553 554 555 556 557 558 559 560 561 562 563 564 565 566 567 568 569 570 571 572 573 574 575 576
  type = 0;
  do {
    fprintf(f, "%s\n  { /* block Type %d */", Comma(type), type);
    band = 0;
    do {
      fprintf(f, "%s\n    { /* Coeff Band %d */", Comma(band), band);
      pt = 0;
      do {
        fprintf(f, "%s\n      {", Comma(pt));

        t = 0;
        do {
          const INT64 x = context_counters [type] [band] [pt] [t];
          const int y = (int) x;
          assert(x == (INT64) y);  /* no overflow handling yet */
          fprintf(f, "%s %d", Comma(t), y);
        } while (++t < MAX_ENTROPY_TOKENS);
        fprintf(f, "}");
      } while (++pt < PREV_COEF_CONTEXTS);
      fprintf(f, "\n    }");
    } while (++band < COEF_BANDS);
    fprintf(f, "\n  }");
  } while (++type < BLOCK_TYPES);
  fprintf(f, "\n};\n");
577

578
  fprintf(f, "static const unsigned int\nvp9_default_coef_counts_8x8"
John Koleszar's avatar
John Koleszar committed
579 580 581 582 583 584 585 586 587 588 589 590 591 592 593
          "[BLOCK_TYPES_8X8] [COEF_BANDS]"
          "[PREV_COEF_CONTEXTS] [MAX_ENTROPY_TOKENS] = {");
  type = 0;
  do {
    fprintf(f, "%s\n  { /* block Type %d */", Comma(type), type);
    band = 0;
    do {
      fprintf(f, "%s\n    { /* Coeff Band %d */", Comma(band), band);
      pt = 0;
      do {
        fprintf(f, "%s\n      {", Comma(pt));
        t = 0;
        do {
          const INT64 x = context_counters_8x8 [type] [band] [pt] [t];
          const int y = (int) x;
594

John Koleszar's avatar
John Koleszar committed
595 596
          assert(x == (INT64) y);  /* no overflow handling yet */
          fprintf(f, "%s %d", Comma(t), y);
John Koleszar's avatar
John Koleszar committed
597

John Koleszar's avatar
John Koleszar committed
598
        } while (++t < MAX_ENTROPY_TOKENS);
599

John Koleszar's avatar
John Koleszar committed
600 601
        fprintf(f, "}");
      } while (++pt < PREV_COEF_CONTEXTS);
602

John Koleszar's avatar
John Koleszar committed
603
      fprintf(f, "\n    }");
604

John Koleszar's avatar
John Koleszar committed
605
    } while (++band < COEF_BANDS);
606

John Koleszar's avatar
John Koleszar committed
607 608
    fprintf(f, "\n  }");
  } while (++type < BLOCK_TYPES_8X8);
Daniel Kang's avatar
Daniel Kang committed
609
  fprintf(f, "\n};\n");
610

611
  fprintf(f, "static const unsigned int\nvp9_default_coef_counts_16x16"
Daniel Kang's avatar
Daniel Kang committed
612 613 614 615 616 617 618 619 620 621 622 623 624 625 626 627 628 629 630 631 632 633 634 635 636 637 638 639 640 641
          "[BLOCK_TYPES_16X16] [COEF_BANDS]"
          "[PREV_COEF_CONTEXTS] [MAX_ENTROPY_TOKENS] = {");
  type = 0;
  do {
    fprintf(f, "%s\n  { /* block Type %d */", Comma(type), type);
    band = 0;
    do {
      fprintf(f, "%s\n    { /* Coeff Band %d */", Comma(band), band);
      pt = 0;
      do {
        fprintf(f, "%s\n      {", Comma(pt));
        t = 0;
        do {
          const INT64 x = context_counters_16x16 [type] [band] [pt] [t];
          const int y = (int) x;

          assert(x == (INT64) y);  /* no overflow handling yet */
          fprintf(f, "%s %d", Comma(t), y);

        } while (++t < MAX_ENTROPY_TOKENS);

        fprintf(f, "}");
      } while (++pt < PREV_COEF_CONTEXTS);

      fprintf(f, "\n    }");

    } while (++band < COEF_BANDS);

    fprintf(f, "\n  }");
  } while (++type < BLOCK_TYPES_16X16);
John Koleszar's avatar
John Koleszar committed
642
  fprintf(f, "\n};\n");
643

644
  fprintf(f, "static const vp9_prob\n"
645
          "vp9_default_coef_probs[BLOCK_TYPES] [COEF_BANDS] \n"
John Koleszar's avatar
John Koleszar committed
646 647 648 649 650 651 652 653 654 655 656
          "[PREV_COEF_CONTEXTS] [ENTROPY_NODES] = {");
  type = 0;
  do {
    fprintf(f, "%s\n  { /* block Type %d */", Comma(type), type);
    band = 0;
    do {
      fprintf(f, "%s\n    { /* Coeff Band %d */", Comma(band), band);
      pt = 0;
      do {
        unsigned int branch_ct [ENTROPY_NODES] [2];
        unsigned int coef_counts[MAX_ENTROPY_TOKENS];
657
        vp9_prob coef_probs[ENTROPY_NODES];
John Koleszar's avatar
John Koleszar committed
658 659
        for (t = 0; t < MAX_ENTROPY_TOKENS; ++t)
          coef_counts[t] = context_counters [type] [band] [pt] [t];
660
        vp9_tree_probs_from_distribution(
661
          MAX_ENTROPY_TOKENS, vp9_coef_encodings, vp9_coef_tree,
John Koleszar's avatar
John Koleszar committed
662 663
          coef_probs, branch_ct, coef_counts, 256, 1);
        fprintf(f, "%s\n      {", Comma(pt));
664

John Koleszar's avatar
John Koleszar committed
665 666 667
        t = 0;
        do {
          fprintf(f, "%s %d", Comma(t), coef_probs[t]);
668

John Koleszar's avatar
John Koleszar committed
669
        } while (++t < ENTROPY_NODES);
670

John Koleszar's avatar
John Koleszar committed
671 672 673 674 675 676 677
        fprintf(f, "}");
      } while (++pt < PREV_COEF_CONTEXTS);
      fprintf(f, "\n    }");
    } while (++band < COEF_BANDS);
    fprintf(f, "\n  }");
  } while (++type < BLOCK_TYPES);
  fprintf(f, "\n};\n");
678

679
  fprintf(f, "static const vp9_prob\n"
680
          "vp9_default_coef_probs_8x8[BLOCK_TYPES_8X8] [COEF_BANDS]\n"
John Koleszar's avatar
John Koleszar committed
681 682 683 684 685 686 687 688 689 690 691
          "[PREV_COEF_CONTEXTS] [ENTROPY_NODES] = {");
  type = 0;
  do {
    fprintf(f, "%s\n  { /* block Type %d */", Comma(type), type);
    band = 0;
    do {
      fprintf(f, "%s\n    { /* Coeff Band %d */", Comma(band), band);
      pt = 0;
      do {
        unsigned int branch_ct [ENTROPY_NODES] [2];
        unsigned int coef_counts[MAX_ENTROPY_TOKENS];
692
        vp9_prob coef_probs[ENTROPY_NODES];
John Koleszar's avatar
John Koleszar committed
693 694
        for (t = 0; t < MAX_ENTROPY_TOKENS; ++t)
          coef_counts[t] = context_counters_8x8[type] [band] [pt] [t];
695
        vp9_tree_probs_from_distribution(
696
          MAX_ENTROPY_TOKENS, vp9_coef_encodings, vp9_coef_tree,
John Koleszar's avatar
John Koleszar committed
697 698
          coef_probs, branch_ct, coef_counts, 256, 1);
        fprintf(f, "%s\n      {", Comma(pt));
699

Daniel Kang's avatar
Daniel Kang committed
700
        t = 0;
John Koleszar's avatar
John Koleszar committed
701 702 703 704 705 706 707 708 709 710 711
        do {
          fprintf(f, "%s %d", Comma(t), coef_probs[t]);
        } while (++t < ENTROPY_NODES);
        fprintf(f, "}");
      } while (++pt < PREV_COEF_CONTEXTS);
      fprintf(f, "\n    }");
    } while (++band < COEF_BANDS);
    fprintf(f, "\n  }");
  } while (++type < BLOCK_TYPES_8X8);
  fprintf(f, "\n};\n");

712
  fprintf(f, "static const vp9_prob\n"
713
          "vp9_default_coef_probs_16x16[BLOCK_TYPES_16X16] [COEF_BANDS]\n"
Daniel Kang's avatar
Daniel Kang committed
714 715 716 717 718 719 720 721 722 723 724
          "[PREV_COEF_CONTEXTS] [ENTROPY_NODES] = {");
  type = 0;
  do {
    fprintf(f, "%s\n  { /* block Type %d */", Comma(type), type);
    band = 0;
    do {
      fprintf(f, "%s\n    { /* Coeff Band %d */", Comma(band), band);
      pt = 0;
      do {
        unsigned int branch_ct [ENTROPY_NODES] [2];
        unsigned int coef_counts[MAX_ENTROPY_TOKENS];
725
        vp9_prob coef_probs[ENTROPY_NODES];
Daniel Kang's avatar
Daniel Kang committed
726 727
        for (t = 0; t < MAX_ENTROPY_TOKENS; ++t)
          coef_counts[t] = context_counters_16x16[type] [band] [pt] [t];
728
        vp9_tree_probs_from_distribution(
729
          MAX_ENTROPY_TOKENS, vp9_coef_encodings, vp9_coef_tree,
Daniel Kang's avatar
Daniel Kang committed
730 731 732 733 734 735 736 737 738 739 740 741 742 743 744
          coef_probs, branch_ct, coef_counts, 256, 1);
        fprintf(f, "%s\n      {", Comma(pt));

        t = 0;
        do {
          fprintf(f, "%s %d", Comma(t), coef_probs[t]);
        } while (++t < ENTROPY_NODES);
        fprintf(f, "}");
      } while (++pt < PREV_COEF_CONTEXTS);
      fprintf(f, "\n    }");
    } while (++band < COEF_BANDS);
    fprintf(f, "\n  }");
  } while (++type < BLOCK_TYPES_16X16);
  fprintf(f, "\n};\n");

John Koleszar's avatar
John Koleszar committed
745 746 747 748 749
  fclose(f);

  f = fopen("context.bin", "wb");
  fwrite(context_counters, sizeof(context_counters), 1, f);
  fwrite(context_counters_8x8, sizeof(context_counters_8x8), 1, f);
Daniel Kang's avatar
Daniel Kang committed
750
  fwrite(context_counters_16x16, sizeof(context_counters_16x16), 1, f);
John Koleszar's avatar
John Koleszar committed
751
  fclose(f);
John Koleszar's avatar
John Koleszar committed
752 753 754
}
#endif

755
void vp9_tokenize_initialize() {
John Koleszar's avatar
John Koleszar committed
756
  fill_value_tokens();
John Koleszar's avatar
John Koleszar committed
757 758
}

759
static __inline void stuff_b(VP9_COMP *cpi,
760 761 762 763 764 765 766 767 768 769
                             MACROBLOCKD *xd,
                             const BLOCKD * const b,
                             TOKENEXTRA **tp,
                             PLANE_TYPE type,
                             ENTROPY_CONTEXT *a,
                             ENTROPY_CONTEXT *l,
                             TX_SIZE tx_size,
                             int dry_run) {
  const int *bands;
  unsigned int (*counts)[COEF_BANDS][PREV_COEF_CONTEXTS][MAX_ENTROPY_TOKENS];
770
  vp9_prob (*probs)[COEF_BANDS][PREV_COEF_CONTEXTS][ENTROPY_NODES];
771 772 773 774
  int pt, band;
  TOKENEXTRA *t = *tp;
  const TX_TYPE tx_type = (type == PLANE_TYPE_Y_WITH_DC) ?
                          get_tx_type(xd, b) : DCT_DCT;
775
  VP9_COMBINEENTROPYCONTEXTS(pt, *a, *l);
John Koleszar's avatar
John Koleszar committed
776

777 778 779
  switch (tx_size) {
    default:
    case TX_4X4:
780
      bands = vp9_coef_bands;
781 782 783 784 785 786 787 788 789
      if (tx_type != DCT_DCT) {
        counts = cpi->hybrid_coef_counts;
        probs = cpi->common.fc.hybrid_coef_probs;
      } else {
        counts = cpi->coef_counts;
        probs = cpi->common.fc.coef_probs;
      }
      break;
    case TX_8X8:
790
      bands = vp9_coef_bands_8x8;
791 792 793 794 795 796 797 798 799
      if (tx_type != DCT_DCT) {
        counts = cpi->hybrid_coef_counts_8x8;
        probs = cpi->common.fc.hybrid_coef_probs_8x8;
      } else {
        counts = cpi->coef_counts_8x8;
        probs = cpi->common.fc.coef_probs_8x8;
      }
      break;
    case TX_16X16:
800
      bands = vp9_coef_bands_16x16;
801 802 803 804 805 806 807 808
      if (tx_type != DCT_DCT) {
        counts = cpi->hybrid_coef_counts_16x16;
        probs = cpi->common.fc.hybrid_coef_probs_16x16;
      } else {
        counts = cpi->coef_counts_16x16;
        probs = cpi->common.fc.coef_probs_16x16;
      }
      break;
809 810 811 812 813 814 815
#if CONFIG_TX32X32 && CONFIG_SUPERBLOCKS
    case TX_32X32:
      bands = vp9_coef_bands_32x32;
      counts = cpi->coef_counts_32x32;
      probs = cpi->common.fc.coef_probs_32x32;
      break;
#endif
816 817
  }
  band = bands[(type == PLANE_TYPE_Y_NO_DC) ? 1 : 0];
John Koleszar's avatar
John Koleszar committed
818
  t->Token = DCT_EOB_TOKEN;
819
  t->context_tree = probs[type][band][pt];
John Koleszar's avatar
John Koleszar committed
820 821 822
  t->skip_eob_node = 0;
  ++t;
  *tp = t;
823
  *a = *l = 0;
824
  if (!dry_run) {
825
    ++counts[type][band][pt][DCT_EOB_TOKEN];
826
  }
827 828
}

829 830
static void stuff_mb_8x8(VP9_COMP *cpi, MACROBLOCKD *xd,
                         TOKENEXTRA **t, int dry_run) {
Paul Wilkins's avatar
Paul Wilkins committed
831 832
  ENTROPY_CONTEXT *A = (ENTROPY_CONTEXT *)xd->above_context;
  ENTROPY_CONTEXT *L = (ENTROPY_CONTEXT *)xd->left_context;
833
  PLANE_TYPE plane_type;
John Koleszar's avatar
John Koleszar committed
834
  int b;
835
  int has_2nd_order = get_2nd_order_usage(xd);
John Koleszar's avatar
John Koleszar committed
836

837
  if (has_2nd_order) {
838
    stuff_b(cpi, xd, xd->block + 24, t, PLANE_TYPE_Y2,
839
            A + vp9_block2above_8x8[24], L + vp9_block2left_8x8[24],
840
            TX_8X8, dry_run);
841 842
    plane_type = PLANE_TYPE_Y_NO_DC;
  } else {
Yaowu Xu's avatar
Yaowu Xu committed
843 844
    xd->above_context->y2 = 1;
    xd->left_context->y2 = 1;
845 846
    plane_type = PLANE_TYPE_Y_WITH_DC;
  }
John Koleszar's avatar
John Koleszar committed
847 848

  for (b = 0; b < 16; b += 4) {
849 850 851 852
    stuff_b(cpi, xd, xd->block + b,