aboutsummaryrefslogtreecommitdiffstats
path: root/libavcodec/vqavideo.c
blob: ea86fb1086a915e2af7b5553537eda16f0a4a573 (plain) (blame)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
/*
 * Westwood Studios VQA Video Decoder
 * Copyright (C) 2003 the ffmpeg project
 *
 * This library is free software; you can redistribute it and/or
 * modify it under the terms of the GNU Lesser General Public
 * License as published by the Free Software Foundation; either
 * version 2 of the License, or (at your option) any later version.
 *
 * This library is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
 * Lesser General Public License for more details.
 *
 * You should have received a copy of the GNU Lesser General Public
 * License along with this library; if not, write to the Free Software
 * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
 *
 */

/**
 * @file vqavideo.c
 * VQA Video Decoder by Mike Melanson (melanson@pcisys.net)
 * For more information about the RPZA format, visit:
 *   http://www.pcisys.net/~melanson/codecs/
 *
 * The VQA video decoder outputs PAL8 or RGB555 colorspace data, depending
 * on the type of data in the file.
 *
 * This decoder needs the 42-byte VQHD header from the beginning
 * of the VQA file passed through the extradata field. The VQHD header
 * is laid out as:
 *
 *   bytes 0-3   chunk fourcc: 'VQHD'
 *   bytes 4-7   chunk size in big-endian format, should be 0x0000002A
 *   bytes 8-49  VQHD chunk data
 *
 * Bytes 8-49 are what this decoder expects to see.
 *
 * Briefly, VQA is a vector quantized animation format that operates in a
 * VGA palettized colorspace. It operates on pixel vectors (blocks)
 * of either 4x2 or 4x4 in size. Compressed VQA chunks can contain vector
 * codebooks, palette information, and code maps for rendering vectors onto
 * frames. Any of these components can also be compressed with a run-length
 * encoding (RLE) algorithm commonly referred to as "format80".
 *
 * VQA takes a novel approach to rate control. Each group of n frames
 * (usually, n = 8) relies on a different vector codebook. Rather than
 * transporting an entire codebook every 8th frame, the new codebook is
 * broken up into 8 pieces and sent along with the compressed video chunks
 * for each of the 8 frames preceding the 8 frames which require the
 * codebook. A full codebook is also sent on the very first frame of a
 * file. This is an interesting technique, although it makes random file
 * seeking difficult despite the fact that the frames are all intracoded.
 *
 * V1,2 VQA uses 12-bit codebook indices. If the 12-bit indices were
 * packed into bytes and then RLE compressed, bytewise, the results would
 * be poor. That is why the coding method divides each index into 2 parts,
 * the top 4 bits and the bottom 8 bits, then RL encodes the 4-bit pieces
 * together and the 8-bit pieces together. If most of the vectors are
 * clustered into one group of 256 vectors, most of the 4-bit index pieces
 * should be the same.
 */

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <unistd.h>

#include "common.h"
#include "avcodec.h"
#include "dsputil.h"

#define PALETTE_COUNT 256
#define VQA_HEADER_SIZE 0x2A
#define CHUNK_PREAMBLE_SIZE 8

/* allocate the maximum vector space, regardless of the file version:
 * (0xFF00 codebook vectors + 0x100 solid pixel vectors) * (4x4 pixels/block) */
#define MAX_CODEBOOK_VECTORS 0xFF00
#define SOLID_PIXEL_VECTORS 0x100
#define MAX_VECTORS (MAX_CODEBOOK_VECTORS + SOLID_PIXEL_VECTORS)
#define MAX_CODEBOOK_SIZE (MAX_VECTORS * 4 * 4)

#define CBF0_TAG MKBETAG('C', 'B', 'F', '0')
#define CBFZ_TAG MKBETAG('C', 'B', 'F', 'Z')
#define CBP0_TAG MKBETAG('C', 'B', 'P', '0')
#define CBPZ_TAG MKBETAG('C', 'B', 'P', 'Z')
#define CPL0_TAG MKBETAG('C', 'P', 'L', '0')
#define CPLZ_TAG MKBETAG('C', 'P', 'L', 'Z')
#define VPTZ_TAG MKBETAG('V', 'P', 'T', 'Z')

