Fix tree to cdf index mapping

This fixes the mis-aligned cdf model derived from tree based
model. It resolves the compression performance regression in
dual filter, intra mode, inter mode, and transform block type
coding, when ec-multisymbol is enabled by default.

With dual filter enabled, the performance regression was 3.6%
loss for lowres. This fix brings the performance gains back to 1%
gains.

Change-Id: I80f5485386045908c152c9c11eeacbc650f1e324

aom_dsp/prob.c

diff --git a/aom_dsp/prob.c b/aom_dsp/prob.c
index 75a0d3f..9fbf0d1 100644
--- a/aom_dsp/prob.c
+++ b/aom_dsp/prob.c
@@ -215,16 +215,25 @@
 /* This code assumes that tree contains as unique leaf nodes the integer values
     0 to len - 1 and produces the forward and inverse mapping tables in ind[]
     and inv[] respectively. */
-void av1_indices_from_tree(int *ind, int *inv, int len,
-                           const aom_tree_index *tree) {
-  int i;
-  int index;
-  for (i = index = 0; i < TREE_SIZE(len); i++) {
-    const aom_tree_index j = tree[i];
-    if (j <= 0) {
-      inv[index] = -j;
-      ind[-j] = index++;
+static void tree_to_index(int *stack_index, int *ind, int *inv,
+                          const aom_tree_index *tree, int value, int index) {
+  value *= 2;
+
+  do {
+    const aom_tree_index content = tree[index];
+    ++index;
+    if (content <= 0) {
+      inv[*stack_index] = -content;
+      ind[-content] = *stack_index;
+      ++(*stack_index);
+    } else {
+      tree_to_index(stack_index, ind, inv, tree, value, content);
     }
-  }
+  } while (++value & 1);
+}
+
+void av1_indices_from_tree(int *ind, int *inv, const aom_tree_index *tree) {
+  int stack_index = 0;
+  tree_to_index(&stack_index, ind, inv, tree, 0, 0);
 }
 #endif

aom_dsp/prob.h

diff --git a/aom_dsp/prob.h b/aom_dsp/prob.h
index a7fc544..9921623 100644
--- a/aom_dsp/prob.h
+++ b/aom_dsp/prob.h
@@ -139,8 +139,7 @@
     }                                                  \
   } while (0)
 
-void av1_indices_from_tree(int *ind, int *inv, int len,
-                           const aom_tree_index *tree);
+void av1_indices_from_tree(int *ind, int *inv, const aom_tree_index *tree);
 #endif
 
 DECLARE_ALIGNED(16, extern const uint8_t, aom_norm[256]);

av1/decoder/decoder.c

diff --git a/av1/decoder/decoder.c b/av1/decoder/decoder.c
index 5a74a3b..1bd9108 100644
--- a/av1/decoder/decoder.c
+++ b/av1/decoder/decoder.c
@@ -51,23 +51,22 @@
 #endif  // CONFIG_EXT_INTER
     init_done = 1;
 #if CONFIG_EC_MULTISYMBOL
-    av1_indices_from_tree(av1_intra_mode_ind, av1_intra_mode_inv, INTRA_MODES,
+    av1_indices_from_tree(av1_intra_mode_ind, av1_intra_mode_inv,
                           av1_intra_mode_tree);
     av1_indices_from_tree(av1_switchable_interp_ind, av1_switchable_interp_inv,
-                          SWITCHABLE_FILTERS, av1_switchable_interp_tree);
+                          av1_switchable_interp_tree);
 #if CONFIG_EXT_TX
     int s;
     for (s = 1; s < EXT_TX_SETS_INTRA; ++s)
       av1_indices_from_tree(av1_ext_tx_intra_ind[s], av1_ext_tx_intra_inv[s],
-                            ext_tx_cnt_intra[s], av1_ext_tx_intra_tree[s]);
+                            av1_ext_tx_intra_tree[s]);
     for (s = 1; s < EXT_TX_SETS_INTER; ++s)
       av1_indices_from_tree(av1_ext_tx_inter_ind[s], av1_ext_tx_inter_inv[s],
-                            ext_tx_cnt_inter[s], av1_ext_tx_inter_tree[s]);
+                            av1_ext_tx_inter_tree[s]);
 #else
-    av1_indices_from_tree(av1_ext_tx_ind, av1_ext_tx_inv, TX_TYPES,
-                          av1_ext_tx_tree);
+    av1_indices_from_tree(av1_ext_tx_ind, av1_ext_tx_inv, av1_ext_tx_tree);
 #endif
-    av1_indices_from_tree(av1_inter_mode_ind, av1_inter_mode_inv, INTER_MODES,
+    av1_indices_from_tree(av1_inter_mode_ind, av1_inter_mode_inv,
                           av1_inter_mode_tree);
 #endif
   }

av1/encoder/bitstream.c

diff --git a/av1/encoder/bitstream.c b/av1/encoder/bitstream.c
index 2d79031..55fdbec 100644
--- a/av1/encoder/bitstream.c
+++ b/av1/encoder/bitstream.c
@@ -192,24 +192,23 @@
       SWITCHABLE_FILTERS are not consecutive, e.g., 0, 1, 2, 3, 4, when doing
       an in-order traversal of the av1_switchable_interp_tree structure. */
   av1_indices_from_tree(av1_switchable_interp_ind, av1_switchable_interp_inv,
-                        SWITCHABLE_FILTERS, av1_switchable_interp_tree);
+                        av1_switchable_interp_tree);
 /* This hack is necessary because the four TX_TYPES are not consecutive,
     e.g., 0, 1, 2, 3, when doing an in-order traversal of the av1_ext_tx_tree
     structure. */
 #if CONFIG_EXT_TX
   for (s = 1; s < EXT_TX_SETS_INTRA; ++s)
     av1_indices_from_tree(av1_ext_tx_intra_ind[s], av1_ext_tx_intra_inv[s],
-                          ext_tx_cnt_intra[s], av1_ext_tx_intra_tree[s]);
+                          av1_ext_tx_intra_tree[s]);
   for (s = 1; s < EXT_TX_SETS_INTER; ++s)
     av1_indices_from_tree(av1_ext_tx_inter_ind[s], av1_ext_tx_inter_inv[s],
-                          ext_tx_cnt_inter[s], av1_ext_tx_inter_tree[s]);
+                          av1_ext_tx_inter_tree[s]);
 #else
-  av1_indices_from_tree(av1_ext_tx_ind, av1_ext_tx_inv, TX_TYPES,
-                        av1_ext_tx_tree);
+  av1_indices_from_tree(av1_ext_tx_ind, av1_ext_tx_inv, av1_ext_tx_tree);
 #endif
-  av1_indices_from_tree(av1_intra_mode_ind, av1_intra_mode_inv, INTRA_MODES,
+  av1_indices_from_tree(av1_intra_mode_ind, av1_intra_mode_inv,
                         av1_intra_mode_tree);
-  av1_indices_from_tree(av1_inter_mode_ind, av1_inter_mode_inv, INTER_MODES,
+  av1_indices_from_tree(av1_inter_mode_ind, av1_inter_mode_inv,
                         av1_inter_mode_tree);
 #endif
 }