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    const void *const *inputs;
  49    const unsigned    *sizes;
  50    unsigned          bytes_left;
  51 };
  52
  53 struct vl_vlc_entry
  54 {
  55    int8_t length;
  56    int8_t value;
  57 };
  58
  59 struct vl_vlc_compressed
  60 {
  61    uint16_t bitcode;
  62    struct vl_vlc_entry entry;
  63 };
  64
  65 /**
  66  * initalize and decompress a lookup table
  67  */
  68 static inline void
  69 vl_vlc_init_table(struct vl_vlc_entry *dst, unsigned dst_size, const struct vl_vlc_compressed *src, unsigned src_size)
  70 {
  71    unsigned i, bits = util_logbase2(dst_size);
  72
  73    assert(dst && dst_size);
  74    assert(src && src_size);
  75
  76    for (i=0;i<dst_size;++i) {
  77       dst[i].length = 0;
  78       dst[i].value = 0;
  79    }
  80
  81    for(; src_size > 0; --src_size, ++src) {
  82       for(i = 0; i < (1u << (bits - src->entry.length)); ++i)
  83          dst[src->bitcode >> (16 - bits) | i] = src->entry;
  84    }
  85 }
  86
  87 /**
  88  * switch over to next input buffer
  89  */
  90 static inline void
  91 vl_vlc_next_input(struct vl_vlc *vlc)
  92 {
  93    unsigned len = vlc->sizes[0];
  94
  95    assert(vlc);
  96    assert(vlc->bytes_left);
  97
  98    if (len < vlc->bytes_left)
  99       vlc->bytes_left -= len;
 100    else {
 101       len = vlc->bytes_left;
 102       vlc->bytes_left = 0;
 103    }
 104
 105    vlc->data = vlc->inputs[0];
 106    vlc->end = vlc->data + len;
 107
 108    ++vlc->inputs;
 109    ++vlc->sizes;
 110 }
 111
 112 /**
 113  * align the data pointer to the next dword
 114  */
 115 static inline void
 116 vl_vlc_align_data_ptr(struct vl_vlc *vlc)
 117 {
 118    /* align the data pointer */
 119    while (vlc->data != vlc->end && pointer_to_uintptr(vlc->data) & 3) {
 120       vlc->buffer |= (uint64_t)*vlc->data << (24 + vlc->invalid_bits);
 121       ++vlc->data;
 122       vlc->invalid_bits -= 8;
 123    }
 124 }
 125
 126 /**
 127  * fill the bit buffer, so that at least 32 bits are valid
 128  */
 129 static inline void
 130 vl_vlc_fillbits(struct vl_vlc *vlc)
 131 {
 132    assert(vlc);
 133
 134    /* as long as the buffer needs to be filled */
 135    while (vlc->invalid_bits > 0) {
 136       unsigned bytes_left = vlc->end - vlc->data;
 137
 138       /* if this input is depleted */
 139       if (bytes_left == 0) {
 140
 141          if (vlc->bytes_left) {
 142             /* go on to next input */
 143             vl_vlc_next_input(vlc);
 144             vl_vlc_align_data_ptr(vlc);
 145          } else
 146             /* or give up since we don't have anymore inputs */
 147             return;
 148
 149       } else if (bytes_left >= 4) {
 150
 151          /* enough bytes in buffer, read in a whole dword */
 152          uint64_t value = *(const uint32_t*)vlc->data;
 153
 154 #if !PIPE_ARCH_BIG_ENDIAN
 155          value = util_bswap32(value);
 156 #endif
 157
 158          vlc->buffer |= value << vlc->invalid_bits;
 159          vlc->data += 4;
 160          vlc->invalid_bits -= 32;
 161
 162          /* buffer is now definitely filled up avoid the loop test */
 163          break;
 164
 165       } else while (vlc->data < vlc->end) {
 166
 167          /* not enough bytes left in buffer, read single bytes */
 168          vlc->buffer |= (uint64_t)*vlc->data << (24 + vlc->invalid_bits);
 169          ++vlc->data;
 170          vlc->invalid_bits -= 8;
 171       }
 172    }
 173 }
 174
 175 /**
 176  * initialize vlc structure and start reading from first input buffer
 177  */
 178 static inline void
 179 vl_vlc_init(struct vl_vlc *vlc, unsigned num_inputs,
 180             const void *const *inputs, const unsigned *sizes)
 181 {
 182    unsigned i;
 183
 184    assert(vlc);
 185    assert(num_inputs);
 186
 187    vlc->buffer = 0;
 188    vlc->invalid_bits = 32;
 189    vlc->inputs = inputs;
 190    vlc->sizes = sizes;
 191    vlc->bytes_left = 0;
 192
 193    for (i = 0; i < num_inputs; ++i)
 194       vlc->bytes_left += sizes[i];
 195
 196    if (vlc->bytes_left) {
 197       vl_vlc_next_input(vlc);
 198       vl_vlc_align_data_ptr(vlc);
 199       vl_vlc_fillbits(vlc);
 200    }
 201 }
 202
 203 /**
 204  * number of bits still valid in bit buffer
 205  */
 206 static inline unsigned
 207 vl_vlc_valid_bits(struct vl_vlc *vlc)
 208 {
 209    return 32 - vlc->invalid_bits;
 210 }
 211
 212 /**
 213  * number of bits left over all inbut buffers
 214  */
 215 static inline unsigned
 216 vl_vlc_bits_left(struct vl_vlc *vlc)
 217 {
 218    signed bytes_left = vlc->end - vlc->data;
 219    bytes_left += vlc->bytes_left;
 220    return bytes_left * 8 + vl_vlc_valid_bits(vlc);
 221 }
 222
 223 /**
 224  * get num_bits from bit buffer without removing them
 225  */
 226 static inline unsigned
 227 vl_vlc_peekbits(struct vl_vlc *vlc, unsigned num_bits)
 228 {
 229    assert(vl_vlc_valid_bits(vlc) >= num_bits || vlc->data >= vlc->end);
 230    return vlc->buffer >> (64 - num_bits);
 231 }
 232
 233 /**
 234  * remove num_bits from bit buffer
 235  */
 236 static inline void
 237 vl_vlc_eatbits(struct vl_vlc *vlc, unsigned num_bits)
 238 {
 239    assert(vl_vlc_valid_bits(vlc) >= num_bits);
 240
 241    vlc->buffer <<= num_bits;
 242    vlc->invalid_bits += num_bits;
 243 }
 244
 245 /**
 246  * get num_bits from bit buffer with removing them
 247  */
 248 static inline unsigned
 249 vl_vlc_get_uimsbf(struct vl_vlc *vlc, unsigned num_bits)
 250 {
 251    unsigned value;
 252
 253    assert(vl_vlc_valid_bits(vlc) >= num_bits);
 254
 255    value = vlc->buffer >> (64 - num_bits);
 256    vl_vlc_eatbits(vlc, num_bits);
 257
 258    return value;
 259 }
 260
 261 /**
 262  * treat num_bits as signed value and remove them from bit buffer
 263  */
 264 static inline signed
 265 vl_vlc_get_simsbf(struct vl_vlc *vlc, unsigned num_bits)
 266 {
 267    signed value;
 268
 269    assert(vl_vlc_valid_bits(vlc) >= num_bits);
 270
 271    value = ((int64_t)vlc->buffer) >> (64 - num_bits);
 272    vl_vlc_eatbits(vlc, num_bits);
 273
 274    return value;
 275 }
 276
 277 /**
 278  * lookup a value and length in a decompressed table
 279  */
 280 static inline int8_t
 281 vl_vlc_get_vlclbf(struct vl_vlc *vlc, const struct vl_vlc_entry *tbl, unsigned num_bits)
 282 {
 283    tbl += vl_vlc_peekbits(vlc, num_bits);
 284    vl_vlc_eatbits(vlc, tbl->length);
 285    return tbl->value;
 286 }
 287
 288 /**
 289  * fast forward search for a specific byte value
 290  */
 291 static inline boolean
 292 vl_vlc_search_byte(struct vl_vlc *vlc, unsigned num_bits, uint8_t value)
 293 {
 294    /* make sure we are on a byte boundary */
 295    assert((vl_vlc_valid_bits(vlc) % 8) == 0);
 296    assert(num_bits == ~0u || (num_bits % 8) == 0);
 297
 298    /* deplete the bit buffer */
 299    while (vl_vlc_valid_bits(vlc) > 0) {
 300
 301       if (vl_vlc_peekbits(vlc, 8) == value) {
 302          vl_vlc_fillbits(vlc);
 303          return TRUE;
 304       }
 305
 306       vl_vlc_eatbits(vlc, 8);
 307
 308       if (num_bits != ~0u) {
 309          num_bits -= 8;
 310          if (num_bits == 0)
 311             return FALSE;
 312       }
 313    }
 314
 315    /* deplete the byte buffers */
 316    while (1) {
 317
 318       /* if this input is depleted */
 319       if (vlc->data == vlc->end) {
 320          if (vlc->bytes_left)
 321             /* go on to next input */
 322             vl_vlc_next_input(vlc);
 323          else
 324             /* or give up since we don't have anymore inputs */
 325             return FALSE;
 326       }
 327
 328       if (*vlc->data == value) {
 329          vl_vlc_align_data_ptr(vlc);
 330          vl_vlc_fillbits(vlc);
 331          return TRUE;
 332       }
 333
 334       ++vlc->data;
 335       if (num_bits != ~0u) {
 336          num_bits -= 8;
 337          if (num_bits == 0) {
 338             vl_vlc_align_data_ptr(vlc);
 339             return FALSE;
 340          }
 341       }
 342    }
 343 }
 344
 345 /**
 346  * remove num_bits bits starting at pos from the bitbuffer
 347  */
 348 static inline void
 349 vl_vlc_removebits(struct vl_vlc *vlc, unsigned pos, unsigned num_bits)
 350 {
 351    uint64_t lo = (vlc->buffer & (~0UL >> (pos + num_bits))) << num_bits;
 352    uint64_t hi = (vlc->buffer & (~0UL << (64 - pos)));
 353    vlc->buffer = lo | hi;
 354    vlc->invalid_bits += num_bits;
 355 }
 356
 357 /**
 358  * limit the number of bits left for fetching
 359  */
 360 static inline void
 361 vl_vlc_limit(struct vl_vlc *vlc, unsigned bits_left)
 362 {
 363    assert(bits_left <= vl_vlc_bits_left(vlc));
 364
 365    vl_vlc_fillbits(vlc);
 366    if (bits_left < vl_vlc_valid_bits(vlc)) {
 367       vlc->invalid_bits = 32 - bits_left;
 368       vlc->buffer &= ~0L << (vlc->invalid_bits + 32);
 369       vlc->end = vlc->data;
 370       vlc->bytes_left = 0;
 371    } else {
 372       assert((bits_left - vl_vlc_valid_bits(vlc)) % 8 == 0);
 373       vlc->bytes_left = (bits_left - vl_vlc_valid_bits(vlc)) / 8;
 374       if (vlc->bytes_left < (vlc->end - vlc->data)) {
 375          vlc->end = vlc->data + vlc->bytes_left;
 376          vlc->bytes_left = 0;
 377       } else
 378          vlc->bytes_left -= vlc->end - vlc->data;
 379    }
 380 }
 381
 382 #endif /* vl_vlc_h */