home *** CD-ROM | disk | FTP | other *** search
/ Usenet 1994 January / usenetsourcesnewsgroupsinfomagicjanuary1994.iso / sources / unix / volume24 / yabbawhap / part02 / unyabba.c < prev    next >
Encoding:
C/C++ Source or Header  |  1991-10-09  |  7.1 KB  |  290 lines
  1. /* Placed into the public domain by Daniel J. Bernstein. */
  2.  
  3. /* Want to make yourself popular? Figure out a fast Y decoding method.  */
  4.  
  5. #include <stdio.h>
  6. extern long atol();
  7. extern int getopt();
  8. extern char *optarg;
  9. extern int optind;
  10. #include "bitout.h"
  11. #include "percent.h"
  12. #include "texts.h"
  13. #include "huptrie.h"
  14.  
  15. static char progname[] = "unyabba";
  16. static char progged[] = "UnY'ed";
  17.  
  18. int twom1[9] = { 0,1,3,7,15,31,63,127,255 } ;
  19.  
  20. #define ALPHABET 256
  21.  
  22. #ifndef NODEMAX
  23. #define NODEMAX (65533)
  24. #endif
  25. #ifndef NODENUM
  26. #define NODENUM NODEMAX
  27. #endif
  28. #ifndef MOD
  29. #define MOD (65536)
  30. #endif
  31.  
  32. STATICDECLARE(n,p,h,NODEMAX,MOD - 1)
  33. node s[NODEMAX + 1];
  34. hash geth[NODEMAX + 2]; /* aargh */
  35. char gc[NODEMAX + 1];
  36.  
  37. #define NUMOF(no) node2pos(n,no,NODEMAX)
  38.  
  39. #define CHECKMAXBITS \
  40. ((max == nextbits) && ((bits++), \
  41.   (nextbits = pos2ipos(n,2 * ipos2pos(n,nextbits,NODEMAX),NODEMAX))))
  42.  
  43. #define ADD(hash,oldnode,node,ch) \
  44. ( (void) ( ADDMAX(n,p,h,max,oldnode,hash,node), \
  45. (gc[node2ipos(n,node,NODEMAX)] = ch), \
  46. (geth[node2ipos(n,node,NODEMAX)] = hash), CHECKMAXBITS ) )
  47.  
  48. #define SUB(ip1,ip2) (ip1 - ip2) /* XXXX: This breaks encapsulation! Ungood. */
  49.  
  50. static unsigned long savein = 0;
  51. static unsigned long saveout = 0;
  52. static int flagverbose = 1;
  53. static int flagrandom = 0;
  54.  
  55. void goaheadandbeverbose()
  56. {
  57.  long per = percent(savein,saveout,10000L);
  58.  
  59.  if (per == 10000L) /* absolutely ridiculous */
  60.    fprintf(stderr,"In: %ld chars  Out: %ld chars  %s from: >9999%%\n",
  61.            savein,saveout,progged);
  62.  else
  63.    fprintf(stderr,"In: %ld chars  Out: %ld chars  %s from: %ld%%\n",
  64.        savein,saveout,progged,per);
  65. }
  66.  
  67. void fatalinfo(x,ss)
  68. int x;
  69. char **ss;
  70. {
  71.  if (flagverbose) while (*ss)
  72.   {
  73.    fprintf(stderr,*(ss++),NODENUM);
  74.    putc('\n',stderr);
  75.   }
  76.  (void) exit(x);
  77. }
  78.  
  79. #define PUTERR { if (flagverbose) fprintf(stderr,"%s: fatal: output error\n",progname); \
  80. savein += in; saveout += out; \
  81. if (flagverbose >= 2) goaheadandbeverbose(); (void) exit(2); }
  82.  
  83. main(argc,argv)
  84. int argc;
  85. char *argv[];
  86. {
  87.  register pos i;
  88.  register node matchnode;
  89.  register hash matchhash;
  90.  register node dosnode;
  91.  register node oldnode;
  92.  register ipos max;
  93.  register ipos nextbits;
  94.  register bitnum bits;
  95.  register bitword curw = 0;
  96.  register bitnum curbb = 0;
  97.  register int ch;
  98.  register ipos min;
  99.  register unsigned long in = 0;
  100.  register unsigned long out = 0;
  101.  register node curnode;
  102.  register int firstch;
  103.  pos smax;
  104.  
  105.  min = pos2ipos(n,NODENUM - 1,NODEMAX);
  106.  
  107.   {
  108.    int opt;
  109.    bitword i;
  110.  
  111.    while ((opt = getopt(argc,argv,"m:vqQrRACHUVW")) != EOF)
  112.      switch(opt)
  113.       {
  114.        case '?': fatalinfo(1,unsqusage);
  115.        case 'm': i = atol(optarg);
  116.          if ((i < 512) || (i > NODEMAX))
  117.           {
  118.            if (flagverbose) fprintf(stderr,
  119.               "%s: fatal: mem size out of range: must be between 512 and %ld\n",
  120.               progname,(long) NODEMAX);
  121.            (void) exit(1);
  122.           }
  123.          min = pos2ipos(n,i - 1,NODEMAX);
  124.          break;
  125.        case 'v': flagverbose = 2; break;
  126.        case 'q': flagverbose = 0; break;
  127.        case 'Q': flagverbose = 1; break;
  128.        case 'r': flagrandom = 1; break;
  129.        case 'R': flagrandom = 0; break;
  130.        case 'A': fatalinfo(1,unsqauthor); break;
  131.        case 'C': fatalinfo(1,unsqcopyright); break;
  132.        case 'H': fatalinfo(1,unsqhelp); break;
  133.        case 'U': fatalinfo(1,unsqusage); break;
  134.        case 'V': fatalinfo(1,unsqversion); break;
  135.        case 'W': fatalinfo(1,unsqwarranty); break;
  136.       }
  137.    argv += optind;
  138.    argc -= optind;
  139.   }
  140.  
  141.  if (!flagrandom)
  142.   {
  143.    bitword i = 0;
  144.    int r;
  145.  
  146.    if ((getchar() != 25)
  147.      ||(getchar() != 1)
  148.      ||(getchar() != 2)
  149.      ||(getchar() != 2)
  150.      ||(getchar() != 1)
  151.      ||((r = getchar()) == EOF))
  152.     {
  153.      if (flagverbose) fprintf(stderr,"%s: fatal: input not in right format\n",progname);
  154.      (void) exit(3);
  155.     }
  156.    in += 6;
  157.    while (r)
  158.     {
  159.      if (((ch = getchar()) == EOF) || (ch < 48) || (ch > 57))
  160.       {
  161.        if (flagverbose) fprintf(stderr,"%s: fatal: input not in right format\n",progname);
  162.        (void) exit(3);
  163.       }
  164.      ++in; /* XXX: check for overflow */
  165.      i = i * 10 + (ch - 48);
  166.      --r;
  167.     }
  168.    if (i != ipos2pos(n,min,NODEMAX) + 1)
  169.     {
  170.      if (flagverbose) fprintf(stderr,"%s: fatal: input has -m %ld, I have -m %ld\n"
  171.          ,progname,(long) i,(long) ipos2pos(n,min,NODEMAX) + 1);
  172.      (void) exit(4);
  173.     }
  174.   }
  175.  
  176.  FIRSTHASH(h,MOD - 1)
  177.  
  178. restart:
  179.  
  180.  STATICINIT(n,p,h,max,smax,NODEMAX,MOD - 1)
  181.  
  182.  nextbits = pos2ipos(n,ALPHABET,NODEMAX);
  183.  bits = 8;
  184.  
  185.  geth[node2ipos(n,topnode(n,NODEMAX),NODEMAX)] = tophash(h,MOD - 1);
  186.  
  187.  for (ch = 0;ch < ALPHABET;++ch)
  188.   {
  189.    ADD(hc(tophash(h,MOD - 1),ch,MOD - 1),topnode(n,NODEMAX),curnode,ch);
  190.    s[node2ipos(n,curnode,NODEMAX)] = topnode(n,NODEMAX);
  191.   }
  192.  WASTEMAX(n,p,h,max,smax,curnode); CHECKMAXBITS;
  193.  /* leaving space for the clear code, ALPHABET */
  194.  
  195.  matchnode = topnode(n,NODEMAX);
  196.  matchhash = tophash(h,MOD - 1);
  197.  
  198.  for (;;)
  199.   {
  200.    /* assumes bits >= 8 */
  201.    while (curbb + 8 < bits) /* could be an if, when bits is < 16 */
  202.      if ((ch = getchar()) != EOF)
  203.       {
  204.        curw += ch << curbb;
  205.        curbb += 8;
  206.        ++in; /* XXX: check for overflow */
  207.       }
  208.      else
  209.       {
  210.        savein += in; saveout += out;
  211.        if (flagverbose >= 2)
  212.      goaheadandbeverbose();
  213.        (void) exit(0);
  214.       }
  215.    if ((ch = getchar()) == EOF)
  216.     {
  217.      savein += in; saveout += out;
  218.      if (flagverbose >= 2)
  219.        goaheadandbeverbose();
  220.      (void) exit(0);
  221.     }
  222.    i = curw + ((ch & twom1[bits - curbb]) << curbb);
  223.    curw = ch >> (bits - curbb);
  224.    curbb = 8 - (bits - curbb);
  225.    ++in; /* XXX: check for overflow */
  226.  
  227.    /* XXX: flagpedantic to control whether we make this test? */
  228.    if (i > ipos2pos(n,max,NODEMAX))
  229.      if (flagrandom)
  230.        i -= ipos2pos(n,max,NODEMAX) + 1;
  231.      else
  232.       {
  233.        if (flagverbose) fprintf(stderr,"%s: fatal: input corrupt at byte %ld\n",progname,in);
  234.        (void) exit(5);
  235.       }
  236.  
  237.    if (i == ALPHABET) /* clear */
  238.     {
  239.      savein += in;
  240.      saveout += out;
  241.      /* XXX: test for overflow? */
  242.      in = 0;
  243.      out = 0;
  244.      CLEARHASH(h,MOD - 1)
  245.      goto restart;
  246.     }
  247.    curnode = pos2node(n,i,NODEMAX);
  248.  
  249.    while (curnode != topnode(n,NODEMAX))
  250.     {
  251.      ch = gc[node2ipos(n,curnode,NODEMAX)];
  252.      curnode = s[node2ipos(n,curnode,NODEMAX)];
  253. #ifdef BRAINDAMAGED
  254.      if (((char) ch) == (char) 255)
  255.        putchar((char) ch);
  256.      else
  257. #endif
  258.      if (putchar((char) ch) == EOF)
  259.        PUTERR
  260.      ++out; /* XXX: check for overflow */
  261.  
  262. #define MATCHADD { if (matchnode == topnode(n,NODEMAX)) firstch = ch; \
  263. if (dosnode) { ADD(matchhash,matchnode,oldnode,firstch); \
  264. s[node2ipos(n,dosnode,NODEMAX)] = oldnode; dosnode = oldnode; } \
  265. else ADD(matchhash,matchnode,dosnode,firstch); \
  266. matchnode = s[node2ipos(n,matchnode,NODEMAX)]; \
  267. firstch = gc[node2ipos(n,matchnode,NODEMAX)]; \
  268. matchhash = geth[node2ipos(n,matchnode,NODEMAX)]; \
  269. }
  270.  
  271. /* XXXX: get rid of first if (max != min) ? */
  272. /* XXX: is DOWNI too slow? */
  273. #define MATCHDOWN if (max != min) { dosnode = 0; \
  274. do { matchhash = hc(matchhash,ch,MOD - 1); \
  275. DOWNI(n,p,h,matchnode,matchhash,oldnode,{break;},MATCHADD) } while(max!=min);\
  276. if (matchnode == topnode(n,NODEMAX)) firstch = ch; \
  277. if (dosnode) s[node2ipos(n,dosnode,NODEMAX)] = oldnode; \
  278. matchnode = oldnode; }
  279. /* XXX: Should unroll the loop a bit. */
  280.      MATCHDOWN
  281.  
  282.     }
  283.  
  284. #ifdef notdef
  285. /*XXX: -d code */
  286. #endif
  287.  
  288.   }
  289. }
  290.