Further experimentation with the mode context

Experiments with a larger set of contexts and some
clean up to replace magic numbers regarding the
number of contexts.

The starting values and rate of backwards adaption
are still suspect and based on a small set of tests.
Added forwards adjustment of probabilities.

The net result of adding the new context and forward
update is small compared to the old context from the
legacy find_near function.  (down a little on derf but
up by a similar amount for HD)

HOWEVER.... with the new context and forward update
the impact of disabling the reverse update (which may be
necessary in some use cases to facilitate parallel decoding)
is hugely reduced.

For the old context without forward update, the impact of
turning off reverse update (Experiment was with SB off) was
Derf - 0.9, Yt -1.89, ythd -2.75 and sthd -8.35. The impact was
mainly at low data rates.

With the new context and forward update enabled the impact
for all the test sets was no more than 0.5-1% (again most at
the low end).

Change-Id: Ic751b414c8ce7f7f3ebc6f19a741d774d2b4b556

12 files changed, 120 insertions, 59 deletions

diff --git a/vp9/common/entropy.h b/vp9/common/entropy.h
index 884c6a1da..fa24a058e 100644
--- a/vp9/common/entropy.h
+++ b/vp9/common/entropy.h
@@ -37,6 +37,8 @@ extern const int vp9_i8x8_block[4];
 #define ENTROPY_NODES 11
 #define EOSB_TOKEN              127     /* Not signalled, encoder only */
 
+#define INTER_MODE_CONTEXTS     7
+
 extern const vp9_tree_index vp9_coef_tree[];
 
 extern struct vp9_token_struct vp9_coef_encodings[MAX_ENTROPY_TOKENS];
