/src/cmp_tool/lib/decompress/read_bitstream.h
Line | Count | Source (jump to first uncovered line) |
1 | | /** |
2 | | * @file read_bitstream.h |
3 | | * @author Dominik Loidolt (dominik.loidolt@univie.ac.at) |
4 | | * @date 2023 |
5 | | * |
6 | | * @copyright GPLv2 |
7 | | * This program is free software; you can redistribute it and/or modify it |
8 | | * under the terms and conditions of the GNU General Public License, |
9 | | * version 2, as published by the Free Software Foundation. |
10 | | * |
11 | | * This program is distributed in the hope it will be useful, but WITHOUT |
12 | | * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or |
13 | | * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for |
14 | | * more details. |
15 | | * |
16 | | * @brief this library handles the reading from an MSB-first bitstream |
17 | | * |
18 | | * This API consists of small unitary functions, which must be inlined for best performance. |
19 | | * Since link-time-optimization is not available for all compilers, these |
20 | | * functions are defined into a .h to be included. |
21 | | * |
22 | | * Start by invoking bit_init_decoder(). A chunk of the bitstream is then stored |
23 | | * into a local register. The local register size is 64 bits. You can then retrieve |
24 | | * bit-fields stored into the local register. The local register is explicitly |
25 | | * reloaded from the memory with the bit_refill() function. |
26 | | * A reload guarantees a minimum of 57 bits in the local register if the |
27 | | * returned status is BIT_UNFINISHED. |
28 | | * Otherwise, it can be less than that, so proceed accordingly. |
29 | | * Checking if bit_decoder has reached its end can be performed with bit_end_of_stream(). |
30 | | * |
31 | | * This is based on the bitstream part of the FiniteStateEntropy library, see: |
32 | | * https://github.com/Cyan4973/FiniteStateEntropy/blob/dev/lib/bitstream.h |
33 | | * by @author Yann Collet |
34 | | * As well as some ideas from this blog post: |
35 | | * https://fgiesen.wordpress.com/2018/02/20/reading-bits-in-far-too-many-ways-part-2/ |
36 | | * by @author Fabian Giesen |
37 | | */ |
38 | | |
39 | | #ifndef READ_BITSTREAM_H |
40 | | #define READ_BITSTREAM_H |
41 | | |
42 | | #include <stdint.h> |
43 | | #include <stddef.h> |
44 | | #include <assert.h> |
45 | | #include <string.h> |
46 | | |
47 | | #include "../common/byteorder.h" |
48 | | #include "../common/compiler.h" |
49 | | |
50 | | |
51 | | |
52 | | /** |
53 | | * @brief bitstream decoder context type |
54 | | */ |
55 | | |
56 | | struct bit_decoder { |
57 | | uint64_t bit_container; |
58 | | unsigned int bits_consumed; |
59 | | const uint8_t *cursor; |
60 | | const uint8_t *limit_ptr; |
61 | | }; |
62 | | |
63 | | |
64 | | /** |
65 | | * @brief bitstream decoder status, return type of bit_refill() |
66 | | */ |
67 | | |
68 | | enum bit_status {BIT_OVERFLOW, BIT_END_OF_BUFFER, BIT_ALL_READ_IN, BIT_UNFINISHED}; |
69 | | |
70 | | |
71 | | /* |
72 | | * bitstream decoder API |
73 | | */ |
74 | | |
75 | | static __inline size_t bit_init_decoder(struct bit_decoder *dec, const void *buf, size_t buf_size); |
76 | | static __inline uint64_t bit_peek_bits(const struct bit_decoder *dec, unsigned int nb_bits); |
77 | | static __inline void bit_consume_bits(struct bit_decoder *dec, unsigned int nb_bits); |
78 | | static __inline uint64_t bit_read_bits(struct bit_decoder *dec, unsigned int nb_bits); |
79 | | static __inline uint32_t bit_read_bits32(struct bit_decoder *dec, unsigned int nb_bits); |
80 | | static __inline uint32_t bit_read_bits32_sub_1(struct bit_decoder *dec, unsigned int nb_bits); |
81 | | static __inline unsigned int bit_end_of_stream(const struct bit_decoder *dec); |
82 | | static __inline int bit_refill(struct bit_decoder *dec); |
83 | | |
84 | | |
85 | | /* |
86 | | * internal implementation |
87 | | */ |
88 | | |
89 | | static const uint32_t BIT_MASK[] = { |
90 | | 0, 1, 3, 7, 0xF, 0x1F, |
91 | | 0x3F, 0x7F, 0xFF, 0x1FF, 0x3FF, 0x7FF, |
92 | | 0xFFF, 0x1FFF, 0x3FFF, 0x7FFF, 0xFFFF, 0x1FFFF, |
93 | | 0x3FFFF, 0x7FFFF, 0xFFFFF, 0x1FFFFF, 0x3FFFFF, 0x7FFFFF, |
94 | | 0xFFFFFF, 0x1FFFFFF, 0x3FFFFFF, 0x7FFFFFF, 0xFFFFFFF, 0x1FFFFFFF, |
95 | | 0x3FFFFFFF, 0x7FFFFFFF, 0xFFFFFFFF}; /* up to 32 bits */ |
96 | | #define BIT_MASK_SIZE ARRAY_SIZE(BIT_mask) |
97 | | |
98 | | |
99 | | /** |
100 | | * @brief read 8 bytes of big-endian data from an unaligned address |
101 | | * |
102 | | * @param ptr pointer to the data (can be unaligned) |
103 | | * |
104 | | * @returns 64 bit data at mem_ptr address in big-endian byte order |
105 | | */ |
106 | | |
107 | | static __inline uint64_t bit_read_unaligned_64be(const void *ptr) |
108 | 105k | { |
109 | | #ifdef __sparc__ |
110 | | uint64_t v; |
111 | | memcpy(&v, ptr, sizeof(v)); |
112 | | return cpu_to_be64(v); |
113 | | |
114 | | #else |
115 | 105k | typedef __attribute__((aligned(1))) uint64_t unalign64; |
116 | 105k | return cpu_to_be64(*(const unalign64*)ptr); |
117 | 105k | #endif |
118 | 105k | } |
119 | | |
120 | | |
121 | | /** |
122 | | * @brief initialize a bit_decoder |
123 | | * |
124 | | * @param dec a pointer to an already allocated bit_decoder structure |
125 | | * @param buf start address of the bitstream buffer |
126 | | * @param buf_size size of the bitstream in bytes |
127 | | * |
128 | | * @returns size of stream (== src_size), or zero if a problem is detected |
129 | | */ |
130 | | |
131 | | static __inline size_t bit_init_decoder(struct bit_decoder *dec, const void *buf, |
132 | | size_t buf_size) |
133 | 7.17k | { |
134 | 7.17k | assert(dec != NULL); |
135 | 7.17k | assert(buf != NULL); |
136 | | |
137 | 7.17k | dec->cursor = (const uint8_t *)buf; |
138 | | |
139 | 7.17k | if (buf_size < 1) { |
140 | 43 | dec->bits_consumed = sizeof(dec->bit_container)*8; |
141 | 43 | dec->bit_container = 0; |
142 | 43 | dec->limit_ptr = (const uint8_t *)buf; |
143 | 43 | return 0; |
144 | 43 | } |
145 | | |
146 | 7.12k | if (buf_size >= sizeof(dec->bit_container)) { /* normal case */ |
147 | 4.41k | dec->bits_consumed = 0; |
148 | 4.41k | dec->bit_container = bit_read_unaligned_64be(dec->cursor); |
149 | 4.41k | dec->limit_ptr = dec->cursor + buf_size - sizeof(dec->bit_container); |
150 | 4.41k | } else { |
151 | 2.71k | const uint8_t *ui8_p = (const uint8_t *)(buf); |
152 | | |
153 | 2.71k | dec->bits_consumed = (unsigned int)(sizeof(dec->bit_container) - buf_size) * 8; |
154 | | |
155 | 2.71k | dec->bit_container = (uint64_t)ui8_p[0] << 56; |
156 | 2.71k | switch (buf_size) { |
157 | 263 | case 7: |
158 | 263 | dec->bit_container += (uint64_t)ui8_p[6] << 8; |
159 | | /* fall-through */ |
160 | 864 | case 6: |
161 | 864 | dec->bit_container += (uint64_t)ui8_p[5] << 16; |
162 | | /* fall-through */ |
163 | 1.21k | case 5: |
164 | 1.21k | dec->bit_container += (uint64_t)ui8_p[4] << 24; |
165 | | /* fall-through */ |
166 | 2.27k | case 4: |
167 | 2.27k | dec->bit_container += (uint64_t)ui8_p[3] << 32; |
168 | | /* fall-through */ |
169 | 2.39k | case 3: |
170 | 2.39k | dec->bit_container += (uint64_t)ui8_p[2] << 40; |
171 | | /* fall-through */ |
172 | 2.61k | case 2: |
173 | 2.61k | dec->bit_container += (uint64_t)ui8_p[1] << 48; |
174 | | /* fall-through */ |
175 | 2.71k | default: |
176 | 2.71k | break; |
177 | 2.71k | } |
178 | 2.71k | dec->bit_container >>= dec->bits_consumed; |
179 | | |
180 | 2.71k | dec->limit_ptr = dec->cursor; |
181 | 2.71k | } |
182 | 7.12k | return buf_size; |
183 | 7.12k | } |
184 | | |
185 | | |
186 | | /** |
187 | | * @brief provides next n bits from local register; local register is not modified |
188 | | * |
189 | | * @param dec a pointer to a bit_decoder context |
190 | | * @param nb_bits number of bits to look; only works if 1 <= nb_bits <= 56 |
191 | | * |
192 | | * @returns extracted value |
193 | | */ |
194 | | static __inline uint64_t bit_peek_bits(const struct bit_decoder *dec, unsigned int nb_bits) |
195 | 90.2k | { |
196 | | /* mask for the shift value register to prevent undefined behaviour */ |
197 | 90.2k | uint32_t const reg_mask = 0x3F; |
198 | | |
199 | 90.2k | assert(nb_bits >= 1 && nb_bits <= (64 - 7)); |
200 | | /* why -7: worst case refill can only put 56 bit in the bit_container */ |
201 | | |
202 | | /* shift out consumed bits; return the top nb_bits bits we want to peek */ |
203 | 90.2k | return (dec->bit_container << (dec->bits_consumed & reg_mask)) >> (64-nb_bits); |
204 | 90.2k | } |
205 | | |
206 | | |
207 | | /** |
208 | | * @brief count the leading ones in the local register; local register is not modified |
209 | | * |
210 | | * @param dec pointer to a bit_decoder context |
211 | | * |
212 | | * @returns number of leading ones; |
213 | | */ |
214 | | |
215 | | static __inline unsigned int bit_peek_leading_ones(const struct bit_decoder *dec) |
216 | 96.1k | { |
217 | | /* mask for the shift value register to prevent undefined behaviour */ |
218 | 96.1k | uint32_t const reg_mask = 0x3F; |
219 | | /* shift out the bits we've already consumed */ |
220 | 96.1k | uint64_t const remaining_flip = ~(dec->bit_container << (dec->bits_consumed & reg_mask)); |
221 | | |
222 | | /* clzll(0) is undefined behaviour */ |
223 | 96.1k | return remaining_flip ? (unsigned int)__builtin_clzll(remaining_flip) : |
224 | 96.1k | sizeof(dec->bit_container)*8; |
225 | 96.1k | } |
226 | | |
227 | | |
228 | | /** |
229 | | * @brief mark next n bits in the local register as consumed |
230 | | * |
231 | | * @param dec pointer to a bit_decoder context |
232 | | * @param nb_bits number of bits to skip |
233 | | */ |
234 | | |
235 | | static __inline void bit_consume_bits(struct bit_decoder *dec, unsigned int nb_bits) |
236 | 217k | { |
237 | 217k | dec->bits_consumed += nb_bits; |
238 | 217k | } |
239 | | |
240 | | |
241 | | /** |
242 | | * @brief read and consume next n bits from the local register |
243 | | * @warning do not read more bits than the local register has unconsumed bits. |
244 | | * If you do this, the bit_refill function will return the BIT_OVERFLOW |
245 | | * status the next time the register is refilled. |
246 | | * |
247 | | * @param dec pointer to a bit_decoder context |
248 | | * @param nb_bits number of bits to look; only works if 1 <= nb_bits <= 56 |
249 | | * |
250 | | * @returns extracted value |
251 | | */ |
252 | | |
253 | | static __inline uint64_t bit_read_bits(struct bit_decoder *dec, unsigned int nb_bits) |
254 | 29.0k | { |
255 | 29.0k | uint64_t const read_bits = bit_peek_bits(dec, nb_bits); |
256 | | |
257 | 29.0k | bit_consume_bits(dec, nb_bits); |
258 | 29.0k | return read_bits; |
259 | 29.0k | } |
260 | | |
261 | | |
262 | | /** |
263 | | * @brief same as bit_read_bits32() but only returns maximum 32 bit |
264 | | * @warning do not read more bits than the local register has unconsumed bits. |
265 | | * If you do this, the bit_refill function will return the BIT_OVERFLOW |
266 | | * status the next time the register is refilled. |
267 | | * |
268 | | * @param dec pointer to a bit_decoder context |
269 | | * @param nb_bits number of bits to read; only works if 1 <= nb_bits <= 32 |
270 | | * |
271 | | * @returns extracted maximum 32 bit value |
272 | | */ |
273 | | |
274 | | static __inline uint32_t bit_read_bits32(struct bit_decoder *dec, unsigned int nb_bits) |
275 | 24.8k | { |
276 | 24.8k | assert(nb_bits <= 32); |
277 | | |
278 | 24.8k | return (uint32_t)bit_read_bits(dec, nb_bits); |
279 | 24.8k | } |
280 | | |
281 | | |
282 | | /** |
283 | | * @brief same as bit_read_bits32() but subtract 1 from the extracted value |
284 | | * @warning do not read more bits than the local register has unconsumed bits. |
285 | | * If you do this, the bit_refill function will return the BIT_OVERFLOW |
286 | | * status the next time the register is refilled. |
287 | | * |
288 | | * @param dec pointer to a bit_decoder context |
289 | | * @param nb_bits number of bits to read; only works if nb_bits <= 32 |
290 | | * |
291 | | * @returns extracted 32 bit value minus 1 |
292 | | * |
293 | | * @note The difference to the bit_read_bits32() function with subtraction is |
294 | | * that the subtracted value is masked with nb_bits. E.g. if you read 4 |
295 | | * bits from the bitstream and get 0 and then subtract 1, you get 0xFF |
296 | | * instead of 0xFFFFFFFF |
297 | | */ |
298 | | |
299 | | static __inline uint32_t bit_read_bits32_sub_1(struct bit_decoder *dec, unsigned int nb_bits) |
300 | 30.9k | { |
301 | | /* mask for the shift value register to prevent undefined behaviour */ |
302 | 30.9k | uint32_t const reg_mask = sizeof(dec->bit_container)*8 - 1; |
303 | 30.9k | unsigned int const shift_bits = (64 - dec->bits_consumed - nb_bits) & reg_mask; |
304 | 30.9k | uint32_t bits_unmask; |
305 | | |
306 | 30.9k | assert(nb_bits <= 32); |
307 | | |
308 | 30.9k | bits_unmask = (uint32_t)(dec->bit_container >> shift_bits); |
309 | 30.9k | bit_consume_bits(dec, nb_bits); |
310 | 30.9k | return (bits_unmask - 1) & BIT_MASK[nb_bits]; |
311 | 30.9k | } |
312 | | |
313 | | |
314 | | /** |
315 | | * @brief refill the local register from the buffer previously set in |
316 | | * bit_init_decoder() |
317 | | * |
318 | | * @param dec a bitstream decoding context |
319 | | * |
320 | | * @note this function is safe, it guarantees that it does not read beyond |
321 | | * initialize buffer |
322 | | * |
323 | | * @returns the status of bit_decoder internal register; |
324 | | * BIT_UNFINISHED: internal register is filled with at least _57-bits_ |
325 | | * BIT_END_OF_BUFFER: reached the end of the buffer, only some bits are left in the bitstream |
326 | | * BIT_ALL_READ_IN: _all_ bits of the buffer have been consumed |
327 | | * BIT_OVERFLOW: more bits have been consumed than contained in the local register |
328 | | */ |
329 | | |
330 | | static __inline int bit_refill(struct bit_decoder *dec) |
331 | 137k | { |
332 | 137k | unsigned int const bytes_consumed = dec->bits_consumed >> 3; |
333 | | |
334 | 137k | if (unlikely(dec->bits_consumed > sizeof(dec->bit_container)*8)) |
335 | 298 | return BIT_OVERFLOW; |
336 | | |
337 | 136k | if (dec->cursor + bytes_consumed < dec->limit_ptr) { |
338 | | /* Advance the pointer by the number of full bytes we consumed */ |
339 | 97.3k | dec->cursor += bytes_consumed; |
340 | | /* Refill the bit container */ |
341 | 97.3k | dec->bit_container = bit_read_unaligned_64be(dec->cursor); |
342 | | /* The number of bits that we have already consumed in the |
343 | | * current byte, excluding the bits that formed a complete byte |
344 | | * and were already processed. |
345 | | */ |
346 | 97.3k | dec->bits_consumed &= 0x7; |
347 | 97.3k | return BIT_UNFINISHED; |
348 | 97.3k | } |
349 | | |
350 | 39.4k | if (dec->cursor == dec->limit_ptr) { |
351 | 35.2k | if (dec->bits_consumed == sizeof(dec->bit_container)*8) |
352 | 5.38k | return BIT_ALL_READ_IN; |
353 | 29.8k | return BIT_END_OF_BUFFER; |
354 | 35.2k | } |
355 | | |
356 | | /* limit_ptr < (cursor + bytes_consumed) < end */ |
357 | 4.17k | dec->bits_consumed -= (dec->limit_ptr - dec->cursor)*8; |
358 | 4.17k | dec->cursor = dec->limit_ptr; |
359 | 4.17k | dec->bit_container = bit_read_unaligned_64be(dec->cursor); |
360 | | |
361 | 4.17k | return BIT_END_OF_BUFFER; |
362 | 39.4k | } |
363 | | |
364 | | |
365 | | /** |
366 | | * @brief Check if the end of the bitstream has been reached |
367 | | * |
368 | | * @param dec a bitstream decoding context |
369 | | * |
370 | | * @returns 1 if bit_decoder has _exactly_ reached its end (all bits consumed) |
371 | | */ |
372 | | |
373 | | static __inline unsigned int bit_end_of_stream(const struct bit_decoder *dec) |
374 | 0 | { |
375 | 0 | return ((dec->cursor == dec->limit_ptr) && |
376 | 0 | (dec->bits_consumed == sizeof(dec->bit_container)*8)); |
377 | 0 | } |
378 | | |
379 | | #endif /* READ_BITSTREAM_H */ |