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: #if defined(HAVE_CONFIG_H)
cannam@154: # include "config.h"
cannam@154: #endif
cannam@154: #include "os_support.h"
cannam@154: #include "arch.h"
cannam@154: #include "entenc.h"
cannam@154: #include "mfrngcod.h"
cannam@154: 
cannam@154: /*A range encoder.
cannam@154:   See entdec.c and the references for implementation details \cite{Mar79,MNW98}.
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/ee398/handouts/papers/Moffat98ArithmCoding.pdf"
cannam@154:   }*/
cannam@154: 
cannam@154: static int ec_write_byte(ec_enc *_this,unsigned _value){
cannam@154:   if(_this->offs+_this->end_offs>=_this->storage)return -1;
cannam@154:   _this->buf[_this->offs++]=(unsigned char)_value;
cannam@154:   return 0;
cannam@154: }
cannam@154: 
cannam@154: static int ec_write_byte_at_end(ec_enc *_this,unsigned _value){
cannam@154:   if(_this->offs+_this->end_offs>=_this->storage)return -1;
cannam@154:   _this->buf[_this->storage-++(_this->end_offs)]=(unsigned char)_value;
cannam@154:   return 0;
cannam@154: }
cannam@154: 
cannam@154: /*Outputs a symbol, with a carry bit.
cannam@154:   If there is a potential to propagate a carry over several symbols, they are
cannam@154:    buffered until it can be determined whether or not an actual carry will
cannam@154:    occur.
cannam@154:   If the counter for the buffered symbols overflows, then the stream becomes
cannam@154:    undecodable.
cannam@154:   This gives a theoretical limit of a few billion symbols in a single packet on
cannam@154:    32-bit systems.
cannam@154:   The alternative is to truncate the range in order to force a carry, but
cannam@154:    requires similar carry tracking in the decoder, needlessly slowing it down.*/
cannam@154: static void ec_enc_carry_out(ec_enc *_this,int _c){
cannam@154:   if(_c!=EC_SYM_MAX){
cannam@154:     /*No further carry propagation possible, flush buffer.*/
cannam@154:     int carry;
cannam@154:     carry=_c>>EC_SYM_BITS;
cannam@154:     /*Don't output a byte on the first write.
cannam@154:       This compare should be taken care of by branch-prediction thereafter.*/
cannam@154:     if(_this->rem>=0)_this->error|=ec_write_byte(_this,_this->rem+carry);
cannam@154:     if(_this->ext>0){
cannam@154:       unsigned sym;
cannam@154:       sym=(EC_SYM_MAX+carry)&EC_SYM_MAX;
cannam@154:       do _this->error|=ec_write_byte(_this,sym);
cannam@154:       while(--(_this->ext)>0);
cannam@154:     }
cannam@154:     _this->rem=_c&EC_SYM_MAX;
cannam@154:   }
cannam@154:   else _this->ext++;
cannam@154: }
cannam@154: 
cannam@154: static OPUS_INLINE void ec_enc_normalize(ec_enc *_this){
cannam@154:   /*If the range is too small, output some bits and rescale it.*/
cannam@154:   while(_this->rng<=EC_CODE_BOT){
cannam@154:     ec_enc_carry_out(_this,(int)(_this->val>>EC_CODE_SHIFT));
cannam@154:     /*Move the next-to-high-order symbol into the high-order position.*/
cannam@154:     _this->val=(_this->val<<EC_SYM_BITS)&(EC_CODE_TOP-1);
cannam@154:     _this->rng<<=EC_SYM_BITS;
cannam@154:     _this->nbits_total+=EC_SYM_BITS;
cannam@154:   }
cannam@154: }
cannam@154: 
cannam@154: void ec_enc_init(ec_enc *_this,unsigned char *_buf,opus_uint32 _size){
cannam@154:   _this->buf=_buf;
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:   _this->nbits_total=EC_CODE_BITS+1;
cannam@154:   _this->offs=0;
cannam@154:   _this->rng=EC_CODE_TOP;
cannam@154:   _this->rem=-1;
cannam@154:   _this->val=0;
cannam@154:   _this->ext=0;
cannam@154:   _this->storage=_size;
cannam@154:   _this->error=0;
cannam@154: }
cannam@154: 
cannam@154: void ec_encode(ec_enc *_this,unsigned _fl,unsigned _fh,unsigned _ft){
cannam@154:   opus_uint32 r;
cannam@154:   r=celt_udiv(_this->rng,_ft);
cannam@154:   if(_fl>0){
cannam@154:     _this->val+=_this->rng-IMUL32(r,(_ft-_fl));
cannam@154:     _this->rng=IMUL32(r,(_fh-_fl));
cannam@154:   }
cannam@154:   else _this->rng-=IMUL32(r,(_ft-_fh));
cannam@154:   ec_enc_normalize(_this);
cannam@154: }
cannam@154: 
cannam@154: void ec_encode_bin(ec_enc *_this,unsigned _fl,unsigned _fh,unsigned _bits){
cannam@154:   opus_uint32 r;
cannam@154:   r=_this->rng>>_bits;
cannam@154:   if(_fl>0){
cannam@154:     _this->val+=_this->rng-IMUL32(r,((1U<<_bits)-_fl));
cannam@154:     _this->rng=IMUL32(r,(_fh-_fl));
cannam@154:   }
cannam@154:   else _this->rng-=IMUL32(r,((1U<<_bits)-_fh));
cannam@154:   ec_enc_normalize(_this);
cannam@154: }
cannam@154: 
cannam@154: /*The probability of having a "one" is 1/(1<<_logp).*/
cannam@154: void ec_enc_bit_logp(ec_enc *_this,int _val,unsigned _logp){
cannam@154:   opus_uint32 r;
cannam@154:   opus_uint32 s;
cannam@154:   opus_uint32 l;
cannam@154:   r=_this->rng;
cannam@154:   l=_this->val;
cannam@154:   s=r>>_logp;
cannam@154:   r-=s;
cannam@154:   if(_val)_this->val=l+r;
cannam@154:   _this->rng=_val?s:r;
cannam@154:   ec_enc_normalize(_this);
cannam@154: }
cannam@154: 
cannam@154: void ec_enc_icdf(ec_enc *_this,int _s,const unsigned char *_icdf,unsigned _ftb){
cannam@154:   opus_uint32 r;
cannam@154:   r=_this->rng>>_ftb;
cannam@154:   if(_s>0){
cannam@154:     _this->val+=_this->rng-IMUL32(r,_icdf[_s-1]);
cannam@154:     _this->rng=IMUL32(r,_icdf[_s-1]-_icdf[_s]);
cannam@154:   }
cannam@154:   else _this->rng-=IMUL32(r,_icdf[_s]);
cannam@154:   ec_enc_normalize(_this);
cannam@154: }
cannam@154: 
cannam@154: void ec_enc_uint(ec_enc *_this,opus_uint32 _fl,opus_uint32 _ft){
cannam@154:   unsigned  ft;
cannam@154:   unsigned  fl;
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:     ftb-=EC_UINT_BITS;
cannam@154:     ft=(_ft>>ftb)+1;
cannam@154:     fl=(unsigned)(_fl>>ftb);
cannam@154:     ec_encode(_this,fl,fl+1,ft);
cannam@154:     ec_enc_bits(_this,_fl&(((opus_uint32)1<<ftb)-1U),ftb);
cannam@154:   }
cannam@154:   else ec_encode(_this,_fl,_fl+1,_ft+1);
cannam@154: }
cannam@154: 
cannam@154: void ec_enc_bits(ec_enc *_this,opus_uint32 _fl,unsigned _bits){
cannam@154:   ec_window window;
cannam@154:   int       used;
cannam@154:   window=_this->end_window;
cannam@154:   used=_this->nend_bits;
cannam@154:   celt_assert(_bits>0);
cannam@154:   if(used+_bits>EC_WINDOW_SIZE){
cannam@154:     do{
cannam@154:       _this->error|=ec_write_byte_at_end(_this,(unsigned)window&EC_SYM_MAX);
cannam@154:       window>>=EC_SYM_BITS;
cannam@154:       used-=EC_SYM_BITS;
cannam@154:     }
cannam@154:     while(used>=EC_SYM_BITS);
cannam@154:   }
cannam@154:   window|=(ec_window)_fl<<used;
cannam@154:   used+=_bits;
cannam@154:   _this->end_window=window;
cannam@154:   _this->nend_bits=used;
cannam@154:   _this->nbits_total+=_bits;
cannam@154: }
cannam@154: 
cannam@154: void ec_enc_patch_initial_bits(ec_enc *_this,unsigned _val,unsigned _nbits){
cannam@154:   int      shift;
cannam@154:   unsigned mask;
cannam@154:   celt_assert(_nbits<=EC_SYM_BITS);
cannam@154:   shift=EC_SYM_BITS-_nbits;
cannam@154:   mask=((1<<_nbits)-1)<<shift;
cannam@154:   if(_this->offs>0){
cannam@154:     /*The first byte has been finalized.*/
cannam@154:     _this->buf[0]=(unsigned char)((_this->buf[0]&~mask)|_val<<shift);
cannam@154:   }
cannam@154:   else if(_this->rem>=0){
cannam@154:     /*The first byte is still awaiting carry propagation.*/
cannam@154:     _this->rem=(_this->rem&~mask)|_val<<shift;
cannam@154:   }
cannam@154:   else if(_this->rng<=(EC_CODE_TOP>>_nbits)){
cannam@154:     /*The renormalization loop has never been run.*/
cannam@154:     _this->val=(_this->val&~((opus_uint32)mask<<EC_CODE_SHIFT))|
cannam@154:      (opus_uint32)_val<<(EC_CODE_SHIFT+shift);
cannam@154:   }
cannam@154:   /*The encoder hasn't even encoded _nbits of data yet.*/
cannam@154:   else _this->error=-1;
cannam@154: }
cannam@154: 
cannam@154: void ec_enc_shrink(ec_enc *_this,opus_uint32 _size){
cannam@154:   celt_assert(_this->offs+_this->end_offs<=_size);
cannam@154:   OPUS_MOVE(_this->buf+_size-_this->end_offs,
cannam@154:    _this->buf+_this->storage-_this->end_offs,_this->end_offs);
cannam@154:   _this->storage=_size;
cannam@154: }
cannam@154: 
cannam@154: void ec_enc_done(ec_enc *_this){
cannam@154:   ec_window   window;
cannam@154:   int         used;
cannam@154:   opus_uint32 msk;
cannam@154:   opus_uint32 end;
cannam@154:   int         l;
cannam@154:   /*We output the minimum number of bits that ensures that the symbols encoded
cannam@154:      thus far will be decoded correctly regardless of the bits that follow.*/
cannam@154:   l=EC_CODE_BITS-EC_ILOG(_this->rng);
cannam@154:   msk=(EC_CODE_TOP-1)>>l;
cannam@154:   end=(_this->val+msk)&~msk;
cannam@154:   if((end|msk)>=_this->val+_this->rng){
cannam@154:     l++;
cannam@154:     msk>>=1;
cannam@154:     end=(_this->val+msk)&~msk;
cannam@154:   }
cannam@154:   while(l>0){
cannam@154:     ec_enc_carry_out(_this,(int)(end>>EC_CODE_SHIFT));
cannam@154:     end=(end<<EC_SYM_BITS)&(EC_CODE_TOP-1);
cannam@154:     l-=EC_SYM_BITS;
cannam@154:   }
cannam@154:   /*If we have a buffered byte flush it into the output buffer.*/
cannam@154:   if(_this->rem>=0||_this->ext>0)ec_enc_carry_out(_this,0);
cannam@154:   /*If we have buffered extra bits, flush them as well.*/
cannam@154:   window=_this->end_window;
cannam@154:   used=_this->nend_bits;
cannam@154:   while(used>=EC_SYM_BITS){
cannam@154:     _this->error|=ec_write_byte_at_end(_this,(unsigned)window&EC_SYM_MAX);
cannam@154:     window>>=EC_SYM_BITS;
cannam@154:     used-=EC_SYM_BITS;
cannam@154:   }
cannam@154:   /*Clear any excess space and add any remaining extra bits to the last byte.*/
cannam@154:   if(!_this->error){
cannam@154:     OPUS_CLEAR(_this->buf+_this->offs,
cannam@154:      _this->storage-_this->offs-_this->end_offs);
cannam@154:     if(used>0){
cannam@154:       /*If there's no range coder data at all, give up.*/
cannam@154:       if(_this->end_offs>=_this->storage)_this->error=-1;
cannam@154:       else{
cannam@154:         l=-l;
cannam@154:         /*If we've busted, don't add too many extra bits to the last byte; it
cannam@154:            would corrupt the range coder data, and that's more important.*/
cannam@154:         if(_this->offs+_this->end_offs>=_this->storage&&l<used){
cannam@154:           window&=(1<<l)-1;
cannam@154:           _this->error=-1;
cannam@154:         }
cannam@154:         _this->buf[_this->storage-_this->end_offs-1]|=(unsigned char)window;
cannam@154:       }
cannam@154:     }
cannam@154:   }
cannam@154: }