PeerStreamer

/*

 * Copyright (C) 2003-2004 the ffmpeg project

 *

 * This file is part of FFmpeg.

 *

 * FFmpeg 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.1 of the License, or (at your option) any later version.

 *

 * FFmpeg 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 FFmpeg; if not, write to the Free Software

 * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA

 */

/**

 * @file vp3.c

 * On2 VP3 Video Decoder

 *

 * VP3 Video Decoder by Mike Melanson (mike at multimedia.cx)

 * For more information about the VP3 coding process, visit:

 *   http://multimedia.cx/

 *

 * Theora decoder by Alex Beregszaszi

 */

#include <stdio.h>

#include <stdlib.h>

#include <string.h>

#include <unistd.h>

#include "avcodec.h"

#include "dsputil.h"

#include "bitstream.h"

#include "vp3data.h"

#include "xiph.h"

#define FRAGMENT_PIXELS 8

/*

 * Debugging Variables

 *

 * Define one or more of the following compile-time variables to 1 to obtain

 * elaborate information about certain aspects of the decoding process.

 *

 * KEYFRAMES_ONLY: set this to 1 to only see keyframes (VP3 slideshow mode)

 * DEBUG_VP3: high-level decoding flow

 * DEBUG_INIT: initialization parameters

 * DEBUG_DEQUANTIZERS: display how the dequanization tables are built

 * DEBUG_BLOCK_CODING: unpacking the superblock/macroblock/fragment coding

 * DEBUG_MODES: unpacking the coding modes for individual fragments

 * DEBUG_VECTORS: display the motion vectors

 * DEBUG_TOKEN: display exhaustive information about each DCT token

 * DEBUG_VLC: display the VLCs as they are extracted from the stream

 * DEBUG_DC_PRED: display the process of reversing DC prediction

 * DEBUG_IDCT: show every detail of the IDCT process

 */

#define KEYFRAMES_ONLY 0

#define DEBUG_VP3 0

#define DEBUG_INIT 0

#define DEBUG_DEQUANTIZERS 0

#define DEBUG_BLOCK_CODING 0

#define DEBUG_MODES 0

#define DEBUG_VECTORS 0

#define DEBUG_TOKEN 0

#define DEBUG_VLC 0

#define DEBUG_DC_PRED 0

#define DEBUG_IDCT 0

#if DEBUG_VP3

#define debug_vp3(args...) av_log(NULL, AV_LOG_DEBUG, ## args)

#else

static inline void debug_vp3(const char *format, ...) { }

#endif

#if DEBUG_INIT

#define debug_init(args...) av_log(NULL, AV_LOG_DEBUG, ## args)

#else

static inline void debug_init(const char *format, ...) { }

#endif

#if DEBUG_DEQUANTIZERS

#define debug_dequantizers(args...) av_log(NULL, AV_LOG_DEBUG, ## args)

#else

static inline void debug_dequantizers(const char *format, ...) { }

#endif

#if DEBUG_BLOCK_CODING

#define debug_block_coding(args...) av_log(NULL, AV_LOG_DEBUG, ## args)

#else

static inline void debug_block_coding(const char *format, ...) { }

#endif

#if DEBUG_MODES

#define debug_modes(args...) av_log(NULL, AV_LOG_DEBUG, ## args)

#else

static inline void debug_modes(const char *format, ...) { }

#endif

#if DEBUG_VECTORS

#define debug_vectors(args...) av_log(NULL, AV_LOG_DEBUG, ## args)

#else

static inline void debug_vectors(const char *format, ...) { }

#endif

#if DEBUG_TOKEN

#define debug_token(args...) av_log(NULL, AV_LOG_DEBUG, ## args)

#else

static inline void debug_token(const char *format, ...) { }

#endif

#if DEBUG_VLC

#define debug_vlc(args...) av_log(NULL, AV_LOG_DEBUG, ## args)

#else

static inline void debug_vlc(const char *format, ...) { }

#endif

#if DEBUG_DC_PRED

#define debug_dc_pred(args...) av_log(NULL, AV_LOG_DEBUG, ## args)

#else

static inline void debug_dc_pred(const char *format, ...) { }

#endif

#if DEBUG_IDCT

#define debug_idct(args...) av_log(NULL, AV_LOG_DEBUG, ## args)

#else

static inline void debug_idct(const char *format, ...) { }

#endif

typedef struct Coeff {

    struct Coeff *next;

    DCTELEM coeff;

    uint8_t index;

} Coeff;

//FIXME split things out into their own arrays

typedef struct Vp3Fragment {

    Coeff *next_coeff;

    /* address of first pixel taking into account which plane the fragment

     * lives on as well as the plane stride */

    int first_pixel;

    /* this is the macroblock that the fragment belongs to */

    uint16_t macroblock;

    uint8_t coding_method;

    uint8_t coeff_count;

    int8_t motion_x;

    int8_t motion_y;

} Vp3Fragment;

#define SB_NOT_CODED        0

#define SB_PARTIALLY_CODED  1

#define SB_FULLY_CODED      2

#define MODE_INTER_NO_MV      0

#define MODE_INTRA            1

#define MODE_INTER_PLUS_MV    2

#define MODE_INTER_LAST_MV    3

#define MODE_INTER_PRIOR_LAST 4

#define MODE_USING_GOLDEN     5

#define MODE_GOLDEN_MV        6

#define MODE_INTER_FOURMV     7

#define CODING_MODE_COUNT     8

/* special internal mode */

#define MODE_COPY             8

/* There are 6 preset schemes, plus a free-form scheme */

static int ModeAlphabet[7][CODING_MODE_COUNT] =

