5% faster get_cabac()
[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 file is part of FFmpeg.
6  *
7  * FFmpeg is free software; you can redistribute it and/or
8  * modify it under the terms of the GNU Lesser General Public
9  * License as published by the Free Software Foundation; either
10  * version 2.1 of the License, or (at your option) any later version.
11  *
12  * FFmpeg is distributed in the hope that it will be useful,
13  * but WITHOUT ANY WARRANTY; without even the implied warranty of
14  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
15  * Lesser General Public License for more details.
16  *
17  * You should have received a copy of the GNU Lesser General Public
18  * License along with FFmpeg; if not, write to the Free Software
19  * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
20  *
21  */
22
23 /**
24  * @file cabac.h
25  * Context Adaptive Binary Arithmetic Coder.
26  */
27
28
29 //#undef NDEBUG
30 #include <assert.h>
31
32 #define CABAC_BITS 16
33 #define CABAC_MASK ((1<<CABAC_BITS)-1)
34
35 typedef struct CABACContext{
36     int low;
37     int range;
38     int outstanding_count;
39 #ifdef STRICT_LIMITS
40     int symCount;
41 #endif
42     uint8_t lps_range[2*66][4];   ///< rangeTabLPS
43     uint8_t lps_state[2*65];      ///< transIdxLPS
44     uint8_t mps_state[2*65];      ///< transIdxMPS
45     const uint8_t *bytestream_start;
46     const uint8_t *bytestream;
47     const uint8_t *bytestream_end;
48     PutBitContext pb;
49 }CABACContext;
50
51 extern const uint8_t ff_h264_lps_range[64][4];
52 extern const uint8_t ff_h264_mps_state[64];
53 extern const uint8_t ff_h264_lps_state[64];
54 extern const uint8_t ff_h264_norm_shift[256];
55
56
57 void ff_init_cabac_encoder(CABACContext *c, uint8_t *buf, int buf_size);
58 void ff_init_cabac_decoder(CABACContext *c, const uint8_t *buf, int buf_size);
59 void ff_init_cabac_states(CABACContext *c, uint8_t const (*lps_range)[4],
60                           uint8_t const *mps_state, uint8_t const *lps_state, int state_count);
61
62
63 static inline void put_cabac_bit(CABACContext *c, int b){
64     put_bits(&c->pb, 1, b);
65     for(;c->outstanding_count; c->outstanding_count--){
66         put_bits(&c->pb, 1, 1-b);
67     }
68 }
69
70 static inline void renorm_cabac_encoder(CABACContext *c){
71     while(c->range < 0x100){
72         //FIXME optimize
73         if(c->low<0x100){
74             put_cabac_bit(c, 0);
75         }else if(c->low<0x200){
76             c->outstanding_count++;
77             c->low -= 0x100;
78         }else{
79             put_cabac_bit(c, 1);
80             c->low -= 0x200;
81         }
82
83         c->range+= c->range;
84         c->low += c->low;
85     }
86 }
87
88 static void put_cabac(CABACContext *c, uint8_t * const state, int bit){
89     int RangeLPS= c->lps_range[*state][c->range>>6];
90
91     if(bit == ((*state)&1)){
92         c->range -= RangeLPS;
93         *state= c->mps_state[*state];
94     }else{
95         c->low += c->range - RangeLPS;
96         c->range = RangeLPS;
97         *state= c->lps_state[*state];
98     }
99
100     renorm_cabac_encoder(c);
101
102 #ifdef STRICT_LIMITS
103     c->symCount++;
104 #endif
105 }
106
107 static void put_cabac_static(CABACContext *c, int RangeLPS, int bit){
108     assert(c->range > RangeLPS);
109
110     if(!bit){
111         c->range -= RangeLPS;
112     }else{
113         c->low += c->range - RangeLPS;
114         c->range = RangeLPS;
115     }
116
117     renorm_cabac_encoder(c);
118
119 #ifdef STRICT_LIMITS
120     c->symCount++;
121 #endif
122 }
123
124 /**
125  * @param bit 0 -> write zero bit, !=0 write one bit
126  */
127 static void put_cabac_bypass(CABACContext *c, int bit){
128     c->low += c->low;
129
130     if(bit){
131         c->low += c->range;
132     }
133 //FIXME optimize
134     if(c->low<0x200){
135         put_cabac_bit(c, 0);
136     }else if(c->low<0x400){
137         c->outstanding_count++;
138         c->low -= 0x200;
139     }else{
140         put_cabac_bit(c, 1);
141         c->low -= 0x400;
142     }
143
144 #ifdef STRICT_LIMITS
145     c->symCount++;
146 #endif
147 }
148
149 /**
150  *
151  * @return the number of bytes written
152  */
153 static int put_cabac_terminate(CABACContext *c, int bit){
154     c->range -= 2;
155
156     if(!bit){
157         renorm_cabac_encoder(c);
158     }else{
159         c->low += c->range;
160         c->range= 2;
161
162         renorm_cabac_encoder(c);
163
164         assert(c->low <= 0x1FF);
165         put_cabac_bit(c, c->low>>9);
166         put_bits(&c->pb, 2, ((c->low>>7)&3)|1);
167
168         flush_put_bits(&c->pb); //FIXME FIXME FIXME XXX wrong
169     }
170
171 #ifdef STRICT_LIMITS
172     c->symCount++;
173 #endif
174
175     return (put_bits_count(&c->pb)+7)>>3;
176 }
177
178 /**
179  * put (truncated) unary binarization.
180  */
181 static void put_cabac_u(CABACContext *c, uint8_t * state, int v, int max, int max_index, int truncated){
182     int i;
183
184     assert(v <= max);
185
186 #if 1
187     for(i=0; i<v; i++){
188         put_cabac(c, state, 1);
189         if(i < max_index) state++;
190     }
191     if(truncated==0 || v<max)
192         put_cabac(c, state, 0);
193 #else
194     if(v <= max_index){
195         for(i=0; i<v; i++){
196             put_cabac(c, state+i, 1);
197         }
198         if(truncated==0 || v<max)
199             put_cabac(c, state+i, 0);
200     }else{
201         for(i=0; i<=max_index; i++){
202             put_cabac(c, state+i, 1);
203         }
204         for(; i<v; i++){
205             put_cabac(c, state+max_index, 1);
206         }
207         if(truncated==0 || v<max)
208             put_cabac(c, state+max_index, 0);
209     }
210 #endif
211 }
212
213 /**
214  * put unary exp golomb k-th order binarization.
215  */
216 static void put_cabac_ueg(CABACContext *c, uint8_t * state, int v, int max, int is_signed, int k, int max_index){
217     int i;
218
219     if(v==0)
220         put_cabac(c, state, 0);
221     else{
222         const int sign= v < 0;
223
224         if(is_signed) v= ABS(v);
225
226         if(v<max){
227             for(i=0; i<v; i++){
228                 put_cabac(c, state, 1);
229                 if(i < max_index) state++;
230             }
231
232             put_cabac(c, state, 0);
233         }else{
234             int m= 1<<k;
235
236             for(i=0; i<max; i++){
237                 put_cabac(c, state, 1);
238                 if(i < max_index) state++;
239             }
240
241             v -= max;
242             while(v >= m){ //FIXME optimize
243                 put_cabac_bypass(c, 1);
244                 v-= m;
245                 m+= m;
246             }
247             put_cabac_bypass(c, 0);
248             while(m>>=1){
249                 put_cabac_bypass(c, v&m);
250             }
251         }
252
253         if(is_signed)
254             put_cabac_bypass(c, sign);
255     }
256 }
257
258 static void refill(CABACContext *c){
259     if(c->bytestream <= c->bytestream_end)
260 #if CABAC_BITS == 16
261         c->low+= (c->bytestream[0]<<9) + (c->bytestream[1]<<1);
262 #else
263         c->low+= c->bytestream[0]<<1;
264 #endif
265     c->low -= CABAC_MASK;
266     c->bytestream+= CABAC_BITS/8;
267 }
268
269 #if 0 /* all use commented */
270 static void refill2(CABACContext *c){
271     int i, x;
272
273     x= c->low ^ (c->low-1);
274     i= 8 - ff_h264_norm_shift[x>>(CABAC_BITS+1)];
275
276     x= -CABAC_MASK;
277
278     if(c->bytestream < c->bytestream_end)
279 #if CABAC_BITS == 16
280         x+= (c->bytestream[0]<<9) + (c->bytestream[1]<<1);
281 #else
282         x+= c->bytestream[0]<<1;
283 #endif
284
285     c->low += x<<i;
286     c->bytestream+= CABAC_BITS/8;
287 }
288 #endif
289
290 static inline void renorm_cabac_decoder(CABACContext *c){
291     while(c->range < (0x200 << CABAC_BITS)){
292         c->range+= c->range;
293         c->low+= c->low;
294         if(!(c->low & CABAC_MASK))
295             refill(c);
296     }
297 }
298
299 static inline void renorm_cabac_decoder_once(CABACContext *c){
300 #ifdef ARCH_X86_DISABLED
301     int temp;
302 #if 0
303     //P3:683    athlon:475
304     asm(
305         "lea -0x2000000(%0), %2     \n\t"
306         "shr $31, %2                \n\t"  //FIXME 31->63 for x86-64
307         "shl %%cl, %0               \n\t"
308         "shl %%cl, %1               \n\t"
309         : "+r"(c->range), "+r"(c->low), "+c"(temp)
310     );
311 #elif 0
312     //P3:680    athlon:474
313     asm(
314         "cmp $0x2000000, %0         \n\t"
315         "setb %%cl                  \n\t"  //FIXME 31->63 for x86-64
316         "shl %%cl, %0               \n\t"
317         "shl %%cl, %1               \n\t"
318         : "+r"(c->range), "+r"(c->low), "+c"(temp)
319     );
320 #elif 1
321     int temp2;
322     //P3:665    athlon:517
323     asm(
324         "lea -0x2000000(%0), %%eax  \n\t"
325         "cdq                        \n\t"
326         "mov %0, %%eax              \n\t"
327         "and %%edx, %0              \n\t"
328         "and %1, %%edx              \n\t"
329         "add %%eax, %0              \n\t"
330         "add %%edx, %1              \n\t"
331         : "+r"(c->range), "+r"(c->low), "+a"(temp), "+d"(temp2)
332     );
333 #elif 0
334     int temp2;
335     //P3:673    athlon:509
336     asm(
337         "cmp $0x2000000, %0         \n\t"
338         "sbb %%edx, %%edx           \n\t"
339         "mov %0, %%eax              \n\t"
340         "and %%edx, %0              \n\t"
341         "and %1, %%edx              \n\t"
342         "add %%eax, %0              \n\t"
343         "add %%edx, %1              \n\t"
344         : "+r"(c->range), "+r"(c->low), "+a"(temp), "+d"(temp2)
345     );
346 #else
347     int temp2;
348     //P3:677    athlon:511
349     asm(
350         "cmp $0x2000000, %0         \n\t"
351         "lea (%0, %0), %%eax        \n\t"
352         "lea (%1, %1), %%edx        \n\t"
353         "cmovb %%eax, %0            \n\t"
354         "cmovb %%edx, %1            \n\t"
355         : "+r"(c->range), "+r"(c->low), "+a"(temp), "+d"(temp2)
356     );
357 #endif
358 #else
359     //P3:675    athlon:476
360     int shift= (uint32_t)(c->range - (0x200 << CABAC_BITS))>>31;
361     c->range<<= shift;
362     c->low  <<= shift;
363 #endif
364     if(!(c->low & CABAC_MASK))
365         refill(c);
366 }
367
368 static int get_cabac(CABACContext *c, uint8_t * const state){
369     //FIXME gcc generates duplicate load/stores for c->low and c->range
370 //START_TIMER
371     int s = *state;
372     int RangeLPS= c->lps_range[s][c->range>>(CABAC_BITS+7)]<<(CABAC_BITS+1);
373     int bit, lps_mask attribute_unused;
374
375     c->range -= RangeLPS;
376 #if 1
377     if(c->low < c->range){
378         bit= s&1;
379 #ifdef ARCH_X86
380     //P3:627
381 asm(
382         "addb $2, %b0       \n\t"
383         " js 1f             \n\t"
384         "movb %b0, %1       \n\t"
385         "1:                 \n\t"
386         : "+q"(s), "=m"(*state)
387 );
388 #else
389         *state= c->mps_state[s]; //P3:655
390 /*        if(s<126) //P3:657
391             *state= s+2;*/
392         s+=2; //P3:631
393         if(s<128)
394             *state= s;
395 #endif
396         renorm_cabac_decoder_once(c);
397     }else{
398 //        int shift= ff_h264_norm_shift[RangeLPS>>17];
399         bit= (s&1)^1;
400         c->low -= c->range;
401         *state= c->lps_state[s];
402         c->range = RangeLPS;
403         renorm_cabac_decoder(c);
404 /*        c->range = RangeLPS<<shift;
405         c->low <<= shift;
406         if(!(c->low & 0xFFFF)){
407             refill2(c);
408         }*/
409     }
410 #else
411     lps_mask= (c->range - c->low)>>31;
412
413     c->low -= c->range & lps_mask;
414     c->range += (RangeLPS - c->range) & lps_mask;
415
416     bit= (s^lps_mask)&1;
417     *state= c->mps_state[s - (128&lps_mask)];
418
419     lps_mask= ff_h264_norm_shift[c->range>>(CABAC_BITS+2)];
420     c->range<<= lps_mask;
421     c->low  <<= lps_mask;
422     if(!(c->low & CABAC_MASK))
423         refill2(c);
424 #endif
425 //STOP_TIMER("get_cabac")
426     return bit;
427 }
428
429 static int get_cabac_bypass(CABACContext *c){
430     c->low += c->low;
431
432     if(!(c->low & CABAC_MASK))
433         refill(c);
434
435     if(c->low < c->range){
436         return 0;
437     }else{
438         c->low -= c->range;
439         return 1;
440     }
441 }
442
443 /**
444  *
445  * @return the number of bytes read or 0 if no end
446  */
447 static int get_cabac_terminate(CABACContext *c){
448     c->range -= 4<<CABAC_BITS;
449     if(c->low < c->range){
450         renorm_cabac_decoder_once(c);
451         return 0;
452     }else{
453         return c->bytestream - c->bytestream_start;
454     }
455 }
456
457 /**
458  * get (truncated) unnary binarization.
459  */
460 static int get_cabac_u(CABACContext *c, uint8_t * state, int max, int max_index, int truncated){
461     int i;
462
463     for(i=0; i<max; i++){
464         if(get_cabac(c, state)==0)
465             return i;
466
467         if(i< max_index) state++;
468     }
469
470     return truncated ? max : -1;
471 }
472
473 /**
474  * get unary exp golomb k-th order binarization.
475  */
476 static int get_cabac_ueg(CABACContext *c, uint8_t * state, int max, int is_signed, int k, int max_index){
477     int i, v;
478     int m= 1<<k;
479
480     if(get_cabac(c, state)==0)
481         return 0;
482
483     if(0 < max_index) state++;
484
485     for(i=1; i<max; i++){
486         if(get_cabac(c, state)==0){
487             if(is_signed && get_cabac_bypass(c)){
488                 return -i;
489             }else
490                 return i;
491         }
492
493         if(i < max_index) state++;
494     }
495
496     while(get_cabac_bypass(c)){
497         i+= m;
498         m+= m;
499     }
500
501     v=0;
502     while(m>>=1){
503         v+= v + get_cabac_bypass(c);
504     }
505     i += v;
506
507     if(is_signed && get_cabac_bypass(c)){
508         return -i;
509     }else
510         return i;
511 }