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