blob: 85268bd2842d4130e50e277e73b62ca57cd597d5
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 | |
32 | static 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 | |
47 | static 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 | |
56 | static 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 | |
66 | static 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 */ |
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); |
87 | opus_rc_enc_normalize(rc); |
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, 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 | } |
127 | opus_rc_dec_normalize(rc); |
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(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 | |
211 | uint32_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 | |
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 | |
234 | uint32_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 | |
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; |
347 | opus_rc_dec_normalize(rc); |
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) { |
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 | rc->waste = (size - (rc->rb.bytes + rng_bytes)) << 3; |
385 | memcpy(dst, rc->buf, rng_bytes); |
386 | memset(dst + rng_bytes, 0, FFMAX(rc->waste >> 3, 0) + 1); |
387 | |
388 | /* Put the rawbits part, if any */ |
389 | if (rc->rb.bytes || rc->rb.cachelen) { |
390 | int rawbytes = FFALIGN(rc->rb.bytes*8 + rc->rb.cachelen, 8) >> 3; |
391 | int dst_loc = FFMAX(size - rawbytes, 0); |
392 | uint8_t *src = rc->buf + OPUS_MAX_PACKET_SIZE + 12 - rawbytes; |
393 | ff_opus_rc_put_raw(rc, 0, 32 - rc->rb.cachelen); |
394 | dst[dst_loc] |= *src++; |
395 | memcpy(&dst[dst_loc + 1], src, rawbytes - 1); |
396 | } |
397 | } |
398 | |
399 | void ff_opus_rc_enc_init(OpusRangeCoder *rc) |
400 | { |
401 | rc->value = 0; |
402 | rc->range = OPUS_RC_TOP; |
403 | rc->total_bits = OPUS_RC_BITS + 1; |
404 | rc->rem = -1; |
405 | rc->ext = 0; |
406 | rc->rng_cur = rc->buf; |
407 | ff_opus_rc_dec_raw_init(rc, rc->buf + OPUS_MAX_PACKET_SIZE + 8, 0); |
408 | } |
409 |