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

[Christophe Fergeau]

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.
> ---
>  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
-------------- next part --------------
A non-text attachment was scrubbed...
Name: not available
Type: application/pgp-signature
Size: 198 bytes
Desc: not available
URL: <http://lists.freedesktop.org/archives/spice-devel/attachments/20130911/595199a1/attachment.pgp>