vp9_tokenize.c 26.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 */

John Koleszar's avatar
John Koleszar committed
39
static TOKENVALUE dct_value_tokens[DCT_MAX_VALUE * 2];
40
const TOKENVALUE *vp9_dct_value_tokens_ptr;
John Koleszar's avatar
John Koleszar committed
41
static int dct_value_cost[DCT_MAX_VALUE * 2];
42
const int *vp9_dct_value_cost_ptr;
43

John Koleszar's avatar
John Koleszar committed
44
static void fill_value_tokens() {
John Koleszar's avatar
John Koleszar committed
45

John Koleszar's avatar
John Koleszar committed
46
  TOKENVALUE *const t = dct_value_tokens + DCT_MAX_VALUE;
47
  vp9_extra_bit *const e = vp9_extra_bits;
John Koleszar's avatar
John Koleszar committed
48

John Koleszar's avatar
John Koleszar committed
49
50
  int i = -DCT_MAX_VALUE;
  int sign = 1;
John Koleszar's avatar
John Koleszar committed
51

John Koleszar's avatar
John Koleszar committed
52
53
54
  do {
    if (!i)
      sign = 0;
John Koleszar's avatar
John Koleszar committed
55

John Koleszar's avatar
John Koleszar committed
56
57
58
    {
      const int a = sign ? -i : i;
      int eb = sign;
John Koleszar's avatar
John Koleszar committed
59

John Koleszar's avatar
John Koleszar committed
60
61
      if (a > 4) {
        int j = 4;
John Koleszar's avatar
John Koleszar committed
62

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

65
        t[i].token = --j;
John Koleszar's avatar
John Koleszar committed
66
67
        eb |= (a - e[j].base_val) << 1;
      } else
68
        t[i].token = a;
John Koleszar's avatar
John Koleszar committed
69

70
      t[i].extra = eb;
John Koleszar's avatar
John Koleszar committed
71
    }
John Koleszar's avatar
John Koleszar committed
72

John Koleszar's avatar
John Koleszar committed
73
74
75
    // initialize the cost for extra bits for all possible coefficient value.
    {
      int cost = 0;
76
      vp9_extra_bit *p = vp9_extra_bits + t[i].token;
John Koleszar's avatar
John Koleszar committed
77

John Koleszar's avatar
John Koleszar committed
78
      if (p->base_val) {
79
        const int extra = t[i].extra;
80
        const int length = p->len;
John Koleszar's avatar
John Koleszar committed
81

82
83
        if (length)
          cost += treed_cost(p->tree, p->prob, extra >> 1, length);
John Koleszar's avatar
John Koleszar committed
84

85
        cost += vp9_cost_bit(vp9_prob_half, extra & 1); /* sign */
John Koleszar's avatar
John Koleszar committed
86
87
        dct_value_cost[i + DCT_MAX_VALUE] = cost;
      }
John Koleszar's avatar
John Koleszar committed
88
89
90

    }

John Koleszar's avatar
John Koleszar committed
91
92
  } while (++i < DCT_MAX_VALUE);

93
94
  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
95
}
96

97
98
extern const int *vp9_get_coef_neighbors_handle(const int *scan, int *pad);

99
static void tokenize_b(VP9_COMP *cpi,
100
                       MACROBLOCKD *xd,
Yaowu Xu's avatar
Yaowu Xu committed
101
                       const int ib,
102
103
104
                       TOKENEXTRA **tp,
                       PLANE_TYPE type,
                       TX_SIZE tx_size,
John Koleszar's avatar
John Koleszar committed
105
                       int y_blocks,
106
                       int dry_run) {
107
  MB_MODE_INFO *mbmi = &xd->mode_info_context->mbmi;
Daniel Kang's avatar
Daniel Kang committed
108
  int pt; /* near block/prev token context index */
109
  int c = 0, rc = 0;
Daniel Kang's avatar
Daniel Kang committed
110
  TOKENEXTRA *t = *tp;        /* store tokens starting here */
John Koleszar's avatar
John Koleszar committed
111
112
  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];
