vp9_bitstream.c 43.8 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
#include "vpx/vpx_encoder.h"
#include "vpx_mem/vpx_mem.h"
17
#include "vpx_ports/mem_ops.h"
18

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

Dmitry Kovalev's avatar
Dmitry Kovalev committed
28
#include "vp9/encoder/vp9_cost.h"
29
#include "vp9/encoder/vp9_bitstream.h"
30
31
#include "vp9/encoder/vp9_encodemv.h"
#include "vp9/encoder/vp9_mcomp.h"
32
#include "vp9/encoder/vp9_segmentation.h"
33
#include "vp9/encoder/vp9_subexp.h"
34
#include "vp9/encoder/vp9_tokenize.h"
35
36
#include "vp9/encoder/vp9_write_bit_buffer.h"

37
38
39
40
41
42
43
44
45
46
47
48
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);
}

49
static void write_intra_mode(vp9_writer *w, PREDICTION_MODE mode,
50
                             const vp9_prob *probs) {
51
  vp9_write_token(w, vp9_intra_mode_tree, probs, &intra_mode_encodings[mode]);
52
53
}

54
static void write_inter_mode(vp9_writer *w, PREDICTION_MODE mode,
55
56
                             const vp9_prob *probs) {
  assert(is_inter_mode(mode));
57
58
  vp9_write_token(w, vp9_inter_mode_tree, probs,
                  &inter_mode_encodings[INTER_OFFSET(mode)]);
59
60
}

61
62
static void encode_unsigned_max(struct vp9_write_bit_buffer *wb,
                                int data, int max) {
63
64
65
  vp9_wb_write_literal(wb, data, get_unsigned_bits(max));
}

66
67
68
69
70
71
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];
72
73

  // Assuming max number of probabilities <= 32
74
  assert(n <= 32);
75

76
  vp9_tree_probs_from_distribution(tree, branch_ct, counts);
77
  for (i = 0; i < n - 1; ++i)
78
    vp9_cond_prob_diff_update(w, &probs[i], branch_ct[i]);
79
80
}

81
static void write_selected_tx_size(const VP9_COMMON *cm,
82
83
84
                                   const MACROBLOCKD *xd, vp9_writer *w) {
  TX_SIZE tx_size = xd->mi[0].src_mi->mbmi.tx_size;
  BLOCK_SIZE bsize = xd->mi[0].src_mi->mbmi.sb_type;
85
86
  const TX_SIZE max_tx_size = max_txsize_lookup[bsize];
  const vp9_prob *const tx_probs = get_tx_probs2(max_tx_size, xd,
87
                                                 &cm->fc->tx_probs);
88
  vp9_write(w, tx_size != TX_4X4, tx_probs[0]);
89
  if (tx_size != TX_4X4 && max_tx_size >= TX_16X16) {
90
    vp9_write(w, tx_size != TX_8X8, tx_probs[1]);
91
    if (tx_size != TX_8X8 && max_tx_size >= TX_32X32)
92
93
94
95
      vp9_write(w, tx_size != TX_16X16, tx_probs[2]);
  }
}

96
97
98
static int write_skip(const VP9_COMMON *cm, const MACROBLOCKD *xd,
                      int segment_id, const MODE_INFO *mi, vp9_writer *w) {
  if (vp9_segfeature_active(&cm->seg, segment_id, SEG_LVL_SKIP)) {
99
100
    return 1;
  } else {
101
    const int skip = mi->mbmi.skip;
102
    vp9_write(w, skip, vp9_get_skip_prob(cm, xd));
103
    return skip;
104
105
106
  }
}

107
static void update_skip_probs(VP9_COMMON *cm, vp9_writer *w) {
108
109
  int k;

Dmitry Kovalev's avatar
Dmitry Kovalev committed
110
  for (k = 0; k < SKIP_CONTEXTS; ++k)
111
    vp9_cond_prob_diff_update(w, &cm->fc->skip_probs[k], cm->counts.skip[k]);
112
113
}

114
static void update_switchable_interp_probs(VP9_COMMON *cm, vp9_writer *w) {
115
116
117
  int j;
  for (j = 0; j < SWITCHABLE_FILTER_CONTEXTS; ++j)
    prob_diff_update(vp9_switchable_interp_tree,
118
                     cm->fc->switchable_interp_prob[j],
119
                     cm->counts.switchable_interp[j], SWITCHABLE_FILTERS, w);
120
121
}

