Line data Source code
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 COPYRIGHT OWNER
19 : OR 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 0 : static int ec_write_byte(ec_enc *_this,unsigned _value){
61 0 : if(_this->offs+_this->end_offs>=_this->storage)return -1;
62 0 : _this->buf[_this->offs++]=(unsigned char)_value;
63 0 : return 0;
64 : }
65 :
66 0 : static int ec_write_byte_at_end(ec_enc *_this,unsigned _value){
67 0 : if(_this->offs+_this->end_offs>=_this->storage)return -1;
68 0 : _this->buf[_this->storage-++(_this->end_offs)]=(unsigned char)_value;
69 0 : 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 0 : static void ec_enc_carry_out(ec_enc *_this,int _c){
83 0 : if(_c!=EC_SYM_MAX){
84 : /*No further carry propagation possible, flush buffer.*/
85 : int carry;
86 0 : 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 0 : if(_this->rem>=0)_this->error|=ec_write_byte(_this,_this->rem+carry);
90 0 : if(_this->ext>0){
91 : unsigned sym;
92 0 : sym=(EC_SYM_MAX+carry)&EC_SYM_MAX;
93 0 : do _this->error|=ec_write_byte(_this,sym);
94 0 : while(--(_this->ext)>0);
95 : }
96 0 : _this->rem=_c&EC_SYM_MAX;
97 : }
98 0 : else _this->ext++;
99 0 : }
100 :
101 0 : static OPUS_INLINE void ec_enc_normalize(ec_enc *_this){
102 : /*If the range is too small, output some bits and rescale it.*/
103 0 : while(_this->rng<=EC_CODE_BOT){
104 0 : 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 0 : _this->val=(_this->val<<EC_SYM_BITS)&(EC_CODE_TOP-1);
107 0 : _this->rng<<=EC_SYM_BITS;
108 0 : _this->nbits_total+=EC_SYM_BITS;
109 : }
110 0 : }
111 :
112 0 : void ec_enc_init(ec_enc *_this,unsigned char *_buf,opus_uint32 _size){
113 0 : _this->buf=_buf;
114 0 : _this->end_offs=0;
115 0 : _this->end_window=0;
116 0 : _this->nend_bits=0;
117 : /*This is the offset from which ec_tell() will subtract partial bits.*/
118 0 : _this->nbits_total=EC_CODE_BITS+1;
119 0 : _this->offs=0;
120 0 : _this->rng=EC_CODE_TOP;
121 0 : _this->rem=-1;
122 0 : _this->val=0;
123 0 : _this->ext=0;
124 0 : _this->storage=_size;
125 0 : _this->error=0;
126 0 : }
127 :
128 0 : void ec_encode(ec_enc *_this,unsigned _fl,unsigned _fh,unsigned _ft){
129 : opus_uint32 r;
130 0 : r=celt_udiv(_this->rng,_ft);
131 0 : if(_fl>0){
132 0 : _this->val+=_this->rng-IMUL32(r,(_ft-_fl));
133 0 : _this->rng=IMUL32(r,(_fh-_fl));
134 : }
135 0 : else _this->rng-=IMUL32(r,(_ft-_fh));
136 0 : ec_enc_normalize(_this);
137 0 : }
138 :
139 0 : void ec_encode_bin(ec_enc *_this,unsigned _fl,unsigned _fh,unsigned _bits){
140 : opus_uint32 r;
141 0 : r=_this->rng>>_bits;
142 0 : if(_fl>0){
143 0 : _this->val+=_this->rng-IMUL32(r,((1U<<_bits)-_fl));
144 0 : _this->rng=IMUL32(r,(_fh-_fl));
145 : }
146 0 : else _this->rng-=IMUL32(r,((1U<<_bits)-_fh));
147 0 : ec_enc_normalize(_this);
148 0 : }
149 :
150 : /*The probability of having a "one" is 1/(1<<_logp).*/
151 0 : 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 0 : r=_this->rng;
156 0 : l=_this->val;
157 0 : s=r>>_logp;
158 0 : r-=s;
159 0 : if(_val)_this->val=l+r;
160 0 : _this->rng=_val?s:r;
161 0 : ec_enc_normalize(_this);
162 0 : }
163 :
164 0 : void ec_enc_icdf(ec_enc *_this,int _s,const unsigned char *_icdf,unsigned _ftb){
165 : opus_uint32 r;
166 0 : r=_this->rng>>_ftb;
167 0 : if(_s>0){
168 0 : _this->val+=_this->rng-IMUL32(r,_icdf[_s-1]);
169 0 : _this->rng=IMUL32(r,_icdf[_s-1]-_icdf[_s]);
170 : }
171 0 : else _this->rng-=IMUL32(r,_icdf[_s]);
172 0 : ec_enc_normalize(_this);
173 0 : }
174 :
175 0 : 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 0 : celt_assert(_ft>1);
181 0 : _ft--;
182 0 : ftb=EC_ILOG(_ft);
183 0 : if(ftb>EC_UINT_BITS){
184 0 : ftb-=EC_UINT_BITS;
185 0 : ft=(_ft>>ftb)+1;
186 0 : fl=(unsigned)(_fl>>ftb);
187 0 : ec_encode(_this,fl,fl+1,ft);
188 0 : ec_enc_bits(_this,_fl&(((opus_uint32)1<<ftb)-1U),ftb);
189 : }
190 0 : else ec_encode(_this,_fl,_fl+1,_ft+1);
191 0 : }
192 :
193 0 : void ec_enc_bits(ec_enc *_this,opus_uint32 _fl,unsigned _bits){
194 : ec_window window;
195 : int used;
196 0 : window=_this->end_window;
197 0 : used=_this->nend_bits;
198 0 : celt_assert(_bits>0);
199 0 : if(used+_bits>EC_WINDOW_SIZE){
200 : do{
201 0 : _this->error|=ec_write_byte_at_end(_this,(unsigned)window&EC_SYM_MAX);
202 0 : window>>=EC_SYM_BITS;
203 0 : used-=EC_SYM_BITS;
204 : }
205 0 : while(used>=EC_SYM_BITS);
206 : }
207 0 : window|=(ec_window)_fl<<used;
208 0 : used+=_bits;
209 0 : _this->end_window=window;
210 0 : _this->nend_bits=used;
211 0 : _this->nbits_total+=_bits;
212 0 : }
213 :
214 0 : void ec_enc_patch_initial_bits(ec_enc *_this,unsigned _val,unsigned _nbits){
215 : int shift;
216 : unsigned mask;
217 0 : celt_assert(_nbits<=EC_SYM_BITS);
218 0 : shift=EC_SYM_BITS-_nbits;
219 0 : mask=((1<<_nbits)-1)<<shift;
220 0 : if(_this->offs>0){
221 : /*The first byte has been finalized.*/
222 0 : _this->buf[0]=(unsigned char)((_this->buf[0]&~mask)|_val<<shift);
223 : }
224 0 : else if(_this->rem>=0){
225 : /*The first byte is still awaiting carry propagation.*/
226 0 : _this->rem=(_this->rem&~mask)|_val<<shift;
227 : }
228 0 : else if(_this->rng<=(EC_CODE_TOP>>_nbits)){
229 : /*The renormalization loop has never been run.*/
230 0 : _this->val=(_this->val&~((opus_uint32)mask<<EC_CODE_SHIFT))|
231 0 : (opus_uint32)_val<<(EC_CODE_SHIFT+shift);
232 : }
233 : /*The encoder hasn't even encoded _nbits of data yet.*/
234 0 : else _this->error=-1;
235 0 : }
236 :
237 0 : void ec_enc_shrink(ec_enc *_this,opus_uint32 _size){
238 0 : celt_assert(_this->offs+_this->end_offs<=_size);
239 0 : OPUS_MOVE(_this->buf+_size-_this->end_offs,
240 : _this->buf+_this->storage-_this->end_offs,_this->end_offs);
241 0 : _this->storage=_size;
242 0 : }
243 :
244 0 : void ec_enc_done(ec_enc *_this){
245 : ec_window window;
246 : int used;
247 : opus_uint32 msk;
248 : opus_uint32 end;
249 : int l;
250 : /*We output the minimum number of bits that ensures that the symbols encoded
251 : thus far will be decoded correctly regardless of the bits that follow.*/
252 0 : l=EC_CODE_BITS-EC_ILOG(_this->rng);
253 0 : msk=(EC_CODE_TOP-1)>>l;
254 0 : end=(_this->val+msk)&~msk;
255 0 : if((end|msk)>=_this->val+_this->rng){
256 0 : l++;
257 0 : msk>>=1;
258 0 : end=(_this->val+msk)&~msk;
259 : }
260 0 : while(l>0){
261 0 : ec_enc_carry_out(_this,(int)(end>>EC_CODE_SHIFT));
262 0 : end=(end<<EC_SYM_BITS)&(EC_CODE_TOP-1);
263 0 : l-=EC_SYM_BITS;
264 : }
265 : /*If we have a buffered byte flush it into the output buffer.*/
266 0 : if(_this->rem>=0||_this->ext>0)ec_enc_carry_out(_this,0);
267 : /*If we have buffered extra bits, flush them as well.*/
268 0 : window=_this->end_window;
269 0 : used=_this->nend_bits;
270 0 : while(used>=EC_SYM_BITS){
271 0 : _this->error|=ec_write_byte_at_end(_this,(unsigned)window&EC_SYM_MAX);
272 0 : window>>=EC_SYM_BITS;
273 0 : used-=EC_SYM_BITS;
274 : }
275 : /*Clear any excess space and add any remaining extra bits to the last byte.*/
276 0 : if(!_this->error){
277 0 : OPUS_CLEAR(_this->buf+_this->offs,
278 : _this->storage-_this->offs-_this->end_offs);
279 0 : if(used>0){
280 : /*If there's no range coder data at all, give up.*/
281 0 : if(_this->end_offs>=_this->storage)_this->error=-1;
282 : else{
283 0 : l=-l;
284 : /*If we've busted, don't add too many extra bits to the last byte; it
285 : would corrupt the range coder data, and that's more important.*/
286 0 : if(_this->offs+_this->end_offs>=_this->storage&&l<used){
287 0 : window&=(1<<l)-1;
288 0 : _this->error=-1;
289 : }
290 0 : _this->buf[_this->storage-_this->end_offs-1]|=(unsigned char)window;
291 : }
292 : }
293 : }
294 0 : }
|
