Alexandre Lision | 744f742 | 2013-09-25 11:39:37 -0400 | [diff] [blame] | 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 | } |