113
114
  const int16_t *qcoeff_ptr = BLOCK_OFFSET(xd->plane[pb_idx.plane].qcoeff,
                                           pb_idx.block, 16);
115
  int seg_eob, default_eob, pad;
116
117
  const int segment_id = mbmi->segment_id;
  const BLOCK_SIZE_TYPE sb_type = mbmi->sb_type;
118
  const int *scan, *nb;
119
  vp9_coeff_count *counts;
120
  vp9_coeff_probs *coef_probs;
121
122
  const int ref = mbmi->ref_frame != INTRA_FRAME;
  ENTROPY_CONTEXT *a, *l, *a1, *l1, *a2, *l2, *a3, *l3, a_ec, l_ec;
123
  uint8_t token_cache[1024];
124
125
126
127
128
129
130
131
132
133
134
135
136
137
  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
#if CONFIG_CODE_ZEROGROUP
  vpx_memset(token_cache, UNKNOWN_TOKEN, sizeof(token_cache));
#endif
138

John Koleszar's avatar
John Koleszar committed
139
  assert((!type && !pb_idx.plane) || (type && pb_idx.plane));
140
141
142
143
144
145
146
147
148
149
  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);
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
  } 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;
166
167
168
169
170
171
  } 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;
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
  } 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;
188
  } else {
189
    assert(sb_type == BLOCK_SIZE_MB16X16);
190
191
192
193
    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;
  }
194

195
196
  switch (tx_size) {
    default:
197
    case TX_4X4: {
198
199
      tx_type = (type == PLANE_TYPE_Y_WITH_DC) ?
          get_tx_type_4x4(xd, ib) : DCT_DCT;
200
201
      a_ec = *a;
      l_ec = *l;
202
      seg_eob = 16;
203
      scan = get_scan_4x4(tx_type);
204
      counts = cpi->coef_counts_4x4;
205
206
207
208
209
      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
210
      break;
211
    }
212
    case TX_8X8: {
213
214
      const int sz = 3 + mb_width_log2(sb_type);
      const int x = ib & ((1 << sz) - 1), y = ib - x;
215
216
      tx_type = (type == PLANE_TYPE_Y_WITH_DC) ?
          get_tx_type_8x8(xd, y + (x >> 1)) : DCT_DCT;
217
218
219
      a_ec = (a[0] + a[1]) != 0;
      l_ec = (l[0] + l[1]) != 0;
      seg_eob = 64;
220
      scan = get_scan_8x8(tx_type);
221
      counts = cpi->coef_counts_8x8;
222
223
224
225
226
      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
227
      break;
228
229
    }
    case TX_16X16: {
230
231
      const int sz = 4 + mb_width_log2(sb_type);
      const int x = ib & ((1 << sz) - 1), y = ib - x;
232
233
      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
234
235
236
      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;
237
238
239
      } 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
240
      }
241
      seg_eob = 256;
242
      scan = get_scan_16x16(tx_type);
243
      counts = cpi->coef_counts_16x16;
244
245
246
247
248
      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
249
      break;
250
    }
251
    case TX_32X32:
252
253
254
255
256
257
258
259
260
261
262
      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;
      }
263
264
265
      seg_eob = 1024;
      scan = vp9_default_zig_zag1d_32x32;
      counts = cpi->coef_counts_32x32;
266
267
268
269
270
      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
271
      break;
John Koleszar's avatar
John Koleszar committed
272
273
  }

274
  pt = combine_entropy_contexts(a_ec, l_ec);
275
276
  nb = vp9_get_coef_neighbors_handle(scan, &pad);
  default_eob = seg_eob;
Yaowu Xu's avatar
Yaowu Xu committed
277

Paul Wilkins's avatar
Paul Wilkins committed
278
279
  if (vp9_segfeature_active(xd, segment_id, SEG_LVL_SKIP))
    seg_eob = 0;
John Koleszar's avatar
John Koleszar committed
280

