Remove redundant mid-only flag when side VAD flag is set.
[opus.git] / celt / entdec.c
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 FOUNDATION OR
19    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   IBM (the author's employer) never sought to patent the idea, and to my
51    knowledge the algorithm is unencumbered by any patents, though its
52    performance is very competitive with proprietary arithmetic coding.
53   The two are based on very similar ideas, however.
54   An excellent description of implementation details is available at
55    http://www.arturocampos.com/ac_range.html
56   A recent work \cite{MNW98} which proposes several changes to arithmetic
57    encoding for efficiency actually re-discovers many of the principles
58    behind range encoding, and presents a good theoretical analysis of them.
59
60   End of stream is handled by writing out the smallest number of bits that
61    ensures that the stream will be correctly decoded regardless of the value of
62    any subsequent bits.
63   ec_tell() can be used to determine how many bits were needed to decode
64    all the symbols thus far; other data can be packed in the remaining bits of
65    the input buffer.
66   @PHDTHESIS{Pas76,
67     author="Richard Clark Pasco",
68     title="Source coding algorithms for fast data compression",
69     school="Dept. of Electrical Engineering, Stanford University",
70     address="Stanford, CA",
71     month=May,
72     year=1976
73   }
74   @INPROCEEDINGS{Mar79,
75    author="Martin, G.N.N.",
76    title="Range encoding: an algorithm for removing redundancy from a digitised
77     message",
78    booktitle="Video & Data Recording Conference",
79    year=1979,
80    address="Southampton",
81    month=Jul
82   }
83   @ARTICLE{MNW98,
84    author="Alistair Moffat and Radford Neal and Ian H. Witten",
85    title="Arithmetic Coding Revisited",
86    journal="{ACM} Transactions on Information Systems",
87    year=1998,
88    volume=16,
89    number=3,
90    pages="256--294",
91    month=Jul,
92    URL="http://www.stanford.edu/class/ee398/handouts/papers/Moffat98ArithmCoding.pdf"
93   }*/
94
95 static int ec_read_byte(ec_dec *_this){
96   return _this->offs<_this->storage?_this->buf[_this->offs++]:0;
97 }
98
99 static int ec_read_byte_from_end(ec_dec *_this){
100   return _this->end_offs<_this->storage?
101    _this->buf[_this->storage-++(_this->end_offs)]:0;
102 }
103
104 /*Normalizes the contents of val and rng so that rng lies entirely in the
105    high-order symbol.*/
106 static void ec_dec_normalize(ec_dec *_this){
107   /*If the range is too small, rescale it and input some bits.*/
108   while(_this->rng<=EC_CODE_BOT){
109     int sym;
110     _this->nbits_total+=EC_SYM_BITS;
111     _this->rng<<=EC_SYM_BITS;
112     /*Use up the remaining bits from our last symbol.*/
113     sym=_this->rem;
114     /*Read the next value from the input.*/
115     _this->rem=ec_read_byte(_this);
116     /*Take the rest of the bits we need from this new symbol.*/
117     sym=(sym<<EC_SYM_BITS|_this->rem)>>(EC_SYM_BITS-EC_CODE_EXTRA);
118     /*And subtract them from val, capped to be less than EC_CODE_TOP.*/
119     _this->val=((_this->val<<EC_SYM_BITS)+(EC_SYM_MAX&~sym))&(EC_CODE_TOP-1);
120   }
121 }
122
123 void ec_dec_init(ec_dec *_this,unsigned char *_buf,opus_uint32 _storage){
124   _this->buf=_buf;
125   _this->storage=_storage;
126   _this->end_offs=0;
127   _this->end_window=0;
128   _this->nend_bits=0;
129   _this->offs=0;
130   _this->rng=1U<<EC_CODE_EXTRA;
131   _this->rem=ec_read_byte(_this);
132   _this->val=_this->rng-1-(_this->rem>>(EC_SYM_BITS-EC_CODE_EXTRA));
133   _this->error=0;
134   /*Normalize the interval.*/
135   ec_dec_normalize(_this);
136   /*This is the offset from which ec_tell() will subtract partial bits.
137     This must be after the initial ec_dec_normalize(), or you will have to
138      compensate for the bits that are read there.*/
139   _this->nbits_total=EC_CODE_BITS+1;
140 }
141
142 unsigned ec_decode(ec_dec *_this,unsigned _ft){
143   unsigned s;
144   _this->ext=_this->rng/_ft;
145   s=(unsigned)(_this->val/_this->ext);
146   return _ft-EC_MINI(s+1,_ft);
147 }
148
149 unsigned ec_decode_bin(ec_dec *_this,unsigned _bits){
150    unsigned s;
151    _this->ext=_this->rng>>_bits;
152    s=(unsigned)(_this->val/_this->ext);
153    return (1U<<_bits)-EC_MINI(s+1U,1U<<_bits);
154 }
155
156 void ec_dec_update(ec_dec *_this,unsigned _fl,unsigned _fh,unsigned _ft){
157   opus_uint32 s;
158   s=IMUL32(_this->ext,_ft-_fh);
159   _this->val-=s;
160   _this->rng=_fl>0?IMUL32(_this->ext,_fh-_fl):_this->rng-s;
161   ec_dec_normalize(_this);
162 }
163
164 /*The probability of having a "one" is 1/(1<<_logp).*/
165 int ec_dec_bit_logp(ec_dec *_this,unsigned _logp){
166   opus_uint32 r;
167   opus_uint32 d;
168   opus_uint32 s;
169   int         ret;
170   r=_this->rng;
171   d=_this->val;
172   s=r>>_logp;
173   ret=d<s;
174   if(!ret)_this->val=d-s;
175   _this->rng=ret?s:r-s;
176   ec_dec_normalize(_this);
177   return ret;
178 }
179
180 int ec_dec_icdf(ec_dec *_this,const unsigned char *_icdf,unsigned _ftb){
181   opus_uint32 r;
182   opus_uint32 d;
183   opus_uint32 s;
184   opus_uint32 t;
185   int         ret;
186   s=_this->rng;
187   d=_this->val;
188   r=s>>_ftb;
189   ret=-1;
190   do{
191     t=s;
192     s=IMUL32(r,_icdf[++ret]);
193   }
194   while(d<s);
195   _this->val=d-s;
196   _this->rng=t-s;
197   ec_dec_normalize(_this);
198   return ret;
199 }
200
201 opus_uint32 ec_dec_uint(ec_dec *_this,opus_uint32 _ft){
202   unsigned ft;
203   unsigned s;
204   int      ftb;
205   /*In order to optimize EC_ILOG(), it is undefined for the value 0.*/
206   celt_assert(_ft>1);
207   _ft--;
208   ftb=EC_ILOG(_ft);
209   if(ftb>EC_UINT_BITS){
210     opus_uint32 t;
211     ftb-=EC_UINT_BITS;
212     ft=(unsigned)(_ft>>ftb)+1;
213     s=ec_decode(_this,ft);
214     ec_dec_update(_this,s,s+1,ft);
215     t=(opus_uint32)s<<ftb|ec_dec_bits(_this,ftb);
216     if(t<=_ft)return t;
217     _this->error=1;
218     return _ft;
219   }
220   else{
221     _ft++;
222     s=ec_decode(_this,(unsigned)_ft);
223     ec_dec_update(_this,s,s+1,(unsigned)_ft);
224     return s;
225   }
226 }
227
228 opus_uint32 ec_dec_bits(ec_dec *_this,unsigned _bits){
229   ec_window   window;
230   int         available;
231   opus_uint32 ret;
232   window=_this->end_window;
233   available=_this->nend_bits;
234   if((unsigned)available<_bits){
235     do{
236       window|=(ec_window)ec_read_byte_from_end(_this)<<available;
237       available+=EC_SYM_BITS;
238     }
239     while(available<=EC_WINDOW_SIZE-EC_SYM_BITS);
240   }
241   ret=(opus_uint32)window&(((opus_uint32)1<<_bits)-1U);
242   window>>=_bits;
243   available-=_bits;
244   _this->end_window=window;
245   _this->nend_bits=available;
246   _this->nbits_total+=_bits;
247   return ret;
248 }