vp9_tokenize.c 36.7 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
vp9_coeff_accum context_counters_4x4[BLOCK_TYPES];
vp9_coeff_accum context_counters_8x8[BLOCK_TYPES];
vp9_coeff_accum context_counters_16x16[BLOCK_TYPES];
31
vp9_coeff_accum context_counters_32x32[BLOCK_TYPES];
32

33 34 35
extern vp9_coeff_stats tree_update_hist_4x4[BLOCK_TYPES];
extern vp9_coeff_stats tree_update_hist_8x8[BLOCK_TYPES];
extern vp9_coeff_stats tree_update_hist_16x16[BLOCK_TYPES];
36
extern vp9_coeff_stats tree_update_hist_32x32[BLOCK_TYPES];
37 38
#endif  /* ENTROPY_STATS */

39 40 41 42 43 44 45 46 47 48 49 50 51 52 53
#if CONFIG_CODE_NONZEROCOUNT
#ifdef NZC_STATS
unsigned int nzc_counts_4x4[MAX_NZC_CONTEXTS][REF_TYPES][BLOCK_TYPES]
                           [NZC4X4_TOKENS];
unsigned int nzc_counts_8x8[MAX_NZC_CONTEXTS][REF_TYPES][BLOCK_TYPES]
                           [NZC8X8_TOKENS];
unsigned int nzc_counts_16x16[MAX_NZC_CONTEXTS][REF_TYPES][BLOCK_TYPES]
                             [NZC16X16_TOKENS];
unsigned int nzc_counts_32x32[MAX_NZC_CONTEXTS][REF_TYPES][BLOCK_TYPES]
                             [NZC32X32_TOKENS];
unsigned int nzc_pcat_counts[MAX_NZC_CONTEXTS][NZC_TOKENS_EXTRA]
                            [NZC_BITS_EXTRA][2];
#endif
#endif

John Koleszar's avatar
John Koleszar committed
54
static TOKENVALUE dct_value_tokens[DCT_MAX_VALUE * 2];
55
const TOKENVALUE *vp9_dct_value_tokens_ptr;
John Koleszar's avatar
John Koleszar committed
56
static int dct_value_cost[DCT_MAX_VALUE * 2];
57
const int *vp9_dct_value_cost_ptr;
58

