libavcodec/ffv1.c

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