FFmpeg
opus_rc.c
Go to the documentation of this file.
1 /*
2  * Copyright (c) 2012 Andrew D'Addesio
3  * Copyright (c) 2013-2014 Mozilla Corporation
4  * Copyright (c) 2017 Rostislav Pehlivanov <atomnuker@gmail.com>
5  *
6  * This file is part of FFmpeg.
7  *
8  * FFmpeg is free software; you can redistribute it and/or
9  * modify it under the terms of the GNU Lesser General Public
10  * License as published by the Free Software Foundation; either
11  * version 2.1 of the License, or (at your option) any later version.
12  *
13  * FFmpeg is distributed in the hope that it will be useful,
14  * but WITHOUT ANY WARRANTY; without even the implied warranty of
15  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
16  * Lesser General Public License for more details.
17  *
18  * You should have received a copy of the GNU Lesser General Public
19  * License along with FFmpeg; if not, write to the Free Software
20  * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
21  */
22 
23 #include "opus_rc.h"
24 
25 #define OPUS_RC_BITS 32
26 #define OPUS_RC_SYM 8
27 #define OPUS_RC_CEIL ((1 << OPUS_RC_SYM) - 1)
28 #define OPUS_RC_TOP (1u << 31)
29 #define OPUS_RC_BOT (OPUS_RC_TOP >> OPUS_RC_SYM)
30 #define OPUS_RC_SHIFT (OPUS_RC_BITS - OPUS_RC_SYM - 1)
31 
33 {
34  const int cb = cbuf >> OPUS_RC_SYM, mb = (OPUS_RC_CEIL + cb) & OPUS_RC_CEIL;
35  if (cbuf == OPUS_RC_CEIL) {
36  rc->ext++;
37  return;
38  }
39  rc->rng_cur[0] = rc->rem + cb;
40  rc->rng_cur += (rc->rem >= 0);
41  for (; rc->ext > 0; rc->ext--)
42  *rc->rng_cur++ = mb;
43  av_assert0(rc->rng_cur < rc->rb.position);
44  rc->rem = cbuf & OPUS_RC_CEIL; /* Propagate */
45 }
46 
48 {
49  while (rc->range <= OPUS_RC_BOT) {
50  rc->value = ((rc->value << OPUS_RC_SYM) | (get_bits(&rc->gb, OPUS_RC_SYM) ^ OPUS_RC_CEIL)) & (OPUS_RC_TOP - 1);
51  rc->range <<= OPUS_RC_SYM;
52  rc->total_bits += OPUS_RC_SYM;
53  }
54 }
55 
57 {
58  while (rc->range <= OPUS_RC_BOT) {
60  rc->value = (rc->value << OPUS_RC_SYM) & (OPUS_RC_TOP - 1);
61  rc->range <<= OPUS_RC_SYM;
62  rc->total_bits += OPUS_RC_SYM;
63  }
64 }
65 
67  uint32_t low, uint32_t high,
68  uint32_t total)
69 {
70  rc->value -= scale * (total - high);
71  rc->range = low ? scale * (high - low)
72  : rc->range - scale * (total - high);
74 }
75 
76 /* Main encoding function, this needs to go fast */
77 static av_always_inline void opus_rc_enc_update(OpusRangeCoder *rc, uint32_t b, uint32_t p,
78  uint32_t p_tot, const int ptwo)
79 {
80  uint32_t rscaled, cnd = !!b;
81  if (ptwo) /* Whole function is inlined so hopefully branch is optimized out */
82  rscaled = rc->range >> ff_log2(p_tot);
83  else
84  rscaled = rc->range/p_tot;
85  rc->value += cnd*(rc->range - rscaled*(p_tot - b));
86  rc->range = (!cnd)*(rc->range - rscaled*(p_tot - p)) + cnd*rscaled*(p - b);
88 }
89 
90 uint32_t ff_opus_rc_dec_cdf(OpusRangeCoder *rc, const uint16_t *cdf)
91 {
92  unsigned int k, scale, total, symbol, low, high;
93 
94  total = *cdf++;
95 
96  scale = rc->range / total;
97  symbol = rc->value / scale + 1;
98  symbol = total - FFMIN(symbol, total);
99 
100  for (k = 0; cdf[k] <= symbol; k++);
101  high = cdf[k];
102  low = k ? cdf[k-1] : 0;
103 
104  opus_rc_dec_update(rc, scale, low, high, total);
105 
106  return k;
107 }
108 
109 void ff_opus_rc_enc_cdf(OpusRangeCoder *rc, int val, const uint16_t *cdf)
110 {
111  opus_rc_enc_update(rc, (!!val)*cdf[val], cdf[val + 1], cdf[0], 1);
112 }
113 
114 uint32_t ff_opus_rc_dec_log(OpusRangeCoder *rc, uint32_t bits)
115 {
116  uint32_t k, scale;
117  scale = rc->range >> bits; // in this case, scale = symbol
118 
119  if (rc->value >= scale) {
120  rc->value -= scale;
121  rc->range -= scale;
122  k = 0;
123  } else {
124  rc->range = scale;
125  k = 1;
126  }
128  return k;
129 }
130 
131 void ff_opus_rc_enc_log(OpusRangeCoder *rc, int val, uint32_t bits)
132 {
133  bits = (1 << bits) - 1;
134  opus_rc_enc_update(rc, (!!val)*bits, bits + !!val, bits + 1, 1);
135 }
136 
137 /**
138  * CELT: read 1-25 raw bits at the end of the frame, backwards byte-wise
139  */
140 uint32_t ff_opus_rc_get_raw(OpusRangeCoder *rc, uint32_t count)
141 {
142  uint32_t value = 0;
143 
144  while (rc->rb.bytes && rc->rb.cachelen < count) {
145  rc->rb.cacheval |= *--rc->rb.position << rc->rb.cachelen;
146  rc->rb.cachelen += 8;
147  rc->rb.bytes--;
148  }
149 
150  value = av_mod_uintp2(rc->rb.cacheval, count);
151  rc->rb.cacheval >>= count;
152  rc->rb.cachelen -= count;
153  rc->total_bits += count;
154 
155  return value;
156 }
157 
158 /**
159  * CELT: write 0 - 31 bits to the rawbits buffer
160  */
161 void ff_opus_rc_put_raw(OpusRangeCoder *rc, uint32_t val, uint32_t count)
162 {
163  const int to_write = FFMIN(32 - rc->rb.cachelen, count);
164 
165  rc->total_bits += count;
166  rc->rb.cacheval |= av_mod_uintp2(val, to_write) << rc->rb.cachelen;
167  rc->rb.cachelen = (rc->rb.cachelen + to_write) % 32;
168 
169  if (!rc->rb.cachelen && count) {
170  AV_WB32((uint8_t *)rc->rb.position, rc->rb.cacheval);
171  rc->rb.bytes += 4;
172  rc->rb.position -= 4;
173  rc->rb.cachelen = count - to_write;
174  rc->rb.cacheval = av_mod_uintp2(val >> to_write, rc->rb.cachelen);
175  av_assert0(rc->rng_cur < rc->rb.position);
176  }
177 }
178 
179 /**
180  * CELT: read a uniform distribution
181  */
182 uint32_t ff_opus_rc_dec_uint(OpusRangeCoder *rc, uint32_t size)
183 {
184  uint32_t bits, k, scale, total;
185 
186  bits = opus_ilog(size - 1);
187  total = (bits > 8) ? ((size - 1) >> (bits - 8)) + 1 : size;
188 
189  scale = rc->range / total;
190  k = rc->value / scale + 1;
191  k = total - FFMIN(k, total);
192  opus_rc_dec_update(rc, scale, k, k + 1, total);
193 
194  if (bits > 8) {
195  k = k << (bits - 8) | ff_opus_rc_get_raw(rc, bits - 8);
196  return FFMIN(k, size - 1);
197  } else
198  return k;
199 }
200 
201 /**
202  * CELT: write a uniformly distributed integer
203  */
204 void ff_opus_rc_enc_uint(OpusRangeCoder *rc, uint32_t val, uint32_t size)
205 {
206  const int ps = FFMAX(opus_ilog(size - 1) - 8, 0);
207  opus_rc_enc_update(rc, val >> ps, (val >> ps) + 1, ((size - 1) >> ps) + 1, 0);
208  ff_opus_rc_put_raw(rc, val, ps);
209 }
210 
212 {
213  /* Use a probability of 3 up to itheta=8192 and then use 1 after */
214  uint32_t k, scale, symbol, total = (k0+1)*3 + k0;
215  scale = rc->range / total;
216  symbol = rc->value / scale + 1;
217  symbol = total - FFMIN(symbol, total);
218 
219  k = (symbol < (k0+1)*3) ? symbol/3 : symbol - (k0+1)*2;
220 
221  opus_rc_dec_update(rc, scale, (k <= k0) ? 3*(k+0) : (k-1-k0) + 3*(k0+1),
222  (k <= k0) ? 3*(k+1) : (k-0-k0) + 3*(k0+1), total);
223  return k;
224 }
225 
226 void ff_opus_rc_enc_uint_step(OpusRangeCoder *rc, uint32_t val, int k0)
227 {
228  const uint32_t a = val <= k0, b = 2*a + 1;
229  k0 = (k0 + 1) << 1;
230  val = b*(val + k0) - 3*a*k0;
231  opus_rc_enc_update(rc, val, val + b, (k0 << 1) - 1, 0);
232 }
233 
235 {
236  uint32_t k, scale, symbol, total, low, center;
237 
238  total = ((qn>>1) + 1) * ((qn>>1) + 1);
239  scale = rc->range / total;
240  center = rc->value / scale + 1;
241  center = total - FFMIN(center, total);
242 
243  if (center < total >> 1) {
244  k = (ff_sqrt(8 * center + 1) - 1) >> 1;
245  low = k * (k + 1) >> 1;
246  symbol = k + 1;
247  } else {
248  k = (2*(qn + 1) - ff_sqrt(8*(total - center - 1) + 1)) >> 1;
249  low = total - ((qn + 1 - k) * (qn + 2 - k) >> 1);
250  symbol = qn + 1 - k;
251  }
252 
253  opus_rc_dec_update(rc, scale, low, low + symbol, total);
254 
255  return k;
256 }
257 
258 void ff_opus_rc_enc_uint_tri(OpusRangeCoder *rc, uint32_t k, int qn)
259 {
260  uint32_t symbol, low, total;
261 
262  total = ((qn>>1) + 1) * ((qn>>1) + 1);
263 
264  if (k <= qn >> 1) {
265  low = k * (k + 1) >> 1;
266  symbol = k + 1;
267  } else {
268  low = total - ((qn + 1 - k) * (qn + 2 - k) >> 1);
269  symbol = qn + 1 - k;
270  }
271 
272  opus_rc_enc_update(rc, low, low + symbol, total, 0);
273 }
274 
275 int ff_opus_rc_dec_laplace(OpusRangeCoder *rc, uint32_t symbol, int decay)
276 {
277  /* extends the range coder to model a Laplace distribution */
278  int value = 0;
279  uint32_t scale, low = 0, center;
280 
281  scale = rc->range >> 15;
282  center = rc->value / scale + 1;
283  center = (1 << 15) - FFMIN(center, 1 << 15);
284 
285  if (center >= symbol) {
286  value++;
287  low = symbol;
288  symbol = 1 + ((32768 - 32 - symbol) * (16384-decay) >> 15);
289 
290  while (symbol > 1 && center >= low + 2 * symbol) {
291  value++;
292  symbol *= 2;
293  low += symbol;
294  symbol = (((symbol - 2) * decay) >> 15) + 1;
295  }
296 
297  if (symbol <= 1) {
298  int distance = (center - low) >> 1;
299  value += distance;
300  low += 2 * distance;
301  }
302 
303  if (center < low + symbol)
304  value *= -1;
305  else
306  low += symbol;
307  }
308 
309  opus_rc_dec_update(rc, scale, low, FFMIN(low + symbol, 32768), 32768);
310 
311  return value;
312 }
313 
314 void ff_opus_rc_enc_laplace(OpusRangeCoder *rc, int *value, uint32_t symbol, int decay)
315 {
316  uint32_t low = symbol;
317  int i = 1, val = FFABS(*value), pos = *value > 0;
318  if (!val) {
319  opus_rc_enc_update(rc, 0, symbol, 1 << 15, 1);
320  return;
321  }
322  symbol = ((32768 - 32 - symbol)*(16384 - decay)) >> 15;
323  for (; i < val && symbol; i++) {
324  low += (symbol << 1) + 2;
325  symbol = (symbol*decay) >> 14;
326  }
327  if (symbol) {
328  low += (++symbol)*pos;
329  } else {
330  const int distance = FFMIN(val - i, (((32768 - low) - !pos) >> 1) - 1);
331  low += pos + (distance << 1);
332  symbol = FFMIN(1, 32768 - low);
333  *value = FFSIGN(*value)*(distance + i);
334  }
335  opus_rc_enc_update(rc, low, low + symbol, 1 << 15, 1);
336 }
337 
338 int ff_opus_rc_dec_init(OpusRangeCoder *rc, const uint8_t *data, int size)
339 {
340  int ret = init_get_bits8(&rc->gb, data, size);
341  if (ret < 0)
342  return ret;
343 
344  rc->range = 128;
345  rc->value = 127 - get_bits(&rc->gb, 7);
346  rc->total_bits = 9;
348 
349  return 0;
350 }
351 
352 void ff_opus_rc_dec_raw_init(OpusRangeCoder *rc, const uint8_t *rightend, uint32_t bytes)
353 {
354  rc->rb.position = rightend;
355  rc->rb.bytes = bytes;
356  rc->rb.cachelen = 0;
357  rc->rb.cacheval = 0;
358 }
359 
360 void ff_opus_rc_enc_end(OpusRangeCoder *rc, uint8_t *dst, int size)
361 {
362  int rng_bytes, bits = OPUS_RC_BITS - opus_ilog(rc->range);
363  uint32_t mask = (OPUS_RC_TOP - 1) >> bits;
364  uint32_t end = (rc->value + mask) & ~mask;
365 
366  if ((end | mask) >= rc->value + rc->range) {
367  bits++;
368  mask >>= 1;
369  end = (rc->value + mask) & ~mask;
370  }
371 
372  /* Finish what's left */
373  while (bits > 0) {
375  end = (end << OPUS_RC_SYM) & (OPUS_RC_TOP - 1);
376  bits -= OPUS_RC_SYM;
377  }
378 
379  /* Flush out anything left or marked */
380  if (rc->rem >= 0 || rc->ext > 0)
381  opus_rc_enc_carryout(rc, 0);
382 
383  rng_bytes = rc->rng_cur - rc->buf;
384  memcpy(dst, rc->buf, rng_bytes);
385 
386  rc->waste = size*8 - (rc->rb.bytes*8 + rc->rb.cachelen) - rng_bytes*8;
387 
388  /* Put the rawbits part, if any */
389  if (rc->rb.bytes || rc->rb.cachelen) {
390  int i, lap;
391  uint8_t *rb_src, *rb_dst;
392  ff_opus_rc_put_raw(rc, 0, 32 - rc->rb.cachelen);
393  rb_src = rc->buf + OPUS_MAX_FRAME_SIZE + 12 - rc->rb.bytes;
394  rb_dst = dst + FFMAX(size - rc->rb.bytes, 0);
395  lap = &dst[rng_bytes] - rb_dst;
396  for (i = 0; i < lap; i++)
397  rb_dst[i] |= rb_src[i];
398  memcpy(&rb_dst[lap], &rb_src[lap], FFMAX(rc->rb.bytes - lap, 0));
399  }
400 }
401 
403 {
404  rc->value = 0;
405  rc->range = OPUS_RC_TOP;
406  rc->total_bits = OPUS_RC_BITS + 1;
407  rc->rem = -1;
408  rc->ext = 0;
409  rc->rng_cur = rc->buf;
411 }
ff_opus_rc_enc_cdf
void ff_opus_rc_enc_cdf(OpusRangeCoder *rc, int val, const uint16_t *cdf)
Definition: opus_rc.c:109
cb
static double cb(void *priv, double x, double y)
Definition: vf_geq.c:239
opus_ilog
#define opus_ilog(i)
Definition: opus_rc.h:30
ff_opus_rc_get_raw
uint32_t ff_opus_rc_get_raw(OpusRangeCoder *rc, uint32_t count)
CELT: read 1-25 raw bits at the end of the frame, backwards byte-wise.
Definition: opus_rc.c:140
ff_opus_rc_enc_uint
void ff_opus_rc_enc_uint(OpusRangeCoder *rc, uint32_t val, uint32_t size)
CELT: write a uniformly distributed integer.
Definition: opus_rc.c:204
OPUS_MAX_FRAME_SIZE
#define OPUS_MAX_FRAME_SIZE
Definition: opus.h:28
av_mod_uintp2
#define av_mod_uintp2
Definition: common.h:122
OpusRangeCoder::rem
int rem
Definition: opus_rc.h:50
b
#define b
Definition: input.c:41
data
const char data[16]
Definition: mxf.c:146
FFMAX
#define FFMAX(a, b)
Definition: macros.h:47
RawBitsContext::position
const uint8_t * position
Definition: opus_rc.h:33
opus_rc_enc_carryout
static av_always_inline void opus_rc_enc_carryout(OpusRangeCoder *rc, int cbuf)
Definition: opus_rc.c:32
OpusRangeCoder::ext
int ext
Definition: opus_rc.h:49
get_bits
static unsigned int get_bits(GetBitContext *s, int n)
Read 1-25 bits.
Definition: get_bits.h:325
FFSIGN
#define FFSIGN(a)
Definition: common.h:65
val
static double val(void *priv, double ch)
Definition: aeval.c:77
scale
static av_always_inline float scale(float x, float s)
Definition: vf_v360.c:1389
opus_rc_dec_update
static av_always_inline void opus_rc_dec_update(OpusRangeCoder *rc, uint32_t scale, uint32_t low, uint32_t high, uint32_t total)
Definition: opus_rc.c:66
ff_sqrt
#define ff_sqrt
Definition: mathops.h:218
OpusRangeCoder::buf
uint8_t buf[OPUS_MAX_FRAME_SIZE+12]
Definition: opus_rc.h:47
init_get_bits8
static int init_get_bits8(GetBitContext *s, const uint8_t *buffer, int byte_size)
Initialize GetBitContext.
Definition: get_bits.h:524
OpusRangeCoder::rng_cur
uint8_t * rng_cur
Definition: opus_rc.h:48
mask
static const uint16_t mask[17]
Definition: lzw.c:38
ff_opus_rc_dec_uint
uint32_t ff_opus_rc_dec_uint(OpusRangeCoder *rc, uint32_t size)
CELT: read a uniform distribution.
Definition: opus_rc.c:182
RawBitsContext::cachelen
uint32_t cachelen
Definition: opus_rc.h:35
bits
uint8_t bits
Definition: vp3data.h:128
av_assert0
#define av_assert0(cond)
assert() equivalent, that is always enabled.
Definition: avassert.h:37
ff_opus_rc_enc_uint_tri
void ff_opus_rc_enc_uint_tri(OpusRangeCoder *rc, uint32_t k, int qn)
Definition: opus_rc.c:258
OPUS_RC_SYM
#define OPUS_RC_SYM
Definition: opus_rc.c:26
FFABS
#define FFABS(a)
Absolute value, Note, INT_MIN / INT64_MIN result in undefined behavior as they are not representable ...
Definition: common.h:64
OpusRangeCoder::range
uint32_t range
Definition: opus_rc.h:42
OPUS_RC_CEIL
#define OPUS_RC_CEIL
Definition: opus_rc.c:27
OpusRangeCoder::value
uint32_t value
Definition: opus_rc.h:43
RawBitsContext::bytes
uint32_t bytes
Definition: opus_rc.h:34
ff_log2
#define ff_log2
Definition: intmath.h:51
opus_rc_enc_normalize
static av_always_inline void opus_rc_enc_normalize(OpusRangeCoder *rc)
Definition: opus_rc.c:56
OPUS_RC_BOT
#define OPUS_RC_BOT
Definition: opus_rc.c:29
ff_opus_rc_dec_uint_tri
uint32_t ff_opus_rc_dec_uint_tri(OpusRangeCoder *rc, int qn)
Definition: opus_rc.c:234
AV_WB32
#define AV_WB32(p, v)
Definition: intreadwrite.h:419
ff_opus_rc_enc_init
void ff_opus_rc_enc_init(OpusRangeCoder *rc)
Definition: opus_rc.c:402
size
int size
Definition: twinvq_data.h:10344
OpusRangeCoder
Definition: opus_rc.h:39
ff_opus_rc_dec_init
int ff_opus_rc_dec_init(OpusRangeCoder *rc, const uint8_t *data, int size)
Definition: opus_rc.c:338
a
The reader does not expect b to be semantically here and if the code is changed by maybe adding a a division or other the signedness will almost certainly be mistaken To avoid this confusion a new type was SUINT is the C unsigned type but it holds a signed int to use the same example SUINT a
Definition: undefined.txt:41
mb
#define mb
Definition: vf_colormatrix.c:101
ff_opus_rc_dec_cdf
uint32_t ff_opus_rc_dec_cdf(OpusRangeCoder *rc, const uint16_t *cdf)
Definition: opus_rc.c:90
ff_opus_rc_enc_uint_step
void ff_opus_rc_enc_uint_step(OpusRangeCoder *rc, uint32_t val, int k0)
Definition: opus_rc.c:226
ff_opus_rc_dec_laplace
int ff_opus_rc_dec_laplace(OpusRangeCoder *rc, uint32_t symbol, int decay)
Definition: opus_rc.c:275
i
#define i(width, name, range_min, range_max)
Definition: cbs_h2645.c:269
ff_opus_rc_enc_laplace
void ff_opus_rc_enc_laplace(OpusRangeCoder *rc, int *value, uint32_t symbol, int decay)
Definition: opus_rc.c:314
OPUS_RC_BITS
#define OPUS_RC_BITS
Definition: opus_rc.c:25
OpusRangeCoder::waste
int waste
Definition: opus_rc.h:53
ff_opus_rc_put_raw
void ff_opus_rc_put_raw(OpusRangeCoder *rc, uint32_t val, uint32_t count)
CELT: write 0 - 31 bits to the rawbits buffer.
Definition: opus_rc.c:161
ff_opus_rc_dec_raw_init
void ff_opus_rc_dec_raw_init(OpusRangeCoder *rc, const uint8_t *rightend, uint32_t bytes)
Definition: opus_rc.c:352
av_always_inline
#define av_always_inline
Definition: attributes.h:49
value
it s the only field you need to keep assuming you have a context There is some magic you don t need to care about around this just let it vf default value
Definition: writing_filters.txt:86
FFMIN
#define FFMIN(a, b)
Definition: macros.h:49
OPUS_RC_TOP
#define OPUS_RC_TOP
Definition: opus_rc.c:28
OpusRangeCoder::gb
GetBitContext gb
Definition: opus_rc.h:40
ret
ret
Definition: filter_design.txt:187
pos
unsigned int pos
Definition: spdifenc.c:413
ff_opus_rc_dec_uint_step
uint32_t ff_opus_rc_dec_uint_step(OpusRangeCoder *rc, int k0)
Definition: opus_rc.c:211
ff_opus_rc_enc_log
void ff_opus_rc_enc_log(OpusRangeCoder *rc, int val, uint32_t bits)
Definition: opus_rc.c:131
OPUS_RC_SHIFT
#define OPUS_RC_SHIFT
Definition: opus_rc.c:30
OpusRangeCoder::rb
RawBitsContext rb
Definition: opus_rc.h:41
opus_rc_dec_normalize
static av_always_inline void opus_rc_dec_normalize(OpusRangeCoder *rc)
Definition: opus_rc.c:47
distance
static float distance(float x, float y, int band)
Definition: nellymoserenc.c:230
RawBitsContext::cacheval
uint32_t cacheval
Definition: opus_rc.h:36
ff_opus_rc_dec_log
uint32_t ff_opus_rc_dec_log(OpusRangeCoder *rc, uint32_t bits)
Definition: opus_rc.c:114
opus_rc.h
opus_rc_enc_update
static av_always_inline void opus_rc_enc_update(OpusRangeCoder *rc, uint32_t b, uint32_t p, uint32_t p_tot, const int ptwo)
Definition: opus_rc.c:77
OpusRangeCoder::total_bits
uint32_t total_bits
Definition: opus_rc.h:44
ff_opus_rc_enc_end
void ff_opus_rc_enc_end(OpusRangeCoder *rc, uint8_t *dst, int size)
Definition: opus_rc.c:360