281
282
283
284
285
286
287
288
289
290
291
292
#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;
293
  do {
294
    const int band = get_coef_band(scan, tx_size, c);
295
    int token;
296
    int v = 0;
297
298
299
    rc = scan[c];
    if (c)
      pt = vp9_get_coef_context(scan, nb, pad, token_cache, c, default_eob);
300
    if (c < eob) {
301
      v = qcoeff_ptr[rc];
302
303
      assert(-DCT_MAX_VALUE <= v  &&  v < DCT_MAX_VALUE);

304
305
      t->extra = vp9_dct_value_tokens_ptr[v].extra;
      token    = vp9_dct_value_tokens_ptr[v].token;
306
    } else {
307
      token = DCT_EOB_TOKEN;
308
    }
John Koleszar's avatar
John Koleszar committed
309

310
    t->token = token;
311
312
    t->context_tree = coef_probs[type][ref][band][pt];
      t->skip_eob_node = (c > 0) && (token_cache[scan[c - 1]] == 0);
313
    assert(vp9_coef_encodings[t->token].len - t->skip_eob_node > 0);
314
315
316
317
318
319
320
321
322
323
324
325
326
327
#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
328
    if (!dry_run) {
329
      ++counts[type][ref][band][pt][token];
330
331
      if (!t->skip_eob_node)
        ++cpi->common.fc.eob_branch_counts[tx_size][type][ref][band][pt];
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
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
    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
402
    ++t;
403
  } while (c < eob && ++c < seg_eob);
404
405

  *tp = t;
406
  a_ec = l_ec = (c > 0); /* 0 <-> all coeff data is zero */
Yaowu Xu's avatar
Yaowu Xu committed
407
408
409
  a[0] = a_ec;
  l[0] = l_ec;

410
  if (tx_size == TX_8X8) {
Yaowu Xu's avatar
Yaowu Xu committed
411
412
413
    a[1] = a_ec;
    l[1] = l_ec;
  } else if (tx_size == TX_16X16) {
Yaowu Xu's avatar
Yaowu Xu committed
414
415
416
417
    if (type != PLANE_TYPE_UV) {
      a[1] = a[2] = a[3] = a_ec;
      l[1] = l[2] = l[3] = l_ec;
    } else {
418
419
      a1[0] = a1[1] = a[1] = a_ec;
      l1[0] = l1[1] = l[1] = l_ec;
Yaowu Xu's avatar
Yaowu Xu committed
420
    }
421
  } else if (tx_size == TX_32X32) {
422
423
424
425
426
427
428
429
430
431
432
    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
433
  }
John Koleszar's avatar
John Koleszar committed
434
435
}

436
437
438
439
440
struct is_skippable_args {
  MACROBLOCKD *xd;
  int *skippable;
};
static void is_skippable(int plane, int block,
441
                         BLOCK_SIZE_TYPE bsize, int ss_txfrm_size, void *argv) {
442
443
  struct is_skippable_args *args = argv;
  args->skippable[0] &= (!args->xd->plane[plane].eobs[block]);
Deb Mukherjee's avatar
Deb Mukherjee committed
444
445
}

446
447
448
int vp9_sb_is_skippable(MACROBLOCKD *xd, BLOCK_SIZE_TYPE bsize) {
  int result = 1;
  struct is_skippable_args args = {xd, &result};
449
  foreach_transformed_block(xd, bsize, is_skippable, &args);
450
  return result;
451
452
}

453
454
455
int vp9_sby_is_skippable(MACROBLOCKD *xd, BLOCK_SIZE_TYPE bsize) {
  int result = 1;
  struct is_skippable_args args = {xd, &result};
456
  foreach_transformed_block_in_plane(xd, bsize, 0, 0, is_skippable, &args);
457
  return result;
458
459
}

460
461
462
int vp9_sbuv_is_skippable(MACROBLOCKD *xd, BLOCK_SIZE_TYPE bsize) {
  int result = 1;
  struct is_skippable_args args = {xd, &result};
463
  foreach_transformed_block_uv(xd, bsize, is_skippable, &args);
464
  return result;
465
466
}

