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