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