Merge commit 'cab8c5f8e140c96ba3725ab709d823abfd1e31a5'
[ffmpeg.git] / libavcodec / cabac.c
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  * @file
24  * Context Adaptive Binary Arithmetic Coder.
25  */
26
27 #include <string.h>
28
29 #include "libavutil/common.h"
30 #include "get_bits.h"
31 #include "cabac.h"
32 #include "cabac_functions.h"
33
34 uint8_t ff_h264_cabac_tables[512 + 4*2*64 + 4*64 + 63] = {
35  9,8,7,7,6,6,6,6,5,5,5,5,5,5,5,5,
36  4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,
37  3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,
38  3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,
39  2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,
40  2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,
41  2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,
42  2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,
43  1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,
44  1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,
45  1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,
46  1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,
47  0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
48  0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
49  0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
50  0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
51  0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
52  0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
53  0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
54  0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
55 };
56
57 static const uint8_t lps_range[64][4]= {
58 {128,176,208,240}, {128,167,197,227}, {128,158,187,216}, {123,150,178,205},
59 {116,142,169,195}, {111,135,160,185}, {105,128,152,175}, {100,122,144,166},
60 { 95,116,137,158}, { 90,110,130,150}, { 85,104,123,142}, { 81, 99,117,135},
61 { 77, 94,111,128}, { 73, 89,105,122}, { 69, 85,100,116}, { 66, 80, 95,110},
62 { 62, 76, 90,104}, { 59, 72, 86, 99}, { 56, 69, 81, 94}, { 53, 65, 77, 89},
63 { 51, 62, 73, 85}, { 48, 59, 69, 80}, { 46, 56, 66, 76}, { 43, 53, 63, 72},
64 { 41, 50, 59, 69}, { 39, 48, 56, 65}, { 37, 45, 54, 62}, { 35, 43, 51, 59},
65 { 33, 41, 48, 56}, { 32, 39, 46, 53}, { 30, 37, 43, 50}, { 29, 35, 41, 48},
66 { 27, 33, 39, 45}, { 26, 31, 37, 43}, { 24, 30, 35, 41}, { 23, 28, 33, 39},
67 { 22, 27, 32, 37}, { 21, 26, 30, 35}, { 20, 24, 29, 33}, { 19, 23, 27, 31},
68 { 18, 22, 26, 30}, { 17, 21, 25, 28}, { 16, 20, 23, 27}, { 15, 19, 22, 25},
69 { 14, 18, 21, 24}, { 14, 17, 20, 23}, { 13, 16, 19, 22}, { 12, 15, 18, 21},
70 { 12, 14, 17, 20}, { 11, 14, 16, 19}, { 11, 13, 15, 18}, { 10, 12, 15, 17},
71 { 10, 12, 14, 16}, {  9, 11, 13, 15}, {  9, 11, 12, 14}, {  8, 10, 12, 14},
72 {  8,  9, 11, 13}, {  7,  9, 11, 12}, {  7,  9, 10, 12}, {  7,  8, 10, 11},
73 {  6,  8,  9, 11}, {  6,  7,  9, 10}, {  6,  7,  8,  9}, {  2,  2,  2,  2},
74 };
75
76 static uint8_t h264_lps_state[2*64];
77
78 static const uint8_t mps_state[64]= {
79   1, 2, 3, 4, 5, 6, 7, 8,
80   9,10,11,12,13,14,15,16,
81  17,18,19,20,21,22,23,24,
82  25,26,27,28,29,30,31,32,
83  33,34,35,36,37,38,39,40,
84  41,42,43,44,45,46,47,48,
85  49,50,51,52,53,54,55,56,
86  57,58,59,60,61,62,62,63,
87 };
88
89 static const uint8_t lps_state[64]= {
90   0, 0, 1, 2, 2, 4, 4, 5,
91   6, 7, 8, 9, 9,11,11,12,
92  13,13,15,15,16,16,18,18,
93  19,19,21,21,22,22,23,24,
94  24,25,26,26,27,27,28,29,
95  29,30,30,30,31,32,32,33,
96  33,33,34,34,35,35,35,36,
97  36,36,37,37,37,38,38,63,
98 };
99
100 static const uint8_t last_coeff_flag_offset_8x8[63] = {
101  0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
102  2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2,
103  3, 3, 3, 3, 3, 3, 3, 3, 4, 4, 4, 4, 4, 4, 4, 4,
104  5, 5, 5, 5, 6, 6, 6, 6, 7, 7, 7, 7, 8, 8, 8
105 };
106
107 /**
108  *
109  * @param buf_size size of buf in bits
110  */
111 void ff_init_cabac_encoder(CABACContext *c, uint8_t *buf, int buf_size){
112     init_put_bits(&c->pb, buf, buf_size);
113
114     c->low= 0;
115     c->range= 0x1FE;
116     c->outstanding_count= 0;
117     c->pb.bit_left++; //avoids firstBitFlag
118 }
119
120 /**
121  *
122  * @param buf_size size of buf in bits
123  */
124 void ff_init_cabac_decoder(CABACContext *c, const uint8_t *buf, int buf_size){
125     c->bytestream_start=
126     c->bytestream= buf;
127     c->bytestream_end= buf + buf_size;
128
129 #if CABAC_BITS == 16
130     c->low =  (*c->bytestream++)<<18;
131     c->low+=  (*c->bytestream++)<<10;
132 #else
133     c->low =  (*c->bytestream++)<<10;
134 #endif
135     c->low+= ((*c->bytestream++)<<2) + 2;
136     c->range= 0x1FE;
137 }
138
139 void ff_init_cabac_states(void)
140 {
141     int i, j;
142     static int initialized = 0;
143
144     if (initialized)
145         return;
146
147     for(i=0; i<64; i++){
148         for(j=0; j<4; j++){ //FIXME check if this is worth the 1 shift we save
149             ff_h264_lps_range[j*2*64+2*i+0]=
150             ff_h264_lps_range[j*2*64+2*i+1]= lps_range[i][j];
151         }
152         ff_h264_mlps_state[128 + 2 * i + 0] = 2 * mps_state[i] + 0;
153         ff_h264_mlps_state[128 + 2 * i + 1] = 2 * mps_state[i] + 1;
154
155         if( i ){
156             h264_lps_state[2*i+0]=
157             ff_h264_mlps_state[128-2*i-1]= 2*lps_state[i]+0;
158             h264_lps_state[2*i+1]=
159             ff_h264_mlps_state[128-2*i-2]= 2*lps_state[i]+1;
160         }else{
161             h264_lps_state[2*i+0]=
162             ff_h264_mlps_state[128-2*i-1]= 1;
163             h264_lps_state[2*i+1]=
164             ff_h264_mlps_state[128-2*i-2]= 0;
165         }
166     }
167     for(i=0; i< 63; i++){
168       ff_h264_last_coeff_flag_offset_8x8[i] = last_coeff_flag_offset_8x8[i];
169     }
170
171     initialized = 1;
172 }
173
174 #ifdef TEST
175 #define SIZE 10240
176
177 #include "libavutil/lfg.h"
178 #include "avcodec.h"
179
180 static inline void put_cabac_bit(CABACContext *c, int b){
181     put_bits(&c->pb, 1, b);
182     for(;c->outstanding_count; c->outstanding_count--){
183         put_bits(&c->pb, 1, 1-b);
184     }
185 }
186
187 static inline void renorm_cabac_encoder(CABACContext *c){
188     while(c->range < 0x100){
189         //FIXME optimize
190         if(c->low<0x100){
191             put_cabac_bit(c, 0);
192         }else if(c->low<0x200){
193             c->outstanding_count++;
194             c->low -= 0x100;
195         }else{
196             put_cabac_bit(c, 1);
197             c->low -= 0x200;
198         }
199
200         c->range+= c->range;
201         c->low += c->low;
202     }
203 }
204
205 static void put_cabac(CABACContext *c, uint8_t * const state, int bit){
206     int RangeLPS= ff_h264_lps_range[2*(c->range&0xC0) + *state];
207
208     if(bit == ((*state)&1)){
209         c->range -= RangeLPS;
210         *state    = ff_h264_mlps_state[128 + *state];
211     }else{
212         c->low += c->range - RangeLPS;
213         c->range = RangeLPS;
214         *state= h264_lps_state[*state];
215     }
216
217     renorm_cabac_encoder(c);
218 }
219
220 /**
221  * @param bit 0 -> write zero bit, !=0 write one bit
222  */
223 static void put_cabac_bypass(CABACContext *c, int bit){
224     c->low += c->low;
225
226     if(bit){
227         c->low += c->range;
228     }
229 //FIXME optimize
230     if(c->low<0x200){
231         put_cabac_bit(c, 0);
232     }else if(c->low<0x400){
233         c->outstanding_count++;
234         c->low -= 0x200;
235     }else{
236         put_cabac_bit(c, 1);
237         c->low -= 0x400;
238     }
239 }
240
241 /**
242  *
243  * @return the number of bytes written
244  */
245 static int put_cabac_terminate(CABACContext *c, int bit){
246     c->range -= 2;
247
248     if(!bit){
249         renorm_cabac_encoder(c);
250     }else{
251         c->low += c->range;
252         c->range= 2;
253
254         renorm_cabac_encoder(c);
255
256         av_assert0(c->low <= 0x1FF);
257         put_cabac_bit(c, c->low>>9);
258         put_bits(&c->pb, 2, ((c->low>>7)&3)|1);
259
260         flush_put_bits(&c->pb); //FIXME FIXME FIXME XXX wrong
261     }
262
263     return (put_bits_count(&c->pb)+7)>>3;
264 }
265
266 int main(void){
267     CABACContext c;
268     uint8_t b[9*SIZE];
269     uint8_t r[9*SIZE];
270     int i;
271     uint8_t state[10]= {0};
272     AVLFG prng;
273
274     av_lfg_init(&prng, 1);
275     ff_init_cabac_encoder(&c, b, SIZE);
276     ff_init_cabac_states();
277
278     for(i=0; i<SIZE; i++){
279         if(2*i<SIZE) r[i] = av_lfg_get(&prng) % 7;
280         else         r[i] = (i>>8)&1;
281     }
282
283     for(i=0; i<SIZE; i++){
284 START_TIMER
285         put_cabac_bypass(&c, r[i]&1);
286 STOP_TIMER("put_cabac_bypass")
287     }
288
289     for(i=0; i<SIZE; i++){
290 START_TIMER
291         put_cabac(&c, state, r[i]&1);
292 STOP_TIMER("put_cabac")
293     }
294
295     put_cabac_terminate(&c, 1);
296
297     ff_init_cabac_decoder(&c, b, SIZE);
298
299     memset(state, 0, sizeof(state));
300
301     for(i=0; i<SIZE; i++){
302 START_TIMER
303         if( (r[i]&1) != get_cabac_bypass(&c) )
304             av_log(NULL, AV_LOG_ERROR, "CABAC bypass failure at %d\n", i);
305 STOP_TIMER("get_cabac_bypass")
306     }
307
308     for(i=0; i<SIZE; i++){
309 START_TIMER
310         if( (r[i]&1) != get_cabac(&c, state) )
311             av_log(NULL, AV_LOG_ERROR, "CABAC failure at %d\n", i);
312 STOP_TIMER("get_cabac")
313     }
314     if(!get_cabac_terminate(&c))
315         av_log(NULL, AV_LOG_ERROR, "where's the Terminator?\n");
316
317     return 0;
318 }
319
320 #endif /* TEST */