sshzlib.c

一个FTP下载的源代码。代码质量非常高

	tab->table[code].code = -1;
	nbits = tab->table[code].nbits - bits;
	if (nbits > 7)
	    nbits = 7;
	tab->table[code].nbits = bits;
	tab->table[code].nexttable = zlib_mkonetab(codes, lengths, nsyms,
						   pfx | (code << pfxbits),
						   pfxbits + bits, nbits);
    }

    return tab;
}

/*
 * Build a decode table, given a set of Huffman tree lengths.
 */
static struct zlib_table *zlib_mktable(unsigned char *lengths,
				       int nlengths)
{
    int count[MAXCODELEN], startcode[MAXCODELEN], codes[MAXSYMS];
    int code, maxlen;
    int i, j;

    /* Count the codes of each length. */
    maxlen = 0;
    for (i = 1; i < MAXCODELEN; i++)
	count[i] = 0;
    for (i = 0; i < nlengths; i++) {
	count[lengths[i]]++;
	if (maxlen < lengths[i])
	    maxlen = lengths[i];
    }
    /* Determine the starting code for each length block. */
    code = 0;
    for (i = 1; i < MAXCODELEN; i++) {
	startcode[i] = code;
	code += count[i];
	code <<= 1;
    }
    /* Determine the code for each symbol. Mirrored, of course. */
    for (i = 0; i < nlengths; i++) {
	code = startcode[lengths[i]]++;
	codes[i] = 0;
	for (j = 0; j < lengths[i]; j++) {
	    codes[i] = (codes[i] << 1) | (code & 1);
	    code >>= 1;
	}
    }

    /*
     * Now we have the complete list of Huffman codes. Build a
     * table.
     */
    return zlib_mkonetab(codes, lengths, nlengths, 0, 0,
			 maxlen < 9 ? maxlen : 9);
}

static int zlib_freetable(struct zlib_table **ztab)
{
    struct zlib_table *tab;
    int code;

    if (ztab == NULL)
	return -1;

    if (*ztab == NULL)
	return 0;

    tab = *ztab;

    for (code = 0; code <= tab->mask; code++)
	if (tab->table[code].nexttable != NULL)
	    zlib_freetable(&tab->table[code].nexttable);

    sfree(tab->table);
    tab->table = NULL;

    sfree(tab);
    *ztab = NULL;

    return (0);
}

struct zlib_decompress_ctx {
    struct zlib_table *staticlentable, *staticdisttable;
    struct zlib_table *currlentable, *currdisttable, *lenlentable;
    enum {
	START, OUTSIDEBLK,
	TREES_HDR, TREES_LENLEN, TREES_LEN, TREES_LENREP,
	INBLK, GOTLENSYM, GOTLEN, GOTDISTSYM,
	UNCOMP_LEN, UNCOMP_NLEN, UNCOMP_DATA
    } state;
    int sym, hlit, hdist, hclen, lenptr, lenextrabits, lenaddon, len,
	lenrep;
    int uncomplen;
    unsigned char lenlen[19];
    unsigned char lengths[286 + 32];
    unsigned long bits;
    int nbits;
    unsigned char window[WINSIZE];
    int winpos;
    unsigned char *outblk;
    int outlen, outsize;
};

void *zlib_decompress_init(void)
{
    struct zlib_decompress_ctx *dctx = snew(struct zlib_decompress_ctx);
    unsigned char lengths[288];

    memset(lengths, 8, 144);
    memset(lengths + 144, 9, 256 - 144);
    memset(lengths + 256, 7, 280 - 256);
    memset(lengths + 280, 8, 288 - 280);
    dctx->staticlentable = zlib_mktable(lengths, 288);
    memset(lengths, 5, 32);
    dctx->staticdisttable = zlib_mktable(lengths, 32);
    dctx->state = START;		       /* even before header */
    dctx->currlentable = dctx->currdisttable = dctx->lenlentable = NULL;
    dctx->bits = 0;
    dctx->nbits = 0;
    dctx->winpos = 0;

    return dctx;
}

void zlib_decompress_cleanup(void *handle)
{
    struct zlib_decompress_ctx *dctx = (struct zlib_decompress_ctx *)handle;
    
    if (dctx->currlentable && dctx->currlentable != dctx->staticlentable)
	zlib_freetable(&dctx->currlentable);
    if (dctx->currdisttable && dctx->currdisttable != dctx->staticdisttable)
	zlib_freetable(&dctx->currdisttable);
    if (dctx->lenlentable)
	zlib_freetable(&dctx->lenlentable);
    sfree(dctx);
}

