vp9_bitstream.c 99.9 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
#include "vp9/common/vp9_header.h"
16
#include "vp9/encoder/vp9_encodemv.h"
17
#include "vp9/common/vp9_entropymode.h"
18
#include "vp9/common/vp9_entropymv.h"
19
#include "vp9/common/vp9_findnearmv.h"
20
#include "vp9/common/vp9_tile_common.h"
21
#include "vp9/encoder/vp9_mcomp.h"
22 23
#include "vp9/common/vp9_systemdependent.h"
#include "vp9/common/vp9_pragmas.h"
24
#include "vpx/vpx_encoder.h"
John Koleszar's avatar
John Koleszar committed
25
#include "vpx_mem/vpx_mem.h"
26 27
#include "vp9/encoder/vp9_bitstream.h"
#include "vp9/encoder/vp9_segmentation.h"
28

29 30 31 32 33 34
#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"
35
#include "vp9/common/vp9_treecoder.h"
Paul Wilkins's avatar
Paul Wilkins committed
36

John Koleszar's avatar
John Koleszar committed
37 38 39 40 41
#if defined(SECTIONBITS_OUTPUT)
unsigned __int64 Sectionbits[500];
#endif

#ifdef ENTROPY_STATS
42 43 44
int intra_mode_stats[VP9_KF_BINTRAMODES]
                    [VP9_KF_BINTRAMODES]
                    [VP9_KF_BINTRAMODES];
45 46 47
vp9_coeff_stats tree_update_hist_4x4[BLOCK_TYPES];
vp9_coeff_stats tree_update_hist_8x8[BLOCK_TYPES];
vp9_coeff_stats tree_update_hist_16x16[BLOCK_TYPES];
48
vp9_coeff_stats tree_update_hist_32x32[BLOCK_TYPES];
49

John Koleszar's avatar
John Koleszar committed
50 51 52
extern unsigned int active_section;
#endif

53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70
#if CONFIG_CODE_NONZEROCOUNT
#ifdef NZC_STATS
unsigned int nzc_stats_4x4[MAX_NZC_CONTEXTS][REF_TYPES][BLOCK_TYPES]
                          [NZC4X4_TOKENS];
unsigned int nzc_stats_8x8[MAX_NZC_CONTEXTS][REF_TYPES][BLOCK_TYPES]
                          [NZC8X8_TOKENS];
unsigned int nzc_stats_16x16[MAX_NZC_CONTEXTS][REF_TYPES][BLOCK_TYPES]
                          [NZC16X16_TOKENS];
unsigned int nzc_stats_32x32[MAX_NZC_CONTEXTS][REF_TYPES][BLOCK_TYPES]
                          [NZC32X32_TOKENS];
unsigned int nzc_pcat_stats[MAX_NZC_CONTEXTS][NZC_TOKENS_EXTRA]
                          [NZC_BITS_EXTRA][2];
void init_nzcstats();
void update_nzcstats(VP9_COMMON *const cm);
void print_nzcstats();
#endif
#endif

John Koleszar's avatar
John Koleszar committed
71 72 73 74
#ifdef MODE_STATS
int count_mb_seg[4] = { 0, 0, 0, 0 };
#endif

75 76
#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)))
77 78 79 80

#define SEARCH_NEWP
static int update_bits[255];

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

John Koleszar's avatar
John Koleszar committed
87 88 89 90 91
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;
92 93
}

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

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

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

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

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

131 132
  vp9_tree_probs_from_distribution(tree, Pnew, bct, num_events, 0);
  n--;
John Koleszar's avatar
John Koleszar committed
133 134

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

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

142
    vp9_write_bit(bc, 1);
John Koleszar's avatar
John Koleszar committed
143

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

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

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

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

John Koleszar's avatar
John Koleszar committed
161
    update_mode(
162
      bc, VP9_YMODES, vp9_ymode_encodings, vp9_ymode_tree,
Paul Wilkins's avatar
Paul Wilkins committed
163
      Pnew, cm->fc.ymode_prob, bct, (unsigned int *)cpi->ymode_count
John Koleszar's avatar
John Koleszar committed
164
    );
165 166 167
    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);
John Koleszar's avatar
John Koleszar committed
168
  }
John Koleszar's avatar
John Koleszar committed
169 170
}

