/src/ffmpeg/libavcodec/opus/rc.c

Source
/*
 * Copyright (c) 2012 Andrew D'Addesio
 * Copyright (c) 2013-2014 Mozilla Corporation
 * Copyright (c) 2017 Rostislav Pehlivanov <atomnuker@gmail.com>
 *
 * This file is part of FFmpeg.
 *
 * FFmpeg is free software; you can redistribute it and/or
 * modify it under the terms of the GNU Lesser General Public
 * License as published by the Free Software Foundation; either
 * version 2.1 of the License, or (at your option) any later version.
 *
 * FFmpeg is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
 * Lesser General Public License for more details.
 *
 * You should have received a copy of the GNU Lesser General Public
 * License along with FFmpeg; if not, write to the Free Software
 * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
 */

#include "rc.h"

#define OPUS_RC_BITS 32
#define OPUS_RC_SYM  8
#define OPUS_RC_CEIL ((1 << OPUS_RC_SYM) - 1)
#define OPUS_RC_TOP (1u << 31)
#define OPUS_RC_BOT (OPUS_RC_TOP >> OPUS_RC_SYM)
#define OPUS_RC_SHIFT (OPUS_RC_BITS - OPUS_RC_SYM - 1)

static av_always_inline void opus_rc_enc_carryout(OpusRangeCoder *rc, int cbuf)
{
    const int cb = cbuf >> OPUS_RC_SYM, mb = (OPUS_RC_CEIL + cb) & OPUS_RC_CEIL;
    if (cbuf == OPUS_RC_CEIL) {
        rc->ext++;
        return;
    }
    rc->rng_cur[0] = rc->rem + cb;
    rc->rng_cur += (rc->rem >= 0);
    for (; rc->ext > 0; rc->ext--)
        *rc->rng_cur++ = mb;
    av_assert0(rc->rng_cur < rc->rb.position);
    rc->rem = cbuf & OPUS_RC_CEIL; /* Propagate */
}

static av_always_inline void opus_rc_dec_normalize(OpusRangeCoder *rc)
{
    while (rc->range <= OPUS_RC_BOT) {
        rc->value = ((rc->value << OPUS_RC_SYM) | (get_bits(&rc->gb, OPUS_RC_SYM) ^ OPUS_RC_CEIL)) & (OPUS_RC_TOP - 1);
        rc->range     <<= OPUS_RC_SYM;
        rc->total_bits += OPUS_RC_SYM;
    }
}

static av_always_inline void opus_rc_enc_normalize(OpusRangeCoder *rc)
{
    while (rc->range <= OPUS_RC_BOT) {
        opus_rc_enc_carryout(rc, rc->value >> OPUS_RC_SHIFT);
        rc->value = (rc->value << OPUS_RC_SYM) & (OPUS_RC_TOP - 1);
        rc->range     <<= OPUS_RC_SYM;
        rc->total_bits += OPUS_RC_SYM;
    }
}

static av_always_inline void opus_rc_dec_update(OpusRangeCoder *rc, uint32_t scale,
                                                uint32_t low, uint32_t high,
                                                uint32_t total)
{
    rc->value -= scale * (total - high);
    rc->range  = low ? scale * (high - low)
                      : rc->range - scale * (total - high);
    opus_rc_dec_normalize(rc);
}

/* Main encoding function, this needs to go fast */
static av_always_inline void opus_rc_enc_update(OpusRangeCoder *rc, uint32_t b, uint32_t p,
                                                uint32_t p_tot, const int ptwo)
{
    uint32_t rscaled, cnd = !!b;
    if (ptwo) /* Whole function is inlined so hopefully branch is optimized out */
        rscaled = rc->range >> ff_log2(p_tot);
    else
        rscaled = rc->range/p_tot;
    rc->value +=    cnd*(rc->range - rscaled*(p_tot - b));
    rc->range  = (!cnd)*(rc->range - rscaled*(p_tot - p)) + cnd*rscaled*(p - b);
    opus_rc_enc_normalize(rc);
}

