21085b21e8a60c7c113b3a0e01e0d2ccd55745ea
[ffmpeg.git] / libavcodec / cabac.h
1 /*
2  * H.26L/H.264/AVC/JVT/14496-10/... encoder/decoder
3  * Copyright (c) 2003 Michael Niedermayer <michaelni@gmx.at>
4  *
5  * This library is free software; you can redistribute it and/or
6  * modify it under the terms of the GNU Lesser General Public
7  * License as published by the Free Software Foundation; either
8  * version 2 of the License, or (at your option) any later version.
9  *
10  * This library is distributed in the hope that it will be useful,
11  * but WITHOUT ANY WARRANTY; without even the implied warranty of
12  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
13  * Lesser General Public License for more details.
14  *
15  * You should have received a copy of the GNU Lesser General Public
16  * License along with this library; if not, write to the Free Software
17  * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
18  *
19  */
20  
21 /**
22  * @file cabac.h
23  * Context Adaptive Binary Arithmetic Coder.
24  */
25
26
27 #undef NDEBUG
28 #include <assert.h>
29
30 typedef struct CABACContext{
31     int low;
32     int range;
33     int outstanding_count;
34 #ifdef STRICT_LIMITS
35     int symCount;
36 #endif
37     uint8_t lps_range[2*64][4];   ///< rangeTabLPS
38     uint8_t lps_state[2*64];      ///< transIdxLPS
39     uint8_t mps_state[2*64];      ///< transIdxMPS
40     const uint8_t *bytestream_start;
41     const uint8_t *bytestream;
42     const uint8_t *bytestream_end;
43     int bits_left;                ///<
44     PutBitContext pb;
45 }CABACContext;
46
47 extern const uint8_t ff_h264_lps_range[64][4];
48 extern const uint8_t ff_h264_mps_state[64];
49 extern const uint8_t ff_h264_lps_state[64];
50
51 void ff_init_cabac_encoder(CABACContext *c, uint8_t *buf, int buf_size);
52 void ff_init_cabac_decoder(CABACContext *c, const uint8_t *buf, int buf_size);
53 void ff_init_cabac_states(CABACContext *c, uint8_t const (*lps_range)[4], 
54                           uint8_t const *mps_state, uint8_t const *lps_state, int state_count);
55
56
57 static inline void put_cabac_bit(CABACContext *c, int b){
58     put_bits(&c->pb, 1, b); 
59     for(;c->outstanding_count; c->outstanding_count--){ 
60         put_bits(&c->pb, 1, 1-b);
61     }
62 }
63
64 static inline void renorm_cabac_encoder(CABACContext *c){
65     while(c->range < 0x100){
66         //FIXME optimize
67         if(c->low<0x100){
68             put_cabac_bit(c, 0);
69         }else if(c->low<0x200){
70             c->outstanding_count++;
71             c->low -= 0x100;
72         }else{
73             put_cabac_bit(c, 1);
74             c->low -= 0x200;
75         }
76         
77         c->range+= c->range;
78         c->low += c->low;
79     }
80 }
81
82 static inline void put_cabac(CABACContext *c, uint8_t * const state, int bit){
83     int RangeLPS= c->lps_range[*state][((c->range)>>6)&3];
84     
85     if(bit == ((*state)&1)){
86         c->range -= RangeLPS;
87         *state= c->mps_state[*state];
88     }else{
89         c->low += c->range - RangeLPS;
90         c->range = RangeLPS;
91         *state= c->lps_state[*state];
92     }
93     
94     renorm_cabac_encoder(c);
95
96 #ifdef STRICT_LIMITS
97     c->symCount++;
98 #endif
99 }
100
101 static inline void put_cabac_static(CABACContext *c, int RangeLPS, int bit){
102     assert(c->range > RangeLPS);
103
104     if(!bit){
105         c->range -= RangeLPS;
106     }else{
107         c->low += c->range - RangeLPS;
108         c->range = RangeLPS;
109     }
110
111     renorm_cabac_encoder(c);
112
113 #ifdef STRICT_LIMITS
114     c->symCount++;
115 #endif
116 }
117
118 /**
119  * @param bit 0 -> write zero bit, !=0 write one bit
120  */
121 static inline void put_cabac_bypass(CABACContext *c, int bit){
122     c->low += c->low;
123
124     if(bit){
125         c->low += c->range;
126     }
127 //FIXME optimize
128     if(c->low<0x200){
129         put_cabac_bit(c, 0);
130     }else if(c->low<0x400){
131         c->outstanding_count++;
132         c->low -= 0x200;
133     }else{
134         put_cabac_bit(c, 1);
135         c->low -= 0x400;
136     }
137         
138 #ifdef STRICT_LIMITS
139     c->symCount++;
140 #endif
141 }
142
143 /**
144  *
145  * @return the number of bytes written
146  */
147 static inline int put_cabac_terminate(CABACContext *c, int bit){
148     c->range -= 2;
149
150     if(!bit){
151         renorm_cabac_encoder(c);
152     }else{
153         c->low += c->range;
154         c->range= 2;
155         
156         renorm_cabac_encoder(c);
157
158         assert(c->low <= 0x1FF);
159         put_cabac_bit(c, c->low>>9);
160         put_bits(&c->pb, 2, ((c->low>>7)&3)|1);
161         
162         flush_put_bits(&c->pb); //FIXME FIXME FIXME XXX wrong
163     }
164         
165 #ifdef STRICT_LIMITS
166     c->symCount++;
167 #endif
168
169     return (put_bits_count(&c->pb)+7)>>3;
170 }
171
172 /**
173  * put (truncated) unary binarization.
174  */
175 static inline void put_cabac_u(CABACContext *c, uint8_t * state, int v, int max, int max_index, int truncated){
176     int i;
177     
178     assert(v <= max);
179     
180 #if 1
181     for(i=0; i<v; i++){
182         put_cabac(c, state, 1);
183         if(i < max_index) state++;
184     }
185     if(truncated==0 || v<max)
186         put_cabac(c, state, 0);
187 #else
188     if(v <= max_index){
189         for(i=0; i<v; i++){
190             put_cabac(c, state+i, 1);
191         }
192         if(truncated==0 || v<max)
193             put_cabac(c, state+i, 0);
194     }else{
195         for(i=0; i<=max_index; i++){
196             put_cabac(c, state+i, 1);
197         }
198         for(; i<v; i++){
199             put_cabac(c, state+max_index, 1);
200         }
201         if(truncated==0 || v<max)
202             put_cabac(c, state+max_index, 0);
203     }
204 #endif
205 }
206
207 /**
208  * put unary exp golomb k-th order binarization.
209  */
210 static inline void put_cabac_ueg(CABACContext *c, uint8_t * state, int v, int max, int is_signed, int k, int max_index){
211     int i;
212     
213     if(v==0)
214         put_cabac(c, state, 0);
215     else{
216         const int sign= v < 0;
217         
218         if(is_signed) v= ABS(v);
219         
220         if(v<max){
221             for(i=0; i<v; i++){
222                 put_cabac(c, state, 1);
223                 if(i < max_index) state++;
224             }
225
226             put_cabac(c, state, 0);
227         }else{
228             int m= 1<<k;
229
230             for(i=0; i<max; i++){
231                 put_cabac(c, state, 1);
232                 if(i < max_index) state++;
233             }
234
235             v -= max;
236             while(v >= m){ //FIXME optimize
237                 put_cabac_bypass(c, 1);
238                 v-= m;
239                 m+= m;
240             }
241             put_cabac_bypass(c, 0);
242             while(m>>=1){
243                 put_cabac_bypass(c, v&m);
244             }
245         }
246
247         if(is_signed)
248             put_cabac_bypass(c, sign);
249     }
250 }
251
252 static inline void renorm_cabac_decoder(CABACContext *c){
253     while(c->range < 0x10000){
254         c->range+= c->range;
255         c->low+= c->low;
256         if(--c->bits_left == 0){
257             if(c->bytestream < c->bytestream_end)
258                 c->low+= *c->bytestream;
259             c->bytestream++;
260             c->bits_left= 8;
261         }
262     }
263 }
264
265 static inline int get_cabac(CABACContext *c, uint8_t * const state){
266     int RangeLPS= c->lps_range[*state][((c->range)>>14)&3]<<8;
267     int bit;
268     
269     c->range -= RangeLPS;
270     if(c->low < c->range){
271         bit= (*state)&1;
272         *state= c->mps_state[*state];
273     }else{
274         bit= ((*state)&1)^1;
275         c->low -= c->range;
276         c->range = RangeLPS;
277         *state= c->lps_state[*state];
278     }
279     renorm_cabac_decoder(c);
280     
281     return bit;    
282 }
283
284 static inline int get_cabac_static(CABACContext *c, int RangeLPS){
285     int bit;
286     
287     c->range -= RangeLPS;
288     if(c->low < c->range){
289         bit= 0;
290     }else{
291         bit= 1;
292         c->low -= c->range;
293         c->range = RangeLPS;
294     }
295     renorm_cabac_decoder(c);
296     
297     return bit;    
298 }
299
300 static inline int get_cabac_bypass(CABACContext *c){
301     c->low += c->low;
302
303     if(--c->bits_left == 0){
304         if(c->bytestream < c->bytestream_end)
305             c->low+= *c->bytestream;
306         c->bytestream++;
307         c->bits_left= 8;
308     }
309     
310     if(c->low < c->range){
311         return 0;
312     }else{
313         c->low -= c->range;
314         return 1;
315     }
316 }
317
318 /**
319  *
320  * @return the number of bytes read or 0 if no end
321  */
322 static inline int get_cabac_terminate(CABACContext *c){
323     c->range -= 2<<8;
324     if(c->low < c->range){
325         renorm_cabac_decoder(c);    
326         return 0;
327     }else{
328         return c->bytestream - c->bytestream_start;
329     }    
330 }
331
332 /**
333  * get (truncated) unnary binarization.
334  */
335 static inline int get_cabac_u(CABACContext *c, uint8_t * state, int max, int max_index, int truncated){
336     int i;
337     
338     for(i=0; i<max; i++){ 
339         if(get_cabac(c, state)==0)
340             return i;
341             
342         if(i< max_index) state++;
343     }
344
345     return truncated ? max : -1;
346 }
347
348 /**
349  * get unary exp golomb k-th order binarization.
350  */
351 static inline int get_cabac_ueg(CABACContext *c, uint8_t * state, int max, int is_signed, int k, int max_index){
352     int i, v;
353     int m= 1<<k;
354     
355     if(get_cabac(c, state)==0) 
356         return 0;
357         
358     if(0 < max_index) state++;
359     
360     for(i=1; i<max; i++){ 
361         if(get_cabac(c, state)==0){
362             if(is_signed && get_cabac_bypass(c)){
363                 return -i;
364             }else
365                 return i;
366         }
367
368         if(i < max_index) state++;
369     }
370     
371     while(get_cabac_bypass(c)){
372         i+= m;
373         m+= m;
374     }
375     
376     v=0;
377     while(m>>=1){
378         v+= v + get_cabac_bypass(c);
379     }
380     i += v;
381
382     if(is_signed && get_cabac_bypass(c)){
383         return -i;
384     }else
385         return i;
386 }