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