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