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    vlc->data = NULL;
189    vlc->end = NULL;
190 
191    for (i = 0; i < num_inputs; ++i)
192       vlc->bytes_left += sizes[i];
193 
194    if (vlc->bytes_left) {
195       vl_vlc_next_input(vlc);
196       vl_vlc_align_data_ptr(vlc);
197       vl_vlc_fillbits(vlc);
198    }
199 }
200 
201 /**
202  * number of bits still valid in bit buffer
203  */
204 static inline unsigned
vl_vlc_valid_bits(struct vl_vlc * vlc)205 vl_vlc_valid_bits(struct vl_vlc *vlc)
206 {
207    return 32 - vlc->invalid_bits;
208 }
209 
210 /**
211  * number of bits left over all inbut buffers
212  */
213 static inline unsigned
vl_vlc_bits_left(struct vl_vlc * vlc)214 vl_vlc_bits_left(struct vl_vlc *vlc)
215 {
216    signed bytes_left = vlc->end - vlc->data;
217    bytes_left += vlc->bytes_left;
218    return bytes_left * 8 + vl_vlc_valid_bits(vlc);
219 }
220 
221 /**
222  * get num_bits from bit buffer without removing them
223  */
224 static inline unsigned
vl_vlc_peekbits(struct vl_vlc * vlc,unsigned num_bits)225 vl_vlc_peekbits(struct vl_vlc *vlc, unsigned num_bits)
226 {
227    assert(vl_vlc_valid_bits(vlc) >= num_bits || vlc->data >= vlc->end);
228    return vlc->buffer >> (64 - num_bits);
229 }
230 
231 /**
232  * remove num_bits from bit buffer
233  */
234 static inline void
vl_vlc_eatbits(struct vl_vlc * vlc,unsigned num_bits)235 vl_vlc_eatbits(struct vl_vlc *vlc, unsigned num_bits)
236 {
237    assert(vl_vlc_valid_bits(vlc) >= num_bits);
238 
239    vlc->buffer <<= num_bits;
240    vlc->invalid_bits += num_bits;
241 }
242 
243 /**
244  * get num_bits from bit buffer with removing them
245  */
246 static inline unsigned
vl_vlc_get_uimsbf(struct vl_vlc * vlc,unsigned num_bits)247 vl_vlc_get_uimsbf(struct vl_vlc *vlc, unsigned num_bits)
248 {
249    unsigned value;
250 
251    assert(vl_vlc_valid_bits(vlc) >= num_bits);
252 
253    value = vlc->buffer >> (64 - num_bits);
254    vl_vlc_eatbits(vlc, num_bits);
255 
256    return value;
257 }
258 
259 /**
260  * treat num_bits as signed value and remove them from bit buffer
261  */
262 static inline signed
vl_vlc_get_simsbf(struct vl_vlc * vlc,unsigned num_bits)263 vl_vlc_get_simsbf(struct vl_vlc *vlc, unsigned num_bits)
264 {
265    signed value;
266 
267    assert(vl_vlc_valid_bits(vlc) >= num_bits);
268 
269    value = ((int64_t)vlc->buffer) >> (64 - num_bits);
270    vl_vlc_eatbits(vlc, num_bits);
271 
272    return value;
273 }
274 
275 /**
276  * lookup a value and length in a decompressed table
277  */
278 static inline int8_t
vl_vlc_get_vlclbf(struct vl_vlc * vlc,const struct vl_vlc_entry * tbl,unsigned num_bits)279 vl_vlc_get_vlclbf(struct vl_vlc *vlc, const struct vl_vlc_entry *tbl, unsigned num_bits)
280 {
281    tbl += vl_vlc_peekbits(vlc, num_bits);
282    vl_vlc_eatbits(vlc, tbl->length);
283    return tbl->value;
284 }
285 
286 /**
287  * fast forward search for a specific byte value
288  */
289 static inline bool
vl_vlc_search_byte(struct vl_vlc * vlc,unsigned num_bits,uint8_t value)290 vl_vlc_search_byte(struct vl_vlc *vlc, unsigned num_bits, uint8_t value)
291 {
292    /* make sure we are on a byte boundary */
293    assert((vl_vlc_valid_bits(vlc) % 8) == 0);
294    assert(num_bits == ~0u || (num_bits % 8) == 0);
295 
296    /* deplete the bit buffer */
297    while (vl_vlc_valid_bits(vlc) > 0) {
298 
299       if (vl_vlc_peekbits(vlc, 8) == value) {
300          vl_vlc_fillbits(vlc);
301          return true;
302       }
303 
304       vl_vlc_eatbits(vlc, 8);
305 
306       if (num_bits != ~0u) {
307          num_bits -= 8;
308          if (num_bits == 0)
309             return false;
310       }
311    }
312 
313    /* deplete the byte buffers */
314    while (1) {
315 
316       /* if this input is depleted */
317       if (vlc->data == vlc->end) {
318          if (vlc->bytes_left)
319             /* go on to next input */
320             vl_vlc_next_input(vlc);
321          else
322             /* or give up since we don't have anymore inputs */
323             return false;
324       }
325 
326       if (*vlc->data == value) {
327          vl_vlc_align_data_ptr(vlc);
328          vl_vlc_fillbits(vlc);
329          return true;
330       }
331 
332       ++vlc->data;
333       if (num_bits != ~0u) {
334          num_bits -= 8;
335          if (num_bits == 0) {
336             vl_vlc_align_data_ptr(vlc);
337             return false;
338          }
339       }
340    }
341 }
342 
343 /**
344  * remove num_bits bits starting at pos from the bitbuffer
345  */
346 static inline void
vl_vlc_removebits(struct vl_vlc * vlc,unsigned pos,unsigned num_bits)347 vl_vlc_removebits(struct vl_vlc *vlc, unsigned pos, unsigned num_bits)
348 {
349 #if defined(_MSC_VER)
350    /* MSVC Compiler defines unsigned long as 4 bytes so use explicit 64 bits mask */
351    uint64_t lo = (vlc->buffer & (UINT64_MAX >> (pos + num_bits))) << num_bits;
352    uint64_t hi = (vlc->buffer & (UINT64_MAX << (64 - pos)));
353 #else
354    uint64_t lo = (vlc->buffer & (~0UL >> (pos + num_bits))) << num_bits;
355    uint64_t hi = (vlc->buffer & (~0UL << (64 - pos)));
356 #endif
357    vlc->buffer = lo | hi;
358    vlc->invalid_bits += num_bits;
359 }
360 
361 /**
362  * limit the number of bits left for fetching
363  */
364 static inline void
vl_vlc_limit(struct vl_vlc * vlc,unsigned bits_left)365 vl_vlc_limit(struct vl_vlc *vlc, unsigned bits_left)
366 {
367    assert(bits_left <= vl_vlc_bits_left(vlc));
368 
369    vl_vlc_fillbits(vlc);
370    if (bits_left < vl_vlc_valid_bits(vlc)) {
371       vlc->invalid_bits = 32 - bits_left;
372       vlc->buffer &= ~0L << (vlc->invalid_bits + 32);
373       vlc->end = vlc->data;
374       vlc->bytes_left = 0;
375    } else {
376       assert((bits_left - vl_vlc_valid_bits(vlc)) % 8 == 0);
377       vlc->bytes_left = (bits_left - vl_vlc_valid_bits(vlc)) / 8;
378       if (vlc->bytes_left < (vlc->end - vlc->data)) {
379          vlc->end = vlc->data + vlc->bytes_left;
380          vlc->bytes_left = 0;
381       } else
382          vlc->bytes_left -= vlc->end - vlc->data;
383    }
384 }
385 
386 #endif /* vl_vlc_h */
387