inflate.c

vxworks MPC8541 BSP

/* includes */
#include "stdio.h"
#include "string.h"
#include "sys/stat.h"

#include "inflate.h"
#ifdef VXWORKS
#include "stdlib.h"
#else
#include "malloc.h"
#endif

#define ZALLOC(strm, items, size) \
           (*((strm)->zalloc))(strm,(strm)->opaque, (items), (size))
#define ZFREE(strm, addr)  (*((strm)->zfree))(strm,(strm)->opaque, (VOIDP)(addr))

/* ===========================================================================
 * Internal compression state.
 */
/* defines for inflate input/output */
/*   update pointers and return */
#define UPDBITS {s->bitb=b;s->bitk=k;}
#define UPDIN {z->avail_in=n;z->total_in+=p-z->next_in;z->next_in=p;}
#define UPDOUT {s->write=q;}
#define ZUPDATE {UPDBITS UPDIN UPDOUT}
#define ZLEAVE {ZUPDATE return inflate_flush(s,z,r);}
/*   get bytes and bits */
#define LOADIN {p=z->next_in;n=z->avail_in;b=s->bitb;k=s->bitk;}
#define NEEDBYTE {if(n)r=Z_OK;else ZLEAVE}
#define NEXTBYTE (n--,*p++)
#define NEEDBITS(j) {while(k<(j)){NEEDBYTE;b|=((ULONG)NEXTBYTE)<<k;k+=8;}}
#define DUMPBITS(j) {b>>=(j);k-=(j);}
/*   output bytes */
#define WAVAIL (UINT)(q<s->read?s->read-q-1:s->end-q)
#define LOADOUT {q=s->write;m=(UINT)WAVAIL;}
#define WRAP {if(q==s->end&&s->read!=s->window){q=s->window;m=(UINT)WAVAIL;}}
#define FLUSH {UPDOUT r=inflate_flush(s,z,r); LOADOUT}
#define NEEDOUT {if(m==0){WRAP if(m==0){FLUSH WRAP if(m==0) ZLEAVE}}r=Z_OK;}
#define OUTBYTE(a) {*q++=(BYTE)(a);m--;}
/*   load local pointers */
#define LOAD {LOADIN LOADOUT}

/* Output a byte on the stream.
 * IN assertion: there is enough room in pending_buf.
 */
#define DO1(buf,i)  {s1 += buf[i]; s2 += s1;}
#define DO2(buf,i)  DO1(buf,i); DO1(buf,i+1);
#define DO4(buf,i)  DO2(buf,i); DO2(buf,i+2);
#define DO8(buf,i)  DO4(buf,i); DO4(buf,i+4);
#define DO16(buf)   DO8(buf,0); DO8(buf,8);

/* simplify the use of the inflate_huft type with some defines */
#define C0 *p++ = 0;
#define C2 C0 C0 C0 C0
#define C4 C2 C2 C2 C2

#define FIXEDH 530      /* number of hufts used by fixed tables */

#define BLK_ALIGN   sizeof(int)
#define ZROUND_UP(n)    ((n + BLK_ALIGN - 1) & (~(BLK_ALIGN - 1)))

#define BLK_HDR_SIZE    (2 * sizeof(int))
#define BLK_NEXT(b) (*(((int *)(b)) - 1))
#define BLK_PREV(b) (*(((int *)(b)) - 2))
#define BLK_HDRS_LINK(this,next)        \
        {               \
        BLK_NEXT(this) = (int)(next);   \
        BLK_PREV(next) = (int)(this);   \
        }

#define BLK_IS_FREE(b)  (BLK_NEXT(b) & 1)
#define BLK_FREE_SET(b) (BLK_NEXT(b) |= 1)
#define BLK_IS_VALID(z,b)   ( (BYTE *)b == (BYTE*)z->z_mem_pool + BLK_HDR_SIZE  \
                            || BLK_PREV(BLK_NEXT(b)) == (int)(b))

