sshzlib.c

putty

    {5, 1, 7, 8},
    {6, 2, 9, 12},
    {7, 2, 13, 16},
    {8, 3, 17, 24},
    {9, 3, 25, 32},
    {10, 4, 33, 48},
    {11, 4, 49, 64},
    {12, 5, 65, 96},
    {13, 5, 97, 128},
    {14, 6, 129, 192},
    {15, 6, 193, 256},
    {16, 7, 257, 384},
    {17, 7, 385, 512},
    {18, 8, 513, 768},
    {19, 8, 769, 1024},
    {20, 9, 1025, 1536},
    {21, 9, 1537, 2048},
    {22, 10, 2049, 3072},
    {23, 10, 3073, 4096},
    {24, 11, 4097, 6144},
    {25, 11, 6145, 8192},
    {26, 12, 8193, 12288},
    {27, 12, 12289, 16384},
    {28, 13, 16385, 24576},
    {29, 13, 24577, 32768},
};

static void zlib_literal(struct LZ77Context *ectx, unsigned char c)
{
    struct Outbuf *out = (struct Outbuf *) ectx->userdata;

    if (out->comp_disabled) {
	/*
	 * We're in an uncompressed block, so just output the byte.
	 */
	outbits(out, c, 8);
	return;
    }

    if (c <= 143) {
	/* 0 through 143 are 8 bits long starting at 00110000. */
	outbits(out, mirrorbytes[0x30 + c], 8);
    } else {
	/* 144 through 255 are 9 bits long starting at 110010000. */
	outbits(out, 1 + 2 * mirrorbytes[0x90 - 144 + c], 9);
    }
}

static void zlib_match(struct LZ77Context *ectx, int distance, int len)
{
    const coderecord *d, *l;
    int i, j, k;
    struct Outbuf *out = (struct Outbuf *) ectx->userdata;

    assert(!out->comp_disabled);

    while (len > 0) {
	int thislen;

	/*
	 * We can transmit matches of lengths 3 through 258
	 * inclusive. So if len exceeds 258, we must transmit in
	 * several steps, with 258 or less in each step.
	 * 
	 * Specifically: if len >= 261, we can transmit 258 and be
	 * sure of having at least 3 left for the next step. And if
	 * len <= 258, we can just transmit len. But if len == 259
	 * or 260, we must transmit len-3.
	 */
	thislen = (len > 260 ? 258 : len <= 258 ? len : len - 3);
	len -= thislen;

	/*
	 * Binary-search to find which length code we're
	 * transmitting.
	 */
	i = -1;
	j = sizeof(lencodes) / sizeof(*lencodes);
	while (1) {
	    assert(j - i >= 2);
	    k = (j + i) / 2;
	    if (thislen < lencodes[k].min)
		j = k;
	    else if (thislen > lencodes[k].max)
		i = k;
	    else {
		l = &lencodes[k];
		break;		       /* found it! */
	    }
	}

	/*
	 * Transmit the length code. 256-279 are seven bits
	 * starting at 0000000; 280-287 are eight bits starting at
	 * 11000000.
	 */
	if (l->code <= 279) {
	    outbits(out, mirrorbytes[(l->code - 256) * 2], 7);
	} else {
	    outbits(out, mirrorbytes[0xc0 - 280 + l->code], 8);
	}

	/*
	 * Transmit the extra bits.
	 */
	if (l->extrabits)
	    outbits(out, thislen - l->min, l->extrabits);

	/*
	 * Binary-search to find which distance code we're
	 * transmitting.
	 */
	i = -1;
	j = sizeof(distcodes) / sizeof(*distcodes);
	while (1) {
	    assert(j - i >= 2);
	    k = (j + i) / 2;
	    if (distance < distcodes[k].min)
		j = k;
	    else if (distance > distcodes[k].max)
		i = k;
	    else {
		d = &distcodes[k];
		break;		       /* found it! */
	    }
	}

	/*
	 * Transmit the distance code. Five bits starting at 00000.
	 */
	outbits(out, mirrorbytes[d->code * 8], 5);

	/*
	 * Transmit the extra bits.
	 */
	if (d->extrabits)
	    outbits(out, distance - d->min, d->extrabits);
    }
}

