entenc.c (9881B)
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 OPUS_INLINE 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=celt_udiv(_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_icdf16(ec_enc *_this,int _s,const opus_uint16 *_icdf,unsigned _ftb){ 176 opus_uint32 r; 177 r=_this->rng>>_ftb; 178 if(_s>0){ 179 _this->val+=_this->rng-IMUL32(r,_icdf[_s-1]); 180 _this->rng=IMUL32(r,_icdf[_s-1]-_icdf[_s]); 181 } 182 else _this->rng-=IMUL32(r,_icdf[_s]); 183 ec_enc_normalize(_this); 184 } 185 186 void ec_enc_uint(ec_enc *_this,opus_uint32 _fl,opus_uint32 _ft){ 187 unsigned ft; 188 unsigned fl; 189 int ftb; 190 /*In order to optimize EC_ILOG(), it is undefined for the value 0.*/ 191 celt_assert(_ft>1); 192 _ft--; 193 ftb=EC_ILOG(_ft); 194 if(ftb>EC_UINT_BITS){ 195 ftb-=EC_UINT_BITS; 196 ft=(_ft>>ftb)+1; 197 fl=(unsigned)(_fl>>ftb); 198 ec_encode(_this,fl,fl+1,ft); 199 ec_enc_bits(_this,_fl&(((opus_uint32)1<<ftb)-1U),ftb); 200 } 201 else ec_encode(_this,_fl,_fl+1,_ft+1); 202 } 203 204 void ec_enc_bits(ec_enc *_this,opus_uint32 _fl,unsigned _bits){ 205 ec_window window; 206 int used; 207 window=_this->end_window; 208 used=_this->nend_bits; 209 celt_assert(_bits>0); 210 if(used+_bits>EC_WINDOW_SIZE){ 211 do{ 212 _this->error|=ec_write_byte_at_end(_this,(unsigned)window&EC_SYM_MAX); 213 window>>=EC_SYM_BITS; 214 used-=EC_SYM_BITS; 215 } 216 while(used>=EC_SYM_BITS); 217 } 218 window|=(ec_window)_fl<<used; 219 used+=_bits; 220 _this->end_window=window; 221 _this->nend_bits=used; 222 _this->nbits_total+=_bits; 223 } 224 225 void ec_enc_patch_initial_bits(ec_enc *_this,unsigned _val,unsigned _nbits){ 226 int shift; 227 unsigned mask; 228 celt_assert(_nbits<=EC_SYM_BITS); 229 shift=EC_SYM_BITS-_nbits; 230 mask=((1<<_nbits)-1)<<shift; 231 if(_this->offs>0){ 232 /*The first byte has been finalized.*/ 233 _this->buf[0]=(unsigned char)((_this->buf[0]&~mask)|_val<<shift); 234 } 235 else if(_this->rem>=0){ 236 /*The first byte is still awaiting carry propagation.*/ 237 _this->rem=(_this->rem&~mask)|_val<<shift; 238 } 239 else if(_this->rng<=(EC_CODE_TOP>>_nbits)){ 240 /*The renormalization loop has never been run.*/ 241 _this->val=(_this->val&~((opus_uint32)mask<<EC_CODE_SHIFT))| 242 (opus_uint32)_val<<(EC_CODE_SHIFT+shift); 243 } 244 /*The encoder hasn't even encoded _nbits of data yet.*/ 245 else _this->error=-1; 246 } 247 248 void ec_enc_shrink(ec_enc *_this,opus_uint32 _size){ 249 celt_assert(_this->offs+_this->end_offs<=_size); 250 OPUS_MOVE(_this->buf+_size-_this->end_offs, 251 _this->buf+_this->storage-_this->end_offs,_this->end_offs); 252 _this->storage=_size; 253 } 254 255 void ec_enc_done(ec_enc *_this){ 256 ec_window window; 257 int used; 258 opus_uint32 msk; 259 opus_uint32 end; 260 int l; 261 /*We output the minimum number of bits that ensures that the symbols encoded 262 thus far will be decoded correctly regardless of the bits that follow.*/ 263 l=EC_CODE_BITS-EC_ILOG(_this->rng); 264 msk=(EC_CODE_TOP-1)>>l; 265 end=(_this->val+msk)&~msk; 266 if((end|msk)>=_this->val+_this->rng){ 267 l++; 268 msk>>=1; 269 end=(_this->val+msk)&~msk; 270 } 271 while(l>0){ 272 ec_enc_carry_out(_this,(int)(end>>EC_CODE_SHIFT)); 273 end=(end<<EC_SYM_BITS)&(EC_CODE_TOP-1); 274 l-=EC_SYM_BITS; 275 } 276 /*If we have a buffered byte flush it into the output buffer.*/ 277 if(_this->rem>=0||_this->ext>0)ec_enc_carry_out(_this,0); 278 /*If we have buffered extra bits, flush them as well.*/ 279 window=_this->end_window; 280 used=_this->nend_bits; 281 while(used>=EC_SYM_BITS){ 282 _this->error|=ec_write_byte_at_end(_this,(unsigned)window&EC_SYM_MAX); 283 window>>=EC_SYM_BITS; 284 used-=EC_SYM_BITS; 285 } 286 /*Clear any excess space and add any remaining extra bits to the last byte.*/ 287 if(!_this->error){ 288 if (_this->buf) OPUS_CLEAR(_this->buf+_this->offs, 289 _this->storage-_this->offs-_this->end_offs); 290 if(used>0){ 291 /*If there's no range coder data at all, give up.*/ 292 if(_this->end_offs>=_this->storage)_this->error=-1; 293 else{ 294 l=-l; 295 /*If we've busted, don't add too many extra bits to the last byte; it 296 would corrupt the range coder data, and that's more important.*/ 297 if(_this->offs+_this->end_offs>=_this->storage&&l<used){ 298 window&=(1<<l)-1; 299 _this->error=-1; 300 } 301 _this->buf[_this->storage-_this->end_offs-1]|=(unsigned char)window; 302 } 303 } 304 } 305 }