122
static void pack_mb_tokens(vp9_writer *w,
123
124
                           TOKENEXTRA **tp, const TOKENEXTRA *const stop,
                           vpx_bit_depth_t bit_depth) {
125
  TOKENEXTRA *p = *tp;
John Koleszar's avatar
John Koleszar committed
126

127
  while (p < stop && p->token != EOSB_TOKEN) {
128
    const int t = p->token;
129
    const struct vp9_token *const a = &vp9_coef_encodings[t];
John Koleszar's avatar
John Koleszar committed
130
131
    int i = 0;
    int v = a->value;
132
    int n = a->len;
133
134
135
136
137
138
139
140
141
142
143
144
#if CONFIG_VP9_HIGHBITDEPTH
    const vp9_extra_bit *b;
    if (bit_depth == VPX_BITS_12)
      b = &vp9_extra_bits_high12[t];
    else if (bit_depth == VPX_BITS_10)
      b = &vp9_extra_bits_high10[t];
    else
      b = &vp9_extra_bits[t];
#else
    const vp9_extra_bit *const b = &vp9_extra_bits[t];
    (void) bit_depth;
#endif  // CONFIG_VP9_HIGHBITDEPTH
145

John Koleszar's avatar
John Koleszar committed
146
147
148
149
150
    /* 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
151

152
153
154
155
156
157
158
159
    // 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.
160
    if (t >= TWO_TOKEN && t < EOB_TOKEN) {
161
162
      int len = UNCONSTRAINED_NODES - p->skip_eob_node;
      int bits = v >> (n - len);
163
164
165
166
      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);
167
    } else {
168
      vp9_write_tree(w, vp9_coef_tree, p->context_tree, v, n, i);
169
    }
John Koleszar's avatar
John Koleszar committed
170

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

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

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

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

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

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

Paul Wilkins's avatar
Paul Wilkins committed
201
// This function encodes the reference frame
202
203
static void write_ref_frames(const VP9_COMMON *cm, const MACROBLOCKD *xd,
                             vp9_writer *w) {
hkuang's avatar
hkuang committed
204
  const MB_MODE_INFO *const mbmi = &xd->mi[0].src_mi->mbmi;
205
206
207
  const int is_compound = has_second_ref(mbmi);
  const int segment_id = mbmi->segment_id;

John Koleszar's avatar
John Koleszar committed
208
209
  // If segment level coding of this signal is disabled...
  // or the segment allows multiple reference frame options
210
211
212
213
214
  if (vp9_segfeature_active(&cm->seg, segment_id, SEG_LVL_REF_FRAME)) {
    assert(!is_compound);
    assert(mbmi->ref_frame[0] ==
               vp9_get_segdata(&cm->seg, segment_id, SEG_LVL_REF_FRAME));
  } else {
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) {
218
      vp9_write(w, is_compound, vp9_get_reference_mode_prob(cm, xd));
Ronald S. Bultje's avatar
Ronald S. Bultje committed
219
    } else {
220
      assert(!is_compound == (cm->reference_mode == SINGLE_REFERENCE));
Ronald S. Bultje's avatar
Ronald S. Bultje committed
221
    }
222

223
224
    if (is_compound) {
      vp9_write(w, mbmi->ref_frame[0] == GOLDEN_FRAME,
225
                vp9_get_pred_prob_comp_ref_p(cm, xd));
Ronald S. Bultje's avatar
Ronald S. Bultje committed
226
    } else {
227
228
229
230
231
232
      const int bit0 = mbmi->ref_frame[0] != LAST_FRAME;
      vp9_write(w, bit0, vp9_get_pred_prob_single_ref_p1(cm, xd));
      if (bit0) {
        const int bit1 = mbmi->ref_frame[0] != GOLDEN_FRAME;
        vp9_write(w, bit1, vp9_get_pred_prob_single_ref_p2(cm, xd));
      }
Paul Wilkins's avatar
Paul Wilkins committed
233
    }
John Koleszar's avatar
John Koleszar committed
234
  }
Paul Wilkins's avatar
Paul Wilkins committed
235
}
John Koleszar's avatar
John Koleszar committed
236

237
238
static void pack_inter_mode_mvs(VP9_COMP *cpi, const MODE_INFO *mi,
                                vp9_writer *w) {
239
  VP9_COMMON *const cm = &cpi->common;
240
  const nmv_context *nmvc = &cm->fc->nmvc;
241
242
  const MACROBLOCK *const x = &cpi->mb;
  const MACROBLOCKD *const xd = &x->e_mbd;
243
  const struct segmentation *const seg = &cm->seg;
244
  const MB_MODE_INFO *const mbmi = &mi->mbmi;
245
  const PREDICTION_MODE mode = mbmi->mode;
246
247
  const int segment_id = mbmi->segment_id;
  const BLOCK_SIZE bsize = mbmi->sb_type;
248
  const int allow_hp = cm->allow_high_precision_mv;
249
250
251
  const int is_inter = is_inter_block(mbmi);
  const int is_compound = has_second_ref(mbmi);
  int skip, ref;
Adrian Grange's avatar
Adrian Grange committed
252

253
254
  if (seg->update_map) {
    if (seg->temporal_update) {
255
      const int pred_flag = mbmi->seg_id_predicted;
256
      vp9_prob pred_prob = vp9_get_pred_prob_seg_id(seg, xd);
257
      vp9_write(w, pred_flag, pred_prob);
258
      if (!pred_flag)
259
        write_segment_id(w, seg, segment_id);
Ronald S. Bultje's avatar
Ronald S. Bultje committed
260
    } else {
261
      write_segment_id(w, seg, segment_id);
Ronald S. Bultje's avatar
Ronald S. Bultje committed
262
263
    }
  }
264

265
  skip = write_skip(cm, xd, segment_id, mi, w);
John Koleszar's avatar
John Koleszar committed
266

267
  if (!vp9_segfeature_active(seg, segment_id, SEG_LVL_REF_FRAME))
268
    vp9_write(w, is_inter, vp9_get_intra_inter_prob(cm, xd));
Paul Wilkins's avatar
Paul Wilkins committed
269

270
  if (bsize >= BLOCK_8X8 && cm->tx_mode == TX_MODE_SELECT &&
271
      !(is_inter &&
272
        (skip || vp9_segfeature_active(seg, segment_id, SEG_LVL_SKIP)))) {
273
    write_selected_tx_size(cm, xd, w);
274
275
  }

276
  if (!is_inter) {
277
    if (bsize >= BLOCK_8X8) {
278
      write_intra_mode(w, mode, cm->fc->y_mode_prob[size_group_lookup[bsize]]);
279
    } else {
280
      int idx, idy;
281
282
283
284
      const int num_4x4_w = num_4x4_blocks_wide_lookup[bsize];
      const int num_4x4_h = num_4x4_blocks_high_lookup[bsize];
      for (idy = 0; idy < 2; idy += num_4x4_h) {
        for (idx = 0; idx < 2; idx += num_4x4_w) {
285
          const PREDICTION_MODE b_mode = mi->bmi[idy * 2 + idx].as_mode;
286
          write_intra_mode(w, b_mode, cm->fc->y_mode_prob[0]);
287
        }
Jim Bankoski's avatar
Jim Bankoski committed
288
      }
Ronald S. Bultje's avatar
Ronald S. Bultje committed
289
    }
290
    write_intra_mode(w, mbmi->uv_mode, cm->fc->uv_mode_prob[mode]);
Ronald S. Bultje's avatar
Ronald S. Bultje committed
291
  } else {
292
    const int mode_ctx = mbmi->mode_context[mbmi->ref_frame[0]];
293
    const vp9_prob *const inter_probs = cm->fc->inter_mode_probs[mode_ctx];
294
    write_ref_frames(cm, xd, w);
Yaowu Xu's avatar
Yaowu Xu committed
295

296
    // If segment skip is not enabled code the mode.
297
    if (!vp9_segfeature_active(seg, segment_id, SEG_LVL_SKIP)) {
298
      if (bsize >= BLOCK_8X8) {
299
300
        write_inter_mode(w, mode, inter_probs);
        ++cm->counts.inter_mode[mode_ctx][INTER_OFFSET(mode)];
Ronald S. Bultje's avatar
Ronald S. Bultje committed
301
      }
Ronald S. Bultje's avatar
Ronald S. Bultje committed
302
    }
303

304
    if (cm->interp_filter == SWITCHABLE) {
305
      const int ctx = vp9_get_pred_context_switchable_interp(xd);
306
      vp9_write_token(w, vp9_switchable_interp_tree,
307
                      cm->fc->switchable_interp_prob[ctx],
308
                      &switchable_interp_encodings[mbmi->interp_filter]);
309
      ++cpi->interp_filter_selected[0][mbmi->interp_filter];
Ronald S. Bultje's avatar
Ronald S. Bultje committed
310
    } else {
311
      assert(mbmi->interp_filter == cm->interp_filter);
Ronald S. Bultje's avatar
Ronald S. Bultje committed
312
    }
313

314
    if (bsize < BLOCK_8X8) {
315
316
      const int num_4x4_w = num_4x4_blocks_wide_lookup[bsize];
      const int num_4x4_h = num_4x4_blocks_high_lookup[bsize];
Ronald S. Bultje's avatar
Ronald S. Bultje committed
317
      int idx, idy;
318
319
      for (idy = 0; idy < 2; idy += num_4x4_h) {
        for (idx = 0; idx < 2; idx += num_4x4_w) {
320
          const int j = idy * 2 + idx;
321
          const PREDICTION_MODE b_mode = mi->bmi[j].as_mode;
322
323
          write_inter_mode(w, b_mode, inter_probs);
          ++cm->counts.inter_mode[mode_ctx][INTER_OFFSET(b_mode)];
324
          if (b_mode == NEWMV) {
325
326
327
328
            for (ref = 0; ref < 1 + is_compound; ++ref)
              vp9_encode_mv(cpi, w, &mi->bmi[j].as_mv[ref].as_mv,
                            &mbmi->ref_mvs[mbmi->ref_frame[ref]][0].as_mv,
                            nmvc, allow_hp);
John Koleszar's avatar
John Koleszar committed
329
          }
330
        }
Ronald S. Bultje's avatar
Ronald S. Bultje committed
331
      }
332
333
334
335
336
337
338
    } else {
      if (mode == NEWMV) {
        for (ref = 0; ref < 1 + is_compound; ++ref)
          vp9_encode_mv(cpi, w, &mbmi->mv[ref].as_mv,
                        &mbmi->ref_mvs[mbmi->ref_frame[ref]][0].as_mv, nmvc,
                        allow_hp);
      }
Ronald S. Bultje's avatar
Ronald S. Bultje committed
339
340
    }
  }
John Koleszar's avatar
John Koleszar committed
341
}
342

343
static void write_mb_modes_kf(const VP9_COMMON *cm, const MACROBLOCKD *xd,
hkuang's avatar
hkuang committed
344
                              MODE_INFO *mi_8x8, vp9_writer *w) {
345
  const struct segmentation *const seg = &cm->seg;
hkuang's avatar
hkuang committed
346
347
348
349
  const MODE_INFO *const mi = mi_8x8;
  const MODE_INFO *const above_mi = mi_8x8[-xd->mi_stride].src_mi;
  const MODE_INFO *const left_mi =
      xd->left_available ? mi_8x8[-1].src_mi : NULL;
350
351
  const MB_MODE_INFO *const mbmi = &mi->mbmi;
  const BLOCK_SIZE bsize = mbmi->sb_type;
352

353
  if (seg->update_map)
354
    write_segment_id(w, seg, mbmi->segment_id);
355

356
  write_skip(cm, xd, mbmi->segment_id, mi, w);
357

358
  if (bsize >= BLOCK_8X8 && cm->tx_mode == TX_MODE_SELECT)
359
    write_selected_tx_size(cm, xd, w);
360

361
362
  if (bsize >= BLOCK_8X8) {
    write_intra_mode(w, mbmi->mode, get_y_mode_probs(mi, above_mi, left_mi, 0));
363
  } else {
364
365
    const int num_4x4_w = num_4x4_blocks_wide_lookup[bsize];
    const int num_4x4_h = num_4x4_blocks_high_lookup[bsize];
366
    int idx, idy;
367
368
369
370
371
372

    for (idy = 0; idy < 2; idy += num_4x4_h) {
      for (idx = 0; idx < 2; idx += num_4x4_w) {
        const int block = idy * 2 + idx;
        write_intra_mode(w, mi->bmi[block].as_mode,
                         get_y_mode_probs(mi, above_mi, left_mi, block));
373
374
      }
    }
375
376
  }

377
  write_intra_mode(w, mbmi->uv_mode, vp9_kf_uv_mode_prob[mbmi->mode]);
378
379
}

James Zern's avatar
James Zern committed
380
static void write_modes_b(VP9_COMP *cpi, const TileInfo *const tile,
381
382
                          vp9_writer *w, TOKENEXTRA **tok,
                          const TOKENEXTRA *const tok_end,
383
                          int mi_row, int mi_col) {
384
  const VP9_COMMON *const cm = &cpi->common;
Ronald S. Bultje's avatar
Ronald S. Bultje committed
385
  MACROBLOCKD *const xd = &cpi->mb.e_mbd;
386
  MODE_INFO *m;
Dmitry Kovalev's avatar
Dmitry Kovalev committed
387

hkuang's avatar
hkuang committed
388
389
  xd->mi = cm->mi + (mi_row * cm->mi_stride + mi_col);
  m = xd->mi;
390

James Zern's avatar
James Zern committed
391
  set_mi_row_col(xd, tile,
Dmitry Kovalev's avatar
Dmitry Kovalev committed
392
                 mi_row, num_8x8_blocks_high_lookup[m->mbmi.sb_type],
James Zern's avatar
James Zern committed
393
394
                 mi_col, num_8x8_blocks_wide_lookup[m->mbmi.sb_type],
                 cm->mi_rows, cm->mi_cols);
395
  if (frame_is_intra_only(cm)) {
396
    write_mb_modes_kf(cm, xd, xd->mi, w);
Ronald S. Bultje's avatar
Ronald S. Bultje committed
397
  } else {
398
    pack_inter_mode_mvs(cpi, m, w);
Ronald S. Bultje's avatar
Ronald S. Bultje committed
399
400
401
  }

  assert(*tok < tok_end);
402
  pack_mb_tokens(w, tok, tok_end, cm->bit_depth);
Ronald S. Bultje's avatar
Ronald S. Bultje committed
403
404
}

405
406
static void write_partition(const VP9_COMMON *const cm,
                            const MACROBLOCKD *const xd,
407
                            int hbs, int mi_row, int mi_col,
408
                            PARTITION_TYPE p, BLOCK_SIZE bsize, vp9_writer *w) {
409
  const int ctx = partition_plane_context(xd, mi_row, mi_col, bsize);
410
411
412
  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;
413
414

  if (has_rows && has_cols) {
415
    vp9_write_token(w, vp9_partition_tree, probs, &partition_encodings[p]);
416
  } else if (!has_rows && has_cols) {
417
418
    assert(p == PARTITION_SPLIT || p == PARTITION_HORZ);
    vp9_write(w, p == PARTITION_SPLIT, probs[1]);
419
  } else if (has_rows && !has_cols) {
420
421
    assert(p == PARTITION_SPLIT || p == PARTITION_VERT);
    vp9_write(w, p == PARTITION_SPLIT, probs[2]);
422
  } else {
423
    assert(p == PARTITION_SPLIT);
424
425
426
  }
}

427
static void write_modes_sb(VP9_COMP *cpi,
428
429
                           const TileInfo *const tile, vp9_writer *w,
                           TOKENEXTRA **tok, const TOKENEXTRA *const tok_end,
430
                           int mi_row, int mi_col, BLOCK_SIZE bsize) {
431
  const VP9_COMMON *const cm = &cpi->common;
432
433
  MACROBLOCKD *const xd = &cpi->mb.e_mbd;

434
  const int bsl = b_width_log2_lookup[bsize];
435
436
  const int bs = (1 << bsl) / 4;
  PARTITION_TYPE partition;
437
  BLOCK_SIZE subsize;
438
  const MODE_INFO *m = NULL;
439

440
  if (mi_row >= cm->mi_rows || mi_col >= cm->mi_cols)
441
442
    return;

hkuang's avatar
hkuang committed
443
  m = cm->mi[mi_row * cm->mi_stride + mi_col].src_mi;
444

Jim Bankoski's avatar
Jim Bankoski committed
445
  partition = partition_lookup[bsl][m->mbmi.sb_type];
446
  write_partition(cm, xd, bs, mi_row, mi_col, partition, bsize, w);
447
  subsize = get_subsize(bsize, partition);
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
  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);
    }
477
  }
478
479

  // update partition context
480
  if (bsize >= BLOCK_8X8 &&
481
      (bsize == BLOCK_8X8 || partition != PARTITION_SPLIT))
482
    update_partition_context(xd, mi_row, mi_col, subsize, bsize);
483
484
}

485
static void write_modes(VP9_COMP *cpi,
486
487
                        const TileInfo *const tile, vp9_writer *w,
                        TOKENEXTRA **tok, const TOKENEXTRA *const tok_end) {
488
  int mi_row, mi_col;
489

James Zern's avatar
James Zern committed
490
  for (mi_row = tile->mi_row_start; mi_row < tile->mi_row_end;
491
       mi_row += MI_BLOCK_SIZE) {
492
    vp9_zero(cpi->mb.e_mbd.left_seg_context);
James Zern's avatar
James Zern committed
493
    for (mi_col = tile->mi_col_start; mi_col < tile->mi_col_end;
494
         mi_col += MI_BLOCK_SIZE)
495
496
      write_modes_sb(cpi, tile, w, tok, tok_end, mi_row, mi_col,
                     BLOCK_64X64);
John Koleszar's avatar
John Koleszar committed
497
  }
John Koleszar's avatar
John Koleszar committed
498
}
499

500
static void build_tree_distribution(VP9_COMP *cpi, TX_SIZE tx_size,
501
502
                                    vp9_coeff_stats *coef_branch_ct,
                                    vp9_coeff_probs_model *coef_probs) {
503
  vp9_coeff_count *coef_counts = cpi->coef_counts[tx_size];
504
  unsigned int (*eob_branch_ct)[REF_TYPES][COEF_BANDS][COEFF_CONTEXTS] =
505
      cpi->common.counts.eob_branch[tx_size];
506
  int i, j, k, l, m;
507

508
  for (i = 0; i < PLANE_TYPES; ++i) {
509
510
    for (j = 0; j < REF_TYPES; ++j) {
      for (k = 0; k < COEF_BANDS; ++k) {
511
        for (l = 0; l < BAND_COEFF_CONTEXTS(k); ++l) {
512
          vp9_tree_probs_from_distribution(vp9_coef_tree,
513
                                           coef_branch_ct[i][j][k][l],
514
                                           coef_counts[i][j][k][l]);
515
516
          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];
517
518
519
520
          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]);
521
        }
Daniel Kang's avatar
Daniel Kang committed
522
523
524
      }
    }
  }
525
526
}

527
static void update_coef_probs_common(vp9_writer* const bc, VP9_COMP *cpi,
528
                                     TX_SIZE tx_size,
529
530
                                     vp9_coeff_stats *frame_branch_ct,
                                     vp9_coeff_probs_model *new_coef_probs) {
531
  vp9_coeff_probs_model *old_coef_probs = cpi->common.fc->coef_probs[tx_size];
532
  const vp9_prob upd = DIFF_UPDATE_PROB;
533
  const int entropy_nodes_update = UNCONSTRAINED_NODES;
534
535
  int i, j, k, l, t;
  switch (cpi->sf.use_fast_coef_updates) {
536
    case TWO_LOOP: {
James Zern's avatar
James Zern committed
537
      /* dry run to see if there is any update at all needed */
538
539
      int savings = 0;
      int update[2] = {0, 0};
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
              for (t = 0; t < entropy_nodes_update; ++t) {
545
546
                vp9_prob newp = new_coef_probs[i][j][k][l][t];
                const vp9_prob oldp = old_coef_probs[i][j][k][l][t];
547
548
549
550
551
                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],
552
                      old_coef_probs[i][j][k][l], &newp, upd);
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
                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]++;
              }
            }
          }
        }
      }
