vp9_bitstream.c 74.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 14 15 16 17
#include "vp9/common/vp9_header.h"
#include "vp9_encodemv.h"
#include "vp9/common/vp9_entropymode.h"
#include "vp9/common/vp9_findnearmv.h"
#include "vp9_mcomp.h"
#include "vp9/common/vp9_systemdependent.h"
John Koleszar's avatar
John Koleszar committed
18 19
#include <assert.h>
#include <stdio.h>
20
#include <limits.h>
21
#include "vp9/common/vp9_pragmas.h"
22
#include "vpx/vpx_encoder.h"
John Koleszar's avatar
John Koleszar committed
23
#include "vpx_mem/vpx_mem.h"
24 25
#include "vp9_bitstream.h"
#include "vp9_segmentation.h"
26

27 28 29 30 31 32
#include "vp9/common/vp9_seg_common.h"
#include "vp9/common/vp9_pred_common.h"
#include "vp9/common/vp9_entropy.h"
#include "vp9/encoder/vp9_encodemv.h"
#include "vp9/common/vp9_entropymv.h"
#include "vp9/common/vp9_mvref_common.h"
Paul Wilkins's avatar
Paul Wilkins committed
33

John Koleszar's avatar
John Koleszar committed
34 35 36 37 38
#if defined(SECTIONBITS_OUTPUT)
unsigned __int64 Sectionbits[500];
#endif

#ifdef ENTROPY_STATS
39 40 41
int intra_mode_stats[VP9_KF_BINTRAMODES]
                    [VP9_KF_BINTRAMODES]
                    [VP9_KF_BINTRAMODES];
42
unsigned int tree_update_hist [BLOCK_TYPES]
43 44 45
                              [COEF_BANDS]
                              [PREV_COEF_CONTEXTS]
                              [ENTROPY_NODES][2];
46 47 48 49
unsigned int hybrid_tree_update_hist [BLOCK_TYPES]
                                     [COEF_BANDS]
                                     [PREV_COEF_CONTEXTS]
                                     [ENTROPY_NODES][2];
50
unsigned int tree_update_hist_8x8 [BLOCK_TYPES_8X8]
51 52 53
                                  [COEF_BANDS]
                                  [PREV_COEF_CONTEXTS]
                                  [ENTROPY_NODES] [2];
54 55 56 57
unsigned int hybrid_tree_update_hist_8x8 [BLOCK_TYPES_8X8]
                                         [COEF_BANDS]
                                         [PREV_COEF_CONTEXTS]
                                         [ENTROPY_NODES] [2];
Daniel Kang's avatar
Daniel Kang committed
58 59 60 61
unsigned int tree_update_hist_16x16 [BLOCK_TYPES_16X16]
                                    [COEF_BANDS]
                                    [PREV_COEF_CONTEXTS]
                                    [ENTROPY_NODES] [2];
62 63 64 65
unsigned int hybrid_tree_update_hist_16x16 [BLOCK_TYPES_16X16]
                                           [COEF_BANDS]
                                           [PREV_COEF_CONTEXTS]
                                           [ENTROPY_NODES] [2];
66

John Koleszar's avatar
John Koleszar committed
67 68 69 70 71 72 73
extern unsigned int active_section;
#endif

#ifdef MODE_STATS
int count_mb_seg[4] = { 0, 0, 0, 0 };
#endif

74 75
#define vp9_cost_upd  ((int)(vp9_cost_one(upd) - vp9_cost_zero(upd)) >> 8)
#define vp9_cost_upd256  ((int)(vp9_cost_one(upd) - vp9_cost_zero(upd)))
76 77 78 79

#define SEARCH_NEWP
static int update_bits[255];

John Koleszar's avatar
John Koleszar committed
80 81 82
static void compute_update_table() {
  int i;
  for (i = 0; i < 255; i++)
83
    update_bits[i] = vp9_count_term_subexp(i, SUBEXP_PARAM, 255);
84 85
}

John Koleszar's avatar
John Koleszar committed
86 87 88 89 90
static int split_index(int i, int n, int modulus) {
  int max1 = (n - 1 - modulus / 2) / modulus + 1;
  if (i % modulus == modulus / 2) i = i / modulus;
  else i = max1 + i - (i + modulus - modulus / 2) / modulus;
  return i;
91 92
}

John Koleszar's avatar
John Koleszar committed
93 94 95 96 97
static int remap_prob(int v, int m) {
  const int n = 256;
  const int modulus = MODULUS_PARAM;
  int i;
  if ((m << 1) <= n)
98
    i = vp9_recenter_nonneg(v, m) - 1;
John Koleszar's avatar
John Koleszar committed
99
  else
100
    i = vp9_recenter_nonneg(n - 1 - v, n - 1 - m) - 1;
John Koleszar's avatar
John Koleszar committed
101 102 103

  i = split_index(i, n - 1, modulus);
  return i;
104
}
105

106 107
static void write_prob_diff_update(vp9_writer *const bc,
                                   vp9_prob newp, vp9_prob oldp) {
John Koleszar's avatar
John Koleszar committed
108
  int delp = remap_prob(newp, oldp);
109
  vp9_encode_term_subexp(bc, delp, SUBEXP_PARAM, 255);
110 111
}

112
static int prob_diff_update_cost(vp9_prob newp, vp9_prob oldp) {
John Koleszar's avatar
John Koleszar committed
113 114
  int delp = remap_prob(newp, oldp);
  return update_bits[delp] * 256;
115
}
116

