"Programming Web Games in C "
by  Andrew Davidson
Web Techniques,  March 1997

Web Techniques grants permission to use these listings for private or 
commercial use provided that credit to Web Techniques and the author is 
maintained within the comments of the source. For questions, contact
editors@web-techniques.com.


[LISTING ONE]

% Listing 1: ngame.c

/* ngame.c */
/* Andrew Davison, June 1996 (ad@cs.mu.oz.au) */

/* Usage:
     ngame

   Nim consists of piles of sticks (or stones, etc) in rows. The
   user removes some sticks from a given row, then the computer
   does the same from a row it chooses, and so on.
   The winner is the player who removes the last stick.

   The computer employs a clever strategy based on summing the
   binary values of the stick numbers in each pile. However, it
   may lose if the player is equally clever.

   My source for this strategy was:
 "The Art of Prolog", by Sterling & Shapiro, 
 The MIT Press, 2nd ed., 1994, section 21.2.
*/

#include <stdio.h>
#include <string.h>

#define ROWS 5          /* number of rows */
#define ROW_STRT 1      /* number of sticks in first row */
#define ROW_CHG 2       /* number of extra sticks per new row */
#define COLS 4          /* max sticks in a row must be <= (2^COLS)-1 */
#define MAXLEN 120      /* max length of a string */

struct movement {
  int row;
  int remove_num;
};
typedef struct movement Move;

enum player_type {USER, COMPUTER};
typedef enum player_type Player;


void init_game(int sticks[], char *nm);
void display_game(int sticks[]);
void make_move(Player p, char *nm, Move m, int sticks[]);
void swap_player(Player *p);
int game_over(int sticks[]);
void give_result(Player p, char *nm);
void choose_move(int sticks[], Player p, Move *m);
void user_move(int sticks[], Move *m);
int legal_move(int sticks[], Move mv);

/* The computer's move */
void comp_move(int sticks[], Move *m);
void init_bsticks(int sticks[], int b_sticks[][COLS]);
void binary_val(int no, int b_sticks[]);
int safe(int b_sticks[][COLS]);
void any_move(int sticks[], Move *m);
void init_pbrow(int pbrow[], int sno);
int safe_now(int b_sticks[][COLS], int pbrow[], int rmove);


int main()
{
  int sticks[ROWS];    /* game data structure */
  Move mv;
  Player p = USER;
  char user_name[MAXLEN];

  init_game(sticks, user_name);
  printf("\nHello %s\n", user_name);
  display_game(sticks);
  do {
    choose_move(sticks, p,  &mv);
    make_move(p, user_name, mv, sticks);
    display_game(sticks);
    swap_player(&p);
  } while (!game_over(sticks));

  give_result(p, user_name);

  return 0;
}


void init_game(int sticks[], char *nm)
/* There are ROW_STRT sticks in the first row, with ROW_CHG
   extra sticks in each subsequent row */
{
  int r;
  int num = ROW_STRT;

  printf("Please enter your name: ");
  gets(nm);

  for (r = 0; r < ROWS; r++) {
    sticks[r] = num;
    num = num + ROW_CHG;
  }
}


void display_game(int sticks[])
{
  int r;
  
  printf("\nThe stick configuration is now:\n");
  for (r = 0; r < ROWS; r++)
    printf("Row %d: %d sticks\n", r, sticks[r]);
  putchar('\n');
}


void make_move(Player p, char *nm, Move m, int sticks[])
/* Remove sticks from the specified row */
{
  if (p == USER)
    printf("%s ", nm);
  else
    printf("The COMPUTER ");
  printf("removes %d stick(s) from row %d\n", m.remove_num, m.row);
  sticks[m.row] = sticks[m.row] - m.remove_num;
}


void swap_player(Player *p)
{
  if (*p == USER)
    *p = COMPUTER;
  else
    *p = USER;
}


int game_over(int sticks[])
/* A game is over when there are no sticks left */
{
  int r;

  for (r = 0; r < ROWS; r++)
    if (sticks[r] != 0)
      return 0;
  return 1;
}


void give_result(Player p, char *nm)
/* p has lost; the other player has won */
{
  if (p == USER)
    printf("I win -- bad luck %s.\n", nm);
  else
    printf("%s, you win -- I'm not feeling well.\n", nm);
}



void choose_move(int sticks[], Player p, Move *m)
{
  if (p == USER)
    user_move(sticks, m);
  else
    comp_move(sticks, m);
}


void user_move(int sticks[], Move *m)
{
  Move nmv;

  printf("Enter a row (0 to %d), and sticks to remove: ", ROWS-1);
  scanf("%d %d", &nmv.row, &nmv.remove_num);
  while (!legal_move(sticks, nmv)) {
    printf("Enter a row (0 to %d), and sticks to remove: ", ROWS-1);
    scanf("%d %d", &nmv.row, &nmv.remove_num);
  }
  (*m) = nmv;
}


int legal_move(int sticks[], Move mv)
{
  if (mv.row < 0) {
    printf("Error: row must be >= 0\n");
    return 0;
  }
  if (mv.row > (ROWS-1)) {
    printf("Error: row must be < %d\n", ROWS);
    return 0;
  }
  if (sticks[mv.row] < mv.remove_num) {
    printf("Error: row %d only contains %d sticks\n",
                              mv.row, sticks[mv.row]);
    return 0;
  }
  return 1;
}



/* The following code is for the computer's move. */


void comp_move(int sticks[], Move *m)
/* The safety of sticks[] is determined first by using b_sticks[].
   If it is safe then the computer selects any move. If sticks[] is
   unsafe then a search is made for a row r, number of sticks to
   remove remv, which makes it safe.

   The search is done by 'brute force'. Each row is examined. In
   a given row, an increasing number of sticks are considered for
   removal. If this makes the resulting sticks[] array safe then
   the search can finish. Otherwise the next row is tried.

   The algorithm is guaranteed to find a move to safety from an
   unsafe sticks arrangement.
*/
{
  int b_sticks[ROWS][COLS];
  int poss_brow[COLS];
  int r, remv;

  init_bsticks(sticks, b_sticks);
  if (safe(b_sticks))
    any_move(sticks, m);
  else {    /* unsafe position */
    for (r = 0; r < ROWS; r++)
      if (sticks[r] > 0)
        for (remv = 1; remv <= sticks[r]; remv++) {
          init_pbrow(poss_brow, sticks[r] - remv);
          if (safe_now(b_sticks, poss_brow, r)) {
            (*m).row = r;
            (*m).remove_num = remv;
            return;
          }
        }
    printf("Error: cannot find a safe move\n");   /* should not happen */
  }
}


