vp9_bitstream.c 43.6 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
#include <assert.h>
#include <stdio.h>
#include <limits.h>
John Koleszar's avatar
John Koleszar committed
14

15
16
17
#include "vpx/vpx_encoder.h"
#include "vpx_mem/vpx_mem.h"

18
#include "vp9/common/vp9_entropymode.h"
19
#include "vp9/common/vp9_entropymv.h"
20
#include "vp9/common/vp9_tile_common.h"
21
22
23
24
#include "vp9/common/vp9_seg_common.h"
#include "vp9/common/vp9_pred_common.h"
#include "vp9/common/vp9_entropy.h"
#include "vp9/common/vp9_mvref_common.h"
25
26
27
28
29
30
31
#include "vp9/common/vp9_systemdependent.h"
#include "vp9/common/vp9_pragmas.h"

#include "vp9/encoder/vp9_mcomp.h"
#include "vp9/encoder/vp9_encodemv.h"
#include "vp9/encoder/vp9_bitstream.h"
#include "vp9/encoder/vp9_segmentation.h"
32
#include "vp9/encoder/vp9_subexp.h"
33
#include "vp9/encoder/vp9_tokenize.h"
34
35
#include "vp9/encoder/vp9_write_bit_buffer.h"

John Koleszar's avatar
John Koleszar committed
36
#ifdef ENTROPY_STATS
37
vp9_coeff_stats tree_update_hist[TX_SIZES][PLANE_TYPES];
John Koleszar's avatar
John Koleszar committed
38
39
40
extern unsigned int active_section;
#endif

41
42
43
44
45
46
47
48
49
50
51
52
53
54
static struct vp9_token intra_mode_encodings[INTRA_MODES];
static struct vp9_token switchable_interp_encodings[SWITCHABLE_FILTERS];
static struct vp9_token partition_encodings[PARTITION_TYPES];
static struct vp9_token inter_mode_encodings[INTER_MODES];

void vp9_entropy_mode_init() {
  vp9_tokens_from_tree(intra_mode_encodings, vp9_intra_mode_tree);
  vp9_tokens_from_tree(switchable_interp_encodings, vp9_switchable_interp_tree);
  vp9_tokens_from_tree(partition_encodings, vp9_partition_tree);
  vp9_tokens_from_tree(inter_mode_encodings, vp9_inter_mode_tree);
}

static void write_intra_mode(vp9_writer *w, MB_PREDICTION_MODE mode,
                             const vp9_prob *probs) {
55
  vp9_write_token(w, vp9_intra_mode_tree, probs, &intra_mode_encodings[mode]);
56
57
58
59
60
}

static void write_inter_mode(vp9_writer *w, MB_PREDICTION_MODE mode,
                             const vp9_prob *probs) {
  assert(is_inter_mode(mode));
61
62
  vp9_write_token(w, vp9_inter_mode_tree, probs,
                  &inter_mode_encodings[INTER_OFFSET(mode)]);
63
64
}

65
66
67
68
69
static INLINE void write_be32(uint8_t *p, int value) {
  p[0] = value >> 24;
  p[1] = value >> 16;
  p[2] = value >> 8;
  p[3] = value;
70
71
}

72
73
74
75
76
void vp9_encode_unsigned_max(struct vp9_write_bit_buffer *wb,
                             int data, int max) {
  vp9_wb_write_literal(wb, data, get_unsigned_bits(max));
}

77
78
79
80
81
82
static void prob_diff_update(const vp9_tree_index *tree,
                             vp9_prob probs[/*n - 1*/],
                             const unsigned int counts[/*n - 1*/],
                             int n, vp9_writer *w) {
  int i;
  unsigned int branch_ct[32][2];
83
84

  // Assuming max number of probabilities <= 32
85
  assert(n <= 32);
86

87
  vp9_tree_probs_from_distribution(tree, branch_ct, counts);
88
  for (i = 0; i < n - 1; ++i)
89
    vp9_cond_prob_diff_update(w, &probs[i], branch_ct[i]);
90
91
}

92
93
94
static void write_selected_tx_size(const VP9_COMP *cpi, MODE_INFO *m,
                                   TX_SIZE tx_size, BLOCK_SIZE bsize,
                                   vp9_writer *w) {
95
  const TX_SIZE max_tx_size = max_txsize_lookup[bsize];
96
  const MACROBLOCKD *const xd = &cpi->mb.e_mbd;
97
98
  const vp9_prob *const tx_probs = get_tx_probs2(max_tx_size, xd,
                                                 &cpi->common.fc.tx_probs);
99
  vp9_write(w, tx_size != TX_4X4, tx_probs[0]);
100
  if (tx_size != TX_4X4 && max_tx_size >= TX_16X16) {
101
    vp9_write(w, tx_size != TX_8X8, tx_probs[1]);
102
    if (tx_size != TX_8X8 && max_tx_size >= TX_32X32)
103
104
105
106
      vp9_write(w, tx_size != TX_16X16, tx_probs[2]);
  }
}

107
108
static int write_skip(const VP9_COMP *cpi, int segment_id, MODE_INFO *m,
                      vp9_writer *w) {
109
  const MACROBLOCKD *const xd = &cpi->mb.e_mbd;
110
  if (vp9_segfeature_active(&cpi->common.seg, segment_id, SEG_LVL_SKIP)) {
111
112
    return 1;
  } else {
113
    const int skip = m->mbmi.skip;
114
115
    vp9_write(w, skip, vp9_get_skip_prob(&cpi->common, xd));
    return skip;
116
117
118
  }
}

119
void vp9_update_skip_probs(VP9_COMMON *cm, vp9_writer *w) {
120
121
  int k;

Dmitry Kovalev's avatar
Dmitry Kovalev committed
122
123
  for (k = 0; k < SKIP_CONTEXTS; ++k)
    vp9_cond_prob_diff_update(w, &cm->fc.skip_probs[k], cm->counts.skip[k]);
124
125
}

