vp9_tokenize.c 32.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
/* 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 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46
vp9_coeff_accum context_counters_4x4[BLOCK_TYPES_4X4];
vp9_coeff_accum hybrid_context_counters_4x4[BLOCK_TYPES_4X4];
vp9_coeff_accum context_counters_8x8[BLOCK_TYPES_8X8];
vp9_coeff_accum hybrid_context_counters_8x8[BLOCK_TYPES_8X8];
vp9_coeff_accum context_counters_16x16[BLOCK_TYPES_16X16];
vp9_coeff_accum hybrid_context_counters_16x16[BLOCK_TYPES_16X16];
#if CONFIG_TX32X32
vp9_coeff_accum context_counters_32x32[BLOCK_TYPES_32X32];
#endif

extern vp9_coeff_stats tree_update_hist_4x4[BLOCK_TYPES_4X4];
extern vp9_coeff_stats hybrid_tree_update_hist_4x4[BLOCK_TYPES_4X4];
extern vp9_coeff_stats tree_update_hist_8x8[BLOCK_TYPES_8X8];
extern vp9_coeff_stats hybrid_tree_update_hist_8x8[BLOCK_TYPES_8X8];
extern vp9_coeff_stats tree_update_hist_16x16[BLOCK_TYPES_16X16];
extern vp9_coeff_stats hybrid_tree_update_hist_16x16[BLOCK_TYPES_16X16];
#if CONFIG_TX32X32
extern vp9_coeff_stats tree_update_hist_32x32[BLOCK_TYPES_32X32];
#endif
47 48
#endif  /* ENTROPY_STATS */

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

John Koleszar's avatar
John Koleszar committed
54
static void fill_value_tokens() {
John Koleszar's avatar
John Koleszar committed
55

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

John Koleszar's avatar
John Koleszar committed
59 60
  int i = -DCT_MAX_VALUE;
  int sign = 1;
John Koleszar's avatar
John Koleszar committed
61

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

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

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

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

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

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

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

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

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

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

    }

John Koleszar's avatar
John Koleszar committed
101 102
  } while (++i < DCT_MAX_VALUE);

103 104
  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
105 106
}

107
static void tokenize_b(VP9_COMP *cpi,
108 109 110 111 112 113 114 115
                       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
116
  int pt; /* near block/prev token context index */
117
  int c = (type == PLANE_TYPE_Y_NO_DC) ? 1 : 0;
118
  int eob = b->eob;     /* one beyond last nonzero coeff */
Daniel Kang's avatar
Daniel Kang committed
119 120
  TOKENEXTRA *t = *tp;        /* store tokens starting here */
  const short *qcoeff_ptr = b->qcoeff;
121
  int seg_eob;
Daniel Kang's avatar
Daniel Kang committed
122
  int segment_id = xd->mode_info_context->mbmi.segment_id;
123
  const int *bands, *scan;
124 125
  vp9_coeff_count *counts;
  vp9_coeff_probs *probs;
126 127
  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
128

129
  VP9_COMBINEENTROPYCONTEXTS(pt, *a, *l);
130 131 132 133
  switch (tx_size) {
    default:
    case TX_4X4:
      seg_eob = 16;
134 135
      bands = vp9_coef_bands;
      scan = vp9_default_zig_zag1d;
136
      if (tx_type != DCT_DCT) {
137 138
        counts = cpi->hybrid_coef_counts_4x4;
        probs = cpi->common.fc.hybrid_coef_probs_4x4;
139
        if (tx_type == ADST_DCT) {
140
          scan = vp9_row_scan;
141
        } else if (tx_type == DCT_ADST) {
142
          scan = vp9_col_scan;
143 144
        }
      } else {
145 146
        counts = cpi->coef_counts_4x4;
        probs = cpi->common.fc.coef_probs_4x4;
147 148 149 150 151
      }
      break;
    case TX_8X8:
      if (type == PLANE_TYPE_Y2) {
        seg_eob = 4;
152 153
        bands = vp9_coef_bands;
        scan = vp9_default_zig_zag1d;
154 155
      } else {
        seg_eob = 64;
156 157
        bands = vp9_coef_bands_8x8;
        scan = vp9_default_zig_zag1d_8x8;
158 159 160 161 162 163 164 165 166 167 168
      }
      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;
169 170
      bands = vp9_coef_bands_16x16;
      scan = vp9_default_zig_zag1d_16x16;
171 172 173 174 175 176 177
      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;
      }
178 179 180 181 182 183 184 185 186 187 188 189 190 191 192
#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;
193
      break;
194
#endif
John Koleszar's avatar
John Koleszar committed
195 196
  }

