2 * H.26L/H.264/AVC/JVT/14496-10/... encoder/decoder
3 * Copyright (c) 2003 Michael Niedermayer <michaelni@gmx.at>
5 * This file is part of FFmpeg.
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.
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.
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
25 * Context Adaptive Binary Arithmetic Coder.
33 #define CABAC_MASK ((1<<CABAC_BITS)-1)
34 #define BRANCHLESS_CABAC_DECODER 1
35 #define CMOV_IS_FAST 1
37 typedef struct CABACContext{
40 int outstanding_count;
44 const uint8_t *bytestream_start;
45 const uint8_t *bytestream;
46 const uint8_t *bytestream_end;
50 extern uint8_t ff_h264_mlps_state[4*64];
51 extern uint8_t ff_h264_lps_range[2*65][4]; ///< rangeTabLPS
52 extern uint8_t ff_h264_mps_state[2*64]; ///< transIdxMPS
53 extern uint8_t ff_h264_lps_state[2*64]; ///< transIdxLPS
54 extern const uint8_t ff_h264_norm_shift[128];
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);
62 static inline void put_cabac_bit(CABACContext *c, int b){
63 put_bits(&c->pb, 1, b);
64 for(;c->outstanding_count; c->outstanding_count--){
65 put_bits(&c->pb, 1, 1-b);
69 static inline void renorm_cabac_encoder(CABACContext *c){
70 while(c->range < 0x100){
74 }else if(c->low<0x200){
75 c->outstanding_count++;
87 static void put_cabac(CABACContext *c, uint8_t * const state, int bit){
88 int RangeLPS= ff_h264_lps_range[*state][c->range>>6];
90 if(bit == ((*state)&1)){
92 *state= ff_h264_mps_state[*state];
94 c->low += c->range - RangeLPS;
96 *state= ff_h264_lps_state[*state];
99 renorm_cabac_encoder(c);
106 static void put_cabac_static(CABACContext *c, int RangeLPS, int bit){
107 assert(c->range > RangeLPS);
110 c->range -= RangeLPS;
112 c->low += c->range - RangeLPS;
116 renorm_cabac_encoder(c);
124 * @param bit 0 -> write zero bit, !=0 write one bit
126 static void put_cabac_bypass(CABACContext *c, int bit){
135 }else if(c->low<0x400){
136 c->outstanding_count++;
150 * @return the number of bytes written
152 static int put_cabac_terminate(CABACContext *c, int bit){
156 renorm_cabac_encoder(c);
161 renorm_cabac_encoder(c);
163 assert(c->low <= 0x1FF);
164 put_cabac_bit(c, c->low>>9);
165 put_bits(&c->pb, 2, ((c->low>>7)&3)|1);
167 flush_put_bits(&c->pb); //FIXME FIXME FIXME XXX wrong
174 return (put_bits_count(&c->pb)+7)>>3;
178 * put (truncated) unary binarization.
180 static void put_cabac_u(CABACContext *c, uint8_t * state, int v, int max, int max_index, int truncated){
187 put_cabac(c, state, 1);
188 if(i < max_index) state++;
190 if(truncated==0 || v<max)
191 put_cabac(c, state, 0);
195 put_cabac(c, state+i, 1);
197 if(truncated==0 || v<max)
198 put_cabac(c, state+i, 0);
200 for(i=0; i<=max_index; i++){
201 put_cabac(c, state+i, 1);
204 put_cabac(c, state+max_index, 1);
206 if(truncated==0 || v<max)
207 put_cabac(c, state+max_index, 0);
213 * put unary exp golomb k-th order binarization.
215 static void put_cabac_ueg(CABACContext *c, uint8_t * state, int v, int max, int is_signed, int k, int max_index){
219 put_cabac(c, state, 0);
221 const int sign= v < 0;
223 if(is_signed) v= FFABS(v);
227 put_cabac(c, state, 1);
228 if(i < max_index) state++;
231 put_cabac(c, state, 0);
235 for(i=0; i<max; i++){
236 put_cabac(c, state, 1);
237 if(i < max_index) state++;
241 while(v >= m){ //FIXME optimize
242 put_cabac_bypass(c, 1);
246 put_cabac_bypass(c, 0);
248 put_cabac_bypass(c, v&m);
253 put_cabac_bypass(c, sign);
257 static void refill(CABACContext *c){
259 c->low+= (c->bytestream[0]<<9) + (c->bytestream[1]<<1);
261 c->low+= c->bytestream[0]<<1;
263 c->low -= CABAC_MASK;
264 c->bytestream+= CABAC_BITS/8;
267 static void refill2(CABACContext *c){
270 x= c->low ^ (c->low-1);
271 i= 7 - ff_h264_norm_shift[x>>(CABAC_BITS+1)];
276 x+= (c->bytestream[0]<<9) + (c->bytestream[1]<<1);
278 x+= c->bytestream[0]<<1;
282 c->bytestream+= CABAC_BITS/8;
285 static inline void renorm_cabac_decoder(CABACContext *c){
286 while(c->range < (0x200 << CABAC_BITS)){
289 if(!(c->low & CABAC_MASK))
294 static inline void renorm_cabac_decoder_once(CABACContext *c){
295 #ifdef ARCH_X86_DISABLED
300 "lea -0x2000000(%0), %2 \n\t"
301 "shr $31, %2 \n\t" //FIXME 31->63 for x86-64
304 : "+r"(c->range), "+r"(c->low), "+c"(temp)
309 "cmp $0x2000000, %0 \n\t"
310 "setb %%cl \n\t" //FIXME 31->63 for x86-64
313 : "+r"(c->range), "+r"(c->low), "+c"(temp)
319 "lea -0x2000000(%0), %%eax \n\t"
326 : "+r"(c->range), "+r"(c->low), "+a"(temp), "+d"(temp2)
332 "cmp $0x2000000, %0 \n\t"
333 "sbb %%edx, %%edx \n\t"
339 : "+r"(c->range), "+r"(c->low), "+a"(temp), "+d"(temp2)
345 "cmp $0x2000000, %0 \n\t"
346 "lea (%0, %0), %%eax \n\t"
347 "lea (%1, %1), %%edx \n\t"
348 "cmovb %%eax, %0 \n\t"
349 "cmovb %%edx, %1 \n\t"
350 : "+r"(c->range), "+r"(c->low), "+a"(temp), "+d"(temp2)
355 int shift= (uint32_t)(c->range - (0x200 << CABAC_BITS))>>31;
359 if(!(c->low & CABAC_MASK))
363 static int always_inline get_cabac_inline(CABACContext *c, uint8_t * const state){
364 //FIXME gcc generates duplicate load/stores for c->low and c->range
370 #define BYTESTART "12"
373 #ifndef BRANCHLESS_CABAC_DECODER
375 "movzbl (%1), %%eax \n\t"
376 "movl "RANGE "(%2), %%ebx \n\t"
377 "movl "RANGE "(%2), %%edx \n\t"
378 "shrl $23, %%ebx \n\t"
379 "movzbl "MANGLE(ff_h264_lps_range)"(%%ebx, %%eax, 4), %%esi\n\t"
380 "shll $17, %%esi \n\t"
381 "movl "LOW "(%2), %%ebx \n\t"
382 //eax:state ebx:low, edx:range, esi:RangeLPS
383 "subl %%esi, %%edx \n\t"
384 "cmpl %%edx, %%ebx \n\t"
388 //athlon:4067 P3:4110
389 "lea -0x2000000(%%edx), %%ecx \n\t"
390 "shr $31, %%ecx \n\t"
391 "shl %%cl, %%edx \n\t"
392 "shl %%cl, %%ebx \n\t"
394 //athlon:4057 P3:4130
395 "cmp $0x2000000, %%edx \n\t" //FIXME avoidable
397 "shl %%cl, %%edx \n\t"
398 "shl %%cl, %%ebx \n\t"
400 "movzbl "MANGLE(ff_h264_mps_state)"(%%eax), %%ecx \n\t"
401 "movb %%cl, (%1) \n\t"
402 //eax:state ebx:low, edx:range, esi:RangeLPS
403 "test %%bx, %%bx \n\t"
405 "movl "BYTE "(%2), %%esi \n\t"
406 "subl $0xFFFF, %%ebx \n\t"
407 "movzwl (%%esi), %%ecx \n\t"
409 "shrl $15, %%ecx \n\t"
410 "addl $2, %%esi \n\t"
411 "addl %%ecx, %%ebx \n\t"
412 "movl %%esi, "BYTE "(%2) \n\t"
415 //eax:state ebx:low, edx:range, esi:RangeLPS
416 "subl %%edx, %%ebx \n\t"
417 "movl %%esi, %%edx \n\t"
418 "shr $19, %%esi \n\t"
419 "movzbl "MANGLE(ff_h264_lps_state)"(%%eax), %%ecx \n\t"
420 "movb %%cl, (%1) \n\t"
421 "movzbl " MANGLE(ff_h264_norm_shift) "(%%esi), %%ecx \n\t"
422 "shll %%cl, %%ebx \n\t"
423 "shll %%cl, %%edx \n\t"
424 "addl $1, %%eax \n\t"
425 "test %%bx, %%bx \n\t"
428 "movl "BYTE "(%2), %%ecx \n\t"
429 "movzwl (%%ecx), %%esi \n\t"
431 "shrl $15, %%esi \n\t"
432 "subl $0xFFFF, %%esi \n\t"
433 "addl $2, %%ecx \n\t"
434 "movl %%ecx, "BYTE "(%2) \n\t"
436 "leal -1(%%ebx), %%ecx \n\t"
437 "xorl %%ebx, %%ecx \n\t"
438 "shrl $17, %%ecx \n\t"
439 "movzbl " MANGLE(ff_h264_norm_shift) "(%%ecx), %%ecx \n\t"
443 "shll %%cl , %%esi \n\t"
444 "addl %%esi, %%ebx \n\t"
446 "movl %%edx, "RANGE "(%2) \n\t"
447 "movl %%ebx, "LOW "(%2) \n\t"
448 :"=&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
450 : "%ecx", "%ebx", "%edx", "%esi", "memory"
453 #else /* BRANCHLESS_CABAC_DECODER */
455 "movzbl (%1), %%eax \n\t"
456 "movl "RANGE "(%2), %%ebx \n\t"
457 "movl "RANGE "(%2), %%edx \n\t"
458 "shrl $23, %%ebx \n\t"
459 "movzbl "MANGLE(ff_h264_lps_range)"(%%ebx, %%eax, 4), %%esi\n\t"
460 "shll $17, %%esi \n\t"
461 "movl "LOW "(%2), %%ebx \n\t"
462 //eax:state ebx:low, edx:range, esi:RangeLPS
463 "subl %%esi, %%edx \n\t"
464 #ifdef CMOV_IS_FAST //FIXME actually define this somewhere
465 "cmpl %%ebx, %%edx \n\t"
466 "cmova %%edx, %%esi \n\t"
467 "sbbl %%ecx, %%ecx \n\t"
468 "andl %%ecx, %%edx \n\t"
469 "subl %%edx, %%ebx \n\t"
470 "xorl %%ecx, %%eax \n\t"
471 #else /* CMOV_IS_FAST */
472 "movl %%edx, %%ecx \n\t"
473 "subl %%ebx, %%edx \n\t"
474 "sarl $31, %%edx \n\t" //lps_mask
475 "subl %%ecx, %%esi \n\t" //RangeLPS - range
476 "andl %%edx, %%esi \n\t" //(RangeLPS - range)&lps_mask
477 "addl %%ecx, %%esi \n\t" //new range
478 "andl %%edx, %%ecx \n\t"
479 "subl %%ecx, %%ebx \n\t"
480 "xorl %%edx, %%eax \n\t"
481 #endif /* CMOV_IS_FAST */
483 //eax:state ebx:low edx:mask esi:range
484 "movzbl "MANGLE(ff_h264_mlps_state)"+128(%%eax), %%ecx \n\t"
485 "movb %%cl, (%1) \n\t"
487 "movl %%esi, %%edx \n\t"
488 //eax:bit ebx:low edx:range esi:range
490 "shr $19, %%esi \n\t"
491 "movzbl " MANGLE(ff_h264_norm_shift) "(%%esi), %%ecx \n\t"
492 "shll %%cl, %%edx \n\t"
493 "movl %%edx, "RANGE "(%2) \n\t"
494 "shll %%cl, %%ebx \n\t"
495 "movl %%ebx, "LOW "(%2) \n\t"
496 "test %%bx, %%bx \n\t"
499 "movl "BYTE "(%2), %%ecx \n\t"
500 "movzwl (%%ecx), %%esi \n\t"
502 "shrl $15, %%esi \n\t"
503 "subl $0xFFFF, %%esi \n\t"
504 "addl $2, %%ecx \n\t"
505 "movl %%ecx, "BYTE "(%2) \n\t"
507 "leal -1(%%ebx), %%ecx \n\t"
508 "xorl %%ebx, %%ecx \n\t"
509 "shrl $17, %%ecx \n\t"
510 "movzbl " MANGLE(ff_h264_norm_shift) "(%%ecx), %%ecx \n\t"
514 "shll %%cl , %%esi \n\t"
515 "addl %%esi, %%ebx \n\t"
516 "movl %%ebx, "LOW "(%2) \n\t"
520 : "%ecx", "%ebx", "%edx", "%esi", "memory"
523 #endif /* BRANCHLESS_CABAC_DECODER */
526 int RangeLPS= ff_h264_lps_range[s][c->range>>(CABAC_BITS+7)]<<(CABAC_BITS+1);
527 int bit, lps_mask attribute_unused;
529 c->range -= RangeLPS;
530 #ifndef BRANCHLESS_CABAC_DECODER
531 if(c->low < c->range){
533 *state= ff_h264_mps_state[s];
534 renorm_cabac_decoder_once(c);
536 bit= ff_h264_norm_shift[RangeLPS>>19];
538 *state= ff_h264_lps_state[s];
539 c->range = RangeLPS<<bit;
543 if(!(c->low & 0xFFFF)){
547 #else /* BRANCHLESS_CABAC_DECODER */
548 lps_mask= (c->range - c->low)>>31;
550 c->low -= c->range & lps_mask;
551 c->range += (RangeLPS - c->range) & lps_mask;
554 *state= (ff_h264_mlps_state+128)[s];
557 lps_mask= ff_h264_norm_shift[c->range>>(CABAC_BITS+3)];
558 c->range<<= lps_mask;
560 if(!(c->low & CABAC_MASK))
562 #endif /* BRANCHLESS_CABAC_DECODER */
563 #endif /* ARCH_X86 */
567 static int __attribute((noinline)) get_cabac_noinline(CABACContext *c, uint8_t * const state){
568 return get_cabac_inline(c,state);
571 static int get_cabac(CABACContext *c, uint8_t * const state){
572 return get_cabac_inline(c,state);
575 static int get_cabac_bypass(CABACContext *c){
578 if(!(c->low & CABAC_MASK))
581 if(c->low < c->range){
591 * @return the number of bytes read or 0 if no end
593 static int get_cabac_terminate(CABACContext *c){
594 c->range -= 4<<CABAC_BITS;
595 if(c->low < c->range){
596 renorm_cabac_decoder_once(c);
599 return c->bytestream - c->bytestream_start;
604 * get (truncated) unnary binarization.
606 static int get_cabac_u(CABACContext *c, uint8_t * state, int max, int max_index, int truncated){
609 for(i=0; i<max; i++){
610 if(get_cabac(c, state)==0)
613 if(i< max_index) state++;
616 return truncated ? max : -1;
620 * get unary exp golomb k-th order binarization.
622 static int get_cabac_ueg(CABACContext *c, uint8_t * state, int max, int is_signed, int k, int max_index){
626 if(get_cabac(c, state)==0)
629 if(0 < max_index) state++;
631 for(i=1; i<max; i++){
632 if(get_cabac(c, state)==0){
633 if(is_signed && get_cabac_bypass(c)){
639 if(i < max_index) state++;
642 while(get_cabac_bypass(c)){
649 v+= v + get_cabac_bypass(c);
653 if(is_signed && get_cabac_bypass(c)){