John Koleszar's avatar
John Koleszar committed
117
static void update_mode(
118
  vp9_writer *const bc,
John Koleszar's avatar
John Koleszar committed
119
  int n,
120 121 122 123
  vp9_token tok               [/* n */],
  vp9_tree tree,
  vp9_prob Pnew               [/* n-1 */],
  vp9_prob Pcur               [/* n-1 */],
John Koleszar's avatar
John Koleszar committed
124 125 126 127 128 129
  unsigned int bct            [/* n-1 */] [2],
  const unsigned int num_events[/* n */]
) {
  unsigned int new_b = 0, old_b = 0;
  int i = 0;

130
  vp9_tree_probs_from_distribution(
John Koleszar's avatar
John Koleszar committed
131 132 133 134 135 136
    n--, tok, tree,
    Pnew, bct, num_events,
    256, 1
  );

  do {
137 138
    new_b += cost_branch(bct[i], Pnew[i]);
    old_b += cost_branch(bct[i], Pcur[i]);
John Koleszar's avatar
John Koleszar committed
139 140 141
  } while (++i < n);

  if (new_b + (n << 8) < old_b) {
John Koleszar's avatar
John Koleszar committed
142 143
    int i = 0;

144
    vp9_write_bit(bc, 1);
John Koleszar's avatar
John Koleszar committed
145

John Koleszar's avatar
John Koleszar committed
146
    do {
147
      const vp9_prob p = Pnew[i];
John Koleszar's avatar
John Koleszar committed
148

149
      vp9_write_literal(bc, Pcur[i] = p ? p : 1, 8);
John Koleszar's avatar
John Koleszar committed
150 151
    } while (++i < n);
  } else
152
    vp9_write_bit(bc, 0);
John Koleszar's avatar
John Koleszar committed
153 154
}

155
static void update_mbintra_mode_probs(VP9_COMP* const cpi,
156
                                      vp9_writer* const bc) {
157
  VP9_COMMON *const cm = &cpi->common;
John Koleszar's avatar
John Koleszar committed
158

John Koleszar's avatar
John Koleszar committed
159
  {
160 161
    vp9_prob Pnew   [VP9_YMODES - 1];
    unsigned int bct [VP9_YMODES - 1] [2];
John Koleszar's avatar
John Koleszar committed
162

John Koleszar's avatar
John Koleszar committed
163
    update_mode(
164
      bc, VP9_YMODES, vp9_ymode_encodings, vp9_ymode_tree,
Paul Wilkins's avatar
Paul Wilkins committed
165
      Pnew, cm->fc.ymode_prob, bct, (unsigned int *)cpi->ymode_count
John Koleszar's avatar
John Koleszar committed
166
    );
167 168 169 170 171
#if CONFIG_SUPERBLOCKS
    update_mode(bc, VP9_I32X32_MODES, vp9_sb_ymode_encodings,
                vp9_sb_ymode_tree, Pnew, cm->fc.sb_ymode_prob, bct,
                (unsigned int *)cpi->sb_ymode_count);
#endif
John Koleszar's avatar
John Koleszar committed
172
  }
John Koleszar's avatar
John Koleszar committed
173 174
}

John Koleszar's avatar
John Koleszar committed
175
static int get_prob(int num, int den) {
176 177 178 179
  int p;
  if (den <= 0)
    return 128;
  p = (num * 255 + (den >> 1)) / den;
180
  return clip_prob(p);
181 182
}

John Koleszar's avatar
John Koleszar committed
183 184 185 186
static int get_binary_prob(int n0, int n1) {
  return get_prob(n0, n0 + n1);
}

187 188
void vp9_update_skip_probs(VP9_COMP *cpi) {
  VP9_COMMON *const pc = &cpi->common;
John Koleszar's avatar
John Koleszar committed
189
  int k;
Paul Wilkins's avatar
Paul Wilkins committed
190

John Koleszar's avatar
John Koleszar committed
191
  for (k = 0; k < MBSKIP_CONTEXTS; ++k) {
John Koleszar's avatar
John Koleszar committed
192 193
    pc->mbskip_pred_probs[k] = get_binary_prob(cpi->skip_false_count[k],
                                               cpi->skip_true_count[k]);
John Koleszar's avatar
John Koleszar committed
194
  }
Paul Wilkins's avatar
Paul Wilkins committed
195 196
}

197
static void update_switchable_interp_probs(VP9_COMP *cpi,
198
                                           vp9_writer* const bc) {
199
  VP9_COMMON *const pc = &cpi->common;
200 201
  unsigned int branch_ct[32][2];
  int i, j;
202
  for (j = 0; j <= VP9_SWITCHABLE_FILTERS; ++j) {
203
    vp9_tree_probs_from_distribution(
204
        VP9_SWITCHABLE_FILTERS,
205
        vp9_switchable_interp_encodings, vp9_switchable_interp_tree,
206 207
        pc->fc.switchable_interp_prob[j], branch_ct,
        cpi->switchable_interp_count[j], 256, 1);
208
    for (i = 0; i < VP9_SWITCHABLE_FILTERS - 1; ++i) {
209 210
      if (pc->fc.switchable_interp_prob[j][i] < 1)
        pc->fc.switchable_interp_prob[j][i] = 1;
211
      vp9_write_literal(bc, pc->fc.switchable_interp_prob[j][i], 8);
212 213 214 215
    }
  }
}

