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