Optimize state initialization in ffv1 clear_state().
[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     if(avctx->flags & CODEC_FLAG_PASS1)
949     avctx->stats_out= av_mallocz(STATS_OUT_SIZE);
950
951     return 0;
952 }
953 #endif /* CONFIG_FFV1_ENCODER */
954
955
956 static void clear_state(FFV1Context *f){
957     int i, si, j;
958
959     for(si=0; si<f->slice_count; si++){
960         FFV1Context *fs= f->slice_context[si];
961         for(i=0; i<f->plane_count; i++){
962             PlaneContext *p= &fs->plane[i];
963
964             p->interlace_bit_state[0]= 128;
965             p->interlace_bit_state[1]= 128;
966
967             if(fs->ac){
968                 memset(p->state, 128, CONTEXT_SIZE*p->context_count);
969             }else{
970             for(j=0; j<p->context_count; j++){
971                     p->vlc_state[j].drift= 0;
972                     p->vlc_state[j].error_sum= 4; //FFMAX((RANGE + 32)/64, 2);
973                     p->vlc_state[j].bias= 0;
974                     p->vlc_state[j].count= 1;
975             }
976             }
977         }
978     }
979 }
980
981 #if CONFIG_FFV1_ENCODER
982 static int encode_slice(AVCodecContext *c, void *arg){
983     FFV1Context *fs= *(void**)arg;
984     FFV1Context *f= fs->avctx->priv_data;
985     int width = fs->slice_width;
986     int height= fs->slice_height;
987     int x= fs->slice_x;
988     int y= fs->slice_y;
989     AVFrame * const p= &f->picture;
990
991     if(f->colorspace==0){
992         const int chroma_width = -((-width )>>f->chroma_h_shift);
993         const int chroma_height= -((-height)>>f->chroma_v_shift);
994         const int cx= x>>f->chroma_h_shift;
995         const int cy= y>>f->chroma_v_shift;
996
997         encode_plane(fs, p->data[0] + x + y*p->linesize[0], width, height, p->linesize[0], 0);
998
999         encode_plane(fs, p->data[1] + cx+cy*p->linesize[1], chroma_width, chroma_height, p->linesize[1], 1);
1000         encode_plane(fs, p->data[2] + cx+cy*p->linesize[2], chroma_width, chroma_height, p->linesize[2], 1);
1001     }else{
1002         encode_rgb_frame(fs, (uint32_t*)(p->data[0]) + x + y*(p->linesize[0]/4), width, height, p->linesize[0]/4);
1003     }
1004     emms_c();
1005
1006     return 0;
1007 }
1008
1009 static int encode_frame(AVCodecContext *avctx, unsigned char *buf, int buf_size, void *data){
1010     FFV1Context *f = avctx->priv_data;
1011     RangeCoder * const c= &f->slice_context[0]->c;
1012     AVFrame *pict = data;
1013     AVFrame * const p= &f->picture;
1014     int used_count= 0;
1015     uint8_t keystate=128;
1016     uint8_t *buf_p;
1017     int i;
1018
1019     ff_init_range_encoder(c, buf, buf_size);
1020     ff_build_rac_states(c, 0.05*(1LL<<32), 256-8);
1021
1022     *p = *pict;
1023     p->pict_type= FF_I_TYPE;
1024
1025     if(avctx->gop_size==0 || f->picture_number % avctx->gop_size == 0){
1026         put_rac(c, &keystate, 1);
1027         p->key_frame= 1;
1028         write_header(f);
1029         clear_state(f);
1030     }else{
1031         put_rac(c, &keystate, 0);
1032         p->key_frame= 0;
1033     }
1034
1035     if(!f->ac){
1036         used_count += ff_rac_terminate(c);
1037 //printf("pos=%d\n", used_count);
1038         init_put_bits(&f->slice_context[0]->pb, buf + used_count, buf_size - used_count);
1039     }else if (f->ac>1){
1040         int i;
1041         for(i=1; i<256; i++){
1042             c->one_state[i]= f->state_transition[i];
1043             c->zero_state[256-i]= 256-c->one_state[i];
1044         }
1045     }
1046
1047     for(i=1; i<f->slice_count; i++){
1048         FFV1Context *fs= f->slice_context[i];
1049         uint8_t *start= buf + (buf_size-used_count)*i/f->slice_count;
1050         int len= buf_size/f->slice_count;
1051
1052         if(fs->ac){
1053             ff_init_range_encoder(&fs->c, start, len);
1054         }else{
1055             init_put_bits(&fs->pb, start, len);
1056         }
1057     }
1058     avctx->execute(avctx, encode_slice, &f->slice_context[0], NULL, f->slice_count, sizeof(void*));
1059
1060     buf_p=buf;
1061     for(i=0; i<f->slice_count; i++){
1062         FFV1Context *fs= f->slice_context[i];
1063         int bytes;
1064
1065         if(fs->ac){
1066             uint8_t state=128;
1067             put_rac(&fs->c, &state, 0);
1068             bytes= ff_rac_terminate(&fs->c);
1069         }else{
1070             flush_put_bits(&fs->pb); //nicer padding FIXME
1071             bytes= used_count + (put_bits_count(&fs->pb)+7)/8;
1072             used_count= 0;
1073         }
1074         if(i>0){
1075             av_assert0(bytes < buf_size/f->slice_count);
1076             memmove(buf_p, fs->ac ? fs->c.bytestream_start : fs->pb.buf, bytes);
1077             av_assert0(bytes < (1<<24));
1078             AV_WB24(buf_p+bytes, bytes);
1079             bytes+=3;
1080         }
1081         buf_p += bytes;
1082     }
1083
1084     if((avctx->flags&CODEC_FLAG_PASS1) && (f->picture_number&31)==0){
1085         int j;
1086         char *p= avctx->stats_out;
1087         char *end= p + STATS_OUT_SIZE;
1088
1089         memset(f->rc_stat, 0, sizeof(f->rc_stat));
1090         for(j=0; j<f->slice_count; j++){
1091             FFV1Context *fs= f->slice_context[j];
1092             for(i=0; i<256; i++){
1093                 f->rc_stat[i][0] += fs->rc_stat[i][0];
1094                 f->rc_stat[i][1] += fs->rc_stat[i][1];
1095             }
1096         }
1097
1098         for(j=0; j<256; j++){
1099             snprintf(p, end-p, "%"PRIu64" %"PRIu64" ", f->rc_stat[j][0], f->rc_stat[j][1]);
1100             p+= strlen(p);
1101         }
1102         snprintf(p, end-p, "\n");
1103     } else if(avctx->flags&CODEC_FLAG_PASS1)
1104         avctx->stats_out[0] = '\0';
1105
1106     f->picture_number++;
1107     return buf_p-buf;
1108 }
1109 #endif /* CONFIG_FFV1_ENCODER */
1110
1111 static av_cold int common_end(AVCodecContext *avctx){
1112     FFV1Context *s = avctx->priv_data;
1113     int i, j;
1114
1115     for(j=0; j<s->slice_count; j++){
1116         FFV1Context *fs= s->slice_context[j];
1117         for(i=0; i<s->plane_count; i++){
1118             PlaneContext *p= &fs->plane[i];
1119
1120             av_freep(&p->state);
1121             av_freep(&p->vlc_state);
1122         }
1123         av_freep(&fs->sample_buffer);
1124     }
1125
1126     av_freep(&avctx->stats_out);
1127
1128     return 0;
1129 }
1130
1131 static av_always_inline void decode_line(FFV1Context *s, int w, int_fast16_t *sample[2], int plane_index, int bits){
1132     PlaneContext * const p= &s->plane[plane_index];
1133     RangeCoder * const c= &s->c;
1134     int x;
1135     int run_count=0;
1136     int run_mode=0;
1137     int run_index= s->run_index;
1138
1139     for(x=0; x<w; x++){
1140         int diff, context, sign;
1141
1142         context= get_context(p, sample[1] + x, sample[0] + x, sample[1] + x);
1143         if(context < 0){
1144             context= -context;
1145             sign=1;
1146         }else
1147             sign=0;
1148
1149         av_assert2(context < p->context_count);
1150
1151         if(s->ac){
1152             diff= get_symbol_inline(c, p->state[context], 1);
1153         }else{
1154             if(context == 0 && run_mode==0) run_mode=1;
1155
1156             if(run_mode){
1157                 if(run_count==0 && run_mode==1){
1158                     if(get_bits1(&s->gb)){
1159                         run_count = 1<<ff_log2_run[run_index];
1160                         if(x + run_count <= w) run_index++;
1161                     }else{
1162                         if(ff_log2_run[run_index]) run_count = get_bits(&s->gb, ff_log2_run[run_index]);
1163                         else run_count=0;
1164                         if(run_index) run_index--;
1165                         run_mode=2;
1166                     }
1167                 }
1168                 run_count--;
1169                 if(run_count < 0){
1170                     run_mode=0;
1171                     run_count=0;
1172                     diff= get_vlc_symbol(&s->gb, &p->vlc_state[context], bits);
1173                     if(diff>=0) diff++;
1174                 }else
1175                     diff=0;
1176             }else
1177                 diff= get_vlc_symbol(&s->gb, &p->vlc_state[context], bits);
1178
1179 //            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));
1180         }
1181
1182         if(sign) diff= -diff;
1183
1184         sample[1][x]= (predict(sample[1] + x, sample[0] + x) + diff) & ((1<<bits)-1);
1185     }
1186     s->run_index= run_index;
1187 }
1188
1189 static void decode_plane(FFV1Context *s, uint8_t *src, int w, int h, int stride, int plane_index){
1190     int x, y;
1191     int_fast16_t *sample[2];
1192     sample[0]=s->sample_buffer    +3;
1193     sample[1]=s->sample_buffer+w+6+3;
1194
1195     s->run_index=0;
1196
1197     memset(s->sample_buffer, 0, 2*(w+6)*sizeof(*s->sample_buffer));
1198
1199     for(y=0; y<h; y++){
1200         int_fast16_t *temp= sample[0]; //FIXME try a normal buffer
1201
1202         sample[0]= sample[1];
1203         sample[1]= temp;
1204
1205         sample[1][-1]= sample[0][0  ];
1206         sample[0][ w]= sample[0][w-1];
1207
1208 //{START_TIMER
1209         if(s->avctx->bits_per_raw_sample <= 8){
1210             decode_line(s, w, sample, plane_index, 8);
1211             for(x=0; x<w; x++){
1212                 src[x + stride*y]= sample[1][x];
1213             }
1214         }else{
1215             decode_line(s, w, sample, plane_index, s->avctx->bits_per_raw_sample);
1216             for(x=0; x<w; x++){
1217                 ((uint16_t*)(src + stride*y))[x]= sample[1][x] << (16 - s->avctx->bits_per_raw_sample);
1218             }
1219         }
1220 //STOP_TIMER("decode-line")}
1221     }
1222 }
1223
1224 static void decode_rgb_frame(FFV1Context *s, uint32_t *src, int w, int h, int stride){
1225     int x, y, p;
1226     int_fast16_t *sample[3][2];
1227     for(x=0; x<3; x++){
1228         sample[x][0] = s->sample_buffer +  x*2   *(w+6) + 3;
1229         sample[x][1] = s->sample_buffer + (x*2+1)*(w+6) + 3;
1230     }
1231
1232     s->run_index=0;
1233
1234     memset(s->sample_buffer, 0, 6*(w+6)*sizeof(*s->sample_buffer));
1235
1236     for(y=0; y<h; y++){
1237         for(p=0; p<3; p++){
1238             int_fast16_t *temp= sample[p][0]; //FIXME try a normal buffer
1239
1240             sample[p][0]= sample[p][1];
1241             sample[p][1]= temp;
1242
1243             sample[p][1][-1]= sample[p][0][0  ];
1244             sample[p][0][ w]= sample[p][0][w-1];
1245             decode_line(s, w, sample[p], FFMIN(p, 1), 9);
1246         }
1247         for(x=0; x<w; x++){
1248             int g= sample[0][1][x];
1249             int b= sample[1][1][x];
1250             int r= sample[2][1][x];
1251
1252 //            assert(g>=0 && b>=0 && r>=0);
1253 //            assert(g<256 && b<512 && r<512);
1254
1255             b -= 0x100;
1256             r -= 0x100;
1257             g -= (b + r)>>2;
1258             b += g;
1259             r += g;
1260
1261             src[x + stride*y]= b + (g<<8) + (r<<16) + (0xFF<<24);
1262         }
1263     }
1264 }
1265
1266 static int decode_slice(AVCodecContext *c, void *arg){
1267     FFV1Context *fs= *(void**)arg;
1268     FFV1Context *f= fs->avctx->priv_data;
1269     int width = fs->slice_width;
1270     int height= fs->slice_height;
1271     int x= fs->slice_x;
1272     int y= fs->slice_y;
1273     AVFrame * const p= &f->picture;
1274
1275     av_assert1(width && height);
1276     if(f->colorspace==0){
1277         const int chroma_width = -((-width )>>f->chroma_h_shift);
1278         const int chroma_height= -((-height)>>f->chroma_v_shift);
1279         const int cx= x>>f->chroma_h_shift;
1280         const int cy= y>>f->chroma_v_shift;
1281         decode_plane(fs, p->data[0] + x + y*p->linesize[0], width, height, p->linesize[0], 0);
1282
1283         decode_plane(fs, p->data[1] + cx+cy*p->linesize[1], chroma_width, chroma_height, p->linesize[1], 1);
1284         decode_plane(fs, p->data[2] + cx+cy*p->linesize[1], chroma_width, chroma_height, p->linesize[2], 1);
1285     }else{
1286         decode_rgb_frame(fs, (uint32_t*)p->data[0] + x + y*(p->linesize[0]/4), width, height, p->linesize[0]/4);
1287     }
1288
1289     emms_c();
1290
1291     return 0;
1292 }
1293
1294 static int read_quant_table(RangeCoder *c, int16_t *quant_table, int scale){
1295     int v;
1296     int i=0;
1297     uint8_t state[CONTEXT_SIZE];
1298
1299     memset(state, 128, sizeof(state));
1300
1301     for(v=0; i<128 ; v++){
1302         int len= get_symbol(c, state, 0) + 1;
1303
1304         if(len + i > 128) return -1;
1305
1306         while(len--){
1307             quant_table[i] = scale*v;
1308             i++;
1309 //printf("%2d ",v);
1310 //if(i%16==0) printf("\n");
1311         }
1312     }
1313
1314     for(i=1; i<128; i++){
1315         quant_table[256-i]= -quant_table[i];
1316     }
1317     quant_table[128]= -quant_table[127];
1318
1319     return 2*v - 1;
1320 }
1321
1322 static int read_quant_tables(RangeCoder *c, int16_t quant_table[MAX_CONTEXT_INPUTS][256]){
1323     int i;
1324     int context_count=1;
1325
1326     for(i=0; i<5; i++){
1327         context_count*= read_quant_table(c, quant_table[i], context_count);
1328         if(context_count > 32768U){
1329             return -1;
1330         }
1331     }
1332     return (context_count+1)/2;
1333 }
1334
1335 static int read_extra_header(FFV1Context *f){
1336     RangeCoder * const c= &f->c;
1337     uint8_t state[CONTEXT_SIZE];
1338     int i;
1339
1340     memset(state, 128, sizeof(state));
1341
1342     ff_init_range_decoder(c, f->avctx->extradata, f->avctx->extradata_size);
1343     ff_build_rac_states(c, 0.05*(1LL<<32), 256-8);
1344
1345     f->version= get_symbol(c, state, 0);
1346     f->ac= f->avctx->coder_type= get_symbol(c, state, 0);
1347     if(f->ac>1){
1348         for(i=1; i<256; i++){
1349             f->state_transition[i]= get_symbol(c, state, 1) + c->one_state[i];
1350         }
1351     }
1352     f->colorspace= get_symbol(c, state, 0); //YUV cs type
1353     f->avctx->bits_per_raw_sample= get_symbol(c, state, 0);
1354     get_rac(c, state); //no chroma = false
1355     f->chroma_h_shift= get_symbol(c, state, 0);
1356     f->chroma_v_shift= get_symbol(c, state, 0);
1357     get_rac(c, state); //transparency plane
1358     f->plane_count= 2;
1359     f->num_h_slices= 1 + get_symbol(c, state, 0);
1360     f->num_v_slices= 1 + get_symbol(c, state, 0);
1361     if(f->num_h_slices > (unsigned)f->width || f->num_v_slices > (unsigned)f->height){
1362         av_log(f->avctx, AV_LOG_ERROR, "too many slices\n");
1363         return -1;
1364     }
1365
1366     f->quant_table_count= get_symbol(c, state, 0);
1367     if(f->quant_table_count > (unsigned)MAX_QUANT_TABLES)
1368         return -1;
1369     for(i=0; i<f->quant_table_count; i++){
1370         if((f->context_count[i]= read_quant_tables(c, f->quant_tables[i])) < 0){
1371             av_log(f->avctx, AV_LOG_ERROR, "read_quant_table error\n");
1372             return -1;
1373         }
1374     }
1375
1376     return 0;
1377 }
1378
1379 static int read_header(FFV1Context *f){
1380     uint8_t state[CONTEXT_SIZE];
1381     int i, j, context_count;
1382     RangeCoder * const c= &f->slice_context[0]->c;
1383
1384     memset(state, 128, sizeof(state));
1385
1386     if(f->version < 2){
1387         f->version= get_symbol(c, state, 0);
1388         f->ac= f->avctx->coder_type= get_symbol(c, state, 0);
1389         if(f->ac>1){
1390             for(i=1; i<256; i++){
1391                 f->state_transition[i]= get_symbol(c, state, 1) + c->one_state[i];
1392             }
1393         }
1394         f->colorspace= get_symbol(c, state, 0); //YUV cs type
1395         if(f->version>0)
1396             f->avctx->bits_per_raw_sample= get_symbol(c, state, 0);
1397         get_rac(c, state); //no chroma = false
1398         f->chroma_h_shift= get_symbol(c, state, 0);
1399         f->chroma_v_shift= get_symbol(c, state, 0);
1400         get_rac(c, state); //transparency plane
1401         f->plane_count= 2;
1402     }
1403
1404     if(f->colorspace==0){
1405         if(f->avctx->bits_per_raw_sample<=8){
1406             switch(16*f->chroma_h_shift + f->chroma_v_shift){
1407             case 0x00: f->avctx->pix_fmt= PIX_FMT_YUV444P; break;
1408             case 0x10: f->avctx->pix_fmt= PIX_FMT_YUV422P; break;
1409             case 0x11: f->avctx->pix_fmt= PIX_FMT_YUV420P; break;
1410             case 0x20: f->avctx->pix_fmt= PIX_FMT_YUV411P; break;
1411             case 0x22: f->avctx->pix_fmt= PIX_FMT_YUV410P; break;
1412             default:
1413                 av_log(f->avctx, AV_LOG_ERROR, "format not supported\n");
1414                 return -1;
1415             }
1416         }else{
1417             switch(16*f->chroma_h_shift + f->chroma_v_shift){
1418             case 0x00: f->avctx->pix_fmt= PIX_FMT_YUV444P16; break;
1419             case 0x10: f->avctx->pix_fmt= PIX_FMT_YUV422P16; break;
1420             case 0x11: f->avctx->pix_fmt= PIX_FMT_YUV420P16; break;
1421             default:
1422                 av_log(f->avctx, AV_LOG_ERROR, "format not supported\n");
1423                 return -1;
1424             }
1425         }
1426     }else if(f->colorspace==1){
1427         if(f->chroma_h_shift || f->chroma_v_shift){
1428             av_log(f->avctx, AV_LOG_ERROR, "chroma subsampling not supported in this colorspace\n");
1429             return -1;
1430         }
1431         f->avctx->pix_fmt= PIX_FMT_RGB32;
1432     }else{
1433         av_log(f->avctx, AV_LOG_ERROR, "colorspace not supported\n");
1434         return -1;
1435     }
1436
1437 //printf("%d %d %d\n", f->chroma_h_shift, f->chroma_v_shift,f->avctx->pix_fmt);
1438     if(f->version < 2){
1439         context_count= read_quant_tables(c, f->quant_table);
1440         if(context_count < 0){
1441                 av_log(f->avctx, AV_LOG_ERROR, "read_quant_table error\n");
1442                 return -1;
1443         }
1444     }else{
1445         f->slice_count= get_symbol(c, state, 0);
1446         if(f->slice_count > (unsigned)MAX_SLICES)
1447             return -1;
1448     }
1449
1450     for(j=0; j<f->slice_count; j++){
1451         FFV1Context *fs= f->slice_context[j];
1452         fs->ac= f->ac;
1453
1454         if(f->version >= 2){
1455             fs->slice_x     = get_symbol(c, state, 0)   *f->width ;
1456             fs->slice_y     = get_symbol(c, state, 0)   *f->height;
1457             fs->slice_width =(get_symbol(c, state, 0)+1)*f->width  + fs->slice_x;
1458             fs->slice_height=(get_symbol(c, state, 0)+1)*f->height + fs->slice_y;
1459
1460             fs->slice_x /= f->num_h_slices;
1461             fs->slice_y /= f->num_v_slices;
1462             fs->slice_width  = fs->slice_width /f->num_h_slices - fs->slice_x;
1463             fs->slice_height = fs->slice_height/f->num_v_slices - fs->slice_y;
1464             if((unsigned)fs->slice_width > f->width || (unsigned)fs->slice_height > f->height)
1465                 return -1;
1466             if(    (unsigned)fs->slice_x + (uint64_t)fs->slice_width  > f->width
1467                 || (unsigned)fs->slice_y + (uint64_t)fs->slice_height > f->height)
1468                 return -1;
1469         }
1470
1471         for(i=0; i<f->plane_count; i++){
1472             PlaneContext * const p= &fs->plane[i];
1473
1474             if(f->version >= 2){
1475                 int idx=get_symbol(c, state, 0);
1476                 if(idx > (unsigned)f->quant_table_count){
1477                     av_log(f->avctx, AV_LOG_ERROR, "quant_table_index out of range\n");
1478                     return -1;
1479                 }
1480                 p->quant_table_index= idx;
1481                 memcpy(p->quant_table, f->quant_tables[idx], sizeof(p->quant_table));
1482                 context_count= f->context_count[idx];
1483             }else{
1484                 memcpy(p->quant_table, f->quant_table, sizeof(p->quant_table));
1485             }
1486
1487             if(p->context_count < context_count){
1488                 av_freep(&p->state);
1489                 av_freep(&p->vlc_state);
1490             }
1491             p->context_count= context_count;
1492         }
1493     }
1494
1495     return 0;
1496 }
1497
1498 static av_cold int decode_init(AVCodecContext *avctx)
1499 {
1500     FFV1Context *f = avctx->priv_data;
1501
1502     common_init(avctx);
1503
1504     if(avctx->extradata && read_extra_header(f) < 0)
1505         return -1;
1506
1507     if(init_slice_contexts(f) < 0)
1508         return -1;
1509
1510     return 0;
1511 }
1512
1513 static int decode_frame(AVCodecContext *avctx, void *data, int *data_size, AVPacket *avpkt){
1514     const uint8_t *buf = avpkt->data;
1515     int buf_size = avpkt->size;
1516     FFV1Context *f = avctx->priv_data;
1517     RangeCoder * const c= &f->slice_context[0]->c;
1518     AVFrame * const p= &f->picture;
1519     int bytes_read, i;
1520     uint8_t keystate= 128;
1521     const uint8_t *buf_p;
1522
1523     AVFrame *picture = data;
1524
1525     ff_init_range_decoder(c, buf, buf_size);
1526     ff_build_rac_states(c, 0.05*(1LL<<32), 256-8);
1527
1528
1529     p->pict_type= FF_I_TYPE; //FIXME I vs. P
1530     if(get_rac(c, &keystate)){
1531         p->key_frame= 1;
1532         if(read_header(f) < 0)
1533             return -1;
1534         if(init_slice_state(f) < 0)
1535             return -1;
1536
1537         clear_state(f);
1538     }else{
1539         p->key_frame= 0;
1540     }
1541     if(f->ac>1){
1542         int i;
1543         for(i=1; i<256; i++){
1544             c->one_state[i]= f->state_transition[i];
1545             c->zero_state[256-i]= 256-c->one_state[i];
1546         }
1547     }
1548
1549     p->reference= 0;
1550     if(avctx->get_buffer(avctx, p) < 0){
1551         av_log(avctx, AV_LOG_ERROR, "get_buffer() failed\n");
1552         return -1;
1553     }
1554
1555     if(avctx->debug&FF_DEBUG_PICT_INFO)
1556         av_log(avctx, AV_LOG_ERROR, "keyframe:%d coder:%d\n", p->key_frame, f->ac);
1557
1558     if(!f->ac){
1559         bytes_read = c->bytestream - c->bytestream_start - 1;
1560         if(bytes_read ==0) av_log(avctx, AV_LOG_ERROR, "error at end of AC stream\n"); //FIXME
1561 //printf("pos=%d\n", bytes_read);
1562         init_get_bits(&f->slice_context[0]->gb, buf + bytes_read, buf_size - bytes_read);
1563     } else {
1564         bytes_read = 0; /* avoid warning */
1565     }
1566
1567     buf_p= buf + buf_size;
1568     for(i=f->slice_count-1; i>0; i--){
1569         FFV1Context *fs= f->slice_context[i];
1570         int v= AV_RB24(buf_p-3)+3;
1571         if(buf_p - buf <= v){
1572             av_log(avctx, AV_LOG_ERROR, "Slice pointer chain broken\n");
1573             return -1;
1574         }
1575         buf_p -= v;
1576         if(fs->ac){
1577             ff_init_range_decoder(&fs->c, buf_p, v);
1578         }else{
1579             init_get_bits(&fs->gb, buf_p, v);
1580         }
1581     }
1582
1583     avctx->execute(avctx, decode_slice, &f->slice_context[0], NULL, f->slice_count, sizeof(void*));
1584     f->picture_number++;
1585
1586     *picture= *p;
1587
1588     avctx->release_buffer(avctx, p); //FIXME
1589
1590     *data_size = sizeof(AVFrame);
1591
1592     return buf_size;
1593 }
1594
1595 AVCodec ffv1_decoder = {
1596     "ffv1",
1597     AVMEDIA_TYPE_VIDEO,
1598     CODEC_ID_FFV1,
1599     sizeof(FFV1Context),
1600     decode_init,
1601     NULL,
1602     common_end,
1603     decode_frame,
1604     CODEC_CAP_DR1 /*| CODEC_CAP_DRAW_HORIZ_BAND*/,
1605     NULL,
1606     .long_name= NULL_IF_CONFIG_SMALL("FFmpeg video codec #1"),
1607 };
1608
1609 #if CONFIG_FFV1_ENCODER
1610 AVCodec ffv1_encoder = {
1611     "ffv1",
1612     AVMEDIA_TYPE_VIDEO,
1613     CODEC_ID_FFV1,
1614     sizeof(FFV1Context),
1615     encode_init,
1616     encode_frame,
1617     common_end,
1618     .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},
1619     .long_name= NULL_IF_CONFIG_SMALL("FFmpeg video codec #1"),
1620 };
1621 #endif