vp9_bitstream.c 43.2 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
static const struct vp9_token intra_mode_encodings[INTRA_MODES] = {
  {0, 1}, {6, 3}, {28, 5}, {30, 5}, {58, 6}, {59, 6}, {126, 7}, {127, 7},
  {62, 6}, {2, 2}};
static const struct vp9_token switchable_interp_encodings[SWITCHABLE_FILTERS] =
  {{0, 1}, {2, 2}, {3, 2}};
static const struct vp9_token partition_encodings[PARTITION_TYPES] =
  {{0, 1}, {2, 2}, {6, 3}, {7, 3}};
static const struct vp9_token inter_mode_encodings[INTER_MODES] =
  {{2, 2}, {6, 3}, {0, 1}, {7, 3}};
46

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

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

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

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

  // Assuming max number of probabilities <= 32
72
  assert(n <= 32);
73

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

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

94
95
96
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)) {
97
98
    return 1;
  } else {
99
    const int skip = mi->mbmi.skip;
100
    vp9_write(w, skip, vp9_get_skip_prob(cm, xd));
101
    return skip;
102
103
104
  }
}

105
106
static void update_skip_probs(VP9_COMMON *cm, vp9_writer *w,
                              FRAME_COUNTS *counts) {
107
108
  int k;

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

113
114
static void update_switchable_interp_probs(VP9_COMMON *cm, vp9_writer *w,
                                           FRAME_COUNTS *counts) {
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
                     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) {
204
  const MB_MODE_INFO *const mbmi = &xd->mi[0]->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
  const MACROBLOCK *const x = &cpi->td.mb;
242
  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 &&
Alex Converse's avatar
Alex Converse committed
271
      !(is_inter && skip)) {
272
    write_selected_tx_size(cm, xd, w);
273
274
  }

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

295
    // If segment skip is not enabled code the mode.
296
    if (!vp9_segfeature_active(seg, segment_id, SEG_LVL_SKIP)) {
297
      if (bsize >= BLOCK_8X8) {
298
        write_inter_mode(w, mode, inter_probs);
Ronald S. Bultje's avatar
Ronald S. Bultje committed
299
      }
Ronald S. Bultje's avatar
Ronald S. Bultje committed
300
    }
301

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

312
    if (bsize < BLOCK_8X8) {
313
314
      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
315
      int idx, idy;
316
317
      for (idy = 0; idy < 2; idy += num_4x4_h) {
        for (idx = 0; idx < 2; idx += num_4x4_w) {
318
          const int j = idy * 2 + idx;
319
          const PREDICTION_MODE b_mode = mi->bmi[j].as_mode;
320
          write_inter_mode(w, b_mode, inter_probs);
321
          if (b_mode == NEWMV) {
322
323
324
325
            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
326
          }
327
        }
Ronald S. Bultje's avatar
Ronald S. Bultje committed
328
      }
329
330
331
332
333
334
335
    } 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
336
337
    }
  }
John Koleszar's avatar
John Koleszar committed
338
}
339

340
static void write_mb_modes_kf(const VP9_COMMON *cm, const MACROBLOCKD *xd,
341
                              MODE_INFO **mi_8x8, vp9_writer *w) {
342
  const struct segmentation *const seg = &cm->seg;
343
  const MODE_INFO *const mi = mi_8x8[0];
344
345
  const MODE_INFO *const above_mi = xd->above_mi;
  const MODE_INFO *const left_mi = xd->left_mi;
346
347
  const MB_MODE_INFO *const mbmi = &mi->mbmi;
  const BLOCK_SIZE bsize = mbmi->sb_type;
348

349
  if (seg->update_map)
350
    write_segment_id(w, seg, mbmi->segment_id);
351

352
  write_skip(cm, xd, mbmi->segment_id, mi, w);
353

354
  if (bsize >= BLOCK_8X8 && cm->tx_mode == TX_MODE_SELECT)
355
    write_selected_tx_size(cm, xd, w);
356

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

    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));
369
370
      }
    }
371
372
  }

373
  write_intra_mode(w, mbmi->uv_mode, vp9_kf_uv_mode_prob[mbmi->mode]);
374
375
}

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

384
385
  xd->mi = cm->mi_grid_visible + (mi_row * cm->mi_stride + mi_col);
  m = xd->mi[0];
386

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

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

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

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

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

430
  const int bsl = b_width_log2_lookup[bsize];
431
432
  const int bs = (1 << bsl) / 4;
  PARTITION_TYPE partition;
433
  BLOCK_SIZE subsize;
434
  const MODE_INFO *m = NULL;
435

436
  if (mi_row >= cm->mi_rows || mi_col >= cm->mi_cols)
437
438
    return;

439
  m = cm->mi_grid_visible[mi_row * cm->mi_stride + mi_col];
440

Jim Bankoski's avatar
Jim Bankoski committed
441
  partition = partition_lookup[bsl][m->mbmi.sb_type];