#define VQA_DEBUG 0

#if VQA_DEBUG
#define vqa_debug printf
#else
static inline void vqa_debug(const char *format, ...) { }
#endif

typedef struct VqaContext {

    AVCodecContext *avctx;
    DSPContext dsp;
    AVFrame frame;

    unsigned char *buf;
    int size;

    unsigned int palette[PALETTE_COUNT];

    int width;   /* width of a frame */
    int height;   /* height of a frame */
    int vector_width;  /* width of individual vector */
    int vector_height;  /* height of individual vector */
    int vqa_version;  /* this should be either 1, 2 or 3 */

    unsigned char *codebook;         /* the current codebook */
    int codebook_size;
    unsigned char *next_codebook_buffer;  /* accumulator for next codebook */
    int next_codebook_buffer_index;

    unsigned char *decode_buffer;
    int decode_buffer_size;

    /* number of frames to go before replacing codebook */
    int partial_countdown;
    int partial_count;

} VqaContext;

static int vqa_decode_init(AVCodecContext *avctx)
{
    VqaContext *s = (VqaContext *)avctx->priv_data;
    unsigned char *vqa_header;
    int i, j, codebook_index;;

    s->avctx = avctx;
    avctx->pix_fmt = PIX_FMT_PAL8;
    avctx->has_b_frames = 0;
    dsputil_init(&s->dsp, avctx);

    /* make sure the extradata made it */
    if (s->avctx->extradata_size != VQA_HEADER_SIZE) {
        av_log(s->avctx, AV_LOG_ERROR, "  VQA video: expected extradata size of %d\n", VQA_HEADER_SIZE);
        return -1;
    }

    /* load up the VQA parameters from the header */
    vqa_header = (unsigned char *)s->avctx->extradata;
    s->vqa_version = vqa_header[0];
    s->width = LE_16(&vqa_header[6]);
    s->height = LE_16(&vqa_header[8]);
    s->vector_width = vqa_header[10];
    s->vector_height = vqa_header[11];
    s->partial_count = s->partial_countdown = vqa_header[13];

    /* the vector dimensions have to meet very stringent requirements */
    if ((s->vector_width != 4) ||
        ((s->vector_height != 2) && (s->vector_height != 4))) {
        /* return without further initialization */
        return -1;
    }

    /* allocate codebooks */
    s->codebook_size = MAX_CODEBOOK_SIZE;
    s->codebook = av_malloc(s->codebook_size);
    s->next_codebook_buffer = av_malloc(s->codebook_size);

    /* initialize the solid-color vectors */
    if (s->vector_height == 4) {
        codebook_index = 0xFF00 * 16;
        for (i = 0; i < 256; i++)
            for (j = 0; j < 16; j++)
                s->codebook[codebook_index++] = i;
    } else {
        codebook_index = 0xF00 * 8;
        for (i = 0; i < 256; i++)
            for (j = 0; j < 8; j++)
                s->codebook[codebook_index++] = i;
    }
    s->next_codebook_buffer_index = 0;

    /* allocate decode buffer */
    s->decode_buffer_size = (s->width / s->vector_width) *
        (s->height / s->vector_height) * 2;
    s->decode_buffer = av_malloc(s->decode_buffer_size);

    s->frame.data[0] = NULL;

    return 0;
}

#define CHECK_COUNT() \
    if (dest_index + count > dest_size) { \
        av_log(NULL, AV_LOG_ERROR, "  VQA video: decode_format80 problem: next op would overflow dest_index\n"); \
        av_log(NULL, AV_LOG_ERROR, "  VQA video: current dest_index = %d, count = %d, dest_size = %d\n", \
            dest_index, count, dest_size); \
        return; \
    }

