Assignment 3: memory locality

Hand-in requirements

Due date: March 11, 2011 at 11:59pm
Files to hand in (both in source code and in PDF form): your entire asn3 directory, which must include your Makefile and all .c and .h files necessary to run your auto-cropper. It doesn't hurt to submit other files that are in that directory, too (like .o files). Do not submit any PPM files. Please submit the directory as the TA will be looking for an "asn3" directory or similar.

Functional requirements

Build a program which will take in the filename of a PPM image file and output the co-ordinates of the image after being "auto-cropped". You should not output the actual image file after being auto-cropped, only the co-ordinates of where to do the cropping.

You may make the following assumptions about any PPM loaded into your program:

It is not corrupt or truncated in any way.
It has a "magic number" of P6 (this will make more sense if you read the PPM format specification).
The maximum colour value (maxval) will always be 255.
The image file will be small enough to be mapped in a 32-bit address space (less than 2GB).

Your program must print out the co-ordinates to do auto-cropping. Consider this example picture. The original image is without the yellow lines or red text. Your program must find the largest borders possible which can be cropped without destroying any of the "foreground" image. For your purposes, you will assume that the pixel in the extreme top-left corner (x=0, y=0) is the background colour and that any pixels with the same red, green and blue values can be considered part of the background; all other pixels are considired the foreground.

Co-ordinates in the image are read from the top down and from left to right, starting at 0. The top-left pixel is (0, 0). The pixel immediately to the right of it is (1, 0). The pixel immediately below the top-left pixel is (0, 1).

After finding the largest possible borders which can be cropped without removing any of the foreground, your program must print to stdout those co-ordinates (x1, x2, y1 and y2 from the example picture).

To gain full marks for the assignment, your program must not only be correct, but be very fast. You will use your knowledge of virtual memory and data caching to make it as fast as possible.

The following strategies are disallowed for assignment 3:

Using multi-threaded or multi-process code. Your program must only ever have a single thread of execution.
Making any assumptions about the data other than what's listed above (don't hardcode your program according to the testing data).

Example usage

bash$ ./autocrop giant-picture.ppm
(402, 17) - (10382, 17893)

Marks

Your base mark will be based on how quickly your program can autocrop the testing data. In the ~mburrel/3305/asn3 directory on GAUL you can find a number of large PPM files and sample output.

Your program will be compiled (with your Makefile) and run and timed on obelix. The amount of time it takes your program to determine a correct answer will decide your base mark. Note that your program may be run multiple times to get an average time (due to experimental error in the results). The PPM file will be in the operating system cache (i.e., we'll run it once first to get the file cached) before timing.

The exact PPM file used to test your program will be asteroids.ppm.

Marks will be given as follows:

Behaviour	Base mark	Total running time (wall clock time) for `asteroids.ppm` on obelix
Very little submitted	0/20
Nothing compiles	2/20
Compiles but has little functionality	5/20
Produces incorrect results due to bug but otherwise complete	7/20
Correct: very slow	9/20	≥30.000 seconds
Correct: slow	13/20	20.000–29.999 seconds
Correct: moderate speed	15/20	9.500–19.999 seconds
Correct: fast	17/20	7.500–9.499 seconds
Correct: very fast	20/20	5.800–7.499 seconds
Faster than my solution	21/20	<5.800 seconds

Mark adjustments
Something's fishy with the Makefile, making it annoying for the TAs to build	-2/20
Bad directory structure	-1/20
Code is hard to read	-1/20 to -4/20, depending on severity
An unnecessary use of a magic number	-1/20
Something really awesome that goes beyond the requirements of this assignment (stick in a README so we know to look for it!)	+1/20 to +3/20, depending on level of awesomeness
Proper C coding techniques have been followed (checking for errors, using errno, printing out error messages, dependencies in Makefiles are correct, etc.)	+1/20

Hints

I recommend you use mmap (see the man page or come to lectures after the break) to map the file into your address space. You can write a fast program which does not use mmap (i.e., it reads the file traditionally using read and lseek system calls) but your code will be more complex.
You may find the following function handy, which determines the size of a file, measured in bytes (if the file descriptor has already been opened):
```
#include <sys/stat.h>

static
unsigned long
fsize(int fd)
{
    struct stat st;
    fstat(fd, &st);
    return st.st_size;
}
```
This may be especially handy if you wish to mmap the file into your address space.
Look in ~mburrel/3305/asn3 on GAUL for example PPM files and sample output.
You may use the __builtin_prefetch GCC extension (we will discuss this briefly in lecture). See this page of documentation about 2/3 of the way down the page for information on how to use __builtin_prefetch. If you choose to use it, I recommend not filling in the two optional arguments (i.e., only give it a single argument).
Before submitting your assignment, ensure that your Makefile is compiling with -O3, which is gcc's maximum level of optimization. This is a very simple thing to do to easily gain you some speed (it doesn't make up for a poor algorithm, though, sadly).

Please use smaller PPM files during testing. For your benefit, here are some vaguely sort of approximate times you might be aiming for with the smaller files (-O0 means there's no optimization at all, like when you compile without a -O flag):

	phobos2_hirise_big.jpg.ppm		asteroidscomets_lakdallawa_....ppm		asteroids_comets_sc_....ppm
	-O3	-O0	-O3	-O0	-O3	-O0
Moderate speed	0.03s	0.03s	0.65s	1.15s	1.25s	3.00s
Fast	0.03s	0.04s	0.53s	1.72s	0.60s	3.20s
Very fast	0.03s	0.04s	0.50s	1.55s	0.55s	2.75s