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