The Tor Browser / file comparison
comparison: media/libopus/celt/entenc.c
media/libopus/celt/entenc.c
- branch
- TOR_BUG_9701
- changeset 10
- ac0c01689b40
equal
deleted
inserted
replaced
| -1:000000000000 | 0:57ece290a034 |
|---|---|
| 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 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 celt_assert(_bits>0); | |
| 199 if(used+_bits>EC_WINDOW_SIZE){ | |
| 200 do{ | |
| 201 _this->error|=ec_write_byte_at_end(_this,(unsigned)window&EC_SYM_MAX); | |
| 202 window>>=EC_SYM_BITS; | |
| 203 used-=EC_SYM_BITS; | |
| 204 } | |
| 205 while(used>=EC_SYM_BITS); | |
| 206 } | |
| 207 window|=(ec_window)_fl<<used; | |
| 208 used+=_bits; | |
| 209 _this->end_window=window; | |
| 210 _this->nend_bits=used; | |
| 211 _this->nbits_total+=_bits; | |
| 212 } | |
| 213 | |
| 214 void ec_enc_patch_initial_bits(ec_enc *_this,unsigned _val,unsigned _nbits){ | |
| 215 int shift; | |
| 216 unsigned mask; | |
| 217 celt_assert(_nbits<=EC_SYM_BITS); | |
| 218 shift=EC_SYM_BITS-_nbits; | |
| 219 mask=((1<<_nbits)-1)<<shift; | |
| 220 if(_this->offs>0){ | |
| 221 /*The first byte has been finalized.*/ | |
| 222 _this->buf[0]=(unsigned char)((_this->buf[0]&~mask)|_val<<shift); | |
| 223 } | |
| 224 else if(_this->rem>=0){ | |
| 225 /*The first byte is still awaiting carry propagation.*/ | |
| 226 _this->rem=(_this->rem&~mask)|_val<<shift; | |
| 227 } | |
| 228 else if(_this->rng<=(EC_CODE_TOP>>_nbits)){ | |
| 229 /*The renormalization loop has never been run.*/ | |
| 230 _this->val=(_this->val&~((opus_uint32)mask<<EC_CODE_SHIFT))| | |
| 231 (opus_uint32)_val<<(EC_CODE_SHIFT+shift); | |
| 232 } | |
| 233 /*The encoder hasn't even encoded _nbits of data yet.*/ | |
| 234 else _this->error=-1; | |
| 235 } | |
| 236 | |
| 237 void ec_enc_shrink(ec_enc *_this,opus_uint32 _size){ | |
| 238 celt_assert(_this->offs+_this->end_offs<=_size); | |
| 239 OPUS_MOVE(_this->buf+_size-_this->end_offs, | |
| 240 _this->buf+_this->storage-_this->end_offs,_this->end_offs); | |
| 241 _this->storage=_size; | |
| 242 } | |
| 243 | |
| 244 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 l=EC_CODE_BITS-EC_ILOG(_this->rng); | |
| 253 msk=(EC_CODE_TOP-1)>>l; | |
| 254 end=(_this->val+msk)&~msk; | |
| 255 if((end|msk)>=_this->val+_this->rng){ | |
| 256 l++; | |
| 257 msk>>=1; | |
| 258 end=(_this->val+msk)&~msk; | |
| 259 } | |
| 260 while(l>0){ | |
| 261 ec_enc_carry_out(_this,(int)(end>>EC_CODE_SHIFT)); | |
| 262 end=(end<<EC_SYM_BITS)&(EC_CODE_TOP-1); | |
| 263 l-=EC_SYM_BITS; | |
| 264 } | |
| 265 /*If we have a buffered byte flush it into the output buffer.*/ | |
| 266 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 window=_this->end_window; | |
| 269 used=_this->nend_bits; | |
| 270 while(used>=EC_SYM_BITS){ | |
| 271 _this->error|=ec_write_byte_at_end(_this,(unsigned)window&EC_SYM_MAX); | |
| 272 window>>=EC_SYM_BITS; | |
| 273 used-=EC_SYM_BITS; | |
| 274 } | |
| 275 /*Clear any excess space and add any remaining extra bits to the last byte.*/ | |
| 276 if(!_this->error){ | |
| 277 OPUS_CLEAR(_this->buf+_this->offs, | |
| 278 _this->storage-_this->offs-_this->end_offs); | |
| 279 if(used>0){ | |
| 280 /*If there's no range coder data at all, give up.*/ | |
| 281 if(_this->end_offs>=_this->storage)_this->error=-1; | |
| 282 else{ | |
| 283 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 if(_this->offs+_this->end_offs>=_this->storage&&l<used){ | |
| 287 window&=(1<<l)-1; | |
| 288 _this->error=-1; | |
| 289 } | |
| 290 _this->buf[_this->storage-_this->end_offs-1]|=(unsigned char)window; | |
| 291 } | |
| 292 } | |
| 293 } | |
| 294 } |