John Koleszar's avatar
John Koleszar committed
59
static void fill_value_tokens() {
John Koleszar's avatar
John Koleszar committed
60

John Koleszar's avatar
John Koleszar committed
61
  TOKENVALUE *const t = dct_value_tokens + DCT_MAX_VALUE;
62
  vp9_extra_bit *const e = vp9_extra_bits;
John Koleszar's avatar
John Koleszar committed
63

John Koleszar's avatar
John Koleszar committed
64 65
  int i = -DCT_MAX_VALUE;
  int sign = 1;
John Koleszar's avatar
John Koleszar committed
66

John Koleszar's avatar
John Koleszar committed
67 68 69
  do {
    if (!i)
      sign = 0;
John Koleszar's avatar
John Koleszar committed
70

John Koleszar's avatar
John Koleszar committed
71 72 73
    {
      const int a = sign ? -i : i;
      int eb = sign;
John Koleszar's avatar
John Koleszar committed
74

John Koleszar's avatar
John Koleszar committed
75 76
      if (a > 4) {
        int j = 4;
John Koleszar's avatar
John Koleszar committed
77

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

80
        t[i].token = --j;
John Koleszar's avatar
John Koleszar committed
81 82
        eb |= (a - e[j].base_val) << 1;
      } else
83
        t[i].token = a;
John Koleszar's avatar
John Koleszar committed
84

85
      t[i].extra = eb;
John Koleszar's avatar
John Koleszar committed
86
    }
John Koleszar's avatar
John Koleszar committed
87

John Koleszar's avatar
John Koleszar committed
88 89 90
    // initialize the cost for extra bits for all possible coefficient value.
    {
      int cost = 0;
91
      vp9_extra_bit *p = vp9_extra_bits + t[i].token;
John Koleszar's avatar
John Koleszar committed
92

John Koleszar's avatar
John Koleszar committed
93
      if (p->base_val) {
94
        const int extra = t[i].extra;
95
        const int length = p->len;
John Koleszar's avatar
John Koleszar committed
96

97 98
        if (length)
          cost += treed_cost(p->tree, p->prob, extra >> 1, length);
John Koleszar's avatar
John Koleszar committed
99

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

    }

John Koleszar's avatar
John Koleszar committed
106 107
  } while (++i < DCT_MAX_VALUE);

108 109
  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
110
}
111

112 113
extern const int *vp9_get_coef_neighbors_handle(const int *scan, int *pad);

114
static void tokenize_b(VP9_COMP *cpi,
115
                       MACROBLOCKD *xd,
Yaowu Xu's avatar
Yaowu Xu committed
116
                       const int ib,
117 118 119
                       TOKENEXTRA **tp,
                       PLANE_TYPE type,
                       TX_SIZE tx_size,
John Koleszar's avatar
John Koleszar committed
120
                       int y_blocks,
121
                       int dry_run) {
122
  MB_MODE_INFO *mbmi = &xd->mode_info_context->mbmi;
Daniel Kang's avatar
Daniel Kang committed
123
  int pt; /* near block/prev token context index */
124
  int c = 0, rc = 0;
Daniel Kang's avatar
Daniel Kang committed
125
  TOKENEXTRA *t = *tp;        /* store tokens starting here */
John Koleszar's avatar
John Koleszar committed
126 127
  const struct plane_block_idx pb_idx = plane_block_idx(y_blocks, ib);
  const int eob = xd->plane[pb_idx.plane].eobs[pb_idx.block];
128 129
  const int16_t *qcoeff_ptr = BLOCK_OFFSET(xd->plane[pb_idx.plane].qcoeff,
                                           pb_idx.block, 16);
130
  int seg_eob, default_eob, pad;
131 132
  const int segment_id = mbmi->segment_id;
  const BLOCK_SIZE_TYPE sb_type = mbmi->sb_type;
133
  const int *scan, *nb;
134
  vp9_coeff_count *counts;
135
  vp9_coeff_probs *coef_probs;
136 137
  const int ref = mbmi->ref_frame != INTRA_FRAME;
  ENTROPY_CONTEXT *a, *l, *a1, *l1, *a2, *l2, *a3, *l3, a_ec, l_ec;
138
  uint8_t token_cache[1024];
139 140 141 142 143 144 145 146 147 148 149
  TX_TYPE tx_type = DCT_DCT;
#if CONFIG_CODE_ZEROGROUP
  int last_nz_pos[3] = {-1, -1, -1};  // Encoder only
  int is_eoo_list[3] = {0, 0, 0};
  int is_last_zero[3] = {0, 0, 0};
  int is_eoo_negative[3] = {0, 0, 0};
  int o;
  vp9_zpc_probs *zpc_probs;
  vp9_zpc_count *zpc_count;
  uint8_t token_cache_full[1024];
#endif
150
#if CONFIG_CODE_NONZEROCOUNT
151 152
  const int nzc_used = get_nzc_used(tx_size);
  int zerosleft = 0, nzc = 0;
153 154 155
  if (eob == 0)
    assert(xd->nzcs[ib] == 0);
#endif
156 157 158
#if CONFIG_CODE_ZEROGROUP
  vpx_memset(token_cache, UNKNOWN_TOKEN, sizeof(token_cache));
#endif
159

John Koleszar's avatar
John Koleszar committed
160
  assert((!type && !pb_idx.plane) || (type && pb_idx.plane));
161 162 163 164 165 166 167 168 169 170
  if (sb_type == BLOCK_SIZE_SB64X64) {
    a = (ENTROPY_CONTEXT *)xd->above_context +
                                             vp9_block2above_sb64[tx_size][ib];
    l = (ENTROPY_CONTEXT *)xd->left_context + vp9_block2left_sb64[tx_size][ib];
    a1 = a + sizeof(ENTROPY_CONTEXT_PLANES) / sizeof(ENTROPY_CONTEXT);
    l1 = l + sizeof(ENTROPY_CONTEXT_PLANES) / sizeof(ENTROPY_CONTEXT);
    a2 = a1 + sizeof(ENTROPY_CONTEXT_PLANES) / sizeof(ENTROPY_CONTEXT);
    l2 = l1 + sizeof(ENTROPY_CONTEXT_PLANES) / sizeof(ENTROPY_CONTEXT);
    a3 = a2 + sizeof(ENTROPY_CONTEXT_PLANES) / sizeof(ENTROPY_CONTEXT);
    l3 = l2 + sizeof(ENTROPY_CONTEXT_PLANES) / sizeof(ENTROPY_CONTEXT);
171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188
#if CONFIG_SBSEGMENT
  } else if (sb_type == BLOCK_SIZE_SB32X64) {
    a = (ENTROPY_CONTEXT *)xd->above_context +
                                          vp9_block2above_sb32x64[tx_size][ib];
    l = (ENTROPY_CONTEXT *)xd->left_context +
                                          vp9_block2left_sb32x64[tx_size][ib];
    a1 = a + sizeof(ENTROPY_CONTEXT_PLANES) / sizeof(ENTROPY_CONTEXT);
    l1 = l + sizeof(ENTROPY_CONTEXT_PLANES) / sizeof(ENTROPY_CONTEXT);
    a2 = a3 = l2 = l3 = NULL;
  } else if (sb_type == BLOCK_SIZE_SB64X32) {
    a = (ENTROPY_CONTEXT *)xd->above_context +
                                          vp9_block2above_sb64x32[tx_size][ib];
    l = (ENTROPY_CONTEXT *)xd->left_context +
                                          vp9_block2left_sb64x32[tx_size][ib];
    a1 = a + sizeof(ENTROPY_CONTEXT_PLANES) / sizeof(ENTROPY_CONTEXT);
    l1 = l + sizeof(ENTROPY_CONTEXT_PLANES) / sizeof(ENTROPY_CONTEXT);
    a2 = a3 = l2 = l3 = NULL;
#endif
189 190 191 192 193 194
  } else if (sb_type == BLOCK_SIZE_SB32X32) {
    a = (ENTROPY_CONTEXT *)xd->above_context + vp9_block2above_sb[tx_size][ib];
    l = (ENTROPY_CONTEXT *)xd->left_context + vp9_block2left_sb[tx_size][ib];
    a1 = a + sizeof(ENTROPY_CONTEXT_PLANES) / sizeof(ENTROPY_CONTEXT);
    l1 = l + sizeof(ENTROPY_CONTEXT_PLANES) / sizeof(ENTROPY_CONTEXT);
    a2 = a3 = l2 = l3 = NULL;
195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212
#if CONFIG_SBSEGMENT
  } else if (sb_type == BLOCK_SIZE_SB16X32) {
    a = (ENTROPY_CONTEXT *)xd->above_context +
                                          vp9_block2above_sb16x32[tx_size][ib];
    l = (ENTROPY_CONTEXT *)xd->left_context +
                                          vp9_block2left_sb16x32[tx_size][ib];
    a1 = a + sizeof(ENTROPY_CONTEXT_PLANES) / sizeof(ENTROPY_CONTEXT);
    l1 = l + sizeof(ENTROPY_CONTEXT_PLANES) / sizeof(ENTROPY_CONTEXT);
    a1 = l1 = a2 = l2 = a3 = l3 = NULL;
  } else if (sb_type == BLOCK_SIZE_SB32X16) {
    a = (ENTROPY_CONTEXT *)xd->above_context +
                                          vp9_block2above_sb32x16[tx_size][ib];
    l = (ENTROPY_CONTEXT *)xd->left_context +
                                          vp9_block2left_sb32x16[tx_size][ib];
    a1 = a + sizeof(ENTROPY_CONTEXT_PLANES) / sizeof(ENTROPY_CONTEXT);
    l1 = l + sizeof(ENTROPY_CONTEXT_PLANES) / sizeof(ENTROPY_CONTEXT);
    a1 = l1 = a2 = l2 = a3 = l3 = NULL;
#endif
213
  } else {
214
    assert(sb_type == BLOCK_SIZE_MB16X16);
215 216 217 218
    a = (ENTROPY_CONTEXT *)xd->above_context + vp9_block2above[tx_size][ib];
    l = (ENTROPY_CONTEXT *)xd->left_context + vp9_block2left[tx_size][ib];
    a1 = l1 = a2 = l2 = a3 = l3 = NULL;
  }
219

220 221
  switch (tx_size) {
    default:
222
    case TX_4X4: {
223 224
      tx_type = (type == PLANE_TYPE_Y_WITH_DC) ?
          get_tx_type_4x4(xd, ib) : DCT_DCT;
225 226
      a_ec = *a;
      l_ec = *l;
227
      seg_eob = 16;
228
      scan = vp9_default_zig_zag1d_4x4;
229 230
      if (tx_type != DCT_DCT) {
        if (tx_type == ADST_DCT) {
231
          scan = vp9_row_scan_4x4;
232
        } else if (tx_type == DCT_ADST) {
233
          scan = vp9_col_scan_4x4;
234 235
        }
      }
236
      counts = cpi->coef_counts_4x4;
237 238 239 240 241
      coef_probs = cpi->common.fc.coef_probs_4x4;
#if CONFIG_CODE_ZEROGROUP
      zpc_count = &cpi->common.fc.zpc_counts_4x4;
      zpc_probs = &cpi->common.fc.zpc_probs_4x4;
#endif
242
      break;
243
    }
244
    case TX_8X8: {
245 246
      const int sz = 3 + mb_width_log2(sb_type);
      const int x = ib & ((1 << sz) - 1), y = ib - x;
247 248
      tx_type = (type == PLANE_TYPE_Y_WITH_DC) ?
          get_tx_type_8x8(xd, y + (x >> 1)) : DCT_DCT;
249 250 251 252
      a_ec = (a[0] + a[1]) != 0;
      l_ec = (l[0] + l[1]) != 0;
      seg_eob = 64;
      scan = vp9_default_zig_zag1d_8x8;
253 254 255 256 257 258 259
      if (tx_type != DCT_DCT) {
        if (tx_type == ADST_DCT) {
          scan = vp9_row_scan_8x8;
        } else if (tx_type == DCT_ADST) {
          scan = vp9_col_scan_8x8;
        }
      }
260
      counts = cpi->coef_counts_8x8;
261 262 263 264 265
      coef_probs = cpi->common.fc.coef_probs_8x8;
#if CONFIG_CODE_ZEROGROUP
      zpc_count = &cpi->common.fc.zpc_counts_8x8;
      zpc_probs = &cpi->common.fc.zpc_probs_8x8;
#endif
266
      break;
267 268
    }
    case TX_16X16: {
269 270
      const int sz = 4 + mb_width_log2(sb_type);
      const int x = ib & ((1 << sz) - 1), y = ib - x;
271 272
      tx_type = (type == PLANE_TYPE_Y_WITH_DC) ?
          get_tx_type_16x16(xd, y + (x >> 2)) : DCT_DCT;
Yaowu Xu's avatar
Yaowu Xu committed
273 274 275
      if (type != PLANE_TYPE_UV) {
        a_ec = (a[0] + a[1] + a[2] + a[3]) != 0;
        l_ec = (l[0] + l[1] + l[2] + l[3]) != 0;
276 277 278
      } else {
        a_ec = (a[0] + a[1] + a1[0] + a1[1]) != 0;
        l_ec = (l[0] + l[1] + l1[0] + l1[1]) != 0;
Yaowu Xu's avatar
Yaowu Xu committed
279
      }
280
      seg_eob = 256;
281
      scan = vp9_default_zig_zag1d_16x16;
282 283 284 285 286 287 288
      if (tx_type != DCT_DCT) {
        if (tx_type == ADST_DCT) {
          scan = vp9_row_scan_16x16;
        } else if (tx_type == DCT_ADST) {
          scan = vp9_col_scan_16x16;
        }
      }
289
      counts = cpi->coef_counts_16x16;
290 291 292 293 294
      coef_probs = cpi->common.fc.coef_probs_16x16;
#if CONFIG_CODE_ZEROGROUP
      zpc_count = &cpi->common.fc.zpc_counts_16x16;
      zpc_probs = &cpi->common.fc.zpc_probs_16x16;
#endif
295
      break;
296
    }
297
    case TX_32X32:
298 299 300 301 302 303 304 305 306 307 308
      if (type != PLANE_TYPE_UV) {
        a_ec = (a[0] + a[1] + a[2] + a[3] +
                a1[0] + a1[1] + a1[2] + a1[3]) != 0;
        l_ec = (l[0] + l[1] + l[2] + l[3] +
                l1[0] + l1[1] + l1[2] + l1[3]) != 0;
      } else {
        a_ec = (a[0] + a[1] + a1[0] + a1[1] +
                a2[0] + a2[1] + a3[0] + a3[1]) != 0;
        l_ec = (l[0] + l[1] + l1[0] + l1[1] +
                l2[0] + l2[1] + l3[0] + l3[1]) != 0;
      }
309 310 311
      seg_eob = 1024;
      scan = vp9_default_zig_zag1d_32x32;
      counts = cpi->coef_counts_32x32;
312 313 314 315 316
      coef_probs = cpi->common.fc.coef_probs_32x32;
#if CONFIG_CODE_ZEROGROUP
      zpc_count = &cpi->common.fc.zpc_counts_32x32;
      zpc_probs = &cpi->common.fc.zpc_probs_32x32;
#endif
317
      break;
John Koleszar's avatar
John Koleszar committed
318 319
  }

320
  pt = combine_entropy_contexts(a_ec, l_ec);
321 322
  nb = vp9_get_coef_neighbors_handle(scan, &pad);
  default_eob = seg_eob;
Yaowu Xu's avatar
Yaowu Xu committed
323

Paul Wilkins's avatar
Paul Wilkins committed
324 325
  if (vp9_segfeature_active(xd, segment_id, SEG_LVL_SKIP))
    seg_eob = 0;
John Koleszar's avatar
John Koleszar committed
326

327 328 329 330 331 332 333 334 335 336 337 338
#if CONFIG_CODE_ZEROGROUP
  vpx_memset(token_cache_full, ZERO_TOKEN, sizeof(token_cache_full));
  for (c = 0; c < eob; ++c) {
    rc = scan[c];
    token_cache_full[rc] = vp9_dct_value_tokens_ptr[qcoeff_ptr[rc]].token;
    o = vp9_get_orientation(rc, tx_size);
    if (qcoeff_ptr[rc] != 0) {
      last_nz_pos[o] = c;
    }
  }
#endif
  c = 0;
339
  do {
340
    const int band = get_coef_band(scan, tx_size, c);
341
    int token;
342
    int v = 0;
343 344 345
    rc = scan[c];
    if (c)
      pt = vp9_get_coef_context(scan, nb, pad, token_cache, c, default_eob);
346
#if CONFIG_CODE_NONZEROCOUNT
347 348
    if (nzc_used)
      zerosleft = seg_eob - xd->nzcs[ib] - c + nzc;
349
#endif
350
    if (c < eob) {
351
      v = qcoeff_ptr[rc];
352 353
      assert(-DCT_MAX_VALUE <= v  &&  v < DCT_MAX_VALUE);

354 355
      t->extra = vp9_dct_value_tokens_ptr[v].extra;
      token    = vp9_dct_value_tokens_ptr[v].token;
356
    } else {
357
#if CONFIG_CODE_NONZEROCOUNT
358 359 360
      if (nzc_used)
        break;
      else
361
#endif
362
        token = DCT_EOB_TOKEN;
363
    }
John Koleszar's avatar
John Koleszar committed
364

365
    t->token = token;
366
    t->context_tree = coef_probs[type][ref][band][pt];
367 368
#if CONFIG_CODE_NONZEROCOUNT
    // Skip zero node if there are no zeros left
369 370 371
    if (nzc_used)
      t->skip_eob_node = 1 + (zerosleft == 0);
    else
372
#endif
373
      t->skip_eob_node = (c > 0) && (token_cache[scan[c - 1]] == 0);
374
    assert(vp9_coef_encodings[t->token].len - t->skip_eob_node > 0);
375 376 377 378 379 380 381 382 383 384 385 386 387 388
#if CONFIG_CODE_ZEROGROUP
    o = vp9_get_orientation(rc, tx_size);
    t->skip_coef_val = (token_cache[rc] == ZERO_TOKEN || is_eoo_list[o]);
    if (t->skip_coef_val) {
      assert(v == 0);
    }
    // No need to transmit any token
    if (t->skip_eob_node && t->skip_coef_val) {
      assert(token == ZERO_TOKEN);
      is_last_zero[o] = 1;
      token_cache[scan[c]] = ZERO_TOKEN;
      continue;
    }
#endif
389
    if (!dry_run) {
390
      ++counts[type][ref][band][pt][token];
391 392
      if (!t->skip_eob_node)
        ++cpi->common.fc.eob_branch_counts[tx_size][type][ref][band][pt];
393
    }
394 395 396
#if CONFIG_CODE_NONZEROCOUNT
    nzc += (v != 0);
#endif
397 398 399 400 401 402 403 404 405 406 407 408 409 410 411 412 413 414 415 416 417 418 419 420 421 422 423 424 425 426 427 428 429 430 431 432 433 434 435 436 437 438 439 440 441 442 443 444 445 446 447 448 449 450 451 452 453 454 455 456 457 458 459 460 461 462 463 464 465
    token_cache[scan[c]] = token;
#if CONFIG_CODE_ZEROGROUP
    if (token == ZERO_TOKEN && !t->skip_coef_val) {
      int eoo = 0, use_eoo;
#if USE_ZPC_EOORIENT == 1
      use_eoo = vp9_use_eoo(c, seg_eob, scan, tx_size,
                            is_last_zero, is_eoo_list);
#else
      use_eoo = 0;
#endif
      if (use_eoo) {
        eoo = vp9_is_eoo(c, eob, scan, tx_size, qcoeff_ptr, last_nz_pos);
        if (eoo && is_eoo_negative[o]) eoo = 0;
        if (eoo) {
          int c_;
          int savings = 0;
          int zsaved = 0;
          savings =
              vp9_cost_bit((*zpc_probs)[ref]
                           [coef_to_zpc_band(band)]
                           [coef_to_zpc_ptok(pt)][0], 1) -
              vp9_cost_bit((*zpc_probs)[ref]
                           [coef_to_zpc_band(band)]
                           [coef_to_zpc_ptok(pt)][0], 0);
          for (c_ = c + 1; c_ < eob; ++c_) {
            if (o == vp9_get_orientation(scan[c_], tx_size)) {
              int pt_ = vp9_get_coef_context(scan, nb, pad, token_cache_full,
                                             c_, default_eob);
              int band_ = get_coef_band(scan, tx_size, c_);
              assert(token_cache_full[scan[c_]] == ZERO_TOKEN);
              if (!c_ || token_cache_full[scan[c_ - 1]])
                savings +=
                    vp9_cost_bit(coef_probs[type][ref][band_][pt_][0], 1);
              savings += vp9_cost_bit(coef_probs[type][ref][band_][pt_][1], 0);
              zsaved++;
            }
          }
          /*
          if (!dry_run)
            if (savings > 0)
              printf("savings %d zsaved %d (%d, %d)\n",
                     savings, zsaved, tx_size, band);
                     */
          if (savings < 0) {
            eoo = 0;
            is_eoo_negative[o] = 1;
          }
        }
      }
      if (use_eoo) {
        t++;
        t->skip_eob_node = t->skip_coef_val = 0;
        // transmit the eoo symbol
        t->token = !eoo ? ZPC_ISOLATED : ZPC_EOORIENT;
        t->context_tree = &((*zpc_probs)[ref]
                            [coef_to_zpc_band(band)]
                            [coef_to_zpc_ptok(pt)][0]);
        if (!dry_run)
          (*zpc_count)[ref]
              [coef_to_zpc_band(band)]
              [coef_to_zpc_ptok(pt)][0][!eoo]++;
        if (eoo) {
          assert(is_eoo_list[o] == 0);
          is_eoo_list[o] = 1;
        }
      }
    }
    is_last_zero[o] = (token == ZERO_TOKEN);
#endif
466
    ++t;
467
} while (c < eob && ++c < seg_eob);
468
#if CONFIG_CODE_NONZEROCOUNT
469
assert(nzc == xd->nzcs[ib]);
470
#endif
471 472

  *tp = t;
473
  a_ec = l_ec = (c > 0); /* 0 <-> all coeff data is zero */
Yaowu Xu's avatar
Yaowu Xu committed
474 475 476
  a[0] = a_ec;
  l[0] = l_ec;

477
  if (tx_size == TX_8X8) {
Yaowu Xu's avatar
Yaowu Xu committed
478 479 480
    a[1] = a_ec;
    l[1] = l_ec;
  } else if (tx_size == TX_16X16) {
Yaowu Xu's avatar
Yaowu Xu committed
481 482 483 484
    if (type != PLANE_TYPE_UV) {
      a[1] = a[2] = a[3] = a_ec;
      l[1] = l[2] = l[3] = l_ec;
    } else {
485 486
      a1[0] = a1[1] = a[1] = a_ec;
      l1[0] = l1[1] = l[1] = l_ec;
Yaowu Xu's avatar
Yaowu Xu committed
487
    }
488
  } else if (tx_size == TX_32X32) {
489 490 491 492 493 494 495 496 497 498 499
    if (type != PLANE_TYPE_UV) {
      a[1] = a[2] = a[3] = a_ec;
      l[1] = l[2] = l[3] = l_ec;
      a1[0] = a1[1] = a1[2] = a1[3] = a_ec;
      l1[0] = l1[1] = l1[2] = l1[3] = l_ec;
    } else {
      a[1] = a1[0] = a1[1] = a_ec;
      l[1] = l1[0] = l1[1] = l_ec;
      a2[0] = a2[1] = a3[0] = a3[1] = a_ec;
      l2[0] = l2[1] = l3[0] = l3[1] = l_ec;
    }
Yaowu Xu's avatar
Yaowu Xu committed
500
  }
John Koleszar's avatar
John Koleszar committed
501 502
}

503 504 505 506 507
struct is_skippable_args {
  MACROBLOCKD *xd;
  int *skippable;
};
static void is_skippable(int plane, int block,
508
                         BLOCK_SIZE_TYPE bsize, int ss_txfrm_size, void *argv) {
509 510
  struct is_skippable_args *args = argv;
  args->skippable[0] &= (!args->xd->plane[plane].eobs[block]);
Deb Mukherjee's avatar
Deb Mukherjee committed
511 512
}

513 514 515
int vp9_sb_is_skippable(MACROBLOCKD *xd, BLOCK_SIZE_TYPE bsize) {
  int result = 1;
  struct is_skippable_args args = {xd, &result};
516
  foreach_transformed_block(xd, bsize, is_skippable, &args);
517
  return result;
518 519
}

520 521 522
int vp9_sby_is_skippable(MACROBLOCKD *xd, BLOCK_SIZE_TYPE bsize) {
  int result = 1;
  struct is_skippable_args args = {xd, &result};
523
  foreach_transformed_block_in_plane(xd, bsize, 0, 0, is_skippable, &args);
524
  return result;
525 526
}

527 528 529
int vp9_sbuv_is_skippable(MACROBLOCKD *xd, BLOCK_SIZE_TYPE bsize) {
  int result = 1;
  struct is_skippable_args args = {xd, &result};
530
  foreach_transformed_block_uv(xd, bsize, is_skippable, &args);
531
  return result;
532 533
}

534 535 536
void vp9_tokenize_sb(VP9_COMP *cpi,
                     MACROBLOCKD *xd,
                     TOKENEXTRA **t,
537 538
                     int dry_run, BLOCK_SIZE_TYPE bsize) {
  const int bwl = mb_width_log2(bsize) + 2, bhl = mb_height_log2(bsize) + 2;
539 540 541 542 543
  VP9_COMMON * const cm = &cpi->common;
  MB_MODE_INFO * const mbmi = &xd->mode_info_context->mbmi;
  TOKENEXTRA *t_backup = *t;
  const int mb_skip_context = vp9_get_pred_context(cm, xd, PRED_MBSKIP);
  const int segment_id = mbmi->segment_id;
Paul Wilkins's avatar
Paul Wilkins committed
544
  const int skip_inc = !vp9_segfeature_active(xd, segment_id, SEG_LVL_SKIP);
545 546 547 548 549
  const TX_SIZE txfm_size = mbmi->txfm_size;
  const TX_SIZE uv_txfm_size = (bsize < BLOCK_SIZE_SB32X32 &&
                                txfm_size == TX_16X16) ? TX_8X8 :
                               (bsize < BLOCK_SIZE_SB64X64 &&
                                txfm_size == TX_32X32) ? TX_16X16 : txfm_size;
550
  int b;
551
  const int n_y = (1 << (bwl + bhl)), n_uv = (n_y * 3) >> 1;
552

553
  mbmi->mb_skip_coeff = vp9_sb_is_skippable(xd, bsize);
554 555 556 557

  if (mbmi->mb_skip_coeff) {
    if (!dry_run)
      cpi->skip_true_count[mb_skip_context] += skip_inc;
558
    vp9_reset_sb_tokens_context(xd, bsize);
559 560 561 562 563 564 565 566
    if (dry_run)
      *t = t_backup;
    return;
  }

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

567
  switch (txfm_size) {
568
    case TX_32X32:
569
      for (b = 0; b < n_y; b += 64)
570
        tokenize_b(cpi, xd, b, t, PLANE_TYPE_Y_WITH_DC,
571 572 573 574 575 576 577 578 579 580 581 582
                   TX_32X32, n_y, dry_run);
      if (uv_txfm_size == TX_32X32) {
        assert(bsize == BLOCK_SIZE_SB64X64);
        tokenize_b(cpi, xd, 256, t, PLANE_TYPE_UV,
                   TX_32X32, n_y, dry_run);
        tokenize_b(cpi, xd, 320, t, PLANE_TYPE_UV,
                   TX_32X32, n_y, dry_run);
      } else {
        for (; b < n_uv; b += 16)
          tokenize_b(cpi, xd, b, t, PLANE_TYPE_UV,
                     TX_16X16, n_y, dry_run);
      }
583 584
      break;
    case TX_16X16:
585
      for (b = 0; b < n_y; b += 16)
586
        tokenize_b(cpi, xd, b, t, PLANE_TYPE_Y_WITH_DC,
587 588 589 590 591 592 593 594 595 596
                   TX_16X16, n_y, dry_run);
      if (uv_txfm_size == TX_16X16) {
        for (; b < n_uv; b += 16)
          tokenize_b(cpi, xd, b, t, PLANE_TYPE_UV,
                     TX_16X16, n_y, dry_run);
      } else {
        for (; b < n_uv; b += 4)
          tokenize_b(cpi, xd, b, t, PLANE_TYPE_UV,
                     TX_8X8, n_y, dry_run);
      }
597 598
      break;
    case TX_8X8:
599
      for (b = 0; b < n_y; b += 4)
600
        tokenize_b(cpi, xd, b, t, PLANE_TYPE_Y_WITH_DC,
601 602
                   TX_8X8, n_y, dry_run);
      for (; b < n_uv; b += 4)
603
        tokenize_b(cpi, xd, b, t, PLANE_TYPE_UV,
604
                   TX_8X8, n_y, dry_run);
605 606
      break;
    case TX_4X4:
607
      for (b = 0; b < n_y; b++)
608
        tokenize_b(cpi, xd, b, t, PLANE_TYPE_Y_WITH_DC,
609 610
                   TX_4X4, n_y, dry_run);
      for (; b < n_uv; b++)
611
        tokenize_b(cpi, xd, b, t, PLANE_TYPE_UV,
612
                   TX_4X4, n_y, dry_run);
613 614
      break;
    default: assert(0);
615
  }
616

617 618 619 620
  if (dry_run)
    *t = t_backup;
}

621
void vp9_tokenize_mb(VP9_COMP *cpi,
Paul Wilkins's avatar
Paul Wilkins committed
622
                     MACROBLOCKD *xd,
623 624
                     TOKENEXTRA **t,
                     int dry_run) {
John Koleszar's avatar
John Koleszar committed
625
  int b;
626
  int tx_size = xd->mode_info_context->mbmi.txfm_size;
Paul Wilkins's avatar
Paul Wilkins committed
627
  int mb_skip_context = vp9_get_pred_context(&cpi->common, xd, PRED_MBSKIP);
628
  TOKENEXTRA *t_backup = *t;
Paul Wilkins's avatar
Paul Wilkins committed
629

John Koleszar's avatar
John Koleszar committed
630 631 632 633
  // 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
634
  int segment_id = xd->mode_info_context->mbmi.segment_id;
635

Paul Wilkins's avatar
Paul Wilkins committed
636
  if (!vp9_segfeature_active(xd, segment_id, SEG_LVL_SKIP)) {
John Koleszar's avatar
John Koleszar committed
637 638 639
    skip_inc = 1;
  } else
    skip_inc = 0;
640

641 642
  xd->mode_info_context->mbmi.mb_skip_coeff = vp9_sb_is_skippable(xd,
                                                  BLOCK_SIZE_MB16X16);
643

Paul Wilkins's avatar
Paul Wilkins committed
644
  if (xd->mode_info_context->mbmi.mb_skip_coeff) {
645 646
    if (!dry_run)
      cpi->skip_true_count[mb_skip_context] += skip_inc;
647
    vp9_reset_sb_tokens_context(xd, BLOCK_SIZE_MB16X16);
Yaowu Xu's avatar
Yaowu Xu committed
648

649 650
    if (dry_run)
      *t = t_backup;
John Koleszar's avatar
John Koleszar committed
651 652 653
    return;
  }

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

657
  if (tx_size == TX_16X16) {
John Koleszar's avatar
John Koleszar committed
658
    tokenize_b(cpi, xd, 0, t, PLANE_TYPE_Y_WITH_DC, TX_16X16, 16, dry_run);
Daniel Kang's avatar
Daniel Kang committed
659
    for (b = 16; b < 24; b += 4) {
John Koleszar's avatar
John Koleszar committed
660
      tokenize_b(cpi, xd, b, t, PLANE_TYPE_UV, TX_8X8, 16, dry_run);
Daniel Kang's avatar
Daniel Kang committed
661
    }
662
  } else if (tx_size == TX_8X8) {
John Koleszar's avatar
John Koleszar committed
663
    for (b = 0; b < 16; b += 4) {
John Koleszar's avatar
John Koleszar committed
664
      tokenize_b(cpi, xd, b, t, PLANE_TYPE_Y_WITH_DC, TX_8X8, 16, dry_run);
John Koleszar's avatar
John Koleszar committed
665
    }
666 667
    if (xd->mode_info_context->mbmi.mode == I8X8_PRED ||
        xd->mode_info_context->mbmi.mode == SPLITMV) {
668
      for (b = 16; b < 24; b++) {
John Koleszar's avatar
John Koleszar committed
669
        tokenize_b(cpi, xd, b, t, PLANE_TYPE_UV, TX_4X4, 16, dry_run);
670
      }
671
    } else {
Deb Mukherjee's avatar
Deb Mukherjee committed
672
      for (b = 16; b < 24; b += 4) {
John Koleszar's avatar
John Koleszar committed
673
        tokenize_b(cpi, xd, b, t, PLANE_TYPE_UV, TX_8X8, 16, dry_run);
Deb Mukherjee's avatar
Deb Mukherjee committed
674
      }
675
    }
Jingning Han's avatar
Jingning Han committed
676
  } else {
677
    for (b = 0; b < 16; b++)
John Koleszar's avatar
John Koleszar committed
678
      tokenize_b(cpi, xd, b, t, PLANE_TYPE_Y_WITH_DC, TX_4X4, 16, dry_run);
679
    for (b = 16; b < 24; b++)
John Koleszar's avatar
John Koleszar committed
680
      tokenize_b(cpi, xd, b, t, PLANE_TYPE_UV, TX_4X4, 16, dry_run);
Jingning Han's avatar
Jingning Han committed
681
  }
682 683
  if (dry_run)
    *t = t_backup;
John Koleszar's avatar
John Koleszar committed
684
}
685

John Koleszar's avatar
John Koleszar committed
686
#ifdef ENTROPY_STATS
John Koleszar's avatar
John Koleszar committed
687 688 689
void init_context_counters(void) {
  FILE *f = fopen("context.bin", "rb");
  if (!f) {
690
    vpx_memset(context_counters_4x4, 0, sizeof(context_counters_4x4));
John Koleszar's avatar
John Koleszar committed
691
    vpx_memset(context_counters_8x8, 0, sizeof(context_counters_8x8));
Daniel Kang's avatar
Daniel Kang committed
692
    vpx_memset(context_counters_16x16, 0, sizeof(context_counters_16x16));
693
    vpx_memset(context_counters_32x32, 0, sizeof(context_counters_32x32));
John Koleszar's avatar
John Koleszar committed
694
  } else {
695
    fread(context_counters_4x4, sizeof(context_counters_4x4), 1, f);
John Koleszar's avatar
John Koleszar committed
696
    fread(context_counters_8x8, sizeof(context_counters_8x8), 1, f);
Daniel Kang's avatar
Daniel Kang committed
697
    fread(context_counters_16x16, sizeof(context_counters_16x16), 1, f);
698
    fread(context_counters_32x32, sizeof(context_counters_32x32), 1, f);
John Koleszar's avatar
John Koleszar committed
699 700 701 702 703
    fclose(f);
  }

  f = fopen("treeupdate.bin", "rb");
  if (!f) {
704
    vpx_memset(tree_update_hist_4x4, 0, sizeof(tree_update_hist_4x4));
John Koleszar's avatar
John Koleszar committed
705
    vpx_memset(tree_update_hist_8x8, 0, sizeof(tree_update_hist_8x8));
Daniel Kang's avatar
Daniel Kang committed
706
    vpx_memset(tree_update_hist_16x16, 0, sizeof(tree_update_hist_16x16));
707
    vpx_memset(tree_update_hist_32x32, 0, sizeof(tree_update_hist_32x32));
John Koleszar's avatar
John Koleszar committed
708
  } else {
709
    fread(tree_update_hist_4x4, sizeof(tree_update_hist_4x4), 1, f);
John Koleszar's avatar
John Koleszar committed
710
    fread(tree_update_hist_8x8, sizeof(tree_update_hist_8x8), 1, f);
Daniel Kang's avatar
Daniel Kang committed
711
    fread(tree_update_hist_16x16, sizeof(tree_update_hist_16x16), 1, f);
712
    fread(tree_update_hist_32x32, sizeof(tree_update_hist_32x32), 1, f);
John Koleszar's avatar
John Koleszar committed
713 714
    fclose(f);
  }
John Koleszar's avatar
John Koleszar committed
715 716
}

717 718
static void print_counter(FILE *f, vp9_coeff_accum *context_counters,
                          int block_types, const char *header) {
719
  int type, ref, band, pt, t;
John Koleszar's avatar
John Koleszar committed
720

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

723
#define Comma(X) (X ? "," : "")
John Koleszar's avatar
John Koleszar committed
724 725
  type = 0;
  do {
726
    ref = 0;
John Koleszar's avatar
John Koleszar committed
727 728
    fprintf(f, "%s\n  { /* block Type %d */", Comma(type), type);
    do {
729 730
      fprintf(f, "%s\n    { /* %s */", Comma(type), ref ? "Inter" : "Intra");
      band = 0;
John Koleszar's avatar
John Koleszar committed
731
      do {
732 733
        fprintf(f, "%s\n      { /* Coeff Band %d */", Comma(band), band);
        pt = 0;
John Koleszar's avatar
John Koleszar committed
734
        do {
735 736 737 738 739 740 741 742 743
          fprintf(f, "%s\n        {", Comma(pt));

          t = 0;
          do {
            const int64_t x = context_counters[type][ref][band][pt][t];
            const int y = (int) x;

            assert(x == (int64_t) y);  /* no overflow handling yet */
            fprintf(f, "%s %d", Comma(t), y);
744
          } while (++t < 1 + MAX_ENTROPY_TOKENS);
745 746 747 748
          fprintf(f, "}");
        } while (++pt < PREV_COEF_CONTEXTS);
        fprintf(f, "\n      }");
      } while (++band < COEF_BANDS);
John Koleszar's avatar
John Koleszar committed
749
      fprintf(f, "\n    }");
750
    } while (++ref < REF_TYPES);
John Koleszar's avatar
John Koleszar committed
751
    fprintf(f, "\n  }");
752
  } while (++type < block_types);
Daniel Kang's avatar
Daniel Kang committed
753
  fprintf(f, "\n};\n");
754
}
755

756 757
static void print_probs(FILE *f, vp9_coeff_accum *context_counters,
                        int block_types, const char *header) {
758
  int type, ref, band, pt, t;
Daniel Kang's avatar
Daniel Kang committed
759

760
  fprintf(f, "static const vp9_coeff_probs %s = {", header);
761

John Koleszar's avatar
John Koleszar committed
762
  type = 0;
763
#define Newline(x, spaces) (x ? " " : "\n" spaces)
John Koleszar's avatar
John Koleszar committed
764
  do {
765 766
    fprintf(f, "%s%s{ /* block Type %d */",
            Comma(type), Newline(type, "  "), type);
767
    ref = 0;
John Koleszar's avatar
John Koleszar committed
768
    do {
769 770 771
      fprintf(f, "%s%s{ /* %s */",
              Comma(band), Newline(band, "    "), ref ? "Inter" : "Intra");
      band = 0;
John Koleszar's avatar
John Koleszar committed
772
      do {
773 774 775
        fprintf(f, "%s%s{ /* Coeff Band %d */",
                Comma(band), Newline(band, "      "), band);
        pt = 0;
John Koleszar's avatar
John Koleszar committed
776
        do {
777
          unsigned int branch_ct[ENTROPY_NODES][2];
778
          unsigned int coef_counts[MAX_ENTROPY_TOKENS + 1];
779 780
          vp9_prob coef_probs[ENTROPY_NODES];

781 782 783
          if (pt >= 3 && band == 0)
            break;
          for (t = 0; t < MAX_ENTROPY_TOKENS + 1; ++t)
784
            coef_counts[t] = context_counters[type][ref][band][pt][t];
785 786
          vp9_tree_probs_from_distribution(vp9_coef_tree, coef_probs,
                                           branch_ct, coef_counts, 0);
787 788
          branch_ct[0][1] = coef_counts[MAX_ENTROPY_TOKENS] - branch_ct[0][0];
          coef_probs[0] = get_binary_prob(branch_ct[0][0], branch_ct[0][1]);
789 790 791 792 793 794 795 796 797 798 799
          fprintf(f, "%s\n      {", Comma(pt));

          t = 0;
          do {
            fprintf(f, "%s %3d", Comma(t), coef_probs[t]);
          } while (++t < ENTROPY_NODES);

          fprintf(f, " }");
        } while (++pt < PREV_COEF_CONTEXTS);
        fprintf(f, "\n      }");
      } while (++band < COEF_BANDS);
John Koleszar's avatar
John Koleszar committed
800
      fprintf(f, "\n    }");
801
    } while (++ref < REF_TYPES);
John Koleszar's avatar
John Koleszar committed
802
    fprintf(f, "\n  }");
803
  } while (++type < block_types);
John Koleszar's avatar
John Koleszar committed
804
  fprintf(f, "\n};\n");
805
}
806

807 808
void print_context_counters() {
  FILE *f = fopen("vp9_context.c", "w");
809

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

Ronald S. Bultje's avatar