home *** CD-ROM | disk | FTP | other *** search
/ Usenet 1994 January / usenetsourcesnewsgroupsinfomagicjanuary1994.iso / sources / unix / volume24 / yabbawhap / part02 / yw.c < prev   
Encoding:
C/C++ Source or Header  |  1991-10-09  |  10.9 KB  |  478 lines
  1. /* Placed into the public domain by Daniel J. Bernstein. */
  2.  
  3. /* This is the source for BOTH coding methods! Y and AP are both here. */
  4. /* Keep this in mind when hacking the source. */
  5.  
  6. #ifdef WHAP
  7. static char whapwarning[] = "\
  8. WARNING! If you use AP coding except for instruction and amusement,\n\
  9. you may be infringing upon a patent.\n\
  10. ";
  11. #endif
  12.  
  13. #include <stdio.h>
  14. extern long atol();
  15. extern int getopt();
  16. extern char *optarg;
  17. extern int optind;
  18. #include "bitout.h"
  19. #include "percent.h"
  20. #include "texts.h"
  21. #include "huptrie.h"
  22.  
  23. #ifdef WHAP
  24. static char progname[] = "whap";
  25. static char progged[] = "Whapped";
  26. #else
  27. static char progname[] = "yabba";
  28. static char progged[] = "Y'ed";
  29. #endif
  30.  
  31. #define ALPHABET 256 /* do not change this! */
  32.  
  33. #ifndef RESETNUM
  34. #define RESETNUM 8192
  35. #endif
  36. #ifndef RESETFUZZ
  37. #define RESETFUZZ 30 /* XXX: any suggestions? */
  38. #endif
  39. static long resetnum = RESETNUM;
  40. static long resetfuzz = RESETFUZZ; /* when in doubt, pass the buck */
  41.  
  42. #ifndef NODEMAX
  43. #define NODEMAX (65533) /* up to 65533---could be 65534 for whap */
  44. #endif
  45. #ifndef NODENUM
  46. #define NODENUM NODEMAX
  47. #endif
  48.  
  49. #ifndef MOD
  50. #define MOD (65536)
  51. #endif
  52.  
  53. STATICDECLARE(n,p,h,NODEMAX,MOD - 1)
  54. #ifndef WHAP
  55. node s[NODEMAX + 1];
  56. hash geth[NODEMAX + 2]; /* XXX: only because of this is 65533 the default */
  57. #endif
  58.  
  59. #define NUMOF(no) node2pos(n,no,NODEMAX)
  60.  
  61. #define CHECKMAXBITS \
  62. ((max == nextbits) && ((bits++), \
  63.   (nextbits = pos2ipos(n,2 * ipos2pos(n,nextbits,NODEMAX),NODEMAX))))
  64.  
  65. #ifndef WHAP
  66. #define ADD(hash,oldnode,node) \
  67. ( (void) ( ADDMAX(n,p,h,max,oldnode,hash,node), \
  68.   (geth[node2ipos(n,node,NODEMAX)] = hash), CHECKMAXBITS ) )
  69. #else
  70. #define ADD(hash,oldnode,node) \
  71. ( (void) ( ADDMAX(n,p,h,max,oldnode,hash,node), CHECKMAXBITS ) )
  72. #endif
  73.  
  74. #define SUB(ip1,ip2) (ip1 - ip2) /* XXXX: This breaks encapsulation! Ungood. */
  75.  
  76. static unsigned long savein = 0;
  77. static unsigned long saveout = 0;
  78. static int flagverbose = 1;
  79.  
  80. void goaheadandbeverbose()
  81. {
  82.  long per;
  83.       
  84.  per = percent(saveout,savein,10000L);
  85.  if (per == 10000L) /* absolutely ridiculous */
  86.    if (flagverbose == 2)
  87.      fprintf(stderr,"In: %ld chars  Out: %ld chars  %s to: >9999%%\n",
  88.      savein,saveout,progged);
  89.    else
  90.      fprintf(stderr,"In: %ld chars  Out: %ld chars  %s by: <-9899%%\n",
  91.      savein,saveout,progged);
  92.  else
  93.    if (flagverbose == 2)
  94.      fprintf(stderr,"In: %ld chars  Out: %ld chars  %s to: %ld%%\n",
  95.      savein,saveout,progged,per);
  96.    else
  97.      fprintf(stderr,"In: %ld chars  Out: %ld chars  %s by: %ld%%\n",
  98.      savein,saveout,progged,100 - per);
  99. }
  100.  
  101. int y[55];
  102. int j;
  103. int k;
  104.  
  105. #define RANDOMBIT ( ( !j ? (j = 54) : --j ), \
  106. ( !k ? (k = 54) : --k ), ( y[k] ^= y[j] ) )
  107.  
  108. void initrandom()
  109. {
  110.  int i;
  111.  
  112. #ifdef RANDINIT
  113.  srand(RANDINIT);
  114. #else
  115.  srand(1);
  116. #endif
  117.  for (i = 0;i < 54;i++)
  118.    y[i] = ((rand()) + (rand() >> 13) + (rand() % 71)) % 2;
  119.  y[54] = 1;
  120.  j = 24;
  121.  k = 0;
  122.  for (i = 0;i < 100;i++)
  123.    (void) RANDOMBIT;
  124. }
  125.  
  126. void fatalinfo(x,ss)
  127. int x;
  128. char **ss;
  129. {
  130.  if (flagverbose) while (*ss)
  131.   {
  132.    fprintf(stderr,*(ss++),NODENUM);
  133.    putc('\n',stderr);
  134.   }
  135.  (void) exit(x);
  136. }
  137.  
  138. main(argc,argv)
  139. int argc;
  140. char *argv[];
  141. {
  142.  register node oldnode;
  143.  register hash oldhash;
  144.  register node curnode;
  145.  register hash curhash;
  146. #ifndef WHAP
  147.  register node matchnode;
  148.  register hash matchhash;
  149.  register node dosnode;
  150.  register node safenode;
  151. #else
  152.  register node lastnode;
  153.  register hash lasthash;
  154.  register node midnode;
  155.  register hash midhash;
  156. #endif
  157.  register int ch;
  158.  register bitnum curbits;
  159. #ifdef WHAP
  160.  register node firstmidnode;
  161.  register node newnode;
  162. #endif
  163.  register ipos max;
  164.  register ipos nextbits;
  165.  register bitnum bits;
  166.  register ipos min;
  167.  register long numin = 0;
  168.  register long nextreset;
  169.  register int flagrandom = 0;
  170.  ipos curmax;
  171.  ipos curnextbits;
  172.  long eff;
  173.  pos smax;
  174.  
  175. #define PUTERR { \
  176. if (flagverbose) fprintf(stderr,"%s: fatal: output error\n",progname); \
  177. savein += numin; saveout += bit_numout; /*XXX*/ \
  178. if (flagverbose >= 2) goaheadandbeverbose(); (void) exit(2); }
  179.  
  180.  
  181.  min = pos2ipos(n,NODENUM - 1,NODEMAX);
  182.  
  183.   {
  184.    int opt;
  185.    bitword i;
  186.  
  187.    while ((opt = getopt(argc,argv,"m:v^qQrz:Z:RACHUVW")) != EOF)
  188.      switch(opt)
  189.       {
  190.        case '?': fatalinfo(1,squsage);
  191.        case 'm': i = atol(optarg);
  192.          if ((i < 512) || (i > NODEMAX))
  193.           {
  194.            if (flagverbose) fprintf(stderr,
  195.               "%s: fatal: mem size out of range: must be between 512 and %ld\n",
  196.               progname,(long) NODEMAX);
  197.            (void) exit(1);
  198.           }
  199.          min = pos2ipos(n,i - 1,NODEMAX);
  200.          break;
  201.        case 'v': flagverbose = 2; break;
  202.        case '^': flagverbose = 3; break;
  203.        case 'q': flagverbose = 0; break;
  204.        case 'Q': flagverbose = 1; break;
  205.        case 'r': flagrandom = 1; break;
  206.        case 'R': flagrandom = 0; break;
  207.        case 'z': resetnum = atol(optarg);
  208.          if (resetnum < 512) resetnum = 512;
  209.          break;
  210.        case 'Z': resetfuzz = atol(optarg); break;
  211.        case 'A': fatalinfo(1,sqauthor);
  212.        case 'C': fatalinfo(1,sqcopyright);
  213.        case 'H': fatalinfo(1,sqhelp);
  214.        case 'U': fatalinfo(1,squsage);
  215.        case 'V': fatalinfo(1,sqversion);
  216.        case 'W': fatalinfo(1,sqwarranty);
  217.       }
  218.    argv += optind;
  219.    argc -= optind;
  220.   }
  221.  
  222. #ifdef WHAP
  223.  if (flagverbose)
  224.    fprintf(stderr,whapwarning);
  225. #endif
  226.  
  227.  if (flagrandom)
  228.    initrandom();
  229.  else
  230.   {
  231.    pos i = ipos2pos(n,min,NODEMAX) + 1;
  232.    bitword q = 1;
  233.    char r = 1;
  234.  
  235.    while (q <= i / 10)
  236.     {
  237.      q *= 10;
  238.      ++r; /* this could overflow! :-) */
  239.     }
  240. #ifndef WHAP
  241.    putchar(25); putchar(1); putchar(2); putchar(2); putchar(1);
  242. #else
  243.    putchar(23); putchar(8); putchar(1); putchar(16);
  244. #endif
  245.    putchar(r);
  246. #ifndef WHAP
  247.    saveout += 6;
  248. #else
  249.    saveout += 5;
  250. #endif
  251.    while (q)
  252.     {
  253.      putchar(48 + (i / q));
  254.      ++saveout;
  255.      i -= (i / q) * q;
  256.      q /= 10;
  257.     }
  258.   }
  259.  
  260.  FIRSTHASH(h,MOD - 1)
  261.  
  262.  
  263. restart:
  264.  
  265.  STATICINIT(n,p,h,max,smax,NODEMAX,MOD - 1)
  266.  
  267.  nextbits = pos2ipos(n,ALPHABET,NODEMAX);
  268.  bits = 8;
  269.  nextreset = 0;
  270.  eff = 0;
  271.  
  272. #ifndef WHAP
  273.  geth[node2ipos(n,topnode(n,NODEMAX),NODEMAX)] = tophash(h,MOD - 1);
  274. #endif
  275.  
  276.  for (ch = 0;ch < ALPHABET;++ch)
  277.   {
  278.    curhash = tophash(h,MOD - 1);
  279.    curhash = hc(curhash,ch,MOD - 1);
  280.    ADD(curhash,topnode(n,NODEMAX),curnode);
  281. #ifndef WHAP
  282.    s[node2ipos(n,curnode,NODEMAX)] = topnode(n,NODEMAX);
  283. #endif
  284.   }
  285.  WASTEMAX(n,p,h,max,smax,curnode); CHECKMAXBITS;
  286.  /* leaving space for the clear code, ALPHABET */
  287.  
  288. #ifndef WHAP
  289.  safenode = ipos2node(n,max,NODEMAX);
  290. #endif
  291.  
  292.  oldnode = topnode(n,NODEMAX);
  293.  oldhash = tophash(h,MOD - 1);
  294.  
  295. #ifndef WHAP
  296.  matchnode = topnode(n,NODEMAX);
  297.  matchhash = tophash(h,MOD - 1);
  298. #else
  299.  lastnode = topnode(n,NODEMAX);
  300.  lasthash = tophash(h,MOD - 1);
  301. #endif
  302.  
  303. #ifdef WHAP
  304.  midhash = lasthash;
  305.  firstmidnode = 0; /* still in tree */
  306. #endif
  307.  
  308.  curbits = bits;
  309.  curmax = max;
  310.  curnextbits = nextbits;
  311.  
  312.  for (;;)
  313.   {
  314.    ch = getchar();
  315.    if (ch == EOF)
  316.     {
  317.      if (flagrandom)
  318.       {
  319.        int b;
  320.  
  321.        if (oldnode != topnode(n,NODEMAX))
  322.      if (bits_out((NUMOF(oldnode) + 1 < SUB(curmax,curnextbits)) &&
  323.                   RANDOMBIT ?
  324.                   (NUMOF(oldnode) + ipos2pos(n,curmax,NODEMAX) + 1) :
  325.               (NUMOF(oldnode))
  326.               ,bits) == EOF)
  327.        PUTERR
  328.        b = RANDOMBIT; b = b + b;
  329.        b += RANDOMBIT; b = b + b; b += RANDOMBIT; b = b + b;
  330.        b += RANDOMBIT; b = b + b; b += RANDOMBIT; b = b + b;
  331.        b += RANDOMBIT; b = b + b; b += RANDOMBIT; b = b + b;
  332.        b += RANDOMBIT;
  333.        if (bit_fillflush(b) == EOF)
  334.      PUTERR
  335.       }
  336.      else
  337.       {
  338.        if (oldnode != topnode(n,NODEMAX))
  339.          if (bits_out(NUMOF(oldnode),bits) == EOF)
  340.        PUTERR
  341.        if (bit_flushbuf() == EOF)
  342.      PUTERR
  343.       }
  344.      savein += numin;
  345.      saveout += bit_numout;
  346.      /* XXX: test for overflow? */
  347.      if (flagverbose >= 2)
  348.        goaheadandbeverbose();
  349.      (void) exit(0);
  350.     }
  351.    numin++;
  352.    for (;;)
  353.     {
  354.      /* We use some tricks to avoid any need for backtracking. */
  355.  
  356. #ifndef WHAP
  357. #define MATCHADD { if (dosnode) { ADD(matchhash,matchnode,oldnode); \
  358. s[node2ipos(n,dosnode,NODEMAX)] = oldnode; dosnode = oldnode; } \
  359. else ADD(matchhash,matchnode,dosnode); \
  360. matchnode = s[node2ipos(n,matchnode,NODEMAX)]; \
  361. matchhash = geth[node2ipos(n,matchnode,NODEMAX)]; \
  362. }
  363.  
  364. /* XXXX: get rid of first if (max != min) ? */
  365. /* XXXX: is the inner DOWNI too slow? */
  366. #define MATCHDOWN if (max != min) { dosnode = 0; \
  367. do { matchhash = hc(matchhash,ch,MOD - 1); \
  368. DOWNI(n,p,h,matchnode,matchhash,oldnode,{break;},MATCHADD) } while(max != min); \
  369. if (dosnode) s[node2ipos(n,dosnode,NODEMAX)] = oldnode; \
  370. matchnode = oldnode; }
  371. /* XXX: Should unroll the loop a bit. */
  372.  
  373. #define SAFEMATCHDOWN { if (curnode > safenode) /*XXX: AARGH!*/ \
  374. { MATCHDOWN break; } }
  375. #endif
  376.  
  377. #ifdef WHAP
  378. #define MIDDOWNF lastnode = firstmidnode; \
  379. WASTEMAX(n,p,h,max,smax,firstmidnode); CHECKMAXBITS; firstmidnode = 0;
  380.  
  381. #define MIDADDF ADD(midhash,0,midnode); firstmidnode = midnode;
  382.  
  383. #define MIDADDM newnode = midnode; ADD(midhash,newnode,midnode);
  384.  
  385. #define MIDDOWN if (max != min) { midhash = hc(midhash,ch,MOD - 1); \
  386. if (!firstmidnode) { \
  387. DOWN(n,p,h,lastnode,midhash,firstmidnode,MIDDOWNF,MIDADDF) \
  388. } else { MIDADDM } }
  389.  
  390. #define SAFEMATCHDOWN { MIDDOWN break; }
  391. #endif
  392.  
  393.      curhash = hc(oldhash,ch,MOD - 1);
  394.      DOWN(n,p,h,oldnode,curhash,curnode,SAFEMATCHDOWN,{;})
  395.  
  396. /* Sheer hell for your optimizer. [grin] */
  397.  
  398.      if (flagrandom)
  399.       {
  400.        if (bits_out((NUMOF(oldnode) + 1 < SUB(curmax,curnextbits)) &&
  401.             RANDOMBIT ?
  402.                     (NUMOF(oldnode) + ipos2pos(n,curmax,NODEMAX) + 1):
  403.             (NUMOF(oldnode))
  404.                 ,curbits) == EOF)
  405.      PUTERR
  406.        curmax = max;
  407.        curnextbits = nextbits;
  408.       }
  409.      else if (bits_out(NUMOF(oldnode),curbits) == EOF)
  410.        PUTERR
  411.  
  412.      curbits = bits;
  413.  
  414. #ifdef WHAP
  415.      if (firstmidnode)
  416.        setparent(p,firstmidnode,lastnode);
  417.      /* hence adding entire tree from neutral down onto lastnode */
  418. #endif
  419.  
  420.      if (max == min)
  421.       {
  422.        if (numin >= nextreset)
  423.     {
  424.      nextreset = numin + resetnum;
  425.      /* XXX: this isn't accurate, we don't know how many bits... */
  426.      if ((eff * ((bit_numout + 2 * bit_bufsize) / 16)) < numin + resetfuzz)
  427.        eff = numin / ((bit_numout + 2 * bit_bufsize) / 16);
  428.      else
  429.       {
  430.        savein += numin;
  431.        saveout += bit_numout;
  432.        /* XXX: test for overflow? */
  433.        numin = 0;
  434.        bit_numout = 0;
  435.  
  436.        if (flagrandom)
  437.         { /*XXX*/
  438.          if (bits_out((ALPHABET + 1 < SUB(max,nextbits)) && RANDOMBIT ?
  439.               (ALPHABET + ipos2pos(n,max,NODEMAX) + 1) :
  440.               ALPHABET,bits) == EOF)
  441.            PUTERR
  442.         }
  443.        else
  444.          if (bits_out(ALPHABET,bits) == EOF)
  445.            PUTERR
  446.  
  447.            CLEARHASH(h,MOD - 1)
  448.  
  449.        (void) ungetc(ch,stdin);
  450.        --savein;
  451.        /* XXX: Shouldn't have this goto at all. */
  452.        goto restart;
  453.       }
  454.     }
  455.       }
  456.      else
  457.       {
  458. #ifndef WHAP
  459.        safenode = ipos2node(n,max,NODEMAX);
  460.        /* if max is min, s's past the old safenode might be out of dict */
  461.        /* so changing safenode here wouldn't be safe */
  462. #else
  463.        lastnode = oldnode;
  464.        lasthash = oldhash;
  465.  
  466.        midhash = lasthash;
  467.  
  468.        firstmidnode = 0;
  469. #endif
  470.       }
  471.      oldnode = topnode(n,NODEMAX);
  472.      oldhash = tophash(h,MOD - 1);
  473.     }
  474.    oldnode = curnode;
  475.    oldhash = curhash;
  476.   }
  477. }
  478.