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                 f->state_transition[i]=ver2_state[i];
 633                 put_symbol(c, state, ver2_state[i] - c->one_state[i], 1);
 634             }
 635         }
 636         put_symbol(c, state, f->colorspace, 0); //YUV cs type
 637         if(f->version>0)
 638             put_symbol(c, state, f->avctx->bits_per_raw_sample, 0);
 639         put_rac(c, state, 1); //chroma planes
 640             put_symbol(c, state, f->chroma_h_shift, 0);
 641             put_symbol(c, state, f->chroma_v_shift, 0);
 642         put_rac(c, state, 0); //no transparency plane
 643
 644         write_quant_tables(c, f->quant_table);
 645     }else{
 646         put_symbol(c, state, f->slice_count, 0);
 647         for(i=0; i<f->slice_count; i++){
 648             FFV1Context *fs= f->slice_context[i];
 649             put_symbol(c, state, (fs->slice_x     +1)*f->num_h_slices / f->width   , 0);
 650             put_symbol(c, state, (fs->slice_y     +1)*f->num_v_slices / f->height  , 0);
 651             put_symbol(c, state, (fs->slice_width +1)*f->num_h_slices / f->width -1, 0);
 652             put_symbol(c, state, (fs->slice_height+1)*f->num_v_slices / f->height-1, 0);
 653             for(j=0; j<f->plane_count; j++)
 654             put_symbol(c, state, f->avctx->context_model, 0);
 655         }
 656     }
 657 }
 658 #endif /* CONFIG_FFV1_ENCODER */
 659
 660 static av_cold int common_init(AVCodecContext *avctx){
 661     FFV1Context *s = avctx->priv_data;
 662
 663     s->avctx= avctx;
 664     s->flags= avctx->flags;
 665
 666     dsputil_init(&s->dsp, avctx);
 667
 668     s->width = avctx->width;
 669     s->height= avctx->height;
 670
 671     assert(s->width && s->height);
 672     //defaults
 673     s->num_h_slices=1;
 674     s->num_v_slices=1;
 675
 676
 677     return 0;
 678 }
 679
 680 static int init_slice_state(FFV1Context *f){
 681     int i, j;
 682
 683     for(i=0; i<f->slice_count; i++){
 684         FFV1Context *fs= f->slice_context[i];
 685         for(j=0; j<f->plane_count; j++){
 686             PlaneContext * const p= &fs->plane[j];
 687
 688             if(fs->ac){
 689                 if(!p->    state) p->    state= av_malloc(CONTEXT_SIZE*p->context_count*sizeof(uint8_t));
 690                 if(!p->    state)
 691                     return AVERROR(ENOMEM);
 692             }else{
 693                 if(!p->vlc_state) p->vlc_state= av_malloc(p->context_count*sizeof(VlcState));
 694                 if(!p->vlc_state)
 695                     return AVERROR(ENOMEM);
 696             }
 697         }
 698
 699         if (fs->ac>1){
 700             //FIXME only redo if state_transition changed
 701             for(j=1; j<256; j++){
 702                 fs->c.one_state [    j]= fs->state_transition[j];
 703                 fs->c.zero_state[256-j]= 256-fs->c.one_state [j];
 704             }
 705         }
 706     }
 707
 708     return 0;
 709 }
 710
 711 static av_cold int init_slice_contexts(FFV1Context *f){
 712     int i;
 713
 714     f->slice_count= f->num_h_slices * f->num_v_slices;
 715
 716     for(i=0; i<f->slice_count; i++){
 717         FFV1Context *fs= av_mallocz(sizeof(*fs));
 718         int sx= i % f->num_h_slices;
 719         int sy= i / f->num_h_slices;
 720         int sxs= f->avctx->width * sx    / f->num_h_slices;
 721         int sxe= f->avctx->width *(sx+1) / f->num_h_slices;
 722         int sys= f->avctx->height* sy    / f->num_v_slices;
 723         int sye= f->avctx->height*(sy+1) / f->num_v_slices;
 724         f->slice_context[i]= fs;
 725         memcpy(fs, f, sizeof(*fs));
 726
 727         fs->slice_width = sxe - sxs;
 728         fs->slice_height= sye - sys;
 729         fs->slice_x     = sxs;
 730         fs->slice_y     = sys;
 731
 732         fs->sample_buffer = av_malloc(6 * (fs->width+6) * sizeof(*fs->sample_buffer));
 733         if (!fs->sample_buffer)
 734             return AVERROR(ENOMEM);
 735     }
 736     return 0;
 737 }
 738
 739 #if CONFIG_FFV1_ENCODER
 740 static int write_extra_header(FFV1Context *f){
 741     RangeCoder * const c= &f->c;
 742     uint8_t state[CONTEXT_SIZE];
 743     int i;
 744     memset(state, 128, sizeof(state));
 745
 746     f->avctx->extradata= av_malloc(f->avctx->extradata_size= 10000);
 747     ff_init_range_encoder(c, f->avctx->extradata, f->avctx->extradata_size);
 748     ff_build_rac_states(c, 0.05*(1LL<<32), 256-8);
 749
 750     put_symbol(c, state, f->version, 0);
 751     put_symbol(c, state, f->ac, 0);
 752     if(f->ac>1){
 753         for(i=1; i<256; i++){
 754             f->state_transition[i]=ver2_state[i];
 755             put_symbol(c, state, ver2_state[i] - c->one_state[i], 1);
 756         }
 757     }
 758     put_symbol(c, state, f->colorspace, 0); //YUV cs type
 759     put_symbol(c, state, f->avctx->bits_per_raw_sample, 0);
 760     put_rac(c, state, 1); //chroma planes
 761         put_symbol(c, state, f->chroma_h_shift, 0);
 762         put_symbol(c, state, f->chroma_v_shift, 0);
 763     put_rac(c, state, 0); //no transparency plane
 764     put_symbol(c, state, f->num_h_slices-1, 0);
 765     put_symbol(c, state, f->num_v_slices-1, 0);
 766
 767     put_symbol(c, state, f->quant_table_count, 0);
 768     for(i=0; i<f->quant_table_count; i++)
 769         write_quant_tables(c, f->quant_tables[i]);
 770
 771     f->avctx->extradata_size= ff_rac_terminate(c);
 772
 773     return 0;
 774 }
 775
 776 static av_cold int encode_init(AVCodecContext *avctx)
 777 {
 778     FFV1Context *s = avctx->priv_data;
 779     int i;
 780
 781     common_init(avctx);
 782
 783     s->version=0;
 784     s->ac= avctx->coder_type ? 2:0;
 785
 786     s->plane_count=2;
 787     for(i=0; i<256; i++){
 788         s->quant_table_count=2;
 789         if(avctx->bits_per_raw_sample <=8){
 790             s->quant_tables[0][0][i]=           quant11[i];
 791             s->quant_tables[0][1][i]=        11*quant11[i];
 792             s->quant_tables[0][2][i]=     11*11*quant11[i];
 793             s->quant_tables[1][0][i]=           quant11[i];
 794             s->quant_tables[1][1][i]=        11*quant11[i];
 795             s->quant_tables[1][2][i]=     11*11*quant5 [i];
 796             s->quant_tables[1][3][i]=   5*11*11*quant5 [i];
 797             s->quant_tables[1][4][i]= 5*5*11*11*quant5 [i];
 798         }else{
 799             s->quant_tables[0][0][i]=           quant9_10bit[i];
 800             s->quant_tables[0][1][i]=        11*quant9_10bit[i];
 801             s->quant_tables[0][2][i]=     11*11*quant9_10bit[i];
 802             s->quant_tables[1][0][i]=           quant9_10bit[i];
 803             s->quant_tables[1][1][i]=        11*quant9_10bit[i];
 804             s->quant_tables[1][2][i]=     11*11*quant5_10bit[i];
 805             s->quant_tables[1][3][i]=   5*11*11*quant5_10bit[i];
 806             s->quant_tables[1][4][i]= 5*5*11*11*quant5_10bit[i];
 807         }
 808     }
 809     memcpy(s->quant_table, s->quant_tables[avctx->context_model], sizeof(s->quant_table));
 810
 811     for(i=0; i<s->plane_count; i++){
 812         PlaneContext * const p= &s->plane[i];
 813
 814         memcpy(p->quant_table, s->quant_table, sizeof(p->quant_table));
 815         if(avctx->context_model==0){
 816             p->context_count= (11*11*11+1)/2;
 817         }else{
 818             p->context_count= (11*11*5*5*5+1)/2;
 819         }
 820     }
 821
 822     avctx->coded_frame= &s->picture;
 823     switch(avctx->pix_fmt){
 824     case PIX_FMT_YUV444P16:
 825     case PIX_FMT_YUV422P16:
 826     case PIX_FMT_YUV420P16:
 827         if(avctx->bits_per_raw_sample <=8){
 828             av_log(avctx, AV_LOG_ERROR, "bits_per_raw_sample invalid\n");
 829             return -1;
 830         }
 831         if(!s->ac){
 832             av_log(avctx, AV_LOG_ERROR, "bits_per_raw_sample of more than 8 needs -coder 1 currently\n");
 833             return -1;
 834         }
 835         s->version= FFMAX(s->version, 1);
 836     case PIX_FMT_YUV444P:
 837     case PIX_FMT_YUV422P:
 838     case PIX_FMT_YUV420P:
 839     case PIX_FMT_YUV411P:
 840     case PIX_FMT_YUV410P:
 841         s->colorspace= 0;
 842         break;
 843     case PIX_FMT_RGB32:
 844         s->colorspace= 1;
 845         break;
 846     default:
 847         av_log(avctx, AV_LOG_ERROR, "format not supported\n");
 848         return -1;
 849     }
 850     avcodec_get_chroma_sub_sample(avctx->pix_fmt, &s->chroma_h_shift, &s->chroma_v_shift);
 851
 852     s->picture_number=0;
 853
 854     if(s->version>1){
 855         s->num_h_slices=2;
 856         s->num_v_slices=2;
 857         write_extra_header(s);
 858     }
 859
 860     if(init_slice_contexts(s) < 0)
 861         return -1;
 862     if(init_slice_state(s) < 0)
 863         return -1;
 864
 865     return 0;
 866 }
 867 #endif /* CONFIG_FFV1_ENCODER */
 868
 869
 870 static void clear_state(FFV1Context *f){
 871     int i, si, j;
 872
 873     for(si=0; si<f->slice_count; si++){
 874         FFV1Context *fs= f->slice_context[si];
 875         for(i=0; i<f->plane_count; i++){
 876             PlaneContext *p= &fs->plane[i];
 877
 878             p->interlace_bit_state[0]= 128;
 879             p->interlace_bit_state[1]= 128;
 880
 881             for(j=0; j<p->context_count; j++){
 882                 if(fs->ac){
 883                     memset(p->state[j], 128, sizeof(uint8_t)*CONTEXT_SIZE);
 884                 }else{
 885                     p->vlc_state[j].drift= 0;
 886                     p->vlc_state[j].error_sum= 4; //FFMAX((RANGE + 32)/64, 2);
 887                     p->vlc_state[j].bias= 0;
 888                     p->vlc_state[j].count= 1;
 889                 }
 890             }
 891         }
 892     }
 893 }
 894
 895 #if CONFIG_FFV1_ENCODER
 896 static int encode_slice(AVCodecContext *c, void *arg){
 897     FFV1Context *fs= *(void**)arg;
 898     FFV1Context *f= fs->avctx->priv_data;
 899     int width = fs->slice_width;
 900     int height= fs->slice_height;
 901     int x= fs->slice_x;
 902     int y= fs->slice_y;
 903     AVFrame * const p= &f->picture;
 904
 905     if(f->colorspace==0){
 906         const int chroma_width = -((-width )>>f->chroma_h_shift);
 907         const int chroma_height= -((-height)>>f->chroma_v_shift);
 908         const int cx= x>>f->chroma_h_shift;
 909         const int cy= y>>f->chroma_v_shift;
 910
 911         encode_plane(fs, p->data[0] + x + y*p->linesize[0], width, height, p->linesize[0], 0);
 912
 913         encode_plane(fs, p->data[1] + cx+cy*p->linesize[1], chroma_width, chroma_height, p->linesize[1], 1);
 914         encode_plane(fs, p->data[2] + cx+cy*p->linesize[2], chroma_width, chroma_height, p->linesize[2], 1);
 915     }else{
 916         encode_rgb_frame(fs, (uint32_t*)(p->data[0]) + x + y*(p->linesize[0]/4), width, height, p->linesize[0]/4);
 917     }
 918     emms_c();
 919
 920     return 0;
 921 }
 922
 923 static int encode_frame(AVCodecContext *avctx, unsigned char *buf, int buf_size, void *data){
 924     FFV1Context *f = avctx->priv_data;
 925     RangeCoder * const c= &f->slice_context[0]->c;
 926     AVFrame *pict = data;
 927     AVFrame * const p= &f->picture;
 928     int used_count= 0;
 929     uint8_t keystate=128;
 930     uint8_t *buf_p;
 931     int i;
 932
 933     ff_init_range_encoder(c, buf, buf_size);
 934     ff_build_rac_states(c, 0.05*(1LL<<32), 256-8);
 935
 936     *p = *pict;
 937     p->pict_type= FF_I_TYPE;
 938
 939     if(avctx->gop_size==0 || f->picture_number % avctx->gop_size == 0){
 940         put_rac(c, &keystate, 1);
 941         p->key_frame= 1;
 942         write_header(f);
 943         clear_state(f);
 944     }else{
 945         put_rac(c, &keystate, 0);
 946         p->key_frame= 0;
 947     }
 948
 949     if(!f->ac){
 950         used_count += ff_rac_terminate(c);
 951 //printf("pos=%d\n", used_count);
 952         init_put_bits(&f->slice_context[0]->pb, buf + used_count, buf_size - used_count);
 953     }else if (f->ac>1){
 954         int i;
 955         for(i=1; i<256; i++){
 956             c->one_state[i]= f->state_transition[i];
 957             c->zero_state[256-i]= 256-c->one_state[i];
 958         }
 959     }
 960
 961     for(i=1; i<f->slice_count; i++){
 962         FFV1Context *fs= f->slice_context[i];
 963         uint8_t *start= buf + (buf_size-used_count)*i/f->slice_count;
 964         int len= buf_size/f->slice_count;
 965
 966         if(fs->ac){
 967             ff_init_range_encoder(&fs->c, start, len);
 968         }else{
 969             init_put_bits(&fs->pb, start, len);
 970         }
 971     }
 972     avctx->execute(avctx, encode_slice, &f->slice_context[0], NULL, f->slice_count, sizeof(void*));
 973
 974     buf_p=buf;
 975     for(i=0; i<f->slice_count; i++){
 976         FFV1Context *fs= f->slice_context[i];
 977         int bytes;
 978
 979         if(fs->ac){
 980             uint8_t state=128;
 981             put_rac(&fs->c, &state, 0);
 982             bytes= ff_rac_terminate(&fs->c);
 983         }else{
 984             flush_put_bits(&fs->pb); //nicer padding FIXME
 985             bytes= used_count + (put_bits_count(&fs->pb)+7)/8;
 986             used_count= 0;
 987         }
 988         if(i>0){
 989             av_assert0(bytes < buf_size/f->slice_count);
 990             memmove(buf_p, fs->ac ? fs->c.bytestream_start : fs->pb.buf, bytes);
 991             av_assert0(bytes < (1<<24));
 992             AV_WB24(buf_p+bytes, bytes);
 993             bytes+=3;
 994         }
 995         buf_p += bytes;
 996     }
 997
 998     f->picture_number++;
 999     return buf_p-buf;
1000 }
1001 #endif /* CONFIG_FFV1_ENCODER */
1002
1003 static av_cold int common_end(AVCodecContext *avctx){
1004     FFV1Context *s = avctx->priv_data;
1005     int i, j;
1006
1007     for(j=0; j<s->slice_count; j++){
1008         FFV1Context *fs= s->slice_context[j];
1009         for(i=0; i<s->plane_count; i++){
1010             PlaneContext *p= &fs->plane[i];
1011
1012             av_freep(&p->state);
1013             av_freep(&p->vlc_state);
1014         }
1015         av_freep(&fs->sample_buffer);
1016     }
1017
1018     return 0;
1019 }
1020
1021 static av_always_inline void decode_line(FFV1Context *s, int w, int_fast16_t *sample[2], int plane_index, int bits){
1022     PlaneContext * const p= &s->plane[plane_index];
1023     RangeCoder * const c= &s->c;
1024     int x;
1025     int run_count=0;
1026     int run_mode=0;
1027     int run_index= s->run_index;
1028
1029     for(x=0; x<w; x++){
1030         int diff, context, sign;
1031
1032         context= get_context(p, sample[1] + x, sample[0] + x, sample[1] + x);
1033         if(context < 0){
1034             context= -context;
1035             sign=1;
1036         }else
1037             sign=0;
1038
1039         av_assert2(context < p->context_count);
1040
1041         if(s->ac){
1042             diff= get_symbol_inline(c, p->state[context], 1);
1043         }else{
1044             if(context == 0 && run_mode==0) run_mode=1;
1045
1046             if(run_mode){
1047                 if(run_count==0 && run_mode==1){
1048                     if(get_bits1(&s->gb)){
1049                         run_count = 1<<ff_log2_run[run_index];
1050                         if(x + run_count <= w) run_index++;
1051                     }else{
1052                         if(ff_log2_run[run_index]) run_count = get_bits(&s->gb, ff_log2_run[run_index]);
1053                         else run_count=0;
1054                         if(run_index) run_index--;
1055                         run_mode=2;
1056                     }
1057                 }
1058                 run_count--;
1059                 if(run_count < 0){
1060                     run_mode=0;
1061                     run_count=0;
1062                     diff= get_vlc_symbol(&s->gb, &p->vlc_state[context], bits);
1063                     if(diff>=0) diff++;
1064                 }else
1065                     diff=0;
1066             }else
1067                 diff= get_vlc_symbol(&s->gb, &p->vlc_state[context], bits);
1068
1069 //            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));
1070         }
1071
1072         if(sign) diff= -diff;
1073
1074         sample[1][x]= (predict(sample[1] + x, sample[0] + x) + diff) & ((1<<bits)-1);
1075     }
1076     s->run_index= run_index;
1077 }
1078
1079 static void decode_plane(FFV1Context *s, uint8_t *src, int w, int h, int stride, int plane_index){
1080     int x, y;
1081     int_fast16_t *sample[2];
1082     sample[0]=s->sample_buffer    +3;
1083     sample[1]=s->sample_buffer+w+6+3;
1084
1085     s->run_index=0;
1086
1087     memset(s->sample_buffer, 0, 2*(w+6)*sizeof(*s->sample_buffer));
1088
1089     for(y=0; y<h; y++){
1090         int_fast16_t *temp= sample[0]; //FIXME try a normal buffer
1091
1092         sample[0]= sample[1];
1093         sample[1]= temp;
1094
1095         sample[1][-1]= sample[0][0  ];
1096         sample[0][ w]= sample[0][w-1];
1097
1098 //{START_TIMER
1099         if(s->avctx->bits_per_raw_sample <= 8){
1100             decode_line(s, w, sample, plane_index, 8);
1101             for(x=0; x<w; x++){
1102                 src[x + stride*y]= sample[1][x];
1103             }
1104         }else{
1105             decode_line(s, w, sample, plane_index, s->avctx->bits_per_raw_sample);
1106             for(x=0; x<w; x++){
1107                 ((uint16_t*)(src + stride*y))[x]= sample[1][x] << (16 - s->avctx->bits_per_raw_sample);
1108             }
1109         }
1110 //STOP_TIMER("decode-line")}
1111     }
1112 }
1113
1114 static void decode_rgb_frame(FFV1Context *s, uint32_t *src, int w, int h, int stride){
1115     int x, y, p;
1116     int_fast16_t *sample[3][2];
1117     for(x=0; x<3; x++){
1118         sample[x][0] = s->sample_buffer +  x*2   *(w+6) + 3;
1119         sample[x][1] = s->sample_buffer + (x*2+1)*(w+6) + 3;
1120     }
1121
1122     s->run_index=0;
1123
1124     memset(s->sample_buffer, 0, 6*(w+6)*sizeof(*s->sample_buffer));
1125
1126     for(y=0; y<h; y++){
1127         for(p=0; p<3; p++){
1128             int_fast16_t *temp= sample[p][0]; //FIXME try a normal buffer
1129
1130             sample[p][0]= sample[p][1];
1131             sample[p][1]= temp;
1132
1133             sample[p][1][-1]= sample[p][0][0  ];
1134             sample[p][0][ w]= sample[p][0][w-1];
1135             decode_line(s, w, sample[p], FFMIN(p, 1), 9);
1136         }
1137         for(x=0; x<w; x++){
1138             int g= sample[0][1][x];
1139             int b= sample[1][1][x];
1140             int r= sample[2][1][x];
1141
1142 //            assert(g>=0 && b>=0 && r>=0);
1143 //            assert(g<256 && b<512 && r<512);
1144
1145             b -= 0x100;
1146             r -= 0x100;
1147             g -= (b + r)>>2;
1148             b += g;
1149             r += g;
1150
1151             src[x + stride*y]= b + (g<<8) + (r<<16) + (0xFF<<24);
1152         }
1153     }
1154 }
1155
1156 static int decode_slice(AVCodecContext *c, void *arg){
1157     FFV1Context *fs= *(void**)arg;
1158     FFV1Context *f= fs->avctx->priv_data;
1159     int width = fs->slice_width;
1160     int height= fs->slice_height;
1161     int x= fs->slice_x;
1162     int y= fs->slice_y;
1163     AVFrame * const p= &f->picture;
1164
1165     av_assert1(width && height);
1166     if(f->colorspace==0){
1167         const int chroma_width = -((-width )>>f->chroma_h_shift);
1168         const int chroma_height= -((-height)>>f->chroma_v_shift);
1169         const int cx= x>>f->chroma_h_shift;
1170         const int cy= y>>f->chroma_v_shift;
1171         decode_plane(fs, p->data[0] + x + y*p->linesize[0], width, height, p->linesize[0], 0);
1172
1173         decode_plane(fs, p->data[1] + cx+cy*p->linesize[1], chroma_width, chroma_height, p->linesize[1], 1);
1174         decode_plane(fs, p->data[2] + cx+cy*p->linesize[1], chroma_width, chroma_height, p->linesize[2], 1);
1175     }else{
1176         decode_rgb_frame(fs, (uint32_t*)p->data[0] + x + y*(p->linesize[0]/4), width, height, p->linesize[0]/4);
1177     }
1178
1179     emms_c();
1180
1181     return 0;
1182 }
1183
1184 static int read_quant_table(RangeCoder *c, int16_t *quant_table, int scale){
1185     int v;
1186     int i=0;
1187     uint8_t state[CONTEXT_SIZE];
1188
1189     memset(state, 128, sizeof(state));
1190
1191     for(v=0; i<128 ; v++){
1192         int len= get_symbol(c, state, 0) + 1;
1193
1194         if(len + i > 128) return -1;
1195
1196         while(len--){
1197             quant_table[i] = scale*v;
1198             i++;
1199 //printf("%2d ",v);
1200 //if(i%16==0) printf("\n");
1201         }
1202     }
1203
1204     for(i=1; i<128; i++){
1205         quant_table[256-i]= -quant_table[i];
1206     }
1207     quant_table[128]= -quant_table[127];
1208
1209     return 2*v - 1;
1210 }
1211
1212 static int read_quant_tables(RangeCoder *c, int16_t quant_table[MAX_CONTEXT_INPUTS][256]){
1213     int i;
1214     int context_count=1;
1215
1216     for(i=0; i<5; i++){
1217         context_count*= read_quant_table(c, quant_table[i], context_count);
1218         if(context_count > 32768U){
1219             return -1;
1220         }
1221     }
1222     return (context_count+1)/2;
1223 }
1224
1225 static int read_extra_header(FFV1Context *f){
1226     RangeCoder * const c= &f->c;
1227     uint8_t state[CONTEXT_SIZE];
1228     int i;
1229
1230     memset(state, 128, sizeof(state));
1231
1232     ff_init_range_decoder(c, f->avctx->extradata, f->avctx->extradata_size);
1233     ff_build_rac_states(c, 0.05*(1LL<<32), 256-8);
1234
1235     f->version= get_symbol(c, state, 0);
1236     f->ac= f->avctx->coder_type= get_symbol(c, state, 0);
1237     if(f->ac>1){
1238         for(i=1; i<256; i++){
1239             f->state_transition[i]= get_symbol(c, state, 1) + c->one_state[i];
1240         }
1241     }
1242     f->colorspace= get_symbol(c, state, 0); //YUV cs type
1243     f->avctx->bits_per_raw_sample= get_symbol(c, state, 0);
1244     get_rac(c, state); //no chroma = false
1245     f->chroma_h_shift= get_symbol(c, state, 0);
1246     f->chroma_v_shift= get_symbol(c, state, 0);
1247     get_rac(c, state); //transparency plane
1248     f->plane_count= 2;
1249     f->num_h_slices= 1 + get_symbol(c, state, 0);
1250     f->num_v_slices= 1 + get_symbol(c, state, 0);
1251     if(f->num_h_slices > (unsigned)f->width || f->num_v_slices > (unsigned)f->height){
1252         av_log(f->avctx, AV_LOG_ERROR, "too many slices\n");
1253         return -1;
1254     }
1255
1256     f->quant_table_count= get_symbol(c, state, 0);
1257     if(f->quant_table_count > (unsigned)MAX_QUANT_TABLES)
1258         return -1;
1259     for(i=0; i<f->quant_table_count; i++){
1260         if((f->context_count[i]= read_quant_tables(c, f->quant_tables[i])) < 0){
1261             av_log(f->avctx, AV_LOG_ERROR, "read_quant_table error\n");
1262             return -1;
1263         }
1264     }
1265
1266     return 0;
1267 }
1268
1269 static int read_header(FFV1Context *f){
1270     uint8_t state[CONTEXT_SIZE];
1271     int i, j, context_count;
1272     RangeCoder * const c= &f->slice_context[0]->c;
1273
1274     memset(state, 128, sizeof(state));
1275
1276     if(f->version < 2){
1277         f->version= get_symbol(c, state, 0);
1278         f->ac= f->avctx->coder_type= get_symbol(c, state, 0);
1279         if(f->ac>1){
1280             for(i=1; i<256; i++){
1281                 f->state_transition[i]= get_symbol(c, state, 1) + c->one_state[i];
1282             }
1283         }
1284         f->colorspace= get_symbol(c, state, 0); //YUV cs type
1285         if(f->version>0)
1286             f->avctx->bits_per_raw_sample= get_symbol(c, state, 0);
1287         get_rac(c, state); //no chroma = false
1288         f->chroma_h_shift= get_symbol(c, state, 0);
1289         f->chroma_v_shift= get_symbol(c, state, 0);
1290         get_rac(c, state); //transparency plane
1291         f->plane_count= 2;
1292     }
1293
1294     if(f->colorspace==0){
1295         if(f->avctx->bits_per_raw_sample<=8){
1296             switch(16*f->chroma_h_shift + f->chroma_v_shift){
1297             case 0x00: f->avctx->pix_fmt= PIX_FMT_YUV444P; break;
1298             case 0x10: f->avctx->pix_fmt= PIX_FMT_YUV422P; break;
1299             case 0x11: f->avctx->pix_fmt= PIX_FMT_YUV420P; break;
1300             case 0x20: f->avctx->pix_fmt= PIX_FMT_YUV411P; break;
1301             case 0x22: f->avctx->pix_fmt= PIX_FMT_YUV410P; break;
1302             default:
1303                 av_log(f->avctx, AV_LOG_ERROR, "format not supported\n");
1304                 return -1;
1305             }
1306         }else{
1307             switch(16*f->chroma_h_shift + f->chroma_v_shift){
1308             case 0x00: f->avctx->pix_fmt= PIX_FMT_YUV444P16; break;
1309             case 0x10: f->avctx->pix_fmt= PIX_FMT_YUV422P16; break;
1310             case 0x11: f->avctx->pix_fmt= PIX_FMT_YUV420P16; break;
1311             default:
1312                 av_log(f->avctx, AV_LOG_ERROR, "format not supported\n");
1313                 return -1;
1314             }
1315         }
1316     }else if(f->colorspace==1){
1317         if(f->chroma_h_shift || f->chroma_v_shift){
1318             av_log(f->avctx, AV_LOG_ERROR, "chroma subsampling not supported in this colorspace\n");
1319             return -1;
1320         }
1321         f->avctx->pix_fmt= PIX_FMT_RGB32;
1322     }else{
1323         av_log(f->avctx, AV_LOG_ERROR, "colorspace not supported\n");
1324         return -1;
1325     }
1326
1327 //printf("%d %d %d\n", f->chroma_h_shift, f->chroma_v_shift,f->avctx->pix_fmt);
1328     if(f->version < 2){
1329         context_count= read_quant_tables(c, f->quant_table);
1330         if(context_count < 0){
1331                 av_log(f->avctx, AV_LOG_ERROR, "read_quant_table error\n");
1332                 return -1;
1333         }
1334     }else{
1335         f->slice_count= get_symbol(c, state, 0);
1336         if(f->slice_count > (unsigned)MAX_SLICES)
1337             return -1;
1338     }
1339
1340     for(j=0; j<f->slice_count; j++){
1341         FFV1Context *fs= f->slice_context[j];
1342         fs->ac= f->ac;
1343
1344         if(f->version >= 2){
1345             fs->slice_x     = get_symbol(c, state, 0)   *f->width ;
1346             fs->slice_y     = get_symbol(c, state, 0)   *f->height;
1347             fs->slice_width =(get_symbol(c, state, 0)+1)*f->width  + fs->slice_x;
1348             fs->slice_height=(get_symbol(c, state, 0)+1)*f->height + fs->slice_y;
1349
1350             fs->slice_x /= f->num_h_slices;
1351             fs->slice_y /= f->num_v_slices;
1352             fs->slice_width  = fs->slice_width /f->num_h_slices - fs->slice_x;
1353             fs->slice_height = fs->slice_height/f->num_v_slices - fs->slice_y;
1354             if((unsigned)fs->slice_width > f->width || (unsigned)fs->slice_height > f->height)
1355                 return -1;
1356             if(    (unsigned)fs->slice_x + (uint64_t)fs->slice_width  > f->width
1357                 || (unsigned)fs->slice_y + (uint64_t)fs->slice_height > f->height)
1358                 return -1;
1359         }
1360
1361         for(i=0; i<f->plane_count; i++){
1362             PlaneContext * const p= &fs->plane[i];
1363
1364             if(f->version >= 2){
1365                 int idx=get_symbol(c, state, 0);
1366                 if(idx > (unsigned)f->quant_table_count){
1367                     av_log(f->avctx, AV_LOG_ERROR, "quant_table_index out of range\n");
1368                     return -1;
1369                 }
1370                 memcpy(p->quant_table, f->quant_tables[idx], sizeof(p->quant_table));
1371                 context_count= f->context_count[idx];
1372             }else{
1373                 memcpy(p->quant_table, f->quant_table, sizeof(p->quant_table));
1374             }
1375
1376             if(p->context_count < context_count){
1377                 av_freep(&p->state);
1378                 av_freep(&p->vlc_state);
1379             }
1380             p->context_count= context_count;
1381         }
1382     }
1383
1384     return 0;
1385 }
1386
1387 static av_cold int decode_init(AVCodecContext *avctx)
1388 {
1389     FFV1Context *f = avctx->priv_data;
1390
1391     common_init(avctx);
1392
1393     if(avctx->extradata && read_extra_header(f) < 0)
1394         return -1;
1395
1396     if(init_slice_contexts(f) < 0)
1397         return -1;
1398
1399     return 0;
1400 }
1401
1402 static int decode_frame(AVCodecContext *avctx, void *data, int *data_size, AVPacket *avpkt){
1403     const uint8_t *buf = avpkt->data;
1404     int buf_size = avpkt->size;
1405     FFV1Context *f = avctx->priv_data;
1406     RangeCoder * const c= &f->slice_context[0]->c;
1407     AVFrame * const p= &f->picture;
1408     int bytes_read, i;
1409     uint8_t keystate= 128;
1410     const uint8_t *buf_p;
1411
1412     AVFrame *picture = data;
1413
1414     ff_init_range_decoder(c, buf, buf_size);
1415     ff_build_rac_states(c, 0.05*(1LL<<32), 256-8);
1416
1417
1418     p->pict_type= FF_I_TYPE; //FIXME I vs. P
1419     if(get_rac(c, &keystate)){
1420         p->key_frame= 1;
1421         if(read_header(f) < 0)
1422             return -1;
1423         if(init_slice_state(f) < 0)
1424             return -1;
1425
1426         clear_state(f);
1427     }else{
1428         p->key_frame= 0;
1429     }
1430     if(f->ac>1){
1431         int i;
1432         for(i=1; i<256; i++){
1433             c->one_state[i]= f->state_transition[i];
1434             c->zero_state[256-i]= 256-c->one_state[i];
1435         }
1436     }
1437
1438     p->reference= 0;
1439     if(avctx->get_buffer(avctx, p) < 0){
1440         av_log(avctx, AV_LOG_ERROR, "get_buffer() failed\n");
1441         return -1;
1442     }
1443
1444     if(avctx->debug&FF_DEBUG_PICT_INFO)
1445         av_log(avctx, AV_LOG_ERROR, "keyframe:%d coder:%d\n", p->key_frame, f->ac);
1446
1447     if(!f->ac){
1448         bytes_read = c->bytestream - c->bytestream_start - 1;
1449         if(bytes_read ==0) av_log(avctx, AV_LOG_ERROR, "error at end of AC stream\n"); //FIXME
1450 //printf("pos=%d\n", bytes_read);
1451         init_get_bits(&f->slice_context[0]->gb, buf + bytes_read, buf_size - bytes_read);
1452     } else {
1453         bytes_read = 0; /* avoid warning */
1454     }
1455
1456     buf_p= buf + buf_size;
1457     for(i=f->slice_count-1; i>0; i--){
1458         FFV1Context *fs= f->slice_context[i];
1459         int v= AV_RB24(buf_p-3)+3;
1460         if(buf_p - buf <= v){
1461             av_log(avctx, AV_LOG_ERROR, "Slice pointer chain broken\n");
1462             return -1;
1463         }
1464         buf_p -= v;
1465         if(fs->ac){
1466             ff_init_range_decoder(&fs->c, buf_p, v);
1467         }else{
1468             init_get_bits(&fs->gb, buf_p, v);
1469         }
1470     }
1471
1472     avctx->execute(avctx, decode_slice, &f->slice_context[0], NULL, f->slice_count, sizeof(void*));
1473     f->picture_number++;
1474
1475     *picture= *p;
1476
1477     avctx->release_buffer(avctx, p); //FIXME
1478
1479     *data_size = sizeof(AVFrame);
1480
1481     return buf_size;
1482 }
1483
1484 AVCodec ffv1_decoder = {
1485     "ffv1",
1486     AVMEDIA_TYPE_VIDEO,
1487     CODEC_ID_FFV1,
1488     sizeof(FFV1Context),
1489     decode_init,
1490     NULL,
1491     common_end,
1492     decode_frame,
1493     CODEC_CAP_DR1 /*| CODEC_CAP_DRAW_HORIZ_BAND*/,
1494     NULL,
1495     .long_name= NULL_IF_CONFIG_SMALL("FFmpeg video codec #1"),
1496 };
1497
1498 #if CONFIG_FFV1_ENCODER
1499 AVCodec ffv1_encoder = {
1500     "ffv1",
1501     AVMEDIA_TYPE_VIDEO,
1502     CODEC_ID_FFV1,
1503     sizeof(FFV1Context),
1504     encode_init,
1505     encode_frame,
1506     common_end,
1507     .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},
1508     .long_name= NULL_IF_CONFIG_SMALL("FFmpeg video codec #1"),
1509 };
1510 #endif