The Tor Browser / file comparison
comparison: media/libopus/celt/entdec.c
media/libopus/celt/entdec.c
- branch
- TOR_BUG_9701
- changeset 10
- ac0c01689b40
equal
deleted
inserted
replaced
| -1:000000000000 | 0:08698d9fe668 |
|---|---|
| 1 /* Copyright (c) 2001-2011 Timothy B. Terriberry | |
| 2 Copyright (c) 2008-2009 Xiph.Org Foundation */ | |
| 3 /* | |
| 4 Redistribution and use in source and binary forms, with or without | |
| 5 modification, are permitted provided that the following conditions | |
| 6 are met: | |
| 7 | |
| 8 - Redistributions of source code must retain the above copyright | |
| 9 notice, this list of conditions and the following disclaimer. | |
| 10 | |
| 11 - Redistributions in binary form must reproduce the above copyright | |
| 12 notice, this list of conditions and the following disclaimer in the | |
| 13 documentation and/or other materials provided with the distribution. | |
| 14 | |
| 15 THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS | |
| 16 ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT | |
| 17 LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR | |
| 18 A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER | |
| 19 OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, | |
| 20 EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, | |
| 21 PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR | |
| 22 PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF | |
| 23 LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING | |
| 24 NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS | |
| 25 SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. | |
| 26 */ | |
| 27 | |
| 28 #ifdef HAVE_CONFIG_H | |
| 29 #include "config.h" | |
| 30 #endif | |
| 31 | |
| 32 #include <stddef.h> | |
| 33 #include "os_support.h" | |
| 34 #include "arch.h" | |
| 35 #include "entdec.h" | |
| 36 #include "mfrngcod.h" | |
| 37 | |
| 38 /*A range decoder. | |
| 39 This is an entropy decoder based upon \cite{Mar79}, which is itself a | |
| 40 rediscovery of the FIFO arithmetic code introduced by \cite{Pas76}. | |
| 41 It is very similar to arithmetic encoding, except that encoding is done with | |
| 42 digits in any base, instead of with bits, and so it is faster when using | |
| 43 larger bases (i.e.: a byte). | |
| 44 The author claims an average waste of $\frac{1}{2}\log_b(2b)$ bits, where $b$ | |
| 45 is the base, longer than the theoretical optimum, but to my knowledge there | |
| 46 is no published justification for this claim. | |
| 47 This only seems true when using near-infinite precision arithmetic so that | |
| 48 the process is carried out with no rounding errors. | |
| 49 | |
| 50 An excellent description of implementation details is available at | |
| 51 http://www.arturocampos.com/ac_range.html | |
| 52 A recent work \cite{MNW98} which proposes several changes to arithmetic | |
| 53 encoding for efficiency actually re-discovers many of the principles | |
| 54 behind range encoding, and presents a good theoretical analysis of them. | |
| 55 | |
| 56 End of stream is handled by writing out the smallest number of bits that | |
| 57 ensures that the stream will be correctly decoded regardless of the value of | |
| 58 any subsequent bits. | |
| 59 ec_tell() can be used to determine how many bits were needed to decode | |
| 60 all the symbols thus far; other data can be packed in the remaining bits of | |
| 61 the input buffer. | |
| 62 @PHDTHESIS{Pas76, | |
| 63 author="Richard Clark Pasco", | |
| 64 title="Source coding algorithms for fast data compression", | |
| 65 school="Dept. of Electrical Engineering, Stanford University", | |
| 66 address="Stanford, CA", | |
| 67 month=May, | |
| 68 year=1976 | |
| 69 } | |
| 70 @INPROCEEDINGS{Mar79, | |
| 71 author="Martin, G.N.N.", | |
| 72 title="Range encoding: an algorithm for removing redundancy from a digitised | |
| 73 message", | |
| 74 booktitle="Video & Data Recording Conference", | |
| 75 year=1979, | |
| 76 address="Southampton", | |
| 77 month=Jul | |
| 78 } | |
| 79 @ARTICLE{MNW98, | |
| 80 author="Alistair Moffat and Radford Neal and Ian H. Witten", | |
| 81 title="Arithmetic Coding Revisited", | |
| 82 journal="{ACM} Transactions on Information Systems", | |
| 83 year=1998, | |
| 84 volume=16, | |
| 85 number=3, | |
| 86 pages="256--294", | |
| 87 month=Jul, | |
| 88 URL="http://www.stanford.edu/class/ee398a/handouts/papers/Moffat98ArithmCoding.pdf" | |
| 89 }*/ | |
| 90 | |
| 91 static int ec_read_byte(ec_dec *_this){ | |
| 92 return _this->offs<_this->storage?_this->buf[_this->offs++]:0; | |
| 93 } | |
| 94 | |
| 95 static int ec_read_byte_from_end(ec_dec *_this){ | |
| 96 return _this->end_offs<_this->storage? | |
| 97 _this->buf[_this->storage-++(_this->end_offs)]:0; | |
| 98 } | |
| 99 | |
| 100 /*Normalizes the contents of val and rng so that rng lies entirely in the | |
| 101 high-order symbol.*/ | |
| 102 static void ec_dec_normalize(ec_dec *_this){ | |
| 103 /*If the range is too small, rescale it and input some bits.*/ | |
| 104 while(_this->rng<=EC_CODE_BOT){ | |
| 105 int sym; | |
| 106 _this->nbits_total+=EC_SYM_BITS; | |
| 107 _this->rng<<=EC_SYM_BITS; | |
| 108 /*Use up the remaining bits from our last symbol.*/ | |
| 109 sym=_this->rem; | |
| 110 /*Read the next value from the input.*/ | |
| 111 _this->rem=ec_read_byte(_this); | |
| 112 /*Take the rest of the bits we need from this new symbol.*/ | |
| 113 sym=(sym<<EC_SYM_BITS|_this->rem)>>(EC_SYM_BITS-EC_CODE_EXTRA); | |
| 114 /*And subtract them from val, capped to be less than EC_CODE_TOP.*/ | |
| 115 _this->val=((_this->val<<EC_SYM_BITS)+(EC_SYM_MAX&~sym))&(EC_CODE_TOP-1); | |
| 116 } | |
| 117 } | |
| 118 | |
| 119 void ec_dec_init(ec_dec *_this,unsigned char *_buf,opus_uint32 _storage){ | |
| 120 _this->buf=_buf; | |
| 121 _this->storage=_storage; | |
| 122 _this->end_offs=0; | |
| 123 _this->end_window=0; | |
| 124 _this->nend_bits=0; | |
| 125 /*This is the offset from which ec_tell() will subtract partial bits. | |
| 126 The final value after the ec_dec_normalize() call will be the same as in | |
| 127 the encoder, but we have to compensate for the bits that are added there.*/ | |
| 128 _this->nbits_total=EC_CODE_BITS+1 | |
| 129 -((EC_CODE_BITS-EC_CODE_EXTRA)/EC_SYM_BITS)*EC_SYM_BITS; | |
| 130 _this->offs=0; | |
| 131 _this->rng=1U<<EC_CODE_EXTRA; | |
| 132 _this->rem=ec_read_byte(_this); | |
| 133 _this->val=_this->rng-1-(_this->rem>>(EC_SYM_BITS-EC_CODE_EXTRA)); | |
| 134 _this->error=0; | |
| 135 /*Normalize the interval.*/ | |
| 136 ec_dec_normalize(_this); | |
| 137 } | |
| 138 | |
| 139 unsigned ec_decode(ec_dec *_this,unsigned _ft){ | |
| 140 unsigned s; | |
| 141 _this->ext=_this->rng/_ft; | |
| 142 s=(unsigned)(_this->val/_this->ext); | |
| 143 return _ft-EC_MINI(s+1,_ft); | |
| 144 } | |
| 145 | |
| 146 unsigned ec_decode_bin(ec_dec *_this,unsigned _bits){ | |
| 147 unsigned s; | |
| 148 _this->ext=_this->rng>>_bits; | |
| 149 s=(unsigned)(_this->val/_this->ext); | |
| 150 return (1U<<_bits)-EC_MINI(s+1U,1U<<_bits); | |
| 151 } | |
| 152 | |
| 153 void ec_dec_update(ec_dec *_this,unsigned _fl,unsigned _fh,unsigned _ft){ | |
| 154 opus_uint32 s; | |
| 155 s=IMUL32(_this->ext,_ft-_fh); | |
| 156 _this->val-=s; | |
| 157 _this->rng=_fl>0?IMUL32(_this->ext,_fh-_fl):_this->rng-s; | |
| 158 ec_dec_normalize(_this); | |
| 159 } | |
| 160 | |
| 161 /*The probability of having a "one" is 1/(1<<_logp).*/ | |
| 162 int ec_dec_bit_logp(ec_dec *_this,unsigned _logp){ | |
| 163 opus_uint32 r; | |
| 164 opus_uint32 d; | |
| 165 opus_uint32 s; | |
| 166 int ret; | |
| 167 r=_this->rng; | |
| 168 d=_this->val; | |
| 169 s=r>>_logp; | |
| 170 ret=d<s; | |
| 171 if(!ret)_this->val=d-s; | |
| 172 _this->rng=ret?s:r-s; | |
| 173 ec_dec_normalize(_this); | |
| 174 return ret; | |
| 175 } | |
| 176 | |
| 177 int ec_dec_icdf(ec_dec *_this,const unsigned char *_icdf,unsigned _ftb){ | |
| 178 opus_uint32 r; | |
| 179 opus_uint32 d; | |
| 180 opus_uint32 s; | |
| 181 opus_uint32 t; | |
| 182 int ret; | |
| 183 s=_this->rng; | |
| 184 d=_this->val; | |
| 185 r=s>>_ftb; | |
| 186 ret=-1; | |
| 187 do{ | |
| 188 t=s; | |
| 189 s=IMUL32(r,_icdf[++ret]); | |
| 190 } | |
| 191 while(d<s); | |
| 192 _this->val=d-s; | |
| 193 _this->rng=t-s; | |
| 194 ec_dec_normalize(_this); | |
| 195 return ret; | |
| 196 } | |
| 197 | |
| 198 opus_uint32 ec_dec_uint(ec_dec *_this,opus_uint32 _ft){ | |
| 199 unsigned ft; | |
| 200 unsigned s; | |
| 201 int ftb; | |
| 202 /*In order to optimize EC_ILOG(), it is undefined for the value 0.*/ | |
| 203 celt_assert(_ft>1); | |
| 204 _ft--; | |
| 205 ftb=EC_ILOG(_ft); | |
| 206 if(ftb>EC_UINT_BITS){ | |
| 207 opus_uint32 t; | |
| 208 ftb-=EC_UINT_BITS; | |
| 209 ft=(unsigned)(_ft>>ftb)+1; | |
| 210 s=ec_decode(_this,ft); | |
| 211 ec_dec_update(_this,s,s+1,ft); | |
| 212 t=(opus_uint32)s<<ftb|ec_dec_bits(_this,ftb); | |
| 213 if(t<=_ft)return t; | |
| 214 _this->error=1; | |
| 215 return _ft; | |
| 216 } | |
| 217 else{ | |
| 218 _ft++; | |
| 219 s=ec_decode(_this,(unsigned)_ft); | |
| 220 ec_dec_update(_this,s,s+1,(unsigned)_ft); | |
| 221 return s; | |
| 222 } | |
| 223 } | |
| 224 | |
| 225 opus_uint32 ec_dec_bits(ec_dec *_this,unsigned _bits){ | |
| 226 ec_window window; | |
| 227 int available; | |
| 228 opus_uint32 ret; | |
| 229 window=_this->end_window; | |
| 230 available=_this->nend_bits; | |
| 231 if((unsigned)available<_bits){ | |
| 232 do{ | |
| 233 window|=(ec_window)ec_read_byte_from_end(_this)<<available; | |
| 234 available+=EC_SYM_BITS; | |
| 235 } | |
| 236 while(available<=EC_WINDOW_SIZE-EC_SYM_BITS); | |
| 237 } | |
| 238 ret=(opus_uint32)window&(((opus_uint32)1<<_bits)-1U); | |
| 239 window>>=_bits; | |
| 240 available-=_bits; | |
| 241 _this->end_window=window; | |
| 242 _this->nend_bits=available; | |
| 243 _this->nbits_total+=_bits; | |
| 244 return ret; | |
| 245 } |
