inflatelib.c

VXWORKS源代码

    )
    {
    int doSwap = 0;
    ulg sum = prevSum;
    union
	{
	uch	c[2];
	ush	s;
	} shorty;
    union
	{
	ush	s[2];
	ulg	l;
	} longy;

#define	REDUCE(x) {longy.l = x; x = longy.s[0] + longy.s[1];}


    REDUCE(sum);

    /* do the first byte now for misaligned buffers */

    if ((int)buf & 1)
	{
	doSwap = 1;
	shorty.c[0] = 0;
	shorty.c[1] = *buf;
	buf++;
	len--;
	sum += shorty.s;
	}

    /* do the rest two bytes at a time */

    while (len > 1)
	{
	sum += *((ush *)buf);
	buf += 2;
	len -= 2;
	if ((len & 0xffff) == 0)
	    REDUCE(sum);
	}

    /* add in the last byte if needed */

    if (len == 1)
	{
	shorty.c[0] = *buf;
	shorty.c[1] = 0;
	sum += shorty.s;
	}

    REDUCE(sum);
    REDUCE(sum);
    shorty.s = sum;

    /* swap bytes if needed */

    if (doSwap)
	{
	uch tmp;
	tmp = shorty.c[0];
	shorty.c[0] = shorty.c[1];
	shorty.c[1] = tmp;
	}

    return (shorty.s);
    }

/******************************************************************************
*
* zcalloc - allocate memory
*/ 

static voidp zcalloc
    (
    voidp opaque,
    unsigned items,
    unsigned size
    )
    {
    voidp thisBlock = (voidp)nextBlock;
    int nBytes = ROUND_UP (items * size);

    if ((char *)thisBlock + nBytes + BLK_HDR_SIZE >= &buf[BUF_SIZE])
	{
	DBG_PUT ("zcalloc %d bytes: buffer overflow!\n", nBytes);
	return (0);
	}

    nextBlock = (char *)thisBlock + nBytes + BLK_HDR_SIZE;
    BLK_HDRS_LINK (thisBlock, nextBlock);

    return (thisBlock);
    }

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

static void  zcfree
    (
    voidp opaque,
    voidp ptr
    )
    {
    voidp thisBlock;

    /* make sure block is valid */

    if (!BLK_IS_VALID(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(nextBlock);
	 thisBlock != 0 && BLK_IS_FREE(thisBlock);
	 thisBlock = (voidp)BLK_PREV(thisBlock))
	{
	nextBlock = thisBlock;
	BLK_NEXT(nextBlock) = 0;
	}

    return;
    }

/* normally stack variable for huft_build - but stack was too large */

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 */

/******************************************************************************
*
* 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 */
    z_streamp	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 = c;
    C4                            /* clear c[]--assume BMAX+1 is 16 */
    p = b;  i = n;
    do
	{
	c[*p++]++;                  /* assume all entries <= BMAX */
	} while (--i);
    if (c[0] == n)                /* null input--all zero length codes */
	{
	*t = (inflate_huft *)Z_NULL;
	*m = 0;
	return Z_OK;
	}

    /* Find minimum and maximum length, bound *m by those */
    l = *m;
    for (j = 1; j <= BMAX; j++)
	if (c[j])
	    break;
    k = j;                        /* minimum code length */
    if ((uInt)l < j)
	l = j;
    for (i = BMAX; i; i--)
	if (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 -= c[j]) < 0)
	    return Z_DATA_ERROR;
    if ((y -= c[i]) < 0)
	return Z_DATA_ERROR;
    c[i] += y;

    /* Generate starting offsets into the value table for each length */
    x[1] = j = 0;
    p = c + 1;  xp = 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)
	    v[x[j]++] = i;
	} while (++i < n);

    /* Generate the Huffman codes and for each, make the table entries */
    x[0] = i = 0;                 /* first Huffman code is zero */
    p = v;                        /* grab values in bit order */
    h = -1;                       /* no tables yet--level -1 */
    w = -l;                       /* bits decoded == (l * h) */
    u[0] = (inflate_huft *)Z_NULL;        /* just to keep compilers happy */
    q = (inflate_huft *)Z_NULL;   /* ditto */
    z = 0;                        /* ditto */

    /* go through the bit lengths (k already is bits in shortest code) */
    for (; k <= g; k++)
	{
	a = c[k];
	while (a--)
	    {
	    /* here i is the Huffman code of length k bits for value *p */
	    /* make tables up to required level */
	    while (k > w + l)
		{
		h++;
	        w += l;                 /* previous table always l bits */

	        /* compute minimum size table less than or equal to l bits */
	        z = g - w;
	        z = z > (uInt)l ? l : z;        /* table size upper limit */
	        if ((f = 1 << (j = k - w)) > a + 1) /* try a k-w bit table */
	            {                 /* too few codes for k-w bit table */
	            f -= a + 1;       /* deduct codes from patterns left */
	            xp = c + k;
	            if (j < z)
	   	        while (++j < z) /* try smaller tables up to z bits */
		            {
	                    if ((f <<= 1) <= *++xp)
	                        break; /* enough codes to use up j bits */
		            f -= *xp;  /* else deduct codes from patterns */
			    }
        	    }
	        z = 1 << j;             /* table entries for j-bit table */

	        /* allocate and link in new table */
	        q = (inflate_huft *)ZALLOC(zs,z + 1,sizeof(inflate_huft));
	        if (q == Z_NULL)
        	    {
	            if (h)
	                inflate_trees_free(u[0], zs);
	            return Z_MEM_ERROR; /* not enough memory */
        	    }

	        *t = q + 1;             /* link to list for huft_free() */
	        *(t = &(q->next)) = Z_NULL;
	        u[h] = ++q;             /* table starts after link */

	        /* connect to last table, if there is one */
	        if (h)
	            {
	            x[h] = i;           /* save pattern for backing up */
	            r.bits = (Byte)l;	/* bits to dump before this table */
	            r.exop = (Byte)j;   /* bits in this table */
	            r.next = q;         /* pointer to this table */
	            j = i >> (w - l);   /* (get around Turbo C bug) */
	            u[h-1][j] = r;      /* connect to last table */
	            }
		}

	    /* set up table entry in r */
	    r.bits = (Byte)(k - w);
	    if (p >= v + n)
	        r.exop = 128 + 64;      /* out of values--invalid code */
	    else if (*p < s)
	        {
		/* 256 is end-of-block */
	        r.exop = (Byte)(*p < 256 ? 0 : 32 + 64);
	        r.base = *p++;          /* simple code is just the value */
	        }
	    else
	        {
		/* non-simple--look up in lists */
	        r.exop = (Byte)(e[*p - s] + 16 + 64);
	        r.base = d[*p++ - s];
	        }

	    /* fill code-like entries with r */
	    f = 1 << (k - w);
	    for (j = i >> w; j < z; j += f)
	        q[j] = r;

	    /* backwards increment the k-bit code i */
	    for (j = 1 << (k - 1); i & j; j >>= 1)
	        i ^= j;
	    i ^= j;

	    /* backup over finished tables */
	    while ((i & ((1 << w) - 1)) != x[h])
	        {
	        h--;                    /* don't need to update q */
	        w -= l;
	        }
	    }
	}

    /* Return Z_BUF_ERROR if we were given an incomplete table */
    return y != 0 && g != 1 ? Z_BUF_ERROR : Z_OK;
    }

