/*  X-automalab, a totalistic celular automaton simulator for X windows.
           
      Michael Creutz   
   creutz@wind.phy.bnl.gov 

 compiling:  cc -O -o xautomalab xautomalab.c -lX11 

 version 1.5 
 26 May 1994 

 This program is still evolving; the latest release can be found via

   http://penguin.phy.bnl.gov/www/xtoys/xtoys.html

 version 1.1 adds save/restore as a gif file
 version 1.2 allows window resizing 
 version 1.3 allows block selection while running and improves picture loading
 version 1.4 supports monochrome 
 version 1.5 uses my own gif routines

 */

# include <X11/Xlib.h>
# include <X11/Xutil.h>
# include <X11/Xos.h>
# include <X11/Xatom.h> 
# include <X11/cursorfont.h>
# include <stdio.h>
# include <stdlib.h>
# include <string.h>
# include <malloc.h>

# define BPW (sizeof(long))

/* size and position parameters for buttons, etc. */
# define PLAYTOP 135
# define PLAYLEFT 10
# define BOUNDHEIGHT 72
# define TRACEHEIGHT 54
# define BOUNDWIDTH  110
# define BARHEIGHT 45
# define BARWIDTH  135
# define BARTOP 0
# define BARLEFT 0
# define XHEIGHT 36

int nrows,ncols,volume; /* lattice dimensions (plus two for boundaries) */
     /* ncols will be truncated to 
        a multiple of bytes per long word (BPW),
        and then two units are lost for boundaries    */
int block,           /* size of cells displayed on the screen          */
    blockshift;      /* log_2(block)                                   */
unsigned char *field[2]={NULL,NULL}; /* pointers to old and new system */
int old=0,new=1;                 /* which field is current?            */
int table[2][256];               /* for the rule table                 */
int nbrhd[3][3];                 /* to tag active neighbors            */
int birth[9],survivor[9];        /* when are there births or survivors */

int paused=0,        /* is the system paused?                  */
    boundary,        /* 0,1,2,3 for open, live, periodic, flow */
    pencolor=1,      /* for sketching                          */
    trace,           /* is the tracer on?                      */
    xpast,           /* are we to xor with the past?           */
    neighbors,       /* how many live neighbors                */
    colshift;        /* how to shift to get the next column    */
long mask0x13,mask0x01,mask0x03,mask0x10; /* some useful masks */
unsigned char stringbuffer[256];     /* generally useful       */
unsigned char *work=NULL;            /* points to a work array */

/* various window stuff */
Display *display;
int screen;
static char *progname;
Window window,quitbutton,pausebutton,playground,boundwindow,rulebar,
       fillbutton,tracewindow,xpastbutton,nhood,srbutton,blockbutton;
XColor xcolor,colorcell;
Colormap cmap;
GC gc, gcr, gcxor, gccolor, gcpen;
int windowwidth,windowheight;
XFontStruct *font=NULL;
int font_height;
XSizeHints size_hints;
int depth,darkcolor,lightcolor,black,white;
XImage *spinimage=NULL;
unsigned char *picture=NULL, *imageptr=NULL; /* for the image structure */
unsigned char translate[256];                /* for converting colors   */

main(argc,argv)
int argc;
char **argv;
{unsigned int width, height;
 int i,j,x,y;
 long bitcheck;
 XEvent report;
 progname=argv[0];

  /* initial lattice size */
 block=1;
 nrows=200/block;
 ncols=(~(BPW-1))&(200/block);
 volume=nrows*ncols;

 /* initial rule */
 for (i=0;i<3;i++)
  for (j=0;j<3;j++)
   nbrhd[i][j]=1;
 nbrhd[0][0]=nbrhd[2][1]=0;
 trace=1;
 xpast=0;
 boundary=1;
 for (i=0;i<9;i++)
   birth[i]=survivor[i]=0;
 birth[2]=birth[5]=birth[6]=1;
 survivor[4]=survivor[5]=1;
 settable();
 openwindow(argc,argv);
 makebuttons();

  /* set the masks for parallel updating */
 for (i=0;i<sizeof(long);i++) 
  {mask0x13=0x13|(mask0x13<<8);
   mask0x01=0x01|(mask0x01<<8);
   mask0x03=0x03|(mask0x03<<8);
   mask0x10=0x10|(mask0x10<<8);
  }
   /* check for byte order in a word */
 bitcheck=1;
 if (* (char*) (&bitcheck) )
   colshift=(-1); /* LSBfirst */
 else 
   colshift=1;    /* MSBfirst */

/* loop forever, looking for events */
 fprintf(stderr, "Entering main loop\n");
 while(1)
  {if ((0==XPending(display))&&(0==paused))
     update();
   else
    {XNextEvent(display,&report); 
     switch (report.type)
      {case Expose:
        if (report.xexpose.count!=0) break; /* more in queue, wait for them */
        repaint();  
        break;
       case ConfigureNotify:
        width=report.xconfigure.width;
        height=report.xconfigure.height;
        if ((width<size_hints.min_width)||(height<size_hints.min_height))
            {fprintf(stderr,"%s: window too small to proceed.\n",progname);
             cleanup();
            } 
        else if ((width!=windowwidth)||(height!=windowheight))
            {windowwidth=width;
             windowheight=height;  
             nrows=(height-PLAYTOP-10)/block;
             ncols=(~(BPW-1))&((width-PLAYLEFT-BOUNDWIDTH-20)/block);
             volume=nrows*ncols;
             makebuttons();
             fixboundary();
             showpic();
            } 
        break; 
       case ButtonPress:
        if (report.xbutton.window==quitbutton)
             cleanup();
        else if (report.xbutton.window==pausebutton)
             setpause(1-paused);
        else if (report.xbutton.window==fillbutton)
            {j=nrows*ncols;
             for (i=0;i<j;i++)
               field[old][i]=0;
             fixboundary();
             showpic();
            }
        else if (report.xbutton.window==boundwindow)
            {setboundary((report.xbutton.y*4)/BOUNDHEIGHT);
             showpic();
            }
        else if (report.xbutton.window==tracewindow)
             settrace((report.xbutton.y*3)/TRACEHEIGHT);
        else if (report.xbutton.window==rulebar)
             setrule((report.xbutton.x*(neighbors+1))/BARWIDTH+
                   ((report.xbutton.y*3)/BARHEIGHT)*10);
        else if (report.xbutton.window==playground) /* sketch */
            {x=report.xbutton.x/block;
             y=report.xbutton.y/block;
             sketch(x,y);
            }
        else if (report.xbutton.window==xpastbutton) 
             setxpast((report.xbutton.y*2)/XHEIGHT);
        else if (report.xbutton.window==nhood) 
            {x=(3*report.xbutton.x)/BARHEIGHT;
             y=(3*report.xbutton.y)/BARHEIGHT;
             setnbrhd(x,y);
            }
        else if (report.xbutton.window==srbutton)
            {if (2*report.xbutton.y<XHEIGHT)
                savepic(field[old],ncols,nrows);
             else
                loadpic(field[old],ncols,nrows);
            }
        else if (report.xbutton.window==blockbutton)
          {i=(1<<(4*report.xbutton.x/BOUNDWIDTH));
           if (i!=block) /* reset for new block size */
             {block=i;
              nrows=(windowheight-PLAYTOP-10)/block;
              ncols=(~(BPW-1))&((windowwidth-PLAYLEFT-BOUNDWIDTH-20)/block);
              volume=nrows*ncols;
              makebuttons();
              fixboundary();
              showpic();
             }
          }
        else
         update(); /* do a sweep when mouse clicked */
        break;
       default:
        break;
      } /* end of switch */
    } /* end of if XPending */
  } /* end of while(1) */
} /* end of main */

