Adds 3rd clause to CELT license
[opus.git] / celt / 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    - Neither the name of Internet Society, IETF or IETF Trust, nor the
16    names of specific contributors, may be used to endorse or promote
17    products derived from this software without specific prior written
18    permission.
19
20    THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
21    ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
22    LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
23    A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER
24    OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
25    EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
26    PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
27    PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
28    LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
29    NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
30    SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
31 */
32
33 #if defined(HAVE_CONFIG_H)
34 # include "config.h"
35 #endif
36 #include "os_support.h"
37 #include "arch.h"
38 #include "entenc.h"
39 #include "mfrngcod.h"
40
41 /*A range encoder.
42   See entdec.c and the references for implementation details \cite{Mar79,MNW98}.
43
44   @INPROCEEDINGS{Mar79,
45    author="Martin, G.N.N.",
46    title="Range encoding: an algorithm for removing redundancy from a digitised
47     message",
48    booktitle="Video \& Data Recording Conference",
49    year=1979,
50    address="Southampton",
51    month=Jul
52   }
53   @ARTICLE{MNW98,
54    author="Alistair Moffat and Radford Neal and Ian H. Witten",
55    title="Arithmetic Coding Revisited",
56    journal="{ACM} Transactions on Information Systems",
57    year=1998,
58    volume=16,
59    number=3,
60    pages="256--294",
61    month=Jul,
62    URL="http://www.stanford.edu/class/ee398/handouts/papers/Moffat98ArithmCoding.pdf"
63   }*/
64
65 static int ec_write_byte(ec_enc *_this,unsigned _value){
66   if(_this->offs+_this->end_offs>=_this->storage)return -1;
67   _this->buf[_this->offs++]=(unsigned char)_value;
68   return 0;
69 }
70
71 static int ec_write_byte_at_end(ec_enc *_this,unsigned _value){
72   if(_this->offs+_this->end_offs>=_this->storage)return -1;
73   _this->buf[_this->storage-++(_this->end_offs)]=(unsigned char)_value;
74   return 0;
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,opus_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   opus_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   opus_uint32 r;
146   r=_this->rng>>_bits;
147   if(_fl>0){
148     _this->val+=_this->rng-IMUL32(r,((1U<<_bits)-_fl));
149     _this->rng=IMUL32(r,(_fh-_fl));
150   }
151   else _this->rng-=IMUL32(r,((1U<<_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   opus_uint32 r;
158   opus_uint32 s;
159   opus_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   opus_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,opus_uint32 _fl,opus_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&(((opus_uint32)1<<ftb)-1U),ftb);
194   }
195   else ec_encode(_this,_fl,_fl+1,_ft+1);
196 }
197
198 void ec_enc_bits(ec_enc *_this,opus_uint32 _fl,unsigned _bits){
199   ec_window window;
200   int       used;
201   window=_this->end_window;
202   used=_this->nend_bits;
203   celt_assert(_bits>0);
204   if(used+_bits>EC_WINDOW_SIZE){
205     do{
206       _this->error|=ec_write_byte_at_end(_this,(unsigned)window&EC_SYM_MAX);
207       window>>=EC_SYM_BITS;
208       used-=EC_SYM_BITS;
209     }
210     while(used>=EC_SYM_BITS);
211   }
212   window|=(ec_window)_fl<<used;
213   used+=_bits;
214   _this->end_window=window;
215   _this->nend_bits=used;
216   _this->nbits_total+=_bits;
217 }
218
219 void ec_enc_patch_initial_bits(ec_enc *_this,unsigned _val,unsigned _nbits){
220   int      shift;
221   unsigned mask;
222   celt_assert(_nbits<=EC_SYM_BITS);
223   shift=EC_SYM_BITS-_nbits;
224   mask=((1<<_nbits)-1)<<shift;
225   if(_this->offs>0){
226     /*The first byte has been finalized.*/
227     _this->buf[0]=(unsigned char)((_this->buf[0]&~mask)|_val<<shift);
228   }
229   else if(_this->rem>=0){
230     /*The first byte is still awaiting carry propagation.*/
231     _this->rem=(_this->rem&~mask)|_val<<shift;
232   }
233   else if(_this->rng<=(EC_CODE_TOP>>_nbits)){
234     /*The renormalization loop has never been run.*/
235     _this->val=(_this->val&~((opus_uint32)mask<<EC_CODE_SHIFT))|
236      (opus_uint32)_val<<(EC_CODE_SHIFT+shift);
237   }
238   /*The encoder hasn't even encoded _nbits of data yet.*/
239   else _this->error=-1;
240 }
241
242 void ec_enc_shrink(ec_enc *_this,opus_uint32 _size){
243   celt_assert(_this->offs+_this->end_offs<=_size);
244   OPUS_MOVE(_this->buf+_size-_this->end_offs,
245    _this->buf+_this->storage-_this->end_offs,_this->end_offs);
246   _this->storage=_size;
247 }
248
249 void ec_enc_done(ec_enc *_this){
250   ec_window   window;
251   int         used;
252   opus_uint32 msk;
253   opus_uint32 end;
254   int         l;
255   /*We output the minimum number of bits that ensures that the symbols encoded
256      thus far will be decoded correctly regardless of the bits that follow.*/
257   l=EC_CODE_BITS-EC_ILOG(_this->rng);
258   msk=(EC_CODE_TOP-1)>>l;
259   end=(_this->val+msk)&~msk;
260   if((end|msk)>=_this->val+_this->rng){
261     l++;
262     msk>>=1;
263     end=(_this->val+msk)&~msk;
264   }
265   while(l>0){
266     ec_enc_carry_out(_this,(int)(end>>EC_CODE_SHIFT));
267     end=(end<<EC_SYM_BITS)&(EC_CODE_TOP-1);
268     l-=EC_SYM_BITS;
269   }
270   /*If we have a buffered byte flush it into the output buffer.*/
271   if(_this->rem>=0||_this->ext>0)ec_enc_carry_out(_this,0);
272   /*If we have buffered extra bits, flush them as well.*/
273   window=_this->end_window;
274   used=_this->nend_bits;
275   while(used>=EC_SYM_BITS){
276     _this->error|=ec_write_byte_at_end(_this,(unsigned)window&EC_SYM_MAX);
277     window>>=EC_SYM_BITS;
278     used-=EC_SYM_BITS;
279   }
280   /*Clear any excess space and add any remaining extra bits to the last byte.*/
281   if(!_this->error){
282     OPUS_CLEAR(_this->buf+_this->offs,
283      _this->storage-_this->offs-_this->end_offs);
284     if(used>0){
285       /*If there's no range coder data at all, give up.*/
286       if(_this->end_offs>=_this->storage)_this->error=-1;
287       else{
288         l=-l;
289         /*If we've busted, don't add too many extra bits to the last byte; it
290            would corrupt the range coder data, and that's more important.*/
291         if(_this->offs+_this->end_offs>=_this->storage&&l<used){
292           window&=(1<<l)-1;
293           _this->error=-1;
294         }
295         _this->buf[_this->storage-_this->end_offs-1]|=(unsigned char)window;
296       }
297     }
298   }
299 }