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