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