/* simplify the use of the inflate_huft type with some defines */
#define base more.Base
#define next more.Next
#define exop word.what.Exop
#define bits word.what.Bits

/* macros for bit input with no checking and for returning unused bytes */
#define GRABBITS(j) {while(k<(j)){b|=((ULONG)NEXTBYTE)<<k;k+=8;}}
#define UNGRAB {n+=(c=k>>3);p-=c;k&=7;}

/* Diagnostic functions */
#ifdef DEBUG
#  ifndef verbose
#    define verbose 0
#  endif
#  define Assert(cond,msg)     {if(!(cond)) fprintf(stderr,msg);}
#  define Trace(x) fprintf x
#  define Tracev(x) {if (verbose) fprintf x ;}
#  define Tracevv(x) {if (verbose>1) fprintf x ;}
#  define Tracec(c,x) {if (verbose && (c)) fprintf x ;}
#  define Tracecv(c,x) {if (verbose>1 && (c)) fprintf x ;}
#  define DBG_PUT(a,b)  fprintf (stderr, a, (unsigned int)b);
#else
#  define Assert(cond,msg)  {}
#  define Trace(x)          {}
#  define Tracev(x)         {}
#  define Tracevv(x)        {}
#  define Tracec(c,x)       {}
#  define Tracecv(c,x)      {}
#  define DBG_PUT(a,b)      {}
#endif

#define ZSTREAM_NEXT_BYTE(z) (z->avail_in--,z->total_in++,*z->next_in++)


/* allocate two extra words for prev/next pointers for first block */
#define MEM_POOL_SIZE  (BLK_HDR_SIZE + 100*1024)

    /* static variables */
    /* Tables for deflate from PKZIP's appnote.txt. */
static  UINT cplens[31] = { /* Copy lengths for literal codes 257..285 */
        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, 0, 0};
        /* actually lengths - 2; also see note #13 above about 258 */
static  UINT cplext[31] = { /* Extra bits for literal codes 257..285 */
        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, 192, 192}; /* 192==invalid */
static UINT cpdist[30] = { /* Copy offsets for distance codes 0..29 */
        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};
static UINT cpdext[30] = { /* Extra bits for distance codes */
        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};
static UINT inflate_mask[17] = {
        0x0000,
        0x0001, 0x0003, 0x0007, 0x000f, 0x001f, 0x003f, 0x007f, 0x00ff,
        0x01ff, 0x03ff, 0x07ff, 0x0fff, 0x1fff, 0x3fff, 0x7fff, 0xffff };
    /* Table for deflate from PKZIP's appnote.txt. */
static UINT border[] = { /* Order of the bit length code lengths */
        16, 17, 18, 0, 8, 7, 9, 6, 10, 5, 11, 4, 12, 3, 13, 2, 14, 1, 15};

/* forward static function declarations */

static int huft_build (
     UINT *,            /* code lengths in bits */
     UINT,              /* number of codes */
     UINT,              /* number of "simple" codes */
     UINT *,            /* list of base values for non-simple codes */
     UINT *,            /* list of extra bits for non-simple codes */
     inflate_huft * *,  /* result: starting table */
     UINT *,            /* maximum lookup bits (returns actual) */
     ZAR_STREAM* );       /* for zalloc function */


static int inflate_trees_free (
     inflate_huft * t,  /* table to free */
     ZAR_STREAM*        z       /* for zfree function */
     );

static int inflate_flush (
     inflate_blocks_statef *,
     ZAR_STREAM* ,
     int);

static int inflate_fast (
     UINT,
     UINT,
     inflate_huft *,
     inflate_huft *,
     inflate_blocks_statef *,
     ZAR_STREAM* );


#ifndef VXWORKS
/******************************************************************************
*
* bzero -
*/
static void bzero(
    char  *buffer,  /* buffer to be zeroed       */
    int   nbytes )   /* number of bytes in buffer */
{
    while (nbytes >= 1)   /* tongxj modified */
    {
        *buffer = 0;
        buffer += 1;
        nbytes -= 1;
    }
}
#endif

