title: strcpy: detected source and destination buffer overlap
body: <p>This is my implementation of Conway's Game of Life. </p>
  
  <p>I'm currently trying to implement <em>repetition detection</em>, which allows the program to detect repetitions with periods up to 4 generations long. For this purpose, I use a list called <code>statelist</code> 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 <code>serialize_board()</code>). To push a new state onto the <code>statelist</code>(and possibly discard the last state in the trail), I have implemented the <code>push_list()</code> function. But in the <code>push_list()</code> function, there is an error: </p>
  
  <pre><code>2017-07-18 13:26:32.496180+0100 Assignment 3[38082:4064098] detected source and destination buffer overlap
  </code></pre>
  
  <p>The desired functionality of <code>push_list</code> 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 <code>statelist</code> and <code>nrows*ncols+1</code> 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.</p>
  
  <pre><code>#include &lt;stdio.h&gt;
  #include &lt;string.h&gt;
  #include &lt;stdlib.h&gt;
  #include &lt;time.h&gt;
  
  #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 &lt;seed-file&gt; &lt;generations&gt;\n&lt;seed-file&gt; 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 &lt; 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 &lt; gens; i++){
          step(&amp;board, nrows, ncols);
          nanosleep(&amp;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&lt;(*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 &lt; 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 &lt; nrows; i++)
      {
          (*board)[i] = firstrow + i * ncols;
      }
  
      for(int i = 0; i &lt; nrows; i++){ //fill the entire board with pieces
          for(int j = 0; j &lt; 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, &amp;n); // get the list of coords to populate board with
      struct cell **board;
  
      init_board(nrows, ncols, &amp;board); // Set up the board
  
      populate_board(coords, &amp;board, &amp;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 &lt; *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&lt;nrows; i++){
          for(int j = 0; j&lt;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 &amp;&amp; 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 &amp;&amp; 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 &amp;&amp; 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 &amp;&amp; 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 &lt; 2)           { return 0; }
          if(n &gt;= 2 &amp;&amp; n &lt;= 3){ return 1; }
          if(n &gt; 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 &lt; nrows; i++){
          nextgenboard[i] = firstrow + i*ncols;
      }
  
      for(int i = 0; i &lt; nrows; i++){
          for(int j = 0; j &lt; ncols; j++){
  
          }
      }
      for(int r = 0; r &lt; nrows; r++){
  
          for(int c = 0; c &lt; 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 &gt; 0; i--){
          strcpy(list[i], list[i-1]); &lt;---- 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 &lt; 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 &lt; nrows; i++){
          for(int j = 0; j &lt; ncols; j++){
              str[z] = board[i][j].pop+48;
              z++;
          }
      }
      printf("\n");
      return str;
  }
  </code></pre>
  
  <p>EDIT1: Added a comment where the error is generated. My question is: Why does this happen and what can I do about it?</p>
  
  <p>EDIT2:</p>
  
  <p>In his answer, @Neil says my code is effectively doing this:</p>
  
  <pre><code>char str[10];
  strcpy(&amp;str[1], &amp;str[0]);
  </code></pre>
  
  <p>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:</p>
  
  <pre><code>int main(){
      char **str;
      str = malloc(sizeof(char *)*3 + sizeof(char)*3*10);
      char * firststring = str+3;
  
      for(int i = 0; i &lt; 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]);
  }
  </code></pre>
  
  <p>Here, I'm using <code>strcpy</code> 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.</p>
  
  <p>EDIT3:</p>
  
  <p>So a few changes made my program finally do what I want it to.</p>
  
  <ol>
  <li>Fix faulty allocation of memory in <code>main()</code>.</li>
  <li>Terminate each string in <code>statelist</code> with <code>'\0'</code>.</li>
  <li>Initialize statelist to <code>\0</code> (although the program did execute properly with just the two above)</li>
  </ol>
  
  <p>1.:</p>
  
  <pre><code>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 &lt; (MAX_REPETITION_PERIOD+1); i++){
      statelist[i] = firstrow + i * (nrows * ncols + 1);
      *statelist[i] = '\0';
  }
  </code></pre>
  
  <p>2.:</p>
  
  <pre><code>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 &lt; nrows; i++){
          for(int j = 0; j &lt; ncols; j++){
              str[z] = board[i][j].pop+48;
              z++;
          }
      }
      str[z] = '\0'; &lt;---- HERE
      return str;
  }
  </code></pre>
  
  <p>3.:</p>
  
  <p>See 1.</p>