467
468
469
void vp9_tokenize_sb(VP9_COMP *cpi,
                     MACROBLOCKD *xd,
                     TOKENEXTRA **t,
470
471
                     int dry_run, BLOCK_SIZE_TYPE bsize) {
  const int bwl = mb_width_log2(bsize) + 2, bhl = mb_height_log2(bsize) + 2;
472
473
474
475
476
  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
477
  const int skip_inc = !vp9_segfeature_active(xd, segment_id, SEG_LVL_SKIP);
478
479
480
481
482
  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;
483
  int b;
484
  const int n_y = (1 << (bwl + bhl)), n_uv = (n_y * 3) >> 1;
485

486
  mbmi->mb_skip_coeff = vp9_sb_is_skippable(xd, bsize);
487
488
489
490

  if (mbmi->mb_skip_coeff) {
    if (!dry_run)
      cpi->skip_true_count[mb_skip_context] += skip_inc;
491
    vp9_reset_sb_tokens_context(xd, bsize);
492
493
494
495
496
497
498
499
    if (dry_run)
      *t = t_backup;
    return;
  }

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

500
  switch (txfm_size) {
501
    case TX_32X32:
502
      for (b = 0; b < n_y; b += 64)
503
        tokenize_b(cpi, xd, b, t, PLANE_TYPE_Y_WITH_DC,
504
505
506
507
508
509
510
511
512
513
514
515
                   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);
      }
516
517
      break;
    case TX_16X16:
518
      for (b = 0; b < n_y; b += 16)
519
        tokenize_b(cpi, xd, b, t, PLANE_TYPE_Y_WITH_DC,
520
521
522
523
524
525
526
527
528
529
                   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);
      }
530
531
      break;
    case TX_8X8:
532
      for (b = 0; b < n_y; b += 4)
533
        tokenize_b(cpi, xd, b, t, PLANE_TYPE_Y_WITH_DC,
534
535
                   TX_8X8, n_y, dry_run);
      for (; b < n_uv; b += 4)
536
        tokenize_b(cpi, xd, b, t, PLANE_TYPE_UV,
537
                   TX_8X8, n_y, dry_run);
538
539
      break;
    case TX_4X4:
540
      for (b = 0; b < n_y; b++)
541
        tokenize_b(cpi, xd, b, t, PLANE_TYPE_Y_WITH_DC,
542
543
                   TX_4X4, n_y, dry_run);
      for (; b < n_uv; b++)
544
        tokenize_b(cpi, xd, b, t, PLANE_TYPE_UV,
545
                   TX_4X4, n_y, dry_run);
546
547
      break;
    default: assert(0);
548
  }
549

550
551
552
553
  if (dry_run)
    *t = t_backup;
}