197 198
  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
199

200
  do {
201
    const int band = bands[c];
202 203 204
    int token;

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

208 209
      assert(-DCT_MAX_VALUE <= v  &&  v < DCT_MAX_VALUE);

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

    t->Token = token;
217 218 219
    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));
220
    assert(vp9_coef_encodings[t->Token].Len - t->skip_eob_node > 0);
221
    if (!dry_run) {
222
      ++counts[type][band][pt][token];
223
    }
224
    pt = vp9_prev_token_class[token];
225
    ++t;
226 227 228
  } while (c < eob && ++c < seg_eob);

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

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

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

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

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

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

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

265
  if (has_2nd_order) {
Deb Mukherjee's avatar
Deb Mukherjee committed
266 267 268 269 270 271 272
    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
273
  return skip;
274
}
275

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

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

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

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

296 297
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
298
}
299

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
#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

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

John Koleszar's avatar
John Koleszar committed
386 387 388 389
  // 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
390
  int segment_id = xd->mode_info_context->mbmi.segment_id;
391

392 393
  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
394 395 396
    skip_inc = 1;
  } else
    skip_inc = 0;
397

398
  has_2nd_order = get_2nd_order_usage(xd);
John Koleszar's avatar
John Koleszar committed
399

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

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

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

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

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

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

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

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

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

John Koleszar's avatar
John Koleszar committed
510 511

#ifdef ENTROPY_STATS
John Koleszar's avatar
John Koleszar committed
512 513 514
void init_context_counters(void) {
  FILE *f = fopen("context.bin", "rb");
  if (!f) {
515 516 517
    vpx_memset(context_counters_4x4, 0, sizeof(context_counters_4x4));
    vpx_memset(hybrid_context_counters_4x4, 0,
               sizeof(hybrid_context_counters_4x4));
John Koleszar's avatar
John Koleszar committed
518
    vpx_memset(context_counters_8x8, 0, sizeof(context_counters_8x8));
519 520
    vpx_memset(hybrid_context_counters_8x8, 0,
               sizeof(hybrid_context_counters_8x8));
Daniel Kang's avatar
Daniel Kang committed
521
    vpx_memset(context_counters_16x16, 0, sizeof(context_counters_16x16));
522 523 524 525 526
    vpx_memset(hybrid_context_counters_16x16, 0,
               sizeof(hybrid_context_counters_16x16));
#if CONFIG_TX32X32
    vpx_memset(context_counters_32x32, 0, sizeof(context_counters_32x32));
#endif
John Koleszar's avatar
John Koleszar committed
527
  } else {
528 529 530
    fread(context_counters_4x4, sizeof(context_counters_4x4), 1, f);
    fread(hybrid_context_counters_4x4,
          sizeof(hybrid_context_counters_4x4), 1, f);
John Koleszar's avatar
John Koleszar committed
531
    fread(context_counters_8x8, sizeof(context_counters_8x8), 1, f);
532 533
    fread(hybrid_context_counters_8x8,
          sizeof(hybrid_context_counters_8x8), 1, f);
Daniel Kang's avatar
Daniel Kang committed
534
    fread(context_counters_16x16, sizeof(context_counters_16x16), 1, f);
535 536 537 538 539
    fread(hybrid_context_counters_16x16,
          sizeof(hybrid_context_counters_16x16), 1, f);
#if CONFIG_TX32X32
    fread(context_counters_32x32, sizeof(context_counters_32x32), 1, f);
#endif
John Koleszar's avatar
John Koleszar committed
540 541 542 543 544
    fclose(f);
  }

  f = fopen("treeupdate.bin", "rb");
  if (!f) {
545 546 547
    vpx_memset(tree_update_hist_4x4, 0, sizeof(tree_update_hist_4x4));
    vpx_memset(hybrid_tree_update_hist_4x4, 0,
               sizeof(hybrid_tree_update_hist_4x4));
John Koleszar's avatar
John Koleszar committed
548
    vpx_memset(tree_update_hist_8x8, 0, sizeof(tree_update_hist_8x8));
549 550
    vpx_memset(hybrid_tree_update_hist_8x8, 0,
               sizeof(hybrid_tree_update_hist_8x8));
Daniel Kang's avatar
Daniel Kang committed
551
    vpx_memset(tree_update_hist_16x16, 0, sizeof(tree_update_hist_16x16));
552 553 554 555 556
    vpx_memset(hybrid_tree_update_hist_16x16, 0,
               sizeof(hybrid_tree_update_hist_16x16));
#if CONFIG_TX32X32
    vpx_memset(tree_update_hist_32x32, 0, sizeof(tree_update_hist_32x32));
#endif
John Koleszar's avatar
John Koleszar committed
557
  } else {
558 559 560
    fread(tree_update_hist_4x4, sizeof(tree_update_hist_4x4), 1, f);
    fread(hybrid_tree_update_hist_4x4,
          sizeof(hybrid_tree_update_hist_4x4), 1, f);
John Koleszar's avatar
John Koleszar committed
561
    fread(tree_update_hist_8x8, sizeof(tree_update_hist_8x8), 1, f);
562 563
    fread(hybrid_tree_update_hist_8x8,
          sizeof(hybrid_tree_update_hist_8x8), 1, f);
Daniel Kang's avatar
Daniel Kang committed
564
    fread(tree_update_hist_16x16, sizeof(tree_update_hist_16x16), 1, f);
565 566 567 568 569
    fread(hybrid_tree_update_hist_16x16,
          sizeof(hybrid_tree_update_hist_16x16), 1, f);
#if CONFIG_TX32X32
    fread(tree_update_hist_32x32, sizeof(tree_update_hist_32x32), 1, f);
#endif
John Koleszar's avatar
John Koleszar committed
570 571
    fclose(f);
  }
John Koleszar's avatar
John Koleszar committed
572 573
}

