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 ffv1.c
  25  * FF Video Codec 1 (an experimental lossless codec)
  26  */
  27
  28 #include "avcodec.h"
  29 #include "bitstream.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 av_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= FFABS(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 += FFABS(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 #ifdef CONFIG_ENCODERS
 358 static inline int encode_line(FFV1Context *s, int w, int_fast16_t *sample[2], int plane_index, int bits){
 359     PlaneContext * const p= &s->plane[plane_index];
 360     RangeCoder * const c= &s->c;
 361     int x;
 362     int run_index= s->run_index;
 363     int run_count=0;
 364     int run_mode=0;
 365
 366     if(s->ac){
 367         if(c->bytestream_end - c->bytestream < w*20){
 368             av_log(s->avctx, AV_LOG_ERROR, "encoded frame too large\n");
 369             return -1;
 370         }
 371     }else{
 372         if(s->pb.buf_end - s->pb.buf - (put_bits_count(&s->pb)>>3) < w*4){
 373             av_log(s->avctx, AV_LOG_ERROR, "encoded frame too large\n");
 374             return -1;
 375         }
 376     }
 377
 378     for(x=0; x<w; x++){
 379         int diff, context;
 380
 381         context= get_context(s, sample[0]+x, sample[1]+x, sample[2]+x);
 382         diff= sample[0][x] - predict(sample[0]+x, sample[1]+x);
 383
 384         if(context < 0){
 385             context = -context;
 386             diff= -diff;
 387         }
 388
 389         diff= fold(diff, bits);
 390
 391         if(s->ac){
 392             put_symbol(c, p->state[context], diff, 1);
 393         }else{
 394             if(context == 0) run_mode=1;
 395
 396             if(run_mode){
 397
 398                 if(diff){
 399                     while(run_count >= 1<<log2_run[run_index]){
 400                         run_count -= 1<<log2_run[run_index];
 401                         run_index++;
 402                         put_bits(&s->pb, 1, 1);
 403                     }
 404
 405                     put_bits(&s->pb, 1 + log2_run[run_index], run_count);
 406                     if(run_index) run_index--;
 407                     run_count=0;
 408                     run_mode=0;
 409                     if(diff>0) diff--;
 410                 }else{
 411                     run_count++;
 412                 }
 413             }
 414
 415 //            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));
 416
 417             if(run_mode == 0)
 418                 put_vlc_symbol(&s->pb, &p->vlc_state[context], diff, bits);
 419         }
 420     }
 421     if(run_mode){
 422         while(run_count >= 1<<log2_run[run_index]){
 423             run_count -= 1<<log2_run[run_index];
 424             run_index++;
 425             put_bits(&s->pb, 1, 1);
 426         }
 427
 428         if(run_count)
 429             put_bits(&s->pb, 1, 1);
 430     }
 431     s->run_index= run_index;
 432
 433     return 0;
 434 }
 435
 436 static void encode_plane(FFV1Context *s, uint8_t *src, int w, int h, int stride, int plane_index){
 437     int x,y,i;
 438     const int ring_size= s->avctx->context_model ? 3 : 2;
 439     int_fast16_t sample_buffer[ring_size][w+6], *sample[ring_size];
 440     s->run_index=0;
 441
 442     memset(sample_buffer, 0, sizeof(sample_buffer));
 443
 444     for(y=0; y<h; y++){
 445         for(i=0; i<ring_size; i++)
 446             sample[i]= sample_buffer[(h+i-y)%ring_size]+3;
 447
 448         sample[0][-1]= sample[1][0  ];
 449         sample[1][ w]= sample[1][w-1];
 450 //{START_TIMER
 451         for(x=0; x<w; x++){
 452             sample[0][x]= src[x + stride*y];
 453         }
 454         encode_line(s, w, sample, plane_index, 8);
 455 //STOP_TIMER("encode line")}
 456     }
 457 }
 458
 459 static void encode_rgb_frame(FFV1Context *s, uint32_t *src, int w, int h, int stride){
 460     int x, y, p, i;
 461     const int ring_size= s->avctx->context_model ? 3 : 2;
 462     int_fast16_t sample_buffer[3][ring_size][w+6], *sample[3][ring_size];
 463     s->run_index=0;
 464
 465     memset(sample_buffer, 0, sizeof(sample_buffer));
 466
 467     for(y=0; y<h; y++){
 468         for(i=0; i<ring_size; i++)
 469             for(p=0; p<3; p++)
 470                 sample[p][i]= sample_buffer[p][(h+i-y)%ring_size]+3;
 471
 472         for(x=0; x<w; x++){
 473             int v= src[x + stride*y];
 474             int b= v&0xFF;
 475             int g= (v>>8)&0xFF;
 476             int r= (v>>16)&0xFF;
 477
 478             b -= g;
 479             r -= g;
 480             g += (b + r)>>2;
 481             b += 0x100;
 482             r += 0x100;
 483
 484 //            assert(g>=0 && b>=0 && r>=0);
 485 //            assert(g<256 && b<512 && r<512);
 486             sample[0][0][x]= g;
 487             sample[1][0][x]= b;
 488             sample[2][0][x]= r;
 489         }
 490         for(p=0; p<3; p++){
 491             sample[p][0][-1]= sample[p][1][0  ];
 492             sample[p][1][ w]= sample[p][1][w-1];
 493             encode_line(s, w, sample[p], FFMIN(p, 1), 9);
 494         }
 495     }
 496 }
 497
 498 static void write_quant_table(RangeCoder *c, int16_t *quant_table){
 499     int last=0;
 500     int i;
 501     uint8_t state[CONTEXT_SIZE];
 502     memset(state, 128, sizeof(state));
 503
 504     for(i=1; i<128 ; i++){
 505         if(quant_table[i] != quant_table[i-1]){
 506             put_symbol(c, state, i-last-1, 0);
 507             last= i;
 508         }
 509     }
 510     put_symbol(c, state, i-last-1, 0);
 511 }
 512
 513 static void write_header(FFV1Context *f){
 514     uint8_t state[CONTEXT_SIZE];
 515     int i;
 516     RangeCoder * const c= &f->c;
 517
 518     memset(state, 128, sizeof(state));
 519
 520     put_symbol(c, state, f->version, 0);
 521     put_symbol(c, state, f->avctx->coder_type, 0);
 522     put_symbol(c, state, f->colorspace, 0); //YUV cs type
 523     put_rac(c, state, 1); //chroma planes
 524         put_symbol(c, state, f->chroma_h_shift, 0);
 525         put_symbol(c, state, f->chroma_v_shift, 0);
 526     put_rac(c, state, 0); //no transparency plane
 527
 528     for(i=0; i<5; i++)
 529         write_quant_table(c, f->quant_table[i]);
 530 }
 531 #endif /* CONFIG_ENCODERS */
 532
 533 static av_cold int common_init(AVCodecContext *avctx){
 534     FFV1Context *s = avctx->priv_data;
 535     int width, height;
 536
 537     s->avctx= avctx;
 538     s->flags= avctx->flags;
 539
 540     dsputil_init(&s->dsp, avctx);
 541
 542     width= s->width= avctx->width;
 543     height= s->height= avctx->height;
 544
 545     assert(width && height);
 546
 547     return 0;
 548 }
 549
 550 #ifdef CONFIG_ENCODERS
 551 static av_cold int encode_init(AVCodecContext *avctx)
 552 {
 553     FFV1Context *s = avctx->priv_data;
 554     int i;
 555
 556     common_init(avctx);
 557
 558     s->version=0;
 559     s->ac= avctx->coder_type;
 560
 561     s->plane_count=2;
 562     for(i=0; i<256; i++){
 563         s->quant_table[0][i]=           quant11[i];
 564         s->quant_table[1][i]=        11*quant11[i];
 565         if(avctx->context_model==0){
 566             s->quant_table[2][i]=     11*11*quant11[i];
 567             s->quant_table[3][i]=
 568             s->quant_table[4][i]=0;
 569         }else{
 570             s->quant_table[2][i]=     11*11*quant5 [i];
 571             s->quant_table[3][i]=   5*11*11*quant5 [i];
 572             s->quant_table[4][i]= 5*5*11*11*quant5 [i];
 573         }
 574     }
 575
 576     for(i=0; i<s->plane_count; i++){
 577         PlaneContext * const p= &s->plane[i];
 578
 579         if(avctx->context_model==0){
 580             p->context_count= (11*11*11+1)/2;
 581         }else{
 582             p->context_count= (11*11*5*5*5+1)/2;
 583         }
 584
 585         if(s->ac){
 586             if(!p->state) p->state= av_malloc(CONTEXT_SIZE*p->context_count*sizeof(uint8_t));
 587         }else{
 588             if(!p->vlc_state) p->vlc_state= av_malloc(p->context_count*sizeof(VlcState));
 589         }
 590     }
 591
 592     avctx->coded_frame= &s->picture;
 593     switch(avctx->pix_fmt){
 594     case PIX_FMT_YUV444P:
 595     case PIX_FMT_YUV422P:
 596     case PIX_FMT_YUV420P:
 597     case PIX_FMT_YUV411P:
 598     case PIX_FMT_YUV410P:
 599         s->colorspace= 0;
 600         break;
 601     case PIX_FMT_RGB32:
 602         s->colorspace= 1;
 603         break;
 604     default:
 605         av_log(avctx, AV_LOG_ERROR, "format not supported\n");
 606         return -1;
 607     }
 608     avcodec_get_chroma_sub_sample(avctx->pix_fmt, &s->chroma_h_shift, &s->chroma_v_shift);
 609
 610     s->picture_number=0;
 611
 612     return 0;
 613 }
 614 #endif /* CONFIG_ENCODERS */
 615
 616
 617 static void clear_state(FFV1Context *f){
 618     int i, j;
 619
 620     for(i=0; i<f->plane_count; i++){
 621         PlaneContext *p= &f->plane[i];
 622
 623         p->interlace_bit_state[0]= 128;
 624         p->interlace_bit_state[1]= 128;
 625
 626         for(j=0; j<p->context_count; j++){
 627             if(f->ac){
 628                 memset(p->state[j], 128, sizeof(uint8_t)*CONTEXT_SIZE);
 629             }else{
 630                 p->vlc_state[j].drift= 0;
 631                 p->vlc_state[j].error_sum= 4; //FFMAX((RANGE + 32)/64, 2);
 632                 p->vlc_state[j].bias= 0;
 633                 p->vlc_state[j].count= 1;
 634             }
 635         }
 636     }
 637 }
 638
 639 #ifdef CONFIG_ENCODERS
 640 static int encode_frame(AVCodecContext *avctx, unsigned char *buf, int buf_size, void *data){
 641     FFV1Context *f = avctx->priv_data;
 642     RangeCoder * const c= &f->c;
 643     AVFrame *pict = data;
 644     const int width= f->width;
 645     const int height= f->height;
 646     AVFrame * const p= &f->picture;
 647     int used_count= 0;
 648     uint8_t keystate=128;
 649
 650     ff_init_range_encoder(c, buf, buf_size);
 651 //    ff_init_cabac_states(c, ff_h264_lps_range, ff_h264_mps_state, ff_h264_lps_state, 64);
 652     ff_build_rac_states(c, 0.05*(1LL<<32), 256-8);
 653
 654     *p = *pict;
 655     p->pict_type= FF_I_TYPE;
 656
 657     if(avctx->gop_size==0 || f->picture_number % avctx->gop_size == 0){
 658         put_rac(c, &keystate, 1);
 659         p->key_frame= 1;
 660         write_header(f);
 661         clear_state(f);
 662     }else{
 663         put_rac(c, &keystate, 0);
 664         p->key_frame= 0;
 665     }
 666
 667     if(!f->ac){
 668         used_count += ff_rac_terminate(c);
 669 //printf("pos=%d\n", used_count);
 670         init_put_bits(&f->pb, buf + used_count, buf_size - used_count);
 671     }
 672
 673     if(f->colorspace==0){
 674         const int chroma_width = -((-width )>>f->chroma_h_shift);
 675         const int chroma_height= -((-height)>>f->chroma_v_shift);
 676
 677         encode_plane(f, p->data[0], width, height, p->linesize[0], 0);
 678
 679         encode_plane(f, p->data[1], chroma_width, chroma_height, p->linesize[1], 1);
 680         encode_plane(f, p->data[2], chroma_width, chroma_height, p->linesize[2], 1);
 681     }else{
 682         encode_rgb_frame(f, (uint32_t*)(p->data[0]), width, height, p->linesize[0]/4);
 683     }
 684     emms_c();
 685
 686     f->picture_number++;
 687
 688     if(f->ac){
 689         return ff_rac_terminate(c);
 690     }else{
 691         flush_put_bits(&f->pb); //nicer padding FIXME
 692         return used_count + (put_bits_count(&f->pb)+7)/8;
 693     }
 694 }
 695 #endif /* CONFIG_ENCODERS */
 696
 697 static av_cold int common_end(AVCodecContext *avctx){
 698     FFV1Context *s = avctx->priv_data;
 699     int i;
 700
 701     for(i=0; i<s->plane_count; i++){
 702         PlaneContext *p= &s->plane[i];
 703
 704         av_freep(&p->state);
 705         av_freep(&p->vlc_state);
 706     }
 707
 708     return 0;
 709 }
 710
 711 static inline void decode_line(FFV1Context *s, int w, int_fast16_t *sample[2], int plane_index, int bits){
 712     PlaneContext * const p= &s->plane[plane_index];
 713     RangeCoder * const c= &s->c;
 714     int x;
 715     int run_count=0;
 716     int run_mode=0;
 717     int run_index= s->run_index;
 718
 719     for(x=0; x<w; x++){
 720         int diff, context, sign;
 721
 722         context= get_context(s, sample[1] + x, sample[0] + x, sample[1] + x);
 723         if(context < 0){
 724             context= -context;
 725             sign=1;
 726         }else
 727             sign=0;
 728
 729
 730         if(s->ac){
 731             diff= get_symbol(c, p->state[context], 1);
 732         }else{
 733             if(context == 0 && run_mode==0) run_mode=1;
 734
 735             if(run_mode){
 736                 if(run_count==0 && run_mode==1){
 737                     if(get_bits1(&s->gb)){
 738                         run_count = 1<<log2_run[run_index];
 739                         if(x + run_count <= w) run_index++;
 740                     }else{
 741                         if(log2_run[run_index]) run_count = get_bits(&s->gb, log2_run[run_index]);
 742                         else run_count=0;
 743                         if(run_index) run_index--;
 744                         run_mode=2;
 745                     }
 746                 }
 747                 run_count--;
 748                 if(run_count < 0){
 749                     run_mode=0;
 750                     run_count=0;
 751                     diff= get_vlc_symbol(&s->gb, &p->vlc_state[context], bits);
 752                     if(diff>=0) diff++;
 753                 }else
 754                     diff=0;
 755             }else
 756                 diff= get_vlc_symbol(&s->gb, &p->vlc_state[context], bits);
 757
 758 //            printf("count:%d index:%d, mode:%d, x:%d y:%d pos:%d\n", run_count, run_index, run_mode, x, y, get_bits_count(&s->gb));
 759         }
 760
 761         if(sign) diff= -diff;
 762
 763         sample[1][x]= (predict(sample[1] + x, sample[0] + x) + diff) & ((1<<bits)-1);
 764     }
 765     s->run_index= run_index;
 766 }
 767
 768 static void decode_plane(FFV1Context *s, uint8_t *src, int w, int h, int stride, int plane_index){
 769     int x, y;
 770     int_fast16_t sample_buffer[2][w+6];
 771     int_fast16_t *sample[2];
 772     sample[0]=sample_buffer[0]+3;
 773     sample[1]=sample_buffer[1]+3;
 774
 775     s->run_index=0;
 776
 777     memset(sample_buffer, 0, sizeof(sample_buffer));
 778
 779     for(y=0; y<h; y++){
 780         int_fast16_t *temp= sample[0]; //FIXME try a normal buffer
 781
 782         sample[0]= sample[1];
 783         sample[1]= temp;
 784
 785         sample[1][-1]= sample[0][0  ];
 786         sample[0][ w]= sample[0][w-1];
 787
 788 //{START_TIMER
 789         decode_line(s, w, sample, plane_index, 8);
 790         for(x=0; x<w; x++){
 791             src[x + stride*y]= sample[1][x];
 792         }
 793 //STOP_TIMER("decode-line")}
 794     }
 795 }
 796
 797 static void decode_rgb_frame(FFV1Context *s, uint32_t *src, int w, int h, int stride){
 798     int x, y, p;
 799     int_fast16_t sample_buffer[3][2][w+6];
 800     int_fast16_t *sample[3][2];
 801     for(x=0; x<3; x++){
 802         sample[x][0] = sample_buffer[x][0]+3;
 803         sample[x][1] = sample_buffer[x][1]+3;
 804     }
 805
 806     s->run_index=0;
 807
 808     memset(sample_buffer, 0, sizeof(sample_buffer));
 809
 810     for(y=0; y<h; y++){
 811         for(p=0; p<3; p++){
 812             int_fast16_t *temp= sample[p][0]; //FIXME try a normal buffer
 813
 814             sample[p][0]= sample[p][1];
 815             sample[p][1]= temp;
 816
 817             sample[p][1][-1]= sample[p][0][0  ];
 818             sample[p][0][ w]= sample[p][0][w-1];
 819             decode_line(s, w, sample[p], FFMIN(p, 1), 9);
 820         }
 821         for(x=0; x<w; x++){
 822             int g= sample[0][1][x];
 823             int b= sample[1][1][x];
 824             int r= sample[2][1][x];
 825
 826 //            assert(g>=0 && b>=0 && r>=0);
 827 //            assert(g<256 && b<512 && r<512);
 828
 829             b -= 0x100;
 830             r -= 0x100;
 831             g -= (b + r)>>2;
 832             b += g;
 833             r += g;
 834
 835             src[x + stride*y]= b + (g<<8) + (r<<16);
 836         }
 837     }
 838 }
 839
 840 static int read_quant_table(RangeCoder *c, int16_t *quant_table, int scale){
 841     int v;
 842     int i=0;
 843     uint8_t state[CONTEXT_SIZE];
 844
 845     memset(state, 128, sizeof(state));
 846
 847     for(v=0; i<128 ; v++){
 848         int len= get_symbol(c, state, 0) + 1;
 849
 850         if(len + i > 128) return -1;
 851
 852         while(len--){
 853             quant_table[i] = scale*v;
 854             i++;
 855 //printf("%2d ",v);
 856 //if(i%16==0) printf("\n");
 857         }
 858     }
 859
 860     for(i=1; i<128; i++){
 861         quant_table[256-i]= -quant_table[i];
 862     }
 863     quant_table[128]= -quant_table[127];
 864
 865     return 2*v - 1;
 866 }
 867
 868 static int read_header(FFV1Context *f){
 869     uint8_t state[CONTEXT_SIZE];
 870     int i, context_count;
 871     RangeCoder * const c= &f->c;
 872
 873     memset(state, 128, sizeof(state));
 874
 875     f->version= get_symbol(c, state, 0);
 876     f->ac= f->avctx->coder_type= get_symbol(c, state, 0);
 877     f->colorspace= get_symbol(c, state, 0); //YUV cs type
 878     get_rac(c, state); //no chroma = false
 879     f->chroma_h_shift= get_symbol(c, state, 0);
 880     f->chroma_v_shift= get_symbol(c, state, 0);
 881     get_rac(c, state); //transparency plane
 882     f->plane_count= 2;
 883
 884     if(f->colorspace==0){
 885         switch(16*f->chroma_h_shift + f->chroma_v_shift){
 886         case 0x00: f->avctx->pix_fmt= PIX_FMT_YUV444P; break;
 887         case 0x10: f->avctx->pix_fmt= PIX_FMT_YUV422P; break;
 888         case 0x11: f->avctx->pix_fmt= PIX_FMT_YUV420P; break;
 889         case 0x20: f->avctx->pix_fmt= PIX_FMT_YUV411P; break;
 890         case 0x22: f->avctx->pix_fmt= PIX_FMT_YUV410P; break;
 891         default:
 892             av_log(f->avctx, AV_LOG_ERROR, "format not supported\n");
 893             return -1;
 894         }
 895     }else if(f->colorspace==1){
 896         if(f->chroma_h_shift || f->chroma_v_shift){
 897             av_log(f->avctx, AV_LOG_ERROR, "chroma subsampling not supported in this colorspace\n");
 898             return -1;
 899         }
 900         f->avctx->pix_fmt= PIX_FMT_RGB32;
 901     }else{
 902         av_log(f->avctx, AV_LOG_ERROR, "colorspace not supported\n");
 903         return -1;
 904     }
 905
 906 //printf("%d %d %d\n", f->chroma_h_shift, f->chroma_v_shift,f->avctx->pix_fmt);
 907
 908     context_count=1;
 909     for(i=0; i<5; i++){
 910         context_count*= read_quant_table(c, f->quant_table[i], context_count);
 911         if(context_count < 0 || context_count > 32768){
 912             av_log(f->avctx, AV_LOG_ERROR, "read_quant_table error\n");
 913             return -1;
 914         }
 915     }
 916     context_count= (context_count+1)/2;
 917
 918     for(i=0; i<f->plane_count; i++){
 919         PlaneContext * const p= &f->plane[i];
 920
 921         p->context_count= context_count;
 922
 923         if(f->ac){
 924             if(!p->state) p->state= av_malloc(CONTEXT_SIZE*p->context_count*sizeof(uint8_t));
 925         }else{
 926             if(!p->vlc_state) p->vlc_state= av_malloc(p->context_count*sizeof(VlcState));
 927         }
 928     }
 929
 930     return 0;
 931 }
 932
 933 static av_cold int decode_init(AVCodecContext *avctx)
 934 {
 935 //    FFV1Context *s = avctx->priv_data;
 936
 937     common_init(avctx);
 938
 939     return 0;
 940 }
 941
 942 static int decode_frame(AVCodecContext *avctx, void *data, int *data_size, const uint8_t *buf, int buf_size){
 943     FFV1Context *f = avctx->priv_data;
 944     RangeCoder * const c= &f->c;
 945     const int width= f->width;
 946     const int height= f->height;
 947     AVFrame * const p= &f->picture;
 948     int bytes_read;
 949     uint8_t keystate= 128;
 950
 951     AVFrame *picture = data;
 952
 953     ff_init_range_decoder(c, buf, buf_size);
 954     ff_build_rac_states(c, 0.05*(1LL<<32), 256-8);
 955
 956
 957     p->pict_type= FF_I_TYPE; //FIXME I vs. P
 958     if(get_rac(c, &keystate)){
 959         p->key_frame= 1;
 960         if(read_header(f) < 0)
 961             return -1;
 962         clear_state(f);
 963     }else{
 964         p->key_frame= 0;
 965     }
 966     if(!f->plane[0].state && !f->plane[0].vlc_state)
 967         return -1;
 968
 969     p->reference= 0;
 970     if(avctx->get_buffer(avctx, p) < 0){
 971         av_log(avctx, AV_LOG_ERROR, "get_buffer() failed\n");
 972         return -1;
 973     }
 974
 975     if(avctx->debug&FF_DEBUG_PICT_INFO)
 976         av_log(avctx, AV_LOG_ERROR, "keyframe:%d coder:%d\n", p->key_frame, f->ac);
 977
 978     if(!f->ac){
 979         bytes_read = c->bytestream - c->bytestream_start - 1;
 980         if(bytes_read ==0) av_log(avctx, AV_LOG_ERROR, "error at end of AC stream\n"); //FIXME
 981 //printf("pos=%d\n", bytes_read);
 982         init_get_bits(&f->gb, buf + bytes_read, buf_size - bytes_read);
 983     } else {
 984         bytes_read = 0; /* avoid warning */
 985     }
 986
 987     if(f->colorspace==0){
 988         const int chroma_width = -((-width )>>f->chroma_h_shift);
 989         const int chroma_height= -((-height)>>f->chroma_v_shift);
 990         decode_plane(f, p->data[0], width, height, p->linesize[0], 0);
 991
 992         decode_plane(f, p->data[1], chroma_width, chroma_height, p->linesize[1], 1);
 993         decode_plane(f, p->data[2], chroma_width, chroma_height, p->linesize[2], 1);
 994     }else{
 995         decode_rgb_frame(f, (uint32_t*)p->data[0], width, height, p->linesize[0]/4);
 996     }
 997
 998     emms_c();
 999
1000     f->picture_number++;
1001
1002     *picture= *p;
1003
1004     avctx->release_buffer(avctx, p); //FIXME
1005
1006     *data_size = sizeof(AVFrame);
1007
1008     if(f->ac){
1009         bytes_read= c->bytestream - c->bytestream_start - 1;
1010         if(bytes_read ==0) av_log(f->avctx, AV_LOG_ERROR, "error at end of frame\n");
1011     }else{
1012         bytes_read+= (get_bits_count(&f->gb)+7)/8;
1013     }
1014
1015     return bytes_read;
1016 }
1017
1018 AVCodec ffv1_decoder = {
1019     "ffv1",
1020     CODEC_TYPE_VIDEO,
1021     CODEC_ID_FFV1,
1022     sizeof(FFV1Context),
1023     decode_init,
1024     NULL,
1025     common_end,
1026     decode_frame,
1027     CODEC_CAP_DR1 /*| CODEC_CAP_DRAW_HORIZ_BAND*/,
1028     NULL,
1029     .long_name= NULL_IF_CONFIG_SMALL("FFmpeg codec #1"),
1030 };
1031
1032 #ifdef CONFIG_ENCODERS
1033 AVCodec ffv1_encoder = {
1034     "ffv1",
1035     CODEC_TYPE_VIDEO,
1036     CODEC_ID_FFV1,
1037     sizeof(FFV1Context),
1038     encode_init,
1039     encode_frame,
1040     common_end,
1041     .pix_fmts= (enum PixelFormat[]){PIX_FMT_YUV420P, PIX_FMT_YUV444P, PIX_FMT_YUV422P, PIX_FMT_YUV411P, PIX_FMT_YUV410P, PIX_FMT_RGB32, PIX_FMT_NONE},
1042     .long_name= NULL_IF_CONFIG_SMALL("FFmpeg codec #1"),
1043 };
1044 #endif