libxcoder  5.2.0
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  stream->data <<= 1;
196 
197  if (data & ni_bit_set_mask[bits])
198  {
199  stream->data |= 1;
200  }
201  stream->cur_bit++;
202 
203  // write the complete byte
204  if (stream->cur_bit == 8)
205  {
206  stream->cur_bit = 0;
207  ni_bs_writer_write_byte(stream, stream->data);
208  }
209  }
210 }
211 
212 /*!*****************************************************************************
213  * \brief write unsigned Exp-Golomb bit string to bitstream, 2^32-2 at most.
214  *
215  * \param stream bitstream
216  * \param data input data
217  * \return none
218  ******************************************************************************/
219 void ni_bs_writer_put_ue(ni_bitstream_writer_t *stream, uint32_t data)
220 {
221  unsigned data_log2 = ni_math_floor_log2(data + 1);
222  unsigned prefix = 1 << data_log2;
223  unsigned suffix = data + 1 - prefix;
224  unsigned num_bits = data_log2 * 2 + 1;
225  unsigned value = prefix | suffix;
226 
227  if (data > 0xFFFFFFFE) // 2^32-2 at most
228  {
229  ni_log(NI_LOG_ERROR, "%s error: data overflow: %u\n", __func__,
230  data);
231  return;
232  }
233 
234  if (num_bits <= 32)
235  {
236  ni_bs_writer_put(stream, value, num_bits);
237  }
238  else
239  {
240  // big endian
241  ni_bs_writer_put(stream, 0, num_bits - 32); // high (num_bits - 32) bits
242  ni_bs_writer_put(stream, value, 32); // low 32 bits
243  }
244 }
245 
246 /*!*****************************************************************************
247  * \brief write signed Exp-Golomb bit string to bitstream
248  *
249  * \param stream bitstream
250  * \param data input data
251  * \return none
252  ******************************************************************************/
253 void ni_bs_writer_put_se(ni_bitstream_writer_t *stream, int32_t data)
254 {
255  // map positive value to even and negative to odd value
256  uint32_t data_num = data <= 0 ? (-data) << 1 : (data << 1) - 1;
257  ni_bs_writer_put_ue(stream, data_num);
258 }
259 
260 /*!*****************************************************************************
261  * \brief align the bitstream with zero
262  *
263  * \param stream bitstream
264  * \return none
265  ******************************************************************************/
267 {
268  if ((stream->cur_bit & 7) != 0)
269  {
270  ni_bs_writer_put(stream, 0, 8 - (stream->cur_bit & 7));
271  }
272 }
273 
274 /*!*****************************************************************************
275  * \brief copy bitstream data to dst
276  * Note: caller must ensure sufficient space in dst
277  *
278  * \param dst copy destination
279  * \param stream bitstream
280  * \return none
281  ******************************************************************************/
282 void ni_bs_writer_copy(uint8_t *dst, const ni_bitstream_writer_t *stream)
283 {
284  ni_data_chunk_t *chunk = stream->first;
285  uint8_t *p_dst = dst;
286  while (chunk && chunk->len)
287  {
288  memcpy(p_dst, chunk->data, chunk->len);
289  p_dst += chunk->len;
290  chunk = chunk->next;
291  }
292 }
293 
294 /*!*****************************************************************************
295  * \brief clear and reset bitstream
296  *
297  * \param stream bitstream
298  * \return none
299  ******************************************************************************/
301 {
302  ni_bs_writer_free_chunks(stream->first);
303  ni_bitstream_writer_init(stream);
304 }
305 
306 // the following is for bitstream get operations
307 
308 /*!*****************************************************************************
309  * \brief init a bitstream reader
310  * Note: bitstream_reader takes reading ownership of the data
311  *
312  * \param br bitstream reader
313  * \param data data to be parsed
314  * \param bit_size number of bits in the data
315  * \return none
316  ******************************************************************************/
317 void ni_bitstream_reader_init(ni_bitstream_reader_t *br, const uint8_t *data,
318  int bit_size)
319 {
320  if (!br || !data)
321  {
322  ni_log(NI_LOG_ERROR, "%s input is NULL !\n", __func__);
323  return;
324  }
325 
326  br->buf = data;
327  br->size_in_bits = bit_size;
328  br->byte_offset = 0;
329  br->bit_offset = 0;
330 }
331 
332 /*!*****************************************************************************
333  * \brief return the number of bits already parsed in stream
334  *
335  * \param br bitstream reader
336  * \return number of bits parsed
337  ******************************************************************************/
339 {
340  return br->byte_offset * 8 + br->bit_offset;
341 }
342 
343 /*!*****************************************************************************
344  * \brief return the number of bits left to parse in stream
345  *
346  * \param br bitstream reader
347  * \return number of bits left
348  ******************************************************************************/
350 {
351  return br->size_in_bits - ni_bs_reader_bits_count(br);
352 }
353 
354 /*!*****************************************************************************
355  * \brief skip a number of bits ahead in the bitstream reader
356  *
357  * \param br bitstream reader
358  * \param n number of bits to skip
359  * \return none
360  ******************************************************************************/
362 {
363  int new_offset = 8 * br->byte_offset + br->bit_offset + n;
364  if (new_offset > br->size_in_bits)
365  {
367  "%s: skip %d, current byte_offset "
368  "%d bit_offset %d, over total size %d, stop !\n",
369  __func__, n, br->byte_offset, br->bit_offset, br->size_in_bits);
370  return;
371  }
372 
373  br->byte_offset = new_offset / 8;
374  br->bit_offset = new_offset % 8;
375 }
376 
377 // read a single bit
379 {
380  uint8_t ret = 0;
381 
382  if (0 == br->bit_offset)
383  {
384  ret = (br->buf[br->byte_offset] >> 7);
385  br->bit_offset = 1;
386  } else
387  {
388  ret = ((br->buf[br->byte_offset] >> (7 - br->bit_offset)) & 0x1);
389  if (7 == br->bit_offset)
390  {
391  br->bit_offset = 0;
392  br->byte_offset++;
393  } else
394  {
395  br->bit_offset++;
396  }
397  }
398 
399  return ret;
400 }
401 
402 // read a single byte
404 {
405  uint8_t ret = 0;
406 
407  ret = (br->buf[br->byte_offset] << br->bit_offset);
408  br->byte_offset++;
409 
410  if (0 != br->bit_offset)
411  {
412  ret |= (br->buf[br->byte_offset] >> (8 - br->bit_offset));
413  }
414 
415  return ret;
416 }
417 
418 // read a 16 bit integer
420 {
421  uint16_t ret = 0;
422  int i;
423  int offset;
424  const uint8_t *src = NULL;
425 
426  src = &(br->buf[br->byte_offset]);
427  offset = 16 + br->bit_offset;
428 
429  for (i = 0; i < 2; i++)
430  {
431  offset -= 8;
432  ret |= ((uint16_t)src[i] << offset);
433  }
434 
435  if (0 != offset)
436  {
437  ret |= (src[2] >> (8 - offset));
438  }
439 
440  br->byte_offset += 2;
441 
442  return ret;
443 }
444 
445 // read <= 8 bits
447 {
448  uint8_t ret = 0;
449 
450  if (n > 8)
451  {
452  ni_log(NI_LOG_ERROR, "%s %d bits > 8, error!\n", __func__, n);
453  return 0;
454  }
455 
456  while (n)
457  {
458  ret = ((ret << 1) | ni_bitstream_get_1bit(br));
459  n--;
460  }
461  return ret;
462 }
463 
464 /*!*****************************************************************************
465  * \brief read bits (up to 32) from the bitstream reader, after reader init
466  *
467  * \param br bitstream reader
468  * \param n number of bits to read
469  * \return value read
470  ******************************************************************************/
472 {
473  uint32_t ret = 0;
474  int bits_left;
475 
476  if (n > 32)
477  {
478  ni_log(NI_LOG_ERROR, "%s %d bits > 32, not supported!\n", __func__, n);
479  return 0;
480  }
481 
482  if (n <= 0)
483  {
484  // return 0
485  } else if (n < 8)
486  {
487  ret = ni_bitstream_get_8bits_or_less(br, n);
488  } else if (8 == n)
489  {
490  ret = ni_bitstream_get_u8(br);
491  } else if (n > 8 && n < 16)
492  {
493  bits_left = n % 8;
494  ret = ((ni_bitstream_get_8bits_or_less(br, bits_left) << 8) |
495  ni_bitstream_get_u8(br));
496  } else if (16 == n)
497  {
498  ret = ni_bitstream_get_u16(br);
499  } else if (n > 16 && n < 24)
500  {
501  bits_left = n % 16;
502  ret = (ni_bitstream_get_8bits_or_less(br, bits_left) << 16);
503  ret |= (ni_bitstream_get_u8(br) << 8);
504  ret |= ni_bitstream_get_u8(br);
505  } else // 32 >= n >= 24
506  {
507  bits_left = n % 24;
508  ret = (ni_bitstream_get_8bits_or_less(br, bits_left) << 24);
509  ret |= (ni_bitstream_get_u8(br) << 16);
510  ret |= (ni_bitstream_get_u8(br) << 8);
511  ret |= ni_bitstream_get_u8(br);
512  }
513  return ret;
514 }
515 
516 /*!*****************************************************************************
517  * \brief read an unsigned Exp-Golomb code ue(v)
518  *
519  * \param br bitstream reader
520  * \return value read
521  ******************************************************************************/
523 {
524  uint32_t ret = 0;
525  int i = 0; // leading zero bits
526 
527  // count leading zero bits
528  while (0 == ni_bitstream_get_1bit(br) && i < 32)
529  {
530  i++;
531  }
532  if (i == 32)
533  return 0;
534  // calc get_bits(leading zero bits)
535  ret = ni_bs_reader_get_bits(br, i);
536  ret += (1U << i) - 1;
537  return ret;
538 }
539 
540 /*!*****************************************************************************
541  * \brief read a signed Exp-Golomb code se(v)
542  *
543  * \param br bitstream reader
544  * \return value read
545  ******************************************************************************/
547 {
548  // get ue
549  int32_t ret = ni_bs_reader_get_ue(br);
550 
551  // determine if it's odd or even
552  if (ret & 0x01) // odd: value before encode > 0
553  {
554  ret = (ret + 1) / 2;
555  } else // even: value before encode <= 0
556  {
557  ret = -(ret / 2);
558  }
559  return ret;
560 }
_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:219
ni_bs_writer_clear
void ni_bs_writer_clear(ni_bitstream_writer_t *stream)
clear and reset bitstream
Definition: ni_bitstream.c:300
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:471
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:282
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:522
ni_bitstream_get_u8
uint8_t ni_bitstream_get_u8(ni_bitstream_reader_t *br)
Definition: ni_bitstream.c:403
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:419
_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:338
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:378
_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:253
_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:266
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:317
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:546
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:446
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:361
_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:349
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