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