171 172
void vp9_update_skip_probs(VP9_COMP *cpi) {
  VP9_COMMON *const pc = &cpi->common;
John Koleszar's avatar
John Koleszar committed
173
  int k;
Paul Wilkins's avatar
Paul Wilkins committed
174

John Koleszar's avatar
John Koleszar committed
175
  for (k = 0; k < MBSKIP_CONTEXTS; ++k) {
John Koleszar's avatar
John Koleszar committed
176 177
    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
178
  }
Paul Wilkins's avatar
Paul Wilkins committed
179 180
}

181
static void update_switchable_interp_probs(VP9_COMP *cpi,
182
                                           vp9_writer* const bc) {
183
  VP9_COMMON *const pc = &cpi->common;
184 185
  unsigned int branch_ct[32][2];
  int i, j;
186
  for (j = 0; j <= VP9_SWITCHABLE_FILTERS; ++j) {
187
    vp9_tree_probs_from_distribution(
188
        vp9_switchable_interp_tree,
189
        pc->fc.switchable_interp_prob[j], branch_ct,
190
        cpi->switchable_interp_count[j], 0);
191
    for (i = 0; i < VP9_SWITCHABLE_FILTERS - 1; ++i) {
192 193
      if (pc->fc.switchable_interp_prob[j][i] < 1)
        pc->fc.switchable_interp_prob[j][i] = 1;
194
      vp9_write_literal(bc, pc->fc.switchable_interp_prob[j][i], 8);
195 196 197 198
    }
  }
}

199
// This function updates the reference frame prediction stats
200 201
static void update_refpred_stats(VP9_COMP *cpi) {
  VP9_COMMON *const cm = &cpi->common;
John Koleszar's avatar
John Koleszar committed
202
  int i;
203
  vp9_prob new_pred_probs[PREDICTION_PROBS];
John Koleszar's avatar
John Koleszar committed
204 205 206
  int old_cost, new_cost;

  // Set the prediction probability structures to defaults
207
  if (cm->frame_type != KEY_FRAME) {
John Koleszar's avatar
John Koleszar committed
208 209
    // From the prediction counts set the probabilities for each context
    for (i = 0; i < PREDICTION_PROBS; i++) {
John Koleszar's avatar
John Koleszar committed
210 211
      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
212 213 214 215

      // Decide whether or not to update the reference frame probs.
      // Returned costs are in 1/256 bit units.
      old_cost =
216 217
        (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
218 219

      new_cost =
220 221
        (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
222 223 224 225 226 227 228

      // 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;
229
    }
John Koleszar's avatar
John Koleszar committed
230
  }
231 232
}

233 234 235 236 237 238
// 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.
239 240
static void update_inter_mode_probs(VP9_COMMON *cm,
                                    int mode_context[INTER_MODE_CONTEXTS][4]) {
241
  int i, j;
Jim Bankoski's avatar
Jim Bankoski committed
242
  unsigned int (*mv_ref_ct)[4][2];
243 244 245 246 247 248 249 250

  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++) {
251
      int new_prob, old_cost, new_cost;
252 253 254

      // 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]);
255
      new_prob = get_binary_prob(mv_ref_ct[i][j][0], mv_ref_ct[i][j][1]);
256 257 258 259 260 261 262 263 264 265 266
      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;
      }
    }
  }
}
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 295 296 297 298 299 300 301 302 303 304 305 306 307 308 309 310 311 312 313 314 315 316

#if CONFIG_NEW_MVREF
static void update_mv_ref_probs(VP9_COMP *cpi,
                                int mvref_probs[MAX_REF_FRAMES]
                                               [MAX_MV_REF_CANDIDATES-1]) {
  MACROBLOCKD *xd = &cpi->mb.e_mbd;
  int rf;     // Reference frame
  int ref_c;  // Motion reference candidate
  int node;   // Probability node index

  for (rf = 0; rf < MAX_REF_FRAMES; ++rf) {
    int count = 0;

    // Skip the dummy entry for intra ref frame.
    if (rf == INTRA_FRAME) {
      continue;
    }

    // Sum the counts for all candidates
    for (ref_c = 0; ref_c < MAX_MV_REF_CANDIDATES; ++ref_c) {
      count += cpi->mb_mv_ref_count[rf][ref_c];
    }

    // Calculate the tree node probabilities
    for (node = 0; node < MAX_MV_REF_CANDIDATES-1; ++node) {
      int new_prob, old_cost, new_cost;
      unsigned int branch_cnts[2];

      // How many hits on each branch at this node
      branch_cnts[0] = cpi->mb_mv_ref_count[rf][node];
      branch_cnts[1] = count - cpi->mb_mv_ref_count[rf][node];

      // Work out cost of coding branches with the old and optimal probability
      old_cost = cost_branch256(branch_cnts, xd->mb_mv_ref_probs[rf][node]);
      new_prob = get_prob(branch_cnts[0], count);
      new_cost = cost_branch256(branch_cnts, new_prob);

      // Take current 0 branch cases out of residual count
      count -= cpi->mb_mv_ref_count[rf][node];

      if ((new_cost + VP9_MV_REF_UPDATE_COST) <= old_cost) {
        mvref_probs[rf][node] = new_prob;
      } else {
        mvref_probs[rf][node] = xd->mb_mv_ref_probs[rf][node];
      }
    }
  }
}
#endif

