Implemented "raw bits"

Making it so all the information encoded directly with ec_enc_bits() gets
stored at the end of the stream, without going through the range coder. This
should be both faster and reduce the effects of bit errors.

Conflicts:

	tests/ectest.c

9 files changed, 101 insertions, 19 deletions

diff --git a/libcelt/celt.c b/libcelt/celt.c
index ec62cf2..eb2d50e 100644
--- a/libcelt/celt.c
+++ b/libcelt/celt.c
@@ -459,23 +459,23 @@ void encode_flags(ec_enc *enc, int intra_ener, int has_pitch, int shortBlocks, i
    flag_bits = flaglist[i]&0xf;
    /*printf ("enc %d: %d %d %d %d\n", flag_bits, intra_ener, has_pitch, shortBlocks, has_fold);*/
    if (i<2)
-      ec_enc_bits(enc, flag_bits, 2);
+      ec_enc_uint(enc, flag_bits, 4);
    else if (i<6)
-      ec_enc_bits(enc, flag_bits, 4);
+      ec_enc_uint(enc, flag_bits, 16);
    else
-      ec_enc_bits(enc, flag_bits, 3);
+      ec_enc_uint(enc, flag_bits, 8);
 }
 
 void decode_flags(ec_dec *dec, int *intra_ener, int *has_pitch, int *shortBlocks, int *has_fold)
 {
    int i;
    int flag_bits;
-   flag_bits = ec_dec_bits(dec, 2);
+   flag_bits = ec_dec_uint(dec, 4);
    /*printf ("(%d) ", flag_bits);*/
    if (flag_bits==2)
-      flag_bits = (flag_bits<<2) | ec_dec_bits(dec, 2);
+      flag_bits = (flag_bits<<2) | ec_dec_uint(dec, 4);
    else if (flag_bits==3)
-      flag_bits = (flag_bits<<1) | ec_dec_bits(dec, 1);
+      flag_bits = (flag_bits<<1) | ec_dec_uint(dec, 2);
    for (i=0;i<8;i++)
       if (flag_bits == (flaglist[i]&0xf))
          break;
diff --git a/libcelt/entcode.h b/libcelt/entcode.h
index 57122f8..5148242 100644
--- a/libcelt/entcode.h
+++ b/libcelt/entcode.h
@@ -56,6 +56,7 @@ typedef struct ec_byte_buffer ec_byte_buffer;
 struct ec_byte_buffer{
   unsigned char *buf;
   unsigned char *ptr;
+  unsigned char *end_ptr;
   long           storage;
   int            resizable;
 };
@@ -65,12 +66,14 @@ void ec_byte_writeinit_buffer(ec_byte_buffer *_b, unsigned char *_buf, long _siz
 void ec_byte_writeinit(ec_byte_buffer *_b);
 void ec_byte_writetrunc(ec_byte_buffer *_b,long _bytes);
 void ec_byte_write1(ec_byte_buffer *_b,unsigned _value);
+void ec_byte_write_at_end(ec_byte_buffer *_b,unsigned _value);
 void ec_byte_write4(ec_byte_buffer *_b,ec_uint32 _value);
 void ec_byte_writecopy(ec_byte_buffer *_b,void *_source,long _bytes);
 void ec_byte_writeclear(ec_byte_buffer *_b);
 /*Decoding functions.*/
 void ec_byte_readinit(ec_byte_buffer *_b,unsigned char *_buf,long _bytes);
 int ec_byte_look1(ec_byte_buffer *_b);
+unsigned char ec_byte_look_at_end(ec_byte_buffer *_b);
 int ec_byte_look4(ec_byte_buffer *_b,ec_uint32 *_val);
 void ec_byte_adv1(ec_byte_buffer *_b);
 void ec_byte_adv4(ec_byte_buffer *_b);
diff --git a/libcelt/entdec.c b/libcelt/entdec.c
index fb39f00..003b5ff 100644
--- a/libcelt/entdec.c
+++ b/libcelt/entdec.c
@@ -38,10 +38,10 @@
 #include "os_support.h"
 #include "arch.h"
 
-
 void ec_byte_readinit(ec_byte_buffer *_b,unsigned char *_buf,long _bytes){
   _b->buf=_b->ptr=_buf;
   _b->storage=_bytes;
+  _b->end_ptr=_b->buf+_bytes-1;
 }
 
 int ec_byte_look1(ec_byte_buffer *_b){
@@ -51,6 +51,14 @@ int ec_byte_look1(ec_byte_buffer *_b){
   else return _b->ptr[0];
 }
 
+unsigned char ec_byte_look_at_end(ec_byte_buffer *_b){
+  if (_b->end_ptr < _b->buf)
+  {
+    celt_fatal("Trying to read raw bits before the beginning of the stream");
+  }
+  return *(_b->end_ptr--);
+}
+
 int ec_byte_look4(ec_byte_buffer *_b,ec_uint32 *_val){
   ptrdiff_t endbyte;
   endbyte=_b->ptr-_b->buf;
@@ -121,13 +129,13 @@ ec_uint32 ec_dec_bits(ec_dec *_this,int _ftb){
   t=0;
   while(_ftb>EC_UNIT_BITS){
     s=ec_decode_bin(_this,EC_UNIT_BITS);
-    ec_dec_update(_this,s,s+1,EC_UNIT_MASK+1);
+    /*ec_dec_update(_this,s,s+1,EC_UNIT_MASK+1);*/
     t=t<<EC_UNIT_BITS|s;
     _ftb-=EC_UNIT_BITS;
   }
   ft=1U<<_ftb;
   s=ec_decode_bin(_this,_ftb);
-  ec_dec_update(_this,s,s+1,ft);
+  /*ec_dec_update(_this,s,s+1,ft);*/
   t=t<<_ftb|s;
   return t;
 }
diff --git a/libcelt/entdec.h b/libcelt/entdec.h
index 76663a4..57bfebc 100644
--- a/libcelt/entdec.h
+++ b/libcelt/entdec.h
@@ -52,6 +52,11 @@ struct ec_dec{
    ec_uint32       dif;
    /*Normalization factor.*/
    ec_uint32       nrm;
+   /*Byte that will be written at the end*/
+   unsigned char   end_byte;
+   /*Number of valid bits in end_byte*/
+   int             end_bits_left;
+   int             nb_end_bits;
 };
 
 
diff --git a/libcelt/entenc.c b/libcelt/entenc.c
index de15f9e..0c902ae 100644
--- a/libcelt/entenc.c
+++ b/libcelt/entenc.c
@@ -42,14 +42,16 @@
 
 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;
-  _b->resizable = 0;
+  _b->resizable=0;
 }
 
 void ec_byte_writeinit(ec_byte_buffer *_b){
   _b->ptr=_b->buf=celt_alloc(EC_BUFFER_INCREMENT*sizeof(char));
   _b->storage=EC_BUFFER_INCREMENT;
-  _b->resizable = 1;
+  _b->end_ptr=_b->buf;
+  _b->resizable=1;
 }
 
 void ec_byte_writetrunc(ec_byte_buffer *_b,long _bytes){
@@ -71,6 +73,14 @@ void ec_byte_write1(ec_byte_buffer *_b,unsigned _value){
   *(_b->ptr++)=(unsigned char)_value;
 }
 
+void ec_byte_write_at_end(ec_byte_buffer *_b,unsigned _value){
+  if (_b->end_ptr < _b->ptr)
+  {
+    celt_fatal("byte buffer collision");
+  }
+  *(_b->end_ptr--)=(unsigned char)_value;
+}
+
 void ec_byte_write4(ec_byte_buffer *_b,ec_uint32 _value){
   ptrdiff_t endbyte;
   endbyte=_b->ptr-_b->buf;
@@ -109,7 +119,8 @@ void ec_byte_writecopy(ec_byte_buffer *_b,void *_source,long _bytes){
 }
 
 void ec_byte_writeclear(ec_byte_buffer *_b){
-  celt_free(_b->buf);
+  if (_b->resizable)
+    celt_free(_b->buf);
 }
 
 
diff --git a/libcelt/entenc.h b/libcelt/entenc.h
index 4918ed4..5c082ab 100644
--- a/libcelt/entenc.h
+++ b/libcelt/entenc.h
@@ -52,6 +52,11 @@ struct ec_enc{
    ec_uint32       rng;
    /*The low end of the current range (inclusive).*/
    ec_uint32       low;
+   /*Byte that will be written at the end*/
+   unsigned char   end_byte;
+   /*Number of valid bits in end_byte*/
+   int             end_bits_left;
+   int             nb_end_bits;
 };
 
 
diff --git a/libcelt/rangedec.c b/libcelt/rangedec.c
index 4a26be6..48cd3a4 100644
--- a/libcelt/rangedec.c
+++ b/libcelt/rangedec.c
@@ -141,6 +141,9 @@ void ec_dec_init(ec_dec *_this,ec_byte_buffer *_buf){
   _this->dif=_this->rng-(_this->rem>>EC_SYM_BITS-EC_CODE_EXTRA);
   /*Normalize the interval.*/
   ec_dec_normalize(_this);
+  /*_this->end_byte=ec_byte_look_at_end(_this->buf);*/
+  _this->end_bits_left=0;
+  _this->nb_end_bits=0;
 }
 
 
@@ -152,12 +155,29 @@ unsigned ec_decode(ec_dec *_this,unsigned _ft){
 }
 
 unsigned ec_decode_bin(ec_dec *_this,unsigned bits){
+#if 0
    unsigned s;
    ec_uint32 ft;
    ft = (ec_uint32)1<<bits;
    _this->nrm=_this->rng>>bits;
    s=(unsigned)((_this->dif-1)/_this->nrm);
    return ft-EC_MINI(s+1,ft);
+#else
+  unsigned value=0;
+  int count=0;
+  _this->nb_end_bits += bits;
+  while (bits>=_this->end_bits_left)
+  {
+    value |= _this->end_byte>>(8-_this->end_bits_left)<<count;
+    count += _this->end_bits_left;
+    bits -= _this->end_bits_left;
+    _this->end_byte=ec_byte_look_at_end(_this->buf);
+    _this->end_bits_left = 8;
+  }
+  value |= ((_this->end_byte>>(8-_this->end_bits_left))&((1<<bits)-1))<<count;
+  _this->end_bits_left -= bits;
+  return value;
+#endif
 }
 
 void ec_dec_update(ec_dec *_this,unsigned _fl,unsigned _fh,unsigned _ft){
@@ -177,7 +197,7 @@ long ec_dec_tell(ec_dec *_this,int _b){
   /*To handle the non-integral number of bits still left in the decoder state,
      we compute the number of bits of low that must be encoded to ensure that
      the value is inside the range for any possible subsequent bits.*/
-  nbits+=EC_CODE_BITS+1;
+  nbits+=EC_CODE_BITS+1+_this->nb_end_bits;
   nbits<<=_b;
   l=EC_ILOG(_this->rng);
   r=_this->rng>>l-16;
diff --git a/libcelt/rangeenc.c b/libcelt/rangeenc.c
index 2d066e2..6f8682d 100644
--- a/libcelt/rangeenc.c
+++ b/libcelt/rangeenc.c
@@ -111,6 +111,9 @@ void ec_enc_init(ec_enc *_this,ec_byte_buffer *_buf){
   _this->ext=0;
   _this->low=0;
   _this->rng=EC_CODE_TOP;
+  _this->end_byte=0;
+  _this->end_bits_left=8;
+  _this->nb_end_bits=0;
 }
 
 void ec_encode(ec_enc *_this,unsigned _fl,unsigned _fh,unsigned _ft){
@@ -125,6 +128,7 @@ void ec_encode(ec_enc *_this,unsigned _fl,unsigned _fh,unsigned _ft){
 }
 
 void ec_encode_bin(ec_enc *_this,unsigned _fl,unsigned _fh,unsigned bits){
+#if 0
    ec_uint32 r, ft;
    r=_this->rng>>bits;
    ft = (ec_uint32)1<<bits;
@@ -134,6 +138,20 @@ void ec_encode_bin(ec_enc *_this,unsigned _fl,unsigned _fh,unsigned bits){
    }
    else _this->rng-=IMUL32(r,(ft-_fh));
    ec_enc_normalize(_this);
+#else
+  _this->nb_end_bits += bits;
+  while (bits >= _this->end_bits_left)
+  {
+    _this->end_byte |= (_fl<<(8-_this->end_bits_left)) & 0xff;
+    _fl >>= _this->end_bits_left;
+    ec_byte_write_at_end(_this->buf, _this->end_byte);
+    _this->end_byte = 0;
+    bits -= _this->end_bits_left;
+    _this->end_bits_left = 8;
+  }
+  _this->end_byte |= (_fl<<(8-_this->end_bits_left)) & 0xff;
+  _this->end_bits_left -= bits;
+#endif
 }
 
 long ec_enc_tell(ec_enc *_this,int _b){
@@ -144,7 +162,7 @@ long ec_enc_tell(ec_enc *_this,int _b){
   /*To handle the non-integral number of bits still left in the encoder state,
      we compute the number of bits of low that must be encoded to ensure that
      the value is inside the range for any possible subsequent bits.*/
-  nbits+=EC_CODE_BITS+1;
+  nbits+=EC_CODE_BITS+1+_this->nb_end_bits;
   nbits<<=_b;
   l=EC_ILOG(_this->rng);
   r=_this->rng>>l-16;
@@ -182,4 +200,11 @@ void ec_enc_done(ec_enc *_this){
     ec_enc_carry_out(_this,0);
     _this->rem=-1;
   }
+  {
+    unsigned char *ptr = _this->buf->ptr;
+    while (ptr<= _this->buf->end_ptr)
+      *ptr++ = 0;
+    if (_this->end_bits_left != 8)
+      *_this->buf->end_ptr |= _this->end_byte;
+  }
 }
diff --git a/tests/ectest.c b/tests/ectest.c
index e861dfb..397a29e 100644
--- a/tests/ectest.c
+++ b/tests/ectest.c
@@ -11,6 +11,7 @@
 #include "entcode.h"
 #include "entenc.h"
 #include "entdec.h"
+#include <string.h>
 
 #include "../libcelt/rangeenc.c"
 #include "../libcelt/rangedec.c"
@@ -21,6 +22,8 @@
 #ifndef M_LOG2E
 # define M_LOG2E    1.4426950408889634074
 #endif
+#define DATA_SIZE 10000000
+#define DATA_SIZE2 10000
 
 int main(int _argc,char **_argv){
   ec_byte_buffer buf;
@@ -38,7 +41,7 @@ int main(int _argc,char **_argv){
   unsigned int   seed;
   ret=0;
   entropy=0;
-
+  unsigned char *ptr;
     if (_argc > 2) {
 	fprintf(stderr, "Usage: %s [<seed>]\n", _argv[0]);
 	return 1;
@@ -48,7 +51,8 @@ int main(int _argc,char **_argv){
     else
 	seed = (time(NULL) ^ (getpid()%(1<<16) << 16));
   /*Testing encoding of raw bit values.*/
-  ec_byte_writeinit(&buf);
+  ptr = malloc(DATA_SIZE);
+  ec_byte_writeinit_buffer(&buf, ptr, DATA_SIZE);
   ec_enc_init(&enc,&buf);
   for(ft=2;ft<1024;ft++){
     for(i=0;i<ft;i++){
@@ -76,7 +80,7 @@ int main(int _argc,char **_argv){
    "Encoded %0.2lf bits of entropy to %0.2lf bits (%0.3lf%% wasted).\n",
    entropy,ldexp(nbits,-4),100*(nbits-ldexp(entropy,4))/nbits);
   fprintf(stderr,"Packed to %li bytes.\n",(long)(buf.ptr-buf.buf));
-  ec_byte_readinit(&buf,ec_byte_get_buffer(&buf),ec_byte_bytes(&buf));
+  ec_byte_readinit(&buf,ptr,DATA_SIZE);
   ec_dec_init(&dec,&buf);
   for(ft=2;ft<1024;ft++){
     for(i=0;i<ft;i++){
@@ -114,7 +118,7 @@ int main(int _argc,char **_argv){
     ft=rand()/((RAND_MAX>>(rand()%11))+1)+10;
     sz=rand()/((RAND_MAX>>(rand()%9))+1);
     data=(unsigned *)malloc(sz*sizeof(*data));
-    ec_byte_writeinit(&buf);
+    ec_byte_writeinit_buffer(&buf, ptr, DATA_SIZE2);
     ec_enc_init(&enc,&buf);
     zeros = rand()%13==0;
     for(j=0;j<sz;j++){
@@ -136,7 +140,7 @@ int main(int _argc,char **_argv){
       ret=-1;
     }
     tell_bits -= 8*ec_byte_bytes(&buf);
-    ec_byte_readinit(&buf,ec_byte_get_buffer(&buf),ec_byte_bytes(&buf));
+    ec_byte_readinit(&buf,ptr,DATA_SIZE2);
     ec_dec_init(&dec,&buf);
     for(j=0;j<sz;j++){
       sym=ec_dec_uint(&dec,ft);
@@ -150,5 +154,6 @@ int main(int _argc,char **_argv){
     ec_byte_writeclear(&buf);
     free(data);
   }
+  free(ptr);
   return ret;
 }