LCOV - code coverage report
Current view: top level - libavcodec - idcinvideo.c (source / functions) Hit Total Coverage
Test: coverage.info Lines: 80 87 92.0 %
Date: 2017-12-17 04:34:43 Functions: 5 5 100.0 %

          Line data    Source code
       1             : /*
       2             :  * id Quake II CIN Video Decoder
       3             :  * Copyright (C) 2003 The FFmpeg project
       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             :  * id Quake II Cin Video Decoder by Dr. Tim Ferguson
      25             :  * For more information about the id CIN format, visit:
      26             :  *   http://www.csse.monash.edu.au/~timf/
      27             :  *
      28             :  * This video decoder outputs PAL8 colorspace data. Interacting with this
      29             :  * decoder is a little involved. During initialization, the demuxer must
      30             :  * transmit the 65536-byte Huffman table(s) to the decoder via extradata.
      31             :  * Then, whenever a palette change is encountered while demuxing the file,
      32             :  * the demuxer must use the same extradata space to transmit an
      33             :  * AVPaletteControl structure.
      34             :  *
      35             :  * id CIN video is purely Huffman-coded, intraframe-only codec. It achieves
      36             :  * a little more compression by exploiting the fact that adjacent pixels
      37             :  * tend to be similar.
      38             :  *
      39             :  * Note that this decoder could use libavcodec's optimized VLC facilities
      40             :  * rather than naive, tree-based Huffman decoding. However, there are 256
      41             :  * Huffman tables. Plus, the VLC bit coding order is right -> left instead
      42             :  * or left -> right, so all of the bits would have to be reversed. Further,
      43             :  * the original Quake II implementation likely used a similar naive
      44             :  * decoding algorithm and it worked fine on much lower spec machines.
      45             :  */
      46             : 
      47             : #include <stdio.h>
      48             : #include <stdlib.h>
      49             : #include <string.h>
      50             : 
      51             : #include "avcodec.h"
      52             : #include "internal.h"
      53             : #include "libavutil/internal.h"
      54             : 
      55             : #define HUFFMAN_TABLE_SIZE 64 * 1024
      56             : #define HUF_TOKENS 256
      57             : #define PALETTE_COUNT 256
      58             : 
      59             : typedef struct hnode {
      60             :   int count;
      61             :   unsigned char used;
      62             :   int children[2];
      63             : } hnode;
      64             : 
      65             : typedef struct IdcinContext {
      66             : 
      67             :     AVCodecContext *avctx;
      68             : 
      69             :     const unsigned char *buf;
      70             :     int size;
      71             : 
      72             :     hnode huff_nodes[256][HUF_TOKENS*2];
      73             :     int num_huff_nodes[256];
      74             : 
      75             :     uint32_t pal[256];
      76             : } IdcinContext;
      77             : 
      78             : /**
      79             :  * Find the lowest probability node in a Huffman table, and mark it as
      80             :  * being assigned to a higher probability.
      81             :  * @return the node index of the lowest unused node, or -1 if all nodes
      82             :  * are used.
      83             :  */
      84       36984 : static int huff_smallest_node(hnode *hnodes, int num_hnodes) {
      85             :     int i;
      86             :     int best, best_node;
      87             : 
      88       36984 :     best = 99999999;
      89       36984 :     best_node = -1;
      90    10824952 :     for(i = 0; i < num_hnodes; i++) {
      91    10787968 :         if(hnodes[i].used)
      92     2658518 :             continue;
      93     8129450 :         if(!hnodes[i].count)
      94     6790996 :             continue;
      95     1338454 :         if(hnodes[i].count < best) {
      96      132488 :             best = hnodes[i].count;
      97      132488 :             best_node = i;
      98             :         }
      99             :     }
     100             : 
     101       36984 :     if(best_node == -1)
     102         512 :         return -1;
     103       36472 :     hnodes[best_node].used = 1;
     104       36472 :     return best_node;
     105             : }
     106             : 
     107             : /*
     108             :  * Build the Huffman tree using the generated/loaded probabilities histogram.
     109             :  *
     110             :  * On completion:
     111             :  *  huff_nodes[prev][i < HUF_TOKENS] - are the nodes at the base of the tree.
     112             :  *  huff_nodes[prev][i >= HUF_TOKENS] - are used to construct the tree.
     113             :  *  num_huff_nodes[prev] - contains the index to the root node of the tree.
     114             :  *    That is: huff_nodes[prev][num_huff_nodes[prev]] is the root node.
     115             :  */
     116         512 : static av_cold void huff_build_tree(IdcinContext *s, int prev) {
     117             :     hnode *node, *hnodes;
     118             :      int num_hnodes, i;
     119             : 
     120         512 :     num_hnodes = HUF_TOKENS;
     121         512 :     hnodes = s->huff_nodes[prev];
     122      262656 :     for(i = 0; i < HUF_TOKENS * 2; i++)
     123      262144 :         hnodes[i].used = 0;
     124             : 
     125             :     while (1) {
     126       36676 :         node = &hnodes[num_hnodes];             /* next free node */
     127             : 
     128             :         /* pick two lowest counts */
     129       18594 :         node->children[0] = huff_smallest_node(hnodes, num_hnodes);
     130       18594 :         if(node->children[0] == -1)
     131         204 :             break;      /* reached the root node */
     132             : 
     133       18390 :         node->children[1] = huff_smallest_node(hnodes, num_hnodes);
     134       18390 :         if(node->children[1] == -1)
     135         308 :             break;      /* reached the root node */
     136             : 
     137             :         /* combine nodes probability for new node */
     138       36164 :         node->count = hnodes[node->children[0]].count +
     139       18082 :         hnodes[node->children[1]].count;
     140       18082 :         num_hnodes++;
     141             :     }
     142             : 
     143         512 :     s->num_huff_nodes[prev] = num_hnodes - 1;
     144         512 : }
     145             : 
     146           2 : static av_cold int idcin_decode_init(AVCodecContext *avctx)
     147             : {
     148           2 :     IdcinContext *s = avctx->priv_data;
     149           2 :     int i, j, histogram_index = 0;
     150             :     unsigned char *histograms;
     151             : 
     152           2 :     s->avctx = avctx;
     153           2 :     avctx->pix_fmt = AV_PIX_FMT_PAL8;
     154             : 
     155             :     /* make sure the Huffman tables make it */
     156           2 :     if (s->avctx->extradata_size != HUFFMAN_TABLE_SIZE) {
     157           0 :         av_log(s->avctx, AV_LOG_ERROR, "  id CIN video: expected extradata size of %d\n", HUFFMAN_TABLE_SIZE);
     158           0 :         return -1;
     159             :     }
     160             : 
     161             :     /* build the 256 Huffman decode trees */
     162           2 :     histograms = (unsigned char *)s->avctx->extradata;
     163         514 :     for (i = 0; i < 256; i++) {
     164      131584 :         for(j = 0; j < HUF_TOKENS; j++)
     165      131072 :             s->huff_nodes[i][j].count = histograms[histogram_index++];
     166         512 :         huff_build_tree(s, i);
     167             :     }
     168             : 
     169           2 :     return 0;
     170             : }
     171             : 
     172          52 : static int idcin_decode_vlcs(IdcinContext *s, AVFrame *frame)
     173             : {
     174             :     hnode *hnodes;
     175             :     long x, y;
     176             :     int prev;
     177          52 :     unsigned char v = 0;
     178             :     int bit_pos, node_num, dat_pos;
     179             : 
     180          52 :     prev = bit_pos = dat_pos = 0;
     181       12584 :     for (y = 0; y < (frame->linesize[0] * s->avctx->height);
     182       12480 :         y += frame->linesize[0]) {
     183     4006080 :         for (x = y; x < y + s->avctx->width; x++) {
     184     3993600 :             node_num = s->num_huff_nodes[prev];
     185     3993600 :             hnodes = s->huff_nodes[prev];
     186             : 
     187    21451408 :             while(node_num >= HUF_TOKENS) {
     188    13464208 :                 if(!bit_pos) {
     189     1683045 :                     if(dat_pos >= s->size) {
     190           0 :                         av_log(s->avctx, AV_LOG_ERROR, "Huffman decode error.\n");
     191           0 :                         return -1;
     192             :                     }
     193     1683045 :                     bit_pos = 8;
     194     1683045 :                     v = s->buf[dat_pos++];
     195             :                 }
     196             : 
     197    13464208 :                 node_num = hnodes[node_num].children[v & 0x01];
     198    13464208 :                 v = v >> 1;
     199    13464208 :                 bit_pos--;
     200             :             }
     201             : 
     202     3993600 :             frame->data[0][x] = node_num;
     203     3993600 :             prev = node_num;
     204             :         }
     205             :     }
     206             : 
     207          52 :     return 0;
     208             : }
     209             : 
     210          52 : static int idcin_decode_frame(AVCodecContext *avctx,
     211             :                               void *data, int *got_frame,
     212             :                               AVPacket *avpkt)
     213             : {
     214          52 :     const uint8_t *buf = avpkt->data;
     215          52 :     int buf_size = avpkt->size;
     216          52 :     IdcinContext *s = avctx->priv_data;
     217             :     int pal_size;
     218          52 :     const uint8_t *pal = av_packet_get_side_data(avpkt, AV_PKT_DATA_PALETTE, &pal_size);
     219          52 :     AVFrame *frame = data;
     220             :     int ret;
     221             : 
     222          52 :     s->buf = buf;
     223          52 :     s->size = buf_size;
     224             : 
     225          52 :     if ((ret = ff_get_buffer(avctx, frame, 0)) < 0)
     226           0 :         return ret;
     227             : 
     228          52 :     if (idcin_decode_vlcs(s, frame))
     229           0 :         return AVERROR_INVALIDDATA;
     230             : 
     231          52 :     if (pal && pal_size == AVPALETTE_SIZE) {
     232           1 :         frame->palette_has_changed = 1;
     233           1 :         memcpy(s->pal, pal, AVPALETTE_SIZE);
     234          51 :     } else if (pal) {
     235           0 :         av_log(avctx, AV_LOG_ERROR, "Palette size %d is wrong\n", pal_size);
     236             :     }
     237             :     /* make the palette available on the way out */
     238          52 :     memcpy(frame->data[1], s->pal, AVPALETTE_SIZE);
     239             : 
     240          52 :     *got_frame = 1;
     241             : 
     242             :     /* report that the buffer was completely consumed */
     243          52 :     return buf_size;
     244             : }
     245             : 
     246             : AVCodec ff_idcin_decoder = {
     247             :     .name           = "idcinvideo",
     248             :     .long_name      = NULL_IF_CONFIG_SMALL("id Quake II CIN video"),
     249             :     .type           = AVMEDIA_TYPE_VIDEO,
     250             :     .id             = AV_CODEC_ID_IDCIN,
     251             :     .priv_data_size = sizeof(IdcinContext),
     252             :     .init           = idcin_decode_init,
     253             :     .decode         = idcin_decode_frame,
     254             :     .capabilities   = AV_CODEC_CAP_DR1,
     255             : };

Generated by: LCOV version 1.13