void *zlib_compress_init(void)
{
    struct Outbuf *out;
    struct LZ77Context *ectx = snew(struct LZ77Context);

    lz77_init(ectx);
    ectx->literal = zlib_literal;
    ectx->match = zlib_match;

    out = snew(struct Outbuf);
    out->outbits = out->noutbits = 0;
    out->firstblock = 1;
    out->comp_disabled = FALSE;
    ectx->userdata = out;

    return ectx;
}

void zlib_compress_cleanup(void *handle)
{
    struct LZ77Context *ectx = (struct LZ77Context *)handle;
    sfree(ectx->userdata);
    sfree(ectx->ictx);
    sfree(ectx);
}

/*
 * Turn off actual LZ77 analysis for one block, to facilitate
 * construction of a precise-length IGNORE packet. Returns the
 * length adjustment (which is only valid for packets < 65536
 * bytes, but that seems reasonable enough).
 */
static int zlib_disable_compression(void *handle)
{
    struct LZ77Context *ectx = (struct LZ77Context *)handle;
    struct Outbuf *out = (struct Outbuf *) ectx->userdata;
    int n;

    out->comp_disabled = TRUE;

    n = 0;
    /*
     * If this is the first block, we will start by outputting two
     * header bytes, and then three bits to begin an uncompressed
     * block. This will cost three bytes (because we will start on
     * a byte boundary, this is certain).
     */
    if (out->firstblock) {
	n = 3;
    } else {
	/*
	 * Otherwise, we will output seven bits to close the
	 * previous static block, and _then_ three bits to begin an
	 * uncompressed block, and then flush the current byte.
	 * This may cost two bytes or three, depending on noutbits.
	 */
	n += (out->noutbits + 10) / 8;
    }

    /*
     * Now we output four bytes for the length / ~length pair in
     * the uncompressed block.
     */
    n += 4;

    return n;
}

int zlib_compress_block(void *handle, unsigned char *block, int len,
			unsigned char **outblock, int *outlen)
{
    struct LZ77Context *ectx = (struct LZ77Context *)handle;
    struct Outbuf *out = (struct Outbuf *) ectx->userdata;
    int in_block;

    out->outbuf = NULL;
    out->outlen = out->outsize = 0;

    /*
     * If this is the first block, output the Zlib (RFC1950) header
     * bytes 78 9C. (Deflate compression, 32K window size, default
     * algorithm.)
     */
    if (out->firstblock) {
	outbits(out, 0x9C78, 16);
	out->firstblock = 0;

	in_block = FALSE;
    } else
	in_block = TRUE;

    if (out->comp_disabled) {
	if (in_block)
	    outbits(out, 0, 7);	       /* close static block */

	while (len > 0) {
	    int blen = (len < 65535 ? len : 65535);

	    /*
	     * Start a Deflate (RFC1951) uncompressed block. We
	     * transmit a zero bit (BFINAL=0), followed by two more
	     * zero bits (BTYPE=00). Of course these are in the
	     * wrong order (00 0), not that it matters.
	     */
	    outbits(out, 0, 3);

	    /*
	     * Output zero bits to align to a byte boundary.
	     */
	    if (out->noutbits)
		outbits(out, 0, 8 - out->noutbits);

	    /*
	     * Output the block length, and then its one's
	     * complement. They're little-endian, so all we need to
	     * do is pass them straight to outbits() with bit count
	     * 16.
	     */
	    outbits(out, blen, 16);
	    outbits(out, blen ^ 0xFFFF, 16);

	    /*
	     * Do the `compression': we need to pass the data to
	     * lz77_compress so that it will be taken into account
	     * for subsequent (distance,length) pairs. But
	     * lz77_compress is passed FALSE, which means it won't
	     * actually find (or even look for) any matches; so
	     * every character will be passed straight to
	     * zlib_literal which will spot out->comp_disabled and
	     * emit in the uncompressed format.
	     */
	    lz77_compress(ectx, block, blen, FALSE);

	    len -= blen;
	    block += blen;
	}
	outbits(out, 2, 3);	       /* open new block */
    } else {
	if (!in_block) {
	    /*
	     * Start a Deflate (RFC1951) fixed-trees block. We
	     * transmit a zero bit (BFINAL=0), followed by a zero
	     * bit and a one bit (BTYPE=01). Of course these are in
	     * the wrong order (01 0).
	     */
	    outbits(out, 2, 3);
	}

	/*
	 * Do the compression.
	 */
	lz77_compress(ectx, block, len, TRUE);

	/*
	 * End the block (by transmitting code 256, which is
	 * 0000000 in fixed-tree mode), and transmit some empty
	 * blocks to ensure we have emitted the byte containing the
	 * last piece of genuine data. There are three ways we can
	 * do this:
	 *
	 *  - Minimal flush. Output end-of-block and then open a
	 *    new static block. This takes 9 bits, which is
	 *    guaranteed to flush out the last genuine code in the
	 *    closed block; but allegedly zlib can't handle it.
	 *
	 *  - Zlib partial flush. Output EOB, open and close an
	 *    empty static block, and _then_ open the new block.
	 *    This is the best zlib can handle.
	 *
	 *  - Zlib sync flush. Output EOB, then an empty
	 *    _uncompressed_ block (000, then sync to byte
	 *    boundary, then send bytes 00 00 FF FF). Then open the
	 *    new block.
	 *
	 * For the moment, we will use Zlib partial flush.
	 */
	outbits(out, 0, 7);	       /* close block */
	outbits(out, 2, 3 + 7);	       /* empty static block */
	outbits(out, 2, 3);	       /* open new block */
    }

    out->comp_disabled = FALSE;

    *outblock = out->outbuf;
    *outlen = out->outlen;

    return 1;
}