settable()  /* set up the rule table from birth and survivor arrays */
/* The use of a table in allows much more general rules
   with no loss in speed over these totalistic ones.
   Any ideas as to how to add easily selected further rules? */
{int i,j,bits,mask;
  /* mask out the unused neighbors */
 mask=nbrhd[0][1]
     |nbrhd[2][1]<<1
     |nbrhd[1][2]<<2
     |nbrhd[1][0]<<3
     |nbrhd[0][2]<<4
     |nbrhd[2][2]<<5
     |nbrhd[0][0]<<6
     |nbrhd[2][0]<<7;
 for (i=0;i<256;i++)
  {bits=0;  /* count the set bits in i */
   j=i&mask;
   while (j) 
    {bits+=(1&j);
     j>>=1;
    }
   table[0][i]=birth[bits];
   table[1][i]=survivor[bits];
  }
 return;
}

sketch(x,y)   /* sketch in playground starting at point x,y */
int x,y;
{int sketching,i,oldx,oldy,deltax,deltay,newx,newy;
 Window root,child;
 XEvent sketchreport;
 unsigned int keys_buttons;
 int window_x,window_y;
 newx=x;
 newy=y;
 field[old][x+ncols*y]^=pencolor;
 sketching=1;
 while (sketching)
  {showpic();
   XNextEvent(display,&sketchreport); 
   switch (sketchreport.type)
    {case MotionNotify: 
      oldx=newx;
      oldy=newy;
      if (!XQueryPointer(display,playground,
        &root,&child,&window_x,&window_y,
        &newx,&newy,&keys_buttons))
          {sketching=0;
           break;
          }
      if (blockshift)
        {newx>>=blockshift;
         newy>>=blockshift;
        }
      if ((newx>ncols)|(newy>nrows)|(newx<0)|(newy<0))
        {sketching=0;
         break;
        }
      deltax=abs(newx-oldx);
      deltay=abs(newy-oldy);
      if (deltax>deltay)
         for (i=1;i<=deltax;i++)
          field [old][oldx+i*(newx-oldx)/deltax
                  +ncols*(oldy+i*(newy-oldy)/deltax)]^=pencolor;
      else 
         for (i=1;i<=deltay;i++)
          field [old][oldx+i*(newx-oldx)/deltay
                  +ncols*(oldy+i*(newy-oldy)/deltay)]^=pencolor;
      break;
     case ButtonRelease:
     default:
      sketching=0;
      break;
    } 
  }
 fixboundary();
 showpic();
 return;
}

update()
{int i,topi=volume-ncols;
 putneighbors((long *) field[old],(long *) field[new]); 
 for (i=ncols;i<topi;i++) /* bottom and top will be fixed by boundary */
   field[new][i]^=table[field[old][i]][work[i]]; 
 old=new;
 new=1-new;
 fixboundary();
 showpic(); 
 return;
}

putneighbors(source,destination)
/* initializes the new field and puts neighbors in work array */
/* this updating is done BPW spins at a time using multi-spin coding */
long *source, *destination;
{int i,rowshift=ncols/BPW,topi,cprshift,cmrshift;
 unsigned long * temp;
 temp=(unsigned long*) work;
 topi=(volume/BPW); 
 if (xpast&trace)
  for (i=0;i<topi;i++)
   {destination[i]=(source[i]    &mask0x10)   /* keep old trace bit      */
                 |((source[i]>>1)&mask0x01)   /* previous spin for xpast */
                 |((source[i]<<1)&mask0x03)   /* old state to second bit */
                 |((source[i]<<3)&mask0x10);  /* new trace bit           */
    source[i]&=mask0x01;  /* clean out the source */
   }
 else if (xpast) /* include previous state into destination */
  for (i=0;i<topi;i++)
   {destination[i]=(source[i]    &mask0x10)   /* keep trace bit          */
                 |((source[i]>>1)&mask0x01)   /* previous spin for xpast */
                 |((source[i]<<1)&mask0x03);  /* old state to second bit */
    source[i]&=mask0x01;  /* clean out the source */
   }
 else if (trace)
  for (i=0;i<topi;i++)
   {destination[i]=(source[i]    &mask0x10)   /* keep old trace bit      */
                 |((source[i]<<1)&mask0x03)   /* old state to second bit */
                 |((source[i]<<3)&mask0x10);  /* new trace bit           */
    source[i]&=mask0x01;  /* clean out the source */
   }
 else /* neither trace nor xpast */
  for (i=0;i<topi;i++)
   {destination[i]=(source[i]    &mask0x10)   /* keep old trace bit      */
                 |((source[i]<<1)&mask0x03);  /* old state to second bit */
    source[i]&=mask0x01;  /* clean out the source */
   }

  /* now put the neighbors into the work array */
 topi=(volume/BPW)-rowshift; 
 cprshift=colshift+rowshift;
 cmrshift=colshift-rowshift;
 for (i=rowshift;i<topi;i++)
  {temp[i]=(source[i         ]>>8)            
          |(source[i-colshift]<<(8*(BPW-1)))   /* W neighbor  */
          |(source[i         ]<<9)  
          |(source[i+colshift]>>(8*(BPW-1)-1)) /* E neighbor  */
          |(source[i+rowshift]<<2 )            /* S neighbor  */
          |(source[i-rowshift]<<3 )            /* N neighbor  */
          |(source[i+rowshift]>>4)
          |(source[i-cmrshift]<<(8*(BPW-1)+4)) /* SW neighbor */
          |(source[i+rowshift]<<13)         
          |(source[i+cprshift]>>(8*(BPW-1)-5)) /* SE neighbor */
          |(source[i-rowshift]>>2)
          |(source[i-cprshift]<<(8*(BPW-1))+6) /* NW neighbor */
          |(source[i-rowshift]<<15)
          |(source[i+cmrshift]>>(8*(BPW-1)-7));/* NE neighbor */ 
  }   
} 

showpic() /* display the field */
{int row,col,i1,i2,color,j,j1,blocktop=block;
 if (block>1) /* I wish I know how to do this faster */
  {if (block>2) blocktop=block-1;
   for (row=0;row<nrows;row++)
   for (col=0;col<ncols;col++)
    {color=translate[field[old][row*ncols+col]];
     j=block*(col+block*ncols*row);
     if (color!=picture[j])
      for (i1=0;i1<blocktop;i1++)
        {j1=i1*block*ncols+j;
         for (i2=0;i2<blocktop;i2++)
           picture[j1+i2]=color;
        }
    }
  }
 else
  {j1=nrows*ncols;
   for (j=0;j<j1;j++)
    picture[j]=translate[field[old][j]];
  }
 if (1==depth) /* smash the data into a bitmap */
   {j1=0;
    i2=1+block*block*nrows*ncols;
    *imageptr=1;
    if (XGetPixel(spinimage,0,0)) /*LSBFirst */
     for (i1=0;i1<i2;i1+=8)
      {imageptr[j1]=(picture[i1]&1)
                  |((picture[i1+1]&1)<<1)
                  |((picture[i1+2]&1)<<2)
                  |((picture[i1+3]&1)<<3)
                  |((picture[i1+4]&1)<<4)
                  |((picture[i1+5]&1)<<5)
                  |((picture[i1+6]&1)<<6)
                  |((picture[i1+7]&1)<<7);
       j1++;
      }
    else /* MSBFirst */
     for (i1=0;i1<i2;i1+=8)
      {imageptr[j1]=(picture[i1+7]&1)
                  |((picture[i1+6]&1)<<1)
                  |((picture[i1+5]&1)<<2)
                  |((picture[i1+4]&1)<<3)
                  |((picture[i1+3]&1)<<4)
                  |((picture[i1+2]&1)<<5)
                  |((picture[i1+1]&1)<<6)
                  |((picture[i1]&1)<<7);
       j1++;
      }
   }
 XPutImage(display,playground,gc,spinimage,0,0,0,0,block*ncols,block*nrows); 
 return;
}