diff --git a/vp9/common/entropymode.c b/vp9/common/entropymode.c
index 83ba21c55..665528d48 100644
--- a/vp9/common/entropymode.c
+++ b/vp9/common/entropymode.c
@@ -441,7 +441,6 @@ void vp9_entropy_mode_init() {
 
 void vp9_init_mode_contexts(VP9_COMMON *pc) {
   vpx_memset(pc->fc.mv_ref_ct, 0, sizeof(pc->fc.mv_ref_ct));
-  vpx_memset(pc->fc.mv_ref_ct_a, 0, sizeof(pc->fc.mv_ref_ct_a));
 
   vpx_memcpy(pc->fc.mode_context,
              vp9_default_mode_contexts,
@@ -457,10 +456,7 @@ void vp9_accum_mv_refs(VP9_COMMON *pc,
                        const int context) {
   int (*mv_ref_ct)[4][2];
 
-  if (pc->refresh_alt_ref_frame)
-    mv_ref_ct = pc->fc.mv_ref_ct_a;
-  else
-    mv_ref_ct = pc->fc.mv_ref_ct;
+  mv_ref_ct = pc->fc.mv_ref_ct;
 
   if (m == ZEROMV) {
     ++mv_ref_ct[context][0][0];
@@ -485,19 +481,18 @@ void vp9_accum_mv_refs(VP9_COMMON *pc,
 }
 
 #define MVREF_COUNT_SAT 20
-#define MVREF_MAX_UPDATE_FACTOR 144
+#define MVREF_MAX_UPDATE_FACTOR 128
 void vp9_update_mode_context(VP9_COMMON *pc) {
   int i, j;
   int (*mv_ref_ct)[4][2];
   int (*mode_context)[4];
 
   if (pc->refresh_alt_ref_frame) {
-    mv_ref_ct = pc->fc.mv_ref_ct_a;
     mode_context = pc->fc.mode_context_a;
   } else {
-    mv_ref_ct = pc->fc.mv_ref_ct;
     mode_context = pc->fc.mode_context;
   }
+  mv_ref_ct = pc->fc.mv_ref_ct;
 
   for (j = 0; j < INTER_MODE_CONTEXTS; j++) {
     for (i = 0; i < 4; i++) {
@@ -522,14 +517,14 @@ void vp9_update_mode_context(VP9_COMMON *pc) {
 void print_mode_contexts(VP9_COMMON *pc) {
   int j, i;
   printf("\n====================\n");
-  for (j = 0; j < 6; j++) {
+  for (j = 0; j < INTER_MODE_CONTEXTS; j++) {
     for (i = 0; i < 4; i++) {
       printf("%4d ", pc->fc.mode_context[j][i]);
     }
     printf("\n");
   }
   printf("====================\n");
-  for (j = 0; j < 6; j++) {
+  for (j = 0; j < INTER_MODE_CONTEXTS; j++) {
     for (i = 0; i < 4; i++) {
       printf("%4d ", pc->fc.mode_context_a[j][i]);
     }
diff --git a/vp9/common/findnearmv.h b/vp9/common/findnearmv.h
index 256745261..4e6418a51 100644
--- a/vp9/common/findnearmv.h
+++ b/vp9/common/findnearmv.h
@@ -14,7 +14,6 @@
 
 #include "mv.h"
 #include "blockd.h"
-#include "modecont.h"
 #include "treecoder.h"
 #include "onyxc_int.h"
 
diff --git a/vp9/common/modecont.c b/vp9/common/modecont.c
index ac6719a1b..1a71eceb5 100644
--- a/vp9/common/modecont.c
+++ b/vp9/common/modecont.c
@@ -11,19 +11,21 @@
 
 #include "entropy.h"
 
-const int vp9_default_mode_contexts[6][4] = {
-  {117,     1,     1,    141},
-  {234,     1,     1,    213},
-  {128,     90,    22,   145},
-  {30,      104,   61,   159},
-  {13,      169,   18,   206},
-  {15,      76,    24,   166}
+const int vp9_default_mode_contexts[INTER_MODE_CONTEXTS][4] = {
+  {223,     1,     1,    237},  // 0,0 best: Only candidate
+  {87,      166,   26,   219},  // 0,0 best: non zero candidates
+  {89,      67,    18,   125},  // 0,0 best: non zero candidates, split
+  {16,      141,   69,   226},  // strong nz candidate(s), no split
+  {35,      122,   14,   227},  // weak nz candidate(s), no split
+  {14,      122,   22,   164},  // strong nz candidate(s), split
+  {16,      70,    9,    183},  // weak nz candidate(s), split
 };
-const int vp9_default_mode_contexts_a[6][4] = {
-  {117,     1,     1,    141},
-  {234,     1,     1,    213},
-  {128,     90,    22,   145},
-  {30,      104,   61,   159},
-  {13,      169,   18,   206},
-  {15,      76,    24,   166}
+const int vp9_default_mode_contexts_a[INTER_MODE_CONTEXTS][4] = {
+  {204,     1,     1,    213},  // 0,0 best: Only candidate
+  {106,     139,   22,   203},  // 0,0 best: non zero candidates
+  {75,      52,    15,   118},  // 0,0 best: non zero candidates, split
+  {12,      148,   61,   211},  // strong nz candidate(s), no split
+  {18,      98,    17,   199},  // weak nz candidate(s), no split
+  {11,      91,    25,   148},  // strong nz candidate(s), split
+  {10,      53,    9,    145},  // weak nz candidate(s), split
 };
diff --git a/vp9/common/modecont.h b/vp9/common/modecont.h
index c13c14f6c..1fa4558e1 100644
--- a/vp9/common/modecont.h
+++ b/vp9/common/modecont.h
@@ -12,6 +12,6 @@
 #ifndef __INC_MODECONT_H
 #define __INC_MODECONT_H
 
-extern const int vp9_default_mode_contexts[6][4];
-extern const int vp9_default_mode_contexts_a[6][4];
+extern const int vp9_default_mode_contexts[INTER_MODE_CONTEXTS][4];
+extern const int vp9_default_mode_contexts_a[INTER_MODE_CONTEXTS][4];
 #endif
diff --git a/vp9/common/mvref_common.c b/vp9/common/mvref_common.c
index 35c74ef89..ebb8fa4bd 100644
--- a/vp9/common/mvref_common.c
+++ b/vp9/common/mvref_common.c
@@ -231,6 +231,7 @@ void vp9_find_mv_refs(
   MV_REFERENCE_FRAME c2_ref_frame;
   int candidate_scores[MAX_MV_REFS];
   int index = 0;
+  int split_count = 0;
   int ref_weight = 0;
   int valid_mv_ref;
   int (*mv_ref_search)[2];
@@ -271,6 +272,7 @@ void vp9_find_mv_refs(
         scale_mv(xd, ref_frame, c_ref_frame, &c_refmv, ref_sign_bias );
         ref_weight = ref_distance_weight[i] +
                      ((c_ref_frame == ref_frame) << 4);
+        split_count += (candidate_mi->mbmi.mode == SPLITMV);
 
         addmv_and_shuffle(candidate_mvs, candidate_scores,
                           &index, c_refmv, ref_weight);
@@ -352,35 +354,39 @@ void vp9_find_mv_refs(
     index = (MAX_MV_REFS - 1);
   }
 
+  // Define inter mode coding context.
+  // 0,0 was best
   if (candidate_mvs[0].as_int == 0) {
-    // 0,0 was best
-    if (index == 0) {
-      // No reference candidates
+    // 0,0 is only candidate
+    if (index <= 1) {
       mbmi->mb_mode_context[ref_frame] = 0;
-    } else if (index == 1) {
-      // 0,0 was only candidate
+    // non zero candidates candidates available
+    } else if (split_count == 0) {
       mbmi->mb_mode_context[ref_frame] = 1;
     } else {
-      // Other candidates available
       mbmi->mb_mode_context[ref_frame] = 2;
     }
-  } else if (candidate_scores[0] >= 32) {
-    if (candidate_scores[1] >= 16) {
-      // Strong primary and strong or moderate secondary candidate
+  // Non zero best, No Split MV cases
+  } else if (split_count == 0) {
+    if (candidate_scores[0] >= 32) {
       mbmi->mb_mode_context[ref_frame] = 3;
     } else {
-      // Strong primary but weak secondary candidate
       mbmi->mb_mode_context[ref_frame] = 4;
     }
+  // Non zero best, some split mv
   } else {
-    // Weak or moderate candidates
-    mbmi->mb_mode_context[ref_frame] = 5;
+    if (candidate_scores[0] >= 32) {
+      mbmi->mb_mode_context[ref_frame] = 5;
+    } else {
+      mbmi->mb_mode_context[ref_frame] = 6;
+    }
   }
 
   // 0,0 is always a valid reference.
-  for (i = 0; i < index; ++i)
+  for (i = 0; i < index; ++i) {
     if (candidate_mvs[i].as_int == 0)
       break;
+  }
   if (i == index) {
     c_refmv.as_int = 0;
     addmv_and_shuffle(candidate_mvs, candidate_scores,
diff --git a/vp9/common/onyxc_int.h b/vp9/common/onyxc_int.h
index d51e292bd..f76c8a008 100644
--- a/vp9/common/onyxc_int.h
+++ b/vp9/common/onyxc_int.h
@@ -42,7 +42,6 @@ void vp9_initialize_common(void);
 #define NUM_YV12_BUFFERS 4
 
 #define COMP_PRED_CONTEXTS   2
-#define INTER_MODE_CONTEXTS 6
 
 typedef struct frame_contexts {
   vp9_prob bmode_prob[VP9_NKF_BINTRAMODES - 1];
@@ -116,7 +115,6 @@ typedef struct frame_contexts {
   int mode_context_a[INTER_MODE_CONTEXTS][4];
   int vp9_mode_contexts[INTER_MODE_CONTEXTS][4];
   int mv_ref_ct[INTER_MODE_CONTEXTS][4][2];
-  int mv_ref_ct_a[INTER_MODE_CONTEXTS][4][2];
 } FRAME_CONTEXT;
 
 typedef enum {
@@ -285,12 +283,6 @@ typedef struct VP9Common {
   FRAME_CONTEXT lfc; /* last frame entropy */
   FRAME_CONTEXT fc;  /* this frame entropy */
 
-  // int mv_ref_ct[6][4][2];
-  // int mv_ref_ct_a[6][4][2];
-  // int mode_context[6][4];
-  // int mode_context_a[6][4];
-  // int vp8_mode_contexts[6][4];
-
   unsigned int current_video_frame;
   int near_boffset[3];
   int version;
diff --git a/vp9/decoder/decodframe.c b/vp9/decoder/decodframe.c
index 275bfb9ca..2642e5a6c 100644
--- a/vp9/decoder/decodframe.c
+++ b/vp9/decoder/decodframe.c
@@ -1315,6 +1315,19 @@ int vp9_decode_frame(VP9D_COMP *pbi) {
   pc->refresh_last_frame = (pc->frame_type == KEY_FRAME)
                            || vp9_read_bit(&header_bc);
 
+  // Read inter mode probability context updates
+  if (pc->frame_type != KEY_FRAME) {
+    int i, j;
+    for (i = 0; i < INTER_MODE_CONTEXTS; i++) {
+      for (j = 0; j < 4; j++) {
+        if (vp9_read(&header_bc, 252)) {
+          pc->fc.vp9_mode_contexts[i][j] =
+            (vp9_prob)vp9_read_literal(&header_bc, 8);
+        }
+      }
+    }
+  }
+
   if (0) {
     FILE *z = fopen("decodestats.stt", "a");
     fprintf(z, "%6d F:%d,G:%d,A:%d,L:%d,Q:%d\n",
@@ -1363,7 +1376,6 @@ int vp9_decode_frame(VP9D_COMP *pbi) {
   vp9_zero(pbi->common.fc.mbsplit_counts);
   vp9_zero(pbi->common.fc.NMVcount);
   vp9_zero(pbi->common.fc.mv_ref_ct);
-  vp9_zero(pbi->common.fc.mv_ref_ct_a);
 #if CONFIG_COMP_INTERINTRA_PRED
   vp9_zero(pbi->common.fc.interintra_counts);
 #endif
diff --git a/vp9/encoder/bitstream.c b/vp9/encoder/bitstream.c
index ccce910c7..6f2771adc 100644
--- a/vp9/encoder/bitstream.c
+++ b/vp9/encoder/bitstream.c
@@ -255,6 +255,42 @@ static void update_refpred_stats(VP9_COMP *cpi) {
   }
 }
 
+// This function is called to update the mode probability context used to encode
+// inter modes. It assumes the branch counts table has already been populated
+// prior to the actual packing of the bitstream (in rd stage or dummy pack)
+//
+// The branch counts table is re-populated during the actual pack stage and in
+// the decoder to facilitate backwards update of the context.
+static update_mode_probs(VP9_COMMON *cm,
+                         int mode_context[INTER_MODE_CONTEXTS][4]) {
+  int i, j;
+  int (*mv_ref_ct)[4][2];
+
+  vpx_memcpy(mode_context, cm->fc.vp9_mode_contexts,
+             sizeof(cm->fc.vp9_mode_contexts));
+
+  mv_ref_ct = cm->fc.mv_ref_ct;
+
+  for (i = 0; i < INTER_MODE_CONTEXTS; i++) {
+    for (j = 0; j < 4; j++) {
+      int new_prob, count, old_cost, new_cost;
+
+      // Work out cost of coding branches with the old and optimal probability
+      old_cost = cost_branch256(mv_ref_ct[i][j], mode_context[i][j]);
+      count = mv_ref_ct[i][j][0] + mv_ref_ct[i][j][1];
+      new_prob = count > 0 ? (255 * mv_ref_ct[i][j][0]) / count : 128;
+      new_prob = (new_prob > 0) ? new_prob : 1;
+      new_cost = cost_branch256(mv_ref_ct[i][j], new_prob);
+
+      // If cost saving is >= 14 bits then update the mode probability.
+      // This is the approximate net cost of updating one probability given
+      // that the no update case ismuch more common than the update case.
+      if (new_cost <= (old_cost - (14 << 8))) {
+        mode_context[i][j] = new_prob;
+      }
+    }
+  }
+}
 static void write_ymode(vp9_writer *bc, int m, const vp9_prob *p) {
   write_token(bc, vp9_ymode_tree, p, vp9_ymode_encodings + m);
 }
@@ -2076,6 +2112,30 @@ void vp9_pack_bitstream(VP9_COMP *cpi, unsigned char *dest,
     active_section = 7;
 #endif
 
+  // If appropriate update the inter mode probability context and code the
+  // changes in the bitstream.
+  if ((pc->frame_type != KEY_FRAME)) {
+    int i, j;
+    int new_context[INTER_MODE_CONTEXTS][4];
+    update_mode_probs(pc, new_context);
+
+    for (i = 0; i < INTER_MODE_CONTEXTS; i++) {
+      for (j = 0; j < 4; j++) {
+        if (new_context[i][j] != pc->fc.vp9_mode_contexts[i][j]) {
+          vp9_write(&header_bc, 1, 252);
+          vp9_write_literal(&header_bc, new_context[i][j], 8);
+
+          // Only update the persistent copy if this is the "real pack"
+          if (!cpi->dummy_packing) {
+            pc->fc.vp9_mode_contexts[i][j] = new_context[i][j];
+          }
+        } else {
+          vp9_write(&header_bc, 0, 252);
+        }
+      }
+    }
+  }
+
   vp9_clear_system_state();  // __asm emms;
 
   vp9_copy(cpi->common.fc.pre_coef_probs, cpi->common.fc.coef_probs);
@@ -2097,7 +2157,6 @@ void vp9_pack_bitstream(VP9_COMP *cpi, unsigned char *dest,
   vp9_zero(cpi->sub_mv_ref_count);
   vp9_zero(cpi->mbsplit_count);
   vp9_zero(cpi->common.fc.mv_ref_ct)
-  vp9_zero(cpi->common.fc.mv_ref_ct_a)
 
   update_coef_probs(cpi, &header_bc);
 
diff --git a/vp9/encoder/encodeframe.c b/vp9/encoder/encodeframe.c
index 094dc5bab..7ac0bd331 100644
--- a/vp9/encoder/encodeframe.c
+++ b/vp9/encoder/encodeframe.c
@@ -1399,7 +1399,6 @@ static void init_encode_frame_mb_context(VP9_COMP *cpi) {
   vp9_zero(cpi->sub_mv_ref_count)
   vp9_zero(cpi->mbsplit_count)
   vp9_zero(cpi->common.fc.mv_ref_ct)
-  vp9_zero(cpi->common.fc.mv_ref_ct_a)
 #if CONFIG_SUPERBLOCKS
   vp9_zero(cpi->sb_ymode_count)
   cpi->sb_count = 0;
diff --git a/vp9/encoder/onyx_int.h b/vp9/encoder/onyx_int.h
index e1ddd45fb..1177451e0 100644
--- a/vp9/encoder/onyx_int.h
+++ b/vp9/encoder/onyx_int.h
@@ -123,10 +123,9 @@ typedef struct {
   vp9_prob interintra_prob;
 #endif
 
-  int mv_ref_ct[6][4][2];
-  int mode_context[6][4];
-  int mv_ref_ct_a[6][4][2];
-  int mode_context_a[6][4];
+  int mv_ref_ct[INTER_MODE_CONTEXTS][4][2];
+  int mode_context[INTER_MODE_CONTEXTS][4];
+  int mode_context_a[INTER_MODE_CONTEXTS][4];
 
 } CODING_CONTEXT;
 
diff --git a/vp9/encoder/ratectrl.c b/vp9/encoder/ratectrl.c
index 097a54d5a..af93d8b42 100644
--- a/vp9/encoder/ratectrl.c
+++ b/vp9/encoder/ratectrl.c
@@ -135,9 +135,7 @@ void vp9_save_coding_context(VP9_COMP *cpi) {
   vp9_copy(cc->nmvcosts,  cpi->mb.nmvcosts);
   vp9_copy(cc->nmvcosts_hp,  cpi->mb.nmvcosts_hp);
 
-  vp9_copy(cc->mv_ref_ct, cm->fc.mv_ref_ct);
   vp9_copy(cc->mode_context, cm->fc.mode_context);
-  vp9_copy(cc->mv_ref_ct_a, cm->fc.mv_ref_ct_a);
   vp9_copy(cc->mode_context_a, cm->fc.mode_context_a);
 
   vp9_copy(cc->ymode_prob, cm->fc.ymode_prob);
@@ -193,9 +191,7 @@ void vp9_restore_coding_context(VP9_COMP *cpi) {
   vp9_copy(cpi->mb.nmvcosts, cc->nmvcosts);
   vp9_copy(cpi->mb.nmvcosts_hp, cc->nmvcosts_hp);
 
-  vp9_copy(cm->fc.mv_ref_ct, cc->mv_ref_ct);
   vp9_copy(cm->fc.mode_context, cc->mode_context);
-  vp9_copy(cm->fc.mv_ref_ct_a, cc->mv_ref_ct_a);
   vp9_copy(cm->fc.mode_context_a, cc->mode_context_a);
 
   vp9_copy(cm->fc.ymode_prob, cc->ymode_prob);