/* xevolve.c (based on xsand.c, by Michael Creutz)

   Benjamin Moody, February 1999

 compiling:  cc -O -o xevolve -L/usr/X11R6/lib xevolve.c -lX11 
*/


# 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>
# include <time.h>
# include <math.h>

# define BPW (sizeof(long))
# define MAX_VAL 1.0     /* max value for fitness */
# define LAMBDA_C  ((2.0 / 3.0) * MAX_VAL)
# define CAT_TSCALE 2000   /* scale for cat time */
# define CAT_MIN 50        /* minimum cat timer  */
# define COLORS 64         /* for the lo-color version */

# define SRNULL 0
# define SRGIF 1
# define SRTXT 2

struct species
{
  float fitness;
  struct species *prev;
  struct species *next;
};

struct species *fmain;

int soc=0, count, srtype=SRGIF, catapen=0, cattime;
float catsize=0;
FILE *recfile;

struct species * smallest(struct species *first); 
struct species * init(int nspec);
struct species * element(int ind, struct species *first);
void saddon(int nspec);
/* void execute(int iter, struct species *first);
   void displayit(struct species *first, struct species *smallest);*/
void checkSoc(struct species *smallest);
void outascii();
void inascii();
void recordstep();
void catastrophe(int place, float size);
void cattimer();

/* size and position parameters for buttons, etc. */
# define PLAYTOP 116
# define PLAYLEFT 10
# define BOUNDHEIGHT 72
# define TRACEHEIGHT 36
# define BOUNDWIDTH  112
# define BARHEIGHT 15
# define BARWIDTH  256
# define BARTOP 8
# define BARLEFT 40
# define SRHEIGHT (3*18)
# define BUTTONWIDTH 68

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 paused=0,        /* is the system paused?                  */
    boundary,        /* 0,1,2,3 for open, live, periodic, flow */
    pencolor=4,      /* for sketching                          */
    trace,           /* is the tracer on?                      */
    colshift,        /* how to shift to get the next column    */
    active=1,
    record=0;
long mask0x13,mask0x01,mask0x03,mask0x10; /* some useful masks */
char stringbuffer[256];              /* generally useful       */
  /* things for regulating the updating speed */
int speed=0; /* updating delay proportional to speed   */
int delay=0; /* counter for implementing speed control */
struct timeval timeout; /* timer for speed control */

/* various window stuff */
Display *display;
int screen;
static char *progname;
Window window,quitbutton,pausebutton,playground,srbutton,blockbutton,
    boundwindow,colorbar,fillbutton,tracewindow,doublebutton,adbutton,
    speedbutton,makebutton();
XColor xcolor,colorcell;
Colormap cmap;
GC gc,gcpen;
int windowwidth,windowheight;
XFontStruct *font=NULL;
int font_height,font_width;
XSizeHints size_hints;
int darkcolor,lightcolor,black,white;
XImage *spinimage=NULL;
long translate[COLORS];                /* for converting colors   */
char * boundtext[4]={"open","sandy","periodic","flow"};
char * srtext[3]={"save","restore","GIF"};
void drawbutton(),settrace(),openwindow(),makebuttons(),update(),repaint(),
     cleanup(),fixboundary(),showpic(),setboundary(),sketch(),savepic(),
     addpic(),setpen(),parallelupdate(),decompress(),compress(),inittable();

struct species * init (int nspec)
{
  int i;
  struct species *s;
  
  srand((unsigned int)time(NULL));
  s = (struct species *) malloc(nspec * sizeof(struct species));
  for (i = 0; i < nspec; i++) {
    s[i].next = &s[i+1];
    s[i].prev = &s[i-1];
    s[i].fitness = rand() * MAX_VAL / RAND_MAX ; 
  }
  s[0].prev = &s[nspec-1];
  s[nspec-1].next = &s[0];
  return s;
}

void saddon(int nspec)
{
  int i;
  struct species *s;

  if (nspec > 0) {
    srand((unsigned int)time(NULL));

    s = (struct species *) malloc(nspec * sizeof(struct species));
    
    for (i = 0; i < nspec; i++) {
      s[i].next = &s[i+1];
      s[i].prev = &s[i-1];
      s[i].fitness = rand() * MAX_VAL / RAND_MAX ; 
    }
    s->prev = fmain->prev;
    fmain->prev->next = s;
    s[nspec-1].next = fmain;    
    fmain->prev = &(s[nspec-1]);
  }
  else {
    s = fmain->prev;
    for (i = 0; i > nspec; i--) {
      s = s -> prev;
    }
    s->next = fmain;
    fmain->prev = s;
  }
}