fixboundary()
{int i,bv;
 if (boundary<2) /* dead or alive */
  {bv=pencolor*boundary;
   for (i=0;i<ncols;i++)
    {field[old][i]=bv;
     field[old][volume-1-i]=bv;
    }
   for (i=0;i<volume;i+=ncols)
    {field[old][i]=bv;
     field[old][i+ncols-1]=bv;
    }
  }
 else if (2==boundary) /* periodic */
  {for (i=0;i<ncols;i++)
    {field[old][i]=field[old][volume-2*ncols+i];
     field[old][volume-ncols+i]=field[old][ncols+i];
    }
   for (i=0;i<volume;i+=ncols)
    {field[old][i]=field[old][i+ncols-2];
     field[old][i+ncols-1]=field[old][i+1];
    }
  }
 else /* flow: alive on top, dead on sides and bottom */
  {for (i=0;i<ncols;i++)
    {field[old][i]=pencolor;
     field[old][volume-1-i]=0;
    }
   for (i=0;i<volume;i+=ncols)
    {field[old][i]=0;
     field[old][i+ncols-1]=0;
    }
  }
 return;
} 

repaint()
   /* this fixes the window up whenever it is uncovered */
{int i;
 XDrawString(display,quitbutton,gcr,0,font_height, "quit",4);
 XDrawString(display,fillbutton,gcr,0,font_height,"clear",5);
 XDrawString(display,srbutton,gcr,8,font_height," save  ",7);
 XDrawString(display,srbutton,gcr,0,XHEIGHT/2+font_height,"restore",7);
 XDrawLine(display,srbutton,gc,0,XHEIGHT/2,68,XHEIGHT/2);
 setpause(paused);
  /* fix the block buttons */
 XFillRectangle(display,blockbutton,gcr,0,0,BOUNDWIDTH,18);
 sprintf(stringbuffer," 1  2  4  8");
 XDrawString(display,blockbutton,gccolor,0,font_height,
        stringbuffer,strlen(stringbuffer));
 XFillRectangle(display,blockbutton,gcxor,
       blockshift*BOUNDWIDTH/4,0,BOUNDWIDTH/4+1,18);
 for (i=1;i<4;i++)
   XDrawLine(display,blockbutton,gc,
       i*BOUNDWIDTH/4,0,i*BOUNDWIDTH/4,18); 
   /* draw the boundary condition buttons */
 XFillRectangle(display,boundwindow,gcr,0,0,BOUNDWIDTH,BOUNDHEIGHT);
 XDrawString(display,boundwindow,gccolor,
        0,font_height,                "    open    ",12);
 XDrawString(display,boundwindow,gccolor,
        0,BOUNDHEIGHT/4+font_height,  "    live    ",12);
 XDrawString(display,boundwindow,gccolor,
        5,2*BOUNDHEIGHT/4+font_height,"  periodic ",11);
 XDrawString(display,boundwindow,gccolor,
        5,3*BOUNDHEIGHT/4+font_height,"    flow   ",11);
 for (i=1;i<4;i++)
   XDrawLine(display,boundwindow,gc,
       0,i*BOUNDHEIGHT/4-1,BOUNDWIDTH,i*BOUNDHEIGHT/4-1);
 XFillRectangle(display,boundwindow,gcxor,0,
    (BOUNDHEIGHT*boundary)/4,BOUNDWIDTH,-1+BOUNDHEIGHT/4);
          /* draw the trace buttons */
 XFillRectangle(display,tracewindow,gcr,0,0,BOUNDWIDTH,TRACEHEIGHT);
 XDrawString(display,tracewindow,gccolor,
        0,font_height,                " tracer off ",12);
 XDrawString(display,tracewindow,gccolor,
        0,TRACEHEIGHT/3+font_height,  " tracer  on ",12);
 XDrawString(display,tracewindow,gccolor,
        5,2*TRACEHEIGHT/3+font_height,"clear trace",11);
 for (i=1;i<3;i++)
   XDrawLine(display,tracewindow,gc,
       0,i*TRACEHEIGHT/3-1,BOUNDWIDTH,i*TRACEHEIGHT/3-1);
 XFillRectangle(display,tracewindow,gcxor,0,
    (TRACEHEIGHT*trace)/3,BOUNDWIDTH,-1+TRACEHEIGHT/3);
 setxpast(-1);
 setnbrhd(-1,-1);
          /* write various strings */
 XDrawString(display,window,gc,BARWIDTH+BARLEFT+4,BARTOP+font_height,
        "births",6);
 XDrawString(display,window,gc,BARWIDTH+BARLEFT+4,BARTOP+BARHEIGHT,
        "survivors",9);
 sprintf(stringbuffer,"%d by %d lattice    ",ncols-2,nrows-2);
 XDrawImageString(display,window,gccolor,5,BARHEIGHT+BARTOP+2*font_height,
               stringbuffer,strlen(stringbuffer));
 if (depth>1)
  {XSetForeground(display,gcpen,translate[1]);
   XDrawString(display,window,gcpen,5,BARTOP+BARHEIGHT+font_height,"young",5); 
   XSetForeground(display,gcpen,translate[3]);
   XDrawString(display,window,gcpen,60,BARTOP+BARHEIGHT+font_height,"old",3); 
   XSetForeground(display,gcpen,translate[2]);
   XDrawString(display,window,gcpen,98,BARTOP+BARHEIGHT+font_height,
      "moribund",8); 
  }
 XDrawString(display,window,gc,windowwidth-BOUNDWIDTH,BOUNDHEIGHT+font_height,
               "  Boundary  ",12);
 XDrawString(display,window,gc,
        8+BARHEIGHT,BARHEIGHT+BARTOP+4*font_height+4,
        "neighbors",9);
 XDrawString(display,window,gc,
        windowwidth-BOUNDWIDTH+12,BOUNDHEIGHT+TRACEHEIGHT+XHEIGHT+74,
        "cell size",9);
 XDrawString(display,window,gc,windowwidth-50,windowheight-5,"MJC",3); 
 showpic();  
 return;
}
 
setboundary(value)
/* take action if boundary buttons hit */
int value;
{XFillRectangle(display,boundwindow,gcxor,0,
    (BOUNDHEIGHT*boundary)/4,BOUNDWIDTH,-1+BOUNDHEIGHT/4);
 boundary=value;
 XFillRectangle(display,boundwindow,gcxor,0,
    (BOUNDHEIGHT*boundary)/4,BOUNDWIDTH,-1+BOUNDHEIGHT/4);
 fixboundary();
 return;
}
 
