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]= fs->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         int len= get_symbol(c, state, 0) + 1;
1655
1656         if(len + i > 128) 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         f->minor_version= get_symbol(c, state, 0);
1702     f->ac= f->avctx->coder_type= get_symbol(c, state, 0);
1703     if(f->ac>1){
1704         for(i=1; i<256; i++){
1705             f->state_transition[i]= get_symbol(c, state, 1) + c->one_state[i];
1706         }
1707     }
1708     f->colorspace= get_symbol(c, state, 0); //YUV cs type
1709     f->avctx->bits_per_raw_sample= get_symbol(c, state, 0);
1710     f->chroma_planes= get_rac(c, state);
1711     f->chroma_h_shift= get_symbol(c, state, 0);
1712     f->chroma_v_shift= get_symbol(c, state, 0);
1713     f->transparency= get_rac(c, state);
1714     f->plane_count= 2 + f->transparency;
1715     f->num_h_slices= 1 + get_symbol(c, state, 0);
1716     f->num_v_slices= 1 + get_symbol(c, state, 0);
1717     if(f->num_h_slices > (unsigned)f->width || f->num_v_slices > (unsigned)f->height){
1718         av_log(f->avctx, AV_LOG_ERROR, "too many slices\n");
1719         return -1;
1720     }
1721
1722     f->quant_table_count= get_symbol(c, state, 0);
1723     if(f->quant_table_count > (unsigned)MAX_QUANT_TABLES)
1724         return -1;
1725     for(i=0; i<f->quant_table_count; i++){
1726         if((f->context_count[i]= read_quant_tables(c, f->quant_tables[i])) < 0){
1727             av_log(f->avctx, AV_LOG_ERROR, "read_quant_table error\n");
1728             return -1;
1729         }
1730     }
1731
1732     if(allocate_initial_states(f) < 0)
1733         return AVERROR(ENOMEM);
1734
1735     for(i=0; i<f->quant_table_count; i++){
1736         if(get_rac(c, state)){
1737             for(j=0; j<f->context_count[i]; j++){
1738                 for(k=0; k<CONTEXT_SIZE; k++){
1739                     int pred= j ? f->initial_states[i][j-1][k] : 128;
1740                     f->initial_states[i][j][k]= (pred+get_symbol(c, state2[k], 1))&0xFF;
1741                 }
1742             }
1743         }
1744     }
1745
1746     if(f->version > 2){
1747         f->ec = get_symbol(c, state, 0);
1748     }
1749
1750     if(f->version > 2){
1751         unsigned v;
1752         v = av_crc(av_crc_get_table(AV_CRC_32_IEEE), 0, f->avctx->extradata, f->avctx->extradata_size);
1753         if(v){
1754             av_log(f->avctx, AV_LOG_ERROR, "CRC mismatch %X!\n", v);
1755             return AVERROR_INVALIDDATA;
1756         }
1757     }
1758
1759     return 0;
1760 }
1761
1762 static int read_header(FFV1Context *f){
1763     uint8_t state[CONTEXT_SIZE];
1764     int i, j, context_count;
1765     RangeCoder * const c= &f->slice_context[0]->c;
1766
1767     memset(state, 128, sizeof(state));
1768
1769     if(f->version < 2){
1770         f->version= get_symbol(c, state, 0);
1771         f->ac= f->avctx->coder_type= get_symbol(c, state, 0);
1772         if(f->ac>1){
1773             for(i=1; i<256; i++){
1774                 f->state_transition[i]= get_symbol(c, state, 1) + c->one_state[i];
1775             }
1776         }
1777         f->colorspace= get_symbol(c, state, 0); //YUV cs type
1778         if(f->version>0)
1779             f->avctx->bits_per_raw_sample= get_symbol(c, state, 0);
1780         f->chroma_planes= get_rac(c, state);
1781         f->chroma_h_shift= get_symbol(c, state, 0);
1782         f->chroma_v_shift= get_symbol(c, state, 0);
1783         f->transparency= get_rac(c, state);
1784         f->plane_count= 2 + f->transparency;
1785     }
1786
1787     if(f->colorspace==0){
1788         if(!f->transparency && !f->chroma_planes){
1789             if (f->avctx->bits_per_raw_sample<=8)
1790                 f->avctx->pix_fmt= PIX_FMT_GRAY8;
1791             else
1792                 f->avctx->pix_fmt= PIX_FMT_GRAY16;
1793         }else if(f->avctx->bits_per_raw_sample<=8 && !f->transparency){
1794             switch(16*f->chroma_h_shift + f->chroma_v_shift){
1795             case 0x00: f->avctx->pix_fmt= PIX_FMT_YUV444P; break;
1796             case 0x01: f->avctx->pix_fmt= PIX_FMT_YUV440P; break;
1797             case 0x10: f->avctx->pix_fmt= PIX_FMT_YUV422P; break;
1798             case 0x11: f->avctx->pix_fmt= PIX_FMT_YUV420P; break;
1799             case 0x20: f->avctx->pix_fmt= PIX_FMT_YUV411P; break;
1800             case 0x22: f->avctx->pix_fmt= PIX_FMT_YUV410P; break;
1801             default:
1802                 av_log(f->avctx, AV_LOG_ERROR, "format not supported\n");
1803                 return -1;
1804             }
1805         }else if(f->avctx->bits_per_raw_sample<=8 && f->transparency){
1806             switch(16*f->chroma_h_shift + f->chroma_v_shift){
1807             case 0x00: f->avctx->pix_fmt= PIX_FMT_YUVA444P; break;
1808             case 0x10: f->avctx->pix_fmt= PIX_FMT_YUVA422P; break;
1809             case 0x11: f->avctx->pix_fmt= PIX_FMT_YUVA420P; break;
1810             default:
1811                 av_log(f->avctx, AV_LOG_ERROR, "format not supported\n");
1812                 return -1;
1813             }
1814         }else if(f->avctx->bits_per_raw_sample==9) {
1815             f->packed_at_lsb=1;
1816             switch(16*f->chroma_h_shift + f->chroma_v_shift){
1817             case 0x00: f->avctx->pix_fmt= PIX_FMT_YUV444P9; break;
1818             case 0x10: f->avctx->pix_fmt= PIX_FMT_YUV422P9; break;
1819             case 0x11: f->avctx->pix_fmt= PIX_FMT_YUV420P9; break;
1820             default:
1821                 av_log(f->avctx, AV_LOG_ERROR, "format not supported\n");
1822                 return -1;
1823             }
1824         }else if(f->avctx->bits_per_raw_sample==10) {
1825             f->packed_at_lsb=1;
1826             switch(16*f->chroma_h_shift + f->chroma_v_shift){
1827             case 0x00: f->avctx->pix_fmt= PIX_FMT_YUV444P10; break;
1828             case 0x10: f->avctx->pix_fmt= PIX_FMT_YUV422P10; break;
1829             case 0x11: f->avctx->pix_fmt= PIX_FMT_YUV420P10; break;
1830             default:
1831                 av_log(f->avctx, AV_LOG_ERROR, "format not supported\n");
1832                 return -1;
1833             }
1834         }else {
1835             switch(16*f->chroma_h_shift + f->chroma_v_shift){
1836             case 0x00: f->avctx->pix_fmt= PIX_FMT_YUV444P16; break;
1837             case 0x10: f->avctx->pix_fmt= PIX_FMT_YUV422P16; break;
1838             case 0x11: f->avctx->pix_fmt= PIX_FMT_YUV420P16; break;
1839             default:
1840                 av_log(f->avctx, AV_LOG_ERROR, "format not supported\n");
1841                 return -1;
1842             }
1843         }
1844     }else if(f->colorspace==1){
1845         if(f->chroma_h_shift || f->chroma_v_shift){
1846             av_log(f->avctx, AV_LOG_ERROR, "chroma subsampling not supported in this colorspace\n");
1847             return -1;
1848         }
1849         if(f->transparency) f->avctx->pix_fmt= PIX_FMT_RGB32;
1850         else                f->avctx->pix_fmt= PIX_FMT_0RGB32;
1851     }else{
1852         av_log(f->avctx, AV_LOG_ERROR, "colorspace not supported\n");
1853         return -1;
1854     }
1855
1856 //printf("%d %d %d\n", f->chroma_h_shift, f->chroma_v_shift,f->avctx->pix_fmt);
1857     if(f->version < 2){
1858         context_count= read_quant_tables(c, f->quant_table);
1859         if(context_count < 0){
1860                 av_log(f->avctx, AV_LOG_ERROR, "read_quant_table error\n");
1861                 return -1;
1862         }
1863     }else if(f->version < 3){
1864         f->slice_count= get_symbol(c, state, 0);
1865     }else{
1866         const uint8_t *p= c->bytestream_end;
1867         for(f->slice_count = 0; f->slice_count < MAX_SLICES && 3 < p - c->bytestream_start; f->slice_count++){
1868             int trailer = 3 + 5*!!f->ec;
1869             int size = AV_RB24(p-trailer);
1870             if(size + trailer > p - c->bytestream_start)
1871                 break;
1872             p -= size + trailer;
1873         }
1874     }
1875     if(f->slice_count > (unsigned)MAX_SLICES || f->slice_count <= 0){
1876         av_log(f->avctx, AV_LOG_ERROR, "slice count %d is invalid\n", f->slice_count);
1877         return -1;
1878     }
1879
1880     for(j=0; j<f->slice_count; j++){
1881         FFV1Context *fs= f->slice_context[j];
1882         fs->ac= f->ac;
1883         fs->packed_at_lsb= f->packed_at_lsb;
1884
1885         if(f->version == 2){
1886             fs->slice_x     = get_symbol(c, state, 0)   *f->width ;
1887             fs->slice_y     = get_symbol(c, state, 0)   *f->height;
1888             fs->slice_width =(get_symbol(c, state, 0)+1)*f->width  + fs->slice_x;
1889             fs->slice_height=(get_symbol(c, state, 0)+1)*f->height + fs->slice_y;
1890
1891             fs->slice_x /= f->num_h_slices;
1892             fs->slice_y /= f->num_v_slices;
1893             fs->slice_width  = fs->slice_width /f->num_h_slices - fs->slice_x;
1894             fs->slice_height = fs->slice_height/f->num_v_slices - fs->slice_y;
1895             if((unsigned)fs->slice_width > f->width || (unsigned)fs->slice_height > f->height)
1896                 return -1;
1897             if(    (unsigned)fs->slice_x + (uint64_t)fs->slice_width  > f->width
1898                 || (unsigned)fs->slice_y + (uint64_t)fs->slice_height > f->height)
1899                 return -1;
1900         }
1901
1902         for(i=0; i<f->plane_count; i++){
1903             PlaneContext * const p= &fs->plane[i];
1904
1905             if(f->version == 2){
1906                 int idx=get_symbol(c, state, 0);
1907                 if(idx > (unsigned)f->quant_table_count){
1908                     av_log(f->avctx, AV_LOG_ERROR, "quant_table_index out of range\n");
1909                     return -1;
1910                 }
1911                 p->quant_table_index= idx;
1912                 memcpy(p->quant_table, f->quant_tables[idx], sizeof(p->quant_table));
1913                 context_count= f->context_count[idx];
1914             }else{
1915                 memcpy(p->quant_table, f->quant_table, sizeof(p->quant_table));
1916             }
1917
1918             if(f->version <= 2){
1919                 if(p->context_count < context_count){
1920                     av_freep(&p->state);
1921                     av_freep(&p->vlc_state);
1922                 }
1923                 p->context_count= context_count;
1924             }
1925         }
1926     }
1927     return 0;
1928 }
1929
1930 static av_cold int decode_init(AVCodecContext *avctx)
1931 {
1932     FFV1Context *f = avctx->priv_data;
1933
1934     common_init(avctx);
1935
1936     if(avctx->extradata && read_extra_header(f) < 0)
1937         return -1;
1938
1939     if(init_slice_contexts(f) < 0)
1940         return -1;
1941
1942     return 0;
1943 }
1944
1945 static int decode_frame(AVCodecContext *avctx, void *data, int *data_size, AVPacket *avpkt){
1946     const uint8_t *buf = avpkt->data;
1947     int buf_size = avpkt->size;
1948     FFV1Context *f = avctx->priv_data;
1949     RangeCoder * const c= &f->slice_context[0]->c;
1950     AVFrame * const p= &f->picture;
1951     int i;
1952     uint8_t keystate= 128;
1953     const uint8_t *buf_p;
1954
1955     AVFrame *picture = data;
1956
1957     /* release previously stored data */
1958     if (p->data[0])
1959         avctx->release_buffer(avctx, p);
1960
1961     ff_init_range_decoder(c, buf, buf_size);
1962     ff_build_rac_states(c, 0.05*(1LL<<32), 256-8);
1963
1964
1965     p->pict_type= AV_PICTURE_TYPE_I; //FIXME I vs. P
1966     if(get_rac(c, &keystate)){
1967         p->key_frame= 1;
1968         f->key_frame_ok = 0;
1969         if(read_header(f) < 0)
1970             return -1;
1971         f->key_frame_ok = 1;
1972     }else{
1973         if (!f->key_frame_ok) {
1974             av_log(avctx, AV_LOG_ERROR, "Cant decode non keyframe without valid keyframe\n");
1975             return AVERROR_INVALIDDATA;
1976         }
1977         p->key_frame= 0;
1978     }
1979
1980     p->reference= 0;
1981     if(avctx->get_buffer(avctx, p) < 0){
1982         av_log(avctx, AV_LOG_ERROR, "get_buffer() failed\n");
1983         return -1;
1984     }
1985
1986     if(avctx->debug&FF_DEBUG_PICT_INFO)
1987         av_log(avctx, AV_LOG_ERROR, "keyframe:%d coder:%d\n", p->key_frame, f->ac);
1988
1989     buf_p= buf + buf_size;
1990     for(i=f->slice_count-1; i>=0; i--){
1991         FFV1Context *fs= f->slice_context[i];
1992         int trailer = 3 + 5*!!f->ec;
1993         int v;
1994
1995         if(i || f->version>2) v = AV_RB24(buf_p-trailer)+trailer;
1996         else                  v = buf_p - c->bytestream_start;
1997         if(buf_p - c->bytestream_start < v){
1998             av_log(avctx, AV_LOG_ERROR, "Slice pointer chain broken\n");
1999             return -1;
2000         }
2001         buf_p -= v;
2002
2003         if(f->ec){
2004             unsigned crc = av_crc(av_crc_get_table(AV_CRC_32_IEEE), 0, buf_p, v);
2005             if(crc){
2006                 av_log(f->avctx, AV_LOG_ERROR, "CRC mismatch %X!\n", crc);
2007             }
2008         }
2009
2010         if(i){
2011             ff_init_range_decoder(&fs->c, buf_p, v);
2012         }
2013     }
2014
2015     avctx->execute(avctx, decode_slice, &f->slice_context[0], NULL, f->slice_count, sizeof(void*));
2016     f->picture_number++;
2017
2018     *picture= *p;
2019     *data_size = sizeof(AVFrame);
2020
2021     return buf_size;
2022 }
2023
2024 AVCodec ff_ffv1_decoder = {
2025     .name           = "ffv1",
2026     .type           = AVMEDIA_TYPE_VIDEO,
2027     .id             = CODEC_ID_FFV1,
2028     .priv_data_size = sizeof(FFV1Context),
2029     .init           = decode_init,
2030     .close          = common_end,
2031     .decode         = decode_frame,
2032     .capabilities   = CODEC_CAP_DR1 /*| CODEC_CAP_DRAW_HORIZ_BAND*/ |
2033                       CODEC_CAP_SLICE_THREADS,
2034     .long_name      = NULL_IF_CONFIG_SMALL("FFmpeg video codec #1"),
2035 };
2036
2037 #if CONFIG_FFV1_ENCODER
2038
2039 #define OFFSET(x) offsetof(FFV1Context, x)
2040 #define VE AV_OPT_FLAG_VIDEO_PARAM | AV_OPT_FLAG_ENCODING_PARAM
2041 static const AVOption options[] = {
2042     { "slicecrc",        "Protect slices with CRCs",               OFFSET(ec),              AV_OPT_TYPE_INT, {-1}, -1, 1, VE},
2043 {NULL}
2044 };
2045
2046 static const AVClass class = {
2047     .class_name = "ffv1 encoder",
2048     .item_name  = av_default_item_name,
2049     .option     = options,
2050     .version    = LIBAVUTIL_VERSION_INT,
2051 };
2052
2053 AVCodec ff_ffv1_encoder = {
2054     .name           = "ffv1",
2055     .type           = AVMEDIA_TYPE_VIDEO,
2056     .id             = CODEC_ID_FFV1,
2057     .priv_data_size = sizeof(FFV1Context),
2058     .init           = encode_init,
2059     .encode2        = encode_frame,
2060     .close          = common_end,
2061     .capabilities   = CODEC_CAP_SLICE_THREADS,
2062     .pix_fmts= (const enum PixelFormat[]){PIX_FMT_YUV420P, PIX_FMT_YUVA420P, PIX_FMT_YUV444P, PIX_FMT_YUVA444P, PIX_FMT_YUV440P, PIX_FMT_YUV422P, PIX_FMT_YUV411P, PIX_FMT_YUV410P, PIX_FMT_0RGB32, PIX_FMT_RGB32, PIX_FMT_YUV420P16, PIX_FMT_YUV422P16, PIX_FMT_YUV444P16, PIX_FMT_YUV444P9, PIX_FMT_YUV422P9, PIX_FMT_YUV420P9, PIX_FMT_YUV420P10, PIX_FMT_YUV422P10, PIX_FMT_YUV444P10, PIX_FMT_GRAY16, PIX_FMT_GRAY8, PIX_FMT_NONE},
2063     .long_name      = NULL_IF_CONFIG_SMALL("FFmpeg video codec #1"),
2064     .priv_class     = &class,
2065 };
2066 #endif