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