317 318
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
319 320
}

321 322
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
323 324
}

325 326 327 328
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);
}

329 330
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
331 332
}

333 334
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
335
}
Yaowu Xu's avatar
Yaowu Xu committed
336

337 338
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
339 340 341
}


342
static void write_bmode(vp9_writer *bc, int m, const vp9_prob *p) {
343 344 345 346
#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
347
  write_token(bc, vp9_bmode_tree, p, vp9_bmode_encodings + m);
John Koleszar's avatar
John Koleszar committed
348 349
}

350 351 352 353
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);
}

354
static void write_split(vp9_writer *bc, int x, const vp9_prob *p) {
355 356
  write_token(
    bc, vp9_mbsplit_tree, p, vp9_mbsplit_encodings + x);
John Koleszar's avatar
John Koleszar committed
357 358
}

359
static int prob_update_savings(const unsigned int *ct,
360 361 362 363 364
                               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
365
  return (old_b - new_b - update_b);
366 367
}

368
static int prob_diff_update_savings(const unsigned int *ct,
369 370 371 372
                                    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
373
  const int update_b = (newp == oldp ? 0 :
374
                        prob_diff_update_cost(newp, oldp) + vp9_cost_upd256);
John Koleszar's avatar
John Koleszar committed
375
  return (old_b - new_b - update_b);
376 377 378
}

static int prob_diff_update_savings_search(const unsigned int *ct,
379 380 381
                                           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
382
  int new_b, update_b, savings, bestsavings, step;
383
  vp9_prob newp, bestnewp;
John Koleszar's avatar
John Koleszar committed
384 385 386 387 388 389

  bestsavings = 0;
  bestnewp = oldp;

  step = (*bestp > oldp ? -1 : 1);
  for (newp = *bestp; newp != oldp; newp += step) {
390 391
    new_b = cost_branch256(ct, newp);
    update_b = prob_diff_update_cost(newp, oldp) + vp9_cost_upd256;
John Koleszar's avatar
John Koleszar committed
392 393 394 395
    savings = old_b - new_b - update_b;
    if (savings > bestsavings) {
      bestsavings = savings;
      bestnewp = newp;
396
    }
John Koleszar's avatar
John Koleszar committed
397 398 399
  }
  *bestp = bestnewp;
  return bestsavings;
400 401
}

402 403 404 405 406 407 408 409 410 411 412 413 414 415 416 417 418 419 420 421 422 423 424 425 426 427 428 429 430 431 432 433 434 435 436 437 438
#if CONFIG_MODELCOEFPROB && MODEL_BASED_UPDATE
static int prob_diff_update_savings_search_model(const unsigned int *ct,
                                                 const vp9_prob *oldp,
                                                 vp9_prob *bestp,
                                                 const vp9_prob upd,
                                                 int b, int r) {
  int i, old_b, new_b, update_b, savings, bestsavings, step;
  int newp;
  vp9_prob bestnewp, newplist[ENTROPY_NODES];
  for (i = UNCONSTRAINED_NODES - 1, old_b = 0; i < ENTROPY_NODES; ++i)
    old_b += cost_branch256(ct + 2 * i, oldp[i]);

  bestsavings = 0;
  bestnewp = oldp[UNCONSTRAINED_NODES - 1];

  step = (*bestp > oldp[UNCONSTRAINED_NODES - 1] ? -1 : 1);
  newp = *bestp;
  // newp = *bestp - step * (abs(*bestp - oldp[UNCONSTRAINED_NODES - 1]) >> 1);
  for (; newp != oldp[UNCONSTRAINED_NODES - 1]; newp += step) {
    if (newp < 1 || newp > 255) continue;
    newplist[UNCONSTRAINED_NODES - 1] = newp;
    vp9_get_model_distribution(newp, newplist, b, r);
    for (i = UNCONSTRAINED_NODES - 1, new_b = 0; i < ENTROPY_NODES; ++i)
      new_b += cost_branch256(ct + 2 * i, newplist[i]);
    update_b = prob_diff_update_cost(newp, oldp[UNCONSTRAINED_NODES - 1]) +
        vp9_cost_upd256;
    savings = old_b - new_b - update_b;
    if (savings > bestsavings) {
      bestsavings = savings;
      bestnewp = newp;
    }
  }
  *bestp = bestnewp;
  return bestsavings;
}
#endif