void init_bsticks(int sticks[], int b_sticks[][COLS])
/* Initialise each b_sticks[] row with the binary value of the
   corresponding sticks[] row. 
*/
{
  int r;
  for (r = 0; r < ROWS; r++)
    binary_val(sticks[r], b_sticks[r]);
}


void binary_val(int no, int b_sticks[])
/* Binary number stored with increasing radix to the right.
   Fill the rest of the row with 0's */
{
  int c = 0;
 
  while (no != 0) {
    b_sticks[c] = no % 2;    /* remainder */
    no = no / 2;             /* integer division */
    c++;
  }
  for( ; c < COLS; c++)
    b_sticks[c] = 0;
}


int safe(int b_sticks[][COLS])
/* sticks[] is safe if the sum of the binary digits in b_sticks[]
   down every column is 0 (modulo 2)
*/
{
  int r, c, tot;

  for (c = 0; c < COLS; c++) {
    tot = 0;
    for (r = 0; r < ROWS; r++)
      tot = tot + b_sticks[r][c];
    if ((tot % 2) != 0)
      return 0; 
  }
  return 1;
}



void any_move(int sticks[], Move *m)
/* A reasonable 'any' move is to choose the first stick found */
{
  int r;
  for (r = 0; r < ROWS; r++)
    if (sticks[r] > 0) {
      (*m).row = r;
      (*m).remove_num = 1;
      return;
    }
}


void init_pbrow(int pbrow[], int sno)
/* Initialise pbrow[] with the binary value for sno */
{
  binary_val(sno, pbrow);
}


int safe_now(int b_sticks[][COLS], int pbrow[], int rpos)
/* The safety calculation is the same as in safe(), except
   that the binary value in pbrow[] is used in row rpos
   rather than the bsticks[] row.
*/
{
  int r, c, tot;

  for (c = 0; c < COLS; c++) {
    tot = 0;
    for (r = 0; r < rpos; r++)
       tot = tot + b_sticks[r][c];
    tot = tot + pbrow[c];
    for (r = (rpos+1); r < ROWS; r++)
       tot = tot + b_sticks[r][c];
    if ((tot % 2) != 0)
      return 0;
  }
  return 1;
}


[LISTING TWO]

% Listing 2: init_nim.c


/* init_nim.c */
/* Andrew Davison, June 1996 (ad@cs.mu.oz.au) */

/* The initialisation form for the Nim game, init.html,
   passes the initial stick configuration and the user's
   name to init_nim. init_nim generates a GIF
   representing the configuration and refers to it in a page
   returned to the user. The page also includes text entry
   fields for accepting the player's game move, and a hidden 
   field holding the stick configuration. The form is set
   to invoke NIM_STEP to process the player's move.
*/
/* Makes use of the gd graphics library, by
   Thomas Boutell and the Quest Protein Database Center
   at Cold Spring Harbor Labs.
   COPYRIGHT 1994,1995 BY THE QUEST PROTEIN DATABASE CENTER
   AT COLD SPRING HARBOR LABS.
*/
/* compilation:
     \gcc -Wall -o init_nim init_nim.c -L/home/staff/ad/gd1.2 -lgd -lm
*/


#include <stdio.h>
#include <string.h>
#include <stdlib.h>     /* for atoi() */
#include <ctype.h>      /* for isdigit() */
#include <math.h>       /* for pow() */
#include <unistd.h>     /* for read(), lseek(), write(), close(), lockf() */
#include <fcntl.h>      /* for open() */
#include "/home/staff/ad/gd1.2/gd.h"
#include "/home/staff/ad/gd1.2/gdfontg.h"


#define ROWS 5          /* number of rows */
#define COLS 4          /* max sticks in a row must be <= (2^COLS)-1 */
#define MAXLEN 120      /* max length of a string */
#define ROWLBL 4        /* max length of a row label in the GIF */
#define DIGLEN 3        /* max length of a digit string */ 

#define XOFFSET 4         /* X distance between sticks */
#define YOFFSET 8         /* Y distance between sticks */
#define TEXT_START 15     /* Start of Row ?: text */

#define DELNO 8           /* offset to delete old gifs */
#define STICK_GIF  "/home/staff/ad/www_public/code/nim/stick.gif"
#define COUNT_NM   "/home/staff/ad/www_public/code/nim/count"
#define NIMTBL     "/home/staff/ad/www_public/code/nim/nimtbl"
#define WWW_NIMTBL "http://www.cs.mu.oz.au/~ad/code/nim/nimtbl"
#define NIM_STEP   "http://www.cs.mu.oz.au/cgi-bin/step_nim"
#define BKGROUND   "http://www.cs.mu.oz.au/~ad/chalk.jpg"

#define MAX_ENTRIES 100         /* max number of input fields */
#define NOVAL "$$no-value$$"    /* when no value is found */

typedef struct {                /* for form nameString=valueString pairs */
    char *name;
    char *val;
} entry;


int init_game(entry entries[], int etnum, int sticks[], char **name);
void get_stcknum(char ln[], int rposn, int max, int *no, int *ok);
void display_game(int sticks[]);
void make_names(char gifnm[], char wgifnm[]);
int get_count(char *nm);
void display_pic(int sticks[], char *wgifnm);
void display_form(int sticks[], char *name);
void single_text(char *nm);

/* GIF creation from view_stcks.c */
void visualise_nim(int sticks[], char *gifnm);
void load_stick(gdImagePtr *stick);
void make_canvas(gdImagePtr *canvas, gdImagePtr stick, int max,
                              int *fst_offset);
void draw_row(gdImagePtr canvas, int fst_offset, int r, int black,
                              int numsticks, gdImagePtr stick);