struct species * element(int ind, struct species *first)
{
  struct species *s;
  int fi;
  
  s=first;
  for (fi=0; fi<ind; fi++) {
    s = s->next;
  }
  return s;
}

float minfitness, meanfitness;

struct species * smallest(struct species *first)
{
  float currentval=(MAX_VAL + 1.0);
  float sumfitness = 0.0;
  struct species *current;
  struct species *best;

  if(first==NULL)
    return NULL;

  current = first;
  do {
    if(current->fitness < currentval) {
      currentval = current->fitness;
      best = current;
    }
    sumfitness += current->fitness;
    current = current->next;
  } while (current!=first);
    minfitness = currentval;
  if (ncols > 0)
    meanfitness = sumfitness / ncols;
  return best;
}

void checkSoc(struct species *smallest)
{
  if(soc==0) {
    // reset command here
    if((smallest->fitness) < LAMBDA_C) {
      // activation command here
      soc=1;
    }
  }
}

void outascii()
{
  FILE *outfile;
  struct species *current;
  int i;

  outfile = fopen("xevolve.txt", "w");

  for (current = fmain, i = 0; i < ncols; i++, current = current->next) {
    fprintf(outfile, "%d %f\n", i, current->fitness);
  }
  fclose(outfile);
}

void inascii()
{
  FILE *infile;
  struct species *current;
  int i, ind;

  infile = fopen("xevolve.txt", "r");

  for (i = 0, current = fmain; i < ncols; current = current->next, i++) {
    fscanf(infile, "%d", &ind);
    fscanf(infile, "%f", &(current->fitness));
  }
  fclose(infile);
}

void recordstep()
{
  /*struct species *current;
  int i;

  for(current = fmain, i = 0; i < ncols; i++, current = current->next) {
    fprintf(recfile, "%f ", current->fitness);
    }*/
    if(trace == 1)
      cattimer();

  if(recfile == NULL)
    return;

  if (catsize > 0)
    fprintf(recfile, "%g %g %g\n", minfitness, meanfitness, catsize);
  else
    fprintf(recfile, "%g %g\n", minfitness, meanfitness);
}

void cattimer()
{
  int xplace;
  float xsize, timething;

  if(cattime == 0) {
    xplace = rand() * ncols / RAND_MAX;
    xsize = (float)rand() / RAND_MAX;
    catastrophe(xplace, xsize);

    //    cattime = CAT_MIN + ((CAT_TSCALE * rand()) / RAND_MAX);
    timething = (float) rand() / RAND_MAX;
    cattime = CAT_MIN + CAT_TSCALE * timething;

    fprintf(stderr, "debugging: next cat in %d frames\n", cattime);
  }
  cattime--;
}

int dist(int s1, int s2)
{
  int answer, su;

  answer = s2 - s1;

  if(answer > ncols / 2) {
    su = s1 + ncols;
    answer = su - s2;
  }
  if(answer < -(ncols / 2)) {
    su = s2 + ncols;
    answer = su - s1;
  }
  answer = abs(answer);
  return answer;
}

/* A catastrophe!   place is an index, size is between 0 and 1*/
void catastrophe(int place, float size)
{
  struct species *current;
  float dis, prob, randnum;
  int i, counter=0; /* counter is only for debug */

  fprintf(stderr, "Catastrophe: Called with place %d and size %f\n", place, size);

  for (i = 0, current = fmain; i < ncols; i++, current = current->next) {
    dis = (float) dist(place, i);
    if (dis != 0) {
      prob = ( ((float)ncols / 2) - dis ) * size * 2 / (float)ncols;
      //prob =   closeness (1 to ncols/2)   * size / ncols/2... This gives a number from 0 to 1...
    }
    else {
      prob = size;
    }
    randnum = ((float) rand()) / RAND_MAX;
    if(randnum < prob) {
      current->fitness *= ( ((float) rand()) / RAND_MAX) ;
      counter++;
    }
  }
  //  fprintf(stderr, "Catastrophe: Changed fitness of %d species\n", counter);
  catsize = size;
}