/******************************************************************************
*
* inflate_trees_bits - inflate bits from huffman tree
*/ 

static int inflate_trees_bits
    (
    uInt *c,		/* 19 code lengths */
    uInt *bb,           /* bits tree desired/actual depth */
    inflate_huft ** tb, /* bits tree result */
    z_streamp z         /* for zfree function */
    )
    {
    int r;

    r = huft_build(c, 19, 19, (uInt*)Z_NULL, (uInt*)Z_NULL, tb, bb, z);
    if (r == Z_DATA_ERROR)
	z->msg = (char*)"oversubscribed dynamic bit lengths tree";
    else if (r == Z_BUF_ERROR)
	{
	inflate_trees_free(*tb, z);
	z->msg = (char*)"incomplete dynamic bit lengths tree";
	r = Z_DATA_ERROR;
	}
    return r;
    }

/******************************************************************************
*
* inflate_trees_dynamic - inflate from dynamic huffman tree
*/ 

static int inflate_trees_dynamic
    (
    uInt	nl,	/* number of literal/length codes */
    uInt	nd,     /* number of distance codes */
    uInt *	c,      /* that many (total) code lengths */
    uInt *	bl,     /* literal desired/actual bit depth */
    uInt *	bd,     /* distance desired/actual bit depth */
    inflate_huft ** tl, /* literal/length tree result */
    inflate_huft ** td, /* distance tree result */
    z_streamp	z       /* for zfree function */
    )
    {
    int r;

    /* build literal/length tree */
    if ((r = huft_build(c, nl, 257, cplens, cplext, tl, bl, z)) != Z_OK)
	{
	if (r == Z_DATA_ERROR)
	    z->msg = (char*)"oversubscribed literal/length tree";
	else if (r == Z_BUF_ERROR)
	    {
	    inflate_trees_free(*tl, z);
	    z->msg = (char*)"incomplete literal/length tree";
	    r = Z_DATA_ERROR;
	    }
	return r;
	}

    /* build distance tree */
    if ((r = huft_build(c + nl, nd, 0, cpdist, cpdext, td, bd, z)) != Z_OK)
	{
	if (r == Z_DATA_ERROR)
	     z->msg = (char*)"oversubscribed literal/length tree";
	else if (r == Z_BUF_ERROR) {
	    inflate_trees_free(*td, z);
	    z->msg = (char*)"incomplete literal/length tree";
	    r = Z_DATA_ERROR;
	    }
	inflate_trees_free(*tl, z);
	return r;
	}

    /* done */
    return Z_OK;
    }

/******************************************************************************
*
* falloc  - fake memeory allocator for huftman trees