void save_canvas(gdImagePtr canvas, char *gifnm);

/* Standard Form Functions */
void start_reply(char *title);
void cgi_errs();
int build_entries(entry entries[]);
char *find_value(entry entries[], int etnum, char *name);

/* Debugging Utilities */
int input_entries(entry entries[]);
void show_entries(entry entries[], int etnum);

/* CGI utilities written by Rob McCool */
char *makeword(char *line, char stop);
char *fmakeword(FILE *f, char stop, int *len);
void unescape_url(char *url);
char x2c(char *what);
void plustospace(char *str);


int main()
{
  entry entries[MAX_ENTRIES];   /* HTML nameString=valueString pairs */
  int etnum = 0;
  int sticks[ROWS];
  char *user_name;

  start_reply("Nim Initialisation Outcome");
  cgi_errs();
  etnum = build_entries(entries);
/*
  etnum = input_entries(entries);
  show_entries(entries, etnum);
*/
  if (init_game(entries, etnum, sticks, &user_name)) {
    printf("\n<P>Hello, <strong>%s</strong></P>\n", user_name);
    display_game(sticks);
    display_form(sticks, user_name);
  }
  else
    printf("<P>Some errors have occured, please start again</P>\n");
  printf("</body></html>\n");
  return 0;
}


int init_game(entry entries[], int etnum, int sticks[], char **user_name)
/* Read the init.html form values. There should be 
   one name/value pair for each row, named rK, where K
   goes from 0 upto ROWS-1. The value associated with rK
   is the number of sticks in that row. There should also be
   a name/value pair called name which holds the user name.
*/
{
  char row_label[ROWLBL];
  char *rowval;
  int maxsticks, r, ok = 1;

  maxsticks = pow(2, COLS) - 1;

  for (r = 0; r < ROWS; r++) {
    sprintf(row_label, "r%d", r);
    rowval = find_value(entries, etnum, row_label);
    get_stcknum(rowval, r, maxsticks, &sticks[r], &ok);
  }
  *user_name = find_value(entries, etnum, "name");
  return ok;
}


void get_stcknum(char ln[], int rposn, int max, int *no, int *ok)
/* The number of sticks for row number rowposn is extracted
   from the string stored in ln[]. The number is returned
   if no error has occurred. An error is signalled by ok
   being set to 0.
*/
{
  char num[DIGLEN];
  int neg = 0, i = 0, j = 0;

  if (ln[0] == '-') {
    neg = 1;
    i = 1;    /* skip the first character */
  } 
  while ((isdigit(ln[i])) && (j < DIGLEN))
    num[j++] = ln[i++];
  num[j] = '\0';

  if ((i == 0) || (neg && (i == 1))) {
    printf("<P>Error: Row %d does not contain an integer</P>\n", rposn);
    *ok = 0;  
  }
  else if (j == DIGLEN) {
    printf("<P>Error: Row %d number is too large (maximum is %d)</P>\n", 
                                                        rposn, max);
    *ok = 0;
  }
  else {
    *no = atoi(num);
    if (neg)
      *no = -1 * *no;
    if (*no > max) {
      printf("<P>Error: Row %d number is too big (maximum is %d)</P>\n", 
                                                        rposn, max);
      *ok = 0;
    }
    else if (*no < 0) {
      printf("<P>Error: Row %d number is negative</P>\n", rposn);
      *ok = 0;
    }
  }
}


void display_game(int sticks[])
/* Generate a GIF for the current stick configuration, and 
   store it in gifnm. The URL of this gif file, web_gifnm, 
   is used to access the picture on a Web page.
*/
{
  char gifnm[MAXLEN], web_gifnm[MAXLEN];

  make_names(gifnm, web_gifnm);
  visualise_nim(sticks, gifnm);
  display_pic(sticks, web_gifnm);
}


void make_names(char gifnm[], char wgifnm[])
/* A GIF filename is a concatenation of NIMTBL with a count 
   and .gif. The URL of the file is a concatenation of WWW_NIMTBL, 
   the same count, and .gif. The count is held in COUNT_NM.
   make_names() also deletes old GIF files.
*/
{
  char oldgif[MAXLEN];
  int count;

  count = get_count(COUNT_NM);
  sprintf(gifnm, "%s%d.gif", NIMTBL, count);
  sprintf(wgifnm, "%s%d.gif", WWW_NIMTBL, count);

  /* Remove old Nim picture */
  sprintf(oldgif, "%s%d.gif", NIMTBL, count-DELNO);
  remove(oldgif);
}


int get_count(char *nm)
/* The count is extracted from COUNT_NM, and the value in 
   the file is incremented. The use of lockf() means that 
   lower-level UNIX file manipulation (e.g. open(), read()) 
   must be utilised.
   Some versions of UNIX use flock() rather than lockf().
   The correct calls for flock() are commented out. If flock()
   is used the <sys/file.h> must usually be included.
*/
{
  char ln[MAXLEN];
  int fd, cnt, size;

  if ((fd = open(nm, O_RDWR)) == -1) {   /* both read and write */
    printf("<P><b>Error</b>: Cannot open %s for changing</P>\n", nm);
    printf("</body></html>");
    exit(1);
  }

  lockf(fd, F_LOCK, 0L);      /* (wait for) exclusive lock */
                              /* or flock(fd, LOCK_EX); */
  size = read(fd, ln, MAXLEN);
  ln[size] = '\0';
  sscanf(ln, "%d\n", &cnt);
  lseek(fd, 0L, 0);           /* rewind to start of file */
  sprintf(ln, "%d\n", cnt+1);
  size = strlen(ln);
  write(fd, ln, size);
  lockf(fd, F_ULOCK, 0L);     /* unlock */
                              /* or flock(fd, LOCK_UN);  */
  close(fd);
 
  return cnt; 
}
   


void display_pic(int sticks[], char *wgifnm)
/* Display the image by accessing its URL via wgifnm.
   Debugging code is also included for listing the
   values in the sticks array.
*/
{
/* int r;

  printf("\n<P>The stick configuration is now:<br>\n");
  for (r = 0; r < ROWS; r++)
    printf("Row %d: %d sticks<br>\n", r, sticks[r]);
  printf("</P>\n");
*/
  printf("\n<P>The stick configuration is now:</P>\n");
  printf("<P><img src=%s></P>\n", wgifnm);
}


