home *** CD-ROM | disk | FTP | other *** search
/ Source Code 1994 March / Source_Code_CD-ROM_Walnut_Creek_March_1994.iso / compsrcs / misc / volume35 / freeze / part02 < prev    next >
Encoding:
Text File  |  1993-02-21  |  54.4 KB  |  2,303 lines
  1. Newsgroups: comp.sources.misc
  2. From: leo@ipmce.su (Leonid A. Broukhis)
  3. Subject: v35i078:  freeze - Freeze/melt compression program, v2.5, Part02/03
  4. Message-ID: <1993Feb22.035709.14895@sparky.imd.sterling.com>
  5. X-Md4-Signature: 15a117efabcbcdae125e925d2da59c56
  6. Date: Mon, 22 Feb 1993 03:57:09 GMT
  7. Approved: kent@sparky.imd.sterling.com
  8.  
  9. Submitted-by: leo@ipmce.su (Leonid A. Broukhis)
  10. Posting-number: Volume 35, Issue 78
  11. Archive-name: freeze/part02
  12. Environment: ISC, Xenix, SunOS, MS-DOS
  13. Supersedes: freeze: Volume 25, Issue 12-13
  14.  
  15. #! /bin/sh
  16. # This is a shell archive.  Remove anything before this line, then feed it
  17. # into a shell via "sh file" or similar.  To overwrite existing files,
  18. # type "sh file -c".
  19. # Contents:  Makefile.in compat.h config.tur decode.c encode.c freeze.1
  20. #   freeze.h huf.c huf.h lz.h statist.1 statist.c
  21. # Wrapped by kent@sparky on Sat Feb 20 22:49:56 1993
  22. PATH=/bin:/usr/bin:/usr/ucb:/usr/local/bin:/usr/lbin ; export PATH
  23. echo If this archive is complete, you will see the following message:
  24. echo '          "shar: End of archive 2 (of 3)."'
  25. if test -f 'Makefile.in' -a "${1}" != "-c" ; then 
  26.   echo shar: Will not clobber existing file \"'Makefile.in'\"
  27. else
  28.   echo shar: Extracting \"'Makefile.in'\" \(3940 characters\)
  29.   sed "s/^X//" >'Makefile.in' <<'END_OF_FILE'
  30. XSHELL         = /bin/sh
  31. Xsrcdir        = @srcdir@
  32. XVPATH         = $(srcdir)
  33. X
  34. XCC            = @CC@
  35. XCFLAGS        = -I.     # -O2   # for gcc 2.2.2
  36. X
  37. XINSTALL       = @INSTALL@
  38. XINSTALL_PROGRAM = @INSTALL_PROGRAM@
  39. XINSTALL_DATA  = @INSTALL_DATA@
  40. X
  41. XLIBS          = @LIBS@
  42. XOBJ           = o
  43. XEXE           =
  44. X
  45. X.PHONY:         default
  46. X
  47. Xdefault:        prog
  48. X
  49. X# Added the prefix macro, so that it was easier to change installation place.
  50. Xprefix        = /usr/local
  51. XDEST          = $(prefix)/bin
  52. XMANDEST       = $(prefix)/man/man1
  53. XSEC           = 1
  54. X
  55. XHDRS          = bitio.h\
  56. X        compat.h\
  57. X        freeze.h\
  58. X        huf.h\
  59. X        lz.h\
  60. X        patchlevel.h
  61. X
  62. X# define DEFFILE as a filename with freeze's default Huffman values
  63. X# e.g. -DDEFFILE=\"/etc/default/freeze\"
  64. X# !!!! NOTE !!!! default is now $(prefix)/lib/freeze.cnf !!!!!
  65. X
  66. XOPTIONS       = -DDEFFILE=\"$(prefix)/lib/freeze.cnf\"
  67. X
  68. XLINTFLAGS     = -DDEBUG -DGATHER_STAT -x -h
  69. X
  70. XMAKEFILE      = makefile
  71. X
  72. XOBJS          = bitio.$(OBJ)\
  73. X        debug.$(OBJ)\
  74. X        decode.$(OBJ)\
  75. X        default.$(OBJ)\
  76. X        encode.$(OBJ)\
  77. X        freeze.$(OBJ)\
  78. X        huf.$(OBJ)\
  79. X        lz.$(OBJ)
  80. X
  81. XCATMAN        = freeze.man statist.man
  82. X
  83. XMAN           = freeze.1 statist.1
  84. X
  85. XSRCS          = bitio.c\
  86. X        debug.c\
  87. X        decode.c\
  88. X        default.c\
  89. X        encode.c\
  90. X        freeze.c\
  91. X        huf.c\
  92. X        lz.c
  93. X
  94. X.SUFFIXES:       .man .1 .$(suffix)
  95. X
  96. X.1.man:
  97. X        nroff -man < $< > $@
  98. X
  99. X.c.$(OBJ):
  100. X        $(CC) -c $(CFLAGS) $(OPTIONS) $<
  101. X
  102. Xprog:           freeze$(EXE) statist$(EXE) showhuf$(EXE)
  103. X
  104. Xman:            $(CATMAN)
  105. X
  106. Xlint:           $(SRCS)
  107. X        lint $(LINTFLAGS) $(SRCS) > lint.out
  108. X
  109. Xfreeze$(EXE):   $(OBJS)
  110. X        $(CC) $(LDFLAGS) -o $@ $(OBJS) $(LIBS)
  111. X        -strip $@
  112. X
  113. Xstatist$(EXE):  statist.$(OBJ) lz.$(OBJ)
  114. X        $(CC) $(LDFLAGS) -o $@ statist.$(OBJ) lz.$(OBJ) $(LIBS)
  115. X        -strip $@
  116. X
  117. Xshowhuf$(EXE):  showhuf.$(OBJ)
  118. X        $(CC) $(LDFLAGS) -o $@ showhuf.$(OBJ) $(LIBS)
  119. X        -strip $@
  120. X
  121. Xclobber:        clean
  122. X        rm -f freeze$(EXE) statist$(EXE) showhuf$(EXE) *.man \#* *~ config.h Makefile
  123. X
  124. Xclean:;         rm -f *.$(OBJ) *.b .,* core *.out
  125. X
  126. Xinstall:        $(DEST)/freeze $(DEST)/statist $(MANDEST)/freeze.$(SEC) $(MANDEST)/statist.$(SEC)
  127. X
  128. Xpatch:;         rm -f patch.out
  129. X        makepatch -manifest MANIFEST -patchlevel patchlev.h ../freeze.distr . > patch.out
  130. X
  131. X$(DEST)/freeze: freeze
  132. X        $(INSTALL_PROGRAM) freeze $@
  133. X        -ln -f $@ $(DEST)/melt
  134. X        -ln -f $@ $(DEST)/unfreeze
  135. X        -ln -f $@ $(DEST)/fcat
  136. X
  137. X$(DEST)/statist: statist
  138. X        $(INSTALL_PROGRAM) statist $@
  139. X
  140. X$(MANDEST)/freeze.$(SEC): freeze.1
  141. X        $(INSTALL_DATA) $(srcdir)/freeze.1 $@
  142. X        -ln -f $@ $(MANDEST)/melt.$(SEC)
  143. X        -ln -f $@ $(MANDEST)/unfreeze.$(SEC)
  144. X        -ln -f $@ $(MANDEST)/fcat.$(SEC)
  145. X# This is much better for places which keep preformated manpages.
  146. X#        echo ".so man1/freeze.$(SEC)" > $(MANDEST)/melt.$(SEC)
  147. X#        echo ".so man1/freeze.$(SEC)" > $(MANDEST)/unfreeze.$(SEC)
  148. X#        echo ".so man1/freeze.$(SEC)" > $(MANDEST)/fcat.$(SEC)
  149. X
  150. X
  151. X$(MANDEST)/statist.$(SEC): statist.1
  152. X        $(INSTALL_DATA) $(srcdir)/statist.1 $@
  153. X
  154. X
  155. XMakefile: $(srcdir)/Makefile.in config.status
  156. X    ./config.status
  157. X
  158. Xconfig.h: $(srcdir)/config.h.in config.status
  159. X    ./config.status
  160. X
  161. Xx286:
  162. X        $(MAKE) prog "CC=cc -LARGE" CFLAGS="-Ox -Ml2" LDFLAGS="-Ml2"
  163. X
  164. Xx286install:
  165. X        $(MAKE) install MANDEST=/usr/man/man.C SEC=C
  166. X
  167. Xmsc:
  168. X        if not exist config.h copy config.msc config.h
  169. X        $(MAKE) prog EXE=.exe OBJ=obj CC="cl" CFLAGS="-Mc -Ox" LDFLAGS="-Mc" LIBS=""
  170. X
  171. Xturbo:
  172. X        if not exist config.h copy config.tur config.h
  173. X        $(MAKE) prog EXE=.exe OBJ=obj CC="tcc" CFLAGS="-Ox -Z -G -mc -Ff" LDFLAGS="-mc -Ff" LIBS=""
  174. X
  175. Xborland:
  176. X        if not exist config.h copy config.tur config.h
  177. X        $(MAKE) prog EXE=.exe OBJ=obj CC="bcc" CFLAGS="-Ox -Z -G -mc -Ff" LDFLAGS="-mc -Ff" LIBS=""
  178. X
  179. X###
  180. Xbitio.$(OBJ):
  181. Xdebug.$(OBJ): freeze.h compat.h huf.h bitio.h
  182. Xdecode.$(OBJ): freeze.h compat.h huf.h bitio.h
  183. Xdefault.$(OBJ): freeze.h compat.h
  184. Xencode.$(OBJ): freeze.h compat.h lz.h huf.h bitio.h
  185. Xfreeze.$(OBJ): freeze.h compat.h patchlev.h bitio.h
  186. Xhuf.$(OBJ): freeze.h compat.h huf.h bitio.h
  187. Xlz.$(OBJ): freeze.h compat.h lz.h
  188. Xstatist.$(OBJ): freeze.h lz.h
  189. Xshowhuf.$(OBJ): freeze.h huf.h
  190. END_OF_FILE
  191.   if test 3940 -ne `wc -c <'Makefile.in'`; then
  192.     echo shar: \"'Makefile.in'\" unpacked with wrong size!
  193.   fi
  194.   # end of 'Makefile.in'
  195. fi
  196. if test -f 'compat.h' -a "${1}" != "-c" ; then 
  197.   echo shar: Will not clobber existing file \"'compat.h'\"
  198. else
  199.   echo shar: Extracting \"'compat.h'\" \(183 characters\)
  200.   sed "s/^X//" >'compat.h' <<'END_OF_FILE'
  201. Xextern uc_t    Table1[];
  202. X
  203. X#define F1              60
  204. X#define N1              4096
  205. X#define N_CHAR1         (256 - THRESHOLD + F1 + 1)
  206. X
  207. Xextern short DecodePOld();
  208. X
  209. Xextern void melt1();
  210. END_OF_FILE
  211.   if test 183 -ne `wc -c <'compat.h'`; then
  212.     echo shar: \"'compat.h'\" unpacked with wrong size!
  213.   fi
  214.   # end of 'compat.h'
  215. fi
  216. if test -f 'config.tur' -a "${1}" != "-c" ; then 
  217.   echo shar: Will not clobber existing file \"'config.tur'\"
  218. else
  219.   echo shar: Extracting \"'config.tur'\" \(2744 characters\)
  220.   sed "s/^X//" >'config.tur' <<'END_OF_FILE'
  221. X/* This is a configuration file prototype, copy it to config.h and      */
  222. X/* "#define" appropriate macros if you have problems with "configure".  */
  223. X
  224. X/* define as "int" or "void" */
  225. X#define RETSIGTYPE void
  226. X
  227. X/* define if your computer/system allows unaligned word access          */
  228. X#define ALLOW_MISALIGN
  229. X
  230. X/* define if sizeof(int) == 2                                           */
  231. X#define INT_16_BITS
  232. X
  233. X/* define if your computer cannot handle data items of more than 64K    */
  234. X#define SEGMENTED
  235. X
  236. X/* define if filenames can be of more than 14 chars                     */
  237. X#undef HAVE_LONG_FILE_NAMES
  238. X
  239. X/* define no more than one of, according to your standard #include's    */
  240. X/* if you have <dirent.h>                                               */
  241. X#undef DIRENT
  242. X/* if you have <sys/ndir.h>                                             */
  243. X#undef SYSNDIR
  244. X/* if you have <sys/dir.h>                                              */
  245. X#undef SYSDIR
  246. X
  247. X/* define if you have <sys/stdtypes.h>                                  */
  248. X#undef HAVE_SYS_STDTYPES_H
  249. X
  250. X/* define if you have "rindex" and "setlinebuf" correspondingly         */
  251. X#undef HAVE_RINDEX
  252. X#undef HAVE_SETLINEBUF
  253. X
  254. X/* define no more than one of, according to your standard #include's    */
  255. X/* if you have <utime.h>                                                */
  256. X#undef UTIME
  257. X/* if you have <sys/utime.h>                                            */
  258. X#undef SYSUTIME
  259. X/* if you have "struct timeval" in <sys/time.h>                         */
  260. X#undef SYSTIME
  261. X
  262. X/* BORLAND C has no off_t definition in <sys/types.h>                   */
  263. X#define off_t long
  264. X
  265. X/* define if you want to have freeze compatible with vers. 1.0          */
  266. X#undef COMPAT
  267. X
  268. X/* define if your system has multibyte NEWLINE (as in MS-DOS) and       */
  269. X/* you want to do text conversion by default                            */
  270. X#undef TEXT_DEFAULT
  271. X
  272. X/* define if you want to build freeze in small model  (64K data)        */
  273. X/* (segmented architectures only)                                       */
  274. X#undef TINY
  275. X
  276. X/* override default value because BCC cannot handle 65536 bytes arrays  */
  277. X#define BITS 14
  278. X
  279. X/* define if you want to decrease the amount of memory but without      */
  280. X/* 64K restriction (no sense for 16-bit machines)                       */
  281. X#undef SMALL
  282. X
  283. X/* define to increase the compression speed by about 10% at the cost    */
  284. X/* of some tenths of % compression rate                                 */
  285. X#undef FASTHASH
  286. X
  287. X/* default Huffman values, define if you don't like the default        */
  288. X/* 0,0,1,2,6,19,34,0. These below are reasonably good also.            */
  289. X/* #define HUFVALUES 0,1,1,1,4,10,27,18                                */
  290. END_OF_FILE
  291.   if test 2744 -ne `wc -c <'config.tur'`; then
  292.     echo shar: \"'config.tur'\" unpacked with wrong size!
  293.   fi
  294.   # end of 'config.tur'
  295. fi
  296. if test -f 'decode.c' -a "${1}" != "-c" ; then 
  297.   echo shar: Will not clobber existing file \"'decode.c'\"
  298. else
  299.   echo shar: Extracting \"'decode.c'\" \(2703 characters\)
  300.   sed "s/^X//" >'decode.c' <<'END_OF_FILE'
  301. X#include "freeze.h"
  302. X#include "huf.h"
  303. X#include "bitio.h"
  304. X
  305. X/*
  306. X * Melt stdin to stdout.
  307. X */
  308. X
  309. Xvoid melt2 ()
  310. X{
  311. X    register short    i, j, k, r, c;
  312. X
  313. X/* Huffman-dependent part */
  314. X    if(read_header() == EOF)
  315. X        return;
  316. X    StartHuff(N_CHAR2);
  317. X    init(Table2);
  318. X/* end of Huffman-dependent part */
  319. X
  320. X    InitIO();
  321. X    for (i = WINSIZE - LOOKAHEAD; i < WINSIZE; i++)
  322. X        text_buf[i] = ' ';
  323. X    r = 0;
  324. X    for (in_count = 0;; ) {
  325. X        c = DecodeChar();
  326. X
  327. X        if (c == ENDOF)
  328. X            break;
  329. X        if (c < 256) {
  330. X#ifdef DEBUG
  331. X            if (debug)
  332. X                fprintf(stderr, "'%s'\n", pr_char((uc_t)c));
  333. X#endif /* DEBUG */
  334. X            text_buf[r++] = c;
  335. X            in_count++;
  336. X            r &= WINMASK;
  337. X#ifdef DEBUG
  338. X            if (!debug)
  339. X#endif
  340. X            if (r == 0) {
  341. X                fwrite(text_buf, WINSIZE, 1, stdout);
  342. X                if (ferror(stdout))
  343. X                    writeerr();
  344. X            }
  345. X        } else {
  346. X            i = (r - DecodePosition() - 1) & WINMASK;
  347. X            j = c - 256 + THRESHOLD;
  348. X#ifdef DEBUG
  349. X            if (debug)
  350. X                fputc('"', stderr);
  351. X#endif
  352. X            for (k = 0; k < j; k++) {
  353. X                c = text_buf[(i + k) & WINMASK];
  354. X#ifdef DEBUG
  355. X                if (debug)
  356. X                    fprintf(stderr, "%s", pr_char((uc_t)c));
  357. X#endif
  358. X                text_buf[r++] = c;
  359. X                in_count++;
  360. X                r &= WINMASK;
  361. X#ifdef DEBUG
  362. X                if (!debug)
  363. X#endif
  364. X                if (r == 0) {
  365. X                    fwrite(text_buf, WINSIZE, 1, stdout);
  366. X                    if (ferror(stdout))
  367. X                        writeerr();
  368. X                }
  369. X            }
  370. X#ifdef DEBUG
  371. X            if (debug)
  372. X                fprintf(stderr, "\"\n");
  373. X#endif
  374. X        }
  375. X        INDICATOR
  376. X    }
  377. X    if (r) {
  378. X        fwrite(text_buf, r, 1, stdout);
  379. X        if (ferror(stdout))
  380. X            writeerr();
  381. X    }
  382. X    if (quiet < 0 && file_length != 0)
  383. X        fprintf(stderr, "100%%\b\b\b\b");
  384. X}
  385. X
  386. X#ifdef COMPAT
  387. Xvoid melt1 ()
  388. X{
  389. X    register short    i, j, k, r, c;
  390. X
  391. X    StartHuff(N_CHAR1);
  392. X    init(Table1);
  393. X    InitIO();
  394. X    for (i = N1 - F1; i < N1; i++)
  395. X        text_buf[i] = ' ';
  396. X    r = 0;
  397. X    for (in_count = 0;; ) {
  398. X        c =  DecodeChar();
  399. X
  400. X        if (c == ENDOF)
  401. X            break;
  402. X
  403. X        if (c < 256) {
  404. X#ifdef DEBUG
  405. X            if (debug)
  406. X                fprintf(stderr, "'%s'\n", pr_char((uc_t)c));
  407. X#endif /* DEBUG */
  408. X            text_buf[r++] = c;
  409. X            in_count++;
  410. X            r &= (N1 - 1);
  411. X#ifdef DEBUG
  412. X            if (!debug)
  413. X#endif
  414. X            if (r == 0) {
  415. X                fwrite(text_buf, N1, 1, stdout);
  416. X                if (ferror(stdout))
  417. X                    writeerr();
  418. X            }
  419. X        } else {
  420. X            i = (r - DecodePOld() - 1) & (N1 - 1);
  421. X            j = c - 256 + THRESHOLD;
  422. X#ifdef DEBUG
  423. X            if (debug)
  424. X                fputc('"', stderr);
  425. X#endif
  426. X            for (k = 0; k < j; k++) {
  427. X                c = text_buf[(i + k) & (N1 - 1)];
  428. X#ifdef DEBUG
  429. X                if (debug)
  430. X                    fprintf(stderr, "%s", pr_char((uc_t)c));
  431. X#endif
  432. X                text_buf[r++] = c;
  433. X                in_count++;
  434. X                r &= (N1 - 1);
  435. X#ifdef DEBUG
  436. X                if (!debug)
  437. X#endif
  438. X                if (r == 0) {
  439. X                    fwrite(text_buf, N1, 1, stdout);
  440. X                    if (ferror(stdout))
  441. X                        writeerr();
  442. X                }
  443. X            }
  444. X#ifdef DEBUG
  445. X            if (debug)
  446. X                fprintf(stderr, "\"\n");
  447. X#endif
  448. X        }
  449. X        INDICATOR
  450. X    }
  451. X    if (r) {
  452. X        fwrite(text_buf, r, 1, stdout);
  453. X        if (ferror(stdout))
  454. X            writeerr();
  455. X    }
  456. X}
  457. X#endif
  458. END_OF_FILE
  459.   if test 2703 -ne `wc -c <'decode.c'`; then
  460.     echo shar: \"'decode.c'\" unpacked with wrong size!
  461.   fi
  462.   # end of 'decode.c'
  463. fi
  464. if test -f 'encode.c' -a "${1}" != "-c" ; then 
  465.   echo shar: Will not clobber existing file \"'encode.c'\"
  466. else
  467.   echo shar: Extracting \"'encode.c'\" \(5594 characters\)
  468.   sed "s/^X//" >'encode.c' <<'END_OF_FILE'
  469. X
  470. X#include "freeze.h"
  471. X#include "lz.h"
  472. X#include "huf.h"
  473. X#include "bitio.h"
  474. X
  475. X/* for future versions ?... */
  476. X
  477. X#define LENGTH_OFFSET   256
  478. X#define EncodeLiteral(l)        EncodeChar((int)l)
  479. X#define EncodeLength(l)         EncodeChar((int)l + LENGTH_OFFSET)
  480. X
  481. X/*
  482. X * Freezes stdin to stdout
  483. X */
  484. X
  485. Xvoid 
  486. Xfreeze()
  487. X{
  488. X  register int i, len, s, c;
  489. X  register hash_t r;
  490. X  int     match_length;
  491. X
  492. X  putchar(MAGIC1);
  493. X  putchar(MAGIC2_2);
  494. X
  495. X/* Huffman-dependent part */
  496. X  write_header();
  497. X  StartHuff(N_CHAR2);
  498. X  init(Table2);
  499. X/* end of Huffman-dependent part */
  500. X
  501. X  InitTree();            /* LZ dependent */
  502. X  InitIO();
  503. X
  504. X  s = r = MAXDIST + 1;              /* to make zero links "too old" */
  505. X
  506. X  for (len = 0; len < LOOKAHEAD && (c = getchar()) != EOF; len++) {
  507. X      text_buf[s] = c;
  508. X      if (s < LOOKAHEAD - 1)
  509. X    text_buf[s + WINSIZE] = c;
  510. X      s = (s + 1) & WINMASK;
  511. X  }
  512. X
  513. X /* check for magic header */
  514. X  if (!topipe && !force && text_buf[r] == MAGIC1 &&
  515. X    text_buf[r + 1] >= MAGIC2_1) {
  516. X    if (quiet != 1)
  517. X      fprintf(stderr, " already frozen ");
  518. X    exit_stat = 2;
  519. X    return;
  520. X  }
  521. X  in_count = len;
  522. X
  523. X  /* Insert 256 "initial" spaces and the very first char into hash table */
  524. X  for (i = r - LOOKAHEAD; i < r; i++)
  525. X    text_buf[i] = ' ';
  526. X  for (i = r - LOOKAHEAD; i <= r; i++) {
  527. X    register uc_t  *key = &text_buf[i];
  528. X    register unsigned p = hashof(key);
  529. X    next[i] = hashtab[p];
  530. X    hashtab[p] = i;
  531. X  }
  532. X
  533. X /* here the main loop begins */
  534. X
  535. X  while (len != 0) {
  536. X    match_length = LOOKAHEAD + get_next_match(THRESHOLD - LOOKAHEAD, r);
  537. X    if (match_length > len)
  538. X      match_length = len;
  539. X
  540. X    if (match_length <= THRESHOLD) {
  541. X      match_length = 1;
  542. X      EncodeLiteral(text_buf[r & WINMASK]);
  543. X#ifdef DEBUG
  544. X      symbols_out++;
  545. X      if (verbose)
  546. X    fprintf(stderr, "'%s'\n",
  547. X      pr_char(text_buf[r & WINMASK]));
  548. X#endif                /* DEBUG */
  549. X    } else if (match_length >= chain_length) {
  550. X
  551. X/* GREEDY parsing (if match_length is big enough, put it right away) */
  552. X
  553. X#if defined(GATHER_STAT) || defined (DEBUG)
  554. X      refers_out++;
  555. X#endif
  556. X      EncodeLength(match_length - THRESHOLD);
  557. X      EncodePosition((int) ((r - match_position) & WINMASK) - 1);
  558. X
  559. X    } else {
  560. X      register int orig_length, orig_position;
  561. X      register us_t oldchar;
  562. X
  563. X/* This fragment (delayed coding, non-greedy) is due to ideas of
  564. X    Jan Mark Wams' <jms@cs.vu.nl> COMIC:
  565. X*/
  566. X      oldchar = text_buf[r & WINMASK];
  567. X      orig_length = match_length;
  568. X      orig_position = match_position;
  569. X
  570. X      Next_Char(WINSIZE, LOOKAHEAD);
  571. X      match_length = LOOKAHEAD + get_next_match(match_length - LOOKAHEAD, r);
  572. X
  573. X      if (match_length > len)
  574. X    match_length = len;
  575. X
  576. X      if (orig_length >= match_length) {
  577. X    EncodeLength(orig_length - THRESHOLD);
  578. X    EncodePosition((int) ((r - 1 - orig_position) & WINMASK) - 1);
  579. X#ifdef DEBUG
  580. X    match_position = orig_position;
  581. X#endif                /* DEBUG */
  582. X    match_length = orig_length - 1;
  583. X      } else {
  584. X    EncodeLiteral(oldchar);
  585. X#ifdef DEBUG
  586. X    symbols_out++;
  587. X    if (verbose)
  588. X      fprintf(stderr, "'%s'\n",
  589. X        pr_char(oldchar));
  590. X#endif                /* DEBUG */
  591. X    EncodeLength(match_length - THRESHOLD);
  592. X    EncodePosition((int) ((r - match_position) & WINMASK) - 1);
  593. X      }
  594. X
  595. X#if defined(GATHER_STAT) || defined (DEBUG)
  596. X      refers_out++;
  597. X#endif
  598. X#ifdef DEBUG
  599. X      if (verbose) {
  600. X    register pos = match_position, leng = match_length;
  601. X    fputc('"', stderr);
  602. X    for (; leng; leng--, pos++)
  603. X      fprintf(stderr, "%s",
  604. X        pr_char(text_buf[pos]));
  605. X    fprintf(stderr, "\"\n");
  606. X      }
  607. X#endif                /* DEBUG */
  608. X    }
  609. X
  610. X/* Process the rest of the matched sequence (insertion in the list
  611. X    only, without any matching !!!)
  612. X*/
  613. X
  614. X    for (i = 0; i < match_length &&
  615. X      (c = getchar()) != EOF; i++) {
  616. X      text_buf[s] = c;
  617. X      if (s < LOOKAHEAD - 1)
  618. X    text_buf[s + WINSIZE] = c;
  619. X      s = (s + 1) & WINMASK;
  620. X      r++;
  621. X      InsertNode();
  622. X    }
  623. X
  624. X    in_count += i;
  625. X
  626. X    INDICATOR
  627. X
  628. X      while (i++ < match_length) {
  629. X      len--;
  630. X      r++;
  631. X      InsertNode();
  632. X    }
  633. X
  634. X  }
  635. X
  636. X /* to flush literals */
  637. X  EncodeLength((short) ENDOF - LENGTH_OFFSET);
  638. X#ifdef DEBUG
  639. X  symbols_out++;
  640. X#endif
  641. X  FlushTail();
  642. X  if (ferror(stdout))
  643. X      writeerr();
  644. X  if (quiet < 0 && file_length != 0)
  645. X      fprintf(stderr, "100%%\b\b\b\b");
  646. X /* Print out stats on stderr */
  647. X  if (quiet != 1) {
  648. X#ifdef GATHER_STAT
  649. X    fprintf(stderr, "Average number of compares per matching: %d.%02d\n",
  650. X      (int) (node_compares / node_matches),
  651. X      (int) ((node_compares * 100 / node_matches) % 100));
  652. X    fprintf(stderr, "Average number of prolongations per reference: %d.%02d\n",
  653. X      (int) (node_prolongations / refers_out),
  654. X      (int) ((node_prolongations * 100 / refers_out) % 100));
  655. X    fprintf(stderr, "Average number of compares per prolongation: %d.%02d\n",
  656. X      (int) (node_compares / node_prolongations),
  657. X      (int) ((node_compares * 100 / node_prolongations) % 100));
  658. X    fprintf(stderr, "Prolongations/compares: %d/%d\n", node_prolongations,
  659. X      node_compares);
  660. X#endif
  661. X#ifdef DEBUG
  662. X    fprintf(stderr,
  663. X      "%ld chars in, %ld codes (%ld bytes) out, freezing factor: ",
  664. X      in_count, symbols_out + refers_out, bytes_out);
  665. X    prratio(stderr, in_count, bytes_out);
  666. X    fprintf(stderr, "\n");
  667. X    fprintf(stderr, "\tFreezing as in compact: ");
  668. X    prratio(stderr, in_count - bytes_out, in_count);
  669. X    prbits(stderr, in_count, bytes_out);
  670. X    fprintf(stderr, "\n");
  671. X    fprintf(stderr, "\tSymbols: %ld; references: %ld.\n",
  672. X      symbols_out, refers_out);
  673. X#else                /* !DEBUG */
  674. X    fprintf(stderr, "Freezing: ");
  675. X    prratio(stderr, in_count - bytes_out, in_count);
  676. X    prbits(stderr, in_count, bytes_out);
  677. X#endif                /* DEBUG */
  678. X  }
  679. X  if (bytes_out >= in_count)    /* exit(2) if no savings */
  680. X    exit_stat = 2;
  681. X  return;
  682. X}
  683. END_OF_FILE
  684.   if test 5594 -ne `wc -c <'encode.c'`; then
  685.     echo shar: \"'encode.c'\" unpacked with wrong size!
  686.   fi
  687.   # end of 'encode.c'
  688. fi
  689. if test -f 'freeze.1' -a "${1}" != "-c" ; then 
  690.   echo shar: Will not clobber existing file \"'freeze.1'\"
  691. else
  692.   echo shar: Extracting \"'freeze.1'\" \(7140 characters\)
  693.   sed "s/^X//" >'freeze.1' <<'END_OF_FILE'
  694. X.PU
  695. X.TH FREEZE 1 local
  696. X.SH NAME
  697. Xfreeze, unfreeze, melt, fcat  \-  compress and uncompress files
  698. X.SH SYNOPSIS
  699. X.ll +8
  700. X.B freeze
  701. X[
  702. X.B \-cdfvVgx
  703. X] [
  704. X.I "filename | type \&..."
  705. X]
  706. X.ll -8
  707. X.br
  708. X.B unfreeze
  709. X[
  710. X.B \-cfvV
  711. X] [
  712. X.I "filename \&..."
  713. X]
  714. X.br
  715. X.B melt
  716. X[
  717. X.B \-cfvV
  718. X] [
  719. X.I "filename \&..."
  720. X]
  721. X.br
  722. X.B fcat
  723. X[
  724. X.I "filename \&..."
  725. X]
  726. X.SH DESCRIPTION
  727. XCompresses the specified files or standard input.
  728. XEach file is replaced by a file with the extension
  729. X.B "\&.F,"
  730. Xbut only if the file got smaller. If no files are specified,
  731. Xthe compression is applied to the standard input
  732. Xand is written to standard output regardless of the results.
  733. XCompressed files can be restored to their original form by specifying the
  734. X.B \-d
  735. Xoption, or by running
  736. X.I melt
  737. Xor
  738. X.I unfreeze
  739. X(both linked to
  740. X.IR freeze ),
  741. Xon the 
  742. X.B "\&.F"
  743. Xfiles or the standard input.
  744. X.PP
  745. XIf the output file exists, it will not be overwritten unless the
  746. X.B \-f
  747. Xflag is given.  If
  748. X.B \-f
  749. Xis not specified and
  750. X.I freeze
  751. Xis run in the foreground,
  752. Xthe user is prompted
  753. Xas to whether the file should be overwritten.
  754. X.PP
  755. XIf the
  756. X.B \-g
  757. Xflag is given, a slightly less powerful (compression
  758. Xrate is 1.5% less), but somewhat faster heuristic is used. This flag can be
  759. Xused more than once (this mode is quite useful when freezing bitmaps) for
  760. Xadditional speedup.
  761. X.PP
  762. XIf you want to improve compression rate at the cost of speed, use
  763. X.B \-x
  764. Xflag. It means "maximum compression" (the speed may degrade
  765. Xsubstantially when freezing bitmaps).
  766. X.PP
  767. XIf the
  768. X.B \-f
  769. Xflag is given, all files specified are replaced with
  770. X.B "\&.F"
  771. Xfiles \- even if the file didn't get smaller.
  772. X.PP
  773. XWhen file names are given, the ownership (if run by root), modes, accessed
  774. Xand modified times are maintained between the file and its 
  775. X.B "\&.F"
  776. Xversion.  In this respect,
  777. X.I freeze
  778. Xcan be used for archival purposes, yet can still be used with
  779. X.IR make "(1)"
  780. Xafter melting.
  781. X.PP
  782. XThe
  783. X.B \-c
  784. Xoption causes the results of the freeze/melt operation to be written
  785. Xto stdout; no files are changed.  The
  786. X.I fcat
  787. Xprogram is the same as specifying
  788. X.B \-c
  789. Xto
  790. X.I melt
  791. X(all files are unpacked and written to stdout).
  792. X.PP
  793. XThe
  794. X.B \-v
  795. X(verbose) option causes the diagnostics (at the end of each file processing)
  796. Xto be printed to stderr, and the
  797. X.B \-vv
  798. Xoption causes the progress indicator to be drawn to the same place.
  799. X.PP
  800. X.I Type
  801. Xis a token preceded by a '+' or a '--', which defines the type
  802. Xof following files in the command string. An explicite definition
  803. Xof the file's type can give up to 2% of additional compression.
  804. XThe list of types is stored in file
  805. X.IR /usr/local/lib/freeze.cnf .
  806. XTypes may be abbreviated while not ambigious. You can also determine
  807. Xvalues for the static Huffman table by using a list of 8 numbers
  808. Xseparated by commas instead of
  809. X.I type.
  810. X.PP
  811. X.I Freeze
  812. Xuses the Lempel-Ziv algorithm on the first pass and the dynamic
  813. XHuffman algorithm on the second one. The size of sliding window
  814. Xis 8K, and the maximum length of matched string is 256.
  815. XThe positions on the window are coded using a static Huffman table.
  816. X.PP
  817. XA two byte magic number is prepended to the file
  818. Xto ensure that neither melting of random text nor refreezing of
  819. Xalready frozen text are attempted.  In addition, the characteristics
  820. Xof the static Huffman table being used during
  821. X.I freeze
  822. Xis written to the file so that these characteristics may be adapted
  823. Xto concrete conditions.
  824. X.PP
  825. X.ne 8
  826. XThe amount of compression obtained depends on the size of the
  827. Xinput file and the distribution of character substrings and their
  828. Xprobabilities.
  829. XTypically, text files, such as C programs,
  830. Xare reduced by 60\-75%, executable files are reduced by 50%.
  831. XCompression is generally much better than that achieved by
  832. XLZW coding (as used in
  833. X.IR compress ),
  834. Xor Huffman coding
  835. X.RI ( pack ),
  836. Xthough takes more time to compute.
  837. X.PP
  838. XIf the
  839. X.B \-V
  840. X(version) flag is given, the program's version number and compilation
  841. Xoptions are printed.
  842. X.PP
  843. XThe exit status is normally 0;
  844. Xif the last file gets bigger after freezing, the exit status is 2;
  845. Xif an error occurs, the exit status is 1.
  846. X.SH "SEE ALSO"
  847. Xcompact(1), pack(1), compress(1)
  848. X.SH "DIAGNOSTICS"
  849. XUnknown flag: 
  850. X.I "\'x\';"
  851. XUsage: freeze [-cdfvVg] [file|+type ...]
  852. X.in +8
  853. XInvalid options were specified on the command line.
  854. X.in -8
  855. X.IR file :
  856. Xnot in frozen format
  857. X.in +8
  858. XThe specified file has not been frozen.
  859. X.in -8
  860. X.IR file :
  861. Xalready has .F suffix -- no change
  862. X.in +8
  863. XCannot compress a file that has a ".F" suffix.
  864. X.IR mv "(1)"
  865. Xthe file to a different name and try again.
  866. X.in -8
  867. X.IR file :
  868. Xfilename too long to tack on .F
  869. X.in +8
  870. XThe specified file cannot be compressed because its filename is longer than
  871. X12 characters.
  872. X.IR mv "(1)"
  873. Xthe file to a different name and try again.  This message does not occur on
  874. X4.XBSD systems.
  875. X.in -8
  876. X.I file
  877. Xalready exists; do you wish to overwrite (y or n)?
  878. X.in +8
  879. XRespond "y" if you want the output file to be replaced; "n" if you want it
  880. Xto be left alone.
  881. X.in -8
  882. X.IR file :
  883. X.IR xx %
  884. X.in +8
  885. Xor
  886. X.in -8
  887. X.IR xxx K
  888. X.in +8
  889. XThese message fragments are written during the processing of a file, if
  890. X.B \-vv
  891. Xoption was given in the command line (in percents, if the length of file
  892. Xbeing processed is known; in Kbytes otherwise).
  893. X.in -8
  894. XFreezing:
  895. X.I "xx.xx% (y.yy"
  896. Xbits)
  897. X.in +8
  898. XThis message fragment gives the percentage of the input file that has been
  899. Xsaved by freezing and the number of remaining bits per byte of original file.
  900. X.in -8
  901. X-- not a regular file: unchanged
  902. X.in +8
  903. XThis message fragment is written when the input file is not a regular file.
  904. XThe input file is left unchanged.
  905. X.in -8
  906. X-- has 
  907. X.I xx 
  908. Xother links: unchanged
  909. X.in +8
  910. XThis message fragment is written when the input file has links.  The input
  911. Xfile is left unchanged.  See
  912. X.IR ln "(1)"
  913. Xfor more information.
  914. X.in -8
  915. X-- file unchanged
  916. X.in +8
  917. XThis message fragment is written when no savings are achieved by
  918. Xfreezing.  The input file is left unchanged.
  919. X.in -8
  920. X-- replaced with 
  921. X.I file
  922. X.in +8
  923. XThis message fragment is written when a file has been sucessfully
  924. Xfrozen/melt.
  925. X.in -8
  926. XUsing "
  927. X.I type
  928. X" type
  929. X.in +8
  930. XThis message indicates a successful switching to
  931. Xposition table for mentioned file type.
  932. X.in -8
  933. X"
  934. X.I xxx
  935. X" - no such file type
  936. X.in +8
  937. Xor
  938. X.in -8
  939. X.I xxx
  940. X- a list of 8 numbers expected
  941. X.in +8
  942. XThis message means the given file type does not exist or
  943. Xthe given string contains a comma, but is not a valid list
  944. Xof values for static Huffman table.
  945. X.in -8
  946. Xmelt: corrupt input
  947. X.in +8
  948. XThis message fragment is written when an error in header or
  949. Xunexpected end of frozen file is detected. Partial
  950. X(or empty, is there was an error in the header) file is created.
  951. X.in -8
  952. Xalready frozen -- file unchanged
  953. X.in +8
  954. XThis message fragment is written when an input file already has
  955. XFreeze's magic header.
  956. X.in -8
  957. XInvalid position table
  958. X.in +8
  959. Xor
  960. X.in -8
  961. X"
  962. X.I type
  963. X" - invalid entry
  964. X.in +8
  965. XThese messages appear only if Freeze has been made with incorrect
  966. Xdata for static Huffman table. It does never appear when freeze
  967. Xis called from a public access directory.
  968. X.in -8
  969. XUnknown header format
  970. X.in +8
  971. XUnknown values of flag bits were discovered in the header
  972. Xof frozen file.
  973. X.in -8
  974. X.SH "BUGS"
  975. XFound bugs descriptions, incompatibilities, etc.  please send to
  976. Xleo@ipmce.su.
  977. END_OF_FILE
  978.   if test 7140 -ne `wc -c <'freeze.1'`; then
  979.     echo shar: \"'freeze.1'\" unpacked with wrong size!
  980.   fi
  981.   # end of 'freeze.1'
  982. fi
  983. if test -f 'freeze.h' -a "${1}" != "-c" ; then 
  984.   echo shar: Will not clobber existing file \"'freeze.h'\"
  985. else
  986.   echo shar: Extracting \"'freeze.h'\" \(4017 characters\)
  987.   sed "s/^X//" >'freeze.h' <<'END_OF_FILE'
  988. X#include <stdio.h>
  989. X#include "config.h"
  990. X
  991. X#ifdef HAVE_SYS_STDTYPES_H
  992. X# include <sys/stdtypes.h>
  993. X#endif
  994. X
  995. X#ifndef getc
  996. X# ifdef m88k                   /* Green Hill C library bug. */
  997. X#  define getc(p)         (--(p)->_cnt < 0 ? __filbuf(p) : (int) *(p)->_ptr++)
  998. X# else
  999. X#  define getc(p)         (--(p)->_cnt < 0 ? _filbuf(p) : (int) *(p)->_ptr++)
  1000. X# endif
  1001. X#endif
  1002. X#ifndef putc
  1003. X# ifdef m88k                   /* Green Hill C library bug. */
  1004. X#  define putc(x, p)      (--(p)->_cnt < 0 ? __flsbuf((unsigned char) (x), (p)) : (int) (*(p)->_ptr++ = (unsigned char) (x)))
  1005. X# else
  1006. X#  define putc(x, p)      (--(p)->_cnt < 0 ? _flsbuf((unsigned char) (x), (p)) : (int) (*(p)->_ptr++ = (unsigned char) (x)))
  1007. X# endif
  1008. X#endif
  1009. X
  1010. X#if !defined(MSDOS) && defined(__MSDOS__)
  1011. X# define MSDOS
  1012. X#endif
  1013. X
  1014. X#ifdef MSDOS
  1015. X# define DOS
  1016. X# include <fcntl.h>
  1017. X#endif  /* MSDOS */
  1018. X
  1019. X#ifdef TOS
  1020. X# define DOS
  1021. X# define O_TEXT          0x01
  1022. X# define O_BINARY        0x02
  1023. X#endif
  1024. X
  1025. X#include <ctype.h>
  1026. X#include <signal.h>
  1027. X
  1028. X#ifndef RETSIGTYPE
  1029. X# define RETSIGTYPE void
  1030. X#endif /* RETSIGTYPE */
  1031. X
  1032. X#ifndef TOS
  1033. X# include <sys/types.h>
  1034. X# include <sys/stat.h>
  1035. X#else
  1036. X# include <tos.h>
  1037. X# include <types.h>
  1038. X#endif
  1039. X
  1040. X#ifdef SYSTIME
  1041. X# include <sys/time.h>
  1042. X# define UTIMES
  1043. X#else
  1044. X# ifdef UTIME
  1045. X#  include <utime.h>
  1046. X# else
  1047. X#  ifdef SYSUTIME
  1048. X#   include <sys/utime.h>
  1049. X#  else
  1050. X#   ifdef unix
  1051. X/*      UNIX without any declaration of utimbuf .... Strange! */
  1052. Xstruct utimbuf {
  1053. X    time_t actime;
  1054. X    time_t modtime;
  1055. X};
  1056. Xextern int utime();
  1057. X#   else
  1058. X#    ifndef DOS
  1059. X#     define BITS no_utimbuf_definition_on_unknown_system
  1060. X#    endif
  1061. X#   endif
  1062. X#  endif
  1063. X# endif
  1064. X#endif
  1065. X
  1066. X/* for MAXNAMLEN only !!! */
  1067. X#ifdef DIRENT
  1068. X# include <dirent.h>
  1069. X#else
  1070. X# ifdef SYSNDIR
  1071. X#  include <sys/ndir.h>
  1072. X# else
  1073. X#  ifdef SYSDIR
  1074. X#   include <sys/dir.h>
  1075. X#  endif
  1076. X# endif
  1077. X#endif
  1078. X
  1079. X#ifndef MAXNAMLEN
  1080. X# define MAXNAMLEN       255
  1081. X#endif
  1082. X
  1083. X#if MAXNAMLEN < 255
  1084. X# undef MAXNAMLEN
  1085. X# define MAXNAMLEN       255
  1086. X#endif
  1087. X
  1088. X#ifdef DEBUG
  1089. X# include <assert.h>
  1090. X#endif  /* DEBUG */
  1091. X
  1092. X#ifdef DOS
  1093. X# include <stdlib.h>
  1094. X#endif  /* DOS */
  1095. X
  1096. X#ifdef __TURBOC__
  1097. X# ifdef MSDOS
  1098. X#  include <io.h>
  1099. X#  include <alloc.h>
  1100. X# else /* TOS */
  1101. X#  include <ext.h>
  1102. X# endif  /* MSDOS */
  1103. X#endif /* __TURBOC__ */
  1104. X
  1105. Xtypedef unsigned short us_t;
  1106. Xtypedef unsigned char uc_t;
  1107. Xtypedef unsigned long ul_t;
  1108. X
  1109. X#define LOOKAHEAD       256     /* pre-sence buffer size */
  1110. X#define MAXDIST         7936
  1111. X#define WINSIZE         (MAXDIST + LOOKAHEAD)   /* must be a power of 2 */
  1112. X#define WINMASK         (WINSIZE - 1)
  1113. X
  1114. X#define THRESHOLD    2
  1115. X
  1116. X#define N_CHAR2         (256 - THRESHOLD + LOOKAHEAD + 1) /* code: 0 .. N_CHARi - 1 */
  1117. X#define T2              (N_CHAR2 * 2 - 1)       /* size of table */
  1118. X
  1119. X#define ENDOF           256                     /* pseudo-literal */
  1120. X
  1121. Xextern uc_t    Table2[];
  1122. X
  1123. Xextern long     in_count;
  1124. Xextern off_t    file_length;
  1125. X
  1126. Xextern uc_t     text_buf[];
  1127. X
  1128. Xextern long     indc_threshold, indc_count;
  1129. X
  1130. Xextern int      do_melt, topipe, greedy, quiet, force;  /* useful flags */
  1131. X
  1132. X#define MAGIC1          ((uc_t)'\037')
  1133. X#define MAGIC2_1        ((uc_t)'\236')          /* freeze vers. 1.X */
  1134. X#define MAGIC2_2        ((uc_t)'\237')
  1135. X
  1136. Xextern int exit_stat;
  1137. X
  1138. X#ifdef DEBUG
  1139. Xextern int debug, verbose;
  1140. Xextern char * pr_char();
  1141. X#endif /* DEBUG */
  1142. X
  1143. X#if defined(GATHER_STAT) || defined(DEBUG)
  1144. Xextern long refers_out, symbols_out;
  1145. X#endif
  1146. X
  1147. Xextern void melt2(), (*meltfunc)(), writeerr(), prratio(), prbits(), freeze();
  1148. X
  1149. X#ifdef COMPAT
  1150. X#include "compat.h"
  1151. X#endif
  1152. X
  1153. X#define INDICATOR \
  1154. Xif (quiet < 0 && (in_count > indc_count)) {\
  1155. X    if (ferror(stdout))\
  1156. X        writeerr();\
  1157. X    if (file_length) {\
  1158. X        static int percents, old_percents = -1;\
  1159. X        if ((percents = ftell(stdin) * 100 / file_length) !=\
  1160. X            old_percents) {\
  1161. X            fprintf(stderr, " %2d%%\b\b\b\b", percents);\
  1162. X            old_percents = percents;\
  1163. X        }\
  1164. X        indc_count += indc_threshold;\
  1165. X    } else {\
  1166. X        fprintf(stderr, " %5ldK\b\b\b\b\b\b\b", in_count / 1024);\
  1167. X        indc_count += indc_threshold;\
  1168. X        indc_threshold += 1024;\
  1169. X    }\
  1170. X    fflush (stderr);\
  1171. X}
  1172. X
  1173. X#ifdef HAVE_RINDEX
  1174. X#define strchr index
  1175. X#define strrchr rindex
  1176. X#endif
  1177. X
  1178. Xextern char *strchr(), *strrchr();
  1179. X
  1180. END_OF_FILE
  1181.   if test 4017 -ne `wc -c <'freeze.h'`; then
  1182.     echo shar: \"'freeze.h'\" unpacked with wrong size!
  1183.   fi
  1184.   # end of 'freeze.h'
  1185. fi
  1186. if test -f 'huf.c' -a "${1}" != "-c" ; then 
  1187.   echo shar: Will not clobber existing file \"'huf.c'\"
  1188. else
  1189.   echo shar: Extracting \"'huf.c'\" \(8925 characters\)
  1190.   sed "s/^X//" >'huf.c' <<'END_OF_FILE'
  1191. X#include "freeze.h"
  1192. X#include "huf.h"
  1193. X#include "bitio.h"
  1194. X
  1195. X/*----------------------------------------------------------------------*/
  1196. X/*                                    */
  1197. X/*        HUFFMAN ENCODING                    */
  1198. X/*                                    */
  1199. X/*----------------------------------------------------------------------*/
  1200. X
  1201. X/* TABLES OF ENCODE/DECODE for upper 6 bits position information */
  1202. X
  1203. X/* The contents of `Table' are used for freezing only, so we use
  1204. X * it freely when melting.
  1205. X */
  1206. X
  1207. X#ifndef HUFVALUES
  1208. X#define HUFVALUES 0,0,1,2,6,19,34,0
  1209. X#endif
  1210. X
  1211. Xuc_t Table2[9] = { 0, HUFVALUES };
  1212. X
  1213. X/* d_len is really the number of bits to read to complete literal
  1214. X * part of position information.
  1215. X */
  1216. Xuc_t p_len[64];        /* These arrays are built accordingly to values */
  1217. Xuc_t d_len[256];       /* of `Table' above which are default, from the */
  1218. X              /* command line or from the header of frozen file */
  1219. Xuc_t code[256];
  1220. X
  1221. X/* use arrays of native word-size elements to improve speed */
  1222. X
  1223. Xunsigned freq[T2 + 1];          /* frequency table */
  1224. Xint     son[T2];                /* points to son node (son[i],son[i+1]) */
  1225. Xint     prnt[T2 + N_CHAR2];     /* points to parent node */
  1226. X
  1227. Xstatic  int t, r, chars;
  1228. X
  1229. X/* notes :
  1230. X   prnt[Tx .. Tx + N_CHARx - 1] used by
  1231. X   indicates leaf position that corresponding to code.
  1232. X*/
  1233. X
  1234. X/* Initializes Huffman tree, bit I/O variables, etc.
  1235. X   Static array is initialized with `table', dynamic Huffman tree
  1236. X   has `n_char' leaves.
  1237. X*/
  1238. X
  1239. Xvoid StartHuff (n_char)
  1240. X    int n_char;
  1241. X{
  1242. X    register int i, j;
  1243. X    t = n_char * 2 - 1;
  1244. X    r = t - 1;
  1245. X    chars = n_char;
  1246. X
  1247. X/* A priori frequences are 1 */
  1248. X
  1249. X    for (i = 0; i < n_char; i++) {
  1250. X        freq[i] = 1;
  1251. X        son[i] = i + t;
  1252. X        prnt[i + t] = i;
  1253. X    }
  1254. X    i = 0; j = n_char;
  1255. X
  1256. X/* Building the balanced tree */
  1257. X
  1258. X    while (j <= r) {
  1259. X        freq[j] = freq[i] + freq[i + 1];
  1260. X        son[j] = i;
  1261. X        prnt[i] = prnt[i + 1] = j;
  1262. X        i += 2; j++;
  1263. X    }
  1264. X    freq[t] = 0xffff;
  1265. X    prnt[r] = 0;
  1266. X    in_count = 1;
  1267. X    bytes_out = 5;
  1268. X#if defined(DEBUG) || defined (GATHER_STAT)
  1269. X    symbols_out = refers_out = 0;
  1270. X#endif
  1271. X}
  1272. X
  1273. X/* Reconstructs tree with `chars' leaves */
  1274. X
  1275. Xvoid reconst ()
  1276. X{
  1277. X    register int i, j, k;
  1278. X    register unsigned f;
  1279. X
  1280. X#ifdef DEBUG
  1281. X    if (quiet < 0)
  1282. X      fprintf(stderr,
  1283. X        "Reconstructing Huffman tree: symbols: %ld, references: %ld\n",
  1284. X        symbols_out, refers_out);
  1285. X#endif
  1286. X
  1287. X/* correct leaf node into of first half,
  1288. X   and set these freqency to (freq+1)/2
  1289. X*/
  1290. X    j = 0;
  1291. X    for (i = 0; i < t; i++) {
  1292. X        if (son[i] >= t) {
  1293. X            freq[j] = (freq[i] + 1) / 2;
  1294. X            son[j] = son[i];
  1295. X            j++;
  1296. X        }
  1297. X    }
  1298. X/* Build tree.  Link sons first */
  1299. X
  1300. X    for (i = 0, j = chars; j < t; i += 2, j++) {
  1301. X        k = i + 1;
  1302. X        f = freq[j] = freq[i] + freq[k];
  1303. X        for (k = j - 1; f < freq[k]; k--);
  1304. X        k++;
  1305. X        {       register unsigned *p, *e;
  1306. X            for (p = &freq[j], e = &freq[k]; p > e; p--)
  1307. X                p[0] = p[-1];
  1308. X            freq[k] = f;
  1309. X        }
  1310. X        {       register int *p, *e;
  1311. X            for (p = &son[j], e = &son[k]; p > e; p--)
  1312. X                p[0] = p[-1];
  1313. X            son[k] = i;
  1314. X        }
  1315. X    }
  1316. X
  1317. X/* Link parents */
  1318. X    for (i = 0; i < t; i++) {
  1319. X        if ((k = son[i]) >= t) {
  1320. X            prnt[k] = i;
  1321. X        } else {
  1322. X            prnt[k] = prnt[k + 1] = i;
  1323. X        }
  1324. X    }
  1325. X}
  1326. X
  1327. X
  1328. X/* Updates given code's frequency, and updates tree */
  1329. X
  1330. Xvoid update (c)
  1331. X    register int c;
  1332. X{
  1333. X    register unsigned k, *p;
  1334. X    register int    i, j, l;
  1335. X
  1336. X    if (freq[r] == MAX_FREQ) {
  1337. X        reconst();
  1338. X    }
  1339. X    c = prnt[c + t];
  1340. X    do {
  1341. X        k = ++freq[c];
  1342. X
  1343. X        /* swap nodes when become wrong frequency order. */
  1344. X        if (k > freq[l = c + 1]) {
  1345. X            for (p = freq+l+1; k > *p++; ) ;
  1346. X            l = p - freq - 2;
  1347. X            freq[c] = p[-2];
  1348. X            p[-2] = k;
  1349. X
  1350. X            i = son[c];
  1351. X            prnt[i] = l;
  1352. X            if (i < t) prnt[i + 1] = l;
  1353. X
  1354. X            j = son[l];
  1355. X            son[l] = i;
  1356. X
  1357. X            prnt[j] = c;
  1358. X            if (j < t) prnt[j + 1] = c;
  1359. X            son[c] = j;
  1360. X
  1361. X            c = l;
  1362. X        }
  1363. X    } while ((c = prnt[c]) != 0);    /* loop until reach to root */
  1364. X}
  1365. X
  1366. X/* Encodes the literal or the length information */
  1367. X
  1368. Xvoid EncodeChar (c)
  1369. X    int c;
  1370. X{
  1371. X    register int k, len = 0;
  1372. X    register unsigned hcode = 0;
  1373. X#ifdef INT_16_BITS
  1374. X    register unsigned hcode2 = 0;
  1375. X#endif
  1376. X    DefBits;
  1377. X
  1378. X    k = prnt[c + t];
  1379. X
  1380. X/* trace links from leaf node to root */
  1381. X    do {
  1382. X/* if node index is odd, trace larger of sons */
  1383. X#ifdef INT_16_BITS
  1384. X        if (len < 16) {
  1385. X#endif
  1386. X            hcode |= (unsigned) (k & 1) << len;
  1387. X#ifdef INT_16_BITS
  1388. X        } else {
  1389. X            hcode2 |= (unsigned) (k & 1) << len;
  1390. X        }
  1391. X#endif
  1392. X        len++;
  1393. X    } while ((k = prnt[k]) != r);
  1394. X
  1395. X#ifdef INT_16_BITS
  1396. X    if (len > 16) {
  1397. X        PutNLowBits(hcode2, len - 16);
  1398. X        FlushBits();
  1399. X        PutNLowBits(hcode >> 8, 8);
  1400. X        FlushBits();
  1401. X        hcode &= 0xFF;
  1402. X        len = 8;
  1403. X    } else if (len > 8) {
  1404. X        PutNLowBits(hcode >> 8, len - 8);
  1405. X        FlushBits();
  1406. X        hcode &= 0xFF;
  1407. X        len = 8;
  1408. X    }
  1409. X#endif
  1410. X    PutNLowBits(hcode, len);
  1411. X    FlushBits();
  1412. X    KeepBits();
  1413. X    if (ferror(stdout))
  1414. X        writeerr();
  1415. X    update(c);
  1416. X}
  1417. X
  1418. X/* Encodes the position information */
  1419. X
  1420. Xvoid EncodePosition (c)
  1421. X    register int c;
  1422. X{
  1423. X    DefBits;
  1424. X    /* output upper 6 bit from table */
  1425. X    PutNLowBits(code[c >> 7], p_len[c >> 7]);
  1426. X#ifdef INT_16_BITS
  1427. X    FlushBits();
  1428. X#endif
  1429. X    /* output lower 7 bit */
  1430. X    PutNLowBits(c & 0x7f, 7);
  1431. X    FlushBits();
  1432. X    KeepBits();
  1433. X}
  1434. X
  1435. X/* Decodes the literal or length info and returns its value.
  1436. X    Returns ENDOF, if the file is corrupt.
  1437. X*/
  1438. X
  1439. Xint DecodeChar ()
  1440. X{
  1441. X    register int c = r;
  1442. X    DefBits;
  1443. X
  1444. X    if (overrun >= sizeof(bitbuf)) {
  1445. X        crpt_message();
  1446. X        return ENDOF;
  1447. X    }
  1448. X    /* As far as MAX_FREQ == 32768, maximum length of a Huffman
  1449. X     * code cannot exceed 23 (consider Fibonacci numbers),
  1450. X     * so we don't need additional FillBits while decoding
  1451. X     * if sizeof(int) == 4.
  1452. X     */
  1453. X    FillBits();
  1454. X    /* trace from root to leaf,
  1455. X       got bit is 0 to small(son[]), 1 to large (son[]+1) son node */
  1456. X
  1457. X    while ((c = son[c]) < t) {
  1458. X        c += GetBit();
  1459. X#ifdef INT_16_BITS
  1460. X        if (loclen == 0)
  1461. X            FillBits();
  1462. X#endif
  1463. X    }
  1464. X    KeepBits();
  1465. X    update(c -= t);
  1466. X    return c;
  1467. X}
  1468. X
  1469. X/* Decodes the position info and returns it */
  1470. X
  1471. Xint DecodePosition ()
  1472. X{
  1473. X    register        i, j;
  1474. X    DefBits;
  1475. X
  1476. X    /* Upper 6 bits can be coded by a byte (8 bits) or less,
  1477. X     * plus 7 bits literally ...
  1478. X     */
  1479. X    FillBits();
  1480. X    /* decode upper 6 bits from the table */
  1481. X    i = GetByte();
  1482. X    j = (code[i] << 7) | (i << d_len[i]) & 0x7F;
  1483. X
  1484. X    /* get lower 7 bits literally */
  1485. X#ifdef INT_16_BITS
  1486. X    FillBits();
  1487. X#endif
  1488. X    j |= GetNBits(d_len[i]);
  1489. X    KeepBits();
  1490. X    return j;
  1491. X}
  1492. X
  1493. X#ifdef COMPAT
  1494. X
  1495. Xuc_t Table1[9] = { 0, 0, 0, 1, 3, 8, 12, 24, 16 };
  1496. X
  1497. X/* Old version of a routine above for handling files made by
  1498. X    the 1st version of Freeze.
  1499. X*/
  1500. X
  1501. Xshort DecodePOld ()
  1502. X{
  1503. X    register        i, j;
  1504. X    DefBits;
  1505. X
  1506. X    FillBits();
  1507. X    i = GetByte();
  1508. X    j = (code[i] << 6) | (i << d_len[i]) & 0x3F;
  1509. X#ifdef INT_16_BITS
  1510. X    FillBits();
  1511. X#endif
  1512. X    j |= GetNBits(d_len[i]);
  1513. X    KeepBits();
  1514. X    return j;
  1515. X}
  1516. X#endif
  1517. X
  1518. X/* Initializes static Huffman arrays */
  1519. X
  1520. Xvoid init(table) uc_t * table; {
  1521. X    short i, j, k, num;
  1522. X    num = 0;
  1523. X
  1524. X/* There are `table[i]' `i'-bits Huffman codes */
  1525. X
  1526. X    for(i = 1, j = 0; i <= 8; i++) {
  1527. X        num += table[i] << (8 - i);
  1528. X        for(k = table[i]; k; j++, k--)
  1529. X            p_len[j] = i;
  1530. X    }
  1531. X    if (num != 256) {
  1532. X        fprintf(stderr, "Invalid position table\n");
  1533. X        exit(1);
  1534. X    }
  1535. X    num = j;
  1536. X    if (do_melt == 0)
  1537. X
  1538. X/* Freezing: building the table for encoding */
  1539. X
  1540. X        for(i = j = 0;;) {
  1541. X            code[j] = i;
  1542. X            i++;
  1543. X            j++;
  1544. X            if (j == num) break;
  1545. X            i <<= p_len[j] - p_len[j-1];
  1546. X        }
  1547. X    else {
  1548. X
  1549. X/* Melting: building the table for decoding */
  1550. X
  1551. X        for(k = j = 0; j < num; j ++)
  1552. X            for(i = 1 << (8 - p_len[j]); i--;)
  1553. X                code[k++] = j;
  1554. X
  1555. X        for(k = j = 0; j < num; j ++)
  1556. X            for(i = 1 << (8 - p_len[j]); i--;)
  1557. X                d_len[k++] =  p_len[j] - 1
  1558. X#ifdef COMPAT
  1559. X                - (table == Table1)
  1560. X#endif
  1561. X                            ;
  1562. X    }
  1563. X}
  1564. X
  1565. X/* Writes a 3-byte header into the frozen form of file; Table[7] and
  1566. X    Table[8] aren't necessary, see `read_header'.
  1567. X*/
  1568. X
  1569. Xvoid write_header() {
  1570. X    unsigned i;
  1571. X
  1572. X    i = Table2[5] & 0x1F; i <<= 4;
  1573. X    i |= Table2[4] & 0xF; i <<= 3;
  1574. X    i |= Table2[3] & 7;   i <<= 2;
  1575. X    i |= Table2[2] & 3;   i <<= 1;
  1576. X    i |= Table2[1] & 1;
  1577. X
  1578. X    putchar((int)(i & 0xFF));
  1579. X    putchar((int)((i >> 8)));
  1580. X    putchar((int)(Table2[6] & 0x3F));
  1581. X    if (ferror(stdout))
  1582. X        writeerr();
  1583. X}
  1584. X
  1585. X/* Reconstructs `Table' from the header of the frozen file and checks
  1586. X    its correctness. Returns 0 if OK, EOF otherwise.
  1587. X*/
  1588. X
  1589. Xint read_header() {
  1590. X    int i, j;
  1591. X    i = getchar() & 0xFF;
  1592. X    i |= (getchar() & 0xFF) << 8;
  1593. X    Table2[1] = i & 1; i >>= 1;
  1594. X    Table2[2] = i & 3; i >>= 2;
  1595. X    Table2[3] = i & 7; i >>= 3;
  1596. X    Table2[4] = i & 0xF; i >>= 4;
  1597. X    Table2[5] = i & 0x1F; i >>= 5;
  1598. X
  1599. X    if (i & 1 || (i = getchar()) & 0xC0) {
  1600. X        fprintf(stderr, "Unknown header format.\n");
  1601. X        crpt_message();
  1602. X        return EOF;
  1603. X    }
  1604. X
  1605. X    Table2[6] = i & 0x3F;
  1606. X
  1607. X    i = Table2[1] + Table2[2] + Table2[3] + Table2[4] +
  1608. X    Table2[5] + Table2[6];
  1609. X
  1610. X    i = 62 - i;     /* free variable length codes for 7 & 8 bits */
  1611. X
  1612. X    j = 128 * Table2[1] + 64 * Table2[2] + 32 * Table2[3] +
  1613. X    16 * Table2[4] + 8 * Table2[5] + 4 * Table2[6];
  1614. X
  1615. X    j = 256 - j;    /* free byte images for these codes */
  1616. X
  1617. X/*      Equation:
  1618. X        Table[7] + Table[8] = i
  1619. X    2 * Table[7] + Table[8] = j
  1620. X*/
  1621. X    j -= i;
  1622. X    if (j < 0 || i < j) {
  1623. X        crpt_message();
  1624. X        return EOF;
  1625. X    }
  1626. X    Table2[7] = j;
  1627. X    Table2[8] = i - j;
  1628. X
  1629. X#ifdef DEBUG
  1630. X    fprintf(stderr, "Codes: %d %d %d %d %d %d %d %d\n",
  1631. X        Table2[1], Table2[2], Table2[3], Table2[4],
  1632. X        Table2[5], Table2[6], Table2[7], Table2[8]);
  1633. X#endif
  1634. X    return 0;
  1635. X}
  1636. X
  1637. X/* File too short or invalid header, print a message */
  1638. Xvoid crpt_message ( )
  1639. X{
  1640. X    fprintf ( stderr, "melt: corrupt input\n" );
  1641. X}
  1642. X
  1643. END_OF_FILE
  1644.   if test 8925 -ne `wc -c <'huf.c'`; then
  1645.     echo shar: \"'huf.c'\" unpacked with wrong size!
  1646.   fi
  1647.   # end of 'huf.c'
  1648. fi
  1649. if test -f 'huf.h' -a "${1}" != "-c" ; then 
  1650.   echo shar: Will not clobber existing file \"'huf.h'\"
  1651. else
  1652.   echo shar: Extracting \"'huf.h'\" \(214 characters\)
  1653.   sed "s/^X//" >'huf.h' <<'END_OF_FILE'
  1654. Xextern void StartHuff(), init(), write_header(), EncodeChar(), crpt_message();
  1655. Xextern int DecodeChar(), DecodePosition();
  1656. Xextern void EncodePosition();
  1657. X#define MAX_FREQ        (us_t)0x8000 /* Tree update timing */
  1658. END_OF_FILE
  1659.   if test 214 -ne `wc -c <'huf.h'`; then
  1660.     echo shar: \"'huf.h'\" unpacked with wrong size!
  1661.   fi
  1662.   # end of 'huf.h'
  1663. fi
  1664. if test -f 'lz.h' -a "${1}" != "-c" ; then 
  1665.   echo shar: Will not clobber existing file \"'lz.h'\"
  1666. else
  1667.   echo shar: Extracting \"'lz.h'\" \(2745 characters\)
  1668.   sed "s/^X//" >'lz.h' <<'END_OF_FILE'
  1669. Xextern void InitTree();
  1670. X
  1671. X#ifndef SEGMENTED
  1672. X# define MAXBITS 16
  1673. X#else
  1674. X# ifdef INT_16_BITS
  1675. X#  define MAXBITS 15
  1676. X# else
  1677. X#  define MAXBITS 14
  1678. X# endif
  1679. X#endif
  1680. X
  1681. X#ifdef SEGMENTED
  1682. X# ifdef TINY
  1683. X#  undef MAXBITS
  1684. X#  define MAXBITS 13
  1685. X# endif
  1686. X#endif
  1687. X
  1688. X#ifndef BITS
  1689. X# define BITS    MAXBITS
  1690. X#endif
  1691. X
  1692. X#if BITS < 13
  1693. X# undef BITS
  1694. X# define BITS    13      /* 1:1 hash */
  1695. X#endif
  1696. X
  1697. X#if BITS > MAXBITS
  1698. X# undef BITS
  1699. X# define BITS    MAXBITS
  1700. X#endif
  1701. X
  1702. X/* The following hash-function isn't optimal but it is very fast:
  1703. X
  1704. X    HASH =      ((first + (second << LEN0) +
  1705. X            (third << LEN1)) & ((1L << BITS) - 1);
  1706. X
  1707. X  The difference of LENs is no more than one bit.
  1708. X*/
  1709. X
  1710. X#define LEN0    ((BITS-8)/2)
  1711. X#define LEN1    (BITS-8)
  1712. X
  1713. X#define hash_size      (1L << BITS)
  1714. X
  1715. X/* Use native size hash unless required otherwise */
  1716. X#if defined(SMALL) || defined(TINY)
  1717. Xtypedef us_t hash_t;
  1718. X#else
  1719. Xtypedef unsigned hash_t;
  1720. X#endif  /* SMALL || TINY */
  1721. X
  1722. Xextern int       match_position, chain_length;
  1723. X
  1724. Xextern hash_t hashtab[], next[];
  1725. X
  1726. X/* Some defines to eliminate function-call overhead */
  1727. X
  1728. X/* Hash function (no more than 16 bits, so we don't need longs */
  1729. X
  1730. X#define hash(p)\
  1731. X    ((unsigned)(p)[0] + ((unsigned)(p)[1] << LEN0) +\
  1732. X    ((unsigned)(p)[2] << LEN1))
  1733. X
  1734. X#ifdef FASTHASH
  1735. X#define hashof(p)\
  1736. X    (((p)[0] != (p)[1] ? hash(p) : hash(p) + hash((p) + 3)) &\
  1737. X    ((1L << BITS) - 1))
  1738. X#else
  1739. X#define hashof(p)\
  1740. X    (hash(p) & ((1L << BITS) - 1))
  1741. X#endif
  1742. X
  1743. X/* Inserting of a node `r' into hashed linked list: `r' becomes
  1744. X    the head of list.
  1745. X*/
  1746. X
  1747. X#define InsertNode()\
  1748. X{\
  1749. X    register uc_t  *key = &text_buf[r & WINMASK];\
  1750. X    register unsigned p = hashof(key);\
  1751. X    if (r < MAXDIST) /* wraparound occured */\
  1752. X        r = rehash(r);\
  1753. X    next[r & WINMASK] = hashtab[p];\
  1754. X    hashtab[p] = r;\
  1755. X}
  1756. X
  1757. X/* This routine inputs the char from stdin and does some other
  1758. X    actions depending of this char's presence.
  1759. X*/
  1760. X
  1761. X#define Next_Char(N,F)\
  1762. X{\
  1763. X    if ((c = getchar()) != EOF) {\
  1764. X        text_buf[s] = c;\
  1765. X        if (s < F - 1)\
  1766. X            text_buf[s + N] = c;\
  1767. X        s = (s + 1) & (N - 1);\
  1768. X        in_count++;\
  1769. X    } else\
  1770. X        len--;\
  1771. X    r++;\
  1772. X    InsertNode();\
  1773. X}
  1774. X
  1775. X#if defined(__GNUC__)
  1776. X#if defined(__i386__)
  1777. X/* Optimizer cannot allocate these registers correctly :( (v1.39) */
  1778. X#define FIX_SI  asm("si")
  1779. X#define FIX_DI  asm("di")
  1780. X#else
  1781. X
  1782. X/* GNU-style register allocations for other processors are welcome! */
  1783. X
  1784. X#define FIX_SI
  1785. X#define FIX_DI
  1786. X#endif
  1787. X#else
  1788. X
  1789. X/* Dummy defines for non-GNU compilers */
  1790. X
  1791. X#define FIX_SI
  1792. X#define FIX_DI
  1793. X#endif
  1794. X
  1795. X/* some heuristic to avoid necessity of "-ggg..." */
  1796. X#define CHAIN_THRESHOLD (LOOKAHEAD / 2)
  1797. X
  1798. Xextern int get_next_match();
  1799. Xextern hash_t rehash();
  1800. X
  1801. X#ifdef GATHER_STAT
  1802. Xextern long node_matches, node_compares, node_prolongations;
  1803. X#endif
  1804. X
  1805. X#ifdef ALLOW_MISALIGN
  1806. X#define FETCH(array,index) *(us_t*)(&array[index]-1)
  1807. X#else
  1808. X#define FETCH(array,index) array[index]
  1809. X#endif
  1810. END_OF_FILE
  1811.   if test 2745 -ne `wc -c <'lz.h'`; then
  1812.     echo shar: \"'lz.h'\" unpacked with wrong size!
  1813.   fi
  1814.   # end of 'lz.h'
  1815. fi
  1816. if test -f 'statist.1' -a "${1}" != "-c" ; then 
  1817.   echo shar: Will not clobber existing file \"'statist.1'\"
  1818. else
  1819.   echo shar: Extracting \"'statist.1'\" \(3300 characters\)
  1820.   sed "s/^X//" >'statist.1' <<'END_OF_FILE'
  1821. X.PU
  1822. X.TH STATIST 1 local
  1823. X.SH NAME
  1824. Xstatist  \-  calculate Huffman distribution for
  1825. X.IR freeze "(1)"
  1826. X.SH SYNOPSIS
  1827. X.ll +8
  1828. X.B statist
  1829. X[
  1830. X.B \-gx...
  1831. X]
  1832. X.ll -8
  1833. X.br
  1834. X.SH DESCRIPTION
  1835. XThe default table is tuned for both C texts and executable files (as in
  1836. XLHARC). If you will freeze any other files (natural language texts,
  1837. Xdatabases, images, fonts, etc.) you can calculate the matching
  1838. Xpositions distribution using the
  1839. X.B "`statist'"
  1840. Xprogram, which calculates and displays the mentioned
  1841. Xdistribution for the given file. It is useful for large (100K or more)
  1842. Xfiles.
  1843. X
  1844. XThough the built-in position table is polyvalent, the tuning can increase
  1845. Xthe compression rate up to one additional percent. (Observed mainly on
  1846. Xtext files.)
  1847. X.SH USAGE
  1848. X.br
  1849. X.B statist [\-g...] < sample_file
  1850. X.in +8
  1851. Xor
  1852. X.in -8
  1853. X.B gensample | statist [\-g...]
  1854. X.br
  1855. Xwhere
  1856. X.B "`gensample'"
  1857. Xis a program generating some sample stream of
  1858. Xbytes similar to files to be frozen.
  1859. X.PP
  1860. XThe
  1861. X.B \-g
  1862. Xand
  1863. X.B \-x
  1864. Xswitches have the same meaning as for
  1865. X.IR freeze "(1)"
  1866. Xand may be repeated.
  1867. X.PP
  1868. XYou can also see the intermediate values
  1869. Xand watch their changes by pressing INTR key when you wish.
  1870. X.PP
  1871. XNote: If you use 
  1872. X.B "gensample | statist"
  1873. X, remember that INTR influence BOTH
  1874. Xprocesses !!
  1875. X.br
  1876. XThe results have the following format:
  1877. X.br
  1878. X.I "n1 n2 n3 n4 n5 n6 n7 n8"
  1879. X(uncertainty =
  1880. X.I x)
  1881. X.br
  1882. XAverage match length:
  1883. X.I xx.yy
  1884. X.br
  1885. XPercentile 99.9:
  1886. X.I p999
  1887. X.br
  1888. XPercentile 99.5:
  1889. X.I p995
  1890. X.br
  1891. XPercentile 99.0:
  1892. X.I p990
  1893. X.br
  1894. XPercentile 97.0:
  1895. X.I p970
  1896. X.br
  1897. XPercentile 95.0:
  1898. X.I p950
  1899. X.br
  1900. XPercentile 90.0:
  1901. X.I p900
  1902. X.br
  1903. XPercentile 80.0:
  1904. X.I p800
  1905. X.br
  1906. XPercentile 70.0:
  1907. X.I p700
  1908. X.br
  1909. XPercentile 50.0:
  1910. X.I p500
  1911. X.br
  1912. XSigma:
  1913. X.I xx.yy
  1914. X.br
  1915. X.PP
  1916. XHere
  1917. X.I n1 \- n8
  1918. Xare values of the calculated position table elements,
  1919. Xuncertainty is a number which denotes validity of given results
  1920. X(non-zero values of uncertainty indicate that the
  1921. Xresults may be unusable). Other values (average match length,
  1922. Xpercentiles and sigma) are FYI only.
  1923. X.PP
  1924. XYou may create the 
  1925. X.IR /etc/default/freeze
  1926. Xfile (if you don't like
  1927. X.IR /etc/default/
  1928. Xdirectory, choose another - in MS-DOS it is FREEZE.CNF in
  1929. Xthe directory of FREEZE.EXE), which has the following format:
  1930. X.in +8
  1931. X.I name
  1932. X=
  1933. X.I "n1 n2 n3 n4 n5 n6 n7 n8"
  1934. X.in -8
  1935. X.I (name
  1936. Xmust start in column 1). For example:
  1937. X.ll +8
  1938. X.br
  1939. X---------- cut here -----------
  1940. X.br
  1941. X# This is freeze's defaults file
  1942. X.br
  1943. Xrussian=0 0 1 2 6 20 31 2   # The sample was mailx.lp (Russian)
  1944. X.br
  1945. Xenglish=0 0 1 2 7 16 36 0   # The sample was gcc.lp (English)
  1946. X.br
  1947. X# End of file
  1948. X.br
  1949. X---------- cut here -----------
  1950. X.ll -8
  1951. X.PP
  1952. XIf you find values, which are better THAN DEFAULT both for text (C
  1953. Xprograms) and binary (executable) files, please send them to me.
  1954. X
  1955. XImportant note: statist.c is NOT a part of freeze package, it is an
  1956. Xaditional feature.
  1957. X
  1958. X.SH "SEE ALSO"
  1959. Xfreeze(1), melt(1), fcat(1)
  1960. X.SH "DIAGNOSTICS"
  1961. XHuffman tree has more than 8 levels, reducing...
  1962. X.in +8
  1963. XSelf-explanatory, but sometimes reducing falls into infinite loop.
  1964. X.in -8
  1965. X.IR xxx K
  1966. X.in +8
  1967. XProgress indicator is written after each 4K of a file processed.
  1968. X.in -8
  1969. X.SH "BUGS"
  1970. XSometimes use of the results with uncertainty = 1 (on a file)
  1971. Xgives compression rate worse than default but use of the results
  1972. Xwith uncertainty = 13 (on other file) works quite good.
  1973. X.PP
  1974. XFound bugs descriptions, incompatibilities, etc.  please send to
  1975. Xleo@s514.ipmce.su.
  1976. X
  1977. END_OF_FILE
  1978.   if test 3300 -ne `wc -c <'statist.1'`; then
  1979.     echo shar: \"'statist.1'\" unpacked with wrong size!
  1980.   fi
  1981.   # end of 'statist.1'
  1982. fi
  1983. if test -f 'statist.c' -a "${1}" != "-c" ; then 
  1984.   echo shar: Will not clobber existing file \"'statist.c'\"
  1985. else
  1986.   echo shar: Extracting \"'statist.c'\" \(6374 characters\)
  1987.   sed "s/^X//" >'statist.c' <<'END_OF_FILE'
  1988. X#include "freeze.h"
  1989. X#include "lz.h"
  1990. X
  1991. X/* This program calculates the distribution of the matched strings'
  1992. Xpositions and lengths using nearly the same code as `freeze'.
  1993. X*/
  1994. X
  1995. X#define N_POS 62
  1996. X#define T (N_POS * 2 - 1)
  1997. X#define R (T - 1)
  1998. X
  1999. X#define update(c) (/* fprintf(stderr, "%d\n", c), */ freq[c]++)
  2000. X
  2001. Xlong in_count, refers = 0;
  2002. X
  2003. Xlong indc_count;
  2004. Xint reduceflag = 0, greedy = 0;
  2005. X
  2006. Xint lens[LOOKAHEAD+1];
  2007. X
  2008. Xus_t bits[9];
  2009. X
  2010. Xshort   prnt[T];
  2011. Xul_t freq[T];
  2012. Xshort used[T];
  2013. X
  2014. Xvoid freeze(), StartHuff();
  2015. X
  2016. XRETSIGTYPE giveres();
  2017. X
  2018. Xint main(argc, argv) char ** argv; {
  2019. X    argv++;
  2020. X    while (argc > 1) {
  2021. X        if (**argv == '-') {
  2022. X            while (*++(*argv) == 'g' || **argv == 'x')
  2023. X                greedy += ((**argv == 'g') << 1) - 1;
  2024. X            if (**argv)
  2025. X                goto usage;
  2026. X            argc--; argv++;
  2027. X        } else
  2028. X            break;
  2029. X    }
  2030. X    usage:
  2031. X    if(argc != 1) {
  2032. X        fprintf(stderr, "Usage: statist [-gx...] < sample_file\n");
  2033. X        fprintf(stderr, "Press INTR to display current values\n");
  2034. X        exit(0);
  2035. X    }
  2036. X    signal(SIGINT, giveres);
  2037. X
  2038. X#ifdef DOS
  2039. X    setmode(fileno(stdin), O_BINARY);       /* Oh this MS-DOS ... */
  2040. X#endif  /* DOS */
  2041. X
  2042. X    freeze();
  2043. X    giveres();
  2044. X    return 0;
  2045. X}
  2046. X
  2047. Xul_t isqrt(val)
  2048. Xul_t val;
  2049. X{
  2050. X  ul_t result = 0;
  2051. X  ul_t side = 0;
  2052. X  ul_t left = 0;
  2053. X  int digit = 0;
  2054. X  int i;
  2055. X  for (i=0; i<sizeof(ul_t)*4; i++)
  2056. X  {
  2057. X    left = (left << 2) + (val >> (sizeof(ul_t) * 8 - 2));
  2058. X    val <<= 2;
  2059. X    if (left >= side*2 + 1)
  2060. X    {
  2061. X      left -= side*2+1;
  2062. X      side = (side+1)*2;
  2063. X      result <<= 1;
  2064. X      result |= 1;
  2065. X    }
  2066. X    else
  2067. X    {
  2068. X      side *= 2;
  2069. X      result <<= 1;
  2070. X    }
  2071. X  }
  2072. X  return result;
  2073. X}
  2074. X
  2075. X
  2076. X/* Prints the (current) values of tunable parameters. Uncertainty is
  2077. Xthe number of missequencings (algorithm assumes the probabilities
  2078. Xof references decrease uniformly when distance increases). Ideally
  2079. Xit should be 0, but somewhat about 5 or less denotes the given 8 values
  2080. Xcould improve the compression rate when using them.
  2081. X*/
  2082. X
  2083. XRETSIGTYPE giveres() {
  2084. X    us_t c;
  2085. X    register int i, j, k, pr, f, average, sum;
  2086. X    ul_t cumul, sigma2;
  2087. X    short r, percent;
  2088. X    signal(SIGINT, giveres);
  2089. X    newtry:
  2090. X    StartHuff(N_POS);
  2091. X    pr = f = 0;
  2092. X    i = N_POS;
  2093. X    r = N_POS * 2 - 2;
  2094. X    while (i <= r) {
  2095. X        j = findmin(i);
  2096. X        k = findmin(i);
  2097. X        freq[i] = freq[j] + freq[k];
  2098. X        prnt[j] = prnt[k] = i++;
  2099. X    }
  2100. X
  2101. X    for (c = 1; c <= 6; c++) bits[c] = 0;
  2102. X
  2103. X    printf("Non-monotonities are in: ");
  2104. X
  2105. X    for(c = 0; c < N_POS; c++) {
  2106. X        j = 0;
  2107. X        k = c;
  2108. X        do j++; while ((k = prnt[k]) != r);
  2109. X        if (j <= 6)
  2110. X            bits[j]++;
  2111. X        if (j < pr) {
  2112. X            f += pr - j;
  2113. X            printf("%d, ", c);
  2114. X
  2115. X        } else
  2116. X            pr = j;
  2117. X    }
  2118. X    if(f == 0)
  2119. X        printf("\b\b\b\babsent.\n");
  2120. X    else
  2121. X        printf("\b\b.\n");
  2122. X
  2123. X    k = bits[1] + bits[2] + bits[3] + bits[4] +
  2124. X    bits[5] + bits[6];
  2125. X
  2126. X    k = N_POS - k;  /* free variable length codes for 7 & 8 bits */
  2127. X
  2128. X    j = 128 * bits[1] + 64 * bits[2] + 32 * bits[3] +
  2129. X    16 * bits[4] + 8 * bits[5] + 4 * bits[6];
  2130. X
  2131. X    j = 256 - j;    /* free byte images for these codes */
  2132. X
  2133. X/*      Equation:
  2134. X        bits[7] + bits[8] = k
  2135. X    2 * bits[7] + bits[8] = j
  2136. X*/
  2137. X    j -= k;
  2138. X    if (j < 0 || k < j) {
  2139. X        printf("Huffman tree has more than 8 levels, reducing...\n");
  2140. X        for (i = 0; i < N_POS; i++)
  2141. X            if (!freq[i])
  2142. X                freq[i] = 1;
  2143. X            else if (reduceflag)
  2144. X                freq[i] = (freq[i] + 1) / 2;
  2145. X        reduceflag = 1;
  2146. X        goto newtry;
  2147. X    } else {
  2148. X        bits[7] = j;
  2149. X        bits[8] = k - j;
  2150. X        printf("%d,%d,%d,%d,%d,%d,%d,%d (uncertainty = %d)\n",
  2151. X            bits[1], bits[2], bits[3], bits[4],
  2152. X            bits[5], bits[6], bits[7], bits[8], f);
  2153. X    }
  2154. X    sum = 0; cumul = 0;
  2155. X    for(i = 3; i <= LOOKAHEAD; i++) {
  2156. X        cumul += (ul_t) i * lens[i];
  2157. X        sum += lens[i];
  2158. X    }
  2159. X    sum || sum++;
  2160. X    printf("Average match length: %d.%02d\n",
  2161. X        average = cumul / sum, i = cumul * 100 / sum % 100);
  2162. X    if (i >= 50) average++;
  2163. X    j = sum;
  2164. X    percent = 0;
  2165. X    for (i = LOOKAHEAD; i >= 3; i--) {
  2166. X        static pcs[] = { 999, 995, 990, 970, 950, 900, 800, 700, 500 };
  2167. X        j -= lens[i];
  2168. X        newpcs:
  2169. X        if (j <= sum * pcs[percent] / 1000) {
  2170. X            printf("Percentile %d.%d: %d\n",
  2171. X                pcs[percent] / 10, pcs[percent] % 10, i);
  2172. X            if (percent == sizeof(pcs)/sizeof(int) - 1)
  2173. X                break;
  2174. X            else {
  2175. X                percent++;
  2176. X                goto newpcs;
  2177. X            }
  2178. X        }
  2179. X    }
  2180. X    for (sigma2 = 0, i = 3; i <= LOOKAHEAD; i++)
  2181. X        sigma2 += (ul_t)(i - average)*(i - average)*lens[i];
  2182. X    sigma2 = sigma2 * 100 / sum;
  2183. X    j = (int)isqrt(sigma2);
  2184. X    printf("Sigma: %d.%1d\n", j / 10, j % 10);
  2185. X    printf("References: %ld\n", refers);
  2186. X    fflush(stdout);
  2187. X}
  2188. X
  2189. X
  2190. Xvoid freeze ()
  2191. X{
  2192. X    register int i, len, s, c;
  2193. X    register hash_t r;
  2194. X    int match_length;
  2195. X
  2196. X    StartHuff(0);
  2197. X    InitTree();
  2198. X    r = MAXDIST + 1;
  2199. X    s = (r + LOOKAHEAD) & WINMASK;
  2200. X    for (len = 0; len < LOOKAHEAD && (c = getchar()) != EOF; len++)
  2201. X      text_buf[r + len] = c;
  2202. X
  2203. X    in_count = len;
  2204. X    for (i = r - LOOKAHEAD; i < MAXDIST; i++)
  2205. X      text_buf[i] = ' ';
  2206. X    for (i = r - LOOKAHEAD; i <= r; i++) {
  2207. X        register uc_t  *key = &text_buf[i];
  2208. X        register unsigned p = hashof(key);
  2209. X        next[i] = hashtab[p];
  2210. X        hashtab[p] = i;
  2211. X    }
  2212. X    while (len != 0) {
  2213. X        match_length = LOOKAHEAD + get_next_match(THRESHOLD - LOOKAHEAD, r);
  2214. X        if (match_length > len)
  2215. X            match_length = len;
  2216. X        if (match_length <= THRESHOLD) {
  2217. X            match_length = 1;
  2218. X        } else if (match_length >= chain_length) {
  2219. X            lens[match_length] ++;
  2220. X            update((((r - match_position) & WINMASK) - 1) >> 7);
  2221. X            refers ++;
  2222. X        } else {
  2223. X            register us_t orig_length, orig_position;
  2224. X            orig_length = match_length;
  2225. X            orig_position = match_position;
  2226. X            Next_Char(WINSIZE, LOOKAHEAD);
  2227. X            match_length = LOOKAHEAD + get_next_match(match_length - LOOKAHEAD, r);
  2228. X            if (match_length > len)
  2229. X                match_length = len;
  2230. X            if (orig_length >= match_length) {
  2231. X                lens[orig_length] ++;
  2232. X                update((((r - 1 - orig_position) & WINMASK) - 1) >> 7);
  2233. X                match_length = orig_length - 1;
  2234. X            } else  {
  2235. X                lens[match_length] ++;
  2236. X                update((((r - match_position) & WINMASK) - 1) >> 7);
  2237. X            }
  2238. X            refers ++;
  2239. X        }
  2240. X        for (i = 0; i < match_length &&
  2241. X                (c = getchar()) != EOF; i++) {
  2242. X            text_buf[s] = c;
  2243. X            if (s < LOOKAHEAD - 1)
  2244. X                text_buf[s + WINSIZE] = c;
  2245. X            s = (s + 1) & WINMASK;
  2246. X            r++;
  2247. X            InsertNode();
  2248. X        }
  2249. X        in_count += i;
  2250. X        if ((in_count > indc_count)) {
  2251. X            fprintf(stderr, "%5dK\b\b\b\b\b\b", in_count / 1024);
  2252. X            fflush (stderr);
  2253. X            indc_count += 4096;
  2254. X        }
  2255. X        while (i++ < match_length) {
  2256. X            len--;
  2257. X            r++;
  2258. X            InsertNode();
  2259. X        }
  2260. X    }
  2261. X}
  2262. X
  2263. Xvoid StartHuff(beg) {
  2264. X    int i;
  2265. X    for (i = beg; i < N_POS * 2 - 1; i++)
  2266. X        freq[i] = 0;
  2267. X    for (i = 0; i < N_POS * 2 - 1; i++)
  2268. X        used[i] = prnt[i] = 0;
  2269. X}
  2270. X
  2271. Xint findmin(range) {
  2272. X    long min = (1 << 30) - 1, argmin = -1, i;
  2273. X    for (i = 0; i < range; i++) {
  2274. X        if(!used[i] && freq[i] < min)
  2275. X            min = freq[argmin = i];
  2276. X    }
  2277. X    used[argmin] = 1;
  2278. X    return argmin;
  2279. X}
  2280. END_OF_FILE
  2281.   if test 6374 -ne `wc -c <'statist.c'`; then
  2282.     echo shar: \"'statist.c'\" unpacked with wrong size!
  2283.   fi
  2284.   # end of 'statist.c'
  2285. fi
  2286. echo shar: End of archive 2 \(of 3\).
  2287. cp /dev/null ark2isdone
  2288. MISSING=""
  2289. for I in 1 2 3 ; do
  2290.     if test ! -f ark${I}isdone ; then
  2291.     MISSING="${MISSING} ${I}"
  2292.     fi
  2293. done
  2294. if test "${MISSING}" = "" ; then
  2295.     echo You have unpacked all 3 archives.
  2296.     rm -f ark[1-9]isdone
  2297. else
  2298.     echo You still must unpack the following archives:
  2299.     echo "        " ${MISSING}
  2300. fi
  2301. exit 0
  2302. exit 0 # Just in case...
  2303.