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 TUNGSTEN GRAPHICS 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 const uint8_t* data = vlc->inputs[0]; 95 unsigned len = vlc->sizes[0]; 96 97 assert(vlc); 98 assert(vlc->num_inputs); 99 100 vlc->bytes_left -= len; 101 102 /* align the data pointer */ 103 while (len && pointer_to_uintptr(data) & 3) { 104 vlc->buffer |= (uint64_t)*data << (24 + vlc->invalid_bits); 105 ++data; 106 --len; 107 vlc->invalid_bits -= 8; 108 } 109 vlc->data = data; 110 vlc->end = data + len; 111 112 --vlc->num_inputs; 113 ++vlc->inputs; 114 ++vlc->sizes; 115 } 116 117 /** 118 * fill the bit buffer, so that at least 32 bits are valid 119 */ 120 static INLINE void 121 vl_vlc_fillbits(struct vl_vlc *vlc) 122 { 123 assert(vlc); 124 125 /* as long as the buffer needs to be filled */ 126 while (vlc->invalid_bits > 0) { 127 unsigned bytes_left = vlc->end - vlc->data; 128 129 /* if this input is depleted */ 130 if (bytes_left == 0) { 131 132 if (vlc->num_inputs) 133 /* go on to next input */ 134 vl_vlc_next_input(vlc); 135 else 136 /* or give up since we don't have anymore inputs */ 137 return; 138 139 } else if (bytes_left >= 4) { 140 141 /* enough bytes in buffer, read in a whole dword */ 142 uint64_t value = *(const uint32_t*)vlc->data; 143 144 #ifndef PIPE_ARCH_BIG_ENDIAN 145 value = util_bswap32(value); 146 #endif 147 148 vlc->buffer |= value << vlc->invalid_bits; 149 vlc->data += 4; 150 vlc->invalid_bits -= 32; 151 152 /* buffer is now definitely filled up avoid the loop test */ 153 break; 154 155 } else while (vlc->data < vlc->end) { 156 157 /* not enough bytes left in buffer, read single bytes */ 158 vlc->buffer |= (uint64_t)*vlc->data << (24 + vlc->invalid_bits); 159 ++vlc->data; 160 vlc->invalid_bits -= 8; 161 } 162 } 163 } 164 165 /** 166 * initialize vlc structure and start reading from first input buffer 167 */ 168 static INLINE void 169 vl_vlc_init(struct vl_vlc *vlc, unsigned num_inputs, 170 const void *const *inputs, const unsigned *sizes) 171 { 172 unsigned i; 173 174 assert(vlc); 175 assert(num_inputs); 176 177 vlc->buffer = 0; 178 vlc->invalid_bits = 32; 179 vlc->num_inputs = num_inputs; 180 vlc->inputs = inputs; 181 vlc->sizes = sizes; 182 vlc->bytes_left = 0; 183 184 for (i = 0; i < num_inputs; ++i) 185 vlc->bytes_left += sizes[i]; 186 187 vl_vlc_next_input(vlc); 188 vl_vlc_fillbits(vlc); 189 vl_vlc_fillbits(vlc); 190 } 191 192 /** 193 * number of bits still valid in bit buffer 194 */ 195 static INLINE unsigned 196 vl_vlc_valid_bits(struct vl_vlc *vlc) 197 { 198 return 32 - vlc->invalid_bits; 199 } 200 201 /** 202 * number of bits left over all inbut buffers 203 */ 204 static INLINE unsigned 205 vl_vlc_bits_left(struct vl_vlc *vlc) 206 { 207 signed bytes_left = vlc->end - vlc->data; 208 bytes_left += vlc->bytes_left; 209 return bytes_left * 8 + vl_vlc_valid_bits(vlc); 210 } 211 212 /** 213 * get num_bits from bit buffer without removing them 214 */ 215 static INLINE unsigned 216 vl_vlc_peekbits(struct vl_vlc *vlc, unsigned num_bits) 217 { 218 assert(vl_vlc_valid_bits(vlc) >= num_bits || vlc->data >= vlc->end); 219 return vlc->buffer >> (64 - num_bits); 220 } 221 222 /** 223 * remove num_bits from bit buffer 224 */ 225 static INLINE void 226 vl_vlc_eatbits(struct vl_vlc *vlc, unsigned num_bits) 227 { 228 assert(vl_vlc_valid_bits(vlc) >= num_bits); 229 230 vlc->buffer <<= num_bits; 231 vlc->invalid_bits += num_bits; 232 } 233 234 /** 235 * get num_bits from bit buffer with removing them 236 */ 237 static INLINE unsigned 238 vl_vlc_get_uimsbf(struct vl_vlc *vlc, unsigned num_bits) 239 { 240 unsigned value; 241 242 assert(vl_vlc_valid_bits(vlc) >= num_bits); 243 244 value = vlc->buffer >> (64 - num_bits); 245 vl_vlc_eatbits(vlc, num_bits); 246 247 return value; 248 } 249 250 /** 251 * treat num_bits as signed value and remove them from bit buffer 252 */ 253 static INLINE signed 254 vl_vlc_get_simsbf(struct vl_vlc *vlc, unsigned num_bits) 255 { 256 signed value; 257 258 assert(vl_vlc_valid_bits(vlc) >= num_bits); 259 260 value = ((int64_t)vlc->buffer) >> (64 - num_bits); 261 vl_vlc_eatbits(vlc, num_bits); 262 263 return value; 264 } 265 266 /** 267 * lookup a value and length in a decompressed table 268 */ 269 static INLINE int8_t 270 vl_vlc_get_vlclbf(struct vl_vlc *vlc, const struct vl_vlc_entry *tbl, unsigned num_bits) 271 { 272 tbl += vl_vlc_peekbits(vlc, num_bits); 273 vl_vlc_eatbits(vlc, tbl->length); 274 return tbl->value; 275 } 276 277 #endif /* vl_vlc_h */ 278