void display_form(int sticks[], char *user_name)
/* The input form for the user's turn is output. It contains
   two text entry fields (for the row to be modified, and
   the number of sticks to be removed). There is also a
   hidden field, called nimstate, which holds the sticks
   array values and user name. nimstate has the form:
 row0-row1-...rowN-user_name
   The action field of the form refers to NIM_STEP, the CGI
   script for processing a player's move.
*/
{
  int r;

  printf("<P>Now its time for you to remove some sticks.</P>\n\n");

  printf("<FORM METHOD=\"POST\"\n");
  printf("ACTION=\"%s\">\n", NIM_STEP);
  printf("\n<P>Enter a row (0 to %d): \n", ROWS-1);
  single_text("row");
  printf("\n<P>Enter sticks to remove: \n");
  single_text("remno");
  printf("<P><INPUT TYPE=\"submit\" VALUE=\"Make Move\">\n");
  printf("<INPUT TYPE=\"reset\"  VALUE=\"Reset\"></P>\n");

  printf("<INPUT TYPE=\"hidden\" NAME=\"nimstate\" VALUE=\"%d", sticks[0]);
  for (r = 1; r < ROWS; r++)
    printf("-%d", sticks[r]);
  printf("-%s\">\n", user_name);

  printf("</FORM>\n");
}


void single_text(char *nm)
/* Output the form syntax for a text entry field
   labelled with nm.
*/
{
  printf("<INPUT TYPE=\"text\" NAME=\"%s\"", nm);
  printf(" SIZE=\"5\" MAXLENGTH=\"5\" VALUE=\"\"></P>\n");
}



/* GIF Creation from view_stks.c */
/* printf()s have been changed to output HTML, and some have
   been commented out. */

void visualise_nim(int sticks[], char *gifnm)
/* A white canvas is created, consisting of rows of
   sticks. The width of the canvas is based on max, the
   maximum number of sticks in the sticks array.
   The final image is stored in gifnm.
*/
{
  int black;
  int r, max = 0, fst_offset;
  gdImagePtr canvas, stick;

  for (r = 0; r < ROWS; r++)
    if (max < sticks[r])
      max = sticks[r];

  load_stick(&stick);
  make_canvas(&canvas, stick, max, &fst_offset);
  black = gdImageColorAllocate(canvas, 0, 0, 0);
  for (r = 0; r < ROWS; r++)
    draw_row(canvas, fst_offset, r, black, sticks[r], stick);

  gdImageDestroy(stick);
  save_canvas(canvas, gifnm);
}



void load_stick(gdImagePtr *stick)
/* Load the image representing a stick, which is
   assumed to be in the STICK_GIF file.
*/
{
  FILE *fp;

  if ((fp = fopen(STICK_GIF, "rb")) == NULL) {
    printf("<P>Cannot read gif image from %s</P>\n", STICK_GIF);
    printf("</body></html>");
    exit(1);
  }
  /* printf("<P>Reading gif image from %s</P>\n", STICK_GIF); */
  *stick = gdImageCreateFromGif(fp);
  fclose(fp);
}


void make_canvas(gdImagePtr *canvas, gdImagePtr stick, int max,
                              int *fst_offset)
/* Create a blank, white canvas, which is wide enough to
   hold the words Row <ROWS-1>: and max sticks. Its depth
   must be enough to contain ROWS rows.

   The offsets between sticks in the X and Y directions are
   obtained from XOFFSET and YOFFSET. TEXT_START contains 
   the offset from the left edge to the text. fst_offset 
   holds the offset from the left edge to the first stick.
*/
{
  char row_title[MAXLEN];
  int xlen, ylen, white;

  sprintf(row_title, "Row %d: ", ROWS-1);
  *fst_offset = TEXT_START +
                (strlen(row_title) * gdFontGiant->w) + XOFFSET;

  xlen = *fst_offset + ((stick->sx + XOFFSET) * max);
  ylen = YOFFSET + ((stick->sy + YOFFSET) * ROWS);

  *canvas = gdImageCreate(xlen, ylen);
  /* first colour created becomes the background */
  white = gdImageColorAllocate(*canvas, 255, 255, 255);
}


void draw_row(gdImagePtr canvas, int fst_offset, int r, int black,
                              int numsticks, gdImagePtr stick)
/* Draw a row of sticks onto the canvas. The row number is r, 
   the number of sticks is numsticks. The text before the
   sticks is drawn in a black Giant font.
*/
{
  char row_title[MAXLEN];
  int i, xposn, yposn;

  yposn = YOFFSET + ((stick->sy + YOFFSET) * r);
  sprintf(row_title, "Row %d: ", r);
  gdImageString(canvas, gdFontGiant, TEXT_START, yposn, row_title, black);

  xposn = fst_offset;          /* start of sticks on canvas */
  for (i = 0; i < numsticks; i++) {
    gdImageCopy(canvas, stick, xposn, yposn, 0, 0, stick->sx, stick->sy);
    xposn = xposn + (stick->sx + XOFFSET);
    /* debugging printf() */
    /* printf("<P>r=%d; xposn=%d yposn=%d</P>\n", r, xposn, yposn); */
  }
}


void save_canvas(gdImagePtr canvas, char *gifnm)
/* Save the canvas image in the GIF file gifnm */
{
  FILE *fp;

  if ((fp = fopen(gifnm, "wb")) == NULL) {
    printf("<P>Cannot write gif image to %s</P>\n", gifnm);
    gdImageDestroy(canvas);
    exit(1);
  }
  /* printf("<P>Writing gif image to %s</P>\n", gifnm); */
  gdImageGif(canvas, fp);
  fclose(fp);
  gdImageDestroy(canvas);
}



/* Standard Form Functions */

void start_reply(char *title)
/* Output the HTML header, including the title and H1 container */
{
  printf("Content-type: text/html\n\n");
  printf("<html><head><title>%s</title></head>\n", title);
  printf("<body background=\"%s\">", BKGROUND);
  printf("<H1 align=center>%s</H1>\n", title);
  fflush(NULL);   /* force output to occur now */
}