126
static void update_switchable_interp_probs(VP9_COMP *cpi, vp9_writer *w) {
127
  VP9_COMMON *const cm = &cpi->common;
128
129
130
131
132
  int j;
  for (j = 0; j < SWITCHABLE_FILTER_CONTEXTS; ++j)
    prob_diff_update(vp9_switchable_interp_tree,
                     cm->fc.switchable_interp_prob[j],
                     cm->counts.switchable_interp[j], SWITCHABLE_FILTERS, w);
133
134
}

135
static void pack_mb_tokens(vp9_writer* const w,
136
137
138
                           TOKENEXTRA **tp,
                           const TOKENEXTRA *const stop) {
  TOKENEXTRA *p = *tp;
John Koleszar's avatar
John Koleszar committed
139

140
  while (p < stop && p->token != EOSB_TOKEN) {
141
    const int t = p->token;
142
143
    const struct vp9_token *const a = &vp9_coef_encodings[t];
    const vp9_extra_bit *const b = &vp9_extra_bits[t];
John Koleszar's avatar
John Koleszar committed
144
145
    int i = 0;
    int v = a->value;
146
    int n = a->len;
147

John Koleszar's avatar
John Koleszar committed
148
149
150
151
152
    /* skip one or two nodes */
    if (p->skip_eob_node) {
      n -= p->skip_eob_node;
      i = 2 * p->skip_eob_node;
    }
John Koleszar's avatar
John Koleszar committed
153

154
155
156
157
158
159
160
161
    // TODO(jbb): expanding this can lead to big gains.  It allows
    // much better branch prediction and would enable us to avoid numerous
    // lookups and compares.

    // If we have a token that's in the constrained set, the coefficient tree
    // is split into two treed writes.  The first treed write takes care of the
    // unconstrained nodes.  The second treed write takes care of the
    // constrained nodes.
162
    if (t >= TWO_TOKEN && t < EOB_TOKEN) {
163
164
      int len = UNCONSTRAINED_NODES - p->skip_eob_node;
      int bits = v >> (n - len);
165
166
167
168
      vp9_write_tree(w, vp9_coef_tree, p->context_tree, bits, len, i);
      vp9_write_tree(w, vp9_coef_con_tree,
                     vp9_pareto8_full[p->context_tree[PIVOT_NODE] - 1],
                     v, n - len, 0);
169
    } else {
170
      vp9_write_tree(w, vp9_coef_tree, p->context_tree, v, n, i);
171
    }
John Koleszar's avatar
John Koleszar committed
172

John Koleszar's avatar
John Koleszar committed
173
    if (b->base_val) {
174
      const int e = p->extra, l = b->len;
John Koleszar's avatar
John Koleszar committed
175

176
      if (l) {
177
        const unsigned char *pb = b->prob;
John Koleszar's avatar
John Koleszar committed
178
        int v = e >> 1;
179
        int n = l;              /* number of bits in v, assumed nonzero */
John Koleszar's avatar
John Koleszar committed
180
        int i = 0;
John Koleszar's avatar
John Koleszar committed
181

John Koleszar's avatar
John Koleszar committed
182
183
        do {
          const int bb = (v >> --n) & 1;
184
          vp9_write(w, bb, pb[i >> 1]);
John Koleszar's avatar
John Koleszar committed
185
186
187
          i = b->tree[i + bb];
        } while (n);
      }
John Koleszar's avatar
John Koleszar committed
188

189
      vp9_write_bit(w, e & 1);
John Koleszar's avatar
John Koleszar committed
190
    }
John Koleszar's avatar
John Koleszar committed
191
192
193
    ++p;
  }

194
  *tp = p + (p->token == EOSB_TOKEN);
John Koleszar's avatar
John Koleszar committed
195
196
}

197
static void write_segment_id(vp9_writer *w, const struct segmentation *seg,
198
                             int segment_id) {
199
  if (seg->enabled && seg->update_map)
200
    vp9_write_tree(w, vp9_segment_tree, seg->tree_probs, segment_id, 3, 0);
John Koleszar's avatar
John Koleszar committed
201
202
}

Paul Wilkins's avatar
Paul Wilkins committed
203
// This function encodes the reference frame
Ronald S. Bultje's avatar
Ronald S. Bultje committed
204
static void encode_ref_frame(VP9_COMP *cpi, vp9_writer *bc) {
205
  VP9_COMMON *const cm = &cpi->common;
Ronald S. Bultje's avatar
Ronald S. Bultje committed
206
207
  MACROBLOCK *const x = &cpi->mb;
  MACROBLOCKD *const xd = &x->e_mbd;
208
  MB_MODE_INFO *mi = &xd->mi_8x8[0]->mbmi;
Ronald S. Bultje's avatar
Ronald S. Bultje committed
209
  const int segment_id = mi->segment_id;
210
  int seg_ref_active = vp9_segfeature_active(&cm->seg, segment_id,
Ronald S. Bultje's avatar
Ronald S. Bultje committed
211
                                             SEG_LVL_REF_FRAME);
John Koleszar's avatar
John Koleszar committed
212
213
  // If segment level coding of this signal is disabled...
  // or the segment allows multiple reference frame options
214
  if (!seg_ref_active) {
Ronald S. Bultje's avatar
Ronald S. Bultje committed
215
216
    // does the feature use compound prediction or not
    // (if not specified at the frame/segment level)
217
    if (cm->reference_mode == REFERENCE_MODE_SELECT) {
Ronald S. Bultje's avatar
Ronald S. Bultje committed
218
      vp9_write(bc, mi->ref_frame[1] > INTRA_FRAME,
219
                vp9_get_reference_mode_prob(cm, xd));
Ronald S. Bultje's avatar
Ronald S. Bultje committed
220
221
    } else {
      assert((mi->ref_frame[1] <= INTRA_FRAME) ==
222
             (cm->reference_mode == SINGLE_REFERENCE));
Ronald S. Bultje's avatar
Ronald S. Bultje committed
223
    }
224

Ronald S. Bultje's avatar
Ronald S. Bultje committed
225
226
    if (mi->ref_frame[1] > INTRA_FRAME) {
      vp9_write(bc, mi->ref_frame[0] == GOLDEN_FRAME,
227
                vp9_get_pred_prob_comp_ref_p(cm, xd));
Ronald S. Bultje's avatar
Ronald S. Bultje committed
228
229
    } else {
      vp9_write(bc, mi->ref_frame[0] != LAST_FRAME,
230
                vp9_get_pred_prob_single_ref_p1(cm, xd));
Ronald S. Bultje's avatar
Ronald S. Bultje committed
231
232
      if (mi->ref_frame[0] != LAST_FRAME)
        vp9_write(bc, mi->ref_frame[0] != GOLDEN_FRAME,
233
                  vp9_get_pred_prob_single_ref_p2(cm, xd));
Paul Wilkins's avatar
Paul Wilkins committed
234
    }
Ronald S. Bultje's avatar
Ronald S. Bultje committed
235
236
  } else {
    assert(mi->ref_frame[1] <= INTRA_FRAME);
237
    assert(vp9_get_segdata(&cm->seg, segment_id, SEG_LVL_REF_FRAME) ==
238
           mi->ref_frame[0]);
John Koleszar's avatar
John Koleszar committed
239
  }
Paul Wilkins's avatar
Paul Wilkins committed
240

Jingning Han's avatar
Jingning Han committed
241
242
  // If using the prediction model we have nothing further to do because
  // the reference frame is fully coded by the segment.
Paul Wilkins's avatar
Paul Wilkins committed
243
}
John Koleszar's avatar
John Koleszar committed
244