{

    /* this is the custom scheme */

    { 0, 0, 0, 0, 0, 0, 0, 0 },

    /* scheme 1: Last motion vector dominates */

    {    MODE_INTER_LAST_MV,    MODE_INTER_PRIOR_LAST,

         MODE_INTER_PLUS_MV,    MODE_INTER_NO_MV,

         MODE_INTRA,            MODE_USING_GOLDEN,

         MODE_GOLDEN_MV,        MODE_INTER_FOURMV },

    /* scheme 2 */

    {    MODE_INTER_LAST_MV,    MODE_INTER_PRIOR_LAST,

         MODE_INTER_NO_MV,      MODE_INTER_PLUS_MV,

         MODE_INTRA,            MODE_USING_GOLDEN,

         MODE_GOLDEN_MV,        MODE_INTER_FOURMV },

    /* scheme 3 */

    {    MODE_INTER_LAST_MV,    MODE_INTER_PLUS_MV,

         MODE_INTER_PRIOR_LAST, MODE_INTER_NO_MV,

         MODE_INTRA,            MODE_USING_GOLDEN,

         MODE_GOLDEN_MV,        MODE_INTER_FOURMV },

    /* scheme 4 */

    {    MODE_INTER_LAST_MV,    MODE_INTER_PLUS_MV,

         MODE_INTER_NO_MV,      MODE_INTER_PRIOR_LAST,

         MODE_INTRA,            MODE_USING_GOLDEN,

         MODE_GOLDEN_MV,        MODE_INTER_FOURMV },

    /* scheme 5: No motion vector dominates */

    {    MODE_INTER_NO_MV,      MODE_INTER_LAST_MV,

         MODE_INTER_PRIOR_LAST, MODE_INTER_PLUS_MV,

         MODE_INTRA,            MODE_USING_GOLDEN,

         MODE_GOLDEN_MV,        MODE_INTER_FOURMV },

    /* scheme 6 */

    {    MODE_INTER_NO_MV,      MODE_USING_GOLDEN,

         MODE_INTER_LAST_MV,    MODE_INTER_PRIOR_LAST,

         MODE_INTER_PLUS_MV,    MODE_INTRA,

         MODE_GOLDEN_MV,        MODE_INTER_FOURMV },

};

#define MIN_DEQUANT_VAL 2

typedef struct Vp3DecodeContext {

    AVCodecContext *avctx;

    int theora, theora_tables;

    int version;

    int width, height;

    AVFrame golden_frame;

    AVFrame last_frame;

    AVFrame current_frame;

    int keyframe;

    DSPContext dsp;

    int flipped_image;

    int qis[3];

    int nqis;

    int quality_index;

    int last_quality_index;

    int superblock_count;

    int superblock_width;

    int superblock_height;

    int y_superblock_width;

    int y_superblock_height;

    int c_superblock_width;

    int c_superblock_height;

    int u_superblock_start;

    int v_superblock_start;

    unsigned char *superblock_coding;

    int macroblock_count;

    int macroblock_width;

    int macroblock_height;

    int fragment_count;

    int fragment_width;

    int fragment_height;

    Vp3Fragment *all_fragments;

    Coeff *coeffs;

    Coeff *next_coeff;

    int fragment_start[3];

    ScanTable scantable;

    /* tables */

    uint16_t coded_dc_scale_factor[64];

    uint32_t coded_ac_scale_factor[64];

    uint8_t base_matrix[384][64];

    uint8_t qr_count[2][3];

    uint8_t qr_size [2][3][64];

    uint16_t qr_base[2][3][64];

    /* this is a list of indices into the all_fragments array indicating

     * which of the fragments are coded */

    int *coded_fragment_list;

    int coded_fragment_list_index;

    int pixel_addresses_initialized;

    VLC dc_vlc[16];

    VLC ac_vlc_1[16];

    VLC ac_vlc_2[16];

    VLC ac_vlc_3[16];

    VLC ac_vlc_4[16];

    VLC superblock_run_length_vlc;

    VLC fragment_run_length_vlc;

    VLC mode_code_vlc;

    VLC motion_vector_vlc;

    /* these arrays need to be on 16-byte boundaries since SSE2 operations

     * index into them */

    DECLARE_ALIGNED_16(int16_t, qmat[2][4][64]);        //<qmat[is_inter][plane]

    /* This table contains superblock_count * 16 entries. Each set of 16

     * numbers corresponds to the fragment indices 0..15 of the superblock.

     * An entry will be -1 to indicate that no entry corresponds to that

     * index. */

    int *superblock_fragments;

    /* This table contains superblock_count * 4 entries. Each set of 4

     * numbers corresponds to the macroblock indices 0..3 of the superblock.

     * An entry will be -1 to indicate that no entry corresponds to that

     * index. */

    int *superblock_macroblocks;

    /* This table contains macroblock_count * 6 entries. Each set of 6

     * numbers corresponds to the fragment indices 0..5 which comprise

     * the macroblock (4 Y fragments and 2 C fragments). */

    int *macroblock_fragments;

    /* This is an array that indicates how a particular macroblock

     * is coded. */

    unsigned char *macroblock_coding;

    int first_coded_y_fragment;

    int first_coded_c_fragment;

    int last_coded_y_fragment;

    int last_coded_c_fragment;

    uint8_t edge_emu_buffer[9*2048]; //FIXME dynamic alloc

    int8_t qscale_table[2048]; //FIXME dynamic alloc (width+15)/16

    /* Huffman decode */

    int hti;

    unsigned int hbits;

    int entries;

    int huff_code_size;

    uint16_t huffman_table[80][32][2];

    uint32_t filter_limit_values[64];

    int bounding_values_array[256];

} Vp3DecodeContext;

/************************************************************************

 * VP3 specific functions

 ************************************************************************/

/*

 * This function sets up all of the various blocks mappings:

 * superblocks <-> fragments, macroblocks <-> fragments,

 * superblocks <-> macroblocks

 *

 * Returns 0 is successful; returns 1 if *anything* went wrong.

 */

static int init_block_mapping(Vp3DecodeContext *s)