216
// This function updates the reference frame prediction stats
217 218
static void update_refpred_stats(VP9_COMP *cpi) {
  VP9_COMMON *const cm = &cpi->common;
John Koleszar's avatar
John Koleszar committed
219
  int i;
220
  vp9_prob new_pred_probs[PREDICTION_PROBS];
John Koleszar's avatar
John Koleszar committed
221 222 223 224 225 226 227 228 229 230 231 232 233 234
  int old_cost, new_cost;

  // Set the prediction probability structures to defaults
  if (cm->frame_type == KEY_FRAME) {
    // Set the prediction probabilities to defaults
    cm->ref_pred_probs[0] = 120;
    cm->ref_pred_probs[1] = 80;
    cm->ref_pred_probs[2] = 40;

    vpx_memset(cpi->ref_pred_probs_update, 0,
               sizeof(cpi->ref_pred_probs_update));
  } else {
    // From the prediction counts set the probabilities for each context
    for (i = 0; i < PREDICTION_PROBS; i++) {
John Koleszar's avatar
John Koleszar committed
235 236
      new_pred_probs[i] = get_binary_prob(cpi->ref_pred_count[i][0],
                                          cpi->ref_pred_count[i][1]);
John Koleszar's avatar
John Koleszar committed
237 238 239 240

      // Decide whether or not to update the reference frame probs.
      // Returned costs are in 1/256 bit units.
      old_cost =
241 242
        (cpi->ref_pred_count[i][0] * vp9_cost_zero(cm->ref_pred_probs[i])) +
        (cpi->ref_pred_count[i][1] * vp9_cost_one(cm->ref_pred_probs[i]));
John Koleszar's avatar
John Koleszar committed
243 244

      new_cost =
245 246
        (cpi->ref_pred_count[i][0] * vp9_cost_zero(new_pred_probs[i])) +
        (cpi->ref_pred_count[i][1] * vp9_cost_one(new_pred_probs[i]));
John Koleszar's avatar
John Koleszar committed
247 248 249 250 251 252 253

      // Cost saving must be >= 8 bits (2048 in these units)
      if ((old_cost - new_cost) >= 2048) {
        cpi->ref_pred_probs_update[i] = 1;
        cm->ref_pred_probs[i] = new_pred_probs[i];
      } else
        cpi->ref_pred_probs_update[i] = 0;
254 255

    }
John Koleszar's avatar
John Koleszar committed
256
  }
257 258
}

259 260 261 262 263 264 265 266 267 268 269 270 271 272 273 274 275 276 277 278 279 280 281 282 283 284 285 286 287 288 289 290 291 292 293 294
// This function is called to update the mode probability context used to encode
// inter modes. It assumes the branch counts table has already been populated
// prior to the actual packing of the bitstream (in rd stage or dummy pack)
//
// The branch counts table is re-populated during the actual pack stage and in
// the decoder to facilitate backwards update of the context.
static update_mode_probs(VP9_COMMON *cm,
                         int mode_context[INTER_MODE_CONTEXTS][4]) {
  int i, j;
  int (*mv_ref_ct)[4][2];

  vpx_memcpy(mode_context, cm->fc.vp9_mode_contexts,
             sizeof(cm->fc.vp9_mode_contexts));

  mv_ref_ct = cm->fc.mv_ref_ct;

  for (i = 0; i < INTER_MODE_CONTEXTS; i++) {
    for (j = 0; j < 4; j++) {
      int new_prob, count, old_cost, new_cost;

      // Work out cost of coding branches with the old and optimal probability
      old_cost = cost_branch256(mv_ref_ct[i][j], mode_context[i][j]);
      count = mv_ref_ct[i][j][0] + mv_ref_ct[i][j][1];
      new_prob = count > 0 ? (255 * mv_ref_ct[i][j][0]) / count : 128;
      new_prob = (new_prob > 0) ? new_prob : 1;
      new_cost = cost_branch256(mv_ref_ct[i][j], new_prob);

      // If cost saving is >= 14 bits then update the mode probability.
      // This is the approximate net cost of updating one probability given
      // that the no update case ismuch more common than the update case.
      if (new_cost <= (old_cost - (14 << 8))) {
        mode_context[i][j] = new_prob;
      }
    }
  }
}
295 296
static void write_ymode(vp9_writer *bc, int m, const vp9_prob *p) {
  write_token(bc, vp9_ymode_tree, p, vp9_ymode_encodings + m);
John Koleszar's avatar
John Koleszar committed
297 298
}

299 300
static void kfwrite_ymode(vp9_writer *bc, int m, const vp9_prob *p) {
  write_token(bc, vp9_kf_ymode_tree, p, vp9_kf_ymode_encodings + m);
John Koleszar's avatar
John Koleszar committed
301 302
}

Ronald S. Bultje's avatar
Ronald S. Bultje committed
303
#if CONFIG_SUPERBLOCKS
304 305 306 307
static void write_sb_ymode(vp9_writer *bc, int m, const vp9_prob *p) {
  write_token(bc, vp9_sb_ymode_tree, p, vp9_sb_ymode_encodings + m);
}

308 309
static void sb_kfwrite_ymode(vp9_writer *bc, int m, const vp9_prob *p) {
  write_token(bc, vp9_uv_mode_tree, p, vp9_sb_kf_ymode_encodings + m);
Ronald S. Bultje's avatar
Ronald S. Bultje committed
310 311 312
}
#endif

313 314
static void write_i8x8_mode(vp9_writer *bc, int m, const vp9_prob *p) {
  write_token(bc, vp9_i8x8_mode_tree, p, vp9_i8x8_mode_encodings + m);
Yaowu Xu's avatar
Yaowu Xu committed
315
}
Yaowu Xu's avatar
Yaowu Xu committed
316

317 318
static void write_uv_mode(vp9_writer *bc, int m, const vp9_prob *p) {
  write_token(bc, vp9_uv_mode_tree, p, vp9_uv_mode_encodings + m);
John Koleszar's avatar
John Koleszar committed
319 320 321
}


322
static void write_bmode(vp9_writer *bc, int m, const vp9_prob *p) {
323 324 325 326
#if CONFIG_NEWBINTRAMODES
  assert(m < B_CONTEXT_PRED - CONTEXT_PRED_REPLACEMENTS || m == B_CONTEXT_PRED);
  if (m == B_CONTEXT_PRED) m -= CONTEXT_PRED_REPLACEMENTS;
#endif
327
  write_token(bc, vp9_bmode_tree, p, vp9_bmode_encodings + m);
John Koleszar's avatar
John Koleszar committed
328 329
}