245
static void pack_inter_mode_mvs(VP9_COMP *cpi, MODE_INFO *m, vp9_writer *bc) {
246
247
  VP9_COMMON *const cm = &cpi->common;
  const nmv_context *nmvc = &cm->fc.nmvc;
Ronald S. Bultje's avatar
Ronald S. Bultje committed
248
249
  MACROBLOCK *const x = &cpi->mb;
  MACROBLOCKD *const xd = &x->e_mbd;
250
  struct segmentation *seg = &cm->seg;
Ronald S. Bultje's avatar
Ronald S. Bultje committed
251
  MB_MODE_INFO *const mi = &m->mbmi;
Ronald S. Bultje's avatar
Ronald S. Bultje committed
252
  const MV_REFERENCE_FRAME rf = mi->ref_frame[0];
Jingning Han's avatar
Jingning Han committed
253
  const MV_REFERENCE_FRAME sec_rf = mi->ref_frame[1];
Ronald S. Bultje's avatar
Ronald S. Bultje committed
254
255
  const MB_PREDICTION_MODE mode = mi->mode;
  const int segment_id = mi->segment_id;
256
  int skip;
257
  const BLOCK_SIZE bsize = mi->sb_type;
258
  const int allow_hp = cm->allow_high_precision_mv;
Adrian Grange's avatar
Adrian Grange committed
259

Ronald S. Bultje's avatar
Ronald S. Bultje committed
260
261
#ifdef ENTROPY_STATS
  active_section = 9;
262
#endif
263

264
265
  if (seg->update_map) {
    if (seg->temporal_update) {
Scott LaVarnway's avatar
Scott LaVarnway committed
266
      const int pred_flag = mi->seg_id_predicted;
267
      vp9_prob pred_prob = vp9_get_pred_prob_seg_id(seg, xd);
268
269
270
      vp9_write(bc, pred_flag, pred_prob);
      if (!pred_flag)
        write_segment_id(bc, seg, segment_id);
Ronald S. Bultje's avatar
Ronald S. Bultje committed
271
    } else {
272
      write_segment_id(bc, seg, segment_id);
Ronald S. Bultje's avatar
Ronald S. Bultje committed
273
274
    }
  }
275

276
  skip = write_skip(cpi, segment_id, m, bc);
John Koleszar's avatar
John Koleszar committed
277

278
  if (!vp9_segfeature_active(seg, segment_id, SEG_LVL_REF_FRAME))
279
    vp9_write(bc, rf != INTRA_FRAME, vp9_get_intra_inter_prob(cm, xd));
Paul Wilkins's avatar
Paul Wilkins committed
280

281
  if (bsize >= BLOCK_8X8 && cm->tx_mode == TX_MODE_SELECT &&
282
      !(rf != INTRA_FRAME &&
283
        (skip || vp9_segfeature_active(seg, segment_id, SEG_LVL_SKIP)))) {
284
    write_selected_tx_size(cpi, m, mi->tx_size, bsize, bc);
285
286
  }

Ronald S. Bultje's avatar
Ronald S. Bultje committed
287
  if (rf == INTRA_FRAME) {
288
#ifdef ENTROPY_STATS
Ronald S. Bultje's avatar
Ronald S. Bultje committed
289
    active_section = 6;
290
#endif
Paul Wilkins's avatar
Paul Wilkins committed
291

292
    if (bsize >= BLOCK_8X8) {
293
      write_intra_mode(bc, mode, cm->fc.y_mode_prob[size_group_lookup[bsize]]);
294
    } else {
295
      int idx, idy;
Jim Bankoski's avatar
Jim Bankoski committed
296
297
298
      const int num_4x4_blocks_wide = num_4x4_blocks_wide_lookup[bsize];
      const int num_4x4_blocks_high = num_4x4_blocks_high_lookup[bsize];
      for (idy = 0; idy < 2; idy += num_4x4_blocks_high) {
Jim Bankoski's avatar
Jim Bankoski committed
299
        for (idx = 0; idx < 2; idx += num_4x4_blocks_wide) {
300
          const MB_PREDICTION_MODE bm = m->bmi[idy * 2 + idx].as_mode;
301
          write_intra_mode(bc, bm, cm->fc.y_mode_prob[0]);
302
        }
Jim Bankoski's avatar
Jim Bankoski committed
303
      }
Ronald S. Bultje's avatar
Ronald S. Bultje committed
304
    }
305
    write_intra_mode(bc, mi->uv_mode, cm->fc.uv_mode_prob[mode]);
Ronald S. Bultje's avatar
Ronald S. Bultje committed
306
  } else {
307
    vp9_prob *mv_ref_p;
Ronald S. Bultje's avatar
Ronald S. Bultje committed
308
    encode_ref_frame(cpi, bc);
Paul Wilkins's avatar
Paul Wilkins committed
309
    mv_ref_p = cpi->common.fc.inter_mode_probs[mi->mode_context[rf]];
Yaowu Xu's avatar
Yaowu Xu committed
310

John Koleszar's avatar
John Koleszar committed
311
#ifdef ENTROPY_STATS
Ronald S. Bultje's avatar
Ronald S. Bultje committed
312
    active_section = 3;
John Koleszar's avatar
John Koleszar committed
313
314
#endif

315
    // If segment skip is not enabled code the mode.
316
    if (!vp9_segfeature_active(seg, segment_id, SEG_LVL_SKIP)) {
317
      if (bsize >= BLOCK_8X8) {
318
        write_inter_mode(bc, mode, mv_ref_p);
319
        ++cm->counts.inter_mode[mi->mode_context[rf]][INTER_OFFSET(mode)];
Ronald S. Bultje's avatar
Ronald S. Bultje committed
320
      }
Ronald S. Bultje's avatar
Ronald S. Bultje committed
321
    }
322

323
    if (cm->interp_filter == SWITCHABLE) {
324
      const int ctx = vp9_get_pred_context_switchable_interp(xd);
325
326
327
      vp9_write_token(bc, vp9_switchable_interp_tree,
                      cm->fc.switchable_interp_prob[ctx],
                      &switchable_interp_encodings[mi->interp_filter]);
Ronald S. Bultje's avatar
Ronald S. Bultje committed
328
    } else {
329
      assert(mi->interp_filter == cm->interp_filter);
Ronald S. Bultje's avatar
Ronald S. Bultje committed
330
    }
331

332
    if (bsize < BLOCK_8X8) {
Jim Bankoski's avatar
Jim Bankoski committed
333
334
      const int num_4x4_blocks_wide = num_4x4_blocks_wide_lookup[bsize];
      const int num_4x4_blocks_high = num_4x4_blocks_high_lookup[bsize];
Ronald S. Bultje's avatar
Ronald S. Bultje committed
335
      int idx, idy;
Jim Bankoski's avatar
Jim Bankoski committed
336
337
      for (idy = 0; idy < 2; idy += num_4x4_blocks_high) {
        for (idx = 0; idx < 2; idx += num_4x4_blocks_wide) {
338
          const int j = idy * 2 + idx;
339
          const MB_PREDICTION_MODE blockmode = m->bmi[j].as_mode;
340
          write_inter_mode(bc, blockmode, mv_ref_p);
341
          ++cm->counts.inter_mode[mi->mode_context[rf]]
342
                                 [INTER_OFFSET(blockmode)];
343

Ronald S. Bultje's avatar
Ronald S. Bultje committed
344
          if (blockmode == NEWMV) {
345
#ifdef ENTROPY_STATS
Ronald S. Bultje's avatar
Ronald S. Bultje committed
346
            active_section = 11;
347
#endif
348
            vp9_encode_mv(cpi, bc, &m->bmi[j].as_mv[0].as_mv,
Jingning Han's avatar
Jingning Han committed
349
                          &mi->ref_mvs[rf][0].as_mv, nmvc, allow_hp);
350
351
352

            if (has_second_ref(mi))
              vp9_encode_mv(cpi, bc, &m->bmi[j].as_mv[1].as_mv,
Jingning Han's avatar
Jingning Han committed
353
                            &mi->ref_mvs[sec_rf][0].as_mv, nmvc, allow_hp);
John Koleszar's avatar
John Koleszar committed
354
          }
355
        }
Ronald S. Bultje's avatar
Ronald S. Bultje committed
356
357
358
359
360
      }
    } else if (mode == NEWMV) {
#ifdef ENTROPY_STATS
      active_section = 5;
#endif
361
      vp9_encode_mv(cpi, bc, &mi->mv[0].as_mv,
Jingning Han's avatar
Jingning Han committed
362
                    &mi->ref_mvs[rf][0].as_mv, nmvc, allow_hp);
Ronald S. Bultje's avatar
Ronald S. Bultje committed
363

364
365
      if (has_second_ref(mi))
        vp9_encode_mv(cpi, bc, &mi->mv[1].as_mv,
Jingning Han's avatar
Jingning Han committed
366
                      &mi->ref_mvs[sec_rf][0].as_mv, nmvc, allow_hp);
Ronald S. Bultje's avatar
Ronald S. Bultje committed
367
368
    }
  }
John Koleszar's avatar
John Koleszar committed
369
}
370

