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