Stack overflow errors in 3 areas

This is a discussion on Stack overflow errors in 3 areas within the C Programming forums, part of the General Programming Boards category; This function reads a terrain map which is just a grayscale bitmap of 131,072 by 1 pixel which contains height ...

  1. #1
    Math wizard
    Join Date
    Dec 2006
    Location
    USA
    Posts
    582

    Stack overflow errors in 3 areas

    This function reads a terrain map which is just a grayscale bitmap of 131,072 by 1 pixel which contains height data. The height data and stuff run without problems, but I'm getting this strange "stack overflow" error when I expanded this function to draw a monochrome bitmap that lets me get a look at what the lay of the land actually looks like in a simple 2D side view instead of looking at shades of gray representing slope angles.

    Code:
    void CheckTerrainHeights()
    {
    	unsigned char TerrainData[131072];
    	unsigned int ArrayIndex = 0;
    	int CurrentHeight = 0; // you start here
    	int MaxHeightPx = 0;
    	double MaxHeightFt = 0.0;
    	unsigned int MaxHeightLocation = 0;
    	int MinHeightPx = 0;
    	double MinHeightFt = 0.0;
    	unsigned int MinHeightLocation = 0;
    	int Errors = 0;
    	unsigned int ImageArrayIndex = 0;
    	double ImageTargetHeight = 0.0;
    	double ImageTerrainHeight = 0.0;
    	unsigned int BitPos = 0;
    	unsigned int ByteBlock = 0;
    	unsigned int ImageBaseArrayIndex = 0;
    	unsigned char TerrainPreviewData[2097152];
    	unsigned char Colors[8] = {0, 0, 0, 0, 255, 255, 255, 0};
    	BITMAPFILEHEADER TempFileHead;
    	BITMAPINFOHEADER TempInfoHead;
    	
    	FileHandle = fopen("C:\\My Documents\\My programs\\Terrain height test.bmp", "rb"); // first, read the data
    	fseek(FileHandle, 1078, SEEK_SET); // skip the header straight to the main data
    	fread(&TerrainData, 1, 131072, FileHandle);
    	fclose(FileHandle);
    	
    	TempFileHead.bfType = 19778; // fills out the structures // 19778 supposedly is "BM"
    	TempFileHead.bfSize = 2097214; // array length plus off bits (or 62)
    	TempFileHead.bfReserved1 = 0;
    	TempFileHead.bfReserved2 = 0;
    	TempFileHead.bfOffBits = 62;
    	
    	TempInfoHead.biSize = 40;
    	TempInfoHead.biWidth = 131072;
    	TempInfoHead.biHeight = 128;
    	TempInfoHead.biPlanes = 1;
    	TempInfoHead.biBitCount = 1; // monochrome bitmap
    	TempInfoHead.biCompression = BI_RGB; // no compression
    	TempInfoHead.biSizeImage = 2097152; // the array size
    	TempInfoHead.biXPelsPerMeter = 2835;
    	TempInfoHead.biYPelsPerMeter = 2835;
    	TempInfoHead.biClrUsed = 2; // black and white only
    	TempInfoHead.biClrImportant = 2; // both possible are important
    	
    	FileHandle = fopen("C:\\My Documents\\My programs\\Terrain height test heights.bmp", "wb"); // prepare to write a BMP file
    	fwrite(&TempFileHead.bfType, 2, 1, FileHandle);
    	fwrite(&TempFileHead.bfSize, 4, 1, FileHandle);
    	fwrite(&TempFileHead.bfReserved1, 2, 1, FileHandle);
    	fwrite(&TempFileHead.bfReserved2, 2, 1, FileHandle);
    	fwrite(&TempFileHead.bfOffBits, 4, 1, FileHandle);
    	fwrite(&TempInfoHead.biSize, 4, 1, FileHandle);
    	fwrite(&TempInfoHead.biWidth, 4, 1, FileHandle);
    	fwrite(&TempInfoHead.biHeight, 4, 1, FileHandle);
    	fwrite(&TempInfoHead.biPlanes, 2, 1, FileHandle);
    	fwrite(&TempInfoHead.biBitCount, 2, 1, FileHandle);
    	fwrite(&TempInfoHead.biCompression, 4, 1, FileHandle);
    	fwrite(&TempInfoHead.biSizeImage, 4, 1, FileHandle);
    	fwrite(&TempInfoHead.biXPelsPerMeter, 4, 1, FileHandle);
    	fwrite(&TempInfoHead.biYPelsPerMeter, 4, 1, FileHandle);
    	fwrite(&TempInfoHead.biClrUsed, 4, 1, FileHandle);
    	fwrite(&TempInfoHead.biClrImportant, 4, 1, FileHandle);
    	fwrite(&Colors, 1, 8, FileHandle); // the colors black then white
    	
    	while ((ArrayIndex < 131072) && (TerrainData[ArrayIndex] != 4)) // loop until the end or unfinished areas are reached
    	{
    		if (TerrainData[ArrayIndex] == 135) { CurrentHeight -= 340; } // steepest downward slope
    		else if (TerrainData[ArrayIndex] == 151) { CurrentHeight -= 224; }
    		else if (TerrainData[ArrayIndex] == 167) { CurrentHeight -= 165; }
    		else if (TerrainData[ArrayIndex] == 183) { CurrentHeight -= 129; }
    		else if (TerrainData[ArrayIndex] == 199) { CurrentHeight -= 104; }
    		else if (TerrainData[ArrayIndex] == 215) { CurrentHeight -= 86; }
    		else if (TerrainData[ArrayIndex] == 231) { CurrentHeight -= 72; }
    		else if (TerrainData[ArrayIndex] == 247) { CurrentHeight -= 60; }
    		else if (TerrainData[ArrayIndex] == 0) { CurrentHeight -= 50; }
    		else if (TerrainData[ArrayIndex] == 16) { CurrentHeight -= 42; }
    		else if (TerrainData[ArrayIndex] == 32) { CurrentHeight -= 35; }
    		else if (TerrainData[ArrayIndex] == 48) { CurrentHeight -= 28; }
    		else if (TerrainData[ArrayIndex] == 64) { CurrentHeight -= 22; }
    		else if (TerrainData[ArrayIndex] == 80) { CurrentHeight -= 16; }
    		else if (TerrainData[ArrayIndex] == 96) { CurrentHeight -= 11; }
    		else if (TerrainData[ArrayIndex] == 112) { CurrentHeight -= 5; }
    		else if (TerrainData[ArrayIndex] == 128) { CurrentHeight += 0; }
    		else if (TerrainData[ArrayIndex] == 143) { CurrentHeight += 5; }
    		else if (TerrainData[ArrayIndex] == 159) { CurrentHeight += 11; }
    		else if (TerrainData[ArrayIndex] == 175) { CurrentHeight += 16; }
    		else if (TerrainData[ArrayIndex] == 191) { CurrentHeight += 22; }
    		else if (TerrainData[ArrayIndex] == 207) { CurrentHeight += 28; }
    		else if (TerrainData[ArrayIndex] == 223) { CurrentHeight += 35; }
    		else if (TerrainData[ArrayIndex] == 239) { CurrentHeight += 42; }
    		else if (TerrainData[ArrayIndex] == 255) { CurrentHeight += 50; }
    		else if (TerrainData[ArrayIndex] == 8) { CurrentHeight += 60; }
    		else if (TerrainData[ArrayIndex] == 24) { CurrentHeight += 72; }
    		else if (TerrainData[ArrayIndex] == 40) { CurrentHeight += 86; }
    		else if (TerrainData[ArrayIndex] == 56) { CurrentHeight += 104; }
    		else if (TerrainData[ArrayIndex] == 72) { CurrentHeight += 129; }
    		else if (TerrainData[ArrayIndex] == 88) { CurrentHeight += 165; }
    		else if (TerrainData[ArrayIndex] == 104) { CurrentHeight += 224; }
    		else if (TerrainData[ArrayIndex] == 120) { CurrentHeight += 340; } // steepest upward slope
    		else { Errors++; printf("Invalid color at location %d\n", ArrayIndex); } // error occurred!
    		
    		if (CurrentHeight > MaxHeightPx) { MaxHeightPx = CurrentHeight; MaxHeightLocation = ArrayIndex;} // logs minimums and maximums
    		if (CurrentHeight < MinHeightPx) { MinHeightPx = CurrentHeight; MinHeightLocation = ArrayIndex;}
    		
    		ImageTerrainHeight = CurrentHeight/60.0+0.5;
    		BitPos = (unsigned int)(ImageTerrainHeight+16.0) % 8; // find bit position to write to - order is 128, 64, 32, 16, 8, 4, 2, then 1
    		ByteBlock = 0;
    		
    		ImageArrayIndex = 0;
    		
    		while (ByteBlock < 16) // 16 bytes, 128 pixels // each byte block is 26.4 feet // this loop causes stack overflow
    		{
    			ImageTargetHeight = ((double)ByteBlock-1.0)*26.4;
    			ImageBaseArrayIndex = ArrayIndex*16+ByteBlock;
    			
    			if (ImageTerrainHeight < ImageTargetHeight) // if below, it should be all black // causes stack overflow
    			{
    				TerrainPreviewData[ImageBaseArrayIndex] = 0; // all 8 pixels are black
    			}
    			
    			else if (ImageTerrainHeight > ImageTargetHeight+26.4) // if above the next step, it should be all white // causes stack overflow
    			{
    				TerrainPreviewData[ImageBaseArrayIndex] = 255; // all 8 pixels are white
    			}
    			
    			else
    			{
    				if (BitPos == 0) { TerrainPreviewData[ImageBaseArrayIndex] = 0; } // more white added for higher BitPos values
    				else if (BitPos == 1) { TerrainPreviewData[ImageBaseArrayIndex] = 1; }
    				else if (BitPos == 2) { TerrainPreviewData[ImageBaseArrayIndex] = 3; }
    				else if (BitPos == 3) { TerrainPreviewData[ImageBaseArrayIndex] = 7; }
    				else if (BitPos == 4) { TerrainPreviewData[ImageBaseArrayIndex] = 15; }
    				else if (BitPos == 5) { TerrainPreviewData[ImageBaseArrayIndex] = 31; }
    				else if (BitPos == 6) { TerrainPreviewData[ImageBaseArrayIndex] = 63; }
    				else if (BitPos == 7) { TerrainPreviewData[ImageBaseArrayIndex] = 127; }
    			}
    			
    			ByteBlock++;
    		}
    		
    		ArrayIndex++;
    	}
    	
    	while (ImageBaseArrayIndex < 2097152) // to fill the rest of the image as something odd to indicate incomplete areas
    	{
    		TerrainPreviewData[ImageBaseArrayIndex] = 5;
    		ImageBaseArrayIndex++;
    	}
    	
    	MaxHeightFt = (double)MaxHeightPx*0.055;
    	MinHeightFt = (double)MinHeightPx*0.055;
    	
    	// fwrite(&TerrainPreviewData, 1, 2097152, FileHandle); // writes the entire output image data // causes stack overflow
    	fclose(FileHandle);
    	
    	// prints textual results with a printf statement
    }
    When the function gets to the first and second if statements in the "while (ByteBlock < 16)" part, I get an unhandled exception notice saying of stack overflow. I don't know about the else though. The other two instructions work just fine and there's no infinite loop encountered. The other while loop where I fill the rest of the array's values to 5, near the bottom, works just fine, but when I try writing this data, I get that stack overflow case again and it's not writing any of the image data. It's writing the file head and info head just fine and I can see it in my hex editor as I expected.

    What is a "stack overflow" error? What is a "stack"? How can I fix this problem? I've had much bigger write amounts (250 MB) done numerous times and not once did I get a problem. I'm getting it with just 2 MB. This is only intended to run on my computer so compatibility with other computers is not necessary. The program has windows.h included at the top and everything in this function uses local variables. I spent some time to find the areas causing the problem and it's only these 3 areas. With the if's and else's used in the "ByteBlock < 16" loop commented out along with the write of 2 MB, the function runs just fine without any problems and behaves as intended for what isn't commented out.

  2. #2
    Woof, woof! zacs7's Avatar
    Join Date
    Mar 2007
    Location
    Australia
    Posts
    3,459
    Your going past memory that belongs to you, (your trying to read/write someone elses memory). Ie If you have an array allocated on the stack that is 5 bytes long, your probably trying to access the 6th byte or something like that.


    Id say in the last loop that 'ImageBaseArrayIndex' points to an element out-of-bounds in 'TerrainPreviewData'.
    Last edited by zacs7; 04-28-2007 at 06:31 PM.

  3. #3
    Math wizard
    Join Date
    Dec 2006
    Location
    USA
    Posts
    582
    That doesn't seem to be the case. The while loop works just fine, but if I try to write the contents, which writes to disk, I get this error. The first, long loop only goes out to 3500 for the ArrayIndex as that's how far I've gone in my terrain. This puts ImageBaseArrayIndex below even 60,000. The array with the data in it has 2 million values possible so array overflow is not the problem.

    I tried setting the write amount to just 2000 and I still get the stack overflow. The array's length is 2097152 (which is 2^21), so I can almost certainly rule out array overflow. Array overflow would cause "error writing to memory at location xxx" instead of just "stack overflow". Heh, I even set the amount to write as just 1 and I still get stack overflow!
    Last edited by ulillillia; 04-28-2007 at 06:55 PM. Reason: another hint added

  4. #4
    Just Lurking Dave_Sinkula's Avatar
    Join Date
    Oct 2002
    Posts
    5,006
    Code:
    unsigned char TerrainData[131072];
    /* ... */
    unsigned char TerrainPreviewData[2097152];
    Why not dynamically allocate these instead of putting them on the stack?
    7. It is easier to write an incorrect program than understand a correct one.
    40. There are two ways to write error-free programs; only the third one works.*

  5. #5
    Woof, woof! zacs7's Avatar
    Join Date
    Mar 2007
    Location
    Australia
    Posts
    3,459
    As Dave_Sinkula said, allocate them on the heap rather than the stack. This way you can manage it easier! Also allocate them as you need them so your not wasting resources.

    If you did re-write it so it uses the heap, you'd probably see the error go away

    Also
    Code:
    fwrite(&TempFileHead.bfType, 2, 1, FileHandle);
    	fwrite(&TempFileHead.bfSize, 4, 1, FileHandle);
    	fwrite(&TempFileHead.bfReserved1, 2, 1, FileHandle);
    	fwrite(&TempFileHead.bfReserved2, 2, 1, FileHandle);
    	fwrite(&TempFileHead.bfOffBits, 4, 1, FileHandle);
    	fwrite(&TempInfoHead.biSize, 4, 1, FileHandle);
    	fwrite(&TempInfoHead.biWidth, 4, 1, FileHandle);
    	fwrite(&TempInfoHead.biHeight, 4, 1, FileHandle);
    	fwrite(&TempInfoHead.biPlanes, 2, 1, FileHandle);
    	fwrite(&TempInfoHead.biBitCount, 2, 1, FileHandle);
    	fwrite(&TempInfoHead.biCompression, 4, 1, FileHandle);
    	fwrite(&TempInfoHead.biSizeImage, 4, 1, FileHandle);
    	fwrite(&TempInfoHead.biXPelsPerMeter, 4, 1, FileHandle);
    	fwrite(&TempInfoHead.biYPelsPerMeter, 4, 1, FileHandle);
    	fwrite(&TempInfoHead.biClrUsed, 4, 1, FileHandle);
    	fwrite(&TempInfoHead.biClrImportant, 4, 1, FileHandle);
    	fwrite(&Colors, 1, 8, FileHandle); // the colors black then white
    Why not just dump the entire struct to disc? Rather than writting each element, it's a lot less code and it's easier to understand.
    Last edited by zacs7; 04-28-2007 at 07:12 PM.

  6. #6
    Captain Crash brewbuck's Avatar
    Join Date
    Mar 2007
    Location
    Portland, OR
    Posts
    7,272
    The stack is no place for a two megabyte object.

  7. #7
    Deathray Engineer MacGyver's Avatar
    Join Date
    Mar 2007
    Posts
    3,211
    Might I add that this is kind of a large function, that large functions do not promote readability, and therefore do not assist in either the debugging or maintaining areas of a software's lifecycle.

  8. #8
    and the hat of int overfl Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    32,823
    > Why not just dump the entire struct to disc?
    Research previous posts on padding and alignment. There is no reason to believe that the way the compiler organises a struct in memory will match that of the file format.

    If you want true portability (solves the endian problem as well), then you have to read and write the file one byte at a time.

    > What is a "stack overflow" error?
    What it means.

    > What is a "stack"?
    That's a very odd question for someone writing code to ask. It's that thing used to manage local variables, function calls and returns etc.

    > How can I fix this problem?
    Remove those big dumb arrays from your function and allocate them elsewhere.
    - dynamically allocate them is one way
    - prefix them with the word 'static' is another (perhaps not so good, but dead easy)

    > I'm getting it with just 2 MB.
    There is a way to change the default stack size (look in the linker options).
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.
    I support http://www.ukip.org/ as the first necessary step to a free Europe.

  9. #9
    Captain Crash brewbuck's Avatar
    Join Date
    Mar 2007
    Location
    Portland, OR
    Posts
    7,272
    Quote Originally Posted by ulillillia View Post
    Code:
    if (TerrainData[ArrayIndex] == 135) { CurrentHeight -= 340; } // steepest downward slope
    else if (TerrainData[ArrayIndex] == 151) { CurrentHeight -= 224; }
    else if (TerrainData[ArrayIndex] == 167) { CurrentHeight -= 165; }
    else if (TerrainData[ArrayIndex] == 183) { CurrentHeight -= 129; }
    ... etc ...
    This piece of code could be made far more readable and maintainable by placing the data in an array or other data structure. I'd suggest something like this:

    Code:
    struct adjust_rec
    {
        int terrain;
        int adjust;
    };
    
    struct adjust_rec terrain_adjust_table[] =
    {
        { 135, -340 },
        { 151, -224 },
        { 167, -165 },
        { 183, -129 },
        ... etc ...
        { -1, -1 } /* Marks the end */
    };
    
    int get_terrain_adjust(int terrain, int *value)
    {
        struct adjust_rec *adj;
    
        /* Loop until we reach the end marker */
        for(adj = terrain_adjust_table; adj->terrain != -1; adj++)
        {
            if(adj->terrain == terrain)
            {
                *value = adj->adjust;
                return 1;
            }
        }
        return 0;
    }
    Now, the string of if-else statements can be replaced with this:

    Code:
    int delta_height;
    
    if(!get_terrain_adjust(TerrainData[ArrayIndex], &delta_height))
    {
        Errors++;
        printf("Invalid color at location %d\n", ArrayIndex);
    }
    else
    {
        CurrentHeight += delta_height;
    }
    Also, the selection of color indexes seems pretty strange. If you had chosen them to all be consecutive, you could have done this with a simple array of ints, used the terrain color to index into this array (after appropriate bounds checking).

  10. #10
    Math wizard
    Join Date
    Dec 2006
    Location
    USA
    Posts
    582
    Basically, if I'm understanding this right, I cannot have a 2 MB local array? In my case where I got a 250 MB array to work without problems, the array was global. I don't know how to dynamically change the size of an array, whether local or global (that is, going from myarray[131072] to myarray[192000] or something else). As to writing the structures, I didn't know it was possible to write the full structure in one write statement.

    The reason for the selection of colors is for the appearance and contrast. It would otherwise have a step value of 8 (going from 0 to 8, 16, 24, etc.) and it's very difficult to see the difference in the colors. The steps of 16 are much easier to see. The X (horizontal) change remains constant for the terrain and the Y (vertical) is adjusted to get as close as possible to a multiple of 5&#176; and goes up to an 80&#176; slope.

  11. #11
    Woof, woof! zacs7's Avatar
    Join Date
    Mar 2007
    Location
    Australia
    Posts
    3,459
    nevermind about writing the structure in one statement, I silly to suggest that - as pointed out by Salem.

    Look-up realloc() that should give you a hint

  12. #12
    Registered User whiteflags's Avatar
    Join Date
    Apr 2006
    Location
    United States
    Posts
    7,761
    Quote Originally Posted by ulillillia View Post
    Basically, if I'm understanding this right, I cannot have a 2 MB local array? In my case where I got a 250 MB array to work without problems, the array was global. I don't know how to dynamically change the size of an array, whether local or global (that is, going from myarray[131072] to myarray[192000] or something else). As to writing the structures, I didn't know it was possible to write the full structure in one write statement.
    These sorts of questions are asked all the time here, so I recommend using our best kept secret (apparently). The search page.

  13. #13
    Captain Crash brewbuck's Avatar
    Join Date
    Mar 2007
    Location
    Portland, OR
    Posts
    7,272
    Quote Originally Posted by ulillillia View Post
    The reason for the selection of colors is for the appearance and contrast.
    But this is indexed color, is it not? You can arrange the palette however you want. You could arrange it so that all the colors you are using are numbered incrementally from 0..n.

  14. #14
    Math wizard
    Join Date
    Dec 2006
    Location
    USA
    Posts
    582
    The terrain map that is read (which is 131072x1 pixels in size) is actually 8-bit grayscale. The file that is written (which is 131072x128 but later to be resized) is 1-bit monochrome. By using a global array instead, then fixing bugs unrelated to the stack overflow, I've got everything working and it looks nice. If only MSPaint actually worked properly for images over 32,768 pixels long, I wouldn't need to wait 20+ seconds for The GIMP to load the 2 MB file. What I'm seeing in my output, which is intended to help visualize what the terrain actually looks like, is what I expected to see.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Stack Overflow when declaring array
    By ejohns85 in forum C++ Programming
    Replies: 3
    Last Post: 04-03-2009, 06:00 AM
  2. Overflow in Stack Counter
    By mlsrar in forum C Programming
    Replies: 36
    Last Post: 10-02-2008, 12:58 PM
  3. problem of garbage values
    By aldajlo in forum C Programming
    Replies: 5
    Last Post: 10-02-2004, 05:41 PM
  4. Stack Overflow
    By madmardigan53 in forum C++ Programming
    Replies: 2
    Last Post: 08-10-2003, 01:32 PM
  5. stack make file problem
    By puckett_m in forum C Programming
    Replies: 2
    Last Post: 11-22-2001, 11:51 AM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21