{

    int i, j;

    signed int hilbert_walk_mb[4];

    int current_fragment = 0;

    int current_width = 0;

    int current_height = 0;

    int right_edge = 0;

    int bottom_edge = 0;

    int superblock_row_inc = 0;

    int *hilbert = NULL;

    int mapping_index = 0;

    int current_macroblock;

    int c_fragment;

    signed char travel_width[16] = {

         1,  1,  0, -1,

         0,  0,  1,  0,

         1,  0,  1,  0,

         0, -1,  0,  1

    };

    signed char travel_height[16] = {

         0,  0,  1,  0,

         1,  1,  0, -1,

         0,  1,  0, -1,

        -1,  0, -1,  0

    };

    signed char travel_width_mb[4] = {

         1,  0,  1,  0

    };

    signed char travel_height_mb[4] = {

         0,  1,  0, -1

    };

    debug_vp3("  vp3: initialize block mapping tables\n");

    hilbert_walk_mb[0] = 1;

    hilbert_walk_mb[1] = s->macroblock_width;

    hilbert_walk_mb[2] = 1;

    hilbert_walk_mb[3] = -s->macroblock_width;

    /* iterate through each superblock (all planes) and map the fragments */

    for (i = 0; i < s->superblock_count; i++) {

        debug_init("    superblock %d (u starts @ %d, v starts @ %d)\n",

            i, s->u_superblock_start, s->v_superblock_start);

        /* time to re-assign the limits? */

        if (i == 0) {

            /* start of Y superblocks */

            right_edge = s->fragment_width;

            bottom_edge = s->fragment_height;

            current_width = -1;

            current_height = 0;

            superblock_row_inc = 3 * s->fragment_width -

                (s->y_superblock_width * 4 - s->fragment_width);

            /* the first operation for this variable is to advance by 1 */

            current_fragment = -1;

        } else if (i == s->u_superblock_start) {

            /* start of U superblocks */

            right_edge = s->fragment_width / 2;

            bottom_edge = s->fragment_height / 2;

            current_width = -1;

            current_height = 0;

            superblock_row_inc = 3 * (s->fragment_width / 2) -

                (s->c_superblock_width * 4 - s->fragment_width / 2);

            /* the first operation for this variable is to advance by 1 */

            current_fragment = s->fragment_start[1] - 1;

        } else if (i == s->v_superblock_start) {

            /* start of V superblocks */

            right_edge = s->fragment_width / 2;

            bottom_edge = s->fragment_height / 2;

            current_width = -1;

            current_height = 0;

            superblock_row_inc = 3 * (s->fragment_width / 2) -

                (s->c_superblock_width * 4 - s->fragment_width / 2);

            /* the first operation for this variable is to advance by 1 */

            current_fragment = s->fragment_start[2] - 1;

        }

        if (current_width >= right_edge - 1) {

            /* reset width and move to next superblock row */

            current_width = -1;

            current_height += 4;

            /* fragment is now at the start of a new superblock row */

            current_fragment += superblock_row_inc;

        }

        /* iterate through all 16 fragments in a superblock */

        for (j = 0; j < 16; j++) {

            current_fragment += travel_width[j] + right_edge * travel_height[j];

            current_width += travel_width[j];

            current_height += travel_height[j];

            /* check if the fragment is in bounds */

            if ((current_width < right_edge) &&

                (current_height < bottom_edge)) {

                s->superblock_fragments[mapping_index] = current_fragment;

                debug_init("    mapping fragment %d to superblock %d, position %d (%d/%d x %d/%d)\n",

                    s->superblock_fragments[mapping_index], i, j,

                    current_width, right_edge, current_height, bottom_edge);

            } else {

                s->superblock_fragments[mapping_index] = -1;

                debug_init("    superblock %d, position %d has no fragment (%d/%d x %d/%d)\n",

                    i, j,

                    current_width, right_edge, current_height, bottom_edge);

            }

            mapping_index++;

        }

    }

    /* initialize the superblock <-> macroblock mapping; iterate through

     * all of the Y plane superblocks to build this mapping */

    right_edge = s->macroblock_width;

    bottom_edge = s->macroblock_height;

    current_width = -1;

    current_height = 0;

    superblock_row_inc = s->macroblock_width -

        (s->y_superblock_width * 2 - s->macroblock_width);

    hilbert = hilbert_walk_mb;

    mapping_index = 0;

    current_macroblock = -1;

    for (i = 0; i < s->u_superblock_start; i++) {

        if (current_width >= right_edge - 1) {

            /* reset width and move to next superblock row */

            current_width = -1;

            current_height += 2;

            /* macroblock is now at the start of a new superblock row */

            current_macroblock += superblock_row_inc;

        }

        /* iterate through each potential macroblock in the superblock */

        for (j = 0; j < 4; j++) {

            current_macroblock += hilbert_walk_mb[j];

            current_width += travel_width_mb[j];

            current_height += travel_height_mb[j];

            /* check if the macroblock is in bounds */

            if ((current_width < right_edge) &&

                (current_height < bottom_edge)) {

                s->superblock_macroblocks[mapping_index] = current_macroblock;

                debug_init("    mapping macroblock %d to superblock %d, position %d (%d/%d x %d/%d)\n",

                    s->superblock_macroblocks[mapping_index], i, j,

                    current_width, right_edge, current_height, bottom_edge);

            } else {

                s->superblock_macroblocks[mapping_index] = -1;

                debug_init("    superblock %d, position %d has no macroblock (%d/%d x %d/%d)\n",

                    i, j,

                    current_width, right_edge, current_height, bottom_edge);

            }

            mapping_index++;

        }

    }

    /* initialize the macroblock <-> fragment mapping */

    current_fragment = 0;

    current_macroblock = 0;

    mapping_index = 0;

    for (i = 0; i < s->fragment_height; i += 2) {

        for (j = 0; j < s->fragment_width; j += 2) {

            debug_init("    macroblock %d contains fragments: ", current_macroblock);

            s->all_fragments[current_fragment].macroblock = current_macroblock;

            s->macroblock_fragments[mapping_index++] = current_fragment;

            debug_init("%d ", current_fragment);

            if (j + 1 < s->fragment_width) {

                s->all_fragments[current_fragment + 1].macroblock = current_macroblock;

                s->macroblock_fragments[mapping_index++] = current_fragment + 1;

                debug_init("%d ", current_fragment + 1);

            } else

                s->macroblock_fragments[mapping_index++] = -1;

            if (i + 1 < s->fragment_height) {

                s->all_fragments[current_fragment + s->fragment_width].macroblock =

                    current_macroblock;

                s->macroblock_fragments[mapping_index++] =

                    current_fragment + s->fragment_width;

                debug_init("%d ", current_fragment + s->fragment_width);

            } else

                s->macroblock_fragments[mapping_index++] = -1;

            if ((j + 1 < s->fragment_width) && (i + 1 < s->fragment_height)) {

                s->all_fragments[current_fragment + s->fragment_width + 1].macroblock =

                    current_macroblock;

                s->macroblock_fragments[mapping_index++] =

                    current_fragment + s->fragment_width + 1;

                debug_init("%d ", current_fragment + s->fragment_width + 1);

            } else

                s->macroblock_fragments[mapping_index++] = -1;

            /* C planes */

            c_fragment = s->fragment_start[1] +

                (i * s->fragment_width / 4) + (j / 2);

            s->all_fragments[c_fragment].macroblock = s->macroblock_count;

            s->macroblock_fragments[mapping_index++] = c_fragment;

            debug_init("%d ", c_fragment);

            c_fragment = s->fragment_start[2] +

                (i * s->fragment_width / 4) + (j / 2);

            s->all_fragments[c_fragment].macroblock = s->macroblock_count;

            s->macroblock_fragments[mapping_index++] = c_fragment;

            debug_init("%d ", c_fragment);

            debug_init("\n");

            if (j + 2 <= s->fragment_width)

                current_fragment += 2;

            else

                current_fragment++;

            current_macroblock++;

        }

        current_fragment += s->fragment_width;

    }

    return 0;  /* successful path out */

}

