Subject: v24i075: Public-domain replacement for compress programs, Part03/04 Newsgroups: comp.sources.unix Approved: rsalz@uunet.UU.NET X-Checksum-Snefru: db10e3bf d4d49c41 27b2b1fb b1ebd740 Submitted-by: Dan Bernstein Posting-number: Volume 24, Issue 75 Archive-name: yabbawhap/part03 #! /bin/sh # This is a shell archive. Remove anything before this line, then feed it # into a shell via "sh file" or similar. To overwrite existing files, # type "sh file -c". # The tool that generated this appeared in the comp.sources.unix newsgroup; # send mail to comp-sources-unix@uunet.uu.net if you want that tool. # Contents: BLURB CHANGES INSTALL PATENTS QUESTIONS bitout.c huptrie.h # percent.c sysconf texts.c unwhap.c unyabba.1 yabba.1 # Wrapped by rsalz@litchi.bbn.com on Wed Mar 20 17:09:24 1991 PATH=/bin:/usr/bin:/usr/ucb ; export PATH echo If this archive is complete, you will see the following message: echo ' "shar: End of archive 3 (of 4)."' if test -f 'BLURB' -a "${1}" != "-c" ; then echo shar: Will not clobber existing file \"'BLURB'\" else echo shar: Extracting \"'BLURB'\" \(1000 characters\) sed "s/^X//" >'BLURB' <<'END_OF_FILE' XThis package includes yabba and unyabba, portable implementations of Y Xcoding. Y coding is unpatented---unlike the LZW coding used by compress Xand the LZ78 variants used by most other dictionary compressors. Y also Xgives somewhat better compression than LZW. X XAs an extra bonus, this package also includes whap and unwhap, portable Ximplementations of AP coding. AP coding is patented, but like Y it is Xmore effective than LZW. whap runs about as fast as compress and, in its Xdefault configuration, uses less memory; unwhap runs as fast as Xuncompress and uses less than half as much memory. X XThe entire package is public-domain. You can copy my Y code into any Xapplication without fear of copyrights or patents. Be aware, however, Xthat the current implementation is probably not too close to optimal, Xand I am actively searching for a better method. If AP were not patented XI would recommend that you use it instead. For more information see XPATENTS in the package. X X---Dan Bernstein, brnstnd@nyu.edu END_OF_FILE if test 1000 -ne `wc -c <'BLURB'`; then echo shar: \"'BLURB'\" unpacked with wrong size! fi # end of 'BLURB' fi if test -f 'CHANGES' -a "${1}" != "-c" ; then echo shar: Will not clobber existing file \"'CHANGES'\" else echo shar: Extracting \"'CHANGES'\" \(2782 characters\) sed "s/^X//" >'CHANGES' <<'END_OF_FILE' Xyabbawhap change file, in reverse chronological order X XEF is Eirik Fuller . XDG is Dave Gudeman . XMA is Marc Andreessen . XLR is Loren J. Rittle . XCP is Colin Plumb . XFW is Frank Wales . XGT is Graham Thoal . X X3/19/91: yabbawhap 1.00. X3/19/91: Cleaned up for 1.00 release. Hopefully no further changes. X3/19/91: Changed >> 4 to / 16 to handle longs. Tnx GT. X3/19/91: Added ycoding.4b, latest revision of paper. X3/19/91: No major changes in a while, release seems appropriate. X X3/14/91: Fixed up various other %d and %ld's. Tnx GT. X3/14/91: Changed %d to %ld for per. Tnx GT. X3/14/91: Fixed 9999% to 9999%%. (Will this ever matter?) Tnx GT. X X3/13/91: Had OPTCANT2 and OPTCANT1 affect DOWNI. I don't like this... X3/13/91: Replaced DOWN2 with DOWNI (``down inner'') in yw.c, unyabba.c. X3/13/91: Added -s to ls in try, tryap. X3/13/91: Noted try* changes in README. X3/13/91: Removed -L from ls's in try*. Tnx FW. X3/13/91: Removed test -s stuff from try*. csh's too incompatible. Tnx FW. X3/13/91: Changed .memset.$$.* to .mmset.$$.* in sysconf. Tnx FW. X3/13/91: Added space before comment line 25 huptrie.h. Tnx FW. X Microsoft SCO compiler reports error on int */*comment*/. Dorks. X X3/6/91: yabbawhap 0.981. X3/6/91: Took out test code from yw.c. Aargh. X X3/6/91: yabbawhap 0.98. X3/6/91: Fixed up .h dependencies in Makefile. X X2/27/91: Added HASHPTRS to huptrie.h. Only visible change is tophash(). X2/27/91: Fixed up ADDAVAIL, INIT, and extra hc parens, just in case. Tnx CP. X2/27/91: Noted in Makefile and QUESTIONS that HASHTYPE does affect memory. X2/27/91: Changed initial ADDs in yw.c to use curhash as a temporary. X2/25/91: Added QUESTIONS. X X2/20/91: Fixed unsigned long return in percent.c. Tnx LR. X2/20/91: Fixed goaheadandbeverbose() and initrandom() to void returns. Tnx LR. X2/20/91: Changed unwhap logic slightly. X2/19/91: Changed sysconf to automatically run checkconf if the user wants. X2/19/91: Added warning in README about ZEROFILLED. X2/19/91: Added warning in README about changing -m. Tnx DG. X2/19/91: Changed to -UZEROFILLED as the default; sysconf sets -DZEROFILLED. X2/19/91: Changed whap to unwhap in unyabba man page. Tnx MA. X2/19/91: Changed tryap and tryapy to interact better with whapwarning. Tnx DG. X2/19/91: Fixed up non-use of BRAINDAMAGED in un*. X2/19/91: Added DOWN1, DOWN0, OPTCANT2, OPTCANT1. X2/18/91: Changed BRAINDAMAGED test slightly for Utek and similar. Tnx EF. X2/18/91: Fixed up sysconf's BRAINDAMAGED test. Oops. Tnx EF. X2/18/91: Added notice about checkconf to the end of sysconf. X2/18/91: Changed sysconf to use cat << instead of echo. I hate System V. X X2/17/91: yabbawhap 0.95. END_OF_FILE if test 2782 -ne `wc -c <'CHANGES'`; then echo shar: \"'CHANGES'\" unpacked with wrong size! fi # end of 'CHANGES' fi if test -f 'INSTALL' -a "${1}" != "-c" ; then echo shar: Will not clobber existing file \"'INSTALL'\" else echo shar: Extracting \"'INSTALL'\" \(1302 characters\) sed "s/^X//" >'INSTALL' <<'END_OF_FILE' X#!/bin/sh X# Public domain. X XMODE=0755 X XYABBA=/usr/local/bin/yabba XUNYABBA=/usr/local/bin/unyabba XWHAP=/usr/local/bin/whap XUNWHAP=/usr/local/bin/unwhap X XMYABBA=/usr/man/man1/yabba.1 XMUNYABBA=/usr/man/man1/unyabba.1 X Xecho "Each action will be printed before it is run. Press return to proceed." Xecho "Note that you need a BSD-compatible install program or script." X Xecho "1. Install yabba and unyabba." Xecho "! install -c -m $MODE yabba $YABBA: " | tr -d '\012' Xread line Xinstall -c -m "$MODE" yabba "$YABBA" X Xecho "! install -c -m $MODE unyabba $UNYABBA: " | tr -d '\012' Xread line Xinstall -c -m "$MODE" unyabba "$UNYABBA" X Xecho "2. Install whap and unwhap." Xif test -r whap -a -r unwhap Xthen echo "! install -c -m $MODE whap $WHAP: " | tr -d '\012' X read line X install -c -m "$MODE" whap "$WHAP" X X echo "! install -c -m $MODE unwhap $UNWHAP: " | tr -d '\012' X read line X install -c -m "$MODE" unwhap "$UNWHAP" X Xelse echo "Looks like you don't have whap compiled. Fine, let's continue." Xfi X Xecho "3. Make the man pages available." Xecho "! install -c -m 0444 yabba.1 $MYABBA: " | tr -d '\012' Xread line Xinstall -c -m 0444 yabba.1 "$MYABBA" X Xecho "! install -c -m 0444 unyabba.1 $MUNYABBA: " | tr -d '\012' Xread line Xinstall -c -m 0444 unyabba.1 "$MUNYABBA" X Xecho "That's it!" X Xexit 0 END_OF_FILE if test 1302 -ne `wc -c <'INSTALL'`; then echo shar: \"'INSTALL'\" unpacked with wrong size! fi chmod +x 'INSTALL' # end of 'INSTALL' fi if test -f 'PATENTS' -a "${1}" != "-c" ; then echo shar: Will not clobber existing file \"'PATENTS'\" else echo shar: Extracting \"'PATENTS'\" \(4266 characters\) sed "s/^X//" >'PATENTS' <<'END_OF_FILE' XAfter someone patents a product or method that he invented, he can sue Xanyone who makes, uses, or sells the invention. You've probably heard Xthat Welch at Unisys patented LZW compression some years back, and so XUnisys can sue anyone who uses UNIX compress or any similar program. XYou may not have heard that Miller and Wegman at IBM independently Xdiscovered several compression methods, including LZW---and sent their Xpatent application to the Patent & Trademark Office before Welch did. XSo it appears that IBM controls LZW. X XHow can Unisys patent something that IBM already patented? And how can Xeither of them patent what are obviously mathematical algorithms, when Xmathematical algorithms aren't supposed to be patentable? The answer is Xthat the Patent & Trademark Office doesn't let mathematicians and Xcomputer scientists become patent examiners. So none of their examiners Xcan recognize mathematics without a court order, and even then they have Xtrouble. They also can't tell that two patents cover exactly the same Xalgorithm when the wording is slightly different. X XPractically every good compression method in the last ten years has been Xpatented. Modem and disk manufacturers can't ignore the possibility of Xgovernment-approved monopolies on compressors: there's too much money at Xstake. So they apply for one patent after another, twisting the wording Xas much as possible so that the patent examiners don't realize they're Xpatenting mathematics. By and large, they succeed. X XOn December 26, 1990, I discovered an apparently new compression method, XY coding. I haven't found a way to make Y run as fast as compress (yet), Xbut it's not too slow for general use, and it produces better results Xoverall than any other non-Huffman dictionary compressor I've seen. I am Xsick and tired of having to tiptoe through this minefield of patents; I Xwant a method that produces good results and can be used freely by Xanyone. Well, now I have it. Everything in Y coding is public domain. No Xcopyrights, no patents, no protection at all, on the code or on the Xalgorithms or on the file format or on anything else. I can't be totally Xsure, of course, that I'm the first to discover Y, but everyone I've Xtalked to thinks it's new. Use it as you will. X XSeveral months before I found Y coding, I found what I now know to be XStorer's AP coding. At first I thought it was new, and I started putting Xtogether an implementation. It's quite a bit faster than my Y Ximplementation---even faster than compress on some machines---and uses Xless memory. But it has turned out to be patented. I've included the Xcode in my Y package because I don't want my work to go to waste, but it Xcan't be used freely. You can use AP for what's sometimes called X``experimental use''; the precise wording in most court cases is ``for Xthe sole purpose of satisfying philosophical taste or curiosity, or for Xinstruction and amusement.'' Patents never apply to that sort of use. X XIf you like AP's efficiency and want to start using it for more than Xsatisfying your philosophical curiosity, you might be tempted to ask XStorer for a license. Don't give in! First, his patent---any compression Xpatent---is on very shaky ground, and as it hasn't been acknowledged in Xthe industry, it's even weaker. Second, you can challenge the patent by Xsending the Patent & Trademark Office about $2000 and an explanation of Xwhy AP is a mathematical algorithm. Now you may not have the money or Xlawyers or time or energy to do this successfully, but there are a lot Xof people who feel just as restricted. You should check up on the League Xfor Programming Freedom; if you don't subscribe to their political goals Xbut still want to get rid of compression patents, send me a note. In any Xcase this will be cheaper on everyone than paying Storer for something Xhe shouldn't even control. Third, Y isn't that much slower than AP, and Xit compresses just as effectively. Chances are good that I or someone Xelse will find a faster implementation soon. Finally, we may be able to Xconvince Storer to donate his patent to the public good. If you want to Xappeal to his morals, send a note to storer@cs.brandeis.edu, copy to Xbrnstnd@nyu.edu. X XDisclaimer: I'm not a lawyer. I'm just an outraged citizen. X X---Dan Bernstein, brnstnd@nyu.edu END_OF_FILE if test 4266 -ne `wc -c <'PATENTS'`; then echo shar: \"'PATENTS'\" unpacked with wrong size! fi # end of 'PATENTS' fi if test -f 'QUESTIONS' -a "${1}" != "-c" ; then echo shar: Will not clobber existing file \"'QUESTIONS'\" else echo shar: Extracting \"'QUESTIONS'\" \(3130 characters\) sed "s/^X//" >'QUESTIONS' <<'END_OF_FILE' X1. Aack! It won't compile! It doesn't work! What do I do? X2. Why do yabba and whap use so much memory? X3. Why does squeeze do better than yabba and whap on long files? X4. What does ``block size'' mean? X5. Why doesn't yabba take a filename argument? X6. When will there be a new version of yabbawhap? X X X1. Aack! It won't compile! It doesn't work! What do I do? X XRead through README, Makefile, and QUESTIONS. Make checkconf, run it, Xand read carefully through its output. Then try again. If you still have Xtrouble, send the author a note at brnstnd@nyu.edu. X X X2. Why do yabba and whap use so much memory? X XWith -UPTRS -DTYPE=short you will typically use half as much memory on a X32-bit machine. With -DHASHTYPE=short you will save some more memory for Xyabba and unyabba, though not for whap or unwhap. These changes usually Xcost a bit of speed. See Makefile for more details. X XYou can also change the block size by changing NODEMAX and MOD. These Xdon't really affect speed, but they do affect compression. With them you Xcan make yabba and whap use as much or as little memory as you like. X X X3. Why does squeeze do better than yabba and whap on long files? X XBy default, yabba and whap are compiled to use similar amounts of memory Xto compress. squeeze uses a lot more memory, so it can keep track of Xmore patterns in the input. If you compile yabba and whap with NODEMAX Xand MOD so high that they use as much memory, they'll do better than Xsqueeze. X XFor example, on a 97338-byte shell archive, yabba -m65533 compresses to X39266 bytes, and whap -m65533 compresses to 37358 bytes. yabba -m100000 Xcompresses to 36673 bytes, and whap -m100000 compresses to 33566 bytes. X(In contrast, compress produces 43322 bytes, squeeze produces 33943 Xbytes, and lharc produces 32455 bytes. A Huffman coder layered on top of Xyabba or whap would produce even better results.) X XThere are occasional files where squeeze performs better than yabba and Xwhap no matter how much memory you use, but never by much. X X X4. What does ``block size'' mean? X XThe number after -m represents a number of input characters. -m100000 Xmeans that yabba (or whap) will try to find patterns in a stretch of Xinput up to 100000 characters long. NODEMAX and NODENUM are on the same Xscale. Here 100000 is the block size. In the above example with a X97338-byte file, any -m value above 97338 will produce the same results. X X(For compress, the natural block size is the number of patterns it is Xkeeping track of at once, not the number of input characters. With -b14, Xcompress will keep track of 2^14 or 16384 patterns at once. Typically X16384 patterns would stretch over 60000 input characters. -b16 is Xroughly equivalent to -m300000.) X X X5. Why doesn't yabba take a filename argument? X XWait for the -f option. Separate programs, fyabba and funyabba, will Xapply yabba and unyabba to files; fyabbadir and funyabbadir will work on Xdirectory hierarchies. X X X6. When will there be a new version of yabbawhap? X XI am actively working on the next release; I have targeted version 1.50 Xwith most of the planned extensions for May 1. Send any suggestions or Xpatches to me at brnstnd@nyu.edu. END_OF_FILE if test 3130 -ne `wc -c <'QUESTIONS'`; then echo shar: \"'QUESTIONS'\" unpacked with wrong size! fi # end of 'QUESTIONS' fi if test -f 'bitout.c' -a "${1}" != "-c" ; then echo shar: Will not clobber existing file \"'bitout.c'\" else echo shar: Extracting \"'bitout.c'\" \(2064 characters\) sed "s/^X//" >'bitout.c' <<'END_OF_FILE' X/* Placed into the public domain by Daniel J. Bernstein. */ X X#include X#include "bitout.h" X Xstatic int twom1[9] = { 0,1,3,7,15,31,63,127,255 } ; X Xbitword bit_wbuf[BITBUFSIZE + 1]; Xbitnum bit_bbuf[BITBUFSIZE + 1]; Xint bit_bufsize = 0; X Xlong bit_numout = 0; X Xstatic int savecurbyte = 0; Xstatic bitnum savecurbb8 = 8; X Xint bit_printbuf() X{ X register int curbyte = savecurbyte; X register bitnum curbb8 = savecurbb8; X register bitword curw; X register int i; X X /* XXX: should use registers & curbyte & so on better */ X X for (i = 0;i < bit_bufsize;i++) X { X /* assumes bit_bbuf[i] <= 0 */ X curw = bit_wbuf[i]; X curbyte += ((curw & twom1[curbb8]) << (8 - curbb8)); X#ifdef BRAINDAMAGED X if (curbyte == 255) X (void) putchar((char) curbyte); X else X#endif X if (putchar((char) curbyte) == EOF) X return EOF; X bit_numout++; X curw >>= curbb8; X curbb8 += bit_bbuf[i]; X X /* just in case bit_bbuf[i] < -7 */ X while (curbb8 <= 0) X { X#ifdef BRAINDAMAGED X if (curw & 255 == 255) X (void) putchar((char) (curw & 255)); X else X#endif X if (putchar((char) (curw & 255)) == EOF) X return EOF; X bit_numout++; X curbb8 += 8; X curw >>= 8; X } X curbyte = (int) curw; /* does not lose accuracy */ X } X savecurbyte = curbyte; /* ah, the joy of coroutines */ X savecurbb8 = curbb8; /* better this way (double vars) for efficiency */ X bit_bufsize = 0; X return 0; X} X Xint bit_flushbuf() X{ X if (bit_printbuf() == EOF) X return EOF; X if (savecurbb8 < 8) X { X#ifdef BRAINDAMAGED X if (savecurbyte == 255) X (void) putchar((char) savecurbyte); X else X#endif X if (putchar((char) savecurbyte) == EOF) X return EOF; X bit_numout++; X } X savecurbyte = 0; X savecurbb8 = 8; X return 0; X} X Xint bit_fillflush(x) Xint x; X{ X if (bit_printbuf() == EOF) X return EOF; X savecurbyte += (x << 8 - savecurbb8) & 255; X#ifdef BRAINDAMAGED X if (savecurbyte == 255) X (void) putchar((char) savecurbyte); X else X#endif X if (putchar((char) savecurbyte) == EOF) X return EOF; X bit_numout++; X savecurbyte = 0; X savecurbb8 = 8; X return 0; X} END_OF_FILE if test 2064 -ne `wc -c <'bitout.c'`; then echo shar: \"'bitout.c'\" unpacked with wrong size! fi # end of 'bitout.c' fi if test -f 'huptrie.h' -a "${1}" != "-c" ; then echo shar: Will not clobber existing file \"'huptrie.h'\" else echo shar: Extracting \"'huptrie.h'\" \(7295 characters\) sed "s/^X//" >'huptrie.h' <<'END_OF_FILE' X/* Placed into the public domain by Daniel J. Bernstein. */ X X#ifndef HUPTRIE_H X#define HUPTRIE_H X X/* Ever seen an efficient data structure library? You're about to. */ X X/* Yes, folks, I have some documentation for this; I'm just not sure */ X/* that the library is ready for general release yet. If you're */ X/* desperate for huptries in an application and *need* to use this */ X/* library *now*, let me know. */ X X/*#defines: PTRS, TYPE, HASHTYPE, ZEROFILLED, BZERO, MEMZERO, OPTCANT{1,2,5}.*/ X/* HASHPTRS. */ X X#ifndef HASHTYPE X#define HASHTYPE TYPE X#endif X Xtypedef unsigned TYPE pos; X X#ifdef PTRS Xtypedef struct nod { struct nod *p; struct nod *n; } *node; Xtypedef struct nod *next; Xtypedef int * /*XXX: irrelevant*/ parent; X#else Xtypedef pos node; Xtypedef node *next; Xtypedef node *parent; X#endif X X#ifdef HASHPTRS Xtypedef struct hod { node n; struct hod *h; } htt; Xtypedef struct hod *hash; X#define HASHP 255 X#define HANO(h,sh) ((sh)->n) X#else Xtypedef node htt; Xtypedef unsigned HASHTYPE hash; X#define HASHP 0 X#define HANO(h,sh) ((h)[sh]) X#endif X Xtypedef htt *hashtable; Xtypedef pos ipos; X X/* A huptrie consists of: X next n; parent p; hashtable h; X ipos m; pos sm; pos l1; hash h1; X*/ X X#define TOPHASH 5381 X X#ifdef HASHPTRS X#define hh(sh,sch,h1) (please do not use this yet, XXX) X#define hc(sh,c,h1) (sh[(unsigned char) c].h) X#else X#define hh(sh,sch,h1) (((sch) - (((sh) << 5) + (sh))) & (h1)) X#define hc(sh,c,h1) ((((sh) << 5) + (sh) + ((hash) (unsigned char) (c))) & (h1)) X#endif X X#ifdef PTRS X#define NEXT(ne,no) ((no)->n) X#define PARENT(pa,no) ((no)->p) X#define AVAIL(ne) ((ne)[0].n) X#define NODEBYN(ne,po) ((ne) + (po)) X#else X#define NEXT(ne,no) ((ne)[no]) X#define PARENT(pa,no) ((pa)[no]) X#define AVAIL(ne) ((ne)[0]) X#define NODEBYN(ne,po) (po) X#endif X X/* INIT, HUP_DELETE, DOWN are block statements. */ X X/* n,p,h,m,sm are by address */ X#ifdef PTRS X#define INIT(n,p,h,m,sm,l1,h1) \ X{ (n) = malloc(sizeof(struct nod) * ((l1) + 1)); AVAIL(n) = 0; \ X (h) = (hashtable) malloc(sizeof(htt) * ((h1) + HASHP + 1)); \ X CLEARHASH(h,h1); FIRSTHASH(h,h1); (m) = (l1) + 1; (sm) = -1; } X#define STATICDECLARE(n,p,h,l1,h1) \ X struct nod (n)[(l1) + 1]; parent (p); htt (h)[(h1) + HASHP + 1]; X#else X#define INIT(n,p,h,m,sm,l1,h1) \ X{ (n) = (next) malloc(sizeof(node) * ((l1) + 1)); AVAIL(n) = 0; \ X (p) = (parent) malloc(sizeof(node) * ((l1) + 1)); \ X (h) = (hashtable) malloc(sizeof(htt) * ((h1) + HASHP + 1)); \ X CLEARHASH(h,h1); FIRSTHASH(h,h1); (m) = (l1) + 1; (sm) = -1; } X#define STATICDECLARE(n,p,h,l1,h1) \ X node (n)[(l1) + 1]; node (p)[(l1) + 1]; htt (h)[(h1) + HASHP + 1]; X#endif X X#define STATICINIT(n,p,h,m,sm,l1,h1) \ X{ INITHASH(h,h1); AVAIL(n) = 0; (m) = (l1) + 1; (sm) = -1; } X/* FIRSTHASH(h,h1) XXX*/ X X#ifdef HASHPTRS X#define FIRSTHASH(h,h1) { hash ha; ha = (h) + ((h1) + HASHP + 1); \ Xdo { --ha; ha->h = (h) + ((((ha - h) << 5) + (ha - h)) & (h1)); } \ Xwhile (ha != (h)); } X#else X#define FIRSTHASH(h,h1) ; X#endif X X#ifdef ZEROFILLED X#define INITHASH(h,h1) ; X#else X#define INITHASH(h,h1) CLEARHASH(h,h1); X#endif X X#ifdef HASHPTRS X#define CLEARHASH(h,h1) { hash ha; ha = (h) + ((h1) + 1); do HANO(h,--ha) = 0; while (ha != (h)); } X/* XXX: if -UZEROFILLED, this is unnecessarily inefficient on the first CLEARHASH */ X#else X#ifdef BZERO X#define CLEARHASH(h,h1) (void) bzero((char *) (h),sizeof(node) * ((h1) + 1)); X#else X#ifdef MEMZERO X#define CLEARHASH(h,h1) (void) memset((char *) (h),0,sizeof(node) * ((h1) + 1)); X#else X#define CLEARHASH(h,h1) { hash ha; ha = (h1) + 1; do HANO(h,--ha) = 0; while (ha); } X#endif X#endif X#endif X X X/* sm and newnode are by address */ X#define ADDAVAIL(n,p,h,sm,sp,sch,newnode) \ X( --(sm), (newnode = AVAIL(n)), (AVAIL(n) = NEXT(n,newnode)), \ X (PARENT(p,newnode) = (sp)), \ X (NEXT(n,newnode) = HANO(h,sch)), (HANO(h,sch) = (newnode)) ) X X/* m, sm, newnode are by address */ X#define WASTEMAX(n,p,h,m,sm,newnode) \ X( (++(sm)), (newnode = NODEBYN(n,--(m))), (PARENT(p,newnode) = 0), \ X (NEXT(n,newnode) = AVAIL(n)), (AVAIL(n) = (newnode)) ) X X/* m and newnode are by address */ X#define ADDMAX(n,p,h,m,sp,sch,newnode) \ X( (newnode = NODEBYN(n,--(m))), (PARENT(p,newnode) = (sp)), \ X (NEXT(n,newnode) = HANO(h,sch)), (HANO(h,sch) = (newnode)) ) X X/* sm and noptr are by address */ X#define HUP_DELETE(n,p,h,sm,sp,sh,noptr) \ X{ (noptr) = &(HANO(h,sh)); while (*(noptr) != (sp)) (noptr) = &(NEXT(n,*(noptr))); \ X *(noptr) = NEXT(n,sp); PARENT(p,sp) = 0; NEXT(n,sp) = AVAIL(n); \ X AVAIL(n) = (sp); ++(sm); } X X/* no is by address, FOUND and NOTFOUND are formal */ X/* XXX: Reorganize hash lists? */ X#define DOWN2(n,p,h,sp,sch,no,FOUND,NOTFOUND) { \ X if ((no) = HANO(h,sch)) { if (PARENT(p,no) != (sp)) { \ X if ((no) = NEXT(n,no)) { if (PARENT(p,no) != (sp)) { \ X if ((no) = NEXT(n,no)) { if (PARENT(p,no) != (sp)) { \ X do (no) = NEXT(n,no); while ((no) && (PARENT(p,no) != (sp))); \ X if (no) { FOUND } else { NOTFOUND } \ X } else { FOUND } } else { NOTFOUND } \ X } else { FOUND } } else { NOTFOUND } \ X } else { FOUND } } else { NOTFOUND } \ X} X X#define DOWN1(n,p,h,sp,sch,no,FOUND,NOTFOUND) { \ X if ((no) = HANO(h,sch)) { if (PARENT(p,no) != (sp)) { \ X if ((no) = NEXT(n,no)) { if (PARENT(p,no) != (sp)) { \ X do (no) = NEXT(n,no); while ((no) && (PARENT(p,no) != (sp))); \ X if (no) { FOUND } else { NOTFOUND } \ X } else { FOUND } } else { NOTFOUND } \ X } else { FOUND } } else { NOTFOUND } \ X} X X#define DOWN0(n,p,h,sp,sch,no,FOUND,NOTFOUND) { \ X if ((no) = HANO(h,sch)) { if (PARENT(p,no) != (sp)) { \ X do (no) = NEXT(n,no); while ((no) && (PARENT(p,no) != (sp))); \ X if (no) { FOUND } else { NOTFOUND } \ X } else { FOUND } } else { NOTFOUND } \ X} X X#define DOWN5(n,p,h,sp,sch,no,FOUND,NOTFOUND) { \ X if ((no) = HANO(h,sch)) { if (PARENT(p,no) != (sp)) { \ X if ((no) = NEXT(n,no)) { if (PARENT(p,no) != (sp)) { \ X if ((no) = NEXT(n,no)) { if (PARENT(p,no) != (sp)) { \ X if ((no) = NEXT(n,no)) { if (PARENT(p,no) != (sp)) { \ X if ((no) = NEXT(n,no)) { if (PARENT(p,no) != (sp)) { \ X if ((no) = NEXT(n,no)) { if (PARENT(p,no) != (sp)) { \ X do (no) = NEXT(n,no); while ((no) && (PARENT(p,no) != (sp))); \ X if (no) { FOUND } else { NOTFOUND } \ X } else { FOUND } } else { NOTFOUND } \ X } else { FOUND } } else { NOTFOUND } \ X } else { FOUND } } else { NOTFOUND } \ X } else { FOUND } } else { NOTFOUND } \ X } else { FOUND } } else { NOTFOUND } \ X } else { FOUND } } else { NOTFOUND } \ X} X X#ifdef OPTCANT1 X#define DOWN DOWN0 X#define DOWNI DOWN0 X#else X#ifdef OPTCANT2 X#define DOWN DOWN1 X#define DOWNI DOWN1 X#else X#ifdef OPTCANT5 X#define DOWN DOWN2 X#define DOWNI DOWN2 X#else X#define DOWN DOWN5 X#define DOWNI DOWN2 X#endif X#endif X#endif X X#define hup_parent(p,no) PARENT(p,no) X#define setparent(p,scp,sp) (PARENT(p,scp) = (sp)) X#ifdef HASHPTRS X#define tophash(h,h1) ((h) + (TOPHASH & (h1))) X#else X#define tophash(h,h1) (TOPHASH & (h1)) X#endif X#define topnode(n,l1) (NODEBYN(n,(l1) + 1)) X#define Hmax(m,l1) ((l1) - (m)) X#define size(m,sm,l1) (((l1) - (m)) - (sm)) X#define limitm1(l1) (l1) X#define ipos2pos(n,ip,l1) ((l1) - (ip)) X#define pos2ipos(n,po,l1) ((l1) - (po)) X X#ifdef PTRS X#define node2pos(n,no,l1) ((l1) - ((no) - (n))) X#define node2ipos(n,no,l1) ((no) - (n)) X#else X#define node2pos(n,no,l1) ((l1) - (no)) X#define node2ipos(n,no,l1) (no) X#endif X X#define ipos2node(n,ip,l1) (NODEBYN(n,ip)) X#define pos2node(n,po,l1) (NODEBYN(n,(l1) - (po))) X X#endif END_OF_FILE if test 7295 -ne `wc -c <'huptrie.h'`; then echo shar: \"'huptrie.h'\" unpacked with wrong size! fi # end of 'huptrie.h' fi if test -f 'percent.c' -a "${1}" != "-c" ; then echo shar: Will not clobber existing file \"'percent.c'\" else echo shar: Extracting \"'percent.c'\" \(2070 characters\) sed "s/^X//" >'percent.c' <<'END_OF_FILE' X/* Placed into the public domain by Daniel J. Bernstein. */ X X#include "percent.h" X X#define MAXULONG ((unsigned long) (-1)) X X#define HENCE(x) ; X X#define ENOUGH(a) { long p = (a); if (q) { \ Xif (q - 1 > limit / 100) return limit; \ Xif ((q - 1) * 100 > limit - 100) return limit; \ Xif (q * 100 > limit - p) return limit; \ Xreturn (long) (p + q*100); } else if (p > limit) return limit; else return p; } X Xlong percent(a,b,limit) Xunsigned long a; Xunsigned long b; Xlong limit; X{ X unsigned long q; X unsigned long s; X unsigned long t; X X q = 0; X X if (b == 0) X ENOUGH(100) X HENCE(b > 0); X X if (b < MAXULONG - 200) X if (a < (MAXULONG / 200) - (b / 200) - 1) /* cannot go below 0 */ X ENOUGH((100 * a + (b / 2)) / b) /* cannot overflow */ X HENCE(a + (b / 200) + 1 >= MAXULONG / 200); X /* How often will a and b be more than 21 million on a 32-bit machine? */ X X if (a < b / 200) X ENOUGH(0) X HENCE(a >= b / 200); X HENCE(a + a + 1 >= MAXULONG / 200); X X if (a >= b) X { X q = a / b; X HENCE(a - q * b < b); X a -= q * b; X } X HENCE(a < b); X X t = 0; s = a; X /* now s is a mod b, t is floor(a/b) */ X if (s >= b - a) { t += 1; s -= b - a; } else { s += a; } X /* now s is 2a mod b, t is floor(2a/b) */ X if (s >= b - a) { t += 1; s -= b - a; } else { s += a; } X /* now s is 3a mod b, t is floor(3a/b) */ X if (s >= b - s) { t += t + 1; s -= b - s; } else { t += t; s += s; } X /* now s is 6a mod b, t is floor(6a/b) */ X if (s >= b - s) { t += t + 1; s -= b - s; } else { t += t; s += s; } X /* now s is 12a mod b, t is floor(12a/b) */ X if (s >= b - s) { t += t + 1; s -= b - s; } else { t += t; s += s; } X /* now s is 24a mod b, t is floor(24a/b) */ X if (s >= b - a) { t += 1; s -= b - a; } else { s += a; } X /* now s is 25a mod b, t is floor(25a/b) */ X if (s >= b - s) { t += t + 1; s -= b - s; } else { t += t; s += s; } X /* now s is 50a mod b, t is floor(50a/b) */ X if (s >= b - s) { t += t + 1; s -= b - s; } else { t += t; s += s; } X /* now s is 100a mod b, t is floor(100a/b) */ X if (s >= b - (b/2)) { t += 1; s -= b - (b/2); } else { s += (b/2); } X X ENOUGH(t) X /* whew. */ X} END_OF_FILE if test 2070 -ne `wc -c <'percent.c'`; then echo shar: \"'percent.c'\" unpacked with wrong size! fi # end of 'percent.c' fi if test -f 'sysconf' -a "${1}" != "-c" ; then echo shar: Will not clobber existing file \"'sysconf'\" else echo shar: Extracting \"'sysconf'\" \(4852 characters\) sed "s/^X//" >'sysconf' <<'END_OF_FILE' X#!/bin/sh X# Public domain. X X# Configure, eat your heart out. X X# make sure we're using sh (stolen from Configure) XPATH='.:/bin:/usr/bin:/usr/local/bin:/usr/ucb:/usr/local:/usr/lbin:/etc' Xexport PATH || (echo "Aargh! This isn't sh. Desperation time. I will now feed myself to sh..."; exec sh $0; sh $0; kill $$) Xecho "We're using sh. Good." X X# make sure cmp works Xif cmp README README >/dev/null 2>&1 Xthen if cmp README FORMLETTER >/dev/null 2>&1 X then echo 'Aargh! cmp returns a zero exit code for different files. This is hopeless.' X exit 1 X else echo 'You have a normal cmp. Good.' X fi Xelse echo 'Aargh! cmp returns a nonzero exit code for the same file. This is hopeless.' X exit 1 Xfi X X# test for bzero() Xcat > .bzero.$$.c << 'YOW' Xextern bzero(); main() { char c = 1; bzero(&c,1); printf("%d\n",c); } XYOW Xif cc -o .bzero.$$ .bzero.$$.c >/dev/null 2>&1 Xthen ./.bzero.$$ > .bzero.$$.out X echo 0 > .zero.$$.out X if cmp .zero.$$.out .bzero.$$.out >/dev/null 2>&1 X then echo 'You have bzero(). Enabling it...' X sed '2s/$/ -DBZERO/' < Makefile | sed '2s/-UBZERO /-DBZERO /g' | sed '2s/-DBZERO\(.*\) -DBZERO$/-DBZERO\1/' > Makefile.new X mv Makefile.new Makefile X else echo 'You seem to have bzero(), but it doesn'\''t work. Disabling it...' X sed '2s/$/ -UBZERO/' < Makefile | sed '2s/-DBZERO /-UBZERO /g' | sed '2s/-UBZERO\(.*\) -UBZERO$/-UBZERO\1/' > Makefile.new X mv Makefile.new Makefile X fi Xelse echo 'You do not have bzero(). Disabling it...' X sed '2s/$/ -UBZERO/' < Makefile | sed '2s/-DBZERO /-UBZERO /g' | sed '2s/-UBZERO\(.*\) -UBZERO$/-UBZERO\1/' > Makefile.new X mv Makefile.new Makefile Xfi Xrm -f .bzero.$$ .bzero.$$.out .bzero.$$.c .zero.$$.out X X# test for memset() Xcat > .mmset.$$.c << 'YOW' Xextern memset(); main() { char c = 1; memset(&c,0,1); printf("%d\n",c); } XYOW Xif cc -o .mmset.$$ .mmset.$$.c >/dev/null 2>&1 Xthen ./.mmset.$$ > .mmset.$$.out X echo 0 > .zero.$$.out X if cmp .zero.$$.out .mmset.$$.out >/dev/null 2>&1 X then echo 'You have memset(). Enabling it...' X sed '2s/$/ -DMEMZERO/' < Makefile | sed '2s/-UMEMZERO /-DMEMZERO /g' | sed '2s/-DMEMZERO\(.*\) -DMEMZERO$/-DMEMZERO\1/' > Makefile.new X mv Makefile.new Makefile X else echo 'You seem to have memset(), but it doesn'\''t work. Disabling it...' X sed '2s/$/ -UMEMZERO/' < Makefile | sed '2s/-DMEMZERO /-UMEMZERO /g' | sed '2s/-UMEMZERO\(.*\) -UMEMZERO$/-UMEMZERO\1/' > Makefile.new X mv Makefile.new Makefile X fi Xelse echo 'You do not have memset(). Disabling it...' X sed '2s/$/ -UMEMZERO/' < Makefile | sed '2s/-DMEMZERO /-UMEMZERO /g' | sed '2s/-UMEMZERO\(.*\) -UMEMZERO$/-UMEMZERO\1/' > Makefile.new X mv Makefile.new Makefile Xfi Xrm -f .mmset.$$ .mmset.$$.out .mmset.$$.c .zero.$$.out X X# test for putchar not sign-extending correctly Xcat > .bozo.$$.c << 'YOW' X#include Xmain() { int i=255; putchar(25); exit(putchar((char)i) != EOF); } XYOW Xif cc -o .bozo.$$ .bozo.$$.c >/dev/null 2>&1 Xthen if ./.bozo.$$ >/dev/null X then echo 'You have the putchar((char) 255) == EOF bug.' X echo 'Let me put -DBRAINDAMAGED into the Makefile for you...' X sed '2s/$/ -DBRAINDAMAGED/' < Makefile | sed '2s/-UBRAINDAMAGED /-DBRAINDAMAGED /g' | sed '2s/-DBRAINDAMAGED\(.*\) -DBRAINDAMAGED$/-DBRAINDAMAGED\1/' > Makefile.new X mv Makefile.new Makefile X echo 'You *must* make sure to leave this defined.' X else echo 'You do not have the putchar((char) 255) == EOF bug.' X echo 'Making sure -DBRAINDAMAGED is not in the Makefile...' X sed '2s/$/ -UBRAINDAMAGED/' < Makefile | sed '2s/-DBRAINDAMAGED /-UBRAINDAMAGED /g' | sed '2s/-UBRAINDAMAGED\(.*\) -UBRAINDAMAGED$/-UBRAINDAMAGED\1/' > Makefile.new X mv Makefile.new Makefile X fi Xelse echo 'Weird, cannot compile normal stdio program.' X echo 'Making sure -DBRAINDAMAGED is not in the Makefile...' X sed '2s/$/ -UBRAINDAMAGED/' < Makefile | sed '2s/-DBRAINDAMAGED /-UBRAINDAMAGED /g' | sed '2s/-UBRAINDAMAGED\(.*\) -UBRAINDAMAGED$/-UBRAINDAMAGED\1/' > Makefile.new X mv Makefile.new Makefile Xfi Xrm -f .bozo.$$ .bozo.$$.out .bozo.$$.c .zero.$$.out X X# set ZEROFILLED Xecho "Since you're running this script, I assume that you're on a UNIX machine," Xecho "and static arrays are zero-filled by default. Enabling -DZEROFILLED..." Xsed '2s/$/ -DZEROFILLED/' < Makefile | sed '2s/-UZEROFILLED /-DZEROFILLED /g' | sed '2s/-DZEROFILLED\(.*\) -DZEROFILLED$/-DZEROFILLED\1/' > Makefile.new Xmv Makefile.new Makefile X Xecho ' ' Xecho 'Okay, now you should make checkconf and run it.' Xecho 'If you would like me to do this for you, press return.' Xecho 'Otherwise type no and press return, or just interrupt this script.' Xread foo Xcase x"$foo"y in Xxy) echo 'make checkconf' X if make checkconf X then echo './checkconf' X ./checkconf X else echo 'Oops, make checkconf failed. I give up: you figure it out.' X fi X ;; Xesac X Xexit 0 END_OF_FILE if test 4852 -ne `wc -c <'sysconf'`; then echo shar: \"'sysconf'\" unpacked with wrong size! fi chmod +x 'sysconf' # end of 'sysconf' fi if test -f 'texts.c' -a "${1}" != "-c" ; then echo shar: Will not clobber existing file \"'texts.c'\" else echo shar: Extracting \"'texts.c'\" \(6240 characters\) sed "s/^X//" >'texts.c' <<'END_OF_FILE' X/* Placed into the public domain by Daniel J. Bernstein. */ X X/* If you change the code, you should (1) add your name to sqauthor[] */ X/* and/or unsqauthor[]; (2) add a patch label to the version numbers */ X/* in sqversion[], sqcopyright[], unsqversion[], and unsqcopyright[]; */ X/* (3) change squsage[], sqhelp[], unsqusage[], and unsqhelp[] if you */ X/* changed the interface. The patch label should be a slash, your */ X/* initials, and the date the patch was released---e.g., version */ X/* 0.98 might become 0.98/JS032291 and then 0.98/JS032291/SS040591. */ X/* If you let me know about your changes, I'll try to integrate them */ X/* into the next release. */ X X#include "texts.h" X Xchar *sqauthor[] = { X"yabbawhap was written by Daniel J. Bernstein." , X"Internet address: brnstnd@nyu.edu." , X0 } ; X Xchar *sqversion[] = { X"yabbawhap version 1.00, March 19, 1991." , X"Placed into the public domain by Daniel J. Bernstein." , X0 } ; X Xchar *sqcopyright[] = { X"yabbawhap version 1.00, March 19, 1991." , X"Placed into the public domain by Daniel J. Bernstein." , X"" , X"There is no copyright on this code. You may use it in any way you want." , X"" , X"If you have questions about this program or about this notice, or if you" , X"have a patch that you don't mind sharing, please contact me on the Internet" , X"at brnstnd@nyu.edu." , X0 } ; X Xchar *sqwarranty[] = { X"Daniel J. Bernstein disclaims all warranties to the extent permitted" , X"by applicable law. He is not and shall not be liable for any damages" , X"arising from the use of this program. This disclaimer shall be governed" , X"by the laws of the state of New York." , X"" , X"In other words, use this program at your own risk." , X"" , X"If you have questions about this program or about this disclaimer of" , X"warranty, please feel free to contact me at brnstnd@nyu.edu on the" , X"Internet." , X0 } ; X Xchar *squsage[] = { X#ifdef WHAP X"Usage: whap [ -mmem ] [ -znum ] [ -Zfuzz ] [ -qQv^rRACHUVW ]" , X"Help: whap -H" , X#else X"Usage: yabba [ -mmem ] [ -znum ] [ -Zfuzz ] [ -qQv^rRACHUVW ]" , X"Help: yabba -H" , X#endif X0 } ; X Xchar *sqhelp[] = { X#ifdef WHAP X"whap compresses its input using AP coding. It writes the result to its output." , X"whap -ACHUVW: print authorship notice, copyright notice, this notice," , X" short usage summary, version number, disclaimer of warranty" , X"whap [ -mmem ] [ -znum ] [ -Zfuzz ] [ -qQv^rR ]: compress" , X#else X"yabba compresses its input using Y coding. It writes the result to its output." , X"yabba -ACHUVW: print authorship notice, copyright notice, this notice," , X" short usage summary, version number, disclaimer of warranty" , X"yabba [ -mmem ] [ -znum ] [ -Zfuzz ] [ -qQv^rR ]: compress" , X#endif X"-mmem: set block size to mem (default: factory 65533 chars, here %d)" , X"-r: randomize output to prepare for encryption; also omit header" , X"-R: don't randomize (default); use header" , X"-q: quiet (nothing on standard error)" , X"-Q: normal level of verbosity" , X"-v: verbose: like In: 312163 chars Out: 106253 chars Whapped to: 34%%" , X"-znum: set blocking test length (factory default 8192)" , X"-Zfuzz: set blocking fuzz (factory default 30)" , X"-^: like -v, but print percent saved rather than percent remaining" , X"" , X#ifdef WHAP X"unwhap must be given the same settings of -m and -r/-R." , X#else X"unyabba must be given the same settings of -m and -r/-R." , X#endif X"" , X"If you have questions about or suggestions for yabbawhap, please feel free" , X"to contact the author, Daniel J. Bernstein, at brnstnd@nyu.edu on the" , X"Internet." , X0 } ; X Xchar *unsqauthor[] = { X"yabbawhap was written by Daniel J. Bernstein." , X"Internet address: brnstnd@nyu.edu." , X0 } ; X Xchar *unsqversion[] = { X"yabbawhap version 1.00, March 19, 1991." , X"Placed into the public domain by Daniel J. Bernstein." , X0 } ; X Xchar *unsqcopyright[] = { X"yabbawhap version 1.00, March 19, 1991." , X"Placed into the public domain by Daniel J. Bernstein." , X"" , X"There is no copyright on this code. You may use it in any way you want." , X"" , X"If you have questions about this program or about this notice, or if you" , X"have a patch that you don't mind sharing, please contact me on the Internet" , X"at brnstnd@nyu.edu." , X0 } ; X Xchar *unsqwarranty[] = { X"Daniel J. Bernstein disclaims all warranties to the extent permitted" , X"by applicable law. He is not and shall not be liable for any damages" , X"arising from the use of this program. This disclaimer shall be governed" , X"by the laws of the state of New York." , X"" , X"In other words, use this program at your own risk." , X"" , X"If you have questions about this program or about this disclaimer of" , X"warranty, please feel free to contact me at brnstnd@nyu.edu on the" , X"Internet." , X0 } ; X Xchar *unsqusage[] = { X#ifdef WHAP X"Usage: unwhap [ -mmem ] [ -qQvrRACHUVW ]" , X"Help: unwhap -H" , X#else X"Usage: unyabba [ -mmem ] [ -qQvrRACHUVW ]" , X"Help: unyabba -H" , X#endif X0 } ; X Xchar *unsqhelp[] = { X#ifdef WHAP X"unwhap uncompresses its input, which must have come from whap, to its output." , X"unwhap -ACHUVW: print authorship notice, copyright notice, this notice," , X" short usage summary, version number, disclaimer of warranty" , X"unwhap [ -mmem ] [ -qQvrR ]: uncompress" , X#else X"unyabba uncompresses its input, which must have come from yabba, to its output." , X"unyabba -ACHUVW: print authorship notice, copyright notice, this notice," , X" short usage summary, version number, disclaimer of warranty" , X"unyabba [ -mmem ] [ -qQvrR ]: uncompress" , X#endif X"-mmem: set block size to mem (default: factory 65533 chars, here %d)" , X"-r: accept randomized input without a header" , X"-R: complain about randomized input; check for header" , X"-q: quiet (nothing on standard error)" , X"-Q: normal level of verbosity" , X"-v: verbose: like In: 106253 chars Out: 312163 chars Whapped from: 34%%" , X"" , X#ifdef WHAP X"The whap that wrote the input must have the same settings of -m and -r/-R." , X#else X"The yabba that wrote the input must have the same settings of -m and -r/-R." , X#endif X"" , X"If you have questions about or suggestions for yabbawhap, please feel free" , X"to contact the author, Daniel J. Bernstein, at brnstnd@nyu.edu on the" , X"Internet." , X0 } ; END_OF_FILE if test 6240 -ne `wc -c <'texts.c'`; then echo shar: \"'texts.c'\" unpacked with wrong size! fi # end of 'texts.c' fi if test -f 'unwhap.c' -a "${1}" != "-c" ; then echo shar: Will not clobber existing file \"'unwhap.c'\" else echo shar: Extracting \"'unwhap.c'\" \(6299 characters\) sed "s/^X//" >'unwhap.c' <<'END_OF_FILE' X/* Placed into the public domain by Daniel J. Bernstein. */ X Xstatic char whapwarning[] = "\ XWARNING! If you use AP coding except for instruction and amusement,\n\ Xyou may be infringing upon a patent.\n\ X"; X X#include Xextern long atol(); Xextern int getopt(); Xextern char *optarg; Xextern int optind; X#include "percent.h" X#include "texts.h" X Xstatic char progname[] = "unwhap"; Xstatic char progged[] = "Unwhapped"; X X#ifndef TYPE X#define TYPE short X#endif X Xtypedef TYPE bitnum; Xtypedef unsigned TYPE bitword; X Xint twom1[9] = { 0,1,3,7,15,31,63,127,255 } ; X X#ifndef NODEMAX X#define NODEMAX (65533) X#endif X#ifndef NODENUM X#define NODENUM NODEMAX X#endif Xstatic char outarray[NODEMAX]; /* first 256 spots unused, boo hoo hoo */ Xstatic bitword outstart[NODEMAX]; /* first 256 spots unused, boo hoo hoo */ X X#define MAXPLUS max++; oamax++; osmax++; \ Xif (max == nextbits) { bits++; nextbits <<= 1; } X Xstatic unsigned long savein; Xstatic unsigned long saveout; Xstatic int flagverbose = 1; Xstatic int flagrandom = 0; X Xvoid goaheadandbeverbose() X{ X long per = percent(savein,saveout,10000L); X X if (per == 10000L) /* absolutely ridiculous */ X fprintf(stderr,"In: %ld chars Out: %ld chars %s from: >9999%%\n", X savein,saveout,progged); X else X fprintf(stderr,"In: %ld chars Out: %ld chars %s from: %ld%%\n", X savein,saveout,progged,per); X} X Xvoid fatalinfo(x,s) Xint x; Xchar **s; X{ X if (flagverbose) while (*s) X { X fprintf(stderr,*(s++),NODENUM); X putc('\n',stderr); X } X (void) exit(x); X} X X#define PUTERR { if (flagverbose) fprintf(stderr,"%s: fatal: output error\n",progname); \ Xsavein = in; saveout = out; \ Xif (flagverbose >= 2) goaheadandbeverbose(); (void) exit(2); } X Xmain(argc,argv) Xint argc; Xchar *argv[]; X{ X register bitword i; X register char *j; X register bitword outb; X register bitword max; X register bitword nextbits; X register bitnum bits; X register bitword curw = 0; X register bitnum curbb = 0; X register int ch; X register char *oamax; X register bitword *osmax; X register char *oai; X register bitword min = NODENUM - 1; /* maximum decompressor size - 1 */ X register unsigned long in = 0; X register unsigned long out = 0; X X { X int opt; X bitword i; X X while ((opt = getopt(argc,argv,"m:vqQrRACHUVW")) != EOF) X switch(opt) X { X case '?': fatalinfo(1,unsqusage); X case 'm': i = atol(optarg); X if ((i < 512) || (i > NODEMAX)) X { X if (flagverbose) fprintf(stderr, X "%s: fatal: mem size out of range: must be between 512 and %ld\n", X progname,(long) NODEMAX); X (void) exit(1); X } X min = i - 1; X break; X case 'v': flagverbose = 2; break; X case 'q': flagverbose = 0; break; X case 'Q': flagverbose = 1; break; X case 'r': flagrandom = 1; break; X case 'R': flagrandom = 0; break; X case 'A': fatalinfo(1,unsqauthor); break; X case 'C': fatalinfo(1,unsqcopyright); break; X case 'H': fatalinfo(1,unsqhelp); break; X case 'U': fatalinfo(1,unsqusage); break; X case 'V': fatalinfo(1,unsqversion); break; X case 'W': fatalinfo(1,unsqwarranty); break; X } X argv += optind; X argc -= optind; X } X X if (flagverbose) X fprintf(stderr,whapwarning); X X if (!flagrandom) X { X bitword i = 0; X int r; X X if ((getchar() != 23) X ||(getchar() != 8) X ||(getchar() != 1) X ||(getchar() != 16) X ||((r = getchar()) == EOF)) X { X if (flagverbose) fprintf(stderr,"%s: fatal: input not in right format\n",progname); X (void) exit(3); X } X in += 5; X while (r) X { X if (((ch = getchar()) == EOF) || (ch < 48) || (ch > 57)) X { X if (flagverbose) fprintf(stderr,"%s: fatal: input not in right format\n",progname); X (void) exit(3); X } X ++in; X i = i * 10 + (ch - 48); X --r; X } X if (i != min + 1) X { X if (flagverbose) fprintf(stderr,"%s: fatal: input has -m %ld, I have -m %ld\n" X ,progname,(long) i,(long) (min + 1)); X (void) exit(4); X } X } X X#define MINIT max = 256; oamax = outarray + 256; osmax = outstart + 256; \ Xoutb = 256; nextbits = 256; bits = 8; \ Xwhile (max >= nextbits) { bits++; nextbits <<= 1; } X/* of course, max = 255 plus one for table clearing */ X X MINIT X X for (;;) X { X /* assumes bits >= 8 */ X while (curbb + 8 < bits) /* could be an if, when bits is < 16 */ X if ((ch = getchar()) != EOF) X { X curw += ch << curbb; X curbb += 8; X ++in; /* XXX: check for overflow */ X } X else X { X savein = in; saveout = out; X if (flagverbose >= 2) X goaheadandbeverbose(); X (void) exit(0); X } X if ((ch = getchar()) == EOF) X { X savein = in; saveout = out; X if (flagverbose >= 2) X goaheadandbeverbose(); X (void) exit(0); X } X i = curw + ((ch & twom1[bits - curbb]) << curbb); X curw = ch >> (bits - curbb); X curbb = 8 - (bits - curbb); X ++in; /* XXX: check for overflow */ X X /* XXX: flagpedantic to control whether we make this test? */ X if (i > max) X if (flagrandom) X i -= max + 1; X else X { X if (flagverbose) fprintf(stderr,"%s: fatal: input corrupt at byte %ld\n",progname,in); X (void) exit(5); X } X X if (i < 257) /* 256 is special */ X if (i != 256) X { X if (max != min) X { X MAXPLUS X *osmax = outb; X *oamax = i; X outb = max; X } X#ifdef BRAINDAMAGED X if (i == 255) X putchar((char) i); X else X#endif X if (putchar((char) i) == EOF) X PUTERR X ++out; /* XXX: check for overflow */ X } X else X { X /* here's where blocking stuff should go */ X MINIT X /* wow, that was easy */ X } X else X { X oai = outarray + i; X j = outarray + outstart[i] - 1; X while ((j != oai) && (max != min)) X { X MAXPLUS X *oamax = *++j; X#ifdef BRAINDAMAGED X if (*oamax == (char) 255) X putchar(*oamax); X else X#endif X if (putchar(*oamax) == EOF) X PUTERR X ++out; /* XXX: check for overflow */ X *osmax = outb; X } X while (j != oai) X { X ++j; X#ifdef BRAINDAMAGED X if (*j == (char) 255) X putchar(*j); X else X#endif X if (putchar(*j) == EOF) X PUTERR X ++out; /* XXX: check for overflow */ X } X outb = max - (i - outstart[i]); X } X#ifdef notdef X/*XXX: -d code */ X#endif X } X} END_OF_FILE if test 6299 -ne `wc -c <'unwhap.c'`; then echo shar: \"'unwhap.c'\" unpacked with wrong size! fi # end of 'unwhap.c' fi if test -f 'unyabba.1' -a "${1}" != "-c" ; then echo shar: Will not clobber existing file \"'unyabba.1'\" else echo shar: Extracting \"'unyabba.1'\" \(2906 characters\) sed "s/^X//" >'unyabba.1' <<'END_OF_FILE' X.TH unyabba 1 X.SH NAME Xunyabba \- decompress data compressed with Y coding X Xunwhap \- decompress data compressed with AP coding X.SH SYNTAX Xunyabba X[ X\fB\-m\fImem X] [ X\fB\-qQvrR\fI X] [ X\fB\-ACHUVW\fI X] X X\fBunwhap X[ X\fB\-m\fImem X] [ X\fB\-qQvrR\fI X] [ X\fB\-ACHUVW\fI X] X.SH DESCRIPTION X.I unyabba Xdecompresses its standard input, Xwhich must have come from X.I yabba, Xand writes the result to its standard output. X X.I unwhap Xis like X.I unyabba, Xbut works with files from X.I whap. XWarning: If you use X.I unwhap Xexcept for experimental use, Xyou may be infringing upon a patent. X XOptions X.B ACHUVW Xprint the authorship notice, Xcopyright notice, Xhelp notice, Xshort usage summary, Xversion number, Xand warranty information respectively. X X.I unyabba Xhas several flags: X.TP 12 X.B\-m\fImem XAssume that the input was produced for memory size X.I mem. X.I yabba Xmust have been given the same value of X.I mem. X.I mem Xcannot be larger than a value specified at compile-time. XTypical values of X.I mem Xare 12000, 20000, 40000, 65533, 200000, 500000, and 1000000. X.TP X.B\-r XAssume that the input was ``randomized'' Xby X.I yabba. X.I unyabba Xwill not expect its usual header, Xand will strip out the pseudo-random information Xintroduced by X.I yabba. XCaveat: X.I unyabba Xnormally checks for the proper X.B\-m Xsetting in the input. XUnder X.B\-r, Xit cannot do so. X.TP X.B\-R XLook for the usual header, and complain about apparently random input. XThis is the default. X.TP X.B\-v X.I unyabba Xwill be ``verbose'' and report compression statistics Xto standard error. X.TP X.B\-q XQuiet. X.I unyabba Xwill not use Xstandard error in any way. X.TP X.B\-Q XNormal level of verbosity. X.PP X.B\-m, X.B\-r, Xand X.B\-R Xassume a different structure for the compressed file. XBe careful to have selected the same flags for X.I yabba. X.SH DIAGNOSTICS X.TP X\fIIn:\fB xxx \fIchars Out:\fB xxx \fIchars UnY'd from:\fB xx% XThe utilizer of the computational machinery Xhas specified the ``verbose'' option Xto X.I unyabba Xvia the Xestablishment of the character v Xwithin an argument Xpreceded by a hyphen. X.TP X\fIfatal: output error\fB XSelf-explanatory. X.TP X\fIfatal: input not in right format\fB XThe X.I yabba Xheader is not there. X.TP X\fIfatal: input has \-m xxx, I have \-m yyy\fB XSelf-explanatory. X.TP X\fIfatal: input corrupt XThe input is not a compressed file. (Note that X.I unyabba Xwill always detect this, unlike X.I uncompress, Xwhich may simply produce incorrect output.) XDid you compress with X.B\-r? X.SH "EXIT CODE" X0 normally, 1 for syntax errors or usage messages, X2 for output errors, X3 if the input is not in the right format, X4 if the input was compressed with a different value of X.I mem, X5 if the input is corrupt. X.SH FILES XNone. X.SH BUGS XNone known. X.SH VERSION Xunwhap 1.00, March 19, 1991. X.SH AUTHOR XPlaced into the public domain by Daniel J. Bernstein. X.SH REFERENCES XD. J. Bernstein, ``Y coding.'' XPreprints available soon. X.SH "SEE ALSO" Xyabba(1), Xcompress(1) END_OF_FILE if test 2906 -ne `wc -c <'unyabba.1'`; then echo shar: \"'unyabba.1'\" unpacked with wrong size! fi # end of 'unyabba.1' fi if test -f 'yabba.1' -a "${1}" != "-c" ; then echo shar: Will not clobber existing file \"'yabba.1'\" else echo shar: Extracting \"'yabba.1'\" \(3586 characters\) sed "s/^X//" >'yabba.1' <<'END_OF_FILE' X.TH yabba 1 X.SH NAME Xyabba \- compress data with Y coding X Xwhap \- compress data with AP coding X.SH SYNTAX Xyabba X[ X\fB\-m\fImem X] [ X\fB\-z\fInum X] [ X\fB\-Z\fIfuzz X] [ X\fB\-qQv^rR\fI X] [ X\fB\-ACHUVW\fI X] X X\fBwhap X[ X\fB\-m\fImem X] [ X\fB\-z\fInum X] [ X\fB\-Z\fIfuzz X] [ X\fB\-qQv^rR\fI X] [ X\fB\-ACHUVW\fI X] X.SH DESCRIPTION X.I yabba Xcompresses its standard input Xand writes the result to its standard output. X\fIyabba\fBd Xfiles can be restored Xwith X\fIunyabba\fB. X X.I whap Xis like X.I yabba, Xbut uses AP coding. XWarning: If you use X.I whap Xexcept for experimental use, Xyou may be infringing upon a patent. X XOptions X.B ACHUVW Xprint the authorship notice, Xcopyright notice, Xhelp notice, Xshort usage summary, Xversion number, Xand warranty information respectively. X X.I yabba Xhas several flags: X.TP 12 X.B\-m\fImem XProduce output for memory size X.I mem. X.I unyabba Xmust be given the same value of X.I mem. X.I mem Xcannot be larger than a value specified at compile-time; Xif you compress with a X.I mem Xlarger than the maximum value for the Xtarget X.I unyabba, Xyou will not be able to decompress the file. XTypical values of X.I mem Xare 12000, 20000, 40000, 65533, 200000, 500000, and 1000000. X.TP X.B\-r XProduce ``randomized'' output suitable for encryption. X.I yabba Xwill introduce Xpseudo-random bits of information Xinto the output, and will leave off its usual output header. XNormally, for efficiency and so that X.I yabba Xcan produce output before seeing the end of the input, Xcompressed texts must have some slight output redundancy. XUnder X.B\-r, Xmost of this redundancy disappears Xand almost all X\fIY'\fBd Xtexts are possible. XCaveat: the beginning Xof the output depends only Xon the beginning Xof the input, Xso you should make sure Xto X.I precede the uncompressed input X.I by unpredictable data Xbefore feeding it to X.I yabba. X.TP X.B\-R XDo not randomize output, and include the usual header. XThis is the default. X.TP X.B\-Z\fIfuzz X.I yabba Xmaintains a X``dictionary'' Xof strings Xadapted to the data seen so far. XWhen X.I yabba Xruns out of memory (as specified by X.B\-m), Xit will periodically test whether the compression ratio is Xgood enough. XIf not, it will adapt to the next ``block'' Xof the file Xby throwing out the dictionary and starting over. X.I fuzz Xhas some vaguely defined effect Xon what ``good enough'' means; Xthe higher X.I fuzz Xis, the longer X.I yabba Xwill hold out before clearing the dictionary. X.I fuzz Xis 30 by default. X.TP X.B\-z\fInum X.I num Xsets how often X.I yabba Xwill check for clearing the dictionary. XThe default is every 8192 characters. X.TP X.B\-v X.I yabba Xwill be ``verbose'' and report compression statistics Xto standard error. X.TP X.B\-^ XSame as X.B\-v, Xbut reports the percent saved rather than the percent left. X.TP X.B\-q XQuiet. X.I yabba Xwill not use Xstandard error in any way. X.TP X.B\-Q XNormal level of verbosity. X.PP X.B\-m, X.B\-r, Xand X.B\-R Xchange the structure of the compressed file. XBe careful to select the same flags for X.I unyabba. X.SH DIAGNOSTICS X.TP X\fIIn:\fB xxx \fIchars Out:\fB xxx \fIchars Y'd to:\fB xx% XThe utilizer of the computational machinery Xhas specified the ``verbose'' option Xto X.I yabba Xvia the Xestablishment of the character v Xwithin an argument Xpreceded by a hyphen. X.TP X\fIfatal: output error\fB XSelf-explanatory. X.SH "EXIT CODE" X0 normally, 1 for syntax errors or usage notices, X2 for output errors. X.SH FILES XNone. X.SH BUGS XNone known. X.SH VERSION Xyabba 1.00, March 19, 1991. X.SH AUTHOR XPlaced into the public domain by Daniel J. Bernstein. X.SH REFERENCES XD. J. Bernstein, ``Y coding.'' XPreprints available soon. X.SH "SEE ALSO" Xunyabba(1), Xcompress(1) END_OF_FILE if test 3586 -ne `wc -c <'yabba.1'`; then echo shar: \"'yabba.1'\" unpacked with wrong size! fi # end of 'yabba.1' fi echo shar: End of archive 3 \(of 4\). cp /dev/null ark3isdone MISSING="" for I in 1 2 3 4 ; do if test ! -f ark${I}isdone ; then MISSING="${MISSING} ${I}" fi done if test "${MISSING}" = "" ; then echo You have unpacked all 4 archives. rm -f ark[1-9]isdone else echo You still must unpack the following archives: echo " " ${MISSING} fi exit 0 exit 0 # Just in case...