src/gallium/auxiliary/vl/vl_vlc.h

   1 /**************************************************************************
   2  *
   3  * Copyright 2011 Christian König.
   4  * All Rights Reserved.
   5  *
   6  * Permission is hereby granted, free of charge, to any person obtaining a
   7  * copy of this software and associated documentation files (the
   8  * "Software"), to deal in the Software without restriction, including
   9  * without limitation the rights to use, copy, modify, merge, publish,
  10  * distribute, sub license, and/or sell copies of the Software, and to
  11  * permit persons to whom the Software is furnished to do so, subject to
  12  * the following conditions:
  13  *
  14  * The above copyright notice and this permission notice (including the
  15  * next paragraph) shall be included in all copies or substantial portions
  16  * of the Software.
  17  *
  18  * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS
  19  * OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
  20  * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NON-INFRINGEMENT.
  21  * IN NO EVENT SHALL VMWARE AND/OR ITS SUPPLIERS BE LIABLE FOR
  22  * ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT,
  23  * TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE
  24  * SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
  25  *
  26  **************************************************************************/
  27
  28 /*
  29  * Functions for fast bitwise access to multiple probably unaligned input buffers
  30  */
  31
  32 #ifndef vl_vlc_h
  33 #define vl_vlc_h
  34
  35 #include "pipe/p_compiler.h"
  36
  37 #include "util/u_math.h"
  38 #include "util/u_pointer.h"
  39 #include "util/u_debug.h"
  40
  41 struct vl_vlc
  42 {
  43    uint64_t buffer;
  44    signed invalid_bits;
  45    const uint8_t *data;
  46    const uint8_t *end;
  47
  48    unsigned          num_inputs;
  49    const void *const *inputs;
  50    const unsigned    *sizes;
  51    unsigned          bytes_left;
  52 };
  53
  54 struct vl_vlc_entry
  55 {
  56    int8_t length;
  57    int8_t value;
  58 };
  59
  60 struct vl_vlc_compressed
  61 {
  62    uint16_t bitcode;
  63    struct vl_vlc_entry entry;
  64 };
  65
  66 /**
  67  * initalize and decompress a lookup table
  68  */
  69 static INLINE void
  70 vl_vlc_init_table(struct vl_vlc_entry *dst, unsigned dst_size, const struct vl_vlc_compressed *src, unsigned src_size)
  71 {
  72    unsigned i, bits = util_logbase2(dst_size);
  73
  74    assert(dst && dst_size);
  75    assert(src && src_size);
  76
  77    for (i=0;i<dst_size;++i) {
  78       dst[i].length = 0;
  79       dst[i].value = 0;
  80    }
  81
  82    for(; src_size > 0; --src_size, ++src) {
  83       for(i=0; i<(1 << (bits - src->entry.length)); ++i)
  84          dst[src->bitcode >> (16 - bits) | i] = src->entry;
  85    }
  86 }
  87
  88 /**
  89  * switch over to next input buffer
  90  */
  91 static INLINE void
  92 vl_vlc_next_input(struct vl_vlc *vlc)
  93 {
  94    unsigned len = vlc->sizes[0];
  95
  96    assert(vlc);
  97    assert(vlc->num_inputs);
  98
  99    vlc->bytes_left -= len;
 100
 101    vlc->data = vlc->inputs[0];
 102    vlc->end = vlc->data + len;
 103
 104    --vlc->num_inputs;
 105    ++vlc->inputs;
 106    ++vlc->sizes;
 107 }
 108
 109 /**
 110  * align the data pointer to the next dword
 111  */
 112 static INLINE void
 113 vl_vlc_align_data_ptr(struct vl_vlc *vlc)
 114 {
 115    /* align the data pointer */
 116    while (vlc->data != vlc->end && pointer_to_uintptr(vlc->data) & 3) {
 117       vlc->buffer |= (uint64_t)*vlc->data << (24 + vlc->invalid_bits);
 118       ++vlc->data;
 119       vlc->invalid_bits -= 8;
 120    }
 121 }
 122
 123 /**
 124  * fill the bit buffer, so that at least 32 bits are valid
 125  */
 126 static INLINE void
 127 vl_vlc_fillbits(struct vl_vlc *vlc)
 128 {
 129    assert(vlc);
 130
 131    /* as long as the buffer needs to be filled */
 132    while (vlc->invalid_bits > 0) {
 133       unsigned bytes_left = vlc->end - vlc->data;
 134
 135       /* if this input is depleted */
 136       if (bytes_left == 0) {
 137
 138          if (vlc->num_inputs)
 139             /* go on to next input */
 140             vl_vlc_next_input(vlc);
 141          else
 142             /* or give up since we don't have anymore inputs */
 143             return;
 144
 145       } else if (bytes_left >= 4) {
 146
 147          /* enough bytes in buffer, read in a whole dword */
 148          uint64_t value = *(const uint32_t*)vlc->data;
 149
 150 #ifndef PIPE_ARCH_BIG_ENDIAN
 151          value = util_bswap32(value);
 152 #endif
 153
 154          vlc->buffer |= value << vlc->invalid_bits;
 155          vlc->data += 4;
 156          vlc->invalid_bits -= 32;
 157
 158          /* buffer is now definitely filled up avoid the loop test */
 159          break;
 160
 161       } else while (vlc->data < vlc->end) {
 162
 163          /* not enough bytes left in buffer, read single bytes */
 164          vlc->buffer |= (uint64_t)*vlc->data << (24 + vlc->invalid_bits);
 165          ++vlc->data;
 166          vlc->invalid_bits -= 8;
 167       }
 168    }
 169 }
 170
 171 /**
 172  * initialize vlc structure and start reading from first input buffer
 173  */
 174 static INLINE void
 175 vl_vlc_init(struct vl_vlc *vlc, unsigned num_inputs,
 176             const void *const *inputs, const unsigned *sizes)
 177 {
 178    unsigned i;
 179
 180    assert(vlc);
 181    assert(num_inputs);
 182
 183    vlc->buffer = 0;
 184    vlc->invalid_bits = 32;
 185    vlc->num_inputs = num_inputs;
 186    vlc->inputs = inputs;
 187    vlc->sizes = sizes;
 188    vlc->bytes_left = 0;
 189
 190    for (i = 0; i < num_inputs; ++i)
 191       vlc->bytes_left += sizes[i];
 192
 193    vl_vlc_next_input(vlc);
 194    vl_vlc_align_data_ptr(vlc);
 195    vl_vlc_fillbits(vlc);
 196    vl_vlc_fillbits(vlc);
 197 }
 198
 199 /**
 200  * number of bits still valid in bit buffer
 201  */
 202 static INLINE unsigned
 203 vl_vlc_valid_bits(struct vl_vlc *vlc)
 204 {
 205    return 32 - vlc->invalid_bits;
 206 }
 207
 208 /**
 209  * number of bits left over all inbut buffers
 210  */
 211 static INLINE unsigned
 212 vl_vlc_bits_left(struct vl_vlc *vlc)
 213 {
 214    signed bytes_left = vlc->end - vlc->data;
 215    bytes_left += vlc->bytes_left;
 216    return bytes_left * 8 + vl_vlc_valid_bits(vlc);
 217 }
 218
 219 /**
 220  * get num_bits from bit buffer without removing them
 221  */
 222 static INLINE unsigned
 223 vl_vlc_peekbits(struct vl_vlc *vlc, unsigned num_bits)
 224 {
 225    assert(vl_vlc_valid_bits(vlc) >= num_bits || vlc->data >= vlc->end);
 226    return vlc->buffer >> (64 - num_bits);
 227 }
 228
 229 /**
 230  * remove num_bits from bit buffer
 231  */
 232 static INLINE void
 233 vl_vlc_eatbits(struct vl_vlc *vlc, unsigned num_bits)
 234 {
 235    assert(vl_vlc_valid_bits(vlc) >= num_bits);
 236
 237    vlc->buffer <<= num_bits;
 238    vlc->invalid_bits += num_bits;
 239 }
 240
 241 /**
 242  * get num_bits from bit buffer with removing them
 243  */
 244 static INLINE unsigned
 245 vl_vlc_get_uimsbf(struct vl_vlc *vlc, unsigned num_bits)
 246 {
 247    unsigned value;
 248
 249    assert(vl_vlc_valid_bits(vlc) >= num_bits);
 250
 251    value = vlc->buffer >> (64 - num_bits);
 252    vl_vlc_eatbits(vlc, num_bits);
 253
 254    return value;
 255 }
 256
 257 /**
 258  * treat num_bits as signed value and remove them from bit buffer
 259  */
 260 static INLINE signed
 261 vl_vlc_get_simsbf(struct vl_vlc *vlc, unsigned num_bits)
 262 {
 263    signed value;
 264
 265    assert(vl_vlc_valid_bits(vlc) >= num_bits);
 266
 267    value = ((int64_t)vlc->buffer) >> (64 - num_bits);
 268    vl_vlc_eatbits(vlc, num_bits);
 269
 270    return value;
 271 }
 272
 273 /**
 274  * lookup a value and length in a decompressed table
 275  */
 276 static INLINE int8_t
 277 vl_vlc_get_vlclbf(struct vl_vlc *vlc, const struct vl_vlc_entry *tbl, unsigned num_bits)
 278 {
 279    tbl += vl_vlc_peekbits(vlc, num_bits);
 280    vl_vlc_eatbits(vlc, tbl->length);
 281    return tbl->value;
 282 }
 283
 284 /**
 285  * fast forward search for a specific byte value
 286  */
 287 static INLINE boolean
 288 vl_vlc_search_byte(struct vl_vlc *vlc, unsigned num_bits, uint8_t value)
 289 {
 290    /* make sure we are on a byte boundary */
 291    assert((vl_vlc_valid_bits(vlc) % 8) == 0);
 292    assert(num_bits == ~0 || (num_bits % 8) == 0);
 293
 294    /* deplete the bit buffer */
 295    while (vl_vlc_valid_bits(vlc) > 0) {
 296
 297       if (vl_vlc_peekbits(vlc, 8) == value) {
 298          vl_vlc_fillbits(vlc);
 299          return TRUE;
 300       }
 301
 302       vl_vlc_eatbits(vlc, 8);
 303
 304       if (num_bits != ~0) {
 305          num_bits -= 8;
 306          if (num_bits == 0)
 307             return FALSE;
 308       }
 309    }
 310
 311    /* deplete the byte buffers */
 312    while (1) {
 313
 314       /* if this input is depleted */
 315       if (vlc->data == vlc->end) {
 316          if (vlc->num_inputs)
 317             /* go on to next input */
 318             vl_vlc_next_input(vlc);
 319          else
 320             /* or give up since we don't have anymore inputs */
 321             return FALSE;
 322       }
 323
 324       if (*vlc->data == value) {
 325          vl_vlc_align_data_ptr(vlc);
 326          vl_vlc_fillbits(vlc);
 327          return TRUE;
 328       }
 329
 330       ++vlc->data;
 331       if (num_bits != ~0) {
 332          num_bits -= 8;
 333          if (num_bits == 0) {
 334             vl_vlc_align_data_ptr(vlc);
 335             return FALSE;
 336          }
 337       }
 338    }
 339 }
 340
 341 #endif /* vl_vlc_h */