442
  write_partition(cm, xd, bs, mi_row, mi_col, partition, bsize, w);
443
  subsize = get_subsize(bsize, partition);
444
445
446
447
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
  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);
    }
473
  }
474
475

  // update partition context
476
  if (bsize >= BLOCK_8X8 &&
477
      (bsize == BLOCK_8X8 || partition != PARTITION_SPLIT))
478
    update_partition_context(xd, mi_row, mi_col, subsize, bsize);
479
480
}

481
static void write_modes(VP9_COMP *cpi,
482
483
                        const TileInfo *const tile, vp9_writer *w,
                        TOKENEXTRA **tok, const TOKENEXTRA *const tok_end) {
484
  MACROBLOCKD *const xd = &cpi->td.mb.e_mbd;
485
  int mi_row, mi_col;
486

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

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

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

524
static void update_coef_probs_common(vp9_writer* const bc, VP9_COMP *cpi,
525
                                     TX_SIZE tx_size,
526
527
                                     vp9_coeff_stats *frame_branch_ct,
                                     vp9_coeff_probs_model *new_coef_probs) {
528
  vp9_coeff_probs_model *old_coef_probs = cpi->common.fc->coef_probs[tx_size];
529
  const vp9_prob upd = DIFF_UPDATE_PROB;
530
  const int entropy_nodes_update = UNCONSTRAINED_NODES;
531
  int i, j, k, l, t;
532
533
  int stepsize = cpi->sf.coeff_prob_appx_step;

534
  switch (cpi->sf.use_fast_coef_updates) {
535
    case TWO_LOOP: {
James Zern's avatar
James Zern committed
536
      /* dry run to see if there is any update at all needed */
537
538
      int savings = 0;
      int update[2] = {0, 0};
539
      for (i = 0; i < PLANE_TYPES; ++i) {
540
541
        for (j = 0; j < REF_TYPES; ++j) {
          for (k = 0; k < COEF_BANDS; ++k) {
542
            for (l = 0; l < BAND_COEFF_CONTEXTS(k); ++l) {
543
              for (t = 0; t < entropy_nodes_update; ++t) {
544
545
                vp9_prob newp = new_coef_probs[i][j][k][l][t];
                const vp9_prob oldp = old_coef_probs[i][j][k][l][t];
546
547
548
549
550
                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],
551
                      old_coef_probs[i][j][k][l], &newp, upd, stepsize);
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
                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]++;
              }
            }
          }
        }
      }
567

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

610
    case ONE_LOOP_REDUCED: {
611
612
      int updates = 0;
      int noupdates_before_first = 0;
613
      for (i = 0; i < PLANE_TYPES; ++i) {
614
615
        for (j = 0; j < REF_TYPES; ++j) {
          for (k = 0; k < COEF_BANDS; ++k) {
616
            for (l = 0; l < BAND_COEFF_CONTEXTS(k); ++l) {
617
618
              // calc probs and branch cts for this frame only
              for (t = 0; t < entropy_nodes_update; ++t) {
619
620
                vp9_prob newp = new_coef_probs[i][j][k][l][t];
                vp9_prob *oldp = old_coef_probs[i][j][k][l] + t;
621
622
                int s;
                int u = 0;
623
624
625
626
627

                if (t == PIVOT_NODE) {
                  s = vp9_prob_diff_update_savings_search_model(
                      frame_branch_ct[i][j][k][l][0],
                      old_coef_probs[i][j][k][l], &newp, upd, stepsize);
628
                } else {
629
630
631
                  s = vp9_prob_diff_update_savings_search(
                      frame_branch_ct[i][j][k][l][t],
                      *oldp, &newp, upd);
632
                }
633
634
635

                if (s > 0 && newp != *oldp)
                  u = 1;
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
                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
655
            }
Daniel Kang's avatar
Daniel Kang committed
656
657
658
          }
        }
      }
659
660
661
662
      if (updates == 0) {
        vp9_write_bit(bc, 0);  // no updates
      }
      return;
Daniel Kang's avatar
Daniel Kang committed
663
    }
664
665
    default:
      assert(0);
John Koleszar's avatar
John Koleszar committed
666
  }
667
}
John Koleszar's avatar
John Koleszar committed
668

669
static void update_coef_probs(VP9_COMP *cpi, vp9_writer* w) {
670
  const TX_MODE tx_mode = cpi->common.tx_mode;
671
672
  const TX_SIZE max_tx_size = tx_mode_to_biggest_tx_size[tx_mode];
  TX_SIZE tx_size;
Yaowu Xu's avatar
Yaowu Xu committed
673
674
675
  for (tx_size = TX_4X4; tx_size <= max_tx_size; ++tx_size) {
    vp9_coeff_stats frame_branch_ct[PLANE_TYPES];
    vp9_coeff_probs_model frame_coef_probs[PLANE_TYPES];
Yaowu Xu's avatar
Yaowu Xu committed
676
    if (cpi->td.counts->tx.tx_totals[tx_size] <= 20 ||
Yaowu Xu's avatar
Yaowu Xu committed
677
678
679
680
681
682
683
684
        (tx_size >= TX_16X16 && cpi->sf.tx_size_search_method == USE_TX_8X8)) {
      vp9_write_bit(w, 0);
    } else {
      build_tree_distribution(cpi, tx_size, frame_branch_ct,
                              frame_coef_probs);
      update_coef_probs_common(w, cpi, tx_size, frame_branch_ct,
                               frame_coef_probs);
    }
Yaowu Xu's avatar
Yaowu Xu committed
685
  }
John Koleszar's avatar
John Koleszar committed
686
}
687

