This is my implementation of Conway's Game of Life.
I'm currently trying to implement repetition detection, which allows the program to detect repetitions with periods up to 4 generations long. For this purpose, I use a list called statelist that is intended to store a trail of 4 states behind the current state (the states are represented as a string created by the function serialize_board()). To push a new state onto the statelist(and possibly discard the last state in the trail), I have implemented the push_list() function. But in the push_list() function, there is an error:
2017-07-18 13:26:32.496180+0100 Assignment 3[38082:4064098] detected source and destination buffer overlap
The desired functionality of push_list is described in a comment by the function initialization. I don't understand how the strings can overlap. I have allocated enough memory for the statelist and nrows*ncols+1 bytes of memory for each string, which is the size of each state string. Sorry for the lengthy program but it's hard to make it shorter when so many functions depend on each other.
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <time.h>
#define MAX_COORDINATE_SIZE 50
#define MAX_FILENAME_SIZE 20
#define MAX_GENERATIONS 10
#define MAX_REPETITION_PERIOD 4
struct coord{ //Holds coordinates to a cell
int x;
int y;
};
struct cell{
int pop; //Populated
// char pos; //C: corner, T: top, R: right, B: bottom, L: left
int age;
};
struct coord *read_init(FILE *fp, int *i);
static int read_line(FILE *fp, char *line, int max_length);
struct coord read_coords(char *line);
struct cell **create_board(int x, int y);
void populate_board(struct coord *coords, struct cell ***board, int *n);
struct cell new_cell(int x, int y, int pop, int age);
struct cell **start_game(FILE *fp, int nrows, int ncols);
void print_board(struct cell **board, int nrows, int ncols);
void init_board(int nrows, int ncols, struct cell ***board);
int live(int i, int j, struct cell **board, int nrows, int ncols);
void step(struct cell ***board, int nrows, int ncols);
void push_list(char **list, int len, char *state);
int repetitive(char **list, int len);
char *serialize_board(struct cell **board, int nrows, int ncols);
int main(int argc, const char * argv[]) {
int gens;
char gens_string[MAX_GENERATIONS];
if(argc != 3){
fprintf(stderr, "Usage: %s <seed-file> <generations>\n<seed-file> can me up to %d characters long\n", argv[0], MAX_FILENAME_SIZE);
exit(1);
}
FILE *fp = fopen(argv[1], "r");
strncat(gens_string, argv[2], MAX_GENERATIONS);
gens = atoi(gens_string);
int nrows = 10;
int ncols = 10;
int repetitions;
//allocate memory and set up pointers for statelist
char **statelist;
statelist = malloc((MAX_REPETITION_PERIOD+1) * sizeof(char *) + (MAX_REPETITION_PERIOD+1+1) * nrows * ncols); //MAXREP+1 is the number of strings we want to store. The other +1 is to fit in the null temrinator
char *firstrow = statelist + MAX_REPETITION_PERIOD+1;
for(int i = 0; i < MAX_REPETITION_PERIOD+1; i++){
statelist[i] = firstrow + i * nrows * ncols;
}
struct cell **board= start_game(fp, nrows, ncols);
print_board(board, nrows, ncols);
push_list(statelist, MAX_REPETITION_PERIOD+1, serialize_board(board, nrows, ncols));
struct timespec t;
t.tv_sec = 0;
t.tv_nsec = 500000000L;
for(int i = 0; i < gens; i++){
step(&board, nrows, ncols);
nanosleep(&t, NULL);
print_board(board, nrows, ncols);
push_list(statelist, MAX_REPETITION_PERIOD+1, serialize_board(board, nrows, ncols));
if((repetitions = repetitive(statelist, MAX_REPETITION_PERIOD+1))){
printf("Repetition detected (%d)\n", repetitions);
exit(1);
}
}
return 0;
}
struct coord *read_init(FILE *fp, int *n){ //Takes in filename and returns list of coordinates to be populated
char raw_n[100];
struct coord *coords;
char *line;
line = malloc(sizeof(char)*MAX_COORDINATE_SIZE);
read_line(fp, raw_n, 100); // get the first line of the file (number of popuated cells)
*n = atoi(raw_n);//make an int out of raw_n
coords = malloc(sizeof(struct coord)*(*n)); //Allocate memory for each coord
for(int i = 0; i<(*n); i++){ // for each line in the file (each populated cell)
read_line(fp, line, MAX_COORDINATE_SIZE);
coords[i] = read_coords(line); //Put coordinates in coords
line[0] = '\0';
}
return coords; // return coordinates
}
static int read_line ( FILE *fp, char *line, int max_length)
{
int i;
char ch;
/* initialize index to string character */
i = 0;
/* read to end of line, filling in characters in string up to its
maximum length, and ignoring the rest, if any */
for(;;)
{
/* read next character */
ch = fgetc(fp);
/* check for end of file error */
if ( ch == EOF )
return -1;
/* check for end of line */
if ( ch == '\n' )
{
/* terminate string and return */
line[i] = '\0';
return 0;
}
/* fill character in string if it is not already full*/
if ( i < max_length )
line[i++] = ch;
}
/* the program should never reach here */
return -1;
}
struct coord read_coords(char *line){ // Returns coordinates read from char *line
struct coord c;
char *x;
char *y;
x = malloc(sizeof(char)*MAX_COORDINATE_SIZE);
y = malloc(sizeof(char)*MAX_COORDINATE_SIZE);
int i = 0;
do{
x[i] = line[i]; //Get the x coordinate
i++;
}while(line[i] != ' ');
i++;
do{
y[i-2] = line[i];
i++;
}while(line[i] != '\0');
c.x = atoi(x)-1;
c.y = atoi(y)-1;
return c;
}
void init_board(int nrows, int ncols, struct cell ***board){
*board = malloc(nrows * sizeof(*board) + nrows * ncols * sizeof(**board));
//Now set the address of each row or whatever stackoverflow says
struct cell * const firstrow = *board + nrows;
for(int i = 0; i < nrows; i++)
{
(*board)[i] = firstrow + i * ncols;
}
for(int i = 0; i < nrows; i++){ //fill the entire board with pieces
for(int j = 0; j < ncols; j++){
(*board)[i][j] = new_cell(i, j, 0, 0);
}
}
}
struct cell new_cell(int x, int y, int pop, int age){ //Return new populated or non-populated cell with specified coordinates
struct cell c;
c.pop = pop;
c.age = age;
return c;
}
struct cell **start_game(FILE *fp, int nrows, int ncols){ //x,y are no of rows/columns, fn is filename
int n; // n is the number of populated cells specified in the seed
struct coord *coords = read_init(fp, &n); // get the list of coords to populate board with
struct cell **board;
init_board(nrows, ncols, &board); // Set up the board
populate_board(coords, &board, &n); //populate the cells specified in the seed
return board;
}
void populate_board(struct coord *coords, struct cell ***board, int *n){
for(int i = 0; i < *n; i++){
(*board)[coords[i].x][coords[i].y].pop = 1; //populate the cell
}
}
void print_board(struct cell **board, int nrows, int ncols){
printf("--------------------\n");
for(int i = 0; i<nrows; i++){
for(int j = 0; j<ncols; j++){
if(board[i][j].pop == 1){
printf("%d ", board[i][j].age);
}else if(board[i][j].pop == 0){
printf(" ");
}else{
printf("\n\nERROR!");
exit(0);
}
}
printf("\n");
}
printf("--------------------");
printf("\n");
}
int live(int i, int j, struct cell **board, int nrows, int ncols){ //returns 1 if cell will live, 0 if cell will die,
int status = board[i][j].pop; // status = 1 if alive, 0 if dead
int n=0; //neighbours
//Counting all the neighbours
if(i == 0 && j == 0){ //if top left cornerpiece
if(board[i][j+1].pop) { n++; } // east
if(board[i+1][j+1].pop){ n++; } // southeast
if(board[i+1][j].pop) { n++; } // south
}
else if(i == 0 && j==ncols-1){ //if top right cornerpiece
if(board[i+1][j].pop) { n++; } // south
if(board[i+1][j-1].pop){ n++; } // southwest
if(board[i][j-1].pop) { n++; } // west
}
else if(i == nrows-1 && j == ncols-1){ //if bottom right cornerpiece
if(board[i][j-1].pop) { n++; } // west
if(board[i-1][j-1].pop){ n++; } // northwest
if(board[i-1][j].pop) { n++; } // north
}
else if(i == nrows-1 && j == 0){ //if bottom left cornerpiece
if(board[i-1][j].pop) { n++; } // north
if(board[i-1][j+1].pop){ n++; } // northeast
if(board[i][j+1].pop) { n++; } // east
}
else if(i == 0){ // middle top piece (not in a corner)
if(board[i][j+1].pop) { n++; } // east
if(board[i+1][j+1].pop){ n++; } // southeast
if(board[i+1][j].pop) { n++; } // south
if(board[i+1][j-1].pop){ n++; } // southwest
if(board[i][j-1].pop) { n++; } // west
}
else if(j == ncols-1){ // middle right side piece
if(board[i+1][j].pop) { n++; } // south
if(board[i+1][j-1].pop){ n++; } // southwest
if(board[i][j-1].pop) { n++; } // west
if(board[i-1][j-1].pop){ n++; } // northwest
if(board[i-1][j].pop) { n++; } // north
}
else if(i == nrows-1){ // middle bottom piece
if(board[i][j-1].pop) { n++; } // west
if(board[i-1][j-1].pop){ n++; } // northwest
if(board[i-1][j].pop) { n++; } // north
if(board[i-1][j+1].pop){ n++; } // northeast
if(board[i][j+1].pop) { n++; } // east
}
else{
if(board[i-1][j].pop) { n++; } // north
if(board[i-1][j+1].pop){ n++; } // northeast
if(board[i][j+1].pop) { n++; } // east
if(board[i+1][j+1].pop){ n++; } // southeast
if(board[i+1][j].pop) { n++; } // south
if(board[i+1][j-1].pop){ n++; } // southwest
if(board[i][j-1].pop) { n++; } // west
if(board[i-1][j-1].pop){ n++; } // northwest
}
if(status){
if(n < 2) { return 0; }
if(n >= 2 && n <= 3){ return 1; }
if(n > 3) { return 0; }
}
if(!status){
if(n == 3) { return 1; }
return 0;
}
//We should never reach here
return -1;
}
void step(struct cell ***board, int nrows, int ncols){ // returns array of strings that contain all of the 5 latest states
struct cell **nextgenboard;
nextgenboard = malloc(nrows*(sizeof(nextgenboard)) + nrows * ncols * sizeof(**nextgenboard));
struct cell * const firstrow = nextgenboard + nrows;
for(int i = 0; i < nrows; i++){
nextgenboard[i] = firstrow + i*ncols;
}
for(int i = 0; i < nrows; i++){
for(int j = 0; j < ncols; j++){
}
}
for(int r = 0; r < nrows; r++){
for(int c = 0; c < ncols; c++){
nextgenboard[r][c].pop = live(r, c, *board, nrows, ncols);
if((*board)[r][c].pop == 0){
nextgenboard[r][c].age = 0;
}else if((*board)[r][c].pop == 1){
nextgenboard[r][c].age = (*board)[r][c].age + 1;
}
//nextgenboard[r][c].age = 0;
}
}
free(*board);
*board = nextgenboard;
}
void push_list(char **list, int len, char *state){ //takes an array of strings, the length of it and a new string. Pushes the other strings down and puts the new string in the first place. The last one gets destroyed.
//move all the other elements down.
for(int i = len-1; i > 0; i--){
strcpy(list[i], list[i-1]); <---- HERE IS THE ERROR
}
//put the new element first
strcpy(list[0], state);
}
int repetitive(char **statelist, int len){ // takes the statelist and checks if the first element reoccurs. Returns 0 for no repetition, and the period otherwise.
for(int i = 1; i < len; i++){
if(strcmp(statelist[0], statelist[i]) == 0){
return i;
}
}
return 0;
}
char *serialize_board(struct cell **board, int nrows, int ncols){
char *str;
str = malloc(sizeof(char)*nrows*ncols);
int z = 0;
printf("\n");
for(int i = 0; i < nrows; i++){
for(int j = 0; j < ncols; j++){
str[z] = board[i][j].pop+48;
z++;
}
}
printf("\n");
return str;
}
EDIT1: Added a comment where the error is generated. My question is: Why does this happen and what can I do about it?
EDIT2:
In his answer, @Neil says my code is effectively doing this:
char str[10];
strcpy(&str[1], &str[0]);
In an effort to create an example that better models my program (such as str being a char ** rather than a char *), I wrote this:
int main(){
char **str;
str = malloc(sizeof(char *)*3 + sizeof(char)*3*10);
char * firststring = str+3;
for(int i = 0; i < 10; i++){
str[i] = firststring + i*10;
}
strcpy(str[0], "123456789");
strcpy(str[1], "000000000");
printf("%s\n", str[0]);
printf("%s\n", str[1]);
strcpy(str[1], str[0]);
printf("%s\n", str[0]);
printf("%s\n", str[1]);
}
Here, I'm using strcpy to copy one array element (containing a pointer to a char) to another. This works fine. So why doesn't my code work? I want it to do the same thing in principle as this mini example.
EDIT3:
So a few changes made my program finally do what I want it to.
main().statelist with '\0'.\0 (although the program did execute properly with just the two above)1.:
char **statelist;
statelist = malloc((MAX_REPETITION_PERIOD+1) * sizeof(char *) + (MAX_REPETITION_PERIOD+1) * (nrows * ncols + 1) * sizeof(char));
char *firstrow = statelist + MAX_REPETITION_PERIOD+1;
for(int i = 0; i < (MAX_REPETITION_PERIOD+1); i++){
statelist[i] = firstrow + i * (nrows * ncols + 1);
*statelist[i] = '\0';
}
2.:
char *serialize_board(struct cell **board, int nrows, int ncols){
char *str;
str = malloc(sizeof(char)*nrows*ncols);
int z = 0;
printf("\n");
for(int i = 0; i < nrows; i++){
for(int j = 0; j < ncols; j++){
str[z] = board[i][j].pop+48;
z++;
}
}
str[z] = '\0'; <---- HERE
return str;
}
3.:
See 1.
First of all, statelist contains a bunch of pointers into uninitialized memory. When you try to strcpy from one of these pointers, this causes undefined behavior.
But even if you initialize the memory to zeroes, what you are doing is fundamentally incorrect. You use the strcpy function and other str* functions, but those functions are only intended for zero-terminated strings. The memory returned by serialize_board which you are attempting to strcpy is just a a bunch of chars that is not zero-terminated. So again you have undefined behavior.
You can use the memcpy function instead to copy these chunks of memory since you know the size of memory to copy. You will also need to use memcpy instead of strcmp.
You also have some serious memory leaks here (e.g. the memory allocated by serialize_board is not freed).