568

569
570
571
572
573
574
575
      // 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);
576
      for (i = 0; i < PLANE_TYPES; ++i) {
577
578
        for (j = 0; j < REF_TYPES; ++j) {
          for (k = 0; k < COEF_BANDS; ++k) {
579
            for (l = 0; l < BAND_COEFF_CONTEXTS(k); ++l) {
580
581
              // calc probs and branch cts for this frame only
              for (t = 0; t < entropy_nodes_update; ++t) {
582
583
                vp9_prob newp = new_coef_probs[i][j][k][l][t];
                vp9_prob *oldp = old_coef_probs[i][j][k][l] + t;
584
                const vp9_prob upd = DIFF_UPDATE_PROB;
585
586
587
588
589
                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],
590
                      old_coef_probs[i][j][k][l], &newp, upd);
591
592
593
594
595
596
597
598
599
600
601
602
603
604
                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);
                if (u) {
                  /* send/use new probability */
                  vp9_write_prob_diff_update(bc, newp, *oldp);
                  *oldp = newp;
                }
              }
            }
605
          }
Daniel Kang's avatar
Daniel Kang committed
606
607
        }
      }
608
      return;
Daniel Kang's avatar
Daniel Kang committed
609
    }
John Koleszar's avatar
John Koleszar committed
610