settrace(value)
/* take action if trace buttons hit */
int value;
{int i;
  XFillRectangle(display,tracewindow,gcxor,0,
    (TRACEHEIGHT*trace)/3,BOUNDWIDTH,-1+TRACEHEIGHT/3);
 if (2==value) /* clear the trace bit */
  {XFillRectangle(display,tracewindow,gcxor,0,
    (TRACEHEIGHT*2)/3,BOUNDWIDTH,-1+TRACEHEIGHT/3);
   for (i=0;i<volume;i++)
     field[old][i]&=0x3;
   XFillRectangle(display,tracewindow,gcxor,0,
    (TRACEHEIGHT*2)/3,BOUNDWIDTH,-1+TRACEHEIGHT/3);
   showpic();
  } 
 else trace=value;
 XFillRectangle(display,tracewindow,gcxor,0,
    (TRACEHEIGHT*trace)/3,BOUNDWIDTH,-1+TRACEHEIGHT/3);
 return;
}

setrule(value)
/* take action if rule buttons hit */
/* call with negative value just to redraw but not change rule */
int value;
{int i;  
 if (value>=0) 
   {if (value<10)
      birth[value]=1-birth[value];
    else if (value>=20)
      survivor[value-20]=1-survivor[value-20];
   }
      /* fix the rulebar */
 XFillRectangle(display,rulebar,gcr,0,0,BARWIDTH,BARHEIGHT);
 for (i=0;i<(neighbors+1);i++)
  {if (birth[i])
    XFillRectangle(display,rulebar,gccolor,i*BARWIDTH/(neighbors+1),0,
           1+BARWIDTH/(neighbors+1),BARHEIGHT/3);
   else
    XFillRectangle(display,rulebar,gcr,i*BARWIDTH/(neighbors+1),0,
           1+BARWIDTH/(neighbors+1),BARHEIGHT/3);
   if (survivor[i])
    XFillRectangle(display,rulebar,gccolor,
          i*BARWIDTH/(neighbors+1),2*BARHEIGHT/3,
          1+BARWIDTH/(neighbors+1),BARHEIGHT/3);
   else
    XFillRectangle(display,rulebar,gcr,
           i*BARWIDTH/(neighbors+1),2*BARHEIGHT/3,
           1+BARWIDTH/(neighbors+1),BARHEIGHT/3);
   XDrawRectangle(display,rulebar,gc,i*BARWIDTH/(neighbors+1),0,
           BARWIDTH,BARHEIGHT/3);
   XDrawRectangle(display,rulebar,gc,i*BARWIDTH/(neighbors+1),2*BARHEIGHT/3,
           BARWIDTH,BARHEIGHT/3);
   sprintf(stringbuffer,"%d",i);
   XDrawString(display,rulebar,gc,
          18-2*neighbors+BARWIDTH*i/(neighbors+1),2*BARHEIGHT/3-2,
          stringbuffer,1);
  }
 settable();
 return;
}

setpause(value)   /* fix up the pause button */
int value;
{paused=value;
 if (paused) 
   XDrawImageString(display,pausebutton,gcr,0,font_height," run ",5);
 else
   XDrawImageString(display,pausebutton,gcr,0,font_height,"pause",5);
 return;
}

setnbrhd(vx,vy)  /* fix the neighborhood buttons */
int vx,vy;
{int i,j;
 neighbors=0;
 if ((vx>=0)&(vy>=0))  /* toggle this neighbor */
  nbrhd[vx][vy]=1-nbrhd[vx][vy];
 nbrhd[1][1]=0;
 for (i=0;i<3;i++)
  for (j=0;j<3;j++)
   if (nbrhd[i][j])
    {XFillRectangle(display,nhood,gccolor,i*BARHEIGHT/3,j*BARHEIGHT/3,
            (i+1)*BARHEIGHT/3,(j+1)*BARHEIGHT/3);
     neighbors++;
    }
   else
    XFillRectangle(display,nhood,gcr,i*BARHEIGHT/3,j*BARHEIGHT/3,
            (i+1)*BARHEIGHT/3,(j+1)*BARHEIGHT/3);
 for (i=0;i<3;i++)
  for (j=0;j<3;j++)
    XDrawRectangle(display,nhood,gc,i*BARHEIGHT/3,j*BARHEIGHT/3,
            (i+1)*BARHEIGHT/3,(j+1)*BARHEIGHT/3);
 setrule(-1); /* redraw the rule bar */
 return;
}

setxpast(value)   /* fix up the xpast button */
int value;
{int i;
 if ((1==value)&xpast) /* swap past and present */
  {for (i=0;i<volume;i++)
    field[old][i]=((field[old][i]>>1)&1)|((field[old][i]&1)<<1);
   showpic();
  }
 if ((0==value)|((1==value)&(0==xpast))) xpast=1-xpast;
 /* repaint the button */
 XFillRectangle(display,xpastbutton,gcr,0,
        0,BOUNDWIDTH,XHEIGHT);
 if (xpast) 
  {XDrawImageString(display,xpastbutton,gccolor,
        0,font_height,"  xor past  ",12);
   XFillRectangle(display,xpastbutton,gcxor,0,0,BOUNDWIDTH,XHEIGHT/2);
   XDrawLine(display,xpastbutton,gc,0,XHEIGHT/2,BOUNDWIDTH,XHEIGHT/2);
   XDrawImageString(display,xpastbutton,gccolor,
        0,font_height+XHEIGHT/2,"  reverse   ",12);
  }
 else
  XDrawImageString(display,xpastbutton,gccolor,
     0,XHEIGHT/2,"xor past off",12);
 return;
}

