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 60static 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 66static 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.*/ 82static 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 101static 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 112void 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 128void 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 139void 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).*/ 151void 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 164void 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 175void 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 193void 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 214void 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 237void 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 244void 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} 295