611
612
    case ONE_LOOP:
    case ONE_LOOP_REDUCED: {
613
      const int prev_coef_contexts_to_update =
614
615
          cpi->sf.use_fast_coef_updates == ONE_LOOP_REDUCED ?
              COEFF_CONTEXTS >> 1 : COEFF_CONTEXTS;
616
      const int coef_band_to_update =
617
618
          cpi->sf.use_fast_coef_updates == ONE_LOOP_REDUCED ?
              COEF_BANDS >> 1 : COEF_BANDS;
619
620
      int updates = 0;
      int noupdates_before_first = 0;
621
      for (i = 0; i < PLANE_TYPES; ++i) {
622
623
        for (j = 0; j < REF_TYPES; ++j) {
          for (k = 0; k < COEF_BANDS; ++k) {
624
            for (l = 0; l < BAND_COEFF_CONTEXTS(k); ++l) {
625
626
              // calc probs and branch cts for this frame only
              for (t = 0; t < entropy_nodes_update; ++t) {
627
628
                vp9_prob newp = new_coef_probs[i][j][k][l][t];
                vp9_prob *oldp = old_coef_probs[i][j][k][l] + t;
629
630
631
632
633
634
635
636
637
                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],
638
                        old_coef_probs[i][j][k][l], &newp, upd);
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
664
                  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++;
                  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);
                if (u) {
                  /* send/use new probability */
                  vp9_write_prob_diff_update(bc, newp, *oldp);
                  *oldp = newp;
                }
              }
John Koleszar's avatar
John Koleszar committed
665
            }
Daniel Kang's avatar
Daniel Kang committed
666
667
668
          }
        }
      }
