avutil: Rename FF_CEIL_COMPAT to AV_CEIL_COMPAT
[ffmpeg.git] / libavcodec / ffv1enc.c
1 /*
2  * FFV1 encoder
3  *
4  * Copyright (c) 2003-2013 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) encoder
26  */
27
28 #include "libavutil/attributes.h"
29 #include "libavutil/avassert.h"
30 #include "libavutil/crc.h"
31 #include "libavutil/opt.h"
32 #include "libavutil/imgutils.h"
33 #include "libavutil/pixdesc.h"
34 #include "libavutil/timer.h"
35 #include "avcodec.h"
36 #include "internal.h"
37 #include "put_bits.h"
38 #include "rangecoder.h"
39 #include "golomb.h"
40 #include "mathops.h"
41 #include "ffv1.h"
42
43 static const int8_t quant5_10bit[256] = {
44      0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  1,  1,  1,  1,  1,
45      1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,
46      1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,
47      1,  1,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,
48      2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,
49      2,  2,  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, -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, -0, -0, -0, -0, -0, -0, -0, -0, -0, -0,
60 };
61
62 static const int8_t quant5[256] = {
63      0,  1,  1,  1,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,
64      2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,
65      2,  2,  2,  2,  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, -1, -1, -1,
79 };
80
81 static const int8_t quant9_10bit[256] = {
82      0,  0,  0,  0,  0,  1,  1,  1,  1,  1,  1,  1,  1,  2,  2,  2,
83      2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  3,  3,  3,  3,  3,
84      3,  3,  3,  3,  3,  3,  3,  3,  3,  3,  3,  3,  3,  3,  3,  3,
85      3,  3,  3,  3,  3,  3,  3,  3,  4,  4,  4,  4,  4,  4,  4,  4,
86      4,  4,  4,  4,  4,  4,  4,  4,  4,  4,  4,  4,  4,  4,  4,  4,
87      4,  4,  4,  4,  4,  4,  4,  4,  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, -3, -3, -3, -3, -3, -3, -3,
95     -3, -3, -3, -3, -3, -3, -3, -3, -3, -3, -3, -3, -3, -3, -3, -3,
96     -3, -3, -3, -3, -3, -3, -2, -2, -2, -2, -2, -2, -2, -2, -2, -2,
97     -2, -2, -2, -2, -1, -1, -1, -1, -1, -1, -1, -1, -0, -0, -0, -0,
98 };
99
100 static const int8_t quant11[256] = {
101      0,  1,  2,  2,  2,  3,  3,  3,  3,  3,  3,  3,  4,  4,  4,  4,
102      4,  4,  4,  4,  4,  4,  4,  4,  4,  4,  4,  4,  4,  4,  4,  4,
103      4,  4,  4,  5,  5,  5,  5,  5,  5,  5,  5,  5,  5,  5,  5,  5,
104      5,  5,  5,  5,  5,  5,  5,  5,  5,  5,  5,  5,  5,  5,  5,  5,
105      5,  5,  5,  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, -4, -4,
115     -4, -4, -4, -4, -4, -4, -4, -4, -4, -4, -4, -4, -4, -4, -4, -4,
116     -4, -4, -4, -4, -4, -3, -3, -3, -3, -3, -3, -3, -2, -2, -2, -1,
117 };
118
119 static const uint8_t ver2_state[256] = {
120       0,  10,  10,  10,  10,  16,  16,  16, 28,   16,  16,  29,  42,  49,  20,  49,
121      59,  25,  26,  26,  27,  31,  33,  33, 33,   34,  34,  37,  67,  38,  39,  39,
122      40,  40,  41,  79,  43,  44,  45,  45, 48,   48,  64,  50,  51,  52,  88,  52,
123      53,  74,  55,  57,  58,  58,  74,  60, 101,  61,  62,  84,  66,  66,  68,  69,
124      87,  82,  71,  97,  73,  73,  82,  75, 111,  77,  94,  78,  87,  81,  83,  97,
125      85,  83,  94,  86,  99,  89,  90,  99, 111,  92,  93,  134, 95,  98,  105, 98,
126     105, 110, 102, 108, 102, 118, 103, 106, 106, 113, 109, 112, 114, 112, 116, 125,
127     115, 116, 117, 117, 126, 119, 125, 121, 121, 123, 145, 124, 126, 131, 127, 129,
128     165, 130, 132, 138, 133, 135, 145, 136, 137, 139, 146, 141, 143, 142, 144, 148,
129     147, 155, 151, 149, 151, 150, 152, 157, 153, 154, 156, 168, 158, 162, 161, 160,
130     172, 163, 169, 164, 166, 184, 167, 170, 177, 174, 171, 173, 182, 176, 180, 178,
131     175, 189, 179, 181, 186, 183, 192, 185, 200, 187, 191, 188, 190, 197, 193, 196,
132     197, 194, 195, 196, 198, 202, 199, 201, 210, 203, 207, 204, 205, 206, 208, 214,
133     209, 211, 221, 212, 213, 215, 224, 216, 217, 218, 219, 220, 222, 228, 223, 225,
134     226, 224, 227, 229, 240, 230, 231, 232, 233, 234, 235, 236, 238, 239, 237, 242,
135     241, 243, 242, 244, 245, 246, 247, 248, 249, 250, 251, 252, 252, 253, 254, 255,
136 };
137
138 static void find_best_state(uint8_t best_state[256][256],
139                             const uint8_t one_state[256])
140 {
141     int i, j, k, m;
142     double l2tab[256];
143
144     for (i = 1; i < 256; i++)
145         l2tab[i] = log2(i / 256.0);
146
147     for (i = 0; i < 256; i++) {
148         double best_len[256];
149         double p = i / 256.0;
150
151         for (j = 0; j < 256; j++)
152             best_len[j] = 1 << 30;
153
154         for (j = FFMAX(i - 10, 1); j < FFMIN(i + 11, 256); j++) {
155             double occ[256] = { 0 };
156             double len      = 0;
157             occ[j] = 1.0;
158
159             if (!one_state[j])
160                 continue;
161
162             for (k = 0; k < 256; k++) {
163                 double newocc[256] = { 0 };
164                 for (m = 1; m < 256; m++)
165                     if (occ[m]) {
166                         len -=occ[m]*(     p *l2tab[    m]
167                                       + (1-p)*l2tab[256-m]);
168                     }
169                 if (len < best_len[k]) {
170                     best_len[k]      = len;
171                     best_state[i][k] = j;
172                 }
173                 for (m = 1; m < 256; m++)
174                     if (occ[m]) {
175                         newocc[      one_state[      m]] += occ[m] * p;
176                         newocc[256 - one_state[256 - m]] += occ[m] * (1 - p);
177                     }
178                 memcpy(occ, newocc, sizeof(occ));
179             }
180         }
181     }
182 }
183
184 static av_always_inline av_flatten void put_symbol_inline(RangeCoder *c,
185                                                           uint8_t *state, int v,
186                                                           int is_signed,
187                                                           uint64_t rc_stat[256][2],
188                                                           uint64_t rc_stat2[32][2])
189 {
190     int i;
191
192 #define put_rac(C, S, B)                        \
193     do {                                        \
194         if (rc_stat) {                          \
195             rc_stat[*(S)][B]++;                 \
196             rc_stat2[(S) - state][B]++;         \
197         }                                       \
198         put_rac(C, S, B);                       \
199     } while (0)
200
201     if (v) {
202         const int a = FFABS(v);
203         const int e = av_log2(a);
204         put_rac(c, state + 0, 0);
205         if (e <= 9) {
206             for (i = 0; i < e; i++)
207                 put_rac(c, state + 1 + i, 1);  // 1..10
208             put_rac(c, state + 1 + i, 0);
209
210             for (i = e - 1; i >= 0; i--)
211                 put_rac(c, state + 22 + i, (a >> i) & 1);  // 22..31
212
213             if (is_signed)
214                 put_rac(c, state + 11 + e, v < 0);  // 11..21
215         } else {
216             for (i = 0; i < e; i++)
217                 put_rac(c, state + 1 + FFMIN(i, 9), 1);  // 1..10
218             put_rac(c, state + 1 + 9, 0);
219
220             for (i = e - 1; i >= 0; i--)
221                 put_rac(c, state + 22 + FFMIN(i, 9), (a >> i) & 1);  // 22..31
222
223             if (is_signed)
224                 put_rac(c, state + 11 + 10, v < 0);  // 11..21
225         }
226     } else {
227         put_rac(c, state + 0, 1);
228     }
229 #undef put_rac
230 }
231
232 static av_noinline void put_symbol(RangeCoder *c, uint8_t *state,
233                                    int v, int is_signed)
234 {
235     put_symbol_inline(c, state, v, is_signed, NULL, NULL);
236 }
237
238
239 static inline void put_vlc_symbol(PutBitContext *pb, VlcState *const state,
240                                   int v, int bits)
241 {
242     int i, k, code;
243     v = fold(v - state->bias, bits);
244
245     i = state->count;
246     k = 0;
247     while (i < state->error_sum) { // FIXME: optimize
248         k++;
249         i += i;
250     }
251
252     av_assert2(k <= 13);
253
254 #if 0 // JPEG LS
255     if (k == 0 && 2 * state->drift <= -state->count)
256         code = v ^ (-1);
257     else
258         code = v;
259 #else
260     code = v ^ ((2 * state->drift + state->count) >> 31);
261 #endif
262
263     ff_dlog(NULL, "v:%d/%d bias:%d error:%d drift:%d count:%d k:%d\n", v, code,
264             state->bias, state->error_sum, state->drift, state->count, k);
265     set_sr_golomb(pb, code, k, 12, bits);
266
267     update_vlc_state(state, v);
268 }
269
270 static av_always_inline int encode_line(FFV1Context *s, int w,
271                                         int16_t *sample[3],
272                                         int plane_index, int bits)
273 {
274     PlaneContext *const p = &s->plane[plane_index];
275     RangeCoder *const c   = &s->c;
276     int x;
277     int run_index = s->run_index;
278     int run_count = 0;
279     int run_mode  = 0;
280
281     if (s->ac != AC_GOLOMB_RICE) {
282         if (c->bytestream_end - c->bytestream < w * 35) {
283             av_log(s->avctx, AV_LOG_ERROR, "encoded frame too large\n");
284             return AVERROR_INVALIDDATA;
285         }
286     } else {
287         if (s->pb.buf_end - s->pb.buf - (put_bits_count(&s->pb) >> 3) < w * 4) {
288             av_log(s->avctx, AV_LOG_ERROR, "encoded frame too large\n");
289             return AVERROR_INVALIDDATA;
290         }
291     }
292
293     if (s->slice_coding_mode == 1) {
294         for (x = 0; x < w; x++) {
295             int i;
296             int v = sample[0][x];
297             for (i = bits-1; i>=0; i--) {
298                 uint8_t state = 128;
299                 put_rac(c, &state, (v>>i) & 1);
300             }
301         }
302         return 0;
303     }
304
305     for (x = 0; x < w; x++) {
306         int diff, context;
307
308         context = get_context(p, sample[0] + x, sample[1] + x, sample[2] + x);
309         diff    = sample[0][x] - predict(sample[0] + x, sample[1] + x);
310
311         if (context < 0) {
312             context = -context;
313             diff    = -diff;
314         }
315
316         diff = fold(diff, bits);
317
318         if (s->ac != AC_GOLOMB_RICE) {
319             if (s->flags & AV_CODEC_FLAG_PASS1) {
320                 put_symbol_inline(c, p->state[context], diff, 1, s->rc_stat,
321                                   s->rc_stat2[p->quant_table_index][context]);
322             } else {
323                 put_symbol_inline(c, p->state[context], diff, 1, NULL, NULL);
324             }
325         } else {
326             if (context == 0)
327                 run_mode = 1;
328
329             if (run_mode) {
330                 if (diff) {
331                     while (run_count >= 1 << ff_log2_run[run_index]) {
332                         run_count -= 1 << ff_log2_run[run_index];
333                         run_index++;
334                         put_bits(&s->pb, 1, 1);
335                     }
336
337                     put_bits(&s->pb, 1 + ff_log2_run[run_index], run_count);
338                     if (run_index)
339                         run_index--;
340                     run_count = 0;
341                     run_mode  = 0;
342                     if (diff > 0)
343                         diff--;
344                 } else {
345                     run_count++;
346                 }
347             }
348
349             ff_dlog(s->avctx, "count:%d index:%d, mode:%d, x:%d pos:%d\n",
350                     run_count, run_index, run_mode, x,
351                     (int)put_bits_count(&s->pb));
352
353             if (run_mode == 0)
354                 put_vlc_symbol(&s->pb, &p->vlc_state[context], diff, bits);
355         }
356     }
357     if (run_mode) {
358         while (run_count >= 1 << ff_log2_run[run_index]) {
359             run_count -= 1 << ff_log2_run[run_index];
360             run_index++;
361             put_bits(&s->pb, 1, 1);
362         }
363
364         if (run_count)
365             put_bits(&s->pb, 1, 1);
366     }
367     s->run_index = run_index;
368
369     return 0;
370 }
371
372 static int encode_plane(FFV1Context *s, uint8_t *src, int w, int h,
373                          int stride, int plane_index, int pixel_stride)
374 {
375     int x, y, i, ret;
376     const int ring_size = s->avctx->context_model ? 3 : 2;
377     int16_t *sample[3];
378     s->run_index = 0;
379
380     memset(s->sample_buffer, 0, ring_size * (w + 6) * sizeof(*s->sample_buffer));
381
382     for (y = 0; y < h; y++) {
383         for (i = 0; i < ring_size; i++)
384             sample[i] = s->sample_buffer + (w + 6) * ((h + i - y) % ring_size) + 3;
385
386         sample[0][-1]= sample[1][0  ];
387         sample[1][ w]= sample[1][w-1];
388 // { START_TIMER
389         if (s->bits_per_raw_sample <= 8) {
390             for (x = 0; x < w; x++)
391                 sample[0][x] = src[x * pixel_stride + stride * y];
392             if((ret = encode_line(s, w, sample, plane_index, 8)) < 0)
393                 return ret;
394         } else {
395             if (s->packed_at_lsb) {
396                 for (x = 0; x < w; x++) {
397                     sample[0][x] = ((uint16_t*)(src + stride*y))[x];
398                 }
399             } else {
400                 for (x = 0; x < w; x++) {
401                     sample[0][x] = ((uint16_t*)(src + stride*y))[x] >> (16 - s->bits_per_raw_sample);
402                 }
403             }
404             if((ret = encode_line(s, w, sample, plane_index, s->bits_per_raw_sample)) < 0)
405                 return ret;
406         }
407 // STOP_TIMER("encode line") }
408     }
409     return 0;
410 }
411
412 static int encode_rgb_frame(FFV1Context *s, const uint8_t *src[3],
413                              int w, int h, const int stride[3])
414 {
415     int x, y, p, i;
416     const int ring_size = s->avctx->context_model ? 3 : 2;
417     int16_t *sample[4][3];
418     int lbd    = s->bits_per_raw_sample <= 8;
419     int bits   = s->bits_per_raw_sample > 0 ? s->bits_per_raw_sample : 8;
420     int offset = 1 << bits;
421
422     s->run_index = 0;
423
424     memset(s->sample_buffer, 0, ring_size * MAX_PLANES *
425                                 (w + 6) * sizeof(*s->sample_buffer));
426
427     for (y = 0; y < h; y++) {
428         for (i = 0; i < ring_size; i++)
429             for (p = 0; p < MAX_PLANES; p++)
430                 sample[p][i]= s->sample_buffer + p*ring_size*(w+6) + ((h+i-y)%ring_size)*(w+6) + 3;
431
432         for (x = 0; x < w; x++) {
433             int b, g, r, av_uninit(a);
434             if (lbd) {
435                 unsigned v = *((const uint32_t*)(src[0] + x*4 + stride[0]*y));
436                 b =  v        & 0xFF;
437                 g = (v >>  8) & 0xFF;
438                 r = (v >> 16) & 0xFF;
439                 a =  v >> 24;
440             } else {
441                 b = *((const uint16_t *)(src[0] + x*2 + stride[0]*y));
442                 g = *((const uint16_t *)(src[1] + x*2 + stride[1]*y));
443                 r = *((const uint16_t *)(src[2] + x*2 + stride[2]*y));
444             }
445
446             if (s->slice_coding_mode != 1) {
447                 b -= g;
448                 r -= g;
449                 g += (b * s->slice_rct_by_coef + r * s->slice_rct_ry_coef) >> 2;
450                 b += offset;
451                 r += offset;
452             }
453
454             sample[0][0][x] = g;
455             sample[1][0][x] = b;
456             sample[2][0][x] = r;
457             sample[3][0][x] = a;
458         }
459         for (p = 0; p < 3 + s->transparency; p++) {
460             int ret;
461             sample[p][0][-1] = sample[p][1][0  ];
462             sample[p][1][ w] = sample[p][1][w-1];
463             if (lbd && s->slice_coding_mode == 0)
464                 ret = encode_line(s, w, sample[p], (p + 1) / 2, 9);
465             else
466                 ret = encode_line(s, w, sample[p], (p + 1) / 2, bits + (s->slice_coding_mode != 1));
467             if (ret < 0)
468                 return ret;
469         }
470     }
471     return 0;
472 }
473
474 static void write_quant_table(RangeCoder *c, int16_t *quant_table)
475 {
476     int last = 0;
477     int i;
478     uint8_t state[CONTEXT_SIZE];
479     memset(state, 128, sizeof(state));
480
481     for (i = 1; i < 128; i++)
482         if (quant_table[i] != quant_table[i - 1]) {
483             put_symbol(c, state, i - last - 1, 0);
484             last = i;
485         }
486     put_symbol(c, state, i - last - 1, 0);
487 }
488
489 static void write_quant_tables(RangeCoder *c,
490                                int16_t quant_table[MAX_CONTEXT_INPUTS][256])
491 {
492     int i;
493     for (i = 0; i < 5; i++)
494         write_quant_table(c, quant_table[i]);
495 }
496
497 static void write_header(FFV1Context *f)
498 {
499     uint8_t state[CONTEXT_SIZE];
500     int i, j;
501     RangeCoder *const c = &f->slice_context[0]->c;
502
503     memset(state, 128, sizeof(state));
504
505     if (f->version < 2) {
506         put_symbol(c, state, f->version, 0);
507         put_symbol(c, state, f->ac, 0);
508         if (f->ac == AC_RANGE_CUSTOM_TAB) {
509             for (i = 1; i < 256; i++)
510                 put_symbol(c, state,
511                            f->state_transition[i] - c->one_state[i], 1);
512         }
513         put_symbol(c, state, f->colorspace, 0); //YUV cs type
514         if (f->version > 0)
515             put_symbol(c, state, f->bits_per_raw_sample, 0);
516         put_rac(c, state, f->chroma_planes);
517         put_symbol(c, state, f->chroma_h_shift, 0);
518         put_symbol(c, state, f->chroma_v_shift, 0);
519         put_rac(c, state, f->transparency);
520
521         write_quant_tables(c, f->quant_table);
522     } else if (f->version < 3) {
523         put_symbol(c, state, f->slice_count, 0);
524         for (i = 0; i < f->slice_count; i++) {
525             FFV1Context *fs = f->slice_context[i];
526             put_symbol(c, state,
527                        (fs->slice_x      + 1) * f->num_h_slices / f->width, 0);
528             put_symbol(c, state,
529                        (fs->slice_y      + 1) * f->num_v_slices / f->height, 0);
530             put_symbol(c, state,
531                        (fs->slice_width  + 1) * f->num_h_slices / f->width - 1,
532                        0);
533             put_symbol(c, state,
534                        (fs->slice_height + 1) * f->num_v_slices / f->height - 1,
535                        0);
536             for (j = 0; j < f->plane_count; j++) {
537                 put_symbol(c, state, f->plane[j].quant_table_index, 0);
538                 av_assert0(f->plane[j].quant_table_index == f->avctx->context_model);
539             }
540         }
541     }
542 }
543
544 static int write_extradata(FFV1Context *f)
545 {
546     RangeCoder *const c = &f->c;
547     uint8_t state[CONTEXT_SIZE];
548     int i, j, k;
549     uint8_t state2[32][CONTEXT_SIZE];
550     unsigned v;
551
552     memset(state2, 128, sizeof(state2));
553     memset(state, 128, sizeof(state));
554
555     f->avctx->extradata_size = 10000 + 4 +
556                                     (11 * 11 * 5 * 5 * 5 + 11 * 11 * 11) * 32;
557     f->avctx->extradata = av_malloc(f->avctx->extradata_size + AV_INPUT_BUFFER_PADDING_SIZE);
558     if (!f->avctx->extradata)
559         return AVERROR(ENOMEM);
560     ff_init_range_encoder(c, f->avctx->extradata, f->avctx->extradata_size);
561     ff_build_rac_states(c, 0.05 * (1LL << 32), 256 - 8);
562
563     put_symbol(c, state, f->version, 0);
564     if (f->version > 2) {
565         if (f->version == 3) {
566             f->micro_version = 4;
567         } else if (f->version == 4)
568             f->micro_version = 2;
569         put_symbol(c, state, f->micro_version, 0);
570     }
571
572     put_symbol(c, state, f->ac, 0);
573     if (f->ac == AC_RANGE_CUSTOM_TAB)
574         for (i = 1; i < 256; i++)
575             put_symbol(c, state, f->state_transition[i] - c->one_state[i], 1);
576
577     put_symbol(c, state, f->colorspace, 0); // YUV cs type
578     put_symbol(c, state, f->bits_per_raw_sample, 0);
579     put_rac(c, state, f->chroma_planes);
580     put_symbol(c, state, f->chroma_h_shift, 0);
581     put_symbol(c, state, f->chroma_v_shift, 0);
582     put_rac(c, state, f->transparency);
583     put_symbol(c, state, f->num_h_slices - 1, 0);
584     put_symbol(c, state, f->num_v_slices - 1, 0);
585
586     put_symbol(c, state, f->quant_table_count, 0);
587     for (i = 0; i < f->quant_table_count; i++)
588         write_quant_tables(c, f->quant_tables[i]);
589
590     for (i = 0; i < f->quant_table_count; i++) {
591         for (j = 0; j < f->context_count[i] * CONTEXT_SIZE; j++)
592             if (f->initial_states[i] && f->initial_states[i][0][j] != 128)
593                 break;
594         if (j < f->context_count[i] * CONTEXT_SIZE) {
595             put_rac(c, state, 1);
596             for (j = 0; j < f->context_count[i]; j++)
597                 for (k = 0; k < CONTEXT_SIZE; k++) {
598                     int pred = j ? f->initial_states[i][j - 1][k] : 128;
599                     put_symbol(c, state2[k],
600                                (int8_t)(f->initial_states[i][j][k] - pred), 1);
601                 }
602         } else {
603             put_rac(c, state, 0);
604         }
605     }
606
607     if (f->version > 2) {
608         put_symbol(c, state, f->ec, 0);
609         put_symbol(c, state, f->intra = (f->avctx->gop_size < 2), 0);
610     }
611
612     f->avctx->extradata_size = ff_rac_terminate(c);
613     v = av_crc(av_crc_get_table(AV_CRC_32_IEEE), 0, f->avctx->extradata, f->avctx->extradata_size);
614     AV_WL32(f->avctx->extradata + f->avctx->extradata_size, v);
615     f->avctx->extradata_size += 4;
616
617     return 0;
618 }
619
620 static int sort_stt(FFV1Context *s, uint8_t stt[256])
621 {
622     int i, i2, changed, print = 0;
623
624     do {
625         changed = 0;
626         for (i = 12; i < 244; i++) {
627             for (i2 = i + 1; i2 < 245 && i2 < i + 4; i2++) {
628
629 #define COST(old, new)                                      \
630     s->rc_stat[old][0] * -log2((256 - (new)) / 256.0) +     \
631     s->rc_stat[old][1] * -log2((new)         / 256.0)
632
633 #define COST2(old, new)                         \
634     COST(old, new) + COST(256 - (old), 256 - (new))
635
636                 double size0 = COST2(i,  i) + COST2(i2, i2);
637                 double sizeX = COST2(i, i2) + COST2(i2, i);
638                 if (size0 - sizeX > size0*(1e-14) && i != 128 && i2 != 128) {
639                     int j;
640                     FFSWAP(int, stt[i], stt[i2]);
641                     FFSWAP(int, s->rc_stat[i][0], s->rc_stat[i2][0]);
642                     FFSWAP(int, s->rc_stat[i][1], s->rc_stat[i2][1]);
643                     if (i != 256 - i2) {
644                         FFSWAP(int, stt[256 - i], stt[256 - i2]);
645                         FFSWAP(int, s->rc_stat[256 - i][0], s->rc_stat[256 - i2][0]);
646                         FFSWAP(int, s->rc_stat[256 - i][1], s->rc_stat[256 - i2][1]);
647                     }
648                     for (j = 1; j < 256; j++) {
649                         if (stt[j] == i)
650                             stt[j] = i2;
651                         else if (stt[j] == i2)
652                             stt[j] = i;
653                         if (i != 256 - i2) {
654                             if (stt[256 - j] == 256 - i)
655                                 stt[256 - j] = 256 - i2;
656                             else if (stt[256 - j] == 256 - i2)
657                                 stt[256 - j] = 256 - i;
658                         }
659                     }
660                     print = changed = 1;
661                 }
662             }
663         }
664     } while (changed);
665     return print;
666 }
667
668 static av_cold int encode_init(AVCodecContext *avctx)
669 {
670     FFV1Context *s = avctx->priv_data;
671     const AVPixFmtDescriptor *desc = av_pix_fmt_desc_get(avctx->pix_fmt);
672     int i, j, k, m, ret;
673
674     if ((ret = ff_ffv1_common_init(avctx)) < 0)
675         return ret;
676
677     s->version = 0;
678
679     if ((avctx->flags & (AV_CODEC_FLAG_PASS1 | AV_CODEC_FLAG_PASS2)) ||
680         avctx->slices > 1)
681         s->version = FFMAX(s->version, 2);
682
683     // Unspecified level & slices, we choose version 1.2+ to ensure multithreaded decodability
684     if (avctx->slices == 0 && avctx->level < 0 && avctx->width * avctx->height > 720*576)
685         s->version = FFMAX(s->version, 2);
686
687     if (avctx->level <= 0 && s->version == 2) {
688         s->version = 3;
689     }
690     if (avctx->level >= 0 && avctx->level <= 4) {
691         if (avctx->level < s->version) {
692             av_log(avctx, AV_LOG_ERROR, "Version %d needed for requested features but %d requested\n", s->version, avctx->level);
693             return AVERROR(EINVAL);
694         }
695         s->version = avctx->level;
696     }
697
698     if (s->ec < 0) {
699         s->ec = (s->version >= 3);
700     }
701
702     if ((s->version == 2 || s->version>3) && avctx->strict_std_compliance > FF_COMPLIANCE_EXPERIMENTAL) {
703         av_log(avctx, AV_LOG_ERROR, "Version 2 needed for requested features but version 2 is experimental and not enabled\n");
704         return AVERROR_INVALIDDATA;
705     }
706
707 #if FF_API_CODER_TYPE
708 FF_DISABLE_DEPRECATION_WARNINGS
709     if (avctx->coder_type != -1)
710         s->ac = avctx->coder_type > 0 ? AC_RANGE_CUSTOM_TAB : AC_GOLOMB_RICE;
711     else
712 FF_ENABLE_DEPRECATION_WARNINGS
713 #endif
714     if (s->ac == 1) // Compatbility with common command line usage
715         s->ac = AC_RANGE_CUSTOM_TAB;
716     else if (s->ac == AC_RANGE_DEFAULT_TAB_FORCE)
717         s->ac = AC_RANGE_DEFAULT_TAB;
718
719     s->plane_count = 3;
720     switch(avctx->pix_fmt) {
721     case AV_PIX_FMT_YUV444P9:
722     case AV_PIX_FMT_YUV422P9:
723     case AV_PIX_FMT_YUV420P9:
724     case AV_PIX_FMT_YUVA444P9:
725     case AV_PIX_FMT_YUVA422P9:
726     case AV_PIX_FMT_YUVA420P9:
727         if (!avctx->bits_per_raw_sample)
728             s->bits_per_raw_sample = 9;
729     case AV_PIX_FMT_YUV444P10:
730     case AV_PIX_FMT_YUV420P10:
731     case AV_PIX_FMT_YUV422P10:
732     case AV_PIX_FMT_YUVA444P10:
733     case AV_PIX_FMT_YUVA422P10:
734     case AV_PIX_FMT_YUVA420P10:
735         s->packed_at_lsb = 1;
736         if (!avctx->bits_per_raw_sample && !s->bits_per_raw_sample)
737             s->bits_per_raw_sample = 10;
738     case AV_PIX_FMT_GRAY16:
739     case AV_PIX_FMT_YUV444P16:
740     case AV_PIX_FMT_YUV422P16:
741     case AV_PIX_FMT_YUV420P16:
742     case AV_PIX_FMT_YUVA444P16:
743     case AV_PIX_FMT_YUVA422P16:
744     case AV_PIX_FMT_YUVA420P16:
745         if (!avctx->bits_per_raw_sample && !s->bits_per_raw_sample) {
746             s->bits_per_raw_sample = 16;
747         } else if (!s->bits_per_raw_sample) {
748             s->bits_per_raw_sample = avctx->bits_per_raw_sample;
749         }
750         if (s->bits_per_raw_sample <= 8) {
751             av_log(avctx, AV_LOG_ERROR, "bits_per_raw_sample invalid\n");
752             return AVERROR_INVALIDDATA;
753         }
754         if (s->ac == AC_GOLOMB_RICE) {
755             av_log(avctx, AV_LOG_INFO,
756                    "bits_per_raw_sample > 8, forcing range coder\n");
757             s->ac = AC_RANGE_CUSTOM_TAB;
758         }
759         s->version = FFMAX(s->version, 1);
760     case AV_PIX_FMT_GRAY8:
761     case AV_PIX_FMT_YA8:
762     case AV_PIX_FMT_YUV444P:
763     case AV_PIX_FMT_YUV440P:
764     case AV_PIX_FMT_YUV422P:
765     case AV_PIX_FMT_YUV420P:
766     case AV_PIX_FMT_YUV411P:
767     case AV_PIX_FMT_YUV410P:
768     case AV_PIX_FMT_YUVA444P:
769     case AV_PIX_FMT_YUVA422P:
770     case AV_PIX_FMT_YUVA420P:
771         s->chroma_planes = desc->nb_components < 3 ? 0 : 1;
772         s->colorspace = 0;
773         s->transparency = desc->nb_components == 4 || desc->nb_components == 2;
774         if (!avctx->bits_per_raw_sample && !s->bits_per_raw_sample)
775             s->bits_per_raw_sample = 8;
776         else if (!s->bits_per_raw_sample)
777             s->bits_per_raw_sample = 8;
778         break;
779     case AV_PIX_FMT_RGB32:
780         s->colorspace = 1;
781         s->transparency = 1;
782         s->chroma_planes = 1;
783         if (!avctx->bits_per_raw_sample)
784             s->bits_per_raw_sample = 8;
785         break;
786     case AV_PIX_FMT_0RGB32:
787         s->colorspace = 1;
788         s->chroma_planes = 1;
789         if (!avctx->bits_per_raw_sample)
790             s->bits_per_raw_sample = 8;
791         break;
792     case AV_PIX_FMT_GBRP9:
793         if (!avctx->bits_per_raw_sample)
794             s->bits_per_raw_sample = 9;
795     case AV_PIX_FMT_GBRP10:
796         if (!avctx->bits_per_raw_sample && !s->bits_per_raw_sample)
797             s->bits_per_raw_sample = 10;
798     case AV_PIX_FMT_GBRP12:
799         if (!avctx->bits_per_raw_sample && !s->bits_per_raw_sample)
800             s->bits_per_raw_sample = 12;
801     case AV_PIX_FMT_GBRP14:
802         if (!avctx->bits_per_raw_sample && !s->bits_per_raw_sample)
803             s->bits_per_raw_sample = 14;
804         else if (!s->bits_per_raw_sample)
805             s->bits_per_raw_sample = avctx->bits_per_raw_sample;
806         s->colorspace = 1;
807         s->chroma_planes = 1;
808         s->version = FFMAX(s->version, 1);
809         if (s->ac == AC_GOLOMB_RICE) {
810             av_log(avctx, AV_LOG_INFO,
811                    "bits_per_raw_sample > 8, forcing coder 1\n");
812             s->ac = AC_RANGE_CUSTOM_TAB;
813         }
814         break;
815     default:
816         av_log(avctx, AV_LOG_ERROR, "format not supported\n");
817         return AVERROR(ENOSYS);
818     }
819     av_assert0(s->bits_per_raw_sample >= 8);
820
821     if (s->transparency) {
822         av_log(avctx, AV_LOG_WARNING, "Storing alpha plane, this will require a recent FFV1 decoder to playback!\n");
823     }
824     if (avctx->context_model > 1U) {
825         av_log(avctx, AV_LOG_ERROR, "Invalid context model %d, valid values are 0 and 1\n", avctx->context_model);
826         return AVERROR(EINVAL);
827     }
828
829     if (s->ac == AC_RANGE_CUSTOM_TAB) {
830         for (i = 1; i < 256; i++)
831             s->state_transition[i] = ver2_state[i];
832     } else {
833         RangeCoder c;
834         ff_build_rac_states(&c, 0.05 * (1LL << 32), 256 - 8);
835         for (i = 1; i < 256; i++)
836             s->state_transition[i] = c.one_state[i];
837     }
838
839     for (i = 0; i < 256; i++) {
840         s->quant_table_count = 2;
841         if (s->bits_per_raw_sample <= 8) {
842             s->quant_tables[0][0][i]=           quant11[i];
843             s->quant_tables[0][1][i]=        11*quant11[i];
844             s->quant_tables[0][2][i]=     11*11*quant11[i];
845             s->quant_tables[1][0][i]=           quant11[i];
846             s->quant_tables[1][1][i]=        11*quant11[i];
847             s->quant_tables[1][2][i]=     11*11*quant5 [i];
848             s->quant_tables[1][3][i]=   5*11*11*quant5 [i];
849             s->quant_tables[1][4][i]= 5*5*11*11*quant5 [i];
850         } else {
851             s->quant_tables[0][0][i]=           quant9_10bit[i];
852             s->quant_tables[0][1][i]=        11*quant9_10bit[i];
853             s->quant_tables[0][2][i]=     11*11*quant9_10bit[i];
854             s->quant_tables[1][0][i]=           quant9_10bit[i];
855             s->quant_tables[1][1][i]=        11*quant9_10bit[i];
856             s->quant_tables[1][2][i]=     11*11*quant5_10bit[i];
857             s->quant_tables[1][3][i]=   5*11*11*quant5_10bit[i];
858             s->quant_tables[1][4][i]= 5*5*11*11*quant5_10bit[i];
859         }
860     }
861     s->context_count[0] = (11 * 11 * 11        + 1) / 2;
862     s->context_count[1] = (11 * 11 * 5 * 5 * 5 + 1) / 2;
863     memcpy(s->quant_table, s->quant_tables[avctx->context_model],
864            sizeof(s->quant_table));
865
866     for (i = 0; i < s->plane_count; i++) {
867         PlaneContext *const p = &s->plane[i];
868
869         memcpy(p->quant_table, s->quant_table, sizeof(p->quant_table));
870         p->quant_table_index = avctx->context_model;
871         p->context_count     = s->context_count[p->quant_table_index];
872     }
873
874     if ((ret = ff_ffv1_allocate_initial_states(s)) < 0)
875         return ret;
876
877 #if FF_API_CODED_FRAME
878 FF_DISABLE_DEPRECATION_WARNINGS
879     avctx->coded_frame->pict_type = AV_PICTURE_TYPE_I;
880 FF_ENABLE_DEPRECATION_WARNINGS
881 #endif
882
883     if (!s->transparency)
884         s->plane_count = 2;
885     if (!s->chroma_planes && s->version > 3)
886         s->plane_count--;
887
888     avcodec_get_chroma_sub_sample(avctx->pix_fmt, &s->chroma_h_shift, &s->chroma_v_shift);
889     s->picture_number = 0;
890
891     if (avctx->flags & (AV_CODEC_FLAG_PASS1 | AV_CODEC_FLAG_PASS2)) {
892         for (i = 0; i < s->quant_table_count; i++) {
893             s->rc_stat2[i] = av_mallocz(s->context_count[i] *
894                                         sizeof(*s->rc_stat2[i]));
895             if (!s->rc_stat2[i])
896                 return AVERROR(ENOMEM);
897         }
898     }
899     if (avctx->stats_in) {
900         char *p = avctx->stats_in;
901         uint8_t (*best_state)[256] = av_malloc_array(256, 256);
902         int gob_count = 0;
903         char *next;
904         if (!best_state)
905             return AVERROR(ENOMEM);
906
907         av_assert0(s->version >= 2);
908
909         for (;;) {
910             for (j = 0; j < 256; j++)
911                 for (i = 0; i < 2; i++) {
912                     s->rc_stat[j][i] = strtol(p, &next, 0);
913                     if (next == p) {
914                         av_log(avctx, AV_LOG_ERROR,
915                                "2Pass file invalid at %d %d [%s]\n", j, i, p);
916                         av_freep(&best_state);
917                         return AVERROR_INVALIDDATA;
918                     }
919                     p = next;
920                 }
921             for (i = 0; i < s->quant_table_count; i++)
922                 for (j = 0; j < s->context_count[i]; j++) {
923                     for (k = 0; k < 32; k++)
924                         for (m = 0; m < 2; m++) {
925                             s->rc_stat2[i][j][k][m] = strtol(p, &next, 0);
926                             if (next == p) {
927                                 av_log(avctx, AV_LOG_ERROR,
928                                        "2Pass file invalid at %d %d %d %d [%s]\n",
929                                        i, j, k, m, p);
930                                 av_freep(&best_state);
931                                 return AVERROR_INVALIDDATA;
932                             }
933                             p = next;
934                         }
935                 }
936             gob_count = strtol(p, &next, 0);
937             if (next == p || gob_count <= 0) {
938                 av_log(avctx, AV_LOG_ERROR, "2Pass file invalid\n");
939                 av_freep(&best_state);
940                 return AVERROR_INVALIDDATA;
941             }
942             p = next;
943             while (*p == '\n' || *p == ' ')
944                 p++;
945             if (p[0] == 0)
946                 break;
947         }
948         if (s->ac == AC_RANGE_CUSTOM_TAB)
949             sort_stt(s, s->state_transition);
950
951         find_best_state(best_state, s->state_transition);
952
953         for (i = 0; i < s->quant_table_count; i++) {
954             for (k = 0; k < 32; k++) {
955                 double a=0, b=0;
956                 int jp = 0;
957                 for (j = 0; j < s->context_count[i]; j++) {
958                     double p = 128;
959                     if (s->rc_stat2[i][j][k][0] + s->rc_stat2[i][j][k][1] > 200 && j || a+b > 200) {
960                         if (a+b)
961                             p = 256.0 * b / (a + b);
962                         s->initial_states[i][jp][k] =
963                             best_state[av_clip(round(p), 1, 255)][av_clip_uint8((a + b) / gob_count)];
964                         for(jp++; jp<j; jp++)
965                             s->initial_states[i][jp][k] = s->initial_states[i][jp-1][k];
966                         a=b=0;
967                     }
968                     a += s->rc_stat2[i][j][k][0];
969                     b += s->rc_stat2[i][j][k][1];
970                     if (a+b) {
971                         p = 256.0 * b / (a + b);
972                     }
973                     s->initial_states[i][j][k] =
974                         best_state[av_clip(round(p), 1, 255)][av_clip_uint8((a + b) / gob_count)];
975                 }
976             }
977         }
978         av_freep(&best_state);
979     }
980
981     if (s->version > 1) {
982         s->num_v_slices = (avctx->width > 352 || avctx->height > 288 || !avctx->slices) ? 2 : 1;
983         for (; s->num_v_slices < 9; s->num_v_slices++) {
984             for (s->num_h_slices = s->num_v_slices; s->num_h_slices < 2*s->num_v_slices; s->num_h_slices++) {
985                 if (avctx->slices == s->num_h_slices * s->num_v_slices && avctx->slices <= 64 || !avctx->slices)
986                     goto slices_ok;
987             }
988         }
989         av_log(avctx, AV_LOG_ERROR,
990                "Unsupported number %d of slices requested, please specify a "
991                "supported number with -slices (ex:4,6,9,12,16, ...)\n",
992                avctx->slices);
993         return AVERROR(ENOSYS);
994 slices_ok:
995         if ((ret = write_extradata(s)) < 0)
996             return ret;
997     }
998
999     if ((ret = ff_ffv1_init_slice_contexts(s)) < 0)
1000         return ret;
1001     s->slice_count = s->max_slice_count;
1002     if ((ret = ff_ffv1_init_slices_state(s)) < 0)
1003         return ret;
1004
1005 #define STATS_OUT_SIZE 1024 * 1024 * 6
1006     if (avctx->flags & AV_CODEC_FLAG_PASS1) {
1007         avctx->stats_out = av_mallocz(STATS_OUT_SIZE);
1008         if (!avctx->stats_out)
1009             return AVERROR(ENOMEM);
1010         for (i = 0; i < s->quant_table_count; i++)
1011             for (j = 0; j < s->max_slice_count; j++) {
1012                 FFV1Context *sf = s->slice_context[j];
1013                 av_assert0(!sf->rc_stat2[i]);
1014                 sf->rc_stat2[i] = av_mallocz(s->context_count[i] *
1015                                              sizeof(*sf->rc_stat2[i]));
1016                 if (!sf->rc_stat2[i])
1017                     return AVERROR(ENOMEM);
1018             }
1019     }
1020
1021     return 0;
1022 }
1023
1024 static void encode_slice_header(FFV1Context *f, FFV1Context *fs)
1025 {
1026     RangeCoder *c = &fs->c;
1027     uint8_t state[CONTEXT_SIZE];
1028     int j;
1029     memset(state, 128, sizeof(state));
1030
1031     put_symbol(c, state, (fs->slice_x     +1)*f->num_h_slices / f->width   , 0);
1032     put_symbol(c, state, (fs->slice_y     +1)*f->num_v_slices / f->height  , 0);
1033     put_symbol(c, state, (fs->slice_width +1)*f->num_h_slices / f->width -1, 0);
1034     put_symbol(c, state, (fs->slice_height+1)*f->num_v_slices / f->height-1, 0);
1035     for (j=0; j<f->plane_count; j++) {
1036         put_symbol(c, state, f->plane[j].quant_table_index, 0);
1037         av_assert0(f->plane[j].quant_table_index == f->avctx->context_model);
1038     }
1039     if (!f->picture.f->interlaced_frame)
1040         put_symbol(c, state, 3, 0);
1041     else
1042         put_symbol(c, state, 1 + !f->picture.f->top_field_first, 0);
1043     put_symbol(c, state, f->picture.f->sample_aspect_ratio.num, 0);
1044     put_symbol(c, state, f->picture.f->sample_aspect_ratio.den, 0);
1045     if (f->version > 3) {
1046         put_rac(c, state, fs->slice_coding_mode == 1);
1047         if (fs->slice_coding_mode == 1)
1048             ff_ffv1_clear_slice_state(f, fs);
1049         put_symbol(c, state, fs->slice_coding_mode, 0);
1050         if (fs->slice_coding_mode != 1) {
1051             put_symbol(c, state, fs->slice_rct_by_coef, 0);
1052             put_symbol(c, state, fs->slice_rct_ry_coef, 0);
1053         }
1054     }
1055 }
1056
1057 static void choose_rct_params(FFV1Context *fs, const uint8_t *src[3], const int stride[3], int w, int h)
1058 {
1059 #define NB_Y_COEFF 15
1060     static const int rct_y_coeff[15][2] = {
1061         {0, 0}, //      4G
1062         {1, 1}, //  R + 2G + B
1063         {2, 2}, // 2R      + 2B
1064         {0, 2}, //      2G + 2B
1065         {2, 0}, // 2R + 2G
1066         {4, 0}, // 4R
1067         {0, 4}, //           4B
1068
1069         {0, 3}, //      1G + 3B
1070         {3, 0}, // 3R + 1G
1071         {3, 1}, // 3R      +  B
1072         {1, 3}, //  R      + 3B
1073         {1, 2}, //  R +  G + 2B
1074         {2, 1}, // 2R +  G +  B
1075         {0, 1}, //      3G +  B
1076         {1, 0}, //  R + 3G
1077     };
1078
1079     int stat[NB_Y_COEFF] = {0};
1080     int x, y, i, p, best;
1081     int16_t *sample[3];
1082     int lbd = fs->bits_per_raw_sample <= 8;
1083
1084     for (y = 0; y < h; y++) {
1085         int lastr=0, lastg=0, lastb=0;
1086         for (p = 0; p < 3; p++)
1087             sample[p] = fs->sample_buffer + p*w;
1088
1089         for (x = 0; x < w; x++) {
1090             int b, g, r;
1091             int ab, ag, ar;
1092             if (lbd) {
1093                 unsigned v = *((const uint32_t*)(src[0] + x*4 + stride[0]*y));
1094                 b =  v        & 0xFF;
1095                 g = (v >>  8) & 0xFF;
1096                 r = (v >> 16) & 0xFF;
1097             } else {
1098                 b = *((const uint16_t*)(src[0] + x*2 + stride[0]*y));
1099                 g = *((const uint16_t*)(src[1] + x*2 + stride[1]*y));
1100                 r = *((const uint16_t*)(src[2] + x*2 + stride[2]*y));
1101             }
1102
1103             ar = r - lastr;
1104             ag = g - lastg;
1105             ab = b - lastb;
1106             if (x && y) {
1107                 int bg = ag - sample[0][x];
1108                 int bb = ab - sample[1][x];
1109                 int br = ar - sample[2][x];
1110
1111                 br -= bg;
1112                 bb -= bg;
1113
1114                 for (i = 0; i<NB_Y_COEFF; i++) {
1115                     stat[i] += FFABS(bg + ((br*rct_y_coeff[i][0] + bb*rct_y_coeff[i][1])>>2));
1116                 }
1117
1118             }
1119             sample[0][x] = ag;
1120             sample[1][x] = ab;
1121             sample[2][x] = ar;
1122
1123             lastr = r;
1124             lastg = g;
1125             lastb = b;
1126         }
1127     }
1128
1129     best = 0;
1130     for (i=1; i<NB_Y_COEFF; i++) {
1131         if (stat[i] < stat[best])
1132             best = i;
1133     }
1134
1135     fs->slice_rct_by_coef = rct_y_coeff[best][1];
1136     fs->slice_rct_ry_coef = rct_y_coeff[best][0];
1137 }
1138
1139 static int encode_slice(AVCodecContext *c, void *arg)
1140 {
1141     FFV1Context *fs  = *(void **)arg;
1142     FFV1Context *f   = fs->avctx->priv_data;
1143     int width        = fs->slice_width;
1144     int height       = fs->slice_height;
1145     int x            = fs->slice_x;
1146     int y            = fs->slice_y;
1147     const AVFrame *const p = f->picture.f;
1148     const int ps     = av_pix_fmt_desc_get(c->pix_fmt)->comp[0].step;
1149     int ret;
1150     RangeCoder c_bak = fs->c;
1151     const uint8_t *planes[3] = {p->data[0] + ps*x + y*p->linesize[0],
1152                                 p->data[1] + ps*x + y*p->linesize[1],
1153                                 p->data[2] + ps*x + y*p->linesize[2]};
1154
1155     fs->slice_coding_mode = 0;
1156     if (f->version > 3) {
1157         choose_rct_params(fs, planes, p->linesize, width, height);
1158     } else {
1159         fs->slice_rct_by_coef = 1;
1160         fs->slice_rct_ry_coef = 1;
1161     }
1162
1163 retry:
1164     if (f->key_frame)
1165         ff_ffv1_clear_slice_state(f, fs);
1166     if (f->version > 2) {
1167         encode_slice_header(f, fs);
1168     }
1169     if (fs->ac == AC_GOLOMB_RICE) {
1170         if (f->version > 2)
1171             put_rac(&fs->c, (uint8_t[]) { 129 }, 0);
1172         fs->ac_byte_count = f->version > 2 || (!x && !y) ? ff_rac_terminate(&fs->c) : 0;
1173         init_put_bits(&fs->pb,
1174                       fs->c.bytestream_start + fs->ac_byte_count,
1175                       fs->c.bytestream_end - fs->c.bytestream_start - fs->ac_byte_count);
1176     }
1177
1178     if (f->colorspace == 0 && c->pix_fmt != AV_PIX_FMT_YA8) {
1179         const int chroma_width  = AV_CEIL_RSHIFT(width,  f->chroma_h_shift);
1180         const int chroma_height = AV_CEIL_RSHIFT(height, f->chroma_v_shift);
1181         const int cx            = x >> f->chroma_h_shift;
1182         const int cy            = y >> f->chroma_v_shift;
1183
1184         ret = encode_plane(fs, p->data[0] + ps*x + y*p->linesize[0], width, height, p->linesize[0], 0, 1);
1185
1186         if (f->chroma_planes) {
1187             ret |= encode_plane(fs, p->data[1] + ps*cx+cy*p->linesize[1], chroma_width, chroma_height, p->linesize[1], 1, 1);
1188             ret |= encode_plane(fs, p->data[2] + ps*cx+cy*p->linesize[2], chroma_width, chroma_height, p->linesize[2], 1, 1);
1189         }
1190         if (fs->transparency)
1191             ret |= encode_plane(fs, p->data[3] + ps*x + y*p->linesize[3], width, height, p->linesize[3], 2, 1);
1192     } else if (c->pix_fmt == AV_PIX_FMT_YA8) {
1193         ret  = encode_plane(fs, p->data[0] +     ps*x + y*p->linesize[0], width, height, p->linesize[0], 0, 2);
1194         ret |= encode_plane(fs, p->data[0] + 1 + ps*x + y*p->linesize[0], width, height, p->linesize[0], 1, 2);
1195     } else {
1196         ret = encode_rgb_frame(fs, planes, width, height, p->linesize);
1197     }
1198     emms_c();
1199
1200     if (ret < 0) {
1201         av_assert0(fs->slice_coding_mode == 0);
1202         if (fs->version < 4 || !fs->ac) {
1203             av_log(c, AV_LOG_ERROR, "Buffer too small\n");
1204             return ret;
1205         }
1206         av_log(c, AV_LOG_DEBUG, "Coding slice as PCM\n");
1207         fs->slice_coding_mode = 1;
1208         fs->c = c_bak;
1209         goto retry;
1210     }
1211
1212     return 0;
1213 }
1214
1215 static int encode_frame(AVCodecContext *avctx, AVPacket *pkt,
1216                         const AVFrame *pict, int *got_packet)
1217 {
1218     FFV1Context *f      = avctx->priv_data;
1219     RangeCoder *const c = &f->slice_context[0]->c;
1220     AVFrame *const p    = f->picture.f;
1221     int used_count      = 0;
1222     uint8_t keystate    = 128;
1223     uint8_t *buf_p;
1224     int i, ret;
1225     int64_t maxsize =   AV_INPUT_BUFFER_MIN_SIZE
1226                       + avctx->width*avctx->height*35LL*4;
1227
1228     if(!pict) {
1229         if (avctx->flags & AV_CODEC_FLAG_PASS1) {
1230             int j, k, m;
1231             char *p   = avctx->stats_out;
1232             char *end = p + STATS_OUT_SIZE;
1233
1234             memset(f->rc_stat, 0, sizeof(f->rc_stat));
1235             for (i = 0; i < f->quant_table_count; i++)
1236                 memset(f->rc_stat2[i], 0, f->context_count[i] * sizeof(*f->rc_stat2[i]));
1237
1238             av_assert0(f->slice_count == f->max_slice_count);
1239             for (j = 0; j < f->slice_count; j++) {
1240                 FFV1Context *fs = f->slice_context[j];
1241                 for (i = 0; i < 256; i++) {
1242                     f->rc_stat[i][0] += fs->rc_stat[i][0];
1243                     f->rc_stat[i][1] += fs->rc_stat[i][1];
1244                 }
1245                 for (i = 0; i < f->quant_table_count; i++) {
1246                     for (k = 0; k < f->context_count[i]; k++)
1247                         for (m = 0; m < 32; m++) {
1248                             f->rc_stat2[i][k][m][0] += fs->rc_stat2[i][k][m][0];
1249                             f->rc_stat2[i][k][m][1] += fs->rc_stat2[i][k][m][1];
1250                         }
1251                 }
1252             }
1253
1254             for (j = 0; j < 256; j++) {
1255                 snprintf(p, end - p, "%" PRIu64 " %" PRIu64 " ",
1256                         f->rc_stat[j][0], f->rc_stat[j][1]);
1257                 p += strlen(p);
1258             }
1259             snprintf(p, end - p, "\n");
1260
1261             for (i = 0; i < f->quant_table_count; i++) {
1262                 for (j = 0; j < f->context_count[i]; j++)
1263                     for (m = 0; m < 32; m++) {
1264                         snprintf(p, end - p, "%" PRIu64 " %" PRIu64 " ",
1265                                 f->rc_stat2[i][j][m][0], f->rc_stat2[i][j][m][1]);
1266                         p += strlen(p);
1267                     }
1268             }
1269             snprintf(p, end - p, "%d\n", f->gob_count);
1270         }
1271         return 0;
1272     }
1273
1274     if (f->version > 3)
1275         maxsize = AV_INPUT_BUFFER_MIN_SIZE + avctx->width*avctx->height*3LL*4;
1276
1277     if ((ret = ff_alloc_packet2(avctx, pkt, maxsize, 0)) < 0)
1278         return ret;
1279
1280     ff_init_range_encoder(c, pkt->data, pkt->size);
1281     ff_build_rac_states(c, 0.05 * (1LL << 32), 256 - 8);
1282
1283     av_frame_unref(p);
1284     if ((ret = av_frame_ref(p, pict)) < 0)
1285         return ret;
1286     avctx->coded_frame->pict_type = AV_PICTURE_TYPE_I;
1287
1288     if (avctx->gop_size == 0 || f->picture_number % avctx->gop_size == 0) {
1289         put_rac(c, &keystate, 1);
1290         f->key_frame = 1;
1291         f->gob_count++;
1292         write_header(f);
1293     } else {
1294         put_rac(c, &keystate, 0);
1295         f->key_frame = 0;
1296     }
1297
1298     if (f->ac == AC_RANGE_CUSTOM_TAB) {
1299         int i;
1300         for (i = 1; i < 256; i++) {
1301             c->one_state[i]        = f->state_transition[i];
1302             c->zero_state[256 - i] = 256 - c->one_state[i];
1303         }
1304     }
1305
1306     for (i = 1; i < f->slice_count; i++) {
1307         FFV1Context *fs = f->slice_context[i];
1308         uint8_t *start  = pkt->data + (pkt->size - used_count) * (int64_t)i / f->slice_count;
1309         int len         = pkt->size / f->slice_count;
1310         ff_init_range_encoder(&fs->c, start, len);
1311     }
1312     avctx->execute(avctx, encode_slice, &f->slice_context[0], NULL,
1313                    f->slice_count, sizeof(void *));
1314
1315     buf_p = pkt->data;
1316     for (i = 0; i < f->slice_count; i++) {
1317         FFV1Context *fs = f->slice_context[i];
1318         int bytes;
1319
1320         if (fs->ac != AC_GOLOMB_RICE) {
1321             uint8_t state = 129;
1322             put_rac(&fs->c, &state, 0);
1323             bytes = ff_rac_terminate(&fs->c);
1324         } else {
1325             flush_put_bits(&fs->pb); // FIXME: nicer padding
1326             bytes = fs->ac_byte_count + (put_bits_count(&fs->pb) + 7) / 8;
1327         }
1328         if (i > 0 || f->version > 2) {
1329             av_assert0(bytes < pkt->size / f->slice_count);
1330             memmove(buf_p, fs->c.bytestream_start, bytes);
1331             av_assert0(bytes < (1 << 24));
1332             AV_WB24(buf_p + bytes, bytes);
1333             bytes += 3;
1334         }
1335         if (f->ec) {
1336             unsigned v;
1337             buf_p[bytes++] = 0;
1338             v = av_crc(av_crc_get_table(AV_CRC_32_IEEE), 0, buf_p, bytes);
1339             AV_WL32(buf_p + bytes, v);
1340             bytes += 4;
1341         }
1342         buf_p += bytes;
1343     }
1344
1345     if (avctx->flags & AV_CODEC_FLAG_PASS1)
1346         avctx->stats_out[0] = '\0';
1347
1348 #if FF_API_CODED_FRAME
1349 FF_DISABLE_DEPRECATION_WARNINGS
1350     avctx->coded_frame->key_frame = f->key_frame;
1351 FF_ENABLE_DEPRECATION_WARNINGS
1352 #endif
1353
1354     f->picture_number++;
1355     pkt->size   = buf_p - pkt->data;
1356     pkt->pts    =
1357     pkt->dts    = pict->pts;
1358     pkt->flags |= AV_PKT_FLAG_KEY * f->key_frame;
1359     *got_packet = 1;
1360
1361     return 0;
1362 }
1363
1364 static av_cold int encode_close(AVCodecContext *avctx)
1365 {
1366     ff_ffv1_close(avctx);
1367     return 0;
1368 }
1369
1370 #define OFFSET(x) offsetof(FFV1Context, x)
1371 #define VE AV_OPT_FLAG_VIDEO_PARAM | AV_OPT_FLAG_ENCODING_PARAM
1372 static const AVOption options[] = {
1373     { "slicecrc", "Protect slices with CRCs", OFFSET(ec), AV_OPT_TYPE_BOOL, { .i64 = -1 }, -1, 1, VE },
1374     { "coder", "Coder type", OFFSET(ac), AV_OPT_TYPE_INT,
1375             { .i64 = 0 }, -2, 2, VE, "coder" },
1376         { "rice", "Golomb rice", 0, AV_OPT_TYPE_CONST,
1377             { .i64 = AC_GOLOMB_RICE }, INT_MIN, INT_MAX, VE, "coder" },
1378         { "range_def", "Range with default table", 0, AV_OPT_TYPE_CONST,
1379             { .i64 = AC_RANGE_DEFAULT_TAB_FORCE }, INT_MIN, INT_MAX, VE, "coder" },
1380         { "range_tab", "Range with custom table", 0, AV_OPT_TYPE_CONST,
1381             { .i64 = AC_RANGE_CUSTOM_TAB }, INT_MIN, INT_MAX, VE, "coder" },
1382         { "ac", "Range with custom table (the ac option exists for compatibility and is deprecated)", 0, AV_OPT_TYPE_CONST,
1383             { .i64 = 1 }, INT_MIN, INT_MAX, VE, "coder" },
1384
1385     { NULL }
1386 };
1387
1388 static const AVClass ffv1_class = {
1389     .class_name = "ffv1 encoder",
1390     .item_name  = av_default_item_name,
1391     .option     = options,
1392     .version    = LIBAVUTIL_VERSION_INT,
1393 };
1394
1395 #if FF_API_CODER_TYPE
1396 static const AVCodecDefault ffv1_defaults[] = {
1397     { "coder", "-1" },
1398     { NULL },
1399 };
1400 #endif
1401
1402 AVCodec ff_ffv1_encoder = {
1403     .name           = "ffv1",
1404     .long_name      = NULL_IF_CONFIG_SMALL("FFmpeg video codec #1"),
1405     .type           = AVMEDIA_TYPE_VIDEO,
1406     .id             = AV_CODEC_ID_FFV1,
1407     .priv_data_size = sizeof(FFV1Context),
1408     .init           = encode_init,
1409     .encode2        = encode_frame,
1410     .close          = encode_close,
1411     .capabilities   = AV_CODEC_CAP_SLICE_THREADS | AV_CODEC_CAP_DELAY,
1412     .pix_fmts       = (const enum AVPixelFormat[]) {
1413         AV_PIX_FMT_YUV420P,   AV_PIX_FMT_YUVA420P,  AV_PIX_FMT_YUVA422P,  AV_PIX_FMT_YUV444P,
1414         AV_PIX_FMT_YUVA444P,  AV_PIX_FMT_YUV440P,   AV_PIX_FMT_YUV422P,   AV_PIX_FMT_YUV411P,
1415         AV_PIX_FMT_YUV410P,   AV_PIX_FMT_0RGB32,    AV_PIX_FMT_RGB32,     AV_PIX_FMT_YUV420P16,
1416         AV_PIX_FMT_YUV422P16, AV_PIX_FMT_YUV444P16, AV_PIX_FMT_YUV444P9,  AV_PIX_FMT_YUV422P9,
1417         AV_PIX_FMT_YUV420P9,  AV_PIX_FMT_YUV420P10, AV_PIX_FMT_YUV422P10, AV_PIX_FMT_YUV444P10,
1418         AV_PIX_FMT_YUVA444P16, AV_PIX_FMT_YUVA422P16, AV_PIX_FMT_YUVA420P16,
1419         AV_PIX_FMT_YUVA444P10, AV_PIX_FMT_YUVA422P10, AV_PIX_FMT_YUVA420P10,
1420         AV_PIX_FMT_YUVA444P9, AV_PIX_FMT_YUVA422P9, AV_PIX_FMT_YUVA420P9,
1421         AV_PIX_FMT_GRAY16,    AV_PIX_FMT_GRAY8,     AV_PIX_FMT_GBRP9,     AV_PIX_FMT_GBRP10,
1422         AV_PIX_FMT_GBRP12,    AV_PIX_FMT_GBRP14,
1423         AV_PIX_FMT_YA8,
1424         AV_PIX_FMT_NONE
1425
1426     },
1427 #if FF_API_CODER_TYPE
1428     .defaults       = ffv1_defaults,
1429 #endif
1430     .priv_class     = &ffv1_class,
1431 };