Force speed irrelevant calls to get/put_symbol() to be noinline.
[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 libavcodec/ffv1.c
25  * FF Video Codec 1 (an experimental 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
36 #define MAX_PLANES 4
37 #define CONTEXT_SIZE 32
38
39 extern const uint8_t ff_log2_run[32];
40
41 static const int8_t quant3[256]={
42  0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
43  1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
44  1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
45  1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
46  1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
47  1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
48  1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
49  1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
50 -1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,
51 -1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,
52 -1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,
53 -1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,
54 -1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,
55 -1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,
56 -1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,
57 -1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1, 0,
58 };
59 static const int8_t quant5[256]={
60  0, 1, 1, 1, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2,
61  2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2,
62  2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2,
63  2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2,
64  2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2,
65  2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2,
66  2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2,
67  2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2,
68 -2,-2,-2,-2,-2,-2,-2,-2,-2,-2,-2,-2,-2,-2,-2,-2,
69 -2,-2,-2,-2,-2,-2,-2,-2,-2,-2,-2,-2,-2,-2,-2,-2,
70 -2,-2,-2,-2,-2,-2,-2,-2,-2,-2,-2,-2,-2,-2,-2,-2,
71 -2,-2,-2,-2,-2,-2,-2,-2,-2,-2,-2,-2,-2,-2,-2,-2,
72 -2,-2,-2,-2,-2,-2,-2,-2,-2,-2,-2,-2,-2,-2,-2,-2,
73 -2,-2,-2,-2,-2,-2,-2,-2,-2,-2,-2,-2,-2,-2,-2,-2,
74 -2,-2,-2,-2,-2,-2,-2,-2,-2,-2,-2,-2,-2,-2,-2,-2,
75 -2,-2,-2,-2,-2,-2,-2,-2,-2,-2,-2,-2,-2,-1,-1,-1,
76 };
77 static const int8_t quant7[256]={
78  0, 1, 1, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2,
79  2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2,
80  2, 2, 2, 2, 2, 2, 2, 2, 3, 3, 3, 3, 3, 3, 3, 3,
81  3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3,
82  3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3,
83  3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3,
84  3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3,
85  3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3,
86 -3,-3,-3,-3,-3,-3,-3,-3,-3,-3,-3,-3,-3,-3,-3,-3,
87 -3,-3,-3,-3,-3,-3,-3,-3,-3,-3,-3,-3,-3,-3,-3,-3,
88 -3,-3,-3,-3,-3,-3,-3,-3,-3,-3,-3,-3,-3,-3,-3,-3,
89 -3,-3,-3,-3,-3,-3,-3,-3,-3,-3,-3,-3,-3,-3,-3,-3,
90 -3,-3,-3,-3,-3,-3,-3,-3,-3,-3,-3,-3,-3,-3,-3,-3,
91 -3,-3,-3,-3,-3,-3,-3,-3,-3,-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,-1,-1,
94 };
95 static const int8_t quant9[256]={
96  0, 1, 1, 2, 2, 2, 2, 3, 3, 3, 3, 3, 3, 3, 3, 3,
97  3, 3, 3, 3, 3, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4,
98  4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4,
99  4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4,
100  4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4,
101  4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4,
102  4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4,
103  4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4,
104 -4,-4,-4,-4,-4,-4,-4,-4,-4,-4,-4,-4,-4,-4,-4,-4,
105 -4,-4,-4,-4,-4,-4,-4,-4,-4,-4,-4,-4,-4,-4,-4,-4,
106 -4,-4,-4,-4,-4,-4,-4,-4,-4,-4,-4,-4,-4,-4,-4,-4,
107 -4,-4,-4,-4,-4,-4,-4,-4,-4,-4,-4,-4,-4,-4,-4,-4,
108 -4,-4,-4,-4,-4,-4,-4,-4,-4,-4,-4,-4,-4,-4,-4,-4,
109 -4,-4,-4,-4,-4,-4,-4,-4,-4,-4,-4,-4,-4,-4,-4,-4,
110 -4,-4,-4,-4,-4,-4,-4,-4,-4,-4,-4,-4,-3,-3,-3,-3,
111 -3,-3,-3,-3,-3,-3,-3,-3,-3,-3,-2,-2,-2,-2,-1,-1,
112 };
113 static const int8_t quant11[256]={
114  0, 1, 2, 2, 2, 3, 3, 3, 3, 3, 3, 3, 4, 4, 4, 4,
115  4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4,
116  4, 4, 4, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5,
117  5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5,
118  5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5,
119  5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5,
120  5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5,
121  5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5,
122 -5,-5,-5,-5,-5,-5,-5,-5,-5,-5,-5,-5,-5,-5,-5,-5,
123 -5,-5,-5,-5,-5,-5,-5,-5,-5,-5,-5,-5,-5,-5,-5,-5,
124 -5,-5,-5,-5,-5,-5,-5,-5,-5,-5,-5,-5,-5,-5,-5,-5,
125 -5,-5,-5,-5,-5,-5,-5,-5,-5,-5,-5,-5,-5,-5,-5,-5,
126 -5,-5,-5,-5,-5,-5,-5,-5,-5,-5,-5,-5,-5,-5,-5,-5,
127 -5,-5,-5,-5,-5,-5,-5,-5,-5,-5,-5,-5,-5,-5,-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,-3,-3,-3,-3,-3,-3,-3,-2,-2,-2,-1,
130 };
131 static const int8_t quant13[256]={
132  0, 1, 2, 2, 3, 3, 3, 3, 4, 4, 4, 4, 4, 4, 4, 4,
133  4, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5,
134  5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5,
135  5, 5, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6,
136  6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6,
137  6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6,
138  6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6,
139  6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6,
140 -6,-6,-6,-6,-6,-6,-6,-6,-6,-6,-6,-6,-6,-6,-6,-6,
141 -6,-6,-6,-6,-6,-6,-6,-6,-6,-6,-6,-6,-6,-6,-6,-6,
142 -6,-6,-6,-6,-6,-6,-6,-6,-6,-6,-6,-6,-6,-6,-6,-6,
143 -6,-6,-6,-6,-6,-6,-6,-6,-6,-6,-6,-6,-6,-6,-6,-6,
144 -6,-6,-6,-6,-6,-6,-6,-6,-6,-6,-6,-6,-6,-6,-6,-5,
145 -5,-5,-5,-5,-5,-5,-5,-5,-5,-5,-5,-5,-5,-5,-5,-5,
146 -5,-5,-5,-5,-5,-5,-5,-5,-5,-5,-5,-5,-5,-5,-5,-5,
147 -4,-4,-4,-4,-4,-4,-4,-4,-4,-3,-3,-3,-3,-2,-2,-1,
148 };
149
150 typedef struct VlcState{
151     int16_t drift;
152     uint16_t error_sum;
153     int8_t bias;
154     uint8_t count;
155 } VlcState;
156
157 typedef struct PlaneContext{
158     int context_count;
159     uint8_t (*state)[CONTEXT_SIZE];
160     VlcState *vlc_state;
161     uint8_t interlace_bit_state[2];
162 } PlaneContext;
163
164 typedef struct FFV1Context{
165     AVCodecContext *avctx;
166     RangeCoder c;
167     GetBitContext gb;
168     PutBitContext pb;
169     int version;
170     int width, height;
171     int chroma_h_shift, chroma_v_shift;
172     int flags;
173     int picture_number;
174     AVFrame picture;
175     int plane_count;
176     int ac;                              ///< 1-> CABAC 0-> golomb rice
177     PlaneContext plane[MAX_PLANES];
178     int16_t quant_table[5][256];
179     int run_index;
180     int colorspace;
181
182     DSPContext dsp;
183 }FFV1Context;
184
185 static av_always_inline int fold(int diff, int bits){
186     if(bits==8)
187         diff= (int8_t)diff;
188     else{
189         diff+= 1<<(bits-1);
190         diff&=(1<<bits)-1;
191         diff-= 1<<(bits-1);
192     }
193
194     return diff;
195 }
196
197 static inline int predict(int_fast16_t *src, int_fast16_t *last){
198     const int LT= last[-1];
199     const int  T= last[ 0];
200     const int L =  src[-1];
201
202     return mid_pred(L, L + T - LT, T);
203 }
204
205 static inline int get_context(FFV1Context *f, int_fast16_t *src, int_fast16_t *last, int_fast16_t *last2){
206     const int LT= last[-1];
207     const int  T= last[ 0];
208     const int RT= last[ 1];
209     const int L =  src[-1];
210
211     if(f->quant_table[3][127]){
212         const int TT= last2[0];
213         const int LL=  src[-2];
214         return f->quant_table[0][(L-LT) & 0xFF] + f->quant_table[1][(LT-T) & 0xFF] + f->quant_table[2][(T-RT) & 0xFF]
215               +f->quant_table[3][(LL-L) & 0xFF] + f->quant_table[4][(TT-T) & 0xFF];
216     }else
217         return f->quant_table[0][(L-LT) & 0xFF] + f->quant_table[1][(LT-T) & 0xFF] + f->quant_table[2][(T-RT) & 0xFF];
218 }
219
220 static inline void put_symbol_inline(RangeCoder *c, uint8_t *state, int v, int is_signed){
221     int i;
222
223     if(v){
224         const int a= FFABS(v);
225         const int e= av_log2(a);
226         put_rac(c, state+0, 0);
227
228         assert(e<=9);
229
230         for(i=0; i<e; i++){
231             put_rac(c, state+1+i, 1);  //1..10
232         }
233         put_rac(c, state+1+i, 0);
234
235         for(i=e-1; i>=0; i--){
236             put_rac(c, state+22+i, (a>>i)&1); //22..31
237         }
238
239         if(is_signed)
240             put_rac(c, state+11 + e, v < 0); //11..21
241     }else{
242         put_rac(c, state+0, 1);
243     }
244 }
245
246 static void av_noinline put_symbol(RangeCoder *c, uint8_t *state, int v, int is_signed){
247     put_symbol_inline(c, state, v, is_signed);
248 }
249
250 static inline int get_symbol_inline(RangeCoder *c, uint8_t *state, int is_signed){
251     if(get_rac(c, state+0))
252         return 0;
253     else{
254         int i, e, a;
255         e= 0;
256         while(get_rac(c, state+1 + e) && e<9){ //1..10
257             e++;
258         }
259
260         a= 1;
261         for(i=e-1; i>=0; i--){
262             a += a + get_rac(c, state+22 + i); //22..31
263         }
264
265         e= -(is_signed && get_rac(c, state+11 + e)); //11..21
266         return (a^e)-e;
267     }
268 }
269
270 static int av_noinline get_symbol(RangeCoder *c, uint8_t *state, int is_signed){
271     return get_symbol_inline(c, state, is_signed);
272 }
273
274 static inline void update_vlc_state(VlcState * const state, const int v){
275     int drift= state->drift;
276     int count= state->count;
277     state->error_sum += FFABS(v);
278     drift += v;
279
280     if(count == 128){ //FIXME variable
281         count >>= 1;
282         drift >>= 1;
283         state->error_sum >>= 1;
284     }
285     count++;
286
287     if(drift <= -count){
288         if(state->bias > -128) state->bias--;
289
290         drift += count;
291         if(drift <= -count)
292             drift= -count + 1;
293     }else if(drift > 0){
294         if(state->bias <  127) state->bias++;
295
296         drift -= count;
297         if(drift > 0)
298             drift= 0;
299     }
300
301     state->drift= drift;
302     state->count= count;
303 }
304
305 static inline void put_vlc_symbol(PutBitContext *pb, VlcState * const state, int v, int bits){
306     int i, k, code;
307 //printf("final: %d ", v);
308     v = fold(v - state->bias, bits);
309
310     i= state->count;
311     k=0;
312     while(i < state->error_sum){ //FIXME optimize
313         k++;
314         i += i;
315     }
316
317     assert(k<=8);
318
319 #if 0 // JPEG LS
320     if(k==0 && 2*state->drift <= - state->count) code= v ^ (-1);
321     else                                         code= v;
322 #else
323      code= v ^ ((2*state->drift + state->count)>>31);
324 #endif
325
326 //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);
327     set_sr_golomb(pb, code, k, 12, bits);
328
329     update_vlc_state(state, v);
330 }
331
332 static inline int get_vlc_symbol(GetBitContext *gb, VlcState * const state, int bits){
333     int k, i, v, ret;
334
335     i= state->count;
336     k=0;
337     while(i < state->error_sum){ //FIXME optimize
338         k++;
339         i += i;
340     }
341
342     assert(k<=8);
343
344     v= get_sr_golomb(gb, k, 12, bits);
345 //printf("v:%d bias:%d error:%d drift:%d count:%d k:%d", v, state->bias, state->error_sum, state->drift, state->count, k);
346
347 #if 0 // JPEG LS
348     if(k==0 && 2*state->drift <= - state->count) v ^= (-1);
349 #else
350      v ^= ((2*state->drift + state->count)>>31);
351 #endif
352
353     ret= fold(v + state->bias, bits);
354
355     update_vlc_state(state, v);
356 //printf("final: %d\n", ret);
357     return ret;
358 }
359
360 #if CONFIG_FFV1_ENCODER
361 static inline int encode_line(FFV1Context *s, int w, int_fast16_t *sample[2], int plane_index, int bits){
362     PlaneContext * const p= &s->plane[plane_index];
363     RangeCoder * const c= &s->c;
364     int x;
365     int run_index= s->run_index;
366     int run_count=0;
367     int run_mode=0;
368
369     if(s->ac){
370         if(c->bytestream_end - c->bytestream < w*20){
371             av_log(s->avctx, AV_LOG_ERROR, "encoded frame too large\n");
372             return -1;
373         }
374     }else{
375         if(s->pb.buf_end - s->pb.buf - (put_bits_count(&s->pb)>>3) < w*4){
376             av_log(s->avctx, AV_LOG_ERROR, "encoded frame too large\n");
377             return -1;
378         }
379     }
380
381     for(x=0; x<w; x++){
382         int diff, context;
383
384         context= get_context(s, sample[0]+x, sample[1]+x, sample[2]+x);
385         diff= sample[0][x] - predict(sample[0]+x, sample[1]+x);
386
387         if(context < 0){
388             context = -context;
389             diff= -diff;
390         }
391
392         diff= fold(diff, bits);
393
394         if(s->ac){
395             put_symbol_inline(c, p->state[context], diff, 1);
396         }else{
397             if(context == 0) run_mode=1;
398
399             if(run_mode){
400
401                 if(diff){
402                     while(run_count >= 1<<ff_log2_run[run_index]){
403                         run_count -= 1<<ff_log2_run[run_index];
404                         run_index++;
405                         put_bits(&s->pb, 1, 1);
406                     }
407
408                     put_bits(&s->pb, 1 + ff_log2_run[run_index], run_count);
409                     if(run_index) run_index--;
410                     run_count=0;
411                     run_mode=0;
412                     if(diff>0) diff--;
413                 }else{
414                     run_count++;
415                 }
416             }
417
418 //            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));
419
420             if(run_mode == 0)
421                 put_vlc_symbol(&s->pb, &p->vlc_state[context], diff, bits);
422         }
423     }
424     if(run_mode){
425         while(run_count >= 1<<ff_log2_run[run_index]){
426             run_count -= 1<<ff_log2_run[run_index];
427             run_index++;
428             put_bits(&s->pb, 1, 1);
429         }
430
431         if(run_count)
432             put_bits(&s->pb, 1, 1);
433     }
434     s->run_index= run_index;
435
436     return 0;
437 }
438
439 static void encode_plane(FFV1Context *s, uint8_t *src, int w, int h, int stride, int plane_index){
440     int x,y,i;
441     const int ring_size= s->avctx->context_model ? 3 : 2;
442     int_fast16_t sample_buffer[ring_size][w+6], *sample[ring_size];
443     s->run_index=0;
444
445     memset(sample_buffer, 0, sizeof(sample_buffer));
446
447     for(y=0; y<h; y++){
448         for(i=0; i<ring_size; i++)
449             sample[i]= sample_buffer[(h+i-y)%ring_size]+3;
450
451         sample[0][-1]= sample[1][0  ];
452         sample[1][ w]= sample[1][w-1];
453 //{START_TIMER
454         for(x=0; x<w; x++){
455             sample[0][x]= src[x + stride*y];
456         }
457         encode_line(s, w, sample, plane_index, 8);
458 //STOP_TIMER("encode line")}
459     }
460 }
461
462 static void encode_rgb_frame(FFV1Context *s, uint32_t *src, int w, int h, int stride){
463     int x, y, p, i;
464     const int ring_size= s->avctx->context_model ? 3 : 2;
465     int_fast16_t sample_buffer[3][ring_size][w+6], *sample[3][ring_size];
466     s->run_index=0;
467
468     memset(sample_buffer, 0, sizeof(sample_buffer));
469
470     for(y=0; y<h; y++){
471         for(i=0; i<ring_size; i++)
472             for(p=0; p<3; p++)
473                 sample[p][i]= sample_buffer[p][(h+i-y)%ring_size]+3;
474
475         for(x=0; x<w; x++){
476             int v= src[x + stride*y];
477             int b= v&0xFF;
478             int g= (v>>8)&0xFF;
479             int r= (v>>16)&0xFF;
480
481             b -= g;
482             r -= g;
483             g += (b + r)>>2;
484             b += 0x100;
485             r += 0x100;
486
487 //            assert(g>=0 && b>=0 && r>=0);
488 //            assert(g<256 && b<512 && r<512);
489             sample[0][0][x]= g;
490             sample[1][0][x]= b;
491             sample[2][0][x]= r;
492         }
493         for(p=0; p<3; p++){
494             sample[p][0][-1]= sample[p][1][0  ];
495             sample[p][1][ w]= sample[p][1][w-1];
496             encode_line(s, w, sample[p], FFMIN(p, 1), 9);
497         }
498     }
499 }
500
501 static void write_quant_table(RangeCoder *c, int16_t *quant_table){
502     int last=0;
503     int i;
504     uint8_t state[CONTEXT_SIZE];
505     memset(state, 128, sizeof(state));
506
507     for(i=1; i<128 ; i++){
508         if(quant_table[i] != quant_table[i-1]){
509             put_symbol(c, state, i-last-1, 0);
510             last= i;
511         }
512     }
513     put_symbol(c, state, i-last-1, 0);
514 }
515
516 static void write_header(FFV1Context *f){
517     uint8_t state[CONTEXT_SIZE];
518     int i;
519     RangeCoder * const c= &f->c;
520
521     memset(state, 128, sizeof(state));
522
523     put_symbol(c, state, f->version, 0);
524     put_symbol(c, state, f->avctx->coder_type, 0);
525     put_symbol(c, state, f->colorspace, 0); //YUV cs type
526     put_rac(c, state, 1); //chroma planes
527         put_symbol(c, state, f->chroma_h_shift, 0);
528         put_symbol(c, state, f->chroma_v_shift, 0);
529     put_rac(c, state, 0); //no transparency plane
530
531     for(i=0; i<5; i++)
532         write_quant_table(c, f->quant_table[i]);
533 }
534 #endif /* CONFIG_FFV1_ENCODER */
535
536 static av_cold int common_init(AVCodecContext *avctx){
537     FFV1Context *s = avctx->priv_data;
538
539     s->avctx= avctx;
540     s->flags= avctx->flags;
541
542     dsputil_init(&s->dsp, avctx);
543
544     s->width = avctx->width;
545     s->height= avctx->height;
546
547     assert(s->width && s->height);
548
549     return 0;
550 }
551
552 #if CONFIG_FFV1_ENCODER
553 static av_cold int encode_init(AVCodecContext *avctx)
554 {
555     FFV1Context *s = avctx->priv_data;
556     int i;
557
558     common_init(avctx);
559
560     s->version=0;
561     s->ac= avctx->coder_type;
562
563     s->plane_count=2;
564     for(i=0; i<256; i++){
565         s->quant_table[0][i]=           quant11[i];
566         s->quant_table[1][i]=        11*quant11[i];
567         if(avctx->context_model==0){
568             s->quant_table[2][i]=     11*11*quant11[i];
569             s->quant_table[3][i]=
570             s->quant_table[4][i]=0;
571         }else{
572             s->quant_table[2][i]=     11*11*quant5 [i];
573             s->quant_table[3][i]=   5*11*11*quant5 [i];
574             s->quant_table[4][i]= 5*5*11*11*quant5 [i];
575         }
576     }
577
578     for(i=0; i<s->plane_count; i++){
579         PlaneContext * const p= &s->plane[i];
580
581         if(avctx->context_model==0){
582             p->context_count= (11*11*11+1)/2;
583         }else{
584             p->context_count= (11*11*5*5*5+1)/2;
585         }
586
587         if(s->ac){
588             if(!p->state) p->state= av_malloc(CONTEXT_SIZE*p->context_count*sizeof(uint8_t));
589         }else{
590             if(!p->vlc_state) p->vlc_state= av_malloc(p->context_count*sizeof(VlcState));
591         }
592     }
593
594     avctx->coded_frame= &s->picture;
595     switch(avctx->pix_fmt){
596     case PIX_FMT_YUV444P:
597     case PIX_FMT_YUV422P:
598     case PIX_FMT_YUV420P:
599     case PIX_FMT_YUV411P:
600     case PIX_FMT_YUV410P:
601         s->colorspace= 0;
602         break;
603     case PIX_FMT_RGB32:
604         s->colorspace= 1;
605         break;
606     default:
607         av_log(avctx, AV_LOG_ERROR, "format not supported\n");
608         return -1;
609     }
610     avcodec_get_chroma_sub_sample(avctx->pix_fmt, &s->chroma_h_shift, &s->chroma_v_shift);
611
612     s->picture_number=0;
613
614     return 0;
615 }
616 #endif /* CONFIG_FFV1_ENCODER */
617
618
619 static void clear_state(FFV1Context *f){
620     int i, j;
621
622     for(i=0; i<f->plane_count; i++){
623         PlaneContext *p= &f->plane[i];
624
625         p->interlace_bit_state[0]= 128;
626         p->interlace_bit_state[1]= 128;
627
628         for(j=0; j<p->context_count; j++){
629             if(f->ac){
630                 memset(p->state[j], 128, sizeof(uint8_t)*CONTEXT_SIZE);
631             }else{
632                 p->vlc_state[j].drift= 0;
633                 p->vlc_state[j].error_sum= 4; //FFMAX((RANGE + 32)/64, 2);
634                 p->vlc_state[j].bias= 0;
635                 p->vlc_state[j].count= 1;
636             }
637         }
638     }
639 }
640
641 #if CONFIG_FFV1_ENCODER
642 static int encode_frame(AVCodecContext *avctx, unsigned char *buf, int buf_size, void *data){
643     FFV1Context *f = avctx->priv_data;
644     RangeCoder * const c= &f->c;
645     AVFrame *pict = data;
646     const int width= f->width;
647     const int height= f->height;
648     AVFrame * const p= &f->picture;
649     int used_count= 0;
650     uint8_t keystate=128;
651
652     ff_init_range_encoder(c, buf, buf_size);
653 //    ff_init_cabac_states(c, ff_h264_lps_range, ff_h264_mps_state, ff_h264_lps_state, 64);
654     ff_build_rac_states(c, 0.05*(1LL<<32), 256-8);
655
656     *p = *pict;
657     p->pict_type= FF_I_TYPE;
658
659     if(avctx->gop_size==0 || f->picture_number % avctx->gop_size == 0){
660         put_rac(c, &keystate, 1);
661         p->key_frame= 1;
662         write_header(f);
663         clear_state(f);
664     }else{
665         put_rac(c, &keystate, 0);
666         p->key_frame= 0;
667     }
668
669     if(!f->ac){
670         used_count += ff_rac_terminate(c);
671 //printf("pos=%d\n", used_count);
672         init_put_bits(&f->pb, buf + used_count, buf_size - used_count);
673     }
674
675     if(f->colorspace==0){
676         const int chroma_width = -((-width )>>f->chroma_h_shift);
677         const int chroma_height= -((-height)>>f->chroma_v_shift);
678
679         encode_plane(f, p->data[0], width, height, p->linesize[0], 0);
680
681         encode_plane(f, p->data[1], chroma_width, chroma_height, p->linesize[1], 1);
682         encode_plane(f, p->data[2], chroma_width, chroma_height, p->linesize[2], 1);
683     }else{
684         encode_rgb_frame(f, (uint32_t*)(p->data[0]), width, height, p->linesize[0]/4);
685     }
686     emms_c();
687
688     f->picture_number++;
689
690     if(f->ac){
691         return ff_rac_terminate(c);
692     }else{
693         flush_put_bits(&f->pb); //nicer padding FIXME
694         return used_count + (put_bits_count(&f->pb)+7)/8;
695     }
696 }
697 #endif /* CONFIG_FFV1_ENCODER */
698
699 static av_cold int common_end(AVCodecContext *avctx){
700     FFV1Context *s = avctx->priv_data;
701     int i;
702
703     for(i=0; i<s->plane_count; i++){
704         PlaneContext *p= &s->plane[i];
705
706         av_freep(&p->state);
707         av_freep(&p->vlc_state);
708     }
709
710     return 0;
711 }
712
713 static av_always_inline void decode_line(FFV1Context *s, int w, int_fast16_t *sample[2], int plane_index, int bits){
714     PlaneContext * const p= &s->plane[plane_index];
715     RangeCoder * const c= &s->c;
716     int x;
717     int run_count=0;
718     int run_mode=0;
719     int run_index= s->run_index;
720
721     for(x=0; x<w; x++){
722         int diff, context, sign;
723
724         context= get_context(s, sample[1] + x, sample[0] + x, sample[1] + x);
725         if(context < 0){
726             context= -context;
727             sign=1;
728         }else
729             sign=0;
730
731
732         if(s->ac){
733             diff= get_symbol_inline(c, p->state[context], 1);
734         }else{
735             if(context == 0 && run_mode==0) run_mode=1;
736
737             if(run_mode){
738                 if(run_count==0 && run_mode==1){
739                     if(get_bits1(&s->gb)){
740                         run_count = 1<<ff_log2_run[run_index];
741                         if(x + run_count <= w) run_index++;
742                     }else{
743                         if(ff_log2_run[run_index]) run_count = get_bits(&s->gb, ff_log2_run[run_index]);
744                         else run_count=0;
745                         if(run_index) run_index--;
746                         run_mode=2;
747                     }
748                 }
749                 run_count--;
750                 if(run_count < 0){
751                     run_mode=0;
752                     run_count=0;
753                     diff= get_vlc_symbol(&s->gb, &p->vlc_state[context], bits);
754                     if(diff>=0) diff++;
755                 }else
756                     diff=0;
757             }else
758                 diff= get_vlc_symbol(&s->gb, &p->vlc_state[context], bits);
759
760 //            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));
761         }
762
763         if(sign) diff= -diff;
764
765         sample[1][x]= (predict(sample[1] + x, sample[0] + x) + diff) & ((1<<bits)-1);
766     }
767     s->run_index= run_index;
768 }
769
770 static void decode_plane(FFV1Context *s, uint8_t *src, int w, int h, int stride, int plane_index){
771     int x, y;
772     int_fast16_t sample_buffer[2][w+6];
773     int_fast16_t *sample[2];
774     sample[0]=sample_buffer[0]+3;
775     sample[1]=sample_buffer[1]+3;
776
777     s->run_index=0;
778
779     memset(sample_buffer, 0, sizeof(sample_buffer));
780
781     for(y=0; y<h; y++){
782         int_fast16_t *temp= sample[0]; //FIXME try a normal buffer
783
784         sample[0]= sample[1];
785         sample[1]= temp;
786
787         sample[1][-1]= sample[0][0  ];
788         sample[0][ w]= sample[0][w-1];
789
790 //{START_TIMER
791         decode_line(s, w, sample, plane_index, 8);
792         for(x=0; x<w; x++){
793             src[x + stride*y]= sample[1][x];
794         }
795 //STOP_TIMER("decode-line")}
796     }
797 }
798
799 static void decode_rgb_frame(FFV1Context *s, uint32_t *src, int w, int h, int stride){
800     int x, y, p;
801     int_fast16_t sample_buffer[3][2][w+6];
802     int_fast16_t *sample[3][2];
803     for(x=0; x<3; x++){
804         sample[x][0] = sample_buffer[x][0]+3;
805         sample[x][1] = sample_buffer[x][1]+3;
806     }
807
808     s->run_index=0;
809
810     memset(sample_buffer, 0, sizeof(sample_buffer));
811
812     for(y=0; y<h; y++){
813         for(p=0; p<3; p++){
814             int_fast16_t *temp= sample[p][0]; //FIXME try a normal buffer
815
816             sample[p][0]= sample[p][1];
817             sample[p][1]= temp;
818
819             sample[p][1][-1]= sample[p][0][0  ];
820             sample[p][0][ w]= sample[p][0][w-1];
821             decode_line(s, w, sample[p], FFMIN(p, 1), 9);
822         }
823         for(x=0; x<w; x++){
824             int g= sample[0][1][x];
825             int b= sample[1][1][x];
826             int r= sample[2][1][x];
827
828 //            assert(g>=0 && b>=0 && r>=0);
829 //            assert(g<256 && b<512 && r<512);
830
831             b -= 0x100;
832             r -= 0x100;
833             g -= (b + r)>>2;
834             b += g;
835             r += g;
836
837             src[x + stride*y]= b + (g<<8) + (r<<16);
838         }
839     }
840 }
841
842 static int read_quant_table(RangeCoder *c, int16_t *quant_table, int scale){
843     int v;
844     int i=0;
845     uint8_t state[CONTEXT_SIZE];
846
847     memset(state, 128, sizeof(state));
848
849     for(v=0; i<128 ; v++){
850         int len= get_symbol(c, state, 0) + 1;
851
852         if(len + i > 128) return -1;
853
854         while(len--){
855             quant_table[i] = scale*v;
856             i++;
857 //printf("%2d ",v);
858 //if(i%16==0) printf("\n");
859         }
860     }
861
862     for(i=1; i<128; i++){
863         quant_table[256-i]= -quant_table[i];
864     }
865     quant_table[128]= -quant_table[127];
866
867     return 2*v - 1;
868 }
869
870 static int read_header(FFV1Context *f){
871     uint8_t state[CONTEXT_SIZE];
872     int i, context_count;
873     RangeCoder * const c= &f->c;
874
875     memset(state, 128, sizeof(state));
876
877     f->version= get_symbol(c, state, 0);
878     f->ac= f->avctx->coder_type= get_symbol(c, state, 0);
879     f->colorspace= get_symbol(c, state, 0); //YUV cs type
880     get_rac(c, state); //no chroma = false
881     f->chroma_h_shift= get_symbol(c, state, 0);
882     f->chroma_v_shift= get_symbol(c, state, 0);
883     get_rac(c, state); //transparency plane
884     f->plane_count= 2;
885
886     if(f->colorspace==0){
887         switch(16*f->chroma_h_shift + f->chroma_v_shift){
888         case 0x00: f->avctx->pix_fmt= PIX_FMT_YUV444P; break;
889         case 0x10: f->avctx->pix_fmt= PIX_FMT_YUV422P; break;
890         case 0x11: f->avctx->pix_fmt= PIX_FMT_YUV420P; break;
891         case 0x20: f->avctx->pix_fmt= PIX_FMT_YUV411P; break;
892         case 0x22: f->avctx->pix_fmt= PIX_FMT_YUV410P; break;
893         default:
894             av_log(f->avctx, AV_LOG_ERROR, "format not supported\n");
895             return -1;
896         }
897     }else if(f->colorspace==1){
898         if(f->chroma_h_shift || f->chroma_v_shift){
899             av_log(f->avctx, AV_LOG_ERROR, "chroma subsampling not supported in this colorspace\n");
900             return -1;
901         }
902         f->avctx->pix_fmt= PIX_FMT_RGB32;
903     }else{
904         av_log(f->avctx, AV_LOG_ERROR, "colorspace not supported\n");
905         return -1;
906     }
907
908 //printf("%d %d %d\n", f->chroma_h_shift, f->chroma_v_shift,f->avctx->pix_fmt);
909
910     context_count=1;
911     for(i=0; i<5; i++){
912         context_count*= read_quant_table(c, f->quant_table[i], context_count);
913         if(context_count < 0 || context_count > 32768){
914             av_log(f->avctx, AV_LOG_ERROR, "read_quant_table error\n");
915             return -1;
916         }
917     }
918     context_count= (context_count+1)/2;
919
920     for(i=0; i<f->plane_count; i++){
921         PlaneContext * const p= &f->plane[i];
922
923         p->context_count= context_count;
924
925         if(f->ac){
926             if(!p->state) p->state= av_malloc(CONTEXT_SIZE*p->context_count*sizeof(uint8_t));
927         }else{
928             if(!p->vlc_state) p->vlc_state= av_malloc(p->context_count*sizeof(VlcState));
929         }
930     }
931
932     return 0;
933 }
934
935 static av_cold int decode_init(AVCodecContext *avctx)
936 {
937 //    FFV1Context *s = avctx->priv_data;
938
939     common_init(avctx);
940
941     return 0;
942 }
943
944 static int decode_frame(AVCodecContext *avctx, void *data, int *data_size, AVPacket *avpkt){
945     const uint8_t *buf = avpkt->data;
946     int buf_size = avpkt->size;
947     FFV1Context *f = avctx->priv_data;
948     RangeCoder * const c= &f->c;
949     const int width= f->width;
950     const int height= f->height;
951     AVFrame * const p= &f->picture;
952     int bytes_read;
953     uint8_t keystate= 128;
954
955     AVFrame *picture = data;
956
957     ff_init_range_decoder(c, buf, buf_size);
958     ff_build_rac_states(c, 0.05*(1LL<<32), 256-8);
959
960
961     p->pict_type= FF_I_TYPE; //FIXME I vs. P
962     if(get_rac(c, &keystate)){
963         p->key_frame= 1;
964         if(read_header(f) < 0)
965             return -1;
966         clear_state(f);
967     }else{
968         p->key_frame= 0;
969     }
970     if(!f->plane[0].state && !f->plane[0].vlc_state)
971         return -1;
972
973     p->reference= 0;
974     if(avctx->get_buffer(avctx, p) < 0){
975         av_log(avctx, AV_LOG_ERROR, "get_buffer() failed\n");
976         return -1;
977     }
978
979     if(avctx->debug&FF_DEBUG_PICT_INFO)
980         av_log(avctx, AV_LOG_ERROR, "keyframe:%d coder:%d\n", p->key_frame, f->ac);
981
982     if(!f->ac){
983         bytes_read = c->bytestream - c->bytestream_start - 1;
984         if(bytes_read ==0) av_log(avctx, AV_LOG_ERROR, "error at end of AC stream\n"); //FIXME
985 //printf("pos=%d\n", bytes_read);
986         init_get_bits(&f->gb, buf + bytes_read, buf_size - bytes_read);
987     } else {
988         bytes_read = 0; /* avoid warning */
989     }
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         decode_plane(f, p->data[0], width, height, p->linesize[0], 0);
995
996         decode_plane(f, p->data[1], chroma_width, chroma_height, p->linesize[1], 1);
997         decode_plane(f, p->data[2], chroma_width, chroma_height, p->linesize[2], 1);
998     }else{
999         decode_rgb_frame(f, (uint32_t*)p->data[0], width, height, p->linesize[0]/4);
1000     }
1001
1002     emms_c();
1003
1004     f->picture_number++;
1005
1006     *picture= *p;
1007
1008     avctx->release_buffer(avctx, p); //FIXME
1009
1010     *data_size = sizeof(AVFrame);
1011
1012     if(f->ac){
1013         bytes_read= c->bytestream - c->bytestream_start - 1;
1014         if(bytes_read ==0) av_log(f->avctx, AV_LOG_ERROR, "error at end of frame\n");
1015     }else{
1016         bytes_read+= (get_bits_count(&f->gb)+7)/8;
1017     }
1018
1019     return bytes_read;
1020 }
1021
1022 AVCodec ffv1_decoder = {
1023     "ffv1",
1024     CODEC_TYPE_VIDEO,
1025     CODEC_ID_FFV1,
1026     sizeof(FFV1Context),
1027     decode_init,
1028     NULL,
1029     common_end,
1030     decode_frame,
1031     CODEC_CAP_DR1 /*| CODEC_CAP_DRAW_HORIZ_BAND*/,
1032     NULL,
1033     .long_name= NULL_IF_CONFIG_SMALL("FFmpeg codec #1"),
1034 };
1035
1036 #if CONFIG_FFV1_ENCODER
1037 AVCodec ffv1_encoder = {
1038     "ffv1",
1039     CODEC_TYPE_VIDEO,
1040     CODEC_ID_FFV1,
1041     sizeof(FFV1Context),
1042     encode_init,
1043     encode_frame,
1044     common_end,
1045     .pix_fmts= (enum PixelFormat[]){PIX_FMT_YUV420P, PIX_FMT_YUV444P, PIX_FMT_YUV422P, PIX_FMT_YUV411P, PIX_FMT_YUV410P, PIX_FMT_RGB32, PIX_FMT_NONE},
1046     .long_name= NULL_IF_CONFIG_SMALL("FFmpeg codec #1"),
1047 };
1048 #endif