371
static void write_mb_modes_kf(const VP9_COMP *cpi, MODE_INFO **mi_8x8,
372
                              vp9_writer *bc) {
373
  const VP9_COMMON *const cm = &cpi->common;
Ronald S. Bultje's avatar
Ronald S. Bultje committed
374
  const MACROBLOCKD *const xd = &cpi->mb.e_mbd;
375
  const struct segmentation *const seg = &cm->seg;
376
  MODE_INFO *m = mi_8x8[0];
Ronald S. Bultje's avatar
Ronald S. Bultje committed
377
378
  const int ym = m->mbmi.mode;
  const int segment_id = m->mbmi.segment_id;
379
  MODE_INFO *above_mi = mi_8x8[-xd->mode_info_stride];
380
  MODE_INFO *left_mi = xd->left_available ? mi_8x8[-1] : NULL;
381

382
383
  if (seg->update_map)
    write_segment_id(bc, seg, m->mbmi.segment_id);
384

385
  write_skip(cpi, segment_id, m, bc);
386

387
  if (m->mbmi.sb_type >= BLOCK_8X8 && cm->tx_mode == TX_MODE_SELECT)
388
    write_selected_tx_size(cpi, m, m->mbmi.tx_size, m->mbmi.sb_type, bc);
389

390
  if (m->mbmi.sb_type >= BLOCK_8X8) {
391
392
    const MB_PREDICTION_MODE A = vp9_above_block_mode(m, above_mi, 0);
    const MB_PREDICTION_MODE L = vp9_left_block_mode(m, left_mi, 0);
393
    write_intra_mode(bc, ym, vp9_kf_y_mode_prob[A][L]);
394
  } else {
395
    int idx, idy;
Jim Bankoski's avatar
Jim Bankoski committed
396
397
    const int num_4x4_blocks_wide = num_4x4_blocks_wide_lookup[m->mbmi.sb_type];
    const int num_4x4_blocks_high = num_4x4_blocks_high_lookup[m->mbmi.sb_type];
Jim Bankoski's avatar
Jim Bankoski committed
398
399
    for (idy = 0; idy < 2; idy += num_4x4_blocks_high) {
      for (idx = 0; idx < 2; idx += num_4x4_blocks_wide) {
400
        int i = idy * 2 + idx;
401
402
        const MB_PREDICTION_MODE A = vp9_above_block_mode(m, above_mi, i);
        const MB_PREDICTION_MODE L = vp9_left_block_mode(m, left_mi, i);
403
        const int bm = m->bmi[i].as_mode;
404
        write_intra_mode(bc, bm, vp9_kf_y_mode_prob[A][L]);
405
406
      }
    }
407
408
  }

409
  write_intra_mode(bc, m->mbmi.uv_mode, vp9_kf_uv_mode_prob[ym]);
410
411
}

