ffv1: include solution hint in the slice error message
[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){
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 = av_crc(av_crc_get_table(AV_CRC_32_IEEE), 0, buf_p, bytes);
1302             AV_WL32(buf_p + bytes, v); bytes += 4;
1303         }
1304         buf_p += bytes;
1305     }
1306
1307     if((avctx->flags&CODEC_FLAG_PASS1) && (f->picture_number&31)==0){
1308         int j, k, m;
1309         char *p= avctx->stats_out;
1310         char *end= p + STATS_OUT_SIZE;
1311
1312         memset(f->rc_stat, 0, sizeof(f->rc_stat));
1313         for(i=0; i<f->quant_table_count; i++)
1314             memset(f->rc_stat2[i], 0, f->context_count[i]*sizeof(*f->rc_stat2[i]));
1315
1316         for(j=0; j<f->slice_count; j++){
1317             FFV1Context *fs= f->slice_context[j];
1318             for(i=0; i<256; i++){
1319                 f->rc_stat[i][0] += fs->rc_stat[i][0];
1320                 f->rc_stat[i][1] += fs->rc_stat[i][1];
1321             }
1322             for(i=0; i<f->quant_table_count; i++){
1323                 for(k=0; k<f->context_count[i]; k++){
1324                     for(m=0; m<32; m++){
1325                         f->rc_stat2[i][k][m][0] += fs->rc_stat2[i][k][m][0];
1326                         f->rc_stat2[i][k][m][1] += fs->rc_stat2[i][k][m][1];
1327                     }
1328                 }
1329             }
1330         }
1331
1332         for(j=0; j<256; j++){
1333             snprintf(p, end-p, "%"PRIu64" %"PRIu64" ", f->rc_stat[j][0], f->rc_stat[j][1]);
1334             p+= strlen(p);
1335         }
1336         snprintf(p, end-p, "\n");
1337
1338         for(i=0; i<f->quant_table_count; i++){
1339             for(j=0; j<f->context_count[i]; j++){
1340                 for(m=0; m<32; m++){
1341                     snprintf(p, end-p, "%"PRIu64" %"PRIu64" ", f->rc_stat2[i][j][m][0], f->rc_stat2[i][j][m][1]);
1342                     p+= strlen(p);
1343                 }
1344             }
1345         }
1346         snprintf(p, end-p, "%d\n", f->gob_count);
1347     } else if(avctx->flags&CODEC_FLAG_PASS1)
1348         avctx->stats_out[0] = '\0';
1349
1350     f->picture_number++;
1351     pkt->size   = buf_p - pkt->data;
1352     pkt->flags |= AV_PKT_FLAG_KEY*p->key_frame;
1353     *got_packet = 1;
1354
1355     return 0;
1356 }
1357 #endif /* CONFIG_FFV1_ENCODER */
1358
1359 static av_cold int common_end(AVCodecContext *avctx){
1360     FFV1Context *s = avctx->priv_data;
1361     int i, j;
1362
1363     if (avctx->codec->decode && s->picture.data[0])
1364         avctx->release_buffer(avctx, &s->picture);
1365
1366     for(j=0; j<s->slice_count; j++){
1367         FFV1Context *fs= s->slice_context[j];
1368         for(i=0; i<s->plane_count; i++){
1369             PlaneContext *p= &fs->plane[i];
1370
1371             av_freep(&p->state);
1372             av_freep(&p->vlc_state);
1373         }
1374         av_freep(&fs->sample_buffer);
1375     }
1376
1377     av_freep(&avctx->stats_out);
1378     for(j=0; j<s->quant_table_count; j++){
1379         av_freep(&s->initial_states[j]);
1380         for(i=0; i<s->slice_count; i++){
1381             FFV1Context *sf= s->slice_context[i];
1382             av_freep(&sf->rc_stat2[j]);
1383         }
1384         av_freep(&s->rc_stat2[j]);
1385     }
1386
1387     for(i=0; i<s->slice_count; i++){
1388         av_freep(&s->slice_context[i]);
1389     }
1390
1391     return 0;
1392 }
1393
1394 static av_always_inline void decode_line(FFV1Context *s, int w,
1395                                          int16_t *sample[2],
1396                                          int plane_index, int bits)
1397 {
1398     PlaneContext * const p= &s->plane[plane_index];
1399     RangeCoder * const c= &s->c;
1400     int x;
1401     int run_count=0;
1402     int run_mode=0;
1403     int run_index= s->run_index;
1404
1405     for(x=0; x<w; x++){
1406         int diff, context, sign;
1407
1408         context= get_context(p, sample[1] + x, sample[0] + x, sample[1] + x);
1409         if(context < 0){
1410             context= -context;
1411             sign=1;
1412         }else
1413             sign=0;
1414
1415         av_assert2(context < p->context_count);
1416
1417         if(s->ac){
1418             diff= get_symbol_inline(c, p->state[context], 1);
1419         }else{
1420             if(context == 0 && run_mode==0) run_mode=1;
1421
1422             if(run_mode){
1423                 if(run_count==0 && run_mode==1){
1424                     if(get_bits1(&s->gb)){
1425                         run_count = 1<<ff_log2_run[run_index];
1426                         if(x + run_count <= w) run_index++;
1427                     }else{
1428                         if(ff_log2_run[run_index]) run_count = get_bits(&s->gb, ff_log2_run[run_index]);
1429                         else run_count=0;
1430                         if(run_index) run_index--;
1431                         run_mode=2;
1432                     }
1433                 }
1434                 run_count--;
1435                 if(run_count < 0){
1436                     run_mode=0;
1437                     run_count=0;
1438                     diff= get_vlc_symbol(&s->gb, &p->vlc_state[context], bits);
1439                     if(diff>=0) diff++;
1440                 }else
1441                     diff=0;
1442             }else
1443                 diff= get_vlc_symbol(&s->gb, &p->vlc_state[context], bits);
1444
1445 //            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));
1446         }
1447
1448         if(sign) diff= -diff;
1449
1450         sample[1][x]= (predict(sample[1] + x, sample[0] + x) + diff) & ((1<<bits)-1);
1451     }
1452     s->run_index= run_index;
1453 }
1454
1455 static void decode_plane(FFV1Context *s, uint8_t *src, int w, int h, int stride, int plane_index){
1456     int x, y;
1457     int16_t *sample[2];
1458     sample[0]=s->sample_buffer    +3;
1459     sample[1]=s->sample_buffer+w+6+3;
1460
1461     s->run_index=0;
1462
1463     memset(s->sample_buffer, 0, 2*(w+6)*sizeof(*s->sample_buffer));
1464
1465     for(y=0; y<h; y++){
1466         int16_t *temp = sample[0]; //FIXME try a normal buffer
1467
1468         sample[0]= sample[1];
1469         sample[1]= temp;
1470
1471         sample[1][-1]= sample[0][0  ];
1472         sample[0][ w]= sample[0][w-1];
1473
1474 //{START_TIMER
1475         if(s->avctx->bits_per_raw_sample <= 8){
1476             decode_line(s, w, sample, plane_index, 8);
1477             for(x=0; x<w; x++){
1478                 src[x + stride*y]= sample[1][x];
1479             }
1480         }else{
1481             decode_line(s, w, sample, plane_index, s->avctx->bits_per_raw_sample);
1482             if(s->packed_at_lsb){
1483                 for(x=0; x<w; x++){
1484                     ((uint16_t*)(src + stride*y))[x]= sample[1][x];
1485                 }
1486             }else{
1487                 for(x=0; x<w; x++){
1488                     ((uint16_t*)(src + stride*y))[x]= sample[1][x] << (16 - s->avctx->bits_per_raw_sample);
1489                 }
1490             }
1491         }
1492 //STOP_TIMER("decode-line")}
1493     }
1494 }
1495
1496 static void decode_rgb_frame(FFV1Context *s, uint32_t *src, int w, int h, int stride){
1497     int x, y, p;
1498     int16_t *sample[4][2];
1499     for(x=0; x<4; x++){
1500         sample[x][0] = s->sample_buffer +  x*2   *(w+6) + 3;
1501         sample[x][1] = s->sample_buffer + (x*2+1)*(w+6) + 3;
1502     }
1503
1504     s->run_index=0;
1505
1506     memset(s->sample_buffer, 0, 8*(w+6)*sizeof(*s->sample_buffer));
1507
1508     for(y=0; y<h; y++){
1509         for(p=0; p<3 + s->transparency; p++){
1510             int16_t *temp = sample[p][0]; //FIXME try a normal buffer
1511
1512             sample[p][0]= sample[p][1];
1513             sample[p][1]= temp;
1514
1515             sample[p][1][-1]= sample[p][0][0  ];
1516             sample[p][0][ w]= sample[p][0][w-1];
1517             decode_line(s, w, sample[p], (p+1)/2, 9);
1518         }
1519         for(x=0; x<w; x++){
1520             int g= sample[0][1][x];
1521             int b= sample[1][1][x];
1522             int r= sample[2][1][x];
1523             int a= sample[3][1][x];
1524
1525 //            assert(g>=0 && b>=0 && r>=0);
1526 //            assert(g<256 && b<512 && r<512);
1527
1528             b -= 0x100;
1529             r -= 0x100;
1530             g -= (b + r)>>2;
1531             b += g;
1532             r += g;
1533
1534             src[x + stride*y]= b + (g<<8) + (r<<16) + (a<<24);
1535         }
1536     }
1537 }
1538
1539 static int decode_slice_header(FFV1Context *f, FFV1Context *fs){
1540     RangeCoder *c = &fs->c;
1541     uint8_t state[CONTEXT_SIZE];
1542     unsigned ps, i, context_count;
1543     memset(state, 128, sizeof(state));
1544
1545     av_assert0(f->version > 2);
1546
1547     fs->slice_x     = get_symbol(c, state, 0)   *f->width ;
1548     fs->slice_y     = get_symbol(c, state, 0)   *f->height;
1549     fs->slice_width =(get_symbol(c, state, 0)+1)*f->width  + fs->slice_x;
1550     fs->slice_height=(get_symbol(c, state, 0)+1)*f->height + fs->slice_y;
1551
1552     fs->slice_x /= f->num_h_slices;
1553     fs->slice_y /= f->num_v_slices;
1554     fs->slice_width  = fs->slice_width /f->num_h_slices - fs->slice_x;
1555     fs->slice_height = fs->slice_height/f->num_v_slices - fs->slice_y;
1556     if((unsigned)fs->slice_width > f->width || (unsigned)fs->slice_height > f->height)
1557         return -1;
1558     if(    (unsigned)fs->slice_x + (uint64_t)fs->slice_width  > f->width
1559         || (unsigned)fs->slice_y + (uint64_t)fs->slice_height > f->height)
1560         return -1;
1561
1562     for(i=0; i<f->plane_count; i++){
1563         PlaneContext * const p= &fs->plane[i];
1564         int idx=get_symbol(c, state, 0);
1565         if(idx > (unsigned)f->quant_table_count){
1566             av_log(f->avctx, AV_LOG_ERROR, "quant_table_index out of range\n");
1567             return -1;
1568         }
1569         p->quant_table_index= idx;
1570         memcpy(p->quant_table, f->quant_tables[idx], sizeof(p->quant_table));
1571         context_count= f->context_count[idx];
1572
1573         if(p->context_count < context_count){
1574             av_freep(&p->state);
1575             av_freep(&p->vlc_state);
1576         }
1577         p->context_count= context_count;
1578     }
1579
1580     ps = get_symbol(c, state, 0);
1581     if(ps==1){
1582         f->picture.interlaced_frame = 1;
1583         f->picture.top_field_first  = 1;
1584     } else if(ps==2){
1585         f->picture.interlaced_frame = 1;
1586         f->picture.top_field_first  = 0;
1587     } else if(ps==3){
1588         f->picture.interlaced_frame = 0;
1589     }
1590     f->picture.sample_aspect_ratio.num = get_symbol(c, state, 0);
1591     f->picture.sample_aspect_ratio.den = get_symbol(c, state, 0);
1592
1593     return 0;
1594 }
1595
1596 static int decode_slice(AVCodecContext *c, void *arg){
1597     FFV1Context *fs= *(void**)arg;
1598     FFV1Context *f= fs->avctx->priv_data;
1599     int width, height, x, y;
1600     const int ps= (c->bits_per_raw_sample>8)+1;
1601     AVFrame * const p= &f->picture;
1602
1603     if(f->version > 2){
1604         if(decode_slice_header(f, fs) < 0)
1605             return AVERROR_INVALIDDATA;
1606
1607         if(init_slice_state(f, fs) < 0)
1608             return AVERROR(ENOMEM);
1609     }
1610     if(f->picture.key_frame)
1611         clear_slice_state(f, fs);
1612     width = fs->slice_width;
1613     height= fs->slice_height;
1614     x= fs->slice_x;
1615     y= fs->slice_y;
1616
1617     if(!fs->ac){
1618         fs->ac_byte_count = f->version > 2 || (!x&&!y) ? fs->c.bytestream - fs->c.bytestream_start - 1 : 0;
1619         init_get_bits(&fs->gb,
1620                       fs->c.bytestream_start + fs->ac_byte_count,
1621                       (fs->c.bytestream_end - fs->c.bytestream_start - fs->ac_byte_count) * 8);
1622     }
1623
1624     av_assert1(width && height);
1625     if(f->colorspace==0){
1626         const int chroma_width = -((-width )>>f->chroma_h_shift);
1627         const int chroma_height= -((-height)>>f->chroma_v_shift);
1628         const int cx= x>>f->chroma_h_shift;
1629         const int cy= y>>f->chroma_v_shift;
1630         decode_plane(fs, p->data[0] + ps*x + y*p->linesize[0], width, height, p->linesize[0], 0);
1631
1632         if (f->chroma_planes){
1633             decode_plane(fs, p->data[1] + ps*cx+cy*p->linesize[1], chroma_width, chroma_height, p->linesize[1], 1);
1634             decode_plane(fs, p->data[2] + ps*cx+cy*p->linesize[2], chroma_width, chroma_height, p->linesize[2], 1);
1635         }
1636         if (fs->transparency)
1637             decode_plane(fs, p->data[3] + ps*x + y*p->linesize[3], width, height, p->linesize[3], 2);
1638     }else{
1639         decode_rgb_frame(fs, (uint32_t*)p->data[0] + ps*x + y*(p->linesize[0]/4), width, height, p->linesize[0]/4);
1640     }
1641
1642     emms_c();
1643
1644     return 0;
1645 }
1646
1647 static int read_quant_table(RangeCoder *c, int16_t *quant_table, int scale){
1648     int v;
1649     int i=0;
1650     uint8_t state[CONTEXT_SIZE];
1651
1652     memset(state, 128, sizeof(state));
1653
1654     for(v=0; i<128 ; v++){
1655         int len= get_symbol(c, state, 0) + 1;
1656
1657         if(len + i > 128) return -1;
1658
1659         while(len--){
1660             quant_table[i] = scale*v;
1661             i++;
1662 //printf("%2d ",v);
1663 //if(i%16==0) printf("\n");
1664         }
1665     }
1666
1667     for(i=1; i<128; i++){
1668         quant_table[256-i]= -quant_table[i];
1669     }
1670     quant_table[128]= -quant_table[127];
1671
1672     return 2*v - 1;
1673 }
1674
1675 static int read_quant_tables(RangeCoder *c, int16_t quant_table[MAX_CONTEXT_INPUTS][256]){
1676     int i;
1677     int context_count=1;
1678
1679     for(i=0; i<5; i++){
1680         context_count*= read_quant_table(c, quant_table[i], context_count);
1681         if(context_count > 32768U){
1682             return -1;
1683         }
1684     }
1685     return (context_count+1)/2;
1686 }
1687
1688 static int read_extra_header(FFV1Context *f){
1689     RangeCoder * const c= &f->c;
1690     uint8_t state[CONTEXT_SIZE];
1691     int i, j, k;
1692     uint8_t state2[32][CONTEXT_SIZE];
1693
1694     memset(state2, 128, sizeof(state2));
1695     memset(state, 128, sizeof(state));
1696
1697     ff_init_range_decoder(c, f->avctx->extradata, f->avctx->extradata_size);
1698     ff_build_rac_states(c, 0.05*(1LL<<32), 256-8);
1699
1700     f->version= get_symbol(c, state, 0);
1701     if(f->version > 2)
1702         f->minor_version= get_symbol(c, state, 0);
1703     f->ac= f->avctx->coder_type= get_symbol(c, state, 0);
1704     if(f->ac>1){
1705         for(i=1; i<256; i++){
1706             f->state_transition[i]= get_symbol(c, state, 1) + c->one_state[i];
1707         }
1708     }
1709     f->colorspace= get_symbol(c, state, 0); //YUV cs type
1710     f->avctx->bits_per_raw_sample= get_symbol(c, state, 0);
1711     f->chroma_planes= get_rac(c, state);
1712     f->chroma_h_shift= get_symbol(c, state, 0);
1713     f->chroma_v_shift= get_symbol(c, state, 0);
1714     f->transparency= get_rac(c, state);
1715     f->plane_count= 2 + f->transparency;
1716     f->num_h_slices= 1 + get_symbol(c, state, 0);
1717     f->num_v_slices= 1 + get_symbol(c, state, 0);
1718     if(f->num_h_slices > (unsigned)f->width || f->num_v_slices > (unsigned)f->height){
1719         av_log(f->avctx, AV_LOG_ERROR, "too many slices\n");
1720         return -1;
1721     }
1722
1723     f->quant_table_count= get_symbol(c, state, 0);
1724     if(f->quant_table_count > (unsigned)MAX_QUANT_TABLES)
1725         return -1;
1726     for(i=0; i<f->quant_table_count; i++){
1727         if((f->context_count[i]= read_quant_tables(c, f->quant_tables[i])) < 0){
1728             av_log(f->avctx, AV_LOG_ERROR, "read_quant_table error\n");
1729             return -1;
1730         }
1731     }
1732
1733     if(allocate_initial_states(f) < 0)
1734         return AVERROR(ENOMEM);
1735
1736     for(i=0; i<f->quant_table_count; i++){
1737         if(get_rac(c, state)){
1738             for(j=0; j<f->context_count[i]; j++){
1739                 for(k=0; k<CONTEXT_SIZE; k++){
1740                     int pred= j ? f->initial_states[i][j-1][k] : 128;
1741                     f->initial_states[i][j][k]= (pred+get_symbol(c, state2[k], 1))&0xFF;
1742                 }
1743             }
1744         }
1745     }
1746
1747     if(f->version > 2){
1748         f->ec = get_symbol(c, state, 0);
1749     }
1750
1751     if(f->version > 2){
1752         unsigned v;
1753         v = av_crc(av_crc_get_table(AV_CRC_32_IEEE), 0, f->avctx->extradata, f->avctx->extradata_size);
1754         if(v){
1755             av_log(f->avctx, AV_LOG_ERROR, "CRC mismatch %X!\n", v);
1756             return AVERROR_INVALIDDATA;
1757         }
1758     }
1759
1760     return 0;
1761 }
1762
1763 static int read_header(FFV1Context *f){
1764     uint8_t state[CONTEXT_SIZE];
1765     int i, j, context_count;
1766     RangeCoder * const c= &f->slice_context[0]->c;
1767
1768     memset(state, 128, sizeof(state));
1769
1770     if(f->version < 2){
1771         f->version= get_symbol(c, state, 0);
1772         f->ac= f->avctx->coder_type= get_symbol(c, state, 0);
1773         if(f->ac>1){
1774             for(i=1; i<256; i++){
1775                 f->state_transition[i]= get_symbol(c, state, 1) + c->one_state[i];
1776             }
1777         }
1778         f->colorspace= get_symbol(c, state, 0); //YUV cs type
1779         if(f->version>0)
1780             f->avctx->bits_per_raw_sample= get_symbol(c, state, 0);
1781         f->chroma_planes= get_rac(c, state);
1782         f->chroma_h_shift= get_symbol(c, state, 0);
1783         f->chroma_v_shift= get_symbol(c, state, 0);
1784         f->transparency= get_rac(c, state);
1785         f->plane_count= 2 + f->transparency;
1786     }
1787
1788     if(f->colorspace==0){
1789         if(!f->transparency && !f->chroma_planes){
1790             if (f->avctx->bits_per_raw_sample<=8)
1791                 f->avctx->pix_fmt= PIX_FMT_GRAY8;
1792             else
1793                 f->avctx->pix_fmt= PIX_FMT_GRAY16;
1794         }else if(f->avctx->bits_per_raw_sample<=8 && !f->transparency){
1795             switch(16*f->chroma_h_shift + f->chroma_v_shift){
1796             case 0x00: f->avctx->pix_fmt= PIX_FMT_YUV444P; break;
1797             case 0x01: f->avctx->pix_fmt= PIX_FMT_YUV440P; break;
1798             case 0x10: f->avctx->pix_fmt= PIX_FMT_YUV422P; break;
1799             case 0x11: f->avctx->pix_fmt= PIX_FMT_YUV420P; break;
1800             case 0x20: f->avctx->pix_fmt= PIX_FMT_YUV411P; break;
1801             case 0x22: f->avctx->pix_fmt= PIX_FMT_YUV410P; break;
1802             default:
1803                 av_log(f->avctx, AV_LOG_ERROR, "format not supported\n");
1804                 return -1;
1805             }
1806         }else if(f->avctx->bits_per_raw_sample<=8 && f->transparency){
1807             switch(16*f->chroma_h_shift + f->chroma_v_shift){
1808             case 0x00: f->avctx->pix_fmt= PIX_FMT_YUVA444P; break;
1809             case 0x11: f->avctx->pix_fmt= PIX_FMT_YUVA420P; break;
1810             default:
1811                 av_log(f->avctx, AV_LOG_ERROR, "format not supported\n");
1812                 return -1;
1813             }
1814         }else if(f->avctx->bits_per_raw_sample==9) {
1815             f->packed_at_lsb=1;
1816             switch(16*f->chroma_h_shift + f->chroma_v_shift){
1817             case 0x00: f->avctx->pix_fmt= PIX_FMT_YUV444P9; break;
1818             case 0x10: f->avctx->pix_fmt= PIX_FMT_YUV422P9; break;
1819             case 0x11: f->avctx->pix_fmt= PIX_FMT_YUV420P9; break;
1820             default:
1821                 av_log(f->avctx, AV_LOG_ERROR, "format not supported\n");
1822                 return -1;
1823             }
1824         }else if(f->avctx->bits_per_raw_sample==10) {
1825             f->packed_at_lsb=1;
1826             switch(16*f->chroma_h_shift + f->chroma_v_shift){
1827             case 0x00: f->avctx->pix_fmt= PIX_FMT_YUV444P10; break;
1828             case 0x10: f->avctx->pix_fmt= PIX_FMT_YUV422P10; break;
1829             case 0x11: f->avctx->pix_fmt= PIX_FMT_YUV420P10; break;
1830             default:
1831                 av_log(f->avctx, AV_LOG_ERROR, "format not supported\n");
1832                 return -1;
1833             }
1834         }else {
1835             switch(16*f->chroma_h_shift + f->chroma_v_shift){
1836             case 0x00: f->avctx->pix_fmt= PIX_FMT_YUV444P16; break;
1837             case 0x10: f->avctx->pix_fmt= PIX_FMT_YUV422P16; break;
1838             case 0x11: f->avctx->pix_fmt= PIX_FMT_YUV420P16; break;
1839             default:
1840                 av_log(f->avctx, AV_LOG_ERROR, "format not supported\n");
1841                 return -1;
1842             }
1843         }
1844     }else if(f->colorspace==1){
1845         if(f->chroma_h_shift || f->chroma_v_shift){
1846             av_log(f->avctx, AV_LOG_ERROR, "chroma subsampling not supported in this colorspace\n");
1847             return -1;
1848         }
1849         if(f->transparency) f->avctx->pix_fmt= PIX_FMT_RGB32;
1850         else                f->avctx->pix_fmt= PIX_FMT_0RGB32;
1851     }else{
1852         av_log(f->avctx, AV_LOG_ERROR, "colorspace not supported\n");
1853         return -1;
1854     }
1855
1856 //printf("%d %d %d\n", f->chroma_h_shift, f->chroma_v_shift,f->avctx->pix_fmt);
1857     if(f->version < 2){
1858         context_count= read_quant_tables(c, f->quant_table);
1859         if(context_count < 0){
1860                 av_log(f->avctx, AV_LOG_ERROR, "read_quant_table error\n");
1861                 return -1;
1862         }
1863     }else{
1864         f->slice_count= get_symbol(c, state, 0);
1865         if(f->slice_count > (unsigned)MAX_SLICES)
1866             return -1;
1867     }
1868
1869     for(j=0; j<f->slice_count; j++){
1870         FFV1Context *fs= f->slice_context[j];
1871         fs->ac= f->ac;
1872         fs->packed_at_lsb= f->packed_at_lsb;
1873
1874         if(f->version == 2){
1875             fs->slice_x     = get_symbol(c, state, 0)   *f->width ;
1876             fs->slice_y     = get_symbol(c, state, 0)   *f->height;
1877             fs->slice_width =(get_symbol(c, state, 0)+1)*f->width  + fs->slice_x;
1878             fs->slice_height=(get_symbol(c, state, 0)+1)*f->height + fs->slice_y;
1879
1880             fs->slice_x /= f->num_h_slices;
1881             fs->slice_y /= f->num_v_slices;
1882             fs->slice_width  = fs->slice_width /f->num_h_slices - fs->slice_x;
1883             fs->slice_height = fs->slice_height/f->num_v_slices - fs->slice_y;
1884             if((unsigned)fs->slice_width > f->width || (unsigned)fs->slice_height > f->height)
1885                 return -1;
1886             if(    (unsigned)fs->slice_x + (uint64_t)fs->slice_width  > f->width
1887                 || (unsigned)fs->slice_y + (uint64_t)fs->slice_height > f->height)
1888                 return -1;
1889         }
1890
1891         for(i=0; i<f->plane_count; i++){
1892             PlaneContext * const p= &fs->plane[i];
1893
1894             if(f->version == 2){
1895                 int idx=get_symbol(c, state, 0);
1896                 if(idx > (unsigned)f->quant_table_count){
1897                     av_log(f->avctx, AV_LOG_ERROR, "quant_table_index out of range\n");
1898                     return -1;
1899                 }
1900                 p->quant_table_index= idx;
1901                 memcpy(p->quant_table, f->quant_tables[idx], sizeof(p->quant_table));
1902                 context_count= f->context_count[idx];
1903             }else{
1904                 memcpy(p->quant_table, f->quant_table, sizeof(p->quant_table));
1905             }
1906
1907             if(f->version <= 2){
1908             if(p->context_count < context_count){
1909                 av_freep(&p->state);
1910                 av_freep(&p->vlc_state);
1911             }
1912             p->context_count= context_count;
1913             }
1914         }
1915     }
1916     return 0;
1917 }
1918
1919 static av_cold int decode_init(AVCodecContext *avctx)
1920 {
1921     FFV1Context *f = avctx->priv_data;
1922
1923     common_init(avctx);
1924
1925     if(avctx->extradata && read_extra_header(f) < 0)
1926         return -1;
1927
1928     if(init_slice_contexts(f) < 0)
1929         return -1;
1930
1931     return 0;
1932 }
1933
1934 static int decode_frame(AVCodecContext *avctx, void *data, int *data_size, AVPacket *avpkt){
1935     const uint8_t *buf = avpkt->data;
1936     int buf_size = avpkt->size;
1937     FFV1Context *f = avctx->priv_data;
1938     RangeCoder * const c= &f->slice_context[0]->c;
1939     AVFrame * const p= &f->picture;
1940     int bytes_read, i;
1941     uint8_t keystate= 128;
1942     const uint8_t *buf_p;
1943
1944     AVFrame *picture = data;
1945
1946     /* release previously stored data */
1947     if (p->data[0])
1948         avctx->release_buffer(avctx, p);
1949
1950     ff_init_range_decoder(c, buf, buf_size);
1951     ff_build_rac_states(c, 0.05*(1LL<<32), 256-8);
1952
1953
1954     p->pict_type= AV_PICTURE_TYPE_I; //FIXME I vs. P
1955     if(get_rac(c, &keystate)){
1956         p->key_frame= 1;
1957         f->key_frame_ok = 0;
1958         if(read_header(f) < 0)
1959             return -1;
1960         if(init_slices_state(f) < 0)
1961             return -1;
1962         f->key_frame_ok = 1;
1963     }else{
1964         if (!f->key_frame_ok) {
1965             av_log(avctx, AV_LOG_ERROR, "Cant decode non keyframe without valid keyframe\n");
1966             return AVERROR_INVALIDDATA;
1967         }
1968         p->key_frame= 0;
1969     }
1970     if(f->ac>1){
1971         int i;
1972         for(i=1; i<256; i++){
1973             c->one_state[i]= f->state_transition[i];
1974             c->zero_state[256-i]= 256-c->one_state[i];
1975         }
1976     }
1977
1978     p->reference= 0;
1979     if(avctx->get_buffer(avctx, p) < 0){
1980         av_log(avctx, AV_LOG_ERROR, "get_buffer() failed\n");
1981         return -1;
1982     }
1983
1984     if(avctx->debug&FF_DEBUG_PICT_INFO)
1985         av_log(avctx, AV_LOG_ERROR, "keyframe:%d coder:%d\n", p->key_frame, f->ac);
1986
1987     buf_p= buf + buf_size;
1988     for(i=f->slice_count-1; i>=0; i--){
1989         FFV1Context *fs= f->slice_context[i];
1990         int trailer = 3 + 4*!!f->ec;
1991         int v;
1992
1993         if(i) v = AV_RB24(buf_p-trailer)+trailer;
1994         else  v = buf_p - c->bytestream_start;
1995         if(buf_p - c->bytestream_start < v){
1996             av_log(avctx, AV_LOG_ERROR, "Slice pointer chain broken\n");
1997             return -1;
1998         }
1999         buf_p -= v;
2000
2001         if(f->ec){
2002             unsigned crc = av_crc(av_crc_get_table(AV_CRC_32_IEEE), 0, buf_p, v);
2003             if(crc){
2004                 av_log(f->avctx, AV_LOG_ERROR, "CRC mismatch %X!\n", crc);
2005             }
2006         }
2007
2008         if(i){
2009             ff_init_range_decoder(&fs->c, buf_p, v);
2010         }
2011     }
2012
2013     avctx->execute(avctx, decode_slice, &f->slice_context[0], NULL, f->slice_count, sizeof(void*));
2014     f->picture_number++;
2015
2016     *picture= *p;
2017     *data_size = sizeof(AVFrame);
2018
2019     return buf_size;
2020 }
2021
2022 AVCodec ff_ffv1_decoder = {
2023     .name           = "ffv1",
2024     .type           = AVMEDIA_TYPE_VIDEO,
2025     .id             = CODEC_ID_FFV1,
2026     .priv_data_size = sizeof(FFV1Context),
2027     .init           = decode_init,
2028     .close          = common_end,
2029     .decode         = decode_frame,
2030     .capabilities   = CODEC_CAP_DR1 /*| CODEC_CAP_DRAW_HORIZ_BAND*/ |
2031                       CODEC_CAP_SLICE_THREADS,
2032     .long_name      = NULL_IF_CONFIG_SMALL("FFmpeg video codec #1"),
2033 };
2034
2035 #if CONFIG_FFV1_ENCODER
2036 AVCodec ff_ffv1_encoder = {
2037     .name           = "ffv1",
2038     .type           = AVMEDIA_TYPE_VIDEO,
2039     .id             = CODEC_ID_FFV1,
2040     .priv_data_size = sizeof(FFV1Context),
2041     .init           = encode_init,
2042     .encode2        = encode_frame,
2043     .close          = common_end,
2044     .capabilities   = CODEC_CAP_SLICE_THREADS,
2045     .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},
2046     .long_name      = NULL_IF_CONFIG_SMALL("FFmpeg video codec #1"),
2047 };
2048 #endif