openwindow(argc,argv)
/* a lot of this is taken from basicwin in the Xlib Programming Manual */
int argc;
char **argv;
{char *window_name="Automalab";
 char *icon_name="Automalab";
 long event_mask;
 Pixmap icon_pixmap;
 char *display_name=NULL;
 int i;
# define icon_bitmap_width 16
# define icon_bitmap_height 16
 static char icon_bitmap_bits[] = {
   0x1f, 0xf8, 0x1f, 0x88, 0x1f, 0x88, 0x1f, 0x88, 0x1f, 0x88, 0x1f, 0xf8,
   0x1f, 0xf8, 0x1f, 0xf8, 0x1f, 0xf8, 0x1f, 0xf8, 0x1f, 0xf8, 0xff, 0xff,
   0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff};

/* open up the display */
 if ((display=XOpenDisplay(display_name))==NULL)
  {fprintf(stderr,"%s: cannot connect to X server %s\n",
    progname,XDisplayName(display_name));
   exit(-1);
  }
 screen=DefaultScreen(display);
 depth=DefaultDepth(display,screen);
 cmap=DefaultColormap(display,screen);

 darkcolor=black=BlackPixel(display,screen);
 lightcolor=white=WhitePixel(display,screen);
 translate[0]=white;
 translate[1]=black;
 translate[2]=white;
 translate[3]=black;
 for(i=4;i<256;i++)
   translate[i]=translate[i%4]; 
  /* for monochrome, invert black and white when traced */
 translate[8]=black;
 translate[17]=white;
 translate[18]=black;
 translate[19]=white;
if (depth>1)
{   /* set the various colors */
 if (XAllocNamedColor(display,cmap,"firebrick",&colorcell,&xcolor))
              darkcolor=colorcell.pixel;
 if (XAllocNamedColor(display,cmap,"wheat",&colorcell,&xcolor))
              lightcolor=colorcell.pixel;
 if (XAllocNamedColor(display,cmap,"black",&colorcell,&xcolor))
              translate[0]=colorcell.pixel;
 if (XAllocNamedColor(display,cmap,"red",&colorcell,&xcolor))
              translate[1]=colorcell.pixel;
 if (XAllocNamedColor(display,cmap,"forest green",&colorcell,&xcolor))
              translate[2]=colorcell.pixel;
 if (XAllocNamedColor(display,cmap,"blue",&colorcell,&xcolor))
              translate[3]=colorcell.pixel;
 if (XAllocNamedColor(display,cmap,"orange",&colorcell,&xcolor))
              translate[4]=colorcell.pixel;
 if (XAllocNamedColor(display,cmap,"gold",&colorcell,&xcolor))
              translate[5]=colorcell.pixel;
 if (XAllocNamedColor(display,cmap,"yellow",&colorcell,&xcolor))
              translate[6]=colorcell.pixel;
 if (XAllocNamedColor(display,cmap,"white",&colorcell,&xcolor))
              translate[7]=colorcell.pixel;
 if (XAllocNamedColor(display,cmap,"light grey",&colorcell,&xcolor))
              translate[8]=colorcell.pixel;
  /* fill out the color table for future uses */
 for(i=9;i<256;i++)
   translate[i]=translate[i%8]; 
}
 translate[16]=translate[8]; /* for tracing */

   /* make the main window */
 windowwidth=(block*ncols+PLAYLEFT+BOUNDWIDTH+20);
 windowheight=(PLAYTOP+block*nrows+10);
 window=XCreateSimpleWindow(display,RootWindow(display,screen),
   0,0,windowwidth,windowheight,4,black,lightcolor);

/* make the icon */
 icon_pixmap=XCreateBitmapFromData(display,window,
   icon_bitmap_bits,icon_bitmap_width,icon_bitmap_height);

 size_hints.flags=PPosition | PSize | PMinSize;
 size_hints.min_width=windowwidth;
 size_hints.min_height=windowheight;
#ifdef X11R3
 size_hints.x=x;
 size_hints.y=y;
 size_hints.width=windowwidth;
 size_hints.height=windowheight;
 XSetStandardProperties(display,window,window_name,icon_name,
    icon_pixmap,argv,argc,&size_hints);
#else
 {XWMHints wm_hints;
  XClassHint class_hints;
  XTextProperty windowName, iconName;
  if (XStringListToTextProperty(&window_name,1,&windowName)==0)
   {fprintf(stderr,"%s: structure allocation for windowName failed.\n"
      ,progname);
    exit(-1);
   }
  if (XStringListToTextProperty(&icon_name,1,&iconName)==0)
   {fprintf(stderr,"%s: structure allocation for iconName failed.\n"
       ,progname);
    exit(-1);
   }
  wm_hints.initial_state=NormalState;
  wm_hints.input=True;
  wm_hints.icon_pixmap=icon_pixmap;
  wm_hints.flags=StateHint|IconPixmapHint|InputHint;
  class_hints.res_name=progname;
  class_hints.res_class="Basicwin";
  XSetWMProperties(display,window,&windowName,&iconName,
       argv,argc,&size_hints,&wm_hints,&class_hints);
 }
#endif

/* pick the events to look for */
 event_mask=ExposureMask|ButtonPressMask|StructureNotifyMask;
 XSelectInput(display,window,event_mask);

/* pick font: 9x15 is supposed to almost always be there */
 if ((font=XLoadQueryFont(display,"9x15"))==NULL)
  {fprintf(stderr,"%s: Cannot open 9x15 font\n",progname);
   exit(-1);
  }
 font_height=font->ascent+font->descent;

/* make graphics contexts: 
      gc for black on white
      gccolor for background and buttons 
      gcr for reverse video 
      gcxor for highlighting 
      gcpen for varying purposes */
   
 gc=XCreateGC(display,window,0,NULL);
 XSetFont(display,gc,font->fid);
 XSetForeground(display,gc,black);
 XSetBackground(display,gc,white); 

 gccolor=XCreateGC(display,window,0,NULL); 
 XSetFont(display,gccolor,font->fid);
 XSetForeground(display,gccolor,darkcolor);
 XSetBackground(display,gccolor,lightcolor); 

 gcr=XCreateGC(display,window,0,NULL); 
 XSetFont(display,gcr,font->fid);
 XSetForeground(display,gcr,lightcolor);
 XSetBackground(display,gcr,darkcolor);

 gcpen=XCreateGC(display,window,0,NULL); 
 XSetFont(display,gcpen,font->fid);
 XSetForeground(display,gcpen,translate[pencolor]);
 XSetBackground(display,gcpen,lightcolor); 

 gcxor=XCreateGC(display,window,0,NULL);
 XSetFont(display,gcxor,font->fid);
 XSetForeground(display,gcxor,darkcolor^lightcolor);
 XSetFunction(display,gcxor,GXxor);

/* show the window */
 XMapWindow(display,window);
 return;
}

