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 "util/u_math.h"
36
37 struct vl_vlc
38 {
39 uint64_t buffer;
40 signed invalid_bits;
41 const uint8_t *data;
42 const uint8_t *end;
43
44 const void *const *inputs;
45 const unsigned *sizes;
46 unsigned bytes_left;
47 };
48
49 struct vl_vlc_entry
50 {
51 int8_t length;
52 int8_t value;
53 };
54
55 struct vl_vlc_compressed
56 {
57 uint16_t bitcode;
58 struct vl_vlc_entry entry;
59 };
60
61 /**
62 * initalize and decompress a lookup table
63 */
64 static inline void
vl_vlc_init_table(struct vl_vlc_entry * dst,unsigned dst_size,const struct vl_vlc_compressed * src,unsigned src_size)65 vl_vlc_init_table(struct vl_vlc_entry *dst, unsigned dst_size, const struct vl_vlc_compressed *src, unsigned src_size)
66 {
67 unsigned i, bits = util_logbase2(dst_size);
68
69 assert(dst && dst_size);
70 assert(src && src_size);
71
72 for (i=0;i<dst_size;++i) {
73 dst[i].length = 0;
74 dst[i].value = 0;
75 }
76
77 for(; src_size > 0; --src_size, ++src) {
78 for(i = 0; i < (1u << (bits - src->entry.length)); ++i)
79 dst[src->bitcode >> (16 - bits) | i] = src->entry;
80 }
81 }
82
83 /**
84 * switch over to next input buffer
85 */
86 static inline void
vl_vlc_next_input(struct vl_vlc * vlc)87 vl_vlc_next_input(struct vl_vlc *vlc)
88 {
89 unsigned len = vlc->sizes[0];
90
91 assert(vlc);
92 assert(vlc->bytes_left);
93
94 if (len < vlc->bytes_left)
95 vlc->bytes_left -= len;
96 else {
97 len = vlc->bytes_left;
98 vlc->bytes_left = 0;
99 }
100
101 vlc->data = (const uint8_t *) vlc->inputs[0];
102 vlc->end = vlc->data + len;
103
104 ++vlc->inputs;
105 ++vlc->sizes;
106 }
107
108 /**
109 * align the data pointer to the next dword
110 */
111 static inline void
vl_vlc_align_data_ptr(struct vl_vlc * vlc)112 vl_vlc_align_data_ptr(struct vl_vlc *vlc)
113 {
114 /* align the data pointer */
115 while (vlc->data != vlc->end && ((uintptr_t)vlc->data) & 3) {
116 vlc->buffer |= (uint64_t)*vlc->data << (24 + vlc->invalid_bits);
117 ++vlc->data;
118 vlc->invalid_bits -= 8;
119 }
120 }
121
122 /**
123 * fill the bit buffer, so that at least 32 bits are valid
124 */
125 static inline void
vl_vlc_fillbits(struct vl_vlc * vlc)126 vl_vlc_fillbits(struct vl_vlc *vlc)
127 {
128 assert(vlc);
129
130 /* as long as the buffer needs to be filled */
131 while (vlc->invalid_bits > 0) {
132 unsigned bytes_left = vlc->end - vlc->data;
133
134 /* if this input is depleted */
135 if (bytes_left == 0) {
136
137 if (vlc->bytes_left) {
138 /* go on to next input */
139 vl_vlc_next_input(vlc);
140 vl_vlc_align_data_ptr(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 #if !UTIL_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
vl_vlc_init(struct vl_vlc * vlc,unsigned num_inputs,const void * const * inputs,const unsigned * sizes)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->inputs = inputs;
186 vlc->sizes = sizes;
187 vlc->bytes_left = 0;
188
189 for (i = 0; i < num_inputs; ++i)
190 vlc->bytes_left += sizes[i];
191
192 if (vlc->bytes_left) {
193 vl_vlc_next_input(vlc);
194 vl_vlc_align_data_ptr(vlc);
195 vl_vlc_fillbits(vlc);
196 }
197 }
198
199 /**
200 * number of bits still valid in bit buffer
201 */
202 static inline unsigned
vl_vlc_valid_bits(struct vl_vlc * vlc)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
vl_vlc_bits_left(struct vl_vlc * vlc)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
vl_vlc_peekbits(struct vl_vlc * vlc,unsigned num_bits)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
vl_vlc_eatbits(struct vl_vlc * vlc,unsigned num_bits)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
vl_vlc_get_uimsbf(struct vl_vlc * vlc,unsigned num_bits)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
vl_vlc_get_simsbf(struct vl_vlc * vlc,unsigned num_bits)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
vl_vlc_get_vlclbf(struct vl_vlc * vlc,const struct vl_vlc_entry * tbl,unsigned num_bits)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 bool
vl_vlc_search_byte(struct vl_vlc * vlc,unsigned num_bits,uint8_t value)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 == ~0u || (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 != ~0u) {
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->bytes_left)
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 != ~0u) {
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 /**
342 * remove num_bits bits starting at pos from the bitbuffer
343 */
344 static inline void
vl_vlc_removebits(struct vl_vlc * vlc,unsigned pos,unsigned num_bits)345 vl_vlc_removebits(struct vl_vlc *vlc, unsigned pos, unsigned num_bits)
346 {
347 uint64_t lo = (vlc->buffer & (~0UL >> (pos + num_bits))) << num_bits;
348 uint64_t hi = (vlc->buffer & (~0UL << (64 - pos)));
349 vlc->buffer = lo | hi;
350 vlc->invalid_bits += num_bits;
351 }
352
353 /**
354 * limit the number of bits left for fetching
355 */
356 static inline void
vl_vlc_limit(struct vl_vlc * vlc,unsigned bits_left)357 vl_vlc_limit(struct vl_vlc *vlc, unsigned bits_left)
358 {
359 assert(bits_left <= vl_vlc_bits_left(vlc));
360
361 vl_vlc_fillbits(vlc);
362 if (bits_left < vl_vlc_valid_bits(vlc)) {
363 vlc->invalid_bits = 32 - bits_left;
364 vlc->buffer &= ~0L << (vlc->invalid_bits + 32);
365 vlc->end = vlc->data;
366 vlc->bytes_left = 0;
367 } else {
368 assert((bits_left - vl_vlc_valid_bits(vlc)) % 8 == 0);
369 vlc->bytes_left = (bits_left - vl_vlc_valid_bits(vlc)) / 8;
370 if (vlc->bytes_left < (vlc->end - vlc->data)) {
371 vlc->end = vlc->data + vlc->bytes_left;
372 vlc->bytes_left = 0;
373 } else
374 vlc->bytes_left -= vlc->end - vlc->data;
375 }
376 }
377
378 #endif /* vl_vlc_h */
379