Source Code 1994 March/Source_Code_CD-ROM_Walnut_Creek_March_1994.iso/compsrcs/misc/volume30/life/part01

Text File | 1992-06-20 | 11.2 KB | 340 lines

Newsgroups: comp.sources.misc
From: [e-mail] (Don Hatch)
Subject:  v30i078:  life - fast pixel-level life for b&w Sun screen, Part01/01
Message-ID: <[e-mail]>
X-Md4-Signature: 9ce19ce6fec727dbfebadc6a2fcf9e8e
Date: Sun, 21 Jun 1992 04:18:24 GMT
Approved: [e-mail]

Submitted-by: [e-mail] (Don Hatch)
Posting-number: Volume 30, Issue 78
Archive-name: life/part01
Environment: SUNOS

Conway's game of life on a torus, for a black&white Sun screen (/dev/bwtwo0).
Uses a very clever method of calculating 32 positions at once.
I don't know who invented it, but Lew Hitchner gave it as an assignment
in his Computer Architecture course at UCSC.
I optimized it as much as I could, so even I don't understand it any more.

On a sparc (compiled with -O) it gives about 6.8 frames per second
full screen, and proportionately faster on smaller regions.

:================================ CUT HERE ====================================
: 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".  If this archive is complete, you
: will see the following message at the end:
:               "End of shell archive."
: Contents:
:     life.c
: Archive created Mon Jun 15 03:39:05 PDT 1992  by  [e-mail]

PATH=/bin:/usr/bin:/usr/ucb ; export PATH
if test -f life.c -a "${1}" != "-c" ; then
  echo shar: Will not clobber existing file \"life.c\"