void cgi_errs()
/* Check for errors in the REQUEST_METHOD and CONTENT_TYPE
   environment variables.
*/
{
  if(strcmp(getenv("REQUEST_METHOD"),"POST")) {
    printf("<P>This script should be referenced with a METHOD of POST.\n");
    printf("If you don't understand this, read ");
    printf("<A HREF=\"http://www.ncsa.uiuc.edu/SDG/Software/Mosaic/Docs/fill-out-forms/overview.html\">forms overview</A>.</P>\n");
    printf("</body></html>");
    exit(1);
  }
  if(strcmp(getenv("CONTENT_TYPE"), "application/x-www-form-urlencoded")) {
    printf("<P>This script can only be used to decode form results.</P>\n");
    printf("</body></html>");
    exit(1);
  }
}


int build_entries(entry entries[])
/* Fill in the entries array with nameString=valueString 
   pairs from the form. 
*/
{
  int len, x;

  len = atoi(getenv("CONTENT_LENGTH"));
  for(x=0; len && (!feof(stdin)) && (x < MAX_ENTRIES); x++) {
    entries[x].val = fmakeword(stdin,'&',&len);
    plustospace(entries[x].val);
    unescape_url(entries[x].val);
    entries[x].name = makeword(entries[x].val,'=');
  }
  return x;  
}


char *find_value(entry entries[], int etnum, char *name)
/* Search through the entries array for a name string 
   which matches name and return its associated value 
   string. Otherwise return NOVAL.
*/
{
  int x;
  char *value;

  for(x=0; x < etnum; x++)
    if (strcmp(entries[x].name, name) == 0) {
      value = (char *)malloc(sizeof(char)*(strlen(entries[x].val)+1));
      strcpy(value, entries[x].val);
      break;
    }
  if ((x == etnum) || (value[0] == '\0')) {
    value = (char *)malloc(sizeof(char)*(strlen(NOVAL)+1));
    strcpy(value, NOVAL);
  }
  return value;
}



/* Debugging Utilities */

int input_entries(entry entries[])
/* Fill in the entries array with nameString=valueString pairs 
   entered by the user at the keyboard.
   Each pair should be entered in the format:
      nameString=valueString
   Terminate the input with <ctrl>d
*/
{
  int num = 0, namelen, linelen;
  char line[MAXLEN];

  while (gets(line) && (num < MAX_ENTRIES)) {
    linelen = strlen(line);
    namelen = strcspn(line, "=");
    entries[num].name =
      (char *)malloc(sizeof(char)*(namelen+1));
    strncpy(entries[num].name, line, namelen);
    entries[num].name[namelen] = '\0';
    entries[num].val =
      (char *)malloc(sizeof(char)*(linelen-namelen));
    strcpy(entries[num].val, &line[namelen+1]);
    num++;
  }
  return num;
}


void show_entries(entry entries[], int etnum)
/* Output the nameString=valueString pairs as an HTML 
   unnumbered list */
{
  int x;

  printf("<P>You submitted these nameString=valueString pairs:</P>\n");
  printf("<ul>\n");
  for(x=0; x < etnum; x++)
    printf("<li><code>%s = %s</code>\n", entries[x].name, entries[x].val);
  printf("</ul>\n");
  printf("</body></html>\n");
}



/* CGI Utilities by Rob McCool; 
   comments by Andrew Davison */

char *makeword(char *line, char stop) 
/* Builds a word by extracting characters from line up to the
   stopping character in stop (or until line is exhausted).
*/
{
  int x = 0, y = 0;
  char *word = (char *) malloc(sizeof(char) * (strlen(line) + 1));

  for(x=0; ((line[x]) && (line[x] != stop)); x++)
     word[x] = line[x];
  word[x] = '\0';
  if(line[x]) 
    ++x;
  while((line[y++] = line[x++]));
  return word;
}


char *fmakeword(FILE *f, char stop, int *len) 
/* Similar to makeword(): builds a word by extracting characters 
   from the file f up to the stopping character in stop (or
   until f is exhausted). The function is also supplied with
   the length of the string (len) left unread in f.
*/
{
  int wsize = 102400, ll = 0;
  char *word = (char *) malloc(sizeof(char) * (wsize + 1));

  while(1) {
    word[ll] = (char)fgetc(f);
    if(ll == wsize) {
       word[ll+1] = '\0';
       wsize += 102400;
       word = (char *)realloc(word,sizeof(char)*(wsize+1));
    }
    --(*len);
    if((word[ll] == stop) || (feof(f)) || (!(*len))) {
       if(word[ll] != stop) ll++;
       word[ll] = '\0';
       return word;
    }
    ++ll;
  }
}


void unescape_url(char *url) 
/* Convert the hexadecimal characters in url into ASCII.
   They are detected by starting with a '%'.
*/
{
  register int x, y;

  for(x=0,y=0; url[y]; ++x,++y) {
    if((url[x] = url[y]) == '%') {
      url[x] = x2c(&url[y+1]);
      y+=2;
    }
  }
  url[x] = '\0';
}


char x2c(char *what) 
/* Convert the hexadecimal (consisting of two characters) into
   a single ASCII character.
*/
{
  register char digit;

  digit = (what[0] >= 'A' ? ((what[0] & 0xdf) - 'A')+10 : (what[0] - '0'));
  digit *= 16;
  digit += (what[1] >= 'A' ? ((what[1] & 0xdf) - 'A')+10 : (what[1] - '0'));
  return(digit);
}


void plustospace(char *str) 
/* Replace '+'s by spaces in str */
{
  register int x;

  for(x=0; str[x]; x++) 
    if(str[x] == '+') str[x] = ' ';
}



[LISTING THREE]

% Listing 3: step_nim.c (partial)


/* step_nim.c */
/* Andrew Davison, June 1996 (ad@cs.mu.oz.au) */

