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

  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);
    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);
      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", 
        display_form(sticks, user_name);
  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);
    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);
    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.