Merge commit '94aefb1932be882fd93f66cf790ceb19ff575c19'
[ffmpeg.git] / libavcodec / 4xm.c
1 /*
2  * 4XM codec
3  * Copyright (c) 2003 Michael Niedermayer
4  *
5  * This file is part of FFmpeg.
6  *
7  * FFmpeg is free software; you can redistribute it and/or
8  * modify it under the terms of the GNU Lesser General Public
9  * License as published by the Free Software Foundation; either
10  * version 2.1 of the License, or (at your option) any later version.
11  *
12  * FFmpeg is distributed in the hope that it will be useful,
13  * but WITHOUT ANY WARRANTY; without even the implied warranty of
14  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
15  * Lesser General Public License for more details.
16  *
17  * You should have received a copy of the GNU Lesser General Public
18  * License along with FFmpeg; if not, write to the Free Software
19  * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
20  */
21
22 /**
23  * @file
24  * 4XM codec.
25  */
26
27 #include "libavutil/avassert.h"
28 #include "libavutil/frame.h"
29 #include "libavutil/intreadwrite.h"
30 #include "avcodec.h"
31 #include "bytestream.h"
32 #include "dsputil.h"
33 #include "get_bits.h"
34 #include "internal.h"
35
36
37 #define BLOCK_TYPE_VLC_BITS 5
38 #define ACDC_VLC_BITS 9
39
40 #define CFRAME_BUFFER_COUNT 100
41
42 static const uint8_t block_type_tab[2][4][8][2] = {
43     {
44         {    // { 8, 4, 2 } x { 8, 4, 2}
45             { 0, 1 }, { 2, 2 }, { 6, 3 }, { 14, 4 }, { 30, 5 }, { 31, 5 }, { 0, 0 }
46         }, { // { 8, 4 } x 1
47             { 0, 1 }, { 0, 0 }, { 2, 2 }, { 6, 3 }, { 14, 4 }, { 15, 4 }, { 0, 0 }
48         }, { // 1 x { 8, 4 }
49             { 0, 1 }, { 2, 2 }, { 0, 0 }, { 6, 3 }, { 14, 4 }, { 15, 4 }, { 0, 0 }
50         }, { // 1 x 2, 2 x 1
51             { 0, 1 }, { 0, 0 }, { 0, 0 }, { 2, 2 }, { 6, 3 }, { 14, 4 }, { 15, 4 }
52         }
53     }, {
54         {   // { 8, 4, 2 } x { 8, 4, 2}
55             { 1, 2 }, { 4, 3 }, { 5, 3 }, { 0, 2 }, { 6, 3 }, { 7, 3 }, { 0, 0 }
56         }, {// { 8, 4 } x 1
57             { 1, 2 }, { 0, 0 }, { 2, 2 }, { 0, 2 }, { 6, 3 }, { 7, 3 }, { 0, 0 }
58         }, {// 1 x { 8, 4 }
59             { 1, 2 }, { 2, 2 }, { 0, 0 }, { 0, 2 }, { 6, 3 }, { 7, 3 }, { 0, 0 }
60         }, {// 1 x 2, 2 x 1
61             { 1, 2 }, { 0, 0 }, { 0, 0 }, { 0, 2 }, { 2, 2 }, { 6, 3 }, { 7, 3 }
62       }
63     }
64 };
65
66 static const uint8_t size2index[4][4] = {
67     { -1, 3, 1, 1 },
68     {  3, 0, 0, 0 },
69     {  2, 0, 0, 0 },
70     {  2, 0, 0, 0 },
71 };
72
73 static const int8_t mv[256][2] = {
74     {   0,   0 }, {   0,  -1 }, {  -1,   0 }, {   1,   0 }, {   0,   1 }, {  -1,  -1 }, {   1,  -1 }, {  -1,   1 },
75     {   1,   1 }, {   0,  -2 }, {  -2,   0 }, {   2,   0 }, {   0,   2 }, {  -1,  -2 }, {   1,  -2 }, {  -2,  -1 },
76     {   2,  -1 }, {  -2,   1 }, {   2,   1 }, {  -1,   2 }, {   1,   2 }, {  -2,  -2 }, {   2,  -2 }, {  -2,   2 },
77     {   2,   2 }, {   0,  -3 }, {  -3,   0 }, {   3,   0 }, {   0,   3 }, {  -1,  -3 }, {   1,  -3 }, {  -3,  -1 },
78     {   3,  -1 }, {  -3,   1 }, {   3,   1 }, {  -1,   3 }, {   1,   3 }, {  -2,  -3 }, {   2,  -3 }, {  -3,  -2 },
79     {   3,  -2 }, {  -3,   2 }, {   3,   2 }, {  -2,   3 }, {   2,   3 }, {   0,  -4 }, {  -4,   0 }, {   4,   0 },
80     {   0,   4 }, {  -1,  -4 }, {   1,  -4 }, {  -4,  -1 }, {   4,  -1 }, {   4,   1 }, {  -1,   4 }, {   1,   4 },
81     {  -3,  -3 }, {  -3,   3 }, {   3,   3 }, {  -2,  -4 }, {  -4,  -2 }, {   4,  -2 }, {  -4,   2 }, {  -2,   4 },
82     {   2,   4 }, {  -3,  -4 }, {   3,  -4 }, {   4,  -3 }, {  -5,   0 }, {  -4,   3 }, {  -3,   4 }, {   3,   4 },
83     {  -1,  -5 }, {  -5,  -1 }, {  -5,   1 }, {  -1,   5 }, {  -2,  -5 }, {   2,  -5 }, {   5,  -2 }, {   5,   2 },
84     {  -4,  -4 }, {  -4,   4 }, {  -3,  -5 }, {  -5,  -3 }, {  -5,   3 }, {   3,   5 }, {  -6,   0 }, {   0,   6 },
85     {  -6,  -1 }, {  -6,   1 }, {   1,   6 }, {   2,  -6 }, {  -6,   2 }, {   2,   6 }, {  -5,  -4 }, {   5,   4 },
86     {   4,   5 }, {  -6,  -3 }, {   6,   3 }, {  -7,   0 }, {  -1,  -7 }, {   5,  -5 }, {  -7,   1 }, {  -1,   7 },
87     {   4,  -6 }, {   6,   4 }, {  -2,  -7 }, {  -7,   2 }, {  -3,  -7 }, {   7,  -3 }, {   3,   7 }, {   6,  -5 },
88     {   0,  -8 }, {  -1,  -8 }, {  -7,  -4 }, {  -8,   1 }, {   4,   7 }, {   2,  -8 }, {  -2,   8 }, {   6,   6 },
89     {  -8,   3 }, {   5,  -7 }, {  -5,   7 }, {   8,  -4 }, {   0,  -9 }, {  -9,  -1 }, {   1,   9 }, {   7,  -6 },
90     {  -7,   6 }, {  -5,  -8 }, {  -5,   8 }, {  -9,   3 }, {   9,  -4 }, {   7,  -7 }, {   8,  -6 }, {   6,   8 },
91     {  10,   1 }, { -10,   2 }, {   9,  -5 }, {  10,  -3 }, {  -8,  -7 }, { -10,  -4 }, {   6,  -9 }, { -11,   0 },
92     {  11,   1 }, { -11,  -2 }, {  -2,  11 }, {   7,  -9 }, {  -7,   9 }, {  10,   6 }, {  -4,  11 }, {   8,  -9 },
93     {   8,   9 }, {   5,  11 }, {   7, -10 }, {  12,  -3 }, {  11,   6 }, {  -9,  -9 }, {   8,  10 }, {   5,  12 },
94     { -11,   7 }, {  13,   2 }, {   6, -12 }, {  10,   9 }, { -11,   8 }, {  -7,  12 }, {   0,  14 }, {  14,  -2 },
95     {  -9,  11 }, {  -6,  13 }, { -14,  -4 }, {  -5, -14 }, {   5,  14 }, { -15,  -1 }, { -14,  -6 }, {   3, -15 },
96     {  11, -11 }, {  -7,  14 }, {  -5,  15 }, {   8, -14 }, {  15,   6 }, {   3,  16 }, {   7, -15 }, { -16,   5 },
97     {   0,  17 }, { -16,  -6 }, { -10,  14 }, { -16,   7 }, {  12,  13 }, { -16,   8 }, { -17,   6 }, { -18,   3 },
98     {  -7,  17 }, {  15,  11 }, {  16,  10 }, {   2, -19 }, {   3, -19 }, { -11, -16 }, { -18,   8 }, { -19,  -6 },
99     {   2, -20 }, { -17, -11 }, { -10, -18 }, {   8,  19 }, { -21,  -1 }, { -20,   7 }, {  -4,  21 }, {  21,   5 },
100     {  15,  16 }, {   2, -22 }, { -10, -20 }, { -22,   5 }, {  20, -11 }, {  -7, -22 }, { -12,  20 }, {  23,  -5 },
101     {  13, -20 }, {  24,  -2 }, { -15,  19 }, { -11,  22 }, {  16,  19 }, {  23, -10 }, { -18, -18 }, {  -9, -24 },
102     {  24, -10 }, {  -3,  26 }, { -23,  13 }, { -18, -20 }, {  17,  21 }, {  -4,  27 }, {  27,   6 }, {   1, -28 },
103     { -11,  26 }, { -17, -23 }, {   7,  28 }, {  11, -27 }, {  29,   5 }, { -23, -19 }, { -28, -11 }, { -21,  22 },
104     { -30,   7 }, { -17,  26 }, { -27,  16 }, {  13,  29 }, {  19, -26 }, {  10, -31 }, { -14, -30 }, {  20, -27 },
105     { -29,  18 }, { -16, -31 }, { -28, -22 }, {  21, -30 }, { -25,  28 }, {  26, -29 }, {  25, -32 }, { -32, -32 }
106 };
107
108 /* This is simply the scaled down elementwise product of the standard JPEG
109  * quantizer table and the AAN premul table. */
110 static const uint8_t dequant_table[64] = {
111     16, 15, 13, 19, 24, 31, 28, 17,
112     17, 23, 25, 31, 36, 63, 45, 21,
113     18, 24, 27, 37, 52, 59, 49, 20,
114     16, 28, 34, 40, 60, 80, 51, 20,
115     18, 31, 48, 66, 68, 86, 56, 21,
116     19, 38, 56, 59, 64, 64, 48, 20,
117     27, 48, 55, 55, 56, 51, 35, 15,
118     20, 35, 34, 32, 31, 22, 15,  8,
119 };
120
121 static VLC block_type_vlc[2][4];
122
123
124 typedef struct CFrameBuffer {
125     unsigned int allocated_size;
126     unsigned int size;
127     int id;
128     uint8_t *data;
129 } CFrameBuffer;
130
131 typedef struct FourXContext {
132     AVCodecContext *avctx;
133     DSPContext dsp;
134     AVFrame *current_picture, *last_picture;
135     GetBitContext pre_gb;          ///< ac/dc prefix
136     GetBitContext gb;
137     GetByteContext g;
138     GetByteContext g2;
139     int mv[256];
140     VLC pre_vlc;
141     int last_dc;
142     DECLARE_ALIGNED(16, int16_t, block)[6][64];
143     void *bitstream_buffer;
144     unsigned int bitstream_buffer_size;
145     int version;
146     CFrameBuffer cfrm[CFRAME_BUFFER_COUNT];
147 } FourXContext;
148
149
150 #define FIX_1_082392200  70936
151 #define FIX_1_414213562  92682
152 #define FIX_1_847759065 121095
153 #define FIX_2_613125930 171254
154
155 #define MULTIPLY(var, const) (((var) * (const)) >> 16)
156
157 static void idct(int16_t block[64])
158 {
159     int tmp0, tmp1, tmp2, tmp3, tmp4, tmp5, tmp6, tmp7;
160     int tmp10, tmp11, tmp12, tmp13;
161     int z5, z10, z11, z12, z13;
162     int i;
163     int temp[64];
164
165     for (i = 0; i < 8; i++) {
166         tmp10 = block[8 * 0 + i] + block[8 * 4 + i];
167         tmp11 = block[8 * 0 + i] - block[8 * 4 + i];
168
169         tmp13 = block[8 * 2 + i] + block[8 * 6 + i];
170         tmp12 = MULTIPLY(block[8 * 2 + i] - block[8 * 6 + i], FIX_1_414213562) - tmp13;
171
172         tmp0 = tmp10 + tmp13;
173         tmp3 = tmp10 - tmp13;
174         tmp1 = tmp11 + tmp12;
175         tmp2 = tmp11 - tmp12;
176
177         z13 = block[8 * 5 + i] + block[8 * 3 + i];
178         z10 = block[8 * 5 + i] - block[8 * 3 + i];
179         z11 = block[8 * 1 + i] + block[8 * 7 + i];
180         z12 = block[8 * 1 + i] - block[8 * 7 + i];
181
182         tmp7  =          z11 + z13;
183         tmp11 = MULTIPLY(z11 - z13, FIX_1_414213562);
184
185         z5    = MULTIPLY(z10 + z12, FIX_1_847759065);
186         tmp10 = MULTIPLY(z12,  FIX_1_082392200) - z5;
187         tmp12 = MULTIPLY(z10, -FIX_2_613125930) + z5;
188
189         tmp6 = tmp12 - tmp7;
190         tmp5 = tmp11 - tmp6;
191         tmp4 = tmp10 + tmp5;
192
193         temp[8 * 0 + i] = tmp0 + tmp7;
194         temp[8 * 7 + i] = tmp0 - tmp7;
195         temp[8 * 1 + i] = tmp1 + tmp6;
196         temp[8 * 6 + i] = tmp1 - tmp6;
197         temp[8 * 2 + i] = tmp2 + tmp5;
198         temp[8 * 5 + i] = tmp2 - tmp5;
199         temp[8 * 4 + i] = tmp3 + tmp4;
200         temp[8 * 3 + i] = tmp3 - tmp4;
201     }
202
203     for (i = 0; i < 8 * 8; i += 8) {
204         tmp10 = temp[0 + i] + temp[4 + i];
205         tmp11 = temp[0 + i] - temp[4 + i];
206
207         tmp13 = temp[2 + i] + temp[6 + i];
208         tmp12 = MULTIPLY(temp[2 + i] - temp[6 + i], FIX_1_414213562) - tmp13;
209
210         tmp0 = tmp10 + tmp13;
211         tmp3 = tmp10 - tmp13;
212         tmp1 = tmp11 + tmp12;
213         tmp2 = tmp11 - tmp12;
214
215         z13 = temp[5 + i] + temp[3 + i];
216         z10 = temp[5 + i] - temp[3 + i];
217         z11 = temp[1 + i] + temp[7 + i];
218         z12 = temp[1 + i] - temp[7 + i];
219
220         tmp7  = z11 + z13;
221         tmp11 = MULTIPLY(z11 - z13, FIX_1_414213562);
222
223         z5    = MULTIPLY(z10 + z12, FIX_1_847759065);
224         tmp10 = MULTIPLY(z12,  FIX_1_082392200) - z5;
225         tmp12 = MULTIPLY(z10, -FIX_2_613125930) + z5;
226
227         tmp6 = tmp12 - tmp7;
228         tmp5 = tmp11 - tmp6;
229         tmp4 = tmp10 + tmp5;
230
231         block[0 + i] = (tmp0 + tmp7) >> 6;
232         block[7 + i] = (tmp0 - tmp7) >> 6;
233         block[1 + i] = (tmp1 + tmp6) >> 6;
234         block[6 + i] = (tmp1 - tmp6) >> 6;
235         block[2 + i] = (tmp2 + tmp5) >> 6;
236         block[5 + i] = (tmp2 - tmp5) >> 6;
237         block[4 + i] = (tmp3 + tmp4) >> 6;
238         block[3 + i] = (tmp3 - tmp4) >> 6;
239     }
240 }
241
242 static av_cold void init_vlcs(FourXContext *f)
243 {
244     static VLC_TYPE table[2][4][32][2];
245     int i, j;
246
247     for (i = 0; i < 2; i++) {
248         for (j = 0; j < 4; j++) {
249             block_type_vlc[i][j].table           = table[i][j];
250             block_type_vlc[i][j].table_allocated = 32;
251             init_vlc(&block_type_vlc[i][j], BLOCK_TYPE_VLC_BITS, 7,
252                      &block_type_tab[i][j][0][1], 2, 1,
253                      &block_type_tab[i][j][0][0], 2, 1,
254                      INIT_VLC_USE_NEW_STATIC);
255         }
256     }
257 }
258
259 static void init_mv(FourXContext *f, int linesize)
260 {
261     int i;
262
263     for (i = 0; i < 256; i++) {
264         if (f->version > 1)
265             f->mv[i] = mv[i][0] + mv[i][1] * linesize / 2;
266         else
267             f->mv[i] = (i & 15) - 8 + ((i >> 4) - 8) * linesize / 2;
268     }
269 }
270
271 #if HAVE_BIGENDIAN
272 #define LE_CENTRIC_MUL(dst, src, scale, dc)             \
273     {                                                   \
274         unsigned tmpval = AV_RN32(src);                 \
275         tmpval = (tmpval << 16) | (tmpval >> 16);       \
276         tmpval = tmpval * (scale) + (dc);               \
277         tmpval = (tmpval << 16) | (tmpval >> 16);       \
278         AV_WN32A(dst, tmpval);                          \
279     }
280 #else
281 #define LE_CENTRIC_MUL(dst, src, scale, dc)              \
282     {                                                    \
283         unsigned tmpval = AV_RN32(src) * (scale) + (dc); \
284         AV_WN32A(dst, tmpval);                           \
285     }
286 #endif
287
288 static inline void mcdc(uint16_t *dst, const uint16_t *src, int log2w,
289                         int h, int stride, int scale, unsigned dc)
290 {
291     int i;
292     dc *= 0x10001;
293
294     switch (log2w) {
295     case 0:
296         for (i = 0; i < h; i++) {
297             dst[0] = scale * src[0] + dc;
298             if (scale)
299                 src += stride;
300             dst += stride;
301         }
302         break;
303     case 1:
304         for (i = 0; i < h; i++) {
305             LE_CENTRIC_MUL(dst, src, scale, dc);
306             if (scale)
307                 src += stride;
308             dst += stride;
309         }
310         break;
311     case 2:
312         for (i = 0; i < h; i++) {
313             LE_CENTRIC_MUL(dst, src, scale, dc);
314             LE_CENTRIC_MUL(dst + 2, src + 2, scale, dc);
315             if (scale)
316                 src += stride;
317             dst += stride;
318         }
319         break;
320     case 3:
321         for (i = 0; i < h; i++) {
322             LE_CENTRIC_MUL(dst,     src,     scale, dc);
323             LE_CENTRIC_MUL(dst + 2, src + 2, scale, dc);
324             LE_CENTRIC_MUL(dst + 4, src + 4, scale, dc);
325             LE_CENTRIC_MUL(dst + 6, src + 6, scale, dc);
326             if (scale)
327                 src += stride;
328             dst += stride;
329         }
330         break;
331     default:
332         av_assert0(0);
333     }
334 }
335
336 static int decode_p_block(FourXContext *f, uint16_t *dst, uint16_t *src,
337                           int log2w, int log2h, int stride)
338 {
339     const int index = size2index[log2h][log2w];
340     const int h     = 1 << log2h;
341     int code        = get_vlc2(&f->gb,
342                                block_type_vlc[1 - (f->version > 1)][index].table,
343                                BLOCK_TYPE_VLC_BITS, 1);
344     uint16_t *start = (uint16_t *)f->last_picture->data[0];
345     uint16_t *end   = start + stride * (f->avctx->height - h + 1) - (1 << log2w);
346     int ret;
347
348     av_assert0(code >= 0 && code <= 6 && log2w >= 0);
349
350     if (code == 0) {
351         if (bytestream2_get_bytes_left(&f->g) < 1) {
352             av_log(f->avctx, AV_LOG_ERROR, "bytestream overread\n");
353             return AVERROR_INVALIDDATA;
354         }
355         src += f->mv[bytestream2_get_byteu(&f->g)];
356         if (start > src || src > end) {
357             av_log(f->avctx, AV_LOG_ERROR, "mv out of pic\n");
358             return AVERROR_INVALIDDATA;
359         }
360         mcdc(dst, src, log2w, h, stride, 1, 0);
361     } else if (code == 1) {
362         log2h--;
363         if ((ret = decode_p_block(f, dst, src, log2w, log2h, stride)) < 0)
364             return ret;
365         if ((ret = decode_p_block(f, dst + (stride << log2h),
366                                   src + (stride << log2h),
367                                   log2w, log2h, stride)) < 0)
368             return ret;
369     } else if (code == 2) {
370         log2w--;
371         if ((ret = decode_p_block(f, dst , src, log2w, log2h, stride)) < 0)
372             return ret;
373         if ((ret = decode_p_block(f, dst + (1 << log2w),
374                                   src + (1 << log2w),
375                                   log2w, log2h, stride)) < 0)
376             return ret;
377     } else if (code == 3 && f->version < 2) {
378         av_assert0(start <= src && src <= end);
379         mcdc(dst, src, log2w, h, stride, 1, 0);
380     } else if (code == 4) {
381         if (bytestream2_get_bytes_left(&f->g) < 1) {
382             av_log(f->avctx, AV_LOG_ERROR, "bytestream overread\n");
383             return AVERROR_INVALIDDATA;
384         }
385         src += f->mv[bytestream2_get_byteu(&f->g)];
386         if (start > src || src > end) {
387             av_log(f->avctx, AV_LOG_ERROR, "mv out of pic\n");
388             return AVERROR_INVALIDDATA;
389         }
390         if (bytestream2_get_bytes_left(&f->g2) < 2){
391             av_log(f->avctx, AV_LOG_ERROR, "wordstream overread\n");
392             return AVERROR_INVALIDDATA;
393         }
394         mcdc(dst, src, log2w, h, stride, 1, bytestream2_get_le16u(&f->g2));
395     } else if (code == 5) {
396         if (bytestream2_get_bytes_left(&f->g2) < 2) {
397             av_log(f->avctx, AV_LOG_ERROR, "wordstream overread\n");
398             return AVERROR_INVALIDDATA;
399         }
400         av_assert0(start <= src && src <= end);
401         mcdc(dst, src, log2w, h, stride, 0, bytestream2_get_le16u(&f->g2));
402     } else if (code == 6) {
403         if (bytestream2_get_bytes_left(&f->g2) < 4) {
404             av_log(f->avctx, AV_LOG_ERROR, "wordstream overread\n");
405             return AVERROR_INVALIDDATA;
406         }
407         if (log2w) {
408             dst[0]      = bytestream2_get_le16u(&f->g2);
409             dst[1]      = bytestream2_get_le16u(&f->g2);
410         } else {
411             dst[0]      = bytestream2_get_le16u(&f->g2);
412             dst[stride] = bytestream2_get_le16u(&f->g2);
413         }
414     }
415     return 0;
416 }
417
418 static int decode_p_frame(FourXContext *f, AVFrame *frame,
419                           const uint8_t *buf, int length)
420 {
421     int x, y;
422     const int width  = f->avctx->width;
423     const int height = f->avctx->height;
424     uint16_t *dst    = (uint16_t *)frame->data[0];
425     const int stride =             frame->linesize[0] >> 1;
426     uint16_t *src;
427     unsigned int bitstream_size, bytestream_size, wordstream_size, extra,
428                  bytestream_offset, wordstream_offset;
429     int ret;
430
431     if (!f->last_picture->data[0]) {
432         if ((ret = ff_get_buffer(f->avctx, f->last_picture,
433                                  AV_GET_BUFFER_FLAG_REF)) < 0) {
434             return ret;
435         }
436         for (y=0; y<f->avctx->height; y++)
437             memset(f->last_picture->data[0] + y*f->last_picture->linesize[0], 0, 2*f->avctx->width);
438     }
439
440     src = (uint16_t *)f->last_picture->data[0];
441
442     if (f->version > 1) {
443         extra           = 20;
444         if (length < extra)
445             return AVERROR_INVALIDDATA;
446         bitstream_size  = AV_RL32(buf + 8);
447         wordstream_size = AV_RL32(buf + 12);
448         bytestream_size = AV_RL32(buf + 16);
449     } else {
450         extra           = 0;
451         bitstream_size  = AV_RL16(buf - 4);
452         wordstream_size = AV_RL16(buf - 2);
453         bytestream_size = FFMAX(length - bitstream_size - wordstream_size, 0);
454     }
455
456     if (bitstream_size > length || bitstream_size >= INT_MAX/8 ||
457         bytestream_size > length - bitstream_size ||
458         wordstream_size > length - bytestream_size - bitstream_size ||
459         extra > length - bytestream_size - bitstream_size - wordstream_size) {
460         av_log(f->avctx, AV_LOG_ERROR, "lengths %d %d %d %d\n", bitstream_size, bytestream_size, wordstream_size,
461         bitstream_size+ bytestream_size+ wordstream_size - length);
462         return AVERROR_INVALIDDATA;
463     }
464
465     av_fast_malloc(&f->bitstream_buffer, &f->bitstream_buffer_size,
466                    bitstream_size + FF_INPUT_BUFFER_PADDING_SIZE);
467     if (!f->bitstream_buffer)
468         return AVERROR(ENOMEM);
469     f->dsp.bswap_buf(f->bitstream_buffer, (const uint32_t*)(buf + extra),
470                      bitstream_size / 4);
471     memset((uint8_t*)f->bitstream_buffer + bitstream_size,
472            0, FF_INPUT_BUFFER_PADDING_SIZE);
473     init_get_bits(&f->gb, f->bitstream_buffer, 8 * bitstream_size);
474
475     wordstream_offset = extra + bitstream_size;
476     bytestream_offset = extra + bitstream_size + wordstream_size;
477     bytestream2_init(&f->g2, buf + wordstream_offset,
478                      length - wordstream_offset);
479     bytestream2_init(&f->g, buf + bytestream_offset,
480                      length - bytestream_offset);
481
482     init_mv(f, frame->linesize[0]);
483
484     for (y = 0; y < height; y += 8) {
485         for (x = 0; x < width; x += 8)
486             if ((ret = decode_p_block(f, dst + x, src + x, 3, 3, stride)) < 0)
487                 return ret;
488         src += 8 * stride;
489         dst += 8 * stride;
490     }
491
492     return 0;
493 }
494
495 /**
496  * decode block and dequantize.
497  * Note this is almost identical to MJPEG.
498  */
499 static int decode_i_block(FourXContext *f, int16_t *block)
500 {
501     int code, i, j, level, val;
502
503     if (get_bits_left(&f->gb) < 2){
504         av_log(f->avctx, AV_LOG_ERROR, "%d bits left before decode_i_block()\n", get_bits_left(&f->gb));
505         return -1;
506     }
507
508     /* DC coef */
509     val = get_vlc2(&f->pre_gb, f->pre_vlc.table, ACDC_VLC_BITS, 3);
510     if (val >> 4)
511         av_log(f->avctx, AV_LOG_ERROR, "error dc run != 0\n");
512
513     if (val)
514         val = get_xbits(&f->gb, val);
515
516     val        = val * dequant_table[0] + f->last_dc;
517     f->last_dc = block[0] = val;
518     /* AC coefs */
519     i = 1;
520     for (;;) {
521         code = get_vlc2(&f->pre_gb, f->pre_vlc.table, ACDC_VLC_BITS, 3);
522
523         /* EOB */
524         if (code == 0)
525             break;
526         if (code == 0xf0) {
527             i += 16;
528         } else {
529             level = get_xbits(&f->gb, code & 0xf);
530             i    += code >> 4;
531             if (i >= 64) {
532                 av_log(f->avctx, AV_LOG_ERROR, "run %d oveflow\n", i);
533                 return 0;
534             }
535
536             j = ff_zigzag_direct[i];
537             block[j] = level * dequant_table[j];
538             i++;
539             if (i >= 64)
540                 break;
541         }
542     }
543
544     return 0;
545 }
546
547 static inline void idct_put(FourXContext *f, AVFrame *frame, int x, int y)
548 {
549     int16_t (*block)[64] = f->block;
550     int stride           = frame->linesize[0] >> 1;
551     int i;
552     uint16_t *dst = ((uint16_t*)frame->data[0]) + y * stride + x;
553
554     for (i = 0; i < 4; i++) {
555         block[i][0] += 0x80 * 8 * 8;
556         idct(block[i]);
557     }
558
559     if (!(f->avctx->flags & CODEC_FLAG_GRAY)) {
560         for (i = 4; i < 6; i++)
561             idct(block[i]);
562     }
563
564     /* Note transform is:
565      * y  = ( 1b + 4g + 2r) / 14
566      * cb = ( 3b - 2g - 1r) / 14
567      * cr = (-1b - 4g + 5r) / 14 */
568     for (y = 0; y < 8; y++) {
569         for (x = 0; x < 8; x++) {
570             int16_t *temp = block[(x >> 2) + 2 * (y >> 2)] +
571                             2 * (x & 3) + 2 * 8 * (y & 3); // FIXME optimize
572             int cb = block[4][x + 8 * y];
573             int cr = block[5][x + 8 * y];
574             int cg = (cb + cr) >> 1;
575             int y;
576
577             cb += cb;
578
579             y               = temp[0];
580             dst[0]          = ((y + cb) >> 3) + (((y - cg) & 0xFC) << 3) + (((y + cr) & 0xF8) << 8);
581             y               = temp[1];
582             dst[1]          = ((y + cb) >> 3) + (((y - cg) & 0xFC) << 3) + (((y + cr) & 0xF8) << 8);
583             y               = temp[8];
584             dst[stride]     = ((y + cb) >> 3) + (((y - cg) & 0xFC) << 3) + (((y + cr) & 0xF8) << 8);
585             y               = temp[9];
586             dst[1 + stride] = ((y + cb) >> 3) + (((y - cg) & 0xFC) << 3) + (((y + cr) & 0xF8) << 8);
587             dst            += 2;
588         }
589         dst += 2 * stride - 2 * 8;
590     }
591 }
592
593 static int decode_i_mb(FourXContext *f)
594 {
595     int ret;
596     int i;
597
598     f->dsp.clear_blocks(f->block[0]);
599
600     for (i = 0; i < 6; i++)
601         if ((ret = decode_i_block(f, f->block[i])) < 0)
602             return ret;
603
604     return 0;
605 }
606
607 static const uint8_t *read_huffman_tables(FourXContext *f,
608                                           const uint8_t * const buf,
609                                           int buf_size)
610 {
611     int frequency[512] = { 0 };
612     uint8_t flag[512];
613     int up[512];
614     uint8_t len_tab[257];
615     int bits_tab[257];
616     int start, end;
617     const uint8_t *ptr = buf;
618     const uint8_t *ptr_end = buf + buf_size;
619     int j;
620
621     memset(up, -1, sizeof(up));
622
623     start = *ptr++;
624     end   = *ptr++;
625     for (;;) {
626         int i;
627
628         if (ptr_end - ptr < FFMAX(end - start + 1, 0) + 1) {
629             av_log(f->avctx, AV_LOG_ERROR, "invalid data in read_huffman_tables\n");
630             return NULL;
631         }
632
633         for (i = start; i <= end; i++)
634             frequency[i] = *ptr++;
635         start = *ptr++;
636         if (start == 0)
637             break;
638
639         end = *ptr++;
640     }
641     frequency[256] = 1;
642
643     while ((ptr - buf) & 3)
644         ptr++; // 4byte align
645
646     if (ptr > ptr_end) {
647         av_log(f->avctx, AV_LOG_ERROR, "ptr overflow in read_huffman_tables\n");
648         return NULL;
649     }
650
651     for (j = 257; j < 512; j++) {
652         int min_freq[2] = { 256 * 256, 256 * 256 };
653         int smallest[2] = { 0, 0 };
654         int i;
655         for (i = 0; i < j; i++) {
656             if (frequency[i] == 0)
657                 continue;
658             if (frequency[i] < min_freq[1]) {
659                 if (frequency[i] < min_freq[0]) {
660                     min_freq[1] = min_freq[0];
661                     smallest[1] = smallest[0];
662                     min_freq[0] = frequency[i];
663                     smallest[0] = i;
664                 } else {
665                     min_freq[1] = frequency[i];
666                     smallest[1] = i;
667                 }
668             }
669         }
670         if (min_freq[1] == 256 * 256)
671             break;
672
673         frequency[j]           = min_freq[0] + min_freq[1];
674         flag[smallest[0]]      = 0;
675         flag[smallest[1]]      = 1;
676         up[smallest[0]]        =
677         up[smallest[1]]        = j;
678         frequency[smallest[0]] = frequency[smallest[1]] = 0;
679     }
680
681     for (j = 0; j < 257; j++) {
682         int node, len = 0, bits = 0;
683
684         for (node = j; up[node] != -1; node = up[node]) {
685             bits += flag[node] << len;
686             len++;
687             if (len > 31)
688                 // can this happen at all ?
689                 av_log(f->avctx, AV_LOG_ERROR,
690                        "vlc length overflow\n");
691         }
692
693         bits_tab[j] = bits;
694         len_tab[j]  = len;
695     }
696
697     if (init_vlc(&f->pre_vlc, ACDC_VLC_BITS, 257, len_tab, 1, 1,
698                  bits_tab, 4, 4, 0))
699         return NULL;
700
701     return ptr;
702 }
703
704 static int mix(int c0, int c1)
705 {
706     int blue  =  2 * (c0 & 0x001F) + (c1 & 0x001F);
707     int green = (2 * (c0 & 0x03E0) + (c1 & 0x03E0)) >> 5;
708     int red   =  2 * (c0 >> 10)    + (c1 >> 10);
709     return red / 3 * 1024 + green / 3 * 32 + blue / 3;
710 }
711
712 static int decode_i2_frame(FourXContext *f, AVFrame *frame, const uint8_t *buf, int length)
713 {
714     int x, y, x2, y2;
715     const int width  = f->avctx->width;
716     const int height = f->avctx->height;
717     const int mbs    = (FFALIGN(width, 16) >> 4) * (FFALIGN(height, 16) >> 4);
718     uint16_t *dst    = (uint16_t*)frame->data[0];
719     const int stride =            frame->linesize[0]>>1;
720     const uint8_t *buf_end = buf + length;
721     GetByteContext g3;
722
723     if (length < mbs * 8) {
724         av_log(f->avctx, AV_LOG_ERROR, "packet size too small\n");
725         return AVERROR_INVALIDDATA;
726     }
727     bytestream2_init(&g3, buf, length);
728
729     for (y = 0; y < height; y += 16) {
730         for (x = 0; x < width; x += 16) {
731             unsigned int color[4] = { 0 }, bits;
732             if (buf_end - buf < 8)
733                 return -1;
734             // warning following is purely guessed ...
735             color[0] = bytestream2_get_le16u(&g3);
736             color[1] = bytestream2_get_le16u(&g3);
737
738             if (color[0] & 0x8000)
739                 av_log(f->avctx, AV_LOG_ERROR, "unk bit 1\n");
740             if (color[1] & 0x8000)
741                 av_log(f->avctx, AV_LOG_ERROR, "unk bit 2\n");
742
743             color[2] = mix(color[0], color[1]);
744             color[3] = mix(color[1], color[0]);
745
746             bits = bytestream2_get_le32u(&g3);
747             for (y2 = 0; y2 < 16; y2++) {
748                 for (x2 = 0; x2 < 16; x2++) {
749                     int index = 2 * (x2 >> 2) + 8 * (y2 >> 2);
750                     dst[y2 * stride + x2] = color[(bits >> index) & 3];
751                 }
752             }
753             dst += 16;
754         }
755         dst += 16 * stride - x;
756     }
757
758     return 0;
759 }
760
761 static int decode_i_frame(FourXContext *f, AVFrame *frame, const uint8_t *buf, int length)
762 {
763     int x, y, ret;
764     const int width  = f->avctx->width;
765     const int height = f->avctx->height;
766     const unsigned int bitstream_size = AV_RL32(buf);
767     unsigned int prestream_size;
768     const uint8_t *prestream;
769
770     if (bitstream_size > (1<<26) || length < bitstream_size + 12) {
771         av_log(f->avctx, AV_LOG_ERROR, "packet size too small\n");
772         return AVERROR_INVALIDDATA;
773     }
774
775     prestream_size = 4 * AV_RL32(buf + bitstream_size + 4);
776     prestream      =             buf + bitstream_size + 12;
777
778     if (prestream_size + bitstream_size + 12 != length
779         || bitstream_size > (1 << 26)
780         || prestream_size > (1 << 26)) {
781         av_log(f->avctx, AV_LOG_ERROR, "size mismatch %d %d %d\n",
782                prestream_size, bitstream_size, length);
783         return AVERROR_INVALIDDATA;
784     }
785
786     prestream = read_huffman_tables(f, prestream, prestream_size);
787     if (!prestream) {
788         av_log(f->avctx, AV_LOG_ERROR, "Error reading Huffman tables.\n");
789         return AVERROR_INVALIDDATA;
790     }
791
792     av_assert0(prestream <= buf + length);
793
794     init_get_bits(&f->gb, buf + 4, 8 * bitstream_size);
795
796     prestream_size = length + buf - prestream;
797
798     av_fast_malloc(&f->bitstream_buffer, &f->bitstream_buffer_size,
799                    prestream_size + FF_INPUT_BUFFER_PADDING_SIZE);
800     if (!f->bitstream_buffer)
801         return AVERROR(ENOMEM);
802     f->dsp.bswap_buf(f->bitstream_buffer, (const uint32_t*)prestream,
803                      prestream_size / 4);
804     memset((uint8_t*)f->bitstream_buffer + prestream_size,
805            0, FF_INPUT_BUFFER_PADDING_SIZE);
806     init_get_bits(&f->pre_gb, f->bitstream_buffer, 8 * prestream_size);
807
808     f->last_dc = 0 * 128 * 8 * 8;
809
810     for (y = 0; y < height; y += 16) {
811         for (x = 0; x < width; x += 16) {
812             if ((ret = decode_i_mb(f)) < 0)
813                 return ret;
814
815             idct_put(f, frame, x, y);
816         }
817     }
818
819     if (get_vlc2(&f->pre_gb, f->pre_vlc.table, ACDC_VLC_BITS, 3) != 256)
820         av_log(f->avctx, AV_LOG_ERROR, "end mismatch\n");
821
822     return 0;
823 }
824
825 static int decode_frame(AVCodecContext *avctx, void *data,
826                         int *got_frame, AVPacket *avpkt)
827 {
828     const uint8_t *buf    = avpkt->data;
829     int buf_size          = avpkt->size;
830     FourXContext *const f = avctx->priv_data;
831     AVFrame *picture      = data;
832     int i, frame_4cc, frame_size, ret;
833
834     if (buf_size < 20)
835         return AVERROR_INVALIDDATA;
836
837     if (buf_size < AV_RL32(buf + 4) + 8) {
838         av_log(f->avctx, AV_LOG_ERROR, "size mismatch %d %d\n",
839                buf_size, AV_RL32(buf + 4));
840         return AVERROR_INVALIDDATA;
841     }
842
843     frame_4cc = AV_RL32(buf);
844
845     if (frame_4cc == AV_RL32("cfrm")) {
846         int free_index       = -1;
847         int id, whole_size;
848         const int data_size  = buf_size - 20;
849         CFrameBuffer *cfrm;
850
851         if (f->version <= 1) {
852             av_log(f->avctx, AV_LOG_ERROR, "cfrm in version %d\n", f->version);
853             return AVERROR_INVALIDDATA;
854         }
855
856         id         = AV_RL32(buf + 12);
857         whole_size = AV_RL32(buf + 16);
858
859         if (data_size < 0 || whole_size < 0) {
860             av_log(f->avctx, AV_LOG_ERROR, "sizes invalid\n");
861             return AVERROR_INVALIDDATA;
862         }
863
864         for (i = 0; i < CFRAME_BUFFER_COUNT; i++)
865             if (f->cfrm[i].id && f->cfrm[i].id < avctx->frame_number)
866                 av_log(f->avctx, AV_LOG_ERROR, "lost c frame %d\n",
867                        f->cfrm[i].id);
868
869         for (i = 0; i < CFRAME_BUFFER_COUNT; i++) {
870             if (f->cfrm[i].id == id)
871                 break;
872             if (f->cfrm[i].size == 0)
873                 free_index = i;
874         }
875
876         if (i >= CFRAME_BUFFER_COUNT) {
877             i             = free_index;
878             f->cfrm[i].id = id;
879         }
880         cfrm = &f->cfrm[i];
881
882         if (data_size > UINT_MAX -  cfrm->size - FF_INPUT_BUFFER_PADDING_SIZE)
883             return AVERROR_INVALIDDATA;
884
885         cfrm->data = av_fast_realloc(cfrm->data, &cfrm->allocated_size,
886                                      cfrm->size + data_size + FF_INPUT_BUFFER_PADDING_SIZE);
887         // explicit check needed as memcpy below might not catch a NULL
888         if (!cfrm->data) {
889             av_log(f->avctx, AV_LOG_ERROR, "realloc failure\n");
890             return AVERROR(ENOMEM);
891         }
892
893         memcpy(cfrm->data + cfrm->size, buf + 20, data_size);
894         cfrm->size += data_size;
895
896         if (cfrm->size >= whole_size) {
897             buf        = cfrm->data;
898             frame_size = cfrm->size;
899
900             if (id != avctx->frame_number)
901                 av_log(f->avctx, AV_LOG_ERROR, "cframe id mismatch %d %d\n",
902                        id, avctx->frame_number);
903
904             if (f->version <= 1)
905                 return AVERROR_INVALIDDATA;
906
907             cfrm->size = cfrm->id = 0;
908             frame_4cc  = AV_RL32("pfrm");
909         } else
910             return buf_size;
911     } else {
912         buf        = buf      + 12;
913         frame_size = buf_size - 12;
914     }
915
916     FFSWAP(AVFrame*, f->current_picture, f->last_picture);
917
918     // alternatively we would have to use our own buffer management
919     avctx->flags |= CODEC_FLAG_EMU_EDGE;
920
921     if ((ret = ff_reget_buffer(avctx, f->current_picture)) < 0)
922         return ret;
923
924     if (frame_4cc == AV_RL32("ifr2")) {
925         f->current_picture->pict_type = AV_PICTURE_TYPE_I;
926         if ((ret = decode_i2_frame(f, f->current_picture, buf - 4, frame_size + 4)) < 0) {
927             av_log(f->avctx, AV_LOG_ERROR, "decode i2 frame failed\n");
928             return ret;
929         }
930     } else if (frame_4cc == AV_RL32("ifrm")) {
931         f->current_picture->pict_type = AV_PICTURE_TYPE_I;
932         if ((ret = decode_i_frame(f, f->current_picture, buf, frame_size)) < 0) {
933             av_log(f->avctx, AV_LOG_ERROR, "decode i frame failed\n");
934             return ret;
935         }
936     } else if (frame_4cc == AV_RL32("pfrm") || frame_4cc == AV_RL32("pfr2")) {
937         f->current_picture->pict_type = AV_PICTURE_TYPE_P;
938         if ((ret = decode_p_frame(f, f->current_picture, buf, frame_size)) < 0) {
939             av_log(f->avctx, AV_LOG_ERROR, "decode p frame failed\n");
940             return ret;
941         }
942     } else if (frame_4cc == AV_RL32("snd_")) {
943         av_log(avctx, AV_LOG_ERROR, "ignoring snd_ chunk length:%d\n",
944                buf_size);
945     } else {
946         av_log(avctx, AV_LOG_ERROR, "ignoring unknown chunk length:%d\n",
947                buf_size);
948     }
949
950     f->current_picture->key_frame = f->current_picture->pict_type == AV_PICTURE_TYPE_I;
951
952     if ((ret = av_frame_ref(picture, f->current_picture)) < 0)
953         return ret;
954     *got_frame = 1;
955
956     emms_c();
957
958     return buf_size;
959 }
960
961 static av_cold int decode_init(AVCodecContext *avctx)
962 {
963     FourXContext * const f = avctx->priv_data;
964
965     if (avctx->extradata_size != 4 || !avctx->extradata) {
966         av_log(avctx, AV_LOG_ERROR, "extradata wrong or missing\n");
967         return AVERROR_INVALIDDATA;
968     }
969     if((avctx->width % 16) || (avctx->height % 16)) {
970         av_log(avctx, AV_LOG_ERROR, "unsupported width/height\n");
971         return AVERROR_INVALIDDATA;
972     }
973
974     f->version = AV_RL32(avctx->extradata) >> 16;
975     ff_dsputil_init(&f->dsp, avctx);
976     f->avctx = avctx;
977     init_vlcs(f);
978
979     if (f->version > 2)
980         avctx->pix_fmt = AV_PIX_FMT_RGB565;
981     else
982         avctx->pix_fmt = AV_PIX_FMT_BGR555;
983
984     f->current_picture = av_frame_alloc();
985     f->last_picture    = av_frame_alloc();
986     if (!f->current_picture  || !f->last_picture)
987         return AVERROR(ENOMEM);
988
989     return 0;
990 }
991
992
993 static av_cold int decode_end(AVCodecContext *avctx)
994 {
995     FourXContext * const f = avctx->priv_data;
996     int i;
997
998     av_freep(&f->bitstream_buffer);
999     f->bitstream_buffer_size = 0;
1000     for (i = 0; i < CFRAME_BUFFER_COUNT; i++) {
1001         av_freep(&f->cfrm[i].data);
1002         f->cfrm[i].allocated_size = 0;
1003     }
1004     ff_free_vlc(&f->pre_vlc);
1005     av_frame_free(&f->current_picture);
1006     av_frame_free(&f->last_picture);
1007
1008     return 0;
1009 }
1010
1011 AVCodec ff_fourxm_decoder = {
1012     .name           = "4xm",
1013     .type           = AVMEDIA_TYPE_VIDEO,
1014     .id             = AV_CODEC_ID_4XM,
1015     .priv_data_size = sizeof(FourXContext),
1016     .init           = decode_init,
1017     .close          = decode_end,
1018     .decode         = decode_frame,
1019     .capabilities   = CODEC_CAP_DR1,
1020     .long_name      = NULL_IF_CONFIG_SMALL("4X Movie"),
1021 };