void main(int argc, char **argv)
{
    unsigned int width, height;
    int i,x,y;
    long bitcheck;
    XEvent report;
    FILE *tempfile;

    progname=argv[0];

    /* initial lattice size */
    block=1;
    nrows=200/block;
    ncols=(~(BPW-1))&(200/block);
    volume=nrows*ncols;
    fmain = init(ncols);
    count = ncols;
    trace=0;
    boundary=0;
    /* open the window and make the buttons */
    openwindow(argc,argv);
    makebuttons();
    recfile = fopen("xevolverec.txt", "a");

    /* 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 */
    while(1) {
	if (0==paused) {
	    if (delay) { /* don't update yet */
		delay--;
		/* this use of select() seems a kludge to me; 
		   why can't usleep() be more standard? */
		timeout.tv_sec=0;
		timeout.tv_usec=100000; /* .1 sec per delay unit */
		select(0,NULL,NULL,NULL,&timeout); 
	    }
	    else {
		delay=speed;
		update();
	    }
	}
	if (paused|XPending(display)|((active|0x0)==0)) {
	    XNextEvent(display,&report); 
	    switch (report.type) {
	    case Expose:
		if ((report.xexpose.window)!=window) break;
		/* cuts down flashing, but you might remove this line
		   if things aren't being redrawn */
		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;  
		    XSetForeground(display,gcpen,lightcolor);  
		    XFillRectangle(display,window,gcpen,0,0,windowwidth,
				   windowheight);
		    nrows=(height-PLAYTOP-10)/block;
		    ncols=(~(BPW-1))&((width-PLAYLEFT-BOUNDWIDTH-20)/block);
		    volume=nrows*ncols;
		    saddon(ncols - count);
		    count = ncols;
		    /* for (i=0; i<ncols; i++)
		       (element(i, fmain)).fitness = ((float)pencolor) / 256.0; this was to fill each time */
		    soc=0;
		    makebuttons();
		    //    fixboundary();
		    showpic();
		} 
		break; 
	    case ButtonPress:
		if (report.xbutton.window==quitbutton)
		    cleanup();
		else if (report.xbutton.window==pausebutton) {
		    paused=1-paused;
		    drawbutton(pausebutton,0,0,BUTTONWIDTH,18,"pause",
			       1-2*paused);
		} 
		else if (report.xbutton.window==fillbutton) {
		    drawbutton(fillbutton,0,0,BUTTONWIDTH,18,"fill",-1);
		    /* for (i=0;i<volume;i++)
		       field[old][i]=pencolor;*/
		    for (i=0;i<ncols;i++)
		      (element(i, fmain))->fitness=((float)pencolor) / COLORS;
		    //	    fixboundary();
		    showpic();
		    drawbutton(fillbutton,0,0,BUTTONWIDTH,18,"fill",1);
		}
		else if (report.xbutton.window==boundwindow) {
		  //    setboundary((report.xbutton.y*4)/BOUNDHEIGHT);
		    showpic();
		}
		else if (report.xbutton.window==tracewindow)
		    settrace((report.xbutton.y*2)/TRACEHEIGHT);
		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==srbutton) {
		    /* save or restore */
		    y=(report.xbutton.y*3)/SRHEIGHT; 
		    drawbutton(srbutton,0,y*(SRHEIGHT/3),BUTTONWIDTH, SRHEIGHT/3,srtext[y],-1);


		    if (srtype == SRGIF) {
		      if (0==y)
			savepic(field[old],ncols,nrows);
		      else if (1==y) { /* load in gif image */
			for (i=0;i<volume;i++)
			  field[old][i]=0;
			addpic(field[old],ncols,nrows);
			
			for (i=volume; i>(volume-ncols); i--) {
			  (element((i-1), fmain))->fitness = ((float) field[old][i-1]) / COLORS;
			}
			
			showpic();
		      }
		      else { /* add gif image mod 256 to existing field *//*
				addpic(field[old],ncols,nrows);
				for (i=0;i<volume;i++)
				field[old][i]&=7;
				showpic();*/
			/* instead, op ascii *//* but no
			   outascii();*/
			/* change mode */
			srtype = SRNULL;
			srtext[2] = "Text";
		      }
		    }

		    if (srtype == SRTXT) {
		      if (0==y)
			outascii();
		      else if (1==y) { /* load in text */
			inascii();
		      }
		      else { /* add gif image mod 256 to existing field *//*
				addpic(field[old],ncols,nrows);
				for (i=0;i<volume;i++)
				field[old][i]&=7;
				showpic();*/
			/* instead, op ascii *//* but no
			   outascii();*/
			/* change mode */
			srtype = SRGIF;
			srtext[2] = "GIF";
		      }
		    }

		    if (srtype == SRNULL)
		      srtype = SRTXT;

		    drawbutton(srbutton,0,y*(SRHEIGHT/3),BUTTONWIDTH,SRHEIGHT/3,srtext[y],1);
		}
		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;
			saddon(ncols-count);
			count = ncols;
			soc=0;
			XSetForeground(display,gcpen,lightcolor);  
			XFillRectangle(display,window,gcpen,0,0,
				       windowwidth,windowheight);
			makebuttons();
			//	fixboundary();
			showpic();
		    }
		}
		else if (report.xbutton.window==colorbar)
		    setpen((report.xbutton.x*COLORS)/BARWIDTH);
		else if (report.xbutton.window==adbutton) {
		  /* autodouble=1-autodouble;*/
		  record = 1-record;
		  if(record == 1) {
		    if (recfile) fclose(recfile);
		    recfile = fopen("xevolverec.txt", "w");
		  }
		  drawbutton(adbutton,0,0,BUTTONWIDTH,18,"record",1-2*record);
		}
		else if (report.xbutton.window==doublebutton) {
		    drawbutton(doublebutton,0,0,BUTTONWIDTH,18,"random",-1);
		    /* for (i=0;i<volume;i++)
		       field[old][i]=7&(field[old][i]<<1);
		       active=1;*/
		    fmain=init(ncols);
		    soc=0;
		    //    fixboundary();
		    repaint();
		    showpic(); 
		    drawbutton(doublebutton,0,0,BUTTONWIDTH,18,"random",1);
		}
		else if (report.xbutton.window==speedbutton) {
		    /* reset speed */
		    speed=10-(11*report.xbutton.x)/BOUNDWIDTH;
		    if (speed<0) speed=0;
		    if (speed>10) speed=10;
		    delay=speed;
		    drawbutton(speedbutton,0,0,BOUNDWIDTH,18,"speed",-1);
		    drawbutton(speedbutton,1+((10-speed)*(BOUNDWIDTH-2))/11,1,
			       (BOUNDWIDTH-2)/11,16,"",2);
		}
		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 */

