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