Home | History | Annotate | Download | only in celt
      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 }
    295