fix type 3 aka skipped blocks for old version
[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 4xm.c
24  * 4XM codec.
25  */
26
27 #include "avcodec.h"
28 #include "dsputil.h"
29 #include "mpegvideo.h"
30
31 //#undef NDEBUG
32 //#include <assert.h>
33
34 #define BLOCK_TYPE_VLC_BITS 5
35 #define ACDC_VLC_BITS 9
36
37 #define CFRAME_BUFFER_COUNT 100
38
39 static const uint8_t block_type_tab[2][4][8][2]={
40  {
41   {   //{8,4,2}x{8,4,2}
42     { 0,1}, { 2,2}, { 6,3}, {14,4}, {30,5}, {31,5}, { 0,0}
43   },{ //{8,4}x1
44     { 0,1}, { 0,0}, { 2,2}, { 6,3}, {14,4}, {15,4}, { 0,0}
45   },{ //1x{8,4}
46     { 0,1}, { 2,2}, { 0,0}, { 6,3}, {14,4}, {15,4}, { 0,0}
47   },{ //1x2, 2x1
48     { 0,1}, { 0,0}, { 0,0}, { 2,2}, { 6,3}, {14,4}, {15,4}
49   }
50  },{
51   {  //{8,4,2}x{8,4,2}
52     { 1,2}, { 4,3}, { 5,3}, {0,2}, {6,3}, {7,3}, {0,0}
53   },{//{8,4}x1
54     { 1,2}, { 0,0}, { 2,2}, {0,2}, {6,3}, {7,3}, {0,0}
55   },{//1x{8,4}
56     { 1,2}, { 2,2}, { 0,0}, {0,2}, {6,3}, {7,3}, {0,0}
57   },{//1x2, 2x1
58     { 1,2}, { 0,0}, { 0,0}, {0,2}, {2,2}, {6,3}, {7,3}
59   }
60  }
61 };
62
63 static const uint8_t size2index[4][4]={
64   {-1, 3, 1, 1},
65   { 3, 0, 0, 0},
66   { 2, 0, 0, 0},
67   { 2, 0, 0, 0},
68 };
69
70 static const int8_t mv[256][2]={
71 {  0,  0},{  0, -1},{ -1,  0},{  1,  0},{  0,  1},{ -1, -1},{  1, -1},{ -1,  1},
72 {  1,  1},{  0, -2},{ -2,  0},{  2,  0},{  0,  2},{ -1, -2},{  1, -2},{ -2, -1},
73 {  2, -1},{ -2,  1},{  2,  1},{ -1,  2},{  1,  2},{ -2, -2},{  2, -2},{ -2,  2},
74 {  2,  2},{  0, -3},{ -3,  0},{  3,  0},{  0,  3},{ -1, -3},{  1, -3},{ -3, -1},
75 {  3, -1},{ -3,  1},{  3,  1},{ -1,  3},{  1,  3},{ -2, -3},{  2, -3},{ -3, -2},
76 {  3, -2},{ -3,  2},{  3,  2},{ -2,  3},{  2,  3},{  0, -4},{ -4,  0},{  4,  0},
77 {  0,  4},{ -1, -4},{  1, -4},{ -4, -1},{  4, -1},{  4,  1},{ -1,  4},{  1,  4},
78 { -3, -3},{ -3,  3},{  3,  3},{ -2, -4},{ -4, -2},{  4, -2},{ -4,  2},{ -2,  4},
79 {  2,  4},{ -3, -4},{  3, -4},{  4, -3},{ -5,  0},{ -4,  3},{ -3,  4},{  3,  4},
80 { -1, -5},{ -5, -1},{ -5,  1},{ -1,  5},{ -2, -5},{  2, -5},{  5, -2},{  5,  2},
81 { -4, -4},{ -4,  4},{ -3, -5},{ -5, -3},{ -5,  3},{  3,  5},{ -6,  0},{  0,  6},
82 { -6, -1},{ -6,  1},{  1,  6},{  2, -6},{ -6,  2},{  2,  6},{ -5, -4},{  5,  4},
83 {  4,  5},{ -6, -3},{  6,  3},{ -7,  0},{ -1, -7},{  5, -5},{ -7,  1},{ -1,  7},
84 {  4, -6},{  6,  4},{ -2, -7},{ -7,  2},{ -3, -7},{  7, -3},{  3,  7},{  6, -5},
85 {  0, -8},{ -1, -8},{ -7, -4},{ -8,  1},{  4,  7},{  2, -8},{ -2,  8},{  6,  6},
86 { -8,  3},{  5, -7},{ -5,  7},{  8, -4},{  0, -9},{ -9, -1},{  1,  9},{  7, -6},
87 { -7,  6},{ -5, -8},{ -5,  8},{ -9,  3},{  9, -4},{  7, -7},{  8, -6},{  6,  8},
88 { 10,  1},{-10,  2},{  9, -5},{ 10, -3},{ -8, -7},{-10, -4},{  6, -9},{-11,  0},
89 { 11,  1},{-11, -2},{ -2, 11},{  7, -9},{ -7,  9},{ 10,  6},{ -4, 11},{  8, -9},
90 {  8,  9},{  5, 11},{  7,-10},{ 12, -3},{ 11,  6},{ -9, -9},{  8, 10},{  5, 12},
91 {-11,  7},{ 13,  2},{  6,-12},{ 10,  9},{-11,  8},{ -7, 12},{  0, 14},{ 14, -2},
92 { -9, 11},{ -6, 13},{-14, -4},{ -5,-14},{  5, 14},{-15, -1},{-14, -6},{  3,-15},
93 { 11,-11},{ -7, 14},{ -5, 15},{  8,-14},{ 15,  6},{  3, 16},{  7,-15},{-16,  5},
94 {  0, 17},{-16, -6},{-10, 14},{-16,  7},{ 12, 13},{-16,  8},{-17,  6},{-18,  3},
95 { -7, 17},{ 15, 11},{ 16, 10},{  2,-19},{  3,-19},{-11,-16},{-18,  8},{-19, -6},
96 {  2,-20},{-17,-11},{-10,-18},{  8, 19},{-21, -1},{-20,  7},{ -4, 21},{ 21,  5},
97 { 15, 16},{  2,-22},{-10,-20},{-22,  5},{ 20,-11},{ -7,-22},{-12, 20},{ 23, -5},
98 { 13,-20},{ 24, -2},{-15, 19},{-11, 22},{ 16, 19},{ 23,-10},{-18,-18},{ -9,-24},
99 { 24,-10},{ -3, 26},{-23, 13},{-18,-20},{ 17, 21},{ -4, 27},{ 27,  6},{  1,-28},
100 {-11, 26},{-17,-23},{  7, 28},{ 11,-27},{ 29,  5},{-23,-19},{-28,-11},{-21, 22},
101 {-30,  7},{-17, 26},{-27, 16},{ 13, 29},{ 19,-26},{ 10,-31},{-14,-30},{ 20,-27},
102 {-29, 18},{-16,-31},{-28,-22},{ 21,-30},{-25, 28},{ 26,-29},{ 25,-32},{-32,-32}
103 };
104
105 // this is simply the scaled down elementwise product of the standard jpeg quantizer table and the AAN premul table
106 static const uint8_t dequant_table[64]={
107  16, 15, 13, 19, 24, 31, 28, 17,
108  17, 23, 25, 31, 36, 63, 45, 21,
109  18, 24, 27, 37, 52, 59, 49, 20,
110  16, 28, 34, 40, 60, 80, 51, 20,
111  18, 31, 48, 66, 68, 86, 56, 21,
112  19, 38, 56, 59, 64, 64, 48, 20,
113  27, 48, 55, 55, 56, 51, 35, 15,
114  20, 35, 34, 32, 31, 22, 15,  8,
115 };
116
117 static VLC block_type_vlc[2][4];
118
119
120 typedef struct CFrameBuffer{
121     unsigned int allocated_size;
122     unsigned int size;
123     int id;
124     uint8_t *data;
125 }CFrameBuffer;
126
127 typedef struct FourXContext{
128     AVCodecContext *avctx;
129     DSPContext dsp;
130     AVFrame current_picture, last_picture;
131     GetBitContext pre_gb;          ///< ac/dc prefix
132     GetBitContext gb;
133     uint8_t *bytestream;
134     uint16_t *wordstream;
135     int mv[256];
136     VLC pre_vlc;
137     int last_dc;
138     DECLARE_ALIGNED_8(DCTELEM, block[6][64]);
139     uint8_t *bitstream_buffer;
140     unsigned int bitstream_buffer_size;
141     int version;
142     CFrameBuffer cfrm[CFRAME_BUFFER_COUNT];
143 } FourXContext;
144
145
146 #define FIX_1_082392200  70936
147 #define FIX_1_414213562  92682
148 #define FIX_1_847759065 121095
149 #define FIX_2_613125930 171254
150
151 #define MULTIPLY(var,const)  (((var)*(const)) >> 16)
152
153 static void idct(DCTELEM block[64]){
154     int tmp0, tmp1, tmp2, tmp3, tmp4, tmp5, tmp6, tmp7;
155     int tmp10, tmp11, tmp12, tmp13;
156     int z5, z10, z11, z12, z13;
157     int i;
158     int temp[64];
159
160     for(i=0; i<8; i++){
161         tmp10 = block[8*0 + i] + block[8*4 + i];
162         tmp11 = block[8*0 + i] - block[8*4 + i];
163
164         tmp13 =          block[8*2 + i] + block[8*6 + i];
165         tmp12 = MULTIPLY(block[8*2 + i] - block[8*6 + i], FIX_1_414213562) - tmp13;
166
167         tmp0 = tmp10 + tmp13;
168         tmp3 = tmp10 - tmp13;
169         tmp1 = tmp11 + tmp12;
170         tmp2 = tmp11 - tmp12;
171
172         z13 = block[8*5 + i] + block[8*3 + i];
173         z10 = block[8*5 + i] - block[8*3 + i];
174         z11 = block[8*1 + i] + block[8*7 + i];
175         z12 = block[8*1 + i] - block[8*7 + i];
176
177         tmp7  =          z11 + z13;
178         tmp11 = MULTIPLY(z11 - z13, FIX_1_414213562);
179
180         z5    = MULTIPLY(z10 + z12, FIX_1_847759065);
181         tmp10 = MULTIPLY(z12, FIX_1_082392200) - z5;
182         tmp12 = MULTIPLY(z10, - FIX_2_613125930) + z5;
183
184         tmp6 = tmp12 - tmp7;
185         tmp5 = tmp11 - tmp6;
186         tmp4 = tmp10 + tmp5;
187
188         temp[8*0 + i] = tmp0 + tmp7;
189         temp[8*7 + i] = tmp0 - tmp7;
190         temp[8*1 + i] = tmp1 + tmp6;
191         temp[8*6 + i] = tmp1 - tmp6;
192         temp[8*2 + i] = tmp2 + tmp5;
193         temp[8*5 + i] = tmp2 - tmp5;
194         temp[8*4 + i] = tmp3 + tmp4;
195         temp[8*3 + i] = tmp3 - tmp4;
196     }
197
198     for(i=0; i<8*8; i+=8){
199         tmp10 = temp[0 + i] + temp[4 + i];
200         tmp11 = temp[0 + i] - temp[4 + i];
201
202         tmp13 = temp[2 + i] + temp[6 + i];
203         tmp12 = MULTIPLY(temp[2 + i] - temp[6 + i], FIX_1_414213562) - tmp13;
204
205         tmp0 = tmp10 + tmp13;
206         tmp3 = tmp10 - tmp13;
207         tmp1 = tmp11 + tmp12;
208         tmp2 = tmp11 - tmp12;
209
210         z13 = temp[5 + i] + temp[3 + i];
211         z10 = temp[5 + i] - temp[3 + i];
212         z11 = temp[1 + i] + temp[7 + i];
213         z12 = temp[1 + i] - temp[7 + i];
214
215         tmp7 = z11 + z13;
216         tmp11 = MULTIPLY(z11 - z13, FIX_1_414213562);
217
218         z5 = MULTIPLY(z10 + z12, FIX_1_847759065);
219         tmp10 = MULTIPLY(z12, FIX_1_082392200) - z5;
220         tmp12 = MULTIPLY(z10, - FIX_2_613125930) + z5;
221
222         tmp6 = tmp12 - tmp7;
223         tmp5 = tmp11 - tmp6;
224         tmp4 = tmp10 + tmp5;
225
226         block[0 + i] = (tmp0 + tmp7)>>6;
227         block[7 + i] = (tmp0 - tmp7)>>6;
228         block[1 + i] = (tmp1 + tmp6)>>6;
229         block[6 + i] = (tmp1 - tmp6)>>6;
230         block[2 + i] = (tmp2 + tmp5)>>6;
231         block[5 + i] = (tmp2 - tmp5)>>6;
232         block[4 + i] = (tmp3 + tmp4)>>6;
233         block[3 + i] = (tmp3 - tmp4)>>6;
234     }
235 }
236
237 static void init_vlcs(FourXContext *f){
238     int i;
239
240     for(i=0; i<8; i++){
241         init_vlc(&block_type_vlc[0][i], BLOCK_TYPE_VLC_BITS, 7,
242                  &block_type_tab[0][i][0][1], 2, 1,
243                  &block_type_tab[0][i][0][0], 2, 1, 1);
244     }
245 }
246
247 static void init_mv(FourXContext *f){
248     int i;
249
250     for(i=0; i<256; i++){
251         if(f->version)
252             f->mv[i] = mv[i][0]   + mv[i][1]  *f->current_picture.linesize[0]/2;
253         else
254             f->mv[i] = (i&15) - 8 + ((i>>4)-8)*f->current_picture.linesize[0]/2;
255     }
256 }
257
258 static inline void mcdc(uint16_t *dst, uint16_t *src, int log2w, int h, int stride, int scale, int dc){
259    int i;
260    dc*= 0x10001;
261
262    switch(log2w){
263    case 0:
264         for(i=0; i<h; i++){
265             dst[0] = scale*src[0] + dc;
266             if(scale) src += stride;
267             dst += stride;
268         }
269         break;
270     case 1:
271         for(i=0; i<h; i++){
272             ((uint32_t*)dst)[0] = scale*((uint32_t*)src)[0] + dc;
273             if(scale) src += stride;
274             dst += stride;
275         }
276         break;
277     case 2:
278         for(i=0; i<h; i++){
279             ((uint32_t*)dst)[0] = scale*((uint32_t*)src)[0] + dc;
280             ((uint32_t*)dst)[1] = scale*((uint32_t*)src)[1] + dc;
281             if(scale) src += stride;
282             dst += stride;
283         }
284         break;
285     case 3:
286         for(i=0; i<h; i++){
287             ((uint32_t*)dst)[0] = scale*((uint32_t*)src)[0] + dc;
288             ((uint32_t*)dst)[1] = scale*((uint32_t*)src)[1] + dc;
289             ((uint32_t*)dst)[2] = scale*((uint32_t*)src)[2] + dc;
290             ((uint32_t*)dst)[3] = scale*((uint32_t*)src)[3] + dc;
291             if(scale) src += stride;
292             dst += stride;
293         }
294         break;
295     default: assert(0);
296     }
297 }
298
299 static void decode_p_block(FourXContext *f, uint16_t *dst, uint16_t *src, int log2w, int log2h, int stride){
300     const int index= size2index[log2h][log2w];
301     const int h= 1<<log2h;
302     int code= get_vlc2(&f->gb, block_type_vlc[1-f->version][index].table, BLOCK_TYPE_VLC_BITS, 1);
303
304     assert(code>=0 && code<=6);
305
306     if(code == 0){
307         src += f->mv[ *f->bytestream++ ];
308         mcdc(dst, src, log2w, h, stride, 1, 0);
309     }else if(code == 1){
310         log2h--;
311         decode_p_block(f, dst                  , src                  , log2w, log2h, stride);
312         decode_p_block(f, dst + (stride<<log2h), src + (stride<<log2h), log2w, log2h, stride);
313     }else if(code == 2){
314         log2w--;
315         decode_p_block(f, dst             , src             , log2w, log2h, stride);
316         decode_p_block(f, dst + (1<<log2w), src + (1<<log2w), log2w, log2h, stride);
317     }else if(code == 3 && f->version==0){
318         mcdc(dst, src, log2w, h, stride, 1, 0);
319     }else if(code == 4){
320         src += f->mv[ *f->bytestream++ ];
321         mcdc(dst, src, log2w, h, stride, 1, le2me_16(*f->wordstream++));
322     }else if(code == 5){
323         mcdc(dst, src, log2w, h, stride, 0, le2me_16(*f->wordstream++));
324     }else if(code == 6){
325         if(log2w){
326             dst[0] = le2me_16(*f->wordstream++);
327             dst[1] = le2me_16(*f->wordstream++);
328         }else{
329             dst[0     ] = le2me_16(*f->wordstream++);
330             dst[stride] = le2me_16(*f->wordstream++);
331         }
332     }
333 }
334
335 static int get32(void *p){
336     return le2me_32(*(uint32_t*)p);
337 }
338
339 static int decode_p_frame(FourXContext *f, uint8_t *buf, int length){
340     int x, y;
341     const int width= f->avctx->width;
342     const int height= f->avctx->height;
343     uint16_t *src= (uint16_t*)f->last_picture.data[0];
344     uint16_t *dst= (uint16_t*)f->current_picture.data[0];
345     const int stride= f->current_picture.linesize[0]>>1;
346     unsigned int bitstream_size, bytestream_size, wordstream_size, extra;
347
348     if(f->version){
349         extra=20;
350         bitstream_size= get32(buf+8);
351         wordstream_size= get32(buf+12);
352         bytestream_size= get32(buf+16);
353     }else{
354         extra=0;
355         bitstream_size = AV_RL16(buf-4);
356         wordstream_size= AV_RL16(buf-2);
357         bytestream_size= FFMAX(length - bitstream_size - wordstream_size, 0);
358     }
359
360     if(bitstream_size+ bytestream_size+ wordstream_size + extra != length
361        || bitstream_size  > (1<<26)
362        || bytestream_size > (1<<26)
363        || wordstream_size > (1<<26)
364        ){
365         av_log(f->avctx, AV_LOG_ERROR, "lengths %d %d %d %d\n", bitstream_size, bytestream_size, wordstream_size,
366         bitstream_size+ bytestream_size+ wordstream_size - length);
367         return -1;
368     }
369
370     f->bitstream_buffer= av_fast_realloc(f->bitstream_buffer, &f->bitstream_buffer_size, bitstream_size + FF_INPUT_BUFFER_PADDING_SIZE);
371     f->dsp.bswap_buf((uint32_t*)f->bitstream_buffer, (uint32_t*)(buf + extra), bitstream_size/4);
372     init_get_bits(&f->gb, f->bitstream_buffer, 8*bitstream_size);
373
374     f->wordstream= (uint16_t*)(buf + extra + bitstream_size);
375     f->bytestream= buf + extra + bitstream_size + wordstream_size;
376
377     init_mv(f);
378
379     for(y=0; y<height; y+=8){
380         for(x=0; x<width; x+=8){
381             decode_p_block(f, dst + x, src + x, 3, 3, stride);
382         }
383         src += 8*stride;
384         dst += 8*stride;
385     }
386
387     if(   bitstream_size != (get_bits_count(&f->gb)+31)/32*4
388        || (((char*)f->wordstream - (char*)buf + 2)&~2) != extra + bitstream_size + wordstream_size
389        || (((char*)f->bytestream - (char*)buf + 3)&~3) != extra + bitstream_size + wordstream_size + bytestream_size)
390         av_log(f->avctx, AV_LOG_ERROR, " %d %td %td bytes left\n",
391             bitstream_size - (get_bits_count(&f->gb)+31)/32*4,
392             -(((char*)f->bytestream - (char*)buf + 3)&~3) + (extra + bitstream_size + wordstream_size + bytestream_size),
393             -(((char*)f->wordstream - (char*)buf + 2)&~2) + (extra + bitstream_size + wordstream_size)
394         );
395
396     return 0;
397 }
398
399 /**
400  * decode block and dequantize.
401  * Note this is allmost identical to mjpeg
402  */
403 static int decode_i_block(FourXContext *f, DCTELEM *block){
404     int code, i, j, level, val;
405
406     /* DC coef */
407     val = get_vlc2(&f->pre_gb, f->pre_vlc.table, ACDC_VLC_BITS, 3);
408     if (val>>4){
409         av_log(f->avctx, AV_LOG_ERROR, "error dc run != 0\n");
410     }
411
412     if(val)
413         val = get_xbits(&f->gb, val);
414
415     val = val * dequant_table[0] + f->last_dc;
416     f->last_dc =
417     block[0] = val;
418     /* AC coefs */
419     i = 1;
420     for(;;) {
421         code = get_vlc2(&f->pre_gb, f->pre_vlc.table, ACDC_VLC_BITS, 3);
422
423         /* EOB */
424         if (code == 0)
425             break;
426         if (code == 0xf0) {
427             i += 16;
428         } else {
429             level = get_xbits(&f->gb, code & 0xf);
430             i += code >> 4;
431             if (i >= 64) {
432                 av_log(f->avctx, AV_LOG_ERROR, "run %d oveflow\n", i);
433                 return 0;
434             }
435
436             j= ff_zigzag_direct[i];
437             block[j] = level * dequant_table[j];
438             i++;
439             if (i >= 64)
440                 break;
441         }
442     }
443
444     return 0;
445 }
446
447 static inline void idct_put(FourXContext *f, int x, int y){
448     DCTELEM (*block)[64]= f->block;
449     int stride= f->current_picture.linesize[0]>>1;
450     int i;
451     uint16_t *dst = ((uint16_t*)f->current_picture.data[0]) + y * stride + x;
452
453     for(i=0; i<4; i++){
454         block[i][0] += 0x80*8*8;
455         idct(block[i]);
456     }
457
458     if(!(f->avctx->flags&CODEC_FLAG_GRAY)){
459         for(i=4; i<6; i++) idct(block[i]);
460     }
461
462 /* Note transform is:
463 y= ( 1b + 4g + 2r)/14
464 cb=( 3b - 2g - 1r)/14
465 cr=(-1b - 4g + 5r)/14
466 */
467     for(y=0; y<8; y++){
468         for(x=0; x<8; x++){
469             DCTELEM *temp= block[(x>>2) + 2*(y>>2)] + 2*(x&3) + 2*8*(y&3); //FIXME optimize
470             int cb= block[4][x + 8*y];
471             int cr= block[5][x + 8*y];
472             int cg= (cb + cr)>>1;
473             int y;
474
475             cb+=cb;
476
477             y = temp[0];
478             dst[0       ]= ((y+cb)>>3) + (((y-cg)&0xFC)<<3) + (((y+cr)&0xF8)<<8);
479             y = temp[1];
480             dst[1       ]= ((y+cb)>>3) + (((y-cg)&0xFC)<<3) + (((y+cr)&0xF8)<<8);
481             y = temp[8];
482             dst[  stride]= ((y+cb)>>3) + (((y-cg)&0xFC)<<3) + (((y+cr)&0xF8)<<8);
483             y = temp[9];
484             dst[1+stride]= ((y+cb)>>3) + (((y-cg)&0xFC)<<3) + (((y+cr)&0xF8)<<8);
485             dst += 2;
486         }
487         dst += 2*stride - 2*8;
488     }
489 }
490
491 static int decode_i_mb(FourXContext *f){
492     int i;
493
494     f->dsp.clear_blocks(f->block[0]);
495
496     for(i=0; i<6; i++){
497         if(decode_i_block(f, f->block[i]) < 0)
498             return -1;
499     }
500
501     return 0;
502 }
503
504 static uint8_t *read_huffman_tables(FourXContext *f, uint8_t * const buf){
505     int frequency[512];
506     uint8_t flag[512];
507     int up[512];
508     uint8_t len_tab[257];
509     int bits_tab[257];
510     int start, end;
511     uint8_t *ptr= buf;
512     int j;
513
514     memset(frequency, 0, sizeof(frequency));
515     memset(up, -1, sizeof(up));
516
517     start= *ptr++;
518     end= *ptr++;
519     for(;;){
520         int i;
521
522         for(i=start; i<=end; i++){
523             frequency[i]= *ptr++;
524         }
525         start= *ptr++;
526         if(start==0) break;
527
528         end= *ptr++;
529     }
530     frequency[256]=1;
531
532     while((ptr - buf)&3) ptr++; // 4byte align
533
534     for(j=257; j<512; j++){
535         int min_freq[2]= {256*256, 256*256};
536         int smallest[2]= {0, 0};
537         int i;
538         for(i=0; i<j; i++){
539             if(frequency[i] == 0) continue;
540             if(frequency[i] < min_freq[1]){
541                 if(frequency[i] < min_freq[0]){
542                     min_freq[1]= min_freq[0]; smallest[1]= smallest[0];
543                     min_freq[0]= frequency[i];smallest[0]= i;
544                 }else{
545                     min_freq[1]= frequency[i];smallest[1]= i;
546                 }
547             }
548         }
549         if(min_freq[1] == 256*256) break;
550
551         frequency[j]= min_freq[0] + min_freq[1];
552         flag[ smallest[0] ]= 0;
553         flag[ smallest[1] ]= 1;
554         up[ smallest[0] ]=
555         up[ smallest[1] ]= j;
556         frequency[ smallest[0] ]= frequency[ smallest[1] ]= 0;
557     }
558
559     for(j=0; j<257; j++){
560         int node;
561         int len=0;
562         int bits=0;
563
564         for(node= j; up[node] != -1; node= up[node]){
565             bits += flag[node]<<len;
566             len++;
567             if(len > 31) av_log(f->avctx, AV_LOG_ERROR, "vlc length overflow\n"); //can this happen at all ?
568         }
569
570         bits_tab[j]= bits;
571         len_tab[j]= len;
572     }
573
574     init_vlc(&f->pre_vlc, ACDC_VLC_BITS, 257,
575              len_tab , 1, 1,
576              bits_tab, 4, 4, 0);
577
578     return ptr;
579 }
580
581 static int mix(int c0, int c1){
582     int blue = 2*(c0&0x001F) + (c1&0x001F);
583     int green= (2*(c0&0x03E0) + (c1&0x03E0))>>5;
584     int red  = 2*(c0>>10) + (c1>>10);
585     return red/3*1024 + green/3*32 + blue/3;
586 }
587
588 static int decode_i2_frame(FourXContext *f, uint8_t *buf, int length){
589     int x, y, x2, y2;
590     const int width= f->avctx->width;
591     const int height= f->avctx->height;
592     uint16_t *dst= (uint16_t*)f->current_picture.data[0];
593     const int stride= f->current_picture.linesize[0]>>1;
594
595     for(y=0; y<height; y+=16){
596         for(x=0; x<width; x+=16){
597             unsigned int color[4], bits;
598             memset(color, 0, sizeof(color));
599 //warning following is purely guessed ...
600             color[0]= AV_RN16(buf); buf+=2; //FIXME use bytestream
601             color[1]= AV_RN16(buf); buf+=2;
602
603             if(color[0]&0x8000) av_log(NULL, AV_LOG_ERROR, "unk bit 1\n");
604             if(color[1]&0x8000) av_log(NULL, AV_LOG_ERROR, "unk bit 2\n");
605
606             color[2]= mix(color[0], color[1]);
607             color[3]= mix(color[1], color[0]);
608
609             bits= AV_RL32(buf); buf+= 4;
610             for(y2=0; y2<16; y2++){
611                 for(x2=0; x2<16; x2++){
612                     int index= 2*(x2>>2) + 8*(y2>>2);
613                     dst[y2*stride+x2]= color[(bits>>index)&3];
614                 }
615             }
616             dst+=16;
617         }
618         dst += 16*stride - width;
619     }
620
621     return 0;
622 }
623
624 static int decode_i_frame(FourXContext *f, uint8_t *buf, int length){
625     int x, y;
626     const int width= f->avctx->width;
627     const int height= f->avctx->height;
628     uint16_t *dst= (uint16_t*)f->current_picture.data[0];
629     const int stride= f->current_picture.linesize[0]>>1;
630     const unsigned int bitstream_size= get32(buf);
631     const int token_count av_unused = get32(buf + bitstream_size + 8);
632     unsigned int prestream_size= 4*get32(buf + bitstream_size + 4);
633     uint8_t *prestream= buf + bitstream_size + 12;
634
635     if(prestream_size + bitstream_size + 12 != length
636        || bitstream_size > (1<<26)
637        || prestream_size > (1<<26)){
638         av_log(f->avctx, AV_LOG_ERROR, "size mismatch %d %d %d\n", prestream_size, bitstream_size, length);
639         return -1;
640     }
641
642     prestream= read_huffman_tables(f, prestream);
643
644     init_get_bits(&f->gb, buf + 4, 8*bitstream_size);
645
646     prestream_size= length + buf - prestream;
647
648     f->bitstream_buffer= av_fast_realloc(f->bitstream_buffer, &f->bitstream_buffer_size, prestream_size + FF_INPUT_BUFFER_PADDING_SIZE);
649     f->dsp.bswap_buf((uint32_t*)f->bitstream_buffer, (uint32_t*)prestream, prestream_size/4);
650     init_get_bits(&f->pre_gb, f->bitstream_buffer, 8*prestream_size);
651
652     f->last_dc= 0*128*8*8;
653
654     for(y=0; y<height; y+=16){
655         for(x=0; x<width; x+=16){
656             if(decode_i_mb(f) < 0)
657                 return -1;
658
659             idct_put(f, x, y);
660         }
661         dst += 16*stride;
662     }
663
664     if(get_vlc2(&f->pre_gb, f->pre_vlc.table, ACDC_VLC_BITS, 3) != 256)
665         av_log(f->avctx, AV_LOG_ERROR, "end mismatch\n");
666
667     return 0;
668 }
669
670 static int decode_frame(AVCodecContext *avctx,
671                         void *data, int *data_size,
672                         uint8_t *buf, int buf_size)
673 {
674     FourXContext * const f = avctx->priv_data;
675     AVFrame *picture = data;
676     AVFrame *p, temp;
677     int i, frame_4cc, frame_size;
678
679     frame_4cc= get32(buf);
680     if(buf_size != get32(buf+4)+8 || buf_size < 20){
681         av_log(f->avctx, AV_LOG_ERROR, "size mismatch %d %d\n", buf_size, get32(buf+4));
682     }
683
684     if(frame_4cc == ff_get_fourcc("cfrm")){
685         int free_index=-1;
686         const int data_size= buf_size - 20;
687         const int id= get32(buf+12);
688         const int whole_size= get32(buf+16);
689         CFrameBuffer *cfrm;
690
691         for(i=0; i<CFRAME_BUFFER_COUNT; i++){
692             if(f->cfrm[i].id && f->cfrm[i].id < avctx->frame_number)
693                 av_log(f->avctx, AV_LOG_ERROR, "lost c frame %d\n", f->cfrm[i].id);
694         }
695
696         for(i=0; i<CFRAME_BUFFER_COUNT; i++){
697             if(f->cfrm[i].id   == id) break;
698             if(f->cfrm[i].size == 0 ) free_index= i;
699         }
700
701         if(i>=CFRAME_BUFFER_COUNT){
702             i= free_index;
703             f->cfrm[i].id= id;
704         }
705         cfrm= &f->cfrm[i];
706
707         cfrm->data= av_fast_realloc(cfrm->data, &cfrm->allocated_size, cfrm->size + data_size + FF_INPUT_BUFFER_PADDING_SIZE);
708         if(!cfrm->data){ //explicit check needed as memcpy below might not catch a NULL
709             av_log(f->avctx, AV_LOG_ERROR, "realloc falure");
710             return -1;
711         }
712
713         memcpy(cfrm->data + cfrm->size, buf+20, data_size);
714         cfrm->size += data_size;
715
716         if(cfrm->size >= whole_size){
717             buf= cfrm->data;
718             frame_size= cfrm->size;
719
720             if(id != avctx->frame_number){
721                 av_log(f->avctx, AV_LOG_ERROR, "cframe id mismatch %d %d\n", id, avctx->frame_number);
722             }
723
724             cfrm->size= cfrm->id= 0;
725             frame_4cc= ff_get_fourcc("pfrm");
726         }else
727             return buf_size;
728     }else{
729         buf= buf + 12;
730         frame_size= buf_size - 12;
731     }
732
733     temp= f->current_picture;
734     f->current_picture= f->last_picture;
735     f->last_picture= temp;
736
737     p= &f->current_picture;
738     avctx->coded_frame= p;
739
740     avctx->flags |= CODEC_FLAG_EMU_EDGE; // alternatively we would have to use our own buffer management
741
742     if(p->data[0])
743         avctx->release_buffer(avctx, p);
744
745     p->reference= 1;
746     if(avctx->get_buffer(avctx, p) < 0){
747         av_log(avctx, AV_LOG_ERROR, "get_buffer() failed\n");
748         return -1;
749     }
750
751     if(frame_4cc == ff_get_fourcc("ifr2")){
752         p->pict_type= I_TYPE;
753         if(decode_i2_frame(f, buf-4, frame_size) < 0)
754             return -1;
755     }else if(frame_4cc == ff_get_fourcc("ifrm")){
756         p->pict_type= I_TYPE;
757         if(decode_i_frame(f, buf, frame_size) < 0)
758             return -1;
759     }else if(frame_4cc == ff_get_fourcc("pfrm") || frame_4cc == ff_get_fourcc("pfr2")){
760         p->pict_type= P_TYPE;
761         if(decode_p_frame(f, buf, frame_size) < 0)
762             return -1;
763     }else if(frame_4cc == ff_get_fourcc("snd_")){
764         av_log(avctx, AV_LOG_ERROR, "ignoring snd_ chunk length:%d\n", buf_size);
765     }else{
766         av_log(avctx, AV_LOG_ERROR, "ignoring unknown chunk length:%d\n", buf_size);
767     }
768
769     p->key_frame= p->pict_type == I_TYPE;
770
771     *picture= *p;
772     *data_size = sizeof(AVPicture);
773
774     emms_c();
775
776     return buf_size;
777 }
778
779
780 static void common_init(AVCodecContext *avctx){
781     FourXContext * const f = avctx->priv_data;
782
783     dsputil_init(&f->dsp, avctx);
784
785     f->avctx= avctx;
786 }
787
788 static int decode_init(AVCodecContext *avctx){
789     FourXContext * const f = avctx->priv_data;
790
791     f->version= avctx->codec_tag == 0x40000;
792     common_init(avctx);
793     init_vlcs(f);
794
795     if(f->version) avctx->pix_fmt= PIX_FMT_RGB565;
796     else           avctx->pix_fmt= PIX_FMT_RGB555;
797
798     return 0;
799 }
800
801
802 static int decode_end(AVCodecContext *avctx){
803     FourXContext * const f = avctx->priv_data;
804     int i;
805
806     av_freep(&f->bitstream_buffer);
807     f->bitstream_buffer_size=0;
808     for(i=0; i<CFRAME_BUFFER_COUNT; i++){
809         av_freep(&f->cfrm[i].data);
810         f->cfrm[i].allocated_size= 0;
811     }
812     free_vlc(&f->pre_vlc);
813
814     return 0;
815 }
816
817 AVCodec fourxm_decoder = {
818     "4xm",
819     CODEC_TYPE_VIDEO,
820     CODEC_ID_4XM,
821     sizeof(FourXContext),
822     decode_init,
823     NULL,
824     decode_end,
825     decode_frame,
826     /*CODEC_CAP_DR1,*/
827 };
828