void sketch(int x, int y)   /* sketch in playground starting at point 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;
    Cursor cursor;


    if (catapen == 0) {
      newx=x;
      newy=y;
      /* field[old][x+ncols*y]=pencolor;*/
      (element(x, fmain))->fitness=((float)pencolor) / COLORS;
      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++)
	      (element ((oldx+i*(newx-oldx)/deltax), fmain))->fitness=((float)pencolor) / COLORS;
	  else 
	    for (i=1;i<=deltay;i++)
	      (element ((oldx+i*(newx-oldx)/deltay), fmain))->fitness=((float)pencolor) / COLORS;
	  break;
	case ButtonRelease:
	default:
	  sketching=0;
	  break;
	} 
      }
      //   fixboundary();
      showpic();
      return;
    }
    else {
      drawbutton(tracewindow, 0, TRACEHEIGHT/2, BOUNDWIDTH, TRACEHEIGHT/2, "catastrophe", 1);
      catapen = 0;
      cursor=XCreateFontCursor(display,XC_pencil); 
      XDefineCursor(display,playground,cursor);
      catastrophe(x, 1.0 - ( ((float)y) / ((float)nrows) ));
    }
}

void update()
{
    int i, j;
    struct species *s;

    if(trace == 1)
      cattimer();
    if(record == 1)
      recordstep();

    s = smallest(fmain);
    s->fitness = rand() * MAX_VAL / RAND_MAX ;
    (s->prev)->fitness = rand() * MAX_VAL / RAND_MAX;
    (s->next)->fitness = rand() * MAX_VAL / RAND_MAX;
    checkSoc(s);
    for (i = ncols, j = 0; i < volume; i++, j++)
      field[new][j] = field[old][i];
    for (s = fmain; j < volume; j++, s = s->next)
      field[new][j] = (char)((s->fitness) * COLORS);

    catsize = 0;
    old=new;
    new=1-new;
    showpic(); 
    return;
}

