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