[Ffmpeg-devel] Reading bit-reversed VLC codes

Kostya kostya.shishkov
Mon Mar 19 05:20:06 CET 2007


On Sun, Mar 18, 2007 at 08:10:59PM +0000, M?ns Rullg?rd wrote:
[...]
> I'm trying to write a zlib decoder.  The spec is RFC1951.
> 
> > i thought that you wanted to reverse the output of get_vlc() not the
> > bits of the vlc codes as stored in the bitstream later wont work in
> > general example:
> 
> [...]
> 
> > init_vlc/get_vlc() doesnt support such non prefix codes (for obvious
> > reasons)
> 
> No, of course it doesn't.  Do you have any suggestion how to solve
> this?
> 
> -- 
> M?ns Rullg?rd
> mans at mansr.com

Look at indeo2.c as it's the first decoder used "reverse" codes.
I also tried to implement zlib but that is too tricky to do.
Here is my code to the point when I gave up. 
-------------- next part --------------
#include "avcodec.h"
#define ALT_BITSTREAM_READER_LE
#include "bitstream.h"
#include "ffzlib.h"

/**
 * @file ffzlib.c
 * @brief Zlib decoding routines
 * @author Konstantin Shishkov
 */

enum BTypes{
    FF_ZL_RAW = 0, ///< Block is not compressed
    FF_ZL_HUFF   , ///< Block uses static Huffman codes
    FF_ZL_DYNHUFF, ///< Block has own Huffman codes
};

#define CODE_CODES 20
#define LIT_CODES  287
#define DIST_CODES 33
/** Order in which code lengths are read */
static const uint8_t cl_order[CODE_CODES] = {
    16, 17, 18,  0,  8,  7,  9,  6, 10,  5, 11,  4, 12,  3, 13,  2, 14,  1, 15
};

/** additional bits to read if got match length */
static const uint8_t match_add_len[LIT_CODES-256] = {
    0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 2, 2, 2, 2, 3, 3, 3, 3, 4, 4, 4, 4, 5, 5, 5, 5, 0
};
/** match length offset */
static const uint16_t match_add_off[LIT_CODES-256] = {
    3, 4, 5, 6, 7, 8, 9, 10, 11, 13, 15, 17, 19, 23, 27, 31,
    35, 43, 51, 59, 67, 83, 99, 115, 131, 163, 195, 227, 258
};
/** pos additional bits */
static const uint8_t pos_add_len[30] = {
    0, 0, 0, 0, 1, 1, 2, 2, 3, 3, 4, 4, 5, 5, 6, 6, 7, 7, 8, 8, 9, 9, 10, 10, 11, 11, 12, 12, 13, 13
};
/** pos offsets */
static const uint16_t pos_add_off[30] = {
    1, 2, 3, 4, 5, 7, 9, 13, 17, 25, 33, 49, 65, 97, 129, 193, 257, 385, 513,
    769, 1025, 1537, 2049, 3073, 4097, 6145, 8193, 12289, 16385, 24577
};

/*
#define LIT_BITS 9
#define LIT_COUNT 2
static VLC static_lit;
#define DIST_BITS 9
#define DIST_COUNT 2
static VLC static_dist;
#define CODES_BITS 9
#define CODES_COUNT 2
static VLC static_codes;
*/

/** Structure which contains all data to decode VLC */
typedef struct ZVLC{
    int size;
    uint8_t *lengths;
    uint16_t *codes;
    uint16_t *recode;
    VLC vlc;
    int bits, rep;
}ZVLC;

static void create_zvlc(ZVLC *z){
    z->lengths = av_mallocz(z->size);
    z->codes = av_mallocz(z->size * 2);
    z->recode = av_mallocz(z->size * 2);
}

static void free_zvlc(ZVLC *z){
    av_freep(&z->lengths);
    av_freep(&z->codes);
    av_freep(&z->recode);
    if(z->vlc.table) free_vlc(&z->vlc);
}

/** Create VLC by given lengths */
static int construct_zvlc(ZVLC *z){
    int i;
    int starts[16], counts[16], start, mb = 0;

    memset(counts, 0, 16 * sizeof(int));

    for(i = 0; i < z->size; i++){
        counts[z->lengths[i]]++;
        mb = FFMAX(mb, z->lengths[i]);
    }

    start = 0;
    for(i = 1; i < 16; i++){
        start = (start + counts[i - 1]) << 1;
        starts[i] = start;
    }

    for(i = 0; i < z->size; i++){
        z->codes[i] = starts[z->lengths[i]]++;
        /* convert new code into LE format */
        z->codes[i] = (ff_reverse[z->codes[i] >> 8] | (ff_reverse[z->codes[i] & 0xFF] << 8)) >> (16 - z->lengths[i]);
    }

    if(mb <= 9){
        z->bits = mb;
        z->rep = 1;
    }else{
        z->bits = 9;
        z->rep = (mb + 8) / 9;
    }
    return init_vlc(&z->vlc, mb, z->size, z->lengths, 1, 1, z->codes, 2, 2, INIT_VLC_LE);
}


/**
 * Construct codes for dynamic Huffman compressed block
 */