669
670
671
672
      if (updates == 0) {
        vp9_write_bit(bc, 0);  // no updates
      }
      return;
Daniel Kang's avatar
Daniel Kang committed
673
    }
674
675
676

    default:
      assert(0);
John Koleszar's avatar
John Koleszar committed
677
  }
678
}
John Koleszar's avatar
John Koleszar committed
679

680
static void update_coef_probs(VP9_COMP *cpi, vp9_writer* w) {
681
  const TX_MODE tx_mode = cpi->common.tx_mode;
682
683
  const TX_SIZE max_tx_size = tx_mode_to_biggest_tx_size[tx_mode];
  TX_SIZE tx_size;
684
  vp9_coeff_stats frame_branch_ct[TX_SIZES][PLANE_TYPES];
685
  vp9_coeff_probs_model frame_coef_probs[TX_SIZES][PLANE_TYPES];
686

687
  for (tx_size = TX_4X4; tx_size <= TX_32X32; ++tx_size)
688
689
    build_tree_distribution(cpi, tx_size, frame_branch_ct[tx_size],
                            frame_coef_probs[tx_size]);
690

691
  for (tx_size = TX_4X4; tx_size <= max_tx_size; ++tx_size)
692
693
    update_coef_probs_common(w, cpi, tx_size, frame_branch_ct[tx_size],
                             frame_coef_probs[tx_size]);
John Koleszar's avatar
John Koleszar committed
694
}
695

