ffv1: add 1 status byte to slices in in case crcs are stored too.
[ffmpeg.git] / libavcodec / ffv1.c
1 /*
2  * FFV1 codec for libavcodec
3  *
4  * Copyright (c) 2003 Michael Niedermayer <michaelni@gmx.at>
5  *
6  * This file is part of FFmpeg.
7  *
8  * FFmpeg is free software; you can redistribute it and/or
9  * modify it under the terms of the GNU Lesser General Public
10  * License as published by the Free Software Foundation; either
11  * version 2.1 of the License, or (at your option) any later version.
12  *
13  * FFmpeg is distributed in the hope that it will be useful,
14  * but WITHOUT ANY WARRANTY; without even the implied warranty of
15  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
16  * Lesser General Public License for more details.
17  *
18  * You should have received a copy of the GNU Lesser General Public
19  * License along with FFmpeg; if not, write to the Free Software
20  * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
21  */
22
23 /**
24  * @file
25  * FF Video Codec 1 (a lossless codec)
26  */
27
28 #include "avcodec.h"
29 #include "internal.h"
30 #include "get_bits.h"
31 #include "put_bits.h"
32 #include "dsputil.h"
33 #include "rangecoder.h"
34 #include "golomb.h"
35 #include "mathops.h"
36 #include "libavutil/pixdesc.h"
37 #include "libavutil/avassert.h"
38 #include "libavutil/crc.h"
39
40 #ifdef __INTEL_COMPILER
41 #undef av_flatten
42 #define av_flatten
43 #endif
44
45 #define MAX_PLANES 4
46 #define CONTEXT_SIZE 32
47
48 #define MAX_QUANT_TABLES 8
49 #define MAX_CONTEXT_INPUTS 5
50
51 extern const uint8_t ff_log2_run[41];
52
53 static const int8_t quant5_10bit[256]={
54  0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1,
55  1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
56  1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
57  1, 1, 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,-1,
67 -1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,
68 -1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,
69 -1,-1,-1,-1,-1,-1,-0,-0,-0,-0,-0,-0,-0,-0,-0,-0,
70 };
71
72 static const int8_t quant5[256]={
73  0, 1, 1, 1, 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, 2, 2, 2, 2, 2, 2, 2, 2,
76  2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2,
77  2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2,
78  2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2,
79  2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2,
80  2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2,
81 -2,-2,-2,-2,-2,-2,-2,-2,-2,-2,-2,-2,-2,-2,-2,-2,
82 -2,-2,-2,-2,-2,-2,-2,-2,-2,-2,-2,-2,-2,-2,-2,-2,
83 -2,-2,-2,-2,-2,-2,-2,-2,-2,-2,-2,-2,-2,-2,-2,-2,
84 -2,-2,-2,-2,-2,-2,-2,-2,-2,-2,-2,-2,-2,-2,-2,-2,
85 -2,-2,-2,-2,-2,-2,-2,-2,-2,-2,-2,-2,-2,-2,-2,-2,
86 -2,-2,-2,-2,-2,-2,-2,-2,-2,-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,-1,-1,-1,
89 };
90
91 static const int8_t quant9_10bit[256]={
92  0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 2, 2, 2,
93  2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 3, 3, 3, 3, 3,
94  3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3,
95  3, 3, 3, 3, 3, 3, 3, 3, 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,-3,-3,-3,-3,-3,-3,-3,
105 -3,-3,-3,-3,-3,-3,-3,-3,-3,-3,-3,-3,-3,-3,-3,-3,
106 -3,-3,-3,-3,-3,-3,-2,-2,-2,-2,-2,-2,-2,-2,-2,-2,
107 -2,-2,-2,-2,-1,-1,-1,-1,-1,-1,-1,-1,-0,-0,-0,-0,
108 };
109
110 static const int8_t quant11[256]={
111  0, 1, 2, 2, 2, 3, 3, 3, 3, 3, 3, 3, 4, 4, 4, 4,
112  4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4,
113  4, 4, 4, 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,-5,-5,
124 -5,-5,-5,-5,-5,-5,-5,-5,-5,-5,-5,-5,-5,-5,-4,-4,
125 -4,-4,-4,-4,-4,-4,-4,-4,-4,-4,-4,-4,-4,-4,-4,-4,
126 -4,-4,-4,-4,-4,-3,-3,-3,-3,-3,-3,-3,-2,-2,-2,-1,
127 };
128
129 static const uint8_t ver2_state[256]= {
130    0,  10,  10,  10,  10,  16,  16,  16,  28,  16,  16,  29,  42,  49,  20,  49,
131   59,  25,  26,  26,  27,  31,  33,  33,  33,  34,  34,  37,  67,  38,  39,  39,
132   40,  40,  41,  79,  43,  44,  45,  45,  48,  48,  64,  50,  51,  52,  88,  52,
133   53,  74,  55,  57,  58,  58,  74,  60, 101,  61,  62,  84,  66,  66,  68,  69,
134   87,  82,  71,  97,  73,  73,  82,  75, 111,  77,  94,  78,  87,  81,  83,  97,
135   85,  83,  94,  86,  99,  89,  90,  99, 111,  92,  93, 134,  95,  98, 105,  98,
136  105, 110, 102, 108, 102, 118, 103, 106, 106, 113, 109, 112, 114, 112, 116, 125,
137  115, 116, 117, 117, 126, 119, 125, 121, 121, 123, 145, 124, 126, 131, 127, 129,
138  165, 130, 132, 138, 133, 135, 145, 136, 137, 139, 146, 141, 143, 142, 144, 148,
139  147, 155, 151, 149, 151, 150, 152, 157, 153, 154, 156, 168, 158, 162, 161, 160,
140  172, 163, 169, 164, 166, 184, 167, 170, 177, 174, 171, 173, 182, 176, 180, 178,
141  175, 189, 179, 181, 186, 183, 192, 185, 200, 187, 191, 188, 190, 197, 193, 196,
142  197, 194, 195, 196, 198, 202, 199, 201, 210, 203, 207, 204, 205, 206, 208, 214,
143  209, 211, 221, 212, 213, 215, 224, 216, 217, 218, 219, 220, 222, 228, 223, 225,
144  226, 224, 227, 229, 240, 230, 231, 232, 233, 234, 235, 236, 238, 239, 237, 242,
145  241, 243, 242, 244, 245, 246, 247, 248, 249, 250, 251, 252, 252, 253, 254, 255,
146 };
147
148 typedef struct VlcState{
149     int16_t drift;
150     uint16_t error_sum;
151     int8_t bias;
152     uint8_t count;
153 } VlcState;
154
155 typedef struct PlaneContext{
156     int16_t quant_table[MAX_CONTEXT_INPUTS][256];
157     int quant_table_index;
158     int context_count;
159     uint8_t (*state)[CONTEXT_SIZE];
160     VlcState *vlc_state;
161     uint8_t interlace_bit_state[2];
162 } PlaneContext;
163
164 #define MAX_SLICES 256
165
166 typedef struct FFV1Context{
167     AVCodecContext *avctx;
168     RangeCoder c;
169     GetBitContext gb;
170     PutBitContext pb;
171     uint64_t rc_stat[256][2];
172     uint64_t (*rc_stat2[MAX_QUANT_TABLES])[32][2];
173     int version;
174     int minor_version;
175     int width, height;
176     int chroma_h_shift, chroma_v_shift;
177     int chroma_planes;
178     int transparency;
179     int flags;
180     int picture_number;
181     AVFrame picture;
182     int plane_count;
183     int ac;                              ///< 1=range coder <-> 0=golomb rice
184     int ac_byte_count;                   ///< number of bytes used for AC coding
185     PlaneContext plane[MAX_PLANES];
186     int16_t quant_table[MAX_CONTEXT_INPUTS][256];
187     int16_t quant_tables[MAX_QUANT_TABLES][MAX_CONTEXT_INPUTS][256];
188     int context_count[MAX_QUANT_TABLES];
189     uint8_t state_transition[256];
190     uint8_t (*initial_states[MAX_QUANT_TABLES])[32];
191     int run_index;
192     int colorspace;
193     int16_t *sample_buffer;
194     int gob_count;
195     int packed_at_lsb;
196     int ec;
197     int key_frame_ok;
198
199     int quant_table_count;
200
201     DSPContext dsp;
202
203     struct FFV1Context *slice_context[MAX_SLICES];
204     int slice_count;
205     int num_v_slices;
206     int num_h_slices;
207     int slice_width;
208     int slice_height;
209     int slice_x;
210     int slice_y;
211     int bits_per_raw_sample;
212 }FFV1Context;
213
214 static av_always_inline int fold(int diff, int bits){
215     if(bits==8)
216         diff= (int8_t)diff;
217     else{
218         diff+= 1<<(bits-1);
219         diff&=(1<<bits)-1;
220         diff-= 1<<(bits-1);
221     }
222
223     return diff;
224 }
225
226 static inline int predict(int16_t *src, int16_t *last)
227 {
228     const int LT= last[-1];
229     const int  T= last[ 0];
230     const int L =  src[-1];
231
232     return mid_pred(L, L + T - LT, T);
233 }
234
235 static inline int get_context(PlaneContext *p, int16_t *src,
236                               int16_t *last, int16_t *last2)
237 {
238     const int LT= last[-1];
239     const int  T= last[ 0];
240     const int RT= last[ 1];
241     const int L =  src[-1];
242
243     if(p->quant_table[3][127]){
244         const int TT= last2[0];
245         const int LL=  src[-2];
246         return p->quant_table[0][(L-LT) & 0xFF] + p->quant_table[1][(LT-T) & 0xFF] + p->quant_table[2][(T-RT) & 0xFF]
247               +p->quant_table[3][(LL-L) & 0xFF] + p->quant_table[4][(TT-T) & 0xFF];
248     }else
249         return p->quant_table[0][(L-LT) & 0xFF] + p->quant_table[1][(LT-T) & 0xFF] + p->quant_table[2][(T-RT) & 0xFF];
250 }
251
252 static void find_best_state(uint8_t best_state[256][256], const uint8_t one_state[256]){
253     int i,j,k,m;
254     double l2tab[256];
255
256     for(i=1; i<256; i++)
257         l2tab[i]= log2(i/256.0);
258
259     for(i=0; i<256; i++){
260         double best_len[256];
261         double p= i/256.0;
262
263         for(j=0; j<256; j++)
264             best_len[j]= 1<<30;
265
266         for(j=FFMAX(i-10,1); j<FFMIN(i+11,256); j++){
267             double occ[256]={0};
268             double len=0;
269             occ[j]=1.0;
270             for(k=0; k<256; k++){
271                 double newocc[256]={0};
272                 for(m=0; m<256; m++){
273                     if(occ[m]){
274                         len -=occ[m]*(     p *l2tab[    m]
275                                       + (1-p)*l2tab[256-m]);
276                     }
277                 }
278                 if(len < best_len[k]){
279                     best_len[k]= len;
280                     best_state[i][k]= j;
281                 }
282                 for(m=0; m<256; m++){
283                     if(occ[m]){
284                         newocc[    one_state[    m]] += occ[m]*   p ;
285                         newocc[256-one_state[256-m]] += occ[m]*(1-p);
286                     }
287                 }
288                 memcpy(occ, newocc, sizeof(occ));
289             }
290         }
291     }
292 }
293
294 static av_always_inline av_flatten void put_symbol_inline(RangeCoder *c, uint8_t *state, int v, int is_signed, uint64_t rc_stat[256][2], uint64_t rc_stat2[32][2]){
295     int i;
296
297 #define put_rac(C,S,B) \
298 do{\
299     if(rc_stat){\
300     rc_stat[*(S)][B]++;\
301         rc_stat2[(S)-state][B]++;\
302     }\
303     put_rac(C,S,B);\
304 }while(0)
305
306     if(v){
307         const int a= FFABS(v);
308         const int e= av_log2(a);
309         put_rac(c, state+0, 0);
310         if(e<=9){
311             for(i=0; i<e; i++){
312                 put_rac(c, state+1+i, 1);  //1..10
313             }
314             put_rac(c, state+1+i, 0);
315
316             for(i=e-1; i>=0; i--){
317                 put_rac(c, state+22+i, (a>>i)&1); //22..31
318             }
319
320             if(is_signed)
321                 put_rac(c, state+11 + e, v < 0); //11..21
322         }else{
323             for(i=0; i<e; i++){
324                 put_rac(c, state+1+FFMIN(i,9), 1);  //1..10
325             }
326             put_rac(c, state+1+9, 0);
327
328             for(i=e-1; i>=0; i--){
329                 put_rac(c, state+22+FFMIN(i,9), (a>>i)&1); //22..31
330             }
331
332             if(is_signed)
333                 put_rac(c, state+11 + 10, v < 0); //11..21
334         }
335     }else{
336         put_rac(c, state+0, 1);
337     }
338 #undef put_rac
339 }
340
341 static av_noinline void put_symbol(RangeCoder *c, uint8_t *state, int v, int is_signed){
342     put_symbol_inline(c, state, v, is_signed, NULL, NULL);
343 }
344
345 static inline av_flatten int get_symbol_inline(RangeCoder *c, uint8_t *state, int is_signed){
346     if(get_rac(c, state+0))
347         return 0;
348     else{
349         int i, e, a;
350         e= 0;
351         while(get_rac(c, state+1 + FFMIN(e,9))){ //1..10
352             e++;
353         }
354
355         a= 1;
356         for(i=e-1; i>=0; i--){
357             a += a + get_rac(c, state+22 + FFMIN(i,9)); //22..31
358         }
359
360         e= -(is_signed && get_rac(c, state+11 + FFMIN(e, 10))); //11..21
361         return (a^e)-e;
362     }
363 }
364
365 static av_noinline int get_symbol(RangeCoder *c, uint8_t *state, int is_signed){
366     return get_symbol_inline(c, state, is_signed);
367 }
368
369 static inline void update_vlc_state(VlcState * const state, const int v){
370     int drift= state->drift;
371     int count= state->count;
372     state->error_sum += FFABS(v);
373     drift += v;
374
375     if(count == 128){ //FIXME variable
376         count >>= 1;
377         drift >>= 1;
378         state->error_sum >>= 1;
379     }
380     count++;
381
382     if(drift <= -count){
383         if(state->bias > -128) state->bias--;
384
385         drift += count;
386         if(drift <= -count)
387             drift= -count + 1;
388     }else if(drift > 0){
389         if(state->bias <  127) state->bias++;
390
391         drift -= count;
392         if(drift > 0)
393             drift= 0;
394     }
395
396     state->drift= drift;
397     state->count= count;
398 }
399
400 static inline void put_vlc_symbol(PutBitContext *pb, VlcState * const state, int v, int bits){
401     int i, k, code;
402 //printf("final: %d ", v);
403     v = fold(v - state->bias, bits);
404
405     i= state->count;
406     k=0;
407     while(i < state->error_sum){ //FIXME optimize
408         k++;
409         i += i;
410     }
411
412     assert(k<=8);
413
414 #if 0 // JPEG LS
415     if(k==0 && 2*state->drift <= - state->count) code= v ^ (-1);
416     else                                         code= v;
417 #else
418      code= v ^ ((2*state->drift + state->count)>>31);
419 #endif
420
421 //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);
422     set_sr_golomb(pb, code, k, 12, bits);
423
424     update_vlc_state(state, v);
425 }
426
427 static inline int get_vlc_symbol(GetBitContext *gb, VlcState * const state, int bits){
428     int k, i, v, ret;
429
430     i= state->count;
431     k=0;
432     while(i < state->error_sum){ //FIXME optimize
433         k++;
434         i += i;
435     }
436
437     assert(k<=8);
438
439     v= get_sr_golomb(gb, k, 12, bits);
440 //printf("v:%d bias:%d error:%d drift:%d count:%d k:%d", v, state->bias, state->error_sum, state->drift, state->count, k);
441
442 #if 0 // JPEG LS
443     if(k==0 && 2*state->drift <= - state->count) v ^= (-1);
444 #else
445      v ^= ((2*state->drift + state->count)>>31);
446 #endif
447
448     ret= fold(v + state->bias, bits);
449
450     update_vlc_state(state, v);
451 //printf("final: %d\n", ret);
452     return ret;
453 }
454
455 #if CONFIG_FFV1_ENCODER
456 static av_always_inline int encode_line(FFV1Context *s, int w,
457                                         int16_t *sample[3],
458                                         int plane_index, int bits)
459 {
460     PlaneContext * const p= &s->plane[plane_index];
461     RangeCoder * const c= &s->c;
462     int x;
463     int run_index= s->run_index;
464     int run_count=0;
465     int run_mode=0;
466
467     if(s->ac){
468         if(c->bytestream_end - c->bytestream < w*20){
469             av_log(s->avctx, AV_LOG_ERROR, "encoded frame too large\n");
470             return -1;
471         }
472     }else{
473         if(s->pb.buf_end - s->pb.buf - (put_bits_count(&s->pb)>>3) < w*4){
474             av_log(s->avctx, AV_LOG_ERROR, "encoded frame too large\n");
475             return -1;
476         }
477     }
478
479     for(x=0; x<w; x++){
480         int diff, context;
481
482         context= get_context(p, sample[0]+x, sample[1]+x, sample[2]+x);
483         diff= sample[0][x] - predict(sample[0]+x, sample[1]+x);
484
485         if(context < 0){
486             context = -context;
487             diff= -diff;
488         }
489
490         diff= fold(diff, bits);
491
492         if(s->ac){
493             if(s->flags & CODEC_FLAG_PASS1){
494                 put_symbol_inline(c, p->state[context], diff, 1, s->rc_stat, s->rc_stat2[p->quant_table_index][context]);
495             }else{
496                 put_symbol_inline(c, p->state[context], diff, 1, NULL, NULL);
497             }
498         }else{
499             if(context == 0) run_mode=1;
500
501             if(run_mode){
502
503                 if(diff){
504                     while(run_count >= 1<<ff_log2_run[run_index]){
505                         run_count -= 1<<ff_log2_run[run_index];
506                         run_index++;
507                         put_bits(&s->pb, 1, 1);
508                     }
509
510                     put_bits(&s->pb, 1 + ff_log2_run[run_index], run_count);
511                     if(run_index) run_index--;
512                     run_count=0;
513                     run_mode=0;
514                     if(diff>0) diff--;
515                 }else{
516                     run_count++;
517                 }
518             }
519
520 //            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));
521
522             if(run_mode == 0)
523                 put_vlc_symbol(&s->pb, &p->vlc_state[context], diff, bits);
524         }
525     }
526     if(run_mode){
527         while(run_count >= 1<<ff_log2_run[run_index]){
528             run_count -= 1<<ff_log2_run[run_index];
529             run_index++;
530             put_bits(&s->pb, 1, 1);
531         }
532
533         if(run_count)
534             put_bits(&s->pb, 1, 1);
535     }
536     s->run_index= run_index;
537
538     return 0;
539 }
540
541 static void encode_plane(FFV1Context *s, uint8_t *src, int w, int h, int stride, int plane_index){
542     int x,y,i;
543     const int ring_size= s->avctx->context_model ? 3 : 2;
544     int16_t *sample[3];
545     s->run_index=0;
546
547     memset(s->sample_buffer, 0, ring_size*(w+6)*sizeof(*s->sample_buffer));
548
549     for(y=0; y<h; y++){
550         for(i=0; i<ring_size; i++)
551             sample[i]= s->sample_buffer + (w+6)*((h+i-y)%ring_size) + 3;
552
553         sample[0][-1]= sample[1][0  ];
554         sample[1][ w]= sample[1][w-1];
555 //{START_TIMER
556         if(s->bits_per_raw_sample<=8){
557             for(x=0; x<w; x++){
558                 sample[0][x]= src[x + stride*y];
559             }
560             encode_line(s, w, sample, plane_index, 8);
561         }else{
562             if(s->packed_at_lsb){
563                 for(x=0; x<w; x++){
564                     sample[0][x]= ((uint16_t*)(src + stride*y))[x];
565                 }
566             }else{
567                 for(x=0; x<w; x++){
568                     sample[0][x]= ((uint16_t*)(src + stride*y))[x] >> (16 - s->bits_per_raw_sample);
569                 }
570             }
571             encode_line(s, w, sample, plane_index, s->bits_per_raw_sample);
572         }
573 //STOP_TIMER("encode line")}
574     }
575 }
576
577 static void encode_rgb_frame(FFV1Context *s, uint32_t *src, int w, int h, int stride){
578     int x, y, p, i;
579     const int ring_size= s->avctx->context_model ? 3 : 2;
580     int16_t *sample[4][3];
581     s->run_index=0;
582
583     memset(s->sample_buffer, 0, ring_size*4*(w+6)*sizeof(*s->sample_buffer));
584
585     for(y=0; y<h; y++){
586         for(i=0; i<ring_size; i++)
587             for(p=0; p<4; p++)
588                 sample[p][i]= s->sample_buffer + p*ring_size*(w+6) + ((h+i-y)%ring_size)*(w+6) + 3;
589
590         for(x=0; x<w; x++){
591             unsigned v= src[x + stride*y];
592             int b= v&0xFF;
593             int g= (v>>8)&0xFF;
594             int r= (v>>16)&0xFF;
595             int a=  v>>24;
596
597             b -= g;
598             r -= g;
599             g += (b + r)>>2;
600             b += 0x100;
601             r += 0x100;
602
603 //            assert(g>=0 && b>=0 && r>=0);
604 //            assert(g<256 && b<512 && r<512);
605             sample[0][0][x]= g;
606             sample[1][0][x]= b;
607             sample[2][0][x]= r;
608             sample[3][0][x]= a;
609         }
610         for(p=0; p<3 + s->transparency; p++){
611             sample[p][0][-1]= sample[p][1][0  ];
612             sample[p][1][ w]= sample[p][1][w-1];
613             encode_line(s, w, sample[p], (p+1)/2, 9);
614         }
615     }
616 }
617
618 static void write_quant_table(RangeCoder *c, int16_t *quant_table){
619     int last=0;
620     int i;
621     uint8_t state[CONTEXT_SIZE];
622     memset(state, 128, sizeof(state));
623
624     for(i=1; i<128 ; i++){
625         if(quant_table[i] != quant_table[i-1]){
626             put_symbol(c, state, i-last-1, 0);
627             last= i;
628         }
629     }
630     put_symbol(c, state, i-last-1, 0);
631 }
632
633 static void write_quant_tables(RangeCoder *c, int16_t quant_table[MAX_CONTEXT_INPUTS][256]){
634     int i;
635     for(i=0; i<5; i++)
636         write_quant_table(c, quant_table[i]);
637 }
638
639 static void write_header(FFV1Context *f){
640     uint8_t state[CONTEXT_SIZE];
641     int i, j;
642     RangeCoder * const c= &f->slice_context[0]->c;
643
644     memset(state, 128, sizeof(state));
645
646     if(f->version < 2){
647         put_symbol(c, state, f->version, 0);
648         put_symbol(c, state, f->ac, 0);
649         if(f->ac>1){
650             for(i=1; i<256; i++){
651                 put_symbol(c, state, f->state_transition[i] - c->one_state[i], 1);
652             }
653         }
654         put_symbol(c, state, f->colorspace, 0); //YUV cs type
655         if(f->version>0)
656             put_symbol(c, state, f->bits_per_raw_sample, 0);
657         put_rac(c, state, f->chroma_planes);
658         put_symbol(c, state, f->chroma_h_shift, 0);
659         put_symbol(c, state, f->chroma_v_shift, 0);
660         put_rac(c, state, f->transparency);
661
662         write_quant_tables(c, f->quant_table);
663     }else{
664         put_symbol(c, state, f->slice_count, 0);
665         if(f->version < 3){
666         for(i=0; i<f->slice_count; i++){
667             FFV1Context *fs= f->slice_context[i];
668             put_symbol(c, state, (fs->slice_x     +1)*f->num_h_slices / f->width   , 0);
669             put_symbol(c, state, (fs->slice_y     +1)*f->num_v_slices / f->height  , 0);
670             put_symbol(c, state, (fs->slice_width +1)*f->num_h_slices / f->width -1, 0);
671             put_symbol(c, state, (fs->slice_height+1)*f->num_v_slices / f->height-1, 0);
672             for(j=0; j<f->plane_count; j++){
673                 put_symbol(c, state, f->plane[j].quant_table_index, 0);
674                 av_assert0(f->plane[j].quant_table_index == f->avctx->context_model);
675             }
676         }
677         }
678     }
679 }
680 #endif /* CONFIG_FFV1_ENCODER */
681
682 static av_cold int common_init(AVCodecContext *avctx){
683     FFV1Context *s = avctx->priv_data;
684
685     s->avctx= avctx;
686     s->flags= avctx->flags;
687
688     avcodec_get_frame_defaults(&s->picture);
689
690     ff_dsputil_init(&s->dsp, avctx);
691
692     s->width = avctx->width;
693     s->height= avctx->height;
694
695     assert(s->width && s->height);
696     //defaults
697     s->num_h_slices=1;
698     s->num_v_slices=1;
699
700
701     return 0;
702 }
703
704 static int init_slice_state(FFV1Context *f, FFV1Context *fs){
705     int j;
706
707         fs->plane_count= f->plane_count;
708         fs->transparency= f->transparency;
709         for(j=0; j<f->plane_count; j++){
710             PlaneContext * const p= &fs->plane[j];
711
712             if(fs->ac){
713                 if(!p->    state) p->    state= av_malloc(CONTEXT_SIZE*p->context_count*sizeof(uint8_t));
714                 if(!p->    state)
715                     return AVERROR(ENOMEM);
716             }else{
717                 if(!p->vlc_state) p->vlc_state= av_malloc(p->context_count*sizeof(VlcState));
718                 if(!p->vlc_state)
719                     return AVERROR(ENOMEM);
720             }
721         }
722
723         if (fs->ac>1){
724             //FIXME only redo if state_transition changed
725             for(j=1; j<256; j++){
726                 fs->c.one_state [    j]= fs->state_transition[j];
727                 fs->c.zero_state[256-j]= 256-fs->c.one_state [j];
728             }
729         }
730
731     return 0;
732 }
733
734 static int init_slices_state(FFV1Context *f){
735     int i;
736     for(i=0; i<f->slice_count; i++){
737         FFV1Context *fs= f->slice_context[i];
738         if(init_slice_state(f, fs) < 0)
739             return -1;
740     }
741     return 0;
742 }
743
744 static av_cold int init_slice_contexts(FFV1Context *f){
745     int i;
746
747     f->slice_count= f->num_h_slices * f->num_v_slices;
748
749     for(i=0; i<f->slice_count; i++){
750         FFV1Context *fs= av_mallocz(sizeof(*fs));
751         int sx= i % f->num_h_slices;
752         int sy= i / f->num_h_slices;
753         int sxs= f->avctx->width * sx    / f->num_h_slices;
754         int sxe= f->avctx->width *(sx+1) / f->num_h_slices;
755         int sys= f->avctx->height* sy    / f->num_v_slices;
756         int sye= f->avctx->height*(sy+1) / f->num_v_slices;
757         f->slice_context[i]= fs;
758         memcpy(fs, f, sizeof(*fs));
759         memset(fs->rc_stat2, 0, sizeof(fs->rc_stat2));
760
761         fs->slice_width = sxe - sxs;
762         fs->slice_height= sye - sys;
763         fs->slice_x     = sxs;
764         fs->slice_y     = sys;
765
766         fs->sample_buffer = av_malloc(3*4 * (fs->width+6) * sizeof(*fs->sample_buffer));
767         if (!fs->sample_buffer)
768             return AVERROR(ENOMEM);
769     }
770     return 0;
771 }
772
773 static int allocate_initial_states(FFV1Context *f){
774     int i;
775
776     for(i=0; i<f->quant_table_count; i++){
777         f->initial_states[i]= av_malloc(f->context_count[i]*sizeof(*f->initial_states[i]));
778         if(!f->initial_states[i])
779             return AVERROR(ENOMEM);
780         memset(f->initial_states[i], 128, f->context_count[i]*sizeof(*f->initial_states[i]));
781     }
782     return 0;
783 }
784
785 #if CONFIG_FFV1_ENCODER
786 static int write_extra_header(FFV1Context *f){
787     RangeCoder * const c= &f->c;
788     uint8_t state[CONTEXT_SIZE];
789     int i, j, k;
790     uint8_t state2[32][CONTEXT_SIZE];
791     unsigned v;
792
793     memset(state2, 128, sizeof(state2));
794     memset(state, 128, sizeof(state));
795
796     f->avctx->extradata= av_malloc(f->avctx->extradata_size= 10000 + (11*11*5*5*5+11*11*11)*32);
797     ff_init_range_encoder(c, f->avctx->extradata, f->avctx->extradata_size);
798     ff_build_rac_states(c, 0.05*(1LL<<32), 256-8);
799
800     put_symbol(c, state, f->version, 0);
801     if(f->version > 2)
802         put_symbol(c, state, f->minor_version, 0);
803     put_symbol(c, state, f->ac, 0);
804     if(f->ac>1){
805         for(i=1; i<256; i++){
806             put_symbol(c, state, f->state_transition[i] - c->one_state[i], 1);
807         }
808     }
809     put_symbol(c, state, f->colorspace, 0); //YUV cs type
810     put_symbol(c, state, f->bits_per_raw_sample, 0);
811     put_rac(c, state, f->chroma_planes);
812     put_symbol(c, state, f->chroma_h_shift, 0);
813     put_symbol(c, state, f->chroma_v_shift, 0);
814     put_rac(c, state, f->transparency);
815     put_symbol(c, state, f->num_h_slices-1, 0);
816     put_symbol(c, state, f->num_v_slices-1, 0);
817
818     put_symbol(c, state, f->quant_table_count, 0);
819     for(i=0; i<f->quant_table_count; i++)
820         write_quant_tables(c, f->quant_tables[i]);
821
822     for(i=0; i<f->quant_table_count; i++){
823         for(j=0; j<f->context_count[i]*CONTEXT_SIZE; j++)
824             if(f->initial_states[i] && f->initial_states[i][0][j] != 128)
825                 break;
826         if(j<f->context_count[i]*CONTEXT_SIZE){
827             put_rac(c, state, 1);
828             for(j=0; j<f->context_count[i]; j++){
829                 for(k=0; k<CONTEXT_SIZE; k++){
830                     int pred= j ? f->initial_states[i][j-1][k] : 128;
831                     put_symbol(c, state2[k], (int8_t)(f->initial_states[i][j][k]-pred), 1);
832                 }
833             }
834         }else{
835             put_rac(c, state, 0);
836         }
837     }
838
839     if(f->version > 2){
840         put_symbol(c, state, f->ec, 0);
841     }
842
843     f->avctx->extradata_size= ff_rac_terminate(c);
844     v = av_crc(av_crc_get_table(AV_CRC_32_IEEE), 0, f->avctx->extradata, f->avctx->extradata_size);
845     AV_WL32(f->avctx->extradata + f->avctx->extradata_size, v);
846     f->avctx->extradata_size += 4;
847
848     return 0;
849 }
850
851 static int sort_stt(FFV1Context *s, uint8_t stt[256]){
852     int i,i2,changed,print=0;
853
854     do{
855         changed=0;
856         for(i=12; i<244; i++){
857             for(i2=i+1; i2<245 && i2<i+4; i2++){
858 #define COST(old, new) \
859     s->rc_stat[old][0]*-log2((256-(new))/256.0)\
860    +s->rc_stat[old][1]*-log2(     (new) /256.0)
861
862 #define COST2(old, new) \
863     COST(old, new)\
864    +COST(256-(old), 256-(new))
865
866                 double size0= COST2(i, i ) + COST2(i2, i2);
867                 double sizeX= COST2(i, i2) + COST2(i2, i );
868                 if(sizeX < size0 && i!=128 && i2!=128){
869                     int j;
870                     FFSWAP(int, stt[    i], stt[    i2]);
871                     FFSWAP(int, s->rc_stat[i    ][0],s->rc_stat[    i2][0]);
872                     FFSWAP(int, s->rc_stat[i    ][1],s->rc_stat[    i2][1]);
873                     if(i != 256-i2){
874                         FFSWAP(int, stt[256-i], stt[256-i2]);
875                         FFSWAP(int, s->rc_stat[256-i][0],s->rc_stat[256-i2][0]);
876                         FFSWAP(int, s->rc_stat[256-i][1],s->rc_stat[256-i2][1]);
877                     }
878                     for(j=1; j<256; j++){
879                         if     (stt[j] == i ) stt[j] = i2;
880                         else if(stt[j] == i2) stt[j] = i ;
881                         if(i != 256-i2){
882                             if     (stt[256-j] == 256-i ) stt[256-j] = 256-i2;
883                             else if(stt[256-j] == 256-i2) stt[256-j] = 256-i ;
884                         }
885                     }
886                     print=changed=1;
887                 }
888             }
889         }
890     }while(changed);
891     return print;
892 }
893
894 static av_cold int encode_init(AVCodecContext *avctx)
895 {
896     FFV1Context *s = avctx->priv_data;
897     int i, j, k, m;
898
899     common_init(avctx);
900
901     s->version=0;
902
903     if((avctx->flags & (CODEC_FLAG_PASS1|CODEC_FLAG_PASS2)) || avctx->slices>1)
904         s->version = FFMAX(s->version, 2);
905
906     if(avctx->level == 3){
907         s->version = 3;
908         s->ec = 1;
909     }
910
911     if(s->version >= 2 && avctx->strict_std_compliance > FF_COMPLIANCE_EXPERIMENTAL) {
912         av_log(avctx, AV_LOG_ERROR, "Version 2 needed for requested features but version 2 is experimental and not enabled\n");
913         return -1;
914     }
915
916     s->ac= avctx->coder_type ? 2:0;
917
918     if(s->ac>1)
919         for(i=1; i<256; i++)
920             s->state_transition[i]=ver2_state[i];
921
922     s->plane_count=3;
923     switch(avctx->pix_fmt){
924     case PIX_FMT_YUV444P9:
925     case PIX_FMT_YUV422P9:
926     case PIX_FMT_YUV420P9:
927         if (!avctx->bits_per_raw_sample)
928             s->bits_per_raw_sample = 9;
929     case PIX_FMT_YUV444P10:
930     case PIX_FMT_YUV420P10:
931     case PIX_FMT_YUV422P10:
932         s->packed_at_lsb = 1;
933         if (!avctx->bits_per_raw_sample && !s->bits_per_raw_sample)
934             s->bits_per_raw_sample = 10;
935     case PIX_FMT_GRAY16:
936     case PIX_FMT_YUV444P16:
937     case PIX_FMT_YUV422P16:
938     case PIX_FMT_YUV420P16:
939         if (!avctx->bits_per_raw_sample && !s->bits_per_raw_sample) {
940             s->bits_per_raw_sample = 16;
941         } else if (!s->bits_per_raw_sample){
942             s->bits_per_raw_sample = avctx->bits_per_raw_sample;
943         }
944         if(s->bits_per_raw_sample <=8){
945             av_log(avctx, AV_LOG_ERROR, "bits_per_raw_sample invalid\n");
946             return -1;
947         }
948         if(!s->ac){
949             av_log(avctx, AV_LOG_ERROR, "bits_per_raw_sample of more than 8 needs -coder 1 currently\n");
950             return -1;
951         }
952         s->version= FFMAX(s->version, 1);
953     case PIX_FMT_GRAY8:
954     case PIX_FMT_YUV444P:
955     case PIX_FMT_YUV440P:
956     case PIX_FMT_YUV422P:
957     case PIX_FMT_YUV420P:
958     case PIX_FMT_YUV411P:
959     case PIX_FMT_YUV410P:
960         s->chroma_planes= av_pix_fmt_descriptors[avctx->pix_fmt].nb_components < 3 ? 0 : 1;
961         s->colorspace= 0;
962         break;
963     case PIX_FMT_YUVA444P:
964     case PIX_FMT_YUVA420P:
965         s->chroma_planes= 1;
966         s->colorspace= 0;
967         s->transparency= 1;
968         break;
969     case PIX_FMT_RGB32:
970         s->colorspace= 1;
971         s->transparency= 1;
972         break;
973     case PIX_FMT_0RGB32:
974         s->colorspace= 1;
975         break;
976     default:
977         av_log(avctx, AV_LOG_ERROR, "format not supported\n");
978         return -1;
979     }
980     if (s->transparency) {
981         av_log(avctx, AV_LOG_WARNING, "Storing alpha plane, this will require a recent FFV1 decoder to playback!\n");
982     }
983     if (avctx->context_model > 1U) {
984         av_log(avctx, AV_LOG_ERROR, "Invalid context model %d, valid values are 0 and 1\n", avctx->context_model);
985         return AVERROR(EINVAL);
986     }
987
988     for(i=0; i<256; i++){
989         s->quant_table_count=2;
990         if(s->bits_per_raw_sample <=8){
991             s->quant_tables[0][0][i]=           quant11[i];
992             s->quant_tables[0][1][i]=        11*quant11[i];
993             s->quant_tables[0][2][i]=     11*11*quant11[i];
994             s->quant_tables[1][0][i]=           quant11[i];
995             s->quant_tables[1][1][i]=        11*quant11[i];
996             s->quant_tables[1][2][i]=     11*11*quant5 [i];
997             s->quant_tables[1][3][i]=   5*11*11*quant5 [i];
998             s->quant_tables[1][4][i]= 5*5*11*11*quant5 [i];
999         }else{
1000             s->quant_tables[0][0][i]=           quant9_10bit[i];
1001             s->quant_tables[0][1][i]=        11*quant9_10bit[i];
1002             s->quant_tables[0][2][i]=     11*11*quant9_10bit[i];
1003             s->quant_tables[1][0][i]=           quant9_10bit[i];
1004             s->quant_tables[1][1][i]=        11*quant9_10bit[i];
1005             s->quant_tables[1][2][i]=     11*11*quant5_10bit[i];
1006             s->quant_tables[1][3][i]=   5*11*11*quant5_10bit[i];
1007             s->quant_tables[1][4][i]= 5*5*11*11*quant5_10bit[i];
1008         }
1009     }
1010     s->context_count[0]= (11*11*11+1)/2;
1011     s->context_count[1]= (11*11*5*5*5+1)/2;
1012     memcpy(s->quant_table, s->quant_tables[avctx->context_model], sizeof(s->quant_table));
1013
1014     for(i=0; i<s->plane_count; i++){
1015         PlaneContext * const p= &s->plane[i];
1016
1017         memcpy(p->quant_table, s->quant_table, sizeof(p->quant_table));
1018         p->quant_table_index= avctx->context_model;
1019         p->context_count= s->context_count[p->quant_table_index];
1020     }
1021
1022     if(allocate_initial_states(s) < 0)
1023         return AVERROR(ENOMEM);
1024
1025     avctx->coded_frame= &s->picture;
1026     if(!s->transparency)
1027         s->plane_count= 2;
1028     avcodec_get_chroma_sub_sample(avctx->pix_fmt, &s->chroma_h_shift, &s->chroma_v_shift);
1029
1030     s->picture_number=0;
1031
1032     if(avctx->flags & (CODEC_FLAG_PASS1|CODEC_FLAG_PASS2)){
1033         for(i=0; i<s->quant_table_count; i++){
1034             s->rc_stat2[i]= av_mallocz(s->context_count[i]*sizeof(*s->rc_stat2[i]));
1035             if(!s->rc_stat2[i])
1036                 return AVERROR(ENOMEM);
1037         }
1038     }
1039     if(avctx->stats_in){
1040         char *p= avctx->stats_in;
1041         uint8_t best_state[256][256];
1042         int gob_count=0;
1043         char *next;
1044
1045         av_assert0(s->version>=2);
1046
1047         for(;;){
1048             for(j=0; j<256; j++){
1049                 for(i=0; i<2; i++){
1050                     s->rc_stat[j][i]= strtol(p, &next, 0);
1051                     if(next==p){
1052                         av_log(avctx, AV_LOG_ERROR, "2Pass file invalid at %d %d [%s]\n", j,i,p);
1053                         return -1;
1054                     }
1055                     p=next;
1056                 }
1057             }
1058             for(i=0; i<s->quant_table_count; i++){
1059                 for(j=0; j<s->context_count[i]; j++){
1060                     for(k=0; k<32; k++){
1061                         for(m=0; m<2; m++){
1062                             s->rc_stat2[i][j][k][m]= strtol(p, &next, 0);
1063                             if(next==p){
1064                                 av_log(avctx, AV_LOG_ERROR, "2Pass file invalid at %d %d %d %d [%s]\n", i,j,k,m,p);
1065                                 return -1;
1066                             }
1067                             p=next;
1068                         }
1069                     }
1070                 }
1071             }
1072             gob_count= strtol(p, &next, 0);
1073             if(next==p || gob_count <0){
1074                 av_log(avctx, AV_LOG_ERROR, "2Pass file invalid\n");
1075                 return -1;
1076             }
1077             p=next;
1078             while(*p=='\n' || *p==' ') p++;
1079             if(p[0]==0) break;
1080         }
1081         sort_stt(s, s->state_transition);
1082
1083         find_best_state(best_state, s->state_transition);
1084
1085         for(i=0; i<s->quant_table_count; i++){
1086             for(j=0; j<s->context_count[i]; j++){
1087                 for(k=0; k<32; k++){
1088                     double p= 128;
1089                     if(s->rc_stat2[i][j][k][0]+s->rc_stat2[i][j][k][1]){
1090                         p=256.0*s->rc_stat2[i][j][k][1] / (s->rc_stat2[i][j][k][0]+s->rc_stat2[i][j][k][1]);
1091                     }
1092                     s->initial_states[i][j][k]= best_state[av_clip(round(p), 1, 255)][av_clip((s->rc_stat2[i][j][k][0]+s->rc_stat2[i][j][k][1])/gob_count, 0, 255)];
1093                 }
1094             }
1095         }
1096     }
1097
1098     if(s->version>1){
1099         for(s->num_v_slices=2; s->num_v_slices<9; s->num_v_slices++){
1100             for(s->num_h_slices=s->num_v_slices; s->num_h_slices<2*s->num_v_slices; s->num_h_slices++){
1101                 if(avctx->slices == s->num_h_slices * s->num_v_slices && avctx->slices <= 64)
1102                     goto slices_ok;
1103             }
1104         }
1105         av_log(avctx, AV_LOG_ERROR, "Unsupported number %d of slices requested, please specify a supported number with -slices\n", avctx->slices);
1106         return -1;
1107         slices_ok:
1108         write_extra_header(s);
1109     }
1110
1111     if(init_slice_contexts(s) < 0)
1112         return -1;
1113     if(init_slices_state(s) < 0)
1114         return -1;
1115
1116 #define STATS_OUT_SIZE 1024*1024*6
1117     if(avctx->flags & CODEC_FLAG_PASS1){
1118         avctx->stats_out= av_mallocz(STATS_OUT_SIZE);
1119         for(i=0; i<s->quant_table_count; i++){
1120             for(j=0; j<s->slice_count; j++){
1121                 FFV1Context *sf= s->slice_context[j];
1122                 av_assert0(!sf->rc_stat2[i]);
1123                 sf->rc_stat2[i]= av_mallocz(s->context_count[i]*sizeof(*sf->rc_stat2[i]));
1124                 if(!sf->rc_stat2[i])
1125                     return AVERROR(ENOMEM);
1126             }
1127         }
1128     }
1129
1130     return 0;
1131 }
1132 #endif /* CONFIG_FFV1_ENCODER */
1133
1134
1135 static void clear_slice_state(FFV1Context *f, FFV1Context *fs){
1136     int i, j;
1137
1138         for(i=0; i<f->plane_count; i++){
1139             PlaneContext *p= &fs->plane[i];
1140
1141             p->interlace_bit_state[0]= 128;
1142             p->interlace_bit_state[1]= 128;
1143
1144             if(fs->ac){
1145                 if(f->initial_states[p->quant_table_index]){
1146                     memcpy(p->state, f->initial_states[p->quant_table_index], CONTEXT_SIZE*p->context_count);
1147                 }else
1148                 memset(p->state, 128, CONTEXT_SIZE*p->context_count);
1149             }else{
1150                 for(j=0; j<p->context_count; j++){
1151                     p->vlc_state[j].drift= 0;
1152                     p->vlc_state[j].error_sum= 4; //FFMAX((RANGE + 32)/64, 2);
1153                     p->vlc_state[j].bias= 0;
1154                     p->vlc_state[j].count= 1;
1155                 }
1156             }
1157         }
1158 }
1159
1160 static void clear_state(FFV1Context *f){
1161     int si;
1162
1163     for(si=0; si<f->slice_count; si++){
1164         FFV1Context *fs= f->slice_context[si];
1165         clear_slice_state(f, fs);
1166     }
1167 }
1168
1169 #if CONFIG_FFV1_ENCODER
1170
1171 static void encode_slice_header(FFV1Context *f, FFV1Context *fs){
1172     RangeCoder *c = &fs->c;
1173     uint8_t state[CONTEXT_SIZE];
1174     int j;
1175     memset(state, 128, sizeof(state));
1176
1177     put_symbol(c, state, (fs->slice_x     +1)*f->num_h_slices / f->width   , 0);
1178     put_symbol(c, state, (fs->slice_y     +1)*f->num_v_slices / f->height  , 0);
1179     put_symbol(c, state, (fs->slice_width +1)*f->num_h_slices / f->width -1, 0);
1180     put_symbol(c, state, (fs->slice_height+1)*f->num_v_slices / f->height-1, 0);
1181     for(j=0; j<f->plane_count; j++){
1182         put_symbol(c, state, f->plane[j].quant_table_index, 0);
1183         av_assert0(f->plane[j].quant_table_index == f->avctx->context_model);
1184     }
1185     if(!f->picture.interlaced_frame) put_symbol(c, state, 3, 0);
1186     else                             put_symbol(c, state, 1 + !f->picture.top_field_first, 0);
1187     put_symbol(c, state, f->picture.sample_aspect_ratio.num, 0);
1188     put_symbol(c, state, f->picture.sample_aspect_ratio.den, 0);
1189 }
1190
1191 static int encode_slice(AVCodecContext *c, void *arg){
1192     FFV1Context *fs= *(void**)arg;
1193     FFV1Context *f= fs->avctx->priv_data;
1194     int width = fs->slice_width;
1195     int height= fs->slice_height;
1196     int x= fs->slice_x;
1197     int y= fs->slice_y;
1198     AVFrame * const p= &f->picture;
1199     const int ps= (f->bits_per_raw_sample>8)+1;
1200
1201     if(f->version > 2){
1202         encode_slice_header(f, fs);
1203     }
1204     if(!fs->ac){
1205         fs->ac_byte_count = f->version > 2 || (!x&&!y) ? ff_rac_terminate(&fs->c) : 0;
1206         init_put_bits(&fs->pb, fs->c.bytestream_start + fs->ac_byte_count, fs->c.bytestream_end - fs->c.bytestream_start - fs->ac_byte_count);
1207     }
1208
1209     if(f->colorspace==0){
1210         const int chroma_width = -((-width )>>f->chroma_h_shift);
1211         const int chroma_height= -((-height)>>f->chroma_v_shift);
1212         const int cx= x>>f->chroma_h_shift;
1213         const int cy= y>>f->chroma_v_shift;
1214
1215         encode_plane(fs, p->data[0] + ps*x + y*p->linesize[0], width, height, p->linesize[0], 0);
1216
1217         if (f->chroma_planes){
1218             encode_plane(fs, p->data[1] + ps*cx+cy*p->linesize[1], chroma_width, chroma_height, p->linesize[1], 1);
1219             encode_plane(fs, p->data[2] + ps*cx+cy*p->linesize[2], chroma_width, chroma_height, p->linesize[2], 1);
1220         }
1221         if (fs->transparency)
1222             encode_plane(fs, p->data[3] + ps*x + y*p->linesize[3], width, height, p->linesize[3], 2);
1223     }else{
1224         encode_rgb_frame(fs, (uint32_t*)(p->data[0]) + ps*x + y*(p->linesize[0]/4), width, height, p->linesize[0]/4);
1225     }
1226     emms_c();
1227
1228     return 0;
1229 }
1230
1231 static int encode_frame(AVCodecContext *avctx, AVPacket *pkt,
1232                         const AVFrame *pict, int *got_packet)
1233 {
1234     FFV1Context *f = avctx->priv_data;
1235     RangeCoder * const c= &f->slice_context[0]->c;
1236     AVFrame * const p= &f->picture;
1237     int used_count= 0;
1238     uint8_t keystate=128;
1239     uint8_t *buf_p;
1240     int i, ret;
1241
1242     if ((ret = ff_alloc_packet2(avctx, pkt, avctx->width*avctx->height*((8*2+1+1)*4)/8
1243                                   + FF_MIN_BUFFER_SIZE)) < 0)
1244         return ret;
1245
1246     ff_init_range_encoder(c, pkt->data, pkt->size);
1247     ff_build_rac_states(c, 0.05*(1LL<<32), 256-8);
1248
1249     *p = *pict;
1250     p->pict_type= AV_PICTURE_TYPE_I;
1251
1252     if(avctx->gop_size==0 || f->picture_number % avctx->gop_size == 0){
1253         put_rac(c, &keystate, 1);
1254         p->key_frame= 1;
1255         f->gob_count++;
1256         write_header(f);
1257         clear_state(f);
1258     }else{
1259         put_rac(c, &keystate, 0);
1260         p->key_frame= 0;
1261     }
1262
1263     if (f->ac>1){
1264         int i;
1265         for(i=1; i<256; i++){
1266             c->one_state[i]= f->state_transition[i];
1267             c->zero_state[256-i]= 256-c->one_state[i];
1268         }
1269     }
1270
1271     for(i=1; i<f->slice_count; i++){
1272         FFV1Context *fs= f->slice_context[i];
1273         uint8_t *start = pkt->data + (pkt->size-used_count)*i/f->slice_count;
1274         int len = pkt->size/f->slice_count;
1275
1276         ff_init_range_encoder(&fs->c, start, len);
1277     }
1278     avctx->execute(avctx, encode_slice, &f->slice_context[0], NULL, f->slice_count, sizeof(void*));
1279
1280     buf_p = pkt->data;
1281     for(i=0; i<f->slice_count; i++){
1282         FFV1Context *fs= f->slice_context[i];
1283         int bytes;
1284
1285         if(fs->ac){
1286             uint8_t state=128;
1287             put_rac(&fs->c, &state, 0);
1288             bytes= ff_rac_terminate(&fs->c);
1289         }else{
1290             flush_put_bits(&fs->pb); //nicer padding FIXME
1291             bytes= fs->ac_byte_count + (put_bits_count(&fs->pb)+7)/8;
1292         }
1293         if(i>0 || f->ec){
1294             av_assert0(bytes < pkt->size/f->slice_count);
1295             memmove(buf_p, fs->c.bytestream_start, bytes);
1296             av_assert0(bytes < (1<<24));
1297             AV_WB24(buf_p+bytes, bytes);
1298             bytes+=3;
1299         }
1300         if(f->ec){
1301             unsigned v;
1302             buf_p[bytes++] = 0;
1303             v = av_crc(av_crc_get_table(AV_CRC_32_IEEE), 0, buf_p, bytes);
1304             AV_WL32(buf_p + bytes, v); bytes += 4;
1305         }
1306         buf_p += bytes;
1307     }
1308
1309     if((avctx->flags&CODEC_FLAG_PASS1) && (f->picture_number&31)==0){
1310         int j, k, m;
1311         char *p= avctx->stats_out;
1312         char *end= p + STATS_OUT_SIZE;
1313
1314         memset(f->rc_stat, 0, sizeof(f->rc_stat));
1315         for(i=0; i<f->quant_table_count; i++)
1316             memset(f->rc_stat2[i], 0, f->context_count[i]*sizeof(*f->rc_stat2[i]));
1317
1318         for(j=0; j<f->slice_count; j++){
1319             FFV1Context *fs= f->slice_context[j];
1320             for(i=0; i<256; i++){
1321                 f->rc_stat[i][0] += fs->rc_stat[i][0];
1322                 f->rc_stat[i][1] += fs->rc_stat[i][1];
1323             }
1324             for(i=0; i<f->quant_table_count; i++){
1325                 for(k=0; k<f->context_count[i]; k++){
1326                     for(m=0; m<32; m++){
1327                         f->rc_stat2[i][k][m][0] += fs->rc_stat2[i][k][m][0];
1328                         f->rc_stat2[i][k][m][1] += fs->rc_stat2[i][k][m][1];
1329                     }
1330                 }
1331             }
1332         }
1333
1334         for(j=0; j<256; j++){
1335             snprintf(p, end-p, "%"PRIu64" %"PRIu64" ", f->rc_stat[j][0], f->rc_stat[j][1]);
1336             p+= strlen(p);
1337         }
1338         snprintf(p, end-p, "\n");
1339
1340         for(i=0; i<f->quant_table_count; i++){
1341             for(j=0; j<f->context_count[i]; j++){
1342                 for(m=0; m<32; m++){
1343                     snprintf(p, end-p, "%"PRIu64" %"PRIu64" ", f->rc_stat2[i][j][m][0], f->rc_stat2[i][j][m][1]);
1344                     p+= strlen(p);
1345                 }
1346             }
1347         }
1348         snprintf(p, end-p, "%d\n", f->gob_count);
1349     } else if(avctx->flags&CODEC_FLAG_PASS1)
1350         avctx->stats_out[0] = '\0';
1351
1352     f->picture_number++;
1353     pkt->size   = buf_p - pkt->data;
1354     pkt->flags |= AV_PKT_FLAG_KEY*p->key_frame;
1355     *got_packet = 1;
1356
1357     return 0;
1358 }
1359 #endif /* CONFIG_FFV1_ENCODER */
1360
1361 static av_cold int common_end(AVCodecContext *avctx){
1362     FFV1Context *s = avctx->priv_data;
1363     int i, j;
1364
1365     if (avctx->codec->decode && s->picture.data[0])
1366         avctx->release_buffer(avctx, &s->picture);
1367
1368     for(j=0; j<s->slice_count; j++){
1369         FFV1Context *fs= s->slice_context[j];
1370         for(i=0; i<s->plane_count; i++){
1371             PlaneContext *p= &fs->plane[i];
1372
1373             av_freep(&p->state);
1374             av_freep(&p->vlc_state);
1375         }
1376         av_freep(&fs->sample_buffer);
1377     }
1378
1379     av_freep(&avctx->stats_out);
1380     for(j=0; j<s->quant_table_count; j++){
1381         av_freep(&s->initial_states[j]);
1382         for(i=0; i<s->slice_count; i++){
1383             FFV1Context *sf= s->slice_context[i];
1384             av_freep(&sf->rc_stat2[j]);
1385         }
1386         av_freep(&s->rc_stat2[j]);
1387     }
1388
1389     for(i=0; i<s->slice_count; i++){
1390         av_freep(&s->slice_context[i]);
1391     }
1392
1393     return 0;
1394 }
1395
1396 static av_always_inline void decode_line(FFV1Context *s, int w,
1397                                          int16_t *sample[2],
1398                                          int plane_index, int bits)
1399 {
1400     PlaneContext * const p= &s->plane[plane_index];
1401     RangeCoder * const c= &s->c;
1402     int x;
1403     int run_count=0;
1404     int run_mode=0;
1405     int run_index= s->run_index;
1406
1407     for(x=0; x<w; x++){
1408         int diff, context, sign;
1409
1410         context= get_context(p, sample[1] + x, sample[0] + x, sample[1] + x);
1411         if(context < 0){
1412             context= -context;
1413             sign=1;
1414         }else
1415             sign=0;
1416
1417         av_assert2(context < p->context_count);
1418
1419         if(s->ac){
1420             diff= get_symbol_inline(c, p->state[context], 1);
1421         }else{
1422             if(context == 0 && run_mode==0) run_mode=1;
1423
1424             if(run_mode){
1425                 if(run_count==0 && run_mode==1){
1426                     if(get_bits1(&s->gb)){
1427                         run_count = 1<<ff_log2_run[run_index];
1428                         if(x + run_count <= w) run_index++;
1429                     }else{
1430                         if(ff_log2_run[run_index]) run_count = get_bits(&s->gb, ff_log2_run[run_index]);
1431                         else run_count=0;
1432                         if(run_index) run_index--;
1433                         run_mode=2;
1434                     }
1435                 }
1436                 run_count--;
1437                 if(run_count < 0){
1438                     run_mode=0;
1439                     run_count=0;
1440                     diff= get_vlc_symbol(&s->gb, &p->vlc_state[context], bits);
1441                     if(diff>=0) diff++;
1442                 }else
1443                     diff=0;
1444             }else
1445                 diff= get_vlc_symbol(&s->gb, &p->vlc_state[context], bits);
1446
1447 //            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));
1448         }
1449
1450         if(sign) diff= -diff;
1451
1452         sample[1][x]= (predict(sample[1] + x, sample[0] + x) + diff) & ((1<<bits)-1);
1453     }
1454     s->run_index= run_index;
1455 }
1456
1457 static void decode_plane(FFV1Context *s, uint8_t *src, int w, int h, int stride, int plane_index){
1458     int x, y;
1459     int16_t *sample[2];
1460     sample[0]=s->sample_buffer    +3;
1461     sample[1]=s->sample_buffer+w+6+3;
1462
1463     s->run_index=0;
1464
1465     memset(s->sample_buffer, 0, 2*(w+6)*sizeof(*s->sample_buffer));
1466
1467     for(y=0; y<h; y++){
1468         int16_t *temp = sample[0]; //FIXME try a normal buffer
1469
1470         sample[0]= sample[1];
1471         sample[1]= temp;
1472
1473         sample[1][-1]= sample[0][0  ];
1474         sample[0][ w]= sample[0][w-1];
1475
1476 //{START_TIMER
1477         if(s->avctx->bits_per_raw_sample <= 8){
1478             decode_line(s, w, sample, plane_index, 8);
1479             for(x=0; x<w; x++){
1480                 src[x + stride*y]= sample[1][x];
1481             }
1482         }else{
1483             decode_line(s, w, sample, plane_index, s->avctx->bits_per_raw_sample);
1484             if(s->packed_at_lsb){
1485                 for(x=0; x<w; x++){
1486                     ((uint16_t*)(src + stride*y))[x]= sample[1][x];
1487                 }
1488             }else{
1489                 for(x=0; x<w; x++){
1490                     ((uint16_t*)(src + stride*y))[x]= sample[1][x] << (16 - s->avctx->bits_per_raw_sample);
1491                 }
1492             }
1493         }
1494 //STOP_TIMER("decode-line")}
1495     }
1496 }
1497
1498 static void decode_rgb_frame(FFV1Context *s, uint32_t *src, int w, int h, int stride){
1499     int x, y, p;
1500     int16_t *sample[4][2];
1501     for(x=0; x<4; x++){
1502         sample[x][0] = s->sample_buffer +  x*2   *(w+6) + 3;
1503         sample[x][1] = s->sample_buffer + (x*2+1)*(w+6) + 3;
1504     }
1505
1506     s->run_index=0;
1507
1508     memset(s->sample_buffer, 0, 8*(w+6)*sizeof(*s->sample_buffer));
1509
1510     for(y=0; y<h; y++){
1511         for(p=0; p<3 + s->transparency; p++){
1512             int16_t *temp = sample[p][0]; //FIXME try a normal buffer
1513
1514             sample[p][0]= sample[p][1];
1515             sample[p][1]= temp;
1516
1517             sample[p][1][-1]= sample[p][0][0  ];
1518             sample[p][0][ w]= sample[p][0][w-1];
1519             decode_line(s, w, sample[p], (p+1)/2, 9);
1520         }
1521         for(x=0; x<w; x++){
1522             int g= sample[0][1][x];
1523             int b= sample[1][1][x];
1524             int r= sample[2][1][x];
1525             int a= sample[3][1][x];
1526
1527 //            assert(g>=0 && b>=0 && r>=0);
1528 //            assert(g<256 && b<512 && r<512);
1529
1530             b -= 0x100;
1531             r -= 0x100;
1532             g -= (b + r)>>2;
1533             b += g;
1534             r += g;
1535
1536             src[x + stride*y]= b + (g<<8) + (r<<16) + (a<<24);
1537         }
1538     }
1539 }
1540
1541 static int decode_slice_header(FFV1Context *f, FFV1Context *fs){
1542     RangeCoder *c = &fs->c;
1543     uint8_t state[CONTEXT_SIZE];
1544     unsigned ps, i, context_count;
1545     memset(state, 128, sizeof(state));
1546
1547     av_assert0(f->version > 2);
1548
1549     fs->slice_x     = get_symbol(c, state, 0)   *f->width ;
1550     fs->slice_y     = get_symbol(c, state, 0)   *f->height;
1551     fs->slice_width =(get_symbol(c, state, 0)+1)*f->width  + fs->slice_x;
1552     fs->slice_height=(get_symbol(c, state, 0)+1)*f->height + fs->slice_y;
1553
1554     fs->slice_x /= f->num_h_slices;
1555     fs->slice_y /= f->num_v_slices;
1556     fs->slice_width  = fs->slice_width /f->num_h_slices - fs->slice_x;
1557     fs->slice_height = fs->slice_height/f->num_v_slices - fs->slice_y;
1558     if((unsigned)fs->slice_width > f->width || (unsigned)fs->slice_height > f->height)
1559         return -1;
1560     if(    (unsigned)fs->slice_x + (uint64_t)fs->slice_width  > f->width
1561         || (unsigned)fs->slice_y + (uint64_t)fs->slice_height > f->height)
1562         return -1;
1563
1564     for(i=0; i<f->plane_count; i++){
1565         PlaneContext * const p= &fs->plane[i];
1566         int idx=get_symbol(c, state, 0);
1567         if(idx > (unsigned)f->quant_table_count){
1568             av_log(f->avctx, AV_LOG_ERROR, "quant_table_index out of range\n");
1569             return -1;
1570         }
1571         p->quant_table_index= idx;
1572         memcpy(p->quant_table, f->quant_tables[idx], sizeof(p->quant_table));
1573         context_count= f->context_count[idx];
1574
1575         if(p->context_count < context_count){
1576             av_freep(&p->state);
1577             av_freep(&p->vlc_state);
1578         }
1579         p->context_count= context_count;
1580     }
1581
1582     ps = get_symbol(c, state, 0);
1583     if(ps==1){
1584         f->picture.interlaced_frame = 1;
1585         f->picture.top_field_first  = 1;
1586     } else if(ps==2){
1587         f->picture.interlaced_frame = 1;
1588         f->picture.top_field_first  = 0;
1589     } else if(ps==3){
1590         f->picture.interlaced_frame = 0;
1591     }
1592     f->picture.sample_aspect_ratio.num = get_symbol(c, state, 0);
1593     f->picture.sample_aspect_ratio.den = get_symbol(c, state, 0);
1594
1595     return 0;
1596 }
1597
1598 static int decode_slice(AVCodecContext *c, void *arg){
1599     FFV1Context *fs= *(void**)arg;
1600     FFV1Context *f= fs->avctx->priv_data;
1601     int width, height, x, y;
1602     const int ps= (c->bits_per_raw_sample>8)+1;
1603     AVFrame * const p= &f->picture;
1604
1605     if(f->version > 2){
1606         if(decode_slice_header(f, fs) < 0)
1607             return AVERROR_INVALIDDATA;
1608
1609         if(init_slice_state(f, fs) < 0)
1610             return AVERROR(ENOMEM);
1611     }
1612     if(f->picture.key_frame)
1613         clear_slice_state(f, fs);
1614     width = fs->slice_width;
1615     height= fs->slice_height;
1616     x= fs->slice_x;
1617     y= fs->slice_y;
1618
1619     if(!fs->ac){
1620         fs->ac_byte_count = f->version > 2 || (!x&&!y) ? fs->c.bytestream - fs->c.bytestream_start - 1 : 0;
1621         init_get_bits(&fs->gb,
1622                       fs->c.bytestream_start + fs->ac_byte_count,
1623                       (fs->c.bytestream_end - fs->c.bytestream_start - fs->ac_byte_count) * 8);
1624     }
1625
1626     av_assert1(width && height);
1627     if(f->colorspace==0){
1628         const int chroma_width = -((-width )>>f->chroma_h_shift);
1629         const int chroma_height= -((-height)>>f->chroma_v_shift);
1630         const int cx= x>>f->chroma_h_shift;
1631         const int cy= y>>f->chroma_v_shift;
1632         decode_plane(fs, p->data[0] + ps*x + y*p->linesize[0], width, height, p->linesize[0], 0);
1633
1634         if (f->chroma_planes){
1635             decode_plane(fs, p->data[1] + ps*cx+cy*p->linesize[1], chroma_width, chroma_height, p->linesize[1], 1);
1636             decode_plane(fs, p->data[2] + ps*cx+cy*p->linesize[2], chroma_width, chroma_height, p->linesize[2], 1);
1637         }
1638         if (fs->transparency)
1639             decode_plane(fs, p->data[3] + ps*x + y*p->linesize[3], width, height, p->linesize[3], 2);
1640     }else{
1641         decode_rgb_frame(fs, (uint32_t*)p->data[0] + ps*x + y*(p->linesize[0]/4), width, height, p->linesize[0]/4);
1642     }
1643
1644     emms_c();
1645
1646     return 0;
1647 }
1648
1649 static int read_quant_table(RangeCoder *c, int16_t *quant_table, int scale){
1650     int v;
1651     int i=0;
1652     uint8_t state[CONTEXT_SIZE];
1653
1654     memset(state, 128, sizeof(state));
1655
1656     for(v=0; i<128 ; v++){
1657         int len= get_symbol(c, state, 0) + 1;
1658
1659         if(len + i > 128) return -1;
1660
1661         while(len--){
1662             quant_table[i] = scale*v;
1663             i++;
1664 //printf("%2d ",v);
1665 //if(i%16==0) printf("\n");
1666         }
1667     }
1668
1669     for(i=1; i<128; i++){
1670         quant_table[256-i]= -quant_table[i];
1671     }
1672     quant_table[128]= -quant_table[127];
1673
1674     return 2*v - 1;
1675 }
1676
1677 static int read_quant_tables(RangeCoder *c, int16_t quant_table[MAX_CONTEXT_INPUTS][256]){
1678     int i;
1679     int context_count=1;
1680
1681     for(i=0; i<5; i++){
1682         context_count*= read_quant_table(c, quant_table[i], context_count);
1683         if(context_count > 32768U){
1684             return -1;
1685         }
1686     }
1687     return (context_count+1)/2;
1688 }
1689
1690 static int read_extra_header(FFV1Context *f){
1691     RangeCoder * const c= &f->c;
1692     uint8_t state[CONTEXT_SIZE];
1693     int i, j, k;
1694     uint8_t state2[32][CONTEXT_SIZE];
1695
1696     memset(state2, 128, sizeof(state2));
1697     memset(state, 128, sizeof(state));
1698
1699     ff_init_range_decoder(c, f->avctx->extradata, f->avctx->extradata_size);
1700     ff_build_rac_states(c, 0.05*(1LL<<32), 256-8);
1701
1702     f->version= get_symbol(c, state, 0);
1703     if(f->version > 2)
1704         f->minor_version= get_symbol(c, state, 0);
1705     f->ac= f->avctx->coder_type= get_symbol(c, state, 0);
1706     if(f->ac>1){
1707         for(i=1; i<256; i++){
1708             f->state_transition[i]= get_symbol(c, state, 1) + c->one_state[i];
1709         }
1710     }
1711     f->colorspace= get_symbol(c, state, 0); //YUV cs type
1712     f->avctx->bits_per_raw_sample= get_symbol(c, state, 0);
1713     f->chroma_planes= get_rac(c, state);
1714     f->chroma_h_shift= get_symbol(c, state, 0);
1715     f->chroma_v_shift= get_symbol(c, state, 0);
1716     f->transparency= get_rac(c, state);
1717     f->plane_count= 2 + f->transparency;
1718     f->num_h_slices= 1 + get_symbol(c, state, 0);
1719     f->num_v_slices= 1 + get_symbol(c, state, 0);
1720     if(f->num_h_slices > (unsigned)f->width || f->num_v_slices > (unsigned)f->height){
1721         av_log(f->avctx, AV_LOG_ERROR, "too many slices\n");
1722         return -1;
1723     }
1724
1725     f->quant_table_count= get_symbol(c, state, 0);
1726     if(f->quant_table_count > (unsigned)MAX_QUANT_TABLES)
1727         return -1;
1728     for(i=0; i<f->quant_table_count; i++){
1729         if((f->context_count[i]= read_quant_tables(c, f->quant_tables[i])) < 0){
1730             av_log(f->avctx, AV_LOG_ERROR, "read_quant_table error\n");
1731             return -1;
1732         }
1733     }
1734
1735     if(allocate_initial_states(f) < 0)
1736         return AVERROR(ENOMEM);
1737
1738     for(i=0; i<f->quant_table_count; i++){
1739         if(get_rac(c, state)){
1740             for(j=0; j<f->context_count[i]; j++){
1741                 for(k=0; k<CONTEXT_SIZE; k++){
1742                     int pred= j ? f->initial_states[i][j-1][k] : 128;
1743                     f->initial_states[i][j][k]= (pred+get_symbol(c, state2[k], 1))&0xFF;
1744                 }
1745             }
1746         }
1747     }
1748
1749     if(f->version > 2){
1750         f->ec = get_symbol(c, state, 0);
1751     }
1752
1753     if(f->version > 2){
1754         unsigned v;
1755         v = av_crc(av_crc_get_table(AV_CRC_32_IEEE), 0, f->avctx->extradata, f->avctx->extradata_size);
1756         if(v){
1757             av_log(f->avctx, AV_LOG_ERROR, "CRC mismatch %X!\n", v);
1758             return AVERROR_INVALIDDATA;
1759         }
1760     }
1761
1762     return 0;
1763 }
1764
1765 static int read_header(FFV1Context *f){
1766     uint8_t state[CONTEXT_SIZE];
1767     int i, j, context_count;
1768     RangeCoder * const c= &f->slice_context[0]->c;
1769
1770     memset(state, 128, sizeof(state));
1771
1772     if(f->version < 2){
1773         f->version= get_symbol(c, state, 0);
1774         f->ac= f->avctx->coder_type= get_symbol(c, state, 0);
1775         if(f->ac>1){
1776             for(i=1; i<256; i++){
1777                 f->state_transition[i]= get_symbol(c, state, 1) + c->one_state[i];
1778             }
1779         }
1780         f->colorspace= get_symbol(c, state, 0); //YUV cs type
1781         if(f->version>0)
1782             f->avctx->bits_per_raw_sample= get_symbol(c, state, 0);
1783         f->chroma_planes= get_rac(c, state);
1784         f->chroma_h_shift= get_symbol(c, state, 0);
1785         f->chroma_v_shift= get_symbol(c, state, 0);
1786         f->transparency= get_rac(c, state);
1787         f->plane_count= 2 + f->transparency;
1788     }
1789
1790     if(f->colorspace==0){
1791         if(!f->transparency && !f->chroma_planes){
1792             if (f->avctx->bits_per_raw_sample<=8)
1793                 f->avctx->pix_fmt= PIX_FMT_GRAY8;
1794             else
1795                 f->avctx->pix_fmt= PIX_FMT_GRAY16;
1796         }else if(f->avctx->bits_per_raw_sample<=8 && !f->transparency){
1797             switch(16*f->chroma_h_shift + f->chroma_v_shift){
1798             case 0x00: f->avctx->pix_fmt= PIX_FMT_YUV444P; break;
1799             case 0x01: f->avctx->pix_fmt= PIX_FMT_YUV440P; break;
1800             case 0x10: f->avctx->pix_fmt= PIX_FMT_YUV422P; break;
1801             case 0x11: f->avctx->pix_fmt= PIX_FMT_YUV420P; break;
1802             case 0x20: f->avctx->pix_fmt= PIX_FMT_YUV411P; break;
1803             case 0x22: f->avctx->pix_fmt= PIX_FMT_YUV410P; break;
1804             default:
1805                 av_log(f->avctx, AV_LOG_ERROR, "format not supported\n");
1806                 return -1;
1807             }
1808         }else if(f->avctx->bits_per_raw_sample<=8 && f->transparency){
1809             switch(16*f->chroma_h_shift + f->chroma_v_shift){
1810             case 0x00: f->avctx->pix_fmt= PIX_FMT_YUVA444P; break;
1811             case 0x11: f->avctx->pix_fmt= PIX_FMT_YUVA420P; break;
1812             default:
1813                 av_log(f->avctx, AV_LOG_ERROR, "format not supported\n");
1814                 return -1;
1815             }
1816         }else if(f->avctx->bits_per_raw_sample==9) {
1817             f->packed_at_lsb=1;
1818             switch(16*f->chroma_h_shift + f->chroma_v_shift){
1819             case 0x00: f->avctx->pix_fmt= PIX_FMT_YUV444P9; break;
1820             case 0x10: f->avctx->pix_fmt= PIX_FMT_YUV422P9; break;
1821             case 0x11: f->avctx->pix_fmt= PIX_FMT_YUV420P9; break;
1822             default:
1823                 av_log(f->avctx, AV_LOG_ERROR, "format not supported\n");
1824                 return -1;
1825             }
1826         }else if(f->avctx->bits_per_raw_sample==10) {
1827             f->packed_at_lsb=1;
1828             switch(16*f->chroma_h_shift + f->chroma_v_shift){
1829             case 0x00: f->avctx->pix_fmt= PIX_FMT_YUV444P10; break;
1830             case 0x10: f->avctx->pix_fmt= PIX_FMT_YUV422P10; break;
1831             case 0x11: f->avctx->pix_fmt= PIX_FMT_YUV420P10; break;
1832             default:
1833                 av_log(f->avctx, AV_LOG_ERROR, "format not supported\n");
1834                 return -1;
1835             }
1836         }else {
1837             switch(16*f->chroma_h_shift + f->chroma_v_shift){
1838             case 0x00: f->avctx->pix_fmt= PIX_FMT_YUV444P16; break;
1839             case 0x10: f->avctx->pix_fmt= PIX_FMT_YUV422P16; break;
1840             case 0x11: f->avctx->pix_fmt= PIX_FMT_YUV420P16; break;
1841             default:
1842                 av_log(f->avctx, AV_LOG_ERROR, "format not supported\n");
1843                 return -1;
1844             }
1845         }
1846     }else if(f->colorspace==1){
1847         if(f->chroma_h_shift || f->chroma_v_shift){
1848             av_log(f->avctx, AV_LOG_ERROR, "chroma subsampling not supported in this colorspace\n");
1849             return -1;
1850         }
1851         if(f->transparency) f->avctx->pix_fmt= PIX_FMT_RGB32;
1852         else                f->avctx->pix_fmt= PIX_FMT_0RGB32;
1853     }else{
1854         av_log(f->avctx, AV_LOG_ERROR, "colorspace not supported\n");
1855         return -1;
1856     }
1857
1858 //printf("%d %d %d\n", f->chroma_h_shift, f->chroma_v_shift,f->avctx->pix_fmt);
1859     if(f->version < 2){
1860         context_count= read_quant_tables(c, f->quant_table);
1861         if(context_count < 0){
1862                 av_log(f->avctx, AV_LOG_ERROR, "read_quant_table error\n");
1863                 return -1;
1864         }
1865     }else{
1866         f->slice_count= get_symbol(c, state, 0);
1867         if(f->slice_count > (unsigned)MAX_SLICES)
1868             return -1;
1869     }
1870
1871     for(j=0; j<f->slice_count; j++){
1872         FFV1Context *fs= f->slice_context[j];
1873         fs->ac= f->ac;
1874         fs->packed_at_lsb= f->packed_at_lsb;
1875
1876         if(f->version == 2){
1877             fs->slice_x     = get_symbol(c, state, 0)   *f->width ;
1878             fs->slice_y     = get_symbol(c, state, 0)   *f->height;
1879             fs->slice_width =(get_symbol(c, state, 0)+1)*f->width  + fs->slice_x;
1880             fs->slice_height=(get_symbol(c, state, 0)+1)*f->height + fs->slice_y;
1881
1882             fs->slice_x /= f->num_h_slices;
1883             fs->slice_y /= f->num_v_slices;
1884             fs->slice_width  = fs->slice_width /f->num_h_slices - fs->slice_x;
1885             fs->slice_height = fs->slice_height/f->num_v_slices - fs->slice_y;
1886             if((unsigned)fs->slice_width > f->width || (unsigned)fs->slice_height > f->height)
1887                 return -1;
1888             if(    (unsigned)fs->slice_x + (uint64_t)fs->slice_width  > f->width
1889                 || (unsigned)fs->slice_y + (uint64_t)fs->slice_height > f->height)
1890                 return -1;
1891         }
1892
1893         for(i=0; i<f->plane_count; i++){
1894             PlaneContext * const p= &fs->plane[i];
1895
1896             if(f->version == 2){
1897                 int idx=get_symbol(c, state, 0);
1898                 if(idx > (unsigned)f->quant_table_count){
1899                     av_log(f->avctx, AV_LOG_ERROR, "quant_table_index out of range\n");
1900                     return -1;
1901                 }
1902                 p->quant_table_index= idx;
1903                 memcpy(p->quant_table, f->quant_tables[idx], sizeof(p->quant_table));
1904                 context_count= f->context_count[idx];
1905             }else{
1906                 memcpy(p->quant_table, f->quant_table, sizeof(p->quant_table));
1907             }
1908
1909             if(f->version <= 2){
1910             if(p->context_count < context_count){
1911                 av_freep(&p->state);
1912                 av_freep(&p->vlc_state);
1913             }
1914             p->context_count= context_count;
1915             }
1916         }
1917     }
1918     return 0;
1919 }
1920
1921 static av_cold int decode_init(AVCodecContext *avctx)
1922 {
1923     FFV1Context *f = avctx->priv_data;
1924
1925     common_init(avctx);
1926
1927     if(avctx->extradata && read_extra_header(f) < 0)
1928         return -1;
1929
1930     if(init_slice_contexts(f) < 0)
1931         return -1;
1932
1933     return 0;
1934 }
1935
1936 static int decode_frame(AVCodecContext *avctx, void *data, int *data_size, AVPacket *avpkt){
1937     const uint8_t *buf = avpkt->data;
1938     int buf_size = avpkt->size;
1939     FFV1Context *f = avctx->priv_data;
1940     RangeCoder * const c= &f->slice_context[0]->c;
1941     AVFrame * const p= &f->picture;
1942     int bytes_read, i;
1943     uint8_t keystate= 128;
1944     const uint8_t *buf_p;
1945
1946     AVFrame *picture = data;
1947
1948     /* release previously stored data */
1949     if (p->data[0])
1950         avctx->release_buffer(avctx, p);
1951
1952     ff_init_range_decoder(c, buf, buf_size);
1953     ff_build_rac_states(c, 0.05*(1LL<<32), 256-8);
1954
1955
1956     p->pict_type= AV_PICTURE_TYPE_I; //FIXME I vs. P
1957     if(get_rac(c, &keystate)){
1958         p->key_frame= 1;
1959         f->key_frame_ok = 0;
1960         if(read_header(f) < 0)
1961             return -1;
1962         if(init_slices_state(f) < 0)
1963             return -1;
1964         f->key_frame_ok = 1;
1965     }else{
1966         if (!f->key_frame_ok) {
1967             av_log(avctx, AV_LOG_ERROR, "Cant decode non keyframe without valid keyframe\n");
1968             return AVERROR_INVALIDDATA;
1969         }
1970         p->key_frame= 0;
1971     }
1972     if(f->ac>1){
1973         int i;
1974         for(i=1; i<256; i++){
1975             c->one_state[i]= f->state_transition[i];
1976             c->zero_state[256-i]= 256-c->one_state[i];
1977         }
1978     }
1979
1980     p->reference= 0;
1981     if(avctx->get_buffer(avctx, p) < 0){
1982         av_log(avctx, AV_LOG_ERROR, "get_buffer() failed\n");
1983         return -1;
1984     }
1985
1986     if(avctx->debug&FF_DEBUG_PICT_INFO)
1987         av_log(avctx, AV_LOG_ERROR, "keyframe:%d coder:%d\n", p->key_frame, f->ac);
1988
1989     buf_p= buf + buf_size;
1990     for(i=f->slice_count-1; i>=0; i--){
1991         FFV1Context *fs= f->slice_context[i];
1992         int trailer = 3 + 5*!!f->ec;
1993         int v;
1994
1995         if(i || f->ec) v = AV_RB24(buf_p-trailer)+trailer;
1996         else           v = buf_p - c->bytestream_start;
1997         if(buf_p - c->bytestream_start < v){
1998             av_log(avctx, AV_LOG_ERROR, "Slice pointer chain broken\n");
1999             return -1;
2000         }
2001         buf_p -= v;
2002
2003         if(f->ec){
2004             unsigned crc = av_crc(av_crc_get_table(AV_CRC_32_IEEE), 0, buf_p, v);
2005             if(crc){
2006                 av_log(f->avctx, AV_LOG_ERROR, "CRC mismatch %X!\n", crc);
2007             }
2008         }
2009
2010         if(i){
2011             ff_init_range_decoder(&fs->c, buf_p, v);
2012         }
2013     }
2014
2015     avctx->execute(avctx, decode_slice, &f->slice_context[0], NULL, f->slice_count, sizeof(void*));
2016     f->picture_number++;
2017
2018     *picture= *p;
2019     *data_size = sizeof(AVFrame);
2020
2021     return buf_size;
2022 }
2023
2024 AVCodec ff_ffv1_decoder = {
2025     .name           = "ffv1",
2026     .type           = AVMEDIA_TYPE_VIDEO,
2027     .id             = CODEC_ID_FFV1,
2028     .priv_data_size = sizeof(FFV1Context),
2029     .init           = decode_init,
2030     .close          = common_end,
2031     .decode         = decode_frame,
2032     .capabilities   = CODEC_CAP_DR1 /*| CODEC_CAP_DRAW_HORIZ_BAND*/ |
2033                       CODEC_CAP_SLICE_THREADS,
2034     .long_name      = NULL_IF_CONFIG_SMALL("FFmpeg video codec #1"),
2035 };
2036
2037 #if CONFIG_FFV1_ENCODER
2038 AVCodec ff_ffv1_encoder = {
2039     .name           = "ffv1",
2040     .type           = AVMEDIA_TYPE_VIDEO,
2041     .id             = CODEC_ID_FFV1,
2042     .priv_data_size = sizeof(FFV1Context),
2043     .init           = encode_init,
2044     .encode2        = encode_frame,
2045     .close          = common_end,
2046     .capabilities   = CODEC_CAP_SLICE_THREADS,
2047     .pix_fmts= (const enum PixelFormat[]){PIX_FMT_YUV420P, PIX_FMT_YUVA420P, PIX_FMT_YUV444P, PIX_FMT_YUVA444P, PIX_FMT_YUV440P, PIX_FMT_YUV422P, PIX_FMT_YUV411P, PIX_FMT_YUV410P, PIX_FMT_0RGB32, PIX_FMT_RGB32, PIX_FMT_YUV420P16, PIX_FMT_YUV422P16, PIX_FMT_YUV444P16, PIX_FMT_YUV444P9, PIX_FMT_YUV422P9, PIX_FMT_YUV420P9, PIX_FMT_YUV420P10, PIX_FMT_YUV422P10, PIX_FMT_YUV444P10, PIX_FMT_GRAY16, PIX_FMT_GRAY8, PIX_FMT_NONE},
2048     .long_name      = NULL_IF_CONFIG_SMALL("FFmpeg video codec #1"),
2049 };
2050 #endif