uint32_t ff_opus_rc_dec_cdf(OpusRangeCoder *rc, const uint16_t *cdf)
{
    unsigned int k, scale, total, symbol, low, high;

    total = *cdf++;

    scale   = rc->range / total;
    symbol = rc->value / scale + 1;
    symbol = total - FFMIN(symbol, total);

    for (k = 0; cdf[k] <= symbol; k++);
    high = cdf[k];
    low  = k ? cdf[k-1] : 0;

    opus_rc_dec_update(rc, scale, low, high, total);

    return k;
}

void ff_opus_rc_enc_cdf(OpusRangeCoder *rc, int val, const uint16_t *cdf)
{
    opus_rc_enc_update(rc, (!!val)*cdf[val], cdf[val + 1], cdf[0], 1);
}

uint32_t ff_opus_rc_dec_log(OpusRangeCoder *rc, uint32_t bits)
{
    uint32_t k, scale;
    scale = rc->range >> bits; // in this case, scale = symbol

    if (rc->value >= scale) {
        rc->value -= scale;
        rc->range -= scale;
        k = 0;
    } else {
        rc->range = scale;
        k = 1;
    }
    opus_rc_dec_normalize(rc);
    return k;
}

void ff_opus_rc_enc_log(OpusRangeCoder *rc, int val, uint32_t bits)
{
    bits = (1 << bits) - 1;
    opus_rc_enc_update(rc, (!!val)*bits, bits + !!val, bits + 1, 1);
}

/**
 * CELT: read 1-25 raw bits at the end of the frame, backwards byte-wise
 */
uint32_t ff_opus_rc_get_raw(OpusRangeCoder *rc, uint32_t count)
{
    uint32_t value = 0;

    while (rc->rb.bytes && rc->rb.cachelen < count) {
        rc->rb.cacheval |= *--rc->rb.position << rc->rb.cachelen;
        rc->rb.cachelen += 8;
        rc->rb.bytes--;
    }

    value = av_zero_extend(rc->rb.cacheval, count);
    rc->rb.cacheval    >>= count;
    rc->rb.cachelen     -= count;
    rc->total_bits      += count;

    return value;
}

/**
 * CELT: write 0 - 31 bits to the rawbits buffer
 */
void ff_opus_rc_put_raw(OpusRangeCoder *rc, uint32_t val, uint32_t count)
{
    const int to_write = FFMIN(32 - rc->rb.cachelen, count);

    rc->total_bits += count;
    rc->rb.cacheval |= av_zero_extend(val, to_write) << rc->rb.cachelen;
    rc->rb.cachelen = (rc->rb.cachelen + to_write) % 32;

    if (!rc->rb.cachelen && count) {
        AV_WB32((uint8_t *)rc->rb.position, rc->rb.cacheval);
        rc->rb.bytes    += 4;
        rc->rb.position -= 4;
        rc->rb.cachelen = count - to_write;
        rc->rb.cacheval = av_zero_extend(val >> to_write, rc->rb.cachelen);
        av_assert0(rc->rng_cur < rc->rb.position);
    }
}

/**
 * CELT: read a uniform distribution
 */
uint32_t ff_opus_rc_dec_uint(OpusRangeCoder *rc, uint32_t size)
{
    uint32_t bits, k, scale, total;

    bits  = opus_ilog(size - 1);
    total = (bits > 8) ? ((size - 1) >> (bits - 8)) + 1 : size;

    scale  = rc->range / total;
    k      = rc->value / scale + 1;
    k      = total - FFMIN(k, total);
    opus_rc_dec_update(rc, scale, k, k + 1, total);

    if (bits > 8) {
        k = k << (bits - 8) | ff_opus_rc_get_raw(rc, bits - 8);
        return FFMIN(k, size - 1);
    } else
        return k;
}

/**
 * CELT: write a uniformly distributed integer
 */
void ff_opus_rc_enc_uint(OpusRangeCoder *rc, uint32_t val, uint32_t size)
{
    const int ps = FFMAX(opus_ilog(size - 1) - 8, 0);
    opus_rc_enc_update(rc, val >> ps, (val >> ps) + 1, ((size - 1) >> ps) + 1, 0);
    ff_opus_rc_put_raw(rc, val, ps);
}

