Introduction
src，
Lab 3: Dynamic Memory Allocation
stack and heap, malloc() and free(), representing images
Goals
After this lab you will be able to
State the difference between heap and stack memory allocation.
For any variable declaration, determine whether it will be allocated on the stack or the heap and why.
Use malloc() and free() to manage heap memory
Used sized integer types.
interpret integer arrays as images and operate on them.
write nested loops.
Setup
Note that these instructions have changed form. slightly from the previous labs. As always, follow them carefully to make sure your files end up in the right place..
In the terminal:
Find your local clone of your class repo, or clone a new one from the server.
cd to the root of your repo.
Fetch the new material for Lab 3, stored in a compressed tar archive:
$ wget
Expand the archive into the current directory:
$ tar xzvf 3.tgz
This will create the new directory “3” containing the files you need.
List the contents of the directory, to make sure the previous steps worked.
$ ls 3
Makefile draw.c draw.h hadfield.png imgops.c imgops.h png.c png.h test.c
Add the new directory “3” to your repo:
$ git add 3
Change directory into 3, which will be our lab 3 working directory:
$ cd 3
Now build the demonstration programs
We will create, view and manipulate images using arrays as described below. Code is provided that displays them on the screen. This lab assumes you have X11 installed, which is true by default on Linux, but Mac users must install XQuartz.
To build two simple demonstration program we run make at the command line. make is a program that automatically determines which pieces of a large program need to be recompiled, and issues commands to recompile them. A description of how to build the program is provided in a Makefile. make is the standard tool for managing builds in the UNIX world. All IDEs such as Visual Studio, XCode and Eclipse have either make or a make-like tool under the hood. We will look at make in more detail later; for now we just run it with the supplied Makefile.
Running make in the current directory will run a relatively complex compile command:
$ make
gcc -std=c99 -g -Wall -O3 -I/usr/X11/include -o test test.c imgops.c draw.c png.c -lm -lpng -L/usr/X11/lib -lX11
If successful, the progam test will be built. If the build fails, look at the file Makefile to see some options for fixing it.
Run the program test:
$ ./test
You should see a new window appear with a completely black image. Click the mouse in the window to let the program continue and exit.
Now run the demonstration program again, this time with a PNG image filename as an argument:
$ ./test hadfield.png
This time the window should contain an image of a moustachioed astronaut. Again, click the mouse in the window to let the program continue and exit.
Read the program text of test.c that contains the program’s main(). You don’t need to understand the code in png.c or draw.c: just realize that the program in test.c is calling functions from these files to load an image from a file, and draw it a window. As you might expect, test.c hash-includes header files png.h and draw.h which contain declarations of the functions defined in the corresponding C source files. If in doubt about this, look at the contents of the headers and C files in your editor.
A second example is also provided: a program that draws a Mandelbrot Set fractal. You can build it with this command:
$ make fractal
and run it like this:
./fractal
Read the implementation in fractal.c to see how memory is allocated to store an image, how it is interpreted as a two-dimensional array, and how the pixel colors are set by changing values stored in the array. The guide below explains this in detail.
There is no task associated with this fractal program. It is just a simple example to study.
Requirements
The task structure in this lab is different to your previous labs. Your job is to finish the implementation of several function definitions in the supplied file imgops.c. The automated tests will exercise these functions to see if they meet the specifications.
You should already have added imgops.c to your repo. Simply commit your changes to this file whenever you have finished implementing one or more functions (or indeed, any time you like).
Read the Guide below.
You should extend the program in test.c to test your functions as you go. This will be demonstrated in the lab session. Writing tests is part of the work of a programmer, so get used to testing as you go.
Important: DO NOT add a main() function in imgops.c. Keep it in test.c. This is because the testing server has its own test program with a main() function. An extra main() will prevent the server’s test program from compiling.
Also important: DO NOT make your imgops.c code rely on any other files. For testing, the server copies only your imgops.c and will not bring any of your other files along.
Guide
Raster Images
In computer graphics, images are usually represented as arrays of pixels (picture elements). Each pixel describes the color of a single point in the image. For grey-level images - regular people call them “black and white” images - a range of 256 shades of grey, smoothly varying from 0=black to 255=white is enough to produce good-looking results.
We can conveniently and compactly represent a grey-level image as a one-dimensional array of unsigned chars of size (image_width image_height). To interpret the array as a two dimensional image, we assume that each row of pixels is stored consecutively in the array. By convention, image coordinates have the origin in the top left, and y values increase downwards. We map image coordinates (x,y) to array indices thus:
index = x + y image_width
The pixel indices of an image of width=5, height=4 are therefore:
A corresponding array declaration could be:
unsigned int width = 5;
unsigned int height = 4;
unsigned char img[ width height ];
or, using the manual memory allocation described in detail below:
unsigned int width = 5;
unsigned int height = 4;
unsigned char img = malloc( width height sizeof(unsigned char) );
Images represented this way are known as raster images, from the latin rastrum (a rake) from the days when images were drawn on the screen of a CRT monitor by steering an electron beam in the same line-by-line pattern. They are also called bitmaps from the days when each pixel was only a single bit representing black and white.
For speed, C does not initialize the values of array elements for you. If you want an all-black image, you must set the pixels to zero:
for( int i=0; i
char get_name( void )
{
printf( “Please enter your name: “ );
// should be enough space for a name
char line[1024];
// reads at most 1023 chars from stdin, up to first newline,
// EOF or error.
if( fgets( line, 1024, stdin ) == 0 ) // we ALWAYS check for I/O errors
{
perror( “failed to read a name” );
exit(1);
}
return line;
}
int main( void )
{
char name = get_name();
printf( “Your name is %s\n”, name );
return 0;
}
The image below shows a sketch of the function call stack for a run of this program up to and including line 23. When the program begins (1), the frame. for main() is on the stack, and its local variables use stack memory for storage. The “stack pointer” keeps track of the current “top” of the stack (growing downwards).
When get_name() returns (2)–(3), the stack pointer is simply replaced to the end of calling function main()’s stack frame. The space used by get_name() will be reused by the next function call.
This mechanism explains:
why you must declare all your variables in C: the compiler has to decide how large a function’s stack frame. needs to be before the function runs;
another reason why C programs can be very fast: memory allocation, and particularly deallocation, are very cheap for automatic variables.
Find the bug!
Test your understanding so far: can you find the bug in get_name()?
Do not return a pointer to an address in your stack frame!
The problem is the pointer returned by get_name() points to data inside that function’s stack frame. When the function returns, that pointer is no longer valid. This sketch illustrates what happens:
At (2) the return value of get_name() is determined to be the address of the line character string. At (3) main()’s name variable is set to the return value of get_name() and that function’s stack frame. is popped from the stack and thus forgotten. At (4) name points into the forgotten stack frame. This is a nasty bug, since the correct data might still be there! At (5) the function call to printf() was entitled to overwrite the old data. There’s a good chance that name now points to garbage.
This kind of bug is one of the main reasons people complain about C. The code looks like it should work: the intent is clear; it compiles; it might even work in testing. Yet details of the implementation mean that the code is fatally bugged. This is undoubtedly a bad thing. The fact that it may work in testing is particularly awful.
The good news is that modern compilers will generate a helpful warning if you return a pointer to memory allocated for an automatic variable. Read your warnings. Better still, always use -Wall and fix all warnings in your builds, every time.
Try it yourself
This C source file provides an extended version of the program above, that demonstrates the corruption of name by overwriting it on the stack. Save it as get_name.c.
Read, build and run the program. Enable all warnings to see if your compiler spots the bug:
$ gcc -Wall get_name.c
And verify that it breaks as anticipated. You may be surprised to see that we have to work quite hard to corrupt the array on the stack. Satisfy yourself that you understand it before moving on.
First Solution: Allocate in caller
There are two different approaches to fixing this problem. The simpler and faster solution - and thus the best one when you can use it - is to have the calling function allocate the array and pass in a pointer to it, like so:
#include
#include
void get_name( char line[], int maxlen )
{
printf( “Please enter your name: “ );
// reads at most maxlen-1 chars from stdin, up to first newline,
// EOF or error.
if( fgets( line, maxlen, stdin ) == 0 ) // we ALWAYS check for I/O errors
{
perror( “failed to read a name” );
exit(1);
}
}
void stuff()
{
// store some random values in my stack frame
int stuff[1000];
for( int i=0; i