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