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