James Zern's avatar
James Zern committed
412
static void write_modes_b(VP9_COMP *cpi, const TileInfo *const tile,
413
414
                          vp9_writer *w, TOKENEXTRA **tok, TOKENEXTRA *tok_end,
                          int mi_row, int mi_col) {
415
  VP9_COMMON *const cm = &cpi->common;
Ronald S. Bultje's avatar
Ronald S. Bultje committed
416
  MACROBLOCKD *const xd = &cpi->mb.e_mbd;
417
  MODE_INFO *m;
Dmitry Kovalev's avatar
Dmitry Kovalev committed
418

419
420
  xd->mi_8x8 = cm->mi_grid_visible + (mi_row * cm->mode_info_stride + mi_col);
  m = xd->mi_8x8[0];
421

James Zern's avatar
James Zern committed
422
  set_mi_row_col(xd, tile,
Dmitry Kovalev's avatar
Dmitry Kovalev committed
423
                 mi_row, num_8x8_blocks_high_lookup[m->mbmi.sb_type],
James Zern's avatar
James Zern committed
424
425
                 mi_col, num_8x8_blocks_wide_lookup[m->mbmi.sb_type],
                 cm->mi_rows, cm->mi_cols);
426
  if (frame_is_intra_only(cm)) {
427
    write_mb_modes_kf(cpi, xd->mi_8x8, w);
Ronald S. Bultje's avatar
Ronald S. Bultje committed
428
429
430
431
#ifdef ENTROPY_STATS
    active_section = 8;
#endif
  } else {
432
    pack_inter_mode_mvs(cpi, m, w);
Ronald S. Bultje's avatar
Ronald S. Bultje committed
433
434
435
436
437
438
#ifdef ENTROPY_STATS
    active_section = 1;
#endif
  }

  assert(*tok < tok_end);
439
  pack_mb_tokens(w, tok, tok_end);
Ronald S. Bultje's avatar
Ronald S. Bultje committed
440
441
}

442
443
444
445
446
447
448
449
450
static void write_partition(VP9_COMP *cpi, int hbs, int mi_row, int mi_col,
                            PARTITION_TYPE p, BLOCK_SIZE bsize, vp9_writer *w) {
  VP9_COMMON *const cm = &cpi->common;
  const int ctx = partition_plane_context(cpi->above_seg_context,
                                          cpi->left_seg_context,
                                          mi_row, mi_col, bsize);
  const vp9_prob *const probs = get_partition_probs(cm, ctx);
  const int has_rows = (mi_row + hbs) < cm->mi_rows;
  const int has_cols = (mi_col + hbs) < cm->mi_cols;
451
452

  if (has_rows && has_cols) {
453
    vp9_write_token(w, vp9_partition_tree, probs, &partition_encodings[p]);
454
  } else if (!has_rows && has_cols) {
455
456
    assert(p == PARTITION_SPLIT || p == PARTITION_HORZ);
    vp9_write(w, p == PARTITION_SPLIT, probs[1]);
457
  } else if (has_rows && !has_cols) {
458
459
    assert(p == PARTITION_SPLIT || p == PARTITION_VERT);
    vp9_write(w, p == PARTITION_SPLIT, probs[2]);
460
  } else {
461
    assert(p == PARTITION_SPLIT);
462
463
464
  }
}

