ffv1: add examples of supported slices counts
[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 if(f->version < 3){
664         put_symbol(c, state, f->slice_count, 0);
665         for(i=0; i<f->slice_count; i++){
666             FFV1Context *fs= f->slice_context[i];
667             put_symbol(c, state, (fs->slice_x     +1)*f->num_h_slices / f->width   , 0);
668             put_symbol(c, state, (fs->slice_y     +1)*f->num_v_slices / f->height  , 0);
669             put_symbol(c, state, (fs->slice_width +1)*f->num_h_slices / f->width -1, 0);
670             put_symbol(c, state, (fs->slice_height+1)*f->num_v_slices / f->height-1, 0);
671             for(j=0; j<f->plane_count; j++){
672                 put_symbol(c, state, f->plane[j].quant_table_index, 0);
673                 av_assert0(f->plane[j].quant_table_index == f->avctx->context_model);
674             }
675         }
676     }
677 }
678 #endif /* CONFIG_FFV1_ENCODER */
679
680 static av_cold int common_init(AVCodecContext *avctx){
681     FFV1Context *s = avctx->priv_data;
682
683     s->avctx= avctx;
684     s->flags= avctx->flags;
685
686     avcodec_get_frame_defaults(&s->picture);
687
688     ff_dsputil_init(&s->dsp, avctx);
689
690     s->width = avctx->width;
691     s->height= avctx->height;
692
693     assert(s->width && s->height);
694     //defaults
695     s->num_h_slices=1;
696     s->num_v_slices=1;
697
698
699     return 0;
700 }
701
702 static int init_slice_state(FFV1Context *f, FFV1Context *fs){
703     int j;
704
705         fs->plane_count= f->plane_count;
706         fs->transparency= f->transparency;
707         for(j=0; j<f->plane_count; j++){
708             PlaneContext * const p= &fs->plane[j];
709
710             if(fs->ac){
711                 if(!p->    state) p->    state= av_malloc(CONTEXT_SIZE*p->context_count*sizeof(uint8_t));
712                 if(!p->    state)
713                     return AVERROR(ENOMEM);
714             }else{
715                 if(!p->vlc_state) p->vlc_state= av_malloc(p->context_count*sizeof(VlcState));
716                 if(!p->vlc_state)
717                     return AVERROR(ENOMEM);
718             }
719         }
720
721         if (fs->ac>1){
722             //FIXME only redo if state_transition changed
723             for(j=1; j<256; j++){
724                 fs->c.one_state [    j]= fs->state_transition[j];
725                 fs->c.zero_state[256-j]= 256-fs->c.one_state [j];
726             }
727         }
728
729     return 0;
730 }
731
732 static int init_slices_state(FFV1Context *f){
733     int i;
734     for(i=0; i<f->slice_count; i++){
735         FFV1Context *fs= f->slice_context[i];
736         if(init_slice_state(f, fs) < 0)
737             return -1;
738     }
739     return 0;
740 }
741
742 static av_cold int init_slice_contexts(FFV1Context *f){
743     int i;
744
745     f->slice_count= f->num_h_slices * f->num_v_slices;
746
747     for(i=0; i<f->slice_count; i++){
748         FFV1Context *fs= av_mallocz(sizeof(*fs));
749         int sx= i % f->num_h_slices;
750         int sy= i / f->num_h_slices;
751         int sxs= f->avctx->width * sx    / f->num_h_slices;
752         int sxe= f->avctx->width *(sx+1) / f->num_h_slices;
753         int sys= f->avctx->height* sy    / f->num_v_slices;
754         int sye= f->avctx->height*(sy+1) / f->num_v_slices;
755         f->slice_context[i]= fs;
756         memcpy(fs, f, sizeof(*fs));
757         memset(fs->rc_stat2, 0, sizeof(fs->rc_stat2));
758
759         fs->slice_width = sxe - sxs;
760         fs->slice_height= sye - sys;
761         fs->slice_x     = sxs;
762         fs->slice_y     = sys;
763
764         fs->sample_buffer = av_malloc(3*4 * (fs->width+6) * sizeof(*fs->sample_buffer));
765         if (!fs->sample_buffer)
766             return AVERROR(ENOMEM);
767     }
768     return 0;
769 }
770
771 static int allocate_initial_states(FFV1Context *f){
772     int i;
773
774     for(i=0; i<f->quant_table_count; i++){
775         f->initial_states[i]= av_malloc(f->context_count[i]*sizeof(*f->initial_states[i]));
776         if(!f->initial_states[i])
777             return AVERROR(ENOMEM);
778         memset(f->initial_states[i], 128, f->context_count[i]*sizeof(*f->initial_states[i]));
779     }
780     return 0;
781 }
782
783 #if CONFIG_FFV1_ENCODER
784 static int write_extra_header(FFV1Context *f){
785     RangeCoder * const c= &f->c;
786     uint8_t state[CONTEXT_SIZE];
787     int i, j, k;
788     uint8_t state2[32][CONTEXT_SIZE];
789     unsigned v;
790
791     memset(state2, 128, sizeof(state2));
792     memset(state, 128, sizeof(state));
793
794     f->avctx->extradata= av_malloc(f->avctx->extradata_size= 10000 + (11*11*5*5*5+11*11*11)*32);
795     ff_init_range_encoder(c, f->avctx->extradata, f->avctx->extradata_size);
796     ff_build_rac_states(c, 0.05*(1LL<<32), 256-8);
797
798     put_symbol(c, state, f->version, 0);
799     if(f->version > 2)
800         put_symbol(c, state, f->minor_version, 0);
801     put_symbol(c, state, f->ac, 0);
802     if(f->ac>1){
803         for(i=1; i<256; i++){
804             put_symbol(c, state, f->state_transition[i] - c->one_state[i], 1);
805         }
806     }
807     put_symbol(c, state, f->colorspace, 0); //YUV cs type
808     put_symbol(c, state, f->bits_per_raw_sample, 0);
809     put_rac(c, state, f->chroma_planes);
810     put_symbol(c, state, f->chroma_h_shift, 0);
811     put_symbol(c, state, f->chroma_v_shift, 0);
812     put_rac(c, state, f->transparency);
813     put_symbol(c, state, f->num_h_slices-1, 0);
814     put_symbol(c, state, f->num_v_slices-1, 0);
815
816     put_symbol(c, state, f->quant_table_count, 0);
817     for(i=0; i<f->quant_table_count; i++)
818         write_quant_tables(c, f->quant_tables[i]);
819
820     for(i=0; i<f->quant_table_count; i++){
821         for(j=0; j<f->context_count[i]*CONTEXT_SIZE; j++)
822             if(f->initial_states[i] && f->initial_states[i][0][j] != 128)
823                 break;
824         if(j<f->context_count[i]*CONTEXT_SIZE){
825             put_rac(c, state, 1);
826             for(j=0; j<f->context_count[i]; j++){
827                 for(k=0; k<CONTEXT_SIZE; k++){
828                     int pred= j ? f->initial_states[i][j-1][k] : 128;
829                     put_symbol(c, state2[k], (int8_t)(f->initial_states[i][j][k]-pred), 1);
830                 }
831             }
832         }else{
833             put_rac(c, state, 0);
834         }
835     }
836
837     if(f->version > 2){
838         put_symbol(c, state, f->ec, 0);
839     }
840
841     f->avctx->extradata_size= ff_rac_terminate(c);
842     v = av_crc(av_crc_get_table(AV_CRC_32_IEEE), 0, f->avctx->extradata, f->avctx->extradata_size);
843     AV_WL32(f->avctx->extradata + f->avctx->extradata_size, v);
844     f->avctx->extradata_size += 4;
845
846     return 0;
847 }
848
849 static int sort_stt(FFV1Context *s, uint8_t stt[256]){
850     int i,i2,changed,print=0;
851
852     do{
853         changed=0;
854         for(i=12; i<244; i++){
855             for(i2=i+1; i2<245 && i2<i+4; i2++){
856 #define COST(old, new) \
857     s->rc_stat[old][0]*-log2((256-(new))/256.0)\
858    +s->rc_stat[old][1]*-log2(     (new) /256.0)
859
860 #define COST2(old, new) \
861     COST(old, new)\
862    +COST(256-(old), 256-(new))
863
864                 double size0= COST2(i, i ) + COST2(i2, i2);
865                 double sizeX= COST2(i, i2) + COST2(i2, i );
866                 if(sizeX < size0 && i!=128 && i2!=128){
867                     int j;
868                     FFSWAP(int, stt[    i], stt[    i2]);
869                     FFSWAP(int, s->rc_stat[i    ][0],s->rc_stat[    i2][0]);
870                     FFSWAP(int, s->rc_stat[i    ][1],s->rc_stat[    i2][1]);
871                     if(i != 256-i2){
872                         FFSWAP(int, stt[256-i], stt[256-i2]);
873                         FFSWAP(int, s->rc_stat[256-i][0],s->rc_stat[256-i2][0]);
874                         FFSWAP(int, s->rc_stat[256-i][1],s->rc_stat[256-i2][1]);
875                     }
876                     for(j=1; j<256; j++){
877                         if     (stt[j] == i ) stt[j] = i2;
878                         else if(stt[j] == i2) stt[j] = i ;
879                         if(i != 256-i2){
880                             if     (stt[256-j] == 256-i ) stt[256-j] = 256-i2;
881                             else if(stt[256-j] == 256-i2) stt[256-j] = 256-i ;
882                         }
883                     }
884                     print=changed=1;
885                 }
886             }
887         }
888     }while(changed);
889     return print;
890 }
891
892 static av_cold int encode_init(AVCodecContext *avctx)
893 {
894     FFV1Context *s = avctx->priv_data;
895     int i, j, k, m;
896
897     common_init(avctx);
898
899     s->version=0;
900
901     if((avctx->flags & (CODEC_FLAG_PASS1|CODEC_FLAG_PASS2)) || avctx->slices>1)
902         s->version = FFMAX(s->version, 2);
903
904     if(avctx->level == 3){
905         s->version = 3;
906         s->ec = 1;
907     }
908
909     if(s->version >= 2 && avctx->strict_std_compliance > FF_COMPLIANCE_EXPERIMENTAL) {
910         av_log(avctx, AV_LOG_ERROR, "Version 2 needed for requested features but version 2 is experimental and not enabled\n");
911         return -1;
912     }
913
914     s->ac= avctx->coder_type ? 2:0;
915
916     if(s->ac>1)
917         for(i=1; i<256; i++)
918             s->state_transition[i]=ver2_state[i];
919
920     s->plane_count=3;
921     switch(avctx->pix_fmt){
922     case PIX_FMT_YUV444P9:
923     case PIX_FMT_YUV422P9:
924     case PIX_FMT_YUV420P9:
925         if (!avctx->bits_per_raw_sample)
926             s->bits_per_raw_sample = 9;
927     case PIX_FMT_YUV444P10:
928     case PIX_FMT_YUV420P10:
929     case PIX_FMT_YUV422P10:
930         s->packed_at_lsb = 1;
931         if (!avctx->bits_per_raw_sample && !s->bits_per_raw_sample)
932             s->bits_per_raw_sample = 10;
933     case PIX_FMT_GRAY16:
934     case PIX_FMT_YUV444P16:
935     case PIX_FMT_YUV422P16:
936     case PIX_FMT_YUV420P16:
937         if (!avctx->bits_per_raw_sample && !s->bits_per_raw_sample) {
938             s->bits_per_raw_sample = 16;
939         } else if (!s->bits_per_raw_sample){
940             s->bits_per_raw_sample = avctx->bits_per_raw_sample;
941         }
942         if(s->bits_per_raw_sample <=8){
943             av_log(avctx, AV_LOG_ERROR, "bits_per_raw_sample invalid\n");
944             return -1;
945         }
946         if(!s->ac){
947             av_log(avctx, AV_LOG_ERROR, "bits_per_raw_sample of more than 8 needs -coder 1 currently\n");
948             return -1;
949         }
950         s->version= FFMAX(s->version, 1);
951     case PIX_FMT_GRAY8:
952     case PIX_FMT_YUV444P:
953     case PIX_FMT_YUV440P:
954     case PIX_FMT_YUV422P:
955     case PIX_FMT_YUV420P:
956     case PIX_FMT_YUV411P:
957     case PIX_FMT_YUV410P:
958         s->chroma_planes= av_pix_fmt_descriptors[avctx->pix_fmt].nb_components < 3 ? 0 : 1;
959         s->colorspace= 0;
960         break;
961     case PIX_FMT_YUVA444P:
962     case PIX_FMT_YUVA420P:
963         s->chroma_planes= 1;
964         s->colorspace= 0;
965         s->transparency= 1;
966         break;
967     case PIX_FMT_RGB32:
968         s->colorspace= 1;
969         s->transparency= 1;
970         break;
971     case PIX_FMT_0RGB32:
972         s->colorspace= 1;
973         break;
974     default:
975         av_log(avctx, AV_LOG_ERROR, "format not supported\n");
976         return -1;
977     }
978     if (s->transparency) {
979         av_log(avctx, AV_LOG_WARNING, "Storing alpha plane, this will require a recent FFV1 decoder to playback!\n");
980     }
981     if (avctx->context_model > 1U) {
982         av_log(avctx, AV_LOG_ERROR, "Invalid context model %d, valid values are 0 and 1\n", avctx->context_model);
983         return AVERROR(EINVAL);
984     }
985
986     for(i=0; i<256; i++){
987         s->quant_table_count=2;
988         if(s->bits_per_raw_sample <=8){
989             s->quant_tables[0][0][i]=           quant11[i];
990             s->quant_tables[0][1][i]=        11*quant11[i];
991             s->quant_tables[0][2][i]=     11*11*quant11[i];
992             s->quant_tables[1][0][i]=           quant11[i];
993             s->quant_tables[1][1][i]=        11*quant11[i];
994             s->quant_tables[1][2][i]=     11*11*quant5 [i];
995             s->quant_tables[1][3][i]=   5*11*11*quant5 [i];
996             s->quant_tables[1][4][i]= 5*5*11*11*quant5 [i];
997         }else{
998             s->quant_tables[0][0][i]=           quant9_10bit[i];
999             s->quant_tables[0][1][i]=        11*quant9_10bit[i];
1000             s->quant_tables[0][2][i]=     11*11*quant9_10bit[i];
1001             s->quant_tables[1][0][i]=           quant9_10bit[i];
1002             s->quant_tables[1][1][i]=        11*quant9_10bit[i];
1003             s->quant_tables[1][2][i]=     11*11*quant5_10bit[i];
1004             s->quant_tables[1][3][i]=   5*11*11*quant5_10bit[i];
1005             s->quant_tables[1][4][i]= 5*5*11*11*quant5_10bit[i];
1006         }
1007     }
1008     s->context_count[0]= (11*11*11+1)/2;
1009     s->context_count[1]= (11*11*5*5*5+1)/2;
1010     memcpy(s->quant_table, s->quant_tables[avctx->context_model], sizeof(s->quant_table));
1011
1012     for(i=0; i<s->plane_count; i++){
1013         PlaneContext * const p= &s->plane[i];
1014
1015         memcpy(p->quant_table, s->quant_table, sizeof(p->quant_table));
1016         p->quant_table_index= avctx->context_model;
1017         p->context_count= s->context_count[p->quant_table_index];
1018     }
1019
1020     if(allocate_initial_states(s) < 0)
1021         return AVERROR(ENOMEM);
1022
1023     avctx->coded_frame= &s->picture;
1024     if(!s->transparency)
1025         s->plane_count= 2;
1026     avcodec_get_chroma_sub_sample(avctx->pix_fmt, &s->chroma_h_shift, &s->chroma_v_shift);
1027
1028     s->picture_number=0;
1029
1030     if(avctx->flags & (CODEC_FLAG_PASS1|CODEC_FLAG_PASS2)){
1031         for(i=0; i<s->quant_table_count; i++){
1032             s->rc_stat2[i]= av_mallocz(s->context_count[i]*sizeof(*s->rc_stat2[i]));
1033             if(!s->rc_stat2[i])
1034                 return AVERROR(ENOMEM);
1035         }
1036     }
1037     if(avctx->stats_in){
1038         char *p= avctx->stats_in;
1039         uint8_t best_state[256][256];
1040         int gob_count=0;
1041         char *next;
1042
1043         av_assert0(s->version>=2);
1044
1045         for(;;){
1046             for(j=0; j<256; j++){
1047                 for(i=0; i<2; i++){
1048                     s->rc_stat[j][i]= strtol(p, &next, 0);
1049                     if(next==p){
1050                         av_log(avctx, AV_LOG_ERROR, "2Pass file invalid at %d %d [%s]\n", j,i,p);
1051                         return -1;
1052                     }
1053                     p=next;
1054                 }
1055             }
1056             for(i=0; i<s->quant_table_count; i++){
1057                 for(j=0; j<s->context_count[i]; j++){
1058                     for(k=0; k<32; k++){
1059                         for(m=0; m<2; m++){
1060                             s->rc_stat2[i][j][k][m]= strtol(p, &next, 0);
1061                             if(next==p){
1062                                 av_log(avctx, AV_LOG_ERROR, "2Pass file invalid at %d %d %d %d [%s]\n", i,j,k,m,p);
1063                                 return -1;
1064                             }
1065                             p=next;
1066                         }
1067                     }
1068                 }
1069             }
1070             gob_count= strtol(p, &next, 0);
1071             if(next==p || gob_count <0){
1072                 av_log(avctx, AV_LOG_ERROR, "2Pass file invalid\n");
1073                 return -1;
1074             }
1075             p=next;
1076             while(*p=='\n' || *p==' ') p++;
1077             if(p[0]==0) break;
1078         }
1079         sort_stt(s, s->state_transition);
1080
1081         find_best_state(best_state, s->state_transition);
1082
1083         for(i=0; i<s->quant_table_count; i++){
1084             for(j=0; j<s->context_count[i]; j++){
1085                 for(k=0; k<32; k++){
1086                     double p= 128;
1087                     if(s->rc_stat2[i][j][k][0]+s->rc_stat2[i][j][k][1]){
1088                         p=256.0*s->rc_stat2[i][j][k][1] / (s->rc_stat2[i][j][k][0]+s->rc_stat2[i][j][k][1]);
1089                     }
1090                     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)];
1091                 }
1092             }
1093         }
1094     }
1095
1096     if(s->version>1){
1097         for(s->num_v_slices=2; s->num_v_slices<9; s->num_v_slices++){
1098             for(s->num_h_slices=s->num_v_slices; s->num_h_slices<2*s->num_v_slices; s->num_h_slices++){
1099                 if(avctx->slices == s->num_h_slices * s->num_v_slices && avctx->slices <= 64)
1100                     goto slices_ok;
1101             }
1102         }
1103         av_log(avctx, AV_LOG_ERROR, "Unsupported number %d of slices requested, please specify a supported number with -slices (ex:4,6,9,12,16, ...)\n", avctx->slices);
1104         return -1;
1105         slices_ok:
1106         write_extra_header(s);
1107     }
1108
1109     if(init_slice_contexts(s) < 0)
1110         return -1;
1111     if(init_slices_state(s) < 0)
1112         return -1;
1113
1114 #define STATS_OUT_SIZE 1024*1024*6
1115     if(avctx->flags & CODEC_FLAG_PASS1){
1116         avctx->stats_out= av_mallocz(STATS_OUT_SIZE);
1117         for(i=0; i<s->quant_table_count; i++){
1118             for(j=0; j<s->slice_count; j++){
1119                 FFV1Context *sf= s->slice_context[j];
1120                 av_assert0(!sf->rc_stat2[i]);
1121                 sf->rc_stat2[i]= av_mallocz(s->context_count[i]*sizeof(*sf->rc_stat2[i]));
1122                 if(!sf->rc_stat2[i])
1123                     return AVERROR(ENOMEM);
1124             }
1125         }
1126     }
1127
1128     return 0;
1129 }
1130 #endif /* CONFIG_FFV1_ENCODER */
1131
1132
1133 static void clear_slice_state(FFV1Context *f, FFV1Context *fs){
1134     int i, j;
1135
1136         for(i=0; i<f->plane_count; i++){
1137             PlaneContext *p= &fs->plane[i];
1138
1139             p->interlace_bit_state[0]= 128;
1140             p->interlace_bit_state[1]= 128;
1141
1142             if(fs->ac){
1143                 if(f->initial_states[p->quant_table_index]){
1144                     memcpy(p->state, f->initial_states[p->quant_table_index], CONTEXT_SIZE*p->context_count);
1145                 }else
1146                 memset(p->state, 128, CONTEXT_SIZE*p->context_count);
1147             }else{
1148                 for(j=0; j<p->context_count; j++){
1149                     p->vlc_state[j].drift= 0;
1150                     p->vlc_state[j].error_sum= 4; //FFMAX((RANGE + 32)/64, 2);
1151                     p->vlc_state[j].bias= 0;
1152                     p->vlc_state[j].count= 1;
1153                 }
1154             }
1155         }
1156 }
1157
1158 #if CONFIG_FFV1_ENCODER
1159
1160 static void encode_slice_header(FFV1Context *f, FFV1Context *fs){
1161     RangeCoder *c = &fs->c;
1162     uint8_t state[CONTEXT_SIZE];
1163     int j;
1164     memset(state, 128, sizeof(state));
1165
1166     put_symbol(c, state, (fs->slice_x     +1)*f->num_h_slices / f->width   , 0);
1167     put_symbol(c, state, (fs->slice_y     +1)*f->num_v_slices / f->height  , 0);
1168     put_symbol(c, state, (fs->slice_width +1)*f->num_h_slices / f->width -1, 0);
1169     put_symbol(c, state, (fs->slice_height+1)*f->num_v_slices / f->height-1, 0);
1170     for(j=0; j<f->plane_count; j++){
1171         put_symbol(c, state, f->plane[j].quant_table_index, 0);
1172         av_assert0(f->plane[j].quant_table_index == f->avctx->context_model);
1173     }
1174     if(!f->picture.interlaced_frame) put_symbol(c, state, 3, 0);
1175     else                             put_symbol(c, state, 1 + !f->picture.top_field_first, 0);
1176     put_symbol(c, state, f->picture.sample_aspect_ratio.num, 0);
1177     put_symbol(c, state, f->picture.sample_aspect_ratio.den, 0);
1178 }
1179
1180 static int encode_slice(AVCodecContext *c, void *arg){
1181     FFV1Context *fs= *(void**)arg;
1182     FFV1Context *f= fs->avctx->priv_data;
1183     int width = fs->slice_width;
1184     int height= fs->slice_height;
1185     int x= fs->slice_x;
1186     int y= fs->slice_y;
1187     AVFrame * const p= &f->picture;
1188     const int ps= (f->bits_per_raw_sample>8)+1;
1189
1190     if(p->key_frame)
1191         clear_slice_state(f, fs);
1192     if(f->version > 2){
1193         encode_slice_header(f, fs);
1194     }
1195     if(!fs->ac){
1196         fs->ac_byte_count = f->version > 2 || (!x&&!y) ? ff_rac_terminate(&fs->c) : 0;
1197         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);
1198     }
1199
1200     if(f->colorspace==0){
1201         const int chroma_width = -((-width )>>f->chroma_h_shift);
1202         const int chroma_height= -((-height)>>f->chroma_v_shift);
1203         const int cx= x>>f->chroma_h_shift;
1204         const int cy= y>>f->chroma_v_shift;
1205
1206         encode_plane(fs, p->data[0] + ps*x + y*p->linesize[0], width, height, p->linesize[0], 0);
1207
1208         if (f->chroma_planes){
1209             encode_plane(fs, p->data[1] + ps*cx+cy*p->linesize[1], chroma_width, chroma_height, p->linesize[1], 1);
1210             encode_plane(fs, p->data[2] + ps*cx+cy*p->linesize[2], chroma_width, chroma_height, p->linesize[2], 1);
1211         }
1212         if (fs->transparency)
1213             encode_plane(fs, p->data[3] + ps*x + y*p->linesize[3], width, height, p->linesize[3], 2);
1214     }else{
1215         encode_rgb_frame(fs, (uint32_t*)(p->data[0]) + ps*x + y*(p->linesize[0]/4), width, height, p->linesize[0]/4);
1216     }
1217     emms_c();
1218
1219     return 0;
1220 }
1221
1222 static int encode_frame(AVCodecContext *avctx, AVPacket *pkt,
1223                         const AVFrame *pict, int *got_packet)
1224 {
1225     FFV1Context *f = avctx->priv_data;
1226     RangeCoder * const c= &f->slice_context[0]->c;
1227     AVFrame * const p= &f->picture;
1228     int used_count= 0;
1229     uint8_t keystate=128;
1230     uint8_t *buf_p;
1231     int i, ret;
1232
1233     if ((ret = ff_alloc_packet2(avctx, pkt, avctx->width*avctx->height*((8*2+1+1)*4)/8
1234                                   + FF_MIN_BUFFER_SIZE)) < 0)
1235         return ret;
1236
1237     ff_init_range_encoder(c, pkt->data, pkt->size);
1238     ff_build_rac_states(c, 0.05*(1LL<<32), 256-8);
1239
1240     *p = *pict;
1241     p->pict_type= AV_PICTURE_TYPE_I;
1242
1243     if(avctx->gop_size==0 || f->picture_number % avctx->gop_size == 0){
1244         put_rac(c, &keystate, 1);
1245         p->key_frame= 1;
1246         f->gob_count++;
1247         write_header(f);
1248     }else{
1249         put_rac(c, &keystate, 0);
1250         p->key_frame= 0;
1251     }
1252
1253     if (f->ac>1){
1254         int i;
1255         for(i=1; i<256; i++){
1256             c->one_state[i]= f->state_transition[i];
1257             c->zero_state[256-i]= 256-c->one_state[i];
1258         }
1259     }
1260
1261     for(i=1; i<f->slice_count; i++){
1262         FFV1Context *fs= f->slice_context[i];
1263         uint8_t *start = pkt->data + (pkt->size-used_count)*i/f->slice_count;
1264         int len = pkt->size/f->slice_count;
1265
1266         ff_init_range_encoder(&fs->c, start, len);
1267     }
1268     avctx->execute(avctx, encode_slice, &f->slice_context[0], NULL, f->slice_count, sizeof(void*));
1269
1270     buf_p = pkt->data;
1271     for(i=0; i<f->slice_count; i++){
1272         FFV1Context *fs= f->slice_context[i];
1273         int bytes;
1274
1275         if(fs->ac){
1276             uint8_t state=128;
1277             put_rac(&fs->c, &state, 0);
1278             bytes= ff_rac_terminate(&fs->c);
1279         }else{
1280             flush_put_bits(&fs->pb); //nicer padding FIXME
1281             bytes= fs->ac_byte_count + (put_bits_count(&fs->pb)+7)/8;
1282         }
1283         if(i>0 || f->version>2){
1284             av_assert0(bytes < pkt->size/f->slice_count);
1285             memmove(buf_p, fs->c.bytestream_start, bytes);
1286             av_assert0(bytes < (1<<24));
1287             AV_WB24(buf_p+bytes, bytes);
1288             bytes+=3;
1289         }
1290         if(f->ec){
1291             unsigned v;
1292             buf_p[bytes++] = 0;
1293             v = av_crc(av_crc_get_table(AV_CRC_32_IEEE), 0, buf_p, bytes);
1294             AV_WL32(buf_p + bytes, v); bytes += 4;
1295         }
1296         buf_p += bytes;
1297     }
1298
1299     if((avctx->flags&CODEC_FLAG_PASS1) && (f->picture_number&31)==0){
1300         int j, k, m;
1301         char *p= avctx->stats_out;
1302         char *end= p + STATS_OUT_SIZE;
1303
1304         memset(f->rc_stat, 0, sizeof(f->rc_stat));
1305         for(i=0; i<f->quant_table_count; i++)
1306             memset(f->rc_stat2[i], 0, f->context_count[i]*sizeof(*f->rc_stat2[i]));
1307
1308         for(j=0; j<f->slice_count; j++){
1309             FFV1Context *fs= f->slice_context[j];
1310             for(i=0; i<256; i++){
1311                 f->rc_stat[i][0] += fs->rc_stat[i][0];
1312                 f->rc_stat[i][1] += fs->rc_stat[i][1];
1313             }
1314             for(i=0; i<f->quant_table_count; i++){
1315                 for(k=0; k<f->context_count[i]; k++){
1316                     for(m=0; m<32; m++){
1317                         f->rc_stat2[i][k][m][0] += fs->rc_stat2[i][k][m][0];
1318                         f->rc_stat2[i][k][m][1] += fs->rc_stat2[i][k][m][1];
1319                     }
1320                 }
1321             }
1322         }
1323
1324         for(j=0; j<256; j++){
1325             snprintf(p, end-p, "%"PRIu64" %"PRIu64" ", f->rc_stat[j][0], f->rc_stat[j][1]);
1326             p+= strlen(p);
1327         }
1328         snprintf(p, end-p, "\n");
1329
1330         for(i=0; i<f->quant_table_count; i++){
1331             for(j=0; j<f->context_count[i]; j++){
1332                 for(m=0; m<32; m++){
1333                     snprintf(p, end-p, "%"PRIu64" %"PRIu64" ", f->rc_stat2[i][j][m][0], f->rc_stat2[i][j][m][1]);
1334                     p+= strlen(p);
1335                 }
1336             }
1337         }
1338         snprintf(p, end-p, "%d\n", f->gob_count);
1339     } else if(avctx->flags&CODEC_FLAG_PASS1)
1340         avctx->stats_out[0] = '\0';
1341
1342     f->picture_number++;
1343     pkt->size   = buf_p - pkt->data;
1344     pkt->flags |= AV_PKT_FLAG_KEY*p->key_frame;
1345     *got_packet = 1;
1346
1347     return 0;
1348 }
1349 #endif /* CONFIG_FFV1_ENCODER */
1350
1351 static av_cold int common_end(AVCodecContext *avctx){
1352     FFV1Context *s = avctx->priv_data;
1353     int i, j;
1354
1355     if (avctx->codec->decode && s->picture.data[0])
1356         avctx->release_buffer(avctx, &s->picture);
1357
1358     for(j=0; j<s->slice_count; j++){
1359         FFV1Context *fs= s->slice_context[j];
1360         for(i=0; i<s->plane_count; i++){
1361             PlaneContext *p= &fs->plane[i];
1362
1363             av_freep(&p->state);
1364             av_freep(&p->vlc_state);
1365         }
1366         av_freep(&fs->sample_buffer);
1367     }
1368
1369     av_freep(&avctx->stats_out);
1370     for(j=0; j<s->quant_table_count; j++){
1371         av_freep(&s->initial_states[j]);
1372         for(i=0; i<s->slice_count; i++){
1373             FFV1Context *sf= s->slice_context[i];
1374             av_freep(&sf->rc_stat2[j]);
1375         }
1376         av_freep(&s->rc_stat2[j]);
1377     }
1378
1379     for(i=0; i<s->slice_count; i++){
1380         av_freep(&s->slice_context[i]);
1381     }
1382
1383     return 0;
1384 }
1385
1386 static av_always_inline void decode_line(FFV1Context *s, int w,
1387                                          int16_t *sample[2],
1388                                          int plane_index, int bits)
1389 {
1390     PlaneContext * const p= &s->plane[plane_index];
1391     RangeCoder * const c= &s->c;
1392     int x;
1393     int run_count=0;
1394     int run_mode=0;
1395     int run_index= s->run_index;
1396
1397     for(x=0; x<w; x++){
1398         int diff, context, sign;
1399
1400         context= get_context(p, sample[1] + x, sample[0] + x, sample[1] + x);
1401         if(context < 0){
1402             context= -context;
1403             sign=1;
1404         }else
1405             sign=0;
1406
1407         av_assert2(context < p->context_count);
1408
1409         if(s->ac){
1410             diff= get_symbol_inline(c, p->state[context], 1);
1411         }else{
1412             if(context == 0 && run_mode==0) run_mode=1;
1413
1414             if(run_mode){
1415                 if(run_count==0 && run_mode==1){
1416                     if(get_bits1(&s->gb)){
1417                         run_count = 1<<ff_log2_run[run_index];
1418                         if(x + run_count <= w) run_index++;
1419                     }else{
1420                         if(ff_log2_run[run_index]) run_count = get_bits(&s->gb, ff_log2_run[run_index]);
1421                         else run_count=0;
1422                         if(run_index) run_index--;
1423                         run_mode=2;
1424                     }
1425                 }
1426                 run_count--;
1427                 if(run_count < 0){
1428                     run_mode=0;
1429                     run_count=0;
1430                     diff= get_vlc_symbol(&s->gb, &p->vlc_state[context], bits);
1431                     if(diff>=0) diff++;
1432                 }else
1433                     diff=0;
1434             }else
1435                 diff= get_vlc_symbol(&s->gb, &p->vlc_state[context], bits);
1436
1437 //            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));
1438         }
1439
1440         if(sign) diff= -diff;
1441
1442         sample[1][x]= (predict(sample[1] + x, sample[0] + x) + diff) & ((1<<bits)-1);
1443     }
1444     s->run_index= run_index;
1445 }
1446
1447 static void decode_plane(FFV1Context *s, uint8_t *src, int w, int h, int stride, int plane_index){
1448     int x, y;
1449     int16_t *sample[2];
1450     sample[0]=s->sample_buffer    +3;
1451     sample[1]=s->sample_buffer+w+6+3;
1452
1453     s->run_index=0;
1454
1455     memset(s->sample_buffer, 0, 2*(w+6)*sizeof(*s->sample_buffer));
1456
1457     for(y=0; y<h; y++){
1458         int16_t *temp = sample[0]; //FIXME try a normal buffer
1459
1460         sample[0]= sample[1];
1461         sample[1]= temp;
1462
1463         sample[1][-1]= sample[0][0  ];
1464         sample[0][ w]= sample[0][w-1];
1465
1466 //{START_TIMER
1467         if(s->avctx->bits_per_raw_sample <= 8){
1468             decode_line(s, w, sample, plane_index, 8);
1469             for(x=0; x<w; x++){
1470                 src[x + stride*y]= sample[1][x];
1471             }
1472         }else{
1473             decode_line(s, w, sample, plane_index, s->avctx->bits_per_raw_sample);
1474             if(s->packed_at_lsb){
1475                 for(x=0; x<w; x++){
1476                     ((uint16_t*)(src + stride*y))[x]= sample[1][x];
1477                 }
1478             }else{
1479                 for(x=0; x<w; x++){
1480                     ((uint16_t*)(src + stride*y))[x]= sample[1][x] << (16 - s->avctx->bits_per_raw_sample);
1481                 }
1482             }
1483         }
1484 //STOP_TIMER("decode-line")}
1485     }
1486 }
1487
1488 static void decode_rgb_frame(FFV1Context *s, uint32_t *src, int w, int h, int stride){
1489     int x, y, p;
1490     int16_t *sample[4][2];
1491     for(x=0; x<4; x++){
1492         sample[x][0] = s->sample_buffer +  x*2   *(w+6) + 3;
1493         sample[x][1] = s->sample_buffer + (x*2+1)*(w+6) + 3;
1494     }
1495
1496     s->run_index=0;
1497
1498     memset(s->sample_buffer, 0, 8*(w+6)*sizeof(*s->sample_buffer));
1499
1500     for(y=0; y<h; y++){
1501         for(p=0; p<3 + s->transparency; p++){
1502             int16_t *temp = sample[p][0]; //FIXME try a normal buffer
1503
1504             sample[p][0]= sample[p][1];
1505             sample[p][1]= temp;
1506
1507             sample[p][1][-1]= sample[p][0][0  ];
1508             sample[p][0][ w]= sample[p][0][w-1];
1509             decode_line(s, w, sample[p], (p+1)/2, 9);
1510         }
1511         for(x=0; x<w; x++){
1512             int g= sample[0][1][x];
1513             int b= sample[1][1][x];
1514             int r= sample[2][1][x];
1515             int a= sample[3][1][x];
1516
1517 //            assert(g>=0 && b>=0 && r>=0);
1518 //            assert(g<256 && b<512 && r<512);
1519
1520             b -= 0x100;
1521             r -= 0x100;
1522             g -= (b + r)>>2;
1523             b += g;
1524             r += g;
1525
1526             src[x + stride*y]= b + (g<<8) + (r<<16) + (a<<24);
1527         }
1528     }
1529 }
1530
1531 static int decode_slice_header(FFV1Context *f, FFV1Context *fs){
1532     RangeCoder *c = &fs->c;
1533     uint8_t state[CONTEXT_SIZE];
1534     unsigned ps, i, context_count;
1535     memset(state, 128, sizeof(state));
1536
1537     av_assert0(f->version > 2);
1538
1539     fs->slice_x     = get_symbol(c, state, 0)   *f->width ;
1540     fs->slice_y     = get_symbol(c, state, 0)   *f->height;
1541     fs->slice_width =(get_symbol(c, state, 0)+1)*f->width  + fs->slice_x;
1542     fs->slice_height=(get_symbol(c, state, 0)+1)*f->height + fs->slice_y;
1543
1544     fs->slice_x /= f->num_h_slices;
1545     fs->slice_y /= f->num_v_slices;
1546     fs->slice_width  = fs->slice_width /f->num_h_slices - fs->slice_x;
1547     fs->slice_height = fs->slice_height/f->num_v_slices - fs->slice_y;
1548     if((unsigned)fs->slice_width > f->width || (unsigned)fs->slice_height > f->height)
1549         return -1;
1550     if(    (unsigned)fs->slice_x + (uint64_t)fs->slice_width  > f->width
1551         || (unsigned)fs->slice_y + (uint64_t)fs->slice_height > f->height)
1552         return -1;
1553
1554     for(i=0; i<f->plane_count; i++){
1555         PlaneContext * const p= &fs->plane[i];
1556         int idx=get_symbol(c, state, 0);
1557         if(idx > (unsigned)f->quant_table_count){
1558             av_log(f->avctx, AV_LOG_ERROR, "quant_table_index out of range\n");
1559             return -1;
1560         }
1561         p->quant_table_index= idx;
1562         memcpy(p->quant_table, f->quant_tables[idx], sizeof(p->quant_table));
1563         context_count= f->context_count[idx];
1564
1565         if(p->context_count < context_count){
1566             av_freep(&p->state);
1567             av_freep(&p->vlc_state);
1568         }
1569         p->context_count= context_count;
1570     }
1571
1572     ps = get_symbol(c, state, 0);
1573     if(ps==1){
1574         f->picture.interlaced_frame = 1;
1575         f->picture.top_field_first  = 1;
1576     } else if(ps==2){
1577         f->picture.interlaced_frame = 1;
1578         f->picture.top_field_first  = 0;
1579     } else if(ps==3){
1580         f->picture.interlaced_frame = 0;
1581     }
1582     f->picture.sample_aspect_ratio.num = get_symbol(c, state, 0);
1583     f->picture.sample_aspect_ratio.den = get_symbol(c, state, 0);
1584
1585     return 0;
1586 }
1587
1588 static int decode_slice(AVCodecContext *c, void *arg){
1589     FFV1Context *fs= *(void**)arg;
1590     FFV1Context *f= fs->avctx->priv_data;
1591     int width, height, x, y;
1592     const int ps= (c->bits_per_raw_sample>8)+1;
1593     AVFrame * const p= &f->picture;
1594
1595     if(f->version > 2){
1596         if(init_slice_state(f, fs) < 0)
1597             return AVERROR(ENOMEM);
1598         if(decode_slice_header(f, fs) < 0)
1599             return AVERROR_INVALIDDATA;
1600     }
1601     if(init_slice_state(f, fs) < 0)
1602         return AVERROR(ENOMEM);
1603     if(f->picture.key_frame)
1604         clear_slice_state(f, fs);
1605     width = fs->slice_width;
1606     height= fs->slice_height;
1607     x= fs->slice_x;
1608     y= fs->slice_y;
1609
1610     if(!fs->ac){
1611         fs->ac_byte_count = f->version > 2 || (!x&&!y) ? fs->c.bytestream - fs->c.bytestream_start - 1 : 0;
1612         init_get_bits(&fs->gb,
1613                       fs->c.bytestream_start + fs->ac_byte_count,
1614                       (fs->c.bytestream_end - fs->c.bytestream_start - fs->ac_byte_count) * 8);
1615     }
1616
1617     av_assert1(width && height);
1618     if(f->colorspace==0){
1619         const int chroma_width = -((-width )>>f->chroma_h_shift);
1620         const int chroma_height= -((-height)>>f->chroma_v_shift);
1621         const int cx= x>>f->chroma_h_shift;
1622         const int cy= y>>f->chroma_v_shift;
1623         decode_plane(fs, p->data[0] + ps*x + y*p->linesize[0], width, height, p->linesize[0], 0);
1624
1625         if (f->chroma_planes){
1626             decode_plane(fs, p->data[1] + ps*cx+cy*p->linesize[1], chroma_width, chroma_height, p->linesize[1], 1);
1627             decode_plane(fs, p->data[2] + ps*cx+cy*p->linesize[2], chroma_width, chroma_height, p->linesize[2], 1);
1628         }
1629         if (fs->transparency)
1630             decode_plane(fs, p->data[3] + ps*x + y*p->linesize[3], width, height, p->linesize[3], 2);
1631     }else{
1632         decode_rgb_frame(fs, (uint32_t*)p->data[0] + ps*x + y*(p->linesize[0]/4), width, height, p->linesize[0]/4);
1633     }
1634
1635     emms_c();
1636
1637     return 0;
1638 }
1639
1640 static int read_quant_table(RangeCoder *c, int16_t *quant_table, int scale){
1641     int v;
1642     int i=0;
1643     uint8_t state[CONTEXT_SIZE];
1644
1645     memset(state, 128, sizeof(state));
1646
1647     for(v=0; i<128 ; v++){
1648         int len= get_symbol(c, state, 0) + 1;
1649
1650         if(len + i > 128) return -1;
1651
1652         while(len--){
1653             quant_table[i] = scale*v;
1654             i++;
1655 //printf("%2d ",v);
1656 //if(i%16==0) printf("\n");
1657         }
1658     }
1659
1660     for(i=1; i<128; i++){
1661         quant_table[256-i]= -quant_table[i];
1662     }
1663     quant_table[128]= -quant_table[127];
1664
1665     return 2*v - 1;
1666 }
1667
1668 static int read_quant_tables(RangeCoder *c, int16_t quant_table[MAX_CONTEXT_INPUTS][256]){
1669     int i;
1670     int context_count=1;
1671
1672     for(i=0; i<5; i++){
1673         context_count*= read_quant_table(c, quant_table[i], context_count);
1674         if(context_count > 32768U){
1675             return -1;
1676         }
1677     }
1678     return (context_count+1)/2;
1679 }
1680
1681 static int read_extra_header(FFV1Context *f){
1682     RangeCoder * const c= &f->c;
1683     uint8_t state[CONTEXT_SIZE];
1684     int i, j, k;
1685     uint8_t state2[32][CONTEXT_SIZE];
1686
1687     memset(state2, 128, sizeof(state2));
1688     memset(state, 128, sizeof(state));
1689
1690     ff_init_range_decoder(c, f->avctx->extradata, f->avctx->extradata_size);
1691     ff_build_rac_states(c, 0.05*(1LL<<32), 256-8);
1692
1693     f->version= get_symbol(c, state, 0);
1694     if(f->version > 2)
1695         f->minor_version= get_symbol(c, state, 0);
1696     f->ac= f->avctx->coder_type= get_symbol(c, state, 0);
1697     if(f->ac>1){
1698         for(i=1; i<256; i++){
1699             f->state_transition[i]= get_symbol(c, state, 1) + c->one_state[i];
1700         }
1701     }
1702     f->colorspace= get_symbol(c, state, 0); //YUV cs type
1703     f->avctx->bits_per_raw_sample= get_symbol(c, state, 0);
1704     f->chroma_planes= get_rac(c, state);
1705     f->chroma_h_shift= get_symbol(c, state, 0);
1706     f->chroma_v_shift= get_symbol(c, state, 0);
1707     f->transparency= get_rac(c, state);
1708     f->plane_count= 2 + f->transparency;
1709     f->num_h_slices= 1 + get_symbol(c, state, 0);
1710     f->num_v_slices= 1 + get_symbol(c, state, 0);
1711     if(f->num_h_slices > (unsigned)f->width || f->num_v_slices > (unsigned)f->height){
1712         av_log(f->avctx, AV_LOG_ERROR, "too many slices\n");
1713         return -1;
1714     }
1715
1716     f->quant_table_count= get_symbol(c, state, 0);
1717     if(f->quant_table_count > (unsigned)MAX_QUANT_TABLES)
1718         return -1;
1719     for(i=0; i<f->quant_table_count; i++){
1720         if((f->context_count[i]= read_quant_tables(c, f->quant_tables[i])) < 0){
1721             av_log(f->avctx, AV_LOG_ERROR, "read_quant_table error\n");
1722             return -1;
1723         }
1724     }
1725
1726     if(allocate_initial_states(f) < 0)
1727         return AVERROR(ENOMEM);
1728
1729     for(i=0; i<f->quant_table_count; i++){
1730         if(get_rac(c, state)){
1731             for(j=0; j<f->context_count[i]; j++){
1732                 for(k=0; k<CONTEXT_SIZE; k++){
1733                     int pred= j ? f->initial_states[i][j-1][k] : 128;
1734                     f->initial_states[i][j][k]= (pred+get_symbol(c, state2[k], 1))&0xFF;
1735                 }
1736             }
1737         }
1738     }
1739
1740     if(f->version > 2){
1741         f->ec = get_symbol(c, state, 0);
1742     }
1743
1744     if(f->version > 2){
1745         unsigned v;
1746         v = av_crc(av_crc_get_table(AV_CRC_32_IEEE), 0, f->avctx->extradata, f->avctx->extradata_size);
1747         if(v){
1748             av_log(f->avctx, AV_LOG_ERROR, "CRC mismatch %X!\n", v);
1749             return AVERROR_INVALIDDATA;
1750         }
1751     }
1752
1753     return 0;
1754 }
1755
1756 static int read_header(FFV1Context *f){
1757     uint8_t state[CONTEXT_SIZE];
1758     int i, j, context_count;
1759     RangeCoder * const c= &f->slice_context[0]->c;
1760
1761     memset(state, 128, sizeof(state));
1762
1763     if(f->version < 2){
1764         f->version= get_symbol(c, state, 0);
1765         f->ac= f->avctx->coder_type= get_symbol(c, state, 0);
1766         if(f->ac>1){
1767             for(i=1; i<256; i++){
1768                 f->state_transition[i]= get_symbol(c, state, 1) + c->one_state[i];
1769             }
1770         }
1771         f->colorspace= get_symbol(c, state, 0); //YUV cs type
1772         if(f->version>0)
1773             f->avctx->bits_per_raw_sample= get_symbol(c, state, 0);
1774         f->chroma_planes= get_rac(c, state);
1775         f->chroma_h_shift= get_symbol(c, state, 0);
1776         f->chroma_v_shift= get_symbol(c, state, 0);
1777         f->transparency= get_rac(c, state);
1778         f->plane_count= 2 + f->transparency;
1779     }
1780
1781     if(f->colorspace==0){
1782         if(!f->transparency && !f->chroma_planes){
1783             if (f->avctx->bits_per_raw_sample<=8)
1784                 f->avctx->pix_fmt= PIX_FMT_GRAY8;
1785             else
1786                 f->avctx->pix_fmt= PIX_FMT_GRAY16;
1787         }else if(f->avctx->bits_per_raw_sample<=8 && !f->transparency){
1788             switch(16*f->chroma_h_shift + f->chroma_v_shift){
1789             case 0x00: f->avctx->pix_fmt= PIX_FMT_YUV444P; break;
1790             case 0x01: f->avctx->pix_fmt= PIX_FMT_YUV440P; break;
1791             case 0x10: f->avctx->pix_fmt= PIX_FMT_YUV422P; break;
1792             case 0x11: f->avctx->pix_fmt= PIX_FMT_YUV420P; break;
1793             case 0x20: f->avctx->pix_fmt= PIX_FMT_YUV411P; break;
1794             case 0x22: f->avctx->pix_fmt= PIX_FMT_YUV410P; break;
1795             default:
1796                 av_log(f->avctx, AV_LOG_ERROR, "format not supported\n");
1797                 return -1;
1798             }
1799         }else if(f->avctx->bits_per_raw_sample<=8 && f->transparency){
1800             switch(16*f->chroma_h_shift + f->chroma_v_shift){
1801             case 0x00: f->avctx->pix_fmt= PIX_FMT_YUVA444P; break;
1802             case 0x11: f->avctx->pix_fmt= PIX_FMT_YUVA420P; break;
1803             default:
1804                 av_log(f->avctx, AV_LOG_ERROR, "format not supported\n");
1805                 return -1;
1806             }
1807         }else if(f->avctx->bits_per_raw_sample==9) {
1808             f->packed_at_lsb=1;
1809             switch(16*f->chroma_h_shift + f->chroma_v_shift){
1810             case 0x00: f->avctx->pix_fmt= PIX_FMT_YUV444P9; break;
1811             case 0x10: f->avctx->pix_fmt= PIX_FMT_YUV422P9; break;
1812             case 0x11: f->avctx->pix_fmt= PIX_FMT_YUV420P9; break;
1813             default:
1814                 av_log(f->avctx, AV_LOG_ERROR, "format not supported\n");
1815                 return -1;
1816             }
1817         }else if(f->avctx->bits_per_raw_sample==10) {
1818             f->packed_at_lsb=1;
1819             switch(16*f->chroma_h_shift + f->chroma_v_shift){
1820             case 0x00: f->avctx->pix_fmt= PIX_FMT_YUV444P10; break;
1821             case 0x10: f->avctx->pix_fmt= PIX_FMT_YUV422P10; break;
1822             case 0x11: f->avctx->pix_fmt= PIX_FMT_YUV420P10; break;
1823             default:
1824                 av_log(f->avctx, AV_LOG_ERROR, "format not supported\n");
1825                 return -1;
1826             }
1827         }else {
1828             switch(16*f->chroma_h_shift + f->chroma_v_shift){
1829             case 0x00: f->avctx->pix_fmt= PIX_FMT_YUV444P16; break;
1830             case 0x10: f->avctx->pix_fmt= PIX_FMT_YUV422P16; break;
1831             case 0x11: f->avctx->pix_fmt= PIX_FMT_YUV420P16; break;
1832             default:
1833                 av_log(f->avctx, AV_LOG_ERROR, "format not supported\n");
1834                 return -1;
1835             }
1836         }
1837     }else if(f->colorspace==1){
1838         if(f->chroma_h_shift || f->chroma_v_shift){
1839             av_log(f->avctx, AV_LOG_ERROR, "chroma subsampling not supported in this colorspace\n");
1840             return -1;
1841         }
1842         if(f->transparency) f->avctx->pix_fmt= PIX_FMT_RGB32;
1843         else                f->avctx->pix_fmt= PIX_FMT_0RGB32;
1844     }else{
1845         av_log(f->avctx, AV_LOG_ERROR, "colorspace not supported\n");
1846         return -1;
1847     }
1848
1849 //printf("%d %d %d\n", f->chroma_h_shift, f->chroma_v_shift,f->avctx->pix_fmt);
1850     if(f->version < 2){
1851         context_count= read_quant_tables(c, f->quant_table);
1852         if(context_count < 0){
1853                 av_log(f->avctx, AV_LOG_ERROR, "read_quant_table error\n");
1854                 return -1;
1855         }
1856     }else if(f->version < 3){
1857         f->slice_count= get_symbol(c, state, 0);
1858     }else{
1859         const uint8_t *p= c->bytestream_end;
1860         for(f->slice_count = 0; f->slice_count < MAX_SLICES && 3 < p - c->bytestream_start; f->slice_count++){
1861             int trailer = 3 + 5*!!f->ec;
1862             int size = AV_RB24(p-trailer);
1863             if(size + trailer > p - c->bytestream_start)
1864                 break;
1865             p -= size + trailer;
1866         }
1867     }
1868     if(f->slice_count > (unsigned)MAX_SLICES || f->slice_count <= 0){
1869         av_log(f->avctx, AV_LOG_ERROR, "slice count %d is invalid\n", f->slice_count);
1870         return -1;
1871     }
1872
1873     for(j=0; j<f->slice_count; j++){
1874         FFV1Context *fs= f->slice_context[j];
1875         fs->ac= f->ac;
1876         fs->packed_at_lsb= f->packed_at_lsb;
1877
1878         if(f->version == 2){
1879             fs->slice_x     = get_symbol(c, state, 0)   *f->width ;
1880             fs->slice_y     = get_symbol(c, state, 0)   *f->height;
1881             fs->slice_width =(get_symbol(c, state, 0)+1)*f->width  + fs->slice_x;
1882             fs->slice_height=(get_symbol(c, state, 0)+1)*f->height + fs->slice_y;
1883
1884             fs->slice_x /= f->num_h_slices;
1885             fs->slice_y /= f->num_v_slices;
1886             fs->slice_width  = fs->slice_width /f->num_h_slices - fs->slice_x;
1887             fs->slice_height = fs->slice_height/f->num_v_slices - fs->slice_y;
1888             if((unsigned)fs->slice_width > f->width || (unsigned)fs->slice_height > f->height)
1889                 return -1;
1890             if(    (unsigned)fs->slice_x + (uint64_t)fs->slice_width  > f->width
1891                 || (unsigned)fs->slice_y + (uint64_t)fs->slice_height > f->height)
1892                 return -1;
1893         }
1894
1895         for(i=0; i<f->plane_count; i++){
1896             PlaneContext * const p= &fs->plane[i];
1897
1898             if(f->version == 2){
1899                 int idx=get_symbol(c, state, 0);
1900                 if(idx > (unsigned)f->quant_table_count){
1901                     av_log(f->avctx, AV_LOG_ERROR, "quant_table_index out of range\n");
1902                     return -1;
1903                 }
1904                 p->quant_table_index= idx;
1905                 memcpy(p->quant_table, f->quant_tables[idx], sizeof(p->quant_table));
1906                 context_count= f->context_count[idx];
1907             }else{
1908                 memcpy(p->quant_table, f->quant_table, sizeof(p->quant_table));
1909             }
1910
1911             if(f->version <= 2){
1912                 if(p->context_count < context_count){
1913                     av_freep(&p->state);
1914                     av_freep(&p->vlc_state);
1915                 }
1916                 p->context_count= context_count;
1917             }
1918         }
1919     }
1920     return 0;
1921 }
1922
1923 static av_cold int decode_init(AVCodecContext *avctx)
1924 {
1925     FFV1Context *f = avctx->priv_data;
1926
1927     common_init(avctx);
1928
1929     if(avctx->extradata && read_extra_header(f) < 0)
1930         return -1;
1931
1932     if(init_slice_contexts(f) < 0)
1933         return -1;
1934
1935     return 0;
1936 }
1937
1938 static int decode_frame(AVCodecContext *avctx, void *data, int *data_size, AVPacket *avpkt){
1939     const uint8_t *buf = avpkt->data;
1940     int buf_size = avpkt->size;
1941     FFV1Context *f = avctx->priv_data;
1942     RangeCoder * const c= &f->slice_context[0]->c;
1943     AVFrame * const p= &f->picture;
1944     int bytes_read, i;
1945     uint8_t keystate= 128;
1946     const uint8_t *buf_p;
1947
1948     AVFrame *picture = data;
1949
1950     /* release previously stored data */
1951     if (p->data[0])
1952         avctx->release_buffer(avctx, p);
1953
1954     ff_init_range_decoder(c, buf, buf_size);
1955     ff_build_rac_states(c, 0.05*(1LL<<32), 256-8);
1956
1957
1958     p->pict_type= AV_PICTURE_TYPE_I; //FIXME I vs. P
1959     if(get_rac(c, &keystate)){
1960         p->key_frame= 1;
1961         f->key_frame_ok = 0;
1962         if(read_header(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
1973     p->reference= 0;
1974     if(avctx->get_buffer(avctx, p) < 0){
1975         av_log(avctx, AV_LOG_ERROR, "get_buffer() failed\n");
1976         return -1;
1977     }
1978
1979     if(avctx->debug&FF_DEBUG_PICT_INFO)
1980         av_log(avctx, AV_LOG_ERROR, "keyframe:%d coder:%d\n", p->key_frame, f->ac);
1981
1982     buf_p= buf + buf_size;
1983     for(i=f->slice_count-1; i>=0; i--){
1984         FFV1Context *fs= f->slice_context[i];
1985         int trailer = 3 + 5*!!f->ec;
1986         int v;
1987
1988         if(i || f->version>2) v = AV_RB24(buf_p-trailer)+trailer;
1989         else                  v = buf_p - c->bytestream_start;
1990         if(buf_p - c->bytestream_start < v){
1991             av_log(avctx, AV_LOG_ERROR, "Slice pointer chain broken\n");
1992             return -1;
1993         }
1994         buf_p -= v;
1995
1996         if(f->ec){
1997             unsigned crc = av_crc(av_crc_get_table(AV_CRC_32_IEEE), 0, buf_p, v);
1998             if(crc){
1999                 av_log(f->avctx, AV_LOG_ERROR, "CRC mismatch %X!\n", crc);
2000             }
2001         }
2002
2003         if(i){
2004             ff_init_range_decoder(&fs->c, buf_p, v);
2005         }
2006     }
2007
2008     avctx->execute(avctx, decode_slice, &f->slice_context[0], NULL, f->slice_count, sizeof(void*));
2009     f->picture_number++;
2010
2011     *picture= *p;
2012     *data_size = sizeof(AVFrame);
2013
2014     return buf_size;
2015 }
2016
2017 AVCodec ff_ffv1_decoder = {
2018     .name           = "ffv1",
2019     .type           = AVMEDIA_TYPE_VIDEO,
2020     .id             = CODEC_ID_FFV1,
2021     .priv_data_size = sizeof(FFV1Context),
2022     .init           = decode_init,
2023     .close          = common_end,
2024     .decode         = decode_frame,
2025     .capabilities   = CODEC_CAP_DR1 /*| CODEC_CAP_DRAW_HORIZ_BAND*/ |
2026                       CODEC_CAP_SLICE_THREADS,
2027     .long_name      = NULL_IF_CONFIG_SMALL("FFmpeg video codec #1"),
2028 };
2029
2030 #if CONFIG_FFV1_ENCODER
2031 AVCodec ff_ffv1_encoder = {
2032     .name           = "ffv1",
2033     .type           = AVMEDIA_TYPE_VIDEO,
2034     .id             = CODEC_ID_FFV1,
2035     .priv_data_size = sizeof(FFV1Context),
2036     .init           = encode_init,
2037     .encode2        = encode_frame,
2038     .close          = common_end,
2039     .capabilities   = CODEC_CAP_SLICE_THREADS,
2040     .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},
2041     .long_name      = NULL_IF_CONFIG_SMALL("FFmpeg video codec #1"),
2042 };
2043 #endif