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