Fixes some issues in the MF range coder on systems were ints are 16 bits.
[opus.git] / libcelt / mfrngenc.c
1 #ifdef HAVE_CONFIG_H
2 #include "config.h"
3 #endif
4
5 #include "arch.h"
6 #include "entenc.h"
7 #include "mfrngcod.h"
8
9
10
11 /*A multiply-free range encoder.
12   See mfrngdec.c and the references for implementation details
13    \cite{Mar79,MNW98,SM98}.
14
15   @INPROCEEDINGS{Mar79,
16    author="Martin, G.N.N.",
17    title="Range encoding: an algorithm for removing redundancy from a digitised
18     message",
19    booktitle="Video \& Data Recording Conference",
20    year=1979,
21    address="Southampton",
22    month=Jul
23   }
24   @ARTICLE{MNW98,
25    author="Alistair Moffat and Radford Neal and Ian H. Witten",
26    title="Arithmetic Coding Revisited",
27    journal="{ACM} Transactions on Information Systems",
28    year=1998,
29    volume=16,
30    number=3,
31    pages="256--294",
32    month=Jul,
33    URL="http://www.stanford.edu/class/ee398/handouts/papers/Moffat98ArithmCoding.pdf"
34   }
35   @INPROCEEDINGS{SM98,
36    author="Lang Stuiver and Alistair Moffat",
37    title="Piecewise Integer Mapping for Arithmetic Coding",
38    booktitle="Proceedings of the {IEEE} Data Compression Conference",
39    pages="1--10",
40    address="Snowbird, UT",
41    month="Mar./Apr.",
42    year=1998
43   }*/
44
45
46
47 /*Outputs a symbol, with a carry bit.
48   If there is a potential to propagate a carry over several symbols, they are
49    buffered until it can be determined whether or not an actual carry will
50    occur.
51   If the counter for the buffered symbols overflows, then the stream becomes
52    undecodable.
53   This gives a theoretical limit of a few billion symbols in a single packet on
54    32-bit systems.
55   The alternative is to truncate the range in order to force a carry, but
56    requires similar carry tracking in the decoder, needlessly slowing it down.*/
57 static void ec_enc_carry_out(ec_enc *_this,int _c){
58   if(_c!=EC_SYM_MAX){
59     /*No further carry propagation possible, flush buffer.*/
60     int carry;
61     carry=_c>>EC_SYM_BITS;
62     /*Don't output a byte on the first write.
63       This compare should be taken care of by branch-prediction thereafter.*/
64     if(_this->rem>=0)ec_byte_write1(_this->buf,_this->rem+carry);
65     if(_this->ext>0){
66       unsigned sym;
67       sym=EC_SYM_MAX+carry&EC_SYM_MAX;
68       do ec_byte_write1(_this->buf,sym);
69       while(--(_this->ext)>0);
70     }
71     _this->rem=_c&EC_SYM_MAX;
72   }
73   else _this->ext++;
74 }
75
76 static inline void ec_enc_normalize(ec_enc *_this){
77   /*If the range is too small, output some bits and rescale it.*/
78   while(_this->rng<=EC_CODE_BOT){
79     ec_enc_carry_out(_this,(int)(_this->low>>EC_CODE_SHIFT));
80     /*Move the next-to-high-order symbol into the high-order position.*/
81     _this->low=_this->low<<EC_SYM_BITS&EC_CODE_TOP-1;
82     _this->rng<<=EC_SYM_BITS;
83   }
84 }
85
86 void ec_enc_init(ec_enc *_this,ec_byte_buffer *_buf){
87   _this->buf=_buf;
88   _this->rem=-1;
89   _this->ext=0;
90   _this->low=0;
91   _this->rng=EC_CODE_TOP;
92 }
93
94 void ec_encode(ec_enc *_this,unsigned _fl,unsigned _fh,unsigned _ft){
95   ec_uint32 fl;
96   ec_uint32 fh;
97   ec_uint32 ft;
98   ec_uint32 r;
99   ec_uint32 s;
100   ec_uint32 d;
101   int       e;
102   int       nrm;
103   /*Step 1: we want ft in the range of [rng/2,rng).
104     The high-order bits of the rng and ft are computed via a logarithm.
105     This could also be done on some architectures with some custom assembly,
106      which would provide even more speed.*/
107   nrm=EC_ILOG(_this->rng)-EC_ILOG(_ft);
108   /*Having the same high order bit may be too much.
109     We may need to shift one less to ensure that ft is actually in the proper
110      range.*/
111   ft=(ec_uint32)_ft<<nrm;
112   e=ft>_this->rng;
113   ft>>=e;
114   nrm-=e;
115   /*We then scale everything by the computed power of 2.*/
116   fl=(ec_uint32)_fl<<nrm;
117   fh=(ec_uint32)_fh<<nrm;
118   /*Step 2: compute the two values of the partition function.
119     d is the splitting point of the interval [0,ft).*/
120   d=_this->rng-ft;
121   r=fh+EC_MINI(fh,d);
122   s=fl+EC_MINI(fl,d);
123   /*Step 3: Update the end-point and range of the interval.*/
124   _this->low+=s;
125   _this->rng=r-s;
126   /*Step 4: Normalize the interval.*/
127   ec_enc_normalize(_this);
128 }
129
130 void ec_encode_bin(ec_enc *_this,unsigned _fl,unsigned _fh,unsigned bits){
131   ec_encode(_this, _fl, _fh, 1U<<bits);
132 }
133
134 long ec_enc_tell(ec_enc *_this,int _b){
135   ec_uint32 r;
136   int       l;
137   long      nbits;
138   nbits=(ec_byte_bytes(_this->buf)+(_this->rem>=0)+_this->ext)*EC_SYM_BITS;
139   /*To handle the non-integral number of bits still left in the encoder state,
140      we compute the number of bits of low that must be encoded to ensure that
141      the value is inside the range for any possible subsequent bits.
142     Note that this is subtly different than the actual value we would end the
143      stream with, which tries to make as many of the trailing bits zeros as
144      possible.*/
145   nbits+=EC_CODE_BITS;
146   nbits<<=_b;
147   l=EC_ILOG(_this->rng);
148   r=_this->rng>>l-16;
149   while(_b-->0){
150     int b;
151     r=r*r>>15;
152     b=(int)(r>>16);
153     l=l<<1|b;
154     r>>=b;
155   }
156   return nbits-l;
157 }
158
159 void ec_enc_done(ec_enc *_this){
160   /*We compute the integer in the current interval that has the largest number
161      of trailing zeros, and write that to the stream.
162     This is guaranteed to yield the smallest possible encoding.*/
163   if(_this->low){
164     ec_uint32 end;
165     end=EC_CODE_TOP;
166     /*Ensure that the end value is in the range.*/
167     if(end-_this->low>=_this->rng){
168       ec_uint32 msk;
169       msk=EC_CODE_TOP-1;
170       do{
171         msk>>=1;
172         end=_this->low+msk&~msk|msk+1;
173       }
174       while(end-_this->low>=_this->rng);
175     }
176     /*The remaining output is the next free end.*/
177     while(end){
178       ec_enc_carry_out(_this,end>>EC_CODE_SHIFT);
179       end=end<<EC_SYM_BITS&EC_CODE_TOP-1;
180     }
181   }
182   /*If we have a buffered byte flush it into the output buffer.*/
183   if(_this->rem>0||_this->ext>0){
184     ec_enc_carry_out(_this,0);
185     _this->rem=-1;
186   }
187 }