From: aburto@nosc.mil (Alfred A. Aburto)
Newsgroups: comp.benchmarks
Subject: Fhourstones Benchmark C Source Code
Date: 22 Jan 93 20:45:29 GMT
Expires: Mon, 15 Feb 1993 08:00:00 GMT
Distribution: comp.arch, comp.benchmarks
Organization: Naval Ocean Systems Center, San Diego

# This is a shell archive.  Remove anything before this line, then unpack
# it by saving it into a file and typing "sh file".  To overwrite existing
# files, type "sh file -c".  You can also feed this as standard input via
# unshar, or by typing "sh <file", e.g..  If this archive is complete, you
# will see the following message at the end:
#		"End of shell archive."
# Contents:  MANIFEST Makefile README best.c best.h c4.c c4.h input
#   mach.c play.c play.h trans.c
# Wrapped by tromp@wolf.cwi.nl on Wed Jan 20 11:44:49 1993
PATH=/bin:/usr/bin:/usr/ucb ; export PATH
if test -f 'MANIFEST' -a "${1}" != "-c" ; then 
  echo shar: Will not clobber existing file \"'MANIFEST'\"
else
echo shar: Extracting \"'MANIFEST'\" \(570 characters\)
sed "s/^X//" >'MANIFEST' <<'END_OF_FILE'
X-rw-r--r--  1 tromp         929 Jan 20 11:11 Makefile
X-rw-r--r--  1 tromp        2724 Jan 20 11:44 README
X-rw-r--r--  1 tromp        2669 Jan 19 11:32 best.c
X-rw-r--r--  1 tromp        3409 Oct 23 13:54 best.h
X-rw-r--r--  1 tromp        3307 Jan 20 09:37 c4.c
X-rw-r--r--  1 tromp         600 Jan 19 11:32 c4.h
X-rw-r--r--  1 tromp          14 Aug 29 18:32 input
X-rw-------  1 tromp        7335 Dec  4 19:22 mach.c
X-rw-r--r--  1 tromp        2236 Oct 15 12:16 play.c
X-rw-r--r--  1 tromp        1443 Aug 20 12:33 play.h
X-rw-r--r--  1 tromp        4179 Jan 19 11:53 trans.c
END_OF_FILE
if test 570 -ne `wc -c <'MANIFEST'`; then
    echo shar: \"'MANIFEST'\" unpacked with wrong size!
fi
# end of 'MANIFEST'
fi
if test -f 'Makefile' -a "${1}" != "-c" ; then 
  echo shar: Will not clobber existing file \"'Makefile'\"
else
echo shar: Extracting \"'Makefile'\" \(929 characters\)
sed "s/^X//" >'Makefile' <<'END_OF_FILE'
X# current options include SMALL.
XDEFINES = -DUNIX -DSMALL
XFLAGS = -O $(DEFINES)
XFILES = Makefile README \
X        best.c best.h c4.c c4.h input mach.c play.c play.h trans.c
X
XCC = cc $(FLAGS)
X
Xc4		: c4.o trans.o best.o play.o mach.o
X		$(CC) -o c4 c4.o trans.o best.o play.o mach.o
X
Xc4.o		: c4.c c4.h Makefile
X		$(CC) -c c4.c
X
Xtrans.o		: trans.c c4.h Makefile
X		$(CC) -c trans.c
X
Xbest.o		: best.c c4.h best.h Makefile
X		$(CC) -c best.c
X
Xplay.o		: play.c c4.h play.h Makefile
X		$(CC) -c play.c
X
Xmach.o		: mach.c Makefile
X		$(CC) -c mach.c
X
X# use the following for optimization levels that preclude separate compilation
Xtogether	: c4.c c4.h trans.c best.c best.h play.c play.h mach.c Makefile
X		$(CC) -o c4 c4.c trans.c best.c play.c mach.c
X
XMANIFEST	: $(FILES)
X		ls -l $(FILES) > MANIFEST
X
Xshar		: $(FILES) MANIFEST
X		shar -o c4.shar MANIFEST $(FILES)
X
Xtar		: $(FILES) MANIFEST
X		tar -cf c4.tar MANIFEST  $(FILES)
X		compress c4.tar
END_OF_FILE
if test 929 -ne `wc -c <'Makefile'`; then
    echo shar: \"'Makefile'\" unpacked with wrong size!
fi
# end of 'Makefile'
fi
if test -f 'README' -a "${1}" != "-c" ; then 
  echo shar: Will not clobber existing file \"'README'\"