void showpic() /* display the field */
{
    int row,col,i1,i2,color,j,j1,j2,blocktop=block;
    char *picture=(*spinimage).data;
    if (block>4) blocktop=block-1;
    if (8==(*spinimage).depth) {
	if (block>1) /* I wish I knew how to do this faster */
	    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
	    for (j=0;j<volume;j++)
		picture[j]=translate[field[old][j]];
    }
    else {	 /* depth is not 8, use xputpixel (this is really ugly) */
	if (block>1) /* I wish I knew how to do this faster */
	    for (row=0;row<nrows;row++)
		for (col=0;col<ncols;col++) {
		    color=translate[field[old][row*ncols+col]];
		    if (color!=XGetPixel(spinimage,j1=block*col,j2=block*row))
			for (i2=0;i2<blocktop;i2++)
			    for (i1=0;i1<blocktop;i1++)
				XPutPixel(spinimage,j1+i1,j2+i2,color);
		}
	else
	    for (row=0;row<nrows;row++) {
		j1=row*ncols; 
		for (col=0;col<ncols;col++)
		    XPutPixel(spinimage,col,row,translate[field[old][j1+col]]);
	    }
    }
    XPutImage(display,playground,gc,spinimage,0,0,0,0,block*ncols,block*nrows);
    return;
}

/* this fixes the window up whenever it is uncovered */
void repaint()
{
    int i;
    drawbutton(pausebutton,0,0,BUTTONWIDTH,18,"pause",1-2*paused);
    drawbutton(quitbutton,0,0,BUTTONWIDTH,18,"quit",1);
    drawbutton(fillbutton,0,0,BUTTONWIDTH,18,"fill",1);
    drawbutton(doublebutton,0,0,BUTTONWIDTH,18,"random",1);
    drawbutton(adbutton,0,0,BUTTONWIDTH,18,"record",1-2*record);
    drawbutton(window,PLAYLEFT-4,PLAYTOP-4,block*ncols+8,block*nrows+8,NULL,4);
    drawbutton(speedbutton,0,0,BOUNDWIDTH,18,"speed",-1);
    drawbutton(speedbutton,1+((10-speed)*(BOUNDWIDTH-2))/11,1,
	       (BOUNDWIDTH-2)/11,16,"",2);
                      /* I changed this from i<3 to i<2 so it doesn't draw the +saved button */
                      /* then I changed it back! */
    for (i=0;i<3;i++)
	drawbutton(srbutton,0,i*(SRHEIGHT/3),BUTTONWIDTH,SRHEIGHT/3,
		   srtext[i],1);

    /* fix the block buttons */
    for (i=1;i<=4;i++) {
	sprintf(stringbuffer,"%d",(1<<i)/2);
	drawbutton(blockbutton,(i-1)*BOUNDWIDTH/4,0,BOUNDWIDTH/4,18,
		   stringbuffer,1-2*(i==(blockshift+1)));
    } 
    XDrawString(display,window,gc,BARLEFT+24,BARTOP+68,"cell size",9);

    /* draw the boundary condition buttons */
    /*    for (i=0;i<4;i++)
	drawbutton(boundwindow,0,i*BOUNDHEIGHT/4,BOUNDWIDTH,BOUNDHEIGHT/4,
	boundtext[i],1-2*(i==boundary));*/
    if(soc == 1) {
      // special command here
      // XDrawString(display,window,gc, windowwidth-BOUNDWIDTH,BOUNDHEIGHT+font_height+2, "Passed SOC",12);
    }
    /* draw the trace buttons */
    drawbutton(tracewindow,0,0,BOUNDWIDTH,TRACEHEIGHT/2,
	       "auto cat",1-2*trace);
    drawbutton(tracewindow,0,TRACEHEIGHT/2,BOUNDWIDTH,TRACEHEIGHT/2,
    "catastrophe",1);

    /* fix the colorbar */
    drawbutton(colorbar,0,0, BARWIDTH,BARHEIGHT,NULL,2);

    for (i=0;i<COLORS;i++) {
	XSetForeground(display,gcpen,translate[i]);
	XFillRectangle(display,colorbar,gcpen,i*BARWIDTH/COLORS,2,
		       BARWIDTH/COLORS+1,BARHEIGHT-4);
    }
    XSetForeground(display,gcpen,black);
    XFillRectangle(display,window,gcpen,(int)(BARLEFT+LAMBDA_C*BARWIDTH),BARTOP+BARHEIGHT, 3, BARHEIGHT);
    sprintf(stringbuffer,"least fit");
    XDrawString(display,window,gc,4+BARLEFT-40,BARTOP+28,stringbuffer,9);
    sprintf(stringbuffer,"most fit");
    XDrawString(display,window,gc,4+BARLEFT+BARWIDTH-40,BARTOP+28,stringbuffer,8);

    /* write various strings */
    sprintf(stringbuffer,"%d species, %d steps ",ncols,nrows);
    XDrawImageString(display,window,gc,BARLEFT-30,100,
		     stringbuffer,strlen(stringbuffer));
    showpic();  
    return;
}
 
