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)){ //1..10
 253             e++;
 254         }
 255         assert(e<=9);
 256
 257         a= 1;
 258         for(i=e-1; i>=0; i--){
 259             a += a + get_rac(c, state+22 + i); //22..31
 260         }
 261
 262         if(is_signed && get_rac(c, state+11 + e)) //11..21
 263             return -a;
 264         else
 265             return a;
 266     }
 267 }
 268
 269 static inline void update_vlc_state(VlcState * const state, const int v){
 270     int drift= state->drift;
 271     int count= state->count;
 272     state->error_sum += FFABS(v);
 273     drift += v;
 274
 275     if(count == 128){ //FIXME variable
 276         count >>= 1;
 277         drift >>= 1;
 278         state->error_sum >>= 1;
 279     }
 280     count++;
 281
 282     if(drift <= -count){
 283         if(state->bias > -128) state->bias--;
 284
 285         drift += count;
 286         if(drift <= -count)
 287             drift= -count + 1;
 288     }else if(drift > 0){
 289         if(state->bias <  127) state->bias++;
 290
 291         drift -= count;
 292         if(drift > 0)
 293             drift= 0;
 294     }
 295
 296     state->drift= drift;
 297     state->count= count;
 298 }
 299
 300 static inline void put_vlc_symbol(PutBitContext *pb, VlcState * const state, int v, int bits){
 301     int i, k, code;
 302 //printf("final: %d ", v);
 303     v = fold(v - state->bias, bits);
 304
 305     i= state->count;
 306     k=0;
 307     while(i < state->error_sum){ //FIXME optimize
 308         k++;
 309         i += i;
 310     }
 311
 312     assert(k<=8);
 313
 314 #if 0 // JPEG LS
 315     if(k==0 && 2*state->drift <= - state->count) code= v ^ (-1);
 316     else                                         code= v;
 317 #else
 318      code= v ^ ((2*state->drift + state->count)>>31);
 319 #endif
 320
 321 //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);
 322     set_sr_golomb(pb, code, k, 12, bits);
 323
 324     update_vlc_state(state, v);
 325 }
 326
 327 static inline int get_vlc_symbol(GetBitContext *gb, VlcState * const state, int bits){
 328     int k, i, v, ret;
 329
 330     i= state->count;
 331     k=0;
 332     while(i < state->error_sum){ //FIXME optimize
 333         k++;
 334         i += i;
 335     }
 336
 337     assert(k<=8);
 338
 339     v= get_sr_golomb(gb, k, 12, bits);
 340 //printf("v:%d bias:%d error:%d drift:%d count:%d k:%d", v, state->bias, state->error_sum, state->drift, state->count, k);
 341
 342 #if 0 // JPEG LS
 343     if(k==0 && 2*state->drift <= - state->count) v ^= (-1);
 344 #else
 345      v ^= ((2*state->drift + state->count)>>31);
 346 #endif
 347
 348     ret= fold(v + state->bias, bits);
 349
 350     update_vlc_state(state, v);
 351 //printf("final: %d\n", ret);
 352     return ret;
 353 }
 354
 355 #if CONFIG_FFV1_ENCODER
 356 static inline int encode_line(FFV1Context *s, int w, int_fast16_t *sample[2], int plane_index, int bits){
 357     PlaneContext * const p= &s->plane[plane_index];
 358     RangeCoder * const c= &s->c;
 359     int x;
 360     int run_index= s->run_index;
 361     int run_count=0;
 362     int run_mode=0;
 363
 364     if(s->ac){
 365         if(c->bytestream_end - c->bytestream < w*20){
 366             av_log(s->avctx, AV_LOG_ERROR, "encoded frame too large\n");
 367             return -1;
 368         }
 369     }else{
 370         if(s->pb.buf_end - s->pb.buf - (put_bits_count(&s->pb)>>3) < w*4){
 371             av_log(s->avctx, AV_LOG_ERROR, "encoded frame too large\n");
 372             return -1;
 373         }
 374     }
 375
 376     for(x=0; x<w; x++){
 377         int diff, context;
 378
 379         context= get_context(s, sample[0]+x, sample[1]+x, sample[2]+x);
 380         diff= sample[0][x] - predict(sample[0]+x, sample[1]+x);
 381
 382         if(context < 0){
 383             context = -context;
 384             diff= -diff;
 385         }
 386
 387         diff= fold(diff, bits);
 388
 389         if(s->ac){
 390             put_symbol(c, p->state[context], diff, 1);
 391         }else{
 392             if(context == 0) run_mode=1;
 393
 394             if(run_mode){
 395
 396                 if(diff){
 397                     while(run_count >= 1<<ff_log2_run[run_index]){
 398                         run_count -= 1<<ff_log2_run[run_index];
 399                         run_index++;
 400                         put_bits(&s->pb, 1, 1);
 401                     }
 402
 403                     put_bits(&s->pb, 1 + ff_log2_run[run_index], run_count);
 404                     if(run_index) run_index--;
 405                     run_count=0;
 406                     run_mode=0;
 407                     if(diff>0) diff--;
 408                 }else{
 409                     run_count++;
 410                 }
 411             }
 412
 413 //            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));
 414
 415             if(run_mode == 0)
 416                 put_vlc_symbol(&s->pb, &p->vlc_state[context], diff, bits);
 417         }
 418     }
 419     if(run_mode){
 420         while(run_count >= 1<<ff_log2_run[run_index]){
 421             run_count -= 1<<ff_log2_run[run_index];
 422             run_index++;
 423             put_bits(&s->pb, 1, 1);
 424         }
 425
 426         if(run_count)
 427             put_bits(&s->pb, 1, 1);
 428     }
 429     s->run_index= run_index;
 430
 431     return 0;
 432 }
 433
 434 static void encode_plane(FFV1Context *s, uint8_t *src, int w, int h, int stride, int plane_index){
 435     int x,y,i;
 436     const int ring_size= s->avctx->context_model ? 3 : 2;
 437     int_fast16_t sample_buffer[ring_size][w+6], *sample[ring_size];
 438     s->run_index=0;
 439
 440     memset(sample_buffer, 0, sizeof(sample_buffer));
 441
 442     for(y=0; y<h; y++){
 443         for(i=0; i<ring_size; i++)
 444             sample[i]= sample_buffer[(h+i-y)%ring_size]+3;
 445
 446         sample[0][-1]= sample[1][0  ];
 447         sample[1][ w]= sample[1][w-1];
 448 //{START_TIMER
 449         for(x=0; x<w; x++){
 450             sample[0][x]= src[x + stride*y];
 451         }
 452         encode_line(s, w, sample, plane_index, 8);
 453 //STOP_TIMER("encode line")}
 454     }
 455 }
 456
 457 static void encode_rgb_frame(FFV1Context *s, uint32_t *src, int w, int h, int stride){
 458     int x, y, p, i;
 459     const int ring_size= s->avctx->context_model ? 3 : 2;
 460     int_fast16_t sample_buffer[3][ring_size][w+6], *sample[3][ring_size];
 461     s->run_index=0;
 462
 463     memset(sample_buffer, 0, sizeof(sample_buffer));
 464
 465     for(y=0; y<h; y++){
 466         for(i=0; i<ring_size; i++)
 467             for(p=0; p<3; p++)
 468                 sample[p][i]= sample_buffer[p][(h+i-y)%ring_size]+3;
 469
 470         for(x=0; x<w; x++){
 471             int v= src[x + stride*y];
 472             int b= v&0xFF;
 473             int g= (v>>8)&0xFF;
 474             int r= (v>>16)&0xFF;
 475
 476             b -= g;
 477             r -= g;
 478             g += (b + r)>>2;
 479             b += 0x100;
 480             r += 0x100;
 481
 482 //            assert(g>=0 && b>=0 && r>=0);
 483 //            assert(g<256 && b<512 && r<512);
 484             sample[0][0][x]= g;
 485             sample[1][0][x]= b;
 486             sample[2][0][x]= r;
 487         }
 488         for(p=0; p<3; p++){
 489             sample[p][0][-1]= sample[p][1][0  ];
 490             sample[p][1][ w]= sample[p][1][w-1];
 491             encode_line(s, w, sample[p], FFMIN(p, 1), 9);
 492         }
 493     }
 494 }
 495
 496 static void write_quant_table(RangeCoder *c, int16_t *quant_table){
 497     int last=0;
 498     int i;
 499     uint8_t state[CONTEXT_SIZE];
 500     memset(state, 128, sizeof(state));
 501
 502     for(i=1; i<128 ; i++){
 503         if(quant_table[i] != quant_table[i-1]){
 504             put_symbol(c, state, i-last-1, 0);
 505             last= i;
 506         }
 507     }
 508     put_symbol(c, state, i-last-1, 0);
 509 }
 510
 511 static void write_header(FFV1Context *f){
 512     uint8_t state[CONTEXT_SIZE];
 513     int i;
 514     RangeCoder * const c= &f->c;
 515
 516     memset(state, 128, sizeof(state));
 517
 518     put_symbol(c, state, f->version, 0);
 519     put_symbol(c, state, f->avctx->coder_type, 0);
 520     put_symbol(c, state, f->colorspace, 0); //YUV cs type
 521     put_rac(c, state, 1); //chroma planes
 522         put_symbol(c, state, f->chroma_h_shift, 0);
 523         put_symbol(c, state, f->chroma_v_shift, 0);
 524     put_rac(c, state, 0); //no transparency plane
 525
 526     for(i=0; i<5; i++)
 527         write_quant_table(c, f->quant_table[i]);
 528 }
 529 #endif /* CONFIG_FFV1_ENCODER */
 530
 531 static av_cold int common_init(AVCodecContext *avctx){
 532     FFV1Context *s = avctx->priv_data;
 533     int width, height;
 534
 535     s->avctx= avctx;
 536     s->flags= avctx->flags;
 537
 538     dsputil_init(&s->dsp, avctx);
 539
 540     width= s->width= avctx->width;
 541     height= s->height= avctx->height;
 542
 543     assert(width && height);
 544
 545     return 0;
 546 }
 547
 548 #if CONFIG_FFV1_ENCODER
 549 static av_cold int encode_init(AVCodecContext *avctx)
 550 {
 551     FFV1Context *s = avctx->priv_data;
 552     int i;
 553
 554     common_init(avctx);
 555
 556     s->version=0;
 557     s->ac= avctx->coder_type;
 558
 559     s->plane_count=2;
 560     for(i=0; i<256; i++){
 561         s->quant_table[0][i]=           quant11[i];
 562         s->quant_table[1][i]=        11*quant11[i];
 563         if(avctx->context_model==0){
 564             s->quant_table[2][i]=     11*11*quant11[i];
 565             s->quant_table[3][i]=
 566             s->quant_table[4][i]=0;
 567         }else{
 568             s->quant_table[2][i]=     11*11*quant5 [i];
 569             s->quant_table[3][i]=   5*11*11*quant5 [i];
 570             s->quant_table[4][i]= 5*5*11*11*quant5 [i];
 571         }
 572     }
 573
 574     for(i=0; i<s->plane_count; i++){
 575         PlaneContext * const p= &s->plane[i];
 576
 577         if(avctx->context_model==0){
 578             p->context_count= (11*11*11+1)/2;
 579         }else{
 580             p->context_count= (11*11*5*5*5+1)/2;
 581         }
 582
 583         if(s->ac){
 584             if(!p->state) p->state= av_malloc(CONTEXT_SIZE*p->context_count*sizeof(uint8_t));
 585         }else{
 586             if(!p->vlc_state) p->vlc_state= av_malloc(p->context_count*sizeof(VlcState));
 587         }
 588     }
 589
 590     avctx->coded_frame= &s->picture;
 591     switch(avctx->pix_fmt){
 592     case PIX_FMT_YUV444P:
 593     case PIX_FMT_YUV422P:
 594     case PIX_FMT_YUV420P:
 595     case PIX_FMT_YUV411P:
 596     case PIX_FMT_YUV410P:
 597         s->colorspace= 0;
 598         break;
 599     case PIX_FMT_RGB32:
 600         s->colorspace= 1;
 601         break;
 602     default:
 603         av_log(avctx, AV_LOG_ERROR, "format not supported\n");
 604         return -1;
 605     }
 606     avcodec_get_chroma_sub_sample(avctx->pix_fmt, &s->chroma_h_shift, &s->chroma_v_shift);
 607
 608     s->picture_number=0;
 609
 610     return 0;
 611 }
 612 #endif /* CONFIG_FFV1_ENCODER */
 613
 614
 615 static void clear_state(FFV1Context *f){
 616     int i, j;
 617
 618     for(i=0; i<f->plane_count; i++){
 619         PlaneContext *p= &f->plane[i];
 620
 621         p->interlace_bit_state[0]= 128;
 622         p->interlace_bit_state[1]= 128;
 623
 624         for(j=0; j<p->context_count; j++){
 625             if(f->ac){
 626                 memset(p->state[j], 128, sizeof(uint8_t)*CONTEXT_SIZE);
 627             }else{
 628                 p->vlc_state[j].drift= 0;
 629                 p->vlc_state[j].error_sum= 4; //FFMAX((RANGE + 32)/64, 2);
 630                 p->vlc_state[j].bias= 0;
 631                 p->vlc_state[j].count= 1;
 632             }
 633         }
 634     }
 635 }
 636
 637 #if CONFIG_FFV1_ENCODER
 638 static int encode_frame(AVCodecContext *avctx, unsigned char *buf, int buf_size, void *data){
 639     FFV1Context *f = avctx->priv_data;
 640     RangeCoder * const c= &f->c;
 641     AVFrame *pict = data;
 642     const int width= f->width;
 643     const int height= f->height;
 644     AVFrame * const p= &f->picture;
 645     int used_count= 0;
 646     uint8_t keystate=128;
 647
 648     ff_init_range_encoder(c, buf, buf_size);
 649 //    ff_init_cabac_states(c, ff_h264_lps_range, ff_h264_mps_state, ff_h264_lps_state, 64);
 650     ff_build_rac_states(c, 0.05*(1LL<<32), 256-8);
 651
 652     *p = *pict;
 653     p->pict_type= FF_I_TYPE;
 654
 655     if(avctx->gop_size==0 || f->picture_number % avctx->gop_size == 0){
 656         put_rac(c, &keystate, 1);
 657         p->key_frame= 1;
 658         write_header(f);
 659         clear_state(f);
 660     }else{
 661         put_rac(c, &keystate, 0);
 662         p->key_frame= 0;
 663     }
 664
 665     if(!f->ac){
 666         used_count += ff_rac_terminate(c);
 667 //printf("pos=%d\n", used_count);
 668         init_put_bits(&f->pb, buf + used_count, buf_size - used_count);
 669     }
 670
 671     if(f->colorspace==0){
 672         const int chroma_width = -((-width )>>f->chroma_h_shift);
 673         const int chroma_height= -((-height)>>f->chroma_v_shift);
 674
 675         encode_plane(f, p->data[0], width, height, p->linesize[0], 0);
 676
 677         encode_plane(f, p->data[1], chroma_width, chroma_height, p->linesize[1], 1);
 678         encode_plane(f, p->data[2], chroma_width, chroma_height, p->linesize[2], 1);
 679     }else{
 680         encode_rgb_frame(f, (uint32_t*)(p->data[0]), width, height, p->linesize[0]/4);
 681     }
 682     emms_c();
 683
 684     f->picture_number++;
 685
 686     if(f->ac){
 687         return ff_rac_terminate(c);
 688     }else{
 689         flush_put_bits(&f->pb); //nicer padding FIXME
 690         return used_count + (put_bits_count(&f->pb)+7)/8;
 691     }
 692 }
 693 #endif /* CONFIG_FFV1_ENCODER */
 694
 695 static av_cold int common_end(AVCodecContext *avctx){
 696     FFV1Context *s = avctx->priv_data;
 697     int i;
 698
 699     for(i=0; i<s->plane_count; i++){
 700         PlaneContext *p= &s->plane[i];
 701
 702         av_freep(&p->state);
 703         av_freep(&p->vlc_state);
 704     }
 705
 706     return 0;
 707 }
 708
 709 static inline void decode_line(FFV1Context *s, int w, int_fast16_t *sample[2], int plane_index, int bits){
 710     PlaneContext * const p= &s->plane[plane_index];
 711     RangeCoder * const c= &s->c;
 712     int x;
 713     int run_count=0;
 714     int run_mode=0;
 715     int run_index= s->run_index;
 716
 717     for(x=0; x<w; x++){
 718         int diff, context, sign;
 719
 720         context= get_context(s, sample[1] + x, sample[0] + x, sample[1] + x);
 721         if(context < 0){
 722             context= -context;
 723             sign=1;
 724         }else
 725             sign=0;
 726
 727
 728         if(s->ac){
 729             diff= get_symbol(c, p->state[context], 1);
 730         }else{
 731             if(context == 0 && run_mode==0) run_mode=1;
 732
 733             if(run_mode){
 734                 if(run_count==0 && run_mode==1){
 735                     if(get_bits1(&s->gb)){
 736                         run_count = 1<<ff_log2_run[run_index];
 737                         if(x + run_count <= w) run_index++;
 738                     }else{
 739                         if(ff_log2_run[run_index]) run_count = get_bits(&s->gb, ff_log2_run[run_index]);
 740                         else run_count=0;
 741                         if(run_index) run_index--;
 742                         run_mode=2;
 743                     }
 744                 }
 745                 run_count--;
 746                 if(run_count < 0){
 747                     run_mode=0;
 748                     run_count=0;
 749                     diff= get_vlc_symbol(&s->gb, &p->vlc_state[context], bits);
 750                     if(diff>=0) diff++;
 751                 }else
 752                     diff=0;
 753             }else
 754                 diff= get_vlc_symbol(&s->gb, &p->vlc_state[context], bits);
 755
 756 //            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));
 757         }
 758
 759         if(sign) diff= -diff;
 760
 761         sample[1][x]= (predict(sample[1] + x, sample[0] + x) + diff) & ((1<<bits)-1);
 762     }
 763     s->run_index= run_index;
 764 }
 765
 766 static void decode_plane(FFV1Context *s, uint8_t *src, int w, int h, int stride, int plane_index){
 767     int x, y;
 768     int_fast16_t sample_buffer[2][w+6];
 769     int_fast16_t *sample[2];
 770     sample[0]=sample_buffer[0]+3;
 771     sample[1]=sample_buffer[1]+3;
 772
 773     s->run_index=0;
 774
 775     memset(sample_buffer, 0, sizeof(sample_buffer));
 776
 777     for(y=0; y<h; y++){
 778         int_fast16_t *temp= sample[0]; //FIXME try a normal buffer
 779
 780         sample[0]= sample[1];
 781         sample[1]= temp;
 782
 783         sample[1][-1]= sample[0][0  ];
 784         sample[0][ w]= sample[0][w-1];
 785
 786 //{START_TIMER
 787         decode_line(s, w, sample, plane_index, 8);
 788         for(x=0; x<w; x++){
 789             src[x + stride*y]= sample[1][x];
 790         }
 791 //STOP_TIMER("decode-line")}
 792     }
 793 }
 794
 795 static void decode_rgb_frame(FFV1Context *s, uint32_t *src, int w, int h, int stride){
 796     int x, y, p;
 797     int_fast16_t sample_buffer[3][2][w+6];
 798     int_fast16_t *sample[3][2];
 799     for(x=0; x<3; x++){
 800         sample[x][0] = sample_buffer[x][0]+3;
 801         sample[x][1] = sample_buffer[x][1]+3;
 802     }
 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_RGB32;
 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 av_cold 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, AVPacket *avpkt){
 941     const uint8_t *buf = avpkt->data;
 942     int buf_size = avpkt->size;
 943     FFV1Context *f = avctx->priv_data;
 944     RangeCoder * const c= &f->c;
 945     const int width= f->width;
 946     const int height= f->height;
 947     AVFrame * const p= &f->picture;
 948     int bytes_read;
 949     uint8_t keystate= 128;
 950
 951     AVFrame *picture = data;
 952
 953     ff_init_range_decoder(c, buf, buf_size);
 954     ff_build_rac_states(c, 0.05*(1LL<<32), 256-8);
 955
 956
 957     p->pict_type= FF_I_TYPE; //FIXME I vs. P
 958     if(get_rac(c, &keystate)){
 959         p->key_frame= 1;
 960         if(read_header(f) < 0)
 961             return -1;
 962         clear_state(f);
 963     }else{
 964         p->key_frame= 0;
 965     }
 966     if(!f->plane[0].state && !f->plane[0].vlc_state)
 967         return -1;
 968
 969     p->reference= 0;
 970     if(avctx->get_buffer(avctx, p) < 0){
 971         av_log(avctx, AV_LOG_ERROR, "get_buffer() failed\n");
 972         return -1;
 973     }
 974
 975     if(avctx->debug&FF_DEBUG_PICT_INFO)
 976         av_log(avctx, AV_LOG_ERROR, "keyframe:%d coder:%d\n", p->key_frame, f->ac);
 977
 978     if(!f->ac){
 979         bytes_read = c->bytestream - c->bytestream_start - 1;
 980         if(bytes_read ==0) av_log(avctx, AV_LOG_ERROR, "error at end of AC stream\n"); //FIXME
 981 //printf("pos=%d\n", bytes_read);
 982         init_get_bits(&f->gb, buf + bytes_read, buf_size - bytes_read);
 983     } else {
 984         bytes_read = 0; /* avoid warning */
 985     }
 986
 987     if(f->colorspace==0){
 988         const int chroma_width = -((-width )>>f->chroma_h_shift);
 989         const int chroma_height= -((-height)>>f->chroma_v_shift);
 990         decode_plane(f, p->data[0], width, height, p->linesize[0], 0);
 991
 992         decode_plane(f, p->data[1], chroma_width, chroma_height, p->linesize[1], 1);
 993         decode_plane(f, p->data[2], chroma_width, chroma_height, p->linesize[2], 1);
 994     }else{
 995         decode_rgb_frame(f, (uint32_t*)p->data[0], width, height, p->linesize[0]/4);
 996     }
 997
 998     emms_c();
 999
1000     f->picture_number++;
1001
1002     *picture= *p;
1003
1004     avctx->release_buffer(avctx, p); //FIXME
1005
1006     *data_size = sizeof(AVFrame);
1007
1008     if(f->ac){
1009         bytes_read= c->bytestream - c->bytestream_start - 1;
1010         if(bytes_read ==0) av_log(f->avctx, AV_LOG_ERROR, "error at end of frame\n");
1011     }else{
1012         bytes_read+= (get_bits_count(&f->gb)+7)/8;
1013     }
1014
1015     return bytes_read;
1016 }
1017
1018 AVCodec ffv1_decoder = {
1019     "ffv1",
1020     CODEC_TYPE_VIDEO,
1021     CODEC_ID_FFV1,
1022     sizeof(FFV1Context),
1023     decode_init,
1024     NULL,
1025     common_end,
1026     decode_frame,
1027     CODEC_CAP_DR1 /*| CODEC_CAP_DRAW_HORIZ_BAND*/,
1028     NULL,
1029     .long_name= NULL_IF_CONFIG_SMALL("FFmpeg codec #1"),
1030 };
1031
1032 #if CONFIG_FFV1_ENCODER
1033 AVCodec ffv1_encoder = {
1034     "ffv1",
1035     CODEC_TYPE_VIDEO,
1036     CODEC_ID_FFV1,
1037     sizeof(FFV1Context),
1038     encode_init,
1039     encode_frame,
1040     common_end,
1041     .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},
1042     .long_name= NULL_IF_CONFIG_SMALL("FFmpeg codec #1"),
1043 };
1044 #endif