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