zlib.c 41 KB

12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576777879808182838485868788899091929394959697989910010110210310410510610710810911011111211311411511611711811912012112212312412512612712812913013113213313413513613713813914014114214314414514614714814915015115215315415515615715815916016116216316416516616716816917017117217317417517617717817918018118218318418518618718818919019119219319419519619719819920020120220320420520620720820921021121221321421521621721821922022122222322422522622722822923023123223323423523623723823924024124224324424524624724824925025125225325425525625725825926026126226326426526626726826927027127227327427527627727827928028128228328428528628728828929029129229329429529629729829930030130230330430530630730830931031131231331431531631731831932032132232332432532632732832933033133233333433533633733833934034134234334434534634734834935035135235335435535635735835936036136236336436536636736836937037137237337437537637737837938038138238338438538638738838939039139239339439539639739839940040140240340440540640740840941041141241341441541641741841942042142242342442542642742842943043143243343443543643743843944044144244344444544644744844945045145245345445545645745845946046146246346446546646746846947047147247347447547647747847948048148248348448548648748848949049149249349449549649749849950050150250350450550650750850951051151251351451551651751851952052152252352452552652752852953053153253353453553653753853954054154254354454554654754854955055155255355455555655755855956056156256356456556656756856957057157257357457557657757857958058158258358458558658758858959059159259359459559659759859960060160260360460560660760860961061161261361461561661761861962062162262362462562662762862963063163263363463563663763863964064164264364464564664764864965065165265365465565665765865966066166266366466566666766866967067167267367467567667767867968068168268368468568668768868969069169269369469569669769869970070170270370470570670770870971071171271371471571671771871972072172272372472572672772872973073173273373473573673773873974074174274374474574674774874975075175275375475575675775875976076176276376476576676776876977077177277377477577677777877978078178278378478578678778878979079179279379479579679779879980080180280380480580680780880981081181281381481581681781881982082182282382482582682782882983083183283383483583683783883984084184284384484584684784884985085185285385485585685785885986086186286386486586686786886987087187287387487587687787887988088188288388488588688788888989089189289389489589689789889990090190290390490590690790890991091191291391491591691791891992092192292392492592692792892993093193293393493593693793893994094194294394494594694794894995095195295395495595695795895996096196296396496596696796896997097197297397497597697797897998098198298398498598698798898999099199299399499599699799899910001001100210031004100510061007100810091010101110121013101410151016101710181019102010211022102310241025102610271028102910301031103210331034103510361037103810391040104110421043104410451046104710481049105010511052105310541055105610571058105910601061106210631064106510661067106810691070107110721073107410751076107710781079108010811082108310841085108610871088108910901091109210931094109510961097109810991100110111021103110411051106110711081109111011111112111311141115111611171118111911201121112211231124112511261127112811291130113111321133113411351136113711381139114011411142114311441145114611471148114911501151115211531154115511561157115811591160116111621163116411651166116711681169117011711172117311741175117611771178117911801181118211831184118511861187118811891190119111921193119411951196119711981199120012011202120312041205120612071208120912101211121212131214121512161217121812191220122112221223122412251226122712281229123012311232123312341235123612371238123912401241124212431244124512461247124812491250125112521253
  1. /*
  2. * Zlib (RFC1950 / RFC1951) compression for PuTTY.
  3. *
  4. * There will no doubt be criticism of my decision to reimplement
  5. * Zlib compression from scratch instead of using the existing zlib
  6. * code. People will cry `reinventing the wheel'; they'll claim
  7. * that the `fundamental basis of OSS' is code reuse; they'll want
  8. * to see a really good reason for me having chosen not to use the
  9. * existing code.
  10. *
  11. * Well, here are my reasons. Firstly, I don't want to link the
  12. * whole of zlib into the PuTTY binary; PuTTY is justifiably proud
  13. * of its small size and I think zlib contains a lot of unnecessary
  14. * baggage for the kind of compression that SSH requires.
  15. *
  16. * Secondly, I also don't like the alternative of using zlib.dll.
  17. * Another thing PuTTY is justifiably proud of is its ease of
  18. * installation, and the last thing I want to do is to start
  19. * mandating DLLs. Not only that, but there are two _kinds_ of
  20. * zlib.dll kicking around, one with C calling conventions on the
  21. * exported functions and another with WINAPI conventions, and
  22. * there would be a significant danger of getting the wrong one.
  23. *
  24. * Thirdly, there seems to be a difference of opinion on the IETF
  25. * secsh mailing list about the correct way to round off a
  26. * compressed packet and start the next. In particular, there's
  27. * some talk of switching to a mechanism zlib isn't currently
  28. * capable of supporting (see below for an explanation). Given that
  29. * sort of uncertainty, I thought it might be better to have code
  30. * that will support even the zlib-incompatible worst case.
  31. *
  32. * Fourthly, it's a _second implementation_. Second implementations
  33. * are fundamentally a Good Thing in standardisation efforts. The
  34. * difference of opinion mentioned above has arisen _precisely_
  35. * because there has been only one zlib implementation and
  36. * everybody has used it. I don't intend that this should happen
  37. * again.
  38. */
  39. #include <stdlib.h>
  40. #include <string.h>
  41. #include <assert.h>
  42. #include "defs.h"
  43. #include "ssh.h"
  44. /* ----------------------------------------------------------------------
  45. * Basic LZ77 code. This bit is designed modularly, so it could be
  46. * ripped out and used in a different LZ77 compressor. Go to it,
  47. * and good luck :-)
  48. */
  49. struct LZ77InternalContext;
  50. struct LZ77Context {
  51. struct LZ77InternalContext *ictx;
  52. void *userdata;
  53. void (*literal) (struct LZ77Context *ctx, unsigned char c);
  54. void (*match) (struct LZ77Context *ctx, int distance, int len);
  55. };
  56. /*
  57. * Initialise the private fields of an LZ77Context. It's up to the
  58. * user to initialise the public fields.
  59. */
  60. static int lz77_init(struct LZ77Context *ctx);
  61. /*
  62. * Supply data to be compressed. Will update the private fields of
  63. * the LZ77Context, and will call literal() and match() to output.
  64. * If `compress' is false, it will never emit a match, but will
  65. * instead call literal() for everything.
  66. */
  67. static void lz77_compress(struct LZ77Context *ctx,
  68. const unsigned char *data, int len);
  69. /*
  70. * Modifiable parameters.
  71. */
  72. #define WINSIZE 32768 /* window size. Must be power of 2! */
  73. #define HASHMAX 2039 /* one more than max hash value */
  74. #define MAXMATCH 32 /* how many matches we track */
  75. #define HASHCHARS 3 /* how many chars make a hash */
  76. /*
  77. * This compressor takes a less slapdash approach than the
  78. * gzip/zlib one. Rather than allowing our hash chains to fall into
  79. * disuse near the far end, we keep them doubly linked so we can
  80. * _find_ the far end, and then every time we add a new byte to the
  81. * window (thus rolling round by one and removing the previous
  82. * byte), we can carefully remove the hash chain entry.
  83. */
  84. #define INVALID -1 /* invalid hash _and_ invalid offset */
  85. struct WindowEntry {
  86. short next, prev; /* array indices within the window */
  87. short hashval;
  88. };
  89. struct HashEntry {
  90. short first; /* window index of first in chain */
  91. };
  92. struct Match {
  93. int distance, len;
  94. };
  95. struct LZ77InternalContext {
  96. struct WindowEntry win[WINSIZE];
  97. unsigned char data[WINSIZE];
  98. int winpos;
  99. struct HashEntry hashtab[HASHMAX];
  100. unsigned char pending[HASHCHARS];
  101. int npending;
  102. };
  103. static int lz77_hash(const unsigned char *data)
  104. {
  105. return (257 * data[0] + 263 * data[1] + 269 * data[2]) % HASHMAX;
  106. }
  107. static int lz77_init(struct LZ77Context *ctx)
  108. {
  109. struct LZ77InternalContext *st;
  110. int i;
  111. st = snew(struct LZ77InternalContext);
  112. if (!st)
  113. return 0;
  114. ctx->ictx = st;
  115. for (i = 0; i < WINSIZE; i++)
  116. st->win[i].next = st->win[i].prev = st->win[i].hashval = INVALID;
  117. for (i = 0; i < HASHMAX; i++)
  118. st->hashtab[i].first = INVALID;
  119. st->winpos = 0;
  120. st->npending = 0;
  121. return 1;
  122. }
  123. static void lz77_advance(struct LZ77InternalContext *st,
  124. unsigned char c, int hash)
  125. {
  126. int off;
  127. /*
  128. * Remove the hash entry at winpos from the tail of its chain,
  129. * or empty the chain if it's the only thing on the chain.
  130. */
  131. if (st->win[st->winpos].prev != INVALID) {
  132. st->win[st->win[st->winpos].prev].next = INVALID;
  133. } else if (st->win[st->winpos].hashval != INVALID) {
  134. st->hashtab[st->win[st->winpos].hashval].first = INVALID;
  135. }
  136. /*
  137. * Create a new entry at winpos and add it to the head of its
  138. * hash chain.
  139. */
  140. st->win[st->winpos].hashval = hash;
  141. st->win[st->winpos].prev = INVALID;
  142. off = st->win[st->winpos].next = st->hashtab[hash].first;
  143. st->hashtab[hash].first = st->winpos;
  144. if (off != INVALID)
  145. st->win[off].prev = st->winpos;
  146. st->data[st->winpos] = c;
  147. /*
  148. * Advance the window pointer.
  149. */
  150. st->winpos = (st->winpos + 1) & (WINSIZE - 1);
  151. }
  152. #define CHARAT(k) ( (k)<0 ? st->data[(st->winpos+k)&(WINSIZE-1)] : data[k] )
  153. static void lz77_compress(struct LZ77Context *ctx,
  154. const unsigned char *data, int len)
  155. {
  156. struct LZ77InternalContext *st = ctx->ictx;
  157. int i, distance, off, nmatch, matchlen, advance;
  158. struct Match defermatch, matches[MAXMATCH];
  159. int deferchr;
  160. assert(st->npending <= HASHCHARS);
  161. /*
  162. * Add any pending characters from last time to the window. (We
  163. * might not be able to.)
  164. *
  165. * This leaves st->pending empty in the usual case (when len >=
  166. * HASHCHARS); otherwise it leaves st->pending empty enough that
  167. * adding all the remaining 'len' characters will not push it past
  168. * HASHCHARS in size.
  169. */
  170. for (i = 0; i < st->npending; i++) {
  171. unsigned char foo[HASHCHARS];
  172. int j;
  173. if (len + st->npending - i < HASHCHARS) {
  174. /* Update the pending array. */
  175. for (j = i; j < st->npending; j++)
  176. st->pending[j - i] = st->pending[j];
  177. break;
  178. }
  179. for (j = 0; j < HASHCHARS; j++)
  180. foo[j] = (i + j < st->npending ? st->pending[i + j] :
  181. data[i + j - st->npending]);
  182. lz77_advance(st, foo[0], lz77_hash(foo));
  183. }
  184. st->npending -= i;
  185. defermatch.distance = 0; /* appease compiler */
  186. defermatch.len = 0;
  187. deferchr = '\0';
  188. while (len > 0) {
  189. if (len >= HASHCHARS) {
  190. /*
  191. * Hash the next few characters.
  192. */
  193. int hash = lz77_hash(data);
  194. /*
  195. * Look the hash up in the corresponding hash chain and see
  196. * what we can find.
  197. */
  198. nmatch = 0;
  199. for (off = st->hashtab[hash].first;
  200. off != INVALID; off = st->win[off].next) {
  201. /* distance = 1 if off == st->winpos-1 */
  202. /* distance = WINSIZE if off == st->winpos */
  203. distance =
  204. WINSIZE - (off + WINSIZE - st->winpos) % WINSIZE;
  205. for (i = 0; i < HASHCHARS; i++)
  206. if (CHARAT(i) != CHARAT(i - distance))
  207. break;
  208. if (i == HASHCHARS) {
  209. matches[nmatch].distance = distance;
  210. matches[nmatch].len = 3;
  211. if (++nmatch >= MAXMATCH)
  212. break;
  213. }
  214. }
  215. } else {
  216. nmatch = 0;
  217. }
  218. if (nmatch > 0) {
  219. /*
  220. * We've now filled up matches[] with nmatch potential
  221. * matches. Follow them down to find the longest. (We
  222. * assume here that it's always worth favouring a
  223. * longer match over a shorter one.)
  224. */
  225. matchlen = HASHCHARS;
  226. while (matchlen < len) {
  227. int j;
  228. for (i = j = 0; i < nmatch; i++) {
  229. if (CHARAT(matchlen) ==
  230. CHARAT(matchlen - matches[i].distance)) {
  231. matches[j++] = matches[i];
  232. }
  233. }
  234. if (j == 0)
  235. break;
  236. matchlen++;
  237. nmatch = j;
  238. }
  239. /*
  240. * We've now got all the longest matches. We favour the
  241. * shorter distances, which means we go with matches[0].
  242. * So see if we want to defer it or throw it away.
  243. */
  244. matches[0].len = matchlen;
  245. if (defermatch.len > 0) {
  246. if (matches[0].len > defermatch.len + 1) {
  247. /* We have a better match. Emit the deferred char,
  248. * and defer this match. */
  249. ctx->literal(ctx, (unsigned char) deferchr);
  250. defermatch = matches[0];
  251. deferchr = data[0];
  252. advance = 1;
  253. } else {
  254. /* We don't have a better match. Do the deferred one. */
  255. ctx->match(ctx, defermatch.distance, defermatch.len);
  256. advance = defermatch.len - 1;
  257. defermatch.len = 0;
  258. }
  259. } else {
  260. /* There was no deferred match. Defer this one. */
  261. defermatch = matches[0];
  262. deferchr = data[0];
  263. advance = 1;
  264. }
  265. } else {
  266. /*
  267. * We found no matches. Emit the deferred match, if
  268. * any; otherwise emit a literal.
  269. */
  270. if (defermatch.len > 0) {
  271. ctx->match(ctx, defermatch.distance, defermatch.len);
  272. advance = defermatch.len - 1;
  273. defermatch.len = 0;
  274. } else {
  275. ctx->literal(ctx, data[0]);
  276. advance = 1;
  277. }
  278. }
  279. /*
  280. * Now advance the position by `advance' characters,
  281. * keeping the window and hash chains consistent.
  282. */
  283. while (advance > 0) {
  284. if (len >= HASHCHARS) {
  285. lz77_advance(st, *data, lz77_hash(data));
  286. } else {
  287. assert(st->npending < HASHCHARS);
  288. st->pending[st->npending++] = *data;
  289. }
  290. data++;
  291. len--;
  292. advance--;
  293. }
  294. }
  295. }
  296. /* ----------------------------------------------------------------------
  297. * Zlib compression. We always use the static Huffman tree option.
  298. * Mostly this is because it's hard to scan a block in advance to
  299. * work out better trees; dynamic trees are great when you're
  300. * compressing a large file under no significant time constraint,
  301. * but when you're compressing little bits in real time, things get
  302. * hairier.
  303. *
  304. * I suppose it's possible that I could compute Huffman trees based
  305. * on the frequencies in the _previous_ block, as a sort of
  306. * heuristic, but I'm not confident that the gain would balance out
  307. * having to transmit the trees.
  308. */
  309. struct Outbuf {
  310. strbuf *outbuf;
  311. unsigned long outbits;
  312. int noutbits;
  313. bool firstblock;
  314. };
  315. static void outbits(struct Outbuf *out, unsigned long bits, int nbits)
  316. {
  317. assert(out->noutbits + nbits <= 32);
  318. out->outbits |= bits << out->noutbits;
  319. out->noutbits += nbits;
  320. while (out->noutbits >= 8) {
  321. put_byte(out->outbuf, out->outbits & 0xFF);
  322. out->outbits >>= 8;
  323. out->noutbits -= 8;
  324. }
  325. }
  326. static const unsigned char mirrorbytes[256] = {
  327. 0x00, 0x80, 0x40, 0xc0, 0x20, 0xa0, 0x60, 0xe0,
  328. 0x10, 0x90, 0x50, 0xd0, 0x30, 0xb0, 0x70, 0xf0,
  329. 0x08, 0x88, 0x48, 0xc8, 0x28, 0xa8, 0x68, 0xe8,
  330. 0x18, 0x98, 0x58, 0xd8, 0x38, 0xb8, 0x78, 0xf8,
  331. 0x04, 0x84, 0x44, 0xc4, 0x24, 0xa4, 0x64, 0xe4,
  332. 0x14, 0x94, 0x54, 0xd4, 0x34, 0xb4, 0x74, 0xf4,
  333. 0x0c, 0x8c, 0x4c, 0xcc, 0x2c, 0xac, 0x6c, 0xec,
  334. 0x1c, 0x9c, 0x5c, 0xdc, 0x3c, 0xbc, 0x7c, 0xfc,
  335. 0x02, 0x82, 0x42, 0xc2, 0x22, 0xa2, 0x62, 0xe2,
  336. 0x12, 0x92, 0x52, 0xd2, 0x32, 0xb2, 0x72, 0xf2,
  337. 0x0a, 0x8a, 0x4a, 0xca, 0x2a, 0xaa, 0x6a, 0xea,
  338. 0x1a, 0x9a, 0x5a, 0xda, 0x3a, 0xba, 0x7a, 0xfa,
  339. 0x06, 0x86, 0x46, 0xc6, 0x26, 0xa6, 0x66, 0xe6,
  340. 0x16, 0x96, 0x56, 0xd6, 0x36, 0xb6, 0x76, 0xf6,
  341. 0x0e, 0x8e, 0x4e, 0xce, 0x2e, 0xae, 0x6e, 0xee,
  342. 0x1e, 0x9e, 0x5e, 0xde, 0x3e, 0xbe, 0x7e, 0xfe,
  343. 0x01, 0x81, 0x41, 0xc1, 0x21, 0xa1, 0x61, 0xe1,
  344. 0x11, 0x91, 0x51, 0xd1, 0x31, 0xb1, 0x71, 0xf1,
  345. 0x09, 0x89, 0x49, 0xc9, 0x29, 0xa9, 0x69, 0xe9,
  346. 0x19, 0x99, 0x59, 0xd9, 0x39, 0xb9, 0x79, 0xf9,
  347. 0x05, 0x85, 0x45, 0xc5, 0x25, 0xa5, 0x65, 0xe5,
  348. 0x15, 0x95, 0x55, 0xd5, 0x35, 0xb5, 0x75, 0xf5,
  349. 0x0d, 0x8d, 0x4d, 0xcd, 0x2d, 0xad, 0x6d, 0xed,
  350. 0x1d, 0x9d, 0x5d, 0xdd, 0x3d, 0xbd, 0x7d, 0xfd,
  351. 0x03, 0x83, 0x43, 0xc3, 0x23, 0xa3, 0x63, 0xe3,
  352. 0x13, 0x93, 0x53, 0xd3, 0x33, 0xb3, 0x73, 0xf3,
  353. 0x0b, 0x8b, 0x4b, 0xcb, 0x2b, 0xab, 0x6b, 0xeb,
  354. 0x1b, 0x9b, 0x5b, 0xdb, 0x3b, 0xbb, 0x7b, 0xfb,
  355. 0x07, 0x87, 0x47, 0xc7, 0x27, 0xa7, 0x67, 0xe7,
  356. 0x17, 0x97, 0x57, 0xd7, 0x37, 0xb7, 0x77, 0xf7,
  357. 0x0f, 0x8f, 0x4f, 0xcf, 0x2f, 0xaf, 0x6f, 0xef,
  358. 0x1f, 0x9f, 0x5f, 0xdf, 0x3f, 0xbf, 0x7f, 0xff,
  359. };
  360. typedef struct {
  361. short code, extrabits;
  362. int min, max;
  363. } coderecord;
  364. static const coderecord lencodes[] = {
  365. {257, 0, 3, 3},
  366. {258, 0, 4, 4},
  367. {259, 0, 5, 5},
  368. {260, 0, 6, 6},
  369. {261, 0, 7, 7},
  370. {262, 0, 8, 8},
  371. {263, 0, 9, 9},
  372. {264, 0, 10, 10},
  373. {265, 1, 11, 12},
  374. {266, 1, 13, 14},
  375. {267, 1, 15, 16},
  376. {268, 1, 17, 18},
  377. {269, 2, 19, 22},
  378. {270, 2, 23, 26},
  379. {271, 2, 27, 30},
  380. {272, 2, 31, 34},
  381. {273, 3, 35, 42},
  382. {274, 3, 43, 50},
  383. {275, 3, 51, 58},
  384. {276, 3, 59, 66},
  385. {277, 4, 67, 82},
  386. {278, 4, 83, 98},
  387. {279, 4, 99, 114},
  388. {280, 4, 115, 130},
  389. {281, 5, 131, 162},
  390. {282, 5, 163, 194},
  391. {283, 5, 195, 226},
  392. {284, 5, 227, 257},
  393. {285, 0, 258, 258},
  394. };
  395. static const coderecord distcodes[] = {
  396. {0, 0, 1, 1},
  397. {1, 0, 2, 2},
  398. {2, 0, 3, 3},
  399. {3, 0, 4, 4},
  400. {4, 1, 5, 6},
  401. {5, 1, 7, 8},
  402. {6, 2, 9, 12},
  403. {7, 2, 13, 16},
  404. {8, 3, 17, 24},
  405. {9, 3, 25, 32},
  406. {10, 4, 33, 48},
  407. {11, 4, 49, 64},
  408. {12, 5, 65, 96},
  409. {13, 5, 97, 128},
  410. {14, 6, 129, 192},
  411. {15, 6, 193, 256},
  412. {16, 7, 257, 384},
  413. {17, 7, 385, 512},
  414. {18, 8, 513, 768},
  415. {19, 8, 769, 1024},
  416. {20, 9, 1025, 1536},
  417. {21, 9, 1537, 2048},
  418. {22, 10, 2049, 3072},
  419. {23, 10, 3073, 4096},
  420. {24, 11, 4097, 6144},
  421. {25, 11, 6145, 8192},
  422. {26, 12, 8193, 12288},
  423. {27, 12, 12289, 16384},
  424. {28, 13, 16385, 24576},
  425. {29, 13, 24577, 32768},
  426. };
  427. static void zlib_literal(struct LZ77Context *ectx, unsigned char c)
  428. {
  429. struct Outbuf *out = (struct Outbuf *) ectx->userdata;
  430. if (c <= 143) {
  431. /* 0 through 143 are 8 bits long starting at 00110000. */
  432. outbits(out, mirrorbytes[0x30 + c], 8);
  433. } else {
  434. /* 144 through 255 are 9 bits long starting at 110010000. */
  435. outbits(out, 1 + 2 * mirrorbytes[0x90 - 144 + c], 9);
  436. }
  437. }
  438. static void zlib_match(struct LZ77Context *ectx, int distance, int len)
  439. {
  440. const coderecord *d, *l;
  441. int i, j, k;
  442. struct Outbuf *out = (struct Outbuf *) ectx->userdata;
  443. while (len > 0) {
  444. int thislen;
  445. /*
  446. * We can transmit matches of lengths 3 through 258
  447. * inclusive. So if len exceeds 258, we must transmit in
  448. * several steps, with 258 or less in each step.
  449. *
  450. * Specifically: if len >= 261, we can transmit 258 and be
  451. * sure of having at least 3 left for the next step. And if
  452. * len <= 258, we can just transmit len. But if len == 259
  453. * or 260, we must transmit len-3.
  454. */
  455. thislen = (len > 260 ? 258 : len <= 258 ? len : len - 3);
  456. len -= thislen;
  457. /*
  458. * Binary-search to find which length code we're
  459. * transmitting.
  460. */
  461. i = -1;
  462. j = lenof(lencodes);
  463. while (1) {
  464. assert(j - i >= 2);
  465. k = (j + i) / 2;
  466. if (thislen < lencodes[k].min)
  467. j = k;
  468. else if (thislen > lencodes[k].max)
  469. i = k;
  470. else {
  471. l = &lencodes[k];
  472. break; /* found it! */
  473. }
  474. }
  475. /*
  476. * Transmit the length code. 256-279 are seven bits
  477. * starting at 0000000; 280-287 are eight bits starting at
  478. * 11000000.
  479. */
  480. if (l->code <= 279) {
  481. outbits(out, mirrorbytes[(l->code - 256) * 2], 7);
  482. } else {
  483. outbits(out, mirrorbytes[0xc0 - 280 + l->code], 8);
  484. }
  485. /*
  486. * Transmit the extra bits.
  487. */
  488. if (l->extrabits)
  489. outbits(out, thislen - l->min, l->extrabits);
  490. /*
  491. * Binary-search to find which distance code we're
  492. * transmitting.
  493. */
  494. i = -1;
  495. j = lenof(distcodes);
  496. while (1) {
  497. assert(j - i >= 2);
  498. k = (j + i) / 2;
  499. if (distance < distcodes[k].min)
  500. j = k;
  501. else if (distance > distcodes[k].max)
  502. i = k;
  503. else {
  504. d = &distcodes[k];
  505. break; /* found it! */
  506. }
  507. }
  508. /*
  509. * Transmit the distance code. Five bits starting at 00000.
  510. */
  511. outbits(out, mirrorbytes[d->code * 8], 5);
  512. /*
  513. * Transmit the extra bits.
  514. */
  515. if (d->extrabits)
  516. outbits(out, distance - d->min, d->extrabits);
  517. }
  518. }
  519. struct ssh_zlib_compressor {
  520. struct LZ77Context ectx;
  521. ssh_compressor sc;
  522. };
  523. static ssh_compressor *zlib_compress_init(void)
  524. {
  525. struct Outbuf *out;
  526. struct ssh_zlib_compressor *comp = snew(struct ssh_zlib_compressor);
  527. lz77_init(&comp->ectx);
  528. comp->sc.vt = &ssh_zlib;
  529. comp->ectx.literal = zlib_literal;
  530. comp->ectx.match = zlib_match;
  531. out = snew(struct Outbuf);
  532. out->outbuf = NULL;
  533. out->outbits = out->noutbits = 0;
  534. out->firstblock = true;
  535. comp->ectx.userdata = out;
  536. return &comp->sc;
  537. }
  538. static void zlib_compress_cleanup(ssh_compressor *sc)
  539. {
  540. struct ssh_zlib_compressor *comp =
  541. container_of(sc, struct ssh_zlib_compressor, sc);
  542. struct Outbuf *out = (struct Outbuf *)comp->ectx.userdata;
  543. if (out->outbuf)
  544. strbuf_free(out->outbuf);
  545. sfree(out);
  546. sfree(comp->ectx.ictx);
  547. sfree(comp);
  548. }
  549. static void zlib_compress_block(
  550. ssh_compressor *sc, const unsigned char *block, int len,
  551. unsigned char **outblock, int *outlen, int minlen)
  552. {
  553. struct ssh_zlib_compressor *comp =
  554. container_of(sc, struct ssh_zlib_compressor, sc);
  555. struct Outbuf *out = (struct Outbuf *) comp->ectx.userdata;
  556. bool in_block;
  557. assert(!out->outbuf);
  558. out->outbuf = strbuf_new_nm();
  559. /*
  560. * If this is the first block, output the Zlib (RFC1950) header
  561. * bytes 78 9C. (Deflate compression, 32K window size, default
  562. * algorithm.)
  563. */
  564. if (out->firstblock) {
  565. outbits(out, 0x9C78, 16);
  566. out->firstblock = false;
  567. in_block = false;
  568. } else
  569. in_block = true;
  570. if (!in_block) {
  571. /*
  572. * Start a Deflate (RFC1951) fixed-trees block. We
  573. * transmit a zero bit (BFINAL=0), followed by a zero
  574. * bit and a one bit (BTYPE=01). Of course these are in
  575. * the wrong order (01 0).
  576. */
  577. outbits(out, 2, 3);
  578. }
  579. /*
  580. * Do the compression.
  581. */
  582. lz77_compress(&comp->ectx, block, len);
  583. /*
  584. * End the block (by transmitting code 256, which is
  585. * 0000000 in fixed-tree mode), and transmit some empty
  586. * blocks to ensure we have emitted the byte containing the
  587. * last piece of genuine data. There are three ways we can
  588. * do this:
  589. *
  590. * - Minimal flush. Output end-of-block and then open a
  591. * new static block. This takes 9 bits, which is
  592. * guaranteed to flush out the last genuine code in the
  593. * closed block; but allegedly zlib can't handle it.
  594. *
  595. * - Zlib partial flush. Output EOB, open and close an
  596. * empty static block, and _then_ open the new block.
  597. * This is the best zlib can handle.
  598. *
  599. * - Zlib sync flush. Output EOB, then an empty
  600. * _uncompressed_ block (000, then sync to byte
  601. * boundary, then send bytes 00 00 FF FF). Then open the
  602. * new block.
  603. *
  604. * For the moment, we will use Zlib partial flush.
  605. */
  606. outbits(out, 0, 7); /* close block */
  607. outbits(out, 2, 3 + 7); /* empty static block */
  608. outbits(out, 2, 3); /* open new block */
  609. /*
  610. * If we've been asked to pad out the compressed data until it's
  611. * at least a given length, do so by emitting further empty static
  612. * blocks.
  613. */
  614. while (out->outbuf->len < minlen) {
  615. outbits(out, 0, 7); /* close block */
  616. outbits(out, 2, 3); /* open new static block */
  617. }
  618. *outlen = out->outbuf->len;
  619. *outblock = (unsigned char *)strbuf_to_str(out->outbuf);
  620. out->outbuf = NULL;
  621. }
  622. /* ----------------------------------------------------------------------
  623. * Zlib decompression. Of course, even though our compressor always
  624. * uses static trees, our _decompressor_ has to be capable of
  625. * handling dynamic trees if it sees them.
  626. */
  627. /*
  628. * The way we work the Huffman decode is to have a table lookup on
  629. * the first N bits of the input stream (in the order they arrive,
  630. * of course, i.e. the first bit of the Huffman code is in bit 0).
  631. * Each table entry lists the number of bits to consume, plus
  632. * either an output code or a pointer to a secondary table.
  633. */
  634. struct zlib_table;
  635. struct zlib_tableentry;
  636. struct zlib_tableentry {
  637. unsigned char nbits;
  638. short code;
  639. struct zlib_table *nexttable;
  640. };
  641. struct zlib_table {
  642. int mask; /* mask applied to input bit stream */
  643. struct zlib_tableentry *table;
  644. };
  645. #define MAXCODELEN 16
  646. #define MAXSYMS 288
  647. /*
  648. * Build a single-level decode table for elements
  649. * [minlength,maxlength) of the provided code/length tables, and
  650. * recurse to build subtables.
  651. */
  652. static struct zlib_table *zlib_mkonetab(int *codes, unsigned char *lengths,
  653. int nsyms,
  654. int pfx, int pfxbits, int bits)
  655. {
  656. struct zlib_table *tab = snew(struct zlib_table);
  657. int pfxmask = (1 << pfxbits) - 1;
  658. int nbits, i, j, code;
  659. tab->table = snewn((size_t)1 << bits, struct zlib_tableentry);
  660. tab->mask = (1 << bits) - 1;
  661. for (code = 0; code <= tab->mask; code++) {
  662. tab->table[code].code = -1;
  663. tab->table[code].nbits = 0;
  664. tab->table[code].nexttable = NULL;
  665. }
  666. for (i = 0; i < nsyms; i++) {
  667. if (lengths[i] <= pfxbits || (codes[i] & pfxmask) != pfx)
  668. continue;
  669. code = (codes[i] >> pfxbits) & tab->mask;
  670. for (j = code; j <= tab->mask; j += 1 << (lengths[i] - pfxbits)) {
  671. tab->table[j].code = i;
  672. nbits = lengths[i] - pfxbits;
  673. if (tab->table[j].nbits < nbits)
  674. tab->table[j].nbits = nbits;
  675. }
  676. }
  677. for (code = 0; code <= tab->mask; code++) {
  678. if (tab->table[code].nbits <= bits)
  679. continue;
  680. /* Generate a subtable. */
  681. tab->table[code].code = -1;
  682. nbits = tab->table[code].nbits - bits;
  683. if (nbits > 7)
  684. nbits = 7;
  685. tab->table[code].nbits = bits;
  686. tab->table[code].nexttable = zlib_mkonetab(codes, lengths, nsyms,
  687. pfx | (code << pfxbits),
  688. pfxbits + bits, nbits);
  689. }
  690. return tab;
  691. }
  692. /*
  693. * Build a decode table, given a set of Huffman tree lengths.
  694. */
  695. static struct zlib_table *zlib_mktable(unsigned char *lengths,
  696. int nlengths)
  697. {
  698. int count[MAXCODELEN], startcode[MAXCODELEN], codes[MAXSYMS];
  699. int code, maxlen;
  700. int i, j;
  701. /* Count the codes of each length. */
  702. maxlen = 0;
  703. for (i = 1; i < MAXCODELEN; i++)
  704. count[i] = 0;
  705. for (i = 0; i < nlengths; i++) {
  706. count[lengths[i]]++;
  707. if (maxlen < lengths[i])
  708. maxlen = lengths[i];
  709. }
  710. /* Determine the starting code for each length block. */
  711. code = 0;
  712. for (i = 1; i < MAXCODELEN; i++) {
  713. startcode[i] = code;
  714. code += count[i];
  715. code <<= 1;
  716. }
  717. /* Determine the code for each symbol. Mirrored, of course. */
  718. for (i = 0; i < nlengths; i++) {
  719. code = startcode[lengths[i]]++;
  720. codes[i] = 0;
  721. for (j = 0; j < lengths[i]; j++) {
  722. codes[i] = (codes[i] << 1) | (code & 1);
  723. code >>= 1;
  724. }
  725. }
  726. /*
  727. * Now we have the complete list of Huffman codes. Build a
  728. * table.
  729. */
  730. return zlib_mkonetab(codes, lengths, nlengths, 0, 0,
  731. maxlen < 9 ? maxlen : 9);
  732. }
  733. static int zlib_freetable(struct zlib_table **ztab)
  734. {
  735. struct zlib_table *tab;
  736. int code;
  737. if (ztab == NULL)
  738. return -1;
  739. if (*ztab == NULL)
  740. return 0;
  741. tab = *ztab;
  742. for (code = 0; code <= tab->mask; code++)
  743. if (tab->table[code].nexttable != NULL)
  744. zlib_freetable(&tab->table[code].nexttable);
  745. sfree(tab->table);
  746. tab->table = NULL;
  747. sfree(tab);
  748. *ztab = NULL;
  749. return (0);
  750. }
  751. struct zlib_decompress_ctx {
  752. struct zlib_table *staticlentable, *staticdisttable;
  753. struct zlib_table *currlentable, *currdisttable, *lenlentable;
  754. enum {
  755. START, OUTSIDEBLK,
  756. TREES_HDR, TREES_LENLEN, TREES_LEN, TREES_LENREP,
  757. INBLK, GOTLENSYM, GOTLEN, GOTDISTSYM,
  758. UNCOMP_LEN, UNCOMP_NLEN, UNCOMP_DATA
  759. } state;
  760. int sym, hlit, hdist, hclen, lenptr, lenextrabits, lenaddon, len,
  761. lenrep;
  762. int uncomplen;
  763. unsigned char lenlen[19];
  764. /*
  765. * Array that accumulates the code lengths sent in the header of a
  766. * dynamic-Huffman-tree block.
  767. *
  768. * There are 286 actual symbols in the literal/length alphabet
  769. * (256 literals plus 20 length categories), and 30 symbols in the
  770. * distance alphabet. However, the block header transmits the
  771. * number of code lengths for the former alphabet as a 5-bit value
  772. * HLIT to be added to 257, and the latter as a 5-bit value HDIST
  773. * to be added to 1. This means that the number of _code lengths_
  774. * can go as high as 288 for the symbol alphabet and 32 for the
  775. * distance alphabet - each of those values being 2 more than the
  776. * maximum number of actual symbols.
  777. *
  778. * It's tempting to rule that sending out-of-range HLIT or HDIST
  779. * is therefore just illegal, and to fault it when we initially
  780. * receive that header. But instead I've chosen to permit the
  781. * Huffman-code definition to include code length entries for
  782. * those unused symbols; if a header of that form is transmitted,
  783. * then the effect will be that in the main body of the block,
  784. * some bit sequence(s) will generate an illegal symbol number,
  785. * and _that_ will be faulted as a decoding error.
  786. *
  787. * Rationale: this can already happen! The standard Huffman code
  788. * used in a _static_ block for the literal/length alphabet is
  789. * defined in such a way that it includes codes for symbols 287
  790. * and 288, which are then never actually sent in the body of the
  791. * block. And I think that if the standard static tree definition
  792. * is willing to include Huffman codes that don't correspond to a
  793. * symbol, then it's an excessive restriction on dynamic tables
  794. * not to permit them to do the same. In particular, it would be
  795. * strange for a dynamic block not to be able to exactly mimic
  796. * either or both of the Huffman codes used by a static block for
  797. * the corresponding alphabet.
  798. *
  799. * So we place no constraint on HLIT or HDIST during code
  800. * construction, and we make this array large enough to include
  801. * the maximum number of code lengths that can possibly arise as a
  802. * result. It's only trying to _use_ the junk Huffman codes after
  803. * table construction is completed that will provoke a decode
  804. * error.
  805. */
  806. unsigned char lengths[288 + 32];
  807. unsigned long bits;
  808. int nbits;
  809. unsigned char window[WINSIZE];
  810. int winpos;
  811. strbuf *outblk;
  812. ssh_decompressor dc;
  813. };
  814. static ssh_decompressor *zlib_decompress_init(void)
  815. {
  816. struct zlib_decompress_ctx *dctx = snew(struct zlib_decompress_ctx);
  817. unsigned char lengths[288];
  818. memset(lengths, 8, 144);
  819. memset(lengths + 144, 9, 256 - 144);
  820. memset(lengths + 256, 7, 280 - 256);
  821. memset(lengths + 280, 8, 288 - 280);
  822. dctx->staticlentable = zlib_mktable(lengths, 288);
  823. memset(lengths, 5, 32);
  824. dctx->staticdisttable = zlib_mktable(lengths, 32);
  825. dctx->state = START; /* even before header */
  826. dctx->currlentable = dctx->currdisttable = dctx->lenlentable = NULL;
  827. dctx->bits = 0;
  828. dctx->nbits = 0;
  829. dctx->winpos = 0;
  830. dctx->outblk = NULL;
  831. dctx->dc.vt = &ssh_zlib;
  832. return &dctx->dc;
  833. }
  834. static void zlib_decompress_cleanup(ssh_decompressor *dc)
  835. {
  836. struct zlib_decompress_ctx *dctx =
  837. container_of(dc, struct zlib_decompress_ctx, dc);
  838. if (dctx->currlentable && dctx->currlentable != dctx->staticlentable)
  839. zlib_freetable(&dctx->currlentable);
  840. if (dctx->currdisttable && dctx->currdisttable != dctx->staticdisttable)
  841. zlib_freetable(&dctx->currdisttable);
  842. if (dctx->lenlentable)
  843. zlib_freetable(&dctx->lenlentable);
  844. zlib_freetable(&dctx->staticlentable);
  845. zlib_freetable(&dctx->staticdisttable);
  846. if (dctx->outblk)
  847. strbuf_free(dctx->outblk);
  848. sfree(dctx);
  849. }
  850. static int zlib_huflookup(unsigned long *bitsp, int *nbitsp,
  851. struct zlib_table *tab)
  852. {
  853. unsigned long bits = *bitsp;
  854. int nbits = *nbitsp;
  855. while (1) {
  856. struct zlib_tableentry *ent;
  857. ent = &tab->table[bits & tab->mask];
  858. if (ent->nbits > nbits)
  859. return -1; /* not enough data */
  860. bits >>= ent->nbits;
  861. nbits -= ent->nbits;
  862. if (ent->code == -1)
  863. tab = ent->nexttable;
  864. else {
  865. *bitsp = bits;
  866. *nbitsp = nbits;
  867. return ent->code;
  868. }
  869. if (!tab) {
  870. /*
  871. * There was a missing entry in the table, presumably
  872. * due to an invalid Huffman table description, and the
  873. * subsequent data has attempted to use the missing
  874. * entry. Return a decoding failure.
  875. */
  876. return -2;
  877. }
  878. }
  879. }
  880. static void zlib_emit_char(struct zlib_decompress_ctx *dctx, int c)
  881. {
  882. dctx->window[dctx->winpos] = c;
  883. dctx->winpos = (dctx->winpos + 1) & (WINSIZE - 1);
  884. put_byte(dctx->outblk, c);
  885. }
  886. #define EATBITS(n) ( dctx->nbits -= (n), dctx->bits >>= (n) )
  887. static bool zlib_decompress_block(
  888. ssh_decompressor *dc, const unsigned char *block, int len,
  889. unsigned char **outblock, int *outlen)
  890. {
  891. struct zlib_decompress_ctx *dctx =
  892. container_of(dc, struct zlib_decompress_ctx, dc);
  893. const coderecord *rec;
  894. int code, blktype, rep, dist, nlen, header;
  895. static const unsigned char lenlenmap[] = {
  896. 16, 17, 18, 0, 8, 7, 9, 6, 10, 5, 11, 4, 12, 3, 13, 2, 14, 1, 15
  897. };
  898. assert(!dctx->outblk);
  899. dctx->outblk = strbuf_new_nm();
  900. while (len > 0 || dctx->nbits > 0) {
  901. while (dctx->nbits < 24 && len > 0) {
  902. dctx->bits |= (*block++) << dctx->nbits;
  903. dctx->nbits += 8;
  904. len--;
  905. }
  906. switch (dctx->state) {
  907. case START:
  908. /* Expect 16-bit zlib header. */
  909. if (dctx->nbits < 16)
  910. goto finished; /* done all we can */
  911. /*
  912. * The header is stored as a big-endian 16-bit integer,
  913. * in contrast to the general little-endian policy in
  914. * the rest of the format :-(
  915. */
  916. header = (((dctx->bits & 0xFF00) >> 8) |
  917. ((dctx->bits & 0x00FF) << 8));
  918. EATBITS(16);
  919. /*
  920. * Check the header:
  921. *
  922. * - bits 8-11 should be 1000 (Deflate/RFC1951)
  923. * - bits 12-15 should be at most 0111 (window size)
  924. * - bit 5 should be zero (no dictionary present)
  925. * - we don't care about bits 6-7 (compression rate)
  926. * - bits 0-4 should be set up to make the whole thing
  927. * a multiple of 31 (checksum).
  928. */
  929. if ((header & 0x0F00) != 0x0800 ||
  930. (header & 0xF000) > 0x7000 ||
  931. (header & 0x0020) != 0x0000 ||
  932. (header % 31) != 0)
  933. goto decode_error;
  934. dctx->state = OUTSIDEBLK;
  935. break;
  936. case OUTSIDEBLK:
  937. /* Expect 3-bit block header. */
  938. if (dctx->nbits < 3)
  939. goto finished; /* done all we can */
  940. EATBITS(1);
  941. blktype = dctx->bits & 3;
  942. EATBITS(2);
  943. if (blktype == 0) {
  944. int to_eat = dctx->nbits & 7;
  945. dctx->state = UNCOMP_LEN;
  946. EATBITS(to_eat); /* align to byte boundary */
  947. } else if (blktype == 1) {
  948. dctx->currlentable = dctx->staticlentable;
  949. dctx->currdisttable = dctx->staticdisttable;
  950. dctx->state = INBLK;
  951. } else if (blktype == 2) {
  952. dctx->state = TREES_HDR;
  953. }
  954. break;
  955. case TREES_HDR:
  956. /*
  957. * Dynamic block header. Five bits of HLIT, five of
  958. * HDIST, four of HCLEN.
  959. */
  960. if (dctx->nbits < 5 + 5 + 4)
  961. goto finished; /* done all we can */
  962. dctx->hlit = 257 + (dctx->bits & 31);
  963. EATBITS(5);
  964. dctx->hdist = 1 + (dctx->bits & 31);
  965. EATBITS(5);
  966. dctx->hclen = 4 + (dctx->bits & 15);
  967. EATBITS(4);
  968. dctx->lenptr = 0;
  969. dctx->state = TREES_LENLEN;
  970. memset(dctx->lenlen, 0, sizeof(dctx->lenlen));
  971. break;
  972. case TREES_LENLEN:
  973. if (dctx->nbits < 3)
  974. goto finished;
  975. while (dctx->lenptr < dctx->hclen && dctx->nbits >= 3) {
  976. dctx->lenlen[lenlenmap[dctx->lenptr++]] =
  977. (unsigned char) (dctx->bits & 7);
  978. EATBITS(3);
  979. }
  980. if (dctx->lenptr == dctx->hclen) {
  981. dctx->lenlentable = zlib_mktable(dctx->lenlen, 19);
  982. dctx->state = TREES_LEN;
  983. dctx->lenptr = 0;
  984. }
  985. break;
  986. case TREES_LEN:
  987. if (dctx->lenptr >= dctx->hlit + dctx->hdist) {
  988. dctx->currlentable = zlib_mktable(dctx->lengths, dctx->hlit);
  989. dctx->currdisttable = zlib_mktable(dctx->lengths + dctx->hlit,
  990. dctx->hdist);
  991. zlib_freetable(&dctx->lenlentable);
  992. dctx->lenlentable = NULL;
  993. dctx->state = INBLK;
  994. break;
  995. }
  996. code =
  997. zlib_huflookup(&dctx->bits, &dctx->nbits, dctx->lenlentable);
  998. if (code == -1)
  999. goto finished;
  1000. if (code == -2)
  1001. goto decode_error;
  1002. if (code < 16)
  1003. dctx->lengths[dctx->lenptr++] = code;
  1004. else {
  1005. dctx->lenextrabits = (code == 16 ? 2 : code == 17 ? 3 : 7);
  1006. dctx->lenaddon = (code == 18 ? 11 : 3);
  1007. dctx->lenrep = (code == 16 && dctx->lenptr > 0 ?
  1008. dctx->lengths[dctx->lenptr - 1] : 0);
  1009. dctx->state = TREES_LENREP;
  1010. }
  1011. break;
  1012. case TREES_LENREP:
  1013. if (dctx->nbits < dctx->lenextrabits)
  1014. goto finished;
  1015. rep =
  1016. dctx->lenaddon +
  1017. (dctx->bits & ((1 << dctx->lenextrabits) - 1));
  1018. EATBITS(dctx->lenextrabits);
  1019. while (rep > 0 && dctx->lenptr < dctx->hlit + dctx->hdist) {
  1020. dctx->lengths[dctx->lenptr] = dctx->lenrep;
  1021. dctx->lenptr++;
  1022. rep--;
  1023. }
  1024. dctx->state = TREES_LEN;
  1025. break;
  1026. case INBLK:
  1027. code =
  1028. zlib_huflookup(&dctx->bits, &dctx->nbits, dctx->currlentable);
  1029. if (code == -1)
  1030. goto finished;
  1031. if (code == -2)
  1032. goto decode_error;
  1033. if (code < 256)
  1034. zlib_emit_char(dctx, code);
  1035. else if (code == 256) {
  1036. dctx->state = OUTSIDEBLK;
  1037. if (dctx->currlentable != dctx->staticlentable) {
  1038. zlib_freetable(&dctx->currlentable);
  1039. dctx->currlentable = NULL;
  1040. }
  1041. if (dctx->currdisttable != dctx->staticdisttable) {
  1042. zlib_freetable(&dctx->currdisttable);
  1043. dctx->currdisttable = NULL;
  1044. }
  1045. } else if (code < 286) {
  1046. dctx->state = GOTLENSYM;
  1047. dctx->sym = code;
  1048. } else {
  1049. /* literal/length symbols 286 and 287 are invalid */
  1050. goto decode_error;
  1051. }
  1052. break;
  1053. case GOTLENSYM:
  1054. rec = &lencodes[dctx->sym - 257];
  1055. if (dctx->nbits < rec->extrabits)
  1056. goto finished;
  1057. dctx->len =
  1058. rec->min + (dctx->bits & ((1 << rec->extrabits) - 1));
  1059. EATBITS(rec->extrabits);
  1060. dctx->state = GOTLEN;
  1061. break;
  1062. case GOTLEN:
  1063. code =
  1064. zlib_huflookup(&dctx->bits, &dctx->nbits,
  1065. dctx->currdisttable);
  1066. if (code == -1)
  1067. goto finished;
  1068. if (code == -2)
  1069. goto decode_error;
  1070. if (code >= 30) /* dist symbols 30 and 31 are invalid */
  1071. goto decode_error;
  1072. dctx->state = GOTDISTSYM;
  1073. dctx->sym = code;
  1074. break;
  1075. case GOTDISTSYM:
  1076. rec = &distcodes[dctx->sym];
  1077. if (dctx->nbits < rec->extrabits)
  1078. goto finished;
  1079. dist = rec->min + (dctx->bits & ((1 << rec->extrabits) - 1));
  1080. EATBITS(rec->extrabits);
  1081. dctx->state = INBLK;
  1082. while (dctx->len--)
  1083. zlib_emit_char(dctx, dctx->window[(dctx->winpos - dist) &
  1084. (WINSIZE - 1)]);
  1085. break;
  1086. case UNCOMP_LEN:
  1087. /*
  1088. * Uncompressed block. We expect to see a 16-bit LEN.
  1089. */
  1090. if (dctx->nbits < 16)
  1091. goto finished;
  1092. dctx->uncomplen = dctx->bits & 0xFFFF;
  1093. EATBITS(16);
  1094. dctx->state = UNCOMP_NLEN;
  1095. break;
  1096. case UNCOMP_NLEN:
  1097. /*
  1098. * Uncompressed block. We expect to see a 16-bit NLEN,
  1099. * which should be the one's complement of the previous
  1100. * LEN.
  1101. */
  1102. if (dctx->nbits < 16)
  1103. goto finished;
  1104. nlen = dctx->bits & 0xFFFF;
  1105. EATBITS(16);
  1106. if (dctx->uncomplen != (nlen ^ 0xFFFF))
  1107. goto decode_error;
  1108. if (dctx->uncomplen == 0)
  1109. dctx->state = OUTSIDEBLK; /* block is empty */
  1110. else
  1111. dctx->state = UNCOMP_DATA;
  1112. break;
  1113. case UNCOMP_DATA:
  1114. if (dctx->nbits < 8)
  1115. goto finished;
  1116. zlib_emit_char(dctx, dctx->bits & 0xFF);
  1117. EATBITS(8);
  1118. if (--dctx->uncomplen == 0)
  1119. dctx->state = OUTSIDEBLK; /* end of uncompressed block */
  1120. break;
  1121. }
  1122. }
  1123. finished:
  1124. *outlen = dctx->outblk->len;
  1125. *outblock = (unsigned char *)strbuf_to_str(dctx->outblk);
  1126. dctx->outblk = NULL;
  1127. return true;
  1128. decode_error:
  1129. *outblock = NULL;
  1130. *outlen = 0;
  1131. return false;
  1132. }
  1133. const ssh_compression_alg ssh_zlib = {
  1134. .name = "zlib",
  1135. .delayed_name = "zlib@openssh.com", /* delayed version */
  1136. .compress_new = zlib_compress_init,
  1137. .compress_free = zlib_compress_cleanup,
  1138. .compress = zlib_compress_block,
  1139. .decompress_new = zlib_decompress_init,
  1140. .decompress_free = zlib_decompress_cleanup,
  1141. .decompress = zlib_decompress_block,
  1142. .text_name = "zlib (RFC1950)",
  1143. };