From c08be4485b9e15461578527f568219459db2036c Mon Sep 17 00:00:00 2001 From: Jean-Marc Valin Date: Wed, 17 Jun 2009 23:23:46 -0400 Subject: 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 --- libcelt/celt.c | 12 ++++++------ libcelt/entcode.h | 3 +++ libcelt/entdec.c | 14 +++++++++++--- libcelt/entdec.h | 5 +++++ libcelt/entenc.c | 17 ++++++++++++++--- libcelt/entenc.h | 5 +++++ libcelt/rangedec.c | 22 +++++++++++++++++++++- libcelt/rangeenc.c | 27 ++++++++++++++++++++++++++- tests/ectest.c | 15 ++++++++++----- 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<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<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)<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<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<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 #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 []\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>(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