574 575
static void print_counter(FILE *f, vp9_coeff_accum *context_counters,
                          int block_types, const char *header) {
John Koleszar's avatar
John Koleszar committed
576
  int type, band, pt, t;
John Koleszar's avatar
John Koleszar committed
577

578
  fprintf(f, "static const vp9_coeff_count %s = {\n", header);
John Koleszar's avatar
John Koleszar committed
579 580

# define Comma( X) (X? ",":"")
John Koleszar's avatar
John Koleszar committed
581 582 583 584 585 586 587 588 589 590 591 592 593 594
  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;
595

John Koleszar's avatar
John Koleszar committed
596 597 598 599 600 601 602 603
          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  }");
604
  } while (++type < block_types);
Daniel Kang's avatar
Daniel Kang committed
605
  fprintf(f, "\n};\n");
606
}
607

608 609 610
static void print_probs(FILE *f, vp9_coeff_accum *context_counters,
                        int block_types, const char *header) {
  int type, band, pt, t;
Daniel Kang's avatar
Daniel Kang committed
611

612
  fprintf(f, "static const vp9_coeff_probs %s = {\n", header);
613

John Koleszar's avatar
John Koleszar committed
614 615 616 617 618 619 620 621 622 623
  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];
624
        vp9_prob coef_probs[ENTROPY_NODES];
625

John Koleszar's avatar
John Koleszar committed
626
        for (t = 0; t < MAX_ENTROPY_TOKENS; ++t)
627 628 629
          coef_counts[t] = context_counters[type][band][pt][t];
        vp9_tree_probs_from_distribution(MAX_ENTROPY_TOKENS,
                                         vp9_coef_encodings, vp9_coef_tree,
630
                                         coef_probs, branch_ct, coef_counts);
John Koleszar's avatar
John Koleszar committed
631
        fprintf(f, "%s\n      {", Comma(pt));
632

John Koleszar's avatar
John Koleszar committed
633 634 635 636
        t = 0;
        do {
          fprintf(f, "%s %d", Comma(t), coef_probs[t]);
        } while (++t < ENTROPY_NODES);
637

John Koleszar's avatar
John Koleszar committed
638 639 640 641 642
        fprintf(f, "}");
      } while (++pt < PREV_COEF_CONTEXTS);
      fprintf(f, "\n    }");
    } while (++band < COEF_BANDS);
    fprintf(f, "\n  }");
643
  } while (++type < block_types);
John Koleszar's avatar
John Koleszar committed
644
  fprintf(f, "\n};\n");
645
}
646

