cannam@154: /* Copyright (c) 2001-2011 Timothy B. Terriberry cannam@154: Copyright (c) 2008-2009 Xiph.Org Foundation */ cannam@154: /* cannam@154: Redistribution and use in source and binary forms, with or without cannam@154: modification, are permitted provided that the following conditions cannam@154: are met: cannam@154: cannam@154: - Redistributions of source code must retain the above copyright cannam@154: notice, this list of conditions and the following disclaimer. cannam@154: cannam@154: - Redistributions in binary form must reproduce the above copyright cannam@154: notice, this list of conditions and the following disclaimer in the cannam@154: documentation and/or other materials provided with the distribution. cannam@154: cannam@154: THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS cannam@154: ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT cannam@154: LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR cannam@154: A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER cannam@154: OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, cannam@154: EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, cannam@154: PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR cannam@154: PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF cannam@154: LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING cannam@154: NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS cannam@154: SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. cannam@154: */ cannam@154: cannam@154: #ifdef HAVE_CONFIG_H cannam@154: #include "config.h" cannam@154: #endif cannam@154: cannam@154: #include cannam@154: #include "os_support.h" cannam@154: #include "arch.h" cannam@154: #include "entdec.h" cannam@154: #include "mfrngcod.h" cannam@154: cannam@154: /*A range decoder. cannam@154: This is an entropy decoder based upon \cite{Mar79}, which is itself a cannam@154: rediscovery of the FIFO arithmetic code introduced by \cite{Pas76}. cannam@154: It is very similar to arithmetic encoding, except that encoding is done with cannam@154: digits in any base, instead of with bits, and so it is faster when using cannam@154: larger bases (i.e.: a byte). cannam@154: The author claims an average waste of $\frac{1}{2}\log_b(2b)$ bits, where $b$ cannam@154: is the base, longer than the theoretical optimum, but to my knowledge there cannam@154: is no published justification for this claim. cannam@154: This only seems true when using near-infinite precision arithmetic so that cannam@154: the process is carried out with no rounding errors. cannam@154: cannam@154: An excellent description of implementation details is available at cannam@154: http://www.arturocampos.com/ac_range.html cannam@154: A recent work \cite{MNW98} which proposes several changes to arithmetic cannam@154: encoding for efficiency actually re-discovers many of the principles cannam@154: behind range encoding, and presents a good theoretical analysis of them. cannam@154: cannam@154: End of stream is handled by writing out the smallest number of bits that cannam@154: ensures that the stream will be correctly decoded regardless of the value of cannam@154: any subsequent bits. cannam@154: ec_tell() can be used to determine how many bits were needed to decode cannam@154: all the symbols thus far; other data can be packed in the remaining bits of cannam@154: the input buffer. cannam@154: @PHDTHESIS{Pas76, cannam@154: author="Richard Clark Pasco", cannam@154: title="Source coding algorithms for fast data compression", cannam@154: school="Dept. of Electrical Engineering, Stanford University", cannam@154: address="Stanford, CA", cannam@154: month=May, cannam@154: year=1976 cannam@154: } cannam@154: @INPROCEEDINGS{Mar79, cannam@154: author="Martin, G.N.N.", cannam@154: title="Range encoding: an algorithm for removing redundancy from a digitised cannam@154: message", cannam@154: booktitle="Video & Data Recording Conference", cannam@154: year=1979, cannam@154: address="Southampton", cannam@154: month=Jul cannam@154: } cannam@154: @ARTICLE{MNW98, cannam@154: author="Alistair Moffat and Radford Neal and Ian H. Witten", cannam@154: title="Arithmetic Coding Revisited", cannam@154: journal="{ACM} Transactions on Information Systems", cannam@154: year=1998, cannam@154: volume=16, cannam@154: number=3, cannam@154: pages="256--294", cannam@154: month=Jul, cannam@154: URL="http://www.stanford.edu/class/ee398a/handouts/papers/Moffat98ArithmCoding.pdf" cannam@154: }*/ cannam@154: cannam@154: static int ec_read_byte(ec_dec *_this){ cannam@154: return _this->offs<_this->storage?_this->buf[_this->offs++]:0; cannam@154: } cannam@154: cannam@154: static int ec_read_byte_from_end(ec_dec *_this){ cannam@154: return _this->end_offs<_this->storage? cannam@154: _this->buf[_this->storage-++(_this->end_offs)]:0; cannam@154: } cannam@154: cannam@154: /*Normalizes the contents of val and rng so that rng lies entirely in the cannam@154: high-order symbol.*/ cannam@154: static void ec_dec_normalize(ec_dec *_this){ cannam@154: /*If the range is too small, rescale it and input some bits.*/ cannam@154: while(_this->rng<=EC_CODE_BOT){ cannam@154: int sym; cannam@154: _this->nbits_total+=EC_SYM_BITS; cannam@154: _this->rng<<=EC_SYM_BITS; cannam@154: /*Use up the remaining bits from our last symbol.*/ cannam@154: sym=_this->rem; cannam@154: /*Read the next value from the input.*/ cannam@154: _this->rem=ec_read_byte(_this); cannam@154: /*Take the rest of the bits we need from this new symbol.*/ cannam@154: sym=(sym<rem)>>(EC_SYM_BITS-EC_CODE_EXTRA); cannam@154: /*And subtract them from val, capped to be less than EC_CODE_TOP.*/ cannam@154: _this->val=((_this->val<buf=_buf; cannam@154: _this->storage=_storage; cannam@154: _this->end_offs=0; cannam@154: _this->end_window=0; cannam@154: _this->nend_bits=0; cannam@154: /*This is the offset from which ec_tell() will subtract partial bits. cannam@154: The final value after the ec_dec_normalize() call will be the same as in cannam@154: the encoder, but we have to compensate for the bits that are added there.*/ cannam@154: _this->nbits_total=EC_CODE_BITS+1 cannam@154: -((EC_CODE_BITS-EC_CODE_EXTRA)/EC_SYM_BITS)*EC_SYM_BITS; cannam@154: _this->offs=0; cannam@154: _this->rng=1U<rem=ec_read_byte(_this); cannam@154: _this->val=_this->rng-1-(_this->rem>>(EC_SYM_BITS-EC_CODE_EXTRA)); cannam@154: _this->error=0; cannam@154: /*Normalize the interval.*/ cannam@154: ec_dec_normalize(_this); cannam@154: } cannam@154: cannam@154: unsigned ec_decode(ec_dec *_this,unsigned _ft){ cannam@154: unsigned s; cannam@154: _this->ext=celt_udiv(_this->rng,_ft); cannam@154: s=(unsigned)(_this->val/_this->ext); cannam@154: return _ft-EC_MINI(s+1,_ft); cannam@154: } cannam@154: cannam@154: unsigned ec_decode_bin(ec_dec *_this,unsigned _bits){ cannam@154: unsigned s; cannam@154: _this->ext=_this->rng>>_bits; cannam@154: s=(unsigned)(_this->val/_this->ext); cannam@154: return (1U<<_bits)-EC_MINI(s+1U,1U<<_bits); cannam@154: } cannam@154: cannam@154: void ec_dec_update(ec_dec *_this,unsigned _fl,unsigned _fh,unsigned _ft){ cannam@154: opus_uint32 s; cannam@154: s=IMUL32(_this->ext,_ft-_fh); cannam@154: _this->val-=s; cannam@154: _this->rng=_fl>0?IMUL32(_this->ext,_fh-_fl):_this->rng-s; cannam@154: ec_dec_normalize(_this); cannam@154: } cannam@154: cannam@154: /*The probability of having a "one" is 1/(1<<_logp).*/ cannam@154: int ec_dec_bit_logp(ec_dec *_this,unsigned _logp){ cannam@154: opus_uint32 r; cannam@154: opus_uint32 d; cannam@154: opus_uint32 s; cannam@154: int ret; cannam@154: r=_this->rng; cannam@154: d=_this->val; cannam@154: s=r>>_logp; cannam@154: ret=dval=d-s; cannam@154: _this->rng=ret?s:r-s; cannam@154: ec_dec_normalize(_this); cannam@154: return ret; cannam@154: } cannam@154: cannam@154: int ec_dec_icdf(ec_dec *_this,const unsigned char *_icdf,unsigned _ftb){ cannam@154: opus_uint32 r; cannam@154: opus_uint32 d; cannam@154: opus_uint32 s; cannam@154: opus_uint32 t; cannam@154: int ret; cannam@154: s=_this->rng; cannam@154: d=_this->val; cannam@154: r=s>>_ftb; cannam@154: ret=-1; cannam@154: do{ cannam@154: t=s; cannam@154: s=IMUL32(r,_icdf[++ret]); cannam@154: } cannam@154: while(dval=d-s; cannam@154: _this->rng=t-s; cannam@154: ec_dec_normalize(_this); cannam@154: return ret; cannam@154: } cannam@154: cannam@154: opus_uint32 ec_dec_uint(ec_dec *_this,opus_uint32 _ft){ cannam@154: unsigned ft; cannam@154: unsigned s; cannam@154: int ftb; cannam@154: /*In order to optimize EC_ILOG(), it is undefined for the value 0.*/ cannam@154: celt_assert(_ft>1); cannam@154: _ft--; cannam@154: ftb=EC_ILOG(_ft); cannam@154: if(ftb>EC_UINT_BITS){ cannam@154: opus_uint32 t; cannam@154: ftb-=EC_UINT_BITS; cannam@154: ft=(unsigned)(_ft>>ftb)+1; cannam@154: s=ec_decode(_this,ft); cannam@154: ec_dec_update(_this,s,s+1,ft); cannam@154: t=(opus_uint32)s<error=1; cannam@154: return _ft; cannam@154: } cannam@154: else{ cannam@154: _ft++; cannam@154: s=ec_decode(_this,(unsigned)_ft); cannam@154: ec_dec_update(_this,s,s+1,(unsigned)_ft); cannam@154: return s; cannam@154: } cannam@154: } cannam@154: cannam@154: opus_uint32 ec_dec_bits(ec_dec *_this,unsigned _bits){ cannam@154: ec_window window; cannam@154: int available; cannam@154: opus_uint32 ret; cannam@154: window=_this->end_window; cannam@154: available=_this->nend_bits; cannam@154: if((unsigned)available<_bits){ cannam@154: do{ cannam@154: window|=(ec_window)ec_read_byte_from_end(_this)<>=_bits; cannam@154: available-=_bits; cannam@154: _this->end_window=window; cannam@154: _this->nend_bits=available; cannam@154: _this->nbits_total+=_bits; cannam@154: return ret; cannam@154: }