1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/media/libopus/celt/entdec.c Wed Dec 31 06:09:35 2014 +0100
1.3 @@ -0,0 +1,245 @@
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 +#ifdef HAVE_CONFIG_H
1.32 +#include "config.h"
1.33 +#endif
1.34 +
1.35 +#include <stddef.h>
1.36 +#include "os_support.h"
1.37 +#include "arch.h"
1.38 +#include "entdec.h"
1.39 +#include "mfrngcod.h"
1.40 +
1.41 +/*A range decoder.
1.42 + This is an entropy decoder based upon \cite{Mar79}, which is itself a
1.43 + rediscovery of the FIFO arithmetic code introduced by \cite{Pas76}.
1.44 + It is very similar to arithmetic encoding, except that encoding is done with
1.45 + digits in any base, instead of with bits, and so it is faster when using
1.46 + larger bases (i.e.: a byte).
1.47 + The author claims an average waste of $\frac{1}{2}\log_b(2b)$ bits, where $b$
1.48 + is the base, longer than the theoretical optimum, but to my knowledge there
1.49 + is no published justification for this claim.
1.50 + This only seems true when using near-infinite precision arithmetic so that
1.51 + the process is carried out with no rounding errors.
1.52 +
1.53 + An excellent description of implementation details is available at
1.54 + http://www.arturocampos.com/ac_range.html
1.55 + A recent work \cite{MNW98} which proposes several changes to arithmetic
1.56 + encoding for efficiency actually re-discovers many of the principles
1.57 + behind range encoding, and presents a good theoretical analysis of them.
1.58 +
1.59 + End of stream is handled by writing out the smallest number of bits that
1.60 + ensures that the stream will be correctly decoded regardless of the value of
1.61 + any subsequent bits.
1.62 + ec_tell() can be used to determine how many bits were needed to decode
1.63 + all the symbols thus far; other data can be packed in the remaining bits of
1.64 + the input buffer.
1.65 + @PHDTHESIS{Pas76,
1.66 + author="Richard Clark Pasco",
1.67 + title="Source coding algorithms for fast data compression",
1.68 + school="Dept. of Electrical Engineering, Stanford University",
1.69 + address="Stanford, CA",
1.70 + month=May,
1.71 + year=1976
1.72 + }
1.73 + @INPROCEEDINGS{Mar79,
1.74 + author="Martin, G.N.N.",
1.75 + title="Range encoding: an algorithm for removing redundancy from a digitised
1.76 + message",
1.77 + booktitle="Video & Data Recording Conference",
1.78 + year=1979,
1.79 + address="Southampton",
1.80 + month=Jul
1.81 + }
1.82 + @ARTICLE{MNW98,
1.83 + author="Alistair Moffat and Radford Neal and Ian H. Witten",
1.84 + title="Arithmetic Coding Revisited",
1.85 + journal="{ACM} Transactions on Information Systems",
1.86 + year=1998,
1.87 + volume=16,
1.88 + number=3,
1.89 + pages="256--294",
1.90 + month=Jul,
1.91 + URL="http://www.stanford.edu/class/ee398a/handouts/papers/Moffat98ArithmCoding.pdf"
1.92 + }*/
1.93 +
1.94 +static int ec_read_byte(ec_dec *_this){
1.95 + return _this->offs<_this->storage?_this->buf[_this->offs++]:0;
1.96 +}
1.97 +
1.98 +static int ec_read_byte_from_end(ec_dec *_this){
1.99 + return _this->end_offs<_this->storage?
1.100 + _this->buf[_this->storage-++(_this->end_offs)]:0;
1.101 +}
1.102 +
1.103 +/*Normalizes the contents of val and rng so that rng lies entirely in the
1.104 + high-order symbol.*/
1.105 +static void ec_dec_normalize(ec_dec *_this){
1.106 + /*If the range is too small, rescale it and input some bits.*/
1.107 + while(_this->rng<=EC_CODE_BOT){
1.108 + int sym;
1.109 + _this->nbits_total+=EC_SYM_BITS;
1.110 + _this->rng<<=EC_SYM_BITS;
1.111 + /*Use up the remaining bits from our last symbol.*/
1.112 + sym=_this->rem;
1.113 + /*Read the next value from the input.*/
1.114 + _this->rem=ec_read_byte(_this);
1.115 + /*Take the rest of the bits we need from this new symbol.*/
1.116 + sym=(sym<<EC_SYM_BITS|_this->rem)>>(EC_SYM_BITS-EC_CODE_EXTRA);
1.117 + /*And subtract them from val, capped to be less than EC_CODE_TOP.*/
1.118 + _this->val=((_this->val<<EC_SYM_BITS)+(EC_SYM_MAX&~sym))&(EC_CODE_TOP-1);
1.119 + }
1.120 +}
1.121 +
1.122 +void ec_dec_init(ec_dec *_this,unsigned char *_buf,opus_uint32 _storage){
1.123 + _this->buf=_buf;
1.124 + _this->storage=_storage;
1.125 + _this->end_offs=0;
1.126 + _this->end_window=0;
1.127 + _this->nend_bits=0;
1.128 + /*This is the offset from which ec_tell() will subtract partial bits.
1.129 + The final value after the ec_dec_normalize() call will be the same as in
1.130 + the encoder, but we have to compensate for the bits that are added there.*/
1.131 + _this->nbits_total=EC_CODE_BITS+1
1.132 + -((EC_CODE_BITS-EC_CODE_EXTRA)/EC_SYM_BITS)*EC_SYM_BITS;
1.133 + _this->offs=0;
1.134 + _this->rng=1U<<EC_CODE_EXTRA;
1.135 + _this->rem=ec_read_byte(_this);
1.136 + _this->val=_this->rng-1-(_this->rem>>(EC_SYM_BITS-EC_CODE_EXTRA));
1.137 + _this->error=0;
1.138 + /*Normalize the interval.*/
1.139 + ec_dec_normalize(_this);
1.140 +}
1.141 +
1.142 +unsigned ec_decode(ec_dec *_this,unsigned _ft){
1.143 + unsigned s;
1.144 + _this->ext=_this->rng/_ft;
1.145 + s=(unsigned)(_this->val/_this->ext);
1.146 + return _ft-EC_MINI(s+1,_ft);
1.147 +}
1.148 +
1.149 +unsigned ec_decode_bin(ec_dec *_this,unsigned _bits){
1.150 + unsigned s;
1.151 + _this->ext=_this->rng>>_bits;
1.152 + s=(unsigned)(_this->val/_this->ext);
1.153 + return (1U<<_bits)-EC_MINI(s+1U,1U<<_bits);
1.154 +}
1.155 +
1.156 +void ec_dec_update(ec_dec *_this,unsigned _fl,unsigned _fh,unsigned _ft){
1.157 + opus_uint32 s;
1.158 + s=IMUL32(_this->ext,_ft-_fh);
1.159 + _this->val-=s;
1.160 + _this->rng=_fl>0?IMUL32(_this->ext,_fh-_fl):_this->rng-s;
1.161 + ec_dec_normalize(_this);
1.162 +}
1.163 +
1.164 +/*The probability of having a "one" is 1/(1<<_logp).*/
1.165 +int ec_dec_bit_logp(ec_dec *_this,unsigned _logp){
1.166 + opus_uint32 r;
1.167 + opus_uint32 d;
1.168 + opus_uint32 s;
1.169 + int ret;
1.170 + r=_this->rng;
1.171 + d=_this->val;
1.172 + s=r>>_logp;
1.173 + ret=d<s;
1.174 + if(!ret)_this->val=d-s;
1.175 + _this->rng=ret?s:r-s;
1.176 + ec_dec_normalize(_this);
1.177 + return ret;
1.178 +}
1.179 +
1.180 +int ec_dec_icdf(ec_dec *_this,const unsigned char *_icdf,unsigned _ftb){
1.181 + opus_uint32 r;
1.182 + opus_uint32 d;
1.183 + opus_uint32 s;
1.184 + opus_uint32 t;
1.185 + int ret;
1.186 + s=_this->rng;
1.187 + d=_this->val;
1.188 + r=s>>_ftb;
1.189 + ret=-1;
1.190 + do{
1.191 + t=s;
1.192 + s=IMUL32(r,_icdf[++ret]);
1.193 + }
1.194 + while(d<s);
1.195 + _this->val=d-s;
1.196 + _this->rng=t-s;
1.197 + ec_dec_normalize(_this);
1.198 + return ret;
1.199 +}
1.200 +
1.201 +opus_uint32 ec_dec_uint(ec_dec *_this,opus_uint32 _ft){
1.202 + unsigned ft;
1.203 + unsigned s;
1.204 + int ftb;
1.205 + /*In order to optimize EC_ILOG(), it is undefined for the value 0.*/
1.206 + celt_assert(_ft>1);
1.207 + _ft--;
1.208 + ftb=EC_ILOG(_ft);
1.209 + if(ftb>EC_UINT_BITS){
1.210 + opus_uint32 t;
1.211 + ftb-=EC_UINT_BITS;
1.212 + ft=(unsigned)(_ft>>ftb)+1;
1.213 + s=ec_decode(_this,ft);
1.214 + ec_dec_update(_this,s,s+1,ft);
1.215 + t=(opus_uint32)s<<ftb|ec_dec_bits(_this,ftb);
1.216 + if(t<=_ft)return t;
1.217 + _this->error=1;
1.218 + return _ft;
1.219 + }
1.220 + else{
1.221 + _ft++;
1.222 + s=ec_decode(_this,(unsigned)_ft);
1.223 + ec_dec_update(_this,s,s+1,(unsigned)_ft);
1.224 + return s;
1.225 + }
1.226 +}
1.227 +
1.228 +opus_uint32 ec_dec_bits(ec_dec *_this,unsigned _bits){
1.229 + ec_window window;
1.230 + int available;
1.231 + opus_uint32 ret;
1.232 + window=_this->end_window;
1.233 + available=_this->nend_bits;
1.234 + if((unsigned)available<_bits){
1.235 + do{
1.236 + window|=(ec_window)ec_read_byte_from_end(_this)<<available;
1.237 + available+=EC_SYM_BITS;
1.238 + }
1.239 + while(available<=EC_WINDOW_SIZE-EC_SYM_BITS);
1.240 + }
1.241 + ret=(opus_uint32)window&(((opus_uint32)1<<_bits)-1U);
1.242 + window>>=_bits;
1.243 + available-=_bits;
1.244 + _this->end_window=window;
1.245 + _this->nend_bits=available;
1.246 + _this->nbits_total+=_bits;
1.247 + return ret;
1.248 +}