/******************************************************************************
*
* adler32 - 32 bit checksum
*/

static ULONG adler32
    (
    ULONG   adler,      /* previous total */
    const BYTE *buf,        /* buffer to checksum */
    UINT    len     /* size of buffer */
    )
    {
    unsigned long s1 = adler & 0xffff;
    unsigned long s2 = (adler >> 16) & 0xffff;
    int k;

    if (buf == NULL)
    return 1L;

    while (len > 0)
    {
        k = len < NMAX ? len : NMAX;
        len -= k;
        while (k >= 16)
        {
            DO16(buf);
        buf += 16;
            k -= 16;
            }
        if (k != 0)
        do
        {
            s1 += *buf++;
        s2 += s1;
            } while (--k);

        s1 %= BASE;
        s2 %= BASE;
    }

    return (s2 << 16) | s1;
    }

/* compute stream 16bit checksum in network order */
unsigned short
z_cksum( unsigned short       prevSum,        /* previous total */
       const unsigned char* buf,            /* buffer to checksum */
       unsigned int         len,
       int                  oddflag )            /* size of buffer */
{
    unsigned short sum = prevSum;
    unsigned int   curpos=0;

    if(buf== NULL || len == 0 )
        return sum;

    if (oddflag) /* odd byte;low byte */
        sum = (unsigned short) (sum + buf[curpos++]);
    /* compute the sum */
    for  ( ;len - curpos > 1;curpos += 2)
        sum = (unsigned short)(sum + (unsigned short)( (buf[curpos] << 8) + buf[curpos+1] ));

    if ( len - curpos > 0 )
        sum = (unsigned short)(sum + ( buf[curpos] << 8));

    return sum;
}

static UINT maxMemAdr=0;
/******************************************************************************
*
* zcalloc - allocate memory
*/
static VOIDP zcalloc
    (
    ZAR_STREAM* z,
    VOIDP opaque,
    unsigned items,
    unsigned size
    )
    {
    VOIDP thisBlock = (VOIDP)z->z_next_block;
    int nBytes = ZROUND_UP (items * size);
    if ((BYTE *)thisBlock + BLK_HDR_SIZE + nBytes >= (BYTE*)z->z_mem_pool+ MEM_POOL_SIZE)
    {
    DBG_PUT ("zcalloc %d bytes: buffer overflow!\n", nBytes);
    return (0);
    }

    z->z_next_block = (BYTE *)thisBlock + nBytes + BLK_HDR_SIZE;
    BLK_HDRS_LINK (thisBlock, z->z_next_block);

    maxMemAdr = ((UINT)thisBlock + BLK_HDR_SIZE + nBytes) > maxMemAdr ?
                    ((UINT)thisBlock + BLK_HDR_SIZE + nBytes):maxMemAdr;
    return (thisBlock);
    }

/******************************************************************************
*
* zcfree - free memory
*/

static void  zcfree
    (
    ZAR_STREAM* z,
    VOIDP opaque,
    VOIDP ptr
    )
    {
    VOIDP thisBlock;
    /* make sure block is valid */

    if (!BLK_IS_VALID(z,ptr))
    {
    DBG_PUT ("free at invalid address 0x%x\n", ptr);
    return;
    }
    /* mark block as free */
    BLK_FREE_SET (ptr);
    /* pop free blocks from the top of the stack */
    for (thisBlock = (VOIDP)BLK_PREV(z->z_next_block);
     thisBlock != 0 && BLK_IS_FREE(thisBlock);
     thisBlock = (VOIDP)BLK_PREV(thisBlock))
    {
        z->z_next_block = thisBlock;
        BLK_NEXT(z->z_next_block) = 0;

    }

    return;
    }

/* normally stack variable for huft_build - but stack was too large */
#if 0
static UINT c[BMAX+1];             /* bit length count table */
static inflate_huft *u[BMAX];      /* table stack */
static UINT v[N_MAX];              /* values in order of bit length */
static UINT x[BMAX+1];             /* bit offsets, then code stack */
#endif