330 331 332 333
static void write_kf_bmode(vp9_writer *bc, int m, const vp9_prob *p) {
  write_token(bc, vp9_kf_bmode_tree, p, vp9_kf_bmode_encodings + m);
}

334
static void write_split(vp9_writer *bc, int x, const vp9_prob *p) {
335 336
  write_token(
    bc, vp9_mbsplit_tree, p, vp9_mbsplit_encodings + x);
John Koleszar's avatar
John Koleszar committed
337 338
}

339
static int prob_update_savings(const unsigned int *ct,
340 341 342 343 344
                               const vp9_prob oldp, const vp9_prob newp,
                               const vp9_prob upd) {
  const int old_b = cost_branch256(ct, oldp);
  const int new_b = cost_branch256(ct, newp);
  const int update_b = 2048 + vp9_cost_upd256;
John Koleszar's avatar
John Koleszar committed
345
  return (old_b - new_b - update_b);
346 347
}

348
static int prob_diff_update_savings(const unsigned int *ct,
349 350 351 352
                                    const vp9_prob oldp, const vp9_prob newp,
                                    const vp9_prob upd) {
  const int old_b = cost_branch256(ct, oldp);
  const int new_b = cost_branch256(ct, newp);
John Koleszar's avatar
John Koleszar committed
353
  const int update_b = (newp == oldp ? 0 :
354
                        prob_diff_update_cost(newp, oldp) + vp9_cost_upd256);
John Koleszar's avatar
John Koleszar committed
355
  return (old_b - new_b - update_b);
356 357 358
}

static int prob_diff_update_savings_search(const unsigned int *ct,
359 360 361
                                           const vp9_prob oldp, vp9_prob *bestp,
                                           const vp9_prob upd) {
  const int old_b = cost_branch256(ct, oldp);
John Koleszar's avatar
John Koleszar committed
362
  int new_b, update_b, savings, bestsavings, step;
363
  vp9_prob newp, bestnewp;
John Koleszar's avatar
John Koleszar committed
364 365 366 367 368 369

  bestsavings = 0;
  bestnewp = oldp;

  step = (*bestp > oldp ? -1 : 1);
  for (newp = *bestp; newp != oldp; newp += step) {
370 371
    new_b = cost_branch256(ct, newp);
    update_b = prob_diff_update_cost(newp, oldp) + vp9_cost_upd256;
John Koleszar's avatar
John Koleszar committed
372 373 374 375
    savings = old_b - new_b - update_b;
    if (savings > bestsavings) {
      bestsavings = savings;
      bestnewp = newp;
376
    }
John Koleszar's avatar
John Koleszar committed
377 378 379
  }
  *bestp = bestnewp;
  return bestsavings;
380 381
}

382 383 384 385 386 387 388 389 390 391 392 393 394 395 396
static void vp9_cond_prob_update(vp9_writer *bc, vp9_prob *oldp, vp9_prob upd,
                                 unsigned int *ct) {
  vp9_prob newp;
  int savings;
  newp = get_binary_prob(ct[0], ct[1]);
  savings = prob_update_savings(ct, *oldp, newp, upd);
  if (savings > 0) {
    vp9_write(bc, 1, upd);
    vp9_write_literal(bc, newp, 8);
    *oldp = newp;
  } else {
    vp9_write(bc, 0, upd);
  }
}

