You can not select more than 25 topics Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.

nrv2b.c 31KB

1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677787980818283848586878889909192939495969798991001011021031041051061071081091101111121131141151161171181191201211221231241251261271281291301311321331341351361371381391401411421431441451461471481491501511521531541551561571581591601611621631641651661671681691701711721731741751761771781791801811821831841851861871881891901911921931941951961971981992002012022032042052062072082092102112122132142152162172182192202212222232242252262272282292302312322332342352362372382392402412422432442452462472482492502512522532542552562572582592602612622632642652662672682692702712722732742752762772782792802812822832842852862872882892902912922932942952962972982993003013023033043053063073083093103113123133143153163173183193203213223233243253263273283293303313323333343353363373383393403413423433443453463473483493503513523533543553563573583593603613623633643653663673683693703713723733743753763773783793803813823833843853863873883893903913923933943953963973983994004014024034044054064074084094104114124134144154164174184194204214224234244254264274284294304314324334344354364374384394404414424434444454464474484494504514524534544554564574584594604614624634644654664674684694704714724734744754764774784794804814824834844854864874884894904914924934944954964974984995005015025035045055065075085095105115125135145155165175185195205215225235245255265275285295305315325335345355365375385395405415425435445455465475485495505515525535545555565575585595605615625635645655665675685695705715725735745755765775785795805815825835845855865875885895905915925935945955965975985996006016026036046056066076086096106116126136146156166176186196206216226236246256266276286296306316326336346356366376386396406416426436446456466476486496506516526536546556566576586596606616626636646656666676686696706716726736746756766776786796806816826836846856866876886896906916926936946956966976986997007017027037047057067077087097107117127137147157167177187197207217227237247257267277287297307317327337347357367377387397407417427437447457467477487497507517527537547557567577587597607617627637647657667677687697707717727737747757767777787797807817827837847857867877887897907917927937947957967977987998008018028038048058068078088098108118128138148158168178188198208218228238248258268278288298308318328338348358368378388398408418428438448458468478488498508518528538548558568578588598608618628638648658668678688698708718728738748758768778788798808818828838848858868878888898908918928938948958968978988999009019029039049059069079089099109119129139149159169179189199209219229239249259269279289299309319329339349359369379389399409419429439449459469479489499509519529539549559569579589599609619629639649659669679689699709719729739749759769779789799809819829839849859869879889899909919929939949959969979989991000100110021003100410051006100710081009101010111012101310141015101610171018101910201021102210231024102510261027102810291030103110321033103410351036103710381039104010411042104310441045104610471048104910501051105210531054105510561057105810591060106110621063106410651066106710681069107010711072107310741075107610771078107910801081108210831084108510861087108810891090109110921093109410951096109710981099110011011102110311041105110611071108110911101111111211131114111511161117111811191120112111221123112411251126112711281129113011311132113311341135113611371138113911401141114211431144114511461147114811491150115111521153115411551156115711581159116011611162116311641165116611671168116911701171117211731174117511761177117811791180118111821183118411851186118711881189119011911192119311941195119611971198119912001201120212031204120512061207120812091210121112121213121412151216121712181219122012211222122312241225122612271228122912301231123212331234123512361237123812391240124112421243124412451246124712481249125012511252125312541255125612571258125912601261126212631264126512661267126812691270127112721273127412751276127712781279128012811282128312841285128612871288128912901291129212931294129512961297129812991300130113021303130413051306130713081309131013111312131313141315131613171318131913201321132213231324132513261327132813291330133113321333133413351336133713381339134013411342134313441345134613471348134913501351135213531354135513561357135813591360136113621363136413651366136713681369137013711372137313741375137613771378137913801381138213831384138513861387138813891390139113921393139413951396139713981399140014011402140314041405140614071408140914101411141214131414141514161417141814191420142114221423142414251426142714281429143014311432143314341435143614371438143914401441144214431444144514461447144814491450145114521453145414551456145714581459146014611462146314641465146614671468146914701471147214731474147514761477147814791480148114821483148414851486148714881489149014911492149314941495149614971498149915001501
  1. /**************************************************************
  2. Form adapted from lzhuf.c
  3. written by Haruyasu Yoshizaki 11/20/1988
  4. some minor changes 4/6/1989
  5. comments translated by Haruhiko Okumura 4/7/1989
  6. minor beautifications and adjustments for compiling under Linux
  7. by Markus Gutschke <gutschk@math.uni-muenster.de>
  8. 1997-01-27
  9. Modifications to allow use as a filter by Ken Yap
  10. <ken_yap@users.sourceforge.net>.
  11. 1997-07-01
  12. Small mod to cope with running on big-endian machines
  13. by Jim Hague <jim.hague@acm.org)
  14. 1998-02-06
  15. Make compression statistics report shorter
  16. by Ken Yap <ken_yap@users.sourceforge.net>.
  17. 2001-04-25
  18. Replaced algorithm with nrv2b from ucl the compression
  19. library from upx. That code is:
  20. Copyright (C) 1996-2002 Markus Franz Xaver Johannes Oberhumer
  21. And is distributed under the terms of the GPL.
  22. The conversion was performed
  23. by Eric Biederman <ebiederman@lnxi.com>.
  24. 20 August 2002
  25. **************************************************************/
  26. #define UCLPACK_COMPAT 0
  27. #define NDEBUG 1
  28. #include <stdio.h>
  29. #include <stdlib.h>
  30. #include <string.h>
  31. #include <ctype.h>
  32. #include <errno.h>
  33. #ifdef __FreeBSD__
  34. #include <inttypes.h>
  35. #else
  36. #include <stdint.h>
  37. #endif
  38. #include <limits.h>
  39. #include <assert.h>
  40. #if UCLPACK_COMPAT
  41. #include <netinet/in.h>
  42. #endif
  43. #ifndef VERBOSE
  44. #define Fprintf(x)
  45. #define wterr 0
  46. #else
  47. #define Fprintf(x) fprintf x
  48. #endif
  49. #ifndef MAIN
  50. extern
  51. #endif
  52. FILE *infile, *outfile;
  53. #if defined(ENCODE) || defined(DECODE)
  54. #ifndef ENDIAN
  55. #define ENDIAN 0
  56. #endif
  57. #ifndef BITSIZE
  58. #define BITSIZE 32
  59. #endif
  60. static __inline__ void Error(char *message)
  61. {
  62. Fprintf((stderr, "\n%s\n", message));
  63. exit(EXIT_FAILURE);
  64. }
  65. /* These will be a complete waste of time on a lo-endian */
  66. /* system, but it only gets done once so WTF. */
  67. static unsigned long i86ul_to_host(unsigned long ul)
  68. {
  69. unsigned long res = 0;
  70. int i;
  71. union
  72. {
  73. unsigned char c[4];
  74. unsigned long ul;
  75. } u;
  76. u.ul = ul;
  77. for (i = 3; i >= 0; i--)
  78. res = (res << 8) + u.c[i];
  79. return res;
  80. }
  81. static unsigned long host_to_i86ul(unsigned long ul)
  82. {
  83. int i;
  84. union
  85. {
  86. unsigned char c[4];
  87. unsigned long ul;
  88. } u;
  89. for (i = 0; i < 4; i++)
  90. {
  91. u.c[i] = ul & 0xff;
  92. ul >>= 8;
  93. }
  94. return u.ul;
  95. }
  96. #endif
  97. #if UCLPACK_COMPAT
  98. /* magic file header for compressed files */
  99. static const unsigned char magic[8] =
  100. { 0x00, 0xe9, 0x55, 0x43, 0x4c, 0xff, 0x01, 0x1a };
  101. #endif
  102. #ifdef ENCODE
  103. /********** NRV2B_99 compression **********/
  104. /* Note by limiting the ring buffer I have limited the maximum
  105. * offset to 64K. Since etherboot rarely gets that big it
  106. * is not a problem and it gives me a firm guarantee
  107. * that I will never get a 3 byte string match that is encodes
  108. * to more than 9/8 it's original size.
  109. * That guaranteee is important to for the inplace decompressor.
  110. * There are better ways to do this if a larger offset and buffer
  111. * would give better compression.
  112. */
  113. #define N (65536ul) /* size of ring buffer */
  114. #define THRESHOLD 1 /* lower limit for match length */
  115. #define F 2048 /* upper limit for match length */
  116. #define M2_MAX_OFFSET 0xd00
  117. /* note: to use default values pass -1, i.e. initialize
  118. * this struct by a memset(x,0xff,sizeof(x)) */
  119. struct ucl_compress_config
  120. {
  121. int bb_endian;
  122. int bb_size;
  123. unsigned int max_offset;
  124. unsigned int max_match;
  125. int s_level;
  126. int h_level;
  127. int p_level;
  128. int c_flags;
  129. unsigned int m_size;
  130. };
  131. struct ucl_compress
  132. {
  133. int init;
  134. unsigned int look; /* bytes in lookahead buffer */
  135. unsigned int m_len;
  136. unsigned int m_off;
  137. unsigned int last_m_len;
  138. unsigned int last_m_off;
  139. const unsigned char *bp;
  140. const unsigned char *ip;
  141. const unsigned char *in;
  142. const unsigned char *in_end;
  143. unsigned char *out;
  144. uint64_t bb_b;
  145. unsigned bb_k;
  146. unsigned bb_c_endian;
  147. unsigned bb_c_s;
  148. unsigned bb_c_s8;
  149. unsigned char *bb_p;
  150. unsigned char *bb_op;
  151. struct ucl_compress_config conf;
  152. unsigned int *result;
  153. unsigned int textsize; /* text size counter */
  154. unsigned int codesize; /* code size counter */
  155. unsigned int printcount; /* counter for reporting progress every 1K
  156. bytes */
  157. /* some stats */
  158. unsigned long lit_bytes;
  159. unsigned long match_bytes;
  160. unsigned long rep_bytes;
  161. unsigned long lazy;
  162. };
  163. #define getbyte(c) ((c).ip < (c).in_end ? *((c).ip)++ : (-1))
  164. #define UCL_E_OK 0
  165. #define UCL_E_INVALID_ARGUMENT 1
  166. #define UCL_E_OUT_OF_MEMORY 2
  167. #define UCL_E_ERROR 3
  168. /***********************************************************************
  169. //
  170. ************************************************************************/
  171. #define SWD_HSIZE 16384
  172. #define SWD_MAX_CHAIN 2048
  173. #define SWD_BEST_OFF 1
  174. #define HEAD3(b,p) \
  175. (((0x9f5f*(((((uint32_t)b[p]<<5)^b[p+1])<<5)^b[p+2]))>>5) & (SWD_HSIZE-1))
  176. #define HEAD2(b,p) (b[p] ^ ((unsigned)b[p+1]<<8))
  177. #define NIL2 UINT_MAX
  178. struct ucl_swd
  179. {
  180. /* public - "built-in" */
  181. unsigned int n;
  182. unsigned int f;
  183. unsigned int threshold;
  184. /* public - configuration */
  185. unsigned int max_chain;
  186. unsigned int nice_length;
  187. int use_best_off;
  188. unsigned int lazy_insert;
  189. /* public - output */
  190. unsigned int m_len;
  191. unsigned int m_off;
  192. unsigned int look;
  193. int b_char;
  194. #if defined(SWD_BEST_OFF)
  195. unsigned int best_off[ SWD_BEST_OFF ];
  196. #endif
  197. /* semi public */
  198. struct ucl_compress *c;
  199. unsigned int m_pos;
  200. #if defined(SWD_BEST_OFF)
  201. unsigned int best_pos[ SWD_BEST_OFF ];
  202. #endif
  203. /* private */
  204. const uint8_t *dict;
  205. const uint8_t *dict_end;
  206. unsigned int dict_len;
  207. /* private */
  208. unsigned int ip; /* input pointer (lookahead) */
  209. unsigned int bp; /* buffer pointer */
  210. unsigned int rp; /* remove pointer */
  211. unsigned int b_size;
  212. unsigned char *b_wrap;
  213. unsigned int node_count;
  214. unsigned int first_rp;
  215. unsigned char b [ N + F + F ];
  216. unsigned int head3 [ SWD_HSIZE ];
  217. unsigned int succ3 [ N + F ];
  218. unsigned int best3 [ N + F ];
  219. unsigned int llen3 [ SWD_HSIZE ];
  220. unsigned int head2 [ 65536U ];
  221. };
  222. #define s_head3(s,key) s->head3[key]
  223. #if !defined( NDEBUG)
  224. static void assert_match(const struct ucl_swd * swd, unsigned int m_len,
  225. unsigned int m_off )
  226. {
  227. const struct ucl_compress *c = swd->c;
  228. unsigned int d_off;
  229. assert(m_len >= 2);
  230. if (m_off <= (unsigned int) (c->bp - c->in))
  231. {
  232. assert(c->bp - m_off + m_len < c->ip);
  233. assert(memcmp(c->bp, c->bp - m_off, m_len) == 0);
  234. }
  235. else
  236. {
  237. assert(swd->dict != NULL);
  238. d_off = m_off - (unsigned int) (c->bp - c->in);
  239. assert(d_off <= swd->dict_len);
  240. if (m_len > d_off)
  241. {
  242. assert(memcmp(c->bp, swd->dict_end - d_off, d_off) ==
  243. 0);
  244. assert(c->in + m_len - d_off < c->ip);
  245. assert(memcmp(c->bp + d_off, c->in, m_len - d_off) ==
  246. 0);
  247. }
  248. else
  249. {
  250. assert(memcmp(c->bp, swd->dict_end - d_off, m_len) ==
  251. 0);
  252. }
  253. }
  254. }
  255. #else
  256. # define assert_match(a,b,c) ((void)0)
  257. #endif
  258. /***********************************************************************
  259. //
  260. ************************************************************************/
  261. static
  262. void swd_initdict(struct ucl_swd *s, const uint8_t *dict, unsigned int dict_len)
  263. {
  264. s->dict = s->dict_end = NULL;
  265. s->dict_len = 0;
  266. if (!dict || dict_len <= 0)
  267. return;
  268. if (dict_len > s->n)
  269. {
  270. dict += dict_len - s->n;
  271. dict_len = s->n;
  272. }
  273. s->dict = dict;
  274. s->dict_len = dict_len;
  275. s->dict_end = dict + dict_len;
  276. memcpy(s->b,dict,dict_len);
  277. s->ip = dict_len;
  278. }
  279. static
  280. void swd_insertdict(struct ucl_swd *s, unsigned int node, unsigned int len)
  281. {
  282. unsigned int key;
  283. s->node_count = s->n - len;
  284. s->first_rp = node;
  285. while (len-- > 0)
  286. {
  287. key = HEAD3(s->b,node);
  288. s->succ3[node] = s_head3(s,key);
  289. s->head3[key] = (unsigned int)(node);
  290. s->best3[node] = (unsigned int)(s->f + 1);
  291. s->llen3[key]++;
  292. assert(s->llen3[key] <= s->n);
  293. key = HEAD2(s->b,node);
  294. s->head2[key] = (unsigned int)(node);
  295. node++;
  296. }
  297. }
  298. /***********************************************************************
  299. //
  300. ************************************************************************/
  301. static
  302. int swd_init(struct ucl_swd *s, const uint8_t *dict, unsigned int dict_len)
  303. {
  304. unsigned int i = 0;
  305. int c = 0;
  306. if (s->n == 0)
  307. s->n = N;
  308. if (s->f == 0)
  309. s->f = F;
  310. s->threshold = THRESHOLD;
  311. if (s->n > N || s->f > F)
  312. return UCL_E_INVALID_ARGUMENT;
  313. /* defaults */
  314. s->max_chain = SWD_MAX_CHAIN;
  315. s->nice_length = s->f;
  316. s->use_best_off = 0;
  317. s->lazy_insert = 0;
  318. s->b_size = s->n + s->f;
  319. if (s->b_size + s->f >= UINT_MAX)
  320. return UCL_E_ERROR;
  321. s->b_wrap = s->b + s->b_size;
  322. s->node_count = s->n;
  323. memset(s->llen3, 0, sizeof(s->llen3[0]) * SWD_HSIZE);
  324. for (i = 0; i < 65536U; i++)
  325. s->head2[i] = NIL2;
  326. s->ip = 0;
  327. swd_initdict(s,dict,dict_len);
  328. s->bp = s->ip;
  329. s->first_rp = s->ip;
  330. assert(s->ip + s->f <= s->b_size);
  331. s->look = (unsigned int) (s->c->in_end - s->c->ip);
  332. if (s->look > 0)
  333. {
  334. if (s->look > s->f)
  335. s->look = s->f;
  336. memcpy(&s->b[s->ip],s->c->ip,s->look);
  337. s->c->ip += s->look;
  338. s->ip += s->look;
  339. }
  340. if (s->ip == s->b_size)
  341. s->ip = 0;
  342. if (s->look >= 2 && s->dict_len > 0)
  343. swd_insertdict(s,0,s->dict_len);
  344. s->rp = s->first_rp;
  345. if (s->rp >= s->node_count)
  346. s->rp -= s->node_count;
  347. else
  348. s->rp += s->b_size - s->node_count;
  349. /* unused i */
  350. /* unused c */
  351. return UCL_E_OK;
  352. }
  353. static
  354. void swd_exit(struct ucl_swd *s)
  355. {
  356. /* unused s */
  357. }
  358. #define swd_pos2off(s,pos) \
  359. (s->bp > (pos) ? s->bp - (pos) : s->b_size - ((pos) - s->bp))
  360. /***********************************************************************
  361. //
  362. ************************************************************************/
  363. static __inline__
  364. void swd_getbyte(struct ucl_swd *s)
  365. {
  366. int c;
  367. if ((c = getbyte(*(s->c))) < 0)
  368. {
  369. if (s->look > 0)
  370. --s->look;
  371. }
  372. else
  373. {
  374. s->b[s->ip] = (uint8_t)(c);
  375. if (s->ip < s->f)
  376. s->b_wrap[s->ip] = (uint8_t)(c);
  377. }
  378. if (++s->ip == s->b_size)
  379. s->ip = 0;
  380. if (++s->bp == s->b_size)
  381. s->bp = 0;
  382. if (++s->rp == s->b_size)
  383. s->rp = 0;
  384. }
  385. /***********************************************************************
  386. // remove node from lists
  387. ************************************************************************/
  388. static __inline__
  389. void swd_remove_node(struct ucl_swd *s, unsigned int node)
  390. {
  391. if (s->node_count == 0)
  392. {
  393. unsigned int key;
  394. #ifdef UCL_DEBUG
  395. if (s->first_rp != UINT_MAX)
  396. {
  397. if (node != s->first_rp)
  398. printf("Remove %5d: %5d %5d %5d %5d %6d %6d\n",
  399. node, s->rp, s->ip, s->bp, s->first_rp,
  400. s->ip - node, s->ip - s->bp);
  401. assert(node == s->first_rp);
  402. s->first_rp = UINT_MAX;
  403. }
  404. #endif
  405. key = HEAD3(s->b,node);
  406. assert(s->llen3[key] > 0);
  407. --s->llen3[key];
  408. key = HEAD2(s->b,node);
  409. assert(s->head2[key] != NIL2);
  410. if ((unsigned int) s->head2[key] == node)
  411. s->head2[key] = NIL2;
  412. }
  413. else
  414. --s->node_count;
  415. }
  416. /***********************************************************************
  417. //
  418. ************************************************************************/
  419. static
  420. void swd_accept(struct ucl_swd *s, unsigned int n)
  421. {
  422. assert(n <= s->look);
  423. if (n > 0) do
  424. {
  425. unsigned int key;
  426. swd_remove_node(s,s->rp);
  427. /* add bp into HEAD3 */
  428. key = HEAD3(s->b,s->bp);
  429. s->succ3[s->bp] = s_head3(s,key);
  430. s->head3[key] = (unsigned int)(s->bp);
  431. s->best3[s->bp] = (unsigned int)(s->f + 1);
  432. s->llen3[key]++;
  433. assert(s->llen3[key] <= s->n);
  434. /* add bp into HEAD2 */
  435. key = HEAD2(s->b,s->bp);
  436. s->head2[key] = (unsigned int)(s->bp);
  437. swd_getbyte(s);
  438. } while (--n > 0);
  439. }
  440. /***********************************************************************
  441. //
  442. ************************************************************************/
  443. static
  444. void swd_search(struct ucl_swd *s, unsigned int node, unsigned int cnt)
  445. {
  446. const unsigned char *p1;
  447. const unsigned char *p2;
  448. const unsigned char *px;
  449. unsigned int m_len = s->m_len;
  450. const unsigned char * b = s->b;
  451. const unsigned char * bp = s->b + s->bp;
  452. const unsigned char * bx = s->b + s->bp + s->look;
  453. unsigned char scan_end1;
  454. assert(s->m_len > 0);
  455. scan_end1 = bp[m_len - 1];
  456. for ( ; cnt-- > 0; node = s->succ3[node])
  457. {
  458. p1 = bp;
  459. p2 = b + node;
  460. px = bx;
  461. assert(m_len < s->look);
  462. if (
  463. p2[m_len - 1] == scan_end1 &&
  464. p2[m_len] == p1[m_len] &&
  465. p2[0] == p1[0] &&
  466. p2[1] == p1[1])
  467. {
  468. unsigned int i;
  469. assert(memcmp(bp,&b[node],3) == 0);
  470. p1 += 2; p2 += 2;
  471. do {} while (++p1 < px && *p1 == *++p2);
  472. i = p1 - bp;
  473. #ifdef UCL_DEBUG
  474. if (memcmp(bp,&b[node],i) != 0)
  475. printf("%5ld %5ld %02x%02x %02x%02x\n",
  476. (long)s->bp, (long) node,
  477. bp[0], bp[1], b[node], b[node+1]);
  478. #endif
  479. assert(memcmp(bp,&b[node],i) == 0);
  480. #if defined(SWD_BEST_OFF)
  481. if (i < SWD_BEST_OFF)
  482. {
  483. if (s->best_pos[i] == 0)
  484. s->best_pos[i] = node + 1;
  485. }
  486. #endif
  487. if (i > m_len)
  488. {
  489. s->m_len = m_len = i;
  490. s->m_pos = node;
  491. if (m_len == s->look)
  492. return;
  493. if (m_len >= s->nice_length)
  494. return;
  495. if (m_len > (unsigned int) s->best3[node])
  496. return;
  497. scan_end1 = bp[m_len - 1];
  498. }
  499. }
  500. }
  501. }
  502. static int swd_search2(struct ucl_swd *s)
  503. {
  504. unsigned int key;
  505. assert(s->look >= 2);
  506. assert(s->m_len > 0);
  507. key = s->head2[ HEAD2(s->b,s->bp) ];
  508. if (key == NIL2)
  509. return 0;
  510. #ifdef UCL_DEBUG
  511. if (memcmp(&s->b[s->bp],&s->b[key],2) != 0)
  512. printf("%5ld %5ld %02x%02x %02x%02x\n", (long)s->bp, (long)key,
  513. s->b[s->bp], s->b[s->bp+1], s->b[key], s->b[key+1]);
  514. #endif
  515. assert(memcmp(&s->b[s->bp],&s->b[key],2) == 0);
  516. #if defined(SWD_BEST_OFF)
  517. if (s->best_pos[2] == 0)
  518. s->best_pos[2] = key + 1;
  519. #endif
  520. if (s->m_len < 2)
  521. {
  522. s->m_len = 2;
  523. s->m_pos = key;
  524. }
  525. return 1;
  526. }
  527. /***********************************************************************
  528. //
  529. ************************************************************************/
  530. static
  531. void swd_findbest(struct ucl_swd *s)
  532. {
  533. unsigned int key;
  534. unsigned int cnt, node;
  535. unsigned int len;
  536. assert(s->m_len > 0);
  537. /* get current head, add bp into HEAD3 */
  538. key = HEAD3(s->b,s->bp);
  539. node = s->succ3[s->bp] = s_head3(s,key);
  540. cnt = s->llen3[key]++;
  541. assert(s->llen3[key] <= s->n + s->f);
  542. if (cnt > s->max_chain && s->max_chain > 0)
  543. cnt = s->max_chain;
  544. s->head3[key] = (unsigned int)(s->bp);
  545. s->b_char = s->b[s->bp];
  546. len = s->m_len;
  547. if (s->m_len >= s->look)
  548. {
  549. if (s->look == 0)
  550. s->b_char = -1;
  551. s->m_off = 0;
  552. s->best3[s->bp] = (unsigned int)(s->f + 1);
  553. }
  554. else
  555. {
  556. if (swd_search2(s))
  557. if (s->look >= 3)
  558. swd_search(s,node,cnt);
  559. if (s->m_len > len)
  560. s->m_off = swd_pos2off(s,s->m_pos);
  561. s->best3[s->bp] = (unsigned int)(s->m_len);
  562. #if defined(SWD_BEST_OFF)
  563. if (s->use_best_off)
  564. {
  565. int i;
  566. for (i = 2; i < SWD_BEST_OFF; i++)
  567. if (s->best_pos[i] > 0)
  568. s->best_off[i] =
  569. swd_pos2off(s,s->best_pos[i]-1);
  570. else
  571. s->best_off[i] = 0;
  572. }
  573. #endif
  574. }
  575. swd_remove_node(s,s->rp);
  576. /* add bp into HEAD2 */
  577. key = HEAD2(s->b,s->bp);
  578. s->head2[key] = (unsigned int)(s->bp);
  579. }
  580. /***********************************************************************
  581. //
  582. ************************************************************************/
  583. static int
  584. init_match ( struct ucl_compress *c, struct ucl_swd *s,
  585. const uint8_t *dict, unsigned int dict_len,
  586. uint32_t flags )
  587. {
  588. int r;
  589. assert(!c->init);
  590. c->init = 1;
  591. s->c = c;
  592. c->last_m_len = c->last_m_off = 0;
  593. c->textsize = c->codesize = c->printcount = 0;
  594. c->lit_bytes = c->match_bytes = c->rep_bytes = 0;
  595. c->lazy = 0;
  596. r = swd_init(s,dict,dict_len);
  597. if (r != UCL_E_OK)
  598. {
  599. swd_exit(s);
  600. return r;
  601. }
  602. s->use_best_off = (flags & 1) ? 1 : 0;
  603. return UCL_E_OK;
  604. }
  605. static int
  606. find_match ( struct ucl_compress *c, struct ucl_swd *s,
  607. unsigned int this_len, unsigned int skip )
  608. {
  609. assert(c->init);
  610. if (skip > 0)
  611. {
  612. assert(this_len >= skip);
  613. swd_accept(s, this_len - skip);
  614. c->textsize += this_len - skip + 1;
  615. }
  616. else
  617. {
  618. assert(this_len <= 1);
  619. c->textsize += this_len - skip;
  620. }
  621. s->m_len = THRESHOLD;
  622. #ifdef SWD_BEST_OFF
  623. if (s->use_best_off)
  624. memset(s->best_pos,0,sizeof(s->best_pos));
  625. #endif
  626. swd_findbest(s);
  627. c->m_len = s->m_len;
  628. c->m_off = s->m_off;
  629. swd_getbyte(s);
  630. if (s->b_char < 0)
  631. {
  632. c->look = 0;
  633. c->m_len = 0;
  634. swd_exit(s);
  635. }
  636. else
  637. {
  638. c->look = s->look + 1;
  639. }
  640. c->bp = c->ip - c->look;
  641. #if 0
  642. /* brute force match search */
  643. if (c->m_len > THRESHOLD && c->m_len + 1 <= c->look)
  644. {
  645. const uint8_t *ip = c->bp;
  646. const uint8_t *m = c->bp - c->m_off;
  647. const uint8_t *in = c->in;
  648. if (ip - in > N)
  649. in = ip - N;
  650. for (;;)
  651. {
  652. while (*in != *ip)
  653. in++;
  654. if (in == ip)
  655. break;
  656. if (in != m)
  657. if (memcmp(in,ip,c->m_len+1) == 0)
  658. printf("%p %p %p %5d\n",in,ip,m,c->m_len);
  659. in++;
  660. }
  661. }
  662. #endif
  663. return UCL_E_OK;
  664. }
  665. static int bbConfig(struct ucl_compress *c, int endian, int bitsize)
  666. {
  667. if (endian != -1)
  668. {
  669. if (endian != 0)
  670. return UCL_E_ERROR;
  671. c->bb_c_endian = endian;
  672. }
  673. if (bitsize != -1)
  674. {
  675. if (bitsize != 8 && bitsize != 16 && bitsize != 32 && bitsize != 64)
  676. return UCL_E_ERROR;
  677. c->bb_c_s = bitsize;
  678. c->bb_c_s8 = bitsize / 8;
  679. }
  680. c->bb_b = 0; c->bb_k = 0;
  681. c->bb_p = NULL;
  682. c->bb_op = NULL;
  683. return UCL_E_OK;
  684. }
  685. static void bbWriteBits(struct ucl_compress *c)
  686. {
  687. uint8_t *p = c->bb_p;
  688. uint64_t b = c->bb_b;
  689. p[0] = (uint8_t)(b >> 0);
  690. if (c->bb_c_s >= 16)
  691. {
  692. p[1] = (uint8_t)(b >> 8);
  693. if (c->bb_c_s >= 32)
  694. {
  695. p[2] = (uint8_t)(b >> 16);
  696. p[3] = (uint8_t)(b >> 24);
  697. if (c->bb_c_s == 64)
  698. {
  699. p[4] = (uint8_t)(b >> 32);
  700. p[5] = (uint8_t)(b >> 40);
  701. p[6] = (uint8_t)(b >> 48);
  702. p[7] = (uint8_t)(b >> 56);
  703. }
  704. }
  705. }
  706. }
  707. static void bbPutBit(struct ucl_compress *c, unsigned bit)
  708. {
  709. assert(bit == 0 || bit == 1);
  710. assert(c->bb_k <= c->bb_c_s);
  711. if (c->bb_k < c->bb_c_s)
  712. {
  713. if (c->bb_k == 0)
  714. {
  715. assert(c->bb_p == NULL);
  716. c->bb_p = c->bb_op;
  717. c->bb_op += c->bb_c_s8;
  718. }
  719. assert(c->bb_p != NULL);
  720. assert(c->bb_p + c->bb_c_s8 <= c->bb_op);
  721. c->bb_b = (c->bb_b << 1) + bit;
  722. c->bb_k++;
  723. }
  724. else
  725. {
  726. assert(c->bb_p != NULL);
  727. assert(c->bb_p + c->bb_c_s8 <= c->bb_op);
  728. bbWriteBits(c);
  729. c->bb_p = c->bb_op;
  730. c->bb_op += c->bb_c_s8;
  731. c->bb_b = bit;
  732. c->bb_k = 1;
  733. }
  734. }
  735. static void bbPutByte(struct ucl_compress *c, unsigned b)
  736. {
  737. /**printf("putbyte %p %p %x (%d)\n", op, bb_p, x, bb_k);*/
  738. assert(c->bb_p == NULL || c->bb_p + c->bb_c_s8 <= c->bb_op);
  739. *c->bb_op++ = (uint8_t)(b);
  740. }
  741. static void bbFlushBits(struct ucl_compress *c, unsigned filler_bit)
  742. {
  743. if (c->bb_k > 0)
  744. {
  745. assert(c->bb_k <= c->bb_c_s);
  746. while (c->bb_k != c->bb_c_s)
  747. bbPutBit(c, filler_bit);
  748. bbWriteBits(c);
  749. c->bb_k = 0;
  750. }
  751. c->bb_p = NULL;
  752. }
  753. /***********************************************************************
  754. //
  755. ************************************************************************/
  756. static void code_prefix_ss11(struct ucl_compress *c, uint32_t i)
  757. {
  758. if (i >= 2)
  759. {
  760. uint32_t t = 4;
  761. i += 2;
  762. do {
  763. t <<= 1;
  764. } while (i >= t);
  765. t >>= 1;
  766. do {
  767. t >>= 1;
  768. bbPutBit(c, (i & t) ? 1 : 0);
  769. bbPutBit(c, 0);
  770. } while (t > 2);
  771. }
  772. bbPutBit(c, (unsigned)i & 1);
  773. bbPutBit(c, 1);
  774. }
  775. static void
  776. code_match(struct ucl_compress *c, unsigned int m_len, const unsigned int m_off)
  777. {
  778. while (m_len > c->conf.max_match)
  779. {
  780. code_match(c, c->conf.max_match - 3, m_off);
  781. m_len -= c->conf.max_match - 3;
  782. }
  783. c->match_bytes += m_len;
  784. if (m_len > c->result[3])
  785. c->result[3] = m_len;
  786. if (m_off > c->result[1])
  787. c->result[1] = m_off;
  788. bbPutBit(c, 0);
  789. if (m_off == c->last_m_off)
  790. {
  791. bbPutBit(c, 0);
  792. bbPutBit(c, 1);
  793. }
  794. else
  795. {
  796. code_prefix_ss11(c, 1 + ((m_off - 1) >> 8));
  797. bbPutByte(c, (unsigned)m_off - 1);
  798. }
  799. m_len = m_len - 1 - (m_off > M2_MAX_OFFSET);
  800. if (m_len >= 4)
  801. {
  802. bbPutBit(c,0);
  803. bbPutBit(c,0);
  804. code_prefix_ss11(c, m_len - 4);
  805. }
  806. else
  807. {
  808. bbPutBit(c, m_len > 1);
  809. bbPutBit(c, (unsigned)m_len & 1);
  810. }
  811. c->last_m_off = m_off;
  812. }
  813. static void
  814. code_run(struct ucl_compress *c, const uint8_t *ii, unsigned int lit)
  815. {
  816. if (lit == 0)
  817. return;
  818. c->lit_bytes += lit;
  819. if (lit > c->result[5])
  820. c->result[5] = lit;
  821. do {
  822. bbPutBit(c, 1);
  823. bbPutByte(c, *ii++);
  824. } while (--lit > 0);
  825. }
  826. /***********************************************************************
  827. //
  828. ************************************************************************/
  829. static int
  830. len_of_coded_match(struct ucl_compress *c, unsigned int m_len, unsigned int
  831. m_off)
  832. {
  833. int b;
  834. if (m_len < 2 || (m_len == 2 && (m_off > M2_MAX_OFFSET))
  835. || m_off > c->conf.max_offset)
  836. return -1;
  837. assert(m_off > 0);
  838. m_len = m_len - 2 - (m_off > M2_MAX_OFFSET);
  839. if (m_off == c->last_m_off)
  840. b = 1 + 2;
  841. else
  842. {
  843. b = 1 + 10;
  844. m_off = (m_off - 1) >> 8;
  845. while (m_off > 0)
  846. {
  847. b += 2;
  848. m_off >>= 1;
  849. }
  850. }
  851. b += 2;
  852. if (m_len < 3)
  853. return b;
  854. m_len -= 3;
  855. do {
  856. b += 2;
  857. m_len >>= 1;
  858. } while (m_len > 0);
  859. return b;
  860. }
  861. int ucl_nrv2b_99_compress(
  862. const uint8_t *in, unsigned long in_len,
  863. uint8_t *out, unsigned long *out_len,
  864. unsigned int *result)
  865. {
  866. const uint8_t *ii;
  867. unsigned int lit;
  868. unsigned int m_len, m_off;
  869. struct ucl_compress c_buffer;
  870. struct ucl_compress * const c = &c_buffer;
  871. struct ucl_swd *swd;
  872. unsigned int result_buffer[16];
  873. int r;
  874. /* max compression */
  875. #define SC_TRY_LAZY 2
  876. #define SC_GOOD_LENGTH F
  877. #define SC_MAX_LAZY F
  878. #define SC_NICE_LENGTH F
  879. #define SC_MAX_CHAIN 4096
  880. #define SC_FLAGS 1
  881. #define SC_MAX_OFFSET N
  882. memset(c, 0, sizeof(*c));
  883. c->ip = c->in = in;
  884. c->in_end = in + in_len;
  885. c->out = out;
  886. c->result = result ? result : result_buffer;
  887. memset(c->result, 0, 16*sizeof(*c->result));
  888. c->result[0] = c->result[2] = c->result[4] = UINT_MAX;
  889. result = NULL;
  890. memset(&c->conf, 0xff, sizeof(c->conf));
  891. r = bbConfig(c, ENDIAN, BITSIZE);
  892. if (r == 0)
  893. r = bbConfig(c, c->conf.bb_endian, c->conf.bb_size);
  894. if (r != 0)
  895. return UCL_E_INVALID_ARGUMENT;
  896. c->bb_op = out;
  897. ii = c->ip; /* point to start of literal run */
  898. lit = 0;
  899. swd = (struct ucl_swd *) malloc(sizeof(*swd));
  900. if (!swd)
  901. return UCL_E_OUT_OF_MEMORY;
  902. swd->f = F;
  903. swd->n = N;
  904. if (in_len >= 256 && in_len < swd->n)
  905. swd->n = in_len;
  906. if (swd->f < 8 || swd->n < 256)
  907. return UCL_E_INVALID_ARGUMENT;
  908. r = init_match(c,swd,NULL,0, SC_FLAGS);
  909. if (r != UCL_E_OK)
  910. {
  911. free(swd);
  912. return r;
  913. }
  914. if (SC_MAX_CHAIN > 0)
  915. swd->max_chain = SC_MAX_CHAIN;
  916. if (SC_NICE_LENGTH > 0)
  917. swd->nice_length = SC_NICE_LENGTH;
  918. if (c->conf.max_match < swd->nice_length)
  919. swd->nice_length = c->conf.max_match;
  920. c->last_m_off = 1;
  921. r = find_match(c,swd,0,0);
  922. if (r != UCL_E_OK)
  923. return r;
  924. while (c->look > 0)
  925. {
  926. unsigned int ahead;
  927. unsigned int max_ahead;
  928. int l1, l2;
  929. c->codesize = c->bb_op - out;
  930. m_len = c->m_len;
  931. m_off = c->m_off;
  932. assert(c->bp == c->ip - c->look);
  933. assert(c->bp >= in);
  934. if (lit == 0)
  935. ii = c->bp;
  936. assert(ii + lit == c->bp);
  937. assert(swd->b_char == *(c->bp));
  938. if (m_len < 2 || (m_len == 2 && (m_off > M2_MAX_OFFSET))
  939. || m_off > c->conf.max_offset)
  940. {
  941. /* a literal */
  942. lit++;
  943. swd->max_chain = SC_MAX_CHAIN;
  944. r = find_match(c,swd,1,0);
  945. assert(r == 0);
  946. continue;
  947. }
  948. /* a match */
  949. assert_match(swd,m_len,m_off);
  950. /* shall we try a lazy match ? */
  951. ahead = 0;
  952. if (SC_TRY_LAZY <= 0 || m_len >= SC_MAX_LAZY || m_off ==
  953. c->last_m_off)
  954. {
  955. /* no */
  956. l1 = 0;
  957. max_ahead = 0;
  958. }
  959. else
  960. {
  961. /* yes, try a lazy match */
  962. l1 = len_of_coded_match(c,m_len,m_off);
  963. assert(l1 > 0);
  964. max_ahead = SC_TRY_LAZY;
  965. if ((m_len - 1) < max_ahead) {
  966. max_ahead = m_len -1;
  967. }
  968. }
  969. while (ahead < max_ahead && c->look > m_len)
  970. {
  971. if (m_len >= SC_GOOD_LENGTH)
  972. swd->max_chain = SC_MAX_CHAIN >> 2;
  973. else
  974. swd->max_chain = SC_MAX_CHAIN;
  975. r = find_match(c,swd,1,0);
  976. ahead++;
  977. assert(r == 0);
  978. assert(c->look > 0);
  979. assert(ii + lit + ahead == c->bp);
  980. if (c->m_len < 2)
  981. continue;
  982. l2 = len_of_coded_match(c,c->m_len,c->m_off);
  983. if (l2 < 0)
  984. continue;
  985. if (l1 + (int)(ahead + c->m_len - m_len) * 5 > l2 +
  986. (int)(ahead) * 9)
  987. {
  988. c->lazy++;
  989. assert_match(swd,c->m_len,c->m_off);
  990. lit += ahead;
  991. assert(ii + lit == c->bp);
  992. goto lazy_match_done;
  993. }
  994. }
  995. assert(ii + lit + ahead == c->bp);
  996. /* 1 - code run */
  997. code_run(c,ii,lit);
  998. lit = 0;
  999. /* 2 - code match */
  1000. code_match(c,m_len,m_off);
  1001. swd->max_chain = SC_MAX_CHAIN;
  1002. r = find_match(c,swd,m_len,1+ahead);
  1003. assert(r == 0);
  1004. lazy_match_done: ;
  1005. }
  1006. /* store final run */
  1007. code_run(c,ii,lit);
  1008. /* EOF */
  1009. bbPutBit(c, 0);
  1010. code_prefix_ss11(c, 0x1000000U);
  1011. bbPutByte(c, 0xff);
  1012. bbFlushBits(c, 0);
  1013. assert(c->textsize == in_len);
  1014. c->codesize = c->bb_op - out;
  1015. *out_len = c->bb_op - out;
  1016. #if 0
  1017. printf("%7ld %7ld -> %7ld %7ld %7ld %ld (max: %d %d %d)\n",
  1018. (long) c->textsize, (long) in_len, (long) c->codesize,
  1019. c->match_bytes, c->lit_bytes, c->lazy,
  1020. c->result[1], c->result[3], c->result[5]);
  1021. #endif
  1022. assert(c->lit_bytes + c->match_bytes == in_len);
  1023. swd_exit(swd);
  1024. free(swd);
  1025. return UCL_E_OK;
  1026. }
  1027. void Encode(void) /* compression */
  1028. {
  1029. uint8_t *in, *out;
  1030. unsigned long in_len, out_len;
  1031. uint32_t tw;
  1032. int r;
  1033. fseek(infile, 0, SEEK_END);
  1034. in_len = ftell(infile);
  1035. #ifdef VERBOSE
  1036. if ((signed long)in_len < 0)
  1037. Fprintf((stderr, "Errno: %d", errno));
  1038. #endif
  1039. #if UCLPACK_COMPAT
  1040. {
  1041. uint8_t byte;
  1042. if (fwrite(magic, sizeof(magic), 1, outfile) != 1)
  1043. Error("Can't write.");
  1044. tw = htonl(0); /* flags */
  1045. if (fwrite(&tw, sizeof(tw), 1, outfile) != 1)
  1046. Error("Can't write.");
  1047. byte = 0x2b; /* method */
  1048. if (fwrite(&byte, sizeof(byte), 1, outfile) != 1)
  1049. Error("Can't write.");
  1050. byte = 10; /* level */
  1051. if (fwrite(&byte, sizeof(byte), 1, outfile) != 1)
  1052. Error("Can't write.");
  1053. tw = htonl(256*1024); /* block_size */
  1054. if (fwrite(&tw, sizeof(tw), 1, outfile) != 1)
  1055. Error("Can't write.");
  1056. tw = htonl(in_len);
  1057. if (fwrite(&tw, sizeof(tw), 1, outfile) != 1)
  1058. Error("Can't write."); /* output size of text */
  1059. }
  1060. #else
  1061. tw = host_to_i86ul(in_len);
  1062. if (fwrite(&tw, sizeof(tw), 1, outfile) != 1)
  1063. Error("Can't write."); /* output size of text */
  1064. #endif
  1065. if (in_len == 0)
  1066. return;
  1067. rewind(infile);
  1068. in = malloc(in_len);
  1069. out_len = in_len + (in_len/8) + 256;
  1070. out = malloc(out_len);
  1071. if (!in || !out) {
  1072. Error("Can't malloc");
  1073. }
  1074. if (fread(in, in_len, 1, infile) != 1) {
  1075. Error("Can't read");
  1076. }
  1077. r = ucl_nrv2b_99_compress(in, in_len, out, &out_len, 0 );
  1078. if (r != UCL_E_OK)
  1079. Error("Compression failure\n");
  1080. #if UCLPACK_COMPAT
  1081. tw = htonl(out_len);
  1082. if (fwrite(&tw, sizeof(tw), 1, outfile) != 1)
  1083. Error("Can't write."); /* file size of text */
  1084. #endif
  1085. if (fwrite(out, out_len, 1, outfile) != 1) {
  1086. Error("Write error\n");
  1087. }
  1088. #if UCLPACK_COMPAT
  1089. tw = htonl(0); /* EOF marker */
  1090. if (fwrite(&tw, sizeof(tw), 1, outfile) != 1)
  1091. Error("Can't write.");
  1092. #endif
  1093. #ifdef LONG_REPORT
  1094. Fprintf((stdout, "input size %ld bytes\n", in_len));
  1095. Fprintf((stdout, "output size %ld bytes\n", out_len));
  1096. Fprintf((stdout, "input/output %.3f\n", (double)in_len / out_len));
  1097. #else
  1098. Fprintf((stdout, "input/output = %ld/%ld = %.3f\n", in_len, out_len,
  1099. (double)in_len / out_len));
  1100. #endif
  1101. }
  1102. #endif
  1103. #ifdef DECODE
  1104. #define GETBIT_8(bb, src, ilen) \
  1105. (((bb = bb & 0x7f ? bb*2 : ((unsigned)src[ilen++]*2+1)) >> 8) & 1)
  1106. #define GETBIT_LE16(bb, src, ilen) \
  1107. (bb*=2,bb&0xffff ? (bb>>16)&1 : (ilen+=2,((bb=(src[ilen-2]+src[ilen-1]*256u)*2+1)>>16)&1))
  1108. #define GETBIT_LE32(bb, src, ilen) \
  1109. (bc > 0 ? ((bb>>--bc)&1) : (bc=31,\
  1110. bb=*(const uint32_t *)((src)+ilen),ilen+=4,(bb>>31)&1))
  1111. #define GETBIT_LE64(bb, src, ilen) \
  1112. (bc > 0 ? ((bb>>--bc)&1) : (bc=63, \
  1113. bb=*(const uint64_t *)((src)+ilen),ilen+=8,(bb>>63)&1))
  1114. #if ENDIAN == 0 && BITSIZE == 8
  1115. #define GETBIT(bb, src, ilen) GETBIT_8(bb, src, ilen)
  1116. #endif
  1117. #if ENDIAN == 0 && BITSIZE == 16
  1118. #define GETBIT(bb, src, ilen) GETBIT_LE16(bb, src, ilen)
  1119. #endif
  1120. #if ENDIAN == 0 && BITSIZE == 32
  1121. #define GETBIT(bb, src, ilen) GETBIT_LE32(bb, src, ilen)
  1122. #endif
  1123. #if ENDIAN == 0 && BITSIZE == 64
  1124. #define GETBIT(bb, src, ilen) GETBIT_LE64(bb, src, ilen)
  1125. #endif
  1126. #ifndef GETBIT
  1127. #error "Bad Combination of ENDIAN and BITSIZE values specified"
  1128. #endif
  1129. #undef SAFE
  1130. #ifdef SAFE
  1131. #define FAIL(x,r) if (x) { Error(r); }
  1132. #else
  1133. #define FAIL(x,r)
  1134. #endif
  1135. void Decode(void) /* recover */
  1136. {
  1137. uint32_t tw;
  1138. uint8_t *src, *dst;
  1139. unsigned long max_src_len, src_len, dst_len;
  1140. unsigned long ilen = 0, olen = 0, last_m_off = 1;
  1141. #if BITSIZE <= 32
  1142. uint32_t bb = 0;
  1143. #elif BITSIZE == 64
  1144. uint64_t bb = 0;
  1145. #endif
  1146. unsigned bc = 0;
  1147. #if UCLPACK_COMPAT
  1148. if (fseek(infile, sizeof(magic) + sizeof(tw) + 1 + 1 + sizeof(tw),
  1149. SEEK_SET) != 0)
  1150. Error("Seek Error");
  1151. if (fread(&tw, sizeof(tw), 1, infile) < 1)
  1152. Error("Can't read"); /* read size of text */
  1153. dst_len = ntohl(tw);
  1154. if (fread(&tw, sizeof(tw), 1, infile) < 1)
  1155. Error("Can't read"); /* read size of file */
  1156. max_src_len = ntohl(tw);
  1157. #else
  1158. if (fread(&tw, sizeof(tw), 1, infile) < 1)
  1159. Error("Can't read"); /* read size of text */
  1160. dst_len = i86ul_to_host(tw);
  1161. max_src_len = dst_len + (dst_len/8) + 256;
  1162. #endif
  1163. if (dst_len == 0)
  1164. return;
  1165. dst = malloc(dst_len);
  1166. if (!dst)
  1167. Error("Can't malloc");
  1168. src = malloc(max_src_len);
  1169. if (!src)
  1170. Error("Can't malloc");
  1171. src_len = fread(src, 1, max_src_len, infile);
  1172. if (src_len <= 0)
  1173. Error("Can't read");
  1174. for(;;) {
  1175. unsigned int m_off, m_len;
  1176. while(GETBIT(bb, src, ilen)) {
  1177. FAIL(ilen >= src_len, "input overrun");
  1178. FAIL(olen >= dst_len, "output overrun");
  1179. dst[olen++] = src[ilen++];
  1180. }
  1181. m_off = 1;
  1182. do {
  1183. m_off = m_off*2 + GETBIT(bb, src, ilen);
  1184. FAIL(ilen >= src_len, "input overrun");
  1185. FAIL(m_off > 0xffffffU +3, "lookbehind overrun");
  1186. } while (!GETBIT(bb, src, ilen));
  1187. if (m_off == 2)
  1188. {
  1189. m_off = last_m_off;
  1190. }
  1191. else
  1192. {
  1193. FAIL(ilen >= src_len, "input overrun");
  1194. m_off = (m_off - 3)*256 + src[ilen++];
  1195. if (m_off == 0xffffffffU)
  1196. break;
  1197. last_m_off = ++m_off;
  1198. }
  1199. m_len = GETBIT(bb, src, ilen);
  1200. m_len = m_len*2 + GETBIT(bb, src, ilen);
  1201. if (m_len == 0)
  1202. {
  1203. m_len++;
  1204. do {
  1205. m_len = m_len*2 + GETBIT(bb, src, ilen);
  1206. FAIL(ilen >= src_len, "input overrun");
  1207. FAIL(m_len >= dst_len, "output overrun");
  1208. } while(!GETBIT(bb, src, ilen));
  1209. m_len += 2;
  1210. }
  1211. m_len += (m_off > 0xd00);
  1212. FAIL(olen + m_len > dst_len, "output overrun");
  1213. FAIL(m_off > olen, "lookbeind overrun");
  1214. {
  1215. const uint8_t *m_pos;
  1216. m_pos = dst + olen - m_off;
  1217. dst[olen++] = *m_pos++;
  1218. do {
  1219. dst[olen++] = *m_pos++;
  1220. } while(--m_len > 0);
  1221. }
  1222. }
  1223. FAIL(ilen < src_len, "input not consumed");
  1224. FAIL(ilen > src_len, "input overrun");
  1225. assert(ilen == src_len);
  1226. Fprintf((stderr, "%12ld\n", olen));
  1227. if (dst_len != olen) {
  1228. fprintf(stderr, "length != expected length\n");
  1229. }
  1230. if (fwrite(dst, olen, 1, outfile) != 1)
  1231. Error("Write error\n");
  1232. free(src);
  1233. free(dst);
  1234. }
  1235. #endif
  1236. #ifdef MAIN
  1237. int main(int argc, char *argv[])
  1238. {
  1239. char *s;
  1240. FILE *f;
  1241. int c;
  1242. if (argc == 2) {
  1243. outfile = stdout;
  1244. if ((f = tmpfile()) == NULL) {
  1245. perror("tmpfile");
  1246. return EXIT_FAILURE;
  1247. }
  1248. while ((c = getchar()) != EOF)
  1249. fputc(c, f);
  1250. rewind(infile = f);
  1251. }
  1252. else if (argc != 4) {
  1253. Fprintf((stderr, "'nrv2b e file1 file2' encodes file1 into file2.\n"
  1254. "'nrv2b d file2 file1' decodes file2 into file1.\n"));
  1255. return EXIT_FAILURE;
  1256. }
  1257. if (argc == 4) {
  1258. if ((s = argv[1], s[1] || strpbrk(s, "DEde") == NULL)
  1259. || (s = argv[2], (infile = fopen(s, "rb")) == NULL)
  1260. || (s = argv[3], (outfile = fopen(s, "wb")) == NULL)) {
  1261. Fprintf((stderr, "??? %s\n", s));
  1262. return EXIT_FAILURE;
  1263. }
  1264. }
  1265. if (toupper(*argv[1]) == 'E')
  1266. Encode();
  1267. else
  1268. Decode();
  1269. fclose(infile);
  1270. fclose(outfile);
  1271. return EXIT_SUCCESS;
  1272. }
  1273. #endif