10l (segfault)
[ffmpeg.git] / libavcodec / ffv1.c
1 /*
2  * FFV1 codec for libavcodec
3  *
4  * Copyright (c) 2003 Michael Niedermayer <michaelni@gmx.at>
5  *
6  * This library is free software; you can redistribute it and/or
7  * modify it under the terms of the GNU Lesser General Public
8  * License as published by the Free Software Foundation; either
9  * version 2 of the License, or (at your option) any later version.
10  *
11  * This library is distributed in the hope that it will be useful,
12  * but WITHOUT ANY WARRANTY; without even the implied warranty of
13  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
14  * Lesser General Public License for more details.
15  *
16  * You should have received a copy of the GNU Lesser General Public
17  * License along with this library; if not, write to the Free Software
18  * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
19  *
20  */
21  
22 /**
23  * @file ffv1.c
24  * FF Video Codec 1 (an experimental lossless codec)
25  */
26
27 #include "common.h"
28 #include "avcodec.h"
29 #include "dsputil.h"
30 #include "cabac.h"
31 #include "golomb.h"
32
33 #define MAX_PLANES 4
34 #define CONTEXT_SIZE 32
35
36 static const int8_t quant3[256]={
37  0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
38  1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
39  1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
40  1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
41  1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
42  1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
43  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,
45 -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,
47 -1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,
48 -1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,
49 -1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,
50 -1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,
51 -1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,
52 -1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1, 0,
53 };
54 static const int8_t quant5[256]={
55  0, 1, 1, 1, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2,
56  2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2,
57  2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2,
58  2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2,
59  2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2,
60  2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2,
61  2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2,
62  2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2,
63 -2,-2,-2,-2,-2,-2,-2,-2,-2,-2,-2,-2,-2,-2,-2,-2,
64 -2,-2,-2,-2,-2,-2,-2,-2,-2,-2,-2,-2,-2,-2,-2,-2,
65 -2,-2,-2,-2,-2,-2,-2,-2,-2,-2,-2,-2,-2,-2,-2,-2,
66 -2,-2,-2,-2,-2,-2,-2,-2,-2,-2,-2,-2,-2,-2,-2,-2,
67 -2,-2,-2,-2,-2,-2,-2,-2,-2,-2,-2,-2,-2,-2,-2,-2,
68 -2,-2,-2,-2,-2,-2,-2,-2,-2,-2,-2,-2,-2,-2,-2,-2,
69 -2,-2,-2,-2,-2,-2,-2,-2,-2,-2,-2,-2,-2,-2,-2,-2,
70 -2,-2,-2,-2,-2,-2,-2,-2,-2,-2,-2,-2,-2,-1,-1,-1,
71 };
72 static const int8_t quant7[256]={
73  0, 1, 1, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2,
74  2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2,
75  2, 2, 2, 2, 2, 2, 2, 2, 3, 3, 3, 3, 3, 3, 3, 3,
76  3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3,
77  3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3,
78  3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3,
79  3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3,
80  3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3,
81 -3,-3,-3,-3,-3,-3,-3,-3,-3,-3,-3,-3,-3,-3,-3,-3,
82 -3,-3,-3,-3,-3,-3,-3,-3,-3,-3,-3,-3,-3,-3,-3,-3,
83 -3,-3,-3,-3,-3,-3,-3,-3,-3,-3,-3,-3,-3,-3,-3,-3,
84 -3,-3,-3,-3,-3,-3,-3,-3,-3,-3,-3,-3,-3,-3,-3,-3,
85 -3,-3,-3,-3,-3,-3,-3,-3,-3,-3,-3,-3,-3,-3,-3,-3,
86 -3,-3,-3,-3,-3,-3,-3,-3,-3,-2,-2,-2,-2,-2,-2,-2,
87 -2,-2,-2,-2,-2,-2,-2,-2,-2,-2,-2,-2,-2,-2,-2,-2,
88 -2,-2,-2,-2,-2,-2,-2,-2,-2,-2,-2,-2,-2,-2,-1,-1,
89 };
90 static const int8_t quant9[256]={
91  0, 1, 1, 2, 2, 2, 2, 3, 3, 3, 3, 3, 3, 3, 3, 3,
92  3, 3, 3, 3, 3, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4,
93  4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4,
94  4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4,
95  4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4,
96  4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4,
97  4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4,
98  4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4,
99 -4,-4,-4,-4,-4,-4,-4,-4,-4,-4,-4,-4,-4,-4,-4,-4,
100 -4,-4,-4,-4,-4,-4,-4,-4,-4,-4,-4,-4,-4,-4,-4,-4,
101 -4,-4,-4,-4,-4,-4,-4,-4,-4,-4,-4,-4,-4,-4,-4,-4,
102 -4,-4,-4,-4,-4,-4,-4,-4,-4,-4,-4,-4,-4,-4,-4,-4,
103 -4,-4,-4,-4,-4,-4,-4,-4,-4,-4,-4,-4,-4,-4,-4,-4,
104 -4,-4,-4,-4,-4,-4,-4,-4,-4,-4,-4,-4,-4,-4,-4,-4,
105 -4,-4,-4,-4,-4,-4,-4,-4,-4,-4,-4,-4,-3,-3,-3,-3,
106 -3,-3,-3,-3,-3,-3,-3,-3,-3,-3,-2,-2,-2,-2,-1,-1,
107 };
108 static const int8_t quant11[256]={
109  0, 1, 2, 2, 2, 3, 3, 3, 3, 3, 3, 3, 4, 4, 4, 4,
110  4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4,
111  4, 4, 4, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5,
112  5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5,
113  5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5,
114  5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5,
115  5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5,
116  5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5,
117 -5,-5,-5,-5,-5,-5,-5,-5,-5,-5,-5,-5,-5,-5,-5,-5,
118 -5,-5,-5,-5,-5,-5,-5,-5,-5,-5,-5,-5,-5,-5,-5,-5,
119 -5,-5,-5,-5,-5,-5,-5,-5,-5,-5,-5,-5,-5,-5,-5,-5,
120 -5,-5,-5,-5,-5,-5,-5,-5,-5,-5,-5,-5,-5,-5,-5,-5,
121 -5,-5,-5,-5,-5,-5,-5,-5,-5,-5,-5,-5,-5,-5,-5,-5,
122 -5,-5,-5,-5,-5,-5,-5,-5,-5,-5,-5,-5,-5,-5,-4,-4,
123 -4,-4,-4,-4,-4,-4,-4,-4,-4,-4,-4,-4,-4,-4,-4,-4,
124 -4,-4,-4,-4,-4,-3,-3,-3,-3,-3,-3,-3,-2,-2,-2,-1,
125 };
126 static const int8_t quant13[256]={
127  0, 1, 2, 2, 3, 3, 3, 3, 4, 4, 4, 4, 4, 4, 4, 4,
128  4, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5,
129  5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5,
130  5, 5, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6,
131  6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6,
132  6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6,
133  6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6,
134  6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6,
135 -6,-6,-6,-6,-6,-6,-6,-6,-6,-6,-6,-6,-6,-6,-6,-6,
136 -6,-6,-6,-6,-6,-6,-6,-6,-6,-6,-6,-6,-6,-6,-6,-6,
137 -6,-6,-6,-6,-6,-6,-6,-6,-6,-6,-6,-6,-6,-6,-6,-6,
138 -6,-6,-6,-6,-6,-6,-6,-6,-6,-6,-6,-6,-6,-6,-6,-6,
139 -6,-6,-6,-6,-6,-6,-6,-6,-6,-6,-6,-6,-6,-6,-6,-5,
140 -5,-5,-5,-5,-5,-5,-5,-5,-5,-5,-5,-5,-5,-5,-5,-5,
141 -5,-5,-5,-5,-5,-5,-5,-5,-5,-5,-5,-5,-5,-5,-5,-5,
142 -4,-4,-4,-4,-4,-4,-4,-4,-4,-3,-3,-3,-3,-2,-2,-1,
143 };
144
145 static const uint8_t log2_run[32]={
146  0, 0, 0, 0, 1, 1, 1, 1, 2, 2, 2, 2, 3, 3, 3, 3, 
147  4, 4, 5, 5, 6, 6, 7, 7, 
148  8, 9,10,11,12,13,14,15,
149 };
150
151 typedef struct VlcState{
152     int16_t drift;
153     uint16_t error_sum;
154     int8_t bias;
155     uint8_t count;
156 } VlcState;
157
158 typedef struct PlaneContext{
159     int context_count;
160     uint8_t (*state)[CONTEXT_SIZE];
161     VlcState *vlc_state;
162     uint8_t interlace_bit_state[2];
163 } PlaneContext;
164
165 typedef struct FFV1Context{
166     AVCodecContext *avctx;
167     CABACContext c;
168     GetBitContext gb;
169     PutBitContext pb;
170     int version;
171     int width, height;
172     int chroma_h_shift, chroma_v_shift;
173     int flags;
174     int picture_number;
175     AVFrame picture;
176     int plane_count;
177     int ac;                              ///< 1-> CABAC 0-> golomb rice
178     PlaneContext plane[MAX_PLANES];
179     int16_t quant_table[5][256];
180     int run_index;
181     int colorspace;
182     
183     DSPContext dsp; 
184 }FFV1Context;
185
186 static always_inline int fold(int diff, int bits){
187     if(bits==8)
188         diff= (int8_t)diff;
189     else{
190         diff+= 1<<(bits-1);
191         diff&=(1<<bits)-1;
192         diff-= 1<<(bits-1);
193     }
194
195     return diff;
196 }
197
198 static inline int predict(int_fast16_t *src, int_fast16_t *last){
199     const int LT= last[-1];
200     const int  T= last[ 0];
201     const int L =  src[-1];
202
203     return mid_pred(L, L + T - LT, T);
204 }
205
206 static inline int get_context(FFV1Context *f, int_fast16_t *src, int_fast16_t *last, int_fast16_t *last2){
207     const int LT= last[-1];
208     const int  T= last[ 0];
209     const int RT= last[ 1];
210     const int L =  src[-1];
211
212     if(f->quant_table[3][127]){
213         const int TT= last2[0];
214         const int LL=  src[-2];
215         return f->quant_table[0][(L-LT) & 0xFF] + f->quant_table[1][(LT-T) & 0xFF] + f->quant_table[2][(T-RT) & 0xFF]
216               +f->quant_table[3][(LL-L) & 0xFF] + f->quant_table[4][(TT-T) & 0xFF];
217     }else
218         return f->quant_table[0][(L-LT) & 0xFF] + f->quant_table[1][(LT-T) & 0xFF] + f->quant_table[2][(T-RT) & 0xFF];
219 }
220
221 /**
222  * put 
223  */
224 static inline void put_symbol(CABACContext *c, uint8_t *state, int v, int is_signed, int max_exp){
225     int i;
226
227     if(v){
228         const int a= ABS(v);
229         const int e= av_log2(a);
230
231         put_cabac(c, state+0, 0);
232         
233         for(i=0; i<e; i++){
234             put_cabac(c, state+1+i, 1);  //1..8
235         }
236
237         if(e<max_exp){
238             put_cabac(c, state+1+i, 0);      //1..8
239
240             for(i=e-1; i>=0; i--){
241                 put_cabac(c, state+16+e+i, (a>>i)&1); //17..29
242             }
243             if(is_signed)
244                 put_cabac(c, state+9 + e, v < 0); //9..16
245         }
246     }else{
247         put_cabac(c, state+0, 1);
248     }
249 }
250
251 static inline int get_symbol(CABACContext *c, uint8_t *state, int is_signed, int max_exp){
252     if(get_cabac(c, state+0))
253         return 0;
254     else{
255         int i, e;
256  
257         for(e=0; e<max_exp; e++){ 
258             int a= 1<<e;
259
260             if(get_cabac(c, state + 1 + e)==0){ // 1..8
261                 for(i=e-1; i>=0; i--){
262                     a += get_cabac(c, state+16+e+i)<<i; //17..29
263                 }
264
265                 if(is_signed && get_cabac(c, state+9 + e)) //9..16
266                     return -a;
267                 else
268                     return a;
269             }
270         }
271         return -(1<<e);
272     }
273 }
274
275 static inline void update_vlc_state(VlcState * const state, const int v){
276     int drift= state->drift;
277     int count= state->count;
278     state->error_sum += ABS(v);
279     drift += v;
280
281     if(count == 128){ //FIXME variable
282         count >>= 1;
283         drift >>= 1;
284         state->error_sum >>= 1;
285     }
286     count++;
287
288     if(drift <= -count){
289         if(state->bias > -128) state->bias--;
290         
291         drift += count;
292         if(drift <= -count)
293             drift= -count + 1;
294     }else if(drift > 0){
295         if(state->bias <  127) state->bias++;
296         
297         drift -= count;
298         if(drift > 0) 
299             drift= 0;
300     }
301
302     state->drift= drift;
303     state->count= count;
304 }
305
306 static inline void put_vlc_symbol(PutBitContext *pb, VlcState * const state, int v, int bits){
307     int i, k, code;
308 //printf("final: %d ", v);
309     v = fold(v - state->bias, bits);
310
311     i= state->count;
312     k=0;
313     while(i < state->error_sum){ //FIXME optimize
314         k++;
315         i += i;
316     }
317
318     assert(k<=8);
319
320 #if 0 // JPEG LS
321     if(k==0 && 2*state->drift <= - state->count) code= v ^ (-1);
322     else                                         code= v;
323 #else
324      code= v ^ ((2*state->drift + state->count)>>31);
325 #endif
326     
327     code = -2*code-1;
328     code^= (code>>31);
329 //printf("v:%d/%d bias:%d error:%d drift:%d count:%d k:%d\n", v, code, state->bias, state->error_sum, state->drift, state->count, k);
330     set_ur_golomb(pb, code, k, 12, bits);
331
332     update_vlc_state(state, v);
333 }
334
335 static inline int get_vlc_symbol(GetBitContext *gb, VlcState * const state, int bits){
336     int k, i, v, ret;
337
338     i= state->count;
339     k=0;
340     while(i < state->error_sum){ //FIXME optimize
341         k++;
342         i += i;
343     }
344
345     assert(k<=8);
346
347     v= get_ur_golomb(gb, k, 12, bits);
348 //printf("v:%d bias:%d error:%d drift:%d count:%d k:%d", v, state->bias, state->error_sum, state->drift, state->count, k);
349
350     v++;
351     if(v&1) v=  (v>>1);
352     else    v= -(v>>1);
353
354 #if 0 // JPEG LS
355     if(k==0 && 2*state->drift <= - state->count) v ^= (-1);
356 #else
357      v ^= ((2*state->drift + state->count)>>31);
358 #endif
359
360     ret= fold(v + state->bias, bits);
361     
362     update_vlc_state(state, v);
363 //printf("final: %d\n", ret);
364     return ret;
365 }
366
367 static inline void encode_line(FFV1Context *s, int w, int_fast16_t *sample[2], int plane_index, int bits){
368     PlaneContext * const p= &s->plane[plane_index];
369     CABACContext * const c= &s->c;
370     int x;
371     int run_index= s->run_index;
372     int run_count=0;
373     int run_mode=0;
374
375     for(x=0; x<w; x++){
376         int diff, context;
377         
378         context= get_context(s, sample[0]+x, sample[1]+x, sample[2]+x);
379         diff= sample[0][x] - predict(sample[0]+x, sample[1]+x);
380
381         if(context < 0){
382             context = -context;
383             diff= -diff;
384         }
385
386         diff= fold(diff, bits);
387         
388         if(s->ac){
389             put_symbol(c, p->state[context], diff, 1, bits-1);
390         }else{
391             if(context == 0) run_mode=1;
392             
393             if(run_mode){
394
395                 if(diff){
396                     while(run_count >= 1<<log2_run[run_index]){
397                         run_count -= 1<<log2_run[run_index];
398                         run_index++;
399                         put_bits(&s->pb, 1, 1);
400                     }
401                     
402                     put_bits(&s->pb, 1 + log2_run[run_index], run_count);
403                     if(run_index) run_index--;
404                     run_count=0;
405                     run_mode=0;
406                     if(diff>0) diff--;
407                 }else{
408                     run_count++;
409                 }
410             }
411             
412 //            printf("count:%d index:%d, mode:%d, x:%d y:%d pos:%d\n", run_count, run_index, run_mode, x, y, (int)put_bits_count(&s->pb));
413
414             if(run_mode == 0)
415                 put_vlc_symbol(&s->pb, &p->vlc_state[context], diff, bits);
416         }
417     }
418     if(run_mode){
419         while(run_count >= 1<<log2_run[run_index]){
420             run_count -= 1<<log2_run[run_index];
421             run_index++;
422             put_bits(&s->pb, 1, 1);
423         }
424
425         if(run_count)
426             put_bits(&s->pb, 1, 1);
427     }
428     s->run_index= run_index;
429 }
430
431 static void encode_plane(FFV1Context *s, uint8_t *src, int w, int h, int stride, int plane_index){
432     int x,y,i;
433     const int ring_size= s->avctx->context_model ? 3 : 2;
434     int_fast16_t sample_buffer[ring_size][w+6], *sample[ring_size];
435     s->run_index=0;
436     
437     memset(sample_buffer, 0, sizeof(sample_buffer));
438     
439     for(y=0; y<h; y++){
440         for(i=0; i<ring_size; i++)
441             sample[i]= sample_buffer[(h+i-y)%ring_size]+3;
442         
443         sample[0][-1]= sample[1][0  ];
444         sample[1][ w]= sample[1][w-1];
445 //{START_TIMER
446         for(x=0; x<w; x++){
447             sample[0][x]= src[x + stride*y];
448         }
449         encode_line(s, w, sample, plane_index, 8);
450 //STOP_TIMER("encode line")}
451     }
452 }
453
454 static void encode_rgb_frame(FFV1Context *s, uint32_t *src, int w, int h, int stride){
455     int x, y, p, i;
456     const int ring_size= s->avctx->context_model ? 3 : 2;
457     int_fast16_t sample_buffer[3][ring_size][w+6], *sample[3][ring_size];
458     s->run_index=0;
459     
460     memset(sample_buffer, 0, sizeof(sample_buffer));
461     
462     for(y=0; y<h; y++){
463         for(i=0; i<ring_size; i++)
464             for(p=0; p<3; p++)
465                 sample[p][i]= sample_buffer[p][(h+i-y)%ring_size]+3;
466
467         for(x=0; x<w; x++){
468             int v= src[x + stride*y];
469             int b= v&0xFF;
470             int g= (v>>8)&0xFF;
471             int r= (v>>16)&0xFF;
472             
473             b -= g;
474             r -= g;
475             g += (b + r)>>2;
476             b += 0x100;
477             r += 0x100;
478             
479 //            assert(g>=0 && b>=0 && r>=0);
480 //            assert(g<256 && b<512 && r<512);
481             sample[0][0][x]= g;
482             sample[1][0][x]= b;
483             sample[2][0][x]= r;
484         }
485         for(p=0; p<3; p++){
486             sample[p][0][-1]= sample[p][1][0  ];
487             sample[p][1][ w]= sample[p][1][w-1];
488             encode_line(s, w, sample[p], FFMIN(p, 1), 9);
489         }
490     }
491 }
492
493 static void write_quant_table(CABACContext *c, int16_t *quant_table){
494     int last=0;
495     int i;
496     uint8_t state[CONTEXT_SIZE]={0};
497
498     for(i=1; i<128 ; i++){
499         if(quant_table[i] != quant_table[i-1]){
500             put_symbol(c, state, i-last-1, 0, 7);
501             last= i;
502         }
503     }
504     put_symbol(c, state, i-last-1, 0, 7);
505 }
506
507 static void write_header(FFV1Context *f){
508     uint8_t state[CONTEXT_SIZE]={0};
509     int i;
510     CABACContext * const c= &f->c;
511
512     put_symbol(c, state, f->version, 0, 7);
513     put_symbol(c, state, f->avctx->coder_type, 0, 7);
514     put_symbol(c, state, f->colorspace, 0, 7); //YUV cs type 
515     put_cabac(c, state, 1); //chroma planes
516         put_symbol(c, state, f->chroma_h_shift, 0, 7);
517         put_symbol(c, state, f->chroma_v_shift, 0, 7);
518     put_cabac(c, state, 0); //no transparency plane
519
520     for(i=0; i<5; i++)
521         write_quant_table(c, f->quant_table[i]);
522 }
523
524 static int common_init(AVCodecContext *avctx){
525     FFV1Context *s = avctx->priv_data;
526     int width, height;
527
528     s->avctx= avctx;
529     s->flags= avctx->flags;
530         
531     dsputil_init(&s->dsp, avctx);
532     
533     width= s->width= avctx->width;
534     height= s->height= avctx->height;
535     
536     assert(width && height);
537
538     return 0;
539 }
540
541 static int encode_init(AVCodecContext *avctx)
542 {
543     FFV1Context *s = avctx->priv_data;
544     int i;
545
546     common_init(avctx);
547  
548     s->version=0;
549     s->ac= avctx->coder_type;
550     
551     s->plane_count=2;
552     for(i=0; i<256; i++){
553         s->quant_table[0][i]=           quant11[i];
554         s->quant_table[1][i]=        11*quant11[i];
555         if(avctx->context_model==0){
556             s->quant_table[2][i]=     11*11*quant11[i];
557             s->quant_table[3][i]=
558             s->quant_table[4][i]=0;
559         }else{
560             s->quant_table[2][i]=     11*11*quant5 [i];
561             s->quant_table[3][i]=   5*11*11*quant5 [i];
562             s->quant_table[4][i]= 5*5*11*11*quant5 [i];
563         }
564     }
565
566     for(i=0; i<s->plane_count; i++){
567         PlaneContext * const p= &s->plane[i];
568                
569         if(avctx->context_model==0){
570             p->context_count= (11*11*11+1)/2;
571         }else{        
572             p->context_count= (11*11*5*5*5+1)/2;
573         }
574
575         if(s->ac){
576             if(!p->state) p->state= av_malloc(CONTEXT_SIZE*p->context_count*sizeof(uint8_t));
577         }else{
578             if(!p->vlc_state) p->vlc_state= av_malloc(p->context_count*sizeof(VlcState));
579         }
580     }
581
582     avctx->coded_frame= &s->picture;
583     switch(avctx->pix_fmt){
584     case PIX_FMT_YUV444P:
585     case PIX_FMT_YUV422P:
586     case PIX_FMT_YUV420P:
587     case PIX_FMT_YUV411P:
588     case PIX_FMT_YUV410P:
589         s->colorspace= 0;
590         break;
591     case PIX_FMT_RGBA32:
592         s->colorspace= 1;
593         break;
594     default:
595         av_log(avctx, AV_LOG_ERROR, "format not supported\n");
596         return -1;
597     }
598     avcodec_get_chroma_sub_sample(avctx->pix_fmt, &s->chroma_h_shift, &s->chroma_v_shift);
599
600     s->picture_number=0;
601     
602     return 0;
603 }
604
605
606 static void clear_state(FFV1Context *f){
607     int i, j;
608
609     for(i=0; i<f->plane_count; i++){
610         PlaneContext *p= &f->plane[i];
611
612         p->interlace_bit_state[0]= 0;
613         p->interlace_bit_state[1]= 0;
614         
615         for(j=0; j<p->context_count; j++){
616             if(f->ac){
617                 memset(p->state[j], 0, sizeof(uint8_t)*CONTEXT_SIZE);
618                 p->state[j][7] = 2*62;
619             }else{
620                 p->vlc_state[j].drift= 0;
621                 p->vlc_state[j].error_sum= 4; //FFMAX((RANGE + 32)/64, 2);
622                 p->vlc_state[j].bias= 0;
623                 p->vlc_state[j].count= 1;
624             }
625         }
626     }
627 }
628
629 static int encode_frame(AVCodecContext *avctx, unsigned char *buf, int buf_size, void *data){
630     FFV1Context *f = avctx->priv_data;
631     CABACContext * const c= &f->c;
632     AVFrame *pict = data;
633     const int width= f->width;
634     const int height= f->height;
635     AVFrame * const p= &f->picture;
636     int used_count= 0;
637
638     if(avctx->strict_std_compliance >= 0){
639         av_log(avctx, AV_LOG_ERROR, "this codec is under development, files encoded with it wont be decodeable with future versions!!!\n"
640                "use vstrict=-1 to use it anyway\n");
641         return -1;
642     }
643         
644     ff_init_cabac_encoder(c, buf, buf_size);
645     ff_init_cabac_states(c, ff_h264_lps_range, ff_h264_mps_state, ff_h264_lps_state, 64);
646     c->lps_state[2] = 1;
647     c->lps_state[3] = 0;
648     
649     *p = *pict;
650     p->pict_type= FF_I_TYPE;
651     
652     if(avctx->gop_size==0 || f->picture_number % avctx->gop_size == 0){
653         put_cabac_bypass(c, 1);
654         p->key_frame= 1;
655         write_header(f);
656         clear_state(f);
657     }else{
658         put_cabac_bypass(c, 0);
659         p->key_frame= 0;
660     }
661
662     if(!f->ac){
663         used_count += put_cabac_terminate(c, 1);
664 //printf("pos=%d\n", used_count);
665         init_put_bits(&f->pb, buf + used_count, buf_size - used_count);
666     }
667     
668     if(f->colorspace==0){
669         const int chroma_width = -((-width )>>f->chroma_h_shift);
670         const int chroma_height= -((-height)>>f->chroma_v_shift);
671
672         encode_plane(f, p->data[0], width, height, p->linesize[0], 0);
673
674         encode_plane(f, p->data[1], chroma_width, chroma_height, p->linesize[1], 1);
675         encode_plane(f, p->data[2], chroma_width, chroma_height, p->linesize[2], 1);
676     }else{
677         encode_rgb_frame(f, (uint32_t*)(p->data[0]), width, height, p->linesize[0]/4);
678     }
679     emms_c();
680     
681     f->picture_number++;
682
683     if(f->ac){
684         return put_cabac_terminate(c, 1);
685     }else{
686         flush_put_bits(&f->pb); //nicer padding FIXME
687         return used_count + (put_bits_count(&f->pb)+7)/8;
688     }
689 }
690
691 static void common_end(FFV1Context *s){
692     int i; 
693
694     for(i=0; i<s->plane_count; i++){
695         PlaneContext *p= &s->plane[i];
696
697         av_freep(&p->state);
698     }
699 }
700
701 static int encode_end(AVCodecContext *avctx)
702 {
703     FFV1Context *s = avctx->priv_data;
704
705     common_end(s);
706
707     return 0;
708 }
709
710 static inline void decode_line(FFV1Context *s, int w, int_fast16_t *sample[2], int plane_index, int bits){
711     PlaneContext * const p= &s->plane[plane_index];
712     CABACContext * const c= &s->c;
713     int x;
714     int run_count=0;
715     int run_mode=0;
716     int run_index= s->run_index;
717
718     for(x=0; x<w; x++){
719         int diff, context, sign;
720          
721         context= get_context(s, sample[1] + x, sample[0] + x, sample[1] + x);
722         if(context < 0){
723             context= -context;
724             sign=1;
725         }else
726             sign=0;
727         
728
729         if(s->ac)
730             diff= get_symbol(c, p->state[context], 1, bits-1);
731         else{
732             if(context == 0 && run_mode==0) run_mode=1;
733             
734             if(run_mode){
735                 if(run_count==0 && run_mode==1){
736                     if(get_bits1(&s->gb)){
737                         run_count = 1<<log2_run[run_index];
738                         if(x + run_count <= w) run_index++;
739                     }else{
740                         if(log2_run[run_index]) run_count = get_bits(&s->gb, log2_run[run_index]);
741                         else run_count=0;
742                         if(run_index) run_index--;
743                         run_mode=2;
744                     }
745                 }
746                 run_count--;
747                 if(run_count < 0){
748                     run_mode=0;
749                     run_count=0;
750                     diff= get_vlc_symbol(&s->gb, &p->vlc_state[context], bits);
751                     if(diff>=0) diff++;
752                 }else
753                     diff=0;
754             }else
755                 diff= get_vlc_symbol(&s->gb, &p->vlc_state[context], bits);
756             
757 //            printf("count:%d index:%d, mode:%d, x:%d y:%d pos:%d\n", run_count, run_index, run_mode, x, y, get_bits_count(&s->gb));
758         }
759
760         if(sign) diff= -diff;
761
762         sample[1][x]= (predict(sample[1] + x, sample[0] + x) + diff) & ((1<<bits)-1);
763     }
764     s->run_index= run_index;        
765 }
766
767 static void decode_plane(FFV1Context *s, uint8_t *src, int w, int h, int stride, int plane_index){
768     int x, y;
769     int_fast16_t sample_buffer[2][w+6];
770     int_fast16_t *sample[2]= {sample_buffer[0]+3, sample_buffer[1]+3};
771
772     s->run_index=0;
773     
774     memset(sample_buffer, 0, sizeof(sample_buffer));
775     
776     for(y=0; y<h; y++){
777         int_fast16_t *temp= sample[0]; //FIXME try a normal buffer
778
779         sample[0]= sample[1];
780         sample[1]= temp;
781
782         sample[1][-1]= sample[0][0  ];
783         sample[0][ w]= sample[0][w-1];
784         
785 //{START_TIMER
786         decode_line(s, w, sample, plane_index, 8);
787         for(x=0; x<w; x++){
788             src[x + stride*y]= sample[1][x];
789         }
790 //STOP_TIMER("decode-line")}
791     }
792 }
793
794 static void decode_rgb_frame(FFV1Context *s, uint32_t *src, int w, int h, int stride){
795     int x, y, p;
796     int_fast16_t sample_buffer[3][2][w+6];
797     int_fast16_t *sample[3][2]= {
798         {sample_buffer[0][0]+3, sample_buffer[0][1]+3},
799         {sample_buffer[1][0]+3, sample_buffer[1][1]+3},
800         {sample_buffer[2][0]+3, sample_buffer[2][1]+3}};
801
802     s->run_index=0;
803     
804     memset(sample_buffer, 0, sizeof(sample_buffer));
805     
806     for(y=0; y<h; y++){
807         for(p=0; p<3; p++){
808             int_fast16_t *temp= sample[p][0]; //FIXME try a normal buffer
809
810             sample[p][0]= sample[p][1];
811             sample[p][1]= temp;
812
813             sample[p][1][-1]= sample[p][0][0  ];
814             sample[p][0][ w]= sample[p][0][w-1];
815             decode_line(s, w, sample[p], FFMIN(p, 1), 9);
816         }
817         for(x=0; x<w; x++){
818             int g= sample[0][1][x];
819             int b= sample[1][1][x];
820             int r= sample[2][1][x];
821
822 //            assert(g>=0 && b>=0 && r>=0);
823 //            assert(g<256 && b<512 && r<512);
824             
825             b -= 0x100;
826             r -= 0x100;
827             g -= (b + r)>>2;
828             b += g;
829             r += g;
830             
831             src[x + stride*y]= b + (g<<8) + (r<<16);
832         }
833     }
834 }
835
836 static int read_quant_table(CABACContext *c, int16_t *quant_table, int scale){
837     int v;
838     int i=0;
839     uint8_t state[CONTEXT_SIZE]={0};
840
841     for(v=0; i<128 ; v++){
842         int len= get_symbol(c, state, 0, 7) + 1;
843
844         if(len + i > 128) return -1;
845         
846         while(len--){
847             quant_table[i] = scale*v;
848             i++;
849 //printf("%2d ",v);
850 //if(i%16==0) printf("\n");
851         }
852     }
853
854     for(i=1; i<128; i++){
855         quant_table[256-i]= -quant_table[i];
856     }
857     quant_table[128]= -quant_table[127];
858     
859     return 2*v - 1;
860 }
861
862 static int read_header(FFV1Context *f){
863     uint8_t state[CONTEXT_SIZE]={0};
864     int i, context_count;
865     CABACContext * const c= &f->c;
866     
867     f->version= get_symbol(c, state, 0, 7);
868     f->ac= f->avctx->coder_type= get_symbol(c, state, 0, 7);
869     f->colorspace= get_symbol(c, state, 0, 7); //YUV cs type
870     get_cabac(c, state); //no chroma = false
871     f->chroma_h_shift= get_symbol(c, state, 0, 7);
872     f->chroma_v_shift= get_symbol(c, state, 0, 7);
873     get_cabac(c, state); //transparency plane
874     f->plane_count= 2;
875
876     if(f->colorspace==0){
877         switch(16*f->chroma_h_shift + f->chroma_v_shift){
878         case 0x00: f->avctx->pix_fmt= PIX_FMT_YUV444P; break;
879         case 0x10: f->avctx->pix_fmt= PIX_FMT_YUV422P; break;
880         case 0x11: f->avctx->pix_fmt= PIX_FMT_YUV420P; break;
881         case 0x20: f->avctx->pix_fmt= PIX_FMT_YUV411P; break;
882         case 0x33: f->avctx->pix_fmt= PIX_FMT_YUV410P; break;
883         default:
884             av_log(f->avctx, AV_LOG_ERROR, "format not supported\n");
885             return -1;
886         }
887     }else if(f->colorspace==1){
888         if(f->chroma_h_shift || f->chroma_v_shift){
889             av_log(f->avctx, AV_LOG_ERROR, "chroma subsampling not supported in this colorspace\n");
890             return -1;
891         }
892         f->avctx->pix_fmt= PIX_FMT_RGBA32;
893     }else{
894         av_log(f->avctx, AV_LOG_ERROR, "colorspace not supported\n");
895         return -1;
896     }
897
898 //printf("%d %d %d\n", f->chroma_h_shift, f->chroma_v_shift,f->avctx->pix_fmt);
899
900     context_count=1;
901     for(i=0; i<5; i++){
902         context_count*= read_quant_table(c, f->quant_table[i], context_count);
903         if(context_count < 0){
904             av_log(f->avctx, AV_LOG_ERROR, "read_quant_table error\n");
905             return -1;
906         }
907     }
908     context_count= (context_count+1)/2;
909     
910     for(i=0; i<f->plane_count; i++){
911         PlaneContext * const p= &f->plane[i];
912
913         p->context_count= context_count;
914
915         if(f->ac){
916             if(!p->state) p->state= av_malloc(CONTEXT_SIZE*p->context_count*sizeof(uint8_t));
917         }else{
918             if(!p->vlc_state) p->vlc_state= av_malloc(p->context_count*sizeof(VlcState));
919         }
920     }
921     
922     return 0;
923 }
924
925 static int decode_init(AVCodecContext *avctx)
926 {
927 //    FFV1Context *s = avctx->priv_data;
928
929     common_init(avctx);
930     
931     return 0;
932 }
933
934 static int decode_frame(AVCodecContext *avctx, void *data, int *data_size, uint8_t *buf, int buf_size){
935     FFV1Context *f = avctx->priv_data;
936     CABACContext * const c= &f->c;
937     const int width= f->width;
938     const int height= f->height;
939     AVFrame * const p= &f->picture;
940     int bytes_read;
941
942     AVFrame *picture = data;
943
944     /* no supplementary picture */
945     if (buf_size == 0)
946         return 0;
947
948     ff_init_cabac_decoder(c, buf, buf_size);
949     ff_init_cabac_states(c, ff_h264_lps_range, ff_h264_mps_state, ff_h264_lps_state, 64);
950     c->lps_state[2] = 1;
951     c->lps_state[3] = 0;
952
953
954     p->pict_type= FF_I_TYPE; //FIXME I vs. P
955     if(get_cabac_bypass(c)){
956         p->key_frame= 1;
957         read_header(f);
958         clear_state(f);
959     }else{
960         p->key_frame= 0;
961     }
962
963     p->reference= 0;
964     if(avctx->get_buffer(avctx, p) < 0){
965         av_log(avctx, AV_LOG_ERROR, "get_buffer() failed\n");
966         return -1;
967     }
968
969     if(avctx->debug&FF_DEBUG_PICT_INFO)
970         av_log(avctx, AV_LOG_ERROR, "keyframe:%d coder:%d\n", p->key_frame, f->ac);
971     
972     if(!f->ac){
973         bytes_read = get_cabac_terminate(c);
974         if(bytes_read ==0) av_log(avctx, AV_LOG_ERROR, "error at end of AC stream\n");
975 //printf("pos=%d\n", bytes_read);
976         init_get_bits(&f->gb, buf + bytes_read, buf_size - bytes_read);
977     } else {
978         bytes_read = 0; /* avoid warning */
979     }
980     
981     if(f->colorspace==0){
982         const int chroma_width = -((-width )>>f->chroma_h_shift);
983         const int chroma_height= -((-height)>>f->chroma_v_shift);
984         decode_plane(f, p->data[0], width, height, p->linesize[0], 0);
985         
986         decode_plane(f, p->data[1], chroma_width, chroma_height, p->linesize[1], 1);
987         decode_plane(f, p->data[2], chroma_width, chroma_height, p->linesize[2], 1);
988     }else{
989         decode_rgb_frame(f, (uint32_t*)p->data[0], width, height, p->linesize[0]/4);
990     }
991         
992     emms_c();
993
994     f->picture_number++;
995
996     *picture= *p;
997     
998     avctx->release_buffer(avctx, p); //FIXME
999
1000     *data_size = sizeof(AVFrame);
1001     
1002     if(f->ac){
1003         bytes_read= get_cabac_terminate(c);
1004         if(bytes_read ==0) av_log(f->avctx, AV_LOG_ERROR, "error at end of frame\n");
1005     }else{
1006         bytes_read+= (get_bits_count(&f->gb)+7)/8;
1007     }
1008
1009     return bytes_read;
1010 }
1011
1012 AVCodec ffv1_decoder = {
1013     "ffv1",
1014     CODEC_TYPE_VIDEO,
1015     CODEC_ID_FFV1,
1016     sizeof(FFV1Context),
1017     decode_init,
1018     NULL,
1019     NULL,
1020     decode_frame,
1021     CODEC_CAP_DR1 /*| CODEC_CAP_DRAW_HORIZ_BAND*/,
1022     NULL
1023 };
1024
1025 #ifdef CONFIG_ENCODERS
1026 AVCodec ffv1_encoder = {
1027     "ffv1",
1028     CODEC_TYPE_VIDEO,
1029     CODEC_ID_FFV1,
1030     sizeof(FFV1Context),
1031     encode_init,
1032     encode_frame,
1033     encode_end,
1034 };
1035 #endif