/* take action if trace buttons hit */
void settrace(int value)
{
  Cursor cursor;
  float timething;

  if (1==value) {
    drawbutton(tracewindow, 0, TRACEHEIGHT/2, BOUNDWIDTH, TRACEHEIGHT/2, "catastrophe", -1);
    catapen = 1;
    cursor=XCreateFontCursor(display,XC_pirate); 
    XDefineCursor(display,playground,cursor);
  }
  else { 
      trace=1-trace;
      drawbutton(tracewindow,0,0,BOUNDWIDTH,TRACEHEIGHT/2,"auto cat",1-2*trace);
      if(trace == 1) {
	timething = (float) rand() / RAND_MAX;
	cattime = CAT_MIN + CAT_TSCALE * timething;
	fprintf(stderr, "debugging: next cat in %d frames\n", cattime);
      }
  }
}


/* take action if pen buttons hit */
void setpen(int value)
{
    pencolor=valuue;
    catapen = 0; /* clear catapen after clicking on colorbar */
    return;
}

/* a lot of this is taken from basicwin in the Xlib Programming Manual */                                                   /* Color info starts here*/
void openwindow(int argc, char **argv)
{
    char *window_name="Evolution";
    char *icon_name="Evolution";
    long event_mask;
    Pixmap icon_pixmap;
    char *display_name=NULL;
    int i;
# define icon_bitmap_width 16
# define icon_bitmap_height 16
    static unsigned 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};
    XWMHints wm_hints;
    XClassHint class_hints;
    XTextProperty windowName, iconName;

    /* 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);
    cmap=DefaultColormap(display,screen);

    darkcolor=black=BlackPixel(display,screen);
    lightcolor=white=WhitePixel(display,screen);
    translate[0]=white;
    translate[1]=black;
    translate[2]=lightcolor;
    translate[3]=darkcolor;
    if (XAllocNamedColor(display,cmap,"salmon",&colorcell,&xcolor))
	darkcolor=colorcell.pixel;
    if (XAllocNamedColor(display,cmap,"wheat",&colorcell,&xcolor))
	lightcolor=colorcell.pixel;
    for (i=0; i<(COLORS/2); i++) {
      colorcell.red = 256 * (255 - (512 * i / COLORS));
      colorcell.green = 131072 * i / COLORS;
      colorcell.blue = 0;
      colorcell.flags = DoRed | DoGreen | DoBlue;
      if(XAllocColor(display, cmap, &colorcell))
	translate[i] = colorcell.pixel;
    }      
    for ( ; i<COLORS; i++) {
      colorcell.red = 0;
      colorcell.green = 256 * (255 - (512 * i/ COLORS));
      colorcell.blue = 131072 * i / COLORS;
      colorcell.flags = DoRed | DoGreen | DoBlue;
      if(XAllocColor(display, cmap, &colorcell))
	translate[i] = colorcell.pixel;
    }      

 /* 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;
    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);

    /* 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,
    the fixed font option put in by Peter Chang */
    if ((font=XLoadQueryFont(display,"9x15"))==NULL) 
	if ((font=XLoadQueryFont(display,"fixed"))==NULL) {
	    fprintf(stderr,"%s: Sorry, having font problems.\n",progname);
	    exit(-1);
	}
    font_height=font->ascent+font->descent;
    font_width=font->max_bounds.width;

    /* make graphics contexts: 
    gc for black on white
    gcpen for varying purposes */
   
    gc=XCreateGC(display,window,0,NULL);
    XSetFont(display,gc,font->fid);
    XSetForeground(display,gc,black);
    XSetBackground(display,gc,lightcolor); 

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

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

