moving another bit&1 out, this is as fast as with it in there, but it makes more...
[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 #define BRANCHLESS_CABAD 1
35
36 typedef struct CABACContext{
37     int low;
38     int range;
39     int outstanding_count;
40 #ifdef STRICT_LIMITS
41     int symCount;
42 #endif
43     uint8_t lps_range[2*65][4];   ///< rangeTabLPS
44     uint8_t lps_state[2*64];      ///< transIdxLPS
45     uint8_t mps_state[2*64];      ///< transIdxMPS
46     const uint8_t *bytestream_start;
47     const uint8_t *bytestream;
48     const uint8_t *bytestream_end;
49     PutBitContext pb;
50 }CABACContext;
51
52 extern const uint8_t ff_h264_lps_range[64][4];
53 extern const uint8_t ff_h264_mps_state[64];
54 extern const uint8_t ff_h264_lps_state[64];
55 extern const uint8_t ff_h264_norm_shift[128];
56
57
58 void ff_init_cabac_encoder(CABACContext *c, uint8_t *buf, int buf_size);
59 void ff_init_cabac_decoder(CABACContext *c, const uint8_t *buf, int buf_size);
60 void ff_init_cabac_states(CABACContext *c, uint8_t const (*lps_range)[4],
61                           uint8_t const *mps_state, uint8_t const *lps_state, int state_count);
62
63
64 static inline void put_cabac_bit(CABACContext *c, int b){
65     put_bits(&c->pb, 1, b);
66     for(;c->outstanding_count; c->outstanding_count--){
67         put_bits(&c->pb, 1, 1-b);
68     }
69 }
70
71 static inline void renorm_cabac_encoder(CABACContext *c){
72     while(c->range < 0x100){
73         //FIXME optimize
74         if(c->low<0x100){
75             put_cabac_bit(c, 0);
76         }else if(c->low<0x200){
77             c->outstanding_count++;
78             c->low -= 0x100;
79         }else{
80             put_cabac_bit(c, 1);
81             c->low -= 0x200;
82         }
83
84         c->range+= c->range;
85         c->low += c->low;
86     }
87 }
88
89 static void put_cabac(CABACContext *c, uint8_t * const state, int bit){
90     int RangeLPS= c->lps_range[*state][c->range>>6];
91
92     if(bit == ((*state)&1)){
93         c->range -= RangeLPS;
94         *state= c->mps_state[*state];
95     }else{
96         c->low += c->range - RangeLPS;
97         c->range = RangeLPS;
98         *state= c->lps_state[*state];
99     }
100
101     renorm_cabac_encoder(c);
102
103 #ifdef STRICT_LIMITS
104     c->symCount++;
105 #endif
106 }
107
108 static void put_cabac_static(CABACContext *c, int RangeLPS, int bit){
109     assert(c->range > RangeLPS);
110
111     if(!bit){
112         c->range -= RangeLPS;
113     }else{
114         c->low += c->range - RangeLPS;
115         c->range = RangeLPS;
116     }
117
118     renorm_cabac_encoder(c);
119
120 #ifdef STRICT_LIMITS
121     c->symCount++;
122 #endif
123 }
124
125 /**
126  * @param bit 0 -> write zero bit, !=0 write one bit
127  */
128 static void put_cabac_bypass(CABACContext *c, int bit){
129     c->low += c->low;
130
131     if(bit){
132         c->low += c->range;
133     }
134 //FIXME optimize
135     if(c->low<0x200){
136         put_cabac_bit(c, 0);
137     }else if(c->low<0x400){
138         c->outstanding_count++;
139         c->low -= 0x200;
140     }else{
141         put_cabac_bit(c, 1);
142         c->low -= 0x400;
143     }
144
145 #ifdef STRICT_LIMITS
146     c->symCount++;
147 #endif
148 }
149
150 /**
151  *
152  * @return the number of bytes written
153  */
154 static int put_cabac_terminate(CABACContext *c, int bit){
155     c->range -= 2;
156
157     if(!bit){
158         renorm_cabac_encoder(c);
159     }else{
160         c->low += c->range;
161         c->range= 2;
162
163         renorm_cabac_encoder(c);
164
165         assert(c->low <= 0x1FF);
166         put_cabac_bit(c, c->low>>9);
167         put_bits(&c->pb, 2, ((c->low>>7)&3)|1);
168
169         flush_put_bits(&c->pb); //FIXME FIXME FIXME XXX wrong
170     }
171
172 #ifdef STRICT_LIMITS
173     c->symCount++;
174 #endif
175
176     return (put_bits_count(&c->pb)+7)>>3;
177 }
178
179 /**
180  * put (truncated) unary binarization.
181  */
182 static void put_cabac_u(CABACContext *c, uint8_t * state, int v, int max, int max_index, int truncated){
183     int i;
184
185     assert(v <= max);
186
187 #if 1
188     for(i=0; i<v; i++){
189         put_cabac(c, state, 1);
190         if(i < max_index) state++;
191     }
192     if(truncated==0 || v<max)
193         put_cabac(c, state, 0);
194 #else
195     if(v <= max_index){
196         for(i=0; i<v; i++){
197             put_cabac(c, state+i, 1);
198         }
199         if(truncated==0 || v<max)
200             put_cabac(c, state+i, 0);
201     }else{
202         for(i=0; i<=max_index; i++){
203             put_cabac(c, state+i, 1);
204         }
205         for(; i<v; i++){
206             put_cabac(c, state+max_index, 1);
207         }
208         if(truncated==0 || v<max)
209             put_cabac(c, state+max_index, 0);
210     }
211 #endif
212 }
213
214 /**
215  * put unary exp golomb k-th order binarization.
216  */
217 static void put_cabac_ueg(CABACContext *c, uint8_t * state, int v, int max, int is_signed, int k, int max_index){
218     int i;
219
220     if(v==0)
221         put_cabac(c, state, 0);
222     else{
223         const int sign= v < 0;
224
225         if(is_signed) v= ABS(v);
226
227         if(v<max){
228             for(i=0; i<v; i++){
229                 put_cabac(c, state, 1);
230                 if(i < max_index) state++;
231             }
232
233             put_cabac(c, state, 0);
234         }else{
235             int m= 1<<k;
236
237             for(i=0; i<max; i++){
238                 put_cabac(c, state, 1);
239                 if(i < max_index) state++;
240             }
241
242             v -= max;
243             while(v >= m){ //FIXME optimize
244                 put_cabac_bypass(c, 1);
245                 v-= m;
246                 m+= m;
247             }
248             put_cabac_bypass(c, 0);
249             while(m>>=1){
250                 put_cabac_bypass(c, v&m);
251             }
252         }
253
254         if(is_signed)
255             put_cabac_bypass(c, sign);
256     }
257 }
258
259 static void refill(CABACContext *c){
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 static void refill2(CABACContext *c){
270     int i, x;
271
272     x= c->low ^ (c->low-1);
273     i= 7 - ff_h264_norm_shift[x>>(CABAC_BITS+1)];
274
275     x= -CABAC_MASK;
276
277 #if CABAC_BITS == 16
278         x+= (c->bytestream[0]<<9) + (c->bytestream[1]<<1);
279 #else
280         x+= c->bytestream[0]<<1;
281 #endif
282
283     c->low += x<<i;
284     c->bytestream+= CABAC_BITS/8;
285 }
286
287 static inline void renorm_cabac_decoder(CABACContext *c){
288     while(c->range < (0x200 << CABAC_BITS)){
289         c->range+= c->range;
290         c->low+= c->low;
291         if(!(c->low & CABAC_MASK))
292             refill(c);
293     }
294 }
295
296 static inline void renorm_cabac_decoder_once(CABACContext *c){
297 #ifdef ARCH_X86_DISABLED
298     int temp;
299 #if 0
300     //P3:683    athlon:475
301     asm(
302         "lea -0x2000000(%0), %2     \n\t"
303         "shr $31, %2                \n\t"  //FIXME 31->63 for x86-64
304         "shl %%cl, %0               \n\t"
305         "shl %%cl, %1               \n\t"
306         : "+r"(c->range), "+r"(c->low), "+c"(temp)
307     );
308 #elif 0
309     //P3:680    athlon:474
310     asm(
311         "cmp $0x2000000, %0         \n\t"
312         "setb %%cl                  \n\t"  //FIXME 31->63 for x86-64
313         "shl %%cl, %0               \n\t"
314         "shl %%cl, %1               \n\t"
315         : "+r"(c->range), "+r"(c->low), "+c"(temp)
316     );
317 #elif 1
318     int temp2;
319     //P3:665    athlon:517
320     asm(
321         "lea -0x2000000(%0), %%eax  \n\t"
322         "cdq                        \n\t"
323         "mov %0, %%eax              \n\t"
324         "and %%edx, %0              \n\t"
325         "and %1, %%edx              \n\t"
326         "add %%eax, %0              \n\t"
327         "add %%edx, %1              \n\t"
328         : "+r"(c->range), "+r"(c->low), "+a"(temp), "+d"(temp2)
329     );
330 #elif 0
331     int temp2;
332     //P3:673    athlon:509
333     asm(
334         "cmp $0x2000000, %0         \n\t"
335         "sbb %%edx, %%edx           \n\t"
336         "mov %0, %%eax              \n\t"
337         "and %%edx, %0              \n\t"
338         "and %1, %%edx              \n\t"
339         "add %%eax, %0              \n\t"
340         "add %%edx, %1              \n\t"
341         : "+r"(c->range), "+r"(c->low), "+a"(temp), "+d"(temp2)
342     );
343 #else
344     int temp2;
345     //P3:677    athlon:511
346     asm(
347         "cmp $0x2000000, %0         \n\t"
348         "lea (%0, %0), %%eax        \n\t"
349         "lea (%1, %1), %%edx        \n\t"
350         "cmovb %%eax, %0            \n\t"
351         "cmovb %%edx, %1            \n\t"
352         : "+r"(c->range), "+r"(c->low), "+a"(temp), "+d"(temp2)
353     );
354 #endif
355 #else
356     //P3:675    athlon:476
357     int shift= (uint32_t)(c->range - (0x200 << CABAC_BITS))>>31;
358     c->range<<= shift;
359     c->low  <<= shift;
360 #endif
361     if(!(c->low & CABAC_MASK))
362         refill(c);
363 }
364
365 static int get_cabac(CABACContext *c, uint8_t * const state){
366     //FIXME gcc generates duplicate load/stores for c->low and c->range
367 #ifdef ARCH_X86
368     int bit;
369
370 #define LOW          "0"
371 #define RANGE        "4"
372 #define LPS_RANGE   "12"
373 #define LPS_STATE   "12+2*65*4"
374 #define MPS_STATE   "12+2*65*4+2*64"
375 #define BYTESTART   "12+2*65*4+4*64"
376 #define BYTE        "16+2*65*4+4*64"
377 #define BYTEEND     "20+2*65*4+4*64"
378 #ifndef BRANCHLESS_CABAD
379     asm volatile(
380         "movzbl (%1), %%eax                     \n\t"
381         "movl "RANGE    "(%2), %%ebx            \n\t"
382         "movl "RANGE    "(%2), %%edx            \n\t"
383         "shrl $23, %%ebx                        \n\t"
384         "leal "LPS_RANGE"(%2, %%eax, 4), %%esi  \n\t"
385         "movzbl (%%ebx, %%esi), %%esi           \n\t"
386         "shll $17, %%esi                        \n\t"
387         "movl "LOW      "(%2), %%ebx            \n\t"
388 //eax:state ebx:low, edx:range, esi:RangeLPS
389         "subl %%esi, %%edx                      \n\t"
390         "cmpl %%edx, %%ebx                      \n\t"
391         " ja 1f                                 \n\t"
392         "cmp $0x2000000, %%edx                  \n\t" //FIXME avoidable
393         "setb %%cl                              \n\t"
394         "shl %%cl, %%edx                        \n\t"
395         "shl %%cl, %%ebx                        \n\t"
396         "movzbl "MPS_STATE"(%2, %%eax), %%ecx   \n\t"
397         "movb %%cl, (%1)                        \n\t"
398 //eax:state ebx:low, edx:range, esi:RangeLPS
399         "test %%bx, %%bx                        \n\t"
400         " jnz 2f                                \n\t"
401         "movl "BYTE     "(%2), %%esi            \n\t"
402         "subl $0xFFFF, %%ebx                    \n\t"
403         "movzwl (%%esi), %%ecx                  \n\t"
404         "bswap %%ecx                            \n\t"
405         "shrl $15, %%ecx                        \n\t"
406         "addl $2, %%esi                         \n\t"
407         "addl %%ecx, %%ebx                      \n\t"
408         "movl %%esi, "BYTE    "(%2)             \n\t"
409         "jmp 2f                                 \n\t"
410         "1:                                     \n\t"
411 //eax:state ebx:low, edx:range, esi:RangeLPS
412         "subl %%edx, %%ebx                      \n\t"
413         "movl %%esi, %%edx                      \n\t"
414         "shr $19, %%esi                         \n\t"
415         "movzbl " MANGLE(ff_h264_norm_shift) "(%%esi), %%ecx   \n\t"
416         "shll %%cl, %%ebx                       \n\t"
417         "shll %%cl, %%edx                       \n\t"
418         "movzbl "LPS_STATE"(%2, %%eax), %%ecx   \n\t"
419         "movb %%cl, (%1)                        \n\t"
420         "addl $1, %%eax                         \n\t"
421         "test %%bx, %%bx                        \n\t"
422         " jnz 2f                                \n\t"
423
424         "movl "BYTE     "(%2), %%ecx            \n\t"
425         "movzwl (%%ecx), %%esi                  \n\t"
426         "bswap %%esi                            \n\t"
427         "shrl $15, %%esi                        \n\t"
428         "subl $0xFFFF, %%esi                    \n\t"
429         "addl $2, %%ecx                         \n\t"
430         "movl %%ecx, "BYTE    "(%2)             \n\t"
431
432         "leal -1(%%ebx), %%ecx                  \n\t"
433         "xorl %%ebx, %%ecx                      \n\t"
434         "shrl $17, %%ecx                        \n\t"
435         "movzbl " MANGLE(ff_h264_norm_shift) "(%%ecx), %%ecx   \n\t"
436         "neg %%cl                               \n\t"
437         "add $7, %%cl                           \n\t"
438
439         "shll %%cl , %%esi                      \n\t"
440         "addl %%esi, %%ebx                      \n\t"
441         "2:                                     \n\t"
442         "movl %%edx, "RANGE    "(%2)            \n\t"
443         "movl %%ebx, "LOW      "(%2)            \n\t"
444         :"=&a"(bit) //FIXME this is fragile gcc either runs out of registers or misscompiles it (for example if "+a"(bit) or "+m"(*state) is used
445         :"r"(state), "r"(c)
446         : "%ecx", "%ebx", "%edx", "%esi"
447     );
448     bit&=1;
449 #else
450     asm volatile(
451         "movzbl (%1), %%eax                     \n\t"
452         "movl "RANGE    "(%2), %%ebx            \n\t"
453         "movl "RANGE    "(%2), %%edx            \n\t"
454         "shrl $23, %%ebx                        \n\t"
455         "leal "LPS_RANGE"(%2, %%eax, 4), %%esi  \n\t"
456         "movzbl (%%ebx, %%esi), %%esi           \n\t"
457         "shll $17, %%esi                        \n\t"
458         "movl "LOW      "(%2), %%ebx            \n\t"
459 //eax:state ebx:low, edx:range, esi:RangeLPS
460         "subl %%esi, %%edx                      \n\t"
461 #ifdef CMOV_IS_FAST //FIXME actually define this somewhere
462         "cmpl %%ebx, %%edx                      \n\t"
463         "cmova %%edx, %%esi                     \n\t"
464         "sbbl %%ecx, %%ecx                      \n\t"
465         "andl %%ecx, %%edx                      \n\t"
466         "subl %%edx, %%ebx                      \n\t"
467         "xorl %%ecx, %%eax                      \n\t"
468 #else
469         "movl %%edx, %%ecx                      \n\t"
470         "subl %%ebx, %%edx                      \n\t"
471         "sarl $31, %%edx                        \n\t" //lps_mask
472         "subl %%ecx, %%esi                      \n\t" //RangeLPS - range
473         "andl %%edx, %%esi                      \n\t" //(RangeLPS - range)&lps_mask
474         "addl %%ecx, %%esi                      \n\t" //new range
475         "andl %%edx, %%ecx                      \n\t"
476         "subl %%ecx, %%ebx                      \n\t"
477         "xorl %%edx, %%eax                      \n\t"
478 #endif
479
480 //eax:state ebx:low edx:mask esi:range
481         "movzbl "MPS_STATE"(%2, %%eax), %%ecx   \n\t"
482         "movb %%cl, (%1)                        \n\t"
483
484         "movl %%esi, %%edx                      \n\t"
485 //eax:bit ebx:low edx:range esi:range
486
487         "shr $19, %%esi                         \n\t"
488         "movzbl " MANGLE(ff_h264_norm_shift) "(%%esi), %%ecx   \n\t"
489         "shll %%cl, %%ebx                       \n\t"
490         "shll %%cl, %%edx                       \n\t"
491         "test %%bx, %%bx                        \n\t"
492         " jnz 1f                                \n\t"
493
494         "movl "BYTE     "(%2), %%ecx            \n\t"
495         "movzwl (%%ecx), %%esi                  \n\t"
496         "bswap %%esi                            \n\t"
497         "shrl $15, %%esi                        \n\t"
498         "subl $0xFFFF, %%esi                    \n\t"
499         "addl $2, %%ecx                         \n\t"
500         "movl %%ecx, "BYTE    "(%2)             \n\t"
501
502         "leal -1(%%ebx), %%ecx                  \n\t"
503         "xorl %%ebx, %%ecx                      \n\t"
504         "shrl $17, %%ecx                        \n\t"
505         "movzbl " MANGLE(ff_h264_norm_shift) "(%%ecx), %%ecx   \n\t"
506         "neg %%cl                               \n\t"
507         "add $7, %%cl                           \n\t"
508
509         "shll %%cl , %%esi                      \n\t"
510         "addl %%esi, %%ebx                      \n\t"
511         "1:                                     \n\t"
512         "movl %%edx, "RANGE    "(%2)            \n\t"
513         "movl %%ebx, "LOW      "(%2)            \n\t"
514         :"=&a"(bit)
515         :"r"(state), "r"(c)
516         : "%ecx", "%ebx", "%edx", "%esi"
517     );
518     bit&=1;
519 #endif
520 #else
521     int s = *state;
522     int RangeLPS= c->lps_range[s][c->range>>(CABAC_BITS+7)]<<(CABAC_BITS+1);
523     int bit, lps_mask attribute_unused;
524
525     c->range -= RangeLPS;
526 #ifndef BRANCHLESS_CABAD
527     if(c->low < c->range){
528         bit= s&1;
529         *state= c->mps_state[s];
530         renorm_cabac_decoder_once(c);
531     }else{
532         bit= ff_h264_norm_shift[RangeLPS>>19];
533         c->low -= c->range;
534         *state= c->lps_state[s];
535         c->range = RangeLPS<<bit;
536         c->low <<= bit;
537         bit= (s&1)^1;
538
539         if(!(c->low & 0xFFFF)){
540             refill2(c);
541         }
542     }
543 #else
544     lps_mask= (c->range - c->low)>>31;
545
546     c->low -= c->range & lps_mask;
547     c->range += (RangeLPS - c->range) & lps_mask;
548
549     s^=lps_mask;
550     *state= c->mps_state[s];
551     bit= s&1;
552
553     lps_mask= ff_h264_norm_shift[c->range>>(CABAC_BITS+3)];
554     c->range<<= lps_mask;
555     c->low  <<= lps_mask;
556     if(!(c->low & CABAC_MASK))
557         refill2(c);
558 #endif
559 #endif
560     return bit;
561 }
562
563 static int get_cabac_bypass(CABACContext *c){
564     c->low += c->low;
565
566     if(!(c->low & CABAC_MASK))
567         refill(c);
568
569     if(c->low < c->range){
570         return 0;
571     }else{
572         c->low -= c->range;
573         return 1;
574     }
575 }
576
577 /**
578  *
579  * @return the number of bytes read or 0 if no end
580  */
581 static int get_cabac_terminate(CABACContext *c){
582     c->range -= 4<<CABAC_BITS;
583     if(c->low < c->range){
584         renorm_cabac_decoder_once(c);
585         return 0;
586     }else{
587         return c->bytestream - c->bytestream_start;
588     }
589 }
590
591 /**
592  * get (truncated) unnary binarization.
593  */
594 static int get_cabac_u(CABACContext *c, uint8_t * state, int max, int max_index, int truncated){
595     int i;
596
597     for(i=0; i<max; i++){
598         if(get_cabac(c, state)==0)
599             return i;
600
601         if(i< max_index) state++;
602     }
603
604     return truncated ? max : -1;
605 }
606
607 /**
608  * get unary exp golomb k-th order binarization.
609  */
610 static int get_cabac_ueg(CABACContext *c, uint8_t * state, int max, int is_signed, int k, int max_index){
611     int i, v;
612     int m= 1<<k;
613
614     if(get_cabac(c, state)==0)
615         return 0;
616
617     if(0 < max_index) state++;
618
619     for(i=1; i<max; i++){
620         if(get_cabac(c, state)==0){
621             if(is_signed && get_cabac_bypass(c)){
622                 return -i;
623             }else
624                 return i;
625         }
626
627         if(i < max_index) state++;
628     }
629
630     while(get_cabac_bypass(c)){
631         i+= m;
632         m+= m;
633     }
634
635     v=0;
636     while(m>>=1){
637         v+= v + get_cabac_bypass(c);
638     }
639     i += v;
640
641     if(is_signed && get_cabac_bypass(c)){
642         return -i;
643     }else
644         return i;
645 }