397
static void pack_mb_tokens(vp9_writer* const bc,
398 399
                           TOKENEXTRA **tp,
                           const TOKENEXTRA *const stop) {
John Koleszar's avatar
John Koleszar committed
400 401
  unsigned int split;
  unsigned int shift;
John Koleszar's avatar
John Koleszar committed
402 403 404
  int count = bc->count;
  unsigned int range = bc->range;
  unsigned int lowvalue = bc->lowvalue;
405
  TOKENEXTRA *p = *tp;
John Koleszar's avatar
John Koleszar committed
406

John Koleszar's avatar
John Koleszar committed
407 408
  while (p < stop) {
    const int t = p->Token;
409 410
    vp9_token *const a = vp9_coef_encodings + t;
    const vp9_extra_bit_struct *const b = vp9_extra_bits + t;
John Koleszar's avatar
John Koleszar committed
411 412 413 414 415
    int i = 0;
    const unsigned char *pp = p->context_tree;
    int v = a->value;
    int n = a->Len;

416 417 418 419 420 421
    if (t == EOSB_TOKEN)
    {
      ++p;
      break;
    }

John Koleszar's avatar
John Koleszar committed
422 423 424 425 426
    /* 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
427

John Koleszar's avatar
John Koleszar committed
428 429 430
    do {
      const int bb = (v >> --n) & 1;
      split = 1 + (((range - 1) * pp[i >> 1]) >> 8);
431
      i = vp9_coef_tree[i + bb];
John Koleszar's avatar
John Koleszar committed
432

John Koleszar's avatar
John Koleszar committed
433 434 435 436 437 438
      if (bb) {
        lowvalue += split;
        range = range - split;
      } else {
        range = split;
      }
John Koleszar's avatar
John Koleszar committed
439

440
      shift = vp9_norm[range];
John Koleszar's avatar
John Koleszar committed
441 442
      range <<= shift;
      count += shift;
John Koleszar's avatar
John Koleszar committed
443

John Koleszar's avatar
John Koleszar committed
444 445
      if (count >= 0) {
        int offset = shift - count;
John Koleszar's avatar
John Koleszar committed
446

John Koleszar's avatar
John Koleszar committed
447
        if ((lowvalue << (offset - 1)) & 0x80000000) {
John Koleszar's avatar
John Koleszar committed
448
          int x = bc->pos - 1;
John Koleszar's avatar
John Koleszar committed
449

John Koleszar's avatar
John Koleszar committed
450 451
          while (x >= 0 && bc->buffer[x] == 0xff) {
            bc->buffer[x] = (unsigned char)0;
John Koleszar's avatar
John Koleszar committed
452 453
            x--;
          }
John Koleszar's avatar
John Koleszar committed
454

John Koleszar's avatar
John Koleszar committed
455
          bc->buffer[x] += 1;
John Koleszar's avatar
John Koleszar committed
456
        }
John Koleszar's avatar
John Koleszar committed
457

John Koleszar's avatar
John Koleszar committed
458
        bc->buffer[bc->pos++] = (lowvalue >> (24 - offset));
John Koleszar's avatar
John Koleszar committed
459 460 461 462 463
        lowvalue <<= offset;
        shift = count;
        lowvalue &= 0xffffff;
        count -= 8;
      }
John Koleszar's avatar
John Koleszar committed
464

John Koleszar's avatar
John Koleszar committed
465 466
      lowvalue <<= shift;
    } while (n);
John Koleszar's avatar
John Koleszar committed
467 468


John Koleszar's avatar
John Koleszar committed
469 470
    if (b->base_val) {
      const int e = p->Extra, L = b->Len;
John Koleszar's avatar
John Koleszar committed
471

John Koleszar's avatar
John Koleszar committed
472 473 474 475 476
      if (L) {
        const unsigned char *pp = b->prob;
        int v = e >> 1;
        int n = L;              /* number of bits in v, assumed nonzero */
        int i = 0;
John Koleszar's avatar
John Koleszar committed
477

John Koleszar's avatar
John Koleszar committed
478 479 480 481
        do {
          const int bb = (v >> --n) & 1;
          split = 1 + (((range - 1) * pp[i >> 1]) >> 8);
          i = b->tree[i + bb];
John Koleszar's avatar
John Koleszar committed
482

John Koleszar's avatar
John Koleszar committed
483 484 485 486 487 488
          if (bb) {
            lowvalue += split;
            range = range - split;
          } else {
            range = split;
          }
John Koleszar's avatar
John Koleszar committed
489

490
          shift = vp9_norm[range];
John Koleszar's avatar
John Koleszar committed
491 492
          range <<= shift;
          count += shift;
John Koleszar's avatar
John Koleszar committed
493

John Koleszar's avatar
John Koleszar committed
494 495
          if (count >= 0) {
            int offset = shift - count;
John Koleszar's avatar
John Koleszar committed
496

John Koleszar's avatar
John Koleszar committed
497
            if ((lowvalue << (offset - 1)) & 0x80000000) {
John Koleszar's avatar
John Koleszar committed
498
              int x = bc->pos - 1;
John Koleszar's avatar
John Koleszar committed
499

John Koleszar's avatar
John Koleszar committed
500 501
              while (x >= 0 && bc->buffer[x] == 0xff) {
                bc->buffer[x] = (unsigned char)0;
John Koleszar's avatar
John Koleszar committed
502 503 504
                x--;
              }

John Koleszar's avatar
John Koleszar committed
505
              bc->buffer[x] += 1;
John Koleszar's avatar
John Koleszar committed
506 507
            }

John Koleszar's avatar
John Koleszar committed
508
            bc->buffer[bc->pos++] = (lowvalue >> (24 - offset));
John Koleszar's avatar
John Koleszar committed
509 510 511 512 513
            lowvalue <<= offset;
            shift = count;
            lowvalue &= 0xffffff;
            count -= 8;
          }
John Koleszar's avatar
John Koleszar committed
514

John Koleszar's avatar
John Koleszar committed
515 516 517
          lowvalue <<= shift;
        } while (n);
      }
John Koleszar's avatar
John Koleszar committed
518 519


John Koleszar's avatar
John Koleszar committed
520
      {
John Koleszar's avatar
John Koleszar committed
521

John Koleszar's avatar
John Koleszar committed
522
        split = (range + 1) >> 1;
John Koleszar's avatar
John Koleszar committed
523

John Koleszar's avatar
John Koleszar committed
524 525 526 527 528 529
        if (e & 1) {
          lowvalue += split;
          range = range - split;
        } else {
          range = split;
        }
John Koleszar's avatar
John Koleszar committed
530

John Koleszar's avatar
John Koleszar committed
531
        range <<= 1;
John Koleszar's avatar
John Koleszar committed
532

John Koleszar's avatar
John Koleszar committed
533
        if ((lowvalue & 0x80000000)) {
John Koleszar's avatar
John Koleszar committed
534
          int x = bc->pos - 1;
John Koleszar's avatar
John Koleszar committed
535

John Koleszar's avatar
John Koleszar committed
536 537
          while (x >= 0 && bc->buffer[x] == 0xff) {
            bc->buffer[x] = (unsigned char)0;
John Koleszar's avatar
John Koleszar committed
538 539
            x--;
          }
John Koleszar's avatar
John Koleszar committed
540

John Koleszar's avatar
John Koleszar committed
541
          bc->buffer[x] += 1;
John Koleszar's avatar
John Koleszar committed
542

John Koleszar's avatar
John Koleszar committed
543
        }
John Koleszar's avatar
John Koleszar committed
544

John Koleszar's avatar
John Koleszar committed
545 546 547 548
        lowvalue  <<= 1;

        if (!++count) {
          count = -8;
John Koleszar's avatar
John Koleszar committed
549
          bc->buffer[bc->pos++] = (lowvalue >> 24);
John Koleszar's avatar
John Koleszar committed
550
          lowvalue &= 0xffffff;
John Koleszar's avatar
John Koleszar committed
551
        }
John Koleszar's avatar
John Koleszar committed
552
      }
John Koleszar's avatar
John Koleszar committed
553 554

    }
John Koleszar's avatar
John Koleszar committed
555 556 557
    ++p;
  }

John Koleszar's avatar
John Koleszar committed
558 559 560
  bc->count = count;
  bc->lowvalue = lowvalue;
  bc->range = range;
561
  *tp = p;