uint32_t ff_opus_rc_dec_uint_step(OpusRangeCoder *rc, int k0)
{
    /* Use a probability of 3 up to itheta=8192 and then use 1 after */
    uint32_t k, scale, symbol, total = (k0+1)*3 + k0;
    scale  = rc->range / total;
    symbol = rc->value / scale + 1;
    symbol = total - FFMIN(symbol, total);

    k = (symbol < (k0+1)*3) ? symbol/3 : symbol - (k0+1)*2;

    opus_rc_dec_update(rc, scale, (k <= k0) ? 3*(k+0) : (k-1-k0) + 3*(k0+1),
                       (k <= k0) ? 3*(k+1) : (k-0-k0) + 3*(k0+1), total);
    return k;
}

void ff_opus_rc_enc_uint_step(OpusRangeCoder *rc, uint32_t val, int k0)
{
    const uint32_t a = val <= k0, b = 2*a + 1;
    k0 = (k0 + 1) << 1;
    val = b*(val + k0) - 3*a*k0;
    opus_rc_enc_update(rc, val, val + b, (k0 << 1) - 1, 0);
}

uint32_t ff_opus_rc_dec_uint_tri(OpusRangeCoder *rc, int qn)
{
    uint32_t k, scale, symbol, total, low, center;

    total = ((qn>>1) + 1) * ((qn>>1) + 1);
    scale   = rc->range / total;
    center = rc->value / scale + 1;
    center = total - FFMIN(center, total);

    if (center < total >> 1) {
        k      = (ff_sqrt(8 * center + 1) - 1) >> 1;
        low    = k * (k + 1) >> 1;
        symbol = k + 1;
    } else {
        k      = (2*(qn + 1) - ff_sqrt(8*(total - center - 1) + 1)) >> 1;
        low    = total - ((qn + 1 - k) * (qn + 2 - k) >> 1);
        symbol = qn + 1 - k;
    }

    opus_rc_dec_update(rc, scale, low, low + symbol, total);

    return k;
}

void ff_opus_rc_enc_uint_tri(OpusRangeCoder *rc, uint32_t k, int qn)
{
    uint32_t symbol, low, total;

    total = ((qn>>1) + 1) * ((qn>>1) + 1);

    if (k <= qn >> 1) {
        low    = k * (k + 1) >> 1;
        symbol = k + 1;
    } else {
        low    = total - ((qn + 1 - k) * (qn + 2 - k) >> 1);
        symbol = qn + 1 - k;
    }

    opus_rc_enc_update(rc, low, low + symbol, total, 0);
}

int ff_opus_rc_dec_laplace(OpusRangeCoder *rc, uint32_t symbol, int decay)
{
    /* extends the range coder to model a Laplace distribution */
    int value = 0;
    uint32_t scale, low = 0, center;

    scale  = rc->range >> 15;
    center = rc->value / scale + 1;
    center = (1 << 15) - FFMIN(center, 1 << 15);

    if (center >= symbol) {
        value++;
        low = symbol;
        symbol = 1 + ((32768 - 32 - symbol) * (16384-decay) >> 15);

        while (symbol > 1 && center >= low + 2 * symbol) {
            value++;
            symbol *= 2;
            low    += symbol;
            symbol  = (((symbol - 2) * decay) >> 15) + 1;
        }

        if (symbol <= 1) {
            int distance = (center - low) >> 1;
            value += distance;
            low   += 2 * distance;
        }

        if (center < low + symbol)
            value *= -1;
        else
            low += symbol;
    }

    opus_rc_dec_update(rc, scale, low, FFMIN(low + symbol, 32768), 32768);

    return value;
}

void ff_opus_rc_enc_laplace(OpusRangeCoder *rc, int *value, uint32_t symbol, int decay)
{
    uint32_t low = symbol;
    int i = 1, val = FFABS(*value), pos = *value > 0;
    if (!val) {
        opus_rc_enc_update(rc, 0, symbol, 1 << 15, 1);
        return;
    }
    symbol = ((32768 - 32 - symbol)*(16384 - decay)) >> 15;
    for (; i < val && symbol; i++) {
        low   += (symbol << 1) + 2;
        symbol = (symbol*decay) >> 14;
    }
    if (symbol) {
        low += (++symbol)*pos;
    } else {
        const int distance = FFMIN(val - i, (((32768 - low) - !pos) >> 1) - 1);
        low   += pos + (distance << 1);
        symbol = FFMIN(1, 32768 - low);
        *value = FFSIGN(*value)*(distance + i);
    }
    opus_rc_enc_update(rc, low, low + symbol, 1 << 15, 1);
}

