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

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