Line data Source code
1 : /*
2 : * Copyright (c) 2001-2016, Alliance for Open Media. All rights reserved
3 : *
4 : * This source code is subject to the terms of the BSD 2 Clause License and
5 : * the Alliance for Open Media Patent License 1.0. If the BSD 2 Clause License
6 : * was not distributed with this source code in the LICENSE file, you can
7 : * obtain it at www.aomedia.org/license/software. If the Alliance for Open
8 : * Media Patent License 1.0 was not distributed with this source code in the
9 : * PATENTS file, you can obtain it at www.aomedia.org/license/patent.
10 : */
11 :
12 : #ifdef HAVE_CONFIG_H
13 : #include "./config.h"
14 : #endif
15 :
16 : #include "aom_dsp/entdec.h"
17 :
18 : /*A range decoder.
19 : This is an entropy decoder based upon \cite{Mar79}, which is itself a
20 : rediscovery of the FIFO arithmetic code introduced by \cite{Pas76}.
21 : It is very similar to arithmetic encoding, except that encoding is done with
22 : digits in any base, instead of with bits, and so it is faster when using
23 : larger bases (i.e.: a byte).
24 : The author claims an average waste of $\frac{1}{2}\log_b(2b)$ bits, where $b$
25 : is the base, longer than the theoretical optimum, but to my knowledge there
26 : is no published justification for this claim.
27 : This only seems true when using near-infinite precision arithmetic so that
28 : the process is carried out with no rounding errors.
29 :
30 : An excellent description of implementation details is available at
31 : http://www.arturocampos.com/ac_range.html
32 : A recent work \cite{MNW98} which proposes several changes to arithmetic
33 : encoding for efficiency actually re-discovers many of the principles
34 : behind range encoding, and presents a good theoretical analysis of them.
35 :
36 : End of stream is handled by writing out the smallest number of bits that
37 : ensures that the stream will be correctly decoded regardless of the value of
38 : any subsequent bits.
39 : od_ec_dec_tell() can be used to determine how many bits were needed to decode
40 : all the symbols thus far; other data can be packed in the remaining bits of
41 : the input buffer.
42 : @PHDTHESIS{Pas76,
43 : author="Richard Clark Pasco",
44 : title="Source coding algorithms for fast data compression",
45 : school="Dept. of Electrical Engineering, Stanford University",
46 : address="Stanford, CA",
47 : month=May,
48 : year=1976,
49 : URL="http://www.richpasco.org/scaffdc.pdf"
50 : }
51 : @INPROCEEDINGS{Mar79,
52 : author="Martin, G.N.N.",
53 : title="Range encoding: an algorithm for removing redundancy from a digitised
54 : message",
55 : booktitle="Video & Data Recording Conference",
56 : year=1979,
57 : address="Southampton",
58 : month=Jul,
59 : URL="http://www.compressconsult.com/rangecoder/rngcod.pdf.gz"
60 : }
61 : @ARTICLE{MNW98,
62 : author="Alistair Moffat and Radford Neal and Ian H. Witten",
63 : title="Arithmetic Coding Revisited",
64 : journal="{ACM} Transactions on Information Systems",
65 : year=1998,
66 : volume=16,
67 : number=3,
68 : pages="256--294",
69 : month=Jul,
70 : URL="http://researchcommons.waikato.ac.nz/bitstream/handle/10289/78/content.pdf"
71 : }*/
72 :
73 : /*This is meant to be a large, positive constant that can still be efficiently
74 : loaded as an immediate (on platforms like ARM, for example).
75 : Even relatively modest values like 100 would work fine.*/
76 : #define OD_EC_LOTS_OF_BITS (0x4000)
77 :
78 0 : static void od_ec_dec_refill(od_ec_dec *dec) {
79 : int s;
80 : od_ec_window dif;
81 : int16_t cnt;
82 : const unsigned char *bptr;
83 : const unsigned char *end;
84 0 : dif = dec->dif;
85 0 : cnt = dec->cnt;
86 0 : bptr = dec->bptr;
87 0 : end = dec->end;
88 0 : s = OD_EC_WINDOW_SIZE - 9 - (cnt + 15);
89 0 : for (; s >= 0 && bptr < end; s -= 8, bptr++) {
90 0 : OD_ASSERT(s <= OD_EC_WINDOW_SIZE - 8);
91 0 : dif ^= (od_ec_window)bptr[0] << s;
92 0 : cnt += 8;
93 : }
94 0 : if (bptr >= end) {
95 0 : dec->tell_offs += OD_EC_LOTS_OF_BITS - cnt;
96 0 : cnt = OD_EC_LOTS_OF_BITS;
97 : }
98 0 : dec->dif = dif;
99 0 : dec->cnt = cnt;
100 0 : dec->bptr = bptr;
101 0 : }
102 :
103 : /*Takes updated dif and range values, renormalizes them so that
104 : 32768 <= rng < 65536 (reading more bytes from the stream into dif if
105 : necessary), and stores them back in the decoder context.
106 : dif: The new value of dif.
107 : rng: The new value of the range.
108 : ret: The value to return.
109 : Return: ret.
110 : This allows the compiler to jump to this function via a tail-call.*/
111 0 : static int od_ec_dec_normalize(od_ec_dec *dec, od_ec_window dif, unsigned rng,
112 : int ret) {
113 : int d;
114 0 : OD_ASSERT(rng <= 65535U);
115 0 : d = 16 - OD_ILOG_NZ(rng);
116 0 : dec->cnt -= d;
117 : #if CONFIG_EC_SMALLMUL
118 : /*This is equivalent to shifting in 1's instead of 0's.*/
119 0 : dec->dif = ((dif + 1) << d) - 1;
120 : #else
121 : dec->dif = dif << d;
122 : #endif
123 0 : dec->rng = rng << d;
124 0 : if (dec->cnt < 0) od_ec_dec_refill(dec);
125 0 : return ret;
126 : }
127 :
128 : /*Initializes the decoder.
129 : buf: The input buffer to use.
130 : Return: 0 on success, or a negative value on error.*/
131 0 : void od_ec_dec_init(od_ec_dec *dec, const unsigned char *buf,
132 : uint32_t storage) {
133 0 : dec->buf = buf;
134 0 : dec->eptr = buf + storage;
135 0 : dec->end_window = 0;
136 0 : dec->nend_bits = 0;
137 0 : dec->tell_offs = 10 - (OD_EC_WINDOW_SIZE - 8);
138 0 : dec->end = buf + storage;
139 0 : dec->bptr = buf;
140 : #if CONFIG_EC_SMALLMUL
141 0 : dec->dif = ((od_ec_window)1 << (OD_EC_WINDOW_SIZE - 1)) - 1;
142 : #else
143 : dec->dif = 0;
144 : #endif
145 0 : dec->rng = 0x8000;
146 0 : dec->cnt = -15;
147 0 : dec->error = 0;
148 0 : od_ec_dec_refill(dec);
149 0 : }
150 :
151 : /*Decode a single binary value.
152 : {EC_SMALLMUL} f: The probability that the bit is one, scaled by 32768.
153 : {else} f: The probability that the bit is zero, scaled by 32768.
154 : Return: The value decoded (0 or 1).*/
155 0 : int od_ec_decode_bool_q15(od_ec_dec *dec, unsigned f) {
156 : od_ec_window dif;
157 : od_ec_window vw;
158 : unsigned r;
159 : unsigned r_new;
160 : unsigned v;
161 : int ret;
162 0 : OD_ASSERT(0 < f);
163 0 : OD_ASSERT(f < 32768U);
164 0 : dif = dec->dif;
165 0 : r = dec->rng;
166 0 : OD_ASSERT(dif >> (OD_EC_WINDOW_SIZE - 16) < r);
167 0 : OD_ASSERT(32768U <= r);
168 : #if CONFIG_EC_SMALLMUL
169 0 : v = (r >> 8) * (uint32_t)f >> 7;
170 0 : vw = (od_ec_window)v << (OD_EC_WINDOW_SIZE - 16);
171 0 : ret = 1;
172 0 : r_new = v;
173 0 : if (dif >= vw) {
174 0 : r_new = r - v;
175 0 : dif -= vw;
176 0 : ret = 0;
177 : }
178 : #else
179 : v = f * (uint32_t)r >> 15;
180 : vw = (od_ec_window)v << (OD_EC_WINDOW_SIZE - 16);
181 : ret = 0;
182 : r_new = v;
183 : if (dif >= vw) {
184 : r_new = r - v;
185 : dif -= vw;
186 : ret = 1;
187 : }
188 : #endif
189 0 : return od_ec_dec_normalize(dec, dif, r_new, ret);
190 : }
191 :
192 : /*Decodes a symbol given a cumulative distribution function (CDF) table in Q15.
193 : cdf: The CDF, such that symbol s falls in the range
194 : [s > 0 ? cdf[s - 1] : 0, cdf[s]).
195 : The values must be monotonically non-increasing, and cdf[nsyms - 1]
196 : must be 32768.
197 : {EC_SMALLMUL}: The CDF contains 32768 minus those values.
198 : nsyms: The number of symbols in the alphabet.
199 : This should be at most 16.
200 : Return: The decoded symbol s.*/
201 0 : int od_ec_decode_cdf_q15(od_ec_dec *dec, const uint16_t *cdf, int nsyms) {
202 : od_ec_window dif;
203 : unsigned r;
204 : unsigned c;
205 : unsigned u;
206 : unsigned v;
207 : int ret;
208 : (void)nsyms;
209 0 : dif = dec->dif;
210 0 : r = dec->rng;
211 0 : OD_ASSERT(dif >> (OD_EC_WINDOW_SIZE - 16) < r);
212 0 : OD_ASSERT(cdf[nsyms - 1] == OD_ICDF(32768U));
213 0 : OD_ASSERT(32768U <= r);
214 : #if CONFIG_EC_SMALLMUL
215 0 : c = (unsigned)(dif >> (OD_EC_WINDOW_SIZE - 16));
216 0 : v = r;
217 0 : ret = -1;
218 : do {
219 0 : u = v;
220 0 : v = (r >> 8) * (uint32_t)cdf[++ret] >> 7;
221 0 : } while (c < v);
222 0 : OD_ASSERT(v < u);
223 0 : OD_ASSERT(u <= r);
224 0 : r = u - v;
225 0 : dif -= (od_ec_window)v << (OD_EC_WINDOW_SIZE - 16);
226 : #else
227 : c = (unsigned)(dif >> (OD_EC_WINDOW_SIZE - 16));
228 : v = 0;
229 : ret = -1;
230 : do {
231 : u = v;
232 : v = cdf[++ret] * (uint32_t)r >> 15;
233 : } while (v <= c);
234 : OD_ASSERT(u < v);
235 : OD_ASSERT(v <= r);
236 : r = v - u;
237 : dif -= (od_ec_window)u << (OD_EC_WINDOW_SIZE - 16);
238 : #endif
239 0 : return od_ec_dec_normalize(dec, dif, r, ret);
240 : }
241 :
242 : #if CONFIG_RAWBITS
243 : /*Extracts a sequence of raw bits from the stream.
244 : The bits must have been encoded with od_ec_enc_bits().
245 : ftb: The number of bits to extract.
246 : This must be between 0 and 25, inclusive.
247 : Return: The decoded bits.*/
248 : uint32_t od_ec_dec_bits_(od_ec_dec *dec, unsigned ftb) {
249 : od_ec_window window;
250 : int available;
251 : uint32_t ret;
252 : OD_ASSERT(ftb <= 25);
253 : window = dec->end_window;
254 : available = dec->nend_bits;
255 : if ((unsigned)available < ftb) {
256 : const unsigned char *buf;
257 : const unsigned char *eptr;
258 : buf = dec->buf;
259 : eptr = dec->eptr;
260 : OD_ASSERT(available <= OD_EC_WINDOW_SIZE - 8);
261 : do {
262 : if (eptr <= buf) {
263 : dec->tell_offs += OD_EC_LOTS_OF_BITS - available;
264 : available = OD_EC_LOTS_OF_BITS;
265 : break;
266 : }
267 : window |= (od_ec_window) * --eptr << available;
268 : available += 8;
269 : } while (available <= OD_EC_WINDOW_SIZE - 8);
270 : dec->eptr = eptr;
271 : }
272 : ret = (uint32_t)window & (((uint32_t)1 << ftb) - 1);
273 : window >>= ftb;
274 : available -= ftb;
275 : dec->end_window = window;
276 : dec->nend_bits = available;
277 : return ret;
278 : }
279 : #endif
280 :
281 : /*Returns the number of bits "used" by the decoded symbols so far.
282 : This same number can be computed in either the encoder or the decoder, and is
283 : suitable for making coding decisions.
284 : Return: The number of bits.
285 : This will always be slightly larger than the exact value (e.g., all
286 : rounding error is in the positive direction).*/
287 0 : int od_ec_dec_tell(const od_ec_dec *dec) {
288 0 : return (int)(((dec->end - dec->eptr) + (dec->bptr - dec->buf)) * 8 -
289 0 : dec->cnt - dec->nend_bits + dec->tell_offs);
290 : }
291 :
292 : /*Returns the number of bits "used" by the decoded symbols so far.
293 : This same number can be computed in either the encoder or the decoder, and is
294 : suitable for making coding decisions.
295 : Return: The number of bits scaled by 2**OD_BITRES.
296 : This will always be slightly larger than the exact value (e.g., all
297 : rounding error is in the positive direction).*/
298 0 : uint32_t od_ec_dec_tell_frac(const od_ec_dec *dec) {
299 0 : return od_ec_tell_frac(od_ec_dec_tell(dec), dec->rng);
300 : }
|
