replace vlc_type by version and set that from codec_tag which contains the
[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         f->mv[i] = mv[i][0] + mv[i][1]*f->current_picture.linesize[0]/2;
252     }
253 }
254
255 static inline void mcdc(uint16_t *dst, uint16_t *src, int log2w, int h, int stride, int scale, int dc){
256    int i;
257    dc*= 0x10001;
258
259    switch(log2w){
260    case 0:
261         for(i=0; i<h; i++){
262             dst[0] = scale*src[0] + dc;
263             if(scale) src += stride;
264             dst += stride;
265         }
266         break;
267     case 1:
268         for(i=0; i<h; i++){
269             ((uint32_t*)dst)[0] = scale*((uint32_t*)src)[0] + dc;
270             if(scale) src += stride;
271             dst += stride;
272         }
273         break;
274     case 2:
275         for(i=0; i<h; i++){
276             ((uint32_t*)dst)[0] = scale*((uint32_t*)src)[0] + dc;
277             ((uint32_t*)dst)[1] = scale*((uint32_t*)src)[1] + dc;
278             if(scale) src += stride;
279             dst += stride;
280         }
281         break;
282     case 3:
283         for(i=0; i<h; i++){
284             ((uint32_t*)dst)[0] = scale*((uint32_t*)src)[0] + dc;
285             ((uint32_t*)dst)[1] = scale*((uint32_t*)src)[1] + dc;
286             ((uint32_t*)dst)[2] = scale*((uint32_t*)src)[2] + dc;
287             ((uint32_t*)dst)[3] = scale*((uint32_t*)src)[3] + dc;
288             if(scale) src += stride;
289             dst += stride;
290         }
291         break;
292     default: assert(0);
293     }
294 }
295
296 static void decode_p_block(FourXContext *f, uint16_t *dst, uint16_t *src, int log2w, int log2h, int stride){
297     const int index= size2index[log2h][log2w];
298     const int h= 1<<log2h;
299     int code= get_vlc2(&f->gb, block_type_vlc[1-f->version][index].table, BLOCK_TYPE_VLC_BITS, 1);
300
301     assert(code>=0 && code<=6);
302
303     if(code == 0){
304         src += f->mv[ *f->bytestream++ ];
305         mcdc(dst, src, log2w, h, stride, 1, 0);
306     }else if(code == 1){
307         log2h--;
308         decode_p_block(f, dst                  , src                  , log2w, log2h, stride);
309         decode_p_block(f, dst + (stride<<log2h), src + (stride<<log2h), log2w, log2h, stride);
310     }else if(code == 2){
311         log2w--;
312         decode_p_block(f, dst             , src             , log2w, log2h, stride);
313         decode_p_block(f, dst + (1<<log2w), src + (1<<log2w), log2w, log2h, stride);
314     }else if(code == 4){
315         src += f->mv[ *f->bytestream++ ];
316         mcdc(dst, src, log2w, h, stride, 1, le2me_16(*f->wordstream++));
317     }else if(code == 5){
318         mcdc(dst, src, log2w, h, stride, 0, le2me_16(*f->wordstream++));
319     }else if(code == 6){
320         if(log2w){
321             dst[0] = le2me_16(*f->wordstream++);
322             dst[1] = le2me_16(*f->wordstream++);
323         }else{
324             dst[0     ] = le2me_16(*f->wordstream++);
325             dst[stride] = le2me_16(*f->wordstream++);
326         }
327     }
328 }
329
330 static int get32(void *p){
331     return le2me_32(*(uint32_t*)p);
332 }
333
334 static int decode_p_frame(FourXContext *f, uint8_t *buf, int length){
335     int x, y;
336     const int width= f->avctx->width;
337     const int height= f->avctx->height;
338     uint16_t *src= (uint16_t*)f->last_picture.data[0];
339     uint16_t *dst= (uint16_t*)f->current_picture.data[0];
340     const int stride= f->current_picture.linesize[0]>>1;
341     unsigned int bitstream_size, bytestream_size, wordstream_size, extra;
342
343     if(!get32(buf-4)){
344         extra=20;
345         bitstream_size= get32(buf+8);
346         wordstream_size= get32(buf+12);
347         bytestream_size= get32(buf+16);
348     }else{
349         extra=0;
350         bitstream_size = AV_RL16(buf-4);
351         wordstream_size= AV_RL16(buf-2);
352         bytestream_size= FFMAX(length - bitstream_size - wordstream_size, 0);
353     }
354
355     if(bitstream_size+ bytestream_size+ wordstream_size + extra != length
356        || bitstream_size  > (1<<26)
357        || bytestream_size > (1<<26)
358        || wordstream_size > (1<<26)
359        ){
360         av_log(f->avctx, AV_LOG_ERROR, "lengths %d %d %d %d\n", bitstream_size, bytestream_size, wordstream_size,
361         bitstream_size+ bytestream_size+ wordstream_size - length);
362         return -1;
363     }
364
365     f->bitstream_buffer= av_fast_realloc(f->bitstream_buffer, &f->bitstream_buffer_size, bitstream_size + FF_INPUT_BUFFER_PADDING_SIZE);
366     f->dsp.bswap_buf((uint32_t*)f->bitstream_buffer, (uint32_t*)(buf + extra), bitstream_size/4);
367     init_get_bits(&f->gb, f->bitstream_buffer, 8*bitstream_size);
368
369     f->wordstream= (uint16_t*)(buf + extra + bitstream_size);
370     f->bytestream= buf + extra + bitstream_size + wordstream_size;
371
372     init_mv(f);
373
374     for(y=0; y<height; y+=8){
375         for(x=0; x<width; x+=8){
376             decode_p_block(f, dst + x, src + x, 3, 3, stride);
377         }
378         src += 8*stride;
379         dst += 8*stride;
380     }
381
382     if(   bitstream_size != (get_bits_count(&f->gb)+31)/32*4
383        || (((char*)f->wordstream - (char*)buf + 2)&~2) != extra + bitstream_size + wordstream_size
384        || (((char*)f->bytestream - (char*)buf + 3)&~3) != extra + bitstream_size + wordstream_size + bytestream_size)
385         av_log(f->avctx, AV_LOG_ERROR, " %d %td %td bytes left\n",
386             bitstream_size - (get_bits_count(&f->gb)+31)/32*4,
387             -(((char*)f->bytestream - (char*)buf + 3)&~3) + (extra + bitstream_size + wordstream_size + bytestream_size),
388             -(((char*)f->wordstream - (char*)buf + 2)&~2) + (extra + bitstream_size + wordstream_size)
389         );
390
391     return 0;
392 }
393
394 /**
395  * decode block and dequantize.
396  * Note this is allmost identical to mjpeg
397  */
398 static int decode_i_block(FourXContext *f, DCTELEM *block){
399     int code, i, j, level, val;
400
401     /* DC coef */
402     val = get_vlc2(&f->pre_gb, f->pre_vlc.table, ACDC_VLC_BITS, 3);
403     if (val>>4){
404         av_log(f->avctx, AV_LOG_ERROR, "error dc run != 0\n");
405     }
406
407     if(val)
408         val = get_xbits(&f->gb, val);
409
410     val = val * dequant_table[0] + f->last_dc;
411     f->last_dc =
412     block[0] = val;
413     /* AC coefs */
414     i = 1;
415     for(;;) {
416         code = get_vlc2(&f->pre_gb, f->pre_vlc.table, ACDC_VLC_BITS, 3);
417
418         /* EOB */
419         if (code == 0)
420             break;
421         if (code == 0xf0) {
422             i += 16;
423         } else {
424             level = get_xbits(&f->gb, code & 0xf);
425             i += code >> 4;
426             if (i >= 64) {
427                 av_log(f->avctx, AV_LOG_ERROR, "run %d oveflow\n", i);
428                 return 0;
429             }
430
431             j= ff_zigzag_direct[i];
432             block[j] = level * dequant_table[j];
433             i++;
434             if (i >= 64)
435                 break;
436         }
437     }
438
439     return 0;
440 }
441
442 static inline void idct_put(FourXContext *f, int x, int y){
443     DCTELEM (*block)[64]= f->block;
444     int stride= f->current_picture.linesize[0]>>1;
445     int i;
446     uint16_t *dst = ((uint16_t*)f->current_picture.data[0]) + y * stride + x;
447
448     for(i=0; i<4; i++){
449         block[i][0] += 0x80*8*8;
450         idct(block[i]);
451     }
452
453     if(!(f->avctx->flags&CODEC_FLAG_GRAY)){
454         for(i=4; i<6; i++) idct(block[i]);
455     }
456
457 /* Note transform is:
458 y= ( 1b + 4g + 2r)/14
459 cb=( 3b - 2g - 1r)/14
460 cr=(-1b - 4g + 5r)/14
461 */
462     for(y=0; y<8; y++){
463         for(x=0; x<8; x++){
464             DCTELEM *temp= block[(x>>2) + 2*(y>>2)] + 2*(x&3) + 2*8*(y&3); //FIXME optimize
465             int cb= block[4][x + 8*y];
466             int cr= block[5][x + 8*y];
467             int cg= (cb + cr)>>1;
468             int y;
469
470             cb+=cb;
471
472             y = temp[0];
473             dst[0       ]= ((y+cb)>>3) + (((y-cg)&0xFC)<<3) + (((y+cr)&0xF8)<<8);
474             y = temp[1];
475             dst[1       ]= ((y+cb)>>3) + (((y-cg)&0xFC)<<3) + (((y+cr)&0xF8)<<8);
476             y = temp[8];
477             dst[  stride]= ((y+cb)>>3) + (((y-cg)&0xFC)<<3) + (((y+cr)&0xF8)<<8);
478             y = temp[9];
479             dst[1+stride]= ((y+cb)>>3) + (((y-cg)&0xFC)<<3) + (((y+cr)&0xF8)<<8);
480             dst += 2;
481         }
482         dst += 2*stride - 2*8;
483     }
484 }
485
486 static int decode_i_mb(FourXContext *f){
487     int i;
488
489     f->dsp.clear_blocks(f->block[0]);
490
491     for(i=0; i<6; i++){
492         if(decode_i_block(f, f->block[i]) < 0)
493             return -1;
494     }
495
496     return 0;
497 }
498
499 static uint8_t *read_huffman_tables(FourXContext *f, uint8_t * const buf){
500     int frequency[512];
501     uint8_t flag[512];
502     int up[512];
503     uint8_t len_tab[257];
504     int bits_tab[257];
505     int start, end;
506     uint8_t *ptr= buf;
507     int j;
508
509     memset(frequency, 0, sizeof(frequency));
510     memset(up, -1, sizeof(up));
511
512     start= *ptr++;
513     end= *ptr++;
514     for(;;){
515         int i;
516
517         for(i=start; i<=end; i++){
518             frequency[i]= *ptr++;
519         }
520         start= *ptr++;
521         if(start==0) break;
522
523         end= *ptr++;
524     }
525     frequency[256]=1;
526
527     while((ptr - buf)&3) ptr++; // 4byte align
528
529     for(j=257; j<512; j++){
530         int min_freq[2]= {256*256, 256*256};
531         int smallest[2]= {0, 0};
532         int i;
533         for(i=0; i<j; i++){
534             if(frequency[i] == 0) continue;
535             if(frequency[i] < min_freq[1]){
536                 if(frequency[i] < min_freq[0]){
537                     min_freq[1]= min_freq[0]; smallest[1]= smallest[0];
538                     min_freq[0]= frequency[i];smallest[0]= i;
539                 }else{
540                     min_freq[1]= frequency[i];smallest[1]= i;
541                 }
542             }
543         }
544         if(min_freq[1] == 256*256) break;
545
546         frequency[j]= min_freq[0] + min_freq[1];
547         flag[ smallest[0] ]= 0;
548         flag[ smallest[1] ]= 1;
549         up[ smallest[0] ]=
550         up[ smallest[1] ]= j;
551         frequency[ smallest[0] ]= frequency[ smallest[1] ]= 0;
552     }
553
554     for(j=0; j<257; j++){
555         int node;
556         int len=0;
557         int bits=0;
558
559         for(node= j; up[node] != -1; node= up[node]){
560             bits += flag[node]<<len;
561             len++;
562             if(len > 31) av_log(f->avctx, AV_LOG_ERROR, "vlc length overflow\n"); //can this happen at all ?
563         }
564
565         bits_tab[j]= bits;
566         len_tab[j]= len;
567     }
568
569     init_vlc(&f->pre_vlc, ACDC_VLC_BITS, 257,
570              len_tab , 1, 1,
571              bits_tab, 4, 4, 0);
572
573     return ptr;
574 }
575
576 static int mix(int c0, int c1){
577     int blue = 2*(c0&0x001F) + (c1&0x001F);
578     int green= (2*(c0&0x03E0) + (c1&0x03E0))>>5;
579     int red  = 2*(c0>>10) + (c1>>10);
580     return red/3*1024 + green/3*32 + blue/3;
581 }
582
583 static int decode_i2_frame(FourXContext *f, uint8_t *buf, int length){
584     int x, y, x2, y2;
585     const int width= f->avctx->width;
586     const int height= f->avctx->height;
587     uint16_t *dst= (uint16_t*)f->current_picture.data[0];
588     const int stride= f->current_picture.linesize[0]>>1;
589
590     for(y=0; y<height; y+=16){
591         for(x=0; x<width; x+=16){
592             unsigned int color[4], bits;
593             memset(color, 0, sizeof(color));
594 //warning following is purely guessed ...
595             color[0]= AV_RN16(buf); buf+=2; //FIXME use bytestream
596             color[1]= AV_RN16(buf); buf+=2;
597
598             if(color[0]&0x8000) av_log(NULL, AV_LOG_ERROR, "unk bit 1\n");
599             if(color[1]&0x8000) av_log(NULL, AV_LOG_ERROR, "unk bit 2\n");
600
601             color[2]= mix(color[0], color[1]);
602             color[3]= mix(color[1], color[0]);
603
604             bits= AV_RL32(buf); buf+= 4;
605             for(y2=0; y2<16; y2++){
606                 for(x2=0; x2<16; x2++){
607                     int index= 2*(x2>>2) + 8*(y2>>2);
608                     dst[y2*stride+x2]= color[(bits>>index)&3];
609                 }
610             }
611             dst+=16;
612         }
613         dst += 16*stride - width;
614     }
615
616     return 0;
617 }
618
619 static int decode_i_frame(FourXContext *f, uint8_t *buf, int length){
620     int x, y;
621     const int width= f->avctx->width;
622     const int height= f->avctx->height;
623     uint16_t *dst= (uint16_t*)f->current_picture.data[0];
624     const int stride= f->current_picture.linesize[0]>>1;
625     const unsigned int bitstream_size= get32(buf);
626     const int token_count av_unused = get32(buf + bitstream_size + 8);
627     unsigned int prestream_size= 4*get32(buf + bitstream_size + 4);
628     uint8_t *prestream= buf + bitstream_size + 12;
629
630     if(prestream_size + bitstream_size + 12 != length
631        || bitstream_size > (1<<26)
632        || prestream_size > (1<<26)){
633         av_log(f->avctx, AV_LOG_ERROR, "size mismatch %d %d %d\n", prestream_size, bitstream_size, length);
634         return -1;
635     }
636
637     prestream= read_huffman_tables(f, prestream);
638
639     init_get_bits(&f->gb, buf + 4, 8*bitstream_size);
640
641     prestream_size= length + buf - prestream;
642
643     f->bitstream_buffer= av_fast_realloc(f->bitstream_buffer, &f->bitstream_buffer_size, prestream_size + FF_INPUT_BUFFER_PADDING_SIZE);
644     f->dsp.bswap_buf((uint32_t*)f->bitstream_buffer, (uint32_t*)prestream, prestream_size/4);
645     init_get_bits(&f->pre_gb, f->bitstream_buffer, 8*prestream_size);
646
647     f->last_dc= 0*128*8*8;
648
649     for(y=0; y<height; y+=16){
650         for(x=0; x<width; x+=16){
651             if(decode_i_mb(f) < 0)
652                 return -1;
653
654             idct_put(f, x, y);
655         }
656         dst += 16*stride;
657     }
658
659     if(get_vlc2(&f->pre_gb, f->pre_vlc.table, ACDC_VLC_BITS, 3) != 256)
660         av_log(f->avctx, AV_LOG_ERROR, "end mismatch\n");
661
662     return 0;
663 }
664
665 static int decode_frame(AVCodecContext *avctx,
666                         void *data, int *data_size,
667                         uint8_t *buf, int buf_size)
668 {
669     FourXContext * const f = avctx->priv_data;
670     AVFrame *picture = data;
671     AVFrame *p, temp;
672     int i, frame_4cc, frame_size;
673
674     frame_4cc= get32(buf);
675     if(buf_size != get32(buf+4)+8 || buf_size < 20){
676         av_log(f->avctx, AV_LOG_ERROR, "size mismatch %d %d\n", buf_size, get32(buf+4));
677     }
678
679     if(frame_4cc == ff_get_fourcc("cfrm")){
680         int free_index=-1;
681         const int data_size= buf_size - 20;
682         const int id= get32(buf+12);
683         const int whole_size= get32(buf+16);
684         CFrameBuffer *cfrm;
685
686         for(i=0; i<CFRAME_BUFFER_COUNT; i++){
687             if(f->cfrm[i].id && f->cfrm[i].id < avctx->frame_number)
688                 av_log(f->avctx, AV_LOG_ERROR, "lost c frame %d\n", f->cfrm[i].id);
689         }
690
691         for(i=0; i<CFRAME_BUFFER_COUNT; i++){
692             if(f->cfrm[i].id   == id) break;
693             if(f->cfrm[i].size == 0 ) free_index= i;
694         }
695
696         if(i>=CFRAME_BUFFER_COUNT){
697             i= free_index;
698             f->cfrm[i].id= id;
699         }
700         cfrm= &f->cfrm[i];
701
702         cfrm->data= av_fast_realloc(cfrm->data, &cfrm->allocated_size, cfrm->size + data_size + FF_INPUT_BUFFER_PADDING_SIZE);
703         if(!cfrm->data){ //explicit check needed as memcpy below might not catch a NULL
704             av_log(f->avctx, AV_LOG_ERROR, "realloc falure");
705             return -1;
706         }
707
708         memcpy(cfrm->data + cfrm->size, buf+20, data_size);
709         cfrm->size += data_size;
710
711         if(cfrm->size >= whole_size){
712             buf= cfrm->data;
713             frame_size= cfrm->size;
714
715             if(id != avctx->frame_number){
716                 av_log(f->avctx, AV_LOG_ERROR, "cframe id mismatch %d %d\n", id, avctx->frame_number);
717             }
718
719             cfrm->size= cfrm->id= 0;
720             frame_4cc= ff_get_fourcc("pfrm");
721         }else
722             return buf_size;
723     }else{
724         buf= buf + 12;
725         frame_size= buf_size - 12;
726     }
727
728     temp= f->current_picture;
729     f->current_picture= f->last_picture;
730     f->last_picture= temp;
731
732     p= &f->current_picture;
733     avctx->coded_frame= p;
734
735     avctx->flags |= CODEC_FLAG_EMU_EDGE; // alternatively we would have to use our own buffer management
736
737     if(p->data[0])
738         avctx->release_buffer(avctx, p);
739
740     p->reference= 1;
741     if(avctx->get_buffer(avctx, p) < 0){
742         av_log(avctx, AV_LOG_ERROR, "get_buffer() failed\n");
743         return -1;
744     }
745
746     if(frame_4cc == ff_get_fourcc("ifr2")){
747         p->pict_type= I_TYPE;
748         if(decode_i2_frame(f, buf-4, frame_size) < 0)
749             return -1;
750     }else if(frame_4cc == ff_get_fourcc("ifrm")){
751         p->pict_type= I_TYPE;
752         if(decode_i_frame(f, buf, frame_size) < 0)
753             return -1;
754     }else if(frame_4cc == ff_get_fourcc("pfrm") || frame_4cc == ff_get_fourcc("pfr2")){
755         p->pict_type= P_TYPE;
756         if(decode_p_frame(f, buf, frame_size) < 0)
757             return -1;
758     }else if(frame_4cc == ff_get_fourcc("snd_")){
759         av_log(avctx, AV_LOG_ERROR, "ignoring snd_ chunk length:%d\n", buf_size);
760     }else{
761         av_log(avctx, AV_LOG_ERROR, "ignoring unknown chunk length:%d\n", buf_size);
762     }
763
764     p->key_frame= p->pict_type == I_TYPE;
765
766     *picture= *p;
767     *data_size = sizeof(AVPicture);
768
769     emms_c();
770
771     return buf_size;
772 }
773
774
775 static void common_init(AVCodecContext *avctx){
776     FourXContext * const f = avctx->priv_data;
777
778     dsputil_init(&f->dsp, avctx);
779
780     f->avctx= avctx;
781 }
782
783 static int decode_init(AVCodecContext *avctx){
784     FourXContext * const f = avctx->priv_data;
785
786     f->version= avctx->codec_tag == 0x40000;
787     common_init(avctx);
788     init_vlcs(f);
789
790     avctx->pix_fmt= PIX_FMT_RGB565;
791
792     return 0;
793 }
794
795
796 static int decode_end(AVCodecContext *avctx){
797     FourXContext * const f = avctx->priv_data;
798     int i;
799
800     av_freep(&f->bitstream_buffer);
801     f->bitstream_buffer_size=0;
802     for(i=0; i<CFRAME_BUFFER_COUNT; i++){
803         av_freep(&f->cfrm[i].data);
804         f->cfrm[i].allocated_size= 0;
805     }
806     free_vlc(&f->pre_vlc);
807
808     return 0;
809 }
810
811 AVCodec fourxm_decoder = {
812     "4xm",
813     CODEC_TYPE_VIDEO,
814     CODEC_ID_4XM,
815     sizeof(FourXContext),
816     decode_init,
817     NULL,
818     decode_end,
819     decode_frame,
820     /*CODEC_CAP_DR1,*/
821 };
822