granicus.if.org Git - libvpx/blob - vp9/encoder/vp9_bitstream.c

   1 /*
   2  *  Copyright (c) 2010 The WebM project authors. All Rights Reserved.
   3  *
   4  *  Use of this source code is governed by a BSD-style license
   5  *  that can be found in the LICENSE file in the root of the source
   6  *  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.
   9  */
  10
  11 #include <assert.h>
  12 #include <stdio.h>
  13 #include <limits.h>
  14
  15 #include "vpx/vpx_encoder.h"
  16 #include "vpx_mem/vpx_mem.h"
  17
  18 #include "vp9/common/vp9_entropymode.h"
  19 #include "vp9/common/vp9_entropymv.h"
  20 #include "vp9/common/vp9_findnearmv.h"
  21 #include "vp9/common/vp9_tile_common.h"
  22 #include "vp9/common/vp9_seg_common.h"
  23 #include "vp9/common/vp9_pred_common.h"
  24 #include "vp9/common/vp9_entropy.h"
  25 #include "vp9/common/vp9_entropymv.h"
  26 #include "vp9/common/vp9_mvref_common.h"
  27 #include "vp9/common/vp9_treecoder.h"
  28 #include "vp9/common/vp9_systemdependent.h"
  29 #include "vp9/common/vp9_pragmas.h"
  30
  31 #include "vp9/encoder/vp9_mcomp.h"
  32 #include "vp9/encoder/vp9_encodemv.h"
  33 #include "vp9/encoder/vp9_bitstream.h"
  34 #include "vp9/encoder/vp9_segmentation.h"
  35 #include "vp9/encoder/vp9_write_bit_buffer.h"
  36
  37
  38 #if defined(SECTIONBITS_OUTPUT)
  39 unsigned __int64 Sectionbits[500];
  40 #endif
  41
  42 #ifdef ENTROPY_STATS
  43 int intra_mode_stats[VP9_INTRA_MODES]
  44                     [VP9_INTRA_MODES]
  45                     [VP9_INTRA_MODES];
  46 vp9_coeff_stats tree_update_hist_4x4[BLOCK_TYPES];
  47 vp9_coeff_stats tree_update_hist_8x8[BLOCK_TYPES];
  48 vp9_coeff_stats tree_update_hist_16x16[BLOCK_TYPES];
  49 vp9_coeff_stats tree_update_hist_32x32[BLOCK_TYPES];
  50
  51 extern unsigned int active_section;
  52 #endif
  53
  54 #define vp9_cost_upd  ((int)(vp9_cost_one(upd) - vp9_cost_zero(upd)) >> 8)
  55 #define vp9_cost_upd256  ((int)(vp9_cost_one(upd) - vp9_cost_zero(upd)))
  56
  57 static int update_bits[255];
  58
  59 static INLINE void write_le16(uint8_t *p, int value) {
  60   p[0] = value;
  61   p[1] = value >> 8;
  62 }
  63
  64 static INLINE void write_le32(uint8_t *p, int value) {
  65   p[0] = value;
  66   p[1] = value >> 8;
  67   p[2] = value >> 16;
  68   p[3] = value >> 24;
  69 }
  70
  71 void vp9_encode_unsigned_max(vp9_writer *br, int data, int max) {
  72   assert(data <= max);
  73   while (max) {
  74     vp9_write_bit(br, data & 1);
  75     data >>= 1;
  76     max >>= 1;
  77   }
  78 }
  79
  80 int recenter_nonneg(int v, int m) {
  81   if (v > (m << 1))
  82     return v;
  83   else if (v >= m)
  84     return ((v - m) << 1);
  85   else
  86     return ((m - v) << 1) - 1;
  87 }
  88
  89 static int get_unsigned_bits(unsigned num_values) {
  90   int cat = 0;
  91   if ((num_values--) <= 1) return 0;
  92   while (num_values > 0) {
  93     cat++;
  94     num_values >>= 1;
  95   }
  96   return cat;
  97 }
  98
  99 void encode_uniform(vp9_writer *w, int v, int n) {
 100   int l = get_unsigned_bits(n);
 101   int m;
 102   if (l == 0)
 103     return;
 104   m = (1 << l) - n;
 105   if (v < m) {
 106     vp9_write_literal(w, v, l - 1);
 107   } else {
 108     vp9_write_literal(w, m + ((v - m) >> 1), l - 1);
 109     vp9_write_literal(w, (v - m) & 1, 1);
 110   }
 111 }
 112
 113 int count_uniform(int v, int n) {
 114   int l = get_unsigned_bits(n);
 115   int m;
 116   if (l == 0) return 0;
 117   m = (1 << l) - n;
 118   if (v < m)
 119     return l - 1;
 120   else
 121     return l;
 122 }
 123
 124 void encode_term_subexp(vp9_writer *w, int word, int k, int num_syms) {
 125   int i = 0;
 126   int mk = 0;
 127   while (1) {
 128     int b = (i ? k + i - 1 : k);
 129     int a = (1 << b);
 130     if (num_syms <= mk + 3 * a) {
 131       encode_uniform(w, word - mk, num_syms - mk);
 132       break;
 133     } else {
 134       int t = (word >= mk + a);
 135       vp9_write_literal(w, t, 1);
 136       if (t) {
 137         i = i + 1;
 138         mk += a;
 139       } else {
 140         vp9_write_literal(w, word - mk, b);
 141         break;
 142       }
 143     }
 144   }
 145 }
 146
 147 int count_term_subexp(int word, int k, int num_syms) {
 148   int count = 0;
 149   int i = 0;
 150   int mk = 0;
 151   while (1) {
 152     int b = (i ? k + i - 1 : k);
 153     int a = (1 << b);
 154     if (num_syms <= mk + 3 * a) {
 155       count += count_uniform(word - mk, num_syms - mk);
 156       break;
 157     } else {
 158       int t = (word >= mk + a);
 159       count++;
 160       if (t) {
 161         i = i + 1;
 162         mk += a;
 163       } else {
 164         count += b;
 165         break;
 166       }
 167     }
 168   }
 169   return count;
 170 }
 171
 172 static void compute_update_table() {
 173   int i;
 174   for (i = 0; i < 255; i++)
 175     update_bits[i] = count_term_subexp(i, SUBEXP_PARAM, 255);
 176 }
 177
 178 static int split_index(int i, int n, int modulus) {
 179   int max1 = (n - 1 - modulus / 2) / modulus + 1;
 180   if (i % modulus == modulus / 2) i = i / modulus;
 181   else i = max1 + i - (i + modulus - modulus / 2) / modulus;
 182   return i;
 183 }
 184
 185 static int remap_prob(int v, int m) {
 186   const int n = 256;
 187   const int modulus = MODULUS_PARAM;
 188   int i;
 189   if ((m << 1) <= n)
 190     i = recenter_nonneg(v, m) - 1;
 191   else
 192     i = recenter_nonneg(n - 1 - v, n - 1 - m) - 1;
 193
 194   i = split_index(i, n - 1, modulus);
 195   return i;
 196 }
 197
 198 static void write_prob_diff_update(vp9_writer *w,
 199                                    vp9_prob newp, vp9_prob oldp) {
 200   int delp = remap_prob(newp, oldp);
 201   encode_term_subexp(w, delp, SUBEXP_PARAM, 255);
 202 }
 203
 204 static int prob_diff_update_cost(vp9_prob newp, vp9_prob oldp) {
 205   int delp = remap_prob(newp, oldp);
 206   return update_bits[delp] * 256;
 207 }
 208
 209 static void update_mode(
 210   vp9_writer *w,
 211   int n,
 212   const struct vp9_token tok[/* n */],
 213   vp9_tree tree,
 214   vp9_prob Pnew               [/* n-1 */],
 215   vp9_prob Pcur               [/* n-1 */],
 216   unsigned int bct            [/* n-1 */] [2],
 217   const unsigned int num_events[/* n */]
 218 ) {
 219   unsigned int new_b = 0, old_b = 0;
 220   int i = 0;
 221
 222   vp9_tree_probs_from_distribution(tree, Pnew, bct, num_events, 0);
 223   n--;
 224
 225   do {
 226     new_b += cost_branch(bct[i], Pnew[i]);
 227     old_b += cost_branch(bct[i], Pcur[i]);
 228   } while (++i < n);
 229
 230   if (new_b + (n << 8) < old_b) {
 231     int i = 0;
 232
 233     vp9_write_bit(w, 1);
 234
 235     do {
 236       const vp9_prob p = Pnew[i];
 237
 238       vp9_write_literal(w, Pcur[i] = p ? p : 1, 8);
 239     } while (++i < n);
 240   } else
 241     vp9_write_bit(w, 0);
 242 }
 243
 244 static void update_mbintra_mode_probs(VP9_COMP* const cpi,
 245                                       vp9_writer* const bc) {
 246   VP9_COMMON *const cm = &cpi->common;
 247
 248   vp9_prob pnew[VP9_INTRA_MODES - 1];
 249   unsigned int bct[VP9_INTRA_MODES - 1][2];
 250
 251   update_mode(bc, VP9_INTRA_MODES, vp9_intra_mode_encodings,
 252               vp9_intra_mode_tree, pnew,
 253               cm->fc.y_mode_prob, bct, (unsigned int *)cpi->y_mode_count);
 254 }
 255
 256 void vp9_update_skip_probs(VP9_COMP *cpi) {
 257   VP9_COMMON *const pc = &cpi->common;
 258   int k;
 259
 260   for (k = 0; k < MBSKIP_CONTEXTS; ++k)
 261     pc->mbskip_pred_probs[k] = get_binary_prob(cpi->skip_false_count[k],
 262                                                cpi->skip_true_count[k]);
 263 }
 264
 265 static void update_switchable_interp_probs(VP9_COMP *cpi,
 266                                            vp9_writer* const bc) {
 267   VP9_COMMON *const pc = &cpi->common;
 268   unsigned int branch_ct[32][2];
 269   int i, j;
 270   for (j = 0; j <= VP9_SWITCHABLE_FILTERS; ++j) {
 271     vp9_tree_probs_from_distribution(
 272         vp9_switchable_interp_tree,
 273         pc->fc.switchable_interp_prob[j], branch_ct,
 274         cpi->switchable_interp_count[j], 0);
 275     for (i = 0; i < VP9_SWITCHABLE_FILTERS - 1; ++i) {
 276       if (pc->fc.switchable_interp_prob[j][i] < 1)
 277         pc->fc.switchable_interp_prob[j][i] = 1;
 278       vp9_write_prob(bc, pc->fc.switchable_interp_prob[j][i]);
 279     }
 280   }
 281 }
 282
 283 // This function updates the reference frame prediction stats
 284 static void update_refpred_stats(VP9_COMP *cpi) {
 285   VP9_COMMON *const cm = &cpi->common;
 286   int i;
 287   vp9_prob new_pred_probs[PREDICTION_PROBS];
 288   int old_cost, new_cost;
 289
 290   // Set the prediction probability structures to defaults
 291   if (cm->frame_type != KEY_FRAME) {
 292     // From the prediction counts set the probabilities for each context
 293     for (i = 0; i < PREDICTION_PROBS; i++) {
 294       const int c0 = cpi->ref_pred_count[i][0];
 295       const int c1 = cpi->ref_pred_count[i][1];
 296
 297       new_pred_probs[i] = get_binary_prob(c0, c1);
 298
 299       // Decide whether or not to update the reference frame probs.
 300       // Returned costs are in 1/256 bit units.
 301       old_cost = c0 * vp9_cost_zero(cm->ref_pred_probs[i]) +
 302                  c1 * vp9_cost_one(cm->ref_pred_probs[i]);
 303
 304       new_cost = c0 * vp9_cost_zero(new_pred_probs[i]) +
 305                  c1 * vp9_cost_one(new_pred_probs[i]);
 306
 307       // Cost saving must be >= 8 bits (2048 in these units)
 308       if ((old_cost - new_cost) >= 2048) {
 309         cpi->ref_pred_probs_update[i] = 1;
 310         cm->ref_pred_probs[i] = new_pred_probs[i];
 311       } else
 312         cpi->ref_pred_probs_update[i] = 0;
 313     }
 314   }
 315 }
 316
 317 // This function is called to update the mode probability context used to encode
 318 // inter modes. It assumes the branch counts table has already been populated
 319 // prior to the actual packing of the bitstream (in rd stage or dummy pack)
 320 //
 321 // The branch counts table is re-populated during the actual pack stage and in
 322 // the decoder to facilitate backwards update of the context.
 323 static void update_inter_mode_probs(VP9_COMMON *cm,
 324     int mode_context[INTER_MODE_CONTEXTS][VP9_MVREFS - 1]) {
 325   int i, j;
 326   unsigned int (*mv_ref_ct)[VP9_MVREFS - 1][2] = cm->fc.mv_ref_ct;
 327
 328   vpx_memcpy(mode_context, cm->fc.vp9_mode_contexts,
 329              sizeof(cm->fc.vp9_mode_contexts));
 330
 331   for (i = 0; i < INTER_MODE_CONTEXTS; i++) {
 332     for (j = 0; j < VP9_MVREFS - 1; j++) {
 333       int new_prob, old_cost, new_cost;
 334
 335       // Work out cost of coding branches with the old and optimal probability
 336       old_cost = cost_branch256(mv_ref_ct[i][j], mode_context[i][j]);
 337       new_prob = get_binary_prob(mv_ref_ct[i][j][0], mv_ref_ct[i][j][1]);
 338       new_cost = cost_branch256(mv_ref_ct[i][j], new_prob);
 339
 340       // If cost saving is >= 14 bits then update the mode probability.
 341       // This is the approximate net cost of updating one probability given
 342       // that the no update case ismuch more common than the update case.
 343       if (new_cost <= (old_cost - (14 << 8))) {
 344         mode_context[i][j] = new_prob;
 345       }
 346     }
 347   }
 348 }
 349
 350 static void write_intra_mode(vp9_writer *bc, int m, const vp9_prob *p) {
 351   write_token(bc, vp9_intra_mode_tree, p, vp9_intra_mode_encodings + m);
 352 }
 353
 354 static int prob_update_savings(const unsigned int *ct,
 355                                const vp9_prob oldp, const vp9_prob newp,
 356                                const vp9_prob upd) {
 357   const int old_b = cost_branch256(ct, oldp);
 358   const int new_b = cost_branch256(ct, newp);
 359   const int update_b = 2048 + vp9_cost_upd256;
 360   return old_b - new_b - update_b;
 361 }
 362
 363 static int prob_diff_update_savings_search(const unsigned int *ct,
 364                                            const vp9_prob oldp, vp9_prob *bestp,
 365                                            const vp9_prob upd) {
 366   const int old_b = cost_branch256(ct, oldp);
 367   int new_b, update_b, savings, bestsavings, step;
 368   vp9_prob newp, bestnewp;
 369
 370   bestsavings = 0;
 371   bestnewp = oldp;
 372
 373   step = (*bestp > oldp ? -1 : 1);
 374   for (newp = *bestp; newp != oldp; newp += step) {
 375     new_b = cost_branch256(ct, newp);
 376     update_b = prob_diff_update_cost(newp, oldp) + vp9_cost_upd256;
 377     savings = old_b - new_b - update_b;
 378     if (savings > bestsavings) {
 379       bestsavings = savings;
 380       bestnewp = newp;
 381     }
 382   }
 383   *bestp = bestnewp;
 384   return bestsavings;
 385 }
 386
 387 static int prob_diff_update_savings_search_model(const unsigned int *ct,
 388                                                  const vp9_prob *oldp,
 389                                                  vp9_prob *bestp,
 390                                                  const vp9_prob upd,
 391                                                  int b, int r) {
 392   int i, old_b, new_b, update_b, savings, bestsavings, step;
 393   int newp;
 394   vp9_prob bestnewp, newplist[ENTROPY_NODES], oldplist[ENTROPY_NODES];
 395   vp9_model_to_full_probs(oldp, oldplist);
 396   vpx_memcpy(newplist, oldp, sizeof(vp9_prob) * UNCONSTRAINED_NODES);
 397   for (i = UNCONSTRAINED_NODES, old_b = 0; i < ENTROPY_NODES; ++i)
 398     old_b += cost_branch256(ct + 2 * i, oldplist[i]);
 399   old_b += cost_branch256(ct + 2 * PIVOT_NODE, oldplist[PIVOT_NODE]);
 400
 401   bestsavings = 0;
 402   bestnewp = oldp[PIVOT_NODE];
 403
 404   step = (*bestp > oldp[PIVOT_NODE] ? -1 : 1);
 405   newp = *bestp;
 406   for (; newp != oldp[PIVOT_NODE]; newp += step) {
 407     if (newp < 1 || newp > 255) continue;
 408     newplist[PIVOT_NODE] = newp;
 409     vp9_model_to_full_probs(newplist, newplist);
 410     for (i = UNCONSTRAINED_NODES, new_b = 0; i < ENTROPY_NODES; ++i)
 411       new_b += cost_branch256(ct + 2 * i, newplist[i]);
 412     new_b += cost_branch256(ct + 2 * PIVOT_NODE, newplist[PIVOT_NODE]);
 413     update_b = prob_diff_update_cost(newp, oldp[PIVOT_NODE]) +
 414         vp9_cost_upd256;
 415     savings = old_b - new_b - update_b;
 416     if (savings > bestsavings) {
 417       bestsavings = savings;
 418       bestnewp = newp;
 419     }
 420   }
 421   *bestp = bestnewp;
 422   return bestsavings;
 423 }
 424
 425 static void vp9_cond_prob_update(vp9_writer *bc, vp9_prob *oldp, vp9_prob upd,
 426                                  unsigned int *ct) {
 427   vp9_prob newp;
 428   int savings;
 429   newp = get_binary_prob(ct[0], ct[1]);
 430   savings = prob_update_savings(ct, *oldp, newp, upd);
 431   if (savings > 0) {
 432     vp9_write(bc, 1, upd);
 433     vp9_write_prob(bc, newp);
 434     *oldp = newp;
 435   } else {
 436     vp9_write(bc, 0, upd);
 437   }
 438 }
 439
 440 static void pack_mb_tokens(vp9_writer* const bc,
 441                            TOKENEXTRA **tp,
 442                            const TOKENEXTRA *const stop) {
 443   TOKENEXTRA *p = *tp;
 444
 445   while (p < stop) {
 446     const int t = p->token;
 447     const struct vp9_token *const a = vp9_coef_encodings + t;
 448     const vp9_extra_bit *const b = vp9_extra_bits + t;
 449     int i = 0;
 450     const vp9_prob *pp;
 451     int v = a->value;
 452     int n = a->len;
 453     vp9_prob probs[ENTROPY_NODES];
 454
 455     if (t == EOSB_TOKEN) {
 456       ++p;
 457       break;
 458     }
 459     if (t >= TWO_TOKEN) {
 460       vp9_model_to_full_probs(p->context_tree, probs);
 461       pp = probs;
 462     } else {
 463       pp = p->context_tree;
 464     }
 465     assert(pp != 0);
 466
 467     /* skip one or two nodes */
 468 #if !CONFIG_BALANCED_COEFTREE
 469     if (p->skip_eob_node) {
 470       n -= p->skip_eob_node;
 471       i = 2 * p->skip_eob_node;
 472     }
 473 #endif
 474
 475     do {
 476       const int bb = (v >> --n) & 1;
 477 #if CONFIG_BALANCED_COEFTREE
 478       if (i == 2 && p->skip_eob_node) {
 479         i += 2;
 480         assert(bb == 1);
 481         continue;
 482       }
 483 #endif
 484       vp9_write(bc, bb, pp[i >> 1]);
 485       i = vp9_coef_tree[i + bb];
 486     } while (n);
 487
 488     if (b->base_val) {
 489       const int e = p->extra, l = b->len;
 490
 491       if (l) {
 492         const unsigned char *pb = b->prob;
 493         int v = e >> 1;
 494         int n = l;              /* number of bits in v, assumed nonzero */
 495         int i = 0;
 496
 497         do {
 498           const int bb = (v >> --n) & 1;
 499           vp9_write(bc, bb, pb[i >> 1]);
 500           i = b->tree[i + bb];
 501         } while (n);
 502       }
 503
 504       vp9_write_bit(bc, e & 1);
 505     }
 506     ++p;
 507   }
 508
 509   *tp = p;
 510 }
 511
 512 static void write_sb_mv_ref(vp9_writer *bc, MB_PREDICTION_MODE m,
 513                             const vp9_prob *p) {
 514 #if CONFIG_DEBUG
 515   assert(NEARESTMV <= m && m <= NEWMV);
 516 #endif
 517   write_token(bc, vp9_sb_mv_ref_tree, p,
 518               vp9_sb_mv_ref_encoding_array - NEARESTMV + m);
 519 }
 520
 521 // This function writes the current macro block's segnment id to the bitstream
 522 // It should only be called if a segment map update is indicated.
 523 static void write_mb_segid(vp9_writer *bc,
 524                            const MB_MODE_INFO *mi, const MACROBLOCKD *xd) {
 525   if (xd->segmentation_enabled && xd->update_mb_segmentation_map)
 526     treed_write(bc, vp9_segment_tree, xd->mb_segment_tree_probs,
 527                 mi->segment_id, 3);
 528 }
 529
 530 // This function encodes the reference frame
 531 static void encode_ref_frame(vp9_writer *const bc,
 532                              VP9_COMMON *const cm,
 533                              MACROBLOCKD *xd,
 534                              int segment_id,
 535                              MV_REFERENCE_FRAME rf) {
 536   int seg_ref_active;
 537   int seg_ref_count = 0;
 538   seg_ref_active = vp9_segfeature_active(xd,
 539                                          segment_id,
 540                                          SEG_LVL_REF_FRAME);
 541
 542   if (seg_ref_active) {
 543     seg_ref_count = vp9_check_segref(xd, segment_id, INTRA_FRAME) +
 544                     vp9_check_segref(xd, segment_id, LAST_FRAME) +
 545                     vp9_check_segref(xd, segment_id, GOLDEN_FRAME) +
 546                     vp9_check_segref(xd, segment_id, ALTREF_FRAME);
 547   }
 548
 549   // If segment level coding of this signal is disabled...
 550   // or the segment allows multiple reference frame options
 551   if (!seg_ref_active || (seg_ref_count > 1)) {
 552     // Values used in prediction model coding
 553     unsigned char prediction_flag;
 554     vp9_prob pred_prob;
 555     MV_REFERENCE_FRAME pred_rf;
 556
 557     // Get the context probability the prediction flag
 558     pred_prob = vp9_get_pred_prob(cm, xd, PRED_REF);
 559
 560     // Get the predicted value.
 561     pred_rf = vp9_get_pred_ref(cm, xd);
 562
 563     // Did the chosen reference frame match its predicted value.
 564     prediction_flag =
 565       (xd->mode_info_context->mbmi.ref_frame == pred_rf);
 566
 567     vp9_set_pred_flag(xd, PRED_REF, prediction_flag);
 568     vp9_write(bc, prediction_flag, pred_prob);
 569
 570     // If not predicted correctly then code value explicitly
 571     if (!prediction_flag) {
 572       vp9_prob mod_refprobs[PREDICTION_PROBS];
 573
 574       vpx_memcpy(mod_refprobs,
 575                  cm->mod_refprobs[pred_rf], sizeof(mod_refprobs));
 576
 577       // If segment coding enabled blank out options that cant occur by
 578       // setting the branch probability to 0.
 579       if (seg_ref_active) {
 580         mod_refprobs[INTRA_FRAME] *=
 581           vp9_check_segref(xd, segment_id, INTRA_FRAME);
 582         mod_refprobs[LAST_FRAME] *=
 583           vp9_check_segref(xd, segment_id, LAST_FRAME);
 584         mod_refprobs[GOLDEN_FRAME] *=
 585           (vp9_check_segref(xd, segment_id, GOLDEN_FRAME) *
 586            vp9_check_segref(xd, segment_id, ALTREF_FRAME));
 587       }
 588
 589       if (mod_refprobs[0]) {
 590         vp9_write(bc, (rf != INTRA_FRAME), mod_refprobs[0]);
 591       }
 592
 593       // Inter coded
 594       if (rf != INTRA_FRAME) {
 595         if (mod_refprobs[1]) {
 596           vp9_write(bc, (rf != LAST_FRAME), mod_refprobs[1]);
 597         }
 598
 599         if (rf != LAST_FRAME) {
 600           if (mod_refprobs[2]) {
 601             vp9_write(bc, (rf != GOLDEN_FRAME), mod_refprobs[2]);
 602           }
 603         }
 604       }
 605     }
 606   }
 607
 608   // if using the prediction mdoel we have nothing further to do because
 609   // the reference frame is fully coded by the segment
 610 }
 611
 612 // Update the probabilities used to encode reference frame data
 613 static void update_ref_probs(VP9_COMP *const cpi) {
 614   VP9_COMMON *const cm = &cpi->common;
 615
 616   const int *const rfct = cpi->count_mb_ref_frame_usage;
 617   const int rf_intra = rfct[INTRA_FRAME];
 618   const int rf_inter = rfct[LAST_FRAME] +
 619                        rfct[GOLDEN_FRAME] + rfct[ALTREF_FRAME];
 620
 621   cm->prob_intra_coded = get_binary_prob(rf_intra, rf_inter);
 622   cm->prob_last_coded = get_prob(rfct[LAST_FRAME], rf_inter);
 623   cm->prob_gf_coded = get_binary_prob(rfct[GOLDEN_FRAME], rfct[ALTREF_FRAME]);
 624
 625   // Compute a modified set of probabilities to use when prediction of the
 626   // reference frame fails
 627   vp9_compute_mod_refprobs(cm);
 628 }
 629
 630 static void pack_inter_mode_mvs(VP9_COMP *cpi, MODE_INFO *m,
 631                                 vp9_writer *bc, int mi_row, int mi_col) {
 632   VP9_COMMON *const pc = &cpi->common;
 633   const nmv_context *nmvc = &pc->fc.nmvc;
 634   MACROBLOCK *const x = &cpi->mb;
 635   MACROBLOCKD *const xd = &x->e_mbd;
 636   MB_MODE_INFO *const mi = &m->mbmi;
 637   const MV_REFERENCE_FRAME rf = mi->ref_frame;
 638   const MB_PREDICTION_MODE mode = mi->mode;
 639   const int segment_id = mi->segment_id;
 640   int skip_coeff;
 641
 642   xd->prev_mode_info_context = pc->prev_mi + (m - pc->mi);
 643   x->partition_info = x->pi + (m - pc->mi);
 644
 645 #ifdef ENTROPY_STATS
 646   active_section = 9;
 647 #endif
 648
 649   if (cpi->mb.e_mbd.update_mb_segmentation_map) {
 650     // Is temporal coding of the segment map enabled
 651     if (pc->temporal_update) {
 652       unsigned char prediction_flag = vp9_get_pred_flag(xd, PRED_SEG_ID);
 653       vp9_prob pred_prob = vp9_get_pred_prob(pc, xd, PRED_SEG_ID);
 654
 655       // Code the segment id prediction flag for this mb
 656       vp9_write(bc, prediction_flag, pred_prob);
 657
 658       // If the mb segment id wasn't predicted code explicitly
 659       if (!prediction_flag)
 660         write_mb_segid(bc, mi, &cpi->mb.e_mbd);
 661     } else {
 662       // Normal unpredicted coding
 663       write_mb_segid(bc, mi, &cpi->mb.e_mbd);
 664     }
 665   }
 666
 667   if (vp9_segfeature_active(xd, segment_id, SEG_LVL_SKIP)) {
 668     skip_coeff = 1;
 669   } else {
 670     skip_coeff = m->mbmi.mb_skip_coeff;
 671     vp9_write(bc, skip_coeff,
 672               vp9_get_pred_prob(pc, xd, PRED_MBSKIP));
 673   }
 674
 675   // Encode the reference frame.
 676   encode_ref_frame(bc, pc, xd, segment_id, rf);
 677
 678   if (mi->sb_type >= BLOCK_SIZE_SB8X8 && pc->txfm_mode == TX_MODE_SELECT &&
 679       !(rf != INTRA_FRAME &&
 680         (skip_coeff || vp9_segfeature_active(xd, segment_id, SEG_LVL_SKIP)))) {
 681     TX_SIZE sz = mi->txfm_size;
 682     // FIXME(rbultje) code ternary symbol once all experiments are merged
 683     vp9_write(bc, sz != TX_4X4, pc->prob_tx[0]);
 684     if (mi->sb_type >= BLOCK_SIZE_MB16X16 && sz != TX_4X4) {
 685       vp9_write(bc, sz != TX_8X8, pc->prob_tx[1]);
 686       if (mi->sb_type >= BLOCK_SIZE_SB32X32 && sz != TX_8X8)
 687         vp9_write(bc, sz != TX_16X16, pc->prob_tx[2]);
 688     }
 689   }
 690
 691   if (rf == INTRA_FRAME) {
 692 #ifdef ENTROPY_STATS
 693     active_section = 6;
 694 #endif
 695
 696     if (m->mbmi.sb_type >= BLOCK_SIZE_SB8X8) {
 697       write_intra_mode(bc, mode, pc->fc.y_mode_prob);
 698     } else {
 699       int idx, idy;
 700       int bw = 1 << b_width_log2(mi->sb_type);
 701       int bh = 1 << b_height_log2(mi->sb_type);
 702       for (idy = 0; idy < 2; idy += bh)
 703         for (idx = 0; idx < 2; idx += bw)
 704           write_intra_mode(bc, m->bmi[idy * 2 + idx].as_mode.first,
 705                            pc->fc.y_mode_prob);
 706     }
 707     write_intra_mode(bc, mi->uv_mode,
 708                      pc->fc.uv_mode_prob[mode]);
 709   } else {
 710     vp9_prob mv_ref_p[VP9_MVREFS - 1];
 711
 712     vp9_mv_ref_probs(&cpi->common, mv_ref_p, mi->mb_mode_context[rf]);
 713
 714 #ifdef ENTROPY_STATS
 715     active_section = 3;
 716 #endif
 717
 718     // If segment skip is not enabled code the mode.
 719     if (!vp9_segfeature_active(xd, segment_id, SEG_LVL_SKIP)) {
 720       if (mi->sb_type >= BLOCK_SIZE_SB8X8) {
 721         write_sb_mv_ref(bc, mode, mv_ref_p);
 722         vp9_accum_mv_refs(&cpi->common, mode, mi->mb_mode_context[rf]);
 723       }
 724     }
 725
 726     if (cpi->common.mcomp_filter_type == SWITCHABLE) {
 727       write_token(bc, vp9_switchable_interp_tree,
 728                   vp9_get_pred_probs(&cpi->common, xd,
 729                                      PRED_SWITCHABLE_INTERP),
 730                   vp9_switchable_interp_encodings +
 731                   vp9_switchable_interp_map[mi->interp_filter]);
 732     } else {
 733       assert(mi->interp_filter == cpi->common.mcomp_filter_type);
 734     }
 735
 736     // does the feature use compound prediction or not
 737     // (if not specified at the frame/segment level)
 738     if (cpi->common.comp_pred_mode == HYBRID_PREDICTION) {
 739       vp9_write(bc, mi->second_ref_frame > INTRA_FRAME,
 740                 vp9_get_pred_prob(pc, xd, PRED_COMP));
 741     }
 742
 743     if (xd->mode_info_context->mbmi.sb_type < BLOCK_SIZE_SB8X8) {
 744       int j;
 745       MB_PREDICTION_MODE blockmode;
 746       int_mv blockmv;
 747       int bwl = b_width_log2(mi->sb_type), bw = 1 << bwl;
 748       int bhl = b_height_log2(mi->sb_type), bh = 1 << bhl;
 749       int idx, idy;
 750       for (idy = 0; idy < 2; idy += bh) {
 751         for (idx = 0; idx < 2; idx += bw) {
 752           j = idy * 2 + idx;
 753           blockmode = cpi->mb.partition_info->bmi[j].mode;
 754           blockmv = cpi->mb.partition_info->bmi[j].mv;
 755           write_sb_mv_ref(bc, blockmode, mv_ref_p);
 756           vp9_accum_mv_refs(&cpi->common, blockmode, mi->mb_mode_context[rf]);
 757           if (blockmode == NEWMV) {
 758 #ifdef ENTROPY_STATS
 759             active_section = 11;
 760 #endif
 761             vp9_encode_mv(bc, &blockmv.as_mv, &mi->best_mv.as_mv,
 762                           nmvc, xd->allow_high_precision_mv);
 763
 764             if (mi->second_ref_frame > 0)
 765               vp9_encode_mv(bc,
 766                             &cpi->mb.partition_info->bmi[j].second_mv.as_mv,
 767                             &mi->best_second_mv.as_mv,
 768                             nmvc, xd->allow_high_precision_mv);
 769           }
 770         }
 771       }
 772
 773 #ifdef MODE_STATS
 774       ++count_mb_seg[mi->partitioning];
 775 #endif
 776     } else if (mode == NEWMV) {
 777 #ifdef ENTROPY_STATS
 778       active_section = 5;
 779 #endif
 780       vp9_encode_mv(bc,
 781                     &mi->mv[0].as_mv, &mi->best_mv.as_mv,
 782                     nmvc, xd->allow_high_precision_mv);
 783
 784       if (mi->second_ref_frame > 0)
 785         vp9_encode_mv(bc,
 786                       &mi->mv[1].as_mv, &mi->best_second_mv.as_mv,
 787                       nmvc, xd->allow_high_precision_mv);
 788     }
 789   }
 790 }
 791
 792 static void write_mb_modes_kf(const VP9_COMP *cpi,
 793                               MODE_INFO *m,
 794                               vp9_writer *bc, int mi_row, int mi_col) {
 795   const VP9_COMMON *const c = &cpi->common;
 796   const MACROBLOCKD *const xd = &cpi->mb.e_mbd;
 797   const int ym = m->mbmi.mode;
 798   const int mis = c->mode_info_stride;
 799   const int segment_id = m->mbmi.segment_id;
 800   int skip_coeff;
 801
 802   if (xd->update_mb_segmentation_map)
 803     write_mb_segid(bc, &m->mbmi, xd);
 804
 805   if (vp9_segfeature_active(xd, segment_id, SEG_LVL_SKIP)) {
 806     skip_coeff = 1;
 807   } else {
 808     skip_coeff = m->mbmi.mb_skip_coeff;
 809     vp9_write(bc, skip_coeff, vp9_get_pred_prob(c, xd, PRED_MBSKIP));
 810   }
 811
 812   if (m->mbmi.sb_type >= BLOCK_SIZE_SB8X8 && c->txfm_mode == TX_MODE_SELECT) {
 813     TX_SIZE sz = m->mbmi.txfm_size;
 814     // FIXME(rbultje) code ternary symbol once all experiments are merged
 815     vp9_write(bc, sz != TX_4X4, c->prob_tx[0]);
 816     if (m->mbmi.sb_type >= BLOCK_SIZE_MB16X16 && sz != TX_4X4) {
 817       vp9_write(bc, sz != TX_8X8, c->prob_tx[1]);
 818       if (m->mbmi.sb_type >= BLOCK_SIZE_SB32X32 && sz != TX_8X8)
 819         vp9_write(bc, sz != TX_16X16, c->prob_tx[2]);
 820     }
 821   }
 822
 823   if (m->mbmi.sb_type >= BLOCK_SIZE_SB8X8) {
 824     const MB_PREDICTION_MODE A = above_block_mode(m, 0, mis);
 825     const MB_PREDICTION_MODE L = xd->left_available ?
 826                                  left_block_mode(m, 0) : DC_PRED;
 827     write_intra_mode(bc, ym, c->kf_y_mode_prob[A][L]);
 828   } else {
 829     int idx, idy;
 830     int bw = 1 << b_width_log2(m->mbmi.sb_type);
 831     int bh = 1 << b_height_log2(m->mbmi.sb_type);
 832     for (idy = 0; idy < 2; idy += bh) {
 833       for (idx = 0; idx < 2; idx += bw) {
 834         int i = idy * 2 + idx;
 835         const MB_PREDICTION_MODE A = above_block_mode(m, i, mis);
 836         const MB_PREDICTION_MODE L = (xd->left_available || idx) ?
 837                                      left_block_mode(m, i) : DC_PRED;
 838         const int bm = m->bmi[i].as_mode.first;
 839 #ifdef ENTROPY_STATS
 840         ++intra_mode_stats[A][L][bm];
 841 #endif
 842         write_intra_mode(bc, bm, c->kf_y_mode_prob[A][L]);
 843       }
 844     }
 845   }
 846
 847   write_intra_mode(bc, m->mbmi.uv_mode, c->kf_uv_mode_prob[ym]);
 848 }
 849
 850 static void write_modes_b(VP9_COMP *cpi, MODE_INFO *m, vp9_writer *bc,
 851                           TOKENEXTRA **tok, TOKENEXTRA *tok_end,
 852                           int mi_row, int mi_col) {
 853   VP9_COMMON *const cm = &cpi->common;
 854   MACROBLOCKD *const xd = &cpi->mb.e_mbd;
 855
 856   if (m->mbmi.sb_type < BLOCK_SIZE_SB8X8)
 857     if (xd->ab_index > 0)
 858       return;
 859   xd->mode_info_context = m;
 860   set_mi_row_col(&cpi->common, xd, mi_row,
 861                  1 << mi_height_log2(m->mbmi.sb_type),
 862                  mi_col, 1 << mi_width_log2(m->mbmi.sb_type));
 863   if (cm->frame_type == KEY_FRAME) {
 864     write_mb_modes_kf(cpi, m, bc, mi_row, mi_col);
 865 #ifdef ENTROPY_STATS
 866     active_section = 8;
 867 #endif
 868   } else {
 869     pack_inter_mode_mvs(cpi, m, bc, mi_row, mi_col);
 870 #ifdef ENTROPY_STATS
 871     active_section = 1;
 872 #endif
 873   }
 874
 875   assert(*tok < tok_end);
 876   pack_mb_tokens(bc, tok, tok_end);
 877 }
 878
 879 static void write_modes_sb(VP9_COMP *cpi, MODE_INFO *m, vp9_writer *bc,
 880                            TOKENEXTRA **tok, TOKENEXTRA *tok_end,
 881                            int mi_row, int mi_col,
 882                            BLOCK_SIZE_TYPE bsize) {
 883   VP9_COMMON *const cm = &cpi->common;
 884   MACROBLOCKD *xd = &cpi->mb.e_mbd;
 885   const int mis = cm->mode_info_stride;
 886   int bwl, bhl;
 887   int bsl = b_width_log2(bsize);
 888   int bs = (1 << bsl) / 4;  // mode_info step for subsize
 889   int n;
 890   PARTITION_TYPE partition;
 891   BLOCK_SIZE_TYPE subsize;
 892
 893   if (mi_row >= cm->mi_rows || mi_col >= cm->mi_cols)
 894     return;
 895
 896   bwl = b_width_log2(m->mbmi.sb_type);
 897   bhl = b_height_log2(m->mbmi.sb_type);
 898
 899   // parse the partition type
 900   if ((bwl == bsl) && (bhl == bsl))
 901     partition = PARTITION_NONE;
 902   else if ((bwl == bsl) && (bhl < bsl))
 903     partition = PARTITION_HORZ;
 904   else if ((bwl < bsl) && (bhl == bsl))
 905     partition = PARTITION_VERT;
 906   else if ((bwl < bsl) && (bhl < bsl))
 907     partition = PARTITION_SPLIT;
 908   else
 909     assert(0);
 910
 911   if (bsize < BLOCK_SIZE_SB8X8)
 912     if (xd->ab_index > 0)
 913       return;
 914
 915   if (bsize >= BLOCK_SIZE_SB8X8) {
 916     int pl;
 917     xd->left_seg_context = cm->left_seg_context + (mi_row & MI_MASK);
 918     xd->above_seg_context = cm->above_seg_context + mi_col;
 919     pl = partition_plane_context(xd, bsize);
 920     // encode the partition information
 921     write_token(bc, vp9_partition_tree, cm->fc.partition_prob[pl],
 922                 vp9_partition_encodings + partition);
 923   }
 924
 925   subsize = get_subsize(bsize, partition);
 926   *(get_sb_index(xd, subsize)) = 0;
 927
 928   switch (partition) {
 929     case PARTITION_NONE:
 930       write_modes_b(cpi, m, bc, tok, tok_end, mi_row, mi_col);
 931       break;
 932     case PARTITION_HORZ:
 933       write_modes_b(cpi, m, bc, tok, tok_end, mi_row, mi_col);
 934       *(get_sb_index(xd, subsize)) = 1;
 935       if ((mi_row + bs) < cm->mi_rows)
 936         write_modes_b(cpi, m + bs * mis, bc, tok, tok_end, mi_row + bs, mi_col);
 937       break;
 938     case PARTITION_VERT:
 939       write_modes_b(cpi, m, bc, tok, tok_end, mi_row, mi_col);
 940       *(get_sb_index(xd, subsize)) = 1;
 941       if ((mi_col + bs) < cm->mi_cols)
 942         write_modes_b(cpi, m + bs, bc, tok, tok_end, mi_row, mi_col + bs);
 943       break;
 944     case PARTITION_SPLIT:
 945       for (n = 0; n < 4; n++) {
 946         int j = n >> 1, i = n & 0x01;
 947         *(get_sb_index(xd, subsize)) = n;
 948         write_modes_sb(cpi, m + j * bs * mis + i * bs, bc, tok, tok_end,
 949                        mi_row + j * bs, mi_col + i * bs, subsize);
 950       }
 951       break;
 952     default:
 953       assert(0);
 954   }
 955
 956   // update partition context
 957   if (bsize >= BLOCK_SIZE_SB8X8 &&
 958       (bsize == BLOCK_SIZE_SB8X8 || partition != PARTITION_SPLIT)) {
 959     set_partition_seg_context(cm, xd, mi_row, mi_col);
 960     update_partition_context(xd, subsize, bsize);
 961   }
 962 }
 963
 964 static void write_modes(VP9_COMP *cpi, vp9_writer* const bc,
 965                         TOKENEXTRA **tok, TOKENEXTRA *tok_end) {
 966   VP9_COMMON *const c = &cpi->common;
 967   const int mis = c->mode_info_stride;
 968   MODE_INFO *m, *m_ptr = c->mi;
 969   int mi_row, mi_col;
 970
 971   m_ptr += c->cur_tile_mi_col_start + c->cur_tile_mi_row_start * mis;
 972   vpx_memset(c->above_seg_context, 0, sizeof(PARTITION_CONTEXT) *
 973              mi_cols_aligned_to_sb(c));
 974
 975   for (mi_row = c->cur_tile_mi_row_start;
 976        mi_row < c->cur_tile_mi_row_end;
 977        mi_row += 8, m_ptr += 8 * mis) {
 978     m = m_ptr;
 979     vpx_memset(c->left_seg_context, 0, sizeof(c->left_seg_context));
 980     for (mi_col = c->cur_tile_mi_col_start;
 981          mi_col < c->cur_tile_mi_col_end;
 982          mi_col += 64 / MI_SIZE, m += 64 / MI_SIZE)
 983       write_modes_sb(cpi, m, bc, tok, tok_end, mi_row, mi_col,
 984                      BLOCK_SIZE_SB64X64);
 985   }
 986 }
 987
 988 /* This function is used for debugging probability trees. */
 989 static void print_prob_tree(vp9_coeff_probs *coef_probs, int block_types) {
 990   /* print coef probability tree */
 991   int i, j, k, l, m;
 992   FILE *f = fopen("enc_tree_probs.txt", "a");
 993   fprintf(f, "{\n");
 994   for (i = 0; i < block_types; i++) {
 995     fprintf(f, "  {\n");
 996     for (j = 0; j < REF_TYPES; ++j) {
 997       fprintf(f, "  {\n");
 998       for (k = 0; k < COEF_BANDS; k++) {
 999         fprintf(f, "    {\n");
1000         for (l = 0; l < PREV_COEF_CONTEXTS; l++) {
1001           fprintf(f, "      {");
1002           for (m = 0; m < ENTROPY_NODES; m++) {
1003             fprintf(f, "%3u, ",
1004                     (unsigned int)(coef_probs[i][j][k][l][m]));
1005           }
1006         }
1007         fprintf(f, " }\n");
1008       }
1009       fprintf(f, "    }\n");
1010     }
1011     fprintf(f, "  }\n");
1012   }
1013   fprintf(f, "}\n");
1014   fclose(f);
1015 }
1016
1017 static void build_tree_distribution(vp9_coeff_probs_model *coef_probs,
1018                                     vp9_coeff_count *coef_counts,
1019                                     unsigned int (*eob_branch_ct)[REF_TYPES]
1020                                                                  [COEF_BANDS]
1021                                                           [PREV_COEF_CONTEXTS],
1022 #ifdef ENTROPY_STATS
1023                                     VP9_COMP *cpi,
1024                                     vp9_coeff_accum *context_counters,
1025 #endif
1026                                     vp9_coeff_stats *coef_branch_ct,
1027                                     int block_types) {
1028   int i, j, k, l;
1029 #ifdef ENTROPY_STATS
1030   int t = 0;
1031 #endif
1032   vp9_prob full_probs[ENTROPY_NODES];
1033
1034   for (i = 0; i < block_types; ++i) {
1035     for (j = 0; j < REF_TYPES; ++j) {
1036       for (k = 0; k < COEF_BANDS; ++k) {
1037         for (l = 0; l < PREV_COEF_CONTEXTS; ++l) {
1038           if (l >= 3 && k == 0)
1039             continue;
1040           vp9_tree_probs_from_distribution(vp9_coef_tree,
1041                                            full_probs,
1042                                            coef_branch_ct[i][j][k][l],
1043                                            coef_counts[i][j][k][l], 0);
1044           vpx_memcpy(coef_probs[i][j][k][l], full_probs,
1045                      sizeof(vp9_prob) * UNCONSTRAINED_NODES);
1046 #if CONFIG_BALANCED_COEFTREE
1047           coef_branch_ct[i][j][k][l][1][1] = eob_branch_ct[i][j][k][l] -
1048                                              coef_branch_ct[i][j][k][l][1][0];
1049           coef_probs[i][j][k][l][1] =
1050               get_binary_prob(coef_branch_ct[i][j][k][l][1][0],
1051                               coef_branch_ct[i][j][k][l][1][1]);
1052 #else
1053           coef_branch_ct[i][j][k][l][0][1] = eob_branch_ct[i][j][k][l] -
1054                                              coef_branch_ct[i][j][k][l][0][0];
1055           coef_probs[i][j][k][l][0] =
1056               get_binary_prob(coef_branch_ct[i][j][k][l][0][0],
1057                               coef_branch_ct[i][j][k][l][0][1]);
1058 #endif
1059 #ifdef ENTROPY_STATS
1060           if (!cpi->dummy_packing) {
1061             for (t = 0; t < MAX_ENTROPY_TOKENS; ++t)
1062               context_counters[i][j][k][l][t] += coef_counts[i][j][k][l][t];
1063             context_counters[i][j][k][l][MAX_ENTROPY_TOKENS] +=
1064                 eob_branch_ct[i][j][k][l];
1065           }
1066 #endif
1067         }
1068       }
1069     }
1070   }
1071 }
1072
1073 static void build_coeff_contexts(VP9_COMP *cpi) {
1074   build_tree_distribution(cpi->frame_coef_probs_4x4,
1075                           cpi->coef_counts_4x4,
1076                           cpi->common.fc.eob_branch_counts[TX_4X4],
1077 #ifdef ENTROPY_STATS
1078                           cpi, context_counters_4x4,
1079 #endif
1080                           cpi->frame_branch_ct_4x4, BLOCK_TYPES);
1081   build_tree_distribution(cpi->frame_coef_probs_8x8,
1082                           cpi->coef_counts_8x8,
1083                           cpi->common.fc.eob_branch_counts[TX_8X8],
1084 #ifdef ENTROPY_STATS
1085                           cpi, context_counters_8x8,
1086 #endif
1087                           cpi->frame_branch_ct_8x8, BLOCK_TYPES);
1088   build_tree_distribution(cpi->frame_coef_probs_16x16,
1089                           cpi->coef_counts_16x16,
1090                           cpi->common.fc.eob_branch_counts[TX_16X16],
1091 #ifdef ENTROPY_STATS
1092                           cpi, context_counters_16x16,
1093 #endif
1094                           cpi->frame_branch_ct_16x16, BLOCK_TYPES);
1095   build_tree_distribution(cpi->frame_coef_probs_32x32,
1096                           cpi->coef_counts_32x32,
1097                           cpi->common.fc.eob_branch_counts[TX_32X32],
1098 #ifdef ENTROPY_STATS
1099                           cpi, context_counters_32x32,
1100 #endif
1101                           cpi->frame_branch_ct_32x32, BLOCK_TYPES);
1102 }
1103
1104 static void update_coef_probs_common(
1105     vp9_writer* const bc,
1106     VP9_COMP *cpi,
1107 #ifdef ENTROPY_STATS
1108     vp9_coeff_stats *tree_update_hist,
1109 #endif
1110     vp9_coeff_probs_model *new_frame_coef_probs,
1111     vp9_coeff_probs_model *old_frame_coef_probs,
1112     vp9_coeff_stats *frame_branch_ct,
1113     TX_SIZE tx_size) {
1114   int i, j, k, l, t;
1115   int update[2] = {0, 0};
1116   int savings;
1117
1118   const int entropy_nodes_update = UNCONSTRAINED_NODES;
1119
1120   const int tstart = 0;
1121   /* dry run to see if there is any udpate at all needed */
1122   savings = 0;
1123   for (i = 0; i < BLOCK_TYPES; ++i) {
1124     for (j = 0; j < REF_TYPES; ++j) {
1125       for (k = 0; k < COEF_BANDS; ++k) {
1126         // int prev_coef_savings[ENTROPY_NODES] = {0};
1127         for (l = 0; l < PREV_COEF_CONTEXTS; ++l) {
1128           for (t = tstart; t < entropy_nodes_update; ++t) {
1129             vp9_prob newp = new_frame_coef_probs[i][j][k][l][t];
1130             const vp9_prob oldp = old_frame_coef_probs[i][j][k][l][t];
1131             const vp9_prob upd = vp9_coef_update_prob[t];
1132             int s;
1133             int u = 0;
1134
1135             if (l >= 3 && k == 0)
1136               continue;
1137             if (t == PIVOT_NODE)
1138               s = prob_diff_update_savings_search_model(
1139                   frame_branch_ct[i][j][k][l][0],
1140                   old_frame_coef_probs[i][j][k][l], &newp, upd, i, j);
1141             else
1142               s = prob_diff_update_savings_search(
1143                   frame_branch_ct[i][j][k][l][t], oldp, &newp, upd);
1144             if (s > 0 && newp != oldp)
1145               u = 1;
1146             if (u)
1147               savings += s - (int)(vp9_cost_zero(upd));
1148             else
1149               savings -= (int)(vp9_cost_zero(upd));
1150             update[u]++;
1151           }
1152         }
1153       }
1154     }
1155   }
1156
1157   // printf("Update %d %d, savings %d\n", update[0], update[1], savings);
1158   /* Is coef updated at all */
1159   if (update[1] == 0 || savings < 0) {
1160     vp9_write_bit(bc, 0);
1161     return;
1162   }
1163   vp9_write_bit(bc, 1);
1164   for (i = 0; i < BLOCK_TYPES; ++i) {
1165     for (j = 0; j < REF_TYPES; ++j) {
1166       for (k = 0; k < COEF_BANDS; ++k) {
1167         // int prev_coef_savings[ENTROPY_NODES] = {0};
1168         for (l = 0; l < PREV_COEF_CONTEXTS; ++l) {
1169           // calc probs and branch cts for this frame only
1170           for (t = tstart; t < entropy_nodes_update; ++t) {
1171             vp9_prob newp = new_frame_coef_probs[i][j][k][l][t];
1172             vp9_prob *oldp = old_frame_coef_probs[i][j][k][l] + t;
1173             const vp9_prob upd = vp9_coef_update_prob[t];
1174             int s;
1175             int u = 0;
1176             if (l >= 3 && k == 0)
1177               continue;
1178             if (t == PIVOT_NODE)
1179               s = prob_diff_update_savings_search_model(
1180                   frame_branch_ct[i][j][k][l][0],
1181                   old_frame_coef_probs[i][j][k][l], &newp, upd, i, j);
1182             else
1183               s = prob_diff_update_savings_search(
1184                   frame_branch_ct[i][j][k][l][t],
1185                   *oldp, &newp, upd);
1186             if (s > 0 && newp != *oldp)
1187               u = 1;
1188             vp9_write(bc, u, upd);
1189 #ifdef ENTROPY_STATS
1190             if (!cpi->dummy_packing)
1191               ++tree_update_hist[i][j][k][l][t][u];
1192 #endif
1193             if (u) {
1194               /* send/use new probability */
1195               write_prob_diff_update(bc, newp, *oldp);
1196               *oldp = newp;
1197             }
1198           }
1199         }
1200       }
1201     }
1202   }
1203 }
1204
1205 static void update_coef_probs(VP9_COMP* const cpi, vp9_writer* const bc) {
1206   vp9_clear_system_state();
1207
1208   // Build the cofficient contexts based on counts collected in encode loop
1209   build_coeff_contexts(cpi);
1210
1211   update_coef_probs_common(bc,
1212                            cpi,
1213 #ifdef ENTROPY_STATS
1214                            tree_update_hist_4x4,
1215 #endif
1216                            cpi->frame_coef_probs_4x4,
1217                            cpi->common.fc.coef_probs_4x4,
1218                            cpi->frame_branch_ct_4x4,
1219                            TX_4X4);
1220
1221   /* do not do this if not even allowed */
1222   if (cpi->common.txfm_mode != ONLY_4X4) {
1223     update_coef_probs_common(bc,
1224                              cpi,
1225 #ifdef ENTROPY_STATS
1226                              tree_update_hist_8x8,
1227 #endif
1228                              cpi->frame_coef_probs_8x8,
1229                              cpi->common.fc.coef_probs_8x8,
1230                              cpi->frame_branch_ct_8x8,
1231                              TX_8X8);
1232   }
1233
1234   if (cpi->common.txfm_mode > ALLOW_8X8) {
1235     update_coef_probs_common(bc,
1236                              cpi,
1237 #ifdef ENTROPY_STATS
1238                              tree_update_hist_16x16,
1239 #endif
1240                              cpi->frame_coef_probs_16x16,
1241                              cpi->common.fc.coef_probs_16x16,
1242                              cpi->frame_branch_ct_16x16,
1243                              TX_16X16);
1244   }
1245
1246   if (cpi->common.txfm_mode > ALLOW_16X16) {
1247     update_coef_probs_common(bc,
1248                              cpi,
1249 #ifdef ENTROPY_STATS
1250                              tree_update_hist_32x32,
1251 #endif
1252                              cpi->frame_coef_probs_32x32,
1253                              cpi->common.fc.coef_probs_32x32,
1254                              cpi->frame_branch_ct_32x32,
1255                              TX_32X32);
1256   }
1257 }
1258
1259 static void segment_reference_frames(VP9_COMP *cpi) {
1260   VP9_COMMON *oci = &cpi->common;
1261   MODE_INFO *mi = oci->mi;
1262   int ref[MAX_MB_SEGMENTS] = {0};
1263   int i, j;
1264   int mb_index = 0;
1265   MACROBLOCKD *const xd = &cpi->mb.e_mbd;
1266
1267   for (i = 0; i < oci->mb_rows; i++) {
1268     for (j = 0; j < oci->mb_cols; j++, mb_index++)
1269       ref[mi[mb_index].mbmi.segment_id] |= (1 << mi[mb_index].mbmi.ref_frame);
1270     mb_index++;
1271   }
1272   for (i = 0; i < MAX_MB_SEGMENTS; i++) {
1273     vp9_enable_segfeature(xd, i, SEG_LVL_REF_FRAME);
1274     vp9_set_segdata(xd, i, SEG_LVL_REF_FRAME, ref[i]);
1275   }
1276 }
1277
1278 static void encode_loopfilter(VP9_COMMON *pc, MACROBLOCKD *xd, vp9_writer *w) {
1279   int i;
1280
1281   // Encode the loop filter level and type
1282   vp9_write_literal(w, pc->filter_level, 6);
1283   vp9_write_literal(w, pc->sharpness_level, 3);
1284
1285   // Write out loop filter deltas applied at the MB level based on mode or
1286   // ref frame (if they are enabled).
1287   vp9_write_bit(w, xd->mode_ref_lf_delta_enabled);
1288
1289   if (xd->mode_ref_lf_delta_enabled) {
1290     // Do the deltas need to be updated
1291     vp9_write_bit(w, xd->mode_ref_lf_delta_update);
1292     if (xd->mode_ref_lf_delta_update) {
1293       // Send update
1294       for (i = 0; i < MAX_REF_LF_DELTAS; i++) {
1295         const int delta = xd->ref_lf_deltas[i];
1296
1297         // Frame level data
1298         if (delta != xd->last_ref_lf_deltas[i]) {
1299           xd->last_ref_lf_deltas[i] = delta;
1300           vp9_write_bit(w, 1);
1301
1302           if (delta > 0) {
1303             vp9_write_literal(w, delta & 0x3F, 6);
1304             vp9_write_bit(w, 0);  // sign
1305           } else {
1306             assert(delta < 0);
1307             vp9_write_literal(w, (-delta) & 0x3F, 6);
1308             vp9_write_bit(w, 1);  // sign
1309           }
1310         } else {
1311           vp9_write_bit(w, 0);
1312         }
1313       }
1314
1315       // Send update
1316       for (i = 0; i < MAX_MODE_LF_DELTAS; i++) {
1317         const int delta = xd->mode_lf_deltas[i];
1318         if (delta != xd->last_mode_lf_deltas[i]) {
1319           xd->last_mode_lf_deltas[i] = delta;
1320           vp9_write_bit(w, 1);
1321
1322           if (delta > 0) {
1323             vp9_write_literal(w, delta & 0x3F, 6);
1324             vp9_write_bit(w, 0);  // sign
1325           } else {
1326             assert(delta < 0);
1327             vp9_write_literal(w, (-delta) & 0x3F, 6);
1328             vp9_write_bit(w, 1);  // sign
1329           }
1330         } else {
1331           vp9_write_bit(w, 0);
1332         }
1333       }
1334     }
1335   }
1336 }
1337
1338 static void put_delta_q(vp9_writer *bc, int delta_q) {
1339   if (delta_q != 0) {
1340     vp9_write_bit(bc, 1);
1341     vp9_write_literal(bc, abs(delta_q), 4);
1342     vp9_write_bit(bc, delta_q < 0);
1343   } else {
1344     vp9_write_bit(bc, 0);
1345   }
1346 }
1347
1348 static void encode_quantization(VP9_COMMON *pc, vp9_writer *w) {
1349   vp9_write_literal(w, pc->base_qindex, QINDEX_BITS);
1350   put_delta_q(w, pc->y_dc_delta_q);
1351   put_delta_q(w, pc->uv_dc_delta_q);
1352   put_delta_q(w, pc->uv_ac_delta_q);
1353 }
1354
1355
1356 static void encode_segmentation(VP9_COMP *cpi, vp9_writer *w) {
1357   int i, j;
1358   VP9_COMMON *const pc = &cpi->common;
1359   MACROBLOCKD *const xd = &cpi->mb.e_mbd;
1360
1361   vp9_write_bit(w, xd->segmentation_enabled);
1362   if (!xd->segmentation_enabled)
1363     return;
1364
1365   // Segmentation map
1366   vp9_write_bit(w, xd->update_mb_segmentation_map);
1367   if (xd->update_mb_segmentation_map) {
1368     // Select the coding strategy (temporal or spatial)
1369     vp9_choose_segmap_coding_method(cpi);
1370     // Write out probabilities used to decode unpredicted  macro-block segments
1371     for (i = 0; i < MB_SEG_TREE_PROBS; i++) {
1372       const int prob = xd->mb_segment_tree_probs[i];
1373       if (prob != MAX_PROB) {
1374         vp9_write_bit(w, 1);
1375         vp9_write_prob(w, prob);
1376       } else {
1377         vp9_write_bit(w, 0);
1378       }
1379     }
1380
1381     // Write out the chosen coding method.
1382     vp9_write_bit(w, pc->temporal_update);
1383     if (pc->temporal_update) {
1384       for (i = 0; i < PREDICTION_PROBS; i++) {
1385         const int prob = pc->segment_pred_probs[i];
1386         if (prob != MAX_PROB) {
1387           vp9_write_bit(w, 1);
1388           vp9_write_prob(w, prob);
1389         } else {
1390           vp9_write_bit(w, 0);
1391         }
1392       }
1393     }
1394   }
1395
1396   // Segmentation data
1397   vp9_write_bit(w, xd->update_mb_segmentation_data);
1398   // segment_reference_frames(cpi);
1399   if (xd->update_mb_segmentation_data) {
1400     vp9_write_bit(w, xd->mb_segment_abs_delta);
1401
1402     for (i = 0; i < MAX_MB_SEGMENTS; i++) {
1403       for (j = 0; j < SEG_LVL_MAX; j++) {
1404         const int data = vp9_get_segdata(xd, i, j);
1405         const int data_max = vp9_seg_feature_data_max(j);
1406
1407         if (vp9_segfeature_active(xd, i, j)) {
1408           vp9_write_bit(w, 1);
1409
1410           if (vp9_is_segfeature_signed(j)) {
1411             if (data < 0) {
1412               vp9_encode_unsigned_max(w, -data, data_max);
1413               vp9_write_bit(w, 1);
1414             } else {
1415               vp9_encode_unsigned_max(w, data, data_max);
1416               vp9_write_bit(w, 0);
1417             }
1418           } else {
1419             vp9_encode_unsigned_max(w, data, data_max);
1420           }
1421         } else {
1422           vp9_write_bit(w, 0);
1423         }
1424       }
1425     }
1426   }
1427 }
1428
1429 void write_uncompressed_header(VP9_COMMON *cm,
1430                                struct vp9_write_bit_buffer *wb) {
1431   const int scaling_active = cm->width != cm->display_width ||
1432                              cm->height != cm->display_height;
1433
1434   vp9_wb_write_bit(wb, cm->frame_type);
1435   vp9_wb_write_literal(wb, cm->version, 3);
1436   vp9_wb_write_bit(wb, cm->show_frame);
1437   vp9_wb_write_bit(wb, scaling_active);
1438   vp9_wb_write_bit(wb, cm->subsampling_x);
1439   vp9_wb_write_bit(wb, cm->subsampling_y);
1440
1441   if (cm->frame_type == KEY_FRAME) {
1442     vp9_wb_write_literal(wb, SYNC_CODE_0, 8);
1443     vp9_wb_write_literal(wb, SYNC_CODE_1, 8);
1444     vp9_wb_write_literal(wb, SYNC_CODE_2, 8);
1445   }
1446
1447   if (scaling_active) {
1448     vp9_wb_write_literal(wb, cm->display_width, 16);
1449     vp9_wb_write_literal(wb, cm->display_height, 16);
1450   }
1451
1452   vp9_wb_write_literal(wb, cm->width, 16);
1453   vp9_wb_write_literal(wb, cm->height, 16);
1454
1455   if (!cm->show_frame) {
1456       vp9_wb_write_bit(wb, cm->intra_only);
1457   }
1458
1459   vp9_wb_write_literal(wb, cm->frame_context_idx, NUM_FRAME_CONTEXTS_LG2);
1460   vp9_wb_write_bit(wb, cm->clr_type);
1461
1462   vp9_wb_write_bit(wb, cm->error_resilient_mode);
1463   if (!cm->error_resilient_mode) {
1464     vp9_wb_write_bit(wb, cm->reset_frame_context);
1465     vp9_wb_write_bit(wb, cm->refresh_frame_context);
1466     vp9_wb_write_bit(wb, cm->frame_parallel_decoding_mode);
1467   }
1468 }
1469
1470 void vp9_pack_bitstream(VP9_COMP *cpi, uint8_t *dest, unsigned long *size) {
1471   int i, bytes_packed;
1472   VP9_COMMON *const pc = &cpi->common;
1473   vp9_writer header_bc, residual_bc;
1474   MACROBLOCKD *const xd = &cpi->mb.e_mbd;
1475
1476   uint8_t *cx_data = dest;
1477   struct vp9_write_bit_buffer wb = {dest, 0};
1478   struct vp9_write_bit_buffer first_partition_size_wb;
1479
1480   write_uncompressed_header(pc, &wb);
1481   first_partition_size_wb = wb;
1482   vp9_wb_write_literal(&wb, 0, 16);  // don't know in advance first part. size
1483
1484   bytes_packed = vp9_rb_bytes_written(&wb);
1485   cx_data += bytes_packed;
1486
1487   compute_update_table();
1488
1489   vp9_start_encode(&header_bc, cx_data);
1490
1491   encode_loopfilter(pc, xd, &header_bc);
1492
1493   encode_quantization(pc, &header_bc);
1494
1495   // When there is a key frame all reference buffers are updated using the new key frame
1496   if (pc->frame_type != KEY_FRAME) {
1497     int refresh_mask;
1498
1499     // Should the GF or ARF be updated using the transmitted frame or buffer
1500 #if CONFIG_MULTIPLE_ARF
1501     if (!cpi->multi_arf_enabled && cpi->refresh_golden_frame &&
1502         !cpi->refresh_alt_ref_frame) {
1503 #else
1504       if (cpi->refresh_golden_frame && !cpi->refresh_alt_ref_frame) {
1505 #endif
1506       /* Preserve the previously existing golden frame and update the frame in
1507        * the alt ref slot instead. This is highly specific to the use of
1508        * alt-ref as a forward reference, and this needs to be generalized as
1509        * other uses are implemented (like RTC/temporal scaling)
1510        *
1511        * gld_fb_idx and alt_fb_idx need to be swapped for future frames, but
1512        * that happens in vp9_onyx_if.c:update_reference_frames() so that it can
1513        * be done outside of the recode loop.
1514        */
1515       refresh_mask = (cpi->refresh_last_frame << cpi->lst_fb_idx) |
1516                      (cpi->refresh_golden_frame << cpi->alt_fb_idx);
1517     } else {
1518       int arf_idx = cpi->alt_fb_idx;
1519 #if CONFIG_MULTIPLE_ARF
1520       // Determine which ARF buffer to use to encode this ARF frame.
1521       if (cpi->multi_arf_enabled) {
1522         int sn = cpi->sequence_number;
1523         arf_idx = (cpi->frame_coding_order[sn] < 0) ?
1524             cpi->arf_buffer_idx[sn + 1] :
1525             cpi->arf_buffer_idx[sn];
1526       }
1527 #endif
1528       refresh_mask = (cpi->refresh_last_frame << cpi->lst_fb_idx) |
1529                      (cpi->refresh_golden_frame << cpi->gld_fb_idx) |
1530                      (cpi->refresh_alt_ref_frame << arf_idx);
1531     }
1532
1533     vp9_write_literal(&header_bc, refresh_mask, NUM_REF_FRAMES);
1534     vp9_write_literal(&header_bc, cpi->lst_fb_idx, NUM_REF_FRAMES_LG2);
1535     vp9_write_literal(&header_bc, cpi->gld_fb_idx, NUM_REF_FRAMES_LG2);
1536     vp9_write_literal(&header_bc, cpi->alt_fb_idx, NUM_REF_FRAMES_LG2);
1537
1538     // Indicate the sign bias for each reference frame buffer.
1539     for (i = 0; i < ALLOWED_REFS_PER_FRAME; ++i) {
1540       vp9_write_bit(&header_bc, pc->ref_frame_sign_bias[LAST_FRAME + i]);
1541     }
1542
1543     // Signal whether to allow high MV precision
1544     vp9_write_bit(&header_bc, (xd->allow_high_precision_mv) ? 1 : 0);
1545     if (pc->mcomp_filter_type == SWITCHABLE) {
1546       /* Check to see if only one of the filters is actually used */
1547       int count[VP9_SWITCHABLE_FILTERS];
1548       int i, j, c = 0;
1549       for (i = 0; i < VP9_SWITCHABLE_FILTERS; ++i) {
1550         count[i] = 0;
1551         for (j = 0; j <= VP9_SWITCHABLE_FILTERS; ++j)
1552           count[i] += cpi->switchable_interp_count[j][i];
1553         c += (count[i] > 0);
1554       }
1555       if (c == 1) {
1556         /* Only one filter is used. So set the filter at frame level */
1557         for (i = 0; i < VP9_SWITCHABLE_FILTERS; ++i) {
1558           if (count[i]) {
1559             pc->mcomp_filter_type = vp9_switchable_interp[i];
1560             break;
1561           }
1562         }
1563       }
1564     }
1565     // Signal the type of subpel filter to use
1566     vp9_write_bit(&header_bc, (pc->mcomp_filter_type == SWITCHABLE));
1567     if (pc->mcomp_filter_type != SWITCHABLE)
1568       vp9_write_literal(&header_bc, (pc->mcomp_filter_type), 2);
1569   }
1570
1571 #ifdef ENTROPY_STATS
1572   if (pc->frame_type == INTER_FRAME)
1573     active_section = 0;
1574   else
1575     active_section = 7;
1576 #endif
1577
1578   encode_segmentation(cpi, &header_bc);
1579
1580   // Encode the common prediction model status flag probability updates for
1581   // the reference frame
1582   update_refpred_stats(cpi);
1583   if (pc->frame_type != KEY_FRAME) {
1584     for (i = 0; i < PREDICTION_PROBS; i++) {
1585       if (cpi->ref_pred_probs_update[i]) {
1586         vp9_write_bit(&header_bc, 1);
1587         vp9_write_prob(&header_bc, pc->ref_pred_probs[i]);
1588       } else {
1589         vp9_write_bit(&header_bc, 0);
1590       }
1591     }
1592   }
1593
1594   if (cpi->mb.e_mbd.lossless) {
1595     pc->txfm_mode = ONLY_4X4;
1596   } else {
1597     if (pc->txfm_mode == TX_MODE_SELECT) {
1598       pc->prob_tx[0] = get_prob(cpi->txfm_count_32x32p[TX_4X4] +
1599                                 cpi->txfm_count_16x16p[TX_4X4] +
1600                                 cpi->txfm_count_8x8p[TX_4X4],
1601                                 cpi->txfm_count_32x32p[TX_4X4] +
1602                                 cpi->txfm_count_32x32p[TX_8X8] +
1603                                 cpi->txfm_count_32x32p[TX_16X16] +
1604                                 cpi->txfm_count_32x32p[TX_32X32] +
1605                                 cpi->txfm_count_16x16p[TX_4X4] +
1606                                 cpi->txfm_count_16x16p[TX_8X8] +
1607                                 cpi->txfm_count_16x16p[TX_16X16] +
1608                                 cpi->txfm_count_8x8p[TX_4X4] +
1609                                 cpi->txfm_count_8x8p[TX_8X8]);
1610       pc->prob_tx[1] = get_prob(cpi->txfm_count_32x32p[TX_8X8] +
1611                                 cpi->txfm_count_16x16p[TX_8X8],
1612                                 cpi->txfm_count_32x32p[TX_8X8] +
1613                                 cpi->txfm_count_32x32p[TX_16X16] +
1614                                 cpi->txfm_count_32x32p[TX_32X32] +
1615                                 cpi->txfm_count_16x16p[TX_8X8] +
1616                                 cpi->txfm_count_16x16p[TX_16X16]);
1617       pc->prob_tx[2] = get_prob(cpi->txfm_count_32x32p[TX_16X16],
1618                                 cpi->txfm_count_32x32p[TX_16X16] +
1619                                 cpi->txfm_count_32x32p[TX_32X32]);
1620     } else {
1621       pc->prob_tx[0] = 128;
1622       pc->prob_tx[1] = 128;
1623       pc->prob_tx[2] = 128;
1624     }
1625     vp9_write_literal(&header_bc, pc->txfm_mode <= 3 ? pc->txfm_mode : 3, 2);
1626     if (pc->txfm_mode > ALLOW_16X16) {
1627       vp9_write_bit(&header_bc, pc->txfm_mode == TX_MODE_SELECT);
1628     }
1629     if (pc->txfm_mode == TX_MODE_SELECT) {
1630       vp9_write_prob(&header_bc, pc->prob_tx[0]);
1631       vp9_write_prob(&header_bc, pc->prob_tx[1]);
1632       vp9_write_prob(&header_bc, pc->prob_tx[2]);
1633     }
1634   }
1635
1636   // If appropriate update the inter mode probability context and code the
1637   // changes in the bitstream.
1638   if (pc->frame_type != KEY_FRAME) {
1639     int i, j;
1640     int new_context[INTER_MODE_CONTEXTS][VP9_MVREFS - 1];
1641     if (!cpi->dummy_packing) {
1642       update_inter_mode_probs(pc, new_context);
1643     } else {
1644       // In dummy pack assume context unchanged.
1645       vpx_memcpy(new_context, pc->fc.vp9_mode_contexts,
1646                  sizeof(pc->fc.vp9_mode_contexts));
1647     }
1648
1649     for (i = 0; i < INTER_MODE_CONTEXTS; i++) {
1650       for (j = 0; j < VP9_MVREFS - 1; j++) {
1651         if (new_context[i][j] != pc->fc.vp9_mode_contexts[i][j]) {
1652           vp9_write(&header_bc, 1, 252);
1653           vp9_write_prob(&header_bc, new_context[i][j]);
1654
1655           // Only update the persistent copy if this is the "real pack"
1656           if (!cpi->dummy_packing) {
1657             pc->fc.vp9_mode_contexts[i][j] = new_context[i][j];
1658           }
1659         } else {
1660           vp9_write(&header_bc, 0, 252);
1661         }
1662       }
1663     }
1664   }
1665
1666   vp9_clear_system_state();  // __asm emms;
1667
1668   vp9_copy(cpi->common.fc.pre_coef_probs_4x4,
1669            cpi->common.fc.coef_probs_4x4);
1670   vp9_copy(cpi->common.fc.pre_coef_probs_8x8,
1671            cpi->common.fc.coef_probs_8x8);
1672   vp9_copy(cpi->common.fc.pre_coef_probs_16x16,
1673            cpi->common.fc.coef_probs_16x16);
1674   vp9_copy(cpi->common.fc.pre_coef_probs_32x32,
1675            cpi->common.fc.coef_probs_32x32);
1676
1677   vp9_copy(cpi->common.fc.pre_y_mode_prob, cpi->common.fc.y_mode_prob);
1678   vp9_copy(cpi->common.fc.pre_uv_mode_prob, cpi->common.fc.uv_mode_prob);
1679   vp9_copy(cpi->common.fc.pre_partition_prob, cpi->common.fc.partition_prob);
1680   cpi->common.fc.pre_nmvc = cpi->common.fc.nmvc;
1681   vp9_zero(cpi->common.fc.mv_ref_ct);
1682
1683   update_coef_probs(cpi, &header_bc);
1684
1685 #ifdef ENTROPY_STATS
1686   active_section = 2;
1687 #endif
1688
1689   vp9_update_skip_probs(cpi);
1690   for (i = 0; i < MBSKIP_CONTEXTS; ++i) {
1691     vp9_write_prob(&header_bc, pc->mbskip_pred_probs[i]);
1692   }
1693
1694   if (pc->frame_type != KEY_FRAME) {
1695     // Update the probabilities used to encode reference frame data
1696     update_ref_probs(cpi);
1697
1698 #ifdef ENTROPY_STATS
1699     active_section = 1;
1700 #endif
1701
1702     if (pc->mcomp_filter_type == SWITCHABLE)
1703       update_switchable_interp_probs(cpi, &header_bc);
1704
1705     vp9_write_prob(&header_bc, pc->prob_intra_coded);
1706     vp9_write_prob(&header_bc, pc->prob_last_coded);
1707     vp9_write_prob(&header_bc, pc->prob_gf_coded);
1708
1709     {
1710       const int comp_pred_mode = cpi->common.comp_pred_mode;
1711       const int use_compound_pred = (comp_pred_mode != SINGLE_PREDICTION_ONLY);
1712       const int use_hybrid_pred = (comp_pred_mode == HYBRID_PREDICTION);
1713
1714       vp9_write_bit(&header_bc, use_compound_pred);
1715       if (use_compound_pred) {
1716         vp9_write_bit(&header_bc, use_hybrid_pred);
1717         if (use_hybrid_pred) {
1718           for (i = 0; i < COMP_PRED_CONTEXTS; i++) {
1719             pc->prob_comppred[i] = get_binary_prob(cpi->single_pred_count[i],
1720                                                    cpi->comp_pred_count[i]);
1721             vp9_write_prob(&header_bc, pc->prob_comppred[i]);
1722           }
1723         }
1724       }
1725     }
1726     update_mbintra_mode_probs(cpi, &header_bc);
1727
1728     for (i = 0; i < NUM_PARTITION_CONTEXTS; ++i) {
1729       vp9_prob Pnew[PARTITION_TYPES - 1];
1730       unsigned int bct[PARTITION_TYPES - 1][2];
1731       update_mode(&header_bc, PARTITION_TYPES, vp9_partition_encodings,
1732                   vp9_partition_tree, Pnew, pc->fc.partition_prob[i], bct,
1733                   (unsigned int *)cpi->partition_count[i]);
1734     }
1735
1736     vp9_write_nmv_probs(cpi, xd->allow_high_precision_mv, &header_bc);
1737   }
1738
1739   /* tiling */
1740   {
1741     int min_log2_tiles, delta_log2_tiles, n_tile_bits, n;
1742
1743     vp9_get_tile_n_bits(pc, &min_log2_tiles, &delta_log2_tiles);
1744     n_tile_bits = pc->log2_tile_columns - min_log2_tiles;
1745     for (n = 0; n < delta_log2_tiles; n++) {
1746       if (n_tile_bits--) {
1747         vp9_write_bit(&header_bc, 1);
1748       } else {
1749         vp9_write_bit(&header_bc, 0);
1750         break;
1751       }
1752     }
1753     vp9_write_bit(&header_bc, pc->log2_tile_rows != 0);
1754     if (pc->log2_tile_rows != 0)
1755       vp9_write_bit(&header_bc, pc->log2_tile_rows != 1);
1756   }
1757
1758   vp9_stop_encode(&header_bc);
1759
1760
1761   // first partition size
1762   assert(header_bc.pos <= 0xffff);
1763   vp9_wb_write_literal(&first_partition_size_wb, header_bc.pos, 16);
1764   *size = bytes_packed + header_bc.pos;
1765
1766   {
1767     int tile_row, tile_col, total_size = 0;
1768     unsigned char *data_ptr = cx_data + header_bc.pos;
1769     TOKENEXTRA *tok[1 << 6], *tok_end;
1770
1771     tok[0] = cpi->tok;
1772     for (tile_col = 1; tile_col < pc->tile_columns; tile_col++)
1773       tok[tile_col] = tok[tile_col - 1] + cpi->tok_count[tile_col - 1];
1774
1775     for (tile_row = 0; tile_row < pc->tile_rows; tile_row++) {
1776       vp9_get_tile_row_offsets(pc, tile_row);
1777       tok_end = cpi->tok + cpi->tok_count[0];
1778       for (tile_col = 0; tile_col < pc->tile_columns;
1779            tile_col++, tok_end += cpi->tok_count[tile_col]) {
1780         vp9_get_tile_col_offsets(pc, tile_col);
1781
1782         if (tile_col < pc->tile_columns - 1 || tile_row < pc->tile_rows - 1)
1783           vp9_start_encode(&residual_bc, data_ptr + total_size + 4);
1784         else
1785           vp9_start_encode(&residual_bc, data_ptr + total_size);
1786         write_modes(cpi, &residual_bc, &tok[tile_col], tok_end);
1787         vp9_stop_encode(&residual_bc);
1788         if (tile_col < pc->tile_columns - 1 || tile_row < pc->tile_rows - 1) {
1789           // size of this tile
1790           write_le32(data_ptr + total_size, residual_bc.pos);
1791           total_size += 4;
1792         }
1793
1794         total_size += residual_bc.pos;
1795       }
1796     }
1797
1798     assert((unsigned int)(tok[0] - cpi->tok) == cpi->tok_count[0]);
1799     for (tile_col = 1; tile_col < pc->tile_columns; tile_col++)
1800       assert((unsigned int)(tok[tile_col] - tok[tile_col - 1]) ==
1801                   cpi->tok_count[tile_col]);
1802
1803     *size += total_size;
1804   }
1805 }
1806
1807 #ifdef ENTROPY_STATS
1808 static void print_tree_update_for_type(FILE *f,
1809                                        vp9_coeff_stats *tree_update_hist,
1810                                        int block_types, const char *header) {
1811   int i, j, k, l, m;
1812
1813   fprintf(f, "const vp9_coeff_prob %s = {\n", header);
1814   for (i = 0; i < block_types; i++) {
1815     fprintf(f, "  { \n");
1816     for (j = 0; j < REF_TYPES; j++) {
1817       fprintf(f, "  { \n");
1818       for (k = 0; k < COEF_BANDS; k++) {
1819         fprintf(f, "    {\n");
1820         for (l = 0; l < PREV_COEF_CONTEXTS; l++) {
1821           fprintf(f, "      {");
1822           for (m = 0; m < ENTROPY_NODES; m++) {
1823             fprintf(f, "%3d, ",
1824                     get_binary_prob(tree_update_hist[i][j][k][l][m][0],
1825                                     tree_update_hist[i][j][k][l][m][1]));
1826           }
1827           fprintf(f, "},\n");
1828         }
1829         fprintf(f, "},\n");
1830       }
1831       fprintf(f, "    },\n");
1832     }
1833     fprintf(f, "  },\n");
1834   }
1835   fprintf(f, "};\n");
1836 }
1837
1838 void print_tree_update_probs() {
1839   FILE *f = fopen("coefupdprob.h", "w");
1840   fprintf(f, "\n/* Update probabilities for token entropy tree. */\n\n");
1841
1842   print_tree_update_for_type(f, tree_update_hist_4x4, BLOCK_TYPES,
1843                              "vp9_coef_update_probs_4x4[BLOCK_TYPES]");
1844   print_tree_update_for_type(f, tree_update_hist_8x8, BLOCK_TYPES,
1845                              "vp9_coef_update_probs_8x8[BLOCK_TYPES]");
1846   print_tree_update_for_type(f, tree_update_hist_16x16, BLOCK_TYPES,
1847                              "vp9_coef_update_probs_16x16[BLOCK_TYPES]");
1848   print_tree_update_for_type(f, tree_update_hist_32x32, BLOCK_TYPES,
1849                              "vp9_coef_update_probs_32x32[BLOCK_TYPES]");
1850
1851   fclose(f);
1852   f = fopen("treeupdate.bin", "wb");
1853   fwrite(tree_update_hist_4x4, sizeof(tree_update_hist_4x4), 1, f);
1854   fwrite(tree_update_hist_8x8, sizeof(tree_update_hist_8x8), 1, f);
1855   fwrite(tree_update_hist_16x16, sizeof(tree_update_hist_16x16), 1, f);
1856   fwrite(tree_update_hist_32x32, sizeof(tree_update_hist_32x32), 1, f);
1857   fclose(f);
1858 }
1859 #endif