/*

 * This function wipes out all of the fragment data.

 */

static void init_frame(Vp3DecodeContext *s, GetBitContext *gb)

{

    int i;

    /* zero out all of the fragment information */

    s->coded_fragment_list_index = 0;

    for (i = 0; i < s->fragment_count; i++) {

        s->all_fragments[i].coeff_count = 0;

        s->all_fragments[i].motion_x = 127;

        s->all_fragments[i].motion_y = 127;

        s->all_fragments[i].next_coeff= NULL;

        s->coeffs[i].index=

        s->coeffs[i].coeff=0;

        s->coeffs[i].next= NULL;

    }

}

/*

 * This function sets up the dequantization tables used for a particular

 * frame.

 */

static void init_dequantizer(Vp3DecodeContext *s)

{

    int ac_scale_factor = s->coded_ac_scale_factor[s->quality_index];

    int dc_scale_factor = s->coded_dc_scale_factor[s->quality_index];

    int i, plane, inter, qri, bmi, bmj, qistart;

    debug_vp3("  vp3: initializing dequantization tables\n");

    for(inter=0; inter<2; inter++){

        for(plane=0; plane<3; plane++){

            int sum=0;

            for(qri=0; qri<s->qr_count[inter][plane]; qri++){

                sum+= s->qr_size[inter][plane][qri];

                if(s->quality_index <= sum)

                    break;

            }

            qistart= sum - s->qr_size[inter][plane][qri];

            bmi= s->qr_base[inter][plane][qri  ];

            bmj= s->qr_base[inter][plane][qri+1];

            for(i=0; i<64; i++){

                int coeff= (  2*(sum    -s->quality_index)*s->base_matrix[bmi][i]

                            - 2*(qistart-s->quality_index)*s->base_matrix[bmj][i]

                            + s->qr_size[inter][plane][qri])

                           / (2*s->qr_size[inter][plane][qri]);

                int qmin= 8<<(inter + !i);

                int qscale= i ? ac_scale_factor : dc_scale_factor;

                s->qmat[inter][plane][i]= av_clip((qscale * coeff)/100 * 4, qmin, 4096);

            }

        }

    }

    memset(s->qscale_table, (FFMAX(s->qmat[0][0][1], s->qmat[0][1][1])+8)/16, 512); //FIXME finetune

}

/*

 * This function initializes the loop filter boundary limits if the frame's

 * quality index is different from the previous frame's.

 */

static void init_loop_filter(Vp3DecodeContext *s)

{

    int *bounding_values= s->bounding_values_array+127;

    int filter_limit;

    int x;

    filter_limit = s->filter_limit_values[s->quality_index];

    /* set up the bounding values */

    memset(s->bounding_values_array, 0, 256 * sizeof(int));

    for (x = 0; x < filter_limit; x++) {

        bounding_values[-x - filter_limit] = -filter_limit + x;

        bounding_values[-x] = -x;

        bounding_values[x] = x;

        bounding_values[x + filter_limit] = filter_limit - x;

    }

}

/*

 * This function unpacks all of the superblock/macroblock/fragment coding

 * information from the bitstream.

 */

static int unpack_superblocks(Vp3DecodeContext *s, GetBitContext *gb)

