FFV1 initial state 2pass code.
[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 "get_bits.h"
30 #include "put_bits.h"
31 #include "dsputil.h"
32 #include "rangecoder.h"
33 #include "golomb.h"
34 #include "mathops.h"
35 #include "libavutil/avassert.h"
36
37 #define MAX_PLANES 4
38 #define CONTEXT_SIZE 32
39
40 #define MAX_QUANT_TABLES 8
41 #define MAX_CONTEXT_INPUTS 5
42
43 extern const uint8_t ff_log2_run[32];
44
45 static const int8_t quant3[256]={
46  0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
47  1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
48  1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
49  1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
50  1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
51  1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
52  1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
53  1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
54 -1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-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,-1,-1,-1,-1,-1,-1,-1,-1,-1,-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,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,
61 -1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1, 0,
62 };
63
64 static const int8_t quant5_10bit[256]={
65  0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1,
66  1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
67  1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
68  1, 1, 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, 2,
70  2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2,
71  2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2,
72  2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2,
73 -2,-2,-2,-2,-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,-1,
78 -1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,
79 -1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,
80 -1,-1,-1,-1,-1,-1,-0,-0,-0,-0,-0,-0,-0,-0,-0,-0,
81 };
82
83 static const int8_t quant5[256]={
84  0, 1, 1, 1, 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, 2, 2, 2,
92 -2,-2,-2,-2,-2,-2,-2,-2,-2,-2,-2,-2,-2,-2,-2,-2,
93 -2,-2,-2,-2,-2,-2,-2,-2,-2,-2,-2,-2,-2,-2,-2,-2,
94 -2,-2,-2,-2,-2,-2,-2,-2,-2,-2,-2,-2,-2,-2,-2,-2,
95 -2,-2,-2,-2,-2,-2,-2,-2,-2,-2,-2,-2,-2,-2,-2,-2,
96 -2,-2,-2,-2,-2,-2,-2,-2,-2,-2,-2,-2,-2,-2,-2,-2,
97 -2,-2,-2,-2,-2,-2,-2,-2,-2,-2,-2,-2,-2,-2,-2,-2,
98 -2,-2,-2,-2,-2,-2,-2,-2,-2,-2,-2,-2,-2,-2,-2,-2,
99 -2,-2,-2,-2,-2,-2,-2,-2,-2,-2,-2,-2,-2,-1,-1,-1,
100 };
101 static const int8_t quant7[256]={
102  0, 1, 1, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2,
103  2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2,
104  2, 2, 2, 2, 2, 2, 2, 2, 3, 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, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3,
107  3, 3, 3, 3, 3, 3, 3, 3, 3, 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, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3,
110 -3,-3,-3,-3,-3,-3,-3,-3,-3,-3,-3,-3,-3,-3,-3,-3,
111 -3,-3,-3,-3,-3,-3,-3,-3,-3,-3,-3,-3,-3,-3,-3,-3,
112 -3,-3,-3,-3,-3,-3,-3,-3,-3,-3,-3,-3,-3,-3,-3,-3,
113 -3,-3,-3,-3,-3,-3,-3,-3,-3,-3,-3,-3,-3,-3,-3,-3,
114 -3,-3,-3,-3,-3,-3,-3,-3,-3,-3,-3,-3,-3,-3,-3,-3,
115 -3,-3,-3,-3,-3,-3,-3,-3,-3,-2,-2,-2,-2,-2,-2,-2,
116 -2,-2,-2,-2,-2,-2,-2,-2,-2,-2,-2,-2,-2,-2,-2,-2,
117 -2,-2,-2,-2,-2,-2,-2,-2,-2,-2,-2,-2,-2,-2,-1,-1,
118 };
119 static const int8_t quant9[256]={
120  0, 1, 1, 2, 2, 2, 2, 3, 3, 3, 3, 3, 3, 3, 3, 3,
121  3, 3, 3, 3, 3, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4,
122  4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4,
123  4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4,
124  4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 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, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4,
127  4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 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,-4,-4,-4,-4,-4,-4,-4,-4,-4,-4,-4,
130 -4,-4,-4,-4,-4,-4,-4,-4,-4,-4,-4,-4,-4,-4,-4,-4,
131 -4,-4,-4,-4,-4,-4,-4,-4,-4,-4,-4,-4,-4,-4,-4,-4,
132 -4,-4,-4,-4,-4,-4,-4,-4,-4,-4,-4,-4,-4,-4,-4,-4,
133 -4,-4,-4,-4,-4,-4,-4,-4,-4,-4,-4,-4,-4,-4,-4,-4,
134 -4,-4,-4,-4,-4,-4,-4,-4,-4,-4,-4,-4,-3,-3,-3,-3,
135 -3,-3,-3,-3,-3,-3,-3,-3,-3,-3,-2,-2,-2,-2,-1,-1,
136 };
137 static const int8_t quant9_10bit[256]={
138  0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 2, 2, 2,
139  2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 3, 3, 3, 3, 3,
140  3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3,
141  3, 3, 3, 3, 3, 3, 3, 3, 4, 4, 4, 4, 4, 4, 4, 4,
142  4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4,
143  4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4,
144  4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4,
145  4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4,
146 -4,-4,-4,-4,-4,-4,-4,-4,-4,-4,-4,-4,-4,-4,-4,-4,
147 -4,-4,-4,-4,-4,-4,-4,-4,-4,-4,-4,-4,-4,-4,-4,-4,
148 -4,-4,-4,-4,-4,-4,-4,-4,-4,-4,-4,-4,-4,-4,-4,-4,
149 -4,-4,-4,-4,-4,-4,-4,-4,-4,-4,-4,-4,-4,-4,-4,-4,
150 -4,-4,-4,-4,-4,-4,-4,-4,-4,-3,-3,-3,-3,-3,-3,-3,
151 -3,-3,-3,-3,-3,-3,-3,-3,-3,-3,-3,-3,-3,-3,-3,-3,
152 -3,-3,-3,-3,-3,-3,-2,-2,-2,-2,-2,-2,-2,-2,-2,-2,
153 -2,-2,-2,-2,-1,-1,-1,-1,-1,-1,-1,-1,-0,-0,-0,-0,
154 };
155
156 static const int8_t quant11[256]={
157  0, 1, 2, 2, 2, 3, 3, 3, 3, 3, 3, 3, 4, 4, 4, 4,
158  4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4,
159  4, 4, 4, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5,
160  5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5,
161  5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5,
162  5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5,
163  5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5,
164  5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5,
165 -5,-5,-5,-5,-5,-5,-5,-5,-5,-5,-5,-5,-5,-5,-5,-5,
166 -5,-5,-5,-5,-5,-5,-5,-5,-5,-5,-5,-5,-5,-5,-5,-5,
167 -5,-5,-5,-5,-5,-5,-5,-5,-5,-5,-5,-5,-5,-5,-5,-5,
168 -5,-5,-5,-5,-5,-5,-5,-5,-5,-5,-5,-5,-5,-5,-5,-5,
169 -5,-5,-5,-5,-5,-5,-5,-5,-5,-5,-5,-5,-5,-5,-5,-5,
170 -5,-5,-5,-5,-5,-5,-5,-5,-5,-5,-5,-5,-5,-5,-4,-4,
171 -4,-4,-4,-4,-4,-4,-4,-4,-4,-4,-4,-4,-4,-4,-4,-4,
172 -4,-4,-4,-4,-4,-3,-3,-3,-3,-3,-3,-3,-2,-2,-2,-1,
173 };
174 static const int8_t quant13[256]={
175  0, 1, 2, 2, 3, 3, 3, 3, 4, 4, 4, 4, 4, 4, 4, 4,
176  4, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5,
177  5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5,
178  5, 5, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6,
179  6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6,
180  6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6,
181  6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6,
182  6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6,
183 -6,-6,-6,-6,-6,-6,-6,-6,-6,-6,-6,-6,-6,-6,-6,-6,
184 -6,-6,-6,-6,-6,-6,-6,-6,-6,-6,-6,-6,-6,-6,-6,-6,
185 -6,-6,-6,-6,-6,-6,-6,-6,-6,-6,-6,-6,-6,-6,-6,-6,
186 -6,-6,-6,-6,-6,-6,-6,-6,-6,-6,-6,-6,-6,-6,-6,-6,
187 -6,-6,-6,-6,-6,-6,-6,-6,-6,-6,-6,-6,-6,-6,-6,-5,
188 -5,-5,-5,-5,-5,-5,-5,-5,-5,-5,-5,-5,-5,-5,-5,-5,
189 -5,-5,-5,-5,-5,-5,-5,-5,-5,-5,-5,-5,-5,-5,-5,-5,
190 -4,-4,-4,-4,-4,-4,-4,-4,-4,-3,-3,-3,-3,-2,-2,-1,
191 };
192
193 static const uint8_t ver2_state[256]= {
194    0,  10,  10,  10,  10,  16,  16,  16,  28,  16,  16,  29,  42,  49,  20,  49,
195   59,  25,  26,  26,  27,  31,  33,  33,  33,  34,  34,  37,  67,  38,  39,  39,
196   40,  40,  41,  79,  43,  44,  45,  45,  48,  48,  64,  50,  51,  52,  88,  52,
197   53,  74,  55,  57,  58,  58,  74,  60, 101,  61,  62,  84,  66,  66,  68,  69,
198   87,  82,  71,  97,  73,  73,  82,  75, 111,  77,  94,  78,  87,  81,  83,  97,
199   85,  83,  94,  86,  99,  89,  90,  99, 111,  92,  93, 134,  95,  98, 105,  98,
200  105, 110, 102, 108, 102, 118, 103, 106, 106, 113, 109, 112, 114, 112, 116, 125,
201  115, 116, 117, 117, 126, 119, 125, 121, 121, 123, 145, 124, 126, 131, 127, 129,
202  165, 130, 132, 138, 133, 135, 145, 136, 137, 139, 146, 141, 143, 142, 144, 148,
203  147, 155, 151, 149, 151, 150, 152, 157, 153, 154, 156, 168, 158, 162, 161, 160,
204  172, 163, 169, 164, 166, 184, 167, 170, 177, 174, 171, 173, 182, 176, 180, 178,
205  175, 189, 179, 181, 186, 183, 192, 185, 200, 187, 191, 188, 190, 197, 193, 196,
206  197, 194, 195, 196, 198, 202, 199, 201, 210, 203, 207, 204, 205, 206, 208, 214,
207  209, 211, 221, 212, 213, 215, 224, 216, 217, 218, 219, 220, 222, 228, 223, 225,
208  226, 224, 227, 229, 240, 230, 231, 232, 233, 234, 235, 236, 238, 239, 237, 242,
209  241, 243, 242, 244, 245, 246, 247, 248, 249, 250, 251, 252, 252, 253, 254, 255,
210 };
211
212 typedef struct VlcState{
213     int16_t drift;
214     uint16_t error_sum;
215     int8_t bias;
216     uint8_t count;
217 } VlcState;
218
219 typedef struct PlaneContext{
220     int16_t quant_table[MAX_CONTEXT_INPUTS][256];
221     int quant_table_index;
222     int context_count;
223     uint8_t (*state)[CONTEXT_SIZE];
224     VlcState *vlc_state;
225     uint8_t interlace_bit_state[2];
226 } PlaneContext;
227
228 #define MAX_SLICES 256
229
230 typedef struct FFV1Context{
231     AVCodecContext *avctx;
232     RangeCoder c;
233     GetBitContext gb;
234     PutBitContext pb;
235     uint64_t rc_stat[256][2];
236     uint64_t (*rc_stat2[MAX_QUANT_TABLES])[32][2];
237     int version;
238     int width, height;
239     int chroma_h_shift, chroma_v_shift;
240     int flags;
241     int picture_number;
242     AVFrame picture;
243     int plane_count;
244     int ac;                              ///< 1=range coder <-> 0=golomb rice
245     PlaneContext plane[MAX_PLANES];
246     int16_t quant_table[MAX_CONTEXT_INPUTS][256];
247     int16_t quant_tables[MAX_QUANT_TABLES][MAX_CONTEXT_INPUTS][256];
248     int context_count[MAX_QUANT_TABLES];
249     uint8_t state_transition[256];
250     uint8_t (*initial_states[MAX_QUANT_TABLES])[32];
251     int run_index;
252     int colorspace;
253     int_fast16_t *sample_buffer;
254
255     int quant_table_count;
256
257     DSPContext dsp;
258
259     struct FFV1Context *slice_context[MAX_SLICES];
260     int slice_count;
261     int num_v_slices;
262     int num_h_slices;
263     int slice_width;
264     int slice_height;
265     int slice_x;
266     int slice_y;
267 }FFV1Context;
268
269 static av_always_inline int fold(int diff, int bits){
270     if(bits==8)
271         diff= (int8_t)diff;
272     else{
273         diff+= 1<<(bits-1);
274         diff&=(1<<bits)-1;
275         diff-= 1<<(bits-1);
276     }
277
278     return diff;
279 }
280
281 static inline int predict(int_fast16_t *src, int_fast16_t *last){
282     const int LT= last[-1];
283     const int  T= last[ 0];
284     const int L =  src[-1];
285
286     return mid_pred(L, L + T - LT, T);
287 }
288
289 static inline int get_context(PlaneContext *p, int_fast16_t *src, int_fast16_t *last, int_fast16_t *last2){
290     const int LT= last[-1];
291     const int  T= last[ 0];
292     const int RT= last[ 1];
293     const int L =  src[-1];
294
295     if(p->quant_table[3][127]){
296         const int TT= last2[0];
297         const int LL=  src[-2];
298         return p->quant_table[0][(L-LT) & 0xFF] + p->quant_table[1][(LT-T) & 0xFF] + p->quant_table[2][(T-RT) & 0xFF]
299               +p->quant_table[3][(LL-L) & 0xFF] + p->quant_table[4][(TT-T) & 0xFF];
300     }else
301         return p->quant_table[0][(L-LT) & 0xFF] + p->quant_table[1][(LT-T) & 0xFF] + p->quant_table[2][(T-RT) & 0xFF];
302 }
303
304 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]){
305     int i;
306
307 #define put_rac(C,S,B) \
308 do{\
309     if(rc_stat){\
310     rc_stat[*(S)][B]++;\
311         rc_stat2[(S)-state][B]++;\
312     }\
313     put_rac(C,S,B);\
314 }while(0)
315
316     if(v){
317         const int a= FFABS(v);
318         const int e= av_log2(a);
319         put_rac(c, state+0, 0);
320         if(e<=9){
321             for(i=0; i<e; i++){
322                 put_rac(c, state+1+i, 1);  //1..10
323             }
324             put_rac(c, state+1+i, 0);
325
326             for(i=e-1; i>=0; i--){
327                 put_rac(c, state+22+i, (a>>i)&1); //22..31
328             }
329
330             if(is_signed)
331                 put_rac(c, state+11 + e, v < 0); //11..21
332         }else{
333             for(i=0; i<e; i++){
334                 put_rac(c, state+1+FFMIN(i,9), 1);  //1..10
335             }
336             put_rac(c, state+1+9, 0);
337
338             for(i=e-1; i>=0; i--){
339                 put_rac(c, state+22+FFMIN(i,9), (a>>i)&1); //22..31
340             }
341
342             if(is_signed)
343                 put_rac(c, state+11 + 10, v < 0); //11..21
344         }
345     }else{
346         put_rac(c, state+0, 1);
347     }
348 #undef put_rac
349 }
350
351 static void av_noinline put_symbol(RangeCoder *c, uint8_t *state, int v, int is_signed){
352     put_symbol_inline(c, state, v, is_signed, NULL, NULL);
353 }
354
355 static inline av_flatten int get_symbol_inline(RangeCoder *c, uint8_t *state, int is_signed){
356     if(get_rac(c, state+0))
357         return 0;
358     else{
359         int i, e, a;
360         e= 0;
361         while(get_rac(c, state+1 + FFMIN(e,9))){ //1..10
362             e++;
363         }
364
365         a= 1;
366         for(i=e-1; i>=0; i--){
367             a += a + get_rac(c, state+22 + FFMIN(i,9)); //22..31
368         }
369
370         e= -(is_signed && get_rac(c, state+11 + FFMIN(e, 10))); //11..21
371         return (a^e)-e;
372     }
373 }
374
375 static int av_noinline get_symbol(RangeCoder *c, uint8_t *state, int is_signed){
376     return get_symbol_inline(c, state, is_signed);
377 }
378
379 static inline void update_vlc_state(VlcState * const state, const int v){
380     int drift= state->drift;
381     int count= state->count;
382     state->error_sum += FFABS(v);
383     drift += v;
384
385     if(count == 128){ //FIXME variable
386         count >>= 1;
387         drift >>= 1;
388         state->error_sum >>= 1;
389     }
390     count++;
391
392     if(drift <= -count){
393         if(state->bias > -128) state->bias--;
394
395         drift += count;
396         if(drift <= -count)
397             drift= -count + 1;
398     }else if(drift > 0){
399         if(state->bias <  127) state->bias++;
400
401         drift -= count;
402         if(drift > 0)
403             drift= 0;
404     }
405
406     state->drift= drift;
407     state->count= count;
408 }
409
410 static inline void put_vlc_symbol(PutBitContext *pb, VlcState * const state, int v, int bits){
411     int i, k, code;
412 //printf("final: %d ", v);
413     v = fold(v - state->bias, bits);
414
415     i= state->count;
416     k=0;
417     while(i < state->error_sum){ //FIXME optimize
418         k++;
419         i += i;
420     }
421
422     assert(k<=8);
423
424 #if 0 // JPEG LS
425     if(k==0 && 2*state->drift <= - state->count) code= v ^ (-1);
426     else                                         code= v;
427 #else
428      code= v ^ ((2*state->drift + state->count)>>31);
429 #endif
430
431 //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);
432     set_sr_golomb(pb, code, k, 12, bits);
433
434     update_vlc_state(state, v);
435 }
436
437 static inline int get_vlc_symbol(GetBitContext *gb, VlcState * const state, int bits){
438     int k, i, v, ret;
439
440     i= state->count;
441     k=0;
442     while(i < state->error_sum){ //FIXME optimize
443         k++;
444         i += i;
445     }
446
447     assert(k<=8);
448
449     v= get_sr_golomb(gb, k, 12, bits);
450 //printf("v:%d bias:%d error:%d drift:%d count:%d k:%d", v, state->bias, state->error_sum, state->drift, state->count, k);
451
452 #if 0 // JPEG LS
453     if(k==0 && 2*state->drift <= - state->count) v ^= (-1);
454 #else
455      v ^= ((2*state->drift + state->count)>>31);
456 #endif
457
458     ret= fold(v + state->bias, bits);
459
460     update_vlc_state(state, v);
461 //printf("final: %d\n", ret);
462     return ret;
463 }
464
465 #if CONFIG_FFV1_ENCODER
466 static av_always_inline int encode_line(FFV1Context *s, int w, int_fast16_t *sample[2], int plane_index, int bits){
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 //            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));
528
529             if(run_mode == 0)
530                 put_vlc_symbol(&s->pb, &p->vlc_state[context], diff, bits);
531         }
532     }
533     if(run_mode){
534         while(run_count >= 1<<ff_log2_run[run_index]){
535             run_count -= 1<<ff_log2_run[run_index];
536             run_index++;
537             put_bits(&s->pb, 1, 1);
538         }
539
540         if(run_count)
541             put_bits(&s->pb, 1, 1);
542     }
543     s->run_index= run_index;
544
545     return 0;
546 }
547
548 static void encode_plane(FFV1Context *s, uint8_t *src, int w, int h, int stride, int plane_index){
549     int x,y,i;
550     const int ring_size= s->avctx->context_model ? 3 : 2;
551     int_fast16_t *sample[3];
552     s->run_index=0;
553
554     memset(s->sample_buffer, 0, ring_size*(w+6)*sizeof(*s->sample_buffer));
555
556     for(y=0; y<h; y++){
557         for(i=0; i<ring_size; i++)
558             sample[i]= s->sample_buffer + (w+6)*((h+i-y)%ring_size) + 3;
559
560         sample[0][-1]= sample[1][0  ];
561         sample[1][ w]= sample[1][w-1];
562 //{START_TIMER
563         if(s->avctx->bits_per_raw_sample<=8){
564             for(x=0; x<w; x++){
565                 sample[0][x]= src[x + stride*y];
566             }
567             encode_line(s, w, sample, plane_index, 8);
568         }else{
569             for(x=0; x<w; x++){
570                 sample[0][x]= ((uint16_t*)(src + stride*y))[x] >> (16 - s->avctx->bits_per_raw_sample);
571             }
572             encode_line(s, w, sample, plane_index, s->avctx->bits_per_raw_sample);
573         }
574 //STOP_TIMER("encode line")}
575     }
576 }
577
578 static void encode_rgb_frame(FFV1Context *s, uint32_t *src, int w, int h, int stride){
579     int x, y, p, i;
580     const int ring_size= s->avctx->context_model ? 3 : 2;
581     int_fast16_t *sample[3][3];
582     s->run_index=0;
583
584     memset(s->sample_buffer, 0, ring_size*3*(w+6)*sizeof(*s->sample_buffer));
585
586     for(y=0; y<h; y++){
587         for(i=0; i<ring_size; i++)
588             for(p=0; p<3; p++)
589                 sample[p][i]= s->sample_buffer + p*ring_size*(w+6) + ((h+i-y)%ring_size)*(w+6) + 3;
590
591         for(x=0; x<w; x++){
592             int v= src[x + stride*y];
593             int b= v&0xFF;
594             int g= (v>>8)&0xFF;
595             int r= (v>>16)&0xFF;
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         }
609         for(p=0; p<3; p++){
610             sample[p][0][-1]= sample[p][1][0  ];
611             sample[p][1][ w]= sample[p][1][w-1];
612             encode_line(s, w, sample[p], FFMIN(p, 1), 9);
613         }
614     }
615 }
616
617 static void write_quant_table(RangeCoder *c, int16_t *quant_table){
618     int last=0;
619     int i;
620     uint8_t state[CONTEXT_SIZE];
621     memset(state, 128, sizeof(state));
622
623     for(i=1; i<128 ; i++){
624         if(quant_table[i] != quant_table[i-1]){
625             put_symbol(c, state, i-last-1, 0);
626             last= i;
627         }
628     }
629     put_symbol(c, state, i-last-1, 0);
630 }
631
632 static void write_quant_tables(RangeCoder *c, int16_t quant_table[MAX_CONTEXT_INPUTS][256]){
633     int i;
634     for(i=0; i<5; i++)
635         write_quant_table(c, quant_table[i]);
636 }
637
638 static void write_header(FFV1Context *f){
639     uint8_t state[CONTEXT_SIZE];
640     int i, j;
641     RangeCoder * const c= &f->slice_context[0]->c;
642
643     memset(state, 128, sizeof(state));
644
645     if(f->version < 2){
646         put_symbol(c, state, f->version, 0);
647         put_symbol(c, state, f->ac, 0);
648         if(f->ac>1){
649             for(i=1; i<256; i++){
650                 put_symbol(c, state, f->state_transition[i] - c->one_state[i], 1);
651             }
652         }
653         put_symbol(c, state, f->colorspace, 0); //YUV cs type
654         if(f->version>0)
655             put_symbol(c, state, f->avctx->bits_per_raw_sample, 0);
656         put_rac(c, state, 1); //chroma planes
657             put_symbol(c, state, f->chroma_h_shift, 0);
658             put_symbol(c, state, f->chroma_v_shift, 0);
659         put_rac(c, state, 0); //no transparency plane
660
661         write_quant_tables(c, f->quant_table);
662     }else{
663         put_symbol(c, state, f->slice_count, 0);
664         for(i=0; i<f->slice_count; i++){
665             FFV1Context *fs= f->slice_context[i];
666             put_symbol(c, state, (fs->slice_x     +1)*f->num_h_slices / f->width   , 0);
667             put_symbol(c, state, (fs->slice_y     +1)*f->num_v_slices / f->height  , 0);
668             put_symbol(c, state, (fs->slice_width +1)*f->num_h_slices / f->width -1, 0);
669             put_symbol(c, state, (fs->slice_height+1)*f->num_v_slices / f->height-1, 0);
670             for(j=0; j<f->plane_count; j++){
671                 put_symbol(c, state, f->plane[j].quant_table_index, 0);
672                 av_assert0(f->plane[j].quant_table_index == f->avctx->context_model);
673             }
674         }
675     }
676 }
677 #endif /* CONFIG_FFV1_ENCODER */
678
679 static av_cold int common_init(AVCodecContext *avctx){
680     FFV1Context *s = avctx->priv_data;
681
682     s->avctx= avctx;
683     s->flags= avctx->flags;
684
685     dsputil_init(&s->dsp, avctx);
686
687     s->width = avctx->width;
688     s->height= avctx->height;
689
690     assert(s->width && s->height);
691     //defaults
692     s->num_h_slices=1;
693     s->num_v_slices=1;
694
695
696     return 0;
697 }
698
699 static int init_slice_state(FFV1Context *f){
700     int i, j;
701
702     for(i=0; i<f->slice_count; i++){
703         FFV1Context *fs= f->slice_context[i];
704         for(j=0; j<f->plane_count; j++){
705             PlaneContext * const p= &fs->plane[j];
706
707             if(fs->ac){
708                 if(!p->    state) p->    state= av_malloc(CONTEXT_SIZE*p->context_count*sizeof(uint8_t));
709                 if(!p->    state)
710                     return AVERROR(ENOMEM);
711             }else{
712                 if(!p->vlc_state) p->vlc_state= av_malloc(p->context_count*sizeof(VlcState));
713                 if(!p->vlc_state)
714                     return AVERROR(ENOMEM);
715             }
716         }
717
718         if (fs->ac>1){
719             //FIXME only redo if state_transition changed
720             for(j=1; j<256; j++){
721                 fs->c.one_state [    j]= fs->state_transition[j];
722                 fs->c.zero_state[256-j]= 256-fs->c.one_state [j];
723             }
724         }
725     }
726
727     return 0;
728 }
729
730 static av_cold int init_slice_contexts(FFV1Context *f){
731     int i;
732
733     f->slice_count= f->num_h_slices * f->num_v_slices;
734
735     for(i=0; i<f->slice_count; i++){
736         FFV1Context *fs= av_mallocz(sizeof(*fs));
737         int sx= i % f->num_h_slices;
738         int sy= i / f->num_h_slices;
739         int sxs= f->avctx->width * sx    / f->num_h_slices;
740         int sxe= f->avctx->width *(sx+1) / f->num_h_slices;
741         int sys= f->avctx->height* sy    / f->num_v_slices;
742         int sye= f->avctx->height*(sy+1) / f->num_v_slices;
743         f->slice_context[i]= fs;
744         memcpy(fs, f, sizeof(*fs));
745         memset(fs->rc_stat2, 0, sizeof(fs->rc_stat2));
746
747         fs->slice_width = sxe - sxs;
748         fs->slice_height= sye - sys;
749         fs->slice_x     = sxs;
750         fs->slice_y     = sys;
751
752         fs->sample_buffer = av_malloc(6 * (fs->width+6) * sizeof(*fs->sample_buffer));
753         if (!fs->sample_buffer)
754             return AVERROR(ENOMEM);
755     }
756     return 0;
757 }
758
759 static int allocate_initial_states(FFV1Context *f){
760     int i;
761
762     for(i=0; i<f->quant_table_count; i++){
763         f->initial_states[i]= av_malloc(f->context_count[i]*sizeof(*f->initial_states[i]));
764         if(!f->initial_states[i])
765             return AVERROR(ENOMEM);
766         memset(f->initial_states[i], 128, f->context_count[i]*sizeof(*f->initial_states[i]));
767     }
768     return 0;
769 }
770
771 #if CONFIG_FFV1_ENCODER
772 static int write_extra_header(FFV1Context *f){
773     RangeCoder * const c= &f->c;
774     uint8_t state[CONTEXT_SIZE];
775     int i, j, k;
776     uint8_t state2[32][CONTEXT_SIZE];
777
778     memset(state2, 128, sizeof(state2));
779     memset(state, 128, sizeof(state));
780
781     f->avctx->extradata= av_malloc(f->avctx->extradata_size= 10000 + (11*11*5*5*5+11*11*11)*32);
782     ff_init_range_encoder(c, f->avctx->extradata, f->avctx->extradata_size);
783     ff_build_rac_states(c, 0.05*(1LL<<32), 256-8);
784
785     put_symbol(c, state, f->version, 0);
786     put_symbol(c, state, f->ac, 0);
787     if(f->ac>1){
788         for(i=1; i<256; i++){
789             put_symbol(c, state, f->state_transition[i] - c->one_state[i], 1);
790         }
791     }
792     put_symbol(c, state, f->colorspace, 0); //YUV cs type
793     put_symbol(c, state, f->avctx->bits_per_raw_sample, 0);
794     put_rac(c, state, 1); //chroma planes
795         put_symbol(c, state, f->chroma_h_shift, 0);
796         put_symbol(c, state, f->chroma_v_shift, 0);
797     put_rac(c, state, 0); //no transparency plane
798     put_symbol(c, state, f->num_h_slices-1, 0);
799     put_symbol(c, state, f->num_v_slices-1, 0);
800
801     put_symbol(c, state, f->quant_table_count, 0);
802     for(i=0; i<f->quant_table_count; i++)
803         write_quant_tables(c, f->quant_tables[i]);
804
805     for(i=0; i<f->quant_table_count; i++){
806         for(j=0; j<f->context_count[i]*CONTEXT_SIZE; j++)
807             if(f->initial_states[i] && f->initial_states[i][0][j] != 128)
808                 break;
809         if(j<f->context_count[i]*CONTEXT_SIZE){
810             put_rac(c, state, 1);
811             for(j=0; j<f->context_count[i]; j++){
812                 for(k=0; k<CONTEXT_SIZE; k++){
813                     int pred= j ? f->initial_states[i][j-1][k] : 128;
814                     put_symbol(c, state2[k], (int8_t)(f->initial_states[i][j][k]-pred), 1);
815                 }
816             }
817         }else{
818             put_rac(c, state, 0);
819         }
820     }
821
822     f->avctx->extradata_size= ff_rac_terminate(c);
823
824     return 0;
825 }
826
827 static int sort_stt(FFV1Context *s, uint8_t stt[256]){
828     int i,i2,changed,print=0;
829
830     do{
831         changed=0;
832         for(i=12; i<244; i++){
833             for(i2=i+1; i2<245 && i2<i+4; i2++){
834 #define COST(old, new) \
835     s->rc_stat[old][0]*-log2((256-(new))/256.0)\
836    +s->rc_stat[old][1]*-log2(     (new) /256.0)
837
838 #define COST2(old, new) \
839     COST(old, new)\
840    +COST(256-(old), 256-(new))
841
842                 double size0= COST2(i, i ) + COST2(i2, i2);
843                 double sizeX= COST2(i, i2) + COST2(i2, i );
844                 if(sizeX < size0 && i!=128 && i2!=128){
845                     int j;
846                     FFSWAP(int, stt[    i], stt[    i2]);
847                     FFSWAP(int, s->rc_stat[i    ][0],s->rc_stat[    i2][0]);
848                     FFSWAP(int, s->rc_stat[i    ][1],s->rc_stat[    i2][1]);
849                     if(i != 256-i2){
850                         FFSWAP(int, stt[256-i], stt[256-i2]);
851                         FFSWAP(int, s->rc_stat[256-i][0],s->rc_stat[256-i2][0]);
852                         FFSWAP(int, s->rc_stat[256-i][1],s->rc_stat[256-i2][1]);
853                     }
854                     for(j=1; j<256; j++){
855                         if     (stt[j] == i ) stt[j] = i2;
856                         else if(stt[j] == i2) stt[j] = i ;
857                         if(i != 256-i2){
858                             if     (stt[256-j] == 256-i ) stt[256-j] = 256-i2;
859                             else if(stt[256-j] == 256-i2) stt[256-j] = 256-i ;
860                         }
861                     }
862                     print=changed=1;
863                 }
864             }
865         }
866     }while(changed);
867     return print;
868 }
869
870 static av_cold int encode_init(AVCodecContext *avctx)
871 {
872     FFV1Context *s = avctx->priv_data;
873     int i, j, k, m;
874
875     common_init(avctx);
876
877     s->version=0;
878     s->ac= avctx->coder_type ? 2:0;
879
880     if(s->ac>1)
881         for(i=1; i<256; i++)
882             s->state_transition[i]=ver2_state[i];
883
884     s->plane_count=2;
885     for(i=0; i<256; i++){
886         s->quant_table_count=2;
887         if(avctx->bits_per_raw_sample <=8){
888             s->quant_tables[0][0][i]=           quant11[i];
889             s->quant_tables[0][1][i]=        11*quant11[i];
890             s->quant_tables[0][2][i]=     11*11*quant11[i];
891             s->quant_tables[1][0][i]=           quant11[i];
892             s->quant_tables[1][1][i]=        11*quant11[i];
893             s->quant_tables[1][2][i]=     11*11*quant5 [i];
894             s->quant_tables[1][3][i]=   5*11*11*quant5 [i];
895             s->quant_tables[1][4][i]= 5*5*11*11*quant5 [i];
896         }else{
897             s->quant_tables[0][0][i]=           quant9_10bit[i];
898             s->quant_tables[0][1][i]=        11*quant9_10bit[i];
899             s->quant_tables[0][2][i]=     11*11*quant9_10bit[i];
900             s->quant_tables[1][0][i]=           quant9_10bit[i];
901             s->quant_tables[1][1][i]=        11*quant9_10bit[i];
902             s->quant_tables[1][2][i]=     11*11*quant5_10bit[i];
903             s->quant_tables[1][3][i]=   5*11*11*quant5_10bit[i];
904             s->quant_tables[1][4][i]= 5*5*11*11*quant5_10bit[i];
905         }
906     }
907     s->context_count[0]= (11*11*11+1)/2;
908     s->context_count[1]= (11*11*5*5*5+1)/2;
909     memcpy(s->quant_table, s->quant_tables[avctx->context_model], sizeof(s->quant_table));
910
911     for(i=0; i<s->plane_count; i++){
912         PlaneContext * const p= &s->plane[i];
913
914         memcpy(p->quant_table, s->quant_table, sizeof(p->quant_table));
915         p->quant_table_index= avctx->context_model;
916         p->context_count= s->context_count[p->quant_table_index];
917     }
918
919     if(allocate_initial_states(s) < 0)
920         return AVERROR(ENOMEM);
921
922     avctx->coded_frame= &s->picture;
923     switch(avctx->pix_fmt){
924     case PIX_FMT_YUV444P16:
925     case PIX_FMT_YUV422P16:
926     case PIX_FMT_YUV420P16:
927         if(avctx->bits_per_raw_sample <=8){
928             av_log(avctx, AV_LOG_ERROR, "bits_per_raw_sample invalid\n");
929             return -1;
930         }
931         if(!s->ac){
932             av_log(avctx, AV_LOG_ERROR, "bits_per_raw_sample of more than 8 needs -coder 1 currently\n");
933             return -1;
934         }
935         s->version= FFMAX(s->version, 1);
936     case PIX_FMT_YUV444P:
937     case PIX_FMT_YUV422P:
938     case PIX_FMT_YUV420P:
939     case PIX_FMT_YUV411P:
940     case PIX_FMT_YUV410P:
941         s->colorspace= 0;
942         break;
943     case PIX_FMT_RGB32:
944         s->colorspace= 1;
945         break;
946     default:
947         av_log(avctx, AV_LOG_ERROR, "format not supported\n");
948         return -1;
949     }
950     avcodec_get_chroma_sub_sample(avctx->pix_fmt, &s->chroma_h_shift, &s->chroma_v_shift);
951
952     s->picture_number=0;
953
954     if(avctx->flags & (CODEC_FLAG_PASS1|CODEC_FLAG_PASS2)){
955         for(i=0; i<s->quant_table_count; i++){
956             s->rc_stat2[i]= av_mallocz(s->context_count[i]*sizeof(*s->rc_stat2[i]));
957             if(!s->rc_stat2[i])
958                 return AVERROR(ENOMEM);
959         }
960     }
961     if(avctx->stats_in){
962         char *p= avctx->stats_in;
963
964         av_assert0(s->version>=2);
965
966         for(;;){
967             for(j=0; j<256; j++){
968                 for(i=0; i<2; i++){
969                     char *next;
970                     s->rc_stat[j][i]= strtol(p, &next, 0);
971                     if(next==p){
972                         av_log(avctx, AV_LOG_ERROR, "2Pass file invalid at %d %d [%s]\n", j,i,p);
973                         return -1;
974                     }
975                     p=next;
976                 }
977             }
978             for(i=0; i<s->quant_table_count; i++){
979                 for(j=0; j<s->context_count[i]; j++){
980                     for(k=0; k<32; k++){
981                         for(m=0; m<2; m++){
982                             char *next;
983                             s->rc_stat2[i][j][k][m]= strtol(p, &next, 0);
984                             if(next==p){
985                                 av_log(avctx, AV_LOG_ERROR, "2Pass file invalid at %d %d %d %d [%s]\n", i,j,k,m,p);
986                                 return -1;
987                             }
988                             p=next;
989                         }
990                     }
991                 }
992             }
993             while(*p=='\n' || *p==' ') p++;
994             if(p[0]==0) break;
995         }
996         sort_stt(s, s->state_transition);
997
998         for(i=0; i<s->quant_table_count; i++){
999             for(j=0; j<s->context_count[i]; j++){
1000                 for(k=0; k<32; k++){
1001                     int p= 128;
1002                     if(s->rc_stat2[i][j][k][0]+s->rc_stat2[i][j][k][1]){
1003                         p=256*s->rc_stat2[i][j][k][1] / (s->rc_stat2[i][j][k][0]+s->rc_stat2[i][j][k][1]);
1004                     }
1005                     p= av_clip(p, 1, 254);
1006                     s->initial_states[i][j][k]= p;
1007                 }
1008             }
1009         }
1010     }
1011
1012     if(s->version>1){
1013         s->num_h_slices=2;
1014         s->num_v_slices=2;
1015         write_extra_header(s);
1016     }
1017
1018     if(init_slice_contexts(s) < 0)
1019         return -1;
1020     if(init_slice_state(s) < 0)
1021         return -1;
1022
1023 #define STATS_OUT_SIZE 1024*1024*6
1024     if(avctx->flags & CODEC_FLAG_PASS1){
1025     avctx->stats_out= av_mallocz(STATS_OUT_SIZE);
1026         for(i=0; i<s->quant_table_count; i++){
1027             for(j=0; j<s->slice_count; j++){
1028                 FFV1Context *sf= s->slice_context[j];
1029                 av_assert0(!sf->rc_stat2[i]);
1030                 sf->rc_stat2[i]= av_mallocz(s->context_count[i]*sizeof(*sf->rc_stat2[i]));
1031                 if(!sf->rc_stat2[i])
1032                     return AVERROR(ENOMEM);
1033             }
1034         }
1035     }
1036
1037     return 0;
1038 }
1039 #endif /* CONFIG_FFV1_ENCODER */
1040
1041
1042 static void clear_state(FFV1Context *f){
1043     int i, si, j;
1044
1045     for(si=0; si<f->slice_count; si++){
1046         FFV1Context *fs= f->slice_context[si];
1047         for(i=0; i<f->plane_count; i++){
1048             PlaneContext *p= &fs->plane[i];
1049
1050             p->interlace_bit_state[0]= 128;
1051             p->interlace_bit_state[1]= 128;
1052
1053             if(fs->ac){
1054                 if(f->initial_states[p->quant_table_index]){
1055                     memcpy(p->state, f->initial_states[p->quant_table_index], CONTEXT_SIZE*p->context_count);
1056                 }else
1057                 memset(p->state, 128, CONTEXT_SIZE*p->context_count);
1058             }else{
1059             for(j=0; j<p->context_count; j++){
1060                     p->vlc_state[j].drift= 0;
1061                     p->vlc_state[j].error_sum= 4; //FFMAX((RANGE + 32)/64, 2);
1062                     p->vlc_state[j].bias= 0;
1063                     p->vlc_state[j].count= 1;
1064             }
1065             }
1066         }
1067     }
1068 }
1069
1070 #if CONFIG_FFV1_ENCODER
1071 static int encode_slice(AVCodecContext *c, void *arg){
1072     FFV1Context *fs= *(void**)arg;
1073     FFV1Context *f= fs->avctx->priv_data;
1074     int width = fs->slice_width;
1075     int height= fs->slice_height;
1076     int x= fs->slice_x;
1077     int y= fs->slice_y;
1078     AVFrame * const p= &f->picture;
1079
1080     if(f->colorspace==0){
1081         const int chroma_width = -((-width )>>f->chroma_h_shift);
1082         const int chroma_height= -((-height)>>f->chroma_v_shift);
1083         const int cx= x>>f->chroma_h_shift;
1084         const int cy= y>>f->chroma_v_shift;
1085
1086         encode_plane(fs, p->data[0] + x + y*p->linesize[0], width, height, p->linesize[0], 0);
1087
1088         encode_plane(fs, p->data[1] + cx+cy*p->linesize[1], chroma_width, chroma_height, p->linesize[1], 1);
1089         encode_plane(fs, p->data[2] + cx+cy*p->linesize[2], chroma_width, chroma_height, p->linesize[2], 1);
1090     }else{
1091         encode_rgb_frame(fs, (uint32_t*)(p->data[0]) + x + y*(p->linesize[0]/4), width, height, p->linesize[0]/4);
1092     }
1093     emms_c();
1094
1095     return 0;
1096 }
1097
1098 static int encode_frame(AVCodecContext *avctx, unsigned char *buf, int buf_size, void *data){
1099     FFV1Context *f = avctx->priv_data;
1100     RangeCoder * const c= &f->slice_context[0]->c;
1101     AVFrame *pict = data;
1102     AVFrame * const p= &f->picture;
1103     int used_count= 0;
1104     uint8_t keystate=128;
1105     uint8_t *buf_p;
1106     int i;
1107
1108     ff_init_range_encoder(c, buf, buf_size);
1109     ff_build_rac_states(c, 0.05*(1LL<<32), 256-8);
1110
1111     *p = *pict;
1112     p->pict_type= FF_I_TYPE;
1113
1114     if(avctx->gop_size==0 || f->picture_number % avctx->gop_size == 0){
1115         put_rac(c, &keystate, 1);
1116         p->key_frame= 1;
1117         write_header(f);
1118         clear_state(f);
1119     }else{
1120         put_rac(c, &keystate, 0);
1121         p->key_frame= 0;
1122     }
1123
1124     if(!f->ac){
1125         used_count += ff_rac_terminate(c);
1126 //printf("pos=%d\n", used_count);
1127         init_put_bits(&f->slice_context[0]->pb, buf + used_count, buf_size - used_count);
1128     }else if (f->ac>1){
1129         int i;
1130         for(i=1; i<256; i++){
1131             c->one_state[i]= f->state_transition[i];
1132             c->zero_state[256-i]= 256-c->one_state[i];
1133         }
1134     }
1135
1136     for(i=1; i<f->slice_count; i++){
1137         FFV1Context *fs= f->slice_context[i];
1138         uint8_t *start= buf + (buf_size-used_count)*i/f->slice_count;
1139         int len= buf_size/f->slice_count;
1140
1141         if(fs->ac){
1142             ff_init_range_encoder(&fs->c, start, len);
1143         }else{
1144             init_put_bits(&fs->pb, start, len);
1145         }
1146     }
1147     avctx->execute(avctx, encode_slice, &f->slice_context[0], NULL, f->slice_count, sizeof(void*));
1148
1149     buf_p=buf;
1150     for(i=0; i<f->slice_count; i++){
1151         FFV1Context *fs= f->slice_context[i];
1152         int bytes;
1153
1154         if(fs->ac){
1155             uint8_t state=128;
1156             put_rac(&fs->c, &state, 0);
1157             bytes= ff_rac_terminate(&fs->c);
1158         }else{
1159             flush_put_bits(&fs->pb); //nicer padding FIXME
1160             bytes= used_count + (put_bits_count(&fs->pb)+7)/8;
1161             used_count= 0;
1162         }
1163         if(i>0){
1164             av_assert0(bytes < buf_size/f->slice_count);
1165             memmove(buf_p, fs->ac ? fs->c.bytestream_start : fs->pb.buf, bytes);
1166             av_assert0(bytes < (1<<24));
1167             AV_WB24(buf_p+bytes, bytes);
1168             bytes+=3;
1169         }
1170         buf_p += bytes;
1171     }
1172
1173     if((avctx->flags&CODEC_FLAG_PASS1) && (f->picture_number&31)==0){
1174         int j, k, m;
1175         char *p= avctx->stats_out;
1176         char *end= p + STATS_OUT_SIZE;
1177
1178         memset(f->rc_stat, 0, sizeof(f->rc_stat));
1179         for(i=0; i<f->quant_table_count; i++)
1180             memset(f->rc_stat2[i], 0, f->context_count[i]*sizeof(*f->rc_stat2[i]));
1181
1182         for(j=0; j<f->slice_count; j++){
1183             FFV1Context *fs= f->slice_context[j];
1184             for(i=0; i<256; i++){
1185                 f->rc_stat[i][0] += fs->rc_stat[i][0];
1186                 f->rc_stat[i][1] += fs->rc_stat[i][1];
1187             }
1188             for(i=0; i<f->quant_table_count; i++){
1189                 for(k=0; k<f->context_count[i]; k++){
1190                     for(m=0; m<32; m++){
1191                         f->rc_stat2[i][k][m][0] += fs->rc_stat2[i][k][m][0];
1192                         f->rc_stat2[i][k][m][1] += fs->rc_stat2[i][k][m][1];
1193                     }
1194                 }
1195             }
1196         }
1197
1198         for(j=0; j<256; j++){
1199             snprintf(p, end-p, "%"PRIu64" %"PRIu64" ", f->rc_stat[j][0], f->rc_stat[j][1]);
1200             p+= strlen(p);
1201         }
1202         snprintf(p, end-p, "\n");
1203
1204         for(i=0; i<f->quant_table_count; i++){
1205             for(j=0; j<f->context_count[i]; j++){
1206                 for(m=0; m<32; m++){
1207                     snprintf(p, end-p, "%"PRIu64" %"PRIu64" ", f->rc_stat2[i][j][m][0], f->rc_stat2[i][j][m][1]);
1208                     p+= strlen(p);
1209                 }
1210             }
1211         }
1212         snprintf(p, end-p, "\n");
1213     } else if(avctx->flags&CODEC_FLAG_PASS1)
1214         avctx->stats_out[0] = '\0';
1215
1216     f->picture_number++;
1217     return buf_p-buf;
1218 }
1219 #endif /* CONFIG_FFV1_ENCODER */
1220
1221 static av_cold int common_end(AVCodecContext *avctx){
1222     FFV1Context *s = avctx->priv_data;
1223     int i, j;
1224
1225     for(j=0; j<s->slice_count; j++){
1226         FFV1Context *fs= s->slice_context[j];
1227         for(i=0; i<s->plane_count; i++){
1228             PlaneContext *p= &fs->plane[i];
1229
1230             av_freep(&p->state);
1231             av_freep(&p->vlc_state);
1232         }
1233         av_freep(&fs->sample_buffer);
1234     }
1235
1236     av_freep(&avctx->stats_out);
1237     for(j=0; j<s->quant_table_count; j++){
1238         av_freep(&s->initial_states[j]);
1239         for(i=0; i<s->slice_count; i++){
1240             FFV1Context *sf= s->slice_context[i];
1241             av_freep(&sf->rc_stat2[j]);
1242         }
1243         av_freep(&s->rc_stat2[j]);
1244     }
1245
1246     return 0;
1247 }
1248
1249 static av_always_inline void decode_line(FFV1Context *s, int w, int_fast16_t *sample[2], int plane_index, int bits){
1250     PlaneContext * const p= &s->plane[plane_index];
1251     RangeCoder * const c= &s->c;
1252     int x;
1253     int run_count=0;
1254     int run_mode=0;
1255     int run_index= s->run_index;
1256
1257     for(x=0; x<w; x++){
1258         int diff, context, sign;
1259
1260         context= get_context(p, sample[1] + x, sample[0] + x, sample[1] + x);
1261         if(context < 0){
1262             context= -context;
1263             sign=1;
1264         }else
1265             sign=0;
1266
1267         av_assert2(context < p->context_count);
1268
1269         if(s->ac){
1270             diff= get_symbol_inline(c, p->state[context], 1);
1271         }else{
1272             if(context == 0 && run_mode==0) run_mode=1;
1273
1274             if(run_mode){
1275                 if(run_count==0 && run_mode==1){
1276                     if(get_bits1(&s->gb)){
1277                         run_count = 1<<ff_log2_run[run_index];
1278                         if(x + run_count <= w) run_index++;
1279                     }else{
1280                         if(ff_log2_run[run_index]) run_count = get_bits(&s->gb, ff_log2_run[run_index]);
1281                         else run_count=0;
1282                         if(run_index) run_index--;
1283                         run_mode=2;
1284                     }
1285                 }
1286                 run_count--;
1287                 if(run_count < 0){
1288                     run_mode=0;
1289                     run_count=0;
1290                     diff= get_vlc_symbol(&s->gb, &p->vlc_state[context], bits);
1291                     if(diff>=0) diff++;
1292                 }else
1293                     diff=0;
1294             }else
1295                 diff= get_vlc_symbol(&s->gb, &p->vlc_state[context], bits);
1296
1297 //            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));
1298         }
1299
1300         if(sign) diff= -diff;
1301
1302         sample[1][x]= (predict(sample[1] + x, sample[0] + x) + diff) & ((1<<bits)-1);
1303     }
1304     s->run_index= run_index;
1305 }
1306
1307 static void decode_plane(FFV1Context *s, uint8_t *src, int w, int h, int stride, int plane_index){
1308     int x, y;
1309     int_fast16_t *sample[2];
1310     sample[0]=s->sample_buffer    +3;
1311     sample[1]=s->sample_buffer+w+6+3;
1312
1313     s->run_index=0;
1314
1315     memset(s->sample_buffer, 0, 2*(w+6)*sizeof(*s->sample_buffer));
1316
1317     for(y=0; y<h; y++){
1318         int_fast16_t *temp= sample[0]; //FIXME try a normal buffer
1319
1320         sample[0]= sample[1];
1321         sample[1]= temp;
1322
1323         sample[1][-1]= sample[0][0  ];
1324         sample[0][ w]= sample[0][w-1];
1325
1326 //{START_TIMER
1327         if(s->avctx->bits_per_raw_sample <= 8){
1328             decode_line(s, w, sample, plane_index, 8);
1329             for(x=0; x<w; x++){
1330                 src[x + stride*y]= sample[1][x];
1331             }
1332         }else{
1333             decode_line(s, w, sample, plane_index, s->avctx->bits_per_raw_sample);
1334             for(x=0; x<w; x++){
1335                 ((uint16_t*)(src + stride*y))[x]= sample[1][x] << (16 - s->avctx->bits_per_raw_sample);
1336             }
1337         }
1338 //STOP_TIMER("decode-line")}
1339     }
1340 }
1341
1342 static void decode_rgb_frame(FFV1Context *s, uint32_t *src, int w, int h, int stride){
1343     int x, y, p;
1344     int_fast16_t *sample[3][2];
1345     for(x=0; x<3; x++){
1346         sample[x][0] = s->sample_buffer +  x*2   *(w+6) + 3;
1347         sample[x][1] = s->sample_buffer + (x*2+1)*(w+6) + 3;
1348     }
1349
1350     s->run_index=0;
1351
1352     memset(s->sample_buffer, 0, 6*(w+6)*sizeof(*s->sample_buffer));
1353
1354     for(y=0; y<h; y++){
1355         for(p=0; p<3; p++){
1356             int_fast16_t *temp= sample[p][0]; //FIXME try a normal buffer
1357
1358             sample[p][0]= sample[p][1];
1359             sample[p][1]= temp;
1360
1361             sample[p][1][-1]= sample[p][0][0  ];
1362             sample[p][0][ w]= sample[p][0][w-1];
1363             decode_line(s, w, sample[p], FFMIN(p, 1), 9);
1364         }
1365         for(x=0; x<w; x++){
1366             int g= sample[0][1][x];
1367             int b= sample[1][1][x];
1368             int r= sample[2][1][x];
1369
1370 //            assert(g>=0 && b>=0 && r>=0);
1371 //            assert(g<256 && b<512 && r<512);
1372
1373             b -= 0x100;
1374             r -= 0x100;
1375             g -= (b + r)>>2;
1376             b += g;
1377             r += g;
1378
1379             src[x + stride*y]= b + (g<<8) + (r<<16) + (0xFF<<24);
1380         }
1381     }
1382 }
1383
1384 static int decode_slice(AVCodecContext *c, void *arg){
1385     FFV1Context *fs= *(void**)arg;
1386     FFV1Context *f= fs->avctx->priv_data;
1387     int width = fs->slice_width;
1388     int height= fs->slice_height;
1389     int x= fs->slice_x;
1390     int y= fs->slice_y;
1391     AVFrame * const p= &f->picture;
1392
1393     av_assert1(width && height);
1394     if(f->colorspace==0){
1395         const int chroma_width = -((-width )>>f->chroma_h_shift);
1396         const int chroma_height= -((-height)>>f->chroma_v_shift);
1397         const int cx= x>>f->chroma_h_shift;
1398         const int cy= y>>f->chroma_v_shift;
1399         decode_plane(fs, p->data[0] + x + y*p->linesize[0], width, height, p->linesize[0], 0);
1400
1401         decode_plane(fs, p->data[1] + cx+cy*p->linesize[1], chroma_width, chroma_height, p->linesize[1], 1);
1402         decode_plane(fs, p->data[2] + cx+cy*p->linesize[1], chroma_width, chroma_height, p->linesize[2], 1);
1403     }else{
1404         decode_rgb_frame(fs, (uint32_t*)p->data[0] + x + y*(p->linesize[0]/4), width, height, p->linesize[0]/4);
1405     }
1406
1407     emms_c();
1408
1409     return 0;
1410 }
1411
1412 static int read_quant_table(RangeCoder *c, int16_t *quant_table, int scale){
1413     int v;
1414     int i=0;
1415     uint8_t state[CONTEXT_SIZE];
1416
1417     memset(state, 128, sizeof(state));
1418
1419     for(v=0; i<128 ; v++){
1420         int len= get_symbol(c, state, 0) + 1;
1421
1422         if(len + i > 128) return -1;
1423
1424         while(len--){
1425             quant_table[i] = scale*v;
1426             i++;
1427 //printf("%2d ",v);
1428 //if(i%16==0) printf("\n");
1429         }
1430     }
1431
1432     for(i=1; i<128; i++){
1433         quant_table[256-i]= -quant_table[i];
1434     }
1435     quant_table[128]= -quant_table[127];
1436
1437     return 2*v - 1;
1438 }
1439
1440 static int read_quant_tables(RangeCoder *c, int16_t quant_table[MAX_CONTEXT_INPUTS][256]){
1441     int i;
1442     int context_count=1;
1443
1444     for(i=0; i<5; i++){
1445         context_count*= read_quant_table(c, quant_table[i], context_count);
1446         if(context_count > 32768U){
1447             return -1;
1448         }
1449     }
1450     return (context_count+1)/2;
1451 }
1452
1453 static int read_extra_header(FFV1Context *f){
1454     RangeCoder * const c= &f->c;
1455     uint8_t state[CONTEXT_SIZE];
1456     int i, j, k;
1457     uint8_t state2[32][CONTEXT_SIZE];
1458
1459     memset(state2, 128, sizeof(state2));
1460     memset(state, 128, sizeof(state));
1461
1462     ff_init_range_decoder(c, f->avctx->extradata, f->avctx->extradata_size);
1463     ff_build_rac_states(c, 0.05*(1LL<<32), 256-8);
1464
1465     f->version= get_symbol(c, state, 0);
1466     f->ac= f->avctx->coder_type= get_symbol(c, state, 0);
1467     if(f->ac>1){
1468         for(i=1; i<256; i++){
1469             f->state_transition[i]= get_symbol(c, state, 1) + c->one_state[i];
1470         }
1471     }
1472     f->colorspace= get_symbol(c, state, 0); //YUV cs type
1473     f->avctx->bits_per_raw_sample= get_symbol(c, state, 0);
1474     get_rac(c, state); //no chroma = false
1475     f->chroma_h_shift= get_symbol(c, state, 0);
1476     f->chroma_v_shift= get_symbol(c, state, 0);
1477     get_rac(c, state); //transparency plane
1478     f->plane_count= 2;
1479     f->num_h_slices= 1 + get_symbol(c, state, 0);
1480     f->num_v_slices= 1 + get_symbol(c, state, 0);
1481     if(f->num_h_slices > (unsigned)f->width || f->num_v_slices > (unsigned)f->height){
1482         av_log(f->avctx, AV_LOG_ERROR, "too many slices\n");
1483         return -1;
1484     }
1485
1486     f->quant_table_count= get_symbol(c, state, 0);
1487     if(f->quant_table_count > (unsigned)MAX_QUANT_TABLES)
1488         return -1;
1489     for(i=0; i<f->quant_table_count; i++){
1490         if((f->context_count[i]= read_quant_tables(c, f->quant_tables[i])) < 0){
1491             av_log(f->avctx, AV_LOG_ERROR, "read_quant_table error\n");
1492             return -1;
1493         }
1494     }
1495
1496     if(allocate_initial_states(f) < 0)
1497         return AVERROR(ENOMEM);
1498
1499     for(i=0; i<f->quant_table_count; i++){
1500         if(get_rac(c, state)){
1501             for(j=0; j<f->context_count[i]; j++){
1502                 for(k=0; k<CONTEXT_SIZE; k++){
1503                     int pred= j ? f->initial_states[i][j-1][k] : 128;
1504                     f->initial_states[i][j][k]= (pred+get_symbol(c, state2[k], 1))&0xFF;
1505                 }
1506             }
1507         }
1508     }
1509
1510     return 0;
1511 }
1512
1513 static int read_header(FFV1Context *f){
1514     uint8_t state[CONTEXT_SIZE];
1515     int i, j, context_count;
1516     RangeCoder * const c= &f->slice_context[0]->c;
1517
1518     memset(state, 128, sizeof(state));
1519
1520     if(f->version < 2){
1521         f->version= get_symbol(c, state, 0);
1522         f->ac= f->avctx->coder_type= get_symbol(c, state, 0);
1523         if(f->ac>1){
1524             for(i=1; i<256; i++){
1525                 f->state_transition[i]= get_symbol(c, state, 1) + c->one_state[i];
1526             }
1527         }
1528         f->colorspace= get_symbol(c, state, 0); //YUV cs type
1529         if(f->version>0)
1530             f->avctx->bits_per_raw_sample= get_symbol(c, state, 0);
1531         get_rac(c, state); //no chroma = false
1532         f->chroma_h_shift= get_symbol(c, state, 0);
1533         f->chroma_v_shift= get_symbol(c, state, 0);
1534         get_rac(c, state); //transparency plane
1535         f->plane_count= 2;
1536     }
1537
1538     if(f->colorspace==0){
1539         if(f->avctx->bits_per_raw_sample<=8){
1540             switch(16*f->chroma_h_shift + f->chroma_v_shift){
1541             case 0x00: f->avctx->pix_fmt= PIX_FMT_YUV444P; break;
1542             case 0x10: f->avctx->pix_fmt= PIX_FMT_YUV422P; break;
1543             case 0x11: f->avctx->pix_fmt= PIX_FMT_YUV420P; break;
1544             case 0x20: f->avctx->pix_fmt= PIX_FMT_YUV411P; break;
1545             case 0x22: f->avctx->pix_fmt= PIX_FMT_YUV410P; break;
1546             default:
1547                 av_log(f->avctx, AV_LOG_ERROR, "format not supported\n");
1548                 return -1;
1549             }
1550         }else{
1551             switch(16*f->chroma_h_shift + f->chroma_v_shift){
1552             case 0x00: f->avctx->pix_fmt= PIX_FMT_YUV444P16; break;
1553             case 0x10: f->avctx->pix_fmt= PIX_FMT_YUV422P16; break;
1554             case 0x11: f->avctx->pix_fmt= PIX_FMT_YUV420P16; break;
1555             default:
1556                 av_log(f->avctx, AV_LOG_ERROR, "format not supported\n");
1557                 return -1;
1558             }
1559         }
1560     }else if(f->colorspace==1){
1561         if(f->chroma_h_shift || f->chroma_v_shift){
1562             av_log(f->avctx, AV_LOG_ERROR, "chroma subsampling not supported in this colorspace\n");
1563             return -1;
1564         }
1565         f->avctx->pix_fmt= PIX_FMT_RGB32;
1566     }else{
1567         av_log(f->avctx, AV_LOG_ERROR, "colorspace not supported\n");
1568         return -1;
1569     }
1570
1571 //printf("%d %d %d\n", f->chroma_h_shift, f->chroma_v_shift,f->avctx->pix_fmt);
1572     if(f->version < 2){
1573         context_count= read_quant_tables(c, f->quant_table);
1574         if(context_count < 0){
1575                 av_log(f->avctx, AV_LOG_ERROR, "read_quant_table error\n");
1576                 return -1;
1577         }
1578     }else{
1579         f->slice_count= get_symbol(c, state, 0);
1580         if(f->slice_count > (unsigned)MAX_SLICES)
1581             return -1;
1582     }
1583
1584     for(j=0; j<f->slice_count; j++){
1585         FFV1Context *fs= f->slice_context[j];
1586         fs->ac= f->ac;
1587
1588         if(f->version >= 2){
1589             fs->slice_x     = get_symbol(c, state, 0)   *f->width ;
1590             fs->slice_y     = get_symbol(c, state, 0)   *f->height;
1591             fs->slice_width =(get_symbol(c, state, 0)+1)*f->width  + fs->slice_x;
1592             fs->slice_height=(get_symbol(c, state, 0)+1)*f->height + fs->slice_y;
1593
1594             fs->slice_x /= f->num_h_slices;
1595             fs->slice_y /= f->num_v_slices;
1596             fs->slice_width  = fs->slice_width /f->num_h_slices - fs->slice_x;
1597             fs->slice_height = fs->slice_height/f->num_v_slices - fs->slice_y;
1598             if((unsigned)fs->slice_width > f->width || (unsigned)fs->slice_height > f->height)
1599                 return -1;
1600             if(    (unsigned)fs->slice_x + (uint64_t)fs->slice_width  > f->width
1601                 || (unsigned)fs->slice_y + (uint64_t)fs->slice_height > f->height)
1602                 return -1;
1603         }
1604
1605         for(i=0; i<f->plane_count; i++){
1606             PlaneContext * const p= &fs->plane[i];
1607
1608             if(f->version >= 2){
1609                 int idx=get_symbol(c, state, 0);
1610                 if(idx > (unsigned)f->quant_table_count){
1611                     av_log(f->avctx, AV_LOG_ERROR, "quant_table_index out of range\n");
1612                     return -1;
1613                 }
1614                 p->quant_table_index= idx;
1615                 memcpy(p->quant_table, f->quant_tables[idx], sizeof(p->quant_table));
1616                 context_count= f->context_count[idx];
1617             }else{
1618                 memcpy(p->quant_table, f->quant_table, sizeof(p->quant_table));
1619             }
1620
1621             if(p->context_count < context_count){
1622                 av_freep(&p->state);
1623                 av_freep(&p->vlc_state);
1624             }
1625             p->context_count= context_count;
1626         }
1627     }
1628
1629     return 0;
1630 }
1631
1632 static av_cold int decode_init(AVCodecContext *avctx)
1633 {
1634     FFV1Context *f = avctx->priv_data;
1635
1636     common_init(avctx);
1637
1638     if(avctx->extradata && read_extra_header(f) < 0)
1639         return -1;
1640
1641     if(init_slice_contexts(f) < 0)
1642         return -1;
1643
1644     return 0;
1645 }
1646
1647 static int decode_frame(AVCodecContext *avctx, void *data, int *data_size, AVPacket *avpkt){
1648     const uint8_t *buf = avpkt->data;
1649     int buf_size = avpkt->size;
1650     FFV1Context *f = avctx->priv_data;
1651     RangeCoder * const c= &f->slice_context[0]->c;
1652     AVFrame * const p= &f->picture;
1653     int bytes_read, i;
1654     uint8_t keystate= 128;
1655     const uint8_t *buf_p;
1656
1657     AVFrame *picture = data;
1658
1659     ff_init_range_decoder(c, buf, buf_size);
1660     ff_build_rac_states(c, 0.05*(1LL<<32), 256-8);
1661
1662
1663     p->pict_type= FF_I_TYPE; //FIXME I vs. P
1664     if(get_rac(c, &keystate)){
1665         p->key_frame= 1;
1666         if(read_header(f) < 0)
1667             return -1;
1668         if(init_slice_state(f) < 0)
1669             return -1;
1670
1671         clear_state(f);
1672     }else{
1673         p->key_frame= 0;
1674     }
1675     if(f->ac>1){
1676         int i;
1677         for(i=1; i<256; i++){
1678             c->one_state[i]= f->state_transition[i];
1679             c->zero_state[256-i]= 256-c->one_state[i];
1680         }
1681     }
1682
1683     p->reference= 0;
1684     if(avctx->get_buffer(avctx, p) < 0){
1685         av_log(avctx, AV_LOG_ERROR, "get_buffer() failed\n");
1686         return -1;
1687     }
1688
1689     if(avctx->debug&FF_DEBUG_PICT_INFO)
1690         av_log(avctx, AV_LOG_ERROR, "keyframe:%d coder:%d\n", p->key_frame, f->ac);
1691
1692     if(!f->ac){
1693         bytes_read = c->bytestream - c->bytestream_start - 1;
1694         if(bytes_read ==0) av_log(avctx, AV_LOG_ERROR, "error at end of AC stream\n"); //FIXME
1695 //printf("pos=%d\n", bytes_read);
1696         init_get_bits(&f->slice_context[0]->gb, buf + bytes_read, buf_size - bytes_read);
1697     } else {
1698         bytes_read = 0; /* avoid warning */
1699     }
1700
1701     buf_p= buf + buf_size;
1702     for(i=f->slice_count-1; i>0; i--){
1703         FFV1Context *fs= f->slice_context[i];
1704         int v= AV_RB24(buf_p-3)+3;
1705         if(buf_p - buf <= v){
1706             av_log(avctx, AV_LOG_ERROR, "Slice pointer chain broken\n");
1707             return -1;
1708         }
1709         buf_p -= v;
1710         if(fs->ac){
1711             ff_init_range_decoder(&fs->c, buf_p, v);
1712         }else{
1713             init_get_bits(&fs->gb, buf_p, v);
1714         }
1715     }
1716
1717     avctx->execute(avctx, decode_slice, &f->slice_context[0], NULL, f->slice_count, sizeof(void*));
1718     f->picture_number++;
1719
1720     *picture= *p;
1721
1722     avctx->release_buffer(avctx, p); //FIXME
1723
1724     *data_size = sizeof(AVFrame);
1725
1726     return buf_size;
1727 }
1728
1729 AVCodec ffv1_decoder = {
1730     "ffv1",
1731     AVMEDIA_TYPE_VIDEO,
1732     CODEC_ID_FFV1,
1733     sizeof(FFV1Context),
1734     decode_init,
1735     NULL,
1736     common_end,
1737     decode_frame,
1738     CODEC_CAP_DR1 /*| CODEC_CAP_DRAW_HORIZ_BAND*/,
1739     NULL,
1740     .long_name= NULL_IF_CONFIG_SMALL("FFmpeg video codec #1"),
1741 };
1742
1743 #if CONFIG_FFV1_ENCODER
1744 AVCodec ffv1_encoder = {
1745     "ffv1",
1746     AVMEDIA_TYPE_VIDEO,
1747     CODEC_ID_FFV1,
1748     sizeof(FFV1Context),
1749     encode_init,
1750     encode_frame,
1751     common_end,
1752     .pix_fmts= (const enum PixelFormat[]){PIX_FMT_YUV420P, PIX_FMT_YUV444P, PIX_FMT_YUV422P, PIX_FMT_YUV411P, PIX_FMT_YUV410P, PIX_FMT_RGB32, PIX_FMT_YUV420P16, PIX_FMT_YUV422P16, PIX_FMT_YUV444P16, PIX_FMT_NONE},
1753     .long_name= NULL_IF_CONFIG_SMALL("FFmpeg video codec #1"),
1754 };
1755 #endif