void makebuttons()
{
    int i,j;
    long event_mask;
    XEvent report;
    Cursor cursor;
    /* first destroy any old buttons */
    XDestroySubwindows(display,window);
    /* now make the new buttons */
    quitbutton =makebutton(windowwidth-92,windowheight-38,    BUTTONWIDTH,18);
    pausebutton=makebutton(windowwidth-92,windowheight-38- 18,BUTTONWIDTH,18);
    fillbutton =makebutton(windowwidth-92,windowheight-38-2*18,BUTTONWIDTH,18);
    doublebutton=makebutton(windowwidth-92,windowheight-38-3*18,BUTTONWIDTH,18);
    adbutton   =makebutton(windowwidth-92,windowheight-38-4*18,BUTTONWIDTH,18);
    srbutton =makebutton(windowwidth-92,windowheight-38-7*18,BUTTONWIDTH,18*3);
    //    boundwindow =makebutton(windowwidth-BOUNDWIDTH-4,4,BOUNDWIDTH,BOUNDHEIGHT);
    tracewindow =makebutton(windowwidth-BOUNDWIDTH-4,BOUNDHEIGHT+25,BOUNDWIDTH,TRACEHEIGHT);
    colorbar    =makebutton(BARLEFT,BARTOP,BARWIDTH,BARHEIGHT);
    blockbutton =makebutton(BARLEFT+12,BARTOP+36,BOUNDWIDTH,18);
    speedbutton=makebutton(windowwidth-BOUNDWIDTH-4,
			   BOUNDHEIGHT+TRACEHEIGHT+30,
			   BOUNDWIDTH,18);

    playground=XCreateSimpleWindow(display,window,
				   PLAYLEFT,PLAYTOP,block*ncols,block*nrows,
				   0,black,translate[8]);
    event_mask=ExposureMask|ButtonReleaseMask|ButtonPressMask|
	PointerMotionHintMask|ButtonMotionMask; 
    XSelectInput(display,playground,event_mask);
    XMapWindow(display,playground);

    /* wait for playground to be displayed befor proceeding */
    i=1; /* a flag */
    while (i) {
	XNextEvent(display,&report); 
	switch (report.type) {
	case Expose:
	    if (report.xexpose.window!=playground) i=0;
	default:
	    break;
	}
    }
    /* make image structure */
    if (NULL!=spinimage) {
	XDestroyImage(spinimage); 
	spinimage=NULL;
    }
    spinimage=XGetImage((Display *) display, (Drawable) playground,
			0,0,block*ncols,block*nrows,AllPlanes,ZPixmap);
    if (NULL==spinimage) {
	fprintf(stderr,"trouble creating image structure\n");
	exit(-1);
    } 
    /* make special cursors to be cute */
    cursor=XCreateFontCursor(display,XC_pencil); 
    XDefineCursor(display,playground,cursor);
    cursor=XCreateFontCursor(display,XC_hand1);
    XDefineCursor(display,doublebutton,cursor);
    XDefineCursor(display,colorbar,cursor);
    //    XDefineCursor(display,boundwindow,cursor);
    XDefineCursor(display,tracewindow,cursor);
    XDefineCursor(display,srbutton,cursor);
    XDefineCursor(display,blockbutton,cursor);
    XDefineCursor(display,fillbutton,cursor);
    XDefineCursor(display,adbutton,cursor);
    XDefineCursor(display,fillbutton,cursor);
    XDefineCursor(display,quitbutton,cursor);
    XDefineCursor(display,pausebutton,cursor);
    XDefineCursor(display,speedbutton,cursor);

    /* reallocate various arrays */
    /* allocate a few bytes of extra space at ends of field array */
    for (i=0;i<2;i++) {
	if (NULL!=field[i])  free((char *) field[i]-BPW);
	if (NULL==( field[i]= (unsigned char *) malloc(volume+2*BPW))) {
	    fprintf(stderr,"allocation problems\n");
	    cleanup();
	} 
	/* clear initial state */
	for (j=0;j<(volume+2*BPW);j++)
	    field[i][j]=pencolor;
	field[i]+=BPW;
    } 
    /* set blockshift to log_2 of block */
    blockshift=0;
    i=block;
    while(i>>=1)
	blockshift++; 
    /* draw everything */
    repaint();
    return;
}

