[Spice-devel] [PATCH spice-gtk 3/4] quic: precompute golomb codes

[Marc-André Lureau]

From: Marc-André Lureau <marcandre.lureau at gmail.com>

We can avoid repetitive computation by using two precomputed array, of
4k each.
---
 common/quic.c             | 25 ++++++++++++++++++++++++-
 common/quic_family_tmpl.c | 22 +++++++++-------------
 2 files changed, 33 insertions(+), 14 deletions(-)

diff --git a/common/quic.c b/common/quic.c
index 3e7c802..c9c3624 100644
--- a/common/quic.c
+++ b/common/quic.c
@@ -75,6 +75,9 @@ typedef struct QuicFamily {
     unsigned int notGRsuffixlen[MAXNUMCODES];    /* indexed by code number, contains suffix
                                                     length of the not-GR codeword */
 
+    unsigned int golomb_code_len[256][MAXNUMCODES];
+    unsigned int golomb_code[256][MAXNUMCODES];
+
     /* array for translating distribution U to L for depths up to 8 bpp,
     initialized by decorelateinit() */
     BYTE xlatU2L[256];
@@ -360,9 +363,22 @@ static void corelate_init(QuicFamily *family, int bpc)
     }
 }
 
+static void golomb_coding_slow(QuicFamily *family, const BYTE n, const unsigned int l,
+                               unsigned int * const codeword,
+                               unsigned int * const codewordlen)
+{
+    if (n < family->nGRcodewords[l]) {
+        (*codeword) = bitat[l] | (n & bppmask[l]);
+        (*codewordlen) = (n >> l) + l + 1;
+    } else {
+        (*codeword) = n - family->nGRcodewords[l];
+        (*codewordlen) = family->notGRcwlen[l];
+    }
+}
+
 static void family_init(QuicFamily *family, int bpc, int limit)
 {
-    int l;
+    int l, b;
 
     for (l = 0; l < bpc; l++) { /* fill arrays indexed by code number */
         int altprefixlen, altcodewords;
@@ -378,6 +394,13 @@ static void family_init(QuicFamily *family, int bpc, int limit)
         family->notGRcwlen[l] = altprefixlen + ceil_log_2(altcodewords);
         family->notGRprefixmask[l] = bppmask[32 - altprefixlen]; /* needed for decoding only */
         family->notGRsuffixlen[l] = ceil_log_2(altcodewords); /* needed for decoding only */
+
+        for (b = 0; b < 256; b++) {
+            unsigned int code, len;
+            golomb_coding_slow(family, b, l, &code, &len);
+            family->golomb_code[b][l] = code;
+            family->golomb_code_len[b][l] = len;
+        }
     }
 
     decorelate_init(family, bpc);
diff --git a/common/quic_family_tmpl.c b/common/quic_family_tmpl.c
index 287ff6d..12ef62f 100644
--- a/common/quic_family_tmpl.c
+++ b/common/quic_family_tmpl.c
@@ -34,26 +34,21 @@
 #define BPC 5
 #endif
 
+static inline unsigned int FNAME(golomb_code)(const BYTE n, const unsigned int l)
+{
+    return VNAME(family).golomb_code[n][l];
+}
 
-static unsigned int FNAME(golomb_code_len)(const BYTE n, const unsigned int l)
+static inline unsigned int FNAME(golomb_code_len)(const BYTE n, const unsigned int l)
 {
-    if (n < VNAME(family).nGRcodewords[l]) {
-        return (n >> l) + 1 + l;
-    } else {
-        return VNAME(family).notGRcwlen[l];
-    }
+    return VNAME(family).golomb_code_len[n][l];
 }
 
 static void FNAME(golomb_coding)(const BYTE n, const unsigned int l, unsigned int * const codeword,
                                  unsigned int * const codewordlen)
 {
-    if (n < VNAME(family).nGRcodewords[l]) {
-        (*codeword) = bitat[l] | (n & bppmask[l]);
-        (*codewordlen) = (n >> l) + l + 1;
-    } else {
-        (*codeword) = n - VNAME(family).nGRcodewords[l];
-        (*codewordlen) = VNAME(family).notGRcwlen[l];
-    }
+    *codeword = FNAME(golomb_code)(n, l);
+    *codewordlen = FNAME(golomb_code_len)(n, l);
 }
 
 static unsigned int FNAME(golomb_decoding)(const unsigned int l, const unsigned int bits,
@@ -76,6 +71,7 @@ static unsigned int FNAME(golomb_decoding)(const unsigned int l, const unsigned
 static void FNAME(update_model)(CommonState *state, s_bucket * const bucket,
                                 const BYTE curval)
 {
+    spice_static_assert(BPC >= 1);
     const unsigned int bpp = BPC;
     COUNTER * const pcounters = bucket->pcounters;
     unsigned int i;
-- 
1.8.3.1