s/intra_decision()/loss_distortion()/
[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,celt_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   celt_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   celt_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   celt_uint32 r;
158   celt_uint32 s;
159   celt_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   celt_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,celt_uint32 _fl,celt_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&((celt_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,celt_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_patch_initial_bits(ec_enc *_this,unsigned _val,unsigned _nbits){
219   int      shift;
220   unsigned mask;
221   celt_assert(_nbits<=EC_SYM_BITS);
222   shift=EC_SYM_BITS-_nbits;
223   mask=(1<<_nbits)-1<<shift;
224   if(_this->offs>0){
225     /*The first byte has been finalized.*/
226     _this->buf[0]=(unsigned char)(_this->buf[0]&~mask|_val<<shift);
227   }
228   else if(_this->rem>=0){
229     /*The first byte is still awaiting carry propagation.*/
230     _this->rem=_this->rem&~mask|_val<<shift;
231   }
232   else if(_this->rng<=EC_CODE_TOP>>shift){
233     /*The renormalization loop has never been run.*/
234     _this->val=_this->val&~((celt_uint32)mask<<EC_CODE_SHIFT)|
235      (celt_uint32)_val<<EC_CODE_SHIFT+shift;
236   }
237   /*The encoder hasn't even encoded _nbits of data yet.*/
238   else _this->error=-1;
239 }
240
241 void ec_enc_shrink(ec_enc *_this,celt_uint32 _size){
242   celt_assert(_this->offs+_this->end_offs<=_size);
243   CELT_MOVE(_this->buf+_size-_this->end_offs,
244    _this->buf+_this->storage-_this->end_offs,_this->end_offs);
245   _this->storage=_size;
246 }
247
248 void ec_enc_done(ec_enc *_this){
249   ec_window   window;
250   int         used;
251   celt_uint32 msk;
252   celt_uint32 end;
253   int         l;
254   /*We output the minimum number of bits that ensures that the symbols encoded
255      thus far will be decoded correctly regardless of the bits that follow.*/
256   l=EC_CODE_BITS-EC_ILOG(_this->rng);
257   msk=EC_CODE_TOP-1>>l;
258   end=_this->val+msk&~msk;
259   if((end|msk)>=_this->val+_this->rng){
260     l++;
261     msk>>=1;
262     end=_this->val+msk&~msk;
263   }
264   while(l>0){
265     ec_enc_carry_out(_this,(int)(end>>EC_CODE_SHIFT));
266     end=end<<EC_SYM_BITS&EC_CODE_TOP-1;
267     l-=EC_SYM_BITS;
268   }
269   /*If we have a buffered byte flush it into the output buffer.*/
270   if(_this->rem>=0||_this->ext>0)ec_enc_carry_out(_this,0);
271   /*If we have buffered extra bits, flush them as well.*/
272   window=_this->end_window;
273   used=_this->nend_bits;
274   while(used>=EC_SYM_BITS){
275     _this->error|=ec_write_byte_at_end(_this,(unsigned)window&EC_SYM_MAX);
276     window>>=EC_SYM_BITS;
277     used-=EC_SYM_BITS;
278   }
279   /*Clear any excess space and add any remaining extra bits to the last byte.*/
280   if(!_this->error){
281     CELT_MEMSET(_this->buf+_this->offs,0,
282      _this->storage-_this->offs-_this->end_offs);
283     if(used>0){
284       /*If there's no range coder data at all, give up.*/
285       if(_this->end_offs>=_this->storage)_this->error=-1;
286       else{
287         l=-l;
288         /*If we've busted, don't add too many extra bits to the last byte; it
289            would corrupt the range coder data, and that's more important.*/
290         if(_this->offs+_this->end_offs>=_this->storage&&l<used){
291           window&=(1<<l)-1;
292           _this->error=-1;
293         }
294       }
295       _this->buf[_this->storage-_this->end_offs-1]|=(unsigned char)window;
296     }
297   }
298 }