John Koleszar's avatar
John Koleszar committed
562 563
}

John Koleszar's avatar
John Koleszar committed
564 565
static void write_partition_size(unsigned char *cx_data, int size) {
  signed char csize;
John Koleszar's avatar
John Koleszar committed
566

John Koleszar's avatar
John Koleszar committed
567 568 569 570 571 572
  csize = size & 0xff;
  *cx_data = csize;
  csize = (size >> 8) & 0xff;
  *(cx_data + 1) = csize;
  csize = (size >> 16) & 0xff;
  *(cx_data + 2) = csize;
John Koleszar's avatar
John Koleszar committed
573 574 575 576 577

}

static void write_mv_ref
(
578
  vp9_writer *bc, MB_PREDICTION_MODE m, const vp9_prob *p
John Koleszar's avatar
John Koleszar committed
579
) {
580
#if CONFIG_DEBUG
John Koleszar's avatar
John Koleszar committed
581
  assert(NEARESTMV <= m  &&  m <= SPLITMV);
582
#endif
583 584
  write_token(bc, vp9_mv_ref_tree, p,
              vp9_mv_ref_encoding_array - NEARESTMV + m);
John Koleszar's avatar
John Koleszar committed
585 586
}

Ronald S. Bultje's avatar
Ronald S. Bultje committed
587
#if CONFIG_SUPERBLOCKS
588 589
static void write_sb_mv_ref(vp9_writer *bc, MB_PREDICTION_MODE m,
                            const vp9_prob *p) {
Ronald S. Bultje's avatar
Ronald S. Bultje committed
590 591 592
#if CONFIG_DEBUG
  assert(NEARESTMV <= m  &&  m < SPLITMV);
#endif
593 594
  write_token(bc, vp9_sb_mv_ref_tree, p,
              vp9_sb_mv_ref_encoding_array - NEARESTMV + m);
Ronald S. Bultje's avatar
Ronald S. Bultje committed
595 596 597
}
#endif

John Koleszar's avatar
John Koleszar committed
598 599
static void write_sub_mv_ref
(
600
  vp9_writer *bc, B_PREDICTION_MODE m, const vp9_prob *p
John Koleszar's avatar
John Koleszar committed
601
) {
602
#if CONFIG_DEBUG
John Koleszar's avatar
John Koleszar committed
603
  assert(LEFT4X4 <= m  &&  m <= NEW4X4);
604
#endif
605 606
  write_token(bc, vp9_sub_mv_ref_tree, p,
              vp9_sub_mv_ref_encoding_array - LEFT4X4 + m);
John Koleszar's avatar
John Koleszar committed
607 608
}

609
static void write_nmv(vp9_writer *bc, const MV *mv, const int_mv *ref,
John Koleszar's avatar
John Koleszar committed
610
                      const nmv_context *nmvc, int usehp) {
611 612 613 614
  MV e;
  e.row = mv->row - ref->as_mv.row;
  e.col = mv->col - ref->as_mv.col;

615 616
  vp9_encode_nmv(bc, &e, &ref->as_mv, nmvc);
  vp9_encode_nmv_fp(bc, &e, &ref->as_mv, nmvc, usehp);
617 618
}

619
#if CONFIG_NEW_MVREF
620 621
static void vp9_write_mv_ref_id(vp9_writer *w,
                                vp9_prob * ref_id_probs,
622 623 624 625
                                int mv_ref_id) {
  // Encode the index for the MV reference.
  switch (mv_ref_id) {
    case 0:
626
      vp9_write(w, 0, ref_id_probs[0]);
627 628
      break;
    case 1:
629 630
      vp9_write(w, 1, ref_id_probs[0]);
      vp9_write(w, 0, ref_id_probs[1]);
631 632
      break;
    case 2:
633 634 635
      vp9_write(w, 1, ref_id_probs[0]);
      vp9_write(w, 1, ref_id_probs[1]);
      vp9_write(w, 0, ref_id_probs[2]);
636 637
      break;
    case 3:
638 639 640
      vp9_write(w, 1, ref_id_probs[0]);
      vp9_write(w, 1, ref_id_probs[1]);
      vp9_write(w, 1, ref_id_probs[2]);
641 642 643 644 645 646 647 648 649 650
      break;

      // TRAP.. This should not happen
    default:
      assert(0);
      break;
  }
}
#endif