int ff_opus_rc_dec_init(OpusRangeCoder *rc, const uint8_t *data, int size)
{
    int ret = init_get_bits8(&rc->gb, data, size);
    if (ret < 0)
        return ret;

    rc->range = 128;
    rc->value = 127 - get_bits(&rc->gb, 7);
    rc->total_bits = 9;
    opus_rc_dec_normalize(rc);

    return 0;
}

void ff_opus_rc_dec_raw_init(OpusRangeCoder *rc, const uint8_t *rightend, uint32_t bytes)
{
    rc->rb.position = rightend;
    rc->rb.bytes    = bytes;
    rc->rb.cachelen = 0;
    rc->rb.cacheval = 0;
}

void ff_opus_rc_enc_end(OpusRangeCoder *rc, uint8_t *dst, int size)
{
    int rng_bytes, bits = OPUS_RC_BITS - opus_ilog(rc->range);
    uint32_t mask = (OPUS_RC_TOP - 1) >> bits;
    uint32_t end = (rc->value + mask) & ~mask;

    if ((end | mask) >= rc->value + rc->range) {
        bits++;
        mask >>= 1;
        end = (rc->value + mask) & ~mask;
    }

    /* Finish what's left */
    while (bits > 0) {
        opus_rc_enc_carryout(rc, end >> OPUS_RC_SHIFT);
        end = (end << OPUS_RC_SYM) & (OPUS_RC_TOP - 1);
        bits -= OPUS_RC_SYM;
    }

    /* Flush out anything left or marked */
    if (rc->rem >= 0 || rc->ext > 0)
        opus_rc_enc_carryout(rc, 0);

    rng_bytes = rc->rng_cur - rc->buf;
    memcpy(dst, rc->buf, rng_bytes);

    rc->waste = size*8 - (rc->rb.bytes*8 + rc->rb.cachelen) - rng_bytes*8;

    /* Put the rawbits part, if any */
    if (rc->rb.bytes || rc->rb.cachelen) {
        int i, lap;
        uint8_t *rb_src, *rb_dst;
        ff_opus_rc_put_raw(rc, 0, 32 - rc->rb.cachelen);
        rb_src = rc->buf + OPUS_MAX_FRAME_SIZE + 12 - rc->rb.bytes;
        rb_dst = dst + FFMAX(size - rc->rb.bytes, 0);
        lap = &dst[rng_bytes] - rb_dst;
        for (i = 0; i < lap; i++)
            rb_dst[i] |= rb_src[i];
        memcpy(&rb_dst[lap], &rb_src[lap], FFMAX(rc->rb.bytes - lap, 0));
    }
}

void ff_opus_rc_enc_init(OpusRangeCoder *rc)
{
    rc->value = 0;
    rc->range = OPUS_RC_TOP;
    rc->total_bits = OPUS_RC_BITS + 1;
    rc->rem = -1;
    rc->ext =  0;
    rc->rng_cur = rc->buf;
    ff_opus_rc_dec_raw_init(rc, rc->buf + OPUS_MAX_FRAME_SIZE + 8, 0);
}

Coverage Report

Created: 2025-12-31 07:57

