The Tor Browser / annotate

media/libopus/celt/entdec.c@ac0c01689b40 (annotated)

media/libopus/celt/entdec.c

Thu, 15 Jan 2015 15:59:08 +0100

author
Michael Schloh von Bennewitz <michael@schloh.com>
date
Thu, 15 Jan 2015 15:59:08 +0100
branch
TOR_BUG_9701
changeset 10
ac0c01689b40
permissions
-rw-r--r--

Implement a real Private Browsing Mode condition by changing the API/ABI;
This solves Tor bug #9701, complying with disk avoidance documented in
https://www.torproject.org/projects/torbrowser/design/#disk-avoidance.

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

Mercurial Repository: The Tor Browser

Europalab SCM Repository Server

mercurial