Paul Wilkins's avatar
Paul Wilkins committed
651 652
// This function writes the current macro block's segnment id to the bitstream
// It should only be called if a segment map update is indicated.
653
static void write_mb_segid(vp9_writer *bc,
Paul Wilkins's avatar
Paul Wilkins committed
654
                           const MB_MODE_INFO *mi, const MACROBLOCKD *xd) {
John Koleszar's avatar
John Koleszar committed
655
  // Encode the MB segment id.
Ronald S. Bultje's avatar
Ronald S. Bultje committed
656 657 658
  int seg_id = mi->segment_id;
#if CONFIG_SUPERBLOCKS
  if (mi->encoded_as_sb) {
659
    if (xd->mb_to_right_edge >= 0)
Ronald S. Bultje's avatar
Ronald S. Bultje committed
660
      seg_id = seg_id && xd->mode_info_context[1].mbmi.segment_id;
661
    if (xd->mb_to_bottom_edge >= 0) {
Ronald S. Bultje's avatar
Ronald S. Bultje committed
662 663
      seg_id = seg_id &&
               xd->mode_info_context[xd->mode_info_stride].mbmi.segment_id;
664
      if (xd->mb_to_right_edge >= 0)
Ronald S. Bultje's avatar
Ronald S. Bultje committed
665 666 667 668 669
        seg_id = seg_id &&
                xd->mode_info_context[xd->mode_info_stride + 1].mbmi.segment_id;
    }
  }
#endif
Paul Wilkins's avatar
Paul Wilkins committed
670
  if (xd->segmentation_enabled && xd->update_mb_segmentation_map) {
Ronald S. Bultje's avatar
Ronald S. Bultje committed
671
    switch (seg_id) {
John Koleszar's avatar
John Koleszar committed
672
      case 0:
673 674
        vp9_write(bc, 0, xd->mb_segment_tree_probs[0]);
        vp9_write(bc, 0, xd->mb_segment_tree_probs[1]);
John Koleszar's avatar
John Koleszar committed
675 676
        break;
      case 1:
677 678
        vp9_write(bc, 0, xd->mb_segment_tree_probs[0]);
        vp9_write(bc, 1, xd->mb_segment_tree_probs[1]);
John Koleszar's avatar
John Koleszar committed
679 680
        break;
      case 2:
681 682
        vp9_write(bc, 1, xd->mb_segment_tree_probs[0]);
        vp9_write(bc, 0, xd->mb_segment_tree_probs[2]);
John Koleszar's avatar
John Koleszar committed
683 684
        break;
      case 3:
685 686
        vp9_write(bc, 1, xd->mb_segment_tree_probs[0]);
        vp9_write(bc, 1, xd->mb_segment_tree_probs[2]);
John Koleszar's avatar
John Koleszar committed
687 688 689 690
        break;

        // TRAP.. This should not happen
      default:
691 692
        vp9_write(bc, 0, xd->mb_segment_tree_probs[0]);
        vp9_write(bc, 0, xd->mb_segment_tree_probs[1]);
John Koleszar's avatar
John Koleszar committed
693
        break;
John Koleszar's avatar
John Koleszar committed
694
    }
John Koleszar's avatar
John Koleszar committed
695
  }
John Koleszar's avatar
John Koleszar committed
696 697
}

Paul Wilkins's avatar
Paul Wilkins committed
698
// This function encodes the reference frame
699
static void encode_ref_frame(vp9_writer *const bc,
700
                             VP9_COMMON *const cm,
John Koleszar's avatar
John Koleszar committed
701 702 703 704 705
                             MACROBLOCKD *xd,
                             int segment_id,
                             MV_REFERENCE_FRAME rf) {
  int seg_ref_active;
  int seg_ref_count = 0;
706 707 708
  seg_ref_active = vp9_segfeature_active(xd,
                                         segment_id,
                                         SEG_LVL_REF_FRAME);
John Koleszar's avatar
John Koleszar committed
709 710

  if (seg_ref_active) {
711 712 713 714
    seg_ref_count = vp9_check_segref(xd, segment_id, INTRA_FRAME) +
                    vp9_check_segref(xd, segment_id, LAST_FRAME) +
                    vp9_check_segref(xd, segment_id, GOLDEN_FRAME) +
                    vp9_check_segref(xd, segment_id, ALTREF_FRAME);
John Koleszar's avatar
John Koleszar committed
715 716 717 718 719 720 721
  }

  // If segment level coding of this signal is disabled...
  // or the segment allows multiple reference frame options
  if (!seg_ref_active || (seg_ref_count > 1)) {
    // Values used in prediction model coding
    unsigned char prediction_flag;
722
    vp9_prob pred_prob;
John Koleszar's avatar
John Koleszar committed
723 724 725
    MV_REFERENCE_FRAME pred_rf;

    // Get the context probability the prediction flag
Paul Wilkins's avatar
Paul Wilkins committed
726
    pred_prob = vp9_get_pred_prob(cm, xd, PRED_REF);
John Koleszar's avatar
John Koleszar committed
727 728

    // Get the predicted value.
Paul Wilkins's avatar
Paul Wilkins committed
729
    pred_rf = vp9_get_pred_ref(cm, xd);
John Koleszar's avatar
John Koleszar committed
730 731 732 733 734

    // Did the chosen reference frame match its predicted value.
    prediction_flag =
      (xd->mode_info_context->mbmi.ref_frame == pred_rf);

Paul Wilkins's avatar
Paul Wilkins committed
735
    vp9_set_pred_flag(xd, PRED_REF, prediction_flag);
736
    vp9_write(bc, prediction_flag, pred_prob);
John Koleszar's avatar
John Koleszar committed
737 738 739

    // If not predicted correctly then code value explicitly
    if (!prediction_flag) {
740
      vp9_prob mod_refprobs[PREDICTION_PROBS];
John Koleszar's avatar
John Koleszar committed
741 742 743 744 745 746 747 748

      vpx_memcpy(mod_refprobs,
                 cm->mod_refprobs[pred_rf], sizeof(mod_refprobs));

      // If segment coding enabled blank out options that cant occur by
      // setting the branch probability to 0.
      if (seg_ref_active) {
        mod_refprobs[INTRA_FRAME] *=
749
          vp9_check_segref(xd, segment_id, INTRA_FRAME);
John Koleszar's avatar
John Koleszar committed
750
        mod_refprobs[LAST_FRAME] *=
751
          vp9_check_segref(xd, segment_id, LAST_FRAME);
John Koleszar's avatar
John Koleszar committed
752
        mod_refprobs[GOLDEN_FRAME] *=
753 754
          (vp9_check_segref(xd, segment_id, GOLDEN_FRAME) *
           vp9_check_segref(xd, segment_id, ALTREF_FRAME));
John Koleszar's avatar
John Koleszar committed
755 756 757
      }

      if (mod_refprobs[0]) {
758
        vp9_write(bc, (rf != INTRA_FRAME), mod_refprobs[0]);
John Koleszar's avatar
John Koleszar committed
759 760 761 762 763
      }

      // Inter coded
      if (rf != INTRA_FRAME) {
        if (mod_refprobs[1]) {
764
          vp9_write(bc, (rf != LAST_FRAME), mod_refprobs[1]);
John Koleszar's avatar
John Koleszar committed
765
        }
766

John Koleszar's avatar
John Koleszar committed
767 768
        if (rf != LAST_FRAME) {
          if (mod_refprobs[2]) {
769
            vp9_write(bc, (rf != GOLDEN_FRAME), mod_refprobs[2]);
John Koleszar's avatar
John Koleszar committed
770
          }
771
        }
John Koleszar's avatar
John Koleszar committed
772
      }
Paul Wilkins's avatar
Paul Wilkins committed
773
    }
John Koleszar's avatar
John Koleszar committed
774
  }
Paul Wilkins's avatar
Paul Wilkins committed
775

John Koleszar's avatar
John Koleszar committed
776 777
  // if using the prediction mdoel we have nothing further to do because
  // the reference frame is fully coded by the segment
Paul Wilkins's avatar
Paul Wilkins committed
778
}
John Koleszar's avatar
John Koleszar committed
779