/* The user activates step_nim via a form created by init_nim
   (the Nim initialisation CGI script) or by a previous call to
   step_nim. The form contains the user's move (the row number
   and the number of sticks to remove), and a hidden 'nimstate'
   field which contains the stick configuration and the user's
   name.
   If the user's move is illegal then a new copy of the form
   is returned to the user.
   If the move is legal amd a winning turn then the game finishes.
   If the move is legal but not a winning turn then the server
   takes its turn. If that is a winning turn then the game
   finishes, otherwise a new form is returned to the player
   for the next move.
*/
/* Makes use of the gd graphics library, by
   Thomas Boutell and the Quest Protein Database Center
   at Cold Spring Harbor Labs.
   COPYRIGHT 1994,1995 BY THE QUEST PROTEIN DATABASE CENTER
   AT COLD SPRING HARBOR LABS.
*/
/* compilation:
     \gcc -Wall -o step_nim step_nim.c -L/home/staff/ad/gd1.2 -lgd -lm
*/


#include <stdio.h>
#include <string.h>
#include <stdlib.h>     /* for atoi() */
#include <ctype.h>      /* for isdigit() */
#include <unistd.h>     /* for read(), lseek(), write(), close(), lockf() */
#include <fcntl.h>      /* for open() */
#include "/home/staff/ad/gd1.2/gd.h"
#include "/home/staff/ad/gd1.2/gdfontg.h"

#define ROWS 5          /* number of rows */
#define COLS 4          /* max sticks in a row must be <= (2^COLS)-1 */
#define MAXLEN 120      /* max length of a string */
#define DIGLEN 3        /* max length of a digit string */

#define XOFFSET 4          /* X distance between sticks */
#define YOFFSET 8          /* Y distance between sticks */
#define TEXT_START 15      /* Start of Row ?: text */

#define DELNO 8           /* offset to delete old gifs */
#define STICK_GIF  "/home/staff/ad/www_public/code/nim/stick.gif"
#define COUNT_NM   "/home/staff/ad/www_public/code/nim/count"
#define NIMTBL     "/home/staff/ad/www_public/code/nim/nimtbl"
#define WWW_NIMTBL "http://www.cs.mu.oz.au/~ad/code/nim/nimtbl"
#define NIM_INIT   "http://www.cs.mu.oz.au/~ad/code/nim/init.html"
#define NIM_STEP   "http://www.cs.mu.oz.au/cgi-bin/step_nim"
#define BKGROUND   "http://www.cs.mu.oz.au/~ad/chalk.jpg"

#define MAX_ENTRIES 100         /* max number of input fields */
#define NOVAL "$$no-value$$"    /* when no value is found */

typedef struct {                /* for form nameString=valueString pairs */
    char *name;
    char *val;
} entry;


struct movement {
  int row;
  int remove_num;
};
typedef struct movement Move;

enum player_type {USER, COMPUTER};
typedef enum player_type Player;


void read_state(entry entries[], int etnum, int sticks[], 
                                      char name[], Move *mv);
void get_sticks(char ln[], int sticks[], char name[]);
int get_digit(char ln[], int *i);
int legal_move(int sticks[], Move mv);
void make_move(Player p, char *nm, Move m, int sticks[]);
void give_result(Player p, char *nm, int sticks[]);

/* Code from init_nim.c */
void display_game(int sticks[]);
void make_names(char gifnm[], char wgifnm[]);
int get_count(char *nm);
void display_pic(int sticks[], char *wgifnm);
void display_form(int sticks[], char *name);
void single_text(char *nm);

/* GIF creation from view_stcks.c */
void visualise_nim(int sticks[], char *gifnm);
void load_stick(gdImagePtr *stick);
void make_canvas(gdImagePtr *canvas, gdImagePtr stick, int max,
                              int *fst_offset);
void draw_row(gdImagePtr canvas, int fst_offset, int r, int black,
                              int numsticks, gdImagePtr stick);
void save_canvas(gdImagePtr canvas, char *gifnm);

/* Code from ngame.c */
int game_over(int sticks[]);
void comp_move(int sticks[], Move *m);
void init_bsticks(int sticks[], int b_sticks[][COLS]);
void binary_val(int no, int b_sticks[]);
int safe(int b_sticks[][COLS]);
void any_move(int sticks[], Move *m);
void init_pbrow(int pbrow[], int sno);
int safe_now(int b_sticks[][COLS], int pbrow[], int rpos);

/* Standard Form Functions */
void start_reply(char *title);
void cgi_errs();
int build_entries(entry entries[]);
char *find_value(entry entries[], int etnum, char *name);

/* Debugging Utilities */
int input_entries(entry entries[]);
void show_entries(entry entries[], int etnum);

/* CGI utilities written by Rob McCool */
char *makeword(char *line, char stop);
char *fmakeword(FILE *f, char stop, int *len);
void unescape_url(char *url);
char x2c(char *what);
void plustospace(char *str);


int main()
{
  entry entries[MAX_ENTRIES];     /* HTML nameString=valueString pairs */
  int etnum = 0;
  int sticks[ROWS];
  Move mv;
  char user_name[MAXLEN];

  start_reply("Nim Move Outcome");
  cgi_errs();
  etnum = build_entries(entries);
/*
  etnum = input_entries(entries);
  show_entries(entries, etnum);
*/
  read_state(entries, etnum, sticks, user_name, &mv);

  printf("\n<P>Hello, <strong>%s</strong></P>\n", user_name);
  display_game(sticks);

  if (!legal_move(sticks, mv)) {
    printf("\n<P><strong>%s</strong>, please try again...</P>\n", user_name);
    display_form(sticks, user_name);
  }
  else {
    make_move(USER, user_name, mv, sticks);
    display_game(sticks);
    if (game_over(sticks))        /* the user has won */
      give_result(COMPUTER, user_name, sticks);
    else {
      comp_move(sticks, &mv);
      make_move(COMPUTER, user_name, mv, sticks);
      display_game(sticks);
      if (game_over(sticks))      /* the computer has won */
        give_result(USER, user_name, sticks);
      else {
        printf("<P><strong>%s</strong>, now it's your turn...</P>\n", 
                                                               user_name);
        display_form(sticks, user_name);
      }
    }
  }
  printf("</body></html>");
  return 0;
}


void read_state(entry entries[], int etnum, int sticks[], 
                                               char name[], Move *mv)