554
void vp9_tokenize_mb(VP9_COMP *cpi,
Paul Wilkins's avatar
Paul Wilkins committed
555
                     MACROBLOCKD *xd,
556
557
                     TOKENEXTRA **t,
                     int dry_run) {
John Koleszar's avatar
John Koleszar committed
558
  int b;
559
  int tx_size = xd->mode_info_context->mbmi.txfm_size;
Paul Wilkins's avatar
Paul Wilkins committed
560
  int mb_skip_context = vp9_get_pred_context(&cpi->common, xd, PRED_MBSKIP);
561
  TOKENEXTRA *t_backup = *t;
Paul Wilkins's avatar
Paul Wilkins committed
562

John Koleszar's avatar
John Koleszar committed
563
564
565
566
  // 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
567
  int segment_id = xd->mode_info_context->mbmi.segment_id;
568

Paul Wilkins's avatar
Paul Wilkins committed
569
  if (!vp9_segfeature_active(xd, segment_id, SEG_LVL_SKIP)) {
John Koleszar's avatar
John Koleszar committed
570
571
572
    skip_inc = 1;
  } else
    skip_inc = 0;
573

574
575
  xd->mode_info_context->mbmi.mb_skip_coeff = vp9_sb_is_skippable(xd,
                                                  BLOCK_SIZE_MB16X16);
576

Paul Wilkins's avatar
Paul Wilkins committed
577
  if (xd->mode_info_context->mbmi.mb_skip_coeff) {
578
579
    if (!dry_run)
      cpi->skip_true_count[mb_skip_context] += skip_inc;
580
    vp9_reset_sb_tokens_context(xd, BLOCK_SIZE_MB16X16);
Yaowu Xu's avatar
Yaowu Xu committed
581

582
583
    if (dry_run)
      *t = t_backup;
John Koleszar's avatar
John Koleszar committed
584
585
586
    return;
  }

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

590
  if (tx_size == TX_16X16) {
John Koleszar's avatar
John Koleszar committed
591
    tokenize_b(cpi, xd, 0, t, PLANE_TYPE_Y_WITH_DC, TX_16X16, 16, dry_run);
Daniel Kang's avatar
Daniel Kang committed
592
    for (b = 16; b < 24; b += 4) {
John Koleszar's avatar
John Koleszar committed
593
      tokenize_b(cpi, xd, b, t, PLANE_TYPE_UV, TX_8X8, 16, dry_run);
Daniel Kang's avatar
Daniel Kang committed
594
    }
595
  } else if (tx_size == TX_8X8) {
John Koleszar's avatar
John Koleszar committed
596
    for (b = 0; b < 16; b += 4) {
John Koleszar's avatar
John Koleszar committed
597
      tokenize_b(cpi, xd, b, t, PLANE_TYPE_Y_WITH_DC, TX_8X8, 16, dry_run);
John Koleszar's avatar
John Koleszar committed
598
    }
599
600
    if (xd->mode_info_context->mbmi.mode == I8X8_PRED ||
        xd->mode_info_context->mbmi.mode == SPLITMV) {
601
      for (b = 16; b < 24; b++) {
John Koleszar's avatar
John Koleszar committed
602
        tokenize_b(cpi, xd, b, t, PLANE_TYPE_UV, TX_4X4, 16, dry_run);
603
      }
604
    } else {
Deb Mukherjee's avatar
Deb Mukherjee committed
605
      for (b = 16; b < 24; b += 4) {
John Koleszar's avatar
John Koleszar committed
606
        tokenize_b(cpi, xd, b, t, PLANE_TYPE_UV, TX_8X8, 16, dry_run);
Deb Mukherjee's avatar
Deb Mukherjee committed
607
      }
608
    }
Jingning Han's avatar
Jingning Han committed
609
  } else {
610
    for (b = 0; b < 16; b++)
John Koleszar's avatar
John Koleszar committed
611
      tokenize_b(cpi, xd, b, t, PLANE_TYPE_Y_WITH_DC, TX_4X4, 16, dry_run);
612
    for (b = 16; b < 24; b++)
John Koleszar's avatar
John Koleszar committed
613
      tokenize_b(cpi, xd, b, t, PLANE_TYPE_UV, TX_4X4, 16, dry_run);
Jingning Han's avatar
Jingning Han committed
614
  }
615
616
  if (dry_run)
    *t = t_backup;
John Koleszar's avatar
John Koleszar committed
617
}
618

