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