git.sesse.net Git - ffmpeg/blob - libavcodec/ffv1.c

   1 /*
   2  * FFV1 codec for libavcodec
   3  *
   4  * Copyright (c) 2003 Michael Niedermayer <michaelni@gmx.at>
   5  *
   6  * This 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
  25  * FF Video Codec 1 (a lossless codec)
  26  */
  27
  28 #include "avcodec.h"
  29 #include "internal.h"
  30 #include "get_bits.h"
  31 #include "put_bits.h"
  32 #include "dsputil.h"
  33 #include "rangecoder.h"
  34 #include "golomb.h"
  35 #include "mathops.h"
  36 #include "libavutil/pixdesc.h"
  37 #include "libavutil/avassert.h"
  38 #include "libavutil/crc.h"
  39 #include "libavutil/opt.h"
  40
  41 #ifdef __INTEL_COMPILER
  42 #undef av_flatten
  43 #define av_flatten
  44 #endif
  45
  46 #define MAX_PLANES 4
  47 #define CONTEXT_SIZE 32
  48
  49 #define MAX_QUANT_TABLES 8
  50 #define MAX_CONTEXT_INPUTS 5
  51
  52 extern const uint8_t ff_log2_run[41];
  53
  54 static const int8_t quant5_10bit[256]={
  55  0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 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, 1,
  58  1, 1, 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,-1,
  68 -1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,
  69 -1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,
  70 -1,-1,-1,-1,-1,-1,-0,-0,-0,-0,-0,-0,-0,-0,-0,-0,
  71 };
  72
  73 static const int8_t quant5[256]={
  74  0, 1, 1, 1, 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, 2, 2, 2, 2, 2, 2, 2, 2,
  77  2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2,
  78  2, 2, 2, 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, 2, 2, 2, 2, 2, 2, 2, 2,
  81  2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2,
  82 -2,-2,-2,-2,-2,-2,-2,-2,-2,-2,-2,-2,-2,-2,-2,-2,
  83 -2,-2,-2,-2,-2,-2,-2,-2,-2,-2,-2,-2,-2,-2,-2,-2,
  84 -2,-2,-2,-2,-2,-2,-2,-2,-2,-2,-2,-2,-2,-2,-2,-2,
  85 -2,-2,-2,-2,-2,-2,-2,-2,-2,-2,-2,-2,-2,-2,-2,-2,
  86 -2,-2,-2,-2,-2,-2,-2,-2,-2,-2,-2,-2,-2,-2,-2,-2,
  87 -2,-2,-2,-2,-2,-2,-2,-2,-2,-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,-1,-1,-1,
  90 };
  91
  92 static const int8_t quant9_10bit[256]={
  93  0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 2, 2, 2,
  94  2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 3, 3, 3, 3, 3,
  95  3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3,
  96  3, 3, 3, 3, 3, 3, 3, 3, 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,-3,-3,-3,-3,-3,-3,-3,
 106 -3,-3,-3,-3,-3,-3,-3,-3,-3,-3,-3,-3,-3,-3,-3,-3,
 107 -3,-3,-3,-3,-3,-3,-2,-2,-2,-2,-2,-2,-2,-2,-2,-2,
 108 -2,-2,-2,-2,-1,-1,-1,-1,-1,-1,-1,-1,-0,-0,-0,-0,
 109 };
 110
 111 static const int8_t quant11[256]={
 112  0, 1, 2, 2, 2, 3, 3, 3, 3, 3, 3, 3, 4, 4, 4, 4,
 113  4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4,
 114  4, 4, 4, 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,-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,-4,-4,
 126 -4,-4,-4,-4,-4,-4,-4,-4,-4,-4,-4,-4,-4,-4,-4,-4,
 127 -4,-4,-4,-4,-4,-3,-3,-3,-3,-3,-3,-3,-2,-2,-2,-1,
 128 };
 129
 130 static const uint8_t ver2_state[256]= {
 131    0,  10,  10,  10,  10,  16,  16,  16,  28,  16,  16,  29,  42,  49,  20,  49,
 132   59,  25,  26,  26,  27,  31,  33,  33,  33,  34,  34,  37,  67,  38,  39,  39,
 133   40,  40,  41,  79,  43,  44,  45,  45,  48,  48,  64,  50,  51,  52,  88,  52,
 134   53,  74,  55,  57,  58,  58,  74,  60, 101,  61,  62,  84,  66,  66,  68,  69,
 135   87,  82,  71,  97,  73,  73,  82,  75, 111,  77,  94,  78,  87,  81,  83,  97,
 136   85,  83,  94,  86,  99,  89,  90,  99, 111,  92,  93, 134,  95,  98, 105,  98,
 137  105, 110, 102, 108, 102, 118, 103, 106, 106, 113, 109, 112, 114, 112, 116, 125,
 138  115, 116, 117, 117, 126, 119, 125, 121, 121, 123, 145, 124, 126, 131, 127, 129,
 139  165, 130, 132, 138, 133, 135, 145, 136, 137, 139, 146, 141, 143, 142, 144, 148,
 140  147, 155, 151, 149, 151, 150, 152, 157, 153, 154, 156, 168, 158, 162, 161, 160,
 141  172, 163, 169, 164, 166, 184, 167, 170, 177, 174, 171, 173, 182, 176, 180, 178,
 142  175, 189, 179, 181, 186, 183, 192, 185, 200, 187, 191, 188, 190, 197, 193, 196,
 143  197, 194, 195, 196, 198, 202, 199, 201, 210, 203, 207, 204, 205, 206, 208, 214,
 144  209, 211, 221, 212, 213, 215, 224, 216, 217, 218, 219, 220, 222, 228, 223, 225,
 145  226, 224, 227, 229, 240, 230, 231, 232, 233, 234, 235, 236, 238, 239, 237, 242,
 146  241, 243, 242, 244, 245, 246, 247, 248, 249, 250, 251, 252, 252, 253, 254, 255,
 147 };
 148
 149 typedef struct VlcState{
 150     int16_t drift;
 151     uint16_t error_sum;
 152     int8_t bias;
 153     uint8_t count;
 154 } VlcState;
 155
 156 typedef struct PlaneContext{
 157     int16_t quant_table[MAX_CONTEXT_INPUTS][256];
 158     int quant_table_index;
 159     int context_count;
 160     uint8_t (*state)[CONTEXT_SIZE];
 161     VlcState *vlc_state;
 162     uint8_t interlace_bit_state[2];
 163 } PlaneContext;
 164
 165 #define MAX_SLICES 256
 166
 167 typedef struct FFV1Context{
 168     AVClass *class;
 169     AVCodecContext *avctx;
 170     RangeCoder c;
 171     GetBitContext gb;
 172     PutBitContext pb;
 173     uint64_t rc_stat[256][2];
 174     uint64_t (*rc_stat2[MAX_QUANT_TABLES])[32][2];
 175     int version;
 176     int minor_version;
 177     int width, height;
 178     int chroma_h_shift, chroma_v_shift;
 179     int chroma_planes;
 180     int transparency;
 181     int flags;
 182     int picture_number;
 183     AVFrame picture;
 184     int plane_count;
 185     int ac;                              ///< 1=range coder <-> 0=golomb rice
 186     int ac_byte_count;                   ///< number of bytes used for AC coding
 187     PlaneContext plane[MAX_PLANES];
 188     int16_t quant_table[MAX_CONTEXT_INPUTS][256];
 189     int16_t quant_tables[MAX_QUANT_TABLES][MAX_CONTEXT_INPUTS][256];
 190     int context_count[MAX_QUANT_TABLES];
 191     uint8_t state_transition[256];
 192     uint8_t (*initial_states[MAX_QUANT_TABLES])[32];
 193     int run_index;
 194     int colorspace;
 195     int16_t *sample_buffer;
 196     int gob_count;
 197     int packed_at_lsb;
 198     int ec;
 199     int key_frame_ok;
 200
 201     int quant_table_count;
 202
 203     DSPContext dsp;
 204
 205     struct FFV1Context *slice_context[MAX_SLICES];
 206     int slice_count;
 207     int num_v_slices;
 208     int num_h_slices;
 209     int slice_width;
 210     int slice_height;
 211     int slice_x;
 212     int slice_y;
 213     int bits_per_raw_sample;
 214 }FFV1Context;
 215
 216 static av_always_inline int fold(int diff, int bits){
 217     if(bits==8)
 218         diff= (int8_t)diff;
 219     else{
 220         diff+= 1<<(bits-1);
 221         diff&=(1<<bits)-1;
 222         diff-= 1<<(bits-1);
 223     }
 224
 225     return diff;
 226 }
 227
 228 static inline int predict(int16_t *src, int16_t *last)
 229 {
 230     const int LT= last[-1];
 231     const int  T= last[ 0];
 232     const int L =  src[-1];
 233
 234     return mid_pred(L, L + T - LT, T);
 235 }
 236
 237 static inline int get_context(PlaneContext *p, int16_t *src,
 238                               int16_t *last, int16_t *last2)
 239 {
 240     const int LT= last[-1];
 241     const int  T= last[ 0];
 242     const int RT= last[ 1];
 243     const int L =  src[-1];
 244
 245     if(p->quant_table[3][127]){
 246         const int TT= last2[0];
 247         const int LL=  src[-2];
 248         return p->quant_table[0][(L-LT) & 0xFF] + p->quant_table[1][(LT-T) & 0xFF] + p->quant_table[2][(T-RT) & 0xFF]
 249               +p->quant_table[3][(LL-L) & 0xFF] + p->quant_table[4][(TT-T) & 0xFF];
 250     }else
 251         return p->quant_table[0][(L-LT) & 0xFF] + p->quant_table[1][(LT-T) & 0xFF] + p->quant_table[2][(T-RT) & 0xFF];
 252 }
 253
 254 static void find_best_state(uint8_t best_state[256][256], const uint8_t one_state[256]){
 255     int i,j,k,m;
 256     double l2tab[256];
 257
 258     for(i=1; i<256; i++)
 259         l2tab[i]= log2(i/256.0);
 260
 261     for(i=0; i<256; i++){
 262         double best_len[256];
 263         double p= i/256.0;
 264
 265         for(j=0; j<256; j++)
 266             best_len[j]= 1<<30;
 267
 268         for(j=FFMAX(i-10,1); j<FFMIN(i+11,256); j++){
 269             double occ[256]={0};
 270             double len=0;
 271             occ[j]=1.0;
 272             for(k=0; k<256; k++){
 273                 double newocc[256]={0};
 274                 for(m=0; m<256; m++){
 275                     if(occ[m]){
 276                         len -=occ[m]*(     p *l2tab[    m]
 277                                       + (1-p)*l2tab[256-m]);
 278                     }
 279                 }
 280                 if(len < best_len[k]){
 281                     best_len[k]= len;
 282                     best_state[i][k]= j;
 283                 }
 284                 for(m=0; m<256; m++){
 285                     if(occ[m]){
 286                         newocc[    one_state[    m]] += occ[m]*   p ;
 287                         newocc[256-one_state[256-m]] += occ[m]*(1-p);
 288                     }
 289                 }
 290                 memcpy(occ, newocc, sizeof(occ));
 291             }
 292         }
 293     }
 294 }
 295
 296 static av_always_inline av_flatten void put_symbol_inline(RangeCoder *c, uint8_t *state, int v, int is_signed, uint64_t rc_stat[256][2], uint64_t rc_stat2[32][2]){
 297     int i;
 298
 299 #define put_rac(C,S,B) \
 300 do{\
 301     if(rc_stat){\
 302     rc_stat[*(S)][B]++;\
 303         rc_stat2[(S)-state][B]++;\
 304     }\
 305     put_rac(C,S,B);\
 306 }while(0)
 307
 308     if(v){
 309         const int a= FFABS(v);
 310         const int e= av_log2(a);
 311         put_rac(c, state+0, 0);
 312         if(e<=9){
 313             for(i=0; i<e; i++){
 314                 put_rac(c, state+1+i, 1);  //1..10
 315             }
 316             put_rac(c, state+1+i, 0);
 317
 318             for(i=e-1; i>=0; i--){
 319                 put_rac(c, state+22+i, (a>>i)&1); //22..31
 320             }
 321
 322             if(is_signed)
 323                 put_rac(c, state+11 + e, v < 0); //11..21
 324         }else{
 325             for(i=0; i<e; i++){
 326                 put_rac(c, state+1+FFMIN(i,9), 1);  //1..10
 327             }
 328             put_rac(c, state+1+9, 0);
 329
 330             for(i=e-1; i>=0; i--){
 331                 put_rac(c, state+22+FFMIN(i,9), (a>>i)&1); //22..31
 332             }
 333
 334             if(is_signed)
 335                 put_rac(c, state+11 + 10, v < 0); //11..21
 336         }
 337     }else{
 338         put_rac(c, state+0, 1);
 339     }
 340 #undef put_rac
 341 }
 342
 343 static av_noinline void put_symbol(RangeCoder *c, uint8_t *state, int v, int is_signed){
 344     put_symbol_inline(c, state, v, is_signed, NULL, NULL);
 345 }
 346
 347 static inline av_flatten int get_symbol_inline(RangeCoder *c, uint8_t *state, int is_signed){
 348     if(get_rac(c, state+0))
 349         return 0;
 350     else{
 351         int i, e, a;
 352         e= 0;
 353         while(get_rac(c, state+1 + FFMIN(e,9))){ //1..10
 354             e++;
 355         }
 356
 357         a= 1;
 358         for(i=e-1; i>=0; i--){
 359             a += a + get_rac(c, state+22 + FFMIN(i,9)); //22..31
 360         }
 361
 362         e= -(is_signed && get_rac(c, state+11 + FFMIN(e, 10))); //11..21
 363         return (a^e)-e;
 364     }
 365 }
 366
 367 static av_noinline int get_symbol(RangeCoder *c, uint8_t *state, int is_signed){
 368     return get_symbol_inline(c, state, is_signed);
 369 }
 370
 371 static inline void update_vlc_state(VlcState * const state, const int v){
 372     int drift= state->drift;
 373     int count= state->count;
 374     state->error_sum += FFABS(v);
 375     drift += v;
 376
 377     if(count == 128){ //FIXME variable
 378         count >>= 1;
 379         drift >>= 1;
 380         state->error_sum >>= 1;
 381     }
 382     count++;
 383
 384     if(drift <= -count){
 385         if(state->bias > -128) state->bias--;
 386
 387         drift += count;
 388         if(drift <= -count)
 389             drift= -count + 1;
 390     }else if(drift > 0){
 391         if(state->bias <  127) state->bias++;
 392
 393         drift -= count;
 394         if(drift > 0)
 395             drift= 0;
 396     }
 397
 398     state->drift= drift;
 399     state->count= count;
 400 }
 401
 402 static inline void put_vlc_symbol(PutBitContext *pb, VlcState * const state, int v, int bits){
 403     int i, k, code;
 404 //printf("final: %d ", v);
 405     v = fold(v - state->bias, bits);
 406
 407     i= state->count;
 408     k=0;
 409     while(i < state->error_sum){ //FIXME optimize
 410         k++;
 411         i += i;
 412     }
 413
 414     assert(k<=8);
 415
 416 #if 0 // JPEG LS
 417     if(k==0 && 2*state->drift <= - state->count) code= v ^ (-1);
 418     else                                         code= v;
 419 #else
 420      code= v ^ ((2*state->drift + state->count)>>31);
 421 #endif
 422
 423 //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);
 424     set_sr_golomb(pb, code, k, 12, bits);
 425
 426     update_vlc_state(state, v);
 427 }
 428
 429 static inline int get_vlc_symbol(GetBitContext *gb, VlcState * const state, int bits){
 430     int k, i, v, ret;
 431
 432     i= state->count;
 433     k=0;
 434     while(i < state->error_sum){ //FIXME optimize
 435         k++;
 436         i += i;
 437     }
 438
 439     assert(k<=8);
 440
 441     v= get_sr_golomb(gb, k, 12, bits);
 442 //printf("v:%d bias:%d error:%d drift:%d count:%d k:%d", v, state->bias, state->error_sum, state->drift, state->count, k);
 443
 444 #if 0 // JPEG LS
 445     if(k==0 && 2*state->drift <= - state->count) v ^= (-1);
 446 #else
 447      v ^= ((2*state->drift + state->count)>>31);
 448 #endif
 449
 450     ret= fold(v + state->bias, bits);
 451
 452     update_vlc_state(state, v);
 453 //printf("final: %d\n", ret);
 454     return ret;
 455 }
 456
 457 #if CONFIG_FFV1_ENCODER
 458 static av_always_inline int encode_line(FFV1Context *s, int w,
 459                                         int16_t *sample[3],
 460                                         int plane_index, int bits)
 461 {
 462     PlaneContext * const p= &s->plane[plane_index];
 463     RangeCoder * const c= &s->c;
 464     int x;
 465     int run_index= s->run_index;
 466     int run_count=0;
 467     int run_mode=0;
 468
 469     if(s->ac){
 470         if(c->bytestream_end - c->bytestream < w*20){
 471             av_log(s->avctx, AV_LOG_ERROR, "encoded frame too large\n");
 472             return -1;
 473         }
 474     }else{
 475         if(s->pb.buf_end - s->pb.buf - (put_bits_count(&s->pb)>>3) < w*4){
 476             av_log(s->avctx, AV_LOG_ERROR, "encoded frame too large\n");
 477             return -1;
 478         }
 479     }
 480
 481     for(x=0; x<w; x++){
 482         int diff, context;
 483
 484         context= get_context(p, sample[0]+x, sample[1]+x, sample[2]+x);
 485         diff= sample[0][x] - predict(sample[0]+x, sample[1]+x);
 486
 487         if(context < 0){
 488             context = -context;
 489             diff= -diff;
 490         }
 491
 492         diff= fold(diff, bits);
 493
 494         if(s->ac){
 495             if(s->flags & CODEC_FLAG_PASS1){
 496                 put_symbol_inline(c, p->state[context], diff, 1, s->rc_stat, s->rc_stat2[p->quant_table_index][context]);
 497             }else{
 498                 put_symbol_inline(c, p->state[context], diff, 1, NULL, NULL);
 499             }
 500         }else{
 501             if(context == 0) run_mode=1;
 502
 503             if(run_mode){
 504
 505                 if(diff){
 506                     while(run_count >= 1<<ff_log2_run[run_index]){
 507                         run_count -= 1<<ff_log2_run[run_index];
 508                         run_index++;
 509                         put_bits(&s->pb, 1, 1);
 510                     }
 511
 512                     put_bits(&s->pb, 1 + ff_log2_run[run_index], run_count);
 513                     if(run_index) run_index--;
 514                     run_count=0;
 515                     run_mode=0;
 516                     if(diff>0) diff--;
 517                 }else{
 518                     run_count++;
 519                 }
 520             }
 521
 522 //            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));
 523
 524             if(run_mode == 0)
 525                 put_vlc_symbol(&s->pb, &p->vlc_state[context], diff, bits);
 526         }
 527     }
 528     if(run_mode){
 529         while(run_count >= 1<<ff_log2_run[run_index]){
 530             run_count -= 1<<ff_log2_run[run_index];
 531             run_index++;
 532             put_bits(&s->pb, 1, 1);
 533         }
 534
 535         if(run_count)
 536             put_bits(&s->pb, 1, 1);
 537     }
 538     s->run_index= run_index;
 539
 540     return 0;
 541 }
 542
 543 static void encode_plane(FFV1Context *s, uint8_t *src, int w, int h, int stride, int plane_index){
 544     int x,y,i;
 545     const int ring_size= s->avctx->context_model ? 3 : 2;
 546     int16_t *sample[3];
 547     s->run_index=0;
 548
 549     memset(s->sample_buffer, 0, ring_size*(w+6)*sizeof(*s->sample_buffer));
 550
 551     for(y=0; y<h; y++){
 552         for(i=0; i<ring_size; i++)
 553             sample[i]= s->sample_buffer + (w+6)*((h+i-y)%ring_size) + 3;
 554
 555         sample[0][-1]= sample[1][0  ];
 556         sample[1][ w]= sample[1][w-1];
 557 //{START_TIMER
 558         if(s->bits_per_raw_sample<=8){
 559             for(x=0; x<w; x++){
 560                 sample[0][x]= src[x + stride*y];
 561             }
 562             encode_line(s, w, sample, plane_index, 8);
 563         }else{
 564             if(s->packed_at_lsb){
 565                 for(x=0; x<w; x++){
 566                     sample[0][x]= ((uint16_t*)(src + stride*y))[x];
 567                 }
 568             }else{
 569                 for(x=0; x<w; x++){
 570                     sample[0][x]= ((uint16_t*)(src + stride*y))[x] >> (16 - s->bits_per_raw_sample);
 571                 }
 572             }
 573             encode_line(s, w, sample, plane_index, s->bits_per_raw_sample);
 574         }
 575 //STOP_TIMER("encode line")}
 576     }
 577 }
 578
 579 static void encode_rgb_frame(FFV1Context *s, uint32_t *src, int w, int h, int stride){
 580     int x, y, p, i;
 581     const int ring_size= s->avctx->context_model ? 3 : 2;
 582     int16_t *sample[4][3];
 583     s->run_index=0;
 584
 585     memset(s->sample_buffer, 0, ring_size*4*(w+6)*sizeof(*s->sample_buffer));
 586
 587     for(y=0; y<h; y++){
 588         for(i=0; i<ring_size; i++)
 589             for(p=0; p<4; p++)
 590                 sample[p][i]= s->sample_buffer + p*ring_size*(w+6) + ((h+i-y)%ring_size)*(w+6) + 3;
 591
 592         for(x=0; x<w; x++){
 593             unsigned v= src[x + stride*y];
 594             int b= v&0xFF;
 595             int g= (v>>8)&0xFF;
 596             int r= (v>>16)&0xFF;
 597             int a=  v>>24;
 598
 599             b -= g;
 600             r -= g;
 601             g += (b + r)>>2;
 602             b += 0x100;
 603             r += 0x100;
 604
 605 //            assert(g>=0 && b>=0 && r>=0);
 606 //            assert(g<256 && b<512 && r<512);
 607             sample[0][0][x]= g;
 608             sample[1][0][x]= b;
 609             sample[2][0][x]= r;
 610             sample[3][0][x]= a;
 611         }
 612         for(p=0; p<3 + s->transparency; p++){
 613             sample[p][0][-1]= sample[p][1][0  ];
 614             sample[p][1][ w]= sample[p][1][w-1];
 615             encode_line(s, w, sample[p], (p+1)/2, 9);
 616         }
 617     }
 618 }
 619
 620 static void write_quant_table(RangeCoder *c, int16_t *quant_table){
 621     int last=0;
 622     int i;
 623     uint8_t state[CONTEXT_SIZE];
 624     memset(state, 128, sizeof(state));
 625
 626     for(i=1; i<128 ; i++){
 627         if(quant_table[i] != quant_table[i-1]){
 628             put_symbol(c, state, i-last-1, 0);
 629             last= i;
 630         }
 631     }
 632     put_symbol(c, state, i-last-1, 0);
 633 }
 634
 635 static void write_quant_tables(RangeCoder *c, int16_t quant_table[MAX_CONTEXT_INPUTS][256]){
 636     int i;
 637     for(i=0; i<5; i++)
 638         write_quant_table(c, quant_table[i]);
 639 }
 640
 641 static void write_header(FFV1Context *f){
 642     uint8_t state[CONTEXT_SIZE];
 643     int i, j;
 644     RangeCoder * const c= &f->slice_context[0]->c;
 645
 646     memset(state, 128, sizeof(state));
 647
 648     if(f->version < 2){
 649         put_symbol(c, state, f->version, 0);
 650         put_symbol(c, state, f->ac, 0);
 651         if(f->ac>1){
 652             for(i=1; i<256; i++){
 653                 put_symbol(c, state, f->state_transition[i] - c->one_state[i], 1);
 654             }
 655         }
 656         put_symbol(c, state, f->colorspace, 0); //YUV cs type
 657         if(f->version>0)
 658             put_symbol(c, state, f->bits_per_raw_sample, 0);
 659         put_rac(c, state, f->chroma_planes);
 660         put_symbol(c, state, f->chroma_h_shift, 0);
 661         put_symbol(c, state, f->chroma_v_shift, 0);
 662         put_rac(c, state, f->transparency);
 663
 664         write_quant_tables(c, f->quant_table);
 665     }else if(f->version < 3){
 666         put_symbol(c, state, f->slice_count, 0);
 667         for(i=0; i<f->slice_count; i++){
 668             FFV1Context *fs= f->slice_context[i];
 669             put_symbol(c, state, (fs->slice_x     +1)*f->num_h_slices / f->width   , 0);
 670             put_symbol(c, state, (fs->slice_y     +1)*f->num_v_slices / f->height  , 0);
 671             put_symbol(c, state, (fs->slice_width +1)*f->num_h_slices / f->width -1, 0);
 672             put_symbol(c, state, (fs->slice_height+1)*f->num_v_slices / f->height-1, 0);
 673             for(j=0; j<f->plane_count; j++){
 674                 put_symbol(c, state, f->plane[j].quant_table_index, 0);
 675                 av_assert0(f->plane[j].quant_table_index == f->avctx->context_model);
 676             }
 677         }
 678     }
 679 }
 680 #endif /* CONFIG_FFV1_ENCODER */
 681
 682 static av_cold int common_init(AVCodecContext *avctx){
 683     FFV1Context *s = avctx->priv_data;
 684
 685     s->avctx= avctx;
 686     s->flags= avctx->flags;
 687
 688     avcodec_get_frame_defaults(&s->picture);
 689
 690     ff_dsputil_init(&s->dsp, avctx);
 691
 692     s->width = avctx->width;
 693     s->height= avctx->height;
 694
 695     assert(s->width && s->height);
 696     //defaults
 697     s->num_h_slices=1;
 698     s->num_v_slices=1;
 699
 700
 701     return 0;
 702 }
 703
 704 static int init_slice_state(FFV1Context *f, FFV1Context *fs){
 705     int j;
 706
 707         fs->plane_count= f->plane_count;
 708         fs->transparency= f->transparency;
 709         for(j=0; j<f->plane_count; j++){
 710             PlaneContext * const p= &fs->plane[j];
 711
 712             if(fs->ac){
 713                 if(!p->    state) p->    state= av_malloc(CONTEXT_SIZE*p->context_count*sizeof(uint8_t));
 714                 if(!p->    state)
 715                     return AVERROR(ENOMEM);
 716             }else{
 717                 if(!p->vlc_state) p->vlc_state= av_malloc(p->context_count*sizeof(VlcState));
 718                 if(!p->vlc_state)
 719                     return AVERROR(ENOMEM);
 720             }
 721         }
 722
 723         if (fs->ac>1){
 724             //FIXME only redo if state_transition changed
 725             for(j=1; j<256; j++){
 726                 fs->c.one_state [    j]= f->state_transition[j];
 727                 fs->c.zero_state[256-j]= 256-fs->c.one_state [j];
 728             }
 729         }
 730
 731     return 0;
 732 }
 733
 734 static int init_slices_state(FFV1Context *f){
 735     int i;
 736     for(i=0; i<f->slice_count; i++){
 737         FFV1Context *fs= f->slice_context[i];
 738         if(init_slice_state(f, fs) < 0)
 739             return -1;
 740     }
 741     return 0;
 742 }
 743
 744 static av_cold int init_slice_contexts(FFV1Context *f){
 745     int i;
 746
 747     f->slice_count= f->num_h_slices * f->num_v_slices;
 748
 749     for(i=0; i<f->slice_count; i++){
 750         FFV1Context *fs= av_mallocz(sizeof(*fs));
 751         int sx= i % f->num_h_slices;
 752         int sy= i / f->num_h_slices;
 753         int sxs= f->avctx->width * sx    / f->num_h_slices;
 754         int sxe= f->avctx->width *(sx+1) / f->num_h_slices;
 755         int sys= f->avctx->height* sy    / f->num_v_slices;
 756         int sye= f->avctx->height*(sy+1) / f->num_v_slices;
 757         f->slice_context[i]= fs;
 758         memcpy(fs, f, sizeof(*fs));
 759         memset(fs->rc_stat2, 0, sizeof(fs->rc_stat2));
 760
 761         fs->slice_width = sxe - sxs;
 762         fs->slice_height= sye - sys;
 763         fs->slice_x     = sxs;
 764         fs->slice_y     = sys;
 765
 766         fs->sample_buffer = av_malloc(3*4 * (fs->width+6) * sizeof(*fs->sample_buffer));
 767         if (!fs->sample_buffer)
 768             return AVERROR(ENOMEM);
 769     }
 770     return 0;
 771 }
 772
 773 static int allocate_initial_states(FFV1Context *f){
 774     int i;
 775
 776     for(i=0; i<f->quant_table_count; i++){
 777         f->initial_states[i]= av_malloc(f->context_count[i]*sizeof(*f->initial_states[i]));
 778         if(!f->initial_states[i])
 779             return AVERROR(ENOMEM);
 780         memset(f->initial_states[i], 128, f->context_count[i]*sizeof(*f->initial_states[i]));
 781     }
 782     return 0;
 783 }
 784
 785 #if CONFIG_FFV1_ENCODER
 786 static int write_extra_header(FFV1Context *f){
 787     RangeCoder * const c= &f->c;
 788     uint8_t state[CONTEXT_SIZE];
 789     int i, j, k;
 790     uint8_t state2[32][CONTEXT_SIZE];
 791     unsigned v;
 792
 793     memset(state2, 128, sizeof(state2));
 794     memset(state, 128, sizeof(state));
 795
 796     f->avctx->extradata= av_malloc(f->avctx->extradata_size= 10000 + (11*11*5*5*5+11*11*11)*32);
 797     ff_init_range_encoder(c, f->avctx->extradata, f->avctx->extradata_size);
 798     ff_build_rac_states(c, 0.05*(1LL<<32), 256-8);
 799
 800     put_symbol(c, state, f->version, 0);
 801     if(f->version > 2)
 802         put_symbol(c, state, f->minor_version, 0);
 803     put_symbol(c, state, f->ac, 0);
 804     if(f->ac>1){
 805         for(i=1; i<256; i++){
 806             put_symbol(c, state, f->state_transition[i] - c->one_state[i], 1);
 807         }
 808     }
 809     put_symbol(c, state, f->colorspace, 0); //YUV cs type
 810     put_symbol(c, state, f->bits_per_raw_sample, 0);
 811     put_rac(c, state, f->chroma_planes);
 812     put_symbol(c, state, f->chroma_h_shift, 0);
 813     put_symbol(c, state, f->chroma_v_shift, 0);
 814     put_rac(c, state, f->transparency);
 815     put_symbol(c, state, f->num_h_slices-1, 0);
 816     put_symbol(c, state, f->num_v_slices-1, 0);
 817
 818     put_symbol(c, state, f->quant_table_count, 0);
 819     for(i=0; i<f->quant_table_count; i++)
 820         write_quant_tables(c, f->quant_tables[i]);
 821
 822     for(i=0; i<f->quant_table_count; i++){
 823         for(j=0; j<f->context_count[i]*CONTEXT_SIZE; j++)
 824             if(f->initial_states[i] && f->initial_states[i][0][j] != 128)
 825                 break;
 826         if(j<f->context_count[i]*CONTEXT_SIZE){
 827             put_rac(c, state, 1);
 828             for(j=0; j<f->context_count[i]; j++){
 829                 for(k=0; k<CONTEXT_SIZE; k++){
 830                     int pred= j ? f->initial_states[i][j-1][k] : 128;
 831                     put_symbol(c, state2[k], (int8_t)(f->initial_states[i][j][k]-pred), 1);
 832                 }
 833             }
 834         }else{
 835             put_rac(c, state, 0);
 836         }
 837     }
 838
 839     if(f->version > 2){
 840         put_symbol(c, state, f->ec, 0);
 841     }
 842
 843     f->avctx->extradata_size= ff_rac_terminate(c);
 844     v = av_crc(av_crc_get_table(AV_CRC_32_IEEE), 0, f->avctx->extradata, f->avctx->extradata_size);
 845     AV_WL32(f->avctx->extradata + f->avctx->extradata_size, v);
 846     f->avctx->extradata_size += 4;
 847
 848     return 0;
 849 }
 850
 851 static int sort_stt(FFV1Context *s, uint8_t stt[256]){
 852     int i,i2,changed,print=0;
 853
 854     do{
 855         changed=0;
 856         for(i=12; i<244; i++){
 857             for(i2=i+1; i2<245 && i2<i+4; i2++){
 858 #define COST(old, new) \
 859     s->rc_stat[old][0]*-log2((256-(new))/256.0)\
 860    +s->rc_stat[old][1]*-log2(     (new) /256.0)
 861
 862 #define COST2(old, new) \
 863     COST(old, new)\
 864    +COST(256-(old), 256-(new))
 865
 866                 double size0= COST2(i, i ) + COST2(i2, i2);
 867                 double sizeX= COST2(i, i2) + COST2(i2, i );
 868                 if(sizeX < size0 && i!=128 && i2!=128){
 869                     int j;
 870                     FFSWAP(int, stt[    i], stt[    i2]);
 871                     FFSWAP(int, s->rc_stat[i    ][0],s->rc_stat[    i2][0]);
 872                     FFSWAP(int, s->rc_stat[i    ][1],s->rc_stat[    i2][1]);
 873                     if(i != 256-i2){
 874                         FFSWAP(int, stt[256-i], stt[256-i2]);
 875                         FFSWAP(int, s->rc_stat[256-i][0],s->rc_stat[256-i2][0]);
 876                         FFSWAP(int, s->rc_stat[256-i][1],s->rc_stat[256-i2][1]);
 877                     }
 878                     for(j=1; j<256; j++){
 879                         if     (stt[j] == i ) stt[j] = i2;
 880                         else if(stt[j] == i2) stt[j] = i ;
 881                         if(i != 256-i2){
 882                             if     (stt[256-j] == 256-i ) stt[256-j] = 256-i2;
 883                             else if(stt[256-j] == 256-i2) stt[256-j] = 256-i ;
 884                         }
 885                     }
 886                     print=changed=1;
 887                 }
 888             }
 889         }
 890     }while(changed);
 891     return print;
 892 }
 893
 894 static av_cold int encode_init(AVCodecContext *avctx)
 895 {
 896     FFV1Context *s = avctx->priv_data;
 897     int i, j, k, m;
 898
 899     common_init(avctx);
 900
 901     s->version=0;
 902
 903     if((avctx->flags & (CODEC_FLAG_PASS1|CODEC_FLAG_PASS2)) || avctx->slices>1)
 904         s->version = FFMAX(s->version, 2);
 905
 906     if(avctx->level == 3){
 907         s->version = 3;
 908     }
 909
 910     if(s->ec < 0){
 911         s->ec = (s->version >= 3);
 912     }
 913
 914     if(s->version >= 2 && avctx->strict_std_compliance > FF_COMPLIANCE_EXPERIMENTAL) {
 915         av_log(avctx, AV_LOG_ERROR, "Version 2 needed for requested features but version 2 is experimental and not enabled\n");
 916         return -1;
 917     }
 918
 919     s->ac= avctx->coder_type ? 2:0;
 920
 921     if(s->ac>1)
 922         for(i=1; i<256; i++)
 923             s->state_transition[i]=ver2_state[i];
 924
 925     s->plane_count=3;
 926     switch(avctx->pix_fmt){
 927     case PIX_FMT_YUV444P9:
 928     case PIX_FMT_YUV422P9:
 929     case PIX_FMT_YUV420P9:
 930         if (!avctx->bits_per_raw_sample)
 931             s->bits_per_raw_sample = 9;
 932     case PIX_FMT_YUV444P10:
 933     case PIX_FMT_YUV420P10:
 934     case PIX_FMT_YUV422P10:
 935         s->packed_at_lsb = 1;
 936         if (!avctx->bits_per_raw_sample && !s->bits_per_raw_sample)
 937             s->bits_per_raw_sample = 10;
 938     case PIX_FMT_GRAY16:
 939     case PIX_FMT_YUV444P16:
 940     case PIX_FMT_YUV422P16:
 941     case PIX_FMT_YUV420P16:
 942         if (!avctx->bits_per_raw_sample && !s->bits_per_raw_sample) {
 943             s->bits_per_raw_sample = 16;
 944         } else if (!s->bits_per_raw_sample){
 945             s->bits_per_raw_sample = avctx->bits_per_raw_sample;
 946         }
 947         if(s->bits_per_raw_sample <=8){
 948             av_log(avctx, AV_LOG_ERROR, "bits_per_raw_sample invalid\n");
 949             return -1;
 950         }
 951         if(!s->ac){
 952             av_log(avctx, AV_LOG_ERROR, "bits_per_raw_sample of more than 8 needs -coder 1 currently\n");
 953             return -1;
 954         }
 955         s->version= FFMAX(s->version, 1);
 956     case PIX_FMT_GRAY8:
 957     case PIX_FMT_YUV444P:
 958     case PIX_FMT_YUV440P:
 959     case PIX_FMT_YUV422P:
 960     case PIX_FMT_YUV420P:
 961     case PIX_FMT_YUV411P:
 962     case PIX_FMT_YUV410P:
 963         s->chroma_planes= av_pix_fmt_descriptors[avctx->pix_fmt].nb_components < 3 ? 0 : 1;
 964         s->colorspace= 0;
 965         break;
 966     case PIX_FMT_YUVA444P:
 967     case PIX_FMT_YUVA422P:
 968     case PIX_FMT_YUVA420P:
 969         s->chroma_planes= 1;
 970         s->colorspace= 0;
 971         s->transparency= 1;
 972         break;
 973     case PIX_FMT_RGB32:
 974         s->colorspace= 1;
 975         s->transparency= 1;
 976         break;
 977     case PIX_FMT_0RGB32:
 978         s->colorspace= 1;
 979         break;
 980     default:
 981         av_log(avctx, AV_LOG_ERROR, "format not supported\n");
 982         return -1;
 983     }
 984     if (s->transparency) {
 985         av_log(avctx, AV_LOG_WARNING, "Storing alpha plane, this will require a recent FFV1 decoder to playback!\n");
 986     }
 987     if (avctx->context_model > 1U) {
 988         av_log(avctx, AV_LOG_ERROR, "Invalid context model %d, valid values are 0 and 1\n", avctx->context_model);
 989         return AVERROR(EINVAL);
 990     }
 991
 992     for(i=0; i<256; i++){
 993         s->quant_table_count=2;
 994         if(s->bits_per_raw_sample <=8){
 995             s->quant_tables[0][0][i]=           quant11[i];
 996             s->quant_tables[0][1][i]=        11*quant11[i];
 997             s->quant_tables[0][2][i]=     11*11*quant11[i];
 998             s->quant_tables[1][0][i]=           quant11[i];
 999             s->quant_tables[1][1][i]=        11*quant11[i];
1000             s->quant_tables[1][2][i]=     11*11*quant5 [i];
1001             s->quant_tables[1][3][i]=   5*11*11*quant5 [i];
1002             s->quant_tables[1][4][i]= 5*5*11*11*quant5 [i];
1003         }else{
1004             s->quant_tables[0][0][i]=           quant9_10bit[i];
1005             s->quant_tables[0][1][i]=        11*quant9_10bit[i];
1006             s->quant_tables[0][2][i]=     11*11*quant9_10bit[i];
1007             s->quant_tables[1][0][i]=           quant9_10bit[i];
1008             s->quant_tables[1][1][i]=        11*quant9_10bit[i];
1009             s->quant_tables[1][2][i]=     11*11*quant5_10bit[i];
1010             s->quant_tables[1][3][i]=   5*11*11*quant5_10bit[i];
1011             s->quant_tables[1][4][i]= 5*5*11*11*quant5_10bit[i];
1012         }
1013     }
1014     s->context_count[0]= (11*11*11+1)/2;
1015     s->context_count[1]= (11*11*5*5*5+1)/2;
1016     memcpy(s->quant_table, s->quant_tables[avctx->context_model], sizeof(s->quant_table));
1017
1018     for(i=0; i<s->plane_count; i++){
1019         PlaneContext * const p= &s->plane[i];
1020
1021         memcpy(p->quant_table, s->quant_table, sizeof(p->quant_table));
1022         p->quant_table_index= avctx->context_model;
1023         p->context_count= s->context_count[p->quant_table_index];
1024     }
1025
1026     if(allocate_initial_states(s) < 0)
1027         return AVERROR(ENOMEM);
1028
1029     avctx->coded_frame= &s->picture;
1030     if(!s->transparency)
1031         s->plane_count= 2;
1032     avcodec_get_chroma_sub_sample(avctx->pix_fmt, &s->chroma_h_shift, &s->chroma_v_shift);
1033
1034     s->picture_number=0;
1035
1036     if(avctx->flags & (CODEC_FLAG_PASS1|CODEC_FLAG_PASS2)){
1037         for(i=0; i<s->quant_table_count; i++){
1038             s->rc_stat2[i]= av_mallocz(s->context_count[i]*sizeof(*s->rc_stat2[i]));
1039             if(!s->rc_stat2[i])
1040                 return AVERROR(ENOMEM);
1041         }
1042     }
1043     if(avctx->stats_in){
1044         char *p= avctx->stats_in;
1045         uint8_t best_state[256][256];
1046         int gob_count=0;
1047         char *next;
1048
1049         av_assert0(s->version>=2);
1050
1051         for(;;){
1052             for(j=0; j<256; j++){
1053                 for(i=0; i<2; i++){
1054                     s->rc_stat[j][i]= strtol(p, &next, 0);
1055                     if(next==p){
1056                         av_log(avctx, AV_LOG_ERROR, "2Pass file invalid at %d %d [%s]\n", j,i,p);
1057                         return -1;
1058                     }
1059                     p=next;
1060                 }
1061             }
1062             for(i=0; i<s->quant_table_count; i++){
1063                 for(j=0; j<s->context_count[i]; j++){
1064                     for(k=0; k<32; k++){
1065                         for(m=0; m<2; m++){
1066                             s->rc_stat2[i][j][k][m]= strtol(p, &next, 0);
1067                             if(next==p){
1068                                 av_log(avctx, AV_LOG_ERROR, "2Pass file invalid at %d %d %d %d [%s]\n", i,j,k,m,p);
1069                                 return -1;
1070                             }
1071                             p=next;
1072                         }
1073                     }
1074                 }
1075             }
1076             gob_count= strtol(p, &next, 0);
1077             if(next==p || gob_count <0){
1078                 av_log(avctx, AV_LOG_ERROR, "2Pass file invalid\n");
1079                 return -1;
1080             }
1081             p=next;
1082             while(*p=='\n' || *p==' ') p++;
1083             if(p[0]==0) break;
1084         }
1085         sort_stt(s, s->state_transition);
1086
1087         find_best_state(best_state, s->state_transition);
1088
1089         for(i=0; i<s->quant_table_count; i++){
1090             for(j=0; j<s->context_count[i]; j++){
1091                 for(k=0; k<32; k++){
1092                     double p= 128;
1093                     if(s->rc_stat2[i][j][k][0]+s->rc_stat2[i][j][k][1]){
1094                         p=256.0*s->rc_stat2[i][j][k][1] / (s->rc_stat2[i][j][k][0]+s->rc_stat2[i][j][k][1]);
1095                     }
1096                     s->initial_states[i][j][k]= best_state[av_clip(round(p), 1, 255)][av_clip((s->rc_stat2[i][j][k][0]+s->rc_stat2[i][j][k][1])/gob_count, 0, 255)];
1097                 }
1098             }
1099         }
1100     }
1101
1102     if(s->version>1){
1103         for(s->num_v_slices=2; s->num_v_slices<9; s->num_v_slices++){
1104             for(s->num_h_slices=s->num_v_slices; s->num_h_slices<2*s->num_v_slices; s->num_h_slices++){
1105                 if(avctx->slices == s->num_h_slices * s->num_v_slices && avctx->slices <= 64)
1106                     goto slices_ok;
1107             }
1108         }
1109         av_log(avctx, AV_LOG_ERROR, "Unsupported number %d of slices requested, please specify a supported number with -slices (ex:4,6,9,12,16, ...)\n", avctx->slices);
1110         return -1;
1111         slices_ok:
1112         write_extra_header(s);
1113     }
1114
1115     if(init_slice_contexts(s) < 0)
1116         return -1;
1117     if(init_slices_state(s) < 0)
1118         return -1;
1119
1120 #define STATS_OUT_SIZE 1024*1024*6
1121     if(avctx->flags & CODEC_FLAG_PASS1){
1122         avctx->stats_out= av_mallocz(STATS_OUT_SIZE);
1123         for(i=0; i<s->quant_table_count; i++){
1124             for(j=0; j<s->slice_count; j++){
1125                 FFV1Context *sf= s->slice_context[j];
1126                 av_assert0(!sf->rc_stat2[i]);
1127                 sf->rc_stat2[i]= av_mallocz(s->context_count[i]*sizeof(*sf->rc_stat2[i]));
1128                 if(!sf->rc_stat2[i])
1129                     return AVERROR(ENOMEM);
1130             }
1131         }
1132     }
1133
1134     return 0;
1135 }
1136 #endif /* CONFIG_FFV1_ENCODER */
1137
1138
1139 static void clear_slice_state(FFV1Context *f, FFV1Context *fs){
1140     int i, j;
1141
1142         for(i=0; i<f->plane_count; i++){
1143             PlaneContext *p= &fs->plane[i];
1144
1145             p->interlace_bit_state[0]= 128;
1146             p->interlace_bit_state[1]= 128;
1147
1148             if(fs->ac){
1149                 if(f->initial_states[p->quant_table_index]){
1150                     memcpy(p->state, f->initial_states[p->quant_table_index], CONTEXT_SIZE*p->context_count);
1151                 }else
1152                 memset(p->state, 128, CONTEXT_SIZE*p->context_count);
1153             }else{
1154                 for(j=0; j<p->context_count; j++){
1155                     p->vlc_state[j].drift= 0;
1156                     p->vlc_state[j].error_sum= 4; //FFMAX((RANGE + 32)/64, 2);
1157                     p->vlc_state[j].bias= 0;
1158                     p->vlc_state[j].count= 1;
1159                 }
1160             }
1161         }
1162 }
1163
1164 #if CONFIG_FFV1_ENCODER
1165
1166 static void encode_slice_header(FFV1Context *f, FFV1Context *fs){
1167     RangeCoder *c = &fs->c;
1168     uint8_t state[CONTEXT_SIZE];
1169     int j;
1170     memset(state, 128, sizeof(state));
1171
1172     put_symbol(c, state, (fs->slice_x     +1)*f->num_h_slices / f->width   , 0);
1173     put_symbol(c, state, (fs->slice_y     +1)*f->num_v_slices / f->height  , 0);
1174     put_symbol(c, state, (fs->slice_width +1)*f->num_h_slices / f->width -1, 0);
1175     put_symbol(c, state, (fs->slice_height+1)*f->num_v_slices / f->height-1, 0);
1176     for(j=0; j<f->plane_count; j++){
1177         put_symbol(c, state, f->plane[j].quant_table_index, 0);
1178         av_assert0(f->plane[j].quant_table_index == f->avctx->context_model);
1179     }
1180     if(!f->picture.interlaced_frame) put_symbol(c, state, 3, 0);
1181     else                             put_symbol(c, state, 1 + !f->picture.top_field_first, 0);
1182     put_symbol(c, state, f->picture.sample_aspect_ratio.num, 0);
1183     put_symbol(c, state, f->picture.sample_aspect_ratio.den, 0);
1184 }
1185
1186 static int encode_slice(AVCodecContext *c, void *arg){
1187     FFV1Context *fs= *(void**)arg;
1188     FFV1Context *f= fs->avctx->priv_data;
1189     int width = fs->slice_width;
1190     int height= fs->slice_height;
1191     int x= fs->slice_x;
1192     int y= fs->slice_y;
1193     AVFrame * const p= &f->picture;
1194     const int ps= (f->bits_per_raw_sample>8)+1;
1195
1196     if(p->key_frame)
1197         clear_slice_state(f, fs);
1198     if(f->version > 2){
1199         encode_slice_header(f, fs);
1200     }
1201     if(!fs->ac){
1202         fs->ac_byte_count = f->version > 2 || (!x&&!y) ? ff_rac_terminate(&fs->c) : 0;
1203         init_put_bits(&fs->pb, fs->c.bytestream_start + fs->ac_byte_count, fs->c.bytestream_end - fs->c.bytestream_start - fs->ac_byte_count);
1204     }
1205
1206     if(f->colorspace==0){
1207         const int chroma_width = -((-width )>>f->chroma_h_shift);
1208         const int chroma_height= -((-height)>>f->chroma_v_shift);
1209         const int cx= x>>f->chroma_h_shift;
1210         const int cy= y>>f->chroma_v_shift;
1211
1212         encode_plane(fs, p->data[0] + ps*x + y*p->linesize[0], width, height, p->linesize[0], 0);
1213
1214         if (f->chroma_planes){
1215             encode_plane(fs, p->data[1] + ps*cx+cy*p->linesize[1], chroma_width, chroma_height, p->linesize[1], 1);
1216             encode_plane(fs, p->data[2] + ps*cx+cy*p->linesize[2], chroma_width, chroma_height, p->linesize[2], 1);
1217         }
1218         if (fs->transparency)
1219             encode_plane(fs, p->data[3] + ps*x + y*p->linesize[3], width, height, p->linesize[3], 2);
1220     }else{
1221         encode_rgb_frame(fs, (uint32_t*)(p->data[0]) + ps*x + y*(p->linesize[0]/4), width, height, p->linesize[0]/4);
1222     }
1223     emms_c();
1224
1225     return 0;
1226 }
1227
1228 static int encode_frame(AVCodecContext *avctx, AVPacket *pkt,
1229                         const AVFrame *pict, int *got_packet)
1230 {
1231     FFV1Context *f = avctx->priv_data;
1232     RangeCoder * const c= &f->slice_context[0]->c;
1233     AVFrame * const p= &f->picture;
1234     int used_count= 0;
1235     uint8_t keystate=128;
1236     uint8_t *buf_p;
1237     int i, ret;
1238
1239     if ((ret = ff_alloc_packet2(avctx, pkt, avctx->width*avctx->height*((8*2+1+1)*4)/8
1240                                   + FF_MIN_BUFFER_SIZE)) < 0)
1241         return ret;
1242
1243     ff_init_range_encoder(c, pkt->data, pkt->size);
1244     ff_build_rac_states(c, 0.05*(1LL<<32), 256-8);
1245
1246     *p = *pict;
1247     p->pict_type= AV_PICTURE_TYPE_I;
1248
1249     if(avctx->gop_size==0 || f->picture_number % avctx->gop_size == 0){
1250         put_rac(c, &keystate, 1);
1251         p->key_frame= 1;
1252         f->gob_count++;
1253         write_header(f);
1254     }else{
1255         put_rac(c, &keystate, 0);
1256         p->key_frame= 0;
1257     }
1258
1259     if (f->ac>1){
1260         int i;
1261         for(i=1; i<256; i++){
1262             c->one_state[i]= f->state_transition[i];
1263             c->zero_state[256-i]= 256-c->one_state[i];
1264         }
1265     }
1266
1267     for(i=1; i<f->slice_count; i++){
1268         FFV1Context *fs= f->slice_context[i];
1269         uint8_t *start = pkt->data + (pkt->size-used_count)*i/f->slice_count;
1270         int len = pkt->size/f->slice_count;
1271
1272         ff_init_range_encoder(&fs->c, start, len);
1273     }
1274     avctx->execute(avctx, encode_slice, &f->slice_context[0], NULL, f->slice_count, sizeof(void*));
1275
1276     buf_p = pkt->data;
1277     for(i=0; i<f->slice_count; i++){
1278         FFV1Context *fs= f->slice_context[i];
1279         int bytes;
1280
1281         if(fs->ac){
1282             uint8_t state=128;
1283             put_rac(&fs->c, &state, 0);
1284             bytes= ff_rac_terminate(&fs->c);
1285         }else{
1286             flush_put_bits(&fs->pb); //nicer padding FIXME
1287             bytes= fs->ac_byte_count + (put_bits_count(&fs->pb)+7)/8;
1288         }
1289         if(i>0 || f->version>2){
1290             av_assert0(bytes < pkt->size/f->slice_count);
1291             memmove(buf_p, fs->c.bytestream_start, bytes);
1292             av_assert0(bytes < (1<<24));
1293             AV_WB24(buf_p+bytes, bytes);
1294             bytes+=3;
1295         }
1296         if(f->ec){
1297             unsigned v;
1298             buf_p[bytes++] = 0;
1299             v = av_crc(av_crc_get_table(AV_CRC_32_IEEE), 0, buf_p, bytes);
1300             AV_WL32(buf_p + bytes, v); bytes += 4;
1301         }
1302         buf_p += bytes;
1303     }
1304
1305     if((avctx->flags&CODEC_FLAG_PASS1) && (f->picture_number&31)==0){
1306         int j, k, m;
1307         char *p= avctx->stats_out;
1308         char *end= p + STATS_OUT_SIZE;
1309
1310         memset(f->rc_stat, 0, sizeof(f->rc_stat));
1311         for(i=0; i<f->quant_table_count; i++)
1312             memset(f->rc_stat2[i], 0, f->context_count[i]*sizeof(*f->rc_stat2[i]));
1313
1314         for(j=0; j<f->slice_count; j++){
1315             FFV1Context *fs= f->slice_context[j];
1316             for(i=0; i<256; i++){
1317                 f->rc_stat[i][0] += fs->rc_stat[i][0];
1318                 f->rc_stat[i][1] += fs->rc_stat[i][1];
1319             }
1320             for(i=0; i<f->quant_table_count; i++){
1321                 for(k=0; k<f->context_count[i]; k++){
1322                     for(m=0; m<32; m++){
1323                         f->rc_stat2[i][k][m][0] += fs->rc_stat2[i][k][m][0];
1324                         f->rc_stat2[i][k][m][1] += fs->rc_stat2[i][k][m][1];
1325                     }
1326                 }
1327             }
1328         }
1329
1330         for(j=0; j<256; j++){
1331             snprintf(p, end-p, "%"PRIu64" %"PRIu64" ", f->rc_stat[j][0], f->rc_stat[j][1]);
1332             p+= strlen(p);
1333         }
1334         snprintf(p, end-p, "\n");
1335
1336         for(i=0; i<f->quant_table_count; i++){
1337             for(j=0; j<f->context_count[i]; j++){
1338                 for(m=0; m<32; m++){
1339                     snprintf(p, end-p, "%"PRIu64" %"PRIu64" ", f->rc_stat2[i][j][m][0], f->rc_stat2[i][j][m][1]);
1340                     p+= strlen(p);
1341                 }
1342             }
1343         }
1344         snprintf(p, end-p, "%d\n", f->gob_count);
1345     } else if(avctx->flags&CODEC_FLAG_PASS1)
1346         avctx->stats_out[0] = '\0';
1347
1348     f->picture_number++;
1349     pkt->size   = buf_p - pkt->data;
1350     pkt->flags |= AV_PKT_FLAG_KEY*p->key_frame;
1351     *got_packet = 1;
1352
1353     return 0;
1354 }
1355 #endif /* CONFIG_FFV1_ENCODER */
1356
1357 static av_cold int common_end(AVCodecContext *avctx){
1358     FFV1Context *s = avctx->priv_data;
1359     int i, j;
1360
1361     if (avctx->codec->decode && s->picture.data[0])
1362         avctx->release_buffer(avctx, &s->picture);
1363
1364     for(j=0; j<s->slice_count; j++){
1365         FFV1Context *fs= s->slice_context[j];
1366         for(i=0; i<s->plane_count; i++){
1367             PlaneContext *p= &fs->plane[i];
1368
1369             av_freep(&p->state);
1370             av_freep(&p->vlc_state);
1371         }
1372         av_freep(&fs->sample_buffer);
1373     }
1374
1375     av_freep(&avctx->stats_out);
1376     for(j=0; j<s->quant_table_count; j++){
1377         av_freep(&s->initial_states[j]);
1378         for(i=0; i<s->slice_count; i++){
1379             FFV1Context *sf= s->slice_context[i];
1380             av_freep(&sf->rc_stat2[j]);
1381         }
1382         av_freep(&s->rc_stat2[j]);
1383     }
1384
1385     for(i=0; i<s->slice_count; i++){
1386         av_freep(&s->slice_context[i]);
1387     }
1388
1389     return 0;
1390 }
1391
1392 static av_always_inline void decode_line(FFV1Context *s, int w,
1393                                          int16_t *sample[2],
1394                                          int plane_index, int bits)
1395 {
1396     PlaneContext * const p= &s->plane[plane_index];
1397     RangeCoder * const c= &s->c;
1398     int x;
1399     int run_count=0;
1400     int run_mode=0;
1401     int run_index= s->run_index;
1402
1403     for(x=0; x<w; x++){
1404         int diff, context, sign;
1405
1406         context= get_context(p, sample[1] + x, sample[0] + x, sample[1] + x);
1407         if(context < 0){
1408             context= -context;
1409             sign=1;
1410         }else
1411             sign=0;
1412
1413         av_assert2(context < p->context_count);
1414
1415         if(s->ac){
1416             diff= get_symbol_inline(c, p->state[context], 1);
1417         }else{
1418             if(context == 0 && run_mode==0) run_mode=1;
1419
1420             if(run_mode){
1421                 if(run_count==0 && run_mode==1){
1422                     if(get_bits1(&s->gb)){
1423                         run_count = 1<<ff_log2_run[run_index];
1424                         if(x + run_count <= w) run_index++;
1425                     }else{
1426                         if(ff_log2_run[run_index]) run_count = get_bits(&s->gb, ff_log2_run[run_index]);
1427                         else run_count=0;
1428                         if(run_index) run_index--;
1429                         run_mode=2;
1430                     }
1431                 }
1432                 run_count--;
1433                 if(run_count < 0){
1434                     run_mode=0;
1435                     run_count=0;
1436                     diff= get_vlc_symbol(&s->gb, &p->vlc_state[context], bits);
1437                     if(diff>=0) diff++;
1438                 }else
1439                     diff=0;
1440             }else
1441                 diff= get_vlc_symbol(&s->gb, &p->vlc_state[context], bits);
1442
1443 //            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));
1444         }
1445
1446         if(sign) diff= -diff;
1447
1448         sample[1][x]= (predict(sample[1] + x, sample[0] + x) + diff) & ((1<<bits)-1);
1449     }
1450     s->run_index= run_index;
1451 }
1452
1453 static void decode_plane(FFV1Context *s, uint8_t *src, int w, int h, int stride, int plane_index){
1454     int x, y;
1455     int16_t *sample[2];
1456     sample[0]=s->sample_buffer    +3;
1457     sample[1]=s->sample_buffer+w+6+3;
1458
1459     s->run_index=0;
1460
1461     memset(s->sample_buffer, 0, 2*(w+6)*sizeof(*s->sample_buffer));
1462
1463     for(y=0; y<h; y++){
1464         int16_t *temp = sample[0]; //FIXME try a normal buffer
1465
1466         sample[0]= sample[1];
1467         sample[1]= temp;
1468
1469         sample[1][-1]= sample[0][0  ];
1470         sample[0][ w]= sample[0][w-1];
1471
1472 //{START_TIMER
1473         if(s->avctx->bits_per_raw_sample <= 8){
1474             decode_line(s, w, sample, plane_index, 8);
1475             for(x=0; x<w; x++){
1476                 src[x + stride*y]= sample[1][x];
1477             }
1478         }else{
1479             decode_line(s, w, sample, plane_index, s->avctx->bits_per_raw_sample);
1480             if(s->packed_at_lsb){
1481                 for(x=0; x<w; x++){
1482                     ((uint16_t*)(src + stride*y))[x]= sample[1][x];
1483                 }
1484             }else{
1485                 for(x=0; x<w; x++){
1486                     ((uint16_t*)(src + stride*y))[x]= sample[1][x] << (16 - s->avctx->bits_per_raw_sample);
1487                 }
1488             }
1489         }
1490 //STOP_TIMER("decode-line")}
1491     }
1492 }
1493
1494 static void decode_rgb_frame(FFV1Context *s, uint32_t *src, int w, int h, int stride){
1495     int x, y, p;
1496     int16_t *sample[4][2];
1497     for(x=0; x<4; x++){
1498         sample[x][0] = s->sample_buffer +  x*2   *(w+6) + 3;
1499         sample[x][1] = s->sample_buffer + (x*2+1)*(w+6) + 3;
1500     }
1501
1502     s->run_index=0;
1503
1504     memset(s->sample_buffer, 0, 8*(w+6)*sizeof(*s->sample_buffer));
1505
1506     for(y=0; y<h; y++){
1507         for(p=0; p<3 + s->transparency; p++){
1508             int16_t *temp = sample[p][0]; //FIXME try a normal buffer
1509
1510             sample[p][0]= sample[p][1];
1511             sample[p][1]= temp;
1512
1513             sample[p][1][-1]= sample[p][0][0  ];
1514             sample[p][0][ w]= sample[p][0][w-1];
1515             decode_line(s, w, sample[p], (p+1)/2, 9);
1516         }
1517         for(x=0; x<w; x++){
1518             int g= sample[0][1][x];
1519             int b= sample[1][1][x];
1520             int r= sample[2][1][x];
1521             int a= sample[3][1][x];
1522
1523 //            assert(g>=0 && b>=0 && r>=0);
1524 //            assert(g<256 && b<512 && r<512);
1525
1526             b -= 0x100;
1527             r -= 0x100;
1528             g -= (b + r)>>2;
1529             b += g;
1530             r += g;
1531
1532             src[x + stride*y]= b + (g<<8) + (r<<16) + (a<<24);
1533         }
1534     }
1535 }
1536
1537 static int decode_slice_header(FFV1Context *f, FFV1Context *fs){
1538     RangeCoder *c = &fs->c;
1539     uint8_t state[CONTEXT_SIZE];
1540     unsigned ps, i, context_count;
1541     memset(state, 128, sizeof(state));
1542
1543     av_assert0(f->version > 2);
1544
1545     fs->slice_x     = get_symbol(c, state, 0)   *f->width ;
1546     fs->slice_y     = get_symbol(c, state, 0)   *f->height;
1547     fs->slice_width =(get_symbol(c, state, 0)+1)*f->width  + fs->slice_x;
1548     fs->slice_height=(get_symbol(c, state, 0)+1)*f->height + fs->slice_y;
1549
1550     fs->slice_x /= f->num_h_slices;
1551     fs->slice_y /= f->num_v_slices;
1552     fs->slice_width  = fs->slice_width /f->num_h_slices - fs->slice_x;
1553     fs->slice_height = fs->slice_height/f->num_v_slices - fs->slice_y;
1554     if((unsigned)fs->slice_width > f->width || (unsigned)fs->slice_height > f->height)
1555         return -1;
1556     if(    (unsigned)fs->slice_x + (uint64_t)fs->slice_width  > f->width
1557         || (unsigned)fs->slice_y + (uint64_t)fs->slice_height > f->height)
1558         return -1;
1559
1560     for(i=0; i<f->plane_count; i++){
1561         PlaneContext * const p= &fs->plane[i];
1562         int idx=get_symbol(c, state, 0);
1563         if(idx > (unsigned)f->quant_table_count){
1564             av_log(f->avctx, AV_LOG_ERROR, "quant_table_index out of range\n");
1565             return -1;
1566         }
1567         p->quant_table_index= idx;
1568         memcpy(p->quant_table, f->quant_tables[idx], sizeof(p->quant_table));
1569         context_count= f->context_count[idx];
1570
1571         if(p->context_count < context_count){
1572             av_freep(&p->state);
1573             av_freep(&p->vlc_state);
1574         }
1575         p->context_count= context_count;
1576     }
1577
1578     ps = get_symbol(c, state, 0);
1579     if(ps==1){
1580         f->picture.interlaced_frame = 1;
1581         f->picture.top_field_first  = 1;
1582     } else if(ps==2){
1583         f->picture.interlaced_frame = 1;
1584         f->picture.top_field_first  = 0;
1585     } else if(ps==3){
1586         f->picture.interlaced_frame = 0;
1587     }
1588     f->picture.sample_aspect_ratio.num = get_symbol(c, state, 0);
1589     f->picture.sample_aspect_ratio.den = get_symbol(c, state, 0);
1590
1591     return 0;
1592 }
1593
1594 static int decode_slice(AVCodecContext *c, void *arg){
1595     FFV1Context *fs= *(void**)arg;
1596     FFV1Context *f= fs->avctx->priv_data;
1597     int width, height, x, y;
1598     const int ps= (c->bits_per_raw_sample>8)+1;
1599     AVFrame * const p= &f->picture;
1600
1601     if(f->version > 2){
1602         if(init_slice_state(f, fs) < 0)
1603             return AVERROR(ENOMEM);
1604         if(decode_slice_header(f, fs) < 0)
1605             return AVERROR_INVALIDDATA;
1606     }
1607     if(init_slice_state(f, fs) < 0)
1608         return AVERROR(ENOMEM);
1609     if(f->picture.key_frame)
1610         clear_slice_state(f, fs);
1611     width = fs->slice_width;
1612     height= fs->slice_height;
1613     x= fs->slice_x;
1614     y= fs->slice_y;
1615
1616     if(!fs->ac){
1617         fs->ac_byte_count = f->version > 2 || (!x&&!y) ? fs->c.bytestream - fs->c.bytestream_start - 1 : 0;
1618         init_get_bits(&fs->gb,
1619                       fs->c.bytestream_start + fs->ac_byte_count,
1620                       (fs->c.bytestream_end - fs->c.bytestream_start - fs->ac_byte_count) * 8);
1621     }
1622
1623     av_assert1(width && height);
1624     if(f->colorspace==0){
1625         const int chroma_width = -((-width )>>f->chroma_h_shift);
1626         const int chroma_height= -((-height)>>f->chroma_v_shift);
1627         const int cx= x>>f->chroma_h_shift;
1628         const int cy= y>>f->chroma_v_shift;
1629         decode_plane(fs, p->data[0] + ps*x + y*p->linesize[0], width, height, p->linesize[0], 0);
1630
1631         if (f->chroma_planes){
1632             decode_plane(fs, p->data[1] + ps*cx+cy*p->linesize[1], chroma_width, chroma_height, p->linesize[1], 1);
1633             decode_plane(fs, p->data[2] + ps*cx+cy*p->linesize[2], chroma_width, chroma_height, p->linesize[2], 1);
1634         }
1635         if (fs->transparency)
1636             decode_plane(fs, p->data[3] + ps*x + y*p->linesize[3], width, height, p->linesize[3], 2);
1637     }else{
1638         decode_rgb_frame(fs, (uint32_t*)p->data[0] + ps*x + y*(p->linesize[0]/4), width, height, p->linesize[0]/4);
1639     }
1640
1641     emms_c();
1642
1643     return 0;
1644 }
1645
1646 static int read_quant_table(RangeCoder *c, int16_t *quant_table, int scale){
1647     int v;
1648     int i=0;
1649     uint8_t state[CONTEXT_SIZE];
1650
1651     memset(state, 128, sizeof(state));
1652
1653     for(v=0; i<128 ; v++){
1654         unsigned len= get_symbol(c, state, 0) + 1;
1655
1656         if(len > 128 - i) return -1;
1657
1658         while(len--){
1659             quant_table[i] = scale*v;
1660             i++;
1661 //printf("%2d ",v);
1662 //if(i%16==0) printf("\n");
1663         }
1664     }
1665
1666     for(i=1; i<128; i++){
1667         quant_table[256-i]= -quant_table[i];
1668     }
1669     quant_table[128]= -quant_table[127];
1670
1671     return 2*v - 1;
1672 }
1673
1674 static int read_quant_tables(RangeCoder *c, int16_t quant_table[MAX_CONTEXT_INPUTS][256]){
1675     int i;
1676     int context_count=1;
1677
1678     for(i=0; i<5; i++){
1679         context_count*= read_quant_table(c, quant_table[i], context_count);
1680         if(context_count > 32768U){
1681             return -1;
1682         }
1683     }
1684     return (context_count+1)/2;
1685 }
1686
1687 static int read_extra_header(FFV1Context *f){
1688     RangeCoder * const c= &f->c;
1689     uint8_t state[CONTEXT_SIZE];
1690     int i, j, k;
1691     uint8_t state2[32][CONTEXT_SIZE];
1692
1693     memset(state2, 128, sizeof(state2));
1694     memset(state, 128, sizeof(state));
1695
1696     ff_init_range_decoder(c, f->avctx->extradata, f->avctx->extradata_size);
1697     ff_build_rac_states(c, 0.05*(1LL<<32), 256-8);
1698
1699     f->version= get_symbol(c, state, 0);
1700     if(f->version > 2) {
1701         c->bytestream_end -= 4;
1702         f->minor_version= get_symbol(c, state, 0);
1703     }
1704     f->ac= f->avctx->coder_type= get_symbol(c, state, 0);
1705     if(f->ac>1){
1706         for(i=1; i<256; i++){
1707             f->state_transition[i]= get_symbol(c, state, 1) + c->one_state[i];
1708         }
1709     }
1710     f->colorspace= get_symbol(c, state, 0); //YUV cs type
1711     f->avctx->bits_per_raw_sample= get_symbol(c, state, 0);
1712     f->chroma_planes= get_rac(c, state);
1713     f->chroma_h_shift= get_symbol(c, state, 0);
1714     f->chroma_v_shift= get_symbol(c, state, 0);
1715     f->transparency= get_rac(c, state);
1716     f->plane_count= 2 + f->transparency;
1717     f->num_h_slices= 1 + get_symbol(c, state, 0);
1718     f->num_v_slices= 1 + get_symbol(c, state, 0);
1719     if(f->num_h_slices > (unsigned)f->width || f->num_v_slices > (unsigned)f->height){
1720         av_log(f->avctx, AV_LOG_ERROR, "too many slices\n");
1721         return -1;
1722     }
1723
1724     f->quant_table_count= get_symbol(c, state, 0);
1725     if(f->quant_table_count > (unsigned)MAX_QUANT_TABLES)
1726         return -1;
1727     for(i=0; i<f->quant_table_count; i++){
1728         if((f->context_count[i]= read_quant_tables(c, f->quant_tables[i])) < 0){
1729             av_log(f->avctx, AV_LOG_ERROR, "read_quant_table error\n");
1730             return -1;
1731         }
1732     }
1733
1734     if(allocate_initial_states(f) < 0)
1735         return AVERROR(ENOMEM);
1736
1737     for(i=0; i<f->quant_table_count; i++){
1738         if(get_rac(c, state)){
1739             for(j=0; j<f->context_count[i]; j++){
1740                 for(k=0; k<CONTEXT_SIZE; k++){
1741                     int pred= j ? f->initial_states[i][j-1][k] : 128;
1742                     f->initial_states[i][j][k]= (pred+get_symbol(c, state2[k], 1))&0xFF;
1743                 }
1744             }
1745         }
1746     }
1747
1748     if(f->version > 2){
1749         f->ec = get_symbol(c, state, 0);
1750     }
1751
1752     if(f->version > 2){
1753         unsigned v;
1754         v = av_crc(av_crc_get_table(AV_CRC_32_IEEE), 0, f->avctx->extradata, f->avctx->extradata_size);
1755         if(v){
1756             av_log(f->avctx, AV_LOG_ERROR, "CRC mismatch %X!\n", v);
1757             return AVERROR_INVALIDDATA;
1758         }
1759     }
1760
1761     return 0;
1762 }
1763
1764 static int read_header(FFV1Context *f){
1765     uint8_t state[CONTEXT_SIZE];
1766     int i, j, context_count;
1767     RangeCoder * const c= &f->slice_context[0]->c;
1768
1769     memset(state, 128, sizeof(state));
1770
1771     if(f->version < 2){
1772         unsigned v= get_symbol(c, state, 0);
1773         if(v >= 2){
1774             av_log(f->avctx, AV_LOG_ERROR, "invalid version %d in ver01 header\n", v);
1775             return AVERROR_INVALIDDATA;
1776         }
1777         f->version = v;
1778         f->ac= f->avctx->coder_type= get_symbol(c, state, 0);
1779         if(f->ac>1){
1780             for(i=1; i<256; i++){
1781                 f->state_transition[i]= get_symbol(c, state, 1) + c->one_state[i];
1782             }
1783         }
1784         f->colorspace= get_symbol(c, state, 0); //YUV cs type
1785         if(f->version>0)
1786             f->avctx->bits_per_raw_sample= get_symbol(c, state, 0);
1787         f->chroma_planes= get_rac(c, state);
1788         f->chroma_h_shift= get_symbol(c, state, 0);
1789         f->chroma_v_shift= get_symbol(c, state, 0);
1790         f->transparency= get_rac(c, state);
1791         f->plane_count= 2 + f->transparency;
1792     }
1793
1794     if(f->colorspace==0){
1795         if(!f->transparency && !f->chroma_planes){
1796             if (f->avctx->bits_per_raw_sample<=8)
1797                 f->avctx->pix_fmt= PIX_FMT_GRAY8;
1798             else
1799                 f->avctx->pix_fmt= PIX_FMT_GRAY16;
1800         }else if(f->avctx->bits_per_raw_sample<=8 && !f->transparency){
1801             switch(16*f->chroma_h_shift + f->chroma_v_shift){
1802             case 0x00: f->avctx->pix_fmt= PIX_FMT_YUV444P; break;
1803             case 0x01: f->avctx->pix_fmt= PIX_FMT_YUV440P; break;
1804             case 0x10: f->avctx->pix_fmt= PIX_FMT_YUV422P; break;
1805             case 0x11: f->avctx->pix_fmt= PIX_FMT_YUV420P; break;
1806             case 0x20: f->avctx->pix_fmt= PIX_FMT_YUV411P; break;
1807             case 0x22: f->avctx->pix_fmt= PIX_FMT_YUV410P; break;
1808             default:
1809                 av_log(f->avctx, AV_LOG_ERROR, "format not supported\n");
1810                 return -1;
1811             }
1812         }else if(f->avctx->bits_per_raw_sample<=8 && f->transparency){
1813             switch(16*f->chroma_h_shift + f->chroma_v_shift){
1814             case 0x00: f->avctx->pix_fmt= PIX_FMT_YUVA444P; break;
1815             case 0x10: f->avctx->pix_fmt= PIX_FMT_YUVA422P; break;
1816             case 0x11: f->avctx->pix_fmt= PIX_FMT_YUVA420P; break;
1817             default:
1818                 av_log(f->avctx, AV_LOG_ERROR, "format not supported\n");
1819                 return -1;
1820             }
1821         }else if(f->avctx->bits_per_raw_sample==9) {
1822             f->packed_at_lsb=1;
1823             switch(16*f->chroma_h_shift + f->chroma_v_shift){
1824             case 0x00: f->avctx->pix_fmt= PIX_FMT_YUV444P9; break;
1825             case 0x10: f->avctx->pix_fmt= PIX_FMT_YUV422P9; break;
1826             case 0x11: f->avctx->pix_fmt= PIX_FMT_YUV420P9; break;
1827             default:
1828                 av_log(f->avctx, AV_LOG_ERROR, "format not supported\n");
1829                 return -1;
1830             }
1831         }else if(f->avctx->bits_per_raw_sample==10) {
1832             f->packed_at_lsb=1;
1833             switch(16*f->chroma_h_shift + f->chroma_v_shift){
1834             case 0x00: f->avctx->pix_fmt= PIX_FMT_YUV444P10; break;
1835             case 0x10: f->avctx->pix_fmt= PIX_FMT_YUV422P10; break;
1836             case 0x11: f->avctx->pix_fmt= PIX_FMT_YUV420P10; break;
1837             default:
1838                 av_log(f->avctx, AV_LOG_ERROR, "format not supported\n");
1839                 return -1;
1840             }
1841         }else {
1842             switch(16*f->chroma_h_shift + f->chroma_v_shift){
1843             case 0x00: f->avctx->pix_fmt= PIX_FMT_YUV444P16; break;
1844             case 0x10: f->avctx->pix_fmt= PIX_FMT_YUV422P16; break;
1845             case 0x11: f->avctx->pix_fmt= PIX_FMT_YUV420P16; break;
1846             default:
1847                 av_log(f->avctx, AV_LOG_ERROR, "format not supported\n");
1848                 return -1;
1849             }
1850         }
1851     }else if(f->colorspace==1){
1852         if(f->chroma_h_shift || f->chroma_v_shift){
1853             av_log(f->avctx, AV_LOG_ERROR, "chroma subsampling not supported in this colorspace\n");
1854             return -1;
1855         }
1856         if(f->transparency) f->avctx->pix_fmt= PIX_FMT_RGB32;
1857         else                f->avctx->pix_fmt= PIX_FMT_0RGB32;
1858     }else{
1859         av_log(f->avctx, AV_LOG_ERROR, "colorspace not supported\n");
1860         return -1;
1861     }
1862
1863 //printf("%d %d %d\n", f->chroma_h_shift, f->chroma_v_shift,f->avctx->pix_fmt);
1864     if(f->version < 2){
1865         context_count= read_quant_tables(c, f->quant_table);
1866         if(context_count < 0){
1867                 av_log(f->avctx, AV_LOG_ERROR, "read_quant_table error\n");
1868                 return -1;
1869         }
1870     }else if(f->version < 3){
1871         f->slice_count= get_symbol(c, state, 0);
1872     }else{
1873         const uint8_t *p= c->bytestream_end;
1874         for(f->slice_count = 0; f->slice_count < MAX_SLICES && 3 < p - c->bytestream_start; f->slice_count++){
1875             int trailer = 3 + 5*!!f->ec;
1876             int size = AV_RB24(p-trailer);
1877             if(size + trailer > p - c->bytestream_start)
1878                 break;
1879             p -= size + trailer;
1880         }
1881     }
1882     if(f->slice_count > (unsigned)MAX_SLICES || f->slice_count <= 0){
1883         av_log(f->avctx, AV_LOG_ERROR, "slice count %d is invalid\n", f->slice_count);
1884         return -1;
1885     }
1886
1887     for(j=0; j<f->slice_count; j++){
1888         FFV1Context *fs= f->slice_context[j];
1889         fs->ac= f->ac;
1890         fs->packed_at_lsb= f->packed_at_lsb;
1891
1892         if(f->version == 2){
1893             fs->slice_x     = get_symbol(c, state, 0)   *f->width ;
1894             fs->slice_y     = get_symbol(c, state, 0)   *f->height;
1895             fs->slice_width =(get_symbol(c, state, 0)+1)*f->width  + fs->slice_x;
1896             fs->slice_height=(get_symbol(c, state, 0)+1)*f->height + fs->slice_y;
1897
1898             fs->slice_x /= f->num_h_slices;
1899             fs->slice_y /= f->num_v_slices;
1900             fs->slice_width  = fs->slice_width /f->num_h_slices - fs->slice_x;
1901             fs->slice_height = fs->slice_height/f->num_v_slices - fs->slice_y;
1902             if((unsigned)fs->slice_width > f->width || (unsigned)fs->slice_height > f->height)
1903                 return -1;
1904             if(    (unsigned)fs->slice_x + (uint64_t)fs->slice_width  > f->width
1905                 || (unsigned)fs->slice_y + (uint64_t)fs->slice_height > f->height)
1906                 return -1;
1907         }
1908
1909         for(i=0; i<f->plane_count; i++){
1910             PlaneContext * const p= &fs->plane[i];
1911
1912             if(f->version == 2){
1913                 int idx=get_symbol(c, state, 0);
1914                 if(idx > (unsigned)f->quant_table_count){
1915                     av_log(f->avctx, AV_LOG_ERROR, "quant_table_index out of range\n");
1916                     return -1;
1917                 }
1918                 p->quant_table_index= idx;
1919                 memcpy(p->quant_table, f->quant_tables[idx], sizeof(p->quant_table));
1920                 context_count= f->context_count[idx];
1921             }else{
1922                 memcpy(p->quant_table, f->quant_table, sizeof(p->quant_table));
1923             }
1924
1925             if(f->version <= 2){
1926                 if(p->context_count < context_count){
1927                     av_freep(&p->state);
1928                     av_freep(&p->vlc_state);
1929                 }
1930                 p->context_count= context_count;
1931             }
1932         }
1933     }
1934     return 0;
1935 }
1936
1937 static av_cold int decode_init(AVCodecContext *avctx)
1938 {
1939     FFV1Context *f = avctx->priv_data;
1940
1941     common_init(avctx);
1942
1943     if(avctx->extradata && read_extra_header(f) < 0)
1944         return -1;
1945
1946     if(init_slice_contexts(f) < 0)
1947         return -1;
1948
1949     return 0;
1950 }
1951
1952 static int decode_frame(AVCodecContext *avctx, void *data, int *data_size, AVPacket *avpkt){
1953     const uint8_t *buf = avpkt->data;
1954     int buf_size = avpkt->size;
1955     FFV1Context *f = avctx->priv_data;
1956     RangeCoder * const c= &f->slice_context[0]->c;
1957     AVFrame * const p= &f->picture;
1958     int i;
1959     uint8_t keystate= 128;
1960     const uint8_t *buf_p;
1961
1962     AVFrame *picture = data;
1963
1964     /* release previously stored data */
1965     if (p->data[0])
1966         avctx->release_buffer(avctx, p);
1967
1968     ff_init_range_decoder(c, buf, buf_size);
1969     ff_build_rac_states(c, 0.05*(1LL<<32), 256-8);
1970
1971
1972     p->pict_type= AV_PICTURE_TYPE_I; //FIXME I vs. P
1973     if(get_rac(c, &keystate)){
1974         p->key_frame= 1;
1975         f->key_frame_ok = 0;
1976         if(read_header(f) < 0)
1977             return -1;
1978         f->key_frame_ok = 1;
1979     }else{
1980         if (!f->key_frame_ok) {
1981             av_log(avctx, AV_LOG_ERROR, "Cant decode non keyframe without valid keyframe\n");
1982             return AVERROR_INVALIDDATA;
1983         }
1984         p->key_frame= 0;
1985     }
1986
1987     p->reference= 0;
1988     if(avctx->get_buffer(avctx, p) < 0){
1989         av_log(avctx, AV_LOG_ERROR, "get_buffer() failed\n");
1990         return -1;
1991     }
1992
1993     if(avctx->debug&FF_DEBUG_PICT_INFO)
1994         av_log(avctx, AV_LOG_DEBUG, "ver:%d keyframe:%d coder:%d ec:%d slices:%d\n",
1995                f->version, p->key_frame, f->ac, f->ec, f->slice_count);
1996
1997     buf_p= buf + buf_size;
1998     for(i=f->slice_count-1; i>=0; i--){
1999         FFV1Context *fs= f->slice_context[i];
2000         int trailer = 3 + 5*!!f->ec;
2001         int v;
2002
2003         if(i || f->version>2) v = AV_RB24(buf_p-trailer)+trailer;
2004         else                  v = buf_p - c->bytestream_start;
2005         if(buf_p - c->bytestream_start < v){
2006             av_log(avctx, AV_LOG_ERROR, "Slice pointer chain broken\n");
2007             return -1;
2008         }
2009         buf_p -= v;
2010
2011         if(f->ec){
2012             unsigned crc = av_crc(av_crc_get_table(AV_CRC_32_IEEE), 0, buf_p, v);
2013             if(crc){
2014                 av_log(f->avctx, AV_LOG_ERROR, "CRC mismatch %X!\n", crc);
2015             }
2016         }
2017
2018         if(i){
2019             ff_init_range_decoder(&fs->c, buf_p, v);
2020         }
2021     }
2022
2023     avctx->execute(avctx, decode_slice, &f->slice_context[0], NULL, f->slice_count, sizeof(void*));
2024     f->picture_number++;
2025
2026     *picture= *p;
2027     *data_size = sizeof(AVFrame);
2028
2029     return buf_size;
2030 }
2031
2032 AVCodec ff_ffv1_decoder = {
2033     .name           = "ffv1",
2034     .type           = AVMEDIA_TYPE_VIDEO,
2035     .id             = CODEC_ID_FFV1,
2036     .priv_data_size = sizeof(FFV1Context),
2037     .init           = decode_init,
2038     .close          = common_end,
2039     .decode         = decode_frame,
2040     .capabilities   = CODEC_CAP_DR1 /*| CODEC_CAP_DRAW_HORIZ_BAND*/ |
2041                       CODEC_CAP_SLICE_THREADS,
2042     .long_name      = NULL_IF_CONFIG_SMALL("FFmpeg video codec #1"),
2043 };
2044
2045 #if CONFIG_FFV1_ENCODER
2046
2047 #define OFFSET(x) offsetof(FFV1Context, x)
2048 #define VE AV_OPT_FLAG_VIDEO_PARAM | AV_OPT_FLAG_ENCODING_PARAM
2049 static const AVOption options[] = {
2050     { "slicecrc",        "Protect slices with CRCs",               OFFSET(ec),              AV_OPT_TYPE_INT, {-1}, -1, 1, VE},
2051 {NULL}
2052 };
2053
2054 static const AVClass class = {
2055     .class_name = "ffv1 encoder",
2056     .item_name  = av_default_item_name,
2057     .option     = options,
2058     .version    = LIBAVUTIL_VERSION_INT,
2059 };
2060
2061 AVCodec ff_ffv1_encoder = {
2062     .name           = "ffv1",
2063     .type           = AVMEDIA_TYPE_VIDEO,
2064     .id             = CODEC_ID_FFV1,
2065     .priv_data_size = sizeof(FFV1Context),
2066     .init           = encode_init,
2067     .encode2        = encode_frame,
2068     .close          = common_end,
2069     .capabilities   = CODEC_CAP_SLICE_THREADS,
2070     .pix_fmts       = (const enum PixelFormat[]){
2071         PIX_FMT_YUV420P, PIX_FMT_YUVA420P, PIX_FMT_YUVA422P, PIX_FMT_YUV444P,
2072         PIX_FMT_YUVA444P, PIX_FMT_YUV440P, PIX_FMT_YUV422P, PIX_FMT_YUV411P,
2073         PIX_FMT_YUV410P, PIX_FMT_0RGB32, PIX_FMT_RGB32, PIX_FMT_YUV420P16,
2074         PIX_FMT_YUV422P16, PIX_FMT_YUV444P16, PIX_FMT_YUV444P9, PIX_FMT_YUV422P9,
2075         PIX_FMT_YUV420P9, PIX_FMT_YUV420P10, PIX_FMT_YUV422P10, PIX_FMT_YUV444P10,
2076         PIX_FMT_GRAY16, PIX_FMT_GRAY8,
2077         PIX_FMT_NONE
2078     },
2079     .long_name      = NULL_IF_CONFIG_SMALL("FFmpeg video codec #1"),
2080     .priv_class     = &class,
2081 };
2082 #endif