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