John Koleszar's avatar
John Koleszar committed
619
#ifdef ENTROPY_STATS
John Koleszar's avatar
John Koleszar committed
620
621
622
void init_context_counters(void) {
  FILE *f = fopen("context.bin", "rb");
  if (!f) {
623
    vpx_memset(context_counters_4x4, 0, sizeof(context_counters_4x4));
John Koleszar's avatar
John Koleszar committed
624
    vpx_memset(context_counters_8x8, 0, sizeof(context_counters_8x8));
Daniel Kang's avatar
Daniel Kang committed
625
    vpx_memset(context_counters_16x16, 0, sizeof(context_counters_16x16));
626
    vpx_memset(context_counters_32x32, 0, sizeof(context_counters_32x32));
John Koleszar's avatar
John Koleszar committed
627
  } else {
628
    fread(context_counters_4x4, sizeof(context_counters_4x4), 1, f);
John Koleszar's avatar
John Koleszar committed
629
    fread(context_counters_8x8, sizeof(context_counters_8x8), 1, f);
Daniel Kang's avatar
Daniel Kang committed
630
    fread(context_counters_16x16, sizeof(context_counters_16x16), 1, f);
631
    fread(context_counters_32x32, sizeof(context_counters_32x32), 1, f);
John Koleszar's avatar
John Koleszar committed
632
633
634
635
636
    fclose(f);
  }

  f = fopen("treeupdate.bin", "rb");
  if (!f) {
637
    vpx_memset(tree_update_hist_4x4, 0, sizeof(tree_update_hist_4x4));
John Koleszar's avatar
John Koleszar committed
638
    vpx_memset(tree_update_hist_8x8, 0, sizeof(tree_update_hist_8x8));
Daniel Kang's avatar
Daniel Kang committed
639
    vpx_memset(tree_update_hist_16x16, 0, sizeof(tree_update_hist_16x16));
640
    vpx_memset(tree_update_hist_32x32, 0, sizeof(tree_update_hist_32x32));
John Koleszar's avatar
John Koleszar committed
641
  } else {
642
    fread(tree_update_hist_4x4, sizeof(tree_update_hist_4x4), 1, f);
John Koleszar's avatar
John Koleszar committed
643
    fread(tree_update_hist_8x8, sizeof(tree_update_hist_8x8), 1, f);
Daniel Kang's avatar
Daniel Kang committed
644
    fread(tree_update_hist_16x16, sizeof(tree_update_hist_16x16), 1, f);
645
    fread(tree_update_hist_32x32, sizeof(tree_update_hist_32x32), 1, f);
John Koleszar's avatar
John Koleszar committed
646
647
    fclose(f);
  }
John Koleszar's avatar
John Koleszar committed
648
649
}

650
651
static void print_counter(FILE *f, vp9_coeff_accum *context_counters,
                          int block_types, const char *header) {
652
  int type, ref, band, pt, t;
John Koleszar's avatar
John Koleszar committed
653

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

656
#define Comma(X) (X ? "," : "")
John Koleszar's avatar
John Koleszar committed
657
658
  type = 0;
  do {
659
    ref = 0;
John Koleszar's avatar
John Koleszar committed
660
661
    fprintf(f, "%s\n  { /* block Type %d */", Comma(type), type);
    do {
662
663
      fprintf(f, "%s\n    { /* %s */", Comma(type), ref ? "Inter" : "Intra");
      band = 0;
John Koleszar's avatar
John Koleszar committed
664
      do {
665
666
        fprintf(f, "%s\n      { /* Coeff Band %d */", Comma(band), band);
        pt = 0;
John Koleszar's avatar
John Koleszar committed
667
        do {
668
669
670
671
672
673
674
675
676
          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);
677
          } while (++t < 1 + MAX_ENTROPY_TOKENS);
678
679
680
681
          fprintf(f, "}");
        } while (++pt < PREV_COEF_CONTEXTS);
        fprintf(f, "\n      }");
      } while (++band < COEF_BANDS);
John Koleszar's avatar
John Koleszar committed
682
      fprintf(f, "\n    }");
683
    } while (++ref < REF_TYPES);
John Koleszar's avatar
John Koleszar committed
684
    fprintf(f, "\n  }");
685
  } while (++type < block_types);
Daniel Kang's avatar
Daniel Kang committed
686
  fprintf(f, "\n};\n");
687
}
688

