/***********************************************************************
* *
* This software is part of the ast package *
* Copyright (c) 1993-2011 AT&T Intellectual Property *
* and is licensed under the *
* Eclipse Public License, Version 1.0 *
* by AT&T Intellectual Property *
* *
* A copy of the License is available at *
* http://www.eclipse.org/org/documents/epl-v10.html *
* (with md5 checksum b35adb5213ca9657e911e9befb180842) *
* *
* Information and Software Systems Research *
* AT&T Research *
* Florham Park NJ *
* *
* David Korn <dgk@research.att.com> *
* *
***********************************************************************/
#pragma prototyped
/*
* huffman coding decoding
*
* David Korn
* AT&T Laboratories
*/
#include "huffman.h"
#define CHUNK 9
#define END (1<<CHAR_BIT)
#define fillbuff(b,left,bit,inp) while(left<(bit))\
{\
if(inp>=inend && !(inp=getbuff())) \
return(-1); \
left+=CHAR_BIT;\
b = (b<<CHAR_BIT)|*inp++; \
}
/* read <n> bits from buffer <b> */
#define getbits(b,left,n) (((b)>>(left-=(n)))&((1L<<(n))-1))
/* 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);
}