libxcoder  5.3.1
ni_bitstream.c
Go to the documentation of this file.
1 /*****************************************************************************
2  * This file is part of Kvazaar HEVC encoder.
3  *
4  * Copyright (c) 2021, Tampere University, ITU/ISO/IEC, project contributors
5  * All rights reserved.
6  *
7  * Redistribution and use in source and binary forms, with or without modification,
8  * are permitted provided that the following conditions are met:
9  *
10  * * Redistributions of source code must retain the above copyright notice, this
11  * list of conditions and the following disclaimer.
12  *
13  * * Redistributions in binary form must reproduce the above copyright notice, this
14  * list of conditions and the following disclaimer in the documentation and/or
15  * other materials provided with the distribution.
16  *
17  * * Neither the name of the Tampere University or ITU/ISO/IEC nor the names of its
18  * contributors may be used to endorse or promote products derived from
19  * this software without specific prior written permission.
20  *
21  * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND
22  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
23  * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
24  * DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE FOR
25  * ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
26  * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
27  * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON
28  * ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
29  * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
30  * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
31  ****************************************************************************/
32 
33 /*!*****************************************************************************
34  * \file ni_bitstream.c
35  *
36  * \brief Utility definitions to operate on bits in a bitstream
37  ******************************************************************************/
38 
39 #include <stdio.h>
40 #include <string.h>
41 #include <assert.h>
42 #include "ni_util.h"
43 #include "ni_bitstream.h"
44 
45 // the following is for bitstream put operations
46 
47 const uint32_t ni_bit_set_mask[] = {
48  0x00000001, 0x00000002, 0x00000004, 0x00000008, 0x00000010, 0x00000020,
49  0x00000040, 0x00000080, 0x00000100, 0x00000200, 0x00000400, 0x00000800,
50  0x00001000, 0x00002000, 0x00004000, 0x00008000, 0x00010000, 0x00020000,
51  0x00040000, 0x00080000, 0x00100000, 0x00200000, 0x00400000, 0x00800000,
52  0x01000000, 0x02000000, 0x04000000, 0x08000000, 0x10000000, 0x20000000,
53  0x40000000, 0x80000000};
54 
55 /*!*****************************************************************************
56  * \brief allocate a new bitstream data chunk
57  *
58  * \return pointer to the new chunk, or NULL.
59  ******************************************************************************/
60 static ni_data_chunk_t *ni_bs_writer_alloc_chunk(void)
61 {
62  ni_data_chunk_t *chunk = malloc(sizeof(ni_data_chunk_t));
63  if (chunk)
64  {
65  chunk->len = 0;
66  chunk->next = NULL;
67  }
68  return chunk;
69 }
70 
71 /*!*****************************************************************************
72  * \brief write a byte to bitstream
73  * Note: the stream must be byte-aligned already
74  *
75  * \param stream bitstream
76  * \param byte byte to write
77  * \return none
78  ******************************************************************************/
79 static void ni_bs_writer_write_byte(ni_bitstream_writer_t *stream, uint8_t byte)
80 {
81  assert(stream->cur_bit == 0);
82 
83  if (stream->last == NULL || stream->last->len == NI_DATA_CHUNK_SIZE)
84  {
85  // need to allocate a new chunk.
86  ni_data_chunk_t *new_chunk = ni_bs_writer_alloc_chunk();
87  if (!new_chunk)
88  {
89  ni_log(NI_LOG_ERROR, "%s error: no memory\n", __func__);
90  return;
91  }
92 
93  if (!stream->first)
94  stream->first = new_chunk;
95  if (stream->last)
96  stream->last->next = new_chunk;
97  stream->last = new_chunk;
98  }
99  if (stream->last->len >= NI_DATA_CHUNK_SIZE)
100  {
101  ni_log(NI_LOG_ERROR, "%s error: new_chunk size >= max %d\n", __func__,
103  return;
104  }
105 
106  stream->last->data[stream->last->len] = byte;
107  stream->last->len += 1;
108  stream->len += 1;
109 }
110 
111 /*!*****************************************************************************
112  * \brief free a list of chunks
113  *
114  * \param chunk start of the chunk list
115  * \return none
116  ******************************************************************************/
117 static void ni_bs_writer_free_chunks(ni_data_chunk_t *chunk)
118 {
119  while (chunk != NULL)
120  {
121  ni_data_chunk_t *next = chunk->next;
122  free(chunk);
123  chunk = next;
124  }
125 }
126 
127 static inline unsigned ni_math_floor_log2(unsigned value)
128 {
129  unsigned result = 0;
130  assert(value > 0);
131  int i;
132 
133  for (i = 4; i >= 0; --i)
134  {
135  unsigned bits = 1ull << i;
136  unsigned shift = (value >= (1ull << bits)) ? bits : 0;
137  result += shift;
138  value >>= shift;
139  }
140 
141  return result;
142 }
143 
144 static inline unsigned ni_math_ceil_log2(unsigned value)
145 {
146  assert(value > 0);
147 
148  // the ceil_log2 is just floor_log2 + 1, except for exact powers of 2.
149  return ni_math_floor_log2(value) + ((value & (value - 1)) ? 1 : 0);
150 }
151 
152 /*!*****************************************************************************
153  * \brief init a bitstream writer
154  *
155  * \param stream bitstream
156  * \return none
157  ******************************************************************************/
159 {
160  memset(stream, 0, sizeof(ni_bitstream_writer_t));
161 }
162 
163 /*!*****************************************************************************
164  * \brief return the number of bits written to bitstream so far
165  *
166  * \param stream bitstream
167  * \return position
168  ******************************************************************************/
169 uint64_t ni_bs_writer_tell(const ni_bitstream_writer_t *const stream)
170 {
171  uint64_t position = stream->len;
172  return position * 8 + stream->cur_bit;
173 }
174 
175 /*!*****************************************************************************
176  * \brief write a specified number (<= 32) of bits to bitstream,
177  * buffer individual bits until a full byte is made
178  * \param stream bitstream
179  * \param data input data
180  * \param bits number of bits in data to write to stream, max 32
181  * \return none
182  ******************************************************************************/
183 void ni_bs_writer_put(ni_bitstream_writer_t *stream, uint32_t data,
184  uint8_t bits)
185 {
186  if (bits > 32)
187  {
188  ni_log(NI_LOG_ERROR, "%s error: too many bits to write: %u\n", __func__,
189  bits);
190  return;
191  }
192 
193  while (bits--)
194  {
195  if (bits >= 32)
196  {
197  ni_log(NI_LOG_ERROR, "%s error: invalid bits to write: %u\n", __func__,
198  bits);
199  return;
200  }
201  stream->data <<= 1;
202 
203  if (data & ni_bit_set_mask[bits])
204  {
205  stream->data |= 1;
206  }
207  stream->cur_bit++;
208 
209  // write the complete byte
210  if (stream->cur_bit == 8)
211  {
212  stream->cur_bit = 0;
213  ni_bs_writer_write_byte(stream, stream->data);
214  }
215  }
216 }
217 
218 /*!*****************************************************************************
219  * \brief write unsigned Exp-Golomb bit string to bitstream, 2^32-2 at most.
220  *
221  * \param stream bitstream
222  * \param data input data
223  * \return none
224  ******************************************************************************/
225 void ni_bs_writer_put_ue(ni_bitstream_writer_t *stream, uint32_t data)
226 {
227  unsigned data_log2 = ni_math_floor_log2(data + 1);
228  unsigned prefix = 0;
229  if (data_log2 < 32)
230  {
231  prefix = 1U << data_log2;
232  }
233  unsigned suffix = data + 1 - prefix;
234  unsigned num_bits = data_log2 * 2 + 1;
235  unsigned value = prefix | suffix;
236 
237  if (data > 0xFFFFFFFE) // 2^32-2 at most
238  {
239  ni_log(NI_LOG_ERROR, "%s error: data overflow: %u\n", __func__,
240  data);
241  return;
242  }
243 
244  if (num_bits <= 32)
245  {
246  ni_bs_writer_put(stream, value, num_bits);
247  }
248  else
249  {
250  // big endian
251  ni_bs_writer_put(stream, 0, num_bits - 32); // high (num_bits - 32) bits
252  ni_bs_writer_put(stream, value, 32); // low 32 bits
253  }
254 }
255 
256 /*!*****************************************************************************
257  * \brief write signed Exp-Golomb bit string to bitstream
258  *
259  * \param stream bitstream
260  * \param data input data
261  * \return none
262  ******************************************************************************/
263 void ni_bs_writer_put_se(ni_bitstream_writer_t *stream, int32_t data)
264 {
265  // map positive value to even and negative to odd value
266  uint32_t data_num = data <= 0 ? (-data) << 1 : (data << 1) - 1;
267  ni_bs_writer_put_ue(stream, data_num);
268 }
269 
270 /*!*****************************************************************************
271  * \brief align the bitstream with zero
272  *
273  * \param stream bitstream
274  * \return none
275  ******************************************************************************/
277 {
278  if ((stream->cur_bit & 7) != 0)
279  {
280  ni_bs_writer_put(stream, 0, 8 - (stream->cur_bit & 7));
281  }
282 }
283 
284 /*!*****************************************************************************
285  * \brief copy bitstream data to dst
286  * Note: caller must ensure sufficient space in dst
287  *
288  * \param dst copy destination
289  * \param stream bitstream
290  * \return none
291  ******************************************************************************/
292 void ni_bs_writer_copy(uint8_t *dst, const ni_bitstream_writer_t *stream)
293 {
294  ni_data_chunk_t *chunk = stream->first;
295  uint8_t *p_dst = dst;
296  while (chunk && chunk->len)
297  {
298  memcpy(p_dst, chunk->data, chunk->len);
299  p_dst += chunk->len;
300  chunk = chunk->next;
301  }
302 }
303 
304 /*!*****************************************************************************
305  * \brief clear and reset bitstream
306  *
307  * \param stream bitstream
308  * \return none
309  ******************************************************************************/
311 {
312  ni_bs_writer_free_chunks(stream->first);
313  ni_bitstream_writer_init(stream);
314 }
315 
316 // the following is for bitstream get operations
317 
318 /*!*****************************************************************************
319  * \brief init a bitstream reader
320  * Note: bitstream_reader takes reading ownership of the data
321  *
322  * \param br bitstream reader
323  * \param data data to be parsed
324  * \param bit_size number of bits in the data
325  * \return none
326  ******************************************************************************/
327 void ni_bitstream_reader_init(ni_bitstream_reader_t *br, const uint8_t *data,
328  int bit_size)
329 {
330  if (!br || !data)
331  {
332  ni_log(NI_LOG_ERROR, "%s input is NULL !\n", __func__);
333  return;
334  }
335 
336  br->buf = data;
337  br->size_in_bits = bit_size;
338  br->byte_offset = 0;
339  br->bit_offset = 0;
340 }
341 
342 /*!*****************************************************************************
343  * \brief return the number of bits already parsed in stream
344  *
345  * \param br bitstream reader
346  * \return number of bits parsed
347  ******************************************************************************/
349 {
350  return br->byte_offset * 8 + br->bit_offset;
351 }
352 
353 /*!*****************************************************************************
354  * \brief return the number of bits left to parse in stream
355  *
356  * \param br bitstream reader
357  * \return number of bits left
358  ******************************************************************************/
360 {
361  return br->size_in_bits - ni_bs_reader_bits_count(br);
362 }
363 
364 /*!*****************************************************************************
365  * \brief skip a number of bits ahead in the bitstream reader
366  *
367  * \param br bitstream reader
368  * \param n number of bits to skip
369  * \return none
370  ******************************************************************************/
372 {
373  int new_offset = 8 * br->byte_offset + br->bit_offset + n;
374  if (new_offset > br->size_in_bits)
375  {
377  "%s: skip %d, current byte_offset "
378  "%d bit_offset %d, over total size %d, stop !\n",
379  __func__, n, br->byte_offset, br->bit_offset, br->size_in_bits);
380  return;
381  }
382 
383  br->byte_offset = new_offset / 8;
384  br->bit_offset = new_offset % 8;
385 }
386 
387 // read a single bit
389 {
390  uint8_t ret = 0;
391 
392  if (0 == br->bit_offset)
393  {
394  ret = (br->buf[br->byte_offset] >> 7);
395  br->bit_offset = 1;
396  } else
397  {
398  ret = ((br->buf[br->byte_offset] >> (7 - br->bit_offset)) & 0x1);
399  if (7 == br->bit_offset)
400  {
401  br->bit_offset = 0;
402  br->byte_offset++;
403  } else
404  {
405  br->bit_offset++;
406  }
407  }
408 
409  return ret;
410 }
411 
412 // read a single byte
414 {
415  uint8_t ret = 0;
416 
417  ret = (br->buf[br->byte_offset] << br->bit_offset);
418  br->byte_offset++;
419 
420  if (0 != br->bit_offset)
421  {
422  ret |= (br->buf[br->byte_offset] >> (8 - br->bit_offset));
423  }
424 
425  return ret;
426 }
427 
428 // read a 16 bit integer
430 {
431  uint16_t ret = 0;
432  int i;
433  int offset;
434  const uint8_t *src = NULL;
435 
436  src = &(br->buf[br->byte_offset]);
437  offset = 16 + br->bit_offset;
438 
439  for (i = 0; i < 2; i++)
440  {
441  offset -= 8;
442  ret |= ((uint16_t)src[i] << offset);
443  }
444 
445  if (0 != offset)
446  {
447  ret |= (src[2] >> (8 - offset));
448  }
449 
450  br->byte_offset += 2;
451 
452  return ret;
453 }
454 
455 // read <= 8 bits
457 {
458  uint8_t ret = 0;
459 
460  if (n > 8)
461  {
462  ni_log(NI_LOG_ERROR, "%s %d bits > 8, error!\n", __func__, n);
463  return 0;
464  }
465 
466  while (n)
467  {
468  ret = ((ret << 1) | ni_bitstream_get_1bit(br));
469  n--;
470  }
471  return ret;
472 }
473 
474 /*!*****************************************************************************
475  * \brief read bits (up to 32) from the bitstream reader, after reader init
476  *
477  * \param br bitstream reader
478  * \param n number of bits to read
479  * \return value read
480  ******************************************************************************/
482 {
483  uint32_t ret = 0;
484  int bits_left;
485 
486  if (n > 32)
487  {
488  ni_log(NI_LOG_ERROR, "%s %d bits > 32, not supported!\n", __func__, n);
489  return 0;
490  }
491 
492  if (n <= 0)
493  {
494  // return 0
495  } else if (n < 8)
496  {
497  ret = ni_bitstream_get_8bits_or_less(br, n);
498  } else if (8 == n)
499  {
500  ret = ni_bitstream_get_u8(br);
501  } else if (n > 8 && n < 16)
502  {
503  bits_left = n % 8;
504  ret = ((ni_bitstream_get_8bits_or_less(br, bits_left) << 8) |
505  ni_bitstream_get_u8(br));
506  } else if (16 == n)
507  {
508  ret = ni_bitstream_get_u16(br);
509  } else if (n > 16 && n < 24)
510  {
511  bits_left = n % 16;
512  ret = (ni_bitstream_get_8bits_or_less(br, bits_left) << 16);
513  ret |= (ni_bitstream_get_u8(br) << 8);
514  ret |= ni_bitstream_get_u8(br);
515  } else // 32 >= n >= 24
516  {
517  bits_left = n % 24;
518  ret = (ni_bitstream_get_8bits_or_less(br, bits_left) << 24);
519  ret |= (ni_bitstream_get_u8(br) << 16);
520  ret |= (ni_bitstream_get_u8(br) << 8);
521  ret |= ni_bitstream_get_u8(br);
522  }
523  return ret;
524 }
525 
526 /*!*****************************************************************************
527  * \brief read an unsigned Exp-Golomb code ue(v)
528  *
529  * \param br bitstream reader
530  * \return value read
531  ******************************************************************************/
533 {
534  uint32_t ret = 0;
535  int i = 0; // leading zero bits
536 
537  // count leading zero bits
538  while (0 == ni_bitstream_get_1bit(br) && i < 32)
539  {
540  i++;
541  }
542  if (i == 32)
543  return 0;
544  // calc get_bits(leading zero bits)
545  ret = ni_bs_reader_get_bits(br, i);
546  ret += (1U << i) - 1;
547  return ret;
548 }
549 
550 /*!*****************************************************************************
551  * \brief read a signed Exp-Golomb code se(v)
552  *
553  * \param br bitstream reader
554  * \return value read
555  ******************************************************************************/
557 {
558  // get ue
559  int32_t ret = ni_bs_reader_get_ue(br);
560 
561  // determine if it's odd or even
562  if (ret & 0x01) // odd: value before encode > 0
563  {
564  ret = (ret + 1) / 2;
565  } else // even: value before encode <= 0
566  {
567  ret = -(ret / 2);
568  }
569  return ret;
570 }
_ni_bitstream_writer_t::last
ni_data_chunk_t * last
Definition: ni_bitstream.h:84
ni_bitstream.h
Utility definitions to operate on bits in a bitstream.
_ni_bitstream_writer_t::len
uint32_t len
Definition: ni_bitstream.h:78
ni_bit_set_mask
const uint32_t ni_bit_set_mask[]
Definition: ni_bitstream.c:47
_ni_bitstream_writer_t::data
uint8_t data
Definition: ni_bitstream.h:87
_ni_bitstream_writer_t::first
ni_data_chunk_t * first
Definition: ni_bitstream.h:81
ni_bs_writer_put_ue
void ni_bs_writer_put_ue(ni_bitstream_writer_t *stream, uint32_t data)
write unsigned Exp-Golomb bit string to bitstream, 2^32-2 at most.
Definition: ni_bitstream.c:225
ni_bs_writer_clear
void ni_bs_writer_clear(ni_bitstream_writer_t *stream)
clear and reset bitstream
Definition: ni_bitstream.c:310
ni_data_chunk_t::data
uint8_t data[NI_DATA_CHUNK_SIZE]
Definition: ni_bitstream.h:65
_ni_bitstream_writer_t
Definition: ni_bitstream.h:75
ni_bitstream_writer_init
void ni_bitstream_writer_init(ni_bitstream_writer_t *stream)
init a bitstream writer
Definition: ni_bitstream.c:158
ni_bs_reader_get_bits
uint32_t ni_bs_reader_get_bits(ni_bitstream_reader_t *br, int n)
read bits (up to 32) from the bitstream reader, after reader init
Definition: ni_bitstream.c:481
ni_bs_writer_copy
void ni_bs_writer_copy(uint8_t *dst, const ni_bitstream_writer_t *stream)
copy bitstream data to dst Note: caller must ensure sufficient space in dst
Definition: ni_bitstream.c:292
ni_bs_reader_get_ue
uint32_t ni_bs_reader_get_ue(ni_bitstream_reader_t *br)
read an unsigned Exp-Golomb code ue(v)
Definition: ni_bitstream.c:532
ni_bitstream_get_u8
uint8_t ni_bitstream_get_u8(ni_bitstream_reader_t *br)
Definition: ni_bitstream.c:413
NI_LOG_ERROR
@ NI_LOG_ERROR
Definition: ni_log.h:60
_ni_bitstream_reader_t::buf
const uint8_t * buf
Definition: ni_bitstream.h:121
ni_bs_writer_put
void ni_bs_writer_put(ni_bitstream_writer_t *stream, uint32_t data, uint8_t bits)
write a specified number (<= 32) of bits to bitstream, buffer individual bits until a full byte is ma...
Definition: ni_bitstream.c:183
ni_bitstream_get_u16
uint16_t ni_bitstream_get_u16(ni_bitstream_reader_t *br)
Definition: ni_bitstream.c:429
_ni_bitstream_reader_t::bit_offset
int bit_offset
Definition: ni_bitstream.h:123
NI_DATA_CHUNK_SIZE
#define NI_DATA_CHUNK_SIZE
Definition: ni_bitstream.h:60
ni_bs_reader_bits_count
int ni_bs_reader_bits_count(ni_bitstream_reader_t *br)
return the number of bits already parsed in stream
Definition: ni_bitstream.c:348
ni_log
void ni_log(ni_log_level_t level, const char *fmt,...)
print log message using ni_log_callback
Definition: ni_log.c:183
ni_bitstream_get_1bit
uint8_t ni_bitstream_get_1bit(ni_bitstream_reader_t *br)
Definition: ni_bitstream.c:388
_ni_bitstream_writer_t::cur_bit
uint8_t cur_bit
Definition: ni_bitstream.h:90
ni_data_chunk_t::len
uint32_t len
Definition: ni_bitstream.h:68
ni_bs_writer_tell
uint64_t ni_bs_writer_tell(const ni_bitstream_writer_t *const stream)
return the number of bits written to bitstream so far
Definition: ni_bitstream.c:169
ni_data_chunk_t::next
struct ni_data_chunk_t * next
Definition: ni_bitstream.h:71
ni_bs_writer_put_se
void ni_bs_writer_put_se(ni_bitstream_writer_t *stream, int32_t data)
write signed Exp-Golomb bit string to bitstream
Definition: ni_bitstream.c:263
_ni_bitstream_reader_t::size_in_bits
int size_in_bits
Definition: ni_bitstream.h:124
ni_bs_writer_align_zero
void ni_bs_writer_align_zero(ni_bitstream_writer_t *stream)
align the bitstream with zero
Definition: ni_bitstream.c:276
ni_data_chunk_t
Definition: ni_bitstream.h:62
ni_bitstream_reader_init
void ni_bitstream_reader_init(ni_bitstream_reader_t *br, const uint8_t *data, int bit_size)
init a bitstream reader Note: bitstream_reader takes reading ownership of the data
Definition: ni_bitstream.c:327
ni_bs_reader_get_se
int32_t ni_bs_reader_get_se(ni_bitstream_reader_t *br)
read a signed Exp-Golomb code se(v)
Definition: ni_bitstream.c:556
ni_util.h
Utility definitions.
ni_bitstream_get_8bits_or_less
uint8_t ni_bitstream_get_8bits_or_less(ni_bitstream_reader_t *br, int n)
Definition: ni_bitstream.c:456
ni_bs_reader_skip_bits
void ni_bs_reader_skip_bits(ni_bitstream_reader_t *br, int n)
skip a number of bits ahead in the bitstream reader
Definition: ni_bitstream.c:371
_ni_bitstream_reader_t
Definition: ni_bitstream.h:119
ni_bs_reader_get_bits_left
int ni_bs_reader_get_bits_left(ni_bitstream_reader_t *br)
return the number of bits left to parse in stream
Definition: ni_bitstream.c:359
NI_LOG_DEBUG
@ NI_LOG_DEBUG
Definition: ni_log.h:62
_ni_bitstream_reader_t::byte_offset
int byte_offset
Definition: ni_bitstream.h:122