/* ----------------------------------------------------------------------
 * Zlib decompression. Of course, even though our compressor always
 * uses static trees, our _decompressor_ has to be capable of
 * handling dynamic trees if it sees them.
 */

/*
 * The way we work the Huffman decode is to have a table lookup on
 * the first N bits of the input stream (in the order they arrive,
 * of course, i.e. the first bit of the Huffman code is in bit 0).
 * Each table entry lists the number of bits to consume, plus
 * either an output code or a pointer to a secondary table.
 */
struct zlib_table;
struct zlib_tableentry;

struct zlib_tableentry {
    unsigned char nbits;
    short code;
    struct zlib_table *nexttable;
};

struct zlib_table {
    int mask;			       /* mask applied to input bit stream */
    struct zlib_tableentry *table;
};

#define MAXCODELEN 16
#define MAXSYMS 288

/*
 * Build a single-level decode table for elements
 * [minlength,maxlength) of the provided code/length tables, and
 * recurse to build subtables.
 */
static struct zlib_table *zlib_mkonetab(int *codes, unsigned char *lengths,
					int nsyms,
					int pfx, int pfxbits, int bits)
{
    struct zlib_table *tab = snew(struct zlib_table);
    int pfxmask = (1 << pfxbits) - 1;
    int nbits, i, j, code;

    tab->table = snewn(1 << bits, struct zlib_tableentry);
    tab->mask = (1 << bits) - 1;

    for (code = 0; code <= tab->mask; code++) {
	tab->table[code].code = -1;
	tab->table[code].nbits = 0;
	tab->table[code].nexttable = NULL;
    }

    for (i = 0; i < nsyms; i++) {
	if (lengths[i] <= pfxbits || (codes[i] & pfxmask) != pfx)
	    continue;
	code = (codes[i] >> pfxbits) & tab->mask;
	for (j = code; j <= tab->mask; j += 1 << (lengths[i] - pfxbits)) {
	    tab->table[j].code = i;
	    nbits = lengths[i] - pfxbits;
	    if (tab->table[j].nbits < nbits)
		tab->table[j].nbits = nbits;
	}
    }
    for (code = 0; code <= tab->mask; code++) {
	if (tab->table[code].nbits <= bits)
	    continue;
	/* Generate a subtable. */
	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;