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 #include <assert.h>
13 #include "aom_dsp/entdec.h"
14 #include "aom_dsp/prob.h"
15
16 /*A range decoder.
17 This is an entropy decoder based upon \cite{Mar79}, which is itself a
18 rediscovery of the FIFO arithmetic code introduced by \cite{Pas76}.
19 It is very similar to arithmetic encoding, except that encoding is done with
20 digits in any base, instead of with bits, and so it is faster when using
21 larger bases (i.e.: a byte).
22 The author claims an average waste of $\frac{1}{2}\log_b(2b)$ bits, where $b$
23 is the base, longer than the theoretical optimum, but to my knowledge there
24 is no published justification for this claim.
25 This only seems true when using near-infinite precision arithmetic so that
26 the process is carried out with no rounding errors.
27
28 An excellent description of implementation details is available at
29 http://www.arturocampos.com/ac_range.html
30 A recent work \cite{MNW98} which proposes several changes to arithmetic
31 encoding for efficiency actually re-discovers many of the principles
32 behind range encoding, and presents a good theoretical analysis of them.
33
34 End of stream is handled by writing out the smallest number of bits that
35 ensures that the stream will be correctly decoded regardless of the value of
36 any subsequent bits.
37 od_ec_dec_tell() can be used to determine how many bits were needed to decode
38 all the symbols thus far; other data can be packed in the remaining bits of
39 the input buffer.
40 @PHDTHESIS{Pas76,
41 author="Richard Clark Pasco",
42 title="Source coding algorithms for fast data compression",
43 school="Dept. of Electrical Engineering, Stanford University",
44 address="Stanford, CA",
45 month=May,
46 year=1976,
47 URL="http://www.richpasco.org/scaffdc.pdf"
48 }
49 @INPROCEEDINGS{Mar79,
50 author="Martin, G.N.N.",
51 title="Range encoding: an algorithm for removing redundancy from a digitised
52 message",
53 booktitle="Video & Data Recording Conference",
54 year=1979,
55 address="Southampton",
56 month=Jul,
57 URL="http://www.compressconsult.com/rangecoder/rngcod.pdf.gz"
58 }
59 @ARTICLE{MNW98,
60 author="Alistair Moffat and Radford Neal and Ian H. Witten",
61 title="Arithmetic Coding Revisited",
62 journal="{ACM} Transactions on Information Systems",
63 year=1998,
64 volume=16,
65 number=3,
66 pages="256--294",
67 month=Jul,
68 URL="http://researchcommons.waikato.ac.nz/bitstream/handle/10289/78/content.pdf"
69 }*/
70
71 /*This is meant to be a large, positive constant that can still be efficiently
72 loaded as an immediate (on platforms like ARM, for example).
73 Even relatively modest values like 100 would work fine.*/
74 #define OD_EC_LOTS_OF_BITS (0x4000)
75
76 /*The return value of od_ec_dec_tell does not change across an od_ec_dec_refill
77 call.*/
od_ec_dec_refill(od_ec_dec * dec)78 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 dif = dec->dif;
85 cnt = dec->cnt;
86 bptr = dec->bptr;
87 end = dec->end;
88 s = OD_EC_WINDOW_SIZE - 9 - (cnt + 15);
89 for (; s >= 0 && bptr < end; s -= 8, bptr++) {
90 assert(s <= OD_EC_WINDOW_SIZE - 8);
91 dif ^= (od_ec_window)bptr[0] << s;
92 cnt += 8;
93 }
94 if (bptr >= end) {
95 dec->tell_offs += OD_EC_LOTS_OF_BITS - cnt;
96 cnt = OD_EC_LOTS_OF_BITS;
97 }
98 dec->dif = dif;
99 dec->cnt = cnt;
100 dec->bptr = bptr;
101 }
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.*/
od_ec_dec_normalize(od_ec_dec * dec,od_ec_window dif,unsigned rng,int ret)111 static int od_ec_dec_normalize(od_ec_dec *dec, od_ec_window dif, unsigned rng,
112 int ret) {
113 int d;
114 assert(rng <= 65535U);
115 // The number of leading zeros in the 16-bit binary representation of rng.
116 d = 16 - OD_ILOG_NZ(rng);
117 dec->cnt -= d;
118 /*This is equivalent to shifting in 1's instead of 0's.*/
119 dec->dif = ((dif + 1) << d) - 1;
120 dec->rng = rng << d;
121 if (dec->cnt < 0) od_ec_dec_refill(dec);
122 return ret;
123 }
124
125 /*Initializes the decoder.
126 buf: The input buffer to use.
127 Return: 0 on success, or a negative value on error.*/
od_ec_dec_init(od_ec_dec * dec,const unsigned char * buf,uint32_t storage)128 void od_ec_dec_init(od_ec_dec *dec, const unsigned char *buf,
129 uint32_t storage) {
130 dec->buf = buf;
131 dec->tell_offs = 10 - (OD_EC_WINDOW_SIZE - 8);
132 dec->end = buf + storage;
133 dec->bptr = buf;
134 dec->dif = ((od_ec_window)1 << (OD_EC_WINDOW_SIZE - 1)) - 1;
135 dec->rng = 0x8000;
136 dec->cnt = -15;
137 dec->error = 0;
138 od_ec_dec_refill(dec);
139 }
140
141 /*Decode a single binary value.
142 f: The probability that the bit is one, scaled by 32768.
143 Return: The value decoded (0 or 1).*/
od_ec_decode_bool_q15(od_ec_dec * dec,unsigned f)144 int od_ec_decode_bool_q15(od_ec_dec *dec, unsigned f) {
145 od_ec_window dif;
146 od_ec_window vw;
147 unsigned r;
148 unsigned r_new;
149 unsigned v;
150 int ret;
151 assert(0 < f);
152 assert(f < 32768U);
153 dif = dec->dif;
154 r = dec->rng;
155 assert(dif >> (OD_EC_WINDOW_SIZE - 16) < r);
156 assert(32768U <= r);
157 v = ((r >> 8) * (uint32_t)(f >> EC_PROB_SHIFT) >> (7 - EC_PROB_SHIFT));
158 v += EC_MIN_PROB;
159 vw = (od_ec_window)v << (OD_EC_WINDOW_SIZE - 16);
160 ret = 1;
161 r_new = v;
162 if (dif >= vw) {
163 r_new = r - v;
164 dif -= vw;
165 ret = 0;
166 }
167 return od_ec_dec_normalize(dec, dif, r_new, ret);
168 }
169
170 /*Decodes a symbol given an inverse cumulative distribution function (CDF)
171 table in Q15.
172 icdf: CDF_PROB_TOP minus the CDF, such that symbol s falls in the range
173 [s > 0 ? (CDF_PROB_TOP - icdf[s - 1]) : 0, CDF_PROB_TOP - icdf[s]).
174 The values must be monotonically non-increasing, and icdf[nsyms - 1]
175 must be 0.
176 nsyms: The number of symbols in the alphabet.
177 This should be at most 16.
178 Return: The decoded symbol s.*/
od_ec_decode_cdf_q15(od_ec_dec * dec,const uint16_t * icdf,int nsyms)179 int od_ec_decode_cdf_q15(od_ec_dec *dec, const uint16_t *icdf, int nsyms) {
180 od_ec_window dif;
181 unsigned r;
182 unsigned c;
183 unsigned u;
184 unsigned v;
185 int ret;
186 (void)nsyms;
187 dif = dec->dif;
188 r = dec->rng;
189 const int N = nsyms - 1;
190
191 assert(dif >> (OD_EC_WINDOW_SIZE - 16) < r);
192 assert(icdf[nsyms - 1] == OD_ICDF(CDF_PROB_TOP));
193 assert(32768U <= r);
194 assert(7 - EC_PROB_SHIFT - CDF_SHIFT >= 0);
195 c = (unsigned)(dif >> (OD_EC_WINDOW_SIZE - 16));
196 v = r;
197 ret = -1;
198 do {
199 u = v;
200 v = ((r >> 8) * (uint32_t)(icdf[++ret] >> EC_PROB_SHIFT) >>
201 (7 - EC_PROB_SHIFT - CDF_SHIFT));
202 v += EC_MIN_PROB * (N - ret);
203 } while (c < v);
204 assert(v < u);
205 assert(u <= r);
206 r = u - v;
207 dif -= (od_ec_window)v << (OD_EC_WINDOW_SIZE - 16);
208 return od_ec_dec_normalize(dec, dif, r, ret);
209 }
210
211 /*Returns the number of bits "used" by the decoded symbols so far.
212 This same number can be computed in either the encoder or the decoder, and is
213 suitable for making coding decisions.
214 Return: The number of bits.
215 This will always be slightly larger than the exact value (e.g., all
216 rounding error is in the positive direction).*/
od_ec_dec_tell(const od_ec_dec * dec)217 int od_ec_dec_tell(const od_ec_dec *dec) {
218 return (int)((dec->bptr - dec->buf) * 8 - dec->cnt + dec->tell_offs);
219 }
220
221 /*Returns the number of bits "used" by the decoded symbols so far.
222 This same number can be computed in either the encoder or the decoder, and is
223 suitable for making coding decisions.
224 Return: The number of bits scaled by 2**OD_BITRES.
225 This will always be slightly larger than the exact value (e.g., all
226 rounding error is in the positive direction).*/
od_ec_dec_tell_frac(const od_ec_dec * dec)227 uint32_t od_ec_dec_tell_frac(const od_ec_dec *dec) {
228 return od_ec_tell_frac(od_ec_dec_tell(dec), dec->rng);
229 }
230