• Home
  • Line#
  • Scopes#
  • Navigate#
  • Raw
  • Download
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
vl_vlc_init_table(struct vl_vlc_entry * dst,unsigned dst_size,const struct vl_vlc_compressed * src,unsigned src_size)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
vl_vlc_next_input(struct vl_vlc * vlc)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
vl_vlc_align_data_ptr(struct vl_vlc * vlc)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
vl_vlc_fillbits(struct vl_vlc * vlc)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
vl_vlc_init(struct vl_vlc * vlc,unsigned num_inputs,const void * const * inputs,const unsigned * sizes)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
vl_vlc_valid_bits(struct vl_vlc * vlc)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
vl_vlc_bits_left(struct vl_vlc * vlc)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
vl_vlc_peekbits(struct vl_vlc * vlc,unsigned num_bits)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
vl_vlc_eatbits(struct vl_vlc * vlc,unsigned num_bits)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
vl_vlc_get_uimsbf(struct vl_vlc * vlc,unsigned num_bits)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
vl_vlc_get_simsbf(struct vl_vlc * vlc,unsigned num_bits)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
vl_vlc_get_vlclbf(struct vl_vlc * vlc,const struct vl_vlc_entry * tbl,unsigned num_bits)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
vl_vlc_search_byte(struct vl_vlc * vlc,unsigned num_bits,uint8_t value)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
vl_vlc_removebits(struct vl_vlc * vlc,unsigned pos,unsigned num_bits)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
vl_vlc_limit(struct vl_vlc * vlc,unsigned bits_left)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