Conway's Game of Life Buffer Underflow

Question

I'm pretty new to C and I've heard of Buffer Overflow before but I've never heard of a stack buffer underflow. I've been trying to read up on it and from what I understand, I'm allocating too much memory? I just want to be sure I understand the issue properly. So my question is related to the following code which takes an a number of generations to update the given file for Conway's Game of Life. If anyone can explain where I'm misunderstanding something, I'd be very grateful. The input should be along the lines of "./life.c # board.txt" where # is the number of generations and board.txt is the board constructed of "."'s and "*"'s. The first line of board.txt also holds the number of rows and columns. The odd thing is that the code works sometimes for smaller board but creates a buffer underflow for bigger boards.

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <ctype.h>

void futureGens(int numRows, int numCols, int original[numRows][numCols], int generations){
    int future[numRows][numCols];
    int i, j;

    for(i = 0; i < numRows; i++){
        for(j = 0; j < numCols; j++){
            int live = 0;

            if(original[i-1][j-1] == 1){
                live++;
            }
            if(original[i-1][j] == 1){
                live++;
            }
            if(original[i-1][j+1] == 1){
                live++;
            }
            if(original[i][j-1] == 1){
                live++;
            }
            if(original[i][j] == 1){
                live++;
            }
            if(original[i][j+1] == 1){
                live++;
            }
            if(original[i+1][j-1] == 1){
                live++;
            }   
            if(original[i+1][j] == 1){
                live++;
            }
            if(original[i+1][j+1] == 1){
                live++;
            }

            live -= original[i][j];

            switch(live){
                case 0:
                case 1: 
                    future[i][j] = 0;
                    break;
                case 2:
                    future[i][j] = original[i][j];
                    break;
                case 3:
                    future[i][j] = 1;
                    break;
                default:
                    future[i][j] = 0;
            }   
        }
    }

    if(generations == 1){           
        //printf("\nFuture: \n");
        for(i = 0; i < numRows; i++){
            for(j = 0; j < numCols; j++){
                if(future[i][j] == 1){
                    printf("*");
                } else {
                    printf(".");
                } 

                //printf("%d", future[i][j]);
            }
            printf("\n");
        }
    }   
     else {
        futureGens(numRows, numCols, future, generations-1);
    } 
}

int main(int argc, char **argv){
    if(argc != 3) {
        return EXIT_FAILURE;
    }

    int generations = atoi(argv[1]);

    FILE *fp = fopen(argv[2], "r");
    if(fp == NULL){
        printf("error: nothing in file\n");
        return EXIT_FAILURE;
    }

    int numRows = 0, numCols = 0;
    char line[256];

    if(fgets(line, sizeof(line), fp)){
        char c[256];
        int p;

        for(p = 0; p < 256; p++){
            if(isdigit(line[p]) != 0){
                c[p] = line[p];
            } else {
                break;
            }

        }

        numRows = atoi(c);
        numCols = atoi(c);
        printf("row: %d, col: %d\n", numRows, numCols);
    }

    //initialize the original array
    int original[numRows][numCols];
    int i, j;

    for(i = 0; i < numRows; i++){
        fgets(line, sizeof(line), fp);
        for(j = 0; j < numCols; j++){
            char c = line[j];
            if(c == '.'){
                original[i][j] = 0;
            } else if(c == '*'){
                original[i][j] = 1;
            }
        }   
    }

    futureGens(numRows, numCols, original, generations);

    return EXIT_SUCCESS;
}

Answer 1

When i or j is zero, then original[i-1][j-1] attempts to access an element outside of the array original.

The C standard does not define the resulting behavior. In many C implementations, this will often attempt to access memory outside the array. The bigger the array rows are (the more columns there are), the further outside the array original[i-1] will be, and the more likely it is to attempt to access memory that is not mapped, which will cause a fault.

You must write code that does not access elements outside of an array.

In the case of algorithms that must examine the neighbors of elements of an array, there are common approaches to this:

• As each element is considered, use if statements to test whether it has neighbors inside the array. For any directions in which neighbors do not exist, do not attempt to examine elements there. This code results in testing the array boundaries repeatedly, for each element.
• Separate the processing of the array into a main loop (or set of nested loops, one for each dimension) for the interior elements, all of which have neighbors in all directions and separate loops for the edges of the array (such as the “left” edge, where i is zero, and the elements do not have neighbors on the left. Then no separate testing for each element is needed; each loop handles cases where the neighbors for elements processed in that loop are known. The corners must also be handled separately.
• Pad the array with dummy rows and columns at the edges that contain neutral information. Thus, for a desired array size of R rows and C columns, an actual array size of R+2 rows and C+2 columns would be used. The loop to process elements would iterate through rows 1 to R-2 and through columns 1 to C-2.