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 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
vl_vlc_init_table(struct vl_vlc_entry * dst,unsigned dst_size,const struct vl_vlc_compressed * src,unsigned src_size)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
vl_vlc_next_input(struct vl_vlc * vlc)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
vl_vlc_fillbits(struct vl_vlc * vlc)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
vl_vlc_init(struct vl_vlc * vlc,unsigned num_inputs,const void * const * inputs,const unsigned * sizes)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
vl_vlc_valid_bits(struct vl_vlc * vlc)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
vl_vlc_bits_left(struct vl_vlc * vlc)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
vl_vlc_peekbits(struct vl_vlc * vlc,unsigned num_bits)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
vl_vlc_eatbits(struct vl_vlc * vlc,unsigned num_bits)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
vl_vlc_get_uimsbf(struct vl_vlc * vlc,unsigned num_bits)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
vl_vlc_get_simsbf(struct vl_vlc * vlc,unsigned num_bits)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
vl_vlc_get_vlclbf(struct vl_vlc * vlc,const struct vl_vlc_entry * tbl,unsigned num_bits)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