static void decode_format80(unsigned char *src, int src_size,
    unsigned char *dest, int dest_size, int check_size) {

    int src_index = 0;
    int dest_index = 0;
    int count;
    int src_pos;
    unsigned char color;
    int i;

    while (src_index < src_size) {

        vqa_debug("      opcode %02X: ", src[src_index]);

        /* 0x80 means that frame is finished */
        if (src[src_index] == 0x80)
            return;

        if (dest_index >= dest_size) {
            av_log(NULL, AV_LOG_ERROR, "  VQA video: decode_format80 problem: dest_index (%d) exceeded dest_size (%d)\n",
                dest_index, dest_size);
            return;
        }

        if (src[src_index] == 0xFF) {

            src_index++;
            count = LE_16(&src[src_index]);
            src_index += 2;
            src_pos = LE_16(&src[src_index]);
            src_index += 2;
            vqa_debug("(1) copy %X bytes from absolute pos %X\n", count, src_pos);
            CHECK_COUNT();
            for (i = 0; i < count; i++)
                dest[dest_index + i] = dest[src_pos + i];
            dest_index += count;

        } else if (src[src_index] == 0xFE) {

            src_index++;
            count = LE_16(&src[src_index]);
            src_index += 2;
            color = src[src_index++];
            vqa_debug("(2) set %X bytes to %02X\n", count, color);
            CHECK_COUNT();
            memset(&dest[dest_index], color, count);
            dest_index += count;

        } else if ((src[src_index] & 0xC0) == 0xC0) {

            count = (src[src_index++] & 0x3F) + 3;
            src_pos = LE_16(&src[src_index]);
            src_index += 2;
            vqa_debug("(3) copy %X bytes from absolute pos %X\n", count, src_pos);
            CHECK_COUNT();
            for (i = 0; i < count; i++)
                dest[dest_index + i] = dest[src_pos + i];
            dest_index += count;

        } else if (src[src_index] > 0x80) {

            count = src[src_index++] & 0x3F;
            vqa_debug("(4) copy %X bytes from source to dest\n", count);
            CHECK_COUNT();
            memcpy(&dest[dest_index], &src[src_index], count);
            src_index += count;
            dest_index += count;

        } else {

            count = ((src[src_index] & 0x70) >> 4) + 3;
            src_pos = BE_16(&src[src_index]) & 0x0FFF;
            src_index += 2;
            vqa_debug("(5) copy %X bytes from relpos %X\n", count, src_pos);
            CHECK_COUNT();
            for (i = 0; i < count; i++)
                dest[dest_index + i] = dest[dest_index - src_pos + i];
            dest_index += count;
        }
    }

    /* validate that the entire destination buffer was filled; this is
     * important for decoding frame maps since each vector needs to have a
     * codebook entry; it is not important for compressed codebooks because
     * not every entry needs to be filled */
    if (check_size)
        if (dest_index < dest_size)
            av_log(NULL, AV_LOG_ERROR, "  VQA video: decode_format80 problem: decode finished with dest_index (%d) < dest_size (%d)\n",
                dest_index, dest_size);
}

