Line data Source code
1 : /* Copyright (c) 2001-2011 Timothy B. Terriberry
2 : Copyright (c) 2008-2009 Xiph.Org Foundation */
3 : /*
4 : Redistribution and use in source and binary forms, with or without
5 : modification, are permitted provided that the following conditions
6 : are met:
7 :
8 : - Redistributions of source code must retain the above copyright
9 : notice, this list of conditions and the following disclaimer.
10 :
11 : - Redistributions in binary form must reproduce the above copyright
12 : notice, this list of conditions and the following disclaimer in the
13 : documentation and/or other materials provided with the distribution.
14 :
15 : THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
16 : ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
17 : LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
18 : A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER
19 : OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
20 : EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
21 : PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
22 : PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
23 : LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
24 : NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
25 : SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
26 : */
27 :
28 : #ifdef HAVE_CONFIG_H
29 : #include "config.h"
30 : #endif
31 :
32 : #include <stddef.h>
33 : #include "os_support.h"
34 : #include "arch.h"
35 : #include "entdec.h"
36 : #include "mfrngcod.h"
37 :
38 : /*A range decoder.
39 : This is an entropy decoder based upon \cite{Mar79}, which is itself a
40 : rediscovery of the FIFO arithmetic code introduced by \cite{Pas76}.
41 : It is very similar to arithmetic encoding, except that encoding is done with
42 : digits in any base, instead of with bits, and so it is faster when using
43 : larger bases (i.e.: a byte).
44 : The author claims an average waste of $\frac{1}{2}\log_b(2b)$ bits, where $b$
45 : is the base, longer than the theoretical optimum, but to my knowledge there
46 : is no published justification for this claim.
47 : This only seems true when using near-infinite precision arithmetic so that
48 : the process is carried out with no rounding errors.
49 :
50 : An excellent description of implementation details is available at
51 : http://www.arturocampos.com/ac_range.html
52 : A recent work \cite{MNW98} which proposes several changes to arithmetic
53 : encoding for efficiency actually re-discovers many of the principles
54 : behind range encoding, and presents a good theoretical analysis of them.
55 :
56 : End of stream is handled by writing out the smallest number of bits that
57 : ensures that the stream will be correctly decoded regardless of the value of
58 : any subsequent bits.
59 : ec_tell() can be used to determine how many bits were needed to decode
60 : all the symbols thus far; other data can be packed in the remaining bits of
61 : the input buffer.
62 : @PHDTHESIS{Pas76,
63 : author="Richard Clark Pasco",
64 : title="Source coding algorithms for fast data compression",
65 : school="Dept. of Electrical Engineering, Stanford University",
66 : address="Stanford, CA",
67 : month=May,
68 : year=1976
69 : }
70 : @INPROCEEDINGS{Mar79,
71 : author="Martin, G.N.N.",
72 : title="Range encoding: an algorithm for removing redundancy from a digitised
73 : message",
74 : booktitle="Video & Data Recording Conference",
75 : year=1979,
76 : address="Southampton",
77 : month=Jul
78 : }
79 : @ARTICLE{MNW98,
80 : author="Alistair Moffat and Radford Neal and Ian H. Witten",
81 : title="Arithmetic Coding Revisited",
82 : journal="{ACM} Transactions on Information Systems",
83 : year=1998,
84 : volume=16,
85 : number=3,
86 : pages="256--294",
87 : month=Jul,
88 : URL="http://www.stanford.edu/class/ee398a/handouts/papers/Moffat98ArithmCoding.pdf"
89 : }*/
90 :
91 0 : static int ec_read_byte(ec_dec *_this){
92 0 : return _this->offs<_this->storage?_this->buf[_this->offs++]:0;
93 : }
94 :
95 0 : static int ec_read_byte_from_end(ec_dec *_this){
96 0 : return _this->end_offs<_this->storage?
97 0 : _this->buf[_this->storage-++(_this->end_offs)]:0;
98 : }
99 :
100 : /*Normalizes the contents of val and rng so that rng lies entirely in the
101 : high-order symbol.*/
102 0 : static void ec_dec_normalize(ec_dec *_this){
103 : /*If the range is too small, rescale it and input some bits.*/
104 0 : while(_this->rng<=EC_CODE_BOT){
105 : int sym;
106 0 : _this->nbits_total+=EC_SYM_BITS;
107 0 : _this->rng<<=EC_SYM_BITS;
108 : /*Use up the remaining bits from our last symbol.*/
109 0 : sym=_this->rem;
110 : /*Read the next value from the input.*/
111 0 : _this->rem=ec_read_byte(_this);
112 : /*Take the rest of the bits we need from this new symbol.*/
113 0 : sym=(sym<<EC_SYM_BITS|_this->rem)>>(EC_SYM_BITS-EC_CODE_EXTRA);
114 : /*And subtract them from val, capped to be less than EC_CODE_TOP.*/
115 0 : _this->val=((_this->val<<EC_SYM_BITS)+(EC_SYM_MAX&~sym))&(EC_CODE_TOP-1);
116 : }
117 0 : }
118 :
119 0 : void ec_dec_init(ec_dec *_this,unsigned char *_buf,opus_uint32 _storage){
120 0 : _this->buf=_buf;
121 0 : _this->storage=_storage;
122 0 : _this->end_offs=0;
123 0 : _this->end_window=0;
124 0 : _this->nend_bits=0;
125 : /*This is the offset from which ec_tell() will subtract partial bits.
126 : The final value after the ec_dec_normalize() call will be the same as in
127 : the encoder, but we have to compensate for the bits that are added there.*/
128 0 : _this->nbits_total=EC_CODE_BITS+1
129 : -((EC_CODE_BITS-EC_CODE_EXTRA)/EC_SYM_BITS)*EC_SYM_BITS;
130 0 : _this->offs=0;
131 0 : _this->rng=1U<<EC_CODE_EXTRA;
132 0 : _this->rem=ec_read_byte(_this);
133 0 : _this->val=_this->rng-1-(_this->rem>>(EC_SYM_BITS-EC_CODE_EXTRA));
134 0 : _this->error=0;
135 : /*Normalize the interval.*/
136 0 : ec_dec_normalize(_this);
137 0 : }
138 :
139 0 : unsigned ec_decode(ec_dec *_this,unsigned _ft){
140 : unsigned s;
141 0 : _this->ext=celt_udiv(_this->rng,_ft);
142 0 : s=(unsigned)(_this->val/_this->ext);
143 0 : return _ft-EC_MINI(s+1,_ft);
144 : }
145 :
146 0 : unsigned ec_decode_bin(ec_dec *_this,unsigned _bits){
147 : unsigned s;
148 0 : _this->ext=_this->rng>>_bits;
149 0 : s=(unsigned)(_this->val/_this->ext);
150 0 : return (1U<<_bits)-EC_MINI(s+1U,1U<<_bits);
151 : }
152 :
153 0 : void ec_dec_update(ec_dec *_this,unsigned _fl,unsigned _fh,unsigned _ft){
154 : opus_uint32 s;
155 0 : s=IMUL32(_this->ext,_ft-_fh);
156 0 : _this->val-=s;
157 0 : _this->rng=_fl>0?IMUL32(_this->ext,_fh-_fl):_this->rng-s;
158 0 : ec_dec_normalize(_this);
159 0 : }
160 :
161 : /*The probability of having a "one" is 1/(1<<_logp).*/
162 0 : int ec_dec_bit_logp(ec_dec *_this,unsigned _logp){
163 : opus_uint32 r;
164 : opus_uint32 d;
165 : opus_uint32 s;
166 : int ret;
167 0 : r=_this->rng;
168 0 : d=_this->val;
169 0 : s=r>>_logp;
170 0 : ret=d<s;
171 0 : if(!ret)_this->val=d-s;
172 0 : _this->rng=ret?s:r-s;
173 0 : ec_dec_normalize(_this);
174 0 : return ret;
175 : }
176 :
177 0 : int ec_dec_icdf(ec_dec *_this,const unsigned char *_icdf,unsigned _ftb){
178 : opus_uint32 r;
179 : opus_uint32 d;
180 : opus_uint32 s;
181 : opus_uint32 t;
182 : int ret;
183 0 : s=_this->rng;
184 0 : d=_this->val;
185 0 : r=s>>_ftb;
186 0 : ret=-1;
187 : do{
188 0 : t=s;
189 0 : s=IMUL32(r,_icdf[++ret]);
190 : }
191 0 : while(d<s);
192 0 : _this->val=d-s;
193 0 : _this->rng=t-s;
194 0 : ec_dec_normalize(_this);
195 0 : return ret;
196 : }
197 :
198 0 : opus_uint32 ec_dec_uint(ec_dec *_this,opus_uint32 _ft){
199 : unsigned ft;
200 : unsigned s;
201 : int ftb;
202 : /*In order to optimize EC_ILOG(), it is undefined for the value 0.*/
203 0 : celt_assert(_ft>1);
204 0 : _ft--;
205 0 : ftb=EC_ILOG(_ft);
206 0 : if(ftb>EC_UINT_BITS){
207 : opus_uint32 t;
208 0 : ftb-=EC_UINT_BITS;
209 0 : ft=(unsigned)(_ft>>ftb)+1;
210 0 : s=ec_decode(_this,ft);
211 0 : ec_dec_update(_this,s,s+1,ft);
212 0 : t=(opus_uint32)s<<ftb|ec_dec_bits(_this,ftb);
213 0 : if(t<=_ft)return t;
214 0 : _this->error=1;
215 0 : return _ft;
216 : }
217 : else{
218 0 : _ft++;
219 0 : s=ec_decode(_this,(unsigned)_ft);
220 0 : ec_dec_update(_this,s,s+1,(unsigned)_ft);
221 0 : return s;
222 : }
223 : }
224 :
225 0 : opus_uint32 ec_dec_bits(ec_dec *_this,unsigned _bits){
226 : ec_window window;
227 : int available;
228 : opus_uint32 ret;
229 0 : window=_this->end_window;
230 0 : available=_this->nend_bits;
231 0 : if((unsigned)available<_bits){
232 : do{
233 0 : window|=(ec_window)ec_read_byte_from_end(_this)<<available;
234 0 : available+=EC_SYM_BITS;
235 : }
236 0 : while(available<=EC_WINDOW_SIZE-EC_SYM_BITS);
237 : }
238 0 : ret=(opus_uint32)window&(((opus_uint32)1<<_bits)-1U);
239 0 : window>>=_bits;
240 0 : available-=_bits;
241 0 : _this->end_window=window;
242 0 : _this->nend_bits=available;
243 0 : _this->nbits_total+=_bits;
244 0 : return ret;
245 : }
|