else
echo x - life.c
sed 's/^X//' > life.c <<'+END+OF+life.c'
X/*
X * life.c
X *
X * Conway's game of life on a torus, for a black&white Sun screen (/dev/bwtwo0).
X * Uses a very clever method of calculating 32 positions at once.
X * I don't know who invented it, but Lew Hitchner gave it as an assignment
X * in his Computer Architecture course at UCSC.
X * I optimized it as much as I could, so even I don't understand it any more.
X *
X * On a sparc (compiled with -O) it gives about 6.8 frames per second
X * full screen, and proportionately faster on smaller regions.
X *
X * Usage: life [-i] [<x> <y> <w> <h>]
X *    x is rounded down to a multiple of 32,
X *    w is rounded up to a multiple of 32.
X *    Default is the full screen.
X *
X * The -i option makes it incorporate externally generated screen changes
X * (such as cursor movement and clock refreshes) into the calculations,
X * but it runs about half as fast.
X *
X * Environment options:
X *      LIFETIMES --    If set and nonnegative, program exits after
X *                      this many generations
X *      LIFE_USEC --    If set and positive, the program pauses between
X *                      generations if necessary so that each generation
X *                      takes at least this many microseconds
X *      LIFE_FB --      Name of frame buffer device (default is /dev/bwtwo0)
X *      LIFE_OFF --     Offset into frame buffer device (default is 0)
X *
X * Compiling notes:
X *      Default is white life on black background, assuming the frame buffer
X *      uses 1 for black and 0 for white.
X *      If you want it to be black on white, xor your frame buffer
X *      does it the opposite way,
X *      compile with: (cut and paste the following line)
X                cc -O -DBLACK_ON_WHITE life.c -o life
X *      otherwise just say
X                cc -O life.c -o life
X *
X * Author: Don Hatch ([e-mail])
X * Last modified: Mon Jun  8 17:01:13 PDT 1992
X *
X * This program may be distributed freely.
X * If you like it, please send me money or give me a job.
X * Comments and suggestions are welcome regardless.
X */
X
X#include <stdio.h>
X#include <stdlib.h>
X#include <signal.h>
X#include <sys/time.h>
X#include <sys/mman.h>
X#include <fcntl.h>
X#include <pixrect/pixrect_hs.h>
X
X#define SIZEX BW2SIZEX
X#define SIZEY BW2SIZEY
X
X#define LIFE_FB "/dev/bwtwo0"
X
X
X#define ADD21(B1,B0, x) \
X       (carry = (x), \
X        B0 ^= carry, \
X        carry &=~ B0, \
X        B1 ^= carry)
X#define ADD31(B2,B1,B0, x) \
X       (ADD21(B1,B0, x), \
X        carry &=~ B1, \
X        B2 ^= carry)
X#define ADD32(B2,B1,B0, X1,X0) \
X       (ADD21(B2,B1, X1), \
X        ADD31(B2,B1,B0, X0))
X
X#ifdef BLACK_ON_WHITE
X#define RESULT(B2,B1,B0,self) (((B2)^(B1)) & ((B2)^(B0)) & ((B0)|(self)))
X#else
X#define RESULT(B2,B1,B0,self) (~(B2) | (~(B1)^(B0)) | (~(B1) & (self)))
X#endif
X
X#define SET21(T1,T0, F0)        SET22(T1,T0, 0, F0)
X#define SET22(T1,T0, F1,F0)     ((T1)=(F1), (T0)=(F0))
X#define SET32(T2,T1,T0, F1,F0)  ((T2)=0, (T1)=(F1), (T0)=(F0))
X#define SUMleftmidright(B1,B0, l,m,r) \
X       (SET21(B1,B0, tmp=(m)), \
X        ADD21(B1,B0, (tmp>>1)|((l)<<31)), \
X        ADD21(B1,B0, (tmp<<1)|((r)>>31)))
X
X#define SWAP(a,b) {u_int (*_temp_)[SIZEX/32] = (a); (a) = (b); (b) = _temp_;}
X
X
X
X
X/* VARARGS */
Xlife(src, dst, h, w, i, j)
Xu_int src[][SIZEX/32];
Xregister u_int dst[][SIZEX/32];
Xregister int h, w;
Xregister int i, j;              /* really local variables */
X{
X    register u_int SUM2,SUM1,SUM0,carry, tmp;
X    register u_int *rightcol, *leftcol, *midcol;
X
X    /*
X     * These probably won't get registers, but that's okay
X     */
X    register u_int BOT1,BOT0;
X    register u_int MID1,MID0;
X    register u_int TOP1,TOP0;
X    register u_int VERYTOP1,VERYTOP0;
X
X    for (j = 0; j < w; ++j) {
X        leftcol =  &src[h-1][(j-1+w)%w];
X        midcol =   &src[h-1][j];
X        rightcol = &src[h-1][(j+1)%w];
X        SUMleftmidright(SUM1,SUM0, *leftcol, *midcol, *rightcol);
X        SET22(TOP1, TOP0, SUM1, SUM0);
X        leftcol =  &src[0][(j-1+w)%w];
X        midcol =   &src[0][j];
X        rightcol = &src[0][(j+1)%w];
X        SUMleftmidright(SUM1,SUM0, *leftcol, *midcol, *rightcol);
X        SET22(MID1, MID0, VERYTOP1=SUM1, VERYTOP0=SUM0);
X        for (i = 0; i < h-1; ++i) {
X            leftcol += SIZEX/32;
X            midcol += SIZEX/32;
X            rightcol += SIZEX/32;
X            SUMleftmidright(SUM1,SUM0, *leftcol, *midcol, *rightcol);
X            SET22(BOT1, BOT0, SUM1, SUM0);
X            SUM2=0;
X            ADD32(SUM2,SUM1,SUM0, MID1, MID0);
X            ADD32(SUM2,SUM1,SUM0, TOP1, TOP0);
X            dst[i][j] = RESULT(SUM2,SUM1,SUM0, src[i][j]);
X            SET22(TOP1,TOP0, MID1,MID0);
X            SET22(MID1,MID0, BOT1,BOT0);
X        }
X        SET32(SUM2,SUM1,SUM0, VERYTOP1,VERYTOP0);
X        ADD32(SUM2,SUM1,SUM0, MID1, MID0);
X        ADD32(SUM2,SUM1,SUM0, TOP1, TOP0);
X        dst[i][j] = RESULT(SUM2,SUM1,SUM0, src[i][j]);
X    }
X}
X
X/* VARARGS */
Xcopy(src, dst, h, w)
Xregister u_int src[][SIZEX/32];
Xregister u_int dst[][SIZEX/32];
Xregister int h, w;
X{
X    register int i, j;
X    for (i = 0; i < h; ++i) {
X        for (j = 0; j < w; ++j) {
X            dst[0][j] = src[0][j];
X        }
X        src++;
X        dst++;
X    }
X}
X
Xvoid ring()
X{
X}
X
Xmain(argc, argv)
Xchar **argv;
X{
X    int argi;
X    u_int (*screen)[SIZEX/32], (*next)[SIZEX/32], (*prev)[SIZEX/32];
X    int x=0, y=0, w=SIZEX, h=SIZEY;
X    int interactive = 0;
X    int usec = 0;
X    int times=-1;
X    int fd;
X    char *fbname = LIFE_FB;
X    if (getenv("LIFE_FB"))
X        fbname = getenv("LIFE_FB");
X
X    for (argi = 1; argi < argc; ++argi) {
X        if (!strcmp(argv[argi], "-i"))
X            interactive = 1;
X        else if (argi+3 < argc) {
X            x = atoi(argv[argi++]);
X            y = atoi(argv[argi++]);
X            w = atoi(argv[argi++]);
X            h = atoi(argv[argi]);
X        } else {
X            (void) fprintf(stderr, "Usage: %s [-i] [<x> <y> <w> <h>]\n",
X                                           argv[0]);
X            exit(1);
X        }
X    }
X
X    /*
X     * From the user's perspective, x is rounded down to a multiple of 32
X     * and w is rounded up to a multiple of 32.
X     */
X    x = x / 32;
X    w = howmany(w, 32);
X
X    if (w > SIZEX/32-x)
X        w = SIZEX/32-x;
X    if (h > SIZEY-y)
X        h = SIZEY-y;
X
X
X    if (getenv("LIFETIMES"))
X        times = atoi(getenv("LIFETIMES"));
X    if (getenv("LIFE_USEC"))
X        usec = atoi(getenv("LIFE_USEC"));
X
X    /*
X     * Get the frame buffer as a chunk of memory.
X     * This could also be done by:
X     *          screen = (int (*)[SIZEX/32])(mpr_d(pr)->md_image);
X     * where pr is a pixrect referring to the screen.
X     * But then you'd have to link with -lpixrect, producing
X     * a needlessly big executable...
X     */
X    if ((fd = open(fbname, O_RDWR)) == -1)
X        perror(fbname), exit(1);
X    screen = (u_int (*)[SIZEX/32])mmap((caddr_t)NULL,
X                    SIZEY*sizeof(*screen),
X                    PROT_READ|PROT_WRITE, MAP_SHARED, fd,
X                    (off_t) (getenv("LIFE_OFF") ? atoi(getenv("LIFE_OFF")) :0));
X    if ((int)screen == -1)
X        perror("mmap"), exit(1);
X    (void) close(fd);
X
X
X    next = (u_int (*)[SIZEX/32])malloc(SIZEY * SIZEX/32 * sizeof(int));
X    if (!next)
X        perror("malloc"), exit(1);
X    if (!interactive) {
X        prev = (u_int (*)[SIZEX/32])malloc(SIZEY * SIZEX/32 * sizeof(int));
X        if (!prev)
X            perror("malloc"), exit(1);
X    } else
X        prev = 0;
X
X    (void) signal(SIGALRM, ring);
X
X    if (prev)
X        copy(&screen[y][x], &prev[y][x], h, w);
X
X    while (times--) {
X        if (usec) {
X            struct itimerval it, oit;
X            timerclear(&it.it_interval);
X            timerclear(&it.it_value);
X            it.it_value.tv_sec = usec / 1000000;
X            it.it_value.tv_usec = usec % 1000000;
X            (void) sigblock(sigmask(SIGALRM));
X            if (setitimer(ITIMER_REAL, &it, &oit) < 0)
X                perror("setitimer"), exit(1);;
X        }
X        if (interactive) {
X            /*
X             * "Interactive" mode.
X             * Calculate new generation into back buffer from screen,
X             * then copy back buffer to screen.
X             * This is slow, since accessing the frame buffer is
X             * slower than accessing "normal" memory.
X             * .306 seconds/screen on a sparc
X             */
X            life(&screen[y][x], &next[y][x], h, w);
X            copy(&next[y][x], &screen[y][x], h, w);
X        } else {
X            /*
X             * This is the fastest mode, and is the default.
X             * it calculates the new generations using only
X             * the "prev" and "next" arrays, which
X             * seems to be faster than accessing the frame buffer
X             * memory directly.  The disadvantage is that there
X             * can be no input except what is on the screen
X             * at startup.
X             * (Sometimes it is fun to let it run on top of a clock
X             * or to violate the prime directive with the mouse.)
X             * Also this mode uses an extra screen-sized chunk of memory.
X             * .148 seconds/screen on a sparc
X             */
X            life(&prev[y][x], &next[y][x], h, w);
X            copy(&next[y][x], &screen[y][x], h, w);
X            SWAP(prev, next);
X        }
X        if (usec)
X            (void) sigpause(0);
X    }
X    return 0;
X}
+END+OF+life.c
echo '-rw-------  1 hatch        9288 Jun 15 03:38 life.c    (as sent)'
chmod u=rw,g=,o= life.c
ls -ldo life.c
if test 9288 -ne `wc -c <life.c` ; then
  echo shar: \"life.c\" unpacked with wrong size!
fi
fi
echo shar: End of shell archive.
exit 0

exit 0 # Just in case...