else
echo shar: Extracting \"'README'\" \(2724 characters\)
sed "s/^X//" >'README' <<'END_OF_FILE'
X                    The FHOURSTONES benchmark
X
X
XThis benchmark is distilled from my pet application `c4', a connect-4 solver.
XIt features a streamlined implementation of exhaustive alpha-beta
Xsearch using the history heuristic and a space optimized hashtable.
X
XSome technical bits:
XOf the full 49 bit lock that describes a connect-4 position, only 32 are
Xstored in the hashtable entry while the remaining 17 are subsumed in the
Xhash-address. To also accomodate 8 fold probing, a minimum of a million
Xhash table entries are required. The benchmark uses just over 5Mb, unlikely
Xto fit into any sort of cache in the foreseeable future.
XThis makes the Fhourstones measure relatively immune to huge cache sizes.
X
XThe potentially expensive modulo operations are implemented with repeated
Xtable lookup. The use of small integer sizes is available as an option.
X
XAlthough this benchmark, like nsieve, emphasizes random access performance,
Xit also exercises standard scalar performance; the recursive alpha-beta
Xcalls, incremental threat table computations, history table updates, and
Xmove-reordering represent a fair mix of scalar operations.
X
XThe benchmark input is a relatively difficult 12-ply position.
XThe output should look like:
X
Xoptions:    small ints
XSolving 12-ply position after 444333377755 . . .
Xscore = 7 (+)  work = 21
X3871322 pos / 98.7 sec = 39227 p/s
Xstore rate = 0.914
X- 0.211  < 0.422  = 0.059  > 0.054  + 0.254
X 56765  376940  173046  174816  121323   70603   38079   19252
X  9741    4853    2393    1147     537     291     116      54
X    30      16       3       2       3       1       0       0
X     0       0       0       0       0       0       0       0
X
XThe first line shows which program-specific options are active.
XCurrently, only one is supported: -DSMALL makes the program use
Xchars and shorts in moderately sized arrays of small integers.
XThe benefit of this option is machine-specific; sometimes it's better and
Xsometimes it's worse.
XThe 2nd line says which positions is being solved (input ends with =),
Xor tested for a 1st player win (+) or for a 2nd player win (-). Due to
Xthe transposition table and history heuristic, the reduced searches are not
Xnecessarily faster.
XThe next line indicates the score of the position and a logarithmic measure
Xof difficulty on a scale from 0 to 31.
XThe fourth line shows the machine performance;
Xof all the output, only the last 2 numbers on this line
Xshould differ from the above output.
XThe store rate gives the percentage of positions actually entered
Xin the transposition table versus those offered to it.
XThe rest of the output shows the final distribution of positions in
Xthe transposition table with respect to
Xscore (line 6) and work (lines 7-10).
END_OF_FILE
if test 2724 -ne `wc -c <'README'`; then
    echo shar: \"'README'\" unpacked with wrong size!
fi
# end of 'README'
fi
if test -f 'best.c' -a "${1}" != "-c" ; then 
  echo shar: Will not clobber existing file \"'best.c'\"
else
echo shar: Extracting \"'best.c'\" \(2669 characters\)
sed "s/^X//" >'best.c' <<'END_OF_FILE'
X/* alpha beta search
X   (c) 1992 John Tromp
X*/
X
X#include "c4.h"
X
X#define BONUS		1
X
Xint window;	/* 0 = [-,+]    1 = [=,+]   2 = [-,=] */
Xstatic uint8 alp[] = {WIN2, DRAW, WIN2},
X             bet[] = {WIN1, WIN1, DRAW};
Xstatic uint8 xkiller[64], okiller[64];
X
Xextern B8 r, columns, height;
Xextern uint8 xthrcnt[], othrcnt[], colthr[], *moves;
Xextern int plycnt;
Xextern u_int posed;
Xextern void makemovx(),makemovo(),backmovx(),backmovo();
Xextern int transpose(), transtore();
Xextern void emptyht();
X
Xu_int nodes;
X
Xvoid initbest()
X{
X}
X
Xstatic FILE *BOOKFILE;
X
Xint bookin()
X{
X  static int buf5 = 1;
X  static int nrle;
X  int score;
X
X  if (buf5 == 1) {
X    if (nrle) {
X      buf5 = 242;
X      nrle--;
X    } else if ((buf5 = getc(BOOKFILE)) > 242) {
X      nrle = buf5 - 242;
X      buf5 = 242;
X    }
X    buf5 += 243;
X  }
X  score = 3 + 2 * (buf5 % 3);
X  buf5 /= 3;
X  return score;
X}
X
X#define ME	1
X#define OPP	2
X#define BOOKME	bookx
X#define BOOKOPP booko
X#define ABME	abx
X#define ABOPP	abo
X#define THRME	xthrcnt
X#define THROPP	othrcnt
X#define IWIN	WIN2
X#define ILOSE	WIN1
X#define MAKEMOV	makemovx
X#define BACKMOV	backmovx
X#define WORST	8
X#define KILLER	xkiller
X#define WRSTBND	beta
X#define BESTBND	alpha
X#define IMPRVS	<
X#define NOWORSE	<=
X#define NOLOSE	DRIN2
X#include "best.h"
X
X#define ME	2
X#define OPP	1
X#define BOOKME	booko
X#define BOOKOPP	bookx
X#define ABME	abo
X#define ABOPP	abx
X#define THRME	othrcnt
X#define THROPP	xthrcnt
X#define IWIN	WIN1
X#define ILOSE	WIN2
X#define MAKEMOV	makemovo
X#define BACKMOV	backmovo
X#define WORST	0
X#define KILLER	okiller
X#define WRSTBND	alpha
X#define BESTBND	beta
X#define IMPRVS	>
X#define NOWORSE	>=
X#define NOLOSE	DRIN1
X#include "best.h"
X
Xvoid loadbook()
X{
X  BOOKFILE = fopen("book.8", "r");
X  if (BOOKFILE == NULL) {
X    printf("File book.8 not found.\n");
X    exit(0);
X  }
X  nodes = 0;
X  booko();
X  if (getc(BOOKFILE) != EOF) {
X    printf("File book.8 corrupt.\n");
X    exit(0);
X  }
X  fclose(BOOKFILE);
X}
X
Xint best()
X{
X  int i,(*myab)();
X  uint8 *mythrcnt;
X  int me,x,work,score;
X  u_int poscnt;
X
X  nodes = 0;
X  if (plycnt & 1) {
X    mythrcnt = xthrcnt;
X    myab = abx;
X    me = 1;
X  } else {
X    mythrcnt = othrcnt;
X    myab = abo;
X    me = 2;
X  }
X  for (i = 0; i = r[i]; ) {
X    if (mythrcnt[height[i]] || colthr[columns[i]] == me)
X      return (plycnt&1) ? WIN2 : WIN1;
X  }
X  if (x = transpose(columns)) {
X    score = SCORE(x);
X    if (EXACT(score))
X      return score;
X  }
X  for (i=0; i<64; i++)
X     okiller[i] = xkiller[i] = 0x80;
X  emptyht();
X  score = myab(alp[window], bet[window]);
X  poscnt = posed;
X  for (work=1; poscnt>>=1; work++) ;	/* work = log of #positions stored */
X  return work << 3 | score;		/* normally bestofall */
X}
END_OF_FILE
if test 2669 -ne `wc -c <'best.c'`; then
    echo shar: \"'best.c'\" unpacked with wrong size!
fi
# end of 'best.c'
fi
if test -f 'best.h' -a "${1}" != "-c" ; then 
  echo shar: Will not clobber existing file \"'best.h'\"
else
echo shar: Extracting \"'best.h'\" \(3409 characters\)
sed "s/^X//" >'best.h' <<'END_OF_FILE'
Xint BOOKME()
X{
X  int score,bestscore,i,x,threat;
X
X  nodes++;
X  if (x = transpose(columns))
X    return SCORE(x);
X
X  if (plycnt >= 8) {
X    for (threat=i=0; i=r[i]; ) {
X      if (THRME[height[i]] || colthr[columns[i]]==ME)
X        return IWIN;
X      if (THROPP[height[i]] || colthr[columns[i]]==OPP)
X        threat = threat << 3 | i;
X    }
X    if (threat > 7)
X      return ILOSE;
X    if (!threat) {
X      score = bookin();
X      transtore(columns, score, 31);
X      return score;
X    }
X    MAKEMOV(threat);
X    score = BOOKOPP();
X    BACKMOV();
X    return score;
X  }
X  for (bestscore=WORST,i=0; i=r[i]; ) {
X    if (THRME[height[i]] || colthr[columns[i]]==ME) {
X      bestscore = IWIN;
X      continue;
X    }
X    MAKEMOV(i);
X    if ((score = BOOKOPP()) IMPRVS bestscore)
X      bestscore = score;
X    BACKMOV();
X  }
X  transtore(columns, bestscore, 1);
X  return bestscore;
X}
X
Xint ABME(alpha, beta)
Xint alpha, beta;
X{
X  register int besti,i,j,k,l,val,score;
X  int x,v,work;
X  int rr[8];
X  u_int poscnt;
X
X  nodes++;
X#if ME == 2		/* O to move can be drawn */
X  if (!r[0])
X    return DRAW;
X#endif
X  for (i = j = 0; i = r[i];) {
X    if (THROPP[height[i]] || colthr[columns[i]]) { /* ignore case of colthr */
X      if (THROPP[height[i]-8])
X        return ILOSE;
X      j = rr[0] = i;		/* forget other moves */
X      while (i = r[i])
X        if (THROPP[height[i]] || colthr[columns[i]])
X          return ILOSE;
X      break;
X    }
X    if (!THROPP[height[i]-8])
X      j = rr[j] = i;
X  }
X  if (!j)
X    return ILOSE;
X  if (j == rr[0]) {
X    MAKEMOV(j);
X    score = ABOPP(alpha, beta);
X    BACKMOV();
X    return score;
X  }
X  if (x = transpose(columns)) {
X    score = SCORE(x);
X    if (score == DRIN2) {
X      if ((beta = DRAW) <= alpha)
X        return score;
X    } else if (score == DRIN1) {
X      if ((alpha = DRAW) >= beta)
X        return score;
X    } else return score;
X  }
X  poscnt = posed;
X  score = WORST;	/* try to get the best bound if score > beta */
X  for (i = rr[j] = 0; rr[i]; ) {
X    for (j = i, val = 0; k = rr[j]; j = k) {
X      v = KILLER[height[k]];           /* truly dynamic move ordering! */
X      if (k == LASTMOVE)		/* make same column attractive */
X        v += BONUS;
X      if (v > val) {
X        val = v;
X        l = j;                          /* l ::= predecessor of best */
X      }
X    }
X    if (i != l) {
X      rr[l] = rr[k = rr[l]];              /* move best */
X      rr[k] = rr[i];
X      i = rr[i] = k;
X    } else i = rr[i];
X
X    MAKEMOV(i);
X    val = ABOPP(alpha, beta);
X    BACKMOV();
X    if (val IMPRVS score) {
X      besti = i;
X      if ((score = val) IMPRVS WRSTBND && (WRSTBND = val) NOWORSE BESTBND) {
X        if (score == DRAW && rr[i])
X          score = NOLOSE;
X        break;
X      }
X    }
X  }
X  for (j = i = 0; (i = rr[i]) != besti; j++)
X    KILLER[height[i]]--;			/* punish bad killers */
X  KILLER[height[besti]] += j;
X  poscnt = posed - poscnt;
X  for (work=1; poscnt>>=1; work++) ;	/* work = log of #positions stored */
X  if (x) {
X    if (score == DRIN1+DRIN2 - SCORE(x))	/* combine < and > */
X      score = DRAW;
X    (void)transrestore(columns, score, work);
X  } else (void)transtore(columns, score, work);
X  return score;
X}
X
X#undef ME
X#undef OPP
X#undef BOOKME
X#undef BOOKOPP
X#undef ABME
X#undef ABOPP
X#undef THRME
X#undef THROPP
X#undef IWIN
X#undef ILOSE
X#undef MAKEMOV
X#undef BACKMOV
X#undef WORST
X#undef KILLER
X#undef WRSTBND
X#undef BESTBND
X#undef IMPRVS
X#undef NOWORSE
X#undef NOLOSE
END_OF_FILE
if test 3409 -ne `wc -c <'best.h'`; then
    echo shar: \"'best.h'\" unpacked with wrong size!
fi
# end of 'best.h'
fi
if test -f 'c4.c' -a "${1}" != "-c" ; then 
  echo shar: Will not clobber existing file \"'c4.c'\"
else
echo shar: Extracting \"'c4.c'\" \(3307 characters\)
sed "s/^X//" >'c4.c' <<'END_OF_FILE'
X/*
X * Fhourstones connect-4 solver
X *
X * implementation of the well-known game
X * played on a vertical board of 7 columns by 6 rows,
X * where 2 players take turns in dropping counters in a column.
X * the first player to get four of his counters
X * in a horizontal, vertical or diagonal row, wins the game.
X * if neither player has won after 42 moves, then the game is drawn.
X *
X * This software is copyright (c) 1992 by
X *      John Tromp
X *      Lindenlaan 33
X *      1701 GT Heerhugowaard
X *      Netherlands
X * E-mail: tromp@cwi.nl
X *
X * This notice must not be removed.
X * This software must not be sold for profit.
X * You may redistribute if your distributees have the
X * same rights and restrictions.
X */
X
X
X#include "c4.h"
X
Xstatic
Xint history[43],	/* history of current game */
X    movenr;		/* number of counters played in current game */
X
Xstatic
Xint error,		/* invalid user input */
X    gameover;		/* game has been drawn or won */
Xextern int window;	/* search window */
X
Xvoid initall()
X{
X  extern void initbest(),inittrans(),initplay();
X
X  initbest();
X  inittrans();
X  initplay();
X}
X
Xvoid game()
X{
X  extern void newgame();
X
X  movenr = gameover = 0;
X  newgame();
X}
X
Xvoid play(n)
Xint n;
X{
X  extern int depth();
X  extern void makemovx(),makemovo();
X
X   if (error = n < 1 || n > 7 || !depth(n) || gameover)
X      return;
X   if (history[movenr] != n)
X   {  history[movenr] = n;
X      history[movenr+1] = 0;     /* end of variation */
X   }
X   if (++movenr & 1)
X     makemovo(n);
X   else
X     makemovx(n);
X   gameover = haswon() || movenr == 42;
X}
X
Xmain()
X{
X  int c,i,result;
X  extern int best();
X  extern void loadbook(),htstat();
X  extern u_int nodes;
X  double timearray[3];
X  extern int dtime();
X
X  initall();
X#ifdef BOOK
X  loadbook();
X#endif
X  (void)printf("options:");
X#ifdef SMALL
X  (void)printf("    small ints");
X#endif
X  (void)printf("\n");
X  for (;;) {
X    game();
X    while ((c = getchar()) != EOF) {
X      if (c >= '1' && c <= '7')
X        c -= '0';
X      else if (c >= 'A' && c <= 'G')
X        c -= ('A' - 1);
X      else if (c >= 'a' && c <= 'g')
X        c -= ('a' - 1);
X      else if (c == '=' || c == '+' || c == '-' ||
X               (error = c != ' ' && c != '\t' && c != '\n'))
X        break;
X      else continue;
X      play(c);
X      if (error) {
X        (void)printf("illegal move.\n");
X        break;
X      }
X    }
X    if (c == EOF)
X      break;
X    if (error) {
X      error = 0;
X      continue;
X    }
X    if (gameover) {
X      (void)printf("Game is over.\n");
X      continue;
X    }
X
X    switch (c) {
X    case '-':
X      window = 2;
X      (void)printf("Looking for 2nd player win in");
X      break;
X    case '=':
X      window = 0;
X      (void)printf("Solving");
X      break;
X    case '+':
X      window = 1;
X      (void)printf("Looking for 1st player win in");
X      break;
X    }
X    (void)printf(" %d-ply position after ", movenr);
X    for (i = 0; i < movenr; i++)
X      (void)printf("%d", history[i]);
X    (void)printf(" . . .\n");
X
X    dtime(timearray);
X    result = best();		/* expect work << 3 | score */
X    dtime(timearray);
X    (void)printf("score = %d (%c)  work = %d\n", result&7,
X           "   -<=>+"[result&7], result>>3);
X    (void)printf("%u pos / %.1f sec = %d p/s\n",
X             nodes, timearray[1], (int)((double)nodes/timearray[1]));
X    htstat();
X  }
X  return 0;
X}
END_OF_FILE
if test 3307 -ne `wc -c <'c4.c'`; then
    echo shar: \"'c4.c'\" unpacked with wrong size!
fi
# end of 'c4.c'
fi
if test -f 'c4.h' -a "${1}" != "-c" ; then 
  echo shar: Will not clobber existing file \"'c4.h'\"
else
echo shar: Extracting \"'c4.h'\" \(600 characters\)
sed "s/^X//" >'c4.h' <<'END_OF_FILE'
X/* type-definitions
X   (c) 1992 John Tromp
X*/
X
X#include <sys/types.h>
X#include <stdio.h>
Xextern void exit();
X
Xextern char *calloc();
X#define allocate(N, T)  ((T *)calloc((unsigned)N,sizeof(T)))
X#define UNK		2
X#define WIN2		3
X#define DRIN2		4
X#define DRAW		5
X#define DRIN1		6
X#define WIN1		7
X#define EXACT(S)	((S)==WIN2 || (S)==DRAW || (S)==WIN1)
X#define SCORE(X)	((X) & 7)
X#define WORK(X)		((X) >> 3)
X#define LASTMOVE        moves[plycnt-1]
X
X#ifdef SMALL
Xtypedef u_char uint8;
Xtypedef u_short uint16;
X#else
Xtypedef int uint8;
Xtypedef int uint16;
X#endif
Xtypedef uint8 B8[8];
Xtypedef u_char hashentry;
END_OF_FILE
if test 600 -ne `wc -c <'c4.h'`; then
    echo shar: \"'c4.h'\" unpacked with wrong size!
fi
# end of 'c4.h'
fi
if test -f 'input' -a "${1}" != "-c" ; then 
  echo shar: Will not clobber existing file \"'input'\"
else
echo shar: Extracting \"'input'\" \(14 characters\)
sed "s/^X//" >'input' <<'END_OF_FILE'
X444333377755=
END_OF_FILE
if test 14 -ne `wc -c <'input'`; then
    echo shar: \"'input'\" unpacked with wrong size!
fi
# end of 'input'
fi
if test -f 'mach.c' -a "${1}" != "-c" ; then 
  echo shar: Will not clobber existing file \"'mach.c'\"
else
echo shar: Extracting \"'mach.c'\" \(7335 characters\)
sed "s/^X//" >'mach.c' <<'END_OF_FILE'
X/*****************************************************/
X/* Various machine dependent timer routines.         */
X/* Al Aburto, aburto@marlin.nosc.mil, 26 Sep 1992    */
X/*                                                   */
X/* dtime(p) outputs the elapsed time seconds in p[1] */
X/* from a call of dtime(p) to the next call of       */
X/* dtime(p).  Use CAUTION as some of these routines  */
X/* will mess up when timing across the hour mark!!!  */
X/*                                                   */
X/* For timing I use the 'user' time whenever         */
X/* possible. Using 'user+sys' time is a separate     */
X/* issue.                                            */
X/*                                                   */
X/* Example Usage:                                    */
X/* [Timer options added here]                        */
X/* double RunTime, TimeArray[3];                     */
X/* main()                                            */
X/* {                                                 */
X/* dtime(TimeArray);                                 */ 
X/* [routine to time]                                 */
X/* dtime(TimeArray);                                 */
X/* RunTime = TimeArray[1];                           */
X/* }                                                 */
X/* [Timer code added here]                           */
X/*****************************************************/
X
X/***************************************************************/
X/* Timer options. You MUST uncomment one of the options below  */
X/* or compile, for example, with the '-DUNIX' option.          */
X/***************************************************************/
X/* #define Amiga       */
X/* #define UNIX        */
X/* #define UNIX_Old    */
X/* #define VMS         */
X/* #define BORLAND_C   */
X/* #define MSC         */
X/* #define MAC         */
X/* #define IPSC        */
X/* #define FORTRAN_SEC */
X/* #define GTODay      */
X/* #define CTimer      */
X
X/******************************/
X/* Timer code.                */
X/******************************/
X/*******************/
X/*  Amiga dtime()  */
X/*******************/
X#ifdef Amiga
X#include <ctype.h>
X#define HZ 50
X
Xdtime(p)
Xdouble p[];
X{
X   double q;
X
X   struct   tt {
X      long  days;
X      long  minutes;
X      long  ticks;
X   } tt;
X
X   q = p[2];
X
X   DateStamp(&tt);
X
X   p[2] = ( (double)(tt.ticks + (tt.minutes * 60L * 50L)) ) / (double)HZ;
X   p[1] = p[2] - q;
X   
X   return 0;
X}
X#endif
X
X/*****************************************************/
X/*  UNIX dtime(). This is the preferred UNIX timer.  */
X/*  Provided by: Markku Kolkka, mk59200@cc.tut.fi    */
X/*  HP-UX Addition by: Bo Thide', bt@irfu.se         */
X/*****************************************************/
X#ifdef UNIX
X#include <sys/time.h>
X#include <sys/resource.h>
X
X#ifdef hpux
X#include <sys/syscall.h>
X#define getrusage(a,b) syscall(SYS_getrusage,a,b)
X#endif
X
Xstruct rusage rusage;
X
Xdtime(p)
Xdouble p[];
X{
X   double q;
X
X   q = p[2];
X
X   getrusage(RUSAGE_SELF,&rusage);
X
X   p[2] = (double)(rusage.ru_utime.tv_sec);
X   p[2] = p[2] + (double)(rusage.ru_utime.tv_usec) * 1.0e-06;
X   p[1] = p[2] - q;
X   
X   return 0;
X}
X#endif
X
X/***************************************************/
X/*  UNIX_Old dtime(). This is the old UNIX timer.  */
X/*  Use only if absolutely necessary as HZ may be  */
X/*  ill defined on your system.                    */
X/***************************************************/
X#ifdef UNIX_Old
X#include <sys/types.h>
X#include <sys/times.h>
X#include <sys/param.h>
X
X#ifndef HZ
X#define HZ 60
X#endif
X
Xstruct tms tms;
X
Xdtime(p)
Xdouble p[];
X{
X   double q;
X
X   q = p[2];
X
X   times(&tms);
X
X   p[2] = (double)(tms.tms_utime) / (double)HZ;
X   p[1] = p[2] - q;
X   
X   return 0;
X}
X#endif
X
X/*********************************************************/
X/*  VMS dtime() for VMS systems.                         */
X/*  Provided by: RAMO@uvphys.phys.UVic.CA                */
X/*  Some people have run into problems with this timer.  */
X/*********************************************************/
X#ifdef VMS
X#include time
X
X#ifndef HZ
X#define HZ 100
X#endif
X
Xstruct tbuffer_t
X       {
X	int proc_user_time;
X	int proc_system_time;
X	int child_user_time;
X	int child_system_time;
X       };
Xstruct tbuffer_t tms;
X
Xdtime(p)
Xdouble p[];
X{
X   double q;
X
X   q = p[2];
X
X   times(&tms);
X
X   p[2] = (double)(tms.proc_user_time) / (double)HZ;
X   p[1] = p[2] - q;
X   
X   return 0;
X}
X#endif
X
X/******************************/
X/*  BORLAND C dtime() for DOS */
X/******************************/
X#ifdef BORLAND_C
X#include <ctype.h>
X#include <dos.h>
X#include <time.h>
X
X#define HZ 100
Xstruct time tnow;
X
Xdtime(p)
Xdouble p[];
X{
X   double q;
X
X   q = p[2];
X
X   gettime(&tnow);
X
X   p[2] = 60.0 * (double)(tnow.ti_min);
X   p[2] = p[2] + (double)(tnow.ti_sec);
X   p[2] = p[2] + (double)(tnow.ti_hund)/(double)HZ;
X   p[1] = p[2] - q;
X   
X   return 0;
X}
X#endif
X
X/**************************************/
X/*  Microsoft C (MSC) dtime() for DOS */
X/**************************************/
X#ifdef MSC
X#include <time.h>
X#include <ctype.h>
X
X#define HZ CLK_TCK
Xclock_t tnow;
X
Xdtime(p)
Xdouble p[];
X{
X   double q;
X
X   q = p[2];
X
X   tnow = clock();
X
X   p[2] = (double)tnow / (double)HZ;
X   p[1] = p[2] - q;
X   
X   return 0;
X}
X#endif
X
X/*************************************/
X/*  Macintosh (MAC) Think C dtime()  */
X/*************************************/
X#ifdef MAC
X#include <time.h>
X
X#define HZ 60
X
Xdtime(p)
Xdouble p[];
X{
X   double q;
X
X   q = p[2];
X
X   p[2] = (double)clock() / (double)HZ;
X   p[1] = p[2] - q;
X   
X   return 0;
X}
X#endif
X
X/************************************************************/
X/*  iPSC/860 (IPSC) dtime() for i860.                       */
X/*  Provided by: Dan Yergeau, yergeau@gloworm.Stanford.EDU  */
X/************************************************************/
X#ifdef IPSC
Xextern double dclock();
X
Xdtime(p)
Xdouble p[];
X{
X   double q;
X
X   q = p[2];
X
X   p[2] = dclock();
X   p[1] = p[2] - q;
X   
X   return 0;
X}
X#endif
X
X/**************************************************/
X/*  FORTRAN dtime() for Cray type systems.        */
X/*  This is the preferred timer for Cray systems. */
X/**************************************************/
X#ifdef FORTRAN_SEC
X
Xfortran double second();
X
Xdtime(p)
Xdouble p[];
X{
X   double q,v;
X
X   q = p[2];
X
X   second(&v);
X   p[2] = v;
X   p[1] = p[2] - q;
X   
X   return 0;
X}
X#endif
X
X/***********************************************************/
X/*  UNICOS C dtime() for Cray UNICOS systems.  Don't use   */
X/*  unless absolutely necessary as returned time includes  */
X/*  'user+system' time.  Provided by: R. Mike Dority,      */
X/*  dority@craysea.cray.com                                */
X/***********************************************************/
X#ifdef CTimer
X#include <time.h>
X
Xdtime(p)
Xdouble p[];
X{
X   double    q;
X   clock_t   t;
X
X       q = p[2];
X
X       t = clock();
X
X       p[2] = (double)t / (double)CLOCKS_PER_SEC;
X       p[1] = p[2] - q;
X
X       return 0;
X}
X#endif
X
X/********************************************/
X/* Another UNIX timer using gettimeofday(). */
X/* However, getrusage() is preferred.       */
X/********************************************/
X#ifdef GTODay
X#include <sys/time.h>
X
Xstruct timeval tnow;
X
Xdtime(p)
Xdouble p[];
X{
X   double q;
X
X   q = p[2];
X
X   gettimeofday(&tnow,NULL);
X   p[2] = (double)tnow.tv_sec + (double)tnow.tv_usec * 1.0e-6;
X   p[1] = p[2] - q;
X
X   return 0;
X}
X#endif
X
END_OF_FILE
if test 7335 -ne `wc -c <'mach.c'`; then
    echo shar: \"'mach.c'\" unpacked with wrong size!
fi
# end of 'mach.c'
fi
if test -f 'play.c' -a "${1}" != "-c" ; then 
  echo shar: Will not clobber existing file \"'play.c'\"
else
echo shar: Extracting \"'play.c'\" \(2236 characters\)
sed "s/^X//" >'play.c' <<'END_OF_FILE'
X/* internal move routines 
X   (c) 1992 John Tromp
X*/
X
X#include "c4.h"
X
X#define xdiabase   (xdias+6)
X#define odiabase   (odias+6)
X
Xstatic B8 linit = {7,6,5,4,0,3,2,1},
X          rinit = {4,7,6,5,3,2,1,0};
Xstatic uint8 msafe[43];
Xstatic uint8 four[128];
Xstatic uint16 xrows[8], orows[8], xdias[21], odias[21];
Xstatic uint8 initdias[21] = {0,0,0,1,2,3,5,6,7,0,0,0,1,2,3,5,6,7,0,0,0};
Xstatic uint8 typemask[8] = {0, 0x78, 0x7c, 0x7e, 0x7f, 0x3f, 0x1f, 0x0f};
Xstatic uint8 thrcols[1024];
X
Xint plycnt;
XB8 l, r, columns, height;
Xuint8 *moves = msafe+1;
Xuint8 xthrcnt[64],othrcnt[64],colthr[128];
X
Xvoid inithrcols()     /* compute threat columns */
X{
X  int i,j,m,t;
X
X  for (i = 0; i < 0x80; i++)
X    for (j = 0x80 | i; j >= 0x10; j >>= 1)
X      if ((j & 0xf) == 0xf) {
X        four[i] = 1;
X        break;
X      }
X  for (i = 0; i < 0x80; i++)
X    if (!four[i])				/* no 4 connected */
X      for (j = 1, m = 0x80; m >>= 1; j++)	/* try 4th stone */
X        if (four[i | m])			/* threat */
X          for (t = 1; t < 8; t++)		/* update relevant types */
X            if (typemask[t] & m)
X              thrcols[t << 7 | i] = thrcols[t << 7 | i] << 3 | j;
X}
X
Xvoid initcolthr()     /* compute column threats */
X{
X  int i;
X
X  for (i=0x8; i<0x40; i+=8) {
X    colthr[i] = 1;		/* threat for player2?! */
X    colthr[i+7] = 2;		/* threat for player1?! */
X  }
X}
X
Xvoid newgame()
X{
X  int i;
X
X  plycnt = 0;
X  for (i=0; i<21; i++)
X    xdias[i] = odias[i] = initdias[i] << 7;
X  for (i=0; i<8; i++) {
X    height[i] = 7*8 + i;
X    xrows[i] = orows[i] = 4 << 7;
X    columns[i] = 1;
X    l[i] = linit[i];
X    r[i] = rinit[i];
X  }
X  for (i=0; i<64; i++) {
X    othrcnt[i] = xthrcnt[i] = 0;
X  }
X}
X
Xvoid initplay()
X{
X  inithrcols();
X  initcolthr();
X  newgame();
X}
X
Xint depth(n)	/* returns 0 (full) through 6 (empty) */
Xint n;
X{
X  return (height[n]>>3) - 1;
X}
X
Xint haswon()
X{
X  if (plycnt < 7)
X    return 0;
X  return ((plycnt & 1) ? othrcnt : xthrcnt)[height[LASTMOVE]+8];
X}
X
X#define BACKMOV	backmovx
X#define MAKEMOV	makemovx
X#define ROWS	xrows
X#define DIABASE	xdiabase
X#define THRCNT	xthrcnt
X#define BIT
X#include "play.h"
X
X#define BACKMOV	backmovo
X#define MAKEMOV	makemovo
X#define ROWS	orows
X#define DIABASE	odiabase
X#define THRCNT	othrcnt
X#define BIT	| 1
X#include "play.h"
END_OF_FILE
if test 2236 -ne `wc -c <'play.c'`; then
    echo shar: \"'play.c'\" unpacked with wrong size!
fi
# end of 'play.c'
fi
if test -f 'play.h' -a "${1}" != "-c" ; then 
  echo shar: Will not clobber existing file \"'play.h'\"
else
echo shar: Extracting \"'play.h'\" \(1443 characters\)
sed "s/^X//" >'play.h' <<'END_OF_FILE'
Xvoid BACKMOV()
X{
X  u_int mask,d,hi,h;
X  int n,v;
X
X  n = moves[--plycnt];
X  if ((hi = height[n] += 8) < 24)
X    l[r[n]]=r[l[n]]=n;
X  h = hi>>3;
X  columns[n] >>= 1;
X  mask = ~(0x80 >> n);
X  ROWS[h] = (d = ROWS[h]) & mask;
X  if (v = thrcols[d]) {
X    --THRCNT[hi+((v&7)-n)];
X    if (v >>= 3)
X      --THRCNT[hi+(v-n)];
X  }
X  if (d = DIABASE[n+h]) {
X    DIABASE[n+h] = d & mask;
X    if (v = thrcols[d]) {
X      --THRCNT[hi-7*((v&7)-n)];
X      if (v >>= 3)
X        --THRCNT[hi-7*(v-n)];
X    }
X  }
X  if (d = DIABASE[n-h]) {
X    DIABASE[n-h] = d & mask;
X    if (v = thrcols[d]) {
X      --THRCNT[hi+9*((v&7)-n)];
X      if (v >>= 3)
X        --THRCNT[hi+9*(v-n)];
X    }
X  }
X}
X
Xvoid MAKEMOV(n) 
Xint n;
X{
X  u_int mask,d,hi,h;
X  int v;
X
X  moves[plycnt++] = n;
X  hi = height[n];
X  h = hi>>3;
X  if ((height[n] = hi-8) < 16)
X    l[r[l[n]]=r[n]]=l[n];
X  columns[n] = columns[n] << 1 BIT;
X  mask = 0x80 >> n;
X  d = ROWS[h] |= mask;
X  if (v = thrcols[d]) {
X    ++THRCNT[hi+((v&7)-n)];
X    if (v >>= 3)
X      ++THRCNT[hi+(v-n)];
X  }
X  if (d = DIABASE[n+h]) {
X    DIABASE[n+h] = d |= mask;
X    if (v = thrcols[d]) {
X      ++THRCNT[hi-7*((v&7)-n)];
X      if (v >>= 3)
X        ++THRCNT[hi-7*(v-n)];
X    }
X  }
X  if (d = DIABASE[n-h]) {
X    DIABASE[n-h] = d |= mask;
X    if (v = thrcols[d]) {
X      ++THRCNT[hi+9*((v&7)-n)];
X      if (v >>= 3)
X        ++THRCNT[hi+9*(v-n)];
X    }
X  }
X}
X
X#undef BACKMOV
X#undef MAKEMOV
X#undef ROWS
X#undef DIABASE
X#undef THRCNT
X#undef BIT
END_OF_FILE
if test 1443 -ne `wc -c <'play.h'`; then
    echo shar: \"'play.h'\" unpacked with wrong size!
fi
# end of 'play.h'
fi
if test -f 'trans.c' -a "${1}" != "-c" ; then 
  echo shar: Will not clobber existing file \"'trans.c'\"
else
echo shar: Extracting \"'trans.c'\" \(4179 characters\)
sed "s/^X//" >'trans.c' <<'END_OF_FILE'
X/* transposition table routines 
X   (c) 1992 John Tromp
X*/
X
X#include "c4.h"
X
X#define HTSIZE  1050011		/* not to be messed with:-) */
X#define HTD	(HTSIZE & 0xfffff)
X#define STRNG	(HTD/8)
X#define STD	(0x100-STRNG)
X#ifndef	PROBES
X#define PROBES	8
X#endif
X
Xstatic u_int *ht;			/* hash locks */
Xstatic hashentry *he;			/* hash entries */
Xstatic u_int stride;
Xstatic u_int htindex, lock, hits;
Xstatic u_int works[32];
Xstatic u_int typecnt[8];                /* bound type stats */
X
Xtypedef struct {
X  unsigned htmod:24;
X  unsigned stmod: 8;
X} mods;
X
Xstatic mods mulmod[0x402];
X
Xu_int posed;				/* counts transtore calls */
X
Xvoid inittrans()
X{
X  int i, htm, stm;
X
X  ht = allocate(HTSIZE,u_int);
X  he = allocate(HTSIZE,hashentry);
X  if (ht == NULL || he == NULL) {
X    printf("Out of memory; failed to allocate %d bytes.\n",
X	   HTSIZE * (sizeof(u_int) + sizeof(hashentry)));
X    exit(0);
X  }
X
X  for (i = htm = stm = 0; i < 0x402; i++) {
X    mulmod[i].htmod = htm;
X    mulmod[i].stmod = stm;
X    if ((htm -= HTD) < 0)
X      htm += HTSIZE;
X    if ((stm += STD) >= STRNG)
X      stm -= STRNG;
X  }
X}
X
Xvoid emptyht()
X{
X  int i;
X
X  for (i=0; i<HTSIZE; i++)
X    if (he[i] < 0xf8)           /* leave book-entries intact */
X      he[i] &= 0x07;
X  posed = hits = 0;
X}
X
Xdouble hitrate()
X{
X  return posed ? (double)hits/(double)posed : 0.0;
X}
X
Xvoid hash(pos)
XB8 pos;
X{
X  register u_int htemp,stemp,t,t1,t2;
X
X  t1 = (pos[1] << 7 | pos[2]) << 7 | pos[3];
X  t2 = (pos[7] << 7 | pos[6]) << 7 | pos[5];
X  
X  if (t1 > t2) {
X    lock = (t1 << 7 | pos[4]) << 4 | t2 >> 17;
X    t = t2 & 0x7ffff;
X  } else {
X    lock = (t2 << 7 | pos[4]) << 4 | t1 >> 17;
X    t = t1 & 0x7ffff;
X  }
X  htemp = (lock >> 2 & 0xfffff) + mulmod[lock >> 22].htmod;
X  htemp = ((htemp & 0x7ff) << 9 | (t >> 10)) + mulmod[htemp >> 11].htmod;
X  if (htemp >= HTSIZE)
X    htemp -= HTSIZE;
X  htemp = ((htemp & 0x3ff) << 10 | (t & 0x3ff)) + mulmod[htemp >> 10].htmod;
X  htindex = htemp >= HTSIZE ? htemp - HTSIZE : htemp;
X  
X  stemp = (lock >> 16 & 0xff) + mulmod[lock >> 24].stmod;
X  stemp = (lock >>  8 & 0xff) + mulmod[stemp].stmod;
X  stemp = (lock       & 0xff) + mulmod[stemp].stmod;
X  if (stemp >= STRNG && (stemp -= STRNG) >= STRNG)
X    stemp -= STRNG;
X  stride = stemp + 0x20000;
X}
X
Xint transpose(pos)
XB8 pos;
X{
X  int i,x;
X
X  hash(pos);
X  for (x=htindex, i=0; i < PROBES; i++) {
X    if (ht[x] == lock)                /* CACHE MISS! */
X      return he[x];
X    if ((x += stride) >= HTSIZE)
X      x -= HTSIZE;
X  }
X  return 0;
X}
X
Xint transrestore(pos,score,work)
XB8 pos;
Xint score,work;
X{
X  register int i,x;
X
X  posed++;
X  hash(pos);
X  for (x=htindex, i=0; i < PROBES; i++) {
X    if (ht[x] == lock) {               /* CACHE MISS! */
X      hits++;
X      he[x] = work << 3 | score;
X      return 1;
X    }
X    if ((x += stride) >= HTSIZE)
X      x -= HTSIZE;
X  }
X  for (x=htindex, i=0; i < PROBES; i++) {
X    if (work > WORK(he[x])) {
X      hits++;
X      ht[x] = lock;
X      he[x] = work << 3 | score;
X      return 1;
X    }
X    if ((x += stride) >= HTSIZE)
X      x -= HTSIZE;
X  }
X  return 0;         /* not good enough to replace existing entries */
X}
X
Xint transtore(pos,score,work)
XB8 pos;
Xint score,work;
X{
X  register int i,x;
X
X  posed++;
X  hash(pos);
X  for (x=htindex, i=0; i < PROBES; i++) {
X    if (work > WORK(he[x])) {
X      hits++;
X      ht[x] = lock;
X      he[x] = work << 3 | score;
X      return 1;
X    }
X    if ((x += stride) >= HTSIZE)
X      x -= HTSIZE;
X  }
X  return 0;         /* not good enough to replace existing entries */
X}
X
Xdouble rate(S)
Xint S;
X{
X  u_int total;
X  int i;
X
X  for (total=i=0; i<8; i++)
X    total += typecnt[i];
X  return total ? (double)typecnt[S]/(double)total : 0.0;
X}
X
Xvoid htstat()      /* some statistics on hash table performance */
X{
X  int i;
X
X  for (i=0; i<32; i++)
X    works[i] = 0;
X  for (i=0; i<8; i++)
X    typecnt[i] = 0;
X  for (i=0; i<HTSIZE; i++) {
X    works[WORK(he[i])]++;
X    if (WORK(he[i]))
X      typecnt[SCORE(he[i])]++;
X  }
X  (void)printf("store rate = %.3f\n",hitrate());
X  (void)printf("- %5.3f  < %5.3f  = %5.3f  > %5.3f  + %5.3f\n",
X            rate(WIN2),rate(DRIN2),rate(DRAW),rate(DRIN1),rate(WIN1));
X  for (i=0; i<32; i++)
X    (void)printf("%6u%c",works[i],(i&7)==7?'\n':'\t');
X}
END_OF_FILE
if test 4179 -ne `wc -c <'trans.c'`; then
    echo shar: \"'trans.c'\" unpacked with wrong size!
fi
# end of 'trans.c'
fi
echo shar: End of shell archive.
exit 0
Newsgroups: comp.benchmarks