12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576777879808182838485868788899091929394959697989910010110210310410510610710810911011111211311411511611711811912012112212312412512612712812913013113213313413513613713813914014114214314414514614714814915015115215315415515615715815916016116216316416516616716816917017117217317417517617717817918018118218318418518618718818919019119219319419519619719819920020120220320420520620720820921021121221321421521621721821922022122222322422522622722822923023123223323423523623723823924024124224324424524624724824925025125225325425525625725825926026126226326426526626726826927027127227327427527627727827928028128228328428528628728828929029129229329429529629729829930030130230330430530630730830931031131231331431531631731831932032132232332432532632732832933033133233333433533633733833934034134234334434534634734834935035135235335435535635735835936036136236336436536636736836937037137237337437537637737837938038138238338438538638738838939039139239339439539639739839940040140240340440540640740840941041141241341441541641741841942042142242342442542642742842943043143243343443543643743843944044144244344444544644744844945045145245345445545645745845946046146246346446546646746846947047147247347447547647747847948048148248348448548648748848949049149249349449549649749849950050150250350450550650750850951051151251351451551651751851952052152252352452552652752852953053153253353453553653753853954054154254354454554654754854955055155255355455555655755855956056156256356456556656756856957057157257357457557657757857958058158258358458558658758858959059159259359459559659759859960060160260360460560660760860961061161261361461561661761861962062162262362462562662762862963063163263363463563663763863964064164264364464564664764864965065165265365465565665765865966066166266366466566666766866967067167267367467567667767867968068168268368468568668768868969069169269369469569669769869970070170270370470570670770870971071171271371471571671771871972072172272372472572672772872973073173273373473573673773873974074174274374474574674774874975075175275375475575675775875976076176276376476576676776876977077177277377477577677777877978078178278378478578678778878979079179279379479579679779879980080180280380480580680780880981081181281381481581681781881982082182282382482582682782882983083183283383483583683783883984084184284384484584684784884985085185285385485585685785885986086186286386486586686786886987087187287387487587687787887988088188288388488588688788888989089189289389489589689789889990090190290390490590690790890991091191291391491591691791891992092192292392492592692792892993093193293393493593693793893994094194294394494594694794894995095195295395495595695795895996096196296396496596696796896997097197297397497597697797897998098198298398498598698798898999099199299399499599699799899910001001100210031004100510061007100810091010101110121013101410151016101710181019102010211022102310241025102610271028102910301031103210331034103510361037103810391040104110421043104410451046104710481049105010511052105310541055105610571058105910601061106210631064106510661067106810691070107110721073107410751076107710781079108010811082108310841085108610871088108910901091109210931094109510961097109810991100110111021103110411051106110711081109111011111112111311141115111611171118111911201121112211231124112511261127112811291130113111321133113411351136113711381139114011411142114311441145114611471148114911501151115211531154115511561157115811591160116111621163116411651166116711681169117011711172117311741175117611771178117911801181118211831184118511861187118811891190119111921193119411951196119711981199120012011202120312041205120612071208120912101211121212131214121512161217121812191220122112221223122412251226122712281229123012311232123312341235123612371238123912401241124212431244124512461247124812491250125112521253 |
- /*
- * Zlib (RFC1950 / RFC1951) compression for PuTTY.
- *
- * There will no doubt be criticism of my decision to reimplement
- * Zlib compression from scratch instead of using the existing zlib
- * code. People will cry `reinventing the wheel'; they'll claim
- * that the `fundamental basis of OSS' is code reuse; they'll want
- * to see a really good reason for me having chosen not to use the
- * existing code.
- *
- * Well, here are my reasons. Firstly, I don't want to link the
- * whole of zlib into the PuTTY binary; PuTTY is justifiably proud
- * of its small size and I think zlib contains a lot of unnecessary
- * baggage for the kind of compression that SSH requires.
- *
- * Secondly, I also don't like the alternative of using zlib.dll.
- * Another thing PuTTY is justifiably proud of is its ease of
- * installation, and the last thing I want to do is to start
- * mandating DLLs. Not only that, but there are two _kinds_ of
- * zlib.dll kicking around, one with C calling conventions on the
- * exported functions and another with WINAPI conventions, and
- * there would be a significant danger of getting the wrong one.
- *
- * Thirdly, there seems to be a difference of opinion on the IETF
- * secsh mailing list about the correct way to round off a
- * compressed packet and start the next. In particular, there's
- * some talk of switching to a mechanism zlib isn't currently
- * capable of supporting (see below for an explanation). Given that
- * sort of uncertainty, I thought it might be better to have code
- * that will support even the zlib-incompatible worst case.
- *
- * Fourthly, it's a _second implementation_. Second implementations
- * are fundamentally a Good Thing in standardisation efforts. The
- * difference of opinion mentioned above has arisen _precisely_
- * because there has been only one zlib implementation and
- * everybody has used it. I don't intend that this should happen
- * again.
- */
- #include <stdlib.h>
- #include <string.h>
- #include <assert.h>
- #include "defs.h"
- #include "ssh.h"
- /* ----------------------------------------------------------------------
- * Basic LZ77 code. This bit is designed modularly, so it could be
- * ripped out and used in a different LZ77 compressor. Go to it,
- * and good luck :-)
- */
- struct LZ77InternalContext;
- struct LZ77Context {
- struct LZ77InternalContext *ictx;
- void *userdata;
- void (*literal) (struct LZ77Context *ctx, unsigned char c);
- void (*match) (struct LZ77Context *ctx, int distance, int len);
- };
- /*
- * Initialise the private fields of an LZ77Context. It's up to the
- * user to initialise the public fields.
- */
- static int lz77_init(struct LZ77Context *ctx);
- /*
- * Supply data to be compressed. Will update the private fields of
- * the LZ77Context, and will call literal() and match() to output.
- * If `compress' is false, it will never emit a match, but will
- * instead call literal() for everything.
- */
- static void lz77_compress(struct LZ77Context *ctx,
- const unsigned char *data, int len);
- /*
- * Modifiable parameters.
- */
- #define WINSIZE 32768 /* window size. Must be power of 2! */
- #define HASHMAX 2039 /* one more than max hash value */
- #define MAXMATCH 32 /* how many matches we track */
- #define HASHCHARS 3 /* how many chars make a hash */
- /*
- * This compressor takes a less slapdash approach than the
- * gzip/zlib one. Rather than allowing our hash chains to fall into
- * disuse near the far end, we keep them doubly linked so we can
- * _find_ the far end, and then every time we add a new byte to the
- * window (thus rolling round by one and removing the previous
- * byte), we can carefully remove the hash chain entry.
- */
- #define INVALID -1 /* invalid hash _and_ invalid offset */
- struct WindowEntry {
- short next, prev; /* array indices within the window */
- short hashval;
- };
- struct HashEntry {
- short first; /* window index of first in chain */
- };
- struct Match {
- int distance, len;
- };
- struct LZ77InternalContext {
- struct WindowEntry win[WINSIZE];
- unsigned char data[WINSIZE];
- int winpos;
- struct HashEntry hashtab[HASHMAX];
- unsigned char pending[HASHCHARS];
- int npending;
- };
- static int lz77_hash(const unsigned char *data)
- {
- return (257 * data[0] + 263 * data[1] + 269 * data[2]) % HASHMAX;
- }
- static int lz77_init(struct LZ77Context *ctx)
- {
- struct LZ77InternalContext *st;
- int i;
- st = snew(struct LZ77InternalContext);
- if (!st)
- return 0;
- ctx->ictx = st;
- for (i = 0; i < WINSIZE; i++)
- st->win[i].next = st->win[i].prev = st->win[i].hashval = INVALID;
- for (i = 0; i < HASHMAX; i++)
- st->hashtab[i].first = INVALID;
- st->winpos = 0;
- st->npending = 0;
- return 1;
- }
- static void lz77_advance(struct LZ77InternalContext *st,
- unsigned char c, int hash)
- {
- int off;
- /*
- * Remove the hash entry at winpos from the tail of its chain,
- * or empty the chain if it's the only thing on the chain.
- */
- if (st->win[st->winpos].prev != INVALID) {
- st->win[st->win[st->winpos].prev].next = INVALID;
- } else if (st->win[st->winpos].hashval != INVALID) {
- st->hashtab[st->win[st->winpos].hashval].first = INVALID;
- }
- /*
- * Create a new entry at winpos and add it to the head of its
- * hash chain.
- */
- st->win[st->winpos].hashval = hash;
- st->win[st->winpos].prev = INVALID;
- off = st->win[st->winpos].next = st->hashtab[hash].first;
- st->hashtab[hash].first = st->winpos;
- if (off != INVALID)
- st->win[off].prev = st->winpos;
- st->data[st->winpos] = c;
- /*
- * Advance the window pointer.
- */
- st->winpos = (st->winpos + 1) & (WINSIZE - 1);
- }
- #define CHARAT(k) ( (k)<0 ? st->data[(st->winpos+k)&(WINSIZE-1)] : data[k] )
- static void lz77_compress(struct LZ77Context *ctx,
- const unsigned char *data, int len)
- {
- struct LZ77InternalContext *st = ctx->ictx;
- int i, distance, off, nmatch, matchlen, advance;
- struct Match defermatch, matches[MAXMATCH];
- int deferchr;
- assert(st->npending <= HASHCHARS);
- /*
- * Add any pending characters from last time to the window. (We
- * might not be able to.)
- *
- * This leaves st->pending empty in the usual case (when len >=
- * HASHCHARS); otherwise it leaves st->pending empty enough that
- * adding all the remaining 'len' characters will not push it past
- * HASHCHARS in size.
- */
- for (i = 0; i < st->npending; i++) {
- unsigned char foo[HASHCHARS];
- int j;
- if (len + st->npending - i < HASHCHARS) {
- /* Update the pending array. */
- for (j = i; j < st->npending; j++)
- st->pending[j - i] = st->pending[j];
- break;
- }
- for (j = 0; j < HASHCHARS; j++)
- foo[j] = (i + j < st->npending ? st->pending[i + j] :
- data[i + j - st->npending]);
- lz77_advance(st, foo[0], lz77_hash(foo));
- }
- st->npending -= i;
- defermatch.distance = 0; /* appease compiler */
- defermatch.len = 0;
- deferchr = '\0';
- while (len > 0) {
- if (len >= HASHCHARS) {
- /*
- * Hash the next few characters.
- */
- int hash = lz77_hash(data);
- /*
- * Look the hash up in the corresponding hash chain and see
- * what we can find.
- */
- nmatch = 0;
- for (off = st->hashtab[hash].first;
- off != INVALID; off = st->win[off].next) {
- /* distance = 1 if off == st->winpos-1 */
- /* distance = WINSIZE if off == st->winpos */
- distance =
- WINSIZE - (off + WINSIZE - st->winpos) % WINSIZE;
- for (i = 0; i < HASHCHARS; i++)
- if (CHARAT(i) != CHARAT(i - distance))
- break;
- if (i == HASHCHARS) {
- matches[nmatch].distance = distance;
- matches[nmatch].len = 3;
- if (++nmatch >= MAXMATCH)
- break;
- }
- }
- } else {
- nmatch = 0;
- }
- if (nmatch > 0) {
- /*
- * We've now filled up matches[] with nmatch potential
- * matches. Follow them down to find the longest. (We
- * assume here that it's always worth favouring a
- * longer match over a shorter one.)
- */
- matchlen = HASHCHARS;
- while (matchlen < len) {
- int j;
- for (i = j = 0; i < nmatch; i++) {
- if (CHARAT(matchlen) ==
- CHARAT(matchlen - matches[i].distance)) {
- matches[j++] = matches[i];
- }
- }
- if (j == 0)
- break;
- matchlen++;
- nmatch = j;
- }
- /*
- * We've now got all the longest matches. We favour the
- * shorter distances, which means we go with matches[0].
- * So see if we want to defer it or throw it away.
- */
- matches[0].len = matchlen;
- if (defermatch.len > 0) {
- if (matches[0].len > defermatch.len + 1) {
- /* We have a better match. Emit the deferred char,
- * and defer this match. */
- ctx->literal(ctx, (unsigned char) deferchr);
- defermatch = matches[0];
- deferchr = data[0];
- advance = 1;
- } else {
- /* We don't have a better match. Do the deferred one. */
- ctx->match(ctx, defermatch.distance, defermatch.len);
- advance = defermatch.len - 1;
- defermatch.len = 0;
- }
- } else {
- /* There was no deferred match. Defer this one. */
- defermatch = matches[0];
- deferchr = data[0];
- advance = 1;
- }
- } else {
- /*
- * We found no matches. Emit the deferred match, if
- * any; otherwise emit a literal.
- */
- if (defermatch.len > 0) {
- ctx->match(ctx, defermatch.distance, defermatch.len);
- advance = defermatch.len - 1;
- defermatch.len = 0;
- } else {
- ctx->literal(ctx, data[0]);
- advance = 1;
- }
- }
- /*
- * Now advance the position by `advance' characters,
- * keeping the window and hash chains consistent.
- */
- while (advance > 0) {
- if (len >= HASHCHARS) {
- lz77_advance(st, *data, lz77_hash(data));
- } else {
- assert(st->npending < HASHCHARS);
- st->pending[st->npending++] = *data;
- }
- data++;
- len--;
- advance--;
- }
- }
- }
- /* ----------------------------------------------------------------------
- * Zlib compression. We always use the static Huffman tree option.
- * Mostly this is because it's hard to scan a block in advance to
- * work out better trees; dynamic trees are great when you're
- * compressing a large file under no significant time constraint,
- * but when you're compressing little bits in real time, things get
- * hairier.
- *
- * I suppose it's possible that I could compute Huffman trees based
- * on the frequencies in the _previous_ block, as a sort of
- * heuristic, but I'm not confident that the gain would balance out
- * having to transmit the trees.
- */
- struct Outbuf {
- strbuf *outbuf;
- unsigned long outbits;
- int noutbits;
- bool firstblock;
- };
- static void outbits(struct Outbuf *out, unsigned long bits, int nbits)
- {
- assert(out->noutbits + nbits <= 32);
- out->outbits |= bits << out->noutbits;
- out->noutbits += nbits;
- while (out->noutbits >= 8) {
- put_byte(out->outbuf, out->outbits & 0xFF);
- out->outbits >>= 8;
- out->noutbits -= 8;
- }
- }
- static const unsigned char mirrorbytes[256] = {
- 0x00, 0x80, 0x40, 0xc0, 0x20, 0xa0, 0x60, 0xe0,
- 0x10, 0x90, 0x50, 0xd0, 0x30, 0xb0, 0x70, 0xf0,
- 0x08, 0x88, 0x48, 0xc8, 0x28, 0xa8, 0x68, 0xe8,
- 0x18, 0x98, 0x58, 0xd8, 0x38, 0xb8, 0x78, 0xf8,
- 0x04, 0x84, 0x44, 0xc4, 0x24, 0xa4, 0x64, 0xe4,
- 0x14, 0x94, 0x54, 0xd4, 0x34, 0xb4, 0x74, 0xf4,
- 0x0c, 0x8c, 0x4c, 0xcc, 0x2c, 0xac, 0x6c, 0xec,
- 0x1c, 0x9c, 0x5c, 0xdc, 0x3c, 0xbc, 0x7c, 0xfc,
- 0x02, 0x82, 0x42, 0xc2, 0x22, 0xa2, 0x62, 0xe2,
- 0x12, 0x92, 0x52, 0xd2, 0x32, 0xb2, 0x72, 0xf2,
- 0x0a, 0x8a, 0x4a, 0xca, 0x2a, 0xaa, 0x6a, 0xea,
- 0x1a, 0x9a, 0x5a, 0xda, 0x3a, 0xba, 0x7a, 0xfa,
- 0x06, 0x86, 0x46, 0xc6, 0x26, 0xa6, 0x66, 0xe6,
- 0x16, 0x96, 0x56, 0xd6, 0x36, 0xb6, 0x76, 0xf6,
- 0x0e, 0x8e, 0x4e, 0xce, 0x2e, 0xae, 0x6e, 0xee,
- 0x1e, 0x9e, 0x5e, 0xde, 0x3e, 0xbe, 0x7e, 0xfe,
- 0x01, 0x81, 0x41, 0xc1, 0x21, 0xa1, 0x61, 0xe1,
- 0x11, 0x91, 0x51, 0xd1, 0x31, 0xb1, 0x71, 0xf1,
- 0x09, 0x89, 0x49, 0xc9, 0x29, 0xa9, 0x69, 0xe9,
- 0x19, 0x99, 0x59, 0xd9, 0x39, 0xb9, 0x79, 0xf9,
- 0x05, 0x85, 0x45, 0xc5, 0x25, 0xa5, 0x65, 0xe5,
- 0x15, 0x95, 0x55, 0xd5, 0x35, 0xb5, 0x75, 0xf5,
- 0x0d, 0x8d, 0x4d, 0xcd, 0x2d, 0xad, 0x6d, 0xed,
- 0x1d, 0x9d, 0x5d, 0xdd, 0x3d, 0xbd, 0x7d, 0xfd,
- 0x03, 0x83, 0x43, 0xc3, 0x23, 0xa3, 0x63, 0xe3,
- 0x13, 0x93, 0x53, 0xd3, 0x33, 0xb3, 0x73, 0xf3,
- 0x0b, 0x8b, 0x4b, 0xcb, 0x2b, 0xab, 0x6b, 0xeb,
- 0x1b, 0x9b, 0x5b, 0xdb, 0x3b, 0xbb, 0x7b, 0xfb,
- 0x07, 0x87, 0x47, 0xc7, 0x27, 0xa7, 0x67, 0xe7,
- 0x17, 0x97, 0x57, 0xd7, 0x37, 0xb7, 0x77, 0xf7,
- 0x0f, 0x8f, 0x4f, 0xcf, 0x2f, 0xaf, 0x6f, 0xef,
- 0x1f, 0x9f, 0x5f, 0xdf, 0x3f, 0xbf, 0x7f, 0xff,
- };
- typedef struct {
- short code, extrabits;
- int min, max;
- } coderecord;
- static const coderecord lencodes[] = {
- {257, 0, 3, 3},
- {258, 0, 4, 4},
- {259, 0, 5, 5},
- {260, 0, 6, 6},
- {261, 0, 7, 7},
- {262, 0, 8, 8},
- {263, 0, 9, 9},
- {264, 0, 10, 10},
- {265, 1, 11, 12},
- {266, 1, 13, 14},
- {267, 1, 15, 16},
- {268, 1, 17, 18},
- {269, 2, 19, 22},
- {270, 2, 23, 26},
- {271, 2, 27, 30},
- {272, 2, 31, 34},
- {273, 3, 35, 42},
- {274, 3, 43, 50},
- {275, 3, 51, 58},
- {276, 3, 59, 66},
- {277, 4, 67, 82},
- {278, 4, 83, 98},
- {279, 4, 99, 114},
- {280, 4, 115, 130},
- {281, 5, 131, 162},
- {282, 5, 163, 194},
- {283, 5, 195, 226},
- {284, 5, 227, 257},
- {285, 0, 258, 258},
- };
- static const coderecord distcodes[] = {
- {0, 0, 1, 1},
- {1, 0, 2, 2},
- {2, 0, 3, 3},
- {3, 0, 4, 4},
- {4, 1, 5, 6},
- {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 (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;
- 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 = lenof(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 = lenof(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);
- }
- }
- struct ssh_zlib_compressor {
- struct LZ77Context ectx;
- ssh_compressor sc;
- };
- static ssh_compressor *zlib_compress_init(void)
- {
- struct Outbuf *out;
- struct ssh_zlib_compressor *comp = snew(struct ssh_zlib_compressor);
- lz77_init(&comp->ectx);
- comp->sc.vt = &ssh_zlib;
- comp->ectx.literal = zlib_literal;
- comp->ectx.match = zlib_match;
- out = snew(struct Outbuf);
- out->outbuf = NULL;
- out->outbits = out->noutbits = 0;
- out->firstblock = true;
- comp->ectx.userdata = out;
- return &comp->sc;
- }
- static void zlib_compress_cleanup(ssh_compressor *sc)
- {
- struct ssh_zlib_compressor *comp =
- container_of(sc, struct ssh_zlib_compressor, sc);
- struct Outbuf *out = (struct Outbuf *)comp->ectx.userdata;
- if (out->outbuf)
- strbuf_free(out->outbuf);
- sfree(out);
- sfree(comp->ectx.ictx);
- sfree(comp);
- }
- static void zlib_compress_block(
- ssh_compressor *sc, const unsigned char *block, int len,
- unsigned char **outblock, int *outlen, int minlen)
- {
- struct ssh_zlib_compressor *comp =
- container_of(sc, struct ssh_zlib_compressor, sc);
- struct Outbuf *out = (struct Outbuf *) comp->ectx.userdata;
- bool in_block;
- assert(!out->outbuf);
- out->outbuf = strbuf_new_nm();
- /*
- * 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 = false;
- in_block = false;
- } else
- in_block = true;
- 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(&comp->ectx, block, len);
- /*
- * 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 */
- /*
- * If we've been asked to pad out the compressed data until it's
- * at least a given length, do so by emitting further empty static
- * blocks.
- */
- while (out->outbuf->len < minlen) {
- outbits(out, 0, 7); /* close block */
- outbits(out, 2, 3); /* open new static block */
- }
- *outlen = out->outbuf->len;
- *outblock = (unsigned char *)strbuf_to_str(out->outbuf);
- out->outbuf = NULL;
- }
- /* ----------------------------------------------------------------------
- * 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((size_t)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;
- 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];
- /*
- * Array that accumulates the code lengths sent in the header of a
- * dynamic-Huffman-tree block.
- *
- * There are 286 actual symbols in the literal/length alphabet
- * (256 literals plus 20 length categories), and 30 symbols in the
- * distance alphabet. However, the block header transmits the
- * number of code lengths for the former alphabet as a 5-bit value
- * HLIT to be added to 257, and the latter as a 5-bit value HDIST
- * to be added to 1. This means that the number of _code lengths_
- * can go as high as 288 for the symbol alphabet and 32 for the
- * distance alphabet - each of those values being 2 more than the
- * maximum number of actual symbols.
- *
- * It's tempting to rule that sending out-of-range HLIT or HDIST
- * is therefore just illegal, and to fault it when we initially
- * receive that header. But instead I've chosen to permit the
- * Huffman-code definition to include code length entries for
- * those unused symbols; if a header of that form is transmitted,
- * then the effect will be that in the main body of the block,
- * some bit sequence(s) will generate an illegal symbol number,
- * and _that_ will be faulted as a decoding error.
- *
- * Rationale: this can already happen! The standard Huffman code
- * used in a _static_ block for the literal/length alphabet is
- * defined in such a way that it includes codes for symbols 287
- * and 288, which are then never actually sent in the body of the
- * block. And I think that if the standard static tree definition
- * is willing to include Huffman codes that don't correspond to a
- * symbol, then it's an excessive restriction on dynamic tables
- * not to permit them to do the same. In particular, it would be
- * strange for a dynamic block not to be able to exactly mimic
- * either or both of the Huffman codes used by a static block for
- * the corresponding alphabet.
- *
- * So we place no constraint on HLIT or HDIST during code
- * construction, and we make this array large enough to include
- * the maximum number of code lengths that can possibly arise as a
- * result. It's only trying to _use_ the junk Huffman codes after
- * table construction is completed that will provoke a decode
- * error.
- */
- unsigned char lengths[288 + 32];
- unsigned long bits;
- int nbits;
- unsigned char window[WINSIZE];
- int winpos;
- strbuf *outblk;
- ssh_decompressor dc;
- };
- static ssh_decompressor *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;
- dctx->outblk = NULL;
- dctx->dc.vt = &ssh_zlib;
- return &dctx->dc;
- }
- static void zlib_decompress_cleanup(ssh_decompressor *dc)
- {
- struct zlib_decompress_ctx *dctx =
- container_of(dc, struct zlib_decompress_ctx, dc);
- 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);
- zlib_freetable(&dctx->staticlentable);
- zlib_freetable(&dctx->staticdisttable);
- if (dctx->outblk)
- strbuf_free(dctx->outblk);
- 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);
- put_byte(dctx->outblk, c);
- }
- #define EATBITS(n) ( dctx->nbits -= (n), dctx->bits >>= (n) )
- static bool zlib_decompress_block(
- ssh_decompressor *dc, const unsigned char *block, int len,
- unsigned char **outblock, int *outlen)
- {
- struct zlib_decompress_ctx *dctx =
- container_of(dc, struct zlib_decompress_ctx, dc);
- const coderecord *rec;
- int code, blktype, rep, dist, nlen, header;
- static const unsigned char lenlenmap[] = {
- 16, 17, 18, 0, 8, 7, 9, 6, 10, 5, 11, 4, 12, 3, 13, 2, 14, 1, 15
- };
- assert(!dctx->outblk);
- dctx->outblk = strbuf_new_nm();
- 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. */
- if (dctx->nbits < 16)
- goto finished; /* done all we can */
- /*
- * The header is stored as a big-endian 16-bit integer,
- * in contrast to the general little-endian policy in
- * the rest of the format :-(
- */
- header = (((dctx->bits & 0xFF00) >> 8) |
- ((dctx->bits & 0x00FF) << 8));
- EATBITS(16);
- /*
- * Check the header:
- *
- * - bits 8-11 should be 1000 (Deflate/RFC1951)
- * - bits 12-15 should be at most 0111 (window size)
- * - bit 5 should be zero (no dictionary present)
- * - we don't care about bits 6-7 (compression rate)
- * - bits 0-4 should be set up to make the whole thing
- * a multiple of 31 (checksum).
- */
- if ((header & 0x0F00) != 0x0800 ||
- (header & 0xF000) > 0x7000 ||
- (header & 0x0020) != 0x0000 ||
- (header % 31) != 0)
- goto decode_error;
- 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) {
- dctx->state = GOTLENSYM;
- dctx->sym = code;
- } else {
- /* literal/length symbols 286 and 287 are invalid */
- goto decode_error;
- }
- 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;
- if (code >= 30) /* dist symbols 30 and 31 are invalid */
- 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 != (nlen ^ 0xFFFF))
- goto decode_error;
- 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:
- *outlen = dctx->outblk->len;
- *outblock = (unsigned char *)strbuf_to_str(dctx->outblk);
- dctx->outblk = NULL;
- return true;
- decode_error:
- *outblock = NULL;
- *outlen = 0;
- return false;
- }
- const ssh_compression_alg ssh_zlib = {
- .name = "zlib",
- .delayed_name = "zlib@openssh.com", /* delayed version */
- .compress_new = zlib_compress_init,
- .compress_free = zlib_compress_cleanup,
- .compress = zlib_compress_block,
- .decompress_new = zlib_decompress_init,
- .decompress_free = zlib_decompress_cleanup,
- .decompress = zlib_decompress_block,
- .text_name = "zlib (RFC1950)",
- };
|