{

    int bit = 0;

    int current_superblock = 0;

    int current_run = 0;

    int decode_fully_flags = 0;

    int decode_partial_blocks = 0;

    int first_c_fragment_seen;

    int i, j;

    int current_fragment;

    debug_vp3("  vp3: unpacking superblock coding\n");

    if (s->keyframe) {

        debug_vp3("    keyframe-- all superblocks are fully coded\n");

        memset(s->superblock_coding, SB_FULLY_CODED, s->superblock_count);

    } else {

        /* unpack the list of partially-coded superblocks */

        bit = get_bits1(gb);

        /* toggle the bit because as soon as the first run length is

         * fetched the bit will be toggled again */

        bit ^= 1;

        while (current_superblock < s->superblock_count) {

            if (current_run-- == 0) {

                bit ^= 1;

                current_run = get_vlc2(gb,

                    s->superblock_run_length_vlc.table, 6, 2);

                if (current_run == 33)

                    current_run += get_bits(gb, 12);

                debug_block_coding("      setting superblocks %d..%d to %s\n",

                    current_superblock,

                    current_superblock + current_run - 1,

                    (bit) ? "partially coded" : "not coded");

                /* if any of the superblocks are not partially coded, flag

                 * a boolean to decode the list of fully-coded superblocks */

                if (bit == 0) {

                    decode_fully_flags = 1;

                } else {

                    /* make a note of the fact that there are partially coded

                     * superblocks */

                    decode_partial_blocks = 1;

                }

            }

            s->superblock_coding[current_superblock++] = bit;

        }

        /* unpack the list of fully coded superblocks if any of the blocks were

         * not marked as partially coded in the previous step */

        if (decode_fully_flags) {

            current_superblock = 0;

            current_run = 0;

            bit = get_bits1(gb);

            /* toggle the bit because as soon as the first run length is

             * fetched the bit will be toggled again */

            bit ^= 1;

            while (current_superblock < s->superblock_count) {

                /* skip any superblocks already marked as partially coded */

                if (s->superblock_coding[current_superblock] == SB_NOT_CODED) {

                    if (current_run-- == 0) {

                        bit ^= 1;

                        current_run = get_vlc2(gb,

                            s->superblock_run_length_vlc.table, 6, 2);

                        if (current_run == 33)

                            current_run += get_bits(gb, 12);

                    }

                    debug_block_coding("      setting superblock %d to %s\n",

                        current_superblock,

                        (bit) ? "fully coded" : "not coded");

                    s->superblock_coding[current_superblock] = 2*bit;

                }

                current_superblock++;

            }

        }

        /* if there were partial blocks, initialize bitstream for

         * unpacking fragment codings */

        if (decode_partial_blocks) {

            current_run = 0;

            bit = get_bits1(gb);

            /* toggle the bit because as soon as the first run length is

             * fetched the bit will be toggled again */

            bit ^= 1;

        }

    }

    /* figure out which fragments are coded; iterate through each

     * superblock (all planes) */

    s->coded_fragment_list_index = 0;

    s->next_coeff= s->coeffs + s->fragment_count;

    s->first_coded_y_fragment = s->first_coded_c_fragment = 0;

    s->last_coded_y_fragment = s->last_coded_c_fragment = -1;

    first_c_fragment_seen = 0;

    memset(s->macroblock_coding, MODE_COPY, s->macroblock_count);

    for (i = 0; i < s->superblock_count; i++) {

        /* iterate through all 16 fragments in a superblock */

        for (j = 0; j < 16; j++) {

            /* if the fragment is in bounds, check its coding status */

            current_fragment = s->superblock_fragments[i * 16 + j];

            if (current_fragment >= s->fragment_count) {

                av_log(s->avctx, AV_LOG_ERROR, "  vp3:unpack_superblocks(): bad fragment number (%d >= %d)\n",

                    current_fragment, s->fragment_count);

                return 1;

            }

            if (current_fragment != -1) {

                if (s->superblock_coding[i] == SB_NOT_CODED) {

                    /* copy all the fragments from the prior frame */

                    s->all_fragments[current_fragment].coding_method =

                        MODE_COPY;

                } else if (s->superblock_coding[i] == SB_PARTIALLY_CODED) {

                    /* fragment may or may not be coded; this is the case

                     * that cares about the fragment coding runs */

                    if (current_run-- == 0) {

                        bit ^= 1;

                        current_run = get_vlc2(gb,

                            s->fragment_run_length_vlc.table, 5, 2);

                    }

                    if (bit) {

                        /* default mode; actual mode will be decoded in

                         * the next phase */

                        s->all_fragments[current_fragment].coding_method =

                            MODE_INTER_NO_MV;

                        s->all_fragments[current_fragment].next_coeff= s->coeffs + current_fragment;

                        s->coded_fragment_list[s->coded_fragment_list_index] =

                            current_fragment;

                        if ((current_fragment >= s->fragment_start[1]) &&

                            (s->last_coded_y_fragment == -1) &&

                            (!first_c_fragment_seen)) {

                            s->first_coded_c_fragment = s->coded_fragment_list_index;

                            s->last_coded_y_fragment = s->first_coded_c_fragment - 1;

                            first_c_fragment_seen = 1;

                        }

                        s->coded_fragment_list_index++;

                        s->macroblock_coding[s->all_fragments[current_fragment].macroblock] = MODE_INTER_NO_MV;

                        debug_block_coding("      superblock %d is partially coded, fragment %d is coded\n",

                            i, current_fragment);

                    } else {

                        /* not coded; copy this fragment from the prior frame */

                        s->all_fragments[current_fragment].coding_method =

                            MODE_COPY;

                        debug_block_coding("      superblock %d is partially coded, fragment %d is not coded\n",

                            i, current_fragment);

                    }

                } else {

                    /* fragments are fully coded in this superblock; actual

                     * coding will be determined in next step */

                    s->all_fragments[current_fragment].coding_method =

                        MODE_INTER_NO_MV;

                    s->all_fragments[current_fragment].next_coeff= s->coeffs + current_fragment;

                    s->coded_fragment_list[s->coded_fragment_list_index] =

                        current_fragment;

                    if ((current_fragment >= s->fragment_start[1]) &&

                        (s->last_coded_y_fragment == -1) &&

                        (!first_c_fragment_seen)) {

                        s->first_coded_c_fragment = s->coded_fragment_list_index;

                        s->last_coded_y_fragment = s->first_coded_c_fragment - 1;

                        first_c_fragment_seen = 1;

                    }

                    s->coded_fragment_list_index++;

                    s->macroblock_coding[s->all_fragments[current_fragment].macroblock] = MODE_INTER_NO_MV;

                    debug_block_coding("      superblock %d is fully coded, fragment %d is coded\n",

                        i, current_fragment);

                }

            }

        }

    }

    if (!first_c_fragment_seen)

        /* only Y fragments coded in this frame */

        s->last_coded_y_fragment = s->coded_fragment_list_index - 1;

    else

        /* end the list of coded C fragments */

        s->last_coded_c_fragment = s->coded_fragment_list_index - 1;

    debug_block_coding("    %d total coded fragments, y: %d -> %d, c: %d -> %d\n",

        s->coded_fragment_list_index,

        s->first_coded_y_fragment,

        s->last_coded_y_fragment,

        s->first_coded_c_fragment,

        s->last_coded_c_fragment);

    return 0;

}

