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