zlib.c 65 KB

1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677787980818283848586878889909192939495969798991001011021031041051061071081091101111121131141151161171181191201211221231241251261271281291301311321331341351361371381391401411421431441451461471481491501511521531541551561571581591601611621631641651661671681691701711721731741751761771781791801811821831841851861871881891901911921931941951961971981992002012022032042052062072082092102112122132142152162172182192202212222232242252262272282292302312322332342352362372382392402412422432442452462472482492502512522532542552562572582592602612622632642652662672682692702712722732742752762772782792802812822832842852862872882892902912922932942952962972982993003013023033043053063073083093103113123133143153163173183193203213223233243253263273283293303313323333343353363373383393403413423433443453463473483493503513523533543553563573583593603613623633643653663673683693703713723733743753763773783793803813823833843853863873883893903913923933943953963973983994004014024034044054064074084094104114124134144154164174184194204214224234244254264274284294304314324334344354364374384394404414424434444454464474484494504514524534544554564574584594604614624634644654664674684694704714724734744754764774784794804814824834844854864874884894904914924934944954964974984995005015025035045055065075085095105115125135145155165175185195205215225235245255265275285295305315325335345355365375385395405415425435445455465475485495505515525535545555565575585595605615625635645655665675685695705715725735745755765775785795805815825835845855865875885895905915925935945955965975985996006016026036046056066076086096106116126136146156166176186196206216226236246256266276286296306316326336346356366376386396406416426436446456466476486496506516526536546556566576586596606616626636646656666676686696706716726736746756766776786796806816826836846856866876886896906916926936946956966976986997007017027037047057067077087097107117127137147157167177187197207217227237247257267277287297307317327337347357367377387397407417427437447457467477487497507517527537547557567577587597607617627637647657667677687697707717727737747757767777787797807817827837847857867877887897907917927937947957967977987998008018028038048058068078088098108118128138148158168178188198208218228238248258268278288298308318328338348358368378388398408418428438448458468478488498508518528538548558568578588598608618628638648658668678688698708718728738748758768778788798808818828838848858868878888898908918928938948958968978988999009019029039049059069079089099109119129139149159169179189199209219229239249259269279289299309319329339349359369379389399409419429439449459469479489499509519529539549559569579589599609619629639649659669679689699709719729739749759769779789799809819829839849859869879889899909919929939949959969979989991000100110021003100410051006100710081009101010111012101310141015101610171018101910201021102210231024102510261027102810291030103110321033103410351036103710381039104010411042104310441045104610471048104910501051105210531054105510561057105810591060106110621063106410651066106710681069107010711072107310741075107610771078107910801081108210831084108510861087108810891090109110921093109410951096109710981099110011011102110311041105110611071108110911101111111211131114111511161117111811191120112111221123112411251126112711281129113011311132113311341135113611371138113911401141114211431144114511461147114811491150115111521153115411551156115711581159116011611162116311641165116611671168116911701171117211731174117511761177117811791180118111821183118411851186118711881189119011911192119311941195119611971198119912001201120212031204120512061207120812091210121112121213121412151216121712181219122012211222122312241225122612271228122912301231123212331234123512361237123812391240124112421243124412451246124712481249125012511252125312541255125612571258125912601261126212631264126512661267126812691270127112721273127412751276127712781279128012811282128312841285128612871288128912901291129212931294129512961297129812991300130113021303130413051306130713081309131013111312131313141315131613171318131913201321132213231324132513261327132813291330133113321333133413351336133713381339134013411342134313441345134613471348134913501351135213531354135513561357135813591360136113621363136413651366136713681369137013711372137313741375137613771378137913801381138213831384138513861387138813891390139113921393139413951396139713981399140014011402140314041405140614071408140914101411141214131414141514161417141814191420142114221423142414251426142714281429143014311432143314341435143614371438143914401441144214431444144514461447144814491450145114521453145414551456145714581459146014611462146314641465146614671468146914701471147214731474147514761477147814791480148114821483148414851486148714881489149014911492149314941495149614971498149915001501150215031504150515061507150815091510151115121513151415151516151715181519152015211522152315241525152615271528152915301531153215331534153515361537153815391540154115421543154415451546154715481549155015511552155315541555155615571558155915601561156215631564156515661567156815691570157115721573157415751576157715781579158015811582158315841585158615871588158915901591159215931594159515961597159815991600160116021603160416051606160716081609161016111612161316141615161616171618161916201621162216231624162516261627162816291630163116321633163416351636163716381639164016411642164316441645164616471648164916501651165216531654165516561657165816591660166116621663166416651666166716681669167016711672167316741675167616771678167916801681168216831684168516861687168816891690169116921693169416951696169716981699170017011702170317041705170617071708170917101711171217131714171517161717171817191720172117221723172417251726172717281729173017311732173317341735173617371738173917401741174217431744174517461747174817491750175117521753175417551756175717581759176017611762176317641765176617671768176917701771177217731774177517761777177817791780178117821783178417851786178717881789179017911792179317941795179617971798179918001801180218031804180518061807180818091810181118121813181418151816181718181819182018211822182318241825182618271828182918301831183218331834183518361837183818391840184118421843184418451846184718481849185018511852185318541855185618571858185918601861186218631864186518661867186818691870187118721873187418751876187718781879188018811882188318841885188618871888188918901891189218931894189518961897189818991900190119021903190419051906190719081909191019111912191319141915191619171918191919201921192219231924192519261927192819291930193119321933193419351936193719381939194019411942194319441945194619471948194919501951195219531954195519561957195819591960196119621963196419651966196719681969197019711972197319741975197619771978197919801981198219831984198519861987198819891990199119921993199419951996199719981999200020012002200320042005200620072008200920102011201220132014201520162017201820192020202120222023202420252026202720282029203020312032203320342035203620372038203920402041204220432044204520462047204820492050205120522053205420552056205720582059206020612062206320642065206620672068206920702071207220732074207520762077207820792080208120822083208420852086208720882089209020912092209320942095209620972098209921002101210221032104210521062107210821092110211121122113211421152116211721182119212021212122212321242125212621272128212921302131213221332134213521362137213821392140214121422143214421452146214721482149215021512152215321542155215621572158215921602161
  1. /*
  2. * This file is derived from various .h and .c files from the zlib-0.95
  3. * distribution by Jean-loup Gailly and Mark Adler, with some additions
  4. * by Paul Mackerras to aid in implementing Deflate compression and
  5. * decompression for PPP packets. See zlib.h for conditions of
  6. * distribution and use.
  7. *
  8. * Changes that have been made include:
  9. * - changed functions not used outside this file to "local"
  10. * - added minCompression parameter to deflateInit2
  11. * - added Z_PACKET_FLUSH (see zlib.h for details)
  12. * - added inflateIncomp
  13. */
  14. /*+++++*/
  15. /* zutil.h -- internal interface and configuration of the compression library
  16. * Copyright (C) 1995 Jean-loup Gailly.
  17. * For conditions of distribution and use, see copyright notice in zlib.h
  18. */
  19. /* WARNING: this file should *not* be used by applications. It is
  20. part of the implementation of the compression library and is
  21. subject to change. Applications should only use zlib.h.
  22. */
  23. /* From: zutil.h,v 1.9 1995/05/03 17:27:12 jloup Exp */
  24. #define _Z_UTIL_H
  25. #include "zlib.h"
  26. #ifndef local
  27. # define local static
  28. #endif
  29. /* compile with -Dlocal if your debugger can't find static symbols */
  30. #define FAR
  31. typedef unsigned char uch;
  32. typedef uch FAR uchf;
  33. typedef unsigned short ush;
  34. typedef ush FAR ushf;
  35. typedef unsigned long ulg;
  36. extern char *z_errmsg[]; /* indexed by 1-zlib_error */
  37. #define ERR_RETURN(strm,err) return (strm->msg=z_errmsg[1-err], err)
  38. /* To be used only when the state is known to be valid */
  39. #ifndef NULL
  40. #define NULL ((void *) 0)
  41. #endif
  42. /* common constants */
  43. #define DEFLATED 8
  44. #ifndef DEF_WBITS
  45. # define DEF_WBITS MAX_WBITS
  46. #endif
  47. /* default windowBits for decompression. MAX_WBITS is for compression only */
  48. #if MAX_MEM_LEVEL >= 8
  49. # define DEF_MEM_LEVEL 8
  50. #else
  51. # define DEF_MEM_LEVEL MAX_MEM_LEVEL
  52. #endif
  53. /* default memLevel */
  54. #define STORED_BLOCK 0
  55. #define STATIC_TREES 1
  56. #define DYN_TREES 2
  57. /* The three kinds of block type */
  58. #define MIN_MATCH 3
  59. #define MAX_MATCH 258
  60. /* The minimum and maximum match lengths */
  61. /* functions */
  62. #include <linux/string.h>
  63. #define zmemcpy memcpy
  64. #define zmemzero(dest, len) memset(dest, 0, len)
  65. /* Diagnostic functions */
  66. #ifdef DEBUG_ZLIB
  67. # include <stdio.h>
  68. # ifndef verbose
  69. # define verbose 0
  70. # endif
  71. # define Assert(cond,msg) {if(!(cond)) z_error(msg);}
  72. # define Trace(x) fprintf x
  73. # define Tracev(x) {if (verbose) fprintf x ;}
  74. # define Tracevv(x) {if (verbose>1) fprintf x ;}
  75. # define Tracec(c,x) {if (verbose && (c)) fprintf x ;}
  76. # define Tracecv(c,x) {if (verbose>1 && (c)) fprintf x ;}
  77. #else
  78. # define Assert(cond,msg)
  79. # define Trace(x)
  80. # define Tracev(x)
  81. # define Tracevv(x)
  82. # define Tracec(c,x)
  83. # define Tracecv(c,x)
  84. #endif
  85. typedef uLong (*check_func) OF((uLong check, Bytef *buf, uInt len));
  86. /* voidpf zcalloc OF((voidpf opaque, unsigned items, unsigned size)); */
  87. /* void zcfree OF((voidpf opaque, voidpf ptr)); */
  88. #define ZALLOC(strm, items, size) \
  89. (*((strm)->zalloc))((strm)->opaque, (items), (size))
  90. #define ZFREE(strm, addr, size) \
  91. (*((strm)->zfree))((strm)->opaque, (voidpf)(addr), (size))
  92. #define TRY_FREE(s, p, n) {if (p) ZFREE(s, p, n);}
  93. /* deflate.h -- internal compression state
  94. * Copyright (C) 1995 Jean-loup Gailly
  95. * For conditions of distribution and use, see copyright notice in zlib.h
  96. */
  97. /* WARNING: this file should *not* be used by applications. It is
  98. part of the implementation of the compression library and is
  99. subject to change. Applications should only use zlib.h.
  100. */
  101. /*+++++*/
  102. /* infblock.h -- header to use infblock.c
  103. * Copyright (C) 1995 Mark Adler
  104. * For conditions of distribution and use, see copyright notice in zlib.h
  105. */
  106. /* WARNING: this file should *not* be used by applications. It is
  107. part of the implementation of the compression library and is
  108. subject to change. Applications should only use zlib.h.
  109. */
  110. struct inflate_blocks_state;
  111. typedef struct inflate_blocks_state FAR inflate_blocks_statef;
  112. local inflate_blocks_statef * inflate_blocks_new OF((
  113. z_stream *z,
  114. check_func c, /* check function */
  115. uInt w)); /* window size */
  116. local int inflate_blocks OF((
  117. inflate_blocks_statef *,
  118. z_stream *,
  119. int)); /* initial return code */
  120. local void inflate_blocks_reset OF((
  121. inflate_blocks_statef *,
  122. z_stream *,
  123. uLongf *)); /* check value on output */
  124. local int inflate_blocks_free OF((
  125. inflate_blocks_statef *,
  126. z_stream *,
  127. uLongf *)); /* check value on output */
  128. local int inflate_addhistory OF((
  129. inflate_blocks_statef *,
  130. z_stream *));
  131. local int inflate_packet_flush OF((
  132. inflate_blocks_statef *));
  133. /*+++++*/
  134. /* inftrees.h -- header to use inftrees.c
  135. * Copyright (C) 1995 Mark Adler
  136. * For conditions of distribution and use, see copyright notice in zlib.h
  137. */
  138. /* WARNING: this file should *not* be used by applications. It is
  139. part of the implementation of the compression library and is
  140. subject to change. Applications should only use zlib.h.
  141. */
  142. /* Huffman code lookup table entry--this entry is four bytes for machines
  143. that have 16-bit pointers (e.g. PC's in the small or medium model). */
  144. typedef struct inflate_huft_s FAR inflate_huft;
  145. struct inflate_huft_s {
  146. union {
  147. struct {
  148. Byte Exop; /* number of extra bits or operation */
  149. Byte Bits; /* number of bits in this code or subcode */
  150. } what;
  151. uInt Nalloc; /* number of these allocated here */
  152. Bytef *pad; /* pad structure to a power of 2 (4 bytes for */
  153. } word; /* 16-bit, 8 bytes for 32-bit machines) */
  154. union {
  155. uInt Base; /* literal, length base, or distance base */
  156. inflate_huft *Next; /* pointer to next level of table */
  157. } more;
  158. };
  159. #ifdef DEBUG_ZLIB
  160. local uInt inflate_hufts;
  161. #endif
  162. local int inflate_trees_bits OF((
  163. uIntf *, /* 19 code lengths */
  164. uIntf *, /* bits tree desired/actual depth */
  165. inflate_huft * FAR *, /* bits tree result */
  166. z_stream *)); /* for zalloc, zfree functions */
  167. local int inflate_trees_dynamic OF((
  168. uInt, /* number of literal/length codes */
  169. uInt, /* number of distance codes */
  170. uIntf *, /* that many (total) code lengths */
  171. uIntf *, /* literal desired/actual bit depth */
  172. uIntf *, /* distance desired/actual bit depth */
  173. inflate_huft * FAR *, /* literal/length tree result */
  174. inflate_huft * FAR *, /* distance tree result */
  175. z_stream *)); /* for zalloc, zfree functions */
  176. local int inflate_trees_fixed OF((
  177. uIntf *, /* literal desired/actual bit depth */
  178. uIntf *, /* distance desired/actual bit depth */
  179. inflate_huft * FAR *, /* literal/length tree result */
  180. inflate_huft * FAR *)); /* distance tree result */
  181. local int inflate_trees_free OF((
  182. inflate_huft *, /* tables to free */
  183. z_stream *)); /* for zfree function */
  184. /*+++++*/
  185. /* infcodes.h -- header to use infcodes.c
  186. * Copyright (C) 1995 Mark Adler
  187. * For conditions of distribution and use, see copyright notice in zlib.h
  188. */
  189. /* WARNING: this file should *not* be used by applications. It is
  190. part of the implementation of the compression library and is
  191. subject to change. Applications should only use zlib.h.
  192. */
  193. struct inflate_codes_state;
  194. typedef struct inflate_codes_state FAR inflate_codes_statef;
  195. local inflate_codes_statef *inflate_codes_new OF((
  196. uInt, uInt,
  197. inflate_huft *, inflate_huft *,
  198. z_stream *));
  199. local int inflate_codes OF((
  200. inflate_blocks_statef *,
  201. z_stream *,
  202. int));
  203. local void inflate_codes_free OF((
  204. inflate_codes_statef *,
  205. z_stream *));
  206. /*+++++*/
  207. /* inflate.c -- zlib interface to inflate modules
  208. * Copyright (C) 1995 Mark Adler
  209. * For conditions of distribution and use, see copyright notice in zlib.h
  210. */
  211. /* inflate private state */
  212. struct internal_state {
  213. /* mode */
  214. enum {
  215. METHOD, /* waiting for method byte */
  216. FLAG, /* waiting for flag byte */
  217. BLOCKS, /* decompressing blocks */
  218. CHECK4, /* four check bytes to go */
  219. CHECK3, /* three check bytes to go */
  220. CHECK2, /* two check bytes to go */
  221. CHECK1, /* one check byte to go */
  222. DONE, /* finished check, done */
  223. BAD} /* got an error--stay here */
  224. mode; /* current inflate mode */
  225. /* mode dependent information */
  226. union {
  227. uInt method; /* if FLAGS, method byte */
  228. struct {
  229. uLong was; /* computed check value */
  230. uLong need; /* stream check value */
  231. } check; /* if CHECK, check values to compare */
  232. uInt marker; /* if BAD, inflateSync's marker bytes count */
  233. } sub; /* submode */
  234. /* mode independent information */
  235. int nowrap; /* flag for no wrapper */
  236. uInt wbits; /* log2(window size) (8..15, defaults to 15) */
  237. inflate_blocks_statef
  238. *blocks; /* current inflate_blocks state */
  239. };
  240. int inflateReset(z)
  241. z_stream *z;
  242. {
  243. uLong c;
  244. if (z == Z_NULL || z->state == Z_NULL)
  245. return Z_STREAM_ERROR;
  246. z->total_in = z->total_out = 0;
  247. z->msg = Z_NULL;
  248. z->state->mode = z->state->nowrap ? BLOCKS : METHOD;
  249. inflate_blocks_reset(z->state->blocks, z, &c);
  250. Trace((stderr, "inflate: reset\n"));
  251. return Z_OK;
  252. }
  253. int inflateEnd(z)
  254. z_stream *z;
  255. {
  256. uLong c;
  257. if (z == Z_NULL || z->state == Z_NULL || z->zfree == Z_NULL)
  258. return Z_STREAM_ERROR;
  259. if (z->state->blocks != Z_NULL)
  260. inflate_blocks_free(z->state->blocks, z, &c);
  261. ZFREE(z, z->state, sizeof(struct internal_state));
  262. z->state = Z_NULL;
  263. Trace((stderr, "inflate: end\n"));
  264. return Z_OK;
  265. }
  266. int inflateInit2(z, w)
  267. z_stream *z;
  268. int w;
  269. {
  270. /* initialize state */
  271. if (z == Z_NULL)
  272. return Z_STREAM_ERROR;
  273. /* if (z->zalloc == Z_NULL) z->zalloc = zcalloc; */
  274. /* if (z->zfree == Z_NULL) z->zfree = zcfree; */
  275. if ((z->state = (struct internal_state FAR *)
  276. ZALLOC(z,1,sizeof(struct internal_state))) == Z_NULL)
  277. return Z_MEM_ERROR;
  278. z->state->blocks = Z_NULL;
  279. /* handle undocumented nowrap option (no zlib header or check) */
  280. z->state->nowrap = 0;
  281. if (w < 0)
  282. {
  283. w = - w;
  284. z->state->nowrap = 1;
  285. }
  286. /* set window size */
  287. if (w < 8 || w > 15)
  288. {
  289. inflateEnd(z);
  290. return Z_STREAM_ERROR;
  291. }
  292. z->state->wbits = (uInt)w;
  293. /* create inflate_blocks state */
  294. if ((z->state->blocks =
  295. inflate_blocks_new(z, z->state->nowrap ? Z_NULL : adler32, 1 << w))
  296. == Z_NULL)
  297. {
  298. inflateEnd(z);
  299. return Z_MEM_ERROR;
  300. }
  301. Trace((stderr, "inflate: allocated\n"));
  302. /* reset state */
  303. inflateReset(z);
  304. return Z_OK;
  305. }
  306. int inflateInit(z)
  307. z_stream *z;
  308. {
  309. return inflateInit2(z, DEF_WBITS);
  310. }
  311. #define NEEDBYTE {if(z->avail_in==0)goto empty;r=Z_OK;}
  312. #define NEXTBYTE (z->avail_in--,z->total_in++,*z->next_in++)
  313. int inflate(z, f)
  314. z_stream *z;
  315. int f;
  316. {
  317. int r;
  318. uInt b;
  319. if (z == Z_NULL || z->next_in == Z_NULL)
  320. return Z_STREAM_ERROR;
  321. r = Z_BUF_ERROR;
  322. while (1) switch (z->state->mode)
  323. {
  324. case METHOD:
  325. NEEDBYTE
  326. if (((z->state->sub.method = NEXTBYTE) & 0xf) != DEFLATED)
  327. {
  328. z->state->mode = BAD;
  329. z->msg = "unknown compression method";
  330. z->state->sub.marker = 5; /* can't try inflateSync */
  331. break;
  332. }
  333. if ((z->state->sub.method >> 4) + 8 > z->state->wbits)
  334. {
  335. z->state->mode = BAD;
  336. z->msg = "invalid window size";
  337. z->state->sub.marker = 5; /* can't try inflateSync */
  338. break;
  339. }
  340. z->state->mode = FLAG;
  341. case FLAG:
  342. NEEDBYTE
  343. if ((b = NEXTBYTE) & 0x20)
  344. {
  345. z->state->mode = BAD;
  346. z->msg = "invalid reserved bit";
  347. z->state->sub.marker = 5; /* can't try inflateSync */
  348. break;
  349. }
  350. if (((z->state->sub.method << 8) + b) % 31)
  351. {
  352. z->state->mode = BAD;
  353. z->msg = "incorrect header check";
  354. z->state->sub.marker = 5; /* can't try inflateSync */
  355. break;
  356. }
  357. Trace((stderr, "inflate: zlib header ok\n"));
  358. z->state->mode = BLOCKS;
  359. case BLOCKS:
  360. r = inflate_blocks(z->state->blocks, z, r);
  361. if (f == Z_PACKET_FLUSH && z->avail_in == 0 && z->avail_out != 0)
  362. r = inflate_packet_flush(z->state->blocks);
  363. if (r == Z_DATA_ERROR)
  364. {
  365. z->state->mode = BAD;
  366. z->state->sub.marker = 0; /* can try inflateSync */
  367. break;
  368. }
  369. if (r != Z_STREAM_END)
  370. return r;
  371. r = Z_OK;
  372. inflate_blocks_reset(z->state->blocks, z, &z->state->sub.check.was);
  373. if (z->state->nowrap)
  374. {
  375. z->state->mode = DONE;
  376. break;
  377. }
  378. z->state->mode = CHECK4;
  379. case CHECK4:
  380. NEEDBYTE
  381. z->state->sub.check.need = (uLong)NEXTBYTE << 24;
  382. z->state->mode = CHECK3;
  383. case CHECK3:
  384. NEEDBYTE
  385. z->state->sub.check.need += (uLong)NEXTBYTE << 16;
  386. z->state->mode = CHECK2;
  387. case CHECK2:
  388. NEEDBYTE
  389. z->state->sub.check.need += (uLong)NEXTBYTE << 8;
  390. z->state->mode = CHECK1;
  391. case CHECK1:
  392. NEEDBYTE
  393. z->state->sub.check.need += (uLong)NEXTBYTE;
  394. if (z->state->sub.check.was != z->state->sub.check.need)
  395. {
  396. z->state->mode = BAD;
  397. z->msg = "incorrect data check";
  398. z->state->sub.marker = 5; /* can't try inflateSync */
  399. break;
  400. }
  401. Trace((stderr, "inflate: zlib check ok\n"));
  402. z->state->mode = DONE;
  403. case DONE:
  404. return Z_STREAM_END;
  405. case BAD:
  406. return Z_DATA_ERROR;
  407. default:
  408. return Z_STREAM_ERROR;
  409. }
  410. empty:
  411. if (f != Z_PACKET_FLUSH)
  412. return r;
  413. z->state->mode = BAD;
  414. z->state->sub.marker = 0; /* can try inflateSync */
  415. return Z_DATA_ERROR;
  416. }
  417. /*
  418. * This subroutine adds the data at next_in/avail_in to the output history
  419. * without performing any output. The output buffer must be "caught up";
  420. * i.e. no pending output (hence s->read equals s->write), and the state must
  421. * be BLOCKS (i.e. we should be willing to see the start of a series of
  422. * BLOCKS). On exit, the output will also be caught up, and the checksum
  423. * will have been updated if need be.
  424. */
  425. int inflateIncomp(z)
  426. z_stream *z;
  427. {
  428. if (z->state->mode != BLOCKS)
  429. return Z_DATA_ERROR;
  430. return inflate_addhistory(z->state->blocks, z);
  431. }
  432. int inflateSync(z)
  433. z_stream *z;
  434. {
  435. uInt n; /* number of bytes to look at */
  436. Bytef *p; /* pointer to bytes */
  437. uInt m; /* number of marker bytes found in a row */
  438. uLong r, w; /* temporaries to save total_in and total_out */
  439. /* set up */
  440. if (z == Z_NULL || z->state == Z_NULL)
  441. return Z_STREAM_ERROR;
  442. if (z->state->mode != BAD)
  443. {
  444. z->state->mode = BAD;
  445. z->state->sub.marker = 0;
  446. }
  447. if ((n = z->avail_in) == 0)
  448. return Z_BUF_ERROR;
  449. p = z->next_in;
  450. m = z->state->sub.marker;
  451. /* search */
  452. while (n && m < 4)
  453. {
  454. if (*p == (Byte)(m < 2 ? 0 : 0xff))
  455. m++;
  456. else if (*p)
  457. m = 0;
  458. else
  459. m = 4 - m;
  460. p++, n--;
  461. }
  462. /* restore */
  463. z->total_in += p - z->next_in;
  464. z->next_in = p;
  465. z->avail_in = n;
  466. z->state->sub.marker = m;
  467. /* return no joy or set up to restart on a new block */
  468. if (m != 4)
  469. return Z_DATA_ERROR;
  470. r = z->total_in; w = z->total_out;
  471. inflateReset(z);
  472. z->total_in = r; z->total_out = w;
  473. z->state->mode = BLOCKS;
  474. return Z_OK;
  475. }
  476. #undef NEEDBYTE
  477. #undef NEXTBYTE
  478. /*+++++*/
  479. /* infutil.h -- types and macros common to blocks and codes
  480. * Copyright (C) 1995 Mark Adler
  481. * For conditions of distribution and use, see copyright notice in zlib.h
  482. */
  483. /* WARNING: this file should *not* be used by applications. It is
  484. part of the implementation of the compression library and is
  485. subject to change. Applications should only use zlib.h.
  486. */
  487. /* inflate blocks semi-private state */
  488. struct inflate_blocks_state {
  489. /* mode */
  490. enum {
  491. TYPE, /* get type bits (3, including end bit) */
  492. LENS, /* get lengths for stored */
  493. STORED, /* processing stored block */
  494. TABLE, /* get table lengths */
  495. BTREE, /* get bit lengths tree for a dynamic block */
  496. DTREE, /* get length, distance trees for a dynamic block */
  497. CODES, /* processing fixed or dynamic block */
  498. DRY, /* output remaining window bytes */
  499. DONEB, /* finished last block, done */
  500. BADB} /* got a data error--stuck here */
  501. mode; /* current inflate_block mode */
  502. /* mode dependent information */
  503. union {
  504. uInt left; /* if STORED, bytes left to copy */
  505. struct {
  506. uInt table; /* table lengths (14 bits) */
  507. uInt index; /* index into blens (or border) */
  508. uIntf *blens; /* bit lengths of codes */
  509. uInt bb; /* bit length tree depth */
  510. inflate_huft *tb; /* bit length decoding tree */
  511. int nblens; /* # elements allocated at blens */
  512. } trees; /* if DTREE, decoding info for trees */
  513. struct {
  514. inflate_huft *tl, *td; /* trees to free */
  515. inflate_codes_statef
  516. *codes;
  517. } decode; /* if CODES, current state */
  518. } sub; /* submode */
  519. uInt last; /* true if this block is the last block */
  520. /* mode independent information */
  521. uInt bitk; /* bits in bit buffer */
  522. uLong bitb; /* bit buffer */
  523. Bytef *window; /* sliding window */
  524. Bytef *end; /* one byte after sliding window */
  525. Bytef *read; /* window read pointer */
  526. Bytef *write; /* window write pointer */
  527. check_func checkfn; /* check function */
  528. uLong check; /* check on output */
  529. };
  530. /* defines for inflate input/output */
  531. /* update pointers and return */
  532. #define UPDBITS {s->bitb=b;s->bitk=k;}
  533. #define UPDIN {z->avail_in=n;z->total_in+=p-z->next_in;z->next_in=p;}
  534. #define UPDOUT {s->write=q;}
  535. #define UPDATE {UPDBITS UPDIN UPDOUT}
  536. #define LEAVE {UPDATE return inflate_flush(s,z,r);}
  537. /* get bytes and bits */
  538. #define LOADIN {p=z->next_in;n=z->avail_in;b=s->bitb;k=s->bitk;}
  539. #define NEEDBYTE {if(n)r=Z_OK;else LEAVE}
  540. #define NEXTBYTE (n--,*p++)
  541. #define NEEDBITS(j) {while(k<(j)){NEEDBYTE;b|=((uLong)NEXTBYTE)<<k;k+=8;}}
  542. #define DUMPBITS(j) {b>>=(j);k-=(j);}
  543. /* output bytes */
  544. #define WAVAIL (q<s->read?s->read-q-1:s->end-q)
  545. #define LOADOUT {q=s->write;m=WAVAIL;}
  546. #define WRAP {if(q==s->end&&s->read!=s->window){q=s->window;m=WAVAIL;}}
  547. #define FLUSH {UPDOUT r=inflate_flush(s,z,r); LOADOUT}
  548. #define NEEDOUT {if(m==0){WRAP if(m==0){FLUSH WRAP if(m==0) LEAVE}}r=Z_OK;}
  549. #define OUTBYTE(a) {*q++=(Byte)(a);m--;}
  550. /* load local pointers */
  551. #define LOAD {LOADIN LOADOUT}
  552. /*
  553. * The IBM 150 firmware munges the data right after _etext[]. This
  554. * protects it. -- Cort
  555. */
  556. #if 0
  557. local uInt protect_mask[] = {0, 0, 0, 0, 0, 0, 0, 0, 0 ,0 ,0 ,0};
  558. #endif
  559. /* And'ing with mask[n] masks the lower n bits */
  560. local uInt inflate_mask[] = {
  561. 0x0000,
  562. 0x0001, 0x0003, 0x0007, 0x000f, 0x001f, 0x003f, 0x007f, 0x00ff,
  563. 0x01ff, 0x03ff, 0x07ff, 0x0fff, 0x1fff, 0x3fff, 0x7fff, 0xffff
  564. };
  565. /* copy as much as possible from the sliding window to the output area */
  566. local int inflate_flush OF((
  567. inflate_blocks_statef *,
  568. z_stream *,
  569. int));
  570. /*+++++*/
  571. /* inffast.h -- header to use inffast.c
  572. * Copyright (C) 1995 Mark Adler
  573. * For conditions of distribution and use, see copyright notice in zlib.h
  574. */
  575. /* WARNING: this file should *not* be used by applications. It is
  576. part of the implementation of the compression library and is
  577. subject to change. Applications should only use zlib.h.
  578. */
  579. local int inflate_fast OF((
  580. uInt,
  581. uInt,
  582. inflate_huft *,
  583. inflate_huft *,
  584. inflate_blocks_statef *,
  585. z_stream *));
  586. /*+++++*/
  587. /* infblock.c -- interpret and process block types to last block
  588. * Copyright (C) 1995 Mark Adler
  589. * For conditions of distribution and use, see copyright notice in zlib.h
  590. */
  591. /* Table for deflate from PKZIP's appnote.txt. */
  592. local uInt border[] = { /* Order of the bit length code lengths */
  593. 16, 17, 18, 0, 8, 7, 9, 6, 10, 5, 11, 4, 12, 3, 13, 2, 14, 1, 15};
  594. /*
  595. Notes beyond the 1.93a appnote.txt:
  596. 1. Distance pointers never point before the beginning of the output
  597. stream.
  598. 2. Distance pointers can point back across blocks, up to 32k away.
  599. 3. There is an implied maximum of 7 bits for the bit length table and
  600. 15 bits for the actual data.
  601. 4. If only one code exists, then it is encoded using one bit. (Zero
  602. would be more efficient, but perhaps a little confusing.) If two
  603. codes exist, they are coded using one bit each (0 and 1).
  604. 5. There is no way of sending zero distance codes--a dummy must be
  605. sent if there are none. (History: a pre 2.0 version of PKZIP would
  606. store blocks with no distance codes, but this was discovered to be
  607. too harsh a criterion.) Valid only for 1.93a. 2.04c does allow
  608. zero distance codes, which is sent as one code of zero bits in
  609. length.
  610. 6. There are up to 286 literal/length codes. Code 256 represents the
  611. end-of-block. Note however that the static length tree defines
  612. 288 codes just to fill out the Huffman codes. Codes 286 and 287
  613. cannot be used though, since there is no length base or extra bits
  614. defined for them. Similarily, there are up to 30 distance codes.
  615. However, static trees define 32 codes (all 5 bits) to fill out the
  616. Huffman codes, but the last two had better not show up in the data.
  617. 7. Unzip can check dynamic Huffman blocks for complete code sets.
  618. The exception is that a single code would not be complete (see #4).
  619. 8. The five bits following the block type is really the number of
  620. literal codes sent minus 257.
  621. 9. Length codes 8,16,16 are interpreted as 13 length codes of 8 bits
  622. (1+6+6). Therefore, to output three times the length, you output
  623. three codes (1+1+1), whereas to output four times the same length,
  624. you only need two codes (1+3). Hmm.
  625. 10. In the tree reconstruction algorithm, Code = Code + Increment
  626. only if BitLength(i) is not zero. (Pretty obvious.)
  627. 11. Correction: 4 Bits: # of Bit Length codes - 4 (4 - 19)
  628. 12. Note: length code 284 can represent 227-258, but length code 285
  629. really is 258. The last length deserves its own, short code
  630. since it gets used a lot in very redundant files. The length
  631. 258 is special since 258 - 3 (the min match length) is 255.
  632. 13. The literal/length and distance code bit lengths are read as a
  633. single stream of lengths. It is possible (and advantageous) for
  634. a repeat code (16, 17, or 18) to go across the boundary between
  635. the two sets of lengths.
  636. */
  637. local void inflate_blocks_reset(s, z, c)
  638. inflate_blocks_statef *s;
  639. z_stream *z;
  640. uLongf *c;
  641. {
  642. if (s->checkfn != Z_NULL)
  643. *c = s->check;
  644. if (s->mode == BTREE || s->mode == DTREE)
  645. ZFREE(z, s->sub.trees.blens, s->sub.trees.nblens * sizeof(uInt));
  646. if (s->mode == CODES)
  647. {
  648. inflate_codes_free(s->sub.decode.codes, z);
  649. inflate_trees_free(s->sub.decode.td, z);
  650. inflate_trees_free(s->sub.decode.tl, z);
  651. }
  652. s->mode = TYPE;
  653. s->bitk = 0;
  654. s->bitb = 0;
  655. s->read = s->write = s->window;
  656. if (s->checkfn != Z_NULL)
  657. s->check = (*s->checkfn)(0L, Z_NULL, 0);
  658. if (z->outcb != Z_NULL)
  659. (*z->outcb)(Z_NULL, 0);
  660. Trace((stderr, "inflate: blocks reset\n"));
  661. }
  662. local inflate_blocks_statef *inflate_blocks_new(z, c, w)
  663. z_stream *z;
  664. check_func c;
  665. uInt w;
  666. {
  667. inflate_blocks_statef *s;
  668. if ((s = (inflate_blocks_statef *)ZALLOC
  669. (z,1,sizeof(struct inflate_blocks_state))) == Z_NULL)
  670. return s;
  671. if ((s->window = (Bytef *)ZALLOC(z, 1, w)) == Z_NULL)
  672. {
  673. ZFREE(z, s, sizeof(struct inflate_blocks_state));
  674. return Z_NULL;
  675. }
  676. s->end = s->window + w;
  677. s->checkfn = c;
  678. s->mode = TYPE;
  679. Trace((stderr, "inflate: blocks allocated\n"));
  680. inflate_blocks_reset(s, z, &s->check);
  681. return s;
  682. }
  683. local int inflate_blocks(s, z, r)
  684. inflate_blocks_statef *s;
  685. z_stream *z;
  686. int r;
  687. {
  688. uInt t; /* temporary storage */
  689. uLong b; /* bit buffer */
  690. uInt k; /* bits in bit buffer */
  691. Bytef *p; /* input data pointer */
  692. uInt n; /* bytes available there */
  693. Bytef *q; /* output window write pointer */
  694. uInt m; /* bytes to end of window or read pointer */
  695. /* copy input/output information to locals (UPDATE macro restores) */
  696. LOAD
  697. /* process input based on current state */
  698. while (1) switch (s->mode)
  699. {
  700. case TYPE:
  701. NEEDBITS(3)
  702. t = (uInt)b & 7;
  703. s->last = t & 1;
  704. switch (t >> 1)
  705. {
  706. case 0: /* stored */
  707. Trace((stderr, "inflate: stored block%s\n",
  708. s->last ? " (last)" : ""));
  709. DUMPBITS(3)
  710. t = k & 7; /* go to byte boundary */
  711. DUMPBITS(t)
  712. s->mode = LENS; /* get length of stored block */
  713. break;
  714. case 1: /* fixed */
  715. Trace((stderr, "inflate: fixed codes block%s\n",
  716. s->last ? " (last)" : ""));
  717. {
  718. uInt bl, bd;
  719. inflate_huft *tl, *td;
  720. inflate_trees_fixed(&bl, &bd, &tl, &td);
  721. s->sub.decode.codes = inflate_codes_new(bl, bd, tl, td, z);
  722. if (s->sub.decode.codes == Z_NULL)
  723. {
  724. r = Z_MEM_ERROR;
  725. LEAVE
  726. }
  727. s->sub.decode.tl = Z_NULL; /* don't try to free these */
  728. s->sub.decode.td = Z_NULL;
  729. }
  730. DUMPBITS(3)
  731. s->mode = CODES;
  732. break;
  733. case 2: /* dynamic */
  734. Trace((stderr, "inflate: dynamic codes block%s\n",
  735. s->last ? " (last)" : ""));
  736. DUMPBITS(3)
  737. s->mode = TABLE;
  738. break;
  739. case 3: /* illegal */
  740. DUMPBITS(3)
  741. s->mode = BADB;
  742. z->msg = "invalid block type";
  743. r = Z_DATA_ERROR;
  744. LEAVE
  745. }
  746. break;
  747. case LENS:
  748. NEEDBITS(32)
  749. if (((~b) >> 16) != (b & 0xffff))
  750. {
  751. s->mode = BADB;
  752. z->msg = "invalid stored block lengths";
  753. r = Z_DATA_ERROR;
  754. LEAVE
  755. }
  756. s->sub.left = (uInt)b & 0xffff;
  757. b = k = 0; /* dump bits */
  758. Tracev((stderr, "inflate: stored length %u\n", s->sub.left));
  759. s->mode = s->sub.left ? STORED : TYPE;
  760. break;
  761. case STORED:
  762. if (n == 0)
  763. LEAVE
  764. NEEDOUT
  765. t = s->sub.left;
  766. if (t > n) t = n;
  767. if (t > m) t = m;
  768. zmemcpy(q, p, t);
  769. p += t; n -= t;
  770. q += t; m -= t;
  771. if ((s->sub.left -= t) != 0)
  772. break;
  773. Tracev((stderr, "inflate: stored end, %lu total out\n",
  774. z->total_out + (q >= s->read ? q - s->read :
  775. (s->end - s->read) + (q - s->window))));
  776. s->mode = s->last ? DRY : TYPE;
  777. break;
  778. case TABLE:
  779. NEEDBITS(14)
  780. s->sub.trees.table = t = (uInt)b & 0x3fff;
  781. #ifndef PKZIP_BUG_WORKAROUND
  782. if ((t & 0x1f) > 29 || ((t >> 5) & 0x1f) > 29)
  783. {
  784. s->mode = BADB;
  785. z->msg = "too many length or distance symbols";
  786. r = Z_DATA_ERROR;
  787. LEAVE
  788. }
  789. #endif
  790. t = 258 + (t & 0x1f) + ((t >> 5) & 0x1f);
  791. if (t < 19)
  792. t = 19;
  793. if ((s->sub.trees.blens = (uIntf*)ZALLOC(z, t, sizeof(uInt))) == Z_NULL)
  794. {
  795. r = Z_MEM_ERROR;
  796. LEAVE
  797. }
  798. s->sub.trees.nblens = t;
  799. DUMPBITS(14)
  800. s->sub.trees.index = 0;
  801. Tracev((stderr, "inflate: table sizes ok\n"));
  802. s->mode = BTREE;
  803. case BTREE:
  804. while (s->sub.trees.index < 4 + (s->sub.trees.table >> 10))
  805. {
  806. NEEDBITS(3)
  807. s->sub.trees.blens[border[s->sub.trees.index++]] = (uInt)b & 7;
  808. DUMPBITS(3)
  809. }
  810. while (s->sub.trees.index < 19)
  811. s->sub.trees.blens[border[s->sub.trees.index++]] = 0;
  812. s->sub.trees.bb = 7;
  813. t = inflate_trees_bits(s->sub.trees.blens, &s->sub.trees.bb,
  814. &s->sub.trees.tb, z);
  815. if (t != Z_OK)
  816. {
  817. r = t;
  818. if (r == Z_DATA_ERROR)
  819. s->mode = BADB;
  820. LEAVE
  821. }
  822. s->sub.trees.index = 0;
  823. Tracev((stderr, "inflate: bits tree ok\n"));
  824. s->mode = DTREE;
  825. case DTREE:
  826. while (t = s->sub.trees.table,
  827. s->sub.trees.index < 258 + (t & 0x1f) + ((t >> 5) & 0x1f))
  828. {
  829. inflate_huft *h;
  830. uInt i, j, c;
  831. t = s->sub.trees.bb;
  832. NEEDBITS(t)
  833. h = s->sub.trees.tb + ((uInt)b & inflate_mask[t]);
  834. t = h->word.what.Bits;
  835. c = h->more.Base;
  836. if (c < 16)
  837. {
  838. DUMPBITS(t)
  839. s->sub.trees.blens[s->sub.trees.index++] = c;
  840. }
  841. else /* c == 16..18 */
  842. {
  843. i = c == 18 ? 7 : c - 14;
  844. j = c == 18 ? 11 : 3;
  845. NEEDBITS(t + i)
  846. DUMPBITS(t)
  847. j += (uInt)b & inflate_mask[i];
  848. DUMPBITS(i)
  849. i = s->sub.trees.index;
  850. t = s->sub.trees.table;
  851. if (i + j > 258 + (t & 0x1f) + ((t >> 5) & 0x1f) ||
  852. (c == 16 && i < 1))
  853. {
  854. s->mode = BADB;
  855. z->msg = "invalid bit length repeat";
  856. r = Z_DATA_ERROR;
  857. LEAVE
  858. }
  859. c = c == 16 ? s->sub.trees.blens[i - 1] : 0;
  860. do {
  861. s->sub.trees.blens[i++] = c;
  862. } while (--j);
  863. s->sub.trees.index = i;
  864. }
  865. }
  866. inflate_trees_free(s->sub.trees.tb, z);
  867. s->sub.trees.tb = Z_NULL;
  868. {
  869. uInt bl, bd;
  870. inflate_huft *tl, *td;
  871. inflate_codes_statef *c;
  872. bl = 9; /* must be <= 9 for lookahead assumptions */
  873. bd = 6; /* must be <= 9 for lookahead assumptions */
  874. t = s->sub.trees.table;
  875. t = inflate_trees_dynamic(257 + (t & 0x1f), 1 + ((t >> 5) & 0x1f),
  876. s->sub.trees.blens, &bl, &bd, &tl, &td, z);
  877. if (t != Z_OK)
  878. {
  879. if (t == (uInt)Z_DATA_ERROR)
  880. s->mode = BADB;
  881. r = t;
  882. LEAVE
  883. }
  884. Tracev((stderr, "inflate: trees ok\n"));
  885. if ((c = inflate_codes_new(bl, bd, tl, td, z)) == Z_NULL)
  886. {
  887. inflate_trees_free(td, z);
  888. inflate_trees_free(tl, z);
  889. r = Z_MEM_ERROR;
  890. LEAVE
  891. }
  892. ZFREE(z, s->sub.trees.blens, s->sub.trees.nblens * sizeof(uInt));
  893. s->sub.decode.codes = c;
  894. s->sub.decode.tl = tl;
  895. s->sub.decode.td = td;
  896. }
  897. s->mode = CODES;
  898. case CODES:
  899. UPDATE
  900. if ((r = inflate_codes(s, z, r)) != Z_STREAM_END)
  901. return inflate_flush(s, z, r);
  902. r = Z_OK;
  903. inflate_codes_free(s->sub.decode.codes, z);
  904. inflate_trees_free(s->sub.decode.td, z);
  905. inflate_trees_free(s->sub.decode.tl, z);
  906. LOAD
  907. Tracev((stderr, "inflate: codes end, %lu total out\n",
  908. z->total_out + (q >= s->read ? q - s->read :
  909. (s->end - s->read) + (q - s->window))));
  910. if (!s->last)
  911. {
  912. s->mode = TYPE;
  913. break;
  914. }
  915. if (k > 7) /* return unused byte, if any */
  916. {
  917. Assert(k < 16, "inflate_codes grabbed too many bytes")
  918. k -= 8;
  919. n++;
  920. p--; /* can always return one */
  921. }
  922. s->mode = DRY;
  923. case DRY:
  924. FLUSH
  925. if (s->read != s->write)
  926. LEAVE
  927. s->mode = DONEB;
  928. case DONEB:
  929. r = Z_STREAM_END;
  930. LEAVE
  931. case BADB:
  932. r = Z_DATA_ERROR;
  933. LEAVE
  934. default:
  935. r = Z_STREAM_ERROR;
  936. LEAVE
  937. }
  938. }
  939. local int inflate_blocks_free(s, z, c)
  940. inflate_blocks_statef *s;
  941. z_stream *z;
  942. uLongf *c;
  943. {
  944. inflate_blocks_reset(s, z, c);
  945. ZFREE(z, s->window, s->end - s->window);
  946. ZFREE(z, s, sizeof(struct inflate_blocks_state));
  947. Trace((stderr, "inflate: blocks freed\n"));
  948. return Z_OK;
  949. }
  950. /*
  951. * This subroutine adds the data at next_in/avail_in to the output history
  952. * without performing any output. The output buffer must be "caught up";
  953. * i.e. no pending output (hence s->read equals s->write), and the state must
  954. * be BLOCKS (i.e. we should be willing to see the start of a series of
  955. * BLOCKS). On exit, the output will also be caught up, and the checksum
  956. * will have been updated if need be.
  957. */
  958. local int inflate_addhistory(s, z)
  959. inflate_blocks_statef *s;
  960. z_stream *z;
  961. {
  962. uLong b; /* bit buffer */ /* NOT USED HERE */
  963. uInt k; /* bits in bit buffer */ /* NOT USED HERE */
  964. uInt t; /* temporary storage */
  965. Bytef *p; /* input data pointer */
  966. uInt n; /* bytes available there */
  967. Bytef *q; /* output window write pointer */
  968. uInt m; /* bytes to end of window or read pointer */
  969. if (s->read != s->write)
  970. return Z_STREAM_ERROR;
  971. if (s->mode != TYPE)
  972. return Z_DATA_ERROR;
  973. /* we're ready to rock */
  974. LOAD
  975. /* while there is input ready, copy to output buffer, moving
  976. * pointers as needed.
  977. */
  978. while (n) {
  979. t = n; /* how many to do */
  980. /* is there room until end of buffer? */
  981. if (t > m) t = m;
  982. /* update check information */
  983. if (s->checkfn != Z_NULL)
  984. s->check = (*s->checkfn)(s->check, q, t);
  985. /* output callback */
  986. if (z->outcb != Z_NULL)
  987. (*z->outcb)(q, t);
  988. zmemcpy(q, p, t);
  989. q += t;
  990. p += t;
  991. n -= t;
  992. z->total_out += t;
  993. s->read = q; /* drag read pointer forward */
  994. /* WRAP */ /* expand WRAP macro by hand to handle s->read */
  995. if (q == s->end) {
  996. s->read = q = s->window;
  997. m = WAVAIL;
  998. }
  999. }
  1000. UPDATE
  1001. return Z_OK;
  1002. }
  1003. /*
  1004. * At the end of a Deflate-compressed PPP packet, we expect to have seen
  1005. * a `stored' block type value but not the (zero) length bytes.
  1006. */
  1007. local int inflate_packet_flush(s)
  1008. inflate_blocks_statef *s;
  1009. {
  1010. if (s->mode != LENS)
  1011. return Z_DATA_ERROR;
  1012. s->mode = TYPE;
  1013. return Z_OK;
  1014. }
  1015. /*+++++*/
  1016. /* inftrees.c -- generate Huffman trees for efficient decoding
  1017. * Copyright (C) 1995 Mark Adler
  1018. * For conditions of distribution and use, see copyright notice in zlib.h
  1019. */
  1020. /* simplify the use of the inflate_huft type with some defines */
  1021. #define base more.Base
  1022. #define next more.Next
  1023. #define exop word.what.Exop
  1024. #define bits word.what.Bits
  1025. local int huft_build OF((
  1026. uIntf *, /* code lengths in bits */
  1027. uInt, /* number of codes */
  1028. uInt, /* number of "simple" codes */
  1029. uIntf *, /* list of base values for non-simple codes */
  1030. uIntf *, /* list of extra bits for non-simple codes */
  1031. inflate_huft * FAR*,/* result: starting table */
  1032. uIntf *, /* maximum lookup bits (returns actual) */
  1033. z_stream *)); /* for zalloc function */
  1034. local voidpf falloc OF((
  1035. voidpf, /* opaque pointer (not used) */
  1036. uInt, /* number of items */
  1037. uInt)); /* size of item */
  1038. local void ffree OF((
  1039. voidpf q, /* opaque pointer (not used) */
  1040. voidpf p, /* what to free (not used) */
  1041. uInt n)); /* number of bytes (not used) */
  1042. /* Tables for deflate from PKZIP's appnote.txt. */
  1043. local uInt cplens[] = { /* Copy lengths for literal codes 257..285 */
  1044. 3, 4, 5, 6, 7, 8, 9, 10, 11, 13, 15, 17, 19, 23, 27, 31,
  1045. 35, 43, 51, 59, 67, 83, 99, 115, 131, 163, 195, 227, 258, 0, 0};
  1046. /* actually lengths - 2; also see note #13 above about 258 */
  1047. local uInt cplext[] = { /* Extra bits for literal codes 257..285 */
  1048. 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 2, 2, 2, 2,
  1049. 3, 3, 3, 3, 4, 4, 4, 4, 5, 5, 5, 5, 0, 192, 192}; /* 192==invalid */
  1050. local uInt cpdist[] = { /* Copy offsets for distance codes 0..29 */
  1051. 1, 2, 3, 4, 5, 7, 9, 13, 17, 25, 33, 49, 65, 97, 129, 193,
  1052. 257, 385, 513, 769, 1025, 1537, 2049, 3073, 4097, 6145,
  1053. 8193, 12289, 16385, 24577};
  1054. local uInt cpdext[] = { /* Extra bits for distance codes */
  1055. 0, 0, 0, 0, 1, 1, 2, 2, 3, 3, 4, 4, 5, 5, 6, 6,
  1056. 7, 7, 8, 8, 9, 9, 10, 10, 11, 11,
  1057. 12, 12, 13, 13};
  1058. /*
  1059. Huffman code decoding is performed using a multi-level table lookup.
  1060. The fastest way to decode is to simply build a lookup table whose
  1061. size is determined by the longest code. However, the time it takes
  1062. to build this table can also be a factor if the data being decoded
  1063. is not very long. The most common codes are necessarily the
  1064. shortest codes, so those codes dominate the decoding time, and hence
  1065. the speed. The idea is you can have a shorter table that decodes the
  1066. shorter, more probable codes, and then point to subsidiary tables for
  1067. the longer codes. The time it costs to decode the longer codes is
  1068. then traded against the time it takes to make longer tables.
  1069. This results of this trade are in the variables lbits and dbits
  1070. below. lbits is the number of bits the first level table for literal/
  1071. length codes can decode in one step, and dbits is the same thing for
  1072. the distance codes. Subsequent tables are also less than or equal to
  1073. those sizes. These values may be adjusted either when all of the
  1074. codes are shorter than that, in which case the longest code length in
  1075. bits is used, or when the shortest code is *longer* than the requested
  1076. table size, in which case the length of the shortest code in bits is
  1077. used.
  1078. There are two different values for the two tables, since they code a
  1079. different number of possibilities each. The literal/length table
  1080. codes 286 possible values, or in a flat code, a little over eight
  1081. bits. The distance table codes 30 possible values, or a little less
  1082. than five bits, flat. The optimum values for speed end up being
  1083. about one bit more than those, so lbits is 8+1 and dbits is 5+1.
  1084. The optimum values may differ though from machine to machine, and
  1085. possibly even between compilers. Your mileage may vary.
  1086. */
  1087. /* If BMAX needs to be larger than 16, then h and x[] should be uLong. */
  1088. #define BMAX 15 /* maximum bit length of any code */
  1089. #define N_MAX 288 /* maximum number of codes in any set */
  1090. #ifdef DEBUG_ZLIB
  1091. uInt inflate_hufts;
  1092. #endif
  1093. local int huft_build(b, n, s, d, e, t, m, zs)
  1094. uIntf *b; /* code lengths in bits (all assumed <= BMAX) */
  1095. uInt n; /* number of codes (assumed <= N_MAX) */
  1096. uInt s; /* number of simple-valued codes (0..s-1) */
  1097. uIntf *d; /* list of base values for non-simple codes */
  1098. uIntf *e; /* list of extra bits for non-simple codes */
  1099. inflate_huft * FAR *t; /* result: starting table */
  1100. uIntf *m; /* maximum lookup bits, returns actual */
  1101. z_stream *zs; /* for zalloc function */
  1102. /* Given a list of code lengths and a maximum table size, make a set of
  1103. tables to decode that set of codes. Return Z_OK on success, Z_BUF_ERROR
  1104. if the given code set is incomplete (the tables are still built in this
  1105. case), Z_DATA_ERROR if the input is invalid (all zero length codes or an
  1106. over-subscribed set of lengths), or Z_MEM_ERROR if not enough memory. */
  1107. {
  1108. uInt a; /* counter for codes of length k */
  1109. uInt c[BMAX+1]; /* bit length count table */
  1110. uInt f; /* i repeats in table every f entries */
  1111. int g; /* maximum code length */
  1112. int h; /* table level */
  1113. register uInt i; /* counter, current code */
  1114. register uInt j; /* counter */
  1115. register int k; /* number of bits in current code */
  1116. int l; /* bits per table (returned in m) */
  1117. register uIntf *p; /* pointer into c[], b[], or v[] */
  1118. inflate_huft *q; /* points to current table */
  1119. struct inflate_huft_s r; /* table entry for structure assignment */
  1120. inflate_huft *u[BMAX]; /* table stack */
  1121. uInt v[N_MAX]; /* values in order of bit length */
  1122. register int w; /* bits before this table == (l * h) */
  1123. uInt x[BMAX+1]; /* bit offsets, then code stack */
  1124. uIntf *xp; /* pointer into x */
  1125. int y; /* number of dummy codes added */
  1126. uInt z; /* number of entries in current table */
  1127. /* Generate counts for each bit length */
  1128. p = c;
  1129. #define C0 *p++ = 0;
  1130. #define C2 C0 C0 C0 C0
  1131. #define C4 C2 C2 C2 C2
  1132. C4 /* clear c[]--assume BMAX+1 is 16 */
  1133. p = b; i = n;
  1134. do {
  1135. c[*p++]++; /* assume all entries <= BMAX */
  1136. } while (--i);
  1137. if (c[0] == n) /* null input--all zero length codes */
  1138. {
  1139. *t = (inflate_huft *)Z_NULL;
  1140. *m = 0;
  1141. return Z_OK;
  1142. }
  1143. /* Find minimum and maximum length, bound *m by those */
  1144. l = *m;
  1145. for (j = 1; j <= BMAX; j++)
  1146. if (c[j])
  1147. break;
  1148. k = j; /* minimum code length */
  1149. if ((uInt)l < j)
  1150. l = j;
  1151. for (i = BMAX; i; i--)
  1152. if (c[i])
  1153. break;
  1154. g = i; /* maximum code length */
  1155. if ((uInt)l > i)
  1156. l = i;
  1157. *m = l;
  1158. /* Adjust last length count to fill out codes, if needed */
  1159. for (y = 1 << j; j < i; j++, y <<= 1)
  1160. if ((y -= c[j]) < 0)
  1161. return Z_DATA_ERROR;
  1162. if ((y -= c[i]) < 0)
  1163. return Z_DATA_ERROR;
  1164. c[i] += y;
  1165. /* Generate starting offsets into the value table for each length */
  1166. x[1] = j = 0;
  1167. p = c + 1; xp = x + 2;
  1168. while (--i) { /* note that i == g from above */
  1169. *xp++ = (j += *p++);
  1170. }
  1171. /* Make a table of values in order of bit lengths */
  1172. p = b; i = 0;
  1173. do {
  1174. if ((j = *p++) != 0)
  1175. v[x[j]++] = i;
  1176. } while (++i < n);
  1177. /* Generate the Huffman codes and for each, make the table entries */
  1178. x[0] = i = 0; /* first Huffman code is zero */
  1179. p = v; /* grab values in bit order */
  1180. h = -1; /* no tables yet--level -1 */
  1181. w = -l; /* bits decoded == (l * h) */
  1182. u[0] = (inflate_huft *)Z_NULL; /* just to keep compilers happy */
  1183. q = (inflate_huft *)Z_NULL; /* ditto */
  1184. z = 0; /* ditto */
  1185. /* go through the bit lengths (k already is bits in shortest code) */
  1186. for (; k <= g; k++)
  1187. {
  1188. a = c[k];
  1189. while (a--)
  1190. {
  1191. /* here i is the Huffman code of length k bits for value *p */
  1192. /* make tables up to required level */
  1193. while (k > w + l)
  1194. {
  1195. h++;
  1196. w += l; /* previous table always l bits */
  1197. /* compute minimum size table less than or equal to l bits */
  1198. z = (z = g - w) > (uInt)l ? l : z; /* table size upper limit */
  1199. if ((f = 1 << (j = k - w)) > a + 1) /* try a k-w bit table */
  1200. { /* too few codes for k-w bit table */
  1201. f -= a + 1; /* deduct codes from patterns left */
  1202. xp = c + k;
  1203. if (j < z)
  1204. while (++j < z) /* try smaller tables up to z bits */
  1205. {
  1206. if ((f <<= 1) <= *++xp)
  1207. break; /* enough codes to use up j bits */
  1208. f -= *xp; /* else deduct codes from patterns */
  1209. }
  1210. }
  1211. z = 1 << j; /* table entries for j-bit table */
  1212. /* allocate and link in new table */
  1213. if ((q = (inflate_huft *)ZALLOC
  1214. (zs,z + 1,sizeof(inflate_huft))) == Z_NULL)
  1215. {
  1216. if (h)
  1217. inflate_trees_free(u[0], zs);
  1218. return Z_MEM_ERROR; /* not enough memory */
  1219. }
  1220. q->word.Nalloc = z + 1;
  1221. #ifdef DEBUG_ZLIB
  1222. inflate_hufts += z + 1;
  1223. #endif
  1224. *t = q + 1; /* link to list for huft_free() */
  1225. *(t = &(q->next)) = Z_NULL;
  1226. u[h] = ++q; /* table starts after link */
  1227. /* connect to last table, if there is one */
  1228. if (h)
  1229. {
  1230. x[h] = i; /* save pattern for backing up */
  1231. r.bits = (Byte)l; /* bits to dump before this table */
  1232. r.exop = (Byte)j; /* bits in this table */
  1233. r.next = q; /* pointer to this table */
  1234. j = i >> (w - l); /* (get around Turbo C bug) */
  1235. u[h-1][j] = r; /* connect to last table */
  1236. }
  1237. }
  1238. /* set up table entry in r */
  1239. r.bits = (Byte)(k - w);
  1240. if (p >= v + n)
  1241. r.exop = 128 + 64; /* out of values--invalid code */
  1242. else if (*p < s)
  1243. {
  1244. r.exop = (Byte)(*p < 256 ? 0 : 32 + 64); /* 256 is end-of-block */
  1245. r.base = *p++; /* simple code is just the value */
  1246. }
  1247. else
  1248. {
  1249. r.exop = (Byte)e[*p - s] + 16 + 64; /* non-simple--look up in lists */
  1250. r.base = d[*p++ - s];
  1251. }
  1252. /* fill code-like entries with r */
  1253. f = 1 << (k - w);
  1254. for (j = i >> w; j < z; j += f)
  1255. q[j] = r;
  1256. /* backwards increment the k-bit code i */
  1257. for (j = 1 << (k - 1); i & j; j >>= 1)
  1258. i ^= j;
  1259. i ^= j;
  1260. /* backup over finished tables */
  1261. while ((i & ((1 << w) - 1)) != x[h])
  1262. {
  1263. h--; /* don't need to update q */
  1264. w -= l;
  1265. }
  1266. }
  1267. }
  1268. /* Return Z_BUF_ERROR if we were given an incomplete table */
  1269. return y != 0 && g != 1 ? Z_BUF_ERROR : Z_OK;
  1270. }
  1271. local int inflate_trees_bits(c, bb, tb, z)
  1272. uIntf *c; /* 19 code lengths */
  1273. uIntf *bb; /* bits tree desired/actual depth */
  1274. inflate_huft * FAR *tb; /* bits tree result */
  1275. z_stream *z; /* for zfree function */
  1276. {
  1277. int r;
  1278. r = huft_build(c, 19, 19, (uIntf*)Z_NULL, (uIntf*)Z_NULL, tb, bb, z);
  1279. if (r == Z_DATA_ERROR)
  1280. z->msg = "oversubscribed dynamic bit lengths tree";
  1281. else if (r == Z_BUF_ERROR)
  1282. {
  1283. inflate_trees_free(*tb, z);
  1284. z->msg = "incomplete dynamic bit lengths tree";
  1285. r = Z_DATA_ERROR;
  1286. }
  1287. return r;
  1288. }
  1289. local int inflate_trees_dynamic(nl, nd, c, bl, bd, tl, td, z)
  1290. uInt nl; /* number of literal/length codes */
  1291. uInt nd; /* number of distance codes */
  1292. uIntf *c; /* that many (total) code lengths */
  1293. uIntf *bl; /* literal desired/actual bit depth */
  1294. uIntf *bd; /* distance desired/actual bit depth */
  1295. inflate_huft * FAR *tl; /* literal/length tree result */
  1296. inflate_huft * FAR *td; /* distance tree result */
  1297. z_stream *z; /* for zfree function */
  1298. {
  1299. int r;
  1300. /* build literal/length tree */
  1301. if ((r = huft_build(c, nl, 257, cplens, cplext, tl, bl, z)) != Z_OK)
  1302. {
  1303. if (r == Z_DATA_ERROR)
  1304. z->msg = "oversubscribed literal/length tree";
  1305. else if (r == Z_BUF_ERROR)
  1306. {
  1307. inflate_trees_free(*tl, z);
  1308. z->msg = "incomplete literal/length tree";
  1309. r = Z_DATA_ERROR;
  1310. }
  1311. return r;
  1312. }
  1313. /* build distance tree */
  1314. if ((r = huft_build(c + nl, nd, 0, cpdist, cpdext, td, bd, z)) != Z_OK)
  1315. {
  1316. if (r == Z_DATA_ERROR)
  1317. z->msg = "oversubscribed literal/length tree";
  1318. else if (r == Z_BUF_ERROR) {
  1319. #ifdef PKZIP_BUG_WORKAROUND
  1320. r = Z_OK;
  1321. }
  1322. #else
  1323. inflate_trees_free(*td, z);
  1324. z->msg = "incomplete literal/length tree";
  1325. r = Z_DATA_ERROR;
  1326. }
  1327. inflate_trees_free(*tl, z);
  1328. return r;
  1329. #endif
  1330. }
  1331. /* done */
  1332. return Z_OK;
  1333. }
  1334. /* build fixed tables only once--keep them here */
  1335. local int fixed_lock = 0;
  1336. local int fixed_built = 0;
  1337. #define FIXEDH 530 /* number of hufts used by fixed tables */
  1338. local uInt fixed_left = FIXEDH;
  1339. local inflate_huft fixed_mem[FIXEDH];
  1340. local uInt fixed_bl;
  1341. local uInt fixed_bd;
  1342. local inflate_huft *fixed_tl;
  1343. local inflate_huft *fixed_td;
  1344. local voidpf falloc(q, n, s)
  1345. voidpf q; /* opaque pointer (not used) */
  1346. uInt n; /* number of items */
  1347. uInt s; /* size of item */
  1348. {
  1349. Assert(s == sizeof(inflate_huft) && n <= fixed_left,
  1350. "inflate_trees falloc overflow");
  1351. if (q) s++; /* to make some compilers happy */
  1352. fixed_left -= n;
  1353. return (voidpf)(fixed_mem + fixed_left);
  1354. }
  1355. local void ffree(q, p, n)
  1356. voidpf q;
  1357. voidpf p;
  1358. uInt n;
  1359. {
  1360. Assert(0, "inflate_trees ffree called!");
  1361. if (q) q = p; /* to make some compilers happy */
  1362. }
  1363. local int inflate_trees_fixed(bl, bd, tl, td)
  1364. uIntf *bl; /* literal desired/actual bit depth */
  1365. uIntf *bd; /* distance desired/actual bit depth */
  1366. inflate_huft * FAR *tl; /* literal/length tree result */
  1367. inflate_huft * FAR *td; /* distance tree result */
  1368. {
  1369. /* build fixed tables if not built already--lock out other instances */
  1370. while (++fixed_lock > 1)
  1371. fixed_lock--;
  1372. if (!fixed_built)
  1373. {
  1374. int k; /* temporary variable */
  1375. unsigned c[288]; /* length list for huft_build */
  1376. z_stream z; /* for falloc function */
  1377. /* set up fake z_stream for memory routines */
  1378. z.zalloc = falloc;
  1379. z.zfree = ffree;
  1380. z.opaque = Z_NULL;
  1381. /* literal table */
  1382. for (k = 0; k < 144; k++)
  1383. c[k] = 8;
  1384. for (; k < 256; k++)
  1385. c[k] = 9;
  1386. for (; k < 280; k++)
  1387. c[k] = 7;
  1388. for (; k < 288; k++)
  1389. c[k] = 8;
  1390. fixed_bl = 7;
  1391. huft_build(c, 288, 257, cplens, cplext, &fixed_tl, &fixed_bl, &z);
  1392. /* distance table */
  1393. for (k = 0; k < 30; k++)
  1394. c[k] = 5;
  1395. fixed_bd = 5;
  1396. huft_build(c, 30, 0, cpdist, cpdext, &fixed_td, &fixed_bd, &z);
  1397. /* done */
  1398. fixed_built = 1;
  1399. }
  1400. fixed_lock--;
  1401. *bl = fixed_bl;
  1402. *bd = fixed_bd;
  1403. *tl = fixed_tl;
  1404. *td = fixed_td;
  1405. return Z_OK;
  1406. }
  1407. local int inflate_trees_free(t, z)
  1408. inflate_huft *t; /* table to free */
  1409. z_stream *z; /* for zfree function */
  1410. /* Free the malloc'ed tables built by huft_build(), which makes a linked
  1411. list of the tables it made, with the links in a dummy first entry of
  1412. each table. */
  1413. {
  1414. register inflate_huft *p, *q;
  1415. /* Go through linked list, freeing from the malloced (t[-1]) address. */
  1416. p = t;
  1417. while (p != Z_NULL)
  1418. {
  1419. q = (--p)->next;
  1420. ZFREE(z, p, p->word.Nalloc * sizeof(inflate_huft));
  1421. p = q;
  1422. }
  1423. return Z_OK;
  1424. }
  1425. /*+++++*/
  1426. /* infcodes.c -- process literals and length/distance pairs
  1427. * Copyright (C) 1995 Mark Adler
  1428. * For conditions of distribution and use, see copyright notice in zlib.h
  1429. */
  1430. /* simplify the use of the inflate_huft type with some defines */
  1431. #define base more.Base
  1432. #define next more.Next
  1433. #define exop word.what.Exop
  1434. #define bits word.what.Bits
  1435. /* inflate codes private state */
  1436. struct inflate_codes_state {
  1437. /* mode */
  1438. enum { /* waiting for "i:"=input, "o:"=output, "x:"=nothing */
  1439. START, /* x: set up for LEN */
  1440. LEN, /* i: get length/literal/eob next */
  1441. LENEXT, /* i: getting length extra (have base) */
  1442. DIST, /* i: get distance next */
  1443. DISTEXT, /* i: getting distance extra */
  1444. COPY, /* o: copying bytes in window, waiting for space */
  1445. LIT, /* o: got literal, waiting for output space */
  1446. WASH, /* o: got eob, possibly still output waiting */
  1447. END, /* x: got eob and all data flushed */
  1448. BADCODE} /* x: got error */
  1449. mode; /* current inflate_codes mode */
  1450. /* mode dependent information */
  1451. uInt len;
  1452. union {
  1453. struct {
  1454. inflate_huft *tree; /* pointer into tree */
  1455. uInt need; /* bits needed */
  1456. } code; /* if LEN or DIST, where in tree */
  1457. uInt lit; /* if LIT, literal */
  1458. struct {
  1459. uInt get; /* bits to get for extra */
  1460. uInt dist; /* distance back to copy from */
  1461. } copy; /* if EXT or COPY, where and how much */
  1462. } sub; /* submode */
  1463. /* mode independent information */
  1464. Byte lbits; /* ltree bits decoded per branch */
  1465. Byte dbits; /* dtree bits decoder per branch */
  1466. inflate_huft *ltree; /* literal/length/eob tree */
  1467. inflate_huft *dtree; /* distance tree */
  1468. };
  1469. local inflate_codes_statef *inflate_codes_new(bl, bd, tl, td, z)
  1470. uInt bl, bd;
  1471. inflate_huft *tl, *td;
  1472. z_stream *z;
  1473. {
  1474. inflate_codes_statef *c;
  1475. if ((c = (inflate_codes_statef *)
  1476. ZALLOC(z,1,sizeof(struct inflate_codes_state))) != Z_NULL)
  1477. {
  1478. c->mode = START;
  1479. c->lbits = (Byte)bl;
  1480. c->dbits = (Byte)bd;
  1481. c->ltree = tl;
  1482. c->dtree = td;
  1483. Tracev((stderr, "inflate: codes new\n"));
  1484. }
  1485. return c;
  1486. }
  1487. local int inflate_codes(s, z, r)
  1488. inflate_blocks_statef *s;
  1489. z_stream *z;
  1490. int r;
  1491. {
  1492. uInt j; /* temporary storage */
  1493. inflate_huft *t; /* temporary pointer */
  1494. uInt e; /* extra bits or operation */
  1495. uLong b; /* bit buffer */
  1496. uInt k; /* bits in bit buffer */
  1497. Bytef *p; /* input data pointer */
  1498. uInt n; /* bytes available there */
  1499. Bytef *q; /* output window write pointer */
  1500. uInt m; /* bytes to end of window or read pointer */
  1501. Bytef *f; /* pointer to copy strings from */
  1502. inflate_codes_statef *c = s->sub.decode.codes; /* codes state */
  1503. /* copy input/output information to locals (UPDATE macro restores) */
  1504. LOAD
  1505. /* process input and output based on current state */
  1506. while (1) switch (c->mode)
  1507. { /* waiting for "i:"=input, "o:"=output, "x:"=nothing */
  1508. case START: /* x: set up for LEN */
  1509. #ifndef SLOW
  1510. if (m >= 258 && n >= 10)
  1511. {
  1512. UPDATE
  1513. r = inflate_fast(c->lbits, c->dbits, c->ltree, c->dtree, s, z);
  1514. LOAD
  1515. if (r != Z_OK)
  1516. {
  1517. c->mode = r == Z_STREAM_END ? WASH : BADCODE;
  1518. break;
  1519. }
  1520. }
  1521. #endif /* !SLOW */
  1522. c->sub.code.need = c->lbits;
  1523. c->sub.code.tree = c->ltree;
  1524. c->mode = LEN;
  1525. case LEN: /* i: get length/literal/eob next */
  1526. j = c->sub.code.need;
  1527. NEEDBITS(j)
  1528. t = c->sub.code.tree + ((uInt)b & inflate_mask[j]);
  1529. DUMPBITS(t->bits)
  1530. e = (uInt)(t->exop);
  1531. if (e == 0) /* literal */
  1532. {
  1533. c->sub.lit = t->base;
  1534. Tracevv((stderr, t->base >= 0x20 && t->base < 0x7f ?
  1535. "inflate: literal '%c'\n" :
  1536. "inflate: literal 0x%02x\n", t->base));
  1537. c->mode = LIT;
  1538. break;
  1539. }
  1540. if (e & 16) /* length */
  1541. {
  1542. c->sub.copy.get = e & 15;
  1543. c->len = t->base;
  1544. c->mode = LENEXT;
  1545. break;
  1546. }
  1547. if ((e & 64) == 0) /* next table */
  1548. {
  1549. c->sub.code.need = e;
  1550. c->sub.code.tree = t->next;
  1551. break;
  1552. }
  1553. if (e & 32) /* end of block */
  1554. {
  1555. Tracevv((stderr, "inflate: end of block\n"));
  1556. c->mode = WASH;
  1557. break;
  1558. }
  1559. c->mode = BADCODE; /* invalid code */
  1560. z->msg = "invalid literal/length code";
  1561. r = Z_DATA_ERROR;
  1562. LEAVE
  1563. case LENEXT: /* i: getting length extra (have base) */
  1564. j = c->sub.copy.get;
  1565. NEEDBITS(j)
  1566. c->len += (uInt)b & inflate_mask[j];
  1567. DUMPBITS(j)
  1568. c->sub.code.need = c->dbits;
  1569. c->sub.code.tree = c->dtree;
  1570. Tracevv((stderr, "inflate: length %u\n", c->len));
  1571. c->mode = DIST;
  1572. case DIST: /* i: get distance next */
  1573. j = c->sub.code.need;
  1574. NEEDBITS(j)
  1575. t = c->sub.code.tree + ((uInt)b & inflate_mask[j]);
  1576. DUMPBITS(t->bits)
  1577. e = (uInt)(t->exop);
  1578. if (e & 16) /* distance */
  1579. {
  1580. c->sub.copy.get = e & 15;
  1581. c->sub.copy.dist = t->base;
  1582. c->mode = DISTEXT;
  1583. break;
  1584. }
  1585. if ((e & 64) == 0) /* next table */
  1586. {
  1587. c->sub.code.need = e;
  1588. c->sub.code.tree = t->next;
  1589. break;
  1590. }
  1591. c->mode = BADCODE; /* invalid code */
  1592. z->msg = "invalid distance code";
  1593. r = Z_DATA_ERROR;
  1594. LEAVE
  1595. case DISTEXT: /* i: getting distance extra */
  1596. j = c->sub.copy.get;
  1597. NEEDBITS(j)
  1598. c->sub.copy.dist += (uInt)b & inflate_mask[j];
  1599. DUMPBITS(j)
  1600. Tracevv((stderr, "inflate: distance %u\n", c->sub.copy.dist));
  1601. c->mode = COPY;
  1602. case COPY: /* o: copying bytes in window, waiting for space */
  1603. #ifndef __TURBOC__ /* Turbo C bug for following expression */
  1604. f = (uInt)(q - s->window) < c->sub.copy.dist ?
  1605. s->end - (c->sub.copy.dist - (q - s->window)) :
  1606. q - c->sub.copy.dist;
  1607. #else
  1608. f = q - c->sub.copy.dist;
  1609. if ((uInt)(q - s->window) < c->sub.copy.dist)
  1610. f = s->end - (c->sub.copy.dist - (q - s->window));
  1611. #endif
  1612. while (c->len)
  1613. {
  1614. NEEDOUT
  1615. OUTBYTE(*f++)
  1616. if (f == s->end)
  1617. f = s->window;
  1618. c->len--;
  1619. }
  1620. c->mode = START;
  1621. break;
  1622. case LIT: /* o: got literal, waiting for output space */
  1623. NEEDOUT
  1624. OUTBYTE(c->sub.lit)
  1625. c->mode = START;
  1626. break;
  1627. case WASH: /* o: got eob, possibly more output */
  1628. FLUSH
  1629. if (s->read != s->write)
  1630. LEAVE
  1631. c->mode = END;
  1632. case END:
  1633. r = Z_STREAM_END;
  1634. LEAVE
  1635. case BADCODE: /* x: got error */
  1636. r = Z_DATA_ERROR;
  1637. LEAVE
  1638. default:
  1639. r = Z_STREAM_ERROR;
  1640. LEAVE
  1641. }
  1642. }
  1643. local void inflate_codes_free(c, z)
  1644. inflate_codes_statef *c;
  1645. z_stream *z;
  1646. {
  1647. ZFREE(z, c, sizeof(struct inflate_codes_state));
  1648. Tracev((stderr, "inflate: codes free\n"));
  1649. }
  1650. /*+++++*/
  1651. /* inflate_util.c -- data and routines common to blocks and codes
  1652. * Copyright (C) 1995 Mark Adler
  1653. * For conditions of distribution and use, see copyright notice in zlib.h
  1654. */
  1655. /* copy as much as possible from the sliding window to the output area */
  1656. local int inflate_flush(s, z, r)
  1657. inflate_blocks_statef *s;
  1658. z_stream *z;
  1659. int r;
  1660. {
  1661. uInt n;
  1662. Bytef *p, *q;
  1663. /* local copies of source and destination pointers */
  1664. p = z->next_out;
  1665. q = s->read;
  1666. /* compute number of bytes to copy as far as end of window */
  1667. n = (uInt)((q <= s->write ? s->write : s->end) - q);
  1668. if (n > z->avail_out) n = z->avail_out;
  1669. if (n && r == Z_BUF_ERROR) r = Z_OK;
  1670. /* update counters */
  1671. z->avail_out -= n;
  1672. z->total_out += n;
  1673. /* update check information */
  1674. if (s->checkfn != Z_NULL)
  1675. s->check = (*s->checkfn)(s->check, q, n);
  1676. /* output callback */
  1677. if (z->outcb != Z_NULL)
  1678. (*z->outcb)(q, n);
  1679. /* copy as far as end of window */
  1680. zmemcpy(p, q, n);
  1681. p += n;
  1682. q += n;
  1683. /* see if more to copy at beginning of window */
  1684. if (q == s->end)
  1685. {
  1686. /* wrap pointers */
  1687. q = s->window;
  1688. if (s->write == s->end)
  1689. s->write = s->window;
  1690. /* compute bytes to copy */
  1691. n = (uInt)(s->write - q);
  1692. if (n > z->avail_out) n = z->avail_out;
  1693. if (n && r == Z_BUF_ERROR) r = Z_OK;
  1694. /* update counters */
  1695. z->avail_out -= n;
  1696. z->total_out += n;
  1697. /* update check information */
  1698. if (s->checkfn != Z_NULL)
  1699. s->check = (*s->checkfn)(s->check, q, n);
  1700. /* output callback */
  1701. if (z->outcb != Z_NULL)
  1702. (*z->outcb)(q, n);
  1703. /* copy */
  1704. zmemcpy(p, q, n);
  1705. p += n;
  1706. q += n;
  1707. }
  1708. /* update pointers */
  1709. z->next_out = p;
  1710. s->read = q;
  1711. /* done */
  1712. return r;
  1713. }
  1714. /*+++++*/
  1715. /* inffast.c -- process literals and length/distance pairs fast
  1716. * Copyright (C) 1995 Mark Adler
  1717. * For conditions of distribution and use, see copyright notice in zlib.h
  1718. */
  1719. /* simplify the use of the inflate_huft type with some defines */
  1720. #define base more.Base
  1721. #define next more.Next
  1722. #define exop word.what.Exop
  1723. #define bits word.what.Bits
  1724. /* macros for bit input with no checking and for returning unused bytes */
  1725. #define GRABBITS(j) {while(k<(j)){b|=((uLong)NEXTBYTE)<<k;k+=8;}}
  1726. #define UNGRAB {n+=(c=k>>3);p-=c;k&=7;}
  1727. /* Called with number of bytes left to write in window at least 258
  1728. (the maximum string length) and number of input bytes available
  1729. at least ten. The ten bytes are six bytes for the longest length/
  1730. distance pair plus four bytes for overloading the bit buffer. */
  1731. local int inflate_fast(bl, bd, tl, td, s, z)
  1732. uInt bl, bd;
  1733. inflate_huft *tl, *td;
  1734. inflate_blocks_statef *s;
  1735. z_stream *z;
  1736. {
  1737. inflate_huft *t; /* temporary pointer */
  1738. uInt e; /* extra bits or operation */
  1739. uLong b; /* bit buffer */
  1740. uInt k; /* bits in bit buffer */
  1741. Bytef *p; /* input data pointer */
  1742. uInt n; /* bytes available there */
  1743. Bytef *q; /* output window write pointer */
  1744. uInt m; /* bytes to end of window or read pointer */
  1745. uInt ml; /* mask for literal/length tree */
  1746. uInt md; /* mask for distance tree */
  1747. uInt c; /* bytes to copy */
  1748. uInt d; /* distance back to copy from */
  1749. Bytef *r; /* copy source pointer */
  1750. /* load input, output, bit values */
  1751. LOAD
  1752. /* initialize masks */
  1753. ml = inflate_mask[bl];
  1754. md = inflate_mask[bd];
  1755. /* do until not enough input or output space for fast loop */
  1756. do { /* assume called with m >= 258 && n >= 10 */
  1757. /* get literal/length code */
  1758. GRABBITS(20) /* max bits for literal/length code */
  1759. if ((e = (t = tl + ((uInt)b & ml))->exop) == 0)
  1760. {
  1761. DUMPBITS(t->bits)
  1762. Tracevv((stderr, t->base >= 0x20 && t->base < 0x7f ?
  1763. "inflate: * literal '%c'\n" :
  1764. "inflate: * literal 0x%02x\n", t->base));
  1765. *q++ = (Byte)t->base;
  1766. m--;
  1767. continue;
  1768. }
  1769. do {
  1770. DUMPBITS(t->bits)
  1771. if (e & 16)
  1772. {
  1773. /* get extra bits for length */
  1774. e &= 15;
  1775. c = t->base + ((uInt)b & inflate_mask[e]);
  1776. DUMPBITS(e)
  1777. Tracevv((stderr, "inflate: * length %u\n", c));
  1778. /* decode distance base of block to copy */
  1779. GRABBITS(15); /* max bits for distance code */
  1780. e = (t = td + ((uInt)b & md))->exop;
  1781. do {
  1782. DUMPBITS(t->bits)
  1783. if (e & 16)
  1784. {
  1785. /* get extra bits to add to distance base */
  1786. e &= 15;
  1787. GRABBITS(e) /* get extra bits (up to 13) */
  1788. d = t->base + ((uInt)b & inflate_mask[e]);
  1789. DUMPBITS(e)
  1790. Tracevv((stderr, "inflate: * distance %u\n", d));
  1791. /* do the copy */
  1792. m -= c;
  1793. if ((uInt)(q - s->window) >= d) /* offset before dest */
  1794. { /* just copy */
  1795. r = q - d;
  1796. *q++ = *r++; c--; /* minimum count is three, */
  1797. *q++ = *r++; c--; /* so unroll loop a little */
  1798. }
  1799. else /* else offset after destination */
  1800. {
  1801. e = d - (q - s->window); /* bytes from offset to end */
  1802. r = s->end - e; /* pointer to offset */
  1803. if (c > e) /* if source crosses, */
  1804. {
  1805. c -= e; /* copy to end of window */
  1806. do {
  1807. *q++ = *r++;
  1808. } while (--e);
  1809. r = s->window; /* copy rest from start of window */
  1810. }
  1811. }
  1812. do { /* copy all or what's left */
  1813. *q++ = *r++;
  1814. } while (--c);
  1815. break;
  1816. }
  1817. else if ((e & 64) == 0)
  1818. e = (t = t->next + ((uInt)b & inflate_mask[e]))->exop;
  1819. else
  1820. {
  1821. z->msg = "invalid distance code";
  1822. UNGRAB
  1823. UPDATE
  1824. return Z_DATA_ERROR;
  1825. }
  1826. } while (1);
  1827. break;
  1828. }
  1829. if ((e & 64) == 0)
  1830. {
  1831. if ((e = (t = t->next + ((uInt)b & inflate_mask[e]))->exop) == 0)
  1832. {
  1833. DUMPBITS(t->bits)
  1834. Tracevv((stderr, t->base >= 0x20 && t->base < 0x7f ?
  1835. "inflate: * literal '%c'\n" :
  1836. "inflate: * literal 0x%02x\n", t->base));
  1837. *q++ = (Byte)t->base;
  1838. m--;
  1839. break;
  1840. }
  1841. }
  1842. else if (e & 32)
  1843. {
  1844. Tracevv((stderr, "inflate: * end of block\n"));
  1845. UNGRAB
  1846. UPDATE
  1847. return Z_STREAM_END;
  1848. }
  1849. else
  1850. {
  1851. z->msg = "invalid literal/length code";
  1852. UNGRAB
  1853. UPDATE
  1854. return Z_DATA_ERROR;
  1855. }
  1856. } while (1);
  1857. } while (m >= 258 && n >= 10);
  1858. /* not enough input or output--restore pointers and return */
  1859. UNGRAB
  1860. UPDATE
  1861. return Z_OK;
  1862. }
  1863. /*+++++*/
  1864. /* zutil.c -- target dependent utility functions for the compression library
  1865. * Copyright (C) 1995 Jean-loup Gailly.
  1866. * For conditions of distribution and use, see copyright notice in zlib.h
  1867. */
  1868. /* From: zutil.c,v 1.8 1995/05/03 17:27:12 jloup Exp */
  1869. char *zlib_version = ZLIB_VERSION;
  1870. char *z_errmsg[] = {
  1871. "stream end", /* Z_STREAM_END 1 */
  1872. "", /* Z_OK 0 */
  1873. "file error", /* Z_ERRNO (-1) */
  1874. "stream error", /* Z_STREAM_ERROR (-2) */
  1875. "data error", /* Z_DATA_ERROR (-3) */
  1876. "insufficient memory", /* Z_MEM_ERROR (-4) */
  1877. "buffer error", /* Z_BUF_ERROR (-5) */
  1878. ""};
  1879. /*+++++*/
  1880. /* adler32.c -- compute the Adler-32 checksum of a data stream
  1881. * Copyright (C) 1995 Mark Adler
  1882. * For conditions of distribution and use, see copyright notice in zlib.h
  1883. */
  1884. /* From: adler32.c,v 1.6 1995/05/03 17:27:08 jloup Exp */
  1885. #define BASE 65521L /* largest prime smaller than 65536 */
  1886. #define NMAX 5552
  1887. /* NMAX is the largest n such that 255n(n+1)/2 + (n+1)(BASE-1) <= 2^32-1 */
  1888. #define DO1(buf) {s1 += *buf++; s2 += s1;}
  1889. #define DO2(buf) DO1(buf); DO1(buf);
  1890. #define DO4(buf) DO2(buf); DO2(buf);
  1891. #define DO8(buf) DO4(buf); DO4(buf);
  1892. #define DO16(buf) DO8(buf); DO8(buf);
  1893. /* ========================================================================= */
  1894. uLong adler32(adler, buf, len)
  1895. uLong adler;
  1896. Bytef *buf;
  1897. uInt len;
  1898. {
  1899. unsigned long s1 = adler & 0xffff;
  1900. unsigned long s2 = (adler >> 16) & 0xffff;
  1901. int k;
  1902. if (buf == Z_NULL) return 1L;
  1903. while (len > 0) {
  1904. k = len < NMAX ? len : NMAX;
  1905. len -= k;
  1906. while (k >= 16) {
  1907. DO16(buf);
  1908. k -= 16;
  1909. }
  1910. if (k != 0) do {
  1911. DO1(buf);
  1912. } while (--k);
  1913. s1 %= BASE;
  1914. s2 %= BASE;
  1915. }
  1916. return (s2 << 16) | s1;
  1917. }