git.sesse.net Git - ffmpeg/blob - libavcodec/ffv1.c

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