647 648
void print_context_counters() {
  FILE *f = fopen("vp9_context.c", "w");
649

650 651
  fprintf(f, "#include \"vp9_entropy.h\"\n");
  fprintf(f, "\n/* *** GENERATED FILE: DO NOT EDIT *** */\n\n");
John Koleszar's avatar
John Koleszar committed
652

653 654 655 656 657 658 659 660 661 662 663 664 665 666 667 668 669
  /* print counts */
  print_counter(f, context_counters_4x4, BLOCK_TYPES_4X4,
                "vp9_default_coef_counts_4x4[BLOCK_TYPES_4X4]");
  print_counter(f, hybrid_context_counters_4x4, BLOCK_TYPES_4X4,
                "vp9_default_hybrid_coef_counts_4x4[BLOCK_TYPES_4X4]");
  print_counter(f, context_counters_8x8, BLOCK_TYPES_8X8,
                "vp9_default_coef_counts_8x8[BLOCK_TYPES_8X8]");
  print_counter(f, hybrid_context_counters_8x8, BLOCK_TYPES_8X8,
                "vp9_default_hybrid_coef_counts_8x8[BLOCK_TYPES_8X8]");
  print_counter(f, context_counters_16x16, BLOCK_TYPES_16X16,
                "vp9_default_coef_counts_16x16[BLOCK_TYPES_16X16]");
  print_counter(f, hybrid_context_counters_16x16, BLOCK_TYPES_16X16,
                "vp9_default_hybrid_coef_counts_16x16[BLOCK_TYPES_16X16]");
#if CONFIG_TX32X32
  print_counter(f, context_counters_32x32, BLOCK_TYPES_32X32,
                "vp9_default_coef_counts_32x32[BLOCK_TYPES_32X32]");
#endif
Daniel Kang's avatar
Daniel Kang committed
670

671 672 673 674 675 676 677 678 679 680 681 682 683 684 685 686 687
  /* print coefficient probabilities */
  print_probs(f, context_counters_4x4, BLOCK_TYPES_4X4,
              "vp9_default_coef_probs_4x4[BLOCK_TYPES_4X4]");
  print_probs(f, hybrid_context_counters_4x4, BLOCK_TYPES_4X4,
              "vp9_default_hybrid_coef_probs_4x4[BLOCK_TYPES_4X4]");
  print_probs(f, context_counters_8x8, BLOCK_TYPES_8X8,
              "vp9_default_coef_probs_8x8[BLOCK_TYPES_8X8]");
  print_probs(f, hybrid_context_counters_8x8, BLOCK_TYPES_8X8,
              "vp9_default_hybrid_coef_probs_8x8[BLOCK_TYPES_8X8]");
  print_probs(f, context_counters_16x16, BLOCK_TYPES_16X16,
              "vp9_default_coef_probs_16x16[BLOCK_TYPES_16X16]");
  print_probs(f, hybrid_context_counters_16x16, BLOCK_TYPES_16X16,
              "vp9_default_hybrid_coef_probs_16x16[BLOCK_TYPES_16X16]");
#if CONFIG_TX32X32
  print_probs(f, context_counters_32x32, BLOCK_TYPES_32X32,
              "vp9_default_coef_probs_32x32[BLOCK_TYPES_32X32]");
#endif
Daniel Kang's avatar
Daniel Kang committed
688

John Koleszar's avatar
John Koleszar committed
689 690 691
  fclose(f);

  f = fopen("context.bin", "wb");
692 693 694
  fwrite(context_counters_4x4, sizeof(context_counters_4x4), 1, f);
  fwrite(hybrid_context_counters_4x4,
         sizeof(hybrid_context_counters_4x4), 1, f);
John Koleszar's avatar
John Koleszar committed
695
  fwrite(context_counters_8x8, sizeof(context_counters_8x8), 1, f);
696 697
  fwrite(hybrid_context_counters_8x8,
         sizeof(hybrid_context_counters_8x8), 1, f);
Daniel Kang's avatar
Daniel Kang committed
698
  fwrite(context_counters_16x16, sizeof(context_counters_16x16), 1, f);
699 700 701 702 703
  fwrite(hybrid_context_counters_16x16,
         sizeof(hybrid_context_counters_16x16), 1, f);
#if CONFIG_TX32X32
  fwrite(context_counters_32x32, sizeof(context_counters_32x32), 1, f);
#endif
John Koleszar's avatar
John Koleszar committed
704
  fclose(f);
John Koleszar's avatar
John Koleszar committed
705 706 707
}
#endif

708
void vp9_tokenize_initialize() {
John Koleszar's avatar
John Koleszar committed
709
  fill_value_tokens();
John Koleszar's avatar
John Koleszar committed
710 711
}

