[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