/* Puts button of specified dimensions on window.  Nothing is drawn. */
Window makebutton(int xoffset, int yoffset, int xsize, int ysize)
{
    Window buttonwindow;
    long event_mask;
    buttonwindow=XCreateSimpleWindow(display,window,xoffset,yoffset,
				     xsize,ysize,0,black,lightcolor);
    /* look for mouse-button presses */
    event_mask=ButtonPressMask|ExposureMask;
    XSelectInput(display,buttonwindow,event_mask);
    XMapWindow(display,buttonwindow);
    return buttonwindow;
}

/* Draw a button in buttonwindow of specified dimensions with text
   centered.  Color of button determined by sign of "state." 
   size of border determined by magnitude. */
void drawbutton(Window buttonwindow, int xoffset, int yoffset, int xsize,
		int ysize, char *text, int state)
{
    int textlength,i,j;
    int cdark,clight,cup,cdown;
    int cleft,cright,cbutton,ctext;

    cup=lightcolor;
    cdown=darkcolor;
    cdark=black;
    clight=white;
    if (state<0) {
	cbutton=cdown;
	ctext=clight;
	cleft=cdark;
	cright=clight;
    } 
    else {
	cbutton=cup;
	ctext=cdark;
	cleft=clight;
	cright=cdark;
    }
    j=abs(state);
    XSetForeground(display,gcpen,cbutton);  
    XFillRectangle(display,buttonwindow,gcpen,xoffset+j,yoffset+j,
		   xsize-2*j,ysize-2*j);
    XSetForeground(display,gcpen,cleft);
    XFillRectangle(display,buttonwindow,gcpen,xoffset,yoffset,xsize,j);
    XFillRectangle(display,buttonwindow,gcpen,xoffset,yoffset,j,ysize);
    XSetForeground(display,gcpen,cright);
    for (i=0;i<j;i++) {
	XDrawLine(display,buttonwindow,gcpen,
		  xoffset+i,yoffset+ysize-i-1,
		  xoffset+xsize-i-1,yoffset+ysize-i-1);
	XDrawLine(display,buttonwindow,gcpen,
		  xoffset+xsize-i-1,yoffset+i,
		  xoffset+xsize-i-1,yoffset+ysize-i-1);
    }
    if (NULL!=text) {
	textlength=strlen(text);
	XSetForeground(display,gcpen,ctext);
	XDrawString(display,buttonwindow,gcpen,
		    xoffset+(xsize-textlength*font_width)/2,
		    yoffset+(ysize+font_height)/2-2,
		    text,textlength);
    }
    return;
}

void cleanup()
{
    XUnloadFont(display,font->fid);
    XFreeGC(display,gc); 
    XFreeGC(display,gcpen); 
    XCloseDisplay(display);
    XDestroyImage(spinimage);
    if (NULL!=field[0]) free((char *) field[0]-BPW);
    if (NULL!=field[1]) free((char *) field[1]-BPW);
    if (recfile) fclose(recfile);
    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="xevolve.gif";

/* add in a GIF image to field  */
void addpic(unsigned char *data,	/* where the output data starts */
	    int xsize, int ysize)	/* output picture dimensions */
{
    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();
    return;
}

/* save the field as a GIF image */
void savepic(unsigned char *data,       /* where the input data starts   */
     int xsize, int 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>>8,outfile);
	fputc(colorcell.green>>8,outfile);
	fputc(colorcell.blue>>8,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)
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)

void compress(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=(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=(char **) NULL;
    return;
}

void decompress(int initcodesize,
		unsigned char *ptr, unsigned char *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=(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,(char *) (ptr1+oldplace));
		    nextcode++;  /* add new code to table */
		}
		oldplace=currentplace;
		currentplace+=lengths[indx];
		oldindx=indx;
	    }
	    /* not in table yet; must be old code plus last=first character */
	    else {
		for (i=0;i<lengths[oldindx];i++)
		    ptr1[currentplace+i]=addresses[oldindx][i];
		ptr1[currentplace+lengths[oldindx]]=addresses[oldindx][0];
		/* store new code */
		findcode(lengths[oldindx]+1,(char *)(ptr1+currentplace)); 
		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=(char **) NULL;
    return;
}

void inittable(int size)
{
    int i,findcode();
    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,(char *) (stringbuffer+i));
	nextcode++;
    }
    return;
}

/* return code for string of given length;  
   if not found, store it and return nextcode */
int findcode(int length, char *string)
{
    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;
}