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