439 440 441 442 443 444 445 446 447 448 449 450 451 452 453
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);
  }
}

454
static void pack_mb_tokens(vp9_writer* const bc,
455 456 457
                           TOKENEXTRA **tp,
                           const TOKENEXTRA *const stop) {
  TOKENEXTRA *p = *tp;
John Koleszar's avatar
John Koleszar committed
458

John Koleszar's avatar
John Koleszar committed
459 460
  while (p < stop) {
    const int t = p->Token;
461 462
    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
463 464 465 466 467
    int i = 0;
    const unsigned char *pp = p->context_tree;
    int v = a->value;
    int n = a->Len;

468 469 470 471 472 473
    if (t == EOSB_TOKEN)
    {
      ++p;
      break;
    }

John Koleszar's avatar
John Koleszar committed
474 475 476 477 478
    /* 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
479

John Koleszar's avatar
John Koleszar committed
480 481
    do {
      const int bb = (v >> --n) & 1;
482
      vp9_write(bc, bb, pp[i >> 1]);
483
      i = vp9_coef_tree[i + bb];
John Koleszar's avatar
John Koleszar committed
484
    } while (n);
John Koleszar's avatar
John Koleszar committed
485 486


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

John Koleszar's avatar
John Koleszar committed
490 491 492 493 494
      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
495

John Koleszar's avatar
John Koleszar committed
496 497
        do {
          const int bb = (v >> --n) & 1;
498
          vp9_write(bc, bb, pp[i >> 1]);
John Koleszar's avatar
John Koleszar committed
499 500 501
          i = b->tree[i + bb];
        } while (n);
      }
John Koleszar's avatar
John Koleszar committed
502

503
      vp9_write_bit(bc, e & 1);
John Koleszar's avatar
John Koleszar committed
504
    }
John Koleszar's avatar
John Koleszar committed
505 506 507
    ++p;
  }

508
  *tp = p;
John Koleszar's avatar
John Koleszar committed
509 510
}

John Koleszar's avatar
John Koleszar committed
511 512
static void write_partition_size(unsigned char *cx_data, int size) {
  signed char csize;
John Koleszar's avatar
John Koleszar committed
513

John Koleszar's avatar
John Koleszar committed
514 515 516 517 518 519
  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
520 521 522 523 524

}

static void write_mv_ref
(
525
  vp9_writer *bc, MB_PREDICTION_MODE m, const vp9_prob *p
John Koleszar's avatar
John Koleszar committed
526
) {
527
#if CONFIG_DEBUG
John Koleszar's avatar
John Koleszar committed
528
  assert(NEARESTMV <= m  &&  m <= SPLITMV);
529
#endif
530 531
  write_token(bc, vp9_mv_ref_tree, p,
              vp9_mv_ref_encoding_array - NEARESTMV + m);
John Koleszar's avatar
John Koleszar committed
532 533
}

534 535
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
536 537 538
#if CONFIG_DEBUG
  assert(NEARESTMV <= m  &&  m < SPLITMV);
#endif
539 540
  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
541 542
}

John Koleszar's avatar
John Koleszar committed
543 544
static void write_sub_mv_ref
(
545
  vp9_writer *bc, B_PREDICTION_MODE m, const vp9_prob *p
John Koleszar's avatar
John Koleszar committed
546
) {
547
#if CONFIG_DEBUG
John Koleszar's avatar
John Koleszar committed
548
  assert(LEFT4X4 <= m  &&  m <= NEW4X4);
549
#endif
550 551
  write_token(bc, vp9_sub_mv_ref_tree, p,
              vp9_sub_mv_ref_encoding_array - LEFT4X4 + m);
John Koleszar's avatar
John Koleszar committed
552 553
}

554 555
static void write_nmv(VP9_COMP *cpi, vp9_writer *bc,
                      const MV *mv, const int_mv *ref,
John Koleszar's avatar
John Koleszar committed
556
                      const nmv_context *nmvc, int usehp) {
557 558 559 560
  MV e;
  e.row = mv->row - ref->as_mv.row;
  e.col = mv->col - ref->as_mv.col;

561 562
  vp9_encode_nmv(bc, &e, &ref->as_mv, nmvc);
  vp9_encode_nmv_fp(bc, &e, &ref->as_mv, nmvc, usehp);
563 564
}

565
#if CONFIG_NEW_MVREF
566 567
static void vp9_write_mv_ref_id(vp9_writer *w,
                                vp9_prob * ref_id_probs,
568 569 570 571
                                int mv_ref_id) {
  // Encode the index for the MV reference.
  switch (mv_ref_id) {
    case 0:
572
      vp9_write(w, 0, ref_id_probs[0]);
573 574
      break;
    case 1:
575 576
      vp9_write(w, 1, ref_id_probs[0]);
      vp9_write(w, 0, ref_id_probs[1]);
577 578
      break;
    case 2:
579 580 581
      vp9_write(w, 1, ref_id_probs[0]);
      vp9_write(w, 1, ref_id_probs[1]);
      vp9_write(w, 0, ref_id_probs[2]);
582 583
      break;
    case 3:
584 585 586
      vp9_write(w, 1, ref_id_probs[0]);
      vp9_write(w, 1, ref_id_probs[1]);
      vp9_write(w, 1, ref_id_probs[2]);
587 588 589 590 591 592 593 594 595 596
      break;

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

Paul Wilkins's avatar
Paul Wilkins committed
597 598
// 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.
599
static void write_mb_segid(vp9_writer *bc,
Paul Wilkins's avatar
Paul Wilkins committed
600
                           const MB_MODE_INFO *mi, const MACROBLOCKD *xd) {
John Koleszar's avatar
John Koleszar committed
601
  // Encode the MB segment id.
Ronald S. Bultje's avatar
Ronald S. Bultje committed
602
  int seg_id = mi->segment_id;
Ronald S. Bultje's avatar
Ronald S. Bultje committed
603

Paul Wilkins's avatar
Paul Wilkins committed
604
  if (xd->segmentation_enabled && xd->update_mb_segmentation_map) {
Ronald S. Bultje's avatar
Ronald S. Bultje committed
605
    switch (seg_id) {
John Koleszar's avatar
John Koleszar committed
606
      case 0:
607 608
        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
609 610
        break;
      case 1:
611 612
        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
613 614
        break;
      case 2:
615 616
        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
617 618
        break;
      case 3:
619 620
        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
621 622 623 624
        break;

        // TRAP.. This should not happen
      default:
625 626
        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
627
        break;
John Koleszar's avatar
John Koleszar committed
628
    }
John Koleszar's avatar
John Koleszar committed
629
  }
John Koleszar's avatar
John Koleszar committed
630 631
}

632 633 634 635 636 637 638 639 640 641 642 643 644 645 646 647 648 649 650 651 652 653
static void write_mb_segid_except(VP9_COMMON *cm,
                                  vp9_writer *bc,
                                  const MB_MODE_INFO *mi,
                                  const MACROBLOCKD *xd,
                                  int mb_row, int mb_col) {
  // Encode the MB segment id.
  int seg_id = mi->segment_id;
  int pred_seg_id = vp9_get_pred_mb_segid(cm, xd,
                                          mb_row * cm->mb_cols + mb_col);
  const vp9_prob *p = xd->mb_segment_tree_probs;
  const vp9_prob p1 = xd->mb_segment_mispred_tree_probs[pred_seg_id];

  if (xd->segmentation_enabled && xd->update_mb_segmentation_map) {
    vp9_write(bc, seg_id >= 2, p1);
    if (pred_seg_id >= 2 && seg_id < 2) {
      vp9_write(bc, seg_id == 1, p[1]);
    } else if (pred_seg_id < 2 && seg_id >= 2) {
      vp9_write(bc, seg_id == 3, p[2]);
    }
  }
}

Paul Wilkins's avatar
Paul Wilkins committed
654
// This function encodes the reference frame
655
static void encode_ref_frame(vp9_writer *const bc,
656
                             VP9_COMMON *const cm,
John Koleszar's avatar
John Koleszar committed
657 658 659 660 661
                             MACROBLOCKD *xd,
                             int segment_id,
                             MV_REFERENCE_FRAME rf) {
  int seg_ref_active;
  int seg_ref_count = 0;
662 663 664
  seg_ref_active = vp9_segfeature_active(xd,
                                         segment_id,
                                         SEG_LVL_REF_FRAME);
John Koleszar's avatar
John Koleszar committed
665 666

  if (seg_ref_active) {
667 668 669 670
    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
671 672 673 674 675 676 677
  }

  // 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;
678
    vp9_prob pred_prob;
John Koleszar's avatar
John Koleszar committed
679 680 681
    MV_REFERENCE_FRAME pred_rf;

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

    // Get the predicted value.
Paul Wilkins's avatar
Paul Wilkins committed
685
    pred_rf = vp9_get_pred_ref(cm, xd);
John Koleszar's avatar
John Koleszar committed
686 687 688 689 690

    // 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
691
    vp9_set_pred_flag(xd, PRED_REF, prediction_flag);
692
    vp9_write(bc, prediction_flag, pred_prob);
John Koleszar's avatar
John Koleszar committed
693 694 695

    // If not predicted correctly then code value explicitly
    if (!prediction_flag) {
696
      vp9_prob mod_refprobs[PREDICTION_PROBS];
John Koleszar's avatar
John Koleszar committed
697 698 699 700 701 702 703 704

      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] *=
705
          vp9_check_segref(xd, segment_id, INTRA_FRAME);
John Koleszar's avatar
John Koleszar committed
706
        mod_refprobs[LAST_FRAME] *=
707
          vp9_check_segref(xd, segment_id, LAST_FRAME);
John Koleszar's avatar
John Koleszar committed
708
        mod_refprobs[GOLDEN_FRAME] *=
709 710
          (vp9_check_segref(xd, segment_id, GOLDEN_FRAME) *
           vp9_check_segref(xd, segment_id, ALTREF_FRAME));
John Koleszar's avatar
John Koleszar committed
711 712 713
      }

      if (mod_refprobs[0]) {
714
        vp9_write(bc, (rf != INTRA_FRAME), mod_refprobs[0]);
John Koleszar's avatar
John Koleszar committed
715 716 717 718 719
      }

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

John Koleszar's avatar
John Koleszar committed
723 724
        if (rf != LAST_FRAME) {
          if (mod_refprobs[2]) {
725
            vp9_write(bc, (rf != GOLDEN_FRAME), mod_refprobs[2]);
John Koleszar's avatar
John Koleszar committed
726
          }
727
        }
John Koleszar's avatar
John Koleszar committed
728
      }
Paul Wilkins's avatar
Paul Wilkins committed
729
    }
John Koleszar's avatar
John Koleszar committed
730
  }
Paul Wilkins's avatar
Paul Wilkins committed
731

John Koleszar's avatar
John Koleszar committed
732 733
  // 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
734
}
John Koleszar's avatar
John Koleszar committed
735

736
// Update the probabilities used to encode reference frame data
737 738
static void update_ref_probs(VP9_COMP *const cpi) {
  VP9_COMMON *const cm = &cpi->common;
739

John Koleszar's avatar
John Koleszar committed
740 741 742 743
  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];
744

John Koleszar's avatar
John Koleszar committed
745 746 747
  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]);
748

John Koleszar's avatar
John Koleszar committed
749 750
  // Compute a modified set of probabilities to use when prediction of the
  // reference frame fails
Paul Wilkins's avatar
Paul Wilkins committed
751
  vp9_compute_mod_refprobs(cm);
752 753
}

Ronald S. Bultje's avatar
Ronald S. Bultje committed
754 755 756
static void pack_inter_mode_mvs(VP9_COMP *cpi, MODE_INFO *m,
                                vp9_writer *bc,
                                int mb_rows_left, int mb_cols_left) {
757
  VP9_COMMON *const pc = &cpi->common;
758
  const nmv_context *nmvc = &pc->fc.nmvc;
Ronald S. Bultje's avatar
Ronald S. Bultje committed
759 760
  MACROBLOCK *const x = &cpi->mb;
  MACROBLOCKD *const xd = &x->e_mbd;
John Koleszar's avatar
John Koleszar committed
761
  const int mis = pc->mode_info_stride;
Ronald S. Bultje's avatar
Ronald S. Bultje committed
762 763 764 765
  MB_MODE_INFO *const mi = &m->mbmi;
  const MV_REFERENCE_FRAME rf = mi->ref_frame;
  const MB_PREDICTION_MODE mode = mi->mode;
  const int segment_id = mi->segment_id;
766 767
  const int bw = 1 << mb_width_log2(mi->sb_type);
  const int bh = 1 << mb_height_log2(mi->sb_type);
Ronald S. Bultje's avatar
Ronald S. Bultje committed
768
  int skip_coeff;
Adrian Grange's avatar
Adrian Grange committed
769

Ronald S. Bultje's avatar
Ronald S. Bultje committed
770 771 772 773
  int mb_row = pc->mb_rows - mb_rows_left;
  int mb_col = pc->mb_cols - mb_cols_left;
  xd->prev_mode_info_context = pc->prev_mi + (m - pc->mi);
  x->partition_info = x->pi + (m - pc->mi);
774

Ronald S. Bultje's avatar
Ronald S. Bultje committed
775 776 777
  // Distance of Mb to the various image edges.
  // These specified to 8th pel as they are always compared to MV
  // values that are in 1/8th pel units
778

779 780
  set_mb_row(pc, xd, mb_row, bh);
  set_mb_col(pc, xd, mb_col, bw);
781

Ronald S. Bultje's avatar
Ronald S. Bultje committed
782 783
#ifdef ENTROPY_STATS
  active_section = 9;
784
#endif
785

Ronald S. Bultje's avatar
Ronald S. Bultje committed
786 787 788 789 790
  if (cpi->mb.e_mbd.update_mb_segmentation_map) {
    // Is temporal coding of the segment map enabled
    if (pc->temporal_update) {
      unsigned char prediction_flag = vp9_get_pred_flag(xd, PRED_SEG_ID);
      vp9_prob pred_prob = vp9_get_pred_prob(pc, xd, PRED_SEG_ID);
Paul Wilkins's avatar
Paul Wilkins committed
791

Ronald S. Bultje's avatar
Ronald S. Bultje committed
792 793
      // Code the segment id prediction flag for this mb
      vp9_write(bc, prediction_flag, pred_prob);
794

Ronald S. Bultje's avatar
Ronald S. Bultje committed
795 796
      // If the mb segment id wasn't predicted code explicitly
      if (!prediction_flag)
797
        write_mb_segid_except(pc, bc, mi, &cpi->mb.e_mbd, mb_row, mb_col);
Ronald S. Bultje's avatar
Ronald S. Bultje committed
798 799 800 801 802
    } else {
      // Normal unpredicted coding
      write_mb_segid(bc, mi, &cpi->mb.e_mbd);
    }
  }
803

Ronald S. Bultje's avatar
Ronald S. Bultje committed
804 805
  if (!pc->mb_no_coeff_skip) {
    skip_coeff = 0;
Paul Wilkins's avatar
Paul Wilkins committed
806
  } else if (vp9_segfeature_active(xd, segment_id, SEG_LVL_SKIP)) {
Ronald S. Bultje's avatar
Ronald S. Bultje committed
807 808
    skip_coeff = 1;
  } else {
809
    skip_coeff = m->mbmi.mb_skip_coeff;
Ronald S. Bultje's avatar
Ronald S. Bultje committed
810 811 812
    vp9_write(bc, skip_coeff,
              vp9_get_pred_prob(pc, xd, PRED_MBSKIP));
  }
John Koleszar's avatar
John Koleszar committed
813

Ronald S. Bultje's avatar
Ronald S. Bultje committed
814
  // Encode the reference frame.
Paul Wilkins's avatar
Paul Wilkins committed
815
  encode_ref_frame(bc, pc, xd, segment_id, rf);
Paul Wilkins's avatar
Paul Wilkins committed
816

Ronald S. Bultje's avatar
Ronald S. Bultje committed
817
  if (rf == INTRA_FRAME) {
818
#ifdef ENTROPY_STATS
Ronald S. Bultje's avatar
Ronald S. Bultje committed
819
    active_section = 6;
820
#endif
Paul Wilkins's avatar
Paul Wilkins committed
821

Paul Wilkins's avatar
Paul Wilkins committed
822 823 824 825 826
    if (m->mbmi.sb_type)
      write_sb_ymode(bc, mode, pc->fc.sb_ymode_prob);
    else
      write_ymode(bc, mode, pc->fc.ymode_prob);

Ronald S. Bultje's avatar
Ronald S. Bultje committed
827 828 829 830 831 832 833 834 835 836 837 838 839 840 841 842 843 844 845 846 847 848
    if (mode == B_PRED) {
      int j = 0;
      do {
        write_bmode(bc, m->bmi[j].as_mode.first,
                    pc->fc.bmode_prob);
      } while (++j < 16);
    }
    if (mode == I8X8_PRED) {
      write_i8x8_mode(bc, m->bmi[0].as_mode.first,
                      pc->fc.i8x8_mode_prob);
      write_i8x8_mode(bc, m->bmi[2].as_mode.first,
                      pc->fc.i8x8_mode_prob);
      write_i8x8_mode(bc, m->bmi[8].as_mode.first,
                      pc->fc.i8x8_mode_prob);
      write_i8x8_mode(bc, m->bmi[10].as_mode.first,
                      pc->fc.i8x8_mode_prob);
    } else {
      write_uv_mode(bc, mi->uv_mode,
                    pc->fc.uv_mode_prob[mode]);
    }
  } else {
    vp9_prob mv_ref_p[VP9_MVREFS - 1];
849

Ronald S. Bultje's avatar
Ronald S. Bultje committed
850
    vp9_mv_ref_probs(&cpi->common, mv_ref_p, mi->mb_mode_context[rf]);
Yaowu Xu's avatar
Yaowu Xu committed
851

John Koleszar's avatar
John Koleszar committed
852
#ifdef ENTROPY_STATS
Ronald S. Bultje's avatar
Ronald S. Bultje committed
853
    active_section = 3;
John Koleszar's avatar
John Koleszar committed
854 855
#endif

856
    // If segment skip is not enabled code the mode.
Paul Wilkins's avatar
Paul Wilkins committed
857
    if (!vp9_segfeature_active(xd, segment_id, SEG_LVL_SKIP)) {
Ronald S. Bultje's avatar
Ronald S. Bultje committed
858 859
      if (mi->sb_type) {
        write_sb_mv_ref(bc, mode, mv_ref_p);
860
      } else {
Ronald S. Bultje's avatar
Ronald S. Bultje committed
861 862 863 864
        write_mv_ref(bc, mode, mv_ref_p);
      }
      vp9_accum_mv_refs(&cpi->common, mode, mi->mb_mode_context[rf]);
    }
865

Ronald S. Bultje's avatar
Ronald S. Bultje committed
866 867 868 869 870 871 872 873 874 875 876
    if (mode >= NEARESTMV && mode <= SPLITMV) {
      if (cpi->common.mcomp_filter_type == SWITCHABLE) {
        write_token(bc, vp9_switchable_interp_tree,
                    vp9_get_pred_probs(&cpi->common, xd,
                                       PRED_SWITCHABLE_INTERP),
                    vp9_switchable_interp_encodings +
                    vp9_switchable_interp_map[mi->interp_filter]);
      } else {
        assert(mi->interp_filter == cpi->common.mcomp_filter_type);
      }
    }
877

Ronald S. Bultje's avatar
Ronald S. Bultje committed
878 879 880 881 882 883
    // does the feature use compound prediction or not
    // (if not specified at the frame/segment level)
    if (cpi->common.comp_pred_mode == HYBRID_PREDICTION) {
      vp9_write(bc, mi->second_ref_frame > INTRA_FRAME,
                vp9_get_pred_prob(pc, xd, PRED_COMP));
    }
884
#if CONFIG_COMP_INTERINTRA_PRED
Ronald S. Bultje's avatar
Ronald S. Bultje committed
885 886 887 888 889 890 891 892 893 894 895 896 897
    if (cpi->common.use_interintra &&
        mode >= NEARESTMV && mode < SPLITMV &&
        mi->second_ref_frame <= INTRA_FRAME) {
      vp9_write(bc, mi->second_ref_frame == INTRA_FRAME,
                pc->fc.interintra_prob);
      // if (!cpi->dummy_packing)
      //   printf("-- %d (%d)\n", mi->second_ref_frame == INTRA_FRAME,
      //          pc->fc.interintra_prob);
      if (mi->second_ref_frame == INTRA_FRAME) {
        // if (!cpi->dummy_packing)
        //   printf("** %d %d\n", mi->interintra_mode,
        // mi->interintra_uv_mode);
        write_ymode(bc, mi->interintra_mode, pc->fc.ymode_prob);
898
#if SEPARATE_INTERINTRA_UV
Ronald S. Bultje's avatar
Ronald S. Bultje committed
899 900
        write_uv_mode(bc, mi->interintra_uv_mode,
                      pc->fc.uv_mode_prob[mi->interintra_mode]);
901
#endif
Ronald S. Bultje's avatar
Ronald S. Bultje committed
902 903
      }
    }