makebuttons()
{int i,j;
 long event_mask;
 Cursor cursor;
     /* first destroy any old buttons */
 XDestroySubwindows(display,window);
     /* now make the new buttons */
 quitbutton=XCreateSimpleWindow(display,window,
    windowwidth-80,windowheight-48,48,18,2,black,darkcolor);
 pausebutton=XCreateSimpleWindow(display,window,
    windowwidth-80,windowheight-72,48,18,2,black,darkcolor);
 fillbutton=XCreateSimpleWindow(display,window,
    windowwidth-80,windowheight-96,48,18,2,black,darkcolor);
 playground=XCreateSimpleWindow(display,window,
    PLAYLEFT,PLAYTOP,block*ncols,block*nrows,2,black,white);
 boundwindow=XCreateSimpleWindow(display,window,
             windowwidth-BOUNDWIDTH-4,0,BOUNDWIDTH,BOUNDHEIGHT-1,2,
             BlackPixel(display,screen),lightcolor);
 tracewindow=XCreateSimpleWindow(display,window,
             windowwidth-BOUNDWIDTH-4,BOUNDHEIGHT+25,BOUNDWIDTH,
             TRACEHEIGHT-1,2,
             BlackPixel(display,screen),lightcolor);
 rulebar=XCreateSimpleWindow(display,window,
             BARLEFT,BARTOP,BARWIDTH,BARHEIGHT,2,
             BlackPixel(display,screen),lightcolor);
 nhood=XCreateSimpleWindow(display,window,
    BARLEFT,BARHEIGHT+BARTOP+34,BARHEIGHT,BARHEIGHT,2,black,lightcolor);
 xpastbutton=XCreateSimpleWindow(display,window,
    windowwidth-BOUNDWIDTH-4,BOUNDHEIGHT+TRACEHEIGHT+30,
    BOUNDWIDTH,XHEIGHT,2,black,lightcolor);
 srbutton=XCreateSimpleWindow(display,window,
    BARWIDTH+10,BARHEIGHT+BARTOP+34,68,XHEIGHT,2,black,darkcolor);
 blockbutton=XCreateSimpleWindow(display,window,
    windowwidth-BOUNDWIDTH-4,BOUNDHEIGHT+TRACEHEIGHT+XHEIGHT+36,
    BOUNDWIDTH,18,2,black,lightcolor);
 event_mask=ButtonPressMask; 
/* note that with this simple mask if one just covers a button
it will not get redrawn.  I wonder if anyone will notice?  If I put
the exposuremask in here, things flash irritatingly on being uncovered. */
 XSelectInput(display,quitbutton,event_mask);
 XSelectInput(display,pausebutton,event_mask);
 XSelectInput(display,boundwindow,event_mask);
 XSelectInput(display,tracewindow,event_mask);
 XSelectInput(display,rulebar,event_mask);
 XSelectInput(display,fillbutton,event_mask);
 XSelectInput(display,nhood,event_mask);
 XSelectInput(display,xpastbutton,event_mask);
 XSelectInput(display,srbutton,event_mask);
 XSelectInput(display,blockbutton,event_mask);
 event_mask=ButtonReleaseMask|ButtonPressMask|
            PointerMotionHintMask|ButtonMotionMask; 
 XSelectInput(display,playground,event_mask);
  /* show the new buttons */
 XMapWindow(display,quitbutton);
 XMapWindow(display,pausebutton);
 XMapWindow(display,boundwindow);
 XMapWindow(display,tracewindow);
 XMapWindow(display,rulebar);
 XMapWindow(display,fillbutton);
 XMapWindow(display,xpastbutton);
 XMapWindow(display,nhood);
 XMapWindow(display,srbutton);
 XMapWindow(display,blockbutton);
 XMapWindow(display,playground);
  /* make special cursors to be cute */
 cursor=XCreateFontCursor(display,XC_sb_up_arrow); 
 XDefineCursor(display,playground,cursor);
 cursor=XCreateFontCursor(display,XC_exchange);
 XDefineCursor(display,xpastbutton,cursor);
 cursor=XCreateFontCursor(display,XC_hand2);
 XDefineCursor(display,nhood,cursor);
 XDefineCursor(display,rulebar,cursor);
 XDefineCursor(display,boundwindow,cursor);
 XDefineCursor(display,tracewindow,cursor);
 XDefineCursor(display,srbutton,cursor);
 XDefineCursor(display,blockbutton,cursor);
  /* reallocate various arrays */
 if (NULL!=spinimage) XDestroyImage(spinimage); 
 if (NULL!=picture)   free((char *) picture);
 if (NULL!=work)      free((char *) work);
 if (NULL==(picture=(unsigned char *) malloc(block*block*volume)))
     {fprintf(stderr,"allocation problems\n");
      cleanup();
     } 
 if (NULL==( work=(unsigned char *) malloc(volume)))
     {fprintf(stderr,"allocation problems\n");
      cleanup();
     } 
   /* clear working arrays */
 fprintf(stderr, "Clearing working arrays...\n");
 for (i=0;i<volume;i++)
   work[i]=0;
 fprintf(stderr, "Cleared\n");
 for (i=0;i<block*block*volume;i++)
   picture[i]=translate[4];
   /* allocate a few bytes of extra space at ends of field array */
 for (i=0;i<2;i++)
   {
	fprintf(stderr, "Well...\n");
       if (NULL!=field[0])  free((char *) field[i]-BPW);
	fprintf(stderr, "Freed it!\n");
       if (NULL==( field[i]= (unsigned char *) malloc((volume+2)*BPW)))
	 {fprintf(stderr,"allocation problems\n");
	  cleanup();
     } 
       fprintf(stderr, "Clearing initial state\n");
       /* clear initial state */
       for (j=0;j<(volume+2*BPW);j++)
	 field[i][j]=0;
       fprintf(stderr, "Hmph\n");
       field[i]+=BPW;
  }
 fprintf(stderr, "Making image structure\n");
   /* make image structure */
 if (depth>1)
   {imageptr=picture;
    spinimage=XCreateImage(display,(Visual *) &window,8,ZPixmap,0,
       (char*) imageptr,block*ncols,block*nrows,8,0);
   }
 else  /* monochrome */
  {if (NULL!=imageptr) free((char *) imageptr);
   if (NULL==(imageptr= (unsigned char *) malloc(1+(block*block*volume)/8)))
     {fprintf(stderr,"allocation problems\n");
      cleanup();
     } 
   spinimage=XCreateImage(display,(Visual *) &window,depth,XYBitmap,0,
     (char*) imageptr,block*ncols,block*nrows,8,0);
  } 
  /* set blockshift to log_2 of block */
 blockshift=0;
 i=block;
 while(i>>=1)
  blockshift++; 
 fprintf(stderr,"exiting this routine...\n");
 return;
}

cleanup()
{XUnloadFont(display,font->fid);
 XFreeGC(display,gc); 
 XFreeGC(display,gcr); 
 XFreeGC(display,gccolor); 
 XFreeGC(display,gcxor); 
 XFreeGC(display,gcpen); 
 XCloseDisplay(display);
 if (NULL!=picture)  free((char *) picture);
 if (NULL!=work)     free((char *) work);
 if (NULL!=field[0]) free((char *) field[0]-BPW);
 if (NULL!=field[1]) free((char *) field[1]-BPW);
 if ((1==depth)&&(NULL!=imageptr)) free((char *) imageptr);
 exit(1);
} 

/* from here on is the stuff for saving and restoring from a gif file */
/* for info on how gif works, see ftp://network.ucsd.edu/graphics/GIF.shar.Z */

char *picturename="xautomalab.gif";

loadpic(data,xsize,ysize) /* load in a GIF image          */
unsigned char *data;      /* where the output data starts */
int xsize,ysize;          /* output picture dimensions    */
/* load in a gif image */
{int i,j,filesize,gwidth,gheight,gvolume;
 unsigned char *ptr, *ptr1, *rawgif;
 int colorbits,codesize;
 FILE *infile;
 if (NULL==(infile=fopen(picturename,"r")))
   {fprintf(stderr,"couldn't open input file\n");
    return;
   }
    /* find the file size */
 fseek(infile, 0L, 2);
 filesize = ftell(infile);
 fseek(infile, 0L, 0);
  /* make a place in memory for the file */
 if (NULL==(rawgif= (unsigned char *) malloc(filesize) ))
    {fprintf(stderr, "not enough memory to read gif file\n");
     return;
    }
 ptr=rawgif;
  /* read in the file */ 
 if (fread(ptr, filesize, 1, infile) != 1)
    {fprintf(stderr, "read failed\n");
     free((char *) rawgif);
     return;
    }
 fclose(infile);
  /* check for GIF signature */
 if (strncmp((char *) ptr,"GIF87a", 6))
     {fprintf(stderr, "not a GIF87a file\n");
      free((char *) rawgif);
      return;
     }
 ptr+=6;
 ptr+=4;                    /* skip over screen size  */
 colorbits=1+(*ptr)&0xf;    /* how many bits of color */
 ptr+=2;                    /* skip over background   */ 
 if (*ptr++)                /* should be zero         */
   {fprintf(stderr, "corrupt GIF file\n");
    free((char *) rawgif);
    return;
   }
 ptr+=(3*(1<<colorbits));   /* skip over colormap     */
 if (','!=(*ptr++))         /* image separator        */
   {fprintf(stderr, "corrupt GIF file\n");
    free((char *) rawgif);
    return;
   }
 ptr+=4;                    /* skip over image offset */
 gwidth=(*ptr)+0x100*(*(ptr+1));
 ptr+=2;
 gheight=(*ptr)+0x100*(*(ptr+1));
 ptr+=2;
 if (0x80&(*ptr++))           /* skip over local color map */
   ptr+=(3*(1<<colorbits));
      /* should now be at start of data */
 codesize=(*ptr++);
  /* make a place for the decompressed file */
 gvolume=gwidth*gheight;
 ptr1=(unsigned char *) malloc(gvolume);
 decompress(codesize,ptr,ptr1,gvolume);
 free((char *) rawgif);
  /* map picture into data, allowing for different dimensions */ 
 for (j=0;j<ysize;j++)
  {if (j>=gheight) break;
   for (i=0;i<xsize;i++)
    {if (i>=gwidth) break;
     data[i+j*xsize]=ptr1[i+j*gwidth];
    }
  }
 free((char *) ptr1);
 fixboundary();
 showpic();
 return;
}

