Conway's Game Of Life

gameoflife.c

#include <stdio.h>
#include <stdint.h>
#include <stdlib.h>
#include <strings.h>
#include <inttypes.h>

// Dimensions are statically defined for now
#define WIDTH 32
#define HEIGHT 32

// For debugging
#define DEBUG(str) fprintf(stdout, #str"\n");
#define DVAR(var) fprintf(stdout, #var": %i\n", var);

#if UINTMAX_MAX == 0xFF
// In bits
#define INT_WIDTH 8
// In bytes
#define INT_SIZE  1
#define DIV_SHIFT 3
#define MODULO_MASK 0x07
#elif UINTMAX_MAX == 0xFFFF
#define INT_WIDTH 16
#define INT_SIZE  2
#define DIV_SHIFT 4
#define MODULO_MASK 0x0F
#elif UINTMAX_MAX == 0xFFFFFFFF
#define INT_WIDTH 32
#define INT_SIZE  4
#define DIV_SHIFT 5
#define MODULO_MASK 0x1F
#elif UINTMAX_MAX == 0xFFFFFFFFFFFFFFFF
#define INT_WIDTH 64
#define INT_SIZE  8
#define DIV_SHIFT 6
#define MODULO_MASK 0x3F
#else
#error "unsupported integer width"
#endif

// Retrieve the cell at index in the medium
#define GET_CELL(medium, index) \
  ((medium[index >> DIV_SHIFT] &   (UINT64_C(1) << (index & MODULO_MASK))) ? 1 : 0)
#define SET_CELL(medium, index) \
  ((medium[index >> DIV_SHIFT] |=  (UINT64_C(1) << (index & MODULO_MASK))) ? 1 : 0)
#define UNSET_CELL(medium, index) \
  ((medium[index >> DIV_SHIFT] &= ~(UINT64_C(1) << (index & MODULO_MASK))) ? 1 : 0)

typedef struct world {
  uintmax_t *medium;
  uintmax_t *next_medium;
  uint16_t width;
  uint16_t height;
  uintmax_t nbbytes;
  uintmax_t medium_size;
  uintmax_t world_size;
} world_t;

world_t *init_world(uint16_t width, uint16_t height) {
  world_t *world = (world_t *) malloc(sizeof (world_t));
  world->width = width;
  world->height = height;
  world->nbbytes = width * height / sizeof (char);
  world->medium = (uintmax_t *) malloc(world->nbbytes);
  world->next_medium = (uintmax_t *) malloc(world->nbbytes);
  world->medium_size = width * height / sizeof(uintmax_t);
  world->world_size = width * height;
  bzero(world->medium, world->nbbytes);
  return world;
}
 /**
  * Determine if cell at index is alive or not
  * #returns 1 if the cell shall live, 0 othersize
  */
uint8_t evaluate(world_t *world, uintmax_t index) {
  uint8_t cell = GET_CELL(world->medium, index);
  uint8_t neighborhood =
    (index >  0                             ? GET_CELL(world->medium, index - 1) : 0) +
    (index <  world->world_size - 1         ? GET_CELL(world->medium, index + 1) : 0) +
    (index >  WIDTH                         ? GET_CELL(world->medium, index - WIDTH - 1) : 0) +
    (index >= WIDTH                         ? GET_CELL(world->medium, index - WIDTH) : 0) +
    (index >= WIDTH - 1                     ? GET_CELL(world->medium, index - WIDTH + 1) : 0) +
    (index <= world->world_size - WIDTH     ? GET_CELL(world->medium, index + WIDTH - 1) : 0) +
    (index <  world->world_size - WIDTH     ? GET_CELL(world->medium, index + WIDTH) : 0) +
    (index <  world->world_size - WIDTH - 1 ? GET_CELL(world->medium, index + WIDTH + 1) : 0);
  return (cell && (neighborhood == 2 || neighborhood == 3)) ||
    (!cell && neighborhood == 3);
}

/**
 * Execute one cycle of the game of life
 */
void evolve(world_t *world) {
  uintmax_t *medium = world->medium;
  uintmax_t *next_medium = world->next_medium;
  for (uintmax_t i = 0; i < world->height * world->width; ++i)
    if (evaluate(world, i))
      SET_CELL(next_medium, i);
    else
      UNSET_CELL(next_medium, i);
  // Swap current medium with next medeum
  medium = world->medium;
  world->medium = next_medium;
  world->next_medium = medium;
}

/**
 * Check if a world is still alive
 * @returns 1 if living cell are still present, 0 otherwise
 */
uint8_t alive(world_t *world) {
  uintmax_t *medium = world->medium;
  while (medium - world->medium < world->medium_size)
    if (*medium != 0) {
      return 1;
    }
    else
      medium++;
  return 0;
}

/**
 * Print the medium
 */
void print_medium(world_t *world) {
  for (uintmax_t i = 0; i < world->height * world->width; ++i) {
    GET_CELL(world->medium, i) ? fprintf(stdout, "#") : fprintf(stdout, ".");
    if (((i + 1) % world->width) == 0) fprintf(stdout, "\n");
  }
}

int main(int argc, char **argv) {
  world_t *world = init_world(WIDTH, HEIGHT);
  for (uint8_t i = 0; i < WIDTH; ++i)
    SET_CELL(world->medium, i + i * WIDTH);
  for (int8_t i = WIDTH - 1, j = 0; i >= 0; --i, ++j)
    SET_CELL(world->medium, i + j * WIDTH);
  for (uintmax_t i = 0; alive(world); ++i) {
    print_medium(world);
    fprintf(stdout, "--------------------------------------\n");
    // if (i % 100000 == 0) fprintf(stdout, "%"PRId64"th generation\n", i);
    evolve(world);
  }
  print_medium(world);
  return 0;
}