/*

 * This function unpacks all the coding mode data for individual macroblocks

 * from the bitstream.

 */

static int unpack_modes(Vp3DecodeContext *s, GetBitContext *gb)

{

    int i, j, k;

    int scheme;

    int current_macroblock;

    int current_fragment;

    int coding_mode;

    debug_vp3("  vp3: unpacking encoding modes\n");

    if (s->keyframe) {

        debug_vp3("    keyframe-- all blocks are coded as INTRA\n");

        for (i = 0; i < s->fragment_count; i++)

            s->all_fragments[i].coding_method = MODE_INTRA;

    } else {

        /* fetch the mode coding scheme for this frame */

        scheme = get_bits(gb, 3);

        debug_modes("    using mode alphabet %d\n", scheme);

        /* is it a custom coding scheme? */

        if (scheme == 0) {

            debug_modes("    custom mode alphabet ahead:\n");

            for (i = 0; i < 8; i++)

                ModeAlphabet[scheme][get_bits(gb, 3)] = i;

        }

        for (i = 0; i < 8; i++)

            debug_modes("      mode[%d][%d] = %d\n", scheme, i,

                ModeAlphabet[scheme][i]);

        /* iterate through all of the macroblocks that contain 1 or more

         * coded fragments */

        for (i = 0; i < s->u_superblock_start; i++) {

            for (j = 0; j < 4; j++) {

                current_macroblock = s->superblock_macroblocks[i * 4 + j];

                if ((current_macroblock == -1) ||

                    (s->macroblock_coding[current_macroblock] == MODE_COPY))

                    continue;

                if (current_macroblock >= s->macroblock_count) {

                    av_log(s->avctx, AV_LOG_ERROR, "  vp3:unpack_modes(): bad macroblock number (%d >= %d)\n",

                        current_macroblock, s->macroblock_count);

                    return 1;

                }

                /* mode 7 means get 3 bits for each coding mode */

                if (scheme == 7)

                    coding_mode = get_bits(gb, 3);

                else

                    coding_mode = ModeAlphabet[scheme]

                        [get_vlc2(gb, s->mode_code_vlc.table, 3, 3)];

                s->macroblock_coding[current_macroblock] = coding_mode;

                for (k = 0; k < 6; k++) {

                    current_fragment =

                        s->macroblock_fragments[current_macroblock * 6 + k];

                    if (current_fragment == -1)

                        continue;

                    if (current_fragment >= s->fragment_count) {

                        av_log(s->avctx, AV_LOG_ERROR, "  vp3:unpack_modes(): bad fragment number (%d >= %d)\n",

                            current_fragment, s->fragment_count);

                        return 1;

                    }

                    if (s->all_fragments[current_fragment].coding_method !=

                        MODE_COPY)

                        s->all_fragments[current_fragment].coding_method =

                            coding_mode;

                }

                debug_modes("    coding method for macroblock starting @ fragment %d = %d\n",

                    s->macroblock_fragments[current_macroblock * 6], coding_mode);

            }

        }

    }

    return 0;

}

/*

 * This function unpacks all the motion vectors for the individual

 * macroblocks from the bitstream.

 */

static int unpack_vectors(Vp3DecodeContext *s, GetBitContext *gb)

