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
  const vp9_prob *const probs = xd->partition_probs[ctx];
407
408
  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
  const VP9_COMMON *const cm = &cpi->common;
485
  MACROBLOCKD *const xd = &cpi->td.mb.e_mbd;
486
  int mi_row, mi_col;
487

488
489
  set_partition_probs(cm, xd);

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(xd->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->td.rd_counts.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
  int i, j, k, l, t;
535
536
  int stepsize = cpi->sf.coeff_prob_appx_step;

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

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

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

                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);
631
                } else {
632
633
634
                  s = vp9_prob_diff_update_savings_search(
                      frame_branch_ct[i][j][k][l][t],
                      *oldp, &newp, upd);
635
                }
636
637
638

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

672
static void update_coef_probs(VP9_COMP *cpi, vp9_writer* w) {
673
  const TX_MODE tx_mode = cpi->common.tx_mode;
674
675
  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
676
677
678
  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
679
    if (cpi->td.counts->tx.tx_totals[tx_size] <= 20 ||
Yaowu Xu's avatar
Yaowu Xu committed
680
681
682
683
684
685
686
687
        (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
688
  }
John Koleszar's avatar
John Koleszar committed
689
}
690

691
static void encode_loopfilter(struct loopfilter *lf,
692
                              struct vp9_write_bit_buffer *wb) {
693
694
  int i;

695
  // Encode the loop filter level and type
696
697
  vp9_wb_write_literal(wb, lf->filter_level, 6);
  vp9_wb_write_literal(wb, lf->sharpness_level, 3);
698

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

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

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

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

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

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

753
  const struct segmentation *seg = &cm->seg;
754
755
756

  vp9_wb_write_bit(wb, seg->enabled);
  if (!seg->enabled)
757
758
759
    return;

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

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

  // Segmentation data
787
788
789
  vp9_wb_write_bit(wb, seg->update_data);
  if (seg->update_data) {
    vp9_wb_write_bit(wb, seg->abs_delta);
790

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

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