712
static __inline void stuff_b(VP9_COMP *cpi,
713 714 715 716 717 718 719 720 721
                             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;
722 723
  vp9_coeff_count *counts;
  vp9_coeff_probs *probs;
724 725 726 727
  int pt, band;
  TOKENEXTRA *t = *tp;
  const TX_TYPE tx_type = (type == PLANE_TYPE_Y_WITH_DC) ?
                          get_tx_type(xd, b) : DCT_DCT;
728
  VP9_COMBINEENTROPYCONTEXTS(pt, *a, *l);
John Koleszar's avatar
John Koleszar committed
729

730 731 732
  switch (tx_size) {
    default:
    case TX_4X4:
733
      bands = vp9_coef_bands;
734
      if (tx_type != DCT_DCT) {
735 736
        counts = cpi->hybrid_coef_counts_4x4;
        probs = cpi->common.fc.hybrid_coef_probs_4x4;
737
      } else {
738 739
        counts = cpi->coef_counts_4x4;
        probs = cpi->common.fc.coef_probs_4x4;
740 741 742
      }
      break;
    case TX_8X8:
743
      bands = vp9_coef_bands_8x8;
744 745 746 747 748 749 750 751 752
      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:
753
      bands = vp9_coef_bands_16x16;
754 755 756 757 758 759 760 761
      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;
762 763 764 765 766 767 768
#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
769 770
  }
  band = bands[(type == PLANE_TYPE_Y_NO_DC) ? 1 : 0];
John Koleszar's avatar
John Koleszar committed
771
  t->Token = DCT_EOB_TOKEN;
772
  t->context_tree = probs[type][band][pt];
John Koleszar's avatar
John Koleszar committed
773 774 775
  t->skip_eob_node = 0;
  ++t;
  *tp = t;
776
  *a = *l = 0;
777
  if (!dry_run) {
778
    ++counts[type][band][pt][DCT_EOB_TOKEN];
779
  }
780 781
}

782 783
static void stuff_mb_8x8(VP9_COMP *cpi, MACROBLOCKD *xd,
                         TOKENEXTRA **t, int dry_run) {
Paul Wilkins's avatar
Paul Wilkins committed
784 785
  ENTROPY_CONTEXT *A = (ENTROPY_CONTEXT *)xd->above_context;
  ENTROPY_CONTEXT *L = (ENTROPY_CONTEXT *)xd->left_context;
786
  PLANE_TYPE plane_type;
John Koleszar's avatar
John Koleszar committed
787
  int b;
788
  int has_2nd_order = get_2nd_order_usage(xd);
John Koleszar's avatar
John Koleszar committed
789

790
  if (has_2nd_order) {
791
    stuff_b(cpi, xd, xd->block + 24, t, PLANE_TYPE_Y2,
792
            A + vp9_block2above_8x8[24], L + vp9_block2left_8x8[24],
793
            TX_8X8, dry_run);
794 795
    plane_type = PLANE_TYPE_Y_NO_DC;
  } else {
Yaowu Xu's avatar
Yaowu Xu committed
796 797
    xd->above_context->y2 = 1;
    xd->left_context->y2 = 1;
798 799
    plane_type = PLANE_TYPE_Y_WITH_DC;
  }
John Koleszar's avatar
John Koleszar committed
800 801

  for (b = 0; b < 16; b += 4) {
802 803 804 805
    stuff_b(cpi, xd, xd->block + b, t, plane_type, A + vp9_block2above_8x8[b],
            L + vp9_block2left_8x8[b], TX_8X8, dry_run);
    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
806 807 808
  }

  for (b = 16; b < 24; b += 4) {
809
    stuff_b(cpi, xd, xd->block + b, t, PLANE_TYPE_UV,
810
            A + vp9_block2above_8x8[b], L + vp9_block2left_8x8[b],
811
            TX_8X8, dry_run);
812 813
    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
814
  }
Daniel Kang's avatar
Daniel Kang committed
815 816
}

817 818
static void stuff_mb_16x16(VP9_COMP *cpi, MACROBLOCKD *xd,
                           TOKENEXTRA **t, int dry_run) {
Paul Wilkins's avatar
Paul Wilkins committed
819 820
  ENTROPY_CONTEXT * A = (ENTROPY_CONTEXT *)xd->above_context;
  ENTROPY_CONTEXT * L = (ENTROPY_CONTEXT *)xd->left_context;
821
  int b;
Daniel Kang's avatar
Daniel Kang committed
822

823
  stuff_b(cpi, xd, xd->block, t, PLANE_TYPE_Y_WITH_DC, A, L, TX_16X16, dry_run);
824 825
  A[1] = A[2] = A[3] = A[0];
  L[1] = L[2] = L[3] = L[0];
Daniel Kang's avatar
Daniel Kang committed
826
  for (b = 16; b < 24; b += 4) {
827 828
    stuff_b(cpi, xd, xd->block + b, t, PLANE_TYPE_UV,
            A + vp9_block2above_8x8[b],