Differential encoding of probability updates

Adds differential encoding of prob updates using a subexponential
code centered around the previous probability value.
Also searches for the most cost-effective update, and breaks
up the coefficient updates into smaller groups.

Small gain on Derf: 0.2%

Change-Id: Ie0071e3dc113e3d0d7ab95b6442bb07a89970030

1 files changed, 96 insertions, 0 deletions

diff --git a/vp8/encoder/boolhuff.c b/vp8/encoder/boolhuff.c
index 08ae66b8d..e1698ede3 100644
--- a/vp8/encoder/boolhuff.c
+++ b/vp8/encoder/boolhuff.c
@@ -68,3 +68,99 @@ void vp8_encode_value(BOOL_CODER *br, int data, int bits)
         vp8_encode_bool(br, (1 & (data >> bit)), 0x80);
 
 }
+
+#if CONFIG_NEWUPDATE
+int recenter_nonneg(int v, int m)
+{
+    if (v > (m<<1)) return v;
+    else if (v >= m) return ((v-m)<<1);
+    else return ((m-v)<<1)-1;
+}
+
+static int get_unsigned_bits(unsigned num_values)
+{
+    int cat=0;
+    if ((num_values--)<=1) return 0;
+    while (num_values>0)
+    {
+        cat++;
+        num_values>>=1;
+    }
+    return cat;
+}
+
+void vp8_encode_uniform(BOOL_CODER *br, int v, int n)
+{
+    int l = get_unsigned_bits(n);
+    if (l == 0) return;
+    int m = (1<<l)-n;
+    if (v<m)
+        vp8_encode_value(br, v, l-1);
+    else
+    {
+        vp8_encode_value(br, m+((v-m)>>1), l-1);
+        vp8_encode_value(br, (v-m)&1, 1);
+    }
+}
+
+int vp8_count_uniform(int v, int n)
+{
+    int l = get_unsigned_bits(n);
+    if (l == 0) return 0;
+    int m = (1<<l)-n;
+    if (v<m)
+        return l-1;
+    else
+        return l;
+}
+
+void vp8_encode_term_subexp(BOOL_CODER *br, int word, int k, int num_syms)
+{
+    int i = 0;
+    int mk = 0;
+    while (1) {
+        int b = (i?k+i-1:k);
+        int a = (1<<b);
+        if (num_syms<=mk+3*a) {
+            vp8_encode_uniform(br, word-mk, num_syms-mk);
+            break;
+        } else {
+            int t = (word>=mk+a);
+            vp8_encode_value(br, t, 1);
+            if (t) {
+                i=i+1;
+                mk+=a;
+            } else {
+                vp8_encode_value(br, word-mk, b);
+                break;
+            }
+        }
+    }
+}
+
+int vp8_count_term_subexp(int word, int k, int num_syms)
+{
+    int count = 0;
+    int i = 0;
+    int mk = 0;
+    while (1) {
+        int b = (i?k+i-1:k);
+        int a = (1<<b);
+        if (num_syms<=mk+3*a) {
+            count += vp8_count_uniform(num_syms-mk, word-mk);
+            break;
+        } else {
+            int t = (word>=mk+a);
+            count++;
+            if (t) {
+                i=i+1;
+                mk+=a;
+            } else {
+                count += b;
+                break;
+            }
+        }
+    }
+    return count;
+}
+#endif