16-bit int fixes.
[opus.git] / libcelt / entenc.c
index 44353f5..125cce9 100644 (file)
@@ -1,4 +1,4 @@
-/* Copyright (c) 2001-2008 Timothy B. Terriberry
+/* Copyright (c) 2001-2011 Timothy B. Terriberry
    Copyright (c) 2008-2009 Xiph.Org Foundation */
 /*
    Redistribution and use in source and binary forms, with or without
    SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
 */
 
-#ifdef HAVE_CONFIG_H
-#include "config.h"
+#if defined(HAVE_CONFIG_H)
+# include "config.h"
 #endif
-
 #include "os_support.h"
-#include "entenc.h"
 #include "arch.h"
+#include "entenc.h"
+#include "mfrngcod.h"
+
+
+
+/*A range encoder.
+  See entdec.c and the references for implementation details \cite{Mar79,MNW98}.
+
+  @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,
+   URL="http://www.stanford.edu/class/ee398/handouts/papers/Moffat98ArithmCoding.pdf"
+  }*/
 
 
-#define EC_BUFFER_INCREMENT (256)
 
-void ec_byte_writeinit_buffer(ec_byte_buffer *_b, unsigned char *_buf, long _size){
-  _b->ptr=_b->buf=_buf;
-  _b->end_ptr=_b->buf+_size-1;
-  _b->storage=_size;
+static int ec_write_byte(ec_enc *_this,unsigned _value){
+  if(_this->offs+_this->end_offs>=_this->storage)return -1;
+  _this->buf[_this->offs++]=(unsigned char)_value;
+  return 0;
 }
 
-void ec_byte_shrink(ec_byte_buffer *_b, long _size){
-   _b->end_ptr=_b->buf+_size-1;
-   _b->storage=_size;
+static int ec_write_byte_at_end(ec_enc *_this,unsigned _value){
+  if(_this->offs+_this->end_offs>=_this->storage)return -1;
+  _this->buf[_this->storage-++(_this->end_offs)]=(unsigned char)_value;
+  return 0;
 }
 
-void ec_byte_write1(ec_byte_buffer *_b,unsigned _value){
-  ptrdiff_t endbyte;
-  endbyte=_b->ptr-_b->buf;
-  if(endbyte>=_b->storage){
-    celt_fatal("range encoder overflow\n");
+
+/*Outputs a symbol, with a carry bit.
+  If there is a potential to propagate a carry over several symbols, they are
+   buffered until it can be determined whether or not an actual carry will
+   occur.
+  If the counter for the buffered symbols overflows, then the stream becomes
+   undecodable.
+  This gives a theoretical limit of a few billion symbols in a single packet on
+   32-bit systems.
+  The alternative is to truncate the range in order to force a carry, but
+   requires similar carry tracking in the decoder, needlessly slowing it down.*/
+static void ec_enc_carry_out(ec_enc *_this,int _c){
+  if(_c!=EC_SYM_MAX){
+    /*No further carry propagation possible, flush buffer.*/
+    int carry;
+    carry=_c>>EC_SYM_BITS;
+    /*Don't output a byte on the first write.
+      This compare should be taken care of by branch-prediction thereafter.*/
+    if(_this->rem>=0)_this->error|=ec_write_byte(_this,_this->rem+carry);
+    if(_this->ext>0){
+      unsigned sym;
+      sym=EC_SYM_MAX+carry&EC_SYM_MAX;
+      do _this->error|=ec_write_byte(_this,sym);
+      while(--(_this->ext)>0);
+    }
+    _this->rem=_c&EC_SYM_MAX;
   }
-  *(_b->ptr++)=(unsigned char)_value;
+  else _this->ext++;
 }
 
-void ec_byte_write_at_end(ec_byte_buffer *_b,unsigned _value){
-  if (_b->end_ptr < _b->ptr)
-  {
-    celt_fatal("byte buffer collision");
+static void ec_enc_normalize(ec_enc *_this){
+  /*If the range is too small, output some bits and rescale it.*/
+  while(_this->rng<=EC_CODE_BOT){
+    ec_enc_carry_out(_this,(int)(_this->val>>EC_CODE_SHIFT));
+    /*Move the next-to-high-order symbol into the high-order position.*/
+    _this->val=_this->val<<EC_SYM_BITS&EC_CODE_TOP-1;
+    _this->rng<<=EC_SYM_BITS;
+    _this->nbits_total+=EC_SYM_BITS;
   }
-  *(_b->end_ptr--)=(unsigned char)_value;
 }
 
+void ec_enc_init(ec_enc *_this,unsigned char *_buf,ec_uint32 _size){
+  _this->buf=_buf;
+  _this->end_offs=0;
+  _this->end_window=0;
+  _this->nend_bits=0;
+  /*This is the offset from which ec_tell() will subtract partial bits.*/
+  _this->nbits_total=EC_CODE_BITS+1;
+  _this->offs=0;
+  _this->rng=EC_CODE_TOP;
+  _this->rem=-1;
+  _this->val=0;
+  _this->ext=0;
+  _this->storage=_size;
+  _this->error=0;
+}
 
-void ec_enc_bits(ec_enc *_this,ec_uint32 _fl,int _ftb){
-  unsigned fl;
-  unsigned ft;
-  while(_ftb>EC_UNIT_BITS){
-    _ftb-=EC_UNIT_BITS;
-    fl=(unsigned)(_fl>>_ftb)&EC_UNIT_MASK;
-    ec_encode_raw(_this,fl,fl+1,EC_UNIT_BITS);
+void ec_encode(ec_enc *_this,unsigned _fl,unsigned _fh,unsigned _ft){
+  ec_uint32 r;
+  r=_this->rng/_ft;
+  if(_fl>0){
+    _this->val+=_this->rng-IMUL32(r,(_ft-_fl));
+    _this->rng=IMUL32(r,(_fh-_fl));
   }
-  ft=1<<_ftb;
-  fl=(unsigned)_fl&ft-1;
-  ec_encode_raw(_this,fl,fl+1,_ftb);
+  else _this->rng-=IMUL32(r,(_ft-_fh));
+  ec_enc_normalize(_this);
+}
+
+void ec_encode_bin(ec_enc *_this,unsigned _fl,unsigned _fh,unsigned _bits){
+  ec_uint32 r;
+  r=_this->rng>>_bits;
+  if(_fl>0){
+    _this->val+=_this->rng-IMUL32(r,((1<<_bits)-_fl));
+    _this->rng=IMUL32(r,(_fh-_fl));
+  }
+  else _this->rng-=IMUL32(r,((1<<_bits)-_fh));
+  ec_enc_normalize(_this);
+}
+
+/*The probability of having a "one" is 1/(1<<_logp).*/
+void ec_enc_bit_logp(ec_enc *_this,int _val,unsigned _logp){
+  ec_uint32 r;
+  ec_uint32 s;
+  ec_uint32 l;
+  r=_this->rng;
+  l=_this->val;
+  s=r>>_logp;
+  r-=s;
+  if(_val)_this->val=l+r;
+  _this->rng=_val?s:r;
+  ec_enc_normalize(_this);
+}
+
+void ec_enc_icdf(ec_enc *_this,int _s,const unsigned char *_icdf,unsigned _ftb){
+  ec_uint32 r;
+  r=_this->rng>>_ftb;
+  if(_s>0){
+    _this->val+=_this->rng-IMUL32(r,_icdf[_s-1]);
+    _this->rng=IMUL32(r,_icdf[_s-1]-_icdf[_s]);
+  }
+  else _this->rng-=IMUL32(r,_icdf[_s]);
+  ec_enc_normalize(_this);
 }
 
 void ec_enc_uint(ec_enc *_this,ec_uint32 _fl,ec_uint32 _ft){
@@ -90,25 +189,91 @@ void ec_enc_uint(ec_enc *_this,ec_uint32 _fl,ec_uint32 _ft){
   celt_assert(_ft>1);
   _ft--;
   ftb=EC_ILOG(_ft);
-  if(ftb>EC_UNIT_BITS){
-    ftb-=EC_UNIT_BITS;
+  if(ftb>EC_UINT_BITS){
+    ftb-=EC_UINT_BITS;
     ft=(_ft>>ftb)+1;
     fl=(unsigned)(_fl>>ftb);
     ec_encode(_this,fl,fl+1,ft);
-    ec_enc_bits(_this,_fl,ftb);
-  } else {
-    ec_encode(_this,_fl,_fl+1,_ft+1);
+    ec_enc_bits(_this,_fl&((ec_uint32)1<<ftb)-1,ftb);
+  }
+  else ec_encode(_this,_fl,_fl+1,_ft+1);
+}
+
+void ec_enc_bits(ec_enc *_this,ec_uint32 _fl,unsigned _bits){
+  ec_window window;
+  int       used;
+  window=_this->end_window;
+  used=_this->nend_bits;
+  if(used+_bits>EC_WINDOW_SIZE){
+    do{
+      _this->error|=ec_write_byte_at_end(_this,(unsigned)window&EC_SYM_MAX);
+      window>>=EC_SYM_BITS;
+      used-=EC_SYM_BITS;
+    }
+    while(used>=EC_SYM_BITS);
   }
+  window|=(ec_window)_fl<<used;
+  used+=_bits;
+  _this->end_window=window;
+  _this->nend_bits=used;
+  _this->nbits_total+=_bits;
 }
 
-/* The probability of having a "one" is given in 1/256 */
-void ec_enc_bit_prob(ec_enc *_this,int val,int _prob)
-{
-   int fl=0, fh=256-_prob;
-   if (val)
-   {
-      fl=fh;
-      fh=256;
-   }
-   ec_encode_bin(_this,fl,fh,8);
+void ec_enc_shrink(ec_enc *_this,ec_uint32 _size){
+  celt_assert(_this->offs+_this->end_offs<=_size);
+  CELT_MOVE(_this->buf+_size-_this->end_offs,
+   _this->buf+_this->storage-_this->end_offs,_this->end_offs);
+  _this->storage=_size;
+}
+
+void ec_enc_done(ec_enc *_this){
+  ec_window window;
+  int       used;
+  ec_uint32 msk;
+  ec_uint32 end;
+  int       l;
+  /*We output the minimum number of bits that ensures that the symbols encoded
+     thus far will be decoded correctly regardless of the bits that follow.*/
+  l=EC_CODE_BITS-EC_ILOG(_this->rng);
+  msk=EC_CODE_TOP-1>>l;
+  end=_this->val+msk&~msk;
+  if((end|msk)>=_this->val+_this->rng){
+    l++;
+    msk>>=1;
+    end=_this->val+msk&~msk;
+  }
+  while(l>0){
+    ec_enc_carry_out(_this,(int)(end>>EC_CODE_SHIFT));
+    end=end<<EC_SYM_BITS&EC_CODE_TOP-1;
+    l-=EC_SYM_BITS;
+  }
+  /*If we have a buffered byte flush it into the output buffer.*/
+  if(_this->rem>=0||_this->ext>0)ec_enc_carry_out(_this,0);
+  /*If we have buffered extra bits, flush them as well.*/
+  window=_this->end_window;
+  used=_this->nend_bits;
+  while(used>=EC_SYM_BITS){
+    _this->error|=ec_write_byte_at_end(_this,(unsigned)window&EC_SYM_MAX);
+    window>>=EC_SYM_BITS;
+    used-=EC_SYM_BITS;
+  }
+  /*Clear any excess space and add any remaining extra bits to the last byte.*/
+  if(!_this->error){
+    CELT_MEMSET(_this->buf+_this->offs,0,
+     _this->storage-_this->offs-_this->end_offs);
+    if(used>0){
+      /*If there's no range coder data at all, give up.*/
+      if(_this->end_offs>=_this->storage)_this->error=-1;
+      else{
+        l=-l;
+        /*If we've busted, don't add too many extra bits to the last byte; it
+           would corrupt the range coder data, and that's more important.*/
+        if(_this->offs+_this->end_offs>=_this->storage&&l<used){
+          window&=(1<<l)-1;
+          _this->error=-1;
+        }
+      }
+      _this->buf[_this->storage-_this->end_offs-1]|=(unsigned char)window;
+    }
+  }
 }