inflate.c

vxworks MPC8541 BSP

    q = (inflate_huft *)NULL;   /* ditto */
    z = 0;                        /* ditto */

    /* go through the bit lengths (k already is bits in shortest code) */
    for (; k <= g; k++)
    {
    a = zs->z_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 ? (UINT)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 = zs->z_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 == NULL)
                {
                if (h)
                    inflate_trees_free(zs->z_u[0], zs);
                return Z_MEM_ERROR; /* not enough memory */
                }

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

            /* connect to last table, if there is one */
            if (h)
                {
                zs->z_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) */
                zs->z_u[h-1][j] = r;      /* connect to last table */
                }
        }

        /* set up table entry in r */
        r.bits = (BYTE)(k - w);
        if (p >= zs->z_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)) != zs->z_x[h])
            {
            h--;                    /* don't need to ZUPDATE 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 */
    ZAR_STREAM* z         /* for zfree function */
    )
    {
    int r;

    r = huft_build(c, 19, 19, (UINT*)NULL, (UINT*)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 */
    ZAR_STREAM* 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;
    }

/******************************************************************************
*
* inflate_trees_fixed -
*/
static int inflate_trees_fixed (
        ZAR_STREAM*       zp,
        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 */
{
    printf("fixed-tree.\n");
    /* build fixed tables if not already (multiple overlapped executions ok) */
    if (!zp->z_fixed_built)
    {
        /* ZAR_STREAM lz;        for falloc function */
        int k;              /* temporary variable */
        unsigned *c = (unsigned *)zcalloc (zp,0, 288, sizeof (unsigned));
                            /* length list for huft_build */
        /* int f = FIXEDH;     number of hufts left in fixed_mem

        set up fake ZAR_STREAM for memory routines
        lz.zalloc = falloc;
        lz.zfree = NULL;
        lz.opaque = (VOIDP)&f;  */

        /* literal table */
        for (k = 0; k < 144; k++)   c[k] = 8;
        for (; k < 256; k++)        c[k] = 9;
        for (; k < 280; k++)        c[k] = 7;
        for (; k < 288; k++)        c[k] = 8;

        zp->z_fixed_bl = 7;
        huft_build(c, 288, 257, cplens, cplext, &zp->z_fixed_tl, &zp->z_fixed_bl, zp);

        /* distance table */
        for (k = 0; k < 30; k++)    c[k] = 5;

        zp->z_fixed_bd = 5;
        huft_build(c, 30, 0, cpdist, cpdext, &zp->z_fixed_td, &zp->z_fixed_bd, zp);

        /* done */
        zp->z_fixed_built = 1;
        zcfree (zp,0, c);
    } /* endif (!z->z_fixed_built)*/

    *bl = zp->z_fixed_bl;
    *bd = zp->z_fixed_bd;
    *tl = zp->z_fixed_tl;
    *td = zp->z_fixed_td;
    return Z_OK;
}

/******************************************************************************
*
* inflate_trees_free -
*
* Free the malloc'ed tables built by huft_build(), which makes a linked
* list of the tables it made, with the links in a dummy first entry of
* each table.
*/

static int inflate_trees_free
    (
    inflate_huft *  t,  /* table to free */
    ZAR_STREAM*     z       /* for zfree function */
    )
    {
    register inflate_huft *p, *q, *r;

    /* Reverse linked list */
    p = NULL;
    q = t;
    while (q != NULL)
    {
    r = (q - 1)->next;
    (q - 1)->next = p;
    p = q;
    q = r;
    }

    /* Go through linked list, freeing from the malloced (t[-1]) address. */
    while (p != NULL)
    {
    q = (--p)->next;
    ZFREE(z,p);
    p = q;
    }

    return Z_OK;
    }

/******************************************************************************
*
* inflate_flush -
*
* copy as much as possible from the sliding window to the output area
*/

static int inflate_flush
    (
    inflate_blocks_statef * s,
    ZAR_STREAM*     z,
    int         r
    )
    {
     UINT n;
     BYTE *p;
     BYTE *q;

    /* local copies of source and destination pointers */
    p = z->next_out;
    q = s->read;

    /* compute number of bytes to copy as far as end of window */
    n = (UINT)((q <= s->write ? s->write : s->end) - q);
    if (n > z->avail_out)
    n = z->avail_out;
    if (n && r == Z_BUF_ERROR)
    r = Z_OK;

    /* ZUPDATE counters */
    z->avail_out -= n;
    z->total_out += n;

    /* ZUPDATE check information */
    if (s->checkfn != NULL)
    z->adler = s->check = (*s->checkfn)(s->check, q, n);

    /* copy as far as end of window */
    memcpy(p, q, n);

     p += n;
    q += n;

    /* see if more to copy at beginning of window */
    if (q == s->end)
    {
    /* wrap pointers */
    q = s->window;
    if (s->write == s->end)
        s->write = s->window;

    /* compute bytes to copy */
    n = (UINT)(s->write - q);
    if (n > z->avail_out)
        n = z->avail_out;
    if (n && r == Z_BUF_ERROR)
        r = Z_OK;

    /* ZUPDATE counters */
    z->avail_out -= n;
    z->total_out += n;

    /* ZUPDATE check information */
    if (s->checkfn != NULL)
        z->adler = s->check = (*s->checkfn)(s->check, q, n);

    /* copy */
    memcpy(p, q, n);

    p += n;
    q += n;

    }

    /* ZUPDATE pointers */
    z->next_out = p;
    s->read = q;

    /* done */
    return r;
    }

/******************************************************************************
*
* inflate_fast -
*
* Called with number of bytes left to write in window at least 258
* (the maximum string length) and number of input bytes available
* at least ten.  The ten bytes are six bytes for the longest length/
* distance pair plus four bytes for overloading the bit buffer.
*/

static int inflate_fast
    (
    UINT    bl,
    UINT    bd,
    inflate_huft * tl,
    inflate_huft * td,
    inflate_blocks_statef * s,
    ZAR_STREAM* z
    )
    {
    inflate_huft *t;    /* temporary pointer */
    UINT e;             /* extra bits or operation */
    ULONG b;            /* bit buffer */
    UINT k;             /* bits in bit buffer */
    BYTE *p;            /* input data pointer */
    UINT n;             /* bytes available there */
    BYTE *q;            /* output window write pointer */
    UINT m;             /* bytes to end of window or read pointer */
    UINT ml;            /* mask for literal/length tree */
    UINT md;            /* mask for distance tree */
    UINT c;             /* bytes to copy */
    UINT d;             /* distance back to copy from */
    BYTE *r;            /* copy source pointer */

  /* load input, output, bit values */
  LOAD

  /* initialize masks */
  ml = inflate_mask[bl];
  md = inflate_mask[bd];

  /* do until not enough input or output space for fast loop */
  do {                          /* assume called with m >= 258 && n >= 10 */
    /* get literal/length code */
    GRABBITS(20)                /* max bits for literal/length code */
    if ((e = (t = tl + ((UINT)b & ml))->exop) == 0)
    {
      DUMPBITS(t->bits)
      Tracevv((stderr, t->base >= 0x20 && t->base < 0x7f ?
                "inflate:         * literal '%c'\n" :
                "inflate:         * literal 0x%02x\n", t->base));
      *q++ = (BYTE)t->base;
      m--;
      continue;
    }
    do {
      DUMPBITS(t->bits)
      if (e & 16)
      {
        /* get extra bits for length */
        e &= 15;
        c = t->base + ((UINT)b & inflate_mask[e]);
        DUMPBITS(e)
        Tracevv((stderr, "inflate:         * length %u\n", c));

        /* decode distance base of block to copy */
        GRABBITS(15);           /* max bits for distance code */
        e = (t = td + ((UINT)b & md))->exop;
        do {
          DUMPBITS(t->bits)
          if (e & 16)
          {
            /* get extra bits to add to distance base */
            e &= 15;
            GRABBITS(e)         /* get extra bits (up to 13) */
            d = t->base + ((UINT)b & inflate_mask[e]);
            DUMPBITS(e)
            Tracevv((stderr, "inflate:         * distance %u\n", d));