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