696
static void encode_loopfilter(struct loopfilter *lf,
697
                              struct vp9_write_bit_buffer *wb) {
698
699
  int i;

700
  // Encode the loop filter level and type
701
702
  vp9_wb_write_literal(wb, lf->filter_level, 6);
  vp9_wb_write_literal(wb, lf->sharpness_level, 3);
703

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

708
709
710
  if (lf->mode_ref_delta_enabled) {
    vp9_wb_write_bit(wb, lf->mode_ref_delta_update);
    if (lf->mode_ref_delta_update) {
711
      for (i = 0; i < MAX_REF_LF_DELTAS; i++) {
712
        const int delta = lf->ref_deltas[i];
713
714
715
        const int changed = delta != lf->last_ref_deltas[i];
        vp9_wb_write_bit(wb, changed);
        if (changed) {
716
          lf->last_ref_deltas[i] = delta;
717
718
          vp9_wb_write_literal(wb, abs(delta) & 0x3F, 6);
          vp9_wb_write_bit(wb, delta < 0);
719
720
721
722
        }
      }

      for (i = 0; i < MAX_MODE_LF_DELTAS; i++) {
723
        const int delta = lf->mode_deltas[i];
724
725
726
        const int changed = delta != lf->last_mode_deltas[i];
        vp9_wb_write_bit(wb, changed);
        if (changed) {
727
          lf->last_mode_deltas[i] = delta;
728
729
          vp9_wb_write_literal(wb, abs(delta) & 0x3F, 6);
          vp9_wb_write_bit(wb, delta < 0);
730
731
732
733
734
735
        }
      }
    }
  }
}