{

    int i, j, k;

    int coding_mode;

    int motion_x[6];

    int motion_y[6];

    int last_motion_x = 0;

    int last_motion_y = 0;

    int prior_last_motion_x = 0;

    int prior_last_motion_y = 0;

    int current_macroblock;

    int current_fragment;

    debug_vp3("  vp3: unpacking motion vectors\n");

    if (s->keyframe) {

        debug_vp3("    keyframe-- there are no motion vectors\n");

    } else {

        memset(motion_x, 0, 6 * sizeof(int));

        memset(motion_y, 0, 6 * sizeof(int));

        /* coding mode 0 is the VLC scheme; 1 is the fixed code scheme */

        coding_mode = get_bits1(gb);

        debug_vectors("    using %s scheme for unpacking motion vectors\n",

            (coding_mode == 0) ? "VLC" : "fixed-length");

        /* iterate through all of the macroblocks that contain 1 or more

         * coded fragments */

        for (i = 0; i < s->u_superblock_start; i++) {

            for (j = 0; j < 4; j++) {

                current_macroblock = s->superblock_macroblocks[i * 4 + j];

                if ((current_macroblock == -1) ||

                    (s->macroblock_coding[current_macroblock] == MODE_COPY))

                    continue;

                if (current_macroblock >= s->macroblock_count) {

                    av_log(s->avctx, AV_LOG_ERROR, "  vp3:unpack_vectors(): bad macroblock number (%d >= %d)\n",

                        current_macroblock, s->macroblock_count);

                    return 1;

                }

                current_fragment = s->macroblock_fragments[current_macroblock * 6];

                if (current_fragment >= s->fragment_count) {

                    av_log(s->avctx, AV_LOG_ERROR, "  vp3:unpack_vectors(): bad fragment number (%d >= %d\n",

                        current_fragment, s->fragment_count);

                    return 1;

                }

                switch (s->macroblock_coding[current_macroblock]) {

                case MODE_INTER_PLUS_MV:

                case MODE_GOLDEN_MV:

                    /* all 6 fragments use the same motion vector */

                    if (coding_mode == 0) {

                        motion_x[0] = motion_vector_table[get_vlc2(gb, s->motion_vector_vlc.table, 6, 2)];

                        motion_y[0] = motion_vector_table[get_vlc2(gb, s->motion_vector_vlc.table, 6, 2)];

                    } else {

                        motion_x[0] = fixed_motion_vector_table[get_bits(gb, 6)];

                        motion_y[0] = fixed_motion_vector_table[get_bits(gb, 6)];

                    }

                    for (k = 1; k < 6; k++) {

                        motion_x[k] = motion_x[0];

                        motion_y[k] = motion_y[0];

                    }

                    /* vector maintenance, only on MODE_INTER_PLUS_MV */

                    if (s->macroblock_coding[current_macroblock] ==

                        MODE_INTER_PLUS_MV) {

                        prior_last_motion_x = last_motion_x;

                        prior_last_motion_y = last_motion_y;

                        last_motion_x = motion_x[0];

                        last_motion_y = motion_y[0];

                    }

                    break;

                case MODE_INTER_FOURMV:

                    /* fetch 4 vectors from the bitstream, one for each

                     * Y fragment, then average for the C fragment vectors */

                    motion_x[4] = motion_y[4] = 0;

                    for (k = 0; k < 4; k++) {

                        if (coding_mode == 0) {

                            motion_x[k] = motion_vector_table[get_vlc2(gb, s->motion_vector_vlc.table, 6, 2)];

                            motion_y[k] = motion_vector_table[get_vlc2(gb, s->motion_vector_vlc.table, 6, 2)];

                        } else {

                            motion_x[k] = fixed_motion_vector_table[get_bits(gb, 6)];

                            motion_y[k] = fixed_motion_vector_table[get_bits(gb, 6)];

                        }

                        motion_x[4] += motion_x[k];

                        motion_y[4] += motion_y[k];

                    }

                    motion_x[5]=

                    motion_x[4]= RSHIFT(motion_x[4], 2);

                    motion_y[5]=

                    motion_y[4]= RSHIFT(motion_y[4], 2);

                    /* vector maintenance; vector[3] is treated as the

                     * last vector in this case */

                    prior_last_motion_x = last_motion_x;

                    prior_last_motion_y = last_motion_y;

                    last_motion_x = motion_x[3];

                    last_motion_y = motion_y[3];

                    break;

                case MODE_INTER_LAST_MV:

                    /* all 6 fragments use the last motion vector */

                    motion_x[0] = last_motion_x;

                    motion_y[0] = last_motion_y;

                    for (k = 1; k < 6; k++) {

                        motion_x[k] = motion_x[0];

                        motion_y[k] = motion_y[0];

                    }

                    /* no vector maintenance (last vector remains the

                     * last vector) */

                    break;

                case MODE_INTER_PRIOR_LAST:

                    /* all 6 fragments use the motion vector prior to the

                     * last motion vector */

                    motion_x[0] = prior_last_motion_x;

                    motion_y[0] = prior_last_motion_y;

                    for (k = 1; k < 6; k++) {

                        motion_x[k] = motion_x[0];

                        motion_y[k] = motion_y[0];

                    }

                    /* vector maintenance */

                    prior_last_motion_x = last_motion_x;

                    prior_last_motion_y = last_motion_y;

                    last_motion_x = motion_x[0];

                    last_motion_y = motion_y[0];

                    break;

                default:

                    /* covers intra, inter without MV, golden without MV */

                    memset(motion_x, 0, 6 * sizeof(int));

                    memset(motion_y, 0, 6 * sizeof(int));

                    /* no vector maintenance */

                    break;

                }

                /* assign the motion vectors to the correct fragments */

                debug_vectors("    vectors for macroblock starting @ fragment %d (coding method %d):\n",

                    current_fragment,

                    s->macroblock_coding[current_macroblock]);

                for (k = 0; k < 6; k++) {

                    current_fragment =

                        s->macroblock_fragments[current_macroblock * 6 + k];

                    if (current_fragment == -1)

                        continue;

                    if (current_fragment >= s->fragment_count) {

                        av_log(s->avctx, AV_LOG_ERROR, "  vp3:unpack_vectors(): bad fragment number (%d >= %d)\n",

                            current_fragment, s->fragment_count);

                        return 1;

                    }

                    s->all_fragments[current_fragment].motion_x = motion_x[k];

                    s->all_fragments[current_fragment].motion_y = motion_y[k];

                    debug_vectors("    vector %d: fragment %d = (%d, %d)\n",

                        k, current_fragment, motion_x[k], motion_y[k]);

                }

            }

        }

    }

    return 0;

}

/*

 * This function is called by unpack_dct_coeffs() to extract the VLCs from

 * the bitstream. The VLCs encode tokens which are used to unpack DCT

 * data. This function unpacks all the VLCs for either the Y plane or both

 * C planes, and is called for DC coefficients or different AC coefficient

 * levels (since different coefficient types require different VLC tables.

 *

 * This function returns a residual eob run. E.g, if a particular token gave

 * instructions to EOB the next 5 fragments and there were only 2 fragments

 * left in the current fragment range, 3 would be returned so that it could

 * be passed into the next call to this same function.

 */

static int unpack_vlcs(Vp3DecodeContext *s, GetBitContext *gb,

                        VLC *table, int coeff_index,

                        int first_fragment, int last_fragment,

                        int eob_run)