savepic(data,xsize,ysize)  /* save the field as a GIF image */
unsigned char *data;       /* where the input data starts   */
int xsize,ysize;           /* picture dimensions            */
{int i;
 int colorbits=5,codesize=5; /* assume a 32 color image */
 FILE *outfile;
 if (NULL==(outfile=fopen(picturename,"w")))
   {fprintf(stderr,"couldn't open output file\n");
    return;
   }
  /* GIF signature */
 fwrite("GIF87a",6,1,outfile);
  /* screen descriptor */
 stringbuffer[0]=xsize&0xff;   /* screen width  */
 stringbuffer[1]=(xsize>>8)&0xff;
 stringbuffer[2]=ysize&0xff;   /* screen height */
 stringbuffer[3]=(ysize>>8)&0xff;
 stringbuffer[4]=(0x80)             /* M=1; global color map follows */
                |((colorbits-1)<<4) /* -1+ bits of color reslution   */
                |(colorbits-1);     /* -1+bits per pixel in image    */
 stringbuffer[5]=0; /* background color */
 stringbuffer[6]=0; /* should be zero   */
 fwrite(stringbuffer,7,1,outfile);
  /* global color map */
 for (i=0;i<(1<<colorbits);i++)
  {colorcell.pixel=translate[i];
   XQueryColor(display,cmap,&colorcell);
   fputc(colorcell.red,outfile);
   fputc(colorcell.green,outfile);
   fputc(colorcell.blue,outfile);
  }
  /* image descriptor */
 stringbuffer[0]=','; /* image descriptor separator */
 stringbuffer[1]=0;   /* image offset               */
 stringbuffer[2]=0;
 stringbuffer[3]=0;
 stringbuffer[4]=0;
 stringbuffer[5]=xsize&0xff;         /* image width  */
 stringbuffer[6]=(xsize>>8)&0xff;
 stringbuffer[7]=ysize&0xff;         /* image height */
 stringbuffer[8]=(ysize>>8)&0xff;
 stringbuffer[9]=0; /* use global color map, no interlace  */ 
 fwrite(stringbuffer,10,1,outfile);
    /* start of image data */
 fputc(codesize,outfile); 
 compress(codesize,data,outfile,volume); 
    /* gif terminator */
 fputc(';',outfile);
 fclose(outfile);
 return;
}

/* LZW compression */
/* hash function assumes TABLELENGTH is a power of 2 */
# define TABLELENGTH (1<<13)
unsigned char **addresses=NULL; /* where to find the string         */
int  *codes=NULL,               /* the code value                   */
     *linktonext=NULL,          /* the next index in the hash chain */
     *lengths=NULL,             /* the length of the coded string   */
     *codeindex=NULL;           /* the index for a given code       */ 
int nextcode;                   /* the next unused code             */

/* hashit is supposed to give a unique fairly random number in the table for
each length a and string b */

# define hashit(a,b) (51*a+53*(57*b[0]+59*(61*b[a-1]+b[a>>1])))&(TABLELENGTH-1)

compress(initcodesize,ptr,outfile,size)
int initcodesize; /* the initial compression bits */
char * ptr;       /* where the data comes from    */
FILE * outfile;   /* where the output goes        */
int size;         /* how much data                */
{int currentcode,prefixcode,codesize,maxbits=12,maxcode;
 int clearcode,eoicode,currentplace=0,length,blocksize=0,bitoffset;
 int findcode();
 unsigned long outputword;
 unsigned char blockbuffer[256]; /* to hold data blocks before writing */
  /* allocate space for hash tables */
 if (NULL==(codes=(int *) malloc(sizeof(int)*TABLELENGTH)))
  {fprintf(stderr,"compress: trouble allocating tables\n");
   currentplace=size;
  }
 if (NULL==(linktonext=(int *) malloc(sizeof(int)*TABLELENGTH)))
  {fprintf(stderr,"compress: trouble allocating tables\n");
   currentplace=size;
  }
 if (NULL==(lengths=(int *) malloc(sizeof(int)*TABLELENGTH)))
  {fprintf(stderr,"compress: trouble allocating tables\n");
   currentplace=size;
  }
   /* need one extra place in codeindex for overflow before resetting: */
 if (NULL==(codeindex=(int *) malloc(sizeof(int)*4097)))
  {fprintf(stderr,"compress: trouble allocating tables\n");
   currentplace=size;
  }
 if (NULL==(addresses=(unsigned char **) malloc(sizeof(char *)*TABLELENGTH)))
  {fprintf(stderr,"compress: trouble allocating tables\n");
   currentplace=size;
  }
   /* set up initial code table */
 inittable(initcodesize);
 clearcode=(1<<initcodesize);
 eoicode=clearcode+1;
 codesize=initcodesize+1;
 maxcode=1<<codesize;
 nextcode=eoicode+1;
  /* start with a clear code */
 outputword=clearcode;
 bitoffset=codesize; 
   /* now do the compressing */
 while (currentplace<size)
  {   /* check if codesize needs increasing */
   if (nextcode>maxcode)
    {codesize++;
     maxcode=1<<codesize;
     /* if too big, then reset compressor */
     if (codesize>maxbits)
      {if (bitoffset) outputword|=(clearcode<<bitoffset);
       else outputword=clearcode;
       bitoffset+=maxbits;
       inittable(initcodesize);
       codesize=initcodesize+1;
       maxcode=1<<codesize;
       nextcode=eoicode+1;
      }
    }
    /* look for an unstored string */
   length=1;
   while (nextcode>
            (currentcode=findcode(length,(char *)(ptr+currentplace))))
    {prefixcode=currentcode;
     length++;
     if ((currentplace+length)>=size) break;
    }
   nextcode++;
   currentplace+=(length-1);
    /* output the prefix code */
   if (bitoffset)  outputword|=(prefixcode<<bitoffset);
   else outputword=prefixcode;
   bitoffset+=codesize;
    /* output finished bytes to blocks */
   while (bitoffset>=8)
     {blockbuffer[blocksize]=outputword&0xff;
      outputword>>=8;
      bitoffset-=8;
      blocksize++;
        /* output filled block */
      if (blocksize>=254)
        {fputc((char) blocksize, outfile);
         fwrite(blockbuffer,blocksize,1,outfile);
         blocksize=0;
        }
     }
  }
   /* output the end of information code */
 if (bitoffset) outputword|=(eoicode<<bitoffset);
 else outputword=eoicode;
 bitoffset+=codesize;
   /* finish outputting the data */
 while (bitoffset>=0) 
     {blockbuffer[blocksize]=(char) (outputword&0xff);
      outputword>>=8;
      bitoffset-=8;
      blocksize++;
      if (blocksize>=254)
        {fputc((char) blocksize, outfile);
         fwrite(blockbuffer,blocksize,1,outfile);
         blocksize=0;
        }
     }
   /* output the last block */
 if (blocksize) 
   {fputc((char) blocksize, outfile);
    fwrite(blockbuffer,blocksize,1,outfile);
   }
  /* a final zero block count */
 fputc(0, outfile);
  /* deallocate tables */
 if (NULL!=codes) free((char *) codes);
 if (NULL!=linktonext) free((char *) linktonext);
 if (NULL!=lengths) free((char *) lengths);
 if (NULL!=codeindex) free((char *) codeindex);
 if (NULL!=addresses) free((char *) addresses);
 codes=linktonext=lengths=codeindex=NULL;
 addresses=(unsigned char **) NULL;
 return;
}

