huffdecode.c revision 3f54fd611f536639ec30dd53c48e5ec1897cc7d9
89876b75747f59feeadde56f2c4950817fdca4ccChristian Maeder/***********************************************************************
b58a5478c73bcb2408dfd5f4d35e14b15c72fd46Christian Maeder* *
b58a5478c73bcb2408dfd5f4d35e14b15c72fd46Christian Maeder* This software is part of the ast package *
89876b75747f59feeadde56f2c4950817fdca4ccChristian Maeder* Copyright (c) 1993-2011 AT&T Intellectual Property *
98890889ffb2e8f6f722b00e265a211f13b5a861Corneliu-Claudiu Prodescu* and is licensed under the *
89876b75747f59feeadde56f2c4950817fdca4ccChristian Maeder* Eclipse Public License, Version 1.0 *
3f69b6948966979163bdfe8331c38833d5d90ecdChristian Maeder* by AT&T Intellectual Property *
89876b75747f59feeadde56f2c4950817fdca4ccChristian Maeder* *
89876b75747f59feeadde56f2c4950817fdca4ccChristian Maeder* A copy of the License is available at *
89876b75747f59feeadde56f2c4950817fdca4ccChristian Maeder* http://www.eclipse.org/org/documents/epl-v10.html *
b58a5478c73bcb2408dfd5f4d35e14b15c72fd46Christian Maeder* (with md5 checksum b35adb5213ca9657e911e9befb180842) *
89876b75747f59feeadde56f2c4950817fdca4ccChristian Maeder* *
89876b75747f59feeadde56f2c4950817fdca4ccChristian Maeder* Information and Software Systems Research *
f07bb197c32ccda6af72da82aa8029e4d6bfc99aChristian Maeder* AT&T Research *
f07bb197c32ccda6af72da82aa8029e4d6bfc99aChristian Maeder* Florham Park NJ *
f07bb197c32ccda6af72da82aa8029e4d6bfc99aChristian Maeder* *
f07bb197c32ccda6af72da82aa8029e4d6bfc99aChristian Maeder* David Korn <dgk@research.att.com> *
bccea164bdfc2ddc3d1e20749bb5477a46eab3a6Christian Maeder* *
8f1f53a2595bb239389fb5119ef590fa48166595Christian Maeder***********************************************************************/
1db8436e3bc935eec7ae680e1a4f6c11eb013270Christian Maeder#pragma prototyped
3141ac1ae0a0b9f86af05f439bc79316451b94f3Carsten Fischer/*
9029484754c7b2037321e7cbd077580866845265Christian Maeder * huffman coding decoding
f07bb197c32ccda6af72da82aa8029e4d6bfc99aChristian Maeder *
f07bb197c32ccda6af72da82aa8029e4d6bfc99aChristian Maeder * David Korn
f07bb197c32ccda6af72da82aa8029e4d6bfc99aChristian Maeder * AT&T Laboratories
f07bb197c32ccda6af72da82aa8029e4d6bfc99aChristian Maeder */
9029484754c7b2037321e7cbd077580866845265Christian Maeder
9029484754c7b2037321e7cbd077580866845265Christian Maeder#include "huffman.h"
9029484754c7b2037321e7cbd077580866845265Christian Maeder
9029484754c7b2037321e7cbd077580866845265Christian Maeder#define CHUNK 9
9029484754c7b2037321e7cbd077580866845265Christian Maeder#define END (1<<CHAR_BIT)
9029484754c7b2037321e7cbd077580866845265Christian Maeder#define fillbuff(b,left,bit,inp) while(left<(bit))\
f07bb197c32ccda6af72da82aa8029e4d6bfc99aChristian Maeder {\
9029484754c7b2037321e7cbd077580866845265Christian Maeder if(inp>=inend && !(inp=getbuff())) \
9029484754c7b2037321e7cbd077580866845265Christian Maeder return(-1); \
9029484754c7b2037321e7cbd077580866845265Christian Maeder left+=CHAR_BIT;\
9029484754c7b2037321e7cbd077580866845265Christian Maeder b = (b<<CHAR_BIT)|*inp++; \
9029484754c7b2037321e7cbd077580866845265Christian Maeder }
9029484754c7b2037321e7cbd077580866845265Christian Maeder/* read <n> bits from buffer <b> */
9029484754c7b2037321e7cbd077580866845265Christian Maeder#define getbits(b,left,n) (((b)>>(left-=(n)))&((1L<<(n))-1))
9029484754c7b2037321e7cbd077580866845265Christian Maeder/* return <n> bits */
#define putbits(b,left,n) (left+=(n))
static long lastid = 1;
static long id = 1;
static unsigned char outchar[(1<<CHUNK)];
static char numbits[(1<<CHUNK)];
static short intnodes[HUFFLEV+1];
static char *tree[HUFFLEV+1];
static char characters[END];
static char *eof;
static unsigned char *inbuff,*inend;
static Sfio_t *infile;
static void decode_header(Huff_t *);
static unsigned char *getbuff(void);
/*
* decode <input> using huffman tree defined in <hp> onto <output>
* if size>0, then decode until size bytes have been decoded
* otherwise, the complete file is decoded.
* The number of bytes written is returned or -1 on error
*/
Sfoff_t huffdecode(register Huff_t *hp,Sfio_t *input,Sfio_t *output,int size)
{
register long buffer;
register int left, i, n;
register int lev = 0;
register unsigned char *outp;
register unsigned char *inp;
unsigned char *outend;
unsigned char *outbuff;
Sfoff_t insize = hp->outsize;
/* decode the header if called with different hp */
if(lastid!=hp->id)
{
decode_header(hp);
if(!hp->id)
hp->id = id++;
lastid = hp->id;
}
/* set up output buffers for faster access */
if(!(outp=outbuff=(unsigned char*)sfreserve(output,SF_UNBOUND,SF_LOCKR)))
return(sfvalue(output));
n = sfvalue(output);
if(size>=0)
{
if(n > size)
n = size;
size -= n;
}
outend = outp+n;
/* set up input buffers for faster access */
infile = input;
if(!(inp=inbuff=(unsigned char*)sfreserve(infile,SF_UNBOUND,0)))
return(sfvalue(infile));
inend = inp + sfvalue(infile);
buffer = hp->buffer;
left = hp->left;
/* main decoding loop */
while (1)
{
if(lev==0)
{
fillbuff(buffer,left,hp->maxlev,inp);
i = getbits(buffer,left,CHUNK);
if((n=(numbits[i]-1)) >= 0)
{
putbits(buffer,left,n);
*outp++ = outchar[i];
goto pout;
}
if(hp->excess)
{
putbits(buffer,left,hp->excess);
i >>= hp->excess;
}
lev = CHUNK-hp->excess;
}
i <<= 1;
i += getbits(buffer,left,1);
if ((n = i - intnodes[lev+1]) >= 0)
{
{
register char *p = &tree[lev+1][n];
if (p == eof)
{
size = 0;
outend = outp;
}
else
*outp++ = *p;
}
pout:
if(outp >= outend)
{
n = outp - outbuff;
hp->outsize +=n;
if(sfwrite(output,outbuff,n)<0)
return(-1);
if(size==0)
{
hp->buffer = buffer;
hp->left = left;
sfread(infile, inbuff,inp-inbuff);
return(hp->outsize-insize);
}
if(!(outp=outbuff=(unsigned char*)sfreserve(output,SF_UNBOUND,SF_LOCKR)))
return(-1);
n = sfvalue(output);
if(size>0)
{
if(n > size)
n = size;
size -= n;
}
outp = outbuff;
outend = outp + n;
}
lev = 0;
}
else
lev++;
}
}
static void decode_header(register Huff_t *hp)
{
register int c, i, n, k;
eof = &characters[0];
for (i=1; i<=hp->maxlev; i++)
{
intnodes[i] = hp->levcount[i];
tree[i] = eof;
for (c=0; c < (1<<CHAR_BIT); c++)
{
if (hp->length[c] == i)
*eof++ = c;
}
}
intnodes[hp->maxlev] += 2;
/*
* convert intnodes[i] to be number of
* internal nodes possessed by level i
*/
for (n=0, i=hp->maxlev; i>=1; i--)
{
c = intnodes[i];
intnodes[i] = n /= 2;
n += c;
}
/* compute output char and number of bits used for each CHUNK of bits */
c = (1<<CHUNK) -1;
for (i=1; i<=CHUNK; i++)
{
for(k = tree[i+1] - tree[i];--k>=0;)
{
for(n=0; n < 1<<(CHUNK-i); n++)
{
numbits[c] = CHUNK+1-i;
outchar[c--] = tree[i][k];
}
}
}
if(hp->maxlev <= CHUNK)
{
hp->excess = CHUNK+1-hp->maxlev;
hp->maxlev = CHUNK;
}
while(c >=0)
numbits[c--] = 0;
}
static unsigned char *getbuff(void)
{
register int n;
register unsigned char *cp;
if(cp=(unsigned char*)sfreserve(infile,SF_UNBOUND,0))
inbuff = cp;
n = sfvalue(infile);
if(!cp && n<0)
return(cp);
inend = inbuff + n;
return(inbuff);
}