static int construct_codes(ZVLC *dists, ZVLC *lengths, GetBitContext *gb, int hl, int hd, int hc)
{
    int i, t, n, rcd;
    ZVLC huff;

    huff.size = 20;
    create_zvlc(&huff);

    n = 0;
    for(i = 0; i < hc; i++){
        t = get_bits(gb, 3);
        if(t){
            huff.lengths[n] = t;
            huff.recode[n] = cl_order[i];
            n++;
        }
    }
    huff.size = n;
    if(construct_zvlc(&huff) < 0){
        av_log(NULL, 0, "Cannot construct HUFF\n");
        return -1;
    }

    n = 0; rcd = 0;
    for(i = 0; i < hl; i++, rcd++){
        t = get_vlc2(gb, huff.vlc.table, huff.bits, huff.rep);
        t = huff.recode[t];
        if(t < 16){
            lengths->lengths[n] = t;
            lengths->recode[n] = rcd;
            n++;
        }else{
            t -= 15;
            if(!t){
                t = 3 + get_bits(gb, 2);
                while(t-- && i < hl){
                    lengths->lengths[n] = lengths->lengths[n - 1];
                    lengths->recode[n] = rcd;
                    n++;
                    rcd++;
                    i++;
                }
                i--;
                rcd--;
            }else{
                t = 3 + ((t & 2) << 2) + get_bits(gb, 3 + ((t & 2) << 1));
                rcd += t - 1;
                i += t;
            }
        }
    }
    lengths->size = n;
    if(construct_zvlc(lengths) < 0){
        free_zvlc(&huff);
        av_log(NULL, 0, "Cannot construct LENGTH\n");
        return -1;
    }

    n = 0; rcd = 0;
    for(i = 0; i < hd; i++){
        t = get_vlc2(gb, huff.vlc.table, 9, 2);
        t = huff.recode[t];
        if(t < 16){
            dists->lengths[n] = t;
            dists->recode[n] = rcd;
            n++;
        }else{
            t -= 15;
            if(!t){
                t = 3 + get_bits(gb, 2);
                while(t-- && i < hd){
                    dists->lengths[n] = dists->lengths[n - 1];
                    dists->recode[n] = rcd;
                    n++;
                    rcd++;
                    i++;
                }
                i--;
                rcd--;
            }else{
                t = 3 + ((t & 2) << 2) + get_bits(gb, 3 + ((t & 2) << 1));
                rcd += t - 1;
                i += t;
            }
        }
    }
    dists->size = n;

    if(construct_zvlc(dists) < 0){
        free_zvlc(&huff);
        av_log(NULL, 0, "Cannot construct DIST\n");
        return -1;
    }

    free_zvlc(&huff);
    return 0;
}

/**
 * Decompress one block
 */
static inline int block_inflate(GetBitContext *gb, uint8_t *dst, int *last, int dsize)
{
    int type;
    int bsize = 0;
    int nlen;
    int i;
    int hlens, hdist, hbits;
    int lit,len,pos;
    ZVLC dists, lengths;

    *last = get_bits1(gb);
    type = get_bits(gb, 2);
    switch(type){
    case FF_ZL_RAW:
        align_get_bits(gb);
        bsize = get_bits(gb, 16);
        nlen = get_bits(gb, 16);
        av_log(NULL,AV_LOG_DEBUG,"Raw: Len = %i (%X/%X)\n",bsize,bsize,nlen);
        for(i = 0; i < bsize; i++)
            *dst++ = get_bits(gb, 8);
        break;
    case FF_ZL_DYNHUFF:
        hlens = get_bits(gb, 5) + 257;
        hdist = get_bits(gb, 5) + 1;
        hbits = get_bits(gb, 4) + 4;
        if(hlens >= LIT_CODES) return -1;
        av_log(NULL,AV_LOG_DEBUG,"Dynhuff: %i/%i/%i\n", hlens, hdist, hbits);

        dists.size = hdist;
        lengths.size = hlens;
        create_zvlc(&dists);
        create_zvlc(&lengths);
        if(construct_codes(&dists, &lengths, gb, hlens, hdist, hbits) < 0){
            av_log(NULL,0,"Error constructing codes\n");
            return 0;
        }
    case FF_ZL_HUFF:

        for(;bsize < dsize;){
            lit = get_vlc2(gb, lengths.vlc.table, 9, 2);
            lit = lengths.recode[lit];
            if(lit < 256){ // one symbol
                *dst++ = lit;
                bsize++;
            }else if(lit == 256){ //EOB
                break;
            }else{ //match length
                lit -= 257;
                len = match_add_off[lit] + (match_add_len[lit] ? get_bits(gb, match_add_len[lit]) : 0);
                pos = get_vlc2(gb, dists.vlc.table, 9, 2);
                pos = dists.recode[pos];
                pos = pos_add_off[pos] + (pos_add_len[pos] ? get_bits(gb, pos_add_len[pos]) : 0);
                memmove(dst, dst - pos, len);
            }
        }
        if(type == FF_ZL_DYNHUFF){
            free_zvlc(&dists);
            free_zvlc(&lengths);
        }
        break;
    default:
        return -1;
    }
    return bsize;
}

/**
 * Decompress one buffer
 * @return bytes consumed
 */
int ff_inflate(uint8_t* src, int ssize, uint8_t *dst, int *dsize)
{
    GetBitContext gb;
    int hdr, wbits, last;
    int size, ssz, sz;

    init_get_bits(&gb, src, ssize * 8);

    /* check header */
    hdr = get_bits(&gb, 8);
    if((hdr & 0xF) != 8)
        return FF_ZL_BADHDR;
    wbits = (hdr >> 4) + 8;
    if(wbits > 15)
        return FF_ZL_BADHDR;
    hdr = (hdr << 8) | get_bits(&gb, 8);
    if((hdr % 31) || (hdr & 0x0020))
        return FF_ZL_BADHDR;
    size = 0;
    ssz = *dsize;
    while(size < ssz){
        sz = block_inflate(&gb, dst, &last, ssz);
        dst += sz;
        size += sz;
        if(last) break;
    }
    av_log(NULL,AV_LOG_DEBUG,"Size = %i\n", size);
    *dsize = size;
    return (get_bits_count(&gb) + 7) >> 3;
}



More information about the ffmpeg-devel mailing list