Welcome to mirror list, hosted at ThFree Co, Russian Federation.

gitlab.com/quite/celt.git - Unnamed repository; edit this file 'description' to name the repository.
summaryrefslogtreecommitdiff
path: root/libcelt/entenc.c
diff options
context:
space:
mode:
Diffstat (limited to 'libcelt/entenc.c')
-rw-r--r--libcelt/entenc.c251
1 files changed, 211 insertions, 40 deletions
diff --git a/libcelt/entenc.c b/libcelt/entenc.c
index 9be46b1..125cce9 100644
--- a/libcelt/entenc.c
+++ b/libcelt/entenc.c
@@ -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
@@ -33,56 +33,152 @@
# include "config.h"
#endif
#include "os_support.h"
-#include "entenc.h"
#include "arch.h"
+#include "entenc.h"
+#include "mfrngcod.h"
-void ec_byte_writeinit_buffer(ec_byte_buffer *_b,
- unsigned char *_buf,ec_uint32 _size){
- _b->buf=_buf;
- _b->end_offs=_b->offs=0;
- _b->storage=_size;
-}
-void ec_byte_shrink(ec_byte_buffer *_b,ec_uint32 _size){
- celt_assert(_b->offs+_b->end_offs<=_size);
- CELT_MOVE(_b->buf+_size-_b->end_offs,
- _b->buf+_b->storage-_b->end_offs,_b->end_offs);
- _b->storage=_size;
-}
+/*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"
+ }*/
+
+
-int ec_byte_write(ec_byte_buffer *_b,unsigned _value){
- if(_b->offs+_b->end_offs>=_b->storage)return -1;
- _b->buf[_b->offs++]=(unsigned char)_value;
+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;
}
-int ec_byte_write_at_end(ec_byte_buffer *_b,unsigned _value){
- if(_b->offs+_b->end_offs>=_b->storage)return -1;
- _b->buf[_b->storage-++(_b->end_offs)]=(unsigned char)_value;
+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;
}
-int ec_byte_write_done(ec_byte_buffer *_b,int _start_bits_available,
- unsigned _end_byte,int _end_bits_used){
- int ret;
- CELT_MEMSET(_b->buf+_b->offs,0,_b->storage-_b->offs-_b->end_offs);
- ret=0;
- if(_end_bits_used>0){
- if(_b->offs+_b->end_offs>=_b->storage){
- /*If there's no range coder data at all, give up.*/
- if(_b->end_offs>=_b->storage)return -1;
- /*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(_start_bits_available<_end_bits_used){
- _end_bits_used=_start_bits_available;
- _end_byte&=(1<<_start_bits_available)-1;
- ret=-1;
- }
+
+/*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);
}
- _b->buf[_b->storage-_b->end_offs-1]|=_end_byte;
+ _this->rem=_c&EC_SYM_MAX;
+ }
+ else _this->ext++;
+}
+
+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;
+ }
+}
+
+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_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));
+ }
+ 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]);
}
- return ret;
+ else _this->rng-=IMUL32(r,_icdf[_s]);
+ ec_enc_normalize(_this);
}
void ec_enc_uint(ec_enc *_this,ec_uint32 _fl,ec_uint32 _ft){
@@ -103,6 +199,81 @@ void ec_enc_uint(ec_enc *_this,ec_uint32 _fl,ec_uint32 _ft){
else ec_encode(_this,_fl,_fl+1,_ft+1);
}
-int ec_enc_get_error(ec_enc *_this){
- return _this->error;
+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;
+}
+
+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;
+ }
+ }
}
generated by cgit v1.2.3 (git 2.25.1) at 2024-06-20 00:22:26 +0300