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