static int zlib_huflookup(unsigned long *bitsp, int *nbitsp,
		   struct zlib_table *tab)
{
    unsigned long bits = *bitsp;
    int nbits = *nbitsp;
    while (1) {
	struct zlib_tableentry *ent;
	ent = &tab->table[bits & tab->mask];
	if (ent->nbits > nbits)
	    return -1;		       /* not enough data */
	bits >>= ent->nbits;
	nbits -= ent->nbits;
	if (ent->code == -1)
	    tab = ent->nexttable;
	else {
	    *bitsp = bits;
	    *nbitsp = nbits;
	    return ent->code;
	}

	if (!tab) {
	    /*
	     * There was a missing entry in the table, presumably
	     * due to an invalid Huffman table description, and the
	     * subsequent data has attempted to use the missing
	     * entry. Return a decoding failure.
	     */
	    return -2;
	}
    }
}

static void zlib_emit_char(struct zlib_decompress_ctx *dctx, int c)
{
    dctx->window[dctx->winpos] = c;
    dctx->winpos = (dctx->winpos + 1) & (WINSIZE - 1);
    if (dctx->outlen >= dctx->outsize) {
	dctx->outsize = dctx->outlen + 512;
	dctx->outblk = sresize(dctx->outblk, dctx->outsize, unsigned char);
    }
    dctx->outblk[dctx->outlen++] = c;
}

#define EATBITS(n) ( dctx->nbits -= (n), dctx->bits >>= (n) )