736
static void write_delta_q(struct vp9_write_bit_buffer *wb, int delta_q) {
737
  if (delta_q != 0) {
738
739
740
    vp9_wb_write_bit(wb, 1);
    vp9_wb_write_literal(wb, abs(delta_q), 4);
    vp9_wb_write_bit(wb, delta_q < 0);
741
  } else {
742
    vp9_wb_write_bit(wb, 0);
743
744
745
  }
}

746
static void encode_quantization(const VP9_COMMON *const cm,
747
748
749
750
751
                                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);
752
753
}

754
static void encode_segmentation(VP9_COMMON *cm, MACROBLOCKD *xd,
755
                                struct vp9_write_bit_buffer *wb) {
John Koleszar's avatar
John Koleszar committed
756
  int i, j;
757

758
  const struct segmentation *seg = &cm->seg;
759
760
761

  vp9_wb_write_bit(wb, seg->enabled);
  if (!seg->enabled)
762
763
764
    return;

  // Segmentation map
765
766
  vp9_wb_write_bit(wb, seg->update_map);
  if (seg->update_map) {
767
    // Select the coding strategy (temporal or spatial)
768
    vp9_choose_segmap_coding_method(cm, xd);
769
    // Write out probabilities used to decode unpredicted  macro-block segments
Paul Wilkins's avatar
Paul Wilkins committed
770
    for (i = 0; i < SEG_TREE_PROBS; i++) {
771
      const int prob = seg->tree_probs[i];
772
773
774
775
      const int update = prob != MAX_PROB;
      vp9_wb_write_bit(wb, update);
      if (update)
        vp9_wb_write_literal(wb, prob, 8);
776
777
778
    }

    // Write out the chosen coding method.
779
780
    vp9_wb_write_bit(wb, seg->temporal_update);
    if (seg->temporal_update) {
781
      for (i = 0; i < PREDICTION_PROBS; i++) {
782
        const int prob = seg->pred_probs[i];
783
784
785
786
        const int update = prob != MAX_PROB;
        vp9_wb_write_bit(wb, update);
        if (update)
          vp9_wb_write_literal(wb, prob, 8);
787
788
789
790
791
      }
    }
  }

  // Segmentation data
792
793
794
  vp9_wb_write_bit(wb, seg->update_data);
  if (seg->update_data) {
    vp9_wb_write_bit(wb, seg->abs_delta);
795

Paul Wilkins's avatar
Paul Wilkins committed
796
    for (i = 0; i < MAX_SEGMENTS; i++) {
797
      for (j = 0; j < SEG_LVL_MAX; j++) {
798
        const int active = vp9_segfeature_active(seg, i, j);
799
800
        vp9_wb_write_bit(wb, active);
        if (active) {
801
          const int data = vp9_get_segdata(seg, i, j);
802
          const int data_max = vp9_seg_feature_data_max(j);
803
804

          if (vp9_is_segfeature_signed(j)) {
805
            encode_unsigned_max(wb, abs(data), data_max);
806
            vp9_wb_write_bit(wb, data < 0);
807
          } else {
808
            encode_unsigned_max(wb, data, data_max);
809
810
811
812
813
814
815
          }
        }
      }
    }
  }
}

816
static void encode_txfm_probs(VP9_COMMON *cm, vp9_writer *w) {
817
  // Mode
818
819
820
  vp9_write_literal(w, MIN(cm->tx_mode, ALLOW_32X32), 2);
  if (cm->tx_mode >= ALLOW_32X32)
    vp9_write_bit(w, cm->tx_mode == TX_MODE_SELECT);
821
822

  // Probabilities
823
  if (cm->tx_mode == TX_MODE_SELECT) {