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
 534     s->avctx= avctx;
 535     s->flags= avctx->flags;
 536
 537     dsputil_init(&s->dsp, avctx);
 538
 539     s->width = avctx->width;
 540     s->height= avctx->height;
 541
 542     assert(s->width && s->height);
 543
 544     return 0;
 545 }
 546
 547 #if CONFIG_FFV1_ENCODER
 548 static av_cold 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_RGB32:
 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 #endif /* CONFIG_FFV1_ENCODER */
 612
 613
 614 static void clear_state(FFV1Context *f){
 615     int i, j;
 616
 617     for(i=0; i<f->plane_count; i++){
 618         PlaneContext *p= &f->plane[i];
 619
 620         p->interlace_bit_state[0]= 128;
 621         p->interlace_bit_state[1]= 128;
 622
 623         for(j=0; j<p->context_count; j++){
 624             if(f->ac){
 625                 memset(p->state[j], 128, sizeof(uint8_t)*CONTEXT_SIZE);
 626             }else{
 627                 p->vlc_state[j].drift= 0;
 628                 p->vlc_state[j].error_sum= 4; //FFMAX((RANGE + 32)/64, 2);
 629                 p->vlc_state[j].bias= 0;
 630                 p->vlc_state[j].count= 1;
 631             }
 632         }
 633     }
 634 }
 635
 636 #if CONFIG_FFV1_ENCODER
 637 static int encode_frame(AVCodecContext *avctx, unsigned char *buf, int buf_size, void *data){
 638     FFV1Context *f = avctx->priv_data;
 639     RangeCoder * const c= &f->c;
 640     AVFrame *pict = data;
 641     const int width= f->width;
 642     const int height= f->height;
 643     AVFrame * const p= &f->picture;
 644     int used_count= 0;
 645     uint8_t keystate=128;
 646
 647     ff_init_range_encoder(c, buf, buf_size);
 648 //    ff_init_cabac_states(c, ff_h264_lps_range, ff_h264_mps_state, ff_h264_lps_state, 64);
 649     ff_build_rac_states(c, 0.05*(1LL<<32), 256-8);
 650
 651     *p = *pict;
 652     p->pict_type= FF_I_TYPE;
 653
 654     if(avctx->gop_size==0 || f->picture_number % avctx->gop_size == 0){
 655         put_rac(c, &keystate, 1);
 656         p->key_frame= 1;
 657         write_header(f);
 658         clear_state(f);
 659     }else{
 660         put_rac(c, &keystate, 0);
 661         p->key_frame= 0;
 662     }
 663
 664     if(!f->ac){
 665         used_count += ff_rac_terminate(c);
 666 //printf("pos=%d\n", used_count);
 667         init_put_bits(&f->pb, buf + used_count, buf_size - used_count);
 668     }
 669
 670     if(f->colorspace==0){
 671         const int chroma_width = -((-width )>>f->chroma_h_shift);
 672         const int chroma_height= -((-height)>>f->chroma_v_shift);
 673
 674         encode_plane(f, p->data[0], width, height, p->linesize[0], 0);
 675
 676         encode_plane(f, p->data[1], chroma_width, chroma_height, p->linesize[1], 1);
 677         encode_plane(f, p->data[2], chroma_width, chroma_height, p->linesize[2], 1);
 678     }else{
 679         encode_rgb_frame(f, (uint32_t*)(p->data[0]), width, height, p->linesize[0]/4);
 680     }
 681     emms_c();
 682
 683     f->picture_number++;
 684
 685     if(f->ac){
 686         return ff_rac_terminate(c);
 687     }else{
 688         flush_put_bits(&f->pb); //nicer padding FIXME
 689         return used_count + (put_bits_count(&f->pb)+7)/8;
 690     }
 691 }
 692 #endif /* CONFIG_FFV1_ENCODER */
 693
 694 static av_cold int common_end(AVCodecContext *avctx){
 695     FFV1Context *s = avctx->priv_data;
 696     int i;
 697
 698     for(i=0; i<s->plane_count; i++){
 699         PlaneContext *p= &s->plane[i];
 700
 701         av_freep(&p->state);
 702         av_freep(&p->vlc_state);
 703     }
 704
 705     return 0;
 706 }
 707
 708 static inline void decode_line(FFV1Context *s, int w, int_fast16_t *sample[2], int plane_index, int bits){
 709     PlaneContext * const p= &s->plane[plane_index];
 710     RangeCoder * const c= &s->c;
 711     int x;
 712     int run_count=0;
 713     int run_mode=0;
 714     int run_index= s->run_index;
 715
 716     for(x=0; x<w; x++){
 717         int diff, context, sign;
 718
 719         context= get_context(s, sample[1] + x, sample[0] + x, sample[1] + x);
 720         if(context < 0){
 721             context= -context;
 722             sign=1;
 723         }else
 724             sign=0;
 725
 726
 727         if(s->ac){
 728             diff= get_symbol(c, p->state[context], 1);
 729         }else{
 730             if(context == 0 && run_mode==0) run_mode=1;
 731
 732             if(run_mode){
 733                 if(run_count==0 && run_mode==1){
 734                     if(get_bits1(&s->gb)){
 735                         run_count = 1<<ff_log2_run[run_index];
 736                         if(x + run_count <= w) run_index++;
 737                     }else{
 738                         if(ff_log2_run[run_index]) run_count = get_bits(&s->gb, ff_log2_run[run_index]);
 739                         else run_count=0;
 740                         if(run_index) run_index--;
 741                         run_mode=2;
 742                     }
 743                 }
 744                 run_count--;
 745                 if(run_count < 0){
 746                     run_mode=0;
 747                     run_count=0;
 748                     diff= get_vlc_symbol(&s->gb, &p->vlc_state[context], bits);
 749                     if(diff>=0) diff++;
 750                 }else
 751                     diff=0;
 752             }else
 753                 diff= get_vlc_symbol(&s->gb, &p->vlc_state[context], bits);
 754
 755 //            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));
 756         }
 757
 758         if(sign) diff= -diff;
 759
 760         sample[1][x]= (predict(sample[1] + x, sample[0] + x) + diff) & ((1<<bits)-1);
 761     }
 762     s->run_index= run_index;
 763 }
 764
 765 static void decode_plane(FFV1Context *s, uint8_t *src, int w, int h, int stride, int plane_index){
 766     int x, y;
 767     int_fast16_t sample_buffer[2][w+6];
 768     int_fast16_t *sample[2];
 769     sample[0]=sample_buffer[0]+3;
 770     sample[1]=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     for(x=0; x<3; x++){
 799         sample[x][0] = sample_buffer[x][0]+3;
 800         sample[x][1] = sample_buffer[x][1]+3;
 801     }
 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 av_cold 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, AVPacket *avpkt){
 940     const uint8_t *buf = avpkt->data;
 941     int buf_size = avpkt->size;
 942     FFV1Context *f = avctx->priv_data;
 943     RangeCoder * const c= &f->c;
 944     const int width= f->width;
 945     const int height= f->height;
 946     AVFrame * const p= &f->picture;
 947     int bytes_read;
 948     uint8_t keystate= 128;
 949
 950     AVFrame *picture = data;
 951
 952     ff_init_range_decoder(c, buf, buf_size);
 953     ff_build_rac_states(c, 0.05*(1LL<<32), 256-8);
 954
 955
 956     p->pict_type= FF_I_TYPE; //FIXME I vs. P
 957     if(get_rac(c, &keystate)){
 958         p->key_frame= 1;
 959         if(read_header(f) < 0)
 960             return -1;
 961         clear_state(f);
 962     }else{
 963         p->key_frame= 0;
 964     }
 965     if(!f->plane[0].state && !f->plane[0].vlc_state)
 966         return -1;
 967
 968     p->reference= 0;
 969     if(avctx->get_buffer(avctx, p) < 0){
 970         av_log(avctx, AV_LOG_ERROR, "get_buffer() failed\n");
 971         return -1;
 972     }
 973
 974     if(avctx->debug&FF_DEBUG_PICT_INFO)
 975         av_log(avctx, AV_LOG_ERROR, "keyframe:%d coder:%d\n", p->key_frame, f->ac);
 976
 977     if(!f->ac){
 978         bytes_read = c->bytestream - c->bytestream_start - 1;
 979         if(bytes_read ==0) av_log(avctx, AV_LOG_ERROR, "error at end of AC stream\n"); //FIXME
 980 //printf("pos=%d\n", bytes_read);
 981         init_get_bits(&f->gb, buf + bytes_read, buf_size - bytes_read);
 982     } else {
 983         bytes_read = 0; /* avoid warning */
 984     }
 985
 986     if(f->colorspace==0){
 987         const int chroma_width = -((-width )>>f->chroma_h_shift);
 988         const int chroma_height= -((-height)>>f->chroma_v_shift);
 989         decode_plane(f, p->data[0], width, height, p->linesize[0], 0);
 990
 991         decode_plane(f, p->data[1], chroma_width, chroma_height, p->linesize[1], 1);
 992         decode_plane(f, p->data[2], chroma_width, chroma_height, p->linesize[2], 1);
 993     }else{
 994         decode_rgb_frame(f, (uint32_t*)p->data[0], width, height, p->linesize[0]/4);
 995     }
 996
 997     emms_c();
 998
 999     f->picture_number++;
1000
1001     *picture= *p;
1002
1003     avctx->release_buffer(avctx, p); //FIXME
1004
1005     *data_size = sizeof(AVFrame);
1006
1007     if(f->ac){
1008         bytes_read= c->bytestream - c->bytestream_start - 1;
1009         if(bytes_read ==0) av_log(f->avctx, AV_LOG_ERROR, "error at end of frame\n");
1010     }else{
1011         bytes_read+= (get_bits_count(&f->gb)+7)/8;
1012     }
1013
1014     return bytes_read;
1015 }
1016
1017 AVCodec ffv1_decoder = {
1018     "ffv1",
1019     CODEC_TYPE_VIDEO,
1020     CODEC_ID_FFV1,
1021     sizeof(FFV1Context),
1022     decode_init,
1023     NULL,
1024     common_end,
1025     decode_frame,
1026     CODEC_CAP_DR1 /*| CODEC_CAP_DRAW_HORIZ_BAND*/,
1027     NULL,
1028     .long_name= NULL_IF_CONFIG_SMALL("FFmpeg codec #1"),
1029 };
1030
1031 #if CONFIG_FFV1_ENCODER
1032 AVCodec ffv1_encoder = {
1033     "ffv1",
1034     CODEC_TYPE_VIDEO,
1035     CODEC_ID_FFV1,
1036     sizeof(FFV1Context),
1037     encode_init,
1038     encode_frame,
1039     common_end,
1040     .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},
1041     .long_name= NULL_IF_CONFIG_SMALL("FFmpeg codec #1"),
1042 };
1043 #endif