688
static void encode_loopfilter(struct loopfilter *lf,
689
                              struct vp9_write_bit_buffer *wb) {
690
691
  int i;

692
  // Encode the loop filter level and type
693
694
  vp9_wb_write_literal(wb, lf->filter_level, 6);
  vp9_wb_write_literal(wb, lf->sharpness_level, 3);
695

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

700
701
702
  if (lf->mode_ref_delta_enabled) {
    vp9_wb_write_bit(wb, lf->mode_ref_delta_update);
    if (lf->mode_ref_delta_update) {
703
      for (i = 0; i < MAX_REF_LF_DELTAS; i++) {
704
        const int delta = lf->ref_deltas[i];
705
706
707
        const int changed = delta != lf->last_ref_deltas[i];
        vp9_wb_write_bit(wb, changed);
        if (changed) {
708
          lf->last_ref_deltas[i] = delta;
709
710
          vp9_wb_write_literal(wb, abs(delta) & 0x3F, 6);
          vp9_wb_write_bit(wb, delta < 0);
711
712
713
714
        }
      }

      for (i = 0; i < MAX_MODE_LF_DELTAS; i++) {
715
        const int delta = lf->mode_deltas[i];
716
717
718
        const int changed = delta != lf->last_mode_deltas[i];
        vp9_wb_write_bit(wb, changed);
        if (changed) {
719
          lf->last_mode_deltas[i] = delta;
720
721
          vp9_wb_write_literal(wb, abs(delta) & 0x3F, 6);
          vp9_wb_write_bit(wb, delta < 0);
722
723
724
725
726
727
        }
      }
    }
  }
}

728
static void write_delta_q(struct vp9_write_bit_buffer *wb, int delta_q) {
729
  if (delta_q != 0) {
730
731
732
    vp9_wb_write_bit(wb, 1);
    vp9_wb_write_literal(wb, abs(delta_q), 4);
    vp9_wb_write_bit(wb, delta_q < 0);
733
  } else {
734
    vp9_wb_write_bit(wb, 0);
735
736
737
  }
}

738
static void encode_quantization(const VP9_COMMON *const cm,
739
740
741
742
743
                                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);
744
745
}

746
static void encode_segmentation(VP9_COMMON *cm, MACROBLOCKD *xd,
747
                                struct vp9_write_bit_buffer *wb) {
John Koleszar's avatar
John Koleszar committed
748
  int i, j;
749

750
  const struct segmentation *seg = &cm->seg;
751
752
753

  vp9_wb_write_bit(wb, seg->enabled);
  if (!seg->enabled)
754
755
756
    return;

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

    // Write out the chosen coding method.
771
772
    vp9_wb_write_bit(wb, seg->temporal_update);
    if (seg->temporal_update) {
773
      for (i = 0; i < PREDICTION_PROBS; i++) {
774
        const int prob = seg->pred_probs[i];
775
776
777
778
        const int update = prob != MAX_PROB;
        vp9_wb_write_bit(wb, update);
        if (update)
          vp9_wb_write_literal(wb, prob, 8);
779
780
781
782
783
      }
    }
  }

  // Segmentation data
784
785
786
  vp9_wb_write_bit(wb, seg->update_data);
  if (seg->update_data) {
    vp9_wb_write_bit(wb, seg->abs_delta);
787

Paul Wilkins's avatar
Paul Wilkins committed
788
    for (i = 0; i < MAX_SEGMENTS; i++) {
789
      for (j = 0; j < SEG_LVL_MAX; j++) {
790
        const int active = vp9_segfeature_active(seg, i, j);
791
792
        vp9_wb_write_bit(wb, active);
        if (active) {
793
          const int data = vp9_get_segdata(seg, i, j);
794
          const int data_max = vp9_seg_feature_data_max(j);
795
796

          if (vp9_is_segfeature_signed(j)) {
797
            encode_unsigned_max(wb, abs(data), data_max);
798
            vp9_wb_write_bit(wb, data < 0);
799
          } else {
800
            encode_unsigned_max(wb, data, data_max);
801
802
803
804
805
806
807
          }
        }
      }
    }
  }
}

808
809
static void encode_txfm_probs(VP9_COMMON *cm, vp9_writer *w,
                              FRAME_COUNTS *counts) {
810
  // Mode
811
812
813
  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);