← Back to branch summary

~mmach/netext73/mesa-haswell

« back to all changes in this revision

Viewing changes to src/util/vl_vlc.h

  • Committer: mmach
  • Date: 2022-09-22 19:56:13 UTC
  • Revision ID: netbit73@gmail.com-20220922195613-wtik9mmy20tmor0i
2022-09-22 21:17:09

Show diffs side-by-side

added added

removed removed

Lines of Context:
src/util/vl_vlc.h
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
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
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 = 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
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
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
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
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
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
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
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
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
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
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
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
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
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 */