Coverage Report

Created: 2025-06-15 00:57

/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
99.7k
{
109
#ifdef __sparc__
110
  uint64_t v;
111
  memcpy(&v, ptr, sizeof(v));
112
  return cpu_to_be64(v);
113
114
#else
115
99.7k
  typedef __attribute__((aligned(1))) uint64_t unalign64;
116
99.7k
  return cpu_to_be64(*(const unalign64*)ptr);
117
99.7k
#endif
118
99.7k
}
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
6.66k
{
134
6.66k
  assert(dec != NULL);
135
6.66k
  assert(buf != NULL);
136
137
6.66k
  dec->cursor = (const uint8_t *)buf;
138
139
6.66k
  if (buf_size < 1) {
140
0
    dec->bits_consumed = sizeof(dec->bit_container)*8;
141
0
    dec->bit_container = 0;
142
0
    dec->limit_ptr = (const uint8_t *)buf;
143
0
    return 0;
144
0
  }
145
146
6.66k
  if (buf_size >= sizeof(dec->bit_container)) {  /* normal case */
147
3.98k
    dec->bits_consumed = 0;
148
3.98k
    dec->bit_container = bit_read_unaligned_64be(dec->cursor);
149
3.98k
    dec->limit_ptr = dec->cursor + buf_size - sizeof(dec->bit_container);
150
3.98k
  } else {
151
2.68k
    const uint8_t *ui8_p = (const uint8_t *)(buf);
152
153
2.68k
    dec->bits_consumed = (unsigned int)(sizeof(dec->bit_container) - buf_size) * 8;
154
155
2.68k
    dec->bit_container = (uint64_t)ui8_p[0] << 56;
156
2.68k
    switch (buf_size) {
157
255
    case 7:
158
255
      dec->bit_container += (uint64_t)ui8_p[6] <<  8;
159
      /* fall-through */
160
854
    case 6:
161
854
      dec->bit_container += (uint64_t)ui8_p[5] << 16;
162
      /* fall-through */
163
1.20k
    case 5:
164
1.20k
      dec->bit_container += (uint64_t)ui8_p[4] << 24;
165
      /* fall-through */
166
2.25k
    case 4:
167
2.25k
      dec->bit_container += (uint64_t)ui8_p[3] << 32;
168
      /* fall-through */
169
2.37k
    case 3:
170
2.37k
      dec->bit_container += (uint64_t)ui8_p[2] << 40;
171
      /* fall-through */
172
2.58k
    case 2:
173
2.58k
      dec->bit_container += (uint64_t)ui8_p[1] << 48;
174
      /* fall-through */
175
2.68k
    default:
176
2.68k
      break;
177
2.68k
    }
178
2.68k
    dec->bit_container >>= dec->bits_consumed;
179
180
2.68k
    dec->limit_ptr = dec->cursor;
181
2.68k
  }
182
6.66k
  return buf_size;
183
6.66k
}
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
85.0k
{
196
  /* mask for the shift value register to prevent undefined behaviour */
197
85.0k
  uint32_t const reg_mask = 0x3F;
198
199
85.0k
  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
85.0k
  return (dec->bit_container << (dec->bits_consumed & reg_mask)) >> (64-nb_bits);
204
85.0k
}
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
90.0k
{
217
  /* mask for the shift value register to prevent undefined behaviour */
218
90.0k
  uint32_t const reg_mask = 0x3F;
219
  /* shift out the bits we've already consumed */
220
90.0k
  uint64_t const remaining_flip = ~(dec->bit_container << (dec->bits_consumed & reg_mask));
221
222
  /* clzll(0) is undefined behaviour */
223
90.0k
  return remaining_flip ? (unsigned int)__builtin_clzll(remaining_flip) :
224
90.0k
    sizeof(dec->bit_container)*8;
225
90.0k
}
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
205k
{
237
205k
  dec->bits_consumed += nb_bits;
238
205k
}
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
27.9k
{
255
27.9k
  uint64_t const read_bits = bit_peek_bits(dec, nb_bits);
256
257
27.9k
  bit_consume_bits(dec, nb_bits);
258
27.9k
  return read_bits;
259
27.9k
}
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
23.8k
{
276
23.8k
  assert(nb_bits <= 32);
277
278
23.8k
  return (uint32_t)bit_read_bits(dec, nb_bits);
279
23.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.1k
{
301
  /* mask for the shift value register to prevent undefined behaviour */
302
30.1k
  uint32_t const reg_mask = sizeof(dec->bit_container)*8 - 1;
303
30.1k
  unsigned int const shift_bits = (64 - dec->bits_consumed - nb_bits) & reg_mask;
304
30.1k
  uint32_t bits_unmask;
305
306
30.1k
  assert(nb_bits <= 32);
307
308
30.1k
  bits_unmask = (uint32_t)(dec->bit_container >> shift_bits);
309
30.1k
  bit_consume_bits(dec, nb_bits);
310
30.1k
  return (bits_unmask - 1) & BIT_MASK[nb_bits];
311
30.1k
}
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
129k
{
332
129k
  unsigned int const bytes_consumed = dec->bits_consumed >> 3;
333
334
129k
  if (unlikely(dec->bits_consumed > sizeof(dec->bit_container)*8))
335
0
    return BIT_OVERFLOW;
336
337
129k
  if (dec->cursor + bytes_consumed < dec->limit_ptr) {
338
    /* Advance the pointer by the number of full bytes we consumed */
339
91.9k
    dec->cursor += bytes_consumed;
340
    /* Refill the bit container */
341
91.9k
    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
91.9k
    dec->bits_consumed &= 0x7;
347
91.9k
    return BIT_UNFINISHED;
348
91.9k
  }
349
350
37.6k
  if (dec->cursor == dec->limit_ptr) {
351
33.7k
    if (dec->bits_consumed == sizeof(dec->bit_container)*8)
352
5.31k
      return BIT_ALL_READ_IN;
353
28.4k
    return BIT_END_OF_BUFFER;
354
33.7k
  }
355
356
  /* limit_ptr < (cursor + bytes_consumed) < end */
357
3.84k
  dec->bits_consumed -= (dec->limit_ptr - dec->cursor)*8;
358
3.84k
  dec->cursor = dec->limit_ptr;
359
3.84k
  dec->bit_container = bit_read_unaligned_64be(dec->cursor);
360
361
3.84k
  return BIT_END_OF_BUFFER;
362
37.6k
}
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 */