entdec.c 7.83 KB
 Timothy B. Terriberry committed Feb 03, 2011 1 /* Copyright (c) 2001-2011 Timothy B. Terriberry  Jean-Marc Valin committed Oct 17, 2009 2  Copyright (c) 2008-2009 Xiph.Org Foundation */  Gregory Maxwell committed Feb 03, 2009 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 /* Redistribution and use in source and binary forms, with or without modification, are permitted provided that the following conditions are met: - Redistributions of source code must retain the above copyright notice, this list of conditions and the following disclaimer. - Redistributions in binary form must reproduce the above copyright notice, this list of conditions and the following disclaimer in the documentation and/or other materials provided with the distribution. THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR  Jean-Marc Valin committed Apr 20, 2012 18 19  A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,  Gregory Maxwell committed Feb 03, 2009 20 21 22 23 24 25 26 27  EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. */  Jean-Marc Valin committed Feb 20, 2008 28 29 30 31 #ifdef HAVE_CONFIG_H #include "config.h" #endif  Timothy B. Terriberry committed Dec 06, 2007 32 #include  Jean-Marc Valin committed Apr 28, 2008 33 #include "os_support.h"  34 #include "arch.h"  Timothy B. Terriberry committed Feb 03, 2011 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 #include "entdec.h" #include "mfrngcod.h" /*A range decoder. This is an entropy decoder based upon \cite{Mar79}, which is itself a rediscovery of the FIFO arithmetic code introduced by \cite{Pas76}. It is very similar to arithmetic encoding, except that encoding is done with digits in any base, instead of with bits, and so it is faster when using larger bases (i.e.: a byte). The author claims an average waste of $\frac{1}{2}\log_b(2b)$ bits, where $b$ is the base, longer than the theoretical optimum, but to my knowledge there is no published justification for this claim. This only seems true when using near-infinite precision arithmetic so that the process is carried out with no rounding errors. An excellent description of implementation details is available at http://www.arturocampos.com/ac_range.html A recent work \cite{MNW98} which proposes several changes to arithmetic encoding for efficiency actually re-discovers many of the principles behind range encoding, and presents a good theoretical analysis of them. End of stream is handled by writing out the smallest number of bits that ensures that the stream will be correctly decoded regardless of the value of any subsequent bits. ec_tell() can be used to determine how many bits were needed to decode all the symbols thus far; other data can be packed in the remaining bits of the input buffer. @PHDTHESIS{Pas76, author="Richard Clark Pasco", title="Source coding algorithms for fast data compression", school="Dept. of Electrical Engineering, Stanford University", address="Stanford, CA", month=May, year=1976 } @INPROCEEDINGS{Mar79, author="Martin, G.N.N.", title="Range encoding: an algorithm for removing redundancy from a digitised message", booktitle="Video & Data Recording Conference", year=1979, address="Southampton", month=Jul } @ARTICLE{MNW98, author="Alistair Moffat and Radford Neal and Ian H. Witten", title="Arithmetic Coding Revisited", journal="{ACM} Transactions on Information Systems", year=1998, volume=16, number=3, pages="256--294", month=Jul,  Timothy B. Terriberry committed Aug 04, 2013 88  URL="http://www.stanford.edu/class/ee398a/handouts/papers/Moffat98ArithmCoding.pdf"  Timothy B. Terriberry committed Feb 03, 2011 89 90 91 92  }*/ static int ec_read_byte(ec_dec *_this){ return _this->offs<_this->storage?_this->buf[_this->offs++]:0;  Timothy B. Terriberry committed Dec 06, 2007 93 94 }  Timothy B. Terriberry committed Feb 03, 2011 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 static int ec_read_byte_from_end(ec_dec *_this){ return _this->end_offs<_this->storage? _this->buf[_this->storage-++(_this->end_offs)]:0; } /*Normalizes the contents of val and rng so that rng lies entirely in the high-order symbol.*/ static void ec_dec_normalize(ec_dec *_this){ /*If the range is too small, rescale it and input some bits.*/ while(_this->rng<=EC_CODE_BOT){ int sym; _this->nbits_total+=EC_SYM_BITS; _this->rng<<=EC_SYM_BITS; /*Use up the remaining bits from our last symbol.*/ sym=_this->rem; /*Read the next value from the input.*/ _this->rem=ec_read_byte(_this); /*Take the rest of the bits we need from this new symbol.*/  Gregory Maxwell committed Aug 30, 2011 113  sym=(sym<rem)>>(EC_SYM_BITS-EC_CODE_EXTRA);  Timothy B. Terriberry committed Feb 03, 2011 114  /*And subtract them from val, capped to be less than EC_CODE_TOP.*/  Gregory Maxwell committed Aug 30, 2011 115  _this->val=((_this->val<buf=_buf; _this->storage=_storage; _this->end_offs=0; _this->end_window=0; _this->nend_bits=0;  Timothy B. Terriberry committed Dec 02, 2011 125 126 127 128 129  /*This is the offset from which ec_tell() will subtract partial bits. The final value after the ec_dec_normalize() call will be the same as in the encoder, but we have to compensate for the bits that are added there.*/ _this->nbits_total=EC_CODE_BITS+1 -((EC_CODE_BITS-EC_CODE_EXTRA)/EC_SYM_BITS)*EC_SYM_BITS;  Timothy B. Terriberry committed Feb 03, 2011 130 131 132  _this->offs=0; _this->rng=1U<rem=ec_read_byte(_this);  Gregory Maxwell committed Aug 30, 2011 133  _this->val=_this->rng-1-(_this->rem>>(EC_SYM_BITS-EC_CODE_EXTRA));  Timothy B. Terriberry committed Feb 03, 2011 134 135 136 137 138 139 140  _this->error=0; /*Normalize the interval.*/ ec_dec_normalize(_this); } unsigned ec_decode(ec_dec *_this,unsigned _ft){ unsigned s;  Jean-Marc Valin committed Jan 20, 2014 141  _this->ext=celt_udiv(_this->rng,_ft);  Timothy B. Terriberry committed Feb 03, 2011 142 143 144 145 146 147 148 149  s=(unsigned)(_this->val/_this->ext); return _ft-EC_MINI(s+1,_ft); } unsigned ec_decode_bin(ec_dec *_this,unsigned _bits){ unsigned s; _this->ext=_this->rng>>_bits; s=(unsigned)(_this->val/_this->ext);  Gregory Maxwell committed Aug 30, 2011 150  return (1U<<_bits)-EC_MINI(s+1U,1U<<_bits);  Timothy B. Terriberry committed Feb 03, 2011 151 152 153 } void ec_dec_update(ec_dec *_this,unsigned _fl,unsigned _fh,unsigned _ft){  Jean-Marc Valin committed Jul 29, 2011 154  opus_uint32 s;  Timothy B. Terriberry committed Feb 03, 2011 155 156 157 158 159 160 161 162  s=IMUL32(_this->ext,_ft-_fh); _this->val-=s; _this->rng=_fl>0?IMUL32(_this->ext,_fh-_fl):_this->rng-s; ec_dec_normalize(_this); } /*The probability of having a "one" is 1/(1<<_logp).*/ int ec_dec_bit_logp(ec_dec *_this,unsigned _logp){  Jean-Marc Valin committed Jul 29, 2011 163 164 165  opus_uint32 r; opus_uint32 d; opus_uint32 s;  Timothy B. Terriberry committed Mar 02, 2011 166  int ret;  Timothy B. Terriberry committed Feb 03, 2011 167 168 169 170 171 172 173 174 175 176 177  r=_this->rng; d=_this->val; s=r>>_logp; ret=dval=d-s; _this->rng=ret?s:r-s; ec_dec_normalize(_this); return ret; } int ec_dec_icdf(ec_dec *_this,const unsigned char *_icdf,unsigned _ftb){  Jean-Marc Valin committed Jul 29, 2011 178 179 180 181  opus_uint32 r; opus_uint32 d; opus_uint32 s; opus_uint32 t;  Timothy B. Terriberry committed Mar 02, 2011 182  int ret;  Timothy B. Terriberry committed Feb 03, 2011 183 184 185 186 187 188 189 190 191 192 193 194 195  s=_this->rng; d=_this->val; r=s>>_ftb; ret=-1; do{ t=s; s=IMUL32(r,_icdf[++ret]); } while(dval=d-s; _this->rng=t-s; ec_dec_normalize(_this); return ret;  Timothy B. Terriberry committed Dec 06, 2007 196 197 }  Jean-Marc Valin committed Jul 29, 2011 198 opus_uint32 ec_dec_uint(ec_dec *_this,opus_uint32 _ft){  Timothy B. Terriberry committed Dec 21, 2010 199 200 201  unsigned ft; unsigned s; int ftb;  202 203  /*In order to optimize EC_ILOG(), it is undefined for the value 0.*/ celt_assert(_ft>1);  Timothy B. Terriberry committed Dec 06, 2007 204 205  _ft--; ftb=EC_ILOG(_ft);  Timothy B. Terriberry committed Dec 21, 2010 206  if(ftb>EC_UINT_BITS){  Jean-Marc Valin committed Jul 29, 2011 207  opus_uint32 t;  Timothy B. Terriberry committed Dec 21, 2010 208  ftb-=EC_UINT_BITS;  Timothy B. Terriberry committed Dec 11, 2007 209  ft=(unsigned)(_ft>>ftb)+1;  Timothy B. Terriberry committed Dec 06, 2007 210 211  s=ec_decode(_this,ft); ec_dec_update(_this,s,s+1,ft);  Jean-Marc Valin committed Jul 29, 2011 212  t=(opus_uint32)s<error=1; return _ft; } else{  Jean-Marc Valin committed Mar 22, 2008 218 219 220  _ft++; s=ec_decode(_this,(unsigned)_ft); ec_dec_update(_this,s,s+1,(unsigned)_ft);  Jean-Marc Valin committed Oct 17, 2010 221  return s;  Timothy B. Terriberry committed Dec 06, 2007 222  }  Timothy B. Terriberry committed Dec 11, 2007 223 }  Jean-Marc Valin committed Jul 18, 2010 224   Jean-Marc Valin committed Jul 29, 2011 225 opus_uint32 ec_dec_bits(ec_dec *_this,unsigned _bits){  Timothy B. Terriberry committed Mar 02, 2011 226 227  ec_window window; int available;  Jean-Marc Valin committed Jul 29, 2011 228  opus_uint32 ret;  Timothy B. Terriberry committed Feb 03, 2011 229 230  window=_this->end_window; available=_this->nend_bits;  Gregory Maxwell committed Aug 30, 2011 231  if((unsigned)available<_bits){  Timothy B. Terriberry committed Feb 03, 2011 232 233 234 235 236 237  do{ window|=(ec_window)ec_read_byte_from_end(_this)<>=_bits; available-=_bits; _this->end_window=window; _this->nend_bits=available; _this->nbits_total+=_bits; return ret;  Jean-Marc Valin committed Jul 18, 2010 245 }