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     const int ps= (c->bits_per_raw_sample>8)+1;
1150
1151     if(f->colorspace==0){
1152         const int chroma_width = -((-width )>>f->chroma_h_shift);
1153         const int chroma_height= -((-height)>>f->chroma_v_shift);
1154         const int cx= x>>f->chroma_h_shift;
1155         const int cy= y>>f->chroma_v_shift;
1156
1157         encode_plane(fs, p->data[0] + ps*x + y*p->linesize[0], width, height, p->linesize[0], 0);
1158
1159         encode_plane(fs, p->data[1] + ps*cx+cy*p->linesize[1], chroma_width, chroma_height, p->linesize[1], 1);
1160         encode_plane(fs, p->data[2] + ps*cx+cy*p->linesize[2], chroma_width, chroma_height, p->linesize[2], 1);
1161     }else{
1162         encode_rgb_frame(fs, (uint32_t*)(p->data[0]) + ps*x + y*(p->linesize[0]/4), width, height, p->linesize[0]/4);
1163     }
1164     emms_c();
1165
1166     return 0;
1167 }
1168
1169 static int encode_frame(AVCodecContext *avctx, unsigned char *buf, int buf_size, void *data){
1170     FFV1Context *f = avctx->priv_data;
1171     RangeCoder * const c= &f->slice_context[0]->c;
1172     AVFrame *pict = data;
1173     AVFrame * const p= &f->picture;
1174     int used_count= 0;
1175     uint8_t keystate=128;
1176     uint8_t *buf_p;
1177     int i;
1178
1179     ff_init_range_encoder(c, buf, buf_size);
1180     ff_build_rac_states(c, 0.05*(1LL<<32), 256-8);
1181
1182     *p = *pict;
1183     p->pict_type= AV_PICTURE_TYPE_I;
1184
1185     if(avctx->gop_size==0 || f->picture_number % avctx->gop_size == 0){
1186         put_rac(c, &keystate, 1);
1187         p->key_frame= 1;
1188         f->gob_count++;
1189         write_header(f);
1190         clear_state(f);
1191     }else{
1192         put_rac(c, &keystate, 0);
1193         p->key_frame= 0;
1194     }
1195
1196     if(!f->ac){
1197         used_count += ff_rac_terminate(c);
1198 //printf("pos=%d\n", used_count);
1199         init_put_bits(&f->slice_context[0]->pb, buf + used_count, buf_size - used_count);
1200     }else if (f->ac>1){
1201         int i;
1202         for(i=1; i<256; i++){
1203             c->one_state[i]= f->state_transition[i];
1204             c->zero_state[256-i]= 256-c->one_state[i];
1205         }
1206     }
1207
1208     for(i=1; i<f->slice_count; i++){
1209         FFV1Context *fs= f->slice_context[i];
1210         uint8_t *start= buf + (buf_size-used_count)*i/f->slice_count;
1211         int len= buf_size/f->slice_count;
1212
1213         if(fs->ac){
1214             ff_init_range_encoder(&fs->c, start, len);
1215         }else{
1216             init_put_bits(&fs->pb, start, len);
1217         }
1218     }
1219     avctx->execute(avctx, encode_slice, &f->slice_context[0], NULL, f->slice_count, sizeof(void*));
1220
1221     buf_p=buf;
1222     for(i=0; i<f->slice_count; i++){
1223         FFV1Context *fs= f->slice_context[i];
1224         int bytes;
1225
1226         if(fs->ac){
1227             uint8_t state=128;
1228             put_rac(&fs->c, &state, 0);
1229             bytes= ff_rac_terminate(&fs->c);
1230         }else{
1231             flush_put_bits(&fs->pb); //nicer padding FIXME
1232             bytes= used_count + (put_bits_count(&fs->pb)+7)/8;
1233             used_count= 0;
1234         }
1235         if(i>0){
1236             av_assert0(bytes < buf_size/f->slice_count);
1237             memmove(buf_p, fs->ac ? fs->c.bytestream_start : fs->pb.buf, bytes);
1238             av_assert0(bytes < (1<<24));
1239             AV_WB24(buf_p+bytes, bytes);
1240             bytes+=3;
1241         }
1242         buf_p += bytes;
1243     }
1244
1245     if((avctx->flags&CODEC_FLAG_PASS1) && (f->picture_number&31)==0){
1246         int j, k, m;
1247         char *p= avctx->stats_out;
1248         char *end= p + STATS_OUT_SIZE;
1249
1250         memset(f->rc_stat, 0, sizeof(f->rc_stat));
1251         for(i=0; i<f->quant_table_count; i++)
1252             memset(f->rc_stat2[i], 0, f->context_count[i]*sizeof(*f->rc_stat2[i]));
1253
1254         for(j=0; j<f->slice_count; j++){
1255             FFV1Context *fs= f->slice_context[j];
1256             for(i=0; i<256; i++){
1257                 f->rc_stat[i][0] += fs->rc_stat[i][0];
1258                 f->rc_stat[i][1] += fs->rc_stat[i][1];
1259             }
1260             for(i=0; i<f->quant_table_count; i++){
1261                 for(k=0; k<f->context_count[i]; k++){
1262                     for(m=0; m<32; m++){
1263                         f->rc_stat2[i][k][m][0] += fs->rc_stat2[i][k][m][0];
1264                         f->rc_stat2[i][k][m][1] += fs->rc_stat2[i][k][m][1];
1265                     }
1266                 }
1267             }
1268         }
1269
1270         for(j=0; j<256; j++){
1271             snprintf(p, end-p, "%"PRIu64" %"PRIu64" ", f->rc_stat[j][0], f->rc_stat[j][1]);
1272             p+= strlen(p);
1273         }
1274         snprintf(p, end-p, "\n");
1275
1276         for(i=0; i<f->quant_table_count; i++){
1277             for(j=0; j<f->context_count[i]; j++){
1278                 for(m=0; m<32; m++){
1279                     snprintf(p, end-p, "%"PRIu64" %"PRIu64" ", f->rc_stat2[i][j][m][0], f->rc_stat2[i][j][m][1]);
1280                     p+= strlen(p);
1281                 }
1282             }
1283         }
1284         snprintf(p, end-p, "%d\n", f->gob_count);
1285     } else if(avctx->flags&CODEC_FLAG_PASS1)
1286         avctx->stats_out[0] = '\0';
1287
1288     f->picture_number++;
1289     return buf_p-buf;
1290 }
1291 #endif /* CONFIG_FFV1_ENCODER */
1292
1293 static av_cold int common_end(AVCodecContext *avctx){
1294     FFV1Context *s = avctx->priv_data;
1295     int i, j;
1296
1297     if (avctx->codec->decode && s->picture.data[0])
1298         avctx->release_buffer(avctx, &s->picture);
1299
1300     for(j=0; j<s->slice_count; j++){
1301         FFV1Context *fs= s->slice_context[j];
1302         for(i=0; i<s->plane_count; i++){
1303             PlaneContext *p= &fs->plane[i];
1304
1305             av_freep(&p->state);
1306             av_freep(&p->vlc_state);
1307         }
1308         av_freep(&fs->sample_buffer);
1309     }
1310
1311     av_freep(&avctx->stats_out);
1312     for(j=0; j<s->quant_table_count; j++){
1313         av_freep(&s->initial_states[j]);
1314         for(i=0; i<s->slice_count; i++){
1315             FFV1Context *sf= s->slice_context[i];
1316             av_freep(&sf->rc_stat2[j]);
1317         }
1318         av_freep(&s->rc_stat2[j]);
1319     }
1320
1321     for(i=0; i<s->slice_count; i++){
1322         av_freep(&s->slice_context[i]);
1323     }
1324
1325     return 0;
1326 }
1327
1328 static av_always_inline void decode_line(FFV1Context *s, int w,
1329                                          int16_t *sample[2],
1330                                          int plane_index, int bits)
1331 {
1332     PlaneContext * const p= &s->plane[plane_index];
1333     RangeCoder * const c= &s->c;
1334     int x;
1335     int run_count=0;
1336     int run_mode=0;
1337     int run_index= s->run_index;
1338
1339     for(x=0; x<w; x++){
1340         int diff, context, sign;
1341
1342         context= get_context(p, sample[1] + x, sample[0] + x, sample[1] + x);
1343         if(context < 0){
1344             context= -context;
1345             sign=1;
1346         }else
1347             sign=0;
1348
1349         av_assert2(context < p->context_count);
1350
1351         if(s->ac){
1352             diff= get_symbol_inline(c, p->state[context], 1);
1353         }else{
1354             if(context == 0 && run_mode==0) run_mode=1;
1355
1356             if(run_mode){
1357                 if(run_count==0 && run_mode==1){
1358                     if(get_bits1(&s->gb)){
1359                         run_count = 1<<ff_log2_run[run_index];
1360                         if(x + run_count <= w) run_index++;
1361                     }else{
1362                         if(ff_log2_run[run_index]) run_count = get_bits(&s->gb, ff_log2_run[run_index]);
1363                         else run_count=0;
1364                         if(run_index) run_index--;
1365                         run_mode=2;
1366                     }
1367                 }
1368                 run_count--;
1369                 if(run_count < 0){
1370                     run_mode=0;
1371                     run_count=0;
1372                     diff= get_vlc_symbol(&s->gb, &p->vlc_state[context], bits);
1373                     if(diff>=0) diff++;
1374                 }else
1375                     diff=0;
1376             }else
1377                 diff= get_vlc_symbol(&s->gb, &p->vlc_state[context], bits);
1378
1379 //            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));
1380         }
1381
1382         if(sign) diff= -diff;
1383
1384         sample[1][x]= (predict(sample[1] + x, sample[0] + x) + diff) & ((1<<bits)-1);
1385     }
1386     s->run_index= run_index;
1387 }
1388
1389 static void decode_plane(FFV1Context *s, uint8_t *src, int w, int h, int stride, int plane_index){
1390     int x, y;
1391     int16_t *sample[2];
1392     sample[0]=s->sample_buffer    +3;
1393     sample[1]=s->sample_buffer+w+6+3;
1394
1395     s->run_index=0;
1396
1397     memset(s->sample_buffer, 0, 2*(w+6)*sizeof(*s->sample_buffer));
1398
1399     for(y=0; y<h; y++){
1400         int16_t *temp = sample[0]; //FIXME try a normal buffer
1401
1402         sample[0]= sample[1];
1403         sample[1]= temp;
1404
1405         sample[1][-1]= sample[0][0  ];
1406         sample[0][ w]= sample[0][w-1];
1407
1408 //{START_TIMER
1409         if(s->avctx->bits_per_raw_sample <= 8){
1410             decode_line(s, w, sample, plane_index, 8);
1411             for(x=0; x<w; x++){
1412                 src[x + stride*y]= sample[1][x];
1413             }
1414         }else{
1415             decode_line(s, w, sample, plane_index, s->avctx->bits_per_raw_sample);
1416             if(s->packed_at_lsb){
1417                 for(x=0; x<w; x++){
1418                     ((uint16_t*)(src + stride*y))[x]= sample[1][x];
1419                 }
1420             }else{
1421                 for(x=0; x<w; x++){
1422                     ((uint16_t*)(src + stride*y))[x]= sample[1][x] << (16 - s->avctx->bits_per_raw_sample);
1423                 }
1424             }
1425         }
1426 //STOP_TIMER("decode-line")}
1427     }
1428 }
1429
1430 static void decode_rgb_frame(FFV1Context *s, uint32_t *src, int w, int h, int stride){
1431     int x, y, p;
1432     int16_t *sample[3][2];
1433     for(x=0; x<3; x++){
1434         sample[x][0] = s->sample_buffer +  x*2   *(w+6) + 3;
1435         sample[x][1] = s->sample_buffer + (x*2+1)*(w+6) + 3;
1436     }
1437
1438     s->run_index=0;
1439
1440     memset(s->sample_buffer, 0, 6*(w+6)*sizeof(*s->sample_buffer));
1441
1442     for(y=0; y<h; y++){
1443         for(p=0; p<3; p++){
1444             int16_t *temp = sample[p][0]; //FIXME try a normal buffer
1445
1446             sample[p][0]= sample[p][1];
1447             sample[p][1]= temp;
1448
1449             sample[p][1][-1]= sample[p][0][0  ];
1450             sample[p][0][ w]= sample[p][0][w-1];
1451             decode_line(s, w, sample[p], FFMIN(p, 1), 9);
1452         }
1453         for(x=0; x<w; x++){
1454             int g= sample[0][1][x];
1455             int b= sample[1][1][x];
1456             int r= sample[2][1][x];
1457
1458 //            assert(g>=0 && b>=0 && r>=0);
1459 //            assert(g<256 && b<512 && r<512);
1460
1461             b -= 0x100;
1462             r -= 0x100;
1463             g -= (b + r)>>2;
1464             b += g;
1465             r += g;
1466
1467             src[x + stride*y]= b + (g<<8) + (r<<16) + (0xFF<<24);
1468         }
1469     }
1470 }
1471
1472 static int decode_slice(AVCodecContext *c, void *arg){
1473     FFV1Context *fs= *(void**)arg;
1474     FFV1Context *f= fs->avctx->priv_data;
1475     int width = fs->slice_width;
1476     int height= fs->slice_height;
1477     int x= fs->slice_x;
1478     int y= fs->slice_y;
1479     const int ps= (c->bits_per_raw_sample>8)+1;
1480     AVFrame * const p= &f->picture;
1481
1482     av_assert1(width && height);
1483     if(f->colorspace==0){
1484         const int chroma_width = -((-width )>>f->chroma_h_shift);
1485         const int chroma_height= -((-height)>>f->chroma_v_shift);
1486         const int cx= x>>f->chroma_h_shift;
1487         const int cy= y>>f->chroma_v_shift;
1488         decode_plane(fs, p->data[0] + ps*x + y*p->linesize[0], width, height, p->linesize[0], 0);
1489
1490         decode_plane(fs, p->data[1] + ps*cx+cy*p->linesize[1], chroma_width, chroma_height, p->linesize[1], 1);
1491         decode_plane(fs, p->data[2] + ps*cx+cy*p->linesize[1], chroma_width, chroma_height, p->linesize[2], 1);
1492     }else{
1493         decode_rgb_frame(fs, (uint32_t*)p->data[0] + ps*x + y*(p->linesize[0]/4), width, height, p->linesize[0]/4);
1494     }
1495
1496     emms_c();
1497
1498     return 0;
1499 }
1500
1501 static int read_quant_table(RangeCoder *c, int16_t *quant_table, int scale){
1502     int v;
1503     int i=0;
1504     uint8_t state[CONTEXT_SIZE];
1505
1506     memset(state, 128, sizeof(state));
1507
1508     for(v=0; i<128 ; v++){
1509         int len= get_symbol(c, state, 0) + 1;
1510
1511         if(len + i > 128) return -1;
1512
1513         while(len--){
1514             quant_table[i] = scale*v;
1515             i++;
1516 //printf("%2d ",v);
1517 //if(i%16==0) printf("\n");
1518         }
1519     }
1520
1521     for(i=1; i<128; i++){
1522         quant_table[256-i]= -quant_table[i];
1523     }
1524     quant_table[128]= -quant_table[127];
1525
1526     return 2*v - 1;
1527 }
1528
1529 static int read_quant_tables(RangeCoder *c, int16_t quant_table[MAX_CONTEXT_INPUTS][256]){
1530     int i;
1531     int context_count=1;
1532
1533     for(i=0; i<5; i++){
1534         context_count*= read_quant_table(c, quant_table[i], context_count);
1535         if(context_count > 32768U){
1536             return -1;
1537         }
1538     }
1539     return (context_count+1)/2;
1540 }
1541
1542 static int read_extra_header(FFV1Context *f){
1543     RangeCoder * const c= &f->c;
1544     uint8_t state[CONTEXT_SIZE];
1545     int i, j, k;
1546     uint8_t state2[32][CONTEXT_SIZE];
1547
1548     memset(state2, 128, sizeof(state2));
1549     memset(state, 128, sizeof(state));
1550
1551     ff_init_range_decoder(c, f->avctx->extradata, f->avctx->extradata_size);
1552     ff_build_rac_states(c, 0.05*(1LL<<32), 256-8);
1553
1554     f->version= get_symbol(c, state, 0);
1555     f->ac= f->avctx->coder_type= get_symbol(c, state, 0);
1556     if(f->ac>1){
1557         for(i=1; i<256; i++){
1558             f->state_transition[i]= get_symbol(c, state, 1) + c->one_state[i];
1559         }
1560     }
1561     f->colorspace= get_symbol(c, state, 0); //YUV cs type
1562     f->avctx->bits_per_raw_sample= get_symbol(c, state, 0);
1563     get_rac(c, state); //no chroma = false
1564     f->chroma_h_shift= get_symbol(c, state, 0);
1565     f->chroma_v_shift= get_symbol(c, state, 0);
1566     get_rac(c, state); //transparency plane
1567     f->plane_count= 2;
1568     f->num_h_slices= 1 + get_symbol(c, state, 0);
1569     f->num_v_slices= 1 + get_symbol(c, state, 0);
1570     if(f->num_h_slices > (unsigned)f->width || f->num_v_slices > (unsigned)f->height){
1571         av_log(f->avctx, AV_LOG_ERROR, "too many slices\n");
1572         return -1;
1573     }
1574
1575     f->quant_table_count= get_symbol(c, state, 0);
1576     if(f->quant_table_count > (unsigned)MAX_QUANT_TABLES)
1577         return -1;
1578     for(i=0; i<f->quant_table_count; i++){
1579         if((f->context_count[i]= read_quant_tables(c, f->quant_tables[i])) < 0){
1580             av_log(f->avctx, AV_LOG_ERROR, "read_quant_table error\n");
1581             return -1;
1582         }
1583     }
1584
1585     if(allocate_initial_states(f) < 0)
1586         return AVERROR(ENOMEM);
1587
1588     for(i=0; i<f->quant_table_count; i++){
1589         if(get_rac(c, state)){
1590             for(j=0; j<f->context_count[i]; j++){
1591                 for(k=0; k<CONTEXT_SIZE; k++){
1592                     int pred= j ? f->initial_states[i][j-1][k] : 128;
1593                     f->initial_states[i][j][k]= (pred+get_symbol(c, state2[k], 1))&0xFF;
1594                 }
1595             }
1596         }
1597     }
1598
1599     return 0;
1600 }
1601
1602 static int read_header(FFV1Context *f){
1603     uint8_t state[CONTEXT_SIZE];
1604     int i, j, context_count;
1605     RangeCoder * const c= &f->slice_context[0]->c;
1606
1607     memset(state, 128, sizeof(state));
1608
1609     if(f->version < 2){
1610         f->version= get_symbol(c, state, 0);
1611         f->ac= f->avctx->coder_type= get_symbol(c, state, 0);
1612         if(f->ac>1){
1613             for(i=1; i<256; i++){
1614                 f->state_transition[i]= get_symbol(c, state, 1) + c->one_state[i];
1615             }
1616         }
1617         f->colorspace= get_symbol(c, state, 0); //YUV cs type
1618         if(f->version>0)
1619             f->avctx->bits_per_raw_sample= get_symbol(c, state, 0);
1620         get_rac(c, state); //no chroma = false
1621         f->chroma_h_shift= get_symbol(c, state, 0);
1622         f->chroma_v_shift= get_symbol(c, state, 0);
1623         get_rac(c, state); //transparency plane
1624         f->plane_count= 2;
1625     }
1626
1627     if(f->colorspace==0){
1628         if(f->avctx->bits_per_raw_sample<=8){
1629             switch(16*f->chroma_h_shift + f->chroma_v_shift){
1630             case 0x00: f->avctx->pix_fmt= PIX_FMT_YUV444P; break;
1631             case 0x10: f->avctx->pix_fmt= PIX_FMT_YUV422P; break;
1632             case 0x11: f->avctx->pix_fmt= PIX_FMT_YUV420P; break;
1633             case 0x20: f->avctx->pix_fmt= PIX_FMT_YUV411P; break;
1634             case 0x22: f->avctx->pix_fmt= PIX_FMT_YUV410P; break;
1635             default:
1636                 av_log(f->avctx, AV_LOG_ERROR, "format not supported\n");
1637                 return -1;
1638             }
1639         }else if(f->avctx->bits_per_raw_sample==9) {
1640             switch(16*f->chroma_h_shift + f->chroma_v_shift){
1641             case 0x00: f->avctx->pix_fmt= PIX_FMT_YUV444P16; break;
1642             case 0x10: f->avctx->pix_fmt= PIX_FMT_YUV422P16; break;
1643             case 0x11: f->avctx->pix_fmt= PIX_FMT_YUV420P9 ; f->packed_at_lsb=1; break;
1644             default:
1645                 av_log(f->avctx, AV_LOG_ERROR, "format not supported\n");
1646                 return -1;
1647             }
1648         }else if(f->avctx->bits_per_raw_sample==10) {
1649             switch(16*f->chroma_h_shift + f->chroma_v_shift){
1650             case 0x00: f->avctx->pix_fmt= PIX_FMT_YUV444P16; break;
1651             case 0x10: f->avctx->pix_fmt= PIX_FMT_YUV422P10; f->packed_at_lsb=1; break;
1652             case 0x11: f->avctx->pix_fmt= PIX_FMT_YUV420P10; f->packed_at_lsb=1; break;
1653             default:
1654                 av_log(f->avctx, AV_LOG_ERROR, "format not supported\n");
1655                 return -1;
1656             }
1657         }else {
1658             switch(16*f->chroma_h_shift + f->chroma_v_shift){
1659             case 0x00: f->avctx->pix_fmt= PIX_FMT_YUV444P16; break;
1660             case 0x10: f->avctx->pix_fmt= PIX_FMT_YUV422P16; break;
1661             case 0x11: f->avctx->pix_fmt= PIX_FMT_YUV420P16; break;
1662             default:
1663                 av_log(f->avctx, AV_LOG_ERROR, "format not supported\n");
1664                 return -1;
1665             }
1666         }
1667     }else if(f->colorspace==1){
1668         if(f->chroma_h_shift || f->chroma_v_shift){
1669             av_log(f->avctx, AV_LOG_ERROR, "chroma subsampling not supported in this colorspace\n");
1670             return -1;
1671         }
1672         f->avctx->pix_fmt= PIX_FMT_RGB32;
1673     }else{
1674         av_log(f->avctx, AV_LOG_ERROR, "colorspace not supported\n");
1675         return -1;
1676     }
1677
1678 //printf("%d %d %d\n", f->chroma_h_shift, f->chroma_v_shift,f->avctx->pix_fmt);
1679     if(f->version < 2){
1680         context_count= read_quant_tables(c, f->quant_table);
1681         if(context_count < 0){
1682                 av_log(f->avctx, AV_LOG_ERROR, "read_quant_table error\n");
1683                 return -1;
1684         }
1685     }else{
1686         f->slice_count= get_symbol(c, state, 0);
1687         if(f->slice_count > (unsigned)MAX_SLICES)
1688             return -1;
1689     }
1690
1691     for(j=0; j<f->slice_count; j++){
1692         FFV1Context *fs= f->slice_context[j];
1693         fs->ac= f->ac;
1694         fs->packed_at_lsb= f->packed_at_lsb;
1695
1696         if(f->version >= 2){
1697             fs->slice_x     = get_symbol(c, state, 0)   *f->width ;
1698             fs->slice_y     = get_symbol(c, state, 0)   *f->height;
1699             fs->slice_width =(get_symbol(c, state, 0)+1)*f->width  + fs->slice_x;
1700             fs->slice_height=(get_symbol(c, state, 0)+1)*f->height + fs->slice_y;
1701
1702             fs->slice_x /= f->num_h_slices;
1703             fs->slice_y /= f->num_v_slices;
1704             fs->slice_width  = fs->slice_width /f->num_h_slices - fs->slice_x;
1705             fs->slice_height = fs->slice_height/f->num_v_slices - fs->slice_y;
1706             if((unsigned)fs->slice_width > f->width || (unsigned)fs->slice_height > f->height)
1707                 return -1;
1708             if(    (unsigned)fs->slice_x + (uint64_t)fs->slice_width  > f->width
1709                 || (unsigned)fs->slice_y + (uint64_t)fs->slice_height > f->height)
1710                 return -1;
1711         }
1712
1713         for(i=0; i<f->plane_count; i++){
1714             PlaneContext * const p= &fs->plane[i];
1715
1716             if(f->version >= 2){
1717                 int idx=get_symbol(c, state, 0);
1718                 if(idx > (unsigned)f->quant_table_count){
1719                     av_log(f->avctx, AV_LOG_ERROR, "quant_table_index out of range\n");
1720                     return -1;
1721                 }
1722                 p->quant_table_index= idx;
1723                 memcpy(p->quant_table, f->quant_tables[idx], sizeof(p->quant_table));
1724                 context_count= f->context_count[idx];
1725             }else{
1726                 memcpy(p->quant_table, f->quant_table, sizeof(p->quant_table));
1727             }
1728
1729             if(p->context_count < context_count){
1730                 av_freep(&p->state);
1731                 av_freep(&p->vlc_state);
1732             }
1733             p->context_count= context_count;
1734         }
1735     }
1736
1737     return 0;
1738 }
1739
1740 static av_cold int decode_init(AVCodecContext *avctx)
1741 {
1742     FFV1Context *f = avctx->priv_data;
1743
1744     common_init(avctx);
1745
1746     if(avctx->extradata && read_extra_header(f) < 0)
1747         return -1;
1748
1749     if(init_slice_contexts(f) < 0)
1750         return -1;
1751
1752     return 0;
1753 }
1754
1755 static int decode_frame(AVCodecContext *avctx, void *data, int *data_size, AVPacket *avpkt){
1756     const uint8_t *buf = avpkt->data;
1757     int buf_size = avpkt->size;
1758     FFV1Context *f = avctx->priv_data;
1759     RangeCoder * const c= &f->slice_context[0]->c;
1760     AVFrame * const p= &f->picture;
1761     int bytes_read, i;
1762     uint8_t keystate= 128;
1763     const uint8_t *buf_p;
1764
1765     AVFrame *picture = data;
1766
1767     /* release previously stored data */
1768     if (p->data[0])
1769         avctx->release_buffer(avctx, p);
1770
1771     ff_init_range_decoder(c, buf, buf_size);
1772     ff_build_rac_states(c, 0.05*(1LL<<32), 256-8);
1773
1774
1775     p->pict_type= AV_PICTURE_TYPE_I; //FIXME I vs. P
1776     if(get_rac(c, &keystate)){
1777         p->key_frame= 1;
1778         if(read_header(f) < 0)
1779             return -1;
1780         if(init_slice_state(f) < 0)
1781             return -1;
1782
1783         clear_state(f);
1784     }else{
1785         p->key_frame= 0;
1786     }
1787     if(f->ac>1){
1788         int i;
1789         for(i=1; i<256; i++){
1790             c->one_state[i]= f->state_transition[i];
1791             c->zero_state[256-i]= 256-c->one_state[i];
1792         }
1793     }
1794
1795     p->reference= 0;
1796     if(avctx->get_buffer(avctx, p) < 0){
1797         av_log(avctx, AV_LOG_ERROR, "get_buffer() failed\n");
1798         return -1;
1799     }
1800
1801     if(avctx->debug&FF_DEBUG_PICT_INFO)
1802         av_log(avctx, AV_LOG_ERROR, "keyframe:%d coder:%d\n", p->key_frame, f->ac);
1803
1804     if(!f->ac){
1805         bytes_read = c->bytestream - c->bytestream_start - 1;
1806         if(bytes_read ==0) av_log(avctx, AV_LOG_ERROR, "error at end of AC stream\n"); //FIXME
1807 //printf("pos=%d\n", bytes_read);
1808         init_get_bits(&f->slice_context[0]->gb, buf + bytes_read, buf_size - bytes_read);
1809     } else {
1810         bytes_read = 0; /* avoid warning */
1811     }
1812
1813     buf_p= buf + buf_size;
1814     for(i=f->slice_count-1; i>0; i--){
1815         FFV1Context *fs= f->slice_context[i];
1816         int v= AV_RB24(buf_p-3)+3;
1817         if(buf_p - buf <= v){
1818             av_log(avctx, AV_LOG_ERROR, "Slice pointer chain broken\n");
1819             return -1;
1820         }
1821         buf_p -= v;
1822         if(fs->ac){
1823             ff_init_range_decoder(&fs->c, buf_p, v);
1824         }else{
1825             init_get_bits(&fs->gb, buf_p, v);
1826         }
1827     }
1828
1829     avctx->execute(avctx, decode_slice, &f->slice_context[0], NULL, f->slice_count, sizeof(void*));
1830     f->picture_number++;
1831
1832     *picture= *p;
1833     *data_size = sizeof(AVFrame);
1834
1835     return buf_size;
1836 }
1837
1838 AVCodec ff_ffv1_decoder = {
1839     "ffv1",
1840     AVMEDIA_TYPE_VIDEO,
1841     CODEC_ID_FFV1,
1842     sizeof(FFV1Context),
1843     decode_init,
1844     NULL,
1845     common_end,
1846     decode_frame,
1847     CODEC_CAP_DR1 /*| CODEC_CAP_DRAW_HORIZ_BAND*/ | CODEC_CAP_SLICE_THREADS,
1848     NULL,
1849     .long_name= NULL_IF_CONFIG_SMALL("FFmpeg video codec #1"),
1850 };
1851
1852 #if CONFIG_FFV1_ENCODER
1853 AVCodec ff_ffv1_encoder = {
1854     "ffv1",
1855     AVMEDIA_TYPE_VIDEO,
1856     CODEC_ID_FFV1,
1857     sizeof(FFV1Context),
1858     encode_init,
1859     encode_frame,
1860     common_end,
1861     .capabilities = CODEC_CAP_SLICE_THREADS,
1862     .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},
1863     .long_name= NULL_IF_CONFIG_SMALL("FFmpeg video codec #1"),
1864 };
1865 #endif