decompress(initcodesize,ptr,ptr1,size)
int initcodesize;
unsigned char *ptr, *ptr1; /* compressed data from ptr go to ptr1 */
int size;                  /* an upper limit purely as a check    */
{int i,currentcode,codesize,maxbits=12,blocksize;
 int clearcode,eoicode,codemask;
 int bitoffset=0,indx,oldindx;
 int currentplace=0,oldplace=0;
 int findcode();
 unsigned long inputword=0;
 unsigned char *p1, *p2;
   /* first deblock the data */
 p1=p2=ptr;
 blocksize=(*p1++);
 while (blocksize)
  {while (blocksize--)
    (*p2++)=(*p1++); /* a wonderful example of how abstruse C can be */
   blocksize=(*p1++);
  }
   /* set up initial code table */
 currentcode=clearcode=(1<<initcodesize);
 eoicode=clearcode+1;
  /* allocate space for hash table */
 if (NULL==(codes=(int *) malloc(sizeof(int)*TABLELENGTH)))
  {fprintf(stderr,"decompress: trouble allocating tables\n");
   currentcode=eoicode;
  }
 if (NULL==(linktonext=(int *) malloc(sizeof(int)*TABLELENGTH)))
  {fprintf(stderr,"decompress: trouble allocating tables\n");
   currentcode=eoicode;
  }
 if (NULL==(lengths=(int *) malloc(sizeof(int)*TABLELENGTH)))
  {fprintf(stderr,"decompress: trouble allocating tables\n");
   currentcode=eoicode;
  }
   /* need one extra place in codeindex for overflow before resetting: */
 if (NULL==(codeindex=(int *) malloc(sizeof(int)*4097)))
  {fprintf(stderr,"compress: trouble allocating tables\n");
   currentcode=eoicode;
  }
 if (NULL==(addresses=(unsigned char **) malloc(sizeof(char*)*TABLELENGTH)))
  {fprintf(stderr,"decompress: trouble allocating tables\n");
   currentplace=eoicode;
  }
 while (currentcode!=eoicode)
  {if (currentcode==clearcode) /* reset the decompressor */
      {inittable(initcodesize);
       codesize=initcodesize+1;
       nextcode=eoicode+1;
       codemask=(1<<codesize)-1;
       oldindx=(-1);
      }
   else /* code represents data */
    {indx=codeindex[currentcode]; /* where in table is currentcode */
     if (indx>=0) /* it is there */
      { /* put it into the output */
       for (i=0;i<lengths[indx];i++)
         ptr1[currentplace+i]=addresses[indx][i];
       if (oldindx>=0) /* first character treated differently */
        {findcode(lengths[oldindx]+1,ptr1+oldplace);
         nextcode++;  /* add new code to table */
        }
       oldplace=currentplace;
       currentplace+=lengths[indx];
       oldindx=indx;
      }
     else /* not in table yet; must be old code plus last=first character */
      {for (i=0;i<lengths[oldindx];i++)
         ptr1[currentplace+i]=addresses[oldindx][i];
       ptr1[currentplace+lengths[oldindx]]=addresses[oldindx][0];
       findcode(lengths[oldindx]+1,ptr1+currentplace); /* store new code */
       oldplace=currentplace;
       currentplace+=lengths[oldindx]+1;
       oldindx=codeindex[nextcode++];
      }
      /* crude error checking */
     if ((oldindx<0)||(currentplace>size))
      {fprintf(stderr,"gif file appears to be corrupt\n");
       break;
      }
    } 
     /* check if codesize needs increasing */     
   if (nextcode>codemask)
      if (codesize<maxbits)
        {codesize++;
         codemask=(1<<codesize)-1;
        }
   while (bitoffset<codesize) /* read some more data */
    {if (bitoffset) inputword|=(((int)(*ptr++))<<bitoffset);
     else inputword=(*ptr++);
     bitoffset+=8;
    } 
    /* strip off current code */
   currentcode=inputword&codemask;
   inputword>>=codesize;
   bitoffset-=codesize;
   if (currentcode>nextcode) 
      {fprintf(stderr,"gif file appears to be corrupt\n");
       break;
      }
  }
  /* deallocate tables */
 if (NULL!=codes) free((char *) codes);
 if (NULL!=linktonext) free((char *) linktonext);
 if (NULL!=lengths) free((char *) lengths);
 if (NULL!=codeindex) free((char *) codeindex);
 if (NULL!=addresses) free((char *) addresses);
 codes=linktonext=lengths=codeindex=NULL;
 addresses=(unsigned char **) NULL;
 return;
}

inittable(size)
int size;
{int i;
 for (i=0;i<TABLELENGTH;i++)
  {linktonext[i]=(-1);
   codes[i]=(-1);
   lengths[i]=(-1);
  }
 for (i=0;i<4096;i++)
   codeindex[i]=(-1);
  /* store initial codes for raw characters */
 nextcode=0;
 for (i=0;i<(1<<size);i++)
  {stringbuffer[i]=i;
   findcode(1,stringbuffer+i);
   nextcode++;
  }
 return;
}

findcode(length,string)
unsigned char * string;
int length;
 /* return code for string of given length;  
    if not found, store it and return nextcode */
{int i,j,indx,previousindex;
 indx=hashit(length,string); 
  /* look for string in table */
 previousindex=indx;
 while (indx>0)
  {if (lengths[indx]==length) /* is the length right ? */
    {for (j=0;j<length;j++)
      if ((string[j]) != (addresses[indx][j])) break;
     if (j==length) return codes[indx]; 
    }
   previousindex=indx;
   indx=linktonext[indx];
  } 
  /* not found, so store it */
 indx=previousindex;
 i=indx;
 while (codes[i]>=0) /* find an unused slot in table */
  {i++;
   if (i>=TABLELENGTH) i-=TABLELENGTH;
  }
 if (i!=indx) 
     {linktonext[indx]=i;  /* link to it */
      indx=i;              /* move to it */
     }
 codes[indx]=nextcode; /* save the new code */
 lengths[indx]=length;
 addresses[indx]=string;
 codeindex[nextcode]=indx; 
 return nextcode;
}