/******************************************************************************
*
* huft_build - build a huffman tree
*
* Given a list of code lengths and a maximum table size, make a set of
* tables to decode that set of codes.  Return Z_OK on success, Z_BUF_ERROR
* if the given code set is incomplete (the tables are still built in this
* case), Z_DATA_ERROR if the input is invalid (all zero length codes or an
* over-subscribed set of lengths), or Z_MEM_ERROR if not enough memory.
*/

static int huft_build
    (
    UINT *  b,  /* code lengths in bits (all assumed <= BMAX) */
    UINT    n,  /* number of codes (assumed <= N_MAX) */
    UINT    s,  /* number of simple-valued codes (0..s-1) */
    UINT *  d,  /* list of base values for non-simple codes */
    UINT *  e,  /* list of extra bits for non-simple codes */
    inflate_huft ** t,  /* result: starting table */
    UINT *  m,  /* maximum lookup bits, returns actual */
    ZAR_STREAM* zs  /* for zalloc function */
    )
    {
    UINT a;                     /* counter for codes of length k */
    UINT f;                     /* i repeats in table every f entries */
    int g;                      /* maximum code length */
    int h;                      /* table level */
    register UINT i;            /* counter, current code */
    register UINT j;            /* counter */
    register int k;             /* number of bits in current code */
    int l;                      /* bits per table (returned in m) */
    register UINT *p;           /* pointer into c[], b[], or v[] */
    inflate_huft *q;            /* points to current table */
     struct inflate_huft_s r;    /* table entry for structure assignment */
    register int w;             /* bits before this table == (l * h) */
    UINT *xp;           /* pointer into x */
    int y;                      /* number of dummy codes added */
    UINT z;                     /* number of entries in current table */


     /* Generate counts for each bit length */
    p = zs->z_c;
     C4                            /* clear c[]--assume BMAX+1 is 16 */
    p = b;  i = n;
    do
    {
    zs->z_c[*p++]++;                  /* assume all entries <= BMAX */
    } while (--i);
    if (zs->z_c[0] == n)                /* null input--all zero length codes */
    {
    *t = (inflate_huft *)NULL;
    *m = 0;
    return Z_OK;
    }

    /* Find minimum and maximum length, bound *m by those */
    l = *m;
    for (j = 1; j <= BMAX; j++)
    if (zs->z_c[j])
        break;
    k = j;                        /* minimum code length */
    if ((UINT)l < j)
    l = j;
    for (i = BMAX; i; i--)
    if (zs->z_c[i])
        break;
    g = i;                        /* maximum code length */
    if ((UINT)l > i)
    l = i;
    *m = l;

     /* Adjust last length count to fill out codes, if needed */
    for (y = 1 << j; j < i; j++, y <<= 1)
    if ((y -= zs->z_c[j]) < 0)
        return Z_DATA_ERROR;
    if ((y -= zs->z_c[i]) < 0)
    return Z_DATA_ERROR;
    zs->z_c[i] += y;

    /* Generate starting offsets into the value table for each length */
    zs->z_x[1] = j = 0;
    p = zs->z_c + 1;  xp = zs->z_x + 2;
    while (--i)
    {                 /* note that i == g from above */
    *xp++ = (j += *p++);
    }

    /* Make a table of values in order of bit lengths */
    p = b;  i = 0;
    do
    {
    if ((j = *p++) != 0)
        zs->z_v[(zs->z_x[j])++] = i;
    } while (++i < n);

    /* Generate the Huffman codes and for each, make the table entries */
    zs->z_x[0] = i = 0;                 /* first Huffman code is zero */
    p = zs->z_v;                        /* grab values in bit order */
    h = -1;                       /* no tables yet--level -1 */
    w = -l;                       /* bits decoded == (l * h) */
    zs->z_u[0] = (inflate_huft *)NULL;        /* just to keep compilers happy */