Line	Count	Source
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 "rc.h"
24
25	0	#define OPUS_RC_BITS 32
26	194M	#define OPUS_RC_SYM 8
27	18.7M	#define OPUS_RC_CEIL ((1 << OPUS_RC_SYM) - 1)
28	119M	#define OPUS_RC_TOP (1u << 31)
29	101M	#define OPUS_RC_BOT (OPUS_RC_TOP >> OPUS_RC_SYM)
30	0	#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	0	{
34	0	const int cb = cbuf >> OPUS_RC_SYM, mb = (OPUS_RC_CEIL + cb) & OPUS_RC_CEIL;
35	0	if (cbuf == OPUS_RC_CEIL) {
36	0	rc->ext++;
37	0	return;
38	0	}
39	0	rc->rng_cur[0] = rc->rem + cb;
40	0	rc->rng_cur += (rc->rem >= 0);
41	0	for (; rc->ext > 0; rc->ext--)
42	0	*rc->rng_cur++ = mb;
43	0	av_assert0(rc->rng_cur < rc->rb.position);
44	0	rc->rem = cbuf & OPUS_RC_CEIL; /* Propagate */
45	0	}
46
47		static av_always_inline void opus_rc_dec_normalize(OpusRangeCoder *rc)
48	82.4M	{
49	101M	while (rc->range <= OPUS_RC_BOT) {
50	18.7M	rc->value = ((rc->value << OPUS_RC_SYM) \| (get_bits(&rc->gb, OPUS_RC_SYM) ^ OPUS_RC_CEIL)) & (OPUS_RC_TOP - 1);
51	18.7M	rc->range <<= OPUS_RC_SYM;
52	18.7M	rc->total_bits += OPUS_RC_SYM;
53	18.7M	}
54	82.4M	}
55
56		static av_always_inline void opus_rc_enc_normalize(OpusRangeCoder *rc)
57	0	{
58	0	while (rc->range <= OPUS_RC_BOT) {
59	0	opus_rc_enc_carryout(rc, rc->value >> OPUS_RC_SHIFT);
60	0	rc->value = (rc->value << OPUS_RC_SYM) & (OPUS_RC_TOP - 1);
61	0	rc->range <<= OPUS_RC_SYM;
62	0	rc->total_bits += OPUS_RC_SYM;
63	0	}
64	0	}
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	76.9M	{
70	76.9M	rc->value -= scale * (total - high);
71	76.9M	rc->range = low ? scale * (high - low)
72	76.9M	: rc->range - scale * (total - high);
73	76.9M	opus_rc_dec_normalize(rc);
74	76.9M	}
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	0	{
80	0	uint32_t rscaled, cnd = !!b;
81	0	if (ptwo) /* Whole function is inlined so hopefully branch is optimized out */
82	0	rscaled = rc->range >> ff_log2(p_tot);
83	0	else
84	0	rscaled = rc->range/p_tot;
85	0	rc->value += cnd(rc->range - rscaled(p_tot - b));
86	0	rc->range = (!cnd)(rc->range - rscaled(p_tot - p)) + cndrscaled(p - b);
87	0	opus_rc_enc_normalize(rc);
88	0	}
89
90		uint32_t ff_opus_rc_dec_cdf(OpusRangeCoder rc, const uint16_t cdf)
91	72.6M	{
92	72.6M	unsigned int k, scale, total, symbol, low, high;
93
94	72.6M	total = *cdf++;
95
96	72.6M	scale = rc->range / total;
97	72.6M	symbol = rc->value / scale + 1;
98	72.6M	symbol = total - FFMIN(symbol, total);
99
100	204M	for (k = 0; cdf[k] <= symbol; k++);
101	72.6M	high = cdf[k];
102	72.6M	low = k ? cdf[k-1] : 0;
103
104	72.6M	opus_rc_dec_update(rc, scale, low, high, total);
105
106	72.6M	return k;
107	72.6M	}
108
109		void ff_opus_rc_enc_cdf(OpusRangeCoder rc, int val, const uint16_t cdf)
110	0	{
111	0	opus_rc_enc_update(rc, (!!val)*cdf[val], cdf[val + 1], cdf[0], 1);
112	0	}
113
114		uint32_t ff_opus_rc_dec_log(OpusRangeCoder *rc, uint32_t bits)
115	5.20M	{
116	5.20M	uint32_t k, scale;
117	5.20M	scale = rc->range >> bits; // in this case, scale = symbol
118
119	5.20M	if (rc->value >= scale) {
120	4.79M	rc->value -= scale;
121	4.79M	rc->range -= scale;
122	4.79M	k = 0;
123	4.79M	} else {
124	411k	rc->range = scale;
125	411k	k = 1;
126	411k	}
127	5.20M	opus_rc_dec_normalize(rc);
128	5.20M	return k;
129	5.20M	}
130
131		void ff_opus_rc_enc_log(OpusRangeCoder *rc, int val, uint32_t bits)
132	0	{
133	0	bits = (1 << bits) - 1;
134	0	opus_rc_enc_update(rc, (!!val)*bits, bits + !!val, bits + 1, 1);
135	0	}
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	3.25M	{
142	3.25M	uint32_t value = 0;
143
144	4.75M	while (rc->rb.bytes && rc->rb.cachelen < count) {
145	1.50M	rc->rb.cacheval \|= *--rc->rb.position << rc->rb.cachelen;
146	1.50M	rc->rb.cachelen += 8;
147	1.50M	rc->rb.bytes--;
148	1.50M	}
149
150	3.25M	value = av_zero_extend(rc->rb.cacheval, count);
151	3.25M	rc->rb.cacheval >>= count;
152	3.25M	rc->rb.cachelen -= count;
153	3.25M	rc->total_bits += count;
154
155	3.25M	return value;
156	3.25M	}
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	0	{
163	0	const int to_write = FFMIN(32 - rc->rb.cachelen, count);
164
165	0	rc->total_bits += count;
166	0	rc->rb.cacheval \|= av_zero_extend(val, to_write) << rc->rb.cachelen;
167	0	rc->rb.cachelen = (rc->rb.cachelen + to_write) % 32;
168
169	0	if (!rc->rb.cachelen && count) {
170	0	AV_WB32((uint8_t *)rc->rb.position, rc->rb.cacheval);
171	0	rc->rb.bytes += 4;
172	0	rc->rb.position -= 4;
173	0	rc->rb.cachelen = count - to_write;
174	0	rc->rb.cacheval = av_zero_extend(val >> to_write, rc->rb.cachelen);
175	0	av_assert0(rc->rng_cur < rc->rb.position);
176	0	}
177	0	}
178
179		/**
180		* CELT: read a uniform distribution
181		*/
182		uint32_t ff_opus_rc_dec_uint(OpusRangeCoder *rc, uint32_t size)
183	1.39M	{
184	1.39M	uint32_t bits, k, scale, total;
185
186	1.39M	bits = opus_ilog(size - 1);
187	1.39M	total = (bits > 8) ? ((size - 1) >> (bits - 8)) + 1 : size;
188
189	1.39M	scale = rc->range / total;
190	1.39M	k = rc->value / scale + 1;
191	1.39M	k = total - FFMIN(k, total);
192	1.39M	opus_rc_dec_update(rc, scale, k, k + 1, total);
193
194	1.39M	if (bits > 8) {
195	1.06M	k = k << (bits - 8) \| ff_opus_rc_get_raw(rc, bits - 8);
196	1.06M	return FFMIN(k, size - 1);
197	1.06M	} else
198	334k	return k;
199	1.39M	}
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	0	{
206	0	const int ps = FFMAX(opus_ilog(size - 1) - 8, 0);
207	0	opus_rc_enc_update(rc, val >> ps, (val >> ps) + 1, ((size - 1) >> ps) + 1, 0);
208	0	ff_opus_rc_put_raw(rc, val, ps);
209	0	}
210
211		uint32_t ff_opus_rc_dec_uint_step(OpusRangeCoder *rc, int k0)
212	49.4k	{
213		/* Use a probability of 3 up to itheta=8192 and then use 1 after */
214	49.4k	uint32_t k, scale, symbol, total = (k0+1)*3 + k0;
215	49.4k	scale = rc->range / total;
216	49.4k	symbol = rc->value / scale + 1;
217	49.4k	symbol = total - FFMIN(symbol, total);
218
219	49.4k	k = (symbol < (k0+1)3) ? symbol/3 : symbol - (k0+1)2;
220
221	49.4k	opus_rc_dec_update(rc, scale, (k <= k0) ? 3(k+0) : (k-1-k0) + 3(k0+1),
222	49.4k	(k <= k0) ? 3(k+1) : (k-0-k0) + 3(k0+1), total);
223	49.4k	return k;
224	49.4k	}
225
226		void ff_opus_rc_enc_uint_step(OpusRangeCoder *rc, uint32_t val, int k0)
227	0	{
228	0	const uint32_t a = val <= k0, b = 2*a + 1;
229	0	k0 = (k0 + 1) << 1;
230	0	val = b(val + k0) - 3a*k0;
231	0	opus_rc_enc_update(rc, val, val + b, (k0 << 1) - 1, 0);
232	0	}
233
234		uint32_t ff_opus_rc_dec_uint_tri(OpusRangeCoder *rc, int qn)
235	311k	{
236	311k	uint32_t k, scale, symbol, total, low, center;
237
238	311k	total = ((qn>>1) + 1) * ((qn>>1) + 1);
239	311k	scale = rc->range / total;
240	311k	center = rc->value / scale + 1;
241	311k	center = total - FFMIN(center, total);
242
243	311k	if (center < total >> 1) {
244	148k	k = (ff_sqrt(8 * center + 1) - 1) >> 1;
245	148k	low = k * (k + 1) >> 1;
246	148k	symbol = k + 1;
247	162k	} else {
248	162k	k = (2(qn + 1) - ff_sqrt(8(total - center - 1) + 1)) >> 1;
249	162k	low = total - ((qn + 1 - k) * (qn + 2 - k) >> 1);
250	162k	symbol = qn + 1 - k;
251	162k	}
252
253	311k	opus_rc_dec_update(rc, scale, low, low + symbol, total);
254
255	311k	return k;
256	311k	}
257
258		void ff_opus_rc_enc_uint_tri(OpusRangeCoder *rc, uint32_t k, int qn)
259	0	{
260	0	uint32_t symbol, low, total;
261
262	0	total = ((qn>>1) + 1) * ((qn>>1) + 1);
263
264	0	if (k <= qn >> 1) {
265	0	low = k * (k + 1) >> 1;
266	0	symbol = k + 1;
267	0	} else {
268	0	low = total - ((qn + 1 - k) * (qn + 2 - k) >> 1);
269	0	symbol = qn + 1 - k;
270	0	}
271
272	0	opus_rc_enc_update(rc, low, low + symbol, total, 0);
273	0	}
274
275		int ff_opus_rc_dec_laplace(OpusRangeCoder *rc, uint32_t symbol, int decay)
276	2.47M	{
277		/* extends the range coder to model a Laplace distribution */
278	2.47M	int value = 0;
279	2.47M	uint32_t scale, low = 0, center;
280
281	2.47M	scale = rc->range >> 15;
282	2.47M	center = rc->value / scale + 1;
283	2.47M	center = (1 << 15) - FFMIN(center, 1 << 15);
284
285	2.47M	if (center >= symbol) {
286	822k	value++;
287	822k	low = symbol;
288	822k	symbol = 1 + ((32768 - 32 - symbol) * (16384-decay) >> 15);
289
290	1.11M	while (symbol > 1 && center >= low + 2 * symbol) {
291	289k	value++;
292	289k	symbol *= 2;
293	289k	low += symbol;
294	289k	symbol = (((symbol - 2) * decay) >> 15) + 1;
295	289k	}
296
297	822k	if (symbol <= 1) {
298	5.55k	int distance = (center - low) >> 1;
299	5.55k	value += distance;
300	5.55k	low += 2 * distance;
301	5.55k	}
302
303	822k	if (center < low + symbol)
304	417k	value *= -1;
305	405k	else
306	405k	low += symbol;
307	822k	}
308
309	2.47M	opus_rc_dec_update(rc, scale, low, FFMIN(low + symbol, 32768), 32768);
310
311	2.47M	return value;
312	2.47M	}
313
314		void ff_opus_rc_enc_laplace(OpusRangeCoder rc, int value, uint32_t symbol, int decay)
315	0	{
316	0	uint32_t low = symbol;
317	0	int i = 1, val = FFABS(value), pos = value > 0;
318	0	if (!val) {
319	0	opus_rc_enc_update(rc, 0, symbol, 1 << 15, 1);
320	0	return;
321	0	}
322	0	symbol = ((32768 - 32 - symbol)*(16384 - decay)) >> 15;
323	0	for (; i < val && symbol; i++) {
324	0	low += (symbol << 1) + 2;
325	0	symbol = (symbol*decay) >> 14;
326	0	}
327	0	if (symbol) {
328	0	low += (++symbol)*pos;
329	0	} else {
330	0	const int distance = FFMIN(val - i, (((32768 - low) - !pos) >> 1) - 1);
331	0	low += pos + (distance << 1);
332	0	symbol = FFMIN(1, 32768 - low);
333	0	value = FFSIGN(value)*(distance + i);
334	0	}
335	0	opus_rc_enc_update(rc, low, low + symbol, 1 << 15, 1);
336	0	}
337
338		int ff_opus_rc_dec_init(OpusRangeCoder rc, const uint8_t data, int size)
339	348k	{
340	348k	int ret = init_get_bits8(&rc->gb, data, size);
341	348k	if (ret < 0)
342	3.41k	return ret;
343
344	345k	rc->range = 128;
345	345k	rc->value = 127 - get_bits(&rc->gb, 7);
346	345k	rc->total_bits = 9;
347	345k	opus_rc_dec_normalize(rc);
348
349	345k	return 0;
350	348k	}
351
352		void ff_opus_rc_dec_raw_init(OpusRangeCoder rc, const uint8_t rightend, uint32_t bytes)
353	141k	{
354	141k	rc->rb.position = rightend;
355	141k	rc->rb.bytes = bytes;
356	141k	rc->rb.cachelen = 0;
357	141k	rc->rb.cacheval = 0;
358	141k	}
359
360		void ff_opus_rc_enc_end(OpusRangeCoder rc, uint8_t dst, int size)
361	0	{
362	0	int rng_bytes, bits = OPUS_RC_BITS - opus_ilog(rc->range);
363	0	uint32_t mask = (OPUS_RC_TOP - 1) >> bits;
364	0	uint32_t end = (rc->value + mask) & ~mask;
365
366	0	if ((end \| mask) >= rc->value + rc->range) {
367	0	bits++;
368	0	mask >>= 1;
369	0	end = (rc->value + mask) & ~mask;
370	0	}
371
372		/* Finish what's left */
373	0	while (bits > 0) {
374	0	opus_rc_enc_carryout(rc, end >> OPUS_RC_SHIFT);
375	0	end = (end << OPUS_RC_SYM) & (OPUS_RC_TOP - 1);
376	0	bits -= OPUS_RC_SYM;
377	0	}
378
379		/* Flush out anything left or marked */
380	0	if (rc->rem >= 0 \|\| rc->ext > 0)
381	0	opus_rc_enc_carryout(rc, 0);
382
383	0	rng_bytes = rc->rng_cur - rc->buf;
384	0	memcpy(dst, rc->buf, rng_bytes);
385
386	0	rc->waste = size8 - (rc->rb.bytes8 + rc->rb.cachelen) - rng_bytes*8;
387
388		/* Put the rawbits part, if any */
389	0	if (rc->rb.bytes \|\| rc->rb.cachelen) {
390	0	int i, lap;
391	0	uint8_t rb_src, rb_dst;
392	0	ff_opus_rc_put_raw(rc, 0, 32 - rc->rb.cachelen);
393	0	rb_src = rc->buf + OPUS_MAX_FRAME_SIZE + 12 - rc->rb.bytes;
394	0	rb_dst = dst + FFMAX(size - rc->rb.bytes, 0);
395	0	lap = &dst[rng_bytes] - rb_dst;
396	0	for (i = 0; i < lap; i++)
397	0	rb_dst[i] \|= rb_src[i];
398	0	memcpy(&rb_dst[lap], &rb_src[lap], FFMAX(rc->rb.bytes - lap, 0));
399	0	}
400	0	}
401
402		void ff_opus_rc_enc_init(OpusRangeCoder *rc)
403	0	{
404	0	rc->value = 0;
405	0	rc->range = OPUS_RC_TOP;
406	0	rc->total_bits = OPUS_RC_BITS + 1;
407	0	rc->rem = -1;
408	0	rc->ext = 0;
409	0	rc->rng_cur = rc->buf;
410	0	ff_opus_rc_dec_raw_init(rc, rc->buf + OPUS_MAX_FRAME_SIZE + 8, 0);
411	0	}