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