1 /************************************************************************** 2 * 3 * Copyright 2011 Christian Knig. 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 #ifndef 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 */ 383