static void vqa_decode_chunk(VqaContext *s)
{
    unsigned int chunk_type;
    unsigned int chunk_size;
    int byte_skip;
    unsigned int index = 0;
    int i;
    unsigned char r, g, b;
    int index_shift;

    int cbf0_chunk = -1;
    int cbfz_chunk = -1;
    int cbp0_chunk = -1;
    int cbpz_chunk = -1;
    int cpl0_chunk = -1;
    int cplz_chunk = -1;
    int vptz_chunk = -1;

    int x, y;
    int lines = 0;
    int pixel_ptr;
    int vector_index = 0;
    int lobyte = 0;
    int hibyte = 0;
    int lobytes = 0;
    int hibytes = s->decode_buffer_size / 2;

    /* first, traverse through the frame and find the subchunks */
    while (index < s->size) {

        chunk_type = BE_32(&s->buf[index]);
        chunk_size = BE_32(&s->buf[index + 4]);

        switch (chunk_type) {

        case CBF0_TAG:
            cbf0_chunk = index;
            break;

        case CBFZ_TAG:
            cbfz_chunk = index;
            break;

        case CBP0_TAG:
            cbp0_chunk = index;
            break;

        case CBPZ_TAG:
            cbpz_chunk = index;
            break;

        case CPL0_TAG:
            cpl0_chunk = index;
            break;

        case CPLZ_TAG:
            cplz_chunk = index;
            break;

        case VPTZ_TAG:
            vptz_chunk = index;
            break;

        default:
            av_log(s->avctx, AV_LOG_ERROR, "  VQA video: Found unknown chunk type: %c%c%c%c (%08X)\n",
            (chunk_type >> 24) & 0xFF,
            (chunk_type >> 16) & 0xFF,
            (chunk_type >>  8) & 0xFF,
            (chunk_type >>  0) & 0xFF,
            chunk_type);
            break;
        }

        byte_skip = chunk_size & 0x01;
        index += (CHUNK_PREAMBLE_SIZE + chunk_size + byte_skip);
    }

    /* next, deal with the palette */
    if ((cpl0_chunk != -1) && (cplz_chunk != -1)) {

        /* a chunk should not have both chunk types */
        av_log(s->avctx, AV_LOG_ERROR, "  VQA video: problem: found both CPL0 and CPLZ chunks\n");
        return;
    }

    /* decompress the palette chunk */
    if (cplz_chunk != -1) {

/* yet to be handled */

    }

    /* convert the RGB palette into the machine's endian format */
    if (cpl0_chunk != -1) {

        chunk_size = BE_32(&s->buf[cpl0_chunk + 4]);
        /* sanity check the palette size */
        if (chunk_size / 3 > 256) {
            av_log(s->avctx, AV_LOG_ERROR, "  VQA video: problem: found a palette chunk with %d colors\n",
                chunk_size / 3);
            return;
        }
        cpl0_chunk += CHUNK_PREAMBLE_SIZE;
        for (i = 0; i < chunk_size / 3; i++) {
            /* scale by 4 to transform 6-bit palette -> 8-bit */
            r = s->buf[cpl0_chunk++] * 4;
            g = s->buf[cpl0_chunk++] * 4;
            b = s->buf[cpl0_chunk++] * 4;
            s->palette[i] = (r << 16) | (g << 8) | (b);
        }
    }

    /* next, look for a full codebook */
    if ((cbf0_chunk != -1) && (cbfz_chunk != -1)) {

        /* a chunk should not have both chunk types */
        av_log(s->avctx, AV_LOG_ERROR, "  VQA video: problem: found both CBF0 and CBFZ chunks\n");
        return;
    }

    /* decompress the full codebook chunk */
    if (cbfz_chunk != -1) {

        chunk_size = BE_32(&s->buf[cbfz_chunk + 4]);
        cbfz_chunk += CHUNK_PREAMBLE_SIZE;
        decode_format80(&s->buf[cbfz_chunk], chunk_size,
            s->codebook, s->codebook_size, 0);
    }

    /* copy a full codebook */
    if (cbf0_chunk != -1) {

        chunk_size = BE_32(&s->buf[cbf0_chunk + 4]);
        /* sanity check the full codebook size */
        if (chunk_size > MAX_CODEBOOK_SIZE) {
            av_log(s->avctx, AV_LOG_ERROR, "  VQA video: problem: CBF0 chunk too large (0x%X bytes)\n",
                chunk_size);
            return;
        }
        cbf0_chunk += CHUNK_PREAMBLE_SIZE;

        memcpy(s->codebook, &s->buf[cbf0_chunk], chunk_size);
    }

    /* decode the frame */
    if (vptz_chunk == -1) {

        /* something is wrong if there is no VPTZ chunk */
        av_log(s->avctx, AV_LOG_ERROR, "  VQA video: problem: no VPTZ chunk found\n");
        return;
    }

    chunk_size = BE_32(&s->buf[vptz_chunk + 4]);
    vptz_chunk += CHUNK_PREAMBLE_SIZE;
    decode_format80(&s->buf[vptz_chunk], chunk_size,
        s->decode_buffer, s->decode_buffer_size, 1);

    /* render the final PAL8 frame */
    if (s->vector_height == 4)
        index_shift = 4;
    else
        index_shift = 3;
    for (y = 0; y < s->frame.linesize[0] * s->height; 
        y += s->frame.linesize[0] * s->vector_height) {

        for (x = y; x < y + s->width; x += 4, lobytes++, hibytes++) {
            pixel_ptr = x;

            /* get the vector index, the method for which varies according to
             * VQA file version */
            switch (s->vqa_version) {

            case 1:
/* still need sample media for this case (only one game, "Legend of 
 * Kyrandia III : Malcolm's Revenge", is known to use this version) */
                lines = 0;
                break;

            case 2:
                lobyte = s->decode_buffer[lobytes];
                hibyte = s->decode_buffer[hibytes];
                vector_index = (hibyte << 8) | lobyte;
                vector_index <<= index_shift;
                lines = s->vector_height;
                break;

            case 3:
/* not implemented yet */
                lines = 0;
                break;
            }

            while (lines--) {
                s->frame.data[0][pixel_ptr + 0] = s->codebook[vector_index++];
                s->frame.data[0][pixel_ptr + 1] = s->codebook[vector_index++];
                s->frame.data[0][pixel_ptr + 2] = s->codebook[vector_index++];
                s->frame.data[0][pixel_ptr + 3] = s->codebook[vector_index++];
                pixel_ptr += s->frame.linesize[0];
            }
        }
    }

    /* handle partial codebook */
    if ((cbp0_chunk != -1) && (cbpz_chunk != -1)) {
        /* a chunk should not have both chunk types */
        av_log(s->avctx, AV_LOG_ERROR, "  VQA video: problem: found both CBP0 and CBPZ chunks\n");
        return;
    }

    if (cbp0_chunk != -1) {

        chunk_size = BE_32(&s->buf[cbp0_chunk + 4]);
        cbp0_chunk += CHUNK_PREAMBLE_SIZE;

        /* accumulate partial codebook */
        memcpy(&s->next_codebook_buffer[s->next_codebook_buffer_index],
            &s->buf[cbp0_chunk], chunk_size);
        s->next_codebook_buffer_index += chunk_size;

        s->partial_countdown--;
        if (s->partial_countdown == 0) {

            /* time to replace codebook */
            memcpy(s->codebook, s->next_codebook_buffer, 
                s->next_codebook_buffer_index);

            /* reset accounting */
            s->next_codebook_buffer_index = 0;
            s->partial_countdown = s->partial_count;
        }
    }

    if (cbpz_chunk != -1) {

        chunk_size = BE_32(&s->buf[cbpz_chunk + 4]);
        cbpz_chunk += CHUNK_PREAMBLE_SIZE;

        /* accumulate partial codebook */
        memcpy(&s->next_codebook_buffer[s->next_codebook_buffer_index],
            &s->buf[cbpz_chunk], chunk_size);
        s->next_codebook_buffer_index += chunk_size;

        s->partial_countdown--;
        if (s->partial_countdown == 0) {

            /* decompress codebook */
            decode_format80(s->next_codebook_buffer, 
                s->next_codebook_buffer_index, 
                s->codebook, s->codebook_size, 0);

            /* reset accounting */
            s->next_codebook_buffer_index = 0;
            s->partial_countdown = s->partial_count;
        }
    }
}