/* Extract the stick configuration and user name from the 'nimstate'
   name/value hidden field. Also obtain the user's move (the row
   and number of sticks to be removed from it).
*/
{
  char *nimstate;

  nimstate = find_value(entries, etnum, "nimstate");
  get_sticks(nimstate, sticks, name);

  (*mv).row = atoi(find_value(entries, etnum, "row"));
  (*mv).remove_num = atoi(find_value(entries, etnum, "remno"));
}


void get_sticks(char ln[], int sticks[], char name[])
/* Read a sequence of ROW digits, in the format:
         digit ['-'digit]* 
  followed by '-'name
*/
{
  int i = 0, r;

  for (r = 0; r < ROWS; r++) {
    sticks[r] = get_digit(ln, &i);
    i++;          /* skip '-' */
  }
  strcpy(name, &ln[i]);
}


int get_digit(char ln[], int *i)
/* Extract a digit from the line; not much error checking */
{
  char num[DIGLEN];
  int j = 0;

  while (isdigit(ln[*i]))
    num[j++] = ln[(*i)++];
  num[j] = '\0';

  return atoi(num);
}


/* Similar to ngame.c functions, but with HTML printf()s */

int legal_move(int sticks[], Move mv)
/* Added a test for 0 and negative remove_num */
{
  if (mv.row < 0) {
    printf("<P>Error: row must be >= 0</P>\n");
    return 0;
  }
  if (mv.row > (ROWS-1)) {
    printf("<P>Error: row must be < %d</P>\n", ROWS);
    return 0;
  }
  if (mv.remove_num <= 0) {
    printf("<P>Error: Must remove more than 0 sticks</P>\n");
    return 0;
  } 
  if (sticks[mv.row] < mv.remove_num) {
    printf("<P>Error: row %d only contains %d sticks</P>\n",
                              mv.row, sticks[mv.row]);
    return 0;
  }
  return 1;
}


void make_move(Player p, char *nm, Move m, int sticks[])
/* Remove sticks from the specified row */
{
  if (p == USER)
    printf("<P><strong>%s</strong> ", nm);
  else
    printf("<P>The COMPUTER ");
  printf("removes %d stick(s) from row %d</P>\n", m.remove_num, m.row);
  sticks[m.row] = sticks[m.row] - m.remove_num;
}


void give_result(Player p, char *nm, int sticks[])
/* p has lost; the other player has won */
{
  if (p == USER)
    printf("<P>I win -- bad luck <strong>%s</strong>.</P>\n", nm);
  else
    printf("<P><strong>%s</strong>, you win -- I'm not feeling well.</P>\n", nm);
  printf("<P><a href=\"%s\">Start another game?</a></P>\n", NIM_INIT);
}


/* The rest of the functions used in step_nim.c are reused
   from ngame.c, init_nim.c and view_stks.c, and so are not
   included. The function prototypes at the top of this
   listing give the names of the functions.
  :
  :
*/



[LISTING FOUR]

% Listing 4: init.html


<html>
<head>
<title>Initialising Nim</title>
</head>

<body background = "chalk.jpg">
<H1 align=center>Initialising Nim</H1>

<P>Nim is a game for two people, but here you will be playing
against a machine!</P>

<P>In this version of Nim there are always 5 rows of sticks, but
you get to choose how many sticks are initially in each row. </P>

<P>The players take turns removing some
of the sticks (up to all) in a row. The winner is the player
who takes the last stick.</P>

<FORM METHOD="POST" ACTION="http://www.cs.mu.oz.au/cgi-bin/init_nim">

<P>Please enter your name:
<INPUT TYPE="text" NAME="name" SIZE="20" MAXLENGTH="20" VALUE=""></P>

<P>Enter the number of sticks in each row (there is a maximum
of 15 sticks allowed per row). Some default values are
supplied:<br>
Row 0: 
<INPUT TYPE="text" NAME="r0" SIZE="5" MAXLENGTH="5" VALUE="1"><br>

Row 1:
<INPUT TYPE="text" NAME="r1" SIZE="5" MAXLENGTH="5" VALUE="3"><br>

Row 2:
<INPUT TYPE="text" NAME="r2" SIZE="5" MAXLENGTH="5" VALUE="5"><br>

Row 3:
<INPUT TYPE="text" NAME="r3" SIZE="5" MAXLENGTH="5" VALUE="7"><br>

Row 4:
<INPUT TYPE="text" NAME="r4" SIZE="5" MAXLENGTH="5" VALUE="9"></P>

<P><INPUT TYPE="submit" VALUE="Start Nim">
<INPUT TYPE="reset" VALUE="Reset"></P>

</FORM>

<hr>
<address>
Last updated: June, 1996<br>
Author: <a href="http://www.cs.mu.oz.au/~ad">Andrew Davison</a><br>
Email: <a href="mailto:ad@cs.mu.oz.au">ad@cs.mu.oz.au</a><br>
</address>

</body>
</html>



[LISTING FIVE]

% Listing 5: view_stks.c



/* view_stks.c */
/* Andrew Davison, June 1996 (ad@cs.mu.oz.au) */

/* Usage:
     view_stks

   view_stks prompts for a Nim sticks configuration, of
   the form:
     row0-row1-...rowN

   rowK is the number of sticks in the Kth row. Rows
   are numbered from 0. The unusual input format is close
   to the input received by the CGI script (step_nim.c)
   for playing Nim.

   The input is used to generate a GIF in the TEST_GIF file,
   which consists of sticks in rows. The GIF for a single
   stick is assumed to be in STICK_GIF.
*/
/* Makes use of the gd graphics library, by
   Thomas Boutell and the Quest Protein Database Center
   at Cold Spring Harbor Labs.
   COPYRIGHT 1994,1995 BY THE QUEST PROTEIN DATABASE CENTER
   AT COLD SPRING HARBOR LABS.
*/
/* compilation: 
      \gcc -Wall view_stks.c -o view_stks -L/home/staff/ad/gd1.2 -lgd -lm
*/

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <ctype.h>
#include "/home/staff/ad/gd1.2/gd.h"
#include "/home/staff/ad/gd1.2/gdfontg.h"   /* text uses a Giant font */