689
690
static void print_probs(FILE *f, vp9_coeff_accum *context_counters,
                        int block_types, const char *header) {
691
  int type, ref, band, pt, t;
Daniel Kang's avatar
Daniel Kang committed
692

693
  fprintf(f, "static const vp9_coeff_probs %s = {", header);
694

John Koleszar's avatar
John Koleszar committed
695
  type = 0;
696
#define Newline(x, spaces) (x ? " " : "\n" spaces)
John Koleszar's avatar
John Koleszar committed
697
  do {
698
699
    fprintf(f, "%s%s{ /* block Type %d */",
            Comma(type), Newline(type, "  "), type);
700
    ref = 0;
John Koleszar's avatar
John Koleszar committed
701
    do {
702
703
704
      fprintf(f, "%s%s{ /* %s */",
              Comma(band), Newline(band, "    "), ref ? "Inter" : "Intra");
      band = 0;
John Koleszar's avatar
John Koleszar committed
705
      do {
706
707
708
        fprintf(f, "%s%s{ /* Coeff Band %d */",
                Comma(band), Newline(band, "      "), band);
        pt = 0;
John Koleszar's avatar
John Koleszar committed
709
        do {
710
          unsigned int branch_ct[ENTROPY_NODES][2];
711
          unsigned int coef_counts[MAX_ENTROPY_TOKENS + 1];
712
713
          vp9_prob coef_probs[ENTROPY_NODES];

714
715
716
          if (pt >= 3 && band == 0)
            break;
          for (t = 0; t < MAX_ENTROPY_TOKENS + 1; ++t)
717
            coef_counts[t] = context_counters[type][ref][band][pt][t];
718
719
          vp9_tree_probs_from_distribution(vp9_coef_tree, coef_probs,
                                           branch_ct, coef_counts, 0);
720
721
          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]);
722
723
724
725
726
727
728
729
730
731
732
          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
733
      fprintf(f, "\n    }");
734
    } while (++ref < REF_TYPES);
John Koleszar's avatar
John Koleszar committed
735
    fprintf(f, "\n  }");
736
  } while (++type < block_types);
John Koleszar's avatar
John Koleszar committed
737
  fprintf(f, "\n};\n");
738
}
739

740
741
void print_context_counters() {
  FILE *f = fopen("vp9_context.c", "w");
742

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

746
  /* print counts */
747
  print_counter(f, context_counters_4x4, BLOCK_TYPES,
748
                "vp9_default_coef_counts_4x4[BLOCK_TYPES]");
749
  print_counter(f, context_counters_8x8, BLOCK_TYPES,
750
                "vp9_default_coef_counts_8x8[BLOCK_TYPES]");
751
  print_counter(f, context_counters_16x16, BLOCK_TYPES,
752
753
754
                "vp9_default_coef_counts_16x16[BLOCK_TYPES]");
  print_counter(f, context_counters_32x32, BLOCK_TYPES,
                "vp9_default_coef_counts_32x32[BLOCK_TYPES]");
Daniel Kang's avatar
Daniel Kang committed
755

756
  /* print coefficient probabilities */
757
  print_probs(f, context_counters_4x4, BLOCK_TYPES,
758
              "default_coef_probs_4x4[BLOCK_TYPES]");
759
  print_probs(f, context_counters_8x8, BLOCK_TYPES,
760
              "default_coef_probs_8x8[BLOCK_TYPES]");
761
  print_probs(f, context_counters_16x16, BLOCK_TYPES,
762
763
764
              "default_coef_probs_16x16[BLOCK_TYPES]");
  print_probs(f, context_counters_32x32, BLOCK_TYPES,
              "default_coef_probs_32x32[BLOCK_TYPES]");
Daniel Kang's avatar
Daniel Kang committed
765

John Koleszar's avatar
John Koleszar committed
766
767
768
  fclose(f);

  f = fopen("context.bin", "wb");
769
  fwrite(context_counters_4x4, sizeof(context_counters_4x4), 1, f);
John Koleszar's avatar
John Koleszar committed
770
  fwrite(context_counters_8x8, sizeof(context_counters_8x8), 1, f);
Daniel Kang's avatar
Daniel Kang committed
771
  fwrite(context_counters_16x16, sizeof(context_counters_16x16), 1, f);
772
  fwrite(context_counters_32x32, sizeof(context_counters_32x32), 1, f);
John Koleszar's avatar
John Koleszar committed
773
  fclose(f);
John Koleszar's avatar
John Koleszar committed
774
775
776
}
#endif

777
void vp9_tokenize_initialize() {
John Koleszar's avatar
John Koleszar committed
778
  fill_value_tokens();
John Koleszar's avatar
John Koleszar committed
779
}