libxcoder  3.5.1
ni_bitstream_logan.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_logan.c
35 *
36 * \brief Utility functions to operate on bits in a bitstream
37 *
38 *******************************************************************************/
39 
40 #include <stdio.h>
41 #include <string.h>
42 #include <assert.h>
43 #include "ni_util_logan.h"
44 #include "ni_bitstream_logan.h"
45 
46 // the following is for bitstream put operations
47 
48 const uint32_t ni_logan_bit_set_mask[] = {
49  0x00000001, 0x00000002, 0x00000004, 0x00000008, 0x00000010, 0x00000020,
50  0x00000040, 0x00000080, 0x00000100, 0x00000200, 0x00000400, 0x00000800,
51  0x00001000, 0x00002000, 0x00004000, 0x00008000, 0x00010000, 0x00020000,
52  0x00040000, 0x00080000, 0x00100000, 0x00200000, 0x00400000, 0x00800000,
53  0x01000000, 0x02000000, 0x04000000, 0x08000000, 0x10000000, 0x20000000,
54  0x40000000, 0x80000000};
55 
56 /*!*****************************************************************************
57  * \brief allocate a new bitstream data chunk
58  *
59  * \return pointer to the new chunk, or NULL.
60  ******************************************************************************/
61 static ni_data_chunk_t *ni_bs_writer_alloc_chunk(void)
62 {
63  ni_data_chunk_t *chunk = malloc(sizeof(ni_data_chunk_t));
64  if (chunk)
65  {
66  chunk->len = 0;
67  chunk->next = NULL;
68  }
69  return chunk;
70 }
71 
72 /*!*****************************************************************************
73  * \brief write a byte to bitstream
74  * Note: the stream must be byte-aligned already
75  *
76  * \param stream bitstream
77  * \param byte byte to write
78  * \return none
79  ******************************************************************************/
80 static void ni_bs_writer_write_byte(ni_bitstream_writer_t *stream, uint8_t byte)
81 {
82  assert(stream->cur_bit == 0);
83 
84  if (stream->last == NULL || stream->last->len == NI_DATA_CHUNK_SIZE)
85  {
86  // need to allocate a new chunk.
87  ni_data_chunk_t *new_chunk = ni_bs_writer_alloc_chunk();
88  if (!new_chunk)
89  {
90  ni_log(NI_LOG_ERROR, "%s error: no memory\n", __func__);
91  return;
92  }
93 
94  if (!stream->first)
95  stream->first = new_chunk;
96  if (stream->last)
97  stream->last->next = new_chunk;
98  stream->last = new_chunk;
99  }
100  if (stream->last->len >= NI_DATA_CHUNK_SIZE)
101  {
102  ni_log(NI_LOG_ERROR, "%s error: new_chunk size >= max %d\n", __func__,
104  return;
105  }
106 
107  stream->last->data[stream->last->len] = byte;
108  stream->last->len += 1;
109  stream->len += 1;
110 }
111 
112 /*!*****************************************************************************
113  * \brief free a list of chunks
114  *
115  * \param chunk start of the chunk list
116  * \return none
117  ******************************************************************************/
118 static void ni_bs_writer_free_chunks(ni_data_chunk_t *chunk)
119 {
120  while (chunk != NULL)
121  {
122  ni_data_chunk_t *next = chunk->next;
123  free(chunk);
124  chunk = next;
125  }
126 }
127 
128 static inline unsigned ni_logan_math_floor_log2(unsigned value)
129 {
130  unsigned result = 0;
131  assert(value > 0);
132  int i;
133 
134  for (i = 4; i >= 0; --i)
135  {
136  unsigned bits = 1ull << i;
137  unsigned shift = (value >= (1ull << bits)) ? bits : 0;
138  result += shift;
139  value >>= shift;
140  }
141 
142  return result;
143 }
144 
145 static inline unsigned ni_logan_math_ceil_log2(unsigned value)
146 {
147  assert(value > 0);
148 
149  // the ceil_log2 is just floor_log2 + 1, except for exact powers of 2.
150  return ni_logan_math_floor_log2(value) + ((value & (value - 1)) ? 1 : 0);
151 }
152 
153 /*!*****************************************************************************
154  * \brief init a bitstream writer
155  *
156  * \param stream bitstream
157  * \return none
158  ******************************************************************************/
160 {
161  memset(stream, 0, sizeof(ni_bitstream_writer_t));
162 }
163 
164 /*!*****************************************************************************
165  * \brief return the number of bits written to bitstream so far
166  *
167  * \param stream bitstream
168  * \return position
169  ******************************************************************************/
170 uint64_t ni_bs_writer_tell(const ni_bitstream_writer_t *const stream)
171 {
172  uint64_t position = stream->len;
173  return position * 8 + stream->cur_bit;
174 }
175 
176 /*!*****************************************************************************
177  * \brief write a specified number (<= 32) of bits to bitstream,
178  * buffer individual bits until a full byte is made
179  * \param stream bitstream
180  * \param data input data
181  * \param bits number of bits in data to write to stream, max 32
182  * \return none
183  ******************************************************************************/
184 void ni_bs_writer_put(ni_bitstream_writer_t *stream, uint32_t data,
185  uint8_t bits)
186 {
187  if (bits > 32)
188  {
189  ni_log(NI_LOG_ERROR, "%s error: too many bits to write: %u\n", __func__,
190  bits);
191  return;
192  }
193 
194  while (bits--)
195  {
196  stream->data <<= 1;
197 
198  if (data & ni_logan_bit_set_mask[bits])
199  {
200  stream->data |= 1;
201  }
202  stream->cur_bit++;
203 
204  // write the complete byte
205  if (stream->cur_bit == 8)
206  {
207  stream->cur_bit = 0;
208  ni_bs_writer_write_byte(stream, stream->data);
209  }
210  }
211 }
212 
213 /*!*****************************************************************************
214  * \brief write unsigned Exp-Golomb bit string to bitstream,
215  * 2^32-2 at most.
216  *
217  * \param stream bitstream
218  * \param data input data
219  * \return none
220  ******************************************************************************/
221 void ni_bs_writer_put_ue(ni_bitstream_writer_t *stream, uint32_t data)
222 {
223  unsigned data_log2 = ni_logan_math_floor_log2(data + 1);
224  unsigned prefix = 1 << data_log2;
225  unsigned suffix = data + 1 - prefix;
226  unsigned num_bits = data_log2 * 2 + 1;
227  unsigned value = prefix | suffix;
228  if (data > 0xFFFFFFFE) // 2^32-2 at most
229  {
230  ni_log(NI_LOG_ERROR, "%s error: data overflow: %u\n", __func__,
231  data);
232  return;
233  }
234 
235  if (num_bits <= 32)
236  {
237  ni_bs_writer_put(stream, value, num_bits);
238  }
239  else
240  {
241  // big endian
242  ni_bs_writer_put(stream, 0, num_bits - 32); // high (num_bits - 32) bits
243  ni_bs_writer_put(stream, value, 32); // low 32 bits
244  }
245 }
246 
247 /*!*****************************************************************************
248  * \brief write signed Exp-Golomb bit string to bitstream
249  *
250  * \param stream bitstream
251  * \param data input data
252  * \return none
253  ******************************************************************************/
255 {
256  // map positive value to even and negative to odd value
257  uint32_t data_num = data <= 0 ? (-data) << 1 : (data << 1) - 1;
258  ni_bs_writer_put_ue(stream, data_num);
259 }
260 
261 /*!*****************************************************************************
262  * \brief align the bitstream with zero
263  *
264  * \param stream bitstream
265  * \return none
266  ******************************************************************************/
268 {
269  if ((stream->cur_bit & 7) != 0)
270  {
271  ni_bs_writer_put(stream, 0, 8 - (stream->cur_bit & 7));
272  }
273 }
274 
275 /*!*****************************************************************************
276  * \brief copy bitstream data to dst
277  * Note: caller must ensure sufficient space in dst
278  *
279  * \param dst copy destination
280  * \param stream bitstream
281  * \return none
282  ******************************************************************************/
283 void ni_bs_writer_copy(uint8_t *dst, const ni_bitstream_writer_t *stream)
284 {
285  ni_data_chunk_t *chunk = stream->first;
286  uint8_t *p_dst = dst;
287  while (chunk && chunk->len)
288  {
289  memcpy(p_dst, chunk->data, chunk->len);
290  p_dst += chunk->len;
291  chunk = chunk->next;
292  }
293 }
294 
295 /*!*****************************************************************************
296  * \brief clear and reset bitstream
297  *
298  * \param stream bitstream
299  * \return none
300  ******************************************************************************/
302 {
303  ni_bs_writer_free_chunks(stream->first);
304  ni_bitstream_writer_init(stream);
305 }
306 
307 // the following is for bitstream get operations
308 
309 /*!*****************************************************************************
310  * \brief init a bitstream reader
311  * Note: bitstream_reader takes reading ownership of the data
312  *
313  * \param br bitstream reader
314  * \param data data to be parsed
315  * \param bit_size number of bits in the data
316  * \return none
317  ******************************************************************************/
318 void ni_bitstream_reader_init(ni_bitstream_reader_t *br, const uint8_t *data,
319  int bit_size)
320 {
321  if (!br || !data)
322  {
323  ni_log(NI_LOG_ERROR, "%s input is NULL !\n", __func__);
324  return;
325  }
326 
327  br->buf = data;
328  br->size_in_bits = bit_size;
329  br->byte_offset = 0;
330  br->bit_offset = 0;
331 }
332 
333 /*!*****************************************************************************
334  * \brief return the number of bits already parsed in stream
335  *
336  * \param br bitstream reader
337  * \return number of bits parsed
338  ******************************************************************************/
340 {
341  return br->byte_offset * 8 + br->bit_offset;
342 }
343 
344 /*!*****************************************************************************
345  * \brief return the number of bits left to parse in stream
346  *
347  * \param br bitstream reader
348  * \return number of bits left
349  ******************************************************************************/
351 {
352  return br->size_in_bits - ni_bs_reader_bits_count(br);
353 }
354 
355 /*!*****************************************************************************
356  * \brief skip a number of bits ahead in the bitstream reader
357  *
358  * \param br bitstream reader
359  * \param n number of bits to skip
360  * \return none
361  ******************************************************************************/
363 {
364  int new_offset = 8 * br->byte_offset + br->bit_offset + n;
365  if (new_offset > br->size_in_bits)
366  {
368  "%s: skip %d, current byte_offset "
369  "%d bit_offset %d, over total size %d, stop !\n",
370  __func__, n, br->byte_offset, br->bit_offset, br->size_in_bits);
371  return;
372  }
373 
374  br->byte_offset = new_offset / 8;
375  br->bit_offset = new_offset % 8;
376 }
377 
378 // read a single bit
380 {
381  uint8_t ret = 0;
382 
383  if (0 == br->bit_offset)
384  {
385  ret = (br->buf[br->byte_offset] >> 7);
386  br->bit_offset = 1;
387  } else
388  {
389  ret = ((br->buf[br->byte_offset] >> (7 - br->bit_offset)) & 0x1);
390  if (7 == br->bit_offset)
391  {
392  br->bit_offset = 0;
393  br->byte_offset++;
394  } else
395  {
396  br->bit_offset++;
397  }
398  }
399 
400  return ret;
401 }
402 
403 // read a single byte
405 {
406  uint8_t ret = 0;
407 
408  ret = (br->buf[br->byte_offset] << br->bit_offset);
409  br->byte_offset++;
410 
411  if (0 != br->bit_offset)
412  {
413  ret |= (br->buf[br->byte_offset] >> (8 - br->bit_offset));
414  }
415 
416  return ret;
417 }
418 
419 // read a 16 bit integer
421 {
422  uint16_t ret = 0;
423  int i;
424  int offset;
425  const uint8_t *src = NULL;
426 
427  src = &(br->buf[br->byte_offset]);
428  offset = 16 + br->bit_offset;
429 
430  for (i = 0; i < 2; i++)
431  {
432  offset -= 8;
433  ret |= ((uint16_t)src[i] << offset);
434  }
435 
436  if (0 != offset)
437  {
438  ret |= (src[2] >> (8 - offset));
439  }
440 
441  br->byte_offset += 2;
442 
443  return ret;
444 }
445 
446 // read <= 8 bits
448 {
449  uint8_t ret = 0;
450 
451  if (n > 8)
452  {
453  ni_log(NI_LOG_ERROR, "%s %d bits > 8, error!\n", __func__, n);
454  return 0;
455  }
456 
457  while (n)
458  {
459  ret = ((ret << 1) | ni_logan_bitstream_get_1bit(br));
460  n--;
461  }
462  return ret;
463 }
464 
465 /*!*****************************************************************************
466  * \brief read bits (up to 32) from the bitstream reader, after reader init
467  *
468  * \param br bitstream reader
469  * \param n number of bits to read
470  * \return value read
471  ******************************************************************************/
473 {
474  uint32_t ret = 0;
475  int bits_left;
476 
477  if (n > 32)
478  {
479  ni_log(NI_LOG_ERROR, "%s %d bits > 32, not supported!\n", __func__, n);
480  return 0;
481  }
482 
483  if (n <= 0)
484  {
485  // return 0
486  } else if (n < 8)
487  {
489  } else if (8 == n)
490  {
491  ret = ni_logan_bitstream_get_u8(br);
492  } else if (n > 8 && n < 16)
493  {
494  bits_left = n % 8;
495  ret = ((ni_logan_bitstream_get_8bits_or_less(br, bits_left) << 8) |
497  } else if (16 == n)
498  {
499  ret = ni_logan_bitstream_get_u16(br);
500  } else if (n > 16 && n < 24)
501  {
502  bits_left = n % 16;
503  ret = (ni_logan_bitstream_get_8bits_or_less(br, bits_left) << 16);
504  ret |= (ni_logan_bitstream_get_u8(br) << 8);
505  ret |= ni_logan_bitstream_get_u8(br);
506  } else // 32 >= n >= 24
507  {
508  bits_left = n % 24;
509  ret = (ni_logan_bitstream_get_8bits_or_less(br, bits_left) << 24);
510  ret |= (ni_logan_bitstream_get_u8(br) << 16);
511  ret |= (ni_logan_bitstream_get_u8(br) << 8);
512  ret |= ni_logan_bitstream_get_u8(br);
513  }
514  return ret;
515 }
516 
517 /*!*****************************************************************************
518  * \brief read an unsigned Exp-Golomb code ue(v)
519  *
520  * \param br bitstream reader
521  * \return value read
522  ******************************************************************************/
524 {
525  uint32_t ret = 0;
526  int i = 0; // leading zero bits
527 
528  // count leading zero bits
529  while (0 == ni_logan_bitstream_get_1bit(br) && i < 32)
530  {
531  i++;
532  }
533  if (i == 32)
534  return 0;
535  // calc get_bits(leading zero bits)
536  ret = ni_bs_reader_get_bits(br, i);
537  ret += (1U << i) - 1;
538  return ret;
539 }
540 
541 /*!*****************************************************************************
542  * \brief read a signed Exp-Golomb code se(v)
543  *
544  * \param br bitstream reader
545  * \return value read
546  ******************************************************************************/
548 {
549  // get ue
550  int32_t ret = ni_bs_reader_get_ue(br);
551 
552  // determine if it's odd or even
553  if (ret & 0x01) // odd: value before encode > 0
554  {
555  ret = (ret + 1) / 2;
556  } else // even: value before encode <= 0
557  {
558  ret = -(ret / 2);
559  }
560  return ret;
561 }
void ni_logan_bitstream_put_se(ni_bitstream_writer_t *stream, int32_t data)
write signed Exp-Golomb bit string to bitstream
int ni_bs_reader_bits_count(ni_bitstream_reader_t *br)
return the number of bits already parsed in stream
const uint32_t ni_logan_bit_set_mask[]
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.
void ni_bitstream_writer_init(ni_bitstream_writer_t *stream)
init a bitstream writer
uint16_t ni_logan_bitstream_get_u16(ni_bitstream_reader_t *br)
uint32_t ni_bs_reader_get_ue(ni_bitstream_reader_t *br)
read an unsigned Exp-Golomb code ue(v)
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
uint8_t ni_logan_bitstream_get_8bits_or_less(ni_bitstream_reader_t *br, int n)
int32_t ni_bs_reader_get_se(ni_bitstream_reader_t *br)
read a signed Exp-Golomb code se(v)
void ni_bs_writer_align_zero(ni_bitstream_writer_t *stream)
align the bitstream with zero
uint8_t ni_logan_bitstream_get_u8(ni_bitstream_reader_t *br)
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
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
void ni_bs_writer_clear(ni_bitstream_writer_t *stream)
clear and reset bitstream
uint64_t ni_bs_writer_tell(const ni_bitstream_writer_t *const stream)
return the number of bits written to bitstream so far
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...
int ni_bs_reader_get_bits_left(ni_bitstream_reader_t *br)
return the number of bits left to parse in stream
void ni_bs_reader_skip_bits(ni_bitstream_reader_t *br, int n)
skip a number of bits ahead in the bitstream reader
uint8_t ni_logan_bitstream_get_1bit(ni_bitstream_reader_t *br)
Utility functions to operate on bits in a bitstream.
#define NI_DATA_CHUNK_SIZE
void ni_log(ni_log_level_t level, const char *fmt,...)
print log message using ni_log_callback
Definition: ni_log_logan.c:120
@ NI_LOG_DEBUG
Definition: ni_log_logan.h:66
@ NI_LOG_ERROR
Definition: ni_log_logan.h:64
Exported utility routines definition.
ni_data_chunk_t * first
ni_data_chunk_t * last
struct ni_data_chunk_t * next
uint8_t data[NI_DATA_CHUNK_SIZE]