billr@saab.CNA.TEK.COM (Bill Randle) (12/21/89)
Submitted-by: Dan Bernstein <brnstnd@stealth.acf.nyu.edu>
Posting-number: Volume 8, Issue 75
Archive-name: travesty/Part01
[I tried this on my Sun 3/60 and it compiled and ran, but I'm
not convinced it produced the "correct" output. -br]
#! /bin/sh
# This is a shell archive. Remove anything before this line, then unpack
# it by saving it into a file and typing "sh file". To overwrite existing
# files, type "sh file -c". You can also feed this as standard input via
# unshar, or by typing "sh <file", e.g.. If this archive is complete, you
# will see the following message at the end:
# "End of archive 1 (of 1)."
# Contents: README CHANGES Makefile djbatoi.h djberr.h travesty.c
# travesty.man
# Wrapped by billr@saab on Wed Dec 20 10:07:56 1989
PATH=/bin:/usr/bin:/usr/ucb ; export PATH
if test -f 'README' -a "${1}" != "-c" ; then
echo shar: Will not clobber existing file \"'README'\"
else
echo shar: Extracting \"'README'\" \(717 characters\)
sed "s/^X//" >'README' <<'END_OF_FILE'
Xtravesty - make a travesty of the input
X
Xtravesty version 1.0, 12/17/89.
XCopyright (c) 1989, Daniel J. Bernstein.
XAll rights reserved.
X
XThis distribution packaged 12/17/89.
X
XFiles:
XCHANGES Description of changes since first distributed version
XREADME This document
XMakefile Installation commands
Xtravesty.c The program
Xtravesty.man Documentation
X
XEdit the options in Makefile and type make. travesty will be the
Xexecutable program; travesty.6 will be the nroff'ed documentation.
X
XI don't pretend to know your machine's setup so there's no make install.
X
XRead CHANGES for a list of changes. Type travesty -C and travesty -W
Xfor copyright and warranty information, travesty -H for help.
END_OF_FILE
if test 717 -ne `wc -c <'README'`; then
echo shar: \"'README'\" unpacked with wrong size!
fi
# end of 'README'
fi
if test -f 'CHANGES' -a "${1}" != "-c" ; then
echo shar: Will not clobber existing file \"'CHANGES'\"
else
echo shar: Extracting \"'CHANGES'\" \(32 characters\)
sed "s/^X//" >'CHANGES' <<'END_OF_FILE'
Xtravesty version 1.0, 12/17/89.
END_OF_FILE
if test 32 -ne `wc -c <'CHANGES'`; then
echo shar: \"'CHANGES'\" unpacked with wrong size!
fi
# end of 'CHANGES'
fi
if test -f 'Makefile' -a "${1}" != "-c" ; then
echo shar: Will not clobber existing file \"'Makefile'\"
else
echo shar: Extracting \"'Makefile'\" \(216 characters\)
sed "s/^X//" >'Makefile' <<'END_OF_FILE'
XCCOPTS=-O
XNROFFOPTS=-man
X
Xdefault: all
X
Xall: travesty travesty.6
X
Xtravesty: travesty.c Makefile
X cc $(CCOPTS) -o travesty travesty.c
X
Xtravesty.6: travesty.man Makefile
X nroff $(NROFFOPTS) < travesty.man > travesty.6
END_OF_FILE
if test 216 -ne `wc -c <'Makefile'`; then
echo shar: \"'Makefile'\" unpacked with wrong size!
fi
# end of 'Makefile'
fi
if test -f 'djbatoi.h' -a "${1}" != "-c" ; then
echo shar: Will not clobber existing file \"'djbatoi.h'\"
else
echo shar: Extracting \"'djbatoi.h'\" \(381 characters\)
sed "s/^X//" >'djbatoi.h' <<'END_OF_FILE'
X/* djbatoi.h, 11/1/89. */
X
X#ifndef __DJBATOIH_
X#define __DJBATOIH_
X
X/* some stupid versions of atoi() crash (!) on nulls */
Xint dummyatoi;
X#define atoi(s) ( ( dummyatoi = 0 ), \
X ( sscanf(s,"%d",&dummyatoi) || ( dummyatoi = 0 ) ), \
X dummyatoi )
Xlong dummyatol;
X#define atol(s) ( ( dummyatol = 0 ), \
X ( sscanf(s,"%D",&dummyatol) || ( dummyatol = 0 ) ), \
X dummyatol )
X
X#endif
END_OF_FILE
if test 381 -ne `wc -c <'djbatoi.h'`; then
echo shar: \"'djbatoi.h'\" unpacked with wrong size!
fi
# end of 'djbatoi.h'
fi
if test -f 'djberr.h' -a "${1}" != "-c" ; then
echo shar: Will not clobber existing file \"'djberr.h'\"
else
echo shar: Extracting \"'djberr.h'\" \(491 characters\)
sed "s/^X//" >'djberr.h' <<'END_OF_FILE'
X/* djberr.h, 11/1/89. */
X
X#ifndef __DJBERRH_
X#define __DJBERRH_
X
Xextern int errno;
X
X#define errn(s) (((void) fputs(s,stderr)), putc('\n',stderr))
X#define err(s) (fputs(s,stderr))
X#define errn2(s,t) (((void) fprintf(stderr,s,t)), putc('\n',stderr))
X#define errn3(s,t,u) (((void) fprintf(stderr,s,t,u)), putc('\n',stderr))
X#define perrn2(s,t) { int dummyerrno = errno; (void) fprintf(stderr,s,t); \
X (void) fputs(": ",stderr); errno = dummyerrno; \
X (void) perror(""); }
X
X#endif
END_OF_FILE
if test 491 -ne `wc -c <'djberr.h'`; then
echo shar: \"'djberr.h'\" unpacked with wrong size!
fi
# end of 'djberr.h'
fi
if test -f 'travesty.c' -a "${1}" != "-c" ; then
echo shar: Will not clobber existing file \"'travesty.c'\"
else
echo shar: Extracting \"'travesty.c'\" \(8144 characters\)
sed "s/^X//" >'travesty.c' <<'END_OF_FILE'
X/*
Xtravesty.c: make a travesty of a file
X*/
X
Xstatic char travestyauthor[] =
X"travesty was written by Daniel J. Bernstein.\n\
XInternet address: brnstnd@acf10.nyu.edu.\n";
X
Xstatic char travestyversion[] =
X"travesty version 1.0, 12/17/89.\n\
XCopyright (c) 1989, Daniel J. Bernstein.\n\
XAll rights reserved.\n";
X
Xstatic char travestycopyright[] =
X"travesty version 1.0, 12/17/89.\n\
XCopyright (c) 1989, Daniel J. Bernstein.\n\
XAll rights reserved.\n\
X\n\
XUntil January 1, 1993, you are granted the following rights: A. To make\n\
Xcopies of this work in original form, so long as (1) the copies are exact\n\
Xand complete; (2) the copies include the copyright notice, this paragraph,\n\
Xand the disclaimer of warranty in their entirety. B. To distribute this\n\
Xwork, or copies made under the provisions above, so long as (1) this is\n\
Xthe original work and not a derivative form; (2) you do not charge a fee\n\
Xfor copying or for distribution; (3) you ensure that the distributed form\n\
Xincludes the copyright notice, this paragraph, and the disclaimer of\n\
Xwarranty in their entirety. These rights are temporary and revocable upon\n\
Xwritten, oral, or other notice by Daniel J. Bernstein. These rights are\n\
Xautomatically revoked on January 1, 1993. This copyright notice shall be\n\
Xgoverned by the laws of the state of New York.\n\
X\n\
XIf you have questions about travesty or about this copyright notice,\n\
Xor if you would like additional rights beyond those granted above,\n\
Xplease feel free to contact the author at brnstnd@acf10.nyu.edu\n\
Xon the Internet.\n";
X
Xstatic char travestywarranty[] =
X"To the extent permitted by applicable law, Daniel J. Bernstein disclaims\n\
Xall warranties, explicit or implied, including but not limited to the\n\
Ximplied warranties of merchantability and fitness for a particular purpose.\n\
XDaniel J. Bernstein is not and shall not be liable for any damages,\n\
Xincidental or consequential, arising from the use of this program, even\n\
Xif you inform him of the possibility of such damages. This disclaimer\n\
Xshall be governed by the laws of the state of New York.\n\
X\n\
XIn other words, use this program at your own risk.\n\
X\n\
XIf you have questions about travesty or about this disclaimer of warranty,\n\
Xplease feel free to contact the author at brnstnd@acf10.nyu.edu\n\
Xon the Internet.\n";
X
Xstatic char travestyusage[] =
X"Usage: travesty [ -oord ] [ -nnum ] [ -rrand ] [ -sS ] [ -ACHUVW ]\n\
XHelp: travesty -H\n";
X
Xstatic char travestyhelp[] =
X"travesty makes a travesty of its input.\n\
X\n\
Xtravesty -A: print authorship notice\n\
Xtravesty -C: print copyright notice\n\
Xtravesty -H: print this notice\n\
Xtravesty -U: print short usage summary\n\
Xtravesty -V: print version number\n\
Xtravesty -W: print disclaimer of warranty\n\
X\n\
Xtravesty [ -oord ] [ -nnum ] [ -rrand ] [ -sS ]: let the monkeys bang away\n\
X -oord: use an order-ord Markov process (default 5, limit 20)\n\
X -nnum: generate num output characters (default 0, meaning forever)\n\
X -rrand: use rand as the random number generator seed (default based on time)\n\
X -s: start output same as input\n\
X -S: start output at a random spot in input (default)\n\
X\n\
Xtravesty will respond to an ALRM signal by printing its random seed on stderr.\n\
X\n\
XIf you have questions about or suggestions for travesty, please feel free\n\
Xto contact the author, Daniel J. Bernstein, at brnstnd@acf10.nyu.edu\n\
Xon the Internet.\n";
X
X#include <stdio.h>
X#include <signal.h>
X#include <sys/time.h>
Xextern int getopt();
Xextern char *optarg; /* these should be in getopt.h! */
Xextern int optind;
Xextern char *malloc();
Xextern char *realloc();
Xlong random();
X#include "djberr.h"
X#include "djbatoi.h"
X
X/* The following macro had better make chars into ints from 0 thru 255. */
X
X#define ctoi(x) ((unsigned int) (x))
X#define copy(s,t,len) bcopy(s,t,len)
X#define cmp(s,t,len) bcmp(s,t,len) /* had better return signed value! */
X
X#define ran(n) (((random() % n) + n) % n) /* idiotic % can be negative */
X
X#define MAXORD 20
X
Xint flagstart = 0;
Xint numout = 0;
Xint ord = 5;
Xint ord1;
Xint seed;
X
Xint s[MAXORD + 1][257];
Xchar *c;
Xint curc;
Xint *p;
Xint *q;
Xint last;
Xint m;
Xint len;
X
Xinitp()
X{
X register int i;
X
X for (i = 0;i < len;i++)
X p[i] = i;
X}
X
Xrearrange()
X{
X register int i,j,k;
X register char t[MAXORD + 1];
X
X for (i = 0;i < len;i++)
X if (i != p[i])
X {
X copy(c + (j = i) * ord1,t,ord1);
X do
X {
X k = p[j];
X copy(c + k * ord1,c + j * ord1,ord1);
X p[j] = j;
X j = k;
X }
X while (p[j] != i);
X copy(t,c + j * ord1,ord1);
X p[j] = j;
X }
X}
X
Xsort(l,u,m)
Xregister int l,u; /* we are useless if l == u; we crash if l > u */
Xregister int m;
X{
X register int i;
X register int ch;
X
X if (m > ord)
X return;
X
X for (ch = 0; ch < 256; ch++)
X s[m][ch] = 0;
X
X for (i = l; i <= u; i++)
X s[m][ctoi(c[p[i] * ord1 + m])]++;
X
X s[m][0] += l - 1;
X for (ch = 1; ch < 256; ch++)
X s[m][ch] += s[m][ch - 1];
X
X for (i = u; i >= l; i--)
X q[s[m][ctoi(c[p[i] * ord1 + m])]--] = p[i]; /* trust me. */
X
X for (i = l; i <= u; i++)
X p[i] = q[i];
X
X s[m][256] = u;
X for (ch = 0; ch < 256; ch++)
X if (s[m][ch] + 1 < s[m][ch + 1]) /* anything to save a procedure call */
X sort(s[m][ch] + 1,s[m][ch + 1],m + 1);
X}
X
Xzeroq()
X{
X register int i;
X
X for (i = 0; i < len; i++)
X q[i] = 0;
X}
X
Xsigalrm()
X{
X fprintf(stderr,"Seed: %d\n",seed);
X fflush(stderr);
X}
X
Xmain(argc,argv,envp)
Xint argc;
Xchar *argv[];
Xchar *envp[];
X{
X register int opt;
X register int l, u, i;
X register int num;
X register int ch;
X struct timeval tv;
X
X (void) gettimeofday(&tv,NULL); /* if it fails, oh well */
X seed = tv.tv_sec + tv.tv_usec;
X
X while ((opt = getopt(argc,argv,"ACHUVWsSr:n:o:")) != EOF)
X switch(opt)
X {
X case 'A': (void) err(travestyauthor); exit(1);
X case 'C': (void) err(travestycopyright); exit(1);
X case 'H': (void) err(travestyhelp); exit(1);
X case 'U': (void) err(travestyusage); exit(1);
X case 'V': (void) err(travestyversion); exit(1);
X case 'W': (void) err(travestywarranty); exit(1);
X case '?': (void) err(travestyusage); exit(1);
X case 's': flagstart = 1; break;
X case 'S': flagstart = 0; break;
X case 'r': seed = atoi(optarg); break;
X case 'n': numout = atoi(optarg); break;
X case 'o': ord = atoi(optarg); break;
X }
X argv += optind, argc -= optind;
X
X if (ord < 1) ord = 1;
X if (ord > MAXORD) ord = MAXORD;
X ord1 = ord + 1;
X
X srandom(seed);
X (void) signal(SIGALRM,sigalrm);
X
X /* read in characters */
X curc = 1024;
X if ((c = malloc(ord1 * curc)) == NULL)
X {
X errn("travesty: fatal: input too big");
X exit(1);
X }
X
X for (len = 0;(ch = getchar()) != EOF;len++)
X {
X if (len >= curc)
X {
X curc += 1024;
X if ((c = realloc(c,ord1 * curc)) == NULL)
X {
X errn("travesty: fatal: input too big");
X exit(1);
X }
X }
X c[len * ord1] = ch;
X }
X
X if (len == 0)
X {
X exit(0); /* the travesty of emptiness is emptiness... right? */
X }
X
X for (i = 0; i < len; i++)
X for (m = 0; m < ord; m++)
X c[((i + (m + 1) * (len - 1)) % len) * ord1 + m + 1] = c[i * ord1];
X
X p = (int *) malloc(sizeof(int) * len);
X q = (int *) malloc(sizeof(int) * len);
X if ((p == NULL) || (q == NULL))
X {
X errn("travesty: fatal: input too big");
X exit(1);
X }
X
X initp(); /* here p is pointer array for sorting c, q is temp p */
X sort(0,len - 1,0);
X rearrange();
X
X zeroq(); /* from now on p and q are start and length from old searches */
X
X if (flagstart)
X last = 0;
X else
X last = ran(len);
X
X if ((numout) && (numout <= ord))
X ord = numout - 1; /* stupid but does the trick */
X
X for (m = 0; m <= ord; m++)
X putchar(c[last * ord1 + m]);
X
X for (num = ord1; (!numout) || (num < numout); num++)
X {
X if (!q[last])
X {
X l = 0; u = len - 1;
X while (u > l)
X if (cmp(c + last * ord1 + 1,c + (i = (u + l)/2) * ord1,ord) > 0)
X l = i + 1;
X else
X u = i;
X p[last] = l;
X u = len - 1;
X while (u > l)
X if (cmp(c + last * ord1 + 1,c + (i = (u + l + 1)/2) * ord1,ord) < 0)
X u = i - 1;
X else
X l = i;
X q[last] = u - p[last] + 1;
X }
X last = p[last] + ran(q[last]);
X putchar(c[last * ord1 + ord]);
X }
X
X exit(0);
X}
END_OF_FILE
if test 8144 -ne `wc -c <'travesty.c'`; then
echo shar: \"'travesty.c'\" unpacked with wrong size!
fi
# end of 'travesty.c'
fi
if test -f 'travesty.man' -a "${1}" != "-c" ; then
echo shar: Will not clobber existing file \"'travesty.man'\"
else
echo shar: Extracting \"'travesty.man'\" \(2466 characters\)
sed "s/^X//" >'travesty.man' <<'END_OF_FILE'
X.TH travesty 6
X.SH NAME
Xtravesty \- make a travesty of the input
X.SH SYNTAX
Xtravesty
X[
X\fB\-n\fInum
X] [
X\fB\-o\fIord
X] [
X\fB\-r\fIrand
X] [
X\fB\-sS\fI
X] [
X\fB\-ACHUVW\fI
X]
X.SH DESCRIPTION
X.I travesty
Xmakes a travesty of its input:
Xit outputs a random stream of characters by
Xa Markov process of some order with frequencies
Xtaken from the input text. In other words,
Xit produces output with the same distribution as the input
Xof letters, pairs of letters, and so on up
Xto the order.
X.PP
XThis implementation of
X.I travesty
Xis very, very fast.
XFor an order
X.I ord
Xprocess on an input file of length
X.I len,
Xit uses approximately
X.I ord*len
Xspace,
X.I ord*len
Xtime to read and process the input,
Xand at most
X.I ord*\fBlog\fI(len)
Xtime for each output character.
XAs it produces more output it becomes even more efficient;
Xafter a while it produces each character in constant time!
X.PP
XOptions
X.B ACHUVW
Xprint the authorship notice,
Xcopyright notice,
Xhelp notice,
Xshort usage summary,
Xversion number,
Xand warranty information respectively.
X.PP
X.I travesty
Xhas a few flags:
X.TP 12
X\fB\-n\fInum
XOutput
X.I num
Xcharacters (default 0, meaning forever).
XRemember that this
X.I travesty
Xis very fast:
Xyou can't just watch characters pop up one by one.
X.TP
X\fB\-o\fIord
XUse a process of order
X.I ord;
Xin other words, choose each character based on the
X.I ord
Xcharacters preceding it.
XHigh orders (15 or so) almost always just reproduce the input text.
XOrders 3 through 8 seem to be the most interesting,
Xdepending on the size of the input.
XThe default order is 5.
X.TP
X\fB\-s\fI
XStart the output with the same characters as the input.
X.TP
X\fB\-S\fI
XStart the output at a random spot in the input (default).
XNote that
X.I travesty
Xtakes the input text to be
Xwrapped around from the end to the beginning.
X.TP
X\fB\-r\fIrand
XSet a particular integer seed for the random number generator.
XIf you do not specify
X.I\-r,
X.I travesty
Xwill choose a seed based on the current time.
XIt will print the seed on standard error if it
Xreceives an ALRM signal.
X.PP
X.SH DIAGNOSTICS
X.TP
X.I fatal: input too big
X.I travesty
Xdoes not have enough memory to handle the input.
X.SH RESTRICTIONS
X.I travesty
Xcannot deal with ridiculously high orders
Xor inputs that cannot fit into memory.
X.SH BUGS
XNone known.
X.SH MACHINES
X.I travesty
Xhas been tested
Xon an Astronautics ZS-2 running ZSUnix.
X.SH VERSION
Xtravesty version 1.0, dated 12/17/89.
X.SH AUTHOR
XCopyright 1989, Daniel J. Bernstein.
X.SH "SEE ALSO"
Xkill(1)
END_OF_FILE
if test 2466 -ne `wc -c <'travesty.man'`; then
echo shar: \"'travesty.man'\" unpacked with wrong size!
fi
# end of 'travesty.man'
fi
echo shar: End of archive 1 \(of 1\).
cp /dev/null ark1isdone
MISSING=""
for I in 1 ; do
if test ! -f ark${I}isdone ; then
MISSING="${MISSING} ${I}"
fi
done
if test "${MISSING}" = "" ; then
echo You have the archive.
rm -f ark[1-9]isdone
else
echo You still need to unpack the following archives:
echo " " ${MISSING}
fi
## End of shell archive.
exit 0