1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/media/libopus/celt/entenc.c Wed Dec 31 06:09:35 2014 +0100
1.3 @@ -0,0 +1,294 @@
1.4 +/* Copyright (c) 2001-2011 Timothy B. Terriberry
1.5 + Copyright (c) 2008-2009 Xiph.Org Foundation */
1.6 +/*
1.7 + Redistribution and use in source and binary forms, with or without
1.8 + modification, are permitted provided that the following conditions
1.9 + are met:
1.10 +
1.11 + - Redistributions of source code must retain the above copyright
1.12 + notice, this list of conditions and the following disclaimer.
1.13 +
1.14 + - Redistributions in binary form must reproduce the above copyright
1.15 + notice, this list of conditions and the following disclaimer in the
1.16 + documentation and/or other materials provided with the distribution.
1.17 +
1.18 + THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
1.19 + ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
1.20 + LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
1.21 + A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER
1.22 + OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
1.23 + EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
1.24 + PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
1.25 + PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
1.26 + LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
1.27 + NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
1.28 + SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
1.29 +*/
1.30 +
1.31 +#if defined(HAVE_CONFIG_H)
1.32 +# include "config.h"
1.33 +#endif
1.34 +#include "os_support.h"
1.35 +#include "arch.h"
1.36 +#include "entenc.h"
1.37 +#include "mfrngcod.h"
1.38 +
1.39 +/*A range encoder.
1.40 + See entdec.c and the references for implementation details \cite{Mar79,MNW98}.
1.41 +
1.42 + @INPROCEEDINGS{Mar79,
1.43 + author="Martin, G.N.N.",
1.44 + title="Range encoding: an algorithm for removing redundancy from a digitised
1.45 + message",
1.46 + booktitle="Video \& Data Recording Conference",
1.47 + year=1979,
1.48 + address="Southampton",
1.49 + month=Jul
1.50 + }
1.51 + @ARTICLE{MNW98,
1.52 + author="Alistair Moffat and Radford Neal and Ian H. Witten",
1.53 + title="Arithmetic Coding Revisited",
1.54 + journal="{ACM} Transactions on Information Systems",
1.55 + year=1998,
1.56 + volume=16,
1.57 + number=3,
1.58 + pages="256--294",
1.59 + month=Jul,
1.60 + URL="http://www.stanford.edu/class/ee398/handouts/papers/Moffat98ArithmCoding.pdf"
1.61 + }*/
1.62 +
1.63 +static int ec_write_byte(ec_enc *_this,unsigned _value){
1.64 + if(_this->offs+_this->end_offs>=_this->storage)return -1;
1.65 + _this->buf[_this->offs++]=(unsigned char)_value;
1.66 + return 0;
1.67 +}
1.68 +
1.69 +static int ec_write_byte_at_end(ec_enc *_this,unsigned _value){
1.70 + if(_this->offs+_this->end_offs>=_this->storage)return -1;
1.71 + _this->buf[_this->storage-++(_this->end_offs)]=(unsigned char)_value;
1.72 + return 0;
1.73 +}
1.74 +
1.75 +/*Outputs a symbol, with a carry bit.
1.76 + If there is a potential to propagate a carry over several symbols, they are
1.77 + buffered until it can be determined whether or not an actual carry will
1.78 + occur.
1.79 + If the counter for the buffered symbols overflows, then the stream becomes
1.80 + undecodable.
1.81 + This gives a theoretical limit of a few billion symbols in a single packet on
1.82 + 32-bit systems.
1.83 + The alternative is to truncate the range in order to force a carry, but
1.84 + requires similar carry tracking in the decoder, needlessly slowing it down.*/
1.85 +static void ec_enc_carry_out(ec_enc *_this,int _c){
1.86 + if(_c!=EC_SYM_MAX){
1.87 + /*No further carry propagation possible, flush buffer.*/
1.88 + int carry;
1.89 + carry=_c>>EC_SYM_BITS;
1.90 + /*Don't output a byte on the first write.
1.91 + This compare should be taken care of by branch-prediction thereafter.*/
1.92 + if(_this->rem>=0)_this->error|=ec_write_byte(_this,_this->rem+carry);
1.93 + if(_this->ext>0){
1.94 + unsigned sym;
1.95 + sym=(EC_SYM_MAX+carry)&EC_SYM_MAX;
1.96 + do _this->error|=ec_write_byte(_this,sym);
1.97 + while(--(_this->ext)>0);
1.98 + }
1.99 + _this->rem=_c&EC_SYM_MAX;
1.100 + }
1.101 + else _this->ext++;
1.102 +}
1.103 +
1.104 +static void ec_enc_normalize(ec_enc *_this){
1.105 + /*If the range is too small, output some bits and rescale it.*/
1.106 + while(_this->rng<=EC_CODE_BOT){
1.107 + ec_enc_carry_out(_this,(int)(_this->val>>EC_CODE_SHIFT));
1.108 + /*Move the next-to-high-order symbol into the high-order position.*/
1.109 + _this->val=(_this->val<<EC_SYM_BITS)&(EC_CODE_TOP-1);
1.110 + _this->rng<<=EC_SYM_BITS;
1.111 + _this->nbits_total+=EC_SYM_BITS;
1.112 + }
1.113 +}
1.114 +
1.115 +void ec_enc_init(ec_enc *_this,unsigned char *_buf,opus_uint32 _size){
1.116 + _this->buf=_buf;
1.117 + _this->end_offs=0;
1.118 + _this->end_window=0;
1.119 + _this->nend_bits=0;
1.120 + /*This is the offset from which ec_tell() will subtract partial bits.*/
1.121 + _this->nbits_total=EC_CODE_BITS+1;
1.122 + _this->offs=0;
1.123 + _this->rng=EC_CODE_TOP;
1.124 + _this->rem=-1;
1.125 + _this->val=0;
1.126 + _this->ext=0;
1.127 + _this->storage=_size;
1.128 + _this->error=0;
1.129 +}
1.130 +
1.131 +void ec_encode(ec_enc *_this,unsigned _fl,unsigned _fh,unsigned _ft){
1.132 + opus_uint32 r;
1.133 + r=_this->rng/_ft;
1.134 + if(_fl>0){
1.135 + _this->val+=_this->rng-IMUL32(r,(_ft-_fl));
1.136 + _this->rng=IMUL32(r,(_fh-_fl));
1.137 + }
1.138 + else _this->rng-=IMUL32(r,(_ft-_fh));
1.139 + ec_enc_normalize(_this);
1.140 +}
1.141 +
1.142 +void ec_encode_bin(ec_enc *_this,unsigned _fl,unsigned _fh,unsigned _bits){
1.143 + opus_uint32 r;
1.144 + r=_this->rng>>_bits;
1.145 + if(_fl>0){
1.146 + _this->val+=_this->rng-IMUL32(r,((1U<<_bits)-_fl));
1.147 + _this->rng=IMUL32(r,(_fh-_fl));
1.148 + }
1.149 + else _this->rng-=IMUL32(r,((1U<<_bits)-_fh));
1.150 + ec_enc_normalize(_this);
1.151 +}
1.152 +
1.153 +/*The probability of having a "one" is 1/(1<<_logp).*/
1.154 +void ec_enc_bit_logp(ec_enc *_this,int _val,unsigned _logp){
1.155 + opus_uint32 r;
1.156 + opus_uint32 s;
1.157 + opus_uint32 l;
1.158 + r=_this->rng;
1.159 + l=_this->val;
1.160 + s=r>>_logp;
1.161 + r-=s;
1.162 + if(_val)_this->val=l+r;
1.163 + _this->rng=_val?s:r;
1.164 + ec_enc_normalize(_this);
1.165 +}
1.166 +
1.167 +void ec_enc_icdf(ec_enc *_this,int _s,const unsigned char *_icdf,unsigned _ftb){
1.168 + opus_uint32 r;
1.169 + r=_this->rng>>_ftb;
1.170 + if(_s>0){
1.171 + _this->val+=_this->rng-IMUL32(r,_icdf[_s-1]);
1.172 + _this->rng=IMUL32(r,_icdf[_s-1]-_icdf[_s]);
1.173 + }
1.174 + else _this->rng-=IMUL32(r,_icdf[_s]);
1.175 + ec_enc_normalize(_this);
1.176 +}
1.177 +
1.178 +void ec_enc_uint(ec_enc *_this,opus_uint32 _fl,opus_uint32 _ft){
1.179 + unsigned ft;
1.180 + unsigned fl;
1.181 + int ftb;
1.182 + /*In order to optimize EC_ILOG(), it is undefined for the value 0.*/
1.183 + celt_assert(_ft>1);
1.184 + _ft--;
1.185 + ftb=EC_ILOG(_ft);
1.186 + if(ftb>EC_UINT_BITS){
1.187 + ftb-=EC_UINT_BITS;
1.188 + ft=(_ft>>ftb)+1;
1.189 + fl=(unsigned)(_fl>>ftb);
1.190 + ec_encode(_this,fl,fl+1,ft);
1.191 + ec_enc_bits(_this,_fl&(((opus_uint32)1<<ftb)-1U),ftb);
1.192 + }
1.193 + else ec_encode(_this,_fl,_fl+1,_ft+1);
1.194 +}
1.195 +
1.196 +void ec_enc_bits(ec_enc *_this,opus_uint32 _fl,unsigned _bits){
1.197 + ec_window window;
1.198 + int used;
1.199 + window=_this->end_window;
1.200 + used=_this->nend_bits;
1.201 + celt_assert(_bits>0);
1.202 + if(used+_bits>EC_WINDOW_SIZE){
1.203 + do{
1.204 + _this->error|=ec_write_byte_at_end(_this,(unsigned)window&EC_SYM_MAX);
1.205 + window>>=EC_SYM_BITS;
1.206 + used-=EC_SYM_BITS;
1.207 + }
1.208 + while(used>=EC_SYM_BITS);
1.209 + }
1.210 + window|=(ec_window)_fl<<used;
1.211 + used+=_bits;
1.212 + _this->end_window=window;
1.213 + _this->nend_bits=used;
1.214 + _this->nbits_total+=_bits;
1.215 +}
1.216 +
1.217 +void ec_enc_patch_initial_bits(ec_enc *_this,unsigned _val,unsigned _nbits){
1.218 + int shift;
1.219 + unsigned mask;
1.220 + celt_assert(_nbits<=EC_SYM_BITS);
1.221 + shift=EC_SYM_BITS-_nbits;
1.222 + mask=((1<<_nbits)-1)<<shift;
1.223 + if(_this->offs>0){
1.224 + /*The first byte has been finalized.*/
1.225 + _this->buf[0]=(unsigned char)((_this->buf[0]&~mask)|_val<<shift);
1.226 + }
1.227 + else if(_this->rem>=0){
1.228 + /*The first byte is still awaiting carry propagation.*/
1.229 + _this->rem=(_this->rem&~mask)|_val<<shift;
1.230 + }
1.231 + else if(_this->rng<=(EC_CODE_TOP>>_nbits)){
1.232 + /*The renormalization loop has never been run.*/
1.233 + _this->val=(_this->val&~((opus_uint32)mask<<EC_CODE_SHIFT))|
1.234 + (opus_uint32)_val<<(EC_CODE_SHIFT+shift);
1.235 + }
1.236 + /*The encoder hasn't even encoded _nbits of data yet.*/
1.237 + else _this->error=-1;
1.238 +}
1.239 +
1.240 +void ec_enc_shrink(ec_enc *_this,opus_uint32 _size){
1.241 + celt_assert(_this->offs+_this->end_offs<=_size);
1.242 + OPUS_MOVE(_this->buf+_size-_this->end_offs,
1.243 + _this->buf+_this->storage-_this->end_offs,_this->end_offs);
1.244 + _this->storage=_size;
1.245 +}
1.246 +
1.247 +void ec_enc_done(ec_enc *_this){
1.248 + ec_window window;
1.249 + int used;
1.250 + opus_uint32 msk;
1.251 + opus_uint32 end;
1.252 + int l;
1.253 + /*We output the minimum number of bits that ensures that the symbols encoded
1.254 + thus far will be decoded correctly regardless of the bits that follow.*/
1.255 + l=EC_CODE_BITS-EC_ILOG(_this->rng);
1.256 + msk=(EC_CODE_TOP-1)>>l;
1.257 + end=(_this->val+msk)&~msk;
1.258 + if((end|msk)>=_this->val+_this->rng){
1.259 + l++;
1.260 + msk>>=1;
1.261 + end=(_this->val+msk)&~msk;
1.262 + }
1.263 + while(l>0){
1.264 + ec_enc_carry_out(_this,(int)(end>>EC_CODE_SHIFT));
1.265 + end=(end<<EC_SYM_BITS)&(EC_CODE_TOP-1);
1.266 + l-=EC_SYM_BITS;
1.267 + }
1.268 + /*If we have a buffered byte flush it into the output buffer.*/
1.269 + if(_this->rem>=0||_this->ext>0)ec_enc_carry_out(_this,0);
1.270 + /*If we have buffered extra bits, flush them as well.*/
1.271 + window=_this->end_window;
1.272 + used=_this->nend_bits;
1.273 + while(used>=EC_SYM_BITS){
1.274 + _this->error|=ec_write_byte_at_end(_this,(unsigned)window&EC_SYM_MAX);
1.275 + window>>=EC_SYM_BITS;
1.276 + used-=EC_SYM_BITS;
1.277 + }
1.278 + /*Clear any excess space and add any remaining extra bits to the last byte.*/
1.279 + if(!_this->error){
1.280 + OPUS_CLEAR(_this->buf+_this->offs,
1.281 + _this->storage-_this->offs-_this->end_offs);
1.282 + if(used>0){
1.283 + /*If there's no range coder data at all, give up.*/
1.284 + if(_this->end_offs>=_this->storage)_this->error=-1;
1.285 + else{
1.286 + l=-l;
1.287 + /*If we've busted, don't add too many extra bits to the last byte; it
1.288 + would corrupt the range coder data, and that's more important.*/
1.289 + if(_this->offs+_this->end_offs>=_this->storage&&l<used){
1.290 + window&=(1<<l)-1;
1.291 + _this->error=-1;
1.292 + }
1.293 + _this->buf[_this->storage-_this->end_offs-1]|=(unsigned char)window;
1.294 + }
1.295 + }
1.296 + }
1.297 +}
