NetNews Usenet Archive 1992 #19/NN_1992_19.iso/spool/comp/theory/cellaut/365

Text File | 1992-09-03 | 5.6 KB | 129 lines

Newsgroups: comp.theory.cell-automata
Path: sparky!uunet!mcsun!ieunet!tcdcs!maths.tcd.ie!chughes
From: [e-mail] (Conrad Hughes)
Subject: Fast parallel Life implementation
Message-ID: <[e-mail]>
Keywords: real mode life game parallel
Organization: Dept. of Maths, Trinity College, Dublin, Ireland.
References: <a_#n=[e-mail]> <[e-mail]>
Date: Thu, 3 Sep 1992 12:22:15 GMT
Lines: 117


  Here's my fast parallel life engine - I'm only including the core
bit to calculate the new state of a group of thirty-two cells when
given the state of that group and their eight sets of thirty-two
neighbours.

  Plugging it into some other life program should be quite trivial.
I include my original ARM2 assembler core and untested C source
derived from it - I would add the caveat that I no longer have
documentation for the standard rules of Conway's life, and consequently
the final calculation may not be accurate - this doesn't seem to
be the case however, as I get very "life-like" (sorry) behaviour
from the program..

  If anybody has further questions about this, please contact me -
I'll be glad (if somewhat slow) to help..  No guarantee, express or
implied, &c. &c.

  If you feel like using this in something, I'd be interested to
hear from you (and I'd appreciate a mention in the credits :-).

  Sorry for the delay in posting,
    Conrad

-- ARM assembly version
\ On entry:
\   registers 0, 1, 2, 3, 5, 6, 7 & 8 each contain a set of thirty-two
\   neighbours, in any grouping - i.e. R0 could be the up-left
\   neighbours or the right neighbours, it doesn't matter.
\   register 4 contains the current state of the cells to be processed.
\ On exit:
\   register 0 contains the new state of the processed group of cells.
\ When I say 'contains', I mean that if bit 0 is set, the leftmost cell
\   is alive, otherwise the leftmost cell is dead, bit 1 indicates life
\   or death for the second cell from the left, and so on.  Big-endian
\   systems may prefer a reverse order, it doesn't matter.
\ These instructions operate in the following way:
\   OP <reg0>, <reg1>, <reg2> means reg0 = reg1 OP reg 2
\ where AND, ORR and EOR are bitwise and, or and exclusive-or operations,
\ BIC is bit-clear, or 'AND NOT'.
AND9,0,1:EOR0,0,1
AND1,0,2:EOR0,0,2:EOR9,9,1
AND1,0,3:EOR0,0,3:AND3,9,1:EOR9,9,1
AND1,0,5:EOR0,0,5:AND5,9,1:EOR9,9,1:EOR3,3,5
AND1,0,6:EOR0,0,6:AND6,9,1:EOR9,9,1:EOR3,3,6
AND1,0,7:EOR0,0,7:AND7,9,1:EOR9,9,1:EOR3,3,7
AND1,0,8:EOR0,0,8:AND8,9,1:EOR9,9,1:EOR3,3,8
ORR0,0,4:AND0,0,9:BIC0,0,3

-- C version -- UNTESTED, verify correct behaviour before you trust it!
/* LT should be a 32-bit int type, but for smaller or larger machines
 * could easily be 8, 16, 64 bits - whatever you like, really.
 * cs is the group of cells to be worked on, and n1-n8 are the groups of
 * neighbours.  If you stored your cell states in an array of 32-bit
 * integers, you could process those in c[x][y] with the following
 * instruction (I think):
 * d[x][y] = nextgen(c[x][y], (c[x-1][y-1] << 31) | (c[x][y-1] >> 1),
 *                   c[x][y-1], (c[x][y-1] << 1) | (c[x+1][y-1] >> 31),
 *                   (c[x-1][y] << 31) | (c[x][y] >> 1),
 *                   (c[x][y] << 1) | (c[x+1][y] >> 31),
 *                   (c[x-1][y+1] << 31) | (c[x][y+1] >> 1), c[x][y+1],
 *                   (c[x][y+1] << 1) | (c[x+1][y+1] >> 31));
 * [the array must be unsigned for the right shift >> to work]
 * Obviously, you can't store the new states back into c[][] without
 * some kind of buffering, so for simplicity I'm just putting them
 * into d[][] instead.
 */

LT nextgen(LT cs, LT n1, LT n2, LT n3, LT n4, LT n5, LT n6, LT n7, LT n8)
  {
  LT b0, b1, b2, b3, c0, c1;

/* Adding the first two neighbours, max result is 2, needs two bits */
  b1 = n1 & n2; /* Carry flags from adding n2 to n1 go into bit 1 */
  b0 = n1 ^ n2; /* Update bit 0 */

/* Adding the third neighbour, max result is 3, still need only two bits */
  c0 = b0 & n3; /* Carry flags from adding n3 to bit 0 */
  b0 ^= n3;     /* Update bit 0 */
  b1 ^= c0;     /* No overflow from bit 1 is possible yet, so just add carry */

/* Adding the fourth neighbour, we need three bits now */
  c0 = b0 & n4; /* Carry flags, same as before */
  b0 ^= n4;     /* Update bit 0 */
  b2 = b1 & c0; /* Carry flags from adding carry to bit 1 go into bit 2 */
  b1 ^= c0;     /* Update bit 1 */

/* Adding fifth neighbour, working with three bits */
  c0 = b0 & n5; /* Carry flags */
  b0 ^= n5;
  c1 = b1 & c0; /* Carry flags from bit 1 */
  b1 ^= c0;     /* Add carry to bit 1 */
  b2 ^= c1;     /* Add carry flags to bit 2 */

/* Adding sixth and seventh neighbours is much the same as adding the fifth */
  c0 = b0 & n6; b0 ^= n6; c1 = b1 & c0; b1 ^= c0; b2 ^= c1;
  c0 = b0 & n7; b0 ^= n7; c1 = b1 & c0; b1 ^= c0; b2 ^= c1;

/* Adding the eighth neighbour could result in carry, but bit 3 is not
 * necessary for results - when it is set, all other bits are clear, and
 * consequently it becomes unnecessary in the application of the rules
 */
  c0 = b0 & n8; b0 ^= n8; c1 = b1 & c0; b1 ^= c0; b2 ^= c1;

/* Dead cells come to life if they have three neighbours alive,
 *  i.e. bits 0 and 1 are set, bit 2 is clear.
 * Live cells die unless they have two or three neighbours alive,
 *  i.e. bit 1 is set, bit 2 is clear.
 * These two combine in the following expression:
 */
  return((b0 | cs) & b1 & (-1 ^ b2));
}
--
,--------------------. Suicide City, Paranoid State. Geddout! trip to, heave'n'
|[e-mail]| ho, up, down, to'n'fro you have no word please leave us
+-=>Conrad  Hughes<=-+ here close our eyes to the octopus ride isn't it good to
`-------<SICK>-------' be lost in the wood isn't it bad so quiet there . . .