git.sesse.net Git - ffmpeg/blob - libavcodec/ffv1.c

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