cconways-game-of-lifestackunderflow

Conway's Game of Life Buffer Underflow


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;
}

Solution

  • 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: