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

[Marc-André Lureau]

On Wed, Sep 11, 2013 at 11:12 AM, Christophe Fergeau
<cfergeau at redhat.com> wrote:
> ACK
>
> On Tue, Sep 10, 2013 at 04:43:38PM +0200, Marc-André Lureau wrote:
>> From: Marc-André Lureau <marcandre.lureau at gmail.com>
>>
>> We can avoid repetitive computation by using two precomputed array, of
>> 4k each.

hmm, I think it's 2k each actually, I'll verify and update commit msg

>> ---
>>  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
>>
>> _______________________________________________
>> Spice-devel mailing list
>> Spice-devel at lists.freedesktop.org
>> http://lists.freedesktop.org/mailman/listinfo/spice-devel



-- 
Marc-André Lureau