#define ROWS 5            /* number of rows */
#define XOFFSET 8         /* X distance between sticks */
#define YOFFSET 12        /* Y distance between sticks */
#define TEXT_START 15     /* Start of Row ?: text */
#define MAXLEN 120        /* max length of a string */
#define DIGLEN 3          /* max length of a digit string */

#define STICK_GIF "/home/staff/ad/www_public/code/nim/stick.gif"
#define TEST_GIF  "/home/staff/ad/www_public/code/nim/test.gif"


void init_sticks(int sticks[]);
void get_sticks(char ln[], int sticks[]);
int get_digit(char ln[], int *i);
void display_game(int sticks[]);

/* GIF creation */
void visualise_nim(int sticks[], char *gifnm);
void load_stick(gdImagePtr *stick);
void make_canvas(gdImagePtr *canvas, gdImagePtr stick, int max,
                              int *fst_offset);
void draw_row(gdImagePtr canvas, int fst_offset, int r, int black, 
                              int numsticks, gdImagePtr stick);
void save_canvas(gdImagePtr canvas, char *gifnm);


int main()
{
  int sticks[ROWS] = {0};

  init_sticks(sticks);
  display_game(sticks);
  visualise_nim(sticks, TEST_GIF);
 
  return 0;
}


void init_sticks(int sticks[])
{
  char line[MAXLEN];

  printf("\nEnter Nim state (row0-row1-...-row%d): ", ROWS-1);
  gets(line);
  get_sticks(line, sticks);
}



void get_sticks(char ln[], int sticks[])
/* Read a sequence of digits, in the format:
         digit ['-'digit]*
*/
{
  int i = 0, sno = 0;

  sticks[sno++] = get_digit(ln, &i);
  while (ln[i] == '-') {
    i++;
    sticks[sno++] = get_digit(ln, &i);
  }
}


int get_digit(char ln[], int *i)
/* Extract a digit from the line; not much error checking */
{
  char num[DIGLEN];
  int j = 0;

  while (isdigit(ln[*i]))
    num[j++] = ln[(*i)++];
  num[j] = '\0';

  return atoi(num);
}


void display_game(int sticks[])
{
  int r;

  printf("\nThe stick configuration is now:\n");
  for (r = 0; r < ROWS; r++)
    printf("Row %d: %d sticks\n", r, sticks[r]);
  putchar('\n');
}


/* GIF Creation */

void visualise_nim(int sticks[], char *gifnm)
/* A white canvas is created, consisting of rows of
   sticks. The width of the canvas is based on max, the
   maximum number of sticks in the sticks array.
   The final image is stored in gifnm.
*/
{
  int black;
  int r, max = 0, fst_offset;
  gdImagePtr canvas, stick;

  for (r = 0; r < ROWS; r++)
    if (max < sticks[r])
      max = sticks[r];

  load_stick(&stick);
  make_canvas(&canvas, stick, max, &fst_offset);
  black = gdImageColorAllocate(canvas, 0, 0, 0);
  for (r = 0; r < ROWS; r++)
    draw_row(canvas, fst_offset, r, black, sticks[r], stick);

  gdImageDestroy(stick);
  save_canvas(canvas, gifnm);
}



void load_stick(gdImagePtr *stick)
/* Load the image representing a stick, which is
   assumed to be in the STICK_GIF file.
*/
{
  FILE *fp;

  if ((fp = fopen(STICK_GIF, "rb")) == NULL) {
    printf("Cannot read gif image from %s\n", STICK_GIF);
    exit(1);
  }
  printf("Reading gif image from %s\n", STICK_GIF);
  *stick = gdImageCreateFromGif(fp);
  fclose(fp);
}


void make_canvas(gdImagePtr *canvas, gdImagePtr stick, int max,
                              int *fst_offset)
/* Create a blank, white canvas, which is wide enough to
   hold the words Row <ROWS-1>: and max sticks. Its depth
   must be enough to contain ROWS rows.

   The offsets between sticks in the X and Y directions are
   obtained from XOFFSET and YOFFSET. TEXT_START contains 
   the offset from the left edge to the text. fst_offset 
   holds the offset from the left edge to the first stick.
*/
{
  char row_title[MAXLEN];
  int xlen, ylen, white;

  sprintf(row_title, "Row %d: ", ROWS-1);
  *fst_offset = TEXT_START +
                (strlen(row_title) * gdFontGiant->w) + XOFFSET;

  xlen = *fst_offset + ((stick->sx + XOFFSET) * max);
  ylen = YOFFSET + ((stick->sy + YOFFSET) * ROWS);

  *canvas = gdImageCreate(xlen, ylen);
  /* first colour created becomes the background */
  white = gdImageColorAllocate(*canvas, 255, 255, 255);
}


void draw_row(gdImagePtr canvas, int fst_offset, int r, int black,
                              int numsticks, gdImagePtr stick)
/* Draw a row of sticks onto the canvas. The row number is r, 
   the number of sticks is numsticks. The text before the
   sticks is drawn in a black Giant font.
*/
{
  char row_title[MAXLEN];
  int i, xposn, yposn;

  yposn = YOFFSET + ((stick->sy + YOFFSET) * r);
  sprintf(row_title, "Row %d: ", r);
  gdImageString(canvas, gdFontGiant, TEXT_START, yposn, row_title, black);

  xposn = fst_offset;          /* start of sticks on canvas */
  for (i = 0; i < numsticks; i++) {
    gdImageCopy(canvas, stick, xposn, yposn, 0, 0, stick->sx, stick->sy);
    xposn = xposn + (stick->sx + XOFFSET);
    /* debugging printf() */
    printf("r=%d; xposn=%d yposn=%d\n", r, xposn, yposn);
  }
}


void save_canvas(gdImagePtr canvas, char *gifnm)
/* Save the canvas image in the GIF file gifnm */
{
  FILE *fp;

  if ((fp = fopen(gifnm, "wb")) == NULL) {
    printf("Cannot write gif image to %s\n", gifnm);
    gdImageDestroy(canvas);
    exit(1);
  }
  printf("Writing gif image to %s\n", gifnm);
  gdImageGif(canvas, fp);
  fclose(fp);
  gdImageDestroy(canvas);
}