James Zern's avatar
James Zern committed
465
static void write_modes_sb(VP9_COMP *cpi, const TileInfo *const tile,
466
467
                           vp9_writer *w, TOKENEXTRA **tok, TOKENEXTRA *tok_end,
                           int mi_row, int mi_col, BLOCK_SIZE bsize) {
468
  VP9_COMMON *const cm = &cpi->common;
469
470
471
  const int bsl = b_width_log2(bsize);
  const int bs = (1 << bsl) / 4;
  PARTITION_TYPE partition;
472
  BLOCK_SIZE subsize;
473
  MODE_INFO *m = cm->mi_grid_visible[mi_row * cm->mode_info_stride + mi_col];
474

475
  if (mi_row >= cm->mi_rows || mi_col >= cm->mi_cols)
476
477
    return;

Jim Bankoski's avatar
Jim Bankoski committed
478
  partition = partition_lookup[bsl][m->mbmi.sb_type];
479
  write_partition(cpi, bs, mi_row, mi_col, partition, bsize, w);
480
  subsize = get_subsize(bsize, partition);
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
  if (subsize < BLOCK_8X8) {
    write_modes_b(cpi, tile, w, tok, tok_end, mi_row, mi_col);
  } else {
    switch (partition) {
      case PARTITION_NONE:
        write_modes_b(cpi, tile, w, tok, tok_end, mi_row, mi_col);
        break;
      case PARTITION_HORZ:
        write_modes_b(cpi, tile, w, tok, tok_end, mi_row, mi_col);
        if (mi_row + bs < cm->mi_rows)
          write_modes_b(cpi, tile, w, tok, tok_end, mi_row + bs, mi_col);
        break;
      case PARTITION_VERT:
        write_modes_b(cpi, tile, w, tok, tok_end, mi_row, mi_col);
        if (mi_col + bs < cm->mi_cols)
          write_modes_b(cpi, tile, w, tok, tok_end, mi_row, mi_col + bs);
        break;
      case PARTITION_SPLIT:
        write_modes_sb(cpi, tile, w, tok, tok_end, mi_row, mi_col, subsize);
        write_modes_sb(cpi, tile, w, tok, tok_end, mi_row, mi_col + bs,
                       subsize);
        write_modes_sb(cpi, tile, w, tok, tok_end, mi_row + bs, mi_col,
                       subsize);
        write_modes_sb(cpi, tile, w, tok, tok_end, mi_row + bs, mi_col + bs,
                       subsize);
        break;
      default:
        assert(0);
    }
510
  }
511
512

  // update partition context
513
  if (bsize >= BLOCK_8X8 &&
514
      (bsize == BLOCK_8X8 || partition != PARTITION_SPLIT))
515
    update_partition_context(cpi->above_seg_context, cpi->left_seg_context,
516
                             mi_row, mi_col, subsize, bsize);
517
518
}

James Zern's avatar
James Zern committed
519
static void write_modes(VP9_COMP *cpi, const TileInfo *const tile,
520
                        vp9_writer *w, TOKENEXTRA **tok, TOKENEXTRA *tok_end) {
521
  int mi_row, mi_col;
522

James Zern's avatar
James Zern committed
523
  for (mi_row = tile->mi_row_start; mi_row < tile->mi_row_end;
524
525
       mi_row += MI_BLOCK_SIZE) {
      vp9_zero(cpi->left_seg_context);
James Zern's avatar
James Zern committed
526
    for (mi_col = tile->mi_col_start; mi_col < tile->mi_col_end;
527
528
         mi_col += MI_BLOCK_SIZE)
      write_modes_sb(cpi, tile, w, tok, tok_end, mi_row, mi_col, BLOCK_64X64);
John Koleszar's avatar
John Koleszar committed
529
  }
John Koleszar's avatar
John Koleszar committed
530
}
531

532
533
534
static void build_tree_distribution(VP9_COMP *cpi, TX_SIZE tx_size) {
  vp9_coeff_probs_model *coef_probs = cpi->frame_coef_probs[tx_size];
  vp9_coeff_count *coef_counts = cpi->coef_counts[tx_size];
535
  unsigned int (*eob_branch_ct)[REF_TYPES][COEF_BANDS][COEFF_CONTEXTS] =
536
537
      cpi->common.counts.eob_branch[tx_size];
  vp9_coeff_stats *coef_branch_ct = cpi->frame_branch_ct[tx_size];
538
  int i, j, k, l, m;
539

540
  for (i = 0; i < PLANE_TYPES; ++i) {
541
542
    for (j = 0; j < REF_TYPES; ++j) {
      for (k = 0; k < COEF_BANDS; ++k) {
543
        for (l = 0; l < BAND_COEFF_CONTEXTS(k); ++l) {
544
          vp9_tree_probs_from_distribution(vp9_coef_tree,
545
                                           coef_branch_ct[i][j][k][l],
546
                                           coef_counts[i][j][k][l]);
547
548
          coef_branch_ct[i][j][k][l][0][1] = eob_branch_ct[i][j][k][l] -
                                             coef_branch_ct[i][j][k][l][0][0];
549
550
551
552
          for (m = 0; m < UNCONSTRAINED_NODES; ++m)
            coef_probs[i][j][k][l][m] = get_binary_prob(
                                            coef_branch_ct[i][j][k][l][m][0],
                                            coef_branch_ct[i][j][k][l][m][1]);
553
        }
Daniel Kang's avatar
Daniel Kang committed
554
555
556
      }
    }
  }
557
558
}

