huffdec3.c

jpeg and mpeg 编解码技术源代码

#include "all.h"


static int __cdecl
huffcmp(const void *va, const void *vb)
{
    const Huffman *a, *b;

    a = (Huffman *)va;
    b = (Huffman *)vb;
    if (a->len < b->len)
	return -1;
    if ( (a->len == b->len) && (a->cw < b->cw) )
	return -1;
    return 1;
}

void ssort (void  *base,
            size_t nel,
            size_t width,
            int (*comp)(const void *, const void *))
{
	size_t wnel, gap, wgap, i, j, k;
	char *a, *b, tmp;

	wnel = width * nel;
	for (gap = 0; ++gap < nel;)
		gap *= 3;
	while ( gap /= 3 )
	{
		wgap = width * gap;
		for (i = wgap; i < wnel; i += width)
		{
			for (j = i - wgap; ;j -= wgap)
			{
				a = j + (char *)base;
				b = a + wgap;
				if ( (*comp)(a, b) <= 0 )
					break;
				k = width;
				do
				{
					tmp = *a;
					*a++ = *b;
					*b++ = tmp;
				} while ( --k );
				if (j < wgap)
					break;
			}
		}
	}
}

/*
 * initialize the Hcb structure and sort the Huffman
 * codewords by length, shortest (most probable) first
 */
void
hufftab(Hcb *hcb, Huffman *hcw, int dim, int lav, int signed_cb)
{
    int i, n;
    
    if (!signed_cb) {
	hcb->mod = lav + 1;
        hcb->off = 0;
    }
    else {
	hcb->mod = 2*lav + 1;
        hcb->off = lav;
    }
    n=1;	    
    for (i=0; i<dim; i++)
	n *= hcb->mod;
    hcb->n = n;
    hcb->dim = dim;
    hcb->lav = lav;
    hcb->signed_cb = signed_cb;
    hcb->hcw = hcw;

    //qsort(hcw, n, sizeof(Huffman), huffcmp);
	ssort(hcw, n, sizeof(Huffman), huffcmp);
}
 
/*
 * Cword is working buffer to which shorts from
 *   bitstream are written. Bits are read from msb to lsb
 * Nbits is number of lsb bits not yet consumed
 * 
 * this uses a minimum-memory method of Huffman decoding
 */
int
decode_huff_cw(Huffman *h)
{
    int i, j;
    long cw;
    
    i = h->len;
    cw = getbits(i);
    while (cw != h->cw) {
	h++;
	j = h->len-i;
	i += j;
	cw <<= j;
	cw |= getbits(j);
    }
    return(h->index);
}


void
unpack_idx(int *qp, int idx, Hcb *hcb)
{
    int dim = hcb->dim;
    int mod = hcb->mod;
    int off = hcb->off;
    if(dim == 4){
	qp[0] = (idx/(mod*mod*mod)) - off;
	idx -= (qp[0] + off)*(mod*mod*mod);
	qp[1] = (idx/(mod*mod)) - off;
	idx -= (qp[1] + off)*(mod*mod);
	qp[2] = (idx/(mod)) - off;
	idx -= (qp[2] + off)*(mod);
	qp[3] = (idx) - off;
    }
    else {
	qp[0] = (idx/(mod)) - off;
	idx -= (qp[0] + off)*(mod);
	qp[1] = (idx) - off;
    }
}

/* get sign bits */
void
get_sign_bits(int *q, int n)
{
    int i;

    if(nbits <= 16) {
		cword = (cword<<16) | getshort();
		nbits += 16;
    }
    for (i=0; i<n; i++) {
		if (q[i]) {
			nbits--;
			if ((cword >> nbits) & 1) {
				/* 1 signals negative, as in 2's complement */
				q[i] = -q[i];
			}
		}
    }
}