Multiply-free version of the range coder. Haven't yet decided which version to
[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   unsigned r;
96   unsigned s;
97   unsigned d;
98   int      nrm;
99   /*Step 1: we want ft in the range of [rng/2,rng).
100     The high-order bits of the rng and ft are computed via a logarithm.
101     This could also be done on some architectures with some custom assembly,
102      which would provide even more speed.*/
103   nrm=EC_ILOG(_this->rng)-EC_ILOG(_ft);
104   /*Having the same high order bit may be too much.
105     We may need to shift one less to ensure that ft is actually in the proper
106      range.*/
107   _ft<<=nrm;
108   d=_ft>_this->rng;
109   _ft>>=d;
110   nrm-=d;
111   /*We then scale everything by the computed power of 2.*/
112   _fl<<=nrm;
113   _fh<<=nrm;
114   /*Step 2: compute the two values of the partition function.
115     d is the splitting point of the interval [0,ft).*/
116   d=_this->rng-_ft;
117   r=_fh+EC_MINI(_fh,d);
118   s=_fl+EC_MINI(_fl,d);
119   /*Step 3: Update the end-point and range of the interval.*/
120   _this->low+=s;
121   _this->rng=r-s;
122   /*Step 4: Normalize the interval.*/
123   ec_enc_normalize(_this);
124 }
125
126 void ec_encode_bin(ec_enc *_this,unsigned _fl,unsigned _fh,unsigned bits){
127   ec_encode(_this, _fl, _fh, 1U<<bits);
128 }
129
130 long ec_enc_tell(ec_enc *_this,int _b){
131   ec_uint32 r;
132   int       l;
133   long      nbits;
134   nbits=ec_byte_bytes(_this->buf)+(_this->rem>=0)+_this->ext<<3;
135   /*To handle the non-integral number of bits still left in the encoder state,
136      we compute the number of bits of low that must be encoded to ensure that
137      the value is inside the range for any possible subsequent bits.
138     Note that this is subtly different than the actual value we would end the
139      stream with, which tries to make as many of the trailing bits zeros as
140      possible.*/
141   nbits+=EC_CODE_BITS;
142   nbits<<=_b;
143   l=EC_ILOG(_this->rng);
144   r=_this->rng>>l-16;
145   while(_b-->0){
146     int b;
147     r=r*r>>15;
148     b=(int)(r>>16);
149     l=l<<1|b;
150     r>>=b;
151   }
152   return nbits-l;
153 }
154
155 void ec_enc_done(ec_enc *_this){
156   /*We compute the integer in the current interval that has the largest number
157      of trailing zeros, and write that to the stream.
158     This is guaranteed to yield the smallest possible encoding.*/
159   if(_this->low){
160     ec_uint32 end;
161     end=EC_CODE_TOP;
162     /*Ensure that the end value is in the range.*/
163     if(end-_this->low>=_this->rng){
164       ec_uint32 msk;
165       msk=EC_CODE_TOP-1;
166       do{
167         msk>>=1;
168         end=_this->low+msk&~msk|msk+1;
169       }
170       while(end-_this->low>=_this->rng);
171     }
172     /*The remaining output is the next free end.*/
173     while(end){
174       ec_enc_carry_out(_this,end>>EC_CODE_SHIFT);
175       end=end<<EC_SYM_BITS&EC_CODE_TOP-1;
176     }
177   }
178   /*If we have a buffered byte flush it into the output buffer.*/
179   if(_this->rem>0||_this->ext>0){
180     ec_enc_carry_out(_this,0);
181     _this->rem=-1;
182   }
183 }