559
560
561
562
563
564
static void update_coef_probs_common(vp9_writer* const bc, VP9_COMP *cpi,
                                     TX_SIZE tx_size) {
  vp9_coeff_probs_model *new_frame_coef_probs = cpi->frame_coef_probs[tx_size];
  vp9_coeff_probs_model *old_frame_coef_probs =
      cpi->common.fc.coef_probs[tx_size];
  vp9_coeff_stats *frame_branch_ct = cpi->frame_branch_ct[tx_size];
565
  const vp9_prob upd = DIFF_UPDATE_PROB;
566
  const int entropy_nodes_update = UNCONSTRAINED_NODES;
567
568
569
570
571
572
  int i, j, k, l, t;
  switch (cpi->sf.use_fast_coef_updates) {
    case 0: {
      /* dry run to see if there is any udpate at all needed */
      int savings = 0;
      int update[2] = {0, 0};
573
      for (i = 0; i < PLANE_TYPES; ++i) {
574
575
        for (j = 0; j < REF_TYPES; ++j) {
          for (k = 0; k < COEF_BANDS; ++k) {
576
            for (l = 0; l < BAND_COEFF_CONTEXTS(k); ++l) {
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
              for (t = 0; t < entropy_nodes_update; ++t) {
                vp9_prob newp = new_frame_coef_probs[i][j][k][l][t];
                const vp9_prob oldp = old_frame_coef_probs[i][j][k][l][t];
                int s;
                int u = 0;
                if (t == PIVOT_NODE)
                  s = vp9_prob_diff_update_savings_search_model(
                      frame_branch_ct[i][j][k][l][0],
                      old_frame_coef_probs[i][j][k][l], &newp, upd, i, j);
                else
                  s = vp9_prob_diff_update_savings_search(
                      frame_branch_ct[i][j][k][l][t], oldp, &newp, upd);
                if (s > 0 && newp != oldp)
                  u = 1;
                if (u)
                  savings += s - (int)(vp9_cost_zero(upd));
                else
                  savings -= (int)(vp9_cost_zero(upd));
                update[u]++;
              }
            }
          }
        }
      }
601

602
603
604
605
606
607
608
      // printf("Update %d %d, savings %d\n", update[0], update[1], savings);
      /* Is coef updated at all */
      if (update[1] == 0 || savings < 0) {
        vp9_write_bit(bc, 0);
        return;
      }
      vp9_write_bit(bc, 1);
609
      for (i = 0; i < PLANE_TYPES; ++i) {
610
611
        for (j = 0; j < REF_TYPES; ++j) {
          for (k = 0; k < COEF_BANDS; ++k) {
612
            for (l = 0; l < BAND_COEFF_CONTEXTS(k); ++l) {
613
614
615
616
              // calc probs and branch cts for this frame only
              for (t = 0; t < entropy_nodes_update; ++t) {
                vp9_prob newp = new_frame_coef_probs[i][j][k][l][t];
                vp9_prob *oldp = old_frame_coef_probs[i][j][k][l] + t;
617
                const vp9_prob upd = DIFF_UPDATE_PROB;
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
                int s;
                int u = 0;
                if (t == PIVOT_NODE)
                  s = vp9_prob_diff_update_savings_search_model(
                      frame_branch_ct[i][j][k][l][0],
                      old_frame_coef_probs[i][j][k][l], &newp, upd, i, j);
                else
                  s = vp9_prob_diff_update_savings_search(
                      frame_branch_ct[i][j][k][l][t],
                      *oldp, &newp, upd);
                if (s > 0 && newp != *oldp)
                  u = 1;
                vp9_write(bc, u, upd);
#ifdef ENTROPY_STATS
                if (!cpi->dummy_packing)
                  ++tree_update_hist[tx_size][i][j][k][l][t][u];
#endif
                if (u) {
                  /* send/use new probability */
                  vp9_write_prob_diff_update(bc, newp, *oldp);
                  *oldp = newp;
                }
              }
            }
642
          }
Daniel Kang's avatar
Daniel Kang committed
643
644
        }
      }
645
      return;
Daniel Kang's avatar
Daniel Kang committed
646
    }
John Koleszar's avatar
John Koleszar committed
647

648
649
650
    case 1:
    case 2: {
      const int prev_coef_contexts_to_update =
651
652
          cpi->sf.use_fast_coef_updates == 2 ? COEFF_CONTEXTS >> 1
                                             : COEFF_CONTEXTS;
653
      const int coef_band_to_update =
654
655
          cpi->sf.use_fast_coef_updates == 2 ? COEF_BANDS >> 1
                                             : COEF_BANDS;
656
657
      int updates = 0;
      int noupdates_before_first = 0;
658
      for (i = 0; i < PLANE_TYPES; ++i) {
659
660
        for (j = 0; j < REF_TYPES; ++j) {
          for (k = 0; k < COEF_BANDS; ++k) {
661
            for (l = 0; l < BAND_COEFF_CONTEXTS(k); ++l) {
662
663
664
665
666
667
668
669
670
671
672
673
674
675
676
677
678
679
680
681
682
683
684
685
              // calc probs and branch cts for this frame only
              for (t = 0; t < entropy_nodes_update; ++t) {
                vp9_prob newp = new_frame_coef_probs[i][j][k][l][t];
                vp9_prob *oldp = old_frame_coef_probs[i][j][k][l] + t;
                int s;
                int u = 0;
                if (l >= prev_coef_contexts_to_update ||
                    k >= coef_band_to_update) {
                  u = 0;
                } else {
                  if (t == PIVOT_NODE)
                    s = vp9_prob_diff_update_savings_search_model(
                        frame_branch_ct[i][j][k][l][0],
                        old_frame_coef_probs[i][j][k][l], &newp, upd, i, j);
                  else
                    s = vp9_prob_diff_update_savings_search(
                        frame_branch_ct[i][j][k][l][t],
                        *oldp, &newp, upd);
                  if (s > 0 && newp != *oldp)
                    u = 1;
                }
                updates += u;
                if (u == 0 && updates == 0) {
                  noupdates_before_first++;
686
#ifdef ENTROPY_STATS
687
688
                  if (!cpi->dummy_packing)
                    ++tree_update_hist[tx_size][i][j][k][l][t][u];
689
#endif
690
691
692
693
694
695
696
697
698
699
700
701
702
703
704
705
706
707
708
709
                  continue;
                }
                if (u == 1 && updates == 1) {
                  int v;
                  // first update
                  vp9_write_bit(bc, 1);
                  for (v = 0; v < noupdates_before_first; ++v)
                    vp9_write(bc, 0, upd);
                }
                vp9_write(bc, u, upd);
#ifdef ENTROPY_STATS
                if (!cpi->dummy_packing)
                  ++tree_update_hist[tx_size][i][j][k][l][t][u];
#endif
                if (u) {
                  /* send/use new probability */
                  vp9_write_prob_diff_update(bc, newp, *oldp);
                  *oldp = newp;
                }
              }
John Koleszar's avatar
John Koleszar committed
710
            }
Daniel Kang's avatar
Daniel Kang committed
711
712
713
          }
        }
      }
714
715
716
717
      if (updates == 0) {
        vp9_write_bit(bc, 0);  // no updates
      }
      return;
Daniel Kang's avatar
Daniel Kang committed
718
    }
719
720
721

    default:
      assert(0);
John Koleszar's avatar
John Koleszar committed
722
  }
723
}
John Koleszar's avatar
John Koleszar committed
724

