1 files changed, 138 insertions, 0 deletions
diff --git a/src/gallium/auxiliary/vl/vp8/treereader_common.c b/src/gallium/auxiliary/vl/vp8/treereader_common.c
new file mode 100644
index 0000000000..defdd12b05
--- /dev/null
+++ b/src/gallium/auxiliary/vl/vp8/treereader_common.c
@@ -0,0 +1,138 @@
+/*
+ *  Copyright (c) 2010 The WebM project authors. All Rights Reserved.
+ *
+ *  Use of this source code is governed by a BSD-style license
+ *  that can be found in the LICENSE file in the root of the source
+ *  tree. An additional intellectual property rights grant can be found
+ *  in the file PATENTS.  All contributing project authors may
+ *  be found in the AUTHORS file in the root of the source tree.
+ */
+
+
+#if ENABLE_DEBUG
+#include <assert.h>
+#endif
+#include <stdio.h>
+
+#include "treereader_common.h"
+
+static void tree2tok(struct vp8_token_struct *const p, vp8_tree t, int i, int v, int L)
+{
+    v += v;
+    ++L;
+
+    do
+    {
+        const vp8_tree_index j = t[i++];
+
+        if (j <= 0)
+        {
+            p[-j].value = v;
+            p[-j].Len = L;
+        }
+        else
+            tree2tok(p, t, j, v, L);
+    }
+    while (++v & 1);
+}
+
+/**
+ * Construct encoding array from tree.
+ */
+void vp8_tokens_from_tree(struct vp8_token_struct *p, vp8_tree t)
+{
+    tree2tok(p, t, 0, 0, 0);
+}
+
+void vp8_tokens_from_tree_offset(struct vp8_token_struct *p, vp8_tree t, int offset)
+{
+    tree2tok(p - offset, t, 0, 0, 0);
+}
+
+static void branch_counts(int n, /* n = size of alphabet */
+                          vp8_token tok[ /* n */ ],
+                          vp8_tree tree,
+                          unsigned int branch_ct[ /* n-1 */ ] [2],
+                          const unsigned int num_events[ /* n */ ])
+{
+    const int tree_len = n - 1;
+    int t = 0;
+
+#if ENABLE_DEBUG
+    assert(tree_len);
+#endif
+
+    do
+    {
+        branch_ct[t][0] = branch_ct[t][1] = 0;
+    }
+    while (++t < tree_len);
+
+    t = 0;
+
+    do
+    {
+        int L = tok[t].Len;
+        const int enc = tok[t].value;
+        const unsigned int ct = num_events[t];
+
+        vp8_tree_index i = 0;
+
+        do
+        {
+            const int b = (enc >> --L) & 1;
+            const int j = i >> 1;
+#if ENABLE_DEBUG
+            assert(j < tree_len  &&  0 <= L);
+#endif
+            branch_ct [j] [b] += ct;
+            i = tree[ i + b];
+        }
+        while (i > 0);
+
+#if ENABLE_DEBUG
+        assert(!L);
+#endif
+    }
+    while (++t < n);
+}
+
+/**
+ * Convert array of token occurrence counts into a table of probabilities
+ * for the associated binary encoding tree.  Also writes count of branches
+ * taken for each node on the tree; this facilitiates decisions as to
+ * probability updates.
+ */
+void vp8_tree_probs_from_distribution(int n, /* n = size of alphabet */
+                                      vp8_token tok[ /* n */ ],
+                                      vp8_tree tree,
+                                      vp8_prob probs[ /* n-1 */ ],
+                                      unsigned int branch_ct[ /* n-1 */ ] [2],
+                                      const unsigned int num_events[ /* n */ ],
+                                      unsigned int Pfac,
+                                      int rd)
+{
+    const int tree_len = n - 1;
+    int t = 0;
+
+    branch_counts(n, tok, tree, branch_ct, num_events);
+
+    do
+    {
+        const unsigned int *const c = branch_ct[t];
+        const unsigned int tot = c[0] + c[1];
+
+#if ENABLE_DEBUG
+        assert(tot < (1 << 24)); /* no overflow below */
+#endif
+
+        if (tot)
+        {
+            const unsigned int p = ((c[0] * Pfac) + (rd ? tot >> 1 : 0)) / tot;
+            probs[t] = p < 256 ? (p ? p : 1) : 255; /* agree w/old version for now */
+        }
+        else
+            probs[t] = vp8_prob_half;
+    }
+    while (++t < tree_len);
+}