1885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org/* Copyright (c) 2001-2011 Timothy B. Terriberry 2885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org Copyright (c) 2008-2009 Xiph.Org Foundation */ 3885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org/* 4885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org Redistribution and use in source and binary forms, with or without 5885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org modification, are permitted provided that the following conditions 6885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org are met: 7885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org 8885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org - Redistributions of source code must retain the above copyright 9885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org notice, this list of conditions and the following disclaimer. 10885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org 11885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org - Redistributions in binary form must reproduce the above copyright 12885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org notice, this list of conditions and the following disclaimer in the 13885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org documentation and/or other materials provided with the distribution. 14885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org 15885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 16885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 17885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR 18885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER 19885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, 20885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, 21885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR 22885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF 23885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING 24885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS 25885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 26885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org*/ 27885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org 28885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org#if defined(HAVE_CONFIG_H) 29885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org# include "config.h" 30885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org#endif 31885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org#include "os_support.h" 32885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org#include "arch.h" 33885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org#include "entenc.h" 34885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org#include "mfrngcod.h" 35885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org 36885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org/*A range encoder. 37885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org See entdec.c and the references for implementation details \cite{Mar79,MNW98}. 38885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org 39885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org @INPROCEEDINGS{Mar79, 40885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org author="Martin, G.N.N.", 41885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org title="Range encoding: an algorithm for removing redundancy from a digitised 42885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org message", 43885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org booktitle="Video \& Data Recording Conference", 44885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org year=1979, 45885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org address="Southampton", 46885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org month=Jul 47885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org } 48885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org @ARTICLE{MNW98, 49885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org author="Alistair Moffat and Radford Neal and Ian H. Witten", 50885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org title="Arithmetic Coding Revisited", 51885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org journal="{ACM} Transactions on Information Systems", 52885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org year=1998, 53885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org volume=16, 54885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org number=3, 55885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org pages="256--294", 56885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org month=Jul, 57885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org URL="http://www.stanford.edu/class/ee398/handouts/papers/Moffat98ArithmCoding.pdf" 58885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org }*/ 59885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org 60885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.orgstatic int ec_write_byte(ec_enc *_this,unsigned _value){ 61885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org if(_this->offs+_this->end_offs>=_this->storage)return -1; 62885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org _this->buf[_this->offs++]=(unsigned char)_value; 63885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org return 0; 64885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org} 65885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org 66885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.orgstatic int ec_write_byte_at_end(ec_enc *_this,unsigned _value){ 67885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org if(_this->offs+_this->end_offs>=_this->storage)return -1; 68885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org _this->buf[_this->storage-++(_this->end_offs)]=(unsigned char)_value; 69885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org return 0; 70885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org} 71885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org 72885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org/*Outputs a symbol, with a carry bit. 73885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org If there is a potential to propagate a carry over several symbols, they are 74885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org buffered until it can be determined whether or not an actual carry will 75885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org occur. 76885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org If the counter for the buffered symbols overflows, then the stream becomes 77885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org undecodable. 78885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org This gives a theoretical limit of a few billion symbols in a single packet on 79885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org 32-bit systems. 80885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org The alternative is to truncate the range in order to force a carry, but 81885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org requires similar carry tracking in the decoder, needlessly slowing it down.*/ 82885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.orgstatic void ec_enc_carry_out(ec_enc *_this,int _c){ 83885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org if(_c!=EC_SYM_MAX){ 84885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org /*No further carry propagation possible, flush buffer.*/ 85885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org int carry; 86885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org carry=_c>>EC_SYM_BITS; 87885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org /*Don't output a byte on the first write. 88885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org This compare should be taken care of by branch-prediction thereafter.*/ 89885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org if(_this->rem>=0)_this->error|=ec_write_byte(_this,_this->rem+carry); 90885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org if(_this->ext>0){ 91885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org unsigned sym; 92885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org sym=(EC_SYM_MAX+carry)&EC_SYM_MAX; 93885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org do _this->error|=ec_write_byte(_this,sym); 94885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org while(--(_this->ext)>0); 95885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org } 96885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org _this->rem=_c&EC_SYM_MAX; 97885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org } 98885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org else _this->ext++; 99885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org} 100885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org 101885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.orgstatic void ec_enc_normalize(ec_enc *_this){ 102885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org /*If the range is too small, output some bits and rescale it.*/ 103885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org while(_this->rng<=EC_CODE_BOT){ 104885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org ec_enc_carry_out(_this,(int)(_this->val>>EC_CODE_SHIFT)); 105885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org /*Move the next-to-high-order symbol into the high-order position.*/ 106885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org _this->val=(_this->val<<EC_SYM_BITS)&(EC_CODE_TOP-1); 107885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org _this->rng<<=EC_SYM_BITS; 108885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org _this->nbits_total+=EC_SYM_BITS; 109885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org } 110885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org} 111885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org 112885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.orgvoid ec_enc_init(ec_enc *_this,unsigned char *_buf,opus_uint32 _size){ 113885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org _this->buf=_buf; 114885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org _this->end_offs=0; 115885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org _this->end_window=0; 116885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org _this->nend_bits=0; 117885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org /*This is the offset from which ec_tell() will subtract partial bits.*/ 118885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org _this->nbits_total=EC_CODE_BITS+1; 119885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org _this->offs=0; 120885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org _this->rng=EC_CODE_TOP; 121885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org _this->rem=-1; 122885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org _this->val=0; 123885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org _this->ext=0; 124885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org _this->storage=_size; 125885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org _this->error=0; 126885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org} 127885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org 128885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.orgvoid ec_encode(ec_enc *_this,unsigned _fl,unsigned _fh,unsigned _ft){ 129885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org opus_uint32 r; 130885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org r=_this->rng/_ft; 131885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org if(_fl>0){ 132885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org _this->val+=_this->rng-IMUL32(r,(_ft-_fl)); 133885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org _this->rng=IMUL32(r,(_fh-_fl)); 134885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org } 135885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org else _this->rng-=IMUL32(r,(_ft-_fh)); 136885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org ec_enc_normalize(_this); 137885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org} 138885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org 139885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.orgvoid ec_encode_bin(ec_enc *_this,unsigned _fl,unsigned _fh,unsigned _bits){ 140885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org opus_uint32 r; 141885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org r=_this->rng>>_bits; 142885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org if(_fl>0){ 143885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org _this->val+=_this->rng-IMUL32(r,((1U<<_bits)-_fl)); 144885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org _this->rng=IMUL32(r,(_fh-_fl)); 145885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org } 146885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org else _this->rng-=IMUL32(r,((1U<<_bits)-_fh)); 147885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org ec_enc_normalize(_this); 148885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org} 149885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org 150885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org/*The probability of having a "one" is 1/(1<<_logp).*/ 151885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.orgvoid ec_enc_bit_logp(ec_enc *_this,int _val,unsigned _logp){ 152885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org opus_uint32 r; 153885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org opus_uint32 s; 154885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org opus_uint32 l; 155885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org r=_this->rng; 156885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org l=_this->val; 157885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org s=r>>_logp; 158885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org r-=s; 159885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org if(_val)_this->val=l+r; 160885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org _this->rng=_val?s:r; 161885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org ec_enc_normalize(_this); 162885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org} 163885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org 164885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.orgvoid ec_enc_icdf(ec_enc *_this,int _s,const unsigned char *_icdf,unsigned _ftb){ 165885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org opus_uint32 r; 166885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org r=_this->rng>>_ftb; 167885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org if(_s>0){ 168885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org _this->val+=_this->rng-IMUL32(r,_icdf[_s-1]); 169885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org _this->rng=IMUL32(r,_icdf[_s-1]-_icdf[_s]); 170885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org } 171885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org else _this->rng-=IMUL32(r,_icdf[_s]); 172885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org ec_enc_normalize(_this); 173885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org} 174885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org 175885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.orgvoid ec_enc_uint(ec_enc *_this,opus_uint32 _fl,opus_uint32 _ft){ 176885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org unsigned ft; 177885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org unsigned fl; 178885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org int ftb; 179885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org /*In order to optimize EC_ILOG(), it is undefined for the value 0.*/ 180885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org celt_assert(_ft>1); 181885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org _ft--; 182885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org ftb=EC_ILOG(_ft); 183885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org if(ftb>EC_UINT_BITS){ 184885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org ftb-=EC_UINT_BITS; 185885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org ft=(_ft>>ftb)+1; 186885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org fl=(unsigned)(_fl>>ftb); 187885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org ec_encode(_this,fl,fl+1,ft); 188885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org ec_enc_bits(_this,_fl&(((opus_uint32)1<<ftb)-1U),ftb); 189885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org } 190885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org else ec_encode(_this,_fl,_fl+1,_ft+1); 191885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org} 192885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org 193885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.orgvoid ec_enc_bits(ec_enc *_this,opus_uint32 _fl,unsigned _bits){ 194885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org ec_window window; 195885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org int used; 196885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org window=_this->end_window; 197885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org used=_this->nend_bits; 198885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org celt_assert(_bits>0); 199885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org if(used+_bits>EC_WINDOW_SIZE){ 200885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org do{ 201885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org _this->error|=ec_write_byte_at_end(_this,(unsigned)window&EC_SYM_MAX); 202885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org window>>=EC_SYM_BITS; 203885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org used-=EC_SYM_BITS; 204885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org } 205885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org while(used>=EC_SYM_BITS); 206885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org } 207885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org window|=(ec_window)_fl<<used; 208885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org used+=_bits; 209885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org _this->end_window=window; 210885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org _this->nend_bits=used; 211885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org _this->nbits_total+=_bits; 212885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org} 213885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org 214885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.orgvoid ec_enc_patch_initial_bits(ec_enc *_this,unsigned _val,unsigned _nbits){ 215885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org int shift; 216885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org unsigned mask; 217885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org celt_assert(_nbits<=EC_SYM_BITS); 218885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org shift=EC_SYM_BITS-_nbits; 219885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org mask=((1<<_nbits)-1)<<shift; 220885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org if(_this->offs>0){ 221885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org /*The first byte has been finalized.*/ 222885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org _this->buf[0]=(unsigned char)((_this->buf[0]&~mask)|_val<<shift); 223885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org } 224885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org else if(_this->rem>=0){ 225885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org /*The first byte is still awaiting carry propagation.*/ 226885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org _this->rem=(_this->rem&~mask)|_val<<shift; 227885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org } 228885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org else if(_this->rng<=(EC_CODE_TOP>>_nbits)){ 229885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org /*The renormalization loop has never been run.*/ 230885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org _this->val=(_this->val&~((opus_uint32)mask<<EC_CODE_SHIFT))| 231885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org (opus_uint32)_val<<(EC_CODE_SHIFT+shift); 232885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org } 233885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org /*The encoder hasn't even encoded _nbits of data yet.*/ 234885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org else _this->error=-1; 235885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org} 236885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org 237885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.orgvoid ec_enc_shrink(ec_enc *_this,opus_uint32 _size){ 238885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org celt_assert(_this->offs+_this->end_offs<=_size); 239885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org OPUS_MOVE(_this->buf+_size-_this->end_offs, 240885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org _this->buf+_this->storage-_this->end_offs,_this->end_offs); 241885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org _this->storage=_size; 242885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org} 243885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org 244885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.orgvoid ec_enc_done(ec_enc *_this){ 245885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org ec_window window; 246885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org int used; 247885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org opus_uint32 msk; 248885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org opus_uint32 end; 249885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org int l; 250885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org /*We output the minimum number of bits that ensures that the symbols encoded 251885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org thus far will be decoded correctly regardless of the bits that follow.*/ 252885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org l=EC_CODE_BITS-EC_ILOG(_this->rng); 253885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org msk=(EC_CODE_TOP-1)>>l; 254885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org end=(_this->val+msk)&~msk; 255885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org if((end|msk)>=_this->val+_this->rng){ 256885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org l++; 257885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org msk>>=1; 258885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org end=(_this->val+msk)&~msk; 259885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org } 260885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org while(l>0){ 261885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org ec_enc_carry_out(_this,(int)(end>>EC_CODE_SHIFT)); 262885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org end=(end<<EC_SYM_BITS)&(EC_CODE_TOP-1); 263885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org l-=EC_SYM_BITS; 264885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org } 265885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org /*If we have a buffered byte flush it into the output buffer.*/ 266885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org if(_this->rem>=0||_this->ext>0)ec_enc_carry_out(_this,0); 267885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org /*If we have buffered extra bits, flush them as well.*/ 268885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org window=_this->end_window; 269885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org used=_this->nend_bits; 270885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org while(used>=EC_SYM_BITS){ 271885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org _this->error|=ec_write_byte_at_end(_this,(unsigned)window&EC_SYM_MAX); 272885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org window>>=EC_SYM_BITS; 273885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org used-=EC_SYM_BITS; 274885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org } 275885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org /*Clear any excess space and add any remaining extra bits to the last byte.*/ 276885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org if(!_this->error){ 277885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org OPUS_CLEAR(_this->buf+_this->offs, 278885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org _this->storage-_this->offs-_this->end_offs); 279885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org if(used>0){ 280885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org /*If there's no range coder data at all, give up.*/ 281885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org if(_this->end_offs>=_this->storage)_this->error=-1; 282885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org else{ 283885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org l=-l; 284885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org /*If we've busted, don't add too many extra bits to the last byte; it 285885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org would corrupt the range coder data, and that's more important.*/ 286885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org if(_this->offs+_this->end_offs>=_this->storage&&l<used){ 287885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org window&=(1<<l)-1; 288885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org _this->error=-1; 289885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org } 290885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org _this->buf[_this->storage-_this->end_offs-1]|=(unsigned char)window; 291885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org } 292885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org } 293885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org } 294885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org} 295