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 32static av_always_inline void opus_rc_enc_carryout(OpusRangeCoder *rc, int cbuf) 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 47static av_always_inline void opus_rc_dec_normalize(OpusRangeCoder *rc) 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 56static av_always_inline void opus_rc_enc_normalize(OpusRangeCoder *rc) 57{ 58 while (rc->range <= OPUS_RC_BOT) { 59 opus_rc_enc_carryout(rc, rc->value >> OPUS_RC_SHIFT); 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 66static av_always_inline void opus_rc_dec_update(OpusRangeCoder *rc, uint32_t scale, 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); 73 opus_rc_dec_normalize(rc); 74} 75 76/* Main encoding function, this needs to go fast */ 77static 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); 87 opus_rc_enc_normalize(rc); 88} 89 90uint32_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 109void 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 114uint32_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 } 127 opus_rc_dec_normalize(rc); 128 return k; 129} 130 131void 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 */ 140uint32_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 */ 161void 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 */ 182uint32_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 */ 204void 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 211uint32_t ff_opus_rc_dec_uint_step(OpusRangeCoder *rc, int k0) 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 226void 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 234uint32_t ff_opus_rc_dec_uint_tri(OpusRangeCoder *rc, int qn) 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 258void 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 275int 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 314void 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 338int 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; 347 opus_rc_dec_normalize(rc); 348 349 return 0; 350} 351 352void 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 360void 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) { 374 opus_rc_enc_carryout(rc, end >> OPUS_RC_SHIFT); 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_PACKET_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 402void ff_opus_rc_enc_init(OpusRangeCoder *rc) 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; 410 ff_opus_rc_dec_raw_init(rc, rc->buf + OPUS_MAX_PACKET_SIZE + 8, 0); 411} 412