{

    int i;

    int token;

    int zero_run = 0;

    DCTELEM coeff = 0;

    Vp3Fragment *fragment;

    uint8_t *perm= s->scantable.permutated;

    int bits_to_get;

    if ((first_fragment >= s->fragment_count) ||

        (last_fragment >= s->fragment_count)) {

        av_log(s->avctx, AV_LOG_ERROR, "  vp3:unpack_vlcs(): bad fragment number (%d -> %d ?)\n",

            first_fragment, last_fragment);

        return 0;

    }

    for (i = first_fragment; i <= last_fragment; i++) {

        fragment = &s->all_fragments[s->coded_fragment_list[i]];

        if (fragment->coeff_count > coeff_index)

            continue;

        if (!eob_run) {

            /* decode a VLC into a token */

            token = get_vlc2(gb, table->table, 5, 3);

            debug_vlc(" token = %2d, ", token);

            /* use the token to get a zero run, a coefficient, and an eob run */

            if (token <= 6) {

                eob_run = eob_run_base[token];

                if (eob_run_get_bits[token])

                    eob_run += get_bits(gb, eob_run_get_bits[token]);

                coeff = zero_run = 0;

            } else {

                bits_to_get = coeff_get_bits[token];

                if (!bits_to_get)

                    coeff = coeff_tables[token][0];

                else

                    coeff = coeff_tables[token][get_bits(gb, bits_to_get)];

                zero_run = zero_run_base[token];

                if (zero_run_get_bits[token])

                    zero_run += get_bits(gb, zero_run_get_bits[token]);

            }

        }

        if (!eob_run) {

            fragment->coeff_count += zero_run;

            if (fragment->coeff_count < 64){

                fragment->next_coeff->coeff= coeff;

                fragment->next_coeff->index= perm[fragment->coeff_count++]; //FIXME perm here already?

                fragment->next_coeff->next= s->next_coeff;

                s->next_coeff->next=NULL;

                fragment->next_coeff= s->next_coeff++;

            }

            debug_vlc(" fragment %d coeff = %d\n",

                s->coded_fragment_list[i], fragment->next_coeff[coeff_index]);

        } else {

            fragment->coeff_count |= 128;

            debug_vlc(" fragment %d eob with %d coefficients\n",

                s->coded_fragment_list[i], fragment->coeff_count&127);

            eob_run--;

        }

    }

    return eob_run;

}

/*

 * This function unpacks all of the DCT coefficient data from the

 * bitstream.

 */

static int unpack_dct_coeffs(Vp3DecodeContext *s, GetBitContext *gb)

{

    int i;

    int dc_y_table;

    int dc_c_table;

    int ac_y_table;

    int ac_c_table;

    int residual_eob_run = 0;

    /* fetch the DC table indices */

    dc_y_table = get_bits(gb, 4);

    dc_c_table = get_bits(gb, 4);

    /* unpack the Y plane DC coefficients */

    debug_vp3("  vp3: unpacking Y plane DC coefficients using table %d\n",

        dc_y_table);

    residual_eob_run = unpack_vlcs(s, gb, &s->dc_vlc[dc_y_table], 0,

        s->first_coded_y_fragment, s->last_coded_y_fragment, residual_eob_run);

    /* unpack the C plane DC coefficients */

    debug_vp3("  vp3: unpacking C plane DC coefficients using table %d\n",

        dc_c_table);

    residual_eob_run = unpack_vlcs(s, gb, &s->dc_vlc[dc_c_table], 0,

        s->first_coded_c_fragment, s->last_coded_c_fragment, residual_eob_run);

    /* fetch the AC table indices */

    ac_y_table = get_bits(gb, 4);

    ac_c_table = get_bits(gb, 4);

    /* unpack the group 1 AC coefficients (coeffs 1-5) */

    for (i = 1; i <= 5; i++) {

        debug_vp3("  vp3: unpacking level %d Y plane AC coefficients using table %d\n",

            i, ac_y_table);

        residual_eob_run = unpack_vlcs(s, gb, &s->ac_vlc_1[ac_y_table], i,

            s->first_coded_y_fragment, s->last_coded_y_fragment, residual_eob_run);

        debug_vp3("  vp3: unpacking level %d C plane AC coefficients using table %d\n",

            i, ac_c_table);

        residual_eob_run = unpack_vlcs(s, gb, &s->ac_vlc_1[ac_c_table], i,

            s->first_coded_c_fragment, s->last_coded_c_fragment, residual_eob_run);

    }

    /* unpack the group 2 AC coefficients (coeffs 6-14) */

    for (i = 6; i <= 14; i++) {

        debug_vp3("  vp3: unpacking level %d Y plane AC coefficients using table %d\n",

            i, ac_y_table);

        residual_eob_run = unpack_vlcs(s, gb, &s->ac_vlc_2[ac_y_table], i,

            s->first_coded_y_fragment, s->last_coded_y_fragment, residual_eob_run);

        debug_vp3("  vp3: unpacking level %d C plane AC coefficients using table %d\n",

            i, ac_c_table);

        residual_eob_run = unpack_vlcs(s, gb, &s->ac_vlc_2[ac_c_table], i,

            s->first_coded_c_fragment, s->last_coded_c_fragment, residual_eob_run);

    }

    /* unpack the group 3 AC coefficients (coeffs 15-27) */

    for (i = 15; i <= 27; i++) {

        debug_vp3("  vp3: unpacking level %d Y plane AC coefficients using table %d\n",

            i, ac_y_table);

        residual_eob_run = unpack_vlcs(s, gb, &s->ac_vlc_3[ac_y_table], i,

            s->first_coded_y_fragment, s->last_coded_y_fragment, residual_eob_run);

        debug_vp3("  vp3: unpacking level %d C plane AC coefficients using table %d\n",

            i, ac_c_table);

        residual_eob_run = unpack_vlcs(s, gb, &s->ac_vlc_3[ac_c_table], i,

            s->first_coded_c_fragment, s->last_coded_c_fragment, residual_eob_run);

    }

    /* unpack the group 4 AC coefficients (coeffs 28-63) */

    for (i = 28; i <= 63; i++) {

        debug_vp3("  vp3: unpacking level %d Y plane AC coefficients using table %d\n",

            i, ac_y_table);

        residual_eob_run = unpack_vlcs(s, gb, &s->ac_vlc_4[ac_y_table], i,

            s->first_coded_y_fragment, s->last_coded_y_fragment, residual_eob_run);

        debug_vp3("  vp3: unpacking level %d C plane AC coefficients using table %d\n",

            i, ac_c_table);

        residual_eob_run = unpack_vlcs(s, gb, &s->ac_vlc_4[ac_c_table], i,

            s->first_coded_c_fragment, s->last_coded_c_fragment, residual_eob_run);

    }

    return 0;

}

/*

 * This function reverses the DC prediction for each coded fragment in

 * the frame. Much of this function is adapted directly from the original