725
static void update_coef_probs(VP9_COMP* cpi, vp9_writer* w) {
726
  const TX_MODE tx_mode = cpi->common.tx_mode;
727
728
  const TX_SIZE max_tx_size = tx_mode_to_biggest_tx_size[tx_mode];
  TX_SIZE tx_size;
729
  vp9_clear_system_state();
730

731
732
  for (tx_size = TX_4X4; tx_size <= TX_32X32; ++tx_size)
    build_tree_distribution(cpi, tx_size);
733

734
735
  for (tx_size = TX_4X4; tx_size <= max_tx_size; ++tx_size)
    update_coef_probs_common(w, cpi, tx_size);
John Koleszar's avatar
John Koleszar committed
736
}
737

738
static void encode_loopfilter(struct loopfilter *lf,
739
                              struct vp9_write_bit_buffer *wb) {
740
741
  int i;

742
  // Encode the loop filter level and type
743
744
  vp9_wb_write_literal(wb, lf->filter_level, 6);
  vp9_wb_write_literal(wb, lf->sharpness_level, 3);
745

746
747
  // Write out loop filter deltas applied at the MB level based on mode or
  // ref frame (if they are enabled).
748
  vp9_wb_write_bit(wb, lf->mode_ref_delta_enabled);
749

750
751
752
  if (lf->mode_ref_delta_enabled) {
    vp9_wb_write_bit(wb, lf->mode_ref_delta_update);
    if (lf->mode_ref_delta_update) {
753
      for (i = 0; i < MAX_REF_LF_DELTAS; i++) {
754
        const int delta = lf->ref_deltas[i];
755
756
757
        const int changed = delta != lf->last_ref_deltas[i];
        vp9_wb_write_bit(wb, changed);
        if (changed) {
758
          lf->last_ref_deltas[i] = delta;
759
760
          vp9_wb_write_literal(wb, abs(delta) & 0x3F, 6);
          vp9_wb_write_bit(wb, delta < 0);
761
762
763
764
        }
      }

      for (i = 0; i < MAX_MODE_LF_DELTAS; i++) {
765
        const int delta = lf->mode_deltas[i];
766
767
768
        const int changed = delta != lf->last_mode_deltas[i];
        vp9_wb_write_bit(wb, changed);
        if (changed) {
769
          lf->last_mode_deltas[i] = delta;
770
771
          vp9_wb_write_literal(wb, abs(delta) & 0x3F, 6);
          vp9_wb_write_bit(wb, delta < 0);
772
773
774
775
776
777
        }
      }
    }
  }
}

778
static void write_delta_q(struct vp9_write_bit_buffer *wb, int delta_q) {
779
  if (delta_q != 0) {
780
781
782
    vp9_wb_write_bit(wb, 1);
    vp9_wb_write_literal(wb, abs(delta_q), 4);
    vp9_wb_write_bit(wb, delta_q < 0);
783
  } else {
784
    vp9_wb_write_bit(wb, 0);
785
786
787
  }
}

788
789
790
791
792
793
static void encode_quantization(VP9_COMMON *cm,
                                struct vp9_write_bit_buffer *wb) {
  vp9_wb_write_literal(wb, cm->base_qindex, QINDEX_BITS);
  write_delta_q(wb, cm->y_dc_delta_q);
  write_delta_q(wb, cm->uv_dc_delta_q);
  write_delta_q(wb, cm->uv_ac_delta_q);
794
795
796
}


797
static void encode_segmentation(VP9_COMP *cpi,
798
                                struct vp9_write_bit_buffer *wb) {
John Koleszar's avatar
John Koleszar committed
799
  int i, j;
800

801
  struct segmentation *seg = &cpi->common.seg;
802
803
804

  vp9_wb_write_bit(wb, seg->enabled);
  if (!seg->enabled)
805
806
807
    return;

  // Segmentation map
808
809
  vp9_wb_write_bit(wb, seg->update_map);
  if (seg->update_map) {
810
811
812
    // Select the coding strategy (temporal or spatial)
    vp9_choose_segmap_coding_method(cpi);
    // Write out probabilities used to decode unpredicted  macro-block segments
Paul Wilkins's avatar
Paul Wilkins committed
813
    for (i = 0; i < SEG_TREE_PROBS; i++) {
814
      const int prob = seg->tree_probs[i];
815
816
817
818
      const int update = prob != MAX_PROB;
      vp9_wb_write_bit(wb, update);
      if (update)
        vp9_wb_write_literal(wb, prob, 8);
819
820
821
    }

    // Write out the chosen coding method.
822
823
    vp9_wb_write_bit(wb, seg->temporal_update);
    if (seg->temporal_update) {
824
      for (i = 0; i < PREDICTION_PROBS; i++) {
825
        const int prob = seg->pred_probs[i];
826
827
828
829
        const int update = prob != MAX_PROB;
        vp9_wb_write_bit(wb, update);
        if (update)
          vp9_wb_write_literal(wb, prob, 8);
830
831
832
833
834
      }
    }
  }

  // Segmentation data
835
836
837
  vp9_wb_write_bit(wb, seg->update_data);
  if (seg->update_data) {
    vp9_wb_write_bit(wb, seg->abs_delta);
838

Paul Wilkins's avatar
Paul Wilkins committed
839
    for (i = 0; i < MAX_SEGMENTS; i++) {
840
      for (j = 0; j < SEG_LVL_MAX; j++) {
841
        const int active = vp9_segfeature_active(seg, i, j);
842
843
        vp9_wb_write_bit(wb, active);
        if (active) {
844
          const int data = vp9_get_segdata(seg, i, j);
845
          const int data_max = vp9_seg_feature_data_max(j);
846
847

          if (vp9_is_segfeature_signed(j)) {
848
849
            vp9_encode_unsigned_max(wb, abs(data), data_max);
            vp9_wb_write_bit(wb, data < 0);
850
          } else {
851
            vp9_encode_unsigned_max(wb, data, data_max);