#include "cyccounter.h"
#include <stdlib.h>
#include <iostream>
using namespace std;

// Suppose a grid of height*width cells is initialized with one third
// of them being alive, chosen pseudo-randomly.
//
// Then the grid goes through 10 generations of cell birth and death,
// in accordance with the rules that John Conway established for his
// "Game of life".  That is, a cell is born (in a spot where there is
// currently no living cell) if it has exactly three living neighbors.
// A living cell continues to live so long as it has either two or
// three living neighbors.
//
// After 10 generations have elapsed, how many of the cells are alive?
// This program answers this question.  It takes the height and width
// as command-line parameters.  It also takes a third parameter, which
// is the amount of unused bytes of padding that should be added to
// each row of the arrays used to store liveness information and the
// counts of live neighbors.  This should have no effect on the
// answers the program produces, but may have some influence on the
// speed, due to memory system effects.  Finally, a fourth parameter,
// which should be 0 or 1, controls the verbosity of the output.  If
// it is 0, a terse comma-separated output format is produced,
// suitable for importing into a spreadsheet or other data-analysis
// program.  It lists in order the first three input parameters, the
// number of living cells, and the total number of clock cycles used
// to work through the generations.  If the verbosity parameter is 1,
// then a human-readable summary of the run is produced instead.

static int height, width, padding, verbosity;

// These two are constants, for which we define names just for clarity:

static const int sparseness = 3;   // initially, 1/3 of cells are live
static const int generations = 10; // simulation runs for 10 generations

// The following two pointer variables point to the start of memory
// regions that hold the two arrays.  Even if the padding is 0, these
// arrays are still not height*width in size, but rather
// (height+2)*(width+2), because a border of one extra permanently
// dead cell is added on the top, bottom, left, and right edges of the
// grid to simplify the computation.  (That way all the cells that
// actually participate in the computation have the full complement of
// neighbors on all sides.)  Taking into account the padding at the
// end of each row, the full array sizes (measured in bytes) are
// (height+2)*(width+2+padding). The reason why these are in bytes
// is that the C++ type "char" corresponds to a single byte.

static char *isLivePtr, *neighborsPtr;

// The next two procedures achieve two-dimensional array access; to
// access a particular row and column, one moves a distance into
// memory calculated by multiplying the row number by the size of a
// full row, then adding the column number.  That is because the data
// is layed out consecutively with one row at a time, so the access is
// some number of full rows in plus some distance into the next row
// worth of data.

static inline char& isLive(int row, int col){
  return isLivePtr[row*(width+2+padding) + col];
}

static inline char& neighbors(int row, int col){
  return neighborsPtr[row*(width+2+padding) + col];
}

int main(int argc, char** argv){
  // First check that the program was given the right number of parameters:
  if(argc != 5){
    cerr << "Usage: " << argv[0]
	 << " height width padding verbosity" << endl;
    return 1;
  }
  // and translate them from strings to integers:
  height = atoi(argv[1]);
  width = atoi(argv[2]);
  padding = atoi(argv[3]);
  verbosity = atoi(argv[4]);

  // Allocate the memory:
  isLivePtr = new char[(height+2)*(width+2+padding)];
  neighborsPtr = new char[(height+2)*(width+2+padding)];
  if(!isLivePtr || !neighborsPtr){
    cerr << "Wasn't able to allocate the required memory." << endl;
    return 1;
  }

  // Fill in the boundaries of permanently dead cells:
  for(int col = 0; col <= width+1; col++){
    isLive(0, col) = 0;
    isLive(height+1, col) = 0;
  }
  for(int row = 0; row <= height+1; row++){
    isLive(row, 0) = 0;
    isLive(row, width+1) = 0;
  }

  // Then fill in the main body pseudo-randomly:
  for(int col = 1; col <= width; col++){
    for(int row = 1; row <= height; row++){
      isLive(row, col) = random()%sparseness == 0;
    }
  }

  // Do the generations of birth and death,
  //  while timing how many clock cycles it takes.
  cycles start = read_cyccounter();
  for(int i = 0; i < generations; i++){
    for(int col = 1; col <= width; col++){
      for(int row = 1; row <= height; row++){
	neighbors(row, col) =
	  isLive(row-1,col-1) + isLive(row-1,col) + isLive(row-1,col+1) +
   	  isLive(row,  col-1)           +           isLive(row,  col+1) +
	  isLive(row+1,col-1) + isLive(row+1,col) + isLive(row+1,col+1);
      }
    }
    for(int col = 1; col <= width; col++){
      for(int row = 1; row <= height; row++){
	isLive(row,col) =
	  neighbors(row,col) == 3 ||  // 3 neighbors: birth or survival
	  neighbors(row,col) == 2 && isLive(row,col); // two neighbors: survival
      }
    }
  }
  cycles end = read_cyccounter();

  // Now find the answer: how many cells live at end:
  int living = 0;
  for(int col = 1; col <= width; col++){
    for(int row = 1; row <= height; row++){
      living += isLive(row,col);
    }
  }

  // Finally, print out a summary:
  if(verbosity){
    cout << "Basic grid had height " << height
	 << " and width " << width << "." << endl;
    cout << "With left and right boundaries and " << padding
	 << " bytes of padding, each row was "
	 << width+2+padding << " bytes." << endl;
    cout << "With top and bottom boundaries, each array had "
	 << height+2 << " rows." << endl;
    cout << "So each of the two arrays was allocated "
	 << (height+2)*(width+2+padding) << " bytes." << endl;
    cout << "After " << generations << " generations, "
         << living << " cells were alive at the end." << endl;
    cout << "The simulation of the generations took " << end - start
	 << " clock cycles." << endl;
    cout << "That averages out to about "
	 << (end-start)/(height*width*generations) << " cycles per cell generation."
	 << endl << endl;
  } else {
    cout << height << "," << width << "," << padding
         << "," << living << "," << end-start << endl;
  }

  return 0;
}