home *** CD-ROM | disk | FTP | other *** search
/ Usenet 1994 October / usenetsourcesnewsgroupsinfomagicoctober1994disk2.iso / games / volume8 / travesty / part01 / travesty.c < prev    next >
C/C++ Source or Header  |  1989-12-20  |  8KB  |  312 lines
  1. /*
  2. travesty.c: make a travesty of a file
  3. */
  4.  
  5. static char travestyauthor[] =
  6. "travesty was written by Daniel J. Bernstein.\n\
  7. Internet address: brnstnd@acf10.nyu.edu.\n";
  8.  
  9. static char travestyversion[] = 
  10. "travesty version 1.0, 12/17/89.\n\
  11. Copyright (c) 1989, Daniel J. Bernstein.\n\
  12. All rights reserved.\n";
  13.  
  14. static char travestycopyright[] =
  15. "travesty version 1.0, 12/17/89.\n\
  16. Copyright (c) 1989, Daniel J. Bernstein.\n\
  17. All rights reserved.\n\
  18. \n\
  19. Until January 1, 1993, you are granted the following rights: A. To make\n\
  20. copies of this work in original form, so long as (1) the copies are exact\n\
  21. and complete; (2) the copies include the copyright notice, this paragraph,\n\
  22. and the disclaimer of warranty in their entirety. B. To distribute this\n\
  23. work, or copies made under the provisions above, so long as (1) this is\n\
  24. the original work and not a derivative form; (2) you do not charge a fee\n\
  25. for copying or for distribution; (3) you ensure that the distributed form\n\
  26. includes the copyright notice, this paragraph, and the disclaimer of\n\
  27. warranty in their entirety. These rights are temporary and revocable upon\n\
  28. written, oral, or other notice by Daniel J. Bernstein. These rights are\n\
  29. automatically revoked on January 1, 1993. This copyright notice shall be\n\
  30. governed by the laws of the state of New York.\n\
  31. \n\
  32. If you have questions about travesty or about this copyright notice,\n\
  33. or if you would like additional rights beyond those granted above,\n\
  34. please feel free to contact the author at brnstnd@acf10.nyu.edu\n\
  35. on the Internet.\n";
  36.  
  37. static char travestywarranty[] =
  38. "To the extent permitted by applicable law, Daniel J. Bernstein disclaims\n\
  39. all warranties, explicit or implied, including but not limited to the\n\
  40. implied warranties of merchantability and fitness for a particular purpose.\n\
  41. Daniel J. Bernstein is not and shall not be liable for any damages,\n\
  42. incidental or consequential, arising from the use of this program, even\n\
  43. if you inform him of the possibility of such damages. This disclaimer\n\
  44. shall be governed by the laws of the state of New York.\n\
  45. \n\
  46. In other words, use this program at your own risk.\n\
  47. \n\
  48. If you have questions about travesty or about this disclaimer of warranty,\n\
  49. please feel free to contact the author at brnstnd@acf10.nyu.edu\n\
  50. on the Internet.\n";
  51.  
  52. static char travestyusage[] =
  53. "Usage: travesty [ -oord ] [ -nnum ] [ -rrand ] [ -sS ] [ -ACHUVW ]\n\
  54. Help:  travesty -H\n";
  55.  
  56. static char travestyhelp[] =
  57. "travesty makes a travesty of its input.\n\
  58. \n\
  59. travesty -A: print authorship notice\n\
  60. travesty -C: print copyright notice\n\
  61. travesty -H: print this notice\n\
  62. travesty -U: print short usage summary\n\
  63. travesty -V: print version number\n\
  64. travesty -W: print disclaimer of warranty\n\
  65. \n\
  66. travesty [ -oord ] [ -nnum ] [ -rrand ] [ -sS ]: let the monkeys bang away\n\
  67.   -oord: use an order-ord Markov process (default 5, limit 20)\n\
  68.   -nnum: generate num output characters (default 0, meaning forever)\n\
  69.   -rrand: use rand as the random number generator seed (default based on time)\n\
  70.   -s: start output same as input\n\
  71.   -S: start output at a random spot in input (default)\n\
  72. \n\
  73. travesty will respond to an ALRM signal by printing its random seed on stderr.\n\
  74. \n\
  75. If you have questions about or suggestions for travesty, please feel free\n\
  76. to contact the author, Daniel J. Bernstein, at brnstnd@acf10.nyu.edu\n\
  77. on the Internet.\n";
  78.  
  79. #include <stdio.h>
  80. #include <signal.h>
  81. #include <sys/time.h>
  82. extern int getopt();
  83. extern char *optarg; /* these should be in getopt.h! */
  84. extern int optind;
  85. extern char *malloc();
  86. extern char *realloc();
  87. long random();
  88. #include "djberr.h"
  89. #include "djbatoi.h"
  90.  
  91. /* The following macro had better make chars into ints from 0 thru 255. */
  92.  
  93. #define ctoi(x) ((unsigned int) (x))
  94. #define copy(s,t,len) bcopy(s,t,len)
  95. #define cmp(s,t,len) bcmp(s,t,len) /* had better return signed value! */
  96.  
  97. #define ran(n) (((random() % n) + n) % n) /* idiotic % can be negative */
  98.  
  99. #define MAXORD 20
  100.  
  101. int flagstart = 0;
  102. int numout = 0;
  103. int ord = 5;
  104. int ord1;
  105. int seed;
  106.  
  107. int s[MAXORD + 1][257];
  108. char *c;
  109. int curc;
  110. int *p;
  111. int *q;
  112. int last;
  113. int m;
  114. int len;
  115.  
  116. initp()
  117. {
  118.  register int i;
  119.  
  120.  for (i = 0;i < len;i++)
  121.    p[i] = i;
  122. }
  123.  
  124. rearrange()
  125. {
  126.  register int i,j,k;
  127.  register char t[MAXORD + 1];
  128.  
  129.  for (i = 0;i < len;i++)
  130.    if (i != p[i])
  131.     {
  132.      copy(c + (j = i) * ord1,t,ord1);
  133.      do
  134.       {
  135.        k = p[j];
  136.        copy(c + k * ord1,c + j * ord1,ord1);
  137.        p[j] = j;
  138.        j = k;
  139.       }
  140.      while (p[j] != i);
  141.      copy(t,c + j * ord1,ord1);
  142.      p[j] = j;
  143.     }
  144. }
  145.  
  146. sort(l,u,m)
  147. register int l,u; /* we are useless if l == u; we crash if l > u */
  148. register int m;
  149. {
  150.  register int i;
  151.  register int ch;
  152.  
  153.  if (m > ord)
  154.    return;
  155.  
  156.  for (ch = 0; ch < 256; ch++)
  157.    s[m][ch] = 0;
  158.  
  159.  for (i = l; i <= u; i++)
  160.    s[m][ctoi(c[p[i] * ord1 + m])]++;
  161.  
  162.  s[m][0] += l - 1;
  163.  for (ch = 1; ch < 256; ch++)
  164.    s[m][ch] += s[m][ch - 1];
  165.  
  166.  for (i = u; i >= l; i--)
  167.    q[s[m][ctoi(c[p[i] * ord1 + m])]--] = p[i]; /* trust me. */
  168.  
  169.  for (i = l; i <= u; i++)
  170.    p[i] = q[i];
  171.  
  172.  s[m][256] = u;
  173.  for (ch = 0; ch < 256; ch++)
  174.    if (s[m][ch] + 1 < s[m][ch + 1]) /* anything to save a procedure call */
  175.      sort(s[m][ch] + 1,s[m][ch + 1],m + 1);
  176. }
  177.  
  178. zeroq()
  179. {
  180.  register int i;
  181.  
  182.  for (i = 0; i < len; i++)
  183.    q[i] = 0;
  184. }
  185.  
  186. sigalrm()
  187. {
  188.  fprintf(stderr,"Seed: %d\n",seed);
  189.  fflush(stderr);
  190. }
  191.  
  192. main(argc,argv,envp)
  193. int argc;
  194. char *argv[];
  195. char *envp[];
  196. {
  197.  register int opt;
  198.  register int l, u, i;
  199.  register int num;
  200.  register int ch;
  201.  struct timeval tv;
  202.  
  203.  (void) gettimeofday(&tv,NULL); /* if it fails, oh well */
  204.  seed = tv.tv_sec + tv.tv_usec;
  205.  
  206.  while ((opt = getopt(argc,argv,"ACHUVWsSr:n:o:")) != EOF)
  207.    switch(opt)
  208.     {
  209.      case 'A': (void) err(travestyauthor); exit(1);
  210.      case 'C': (void) err(travestycopyright); exit(1);
  211.      case 'H': (void) err(travestyhelp); exit(1);
  212.      case 'U': (void) err(travestyusage); exit(1);
  213.      case 'V': (void) err(travestyversion); exit(1);
  214.      case 'W': (void) err(travestywarranty); exit(1);
  215.      case '?': (void) err(travestyusage); exit(1);
  216.      case 's': flagstart = 1; break;
  217.      case 'S': flagstart = 0; break;
  218.      case 'r': seed = atoi(optarg); break;
  219.      case 'n': numout = atoi(optarg); break;
  220.      case 'o': ord = atoi(optarg); break;
  221.     }
  222.  argv += optind, argc -= optind;
  223.  
  224.  if (ord < 1) ord = 1;
  225.  if (ord > MAXORD) ord = MAXORD;
  226.  ord1 = ord + 1;
  227.  
  228.  srandom(seed);
  229.  (void) signal(SIGALRM,sigalrm);
  230.  
  231.  /* read in characters */
  232.  curc = 1024;
  233.  if ((c = malloc(ord1 * curc)) == NULL)
  234.   {
  235.    errn("travesty: fatal: input too big");
  236.    exit(1);
  237.   }
  238.  
  239.  for (len = 0;(ch = getchar()) != EOF;len++)
  240.   {
  241.    if (len >= curc)
  242.     {
  243.      curc += 1024;
  244.      if ((c = realloc(c,ord1 * curc)) == NULL)
  245.       {
  246.        errn("travesty: fatal: input too big");
  247.        exit(1);
  248.       }
  249.     }
  250.    c[len * ord1] = ch;
  251.   }
  252.  
  253.  if (len == 0)
  254.   {
  255.    exit(0); /* the travesty of emptiness is emptiness... right? */
  256.   }
  257.  
  258.  for (i = 0; i < len; i++)
  259.    for (m = 0; m < ord; m++)
  260.      c[((i + (m + 1) * (len - 1)) % len) * ord1 + m + 1] = c[i * ord1];
  261.  
  262.  p = (int *) malloc(sizeof(int) * len);
  263.  q = (int *) malloc(sizeof(int) * len);
  264.  if ((p == NULL) || (q == NULL))
  265.   {
  266.    errn("travesty: fatal: input too big");
  267.    exit(1);
  268.   }
  269.  
  270.  initp(); /* here p is pointer array for sorting c, q is temp p */
  271.  sort(0,len - 1,0);
  272.  rearrange();
  273.  
  274.  zeroq(); /* from now on p and q are start and length from old searches */
  275.  
  276.  if (flagstart)
  277.    last = 0;
  278.  else
  279.    last = ran(len);
  280.  
  281.  if ((numout) && (numout <= ord))
  282.    ord = numout - 1; /* stupid but does the trick */
  283.  
  284.  for (m = 0; m <= ord; m++)
  285.    putchar(c[last * ord1 + m]);
  286.  
  287.  for (num = ord1; (!numout) || (num < numout); num++)
  288.   {
  289.    if (!q[last])
  290.     {
  291.      l = 0; u = len - 1;
  292.      while (u > l)
  293.        if (cmp(c + last * ord1 + 1,c + (i = (u + l)/2) * ord1,ord) > 0)
  294.      l = i + 1;
  295.        else
  296.      u = i;
  297.      p[last] = l;
  298.      u = len - 1;
  299.      while (u > l)
  300.        if (cmp(c + last * ord1 + 1,c + (i = (u + l + 1)/2) * ord1,ord) < 0)
  301.      u = i - 1;
  302.        else
  303.      l = i;
  304.      q[last] = u - p[last] + 1;
  305.     }
  306.    last = p[last] + ran(q[last]);
  307.    putchar(c[last * ord1 + ord]);
  308.   }
  309.  
  310.  exit(0);
  311. }
  312.