780
// Update the probabilities used to encode reference frame data
781 782
static void update_ref_probs(VP9_COMP *const cpi) {
  VP9_COMMON *const cm = &cpi->common;
783

John Koleszar's avatar
John Koleszar committed
784 785 786 787
  const int *const rfct = cpi->count_mb_ref_frame_usage;
  const int rf_intra = rfct[INTRA_FRAME];
  const int rf_inter = rfct[LAST_FRAME] +
                       rfct[GOLDEN_FRAME] + rfct[ALTREF_FRAME];
788

John Koleszar's avatar
John Koleszar committed
789 790 791
  cm->prob_intra_coded = get_binary_prob(rf_intra, rf_inter);
  cm->prob_last_coded = get_prob(rfct[LAST_FRAME], rf_inter);
  cm->prob_gf_coded = get_binary_prob(rfct[GOLDEN_FRAME], rfct[ALTREF_FRAME]);
792

John Koleszar's avatar
John Koleszar committed
793 794
  // Compute a modified set of probabilities to use when prediction of the
  // reference frame fails
Paul Wilkins's avatar
Paul Wilkins committed
795
  vp9_compute_mod_refprobs(cm);
796 797
}

798
static void pack_inter_mode_mvs(VP9_COMP *const cpi, vp9_writer *const bc) {
799
  VP9_COMMON *const pc = &cpi->common;
800
  const nmv_context *nmvc = &pc->fc.nmvc;
Paul Wilkins's avatar
Paul Wilkins committed
801
  MACROBLOCK *x = &cpi->mb;
John Koleszar's avatar
John Koleszar committed
802 803 804
  MACROBLOCKD *xd = &cpi->mb.e_mbd;
  MODE_INFO *m;
  MODE_INFO *prev_m;
805 806
  TOKENEXTRA *tok = cpi->tok;
  TOKENEXTRA *tok_end = tok + cpi->tok_count;
807

John Koleszar's avatar
John Koleszar committed
808 809 810
  const int mis = pc->mode_info_stride;
  int mb_row, mb_col;
  int row, col;
John Koleszar's avatar
John Koleszar committed
811

John Koleszar's avatar
John Koleszar committed
812
  // Values used in prediction model coding
813
  vp9_prob pred_prob;
John Koleszar's avatar
John Koleszar committed
814
  unsigned char prediction_flag;
815

John Koleszar's avatar
John Koleszar committed
816 817
  int row_delta[4] = { 0, +1,  0, -1};
  int col_delta[4] = { +1, -1, +1, +1};
Adrian Grange's avatar
Adrian Grange committed
818

John Koleszar's avatar
John Koleszar committed
819
  cpi->mb.partition_info = cpi->mb.pi;
820

John Koleszar's avatar
John Koleszar committed
821 822 823 824 825 826 827 828 829 830 831
  mb_row = 0;
  for (row = 0; row < pc->mb_rows; row += 2) {
    m = pc->mi + row * mis;
    prev_m = pc->prev_mi + row * mis;

    mb_col = 0;
    for (col = 0; col < pc->mb_cols; col += 2) {
      int i;

      // Process the 4 MBs in the order:
      // top-left, top-right, bottom-left, bottom-right
Ronald S. Bultje's avatar
Ronald S. Bultje committed
832
#if CONFIG_SUPERBLOCKS
833
      vp9_write(bc, m->mbmi.encoded_as_sb, pc->sb_coded);
Ronald S. Bultje's avatar
Ronald S. Bultje committed
834
#endif
John Koleszar's avatar
John Koleszar committed
835 836 837
      for (i = 0; i < 4; i++) {
        MB_MODE_INFO *mi;
        MV_REFERENCE_FRAME rf;
Deb Mukherjee's avatar
Deb Mukherjee committed
838
        MV_REFERENCE_FRAME sec_ref_frame;
John Koleszar's avatar
John Koleszar committed
839
        MB_PREDICTION_MODE mode;
840
        int segment_id, skip_coeff;
John Koleszar's avatar
John Koleszar committed
841 842 843 844 845 846 847 848 849 850 851 852 853 854

        int dy = row_delta[i];
        int dx = col_delta[i];
        int offset_extended = dy * mis + dx;

        if ((mb_row >= pc->mb_rows) || (mb_col >= pc->mb_cols)) {
          // MB lies outside frame, move on
          mb_row += dy;
          mb_col += dx;
          m += offset_extended;
          prev_m += offset_extended;
          cpi->mb.partition_info += offset_extended;
          continue;
        }
Adrian Grange's avatar
Adrian Grange committed
855

John Koleszar's avatar
John Koleszar committed
856
        mi = &m->mbmi;
John Koleszar's avatar
John Koleszar committed
857
        rf = mi->ref_frame;
Deb Mukherjee's avatar
Deb Mukherjee committed
858
        sec_ref_frame = mi->second_ref_frame;
John Koleszar's avatar
John Koleszar committed
859 860
        mode = mi->mode;
        segment_id = mi->segment_id;