int zlib_decompress_block(void *handle, unsigned char *block, int len,
			  unsigned char **outblock, int *outlen)
{
    struct zlib_decompress_ctx *dctx = (struct zlib_decompress_ctx *)handle;
    const coderecord *rec;
    int code, blktype, rep, dist, nlen;
    static const unsigned char lenlenmap[] = {
	16, 17, 18, 0, 8, 7, 9, 6, 10, 5, 11, 4, 12, 3, 13, 2, 14, 1, 15
    };

    dctx->outblk = NULL;
    dctx->outsize = dctx->outlen = 0;

    while (len > 0 || dctx->nbits > 0) {
	while (dctx->nbits < 24 && len > 0) {
	    dctx->bits |= (*block++) << dctx->nbits;
	    dctx->nbits += 8;
	    len--;
	}
	switch (dctx->state) {
	  case START:
	    /* Expect 16-bit zlib header, which we'll dishonourably ignore. */
	    if (dctx->nbits < 16)
		goto finished;	       /* done all we can */
	    EATBITS(16);
	    dctx->state = OUTSIDEBLK;
	    break;
	  case OUTSIDEBLK:
	    /* Expect 3-bit block header. */
	    if (dctx->nbits < 3)
		goto finished;	       /* done all we can */
	    EATBITS(1);
	    blktype = dctx->bits & 3;
	    EATBITS(2);
	    if (blktype == 0) {
		int to_eat = dctx->nbits & 7;
		dctx->state = UNCOMP_LEN;
		EATBITS(to_eat);       /* align to byte boundary */
	    } else if (blktype == 1) {
		dctx->currlentable = dctx->staticlentable;
		dctx->currdisttable = dctx->staticdisttable;
		dctx->state = INBLK;
	    } else if (blktype == 2) {
		dctx->state = TREES_HDR;
	    }
	    break;
	  case TREES_HDR:
	    /*
	     * Dynamic block header. Five bits of HLIT, five of
	     * HDIST, four of HCLEN.
	     */
	    if (dctx->nbits < 5 + 5 + 4)
		goto finished;	       /* done all we can */
	    dctx->hlit = 257 + (dctx->bits & 31);
	    EATBITS(5);
	    dctx->hdist = 1 + (dctx->bits & 31);
	    EATBITS(5);
	    dctx->hclen = 4 + (dctx->bits & 15);
	    EATBITS(4);
	    dctx->lenptr = 0;
	    dctx->state = TREES_LENLEN;
	    memset(dctx->lenlen, 0, sizeof(dctx->lenlen));
	    break;
	  case TREES_LENLEN:
	    if (dctx->nbits < 3)
		goto finished;
	    while (dctx->lenptr < dctx->hclen && dctx->nbits >= 3) {
		dctx->lenlen[lenlenmap[dctx->lenptr++]] =
		    (unsigned char) (dctx->bits & 7);
		EATBITS(3);
	    }
	    if (dctx->lenptr == dctx->hclen) {
		dctx->lenlentable = zlib_mktable(dctx->lenlen, 19);
		dctx->state = TREES_LEN;
		dctx->lenptr = 0;
	    }
	    break;
	  case TREES_LEN:
	    if (dctx->lenptr >= dctx->hlit + dctx->hdist) {
		dctx->currlentable = zlib_mktable(dctx->lengths, dctx->hlit);
		dctx->currdisttable = zlib_mktable(dctx->lengths + dctx->hlit,
						  dctx->hdist);
		zlib_freetable(&dctx->lenlentable);
		dctx->lenlentable = NULL;
		dctx->state = INBLK;
		break;
	    }
	    code =
		zlib_huflookup(&dctx->bits, &dctx->nbits, dctx->lenlentable);
	    if (code == -1)
		goto finished;
	    if (code == -2)
		goto decode_error;
	    if (code < 16)
		dctx->lengths[dctx->lenptr++] = code;
	    else {
		dctx->lenextrabits = (code == 16 ? 2 : code == 17 ? 3 : 7);
		dctx->lenaddon = (code == 18 ? 11 : 3);
		dctx->lenrep = (code == 16 && dctx->lenptr > 0 ?
			       dctx->lengths[dctx->lenptr - 1] : 0);
		dctx->state = TREES_LENREP;
	    }
	    break;
	  case TREES_LENREP:
	    if (dctx->nbits < dctx->lenextrabits)
		goto finished;
	    rep =
		dctx->lenaddon +
		(dctx->bits & ((1 << dctx->lenextrabits) - 1));
	    EATBITS(dctx->lenextrabits);
	    while (rep > 0 && dctx->lenptr < dctx->hlit + dctx->hdist) {
		dctx->lengths[dctx->lenptr] = dctx->lenrep;
		dctx->lenptr++;
		rep--;
	    }
	    dctx->state = TREES_LEN;
	    break;
	  case INBLK:
	    code =
		zlib_huflookup(&dctx->bits, &dctx->nbits, dctx->currlentable);
	    if (code == -1)
		goto finished;
	    if (code == -2)
		goto decode_error;
	    if (code < 256)
		zlib_emit_char(dctx, code);
	    else if (code == 256) {
		dctx->state = OUTSIDEBLK;
		if (dctx->currlentable != dctx->staticlentable) {
		    zlib_freetable(&dctx->currlentable);
		    dctx->currlentable = NULL;
		}
		if (dctx->currdisttable != dctx->staticdisttable) {
		    zlib_freetable(&dctx->currdisttable);
		    dctx->currdisttable = NULL;
		}
	    } else if (code < 286) {   /* static tree can give >285; ignore */
		dctx->state = GOTLENSYM;
		dctx->sym = code;
	    }
	    break;
	  case GOTLENSYM:
	    rec = &lencodes[dctx->sym - 257];
	    if (dctx->nbits < rec->extrabits)
		goto finished;
	    dctx->len =
		rec->min + (dctx->bits & ((1 << rec->extrabits) - 1));
	    EATBITS(rec->extrabits);
	    dctx->state = GOTLEN;
	    break;
	  case GOTLEN:
	    code =
		zlib_huflookup(&dctx->bits, &dctx->nbits,
			       dctx->currdisttable);
	    if (code == -1)
		goto finished;
	    if (code == -2)
		goto decode_error;
	    dctx->state = GOTDISTSYM;
	    dctx->sym = code;
	    break;
	  case GOTDISTSYM:
	    rec = &distcodes[dctx->sym];
	    if (dctx->nbits < rec->extrabits)
		goto finished;
	    dist = rec->min + (dctx->bits & ((1 << rec->extrabits) - 1));
	    EATBITS(rec->extrabits);
	    dctx->state = INBLK;
	    while (dctx->len--)
		zlib_emit_char(dctx, dctx->window[(dctx->winpos - dist) &
						  (WINSIZE - 1)]);
	    break;
	  case UNCOMP_LEN:
	    /*
	     * Uncompressed block. We expect to see a 16-bit LEN.
	     */
	    if (dctx->nbits < 16)
		goto finished;
	    dctx->uncomplen = dctx->bits & 0xFFFF;
	    EATBITS(16);
	    dctx->state = UNCOMP_NLEN;
	    break;
	  case UNCOMP_NLEN:
	    /*
	     * Uncompressed block. We expect to see a 16-bit NLEN,
	     * which should be the one's complement of the previous
	     * LEN.
	     */
	    if (dctx->nbits < 16)
		goto finished;
	    nlen = dctx->bits & 0xFFFF;
	    EATBITS(16);
	    if (dctx->uncomplen == 0)
		dctx->state = OUTSIDEBLK;	/* block is empty */
	    else
		dctx->state = UNCOMP_DATA;
	    break;
	  case UNCOMP_DATA:
	    if (dctx->nbits < 8)
		goto finished;
	    zlib_emit_char(dctx, dctx->bits & 0xFF);
	    EATBITS(8);
	    if (--dctx->uncomplen == 0)
		dctx->state = OUTSIDEBLK;	/* end of uncompressed block */
	    break;
	}
    }

  finished:
    *outblock = dctx->outblk;
    *outlen = dctx->outlen;
    return 1;

  decode_error:
    sfree(dctx->outblk);
    *outblock = dctx->outblk = NULL;
    *outlen = 0;
    return 0;
}

const struct ssh_compress ssh_zlib = {
    "zlib",
    zlib_compress_init,
    zlib_compress_cleanup,
    zlib_compress_block,
    zlib_decompress_init,
    zlib_decompress_cleanup,
    zlib_decompress_block,
    zlib_disable_compression,
    "zlib (RFC1950)"
};