Fixes post-filter for transitions between 2.5ms and other frame sizes
[opus.git] / libcelt / entenc.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 #if defined(HAVE_CONFIG_H)
29 # include "config.h"
30 #endif
31 #include "os_support.h"
32 #include "arch.h"
33 #include "entenc.h"
34 #include "mfrngcod.h"
35
36
37
38 /*A range encoder.
39   See entdec.c and the references for implementation details \cite{Mar79,MNW98}.
40
41   @INPROCEEDINGS{Mar79,
42    author="Martin, G.N.N.",
43    title="Range encoding: an algorithm for removing redundancy from a digitised
44     message",
45    booktitle="Video \& Data Recording Conference",
46    year=1979,
47    address="Southampton",
48    month=Jul
49   }
50   @ARTICLE{MNW98,
51    author="Alistair Moffat and Radford Neal and Ian H. Witten",
52    title="Arithmetic Coding Revisited",
53    journal="{ACM} Transactions on Information Systems",
54    year=1998,
55    volume=16,
56    number=3,
57    pages="256--294",
58    month=Jul,
59    URL="http://www.stanford.edu/class/ee398/handouts/papers/Moffat98ArithmCoding.pdf"
60   }*/
61
62
63
64 static int ec_write_byte(ec_enc *_this,unsigned _value){
65   if(_this->offs+_this->end_offs>=_this->storage)return -1;
66   _this->buf[_this->offs++]=(unsigned char)_value;
67   return 0;
68 }
69
70 static int ec_write_byte_at_end(ec_enc *_this,unsigned _value){
71   if(_this->offs+_this->end_offs>=_this->storage)return -1;
72   _this->buf[_this->storage-++(_this->end_offs)]=(unsigned char)_value;
73   return 0;
74 }
75
76
77 /*Outputs a symbol, with a carry bit.
78   If there is a potential to propagate a carry over several symbols, they are
79    buffered until it can be determined whether or not an actual carry will
80    occur.
81   If the counter for the buffered symbols overflows, then the stream becomes
82    undecodable.
83   This gives a theoretical limit of a few billion symbols in a single packet on
84    32-bit systems.
85   The alternative is to truncate the range in order to force a carry, but
86    requires similar carry tracking in the decoder, needlessly slowing it down.*/
87 static void ec_enc_carry_out(ec_enc *_this,int _c){
88   if(_c!=EC_SYM_MAX){
89     /*No further carry propagation possible, flush buffer.*/
90     int carry;
91     carry=_c>>EC_SYM_BITS;
92     /*Don't output a byte on the first write.
93       This compare should be taken care of by branch-prediction thereafter.*/
94     if(_this->rem>=0)_this->error|=ec_write_byte(_this,_this->rem+carry);
95     if(_this->ext>0){
96       unsigned sym;
97       sym=EC_SYM_MAX+carry&EC_SYM_MAX;
98       do _this->error|=ec_write_byte(_this,sym);
99       while(--(_this->ext)>0);
100     }
101     _this->rem=_c&EC_SYM_MAX;
102   }
103   else _this->ext++;
104 }
105
106 static void ec_enc_normalize(ec_enc *_this){
107   /*If the range is too small, output some bits and rescale it.*/
108   while(_this->rng<=EC_CODE_BOT){
109     ec_enc_carry_out(_this,(int)(_this->val>>EC_CODE_SHIFT));
110     /*Move the next-to-high-order symbol into the high-order position.*/
111     _this->val=_this->val<<EC_SYM_BITS&EC_CODE_TOP-1;
112     _this->rng<<=EC_SYM_BITS;
113     _this->nbits_total+=EC_SYM_BITS;
114   }
115 }
116
117 void ec_enc_init(ec_enc *_this,unsigned char *_buf,ec_uint32 _size){
118   _this->buf=_buf;
119   _this->end_offs=0;
120   _this->end_window=0;
121   _this->nend_bits=0;
122   /*This is the offset from which ec_tell() will subtract partial bits.*/
123   _this->nbits_total=EC_CODE_BITS+1;
124   _this->offs=0;
125   _this->rng=EC_CODE_TOP;
126   _this->rem=-1;
127   _this->val=0;
128   _this->ext=0;
129   _this->storage=_size;
130   _this->error=0;
131 }
132
133 void ec_encode(ec_enc *_this,unsigned _fl,unsigned _fh,unsigned _ft){
134   ec_uint32 r;
135   r=_this->rng/_ft;
136   if(_fl>0){
137     _this->val+=_this->rng-IMUL32(r,(_ft-_fl));
138     _this->rng=IMUL32(r,(_fh-_fl));
139   }
140   else _this->rng-=IMUL32(r,(_ft-_fh));
141   ec_enc_normalize(_this);
142 }
143
144 void ec_encode_bin(ec_enc *_this,unsigned _fl,unsigned _fh,unsigned _bits){
145   ec_uint32 r;
146   r=_this->rng>>_bits;
147   if(_fl>0){
148     _this->val+=_this->rng-IMUL32(r,((1<<_bits)-_fl));
149     _this->rng=IMUL32(r,(_fh-_fl));
150   }
151   else _this->rng-=IMUL32(r,((1<<_bits)-_fh));
152   ec_enc_normalize(_this);
153 }
154
155 /*The probability of having a "one" is 1/(1<<_logp).*/
156 void ec_enc_bit_logp(ec_enc *_this,int _val,unsigned _logp){
157   ec_uint32 r;
158   ec_uint32 s;
159   ec_uint32 l;
160   r=_this->rng;
161   l=_this->val;
162   s=r>>_logp;
163   r-=s;
164   if(_val)_this->val=l+r;
165   _this->rng=_val?s:r;
166   ec_enc_normalize(_this);
167 }
168
169 void ec_enc_icdf(ec_enc *_this,int _s,const unsigned char *_icdf,unsigned _ftb){
170   ec_uint32 r;
171   r=_this->rng>>_ftb;
172   if(_s>0){
173     _this->val+=_this->rng-IMUL32(r,_icdf[_s-1]);
174     _this->rng=IMUL32(r,_icdf[_s-1]-_icdf[_s]);
175   }
176   else _this->rng-=IMUL32(r,_icdf[_s]);
177   ec_enc_normalize(_this);
178 }
179
180 void ec_enc_uint(ec_enc *_this,ec_uint32 _fl,ec_uint32 _ft){
181   unsigned  ft;
182   unsigned  fl;
183   int       ftb;
184   /*In order to optimize EC_ILOG(), it is undefined for the value 0.*/
185   celt_assert(_ft>1);
186   _ft--;
187   ftb=EC_ILOG(_ft);
188   if(ftb>EC_UINT_BITS){
189     ftb-=EC_UINT_BITS;
190     ft=(_ft>>ftb)+1;
191     fl=(unsigned)(_fl>>ftb);
192     ec_encode(_this,fl,fl+1,ft);
193     ec_enc_bits(_this,_fl&((ec_uint32)1<<ftb)-1,ftb);
194   }
195   else ec_encode(_this,_fl,_fl+1,_ft+1);
196 }
197
198 void ec_enc_bits(ec_enc *_this,ec_uint32 _fl,unsigned _bits){
199   ec_window window;
200   int       used;
201   window=_this->end_window;
202   used=_this->nend_bits;
203   if(used+_bits>EC_WINDOW_SIZE){
204     do{
205       _this->error|=ec_write_byte_at_end(_this,(unsigned)window&EC_SYM_MAX);
206       window>>=EC_SYM_BITS;
207       used-=EC_SYM_BITS;
208     }
209     while(used>=EC_SYM_BITS);
210   }
211   window|=(ec_window)_fl<<used;
212   used+=_bits;
213   _this->end_window=window;
214   _this->nend_bits=used;
215   _this->nbits_total+=_bits;
216 }
217
218 void ec_enc_shrink(ec_enc *_this,ec_uint32 _size){
219   celt_assert(_this->offs+_this->end_offs<=_size);
220   CELT_MOVE(_this->buf+_size-_this->end_offs,
221    _this->buf+_this->storage-_this->end_offs,_this->end_offs);
222   _this->storage=_size;
223 }
224
225 void ec_enc_done(ec_enc *_this){
226   ec_window window;
227   int       used;
228   ec_uint32 msk;
229   ec_uint32 end;
230   int       l;
231   /*We output the minimum number of bits that ensures that the symbols encoded
232      thus far will be decoded correctly regardless of the bits that follow.*/
233   l=EC_CODE_BITS-EC_ILOG(_this->rng);
234   msk=EC_CODE_TOP-1>>l;
235   end=_this->val+msk&~msk;
236   if((end|msk)>=_this->val+_this->rng){
237     l++;
238     msk>>=1;
239     end=_this->val+msk&~msk;
240   }
241   while(l>0){
242     ec_enc_carry_out(_this,(int)(end>>EC_CODE_SHIFT));
243     end=end<<EC_SYM_BITS&EC_CODE_TOP-1;
244     l-=EC_SYM_BITS;
245   }
246   /*If we have a buffered byte flush it into the output buffer.*/
247   if(_this->rem>=0||_this->ext>0)ec_enc_carry_out(_this,0);
248   /*If we have buffered extra bits, flush them as well.*/
249   window=_this->end_window;
250   used=_this->nend_bits;
251   while(used>=EC_SYM_BITS){
252     _this->error|=ec_write_byte_at_end(_this,(unsigned)window&EC_SYM_MAX);
253     window>>=EC_SYM_BITS;
254     used-=EC_SYM_BITS;
255   }
256   /*Clear any excess space and add any remaining extra bits to the last byte.*/
257   if(!_this->error){
258     CELT_MEMSET(_this->buf+_this->offs,0,
259      _this->storage-_this->offs-_this->end_offs);
260     if(used>0){
261       /*If there's no range coder data at all, give up.*/
262       if(_this->end_offs>=_this->storage)_this->error=-1;
263       else{
264         l=-l;
265         /*If we've busted, don't add too many extra bits to the last byte; it
266            would corrupt the range coder data, and that's more important.*/
267         if(_this->offs+_this->end_offs>=_this->storage&&l<used){
268           window&=(1<<l)-1;
269           _this->error=-1;
270         }
271       }
272       _this->buf[_this->storage-_this->end_offs-1]|=(unsigned char)window;
273     }
274   }
275 }