static int vqa_decode_frame(AVCodecContext *avctx,
                            void *data, int *data_size,
                            uint8_t *buf, int buf_size)
{
    VqaContext *s = (VqaContext *)avctx->priv_data;

    s->buf = buf;
    s->size = buf_size;

    if (s->frame.data[0])
        avctx->release_buffer(avctx, &s->frame);

    if (avctx->get_buffer(avctx, &s->frame)) {
        av_log(s->avctx, AV_LOG_ERROR, "  VQA Video: get_buffer() failed\n");
        return -1;
    }

    vqa_decode_chunk(s);

    /* make the palette available on the way out */
    memcpy(s->frame.data[1], s->palette, PALETTE_COUNT * 4);
    s->frame.palette_has_changed = 1;

    *data_size = sizeof(AVFrame);
    *(AVFrame*)data = s->frame;

    /* report that the buffer was completely consumed */
    return buf_size;
}

static int vqa_decode_end(AVCodecContext *avctx)
{
    VqaContext *s = (VqaContext *)avctx->priv_data;

    av_free(s->codebook);
    av_free(s->next_codebook_buffer);
    av_free(s->decode_buffer);

    if (s->frame.data[0])
        avctx->release_buffer(avctx, &s->frame);

    return 0;
}

AVCodec vqa_decoder = {
    "vqavideo",
    CODEC_TYPE_VIDEO,
    CODEC_ID_WS_VQA,
    sizeof(VqaContext),
    vqa_decode_init,
    NULL,
    vqa_decode_end,
    vqa_decode_frame,
    CODEC_CAP_DR1,
};