Due:

• Milestone 1 due Friday, Sep 19th by 11 pm
• Milestone 2 due Friday, Sep 26 by 11 pm
• Milestone 3 due Friday, Oct 3rd by 11 pm

This is a pair assignment, so you may work with one partner.

Update 9/25: the evaluation of the quality and comprehensiveness of your helper function unit tests will happen in Milestone 3, not Milestone 2.

Overview

In this assignment, you will implement transformations on image files, using both C (in Milestone 1) and x86-64 assembly language (in Milestones 2 and 3.)

Milestones

In Milestone 1, you are required to implement all of the image transformations in C. You are also required to implement comprehensive unit tests for all of the helper functions you use to implement the transformations. The intent is that your assembly language code in Milestones 2 and 3 will implement the same helper functions, and your unit tests will help you gain confidence in their correctness.

In Milestone 2, you are required to implement the complement and transpose transformations in assembly language. We expect you to have comprehensive unit tests for the assembly language implementations of your helper functions. (In theory you can just use the ones you implemented in Milestone 1.)

In Milestone 3, you will implement the ellipse and emboss transformations.

Note that in each milestone, we expect all of the tests executed by your unit test program to pass. For Milestone 2 in particular, you can comment out calls to test functions that aren’t related to helper functions needed for Milestone 2. For example, for Milestone 2 your imgproc_test.c’s main function might have code similar to the following:

TEST( test_get_r );
TEST( test_get_g );
TEST( test_get_b );
TEST( test_get_a );
TEST( test_make_pixel );
//TEST( test_is_in_ellipse );

The tests for get_r, get_g, get_b, get_a, and make_pixel are enabled because they are all test functions involved in the implementations of the transformations required for MS2. The test for is_in_ellipse is commented out because it is used in the ellipse transformation, which is not part of the requirements for MS2.

Non-functional requirements

In Milestones 2 and 3, you will be writing assembly language functions. You must write these “by hand”, and your assembly code must have very detailed code comments explaining the purpose of each assembly language instruction.

It is not allowed to generate assembly code using a C compiler and submit this as your own code. We will assign a grade of 0 to any submissions containing compiler-generated code where hand-written assembly language is expected.

Your submission for each milestone should include a README.txt file describing how you and your partner divided the work, and letting us know about any interesting implementation details. If there is functionality you weren’t able to get working completely, this is a good place to mention that.

We expect you to follow the style guidelines. However, the expectations for function length will be relaxed considerably for your assembly language code. It is not unusual for an assembly language function to have 100 or more lines of code. In the reference solution, the longest function was about 115 lines, although there was extensive use of comments and whitespace to improve readability.

Of course, you should strive to make your assembly language functions as simple and readable as possible.

We expect your code to be free of memory errors. You should use valgrind to test your code to make sure there are no uses of uninitialized variables, out of bounds memory reads or writes, etc. This applies to both your C code and your assembly code.

Grading breakdown

Milestone 1: 30%

• Implementation of C image transformation functions: 12.5%
• Unit testing of helper functions: 12.5%
• Design/coding style of C functions: 5%

Milestone 2: 35%

• Functional correctness of imgproc_complement and imgproc_transpose: 30%
• Design/coding style of assembly functions: 5%

Milestone 3: 35%

• Functional correctness of imgproc_ellipse: 10%
• Functional correctness of imgproc_emboss: 10%
• Unit testing of helper functions: 10%
• Design/coding style of assembly functions: 5%

Getting started

To get started, download csf_assign02.zip and unzip it.

You will implement the functions in c_imgproc_fns.c (Milestone 1) and asm_imgproc_fns.S (Milestones 2 and 3.) You will also add prototypes for helper functions to imgproc.h and implement additional unit tests in imgproc_tests.c.

Image processing

This section describes the image format and the image transformations you will implement.

struct Image

An instance of the struct Image data type represents a grid of pixels, where each pixel has 8-bit red, green, and blue color component values, as well as an 8-bit alpha value.

The struct Image type is defined as follows (in image.h):

struct Image {
  int32_t width;
  int32_t height;
  uint32_t *data;
};

The width and height fields define the width and height of an image, in pixels. The data field is a pointer to a dynamically-allocated array of uint32_t values, each one representing one pixel. The pixels are stored in row-major order, starting with the top row of pixels.

A color is represented by a uint32_t value as follows:

• Bits 24-31 are the 8 bit red component value, ranging from 0–255
• Bits 16-23 are the 8 bit green component value, ranging from 0–255
• Bits 8–15 are the 8 bit blue component value, ranging from 0–255
• Bits 0–7 are the 8 bit alpha value, ranging from 0–255

This pixel data format is known as “RGBA”.

The alpha value of a color represents its opacity, with 255 meaning “fully opaque” and 0 meaning “fully transparent”.

Image transformation functions

You will implement the following image transformation functions in both C and assembly language:

void imgproc_complement( struct Image *input_img,
                         struct Image *output_img );
int imgproc_transpose( struct Image *input_img,
                       struct Image *output_img );
void imgproc_ellipse( struct Image *input_img,
                      struct Image *output_img );
void imgproc_emboss( struct Image *input_img,
                     struct Image *output_img );

These functions are declared in imgproc.h, and each one has a detailed API comment describing its function, the meaning of the parameters, and the meaning of the return value (for the non-void functions.)

The complement transformation

In the complement transformation, the bits in each pixel value representing the red, green, and blue color component values should be replaced by their bitwise complements. In other words, for just the color component bits, each 1 bit should be replaced by 0, and each 0 bit should be replaced by 1. The C ~ operator and the x86-64 not instruction can implement this transformation. All alpha values should remain unmodified.

Visually, this transformation has the effect of making intense color component values dim and dim color component value intense, much like a photographic negative. (Think about why this happens!)

Original image	Transformed image

The transpose transformation

In the transpose transformation, which can only be applied to square images (where the image width and height are the same), the row and column of each source pixel are swapped to yield the row and column of the destination pixel. I.e., a pixel at row \(i\) and column \(j\) in the input image should be placed at row \(j\) and column \(i\) in the output image.

Original image	Transformed image

The ellipse transformation

In the ellipse transformation, pixels within an centered ellipse are retained with their original color component and alpha values, while pixels outside of the ellipse are set to fully-opaque black.

Determining which pixels are in the ellipse should be done as follows.

Compute values \(a = \lfloor w/2 \rfloor\) and \(b = \lfloor h/2 \rfloor\), where \(w\) is the image width and \(h\) is the image height.

Consider the pixel at row \(b\) and column \(a\) as being the center pixel of the image.

For each pixel in the image, compute \(x\) as the horizontal distance from the center pixel, and \(y\) as the vertical distance from the center pixel.

A pixel is in the ellipse, and should be copied to the output image, if it satisfies the inequality

Note that in these computations, the floor operations indicate that integer division is used. You will not need to use floating-point operations.

It should be sufficient to use 32-bit integers for these computations.

Original image	Transformed image

The emboss transformation

The emboss transformation generates an “emboss” effect. The pixels of the source image are transformed as follows.

The top row and left column of pixels are transformed so that their red, green, and blue color component values are all set to 128, and their alpha values are not modified.

For all other pixels, we consider the pixel’s color component values \(r\), \(g\), and \(b\), and also the pixel’s upper-left neighbor’s color component values \(nr\), \(ng\), and \(nb\). In comparing the color component values of the pixel and its upper-left neighbor, we consider the differences \((nr-r)\), \((ng-g)\), and \((nb-b)\). Whichever of these differences has the largest absolute value we refer to as diff. (Note that in the case that more than one difference has the same absolute value, the red difference has priority over green and blue, and the green difference has priority over blue.)

From the value diff, compute the value gray as 128 + diff. However, gray should be clamped so that it is in the range 0–255. I.e., if it’s negative, it should become 0, and if it’s greater than 255, it should become 255.

For all pixels not in the top or left row, the pixel’s red, green, and blue color component values should be set to gray, and the alpha value should be left unmodified.

Original image	Transformed image

c_imgproc and asm_imgproc programs

The c_imgproc and asm_imgproc programs apply one of the image transformations to an input image (or, in the case of the composite transformation, two input images), and write the result to an output image file. The c_imgproc_main.c source file implements both of these programs. The only difference between c_imgproc and asm_imgproc is whether the image transformations are implemented in C (c_imgproc_fns.c) or x86-64 assembly language (asm_imgproc_fns.S.)

To run these programs:

./c_imgproc transformation input.png output.png
./asm_imgproc transformation input.png output.png

In these commands:

• transformation is the name of the image transformation to perform
• input.png is the name of the input image file
• output.png is the name of the output image file to write

For example, to run the complement transformation using the c_imgproc program:

mkdir -p actual
./c_imgproc complement input/ingo.png actual/c_ingo_complement.png

The commands in this example would apply the complement transformation on the input image input/ingo.png to produce the output image file actual/c_ingo_complement.png.

Unit tests, helper functions

The source file imgproc_tests.c is a unit test program that you should use to test the functions in c_imgproc_fns.c and asm_imgproc_fns.S.

The starter code has some very basic tests for the API functions implementing the various image transformations. However, you will need to write unit tests for your helper functions. The idea is that your assembly language code will implement exactly the same helper functions as your C code, and having a comprehensive set of unit tests for these helper functions will allow you to get your assembly code working incrementally by implementing the helper functions one at a time.

You are free to implement whatever helper functions make sense. The reference implementation defined the following helper functions:

uint32_t get_r( uint32_t pixel );
uint32_t get_g( uint32_t pixel );
uint32_t get_b( uint32_t pixel );
uint32_t get_a( uint32_t pixel );
uint32_t make_pixel( uint32_t r, uint32_t g, uint32_t b, uint32_t a );
int32_t compute_index( struct Image *img, int32_t row, int32_t col );
int is_in_ellipse( struct Image *img, int32_t row, int32_t col );

Image tests

The provided script run_all.sh runs your c_imgproc or asm_imgproc program on some example input images and checks whether a correct output image is produced. To run it:

# test the C implementations of the image transformations
./run_all.sh c
# test the assembly implementations of the image transformations
./run_all.sh asm

Hints and tips

x86-64 tips

Here are some x86-64 assembly language tips and tricks in no particular order.

Callee-saved registers are your best option to serve as local variables in your assembly language functions. The callee-saved registers are %r12, %r13, %r14, %r15, %rbx, and %rbp. If you are going to store data in a callee-saved register, make sure that you use pushq to save its value at the beginning of the function, and popq to restore its value at the end of the function. (The popq instructions must be in the opposite order as the pushq instructions.)

If you run out of callee-saved registers, then you can use memory in the stack frame to store local variables. We highly recommend using an ABI-compliant stack frame to reserve memory for local variables, since that will allow gdb to properly recognize the functions on the call stack. To do so, your function’s prologue code should look like this:

pushq %rbp
movq %rsp, %rbp
subq $N, %rsp
...push callee-saved registers...

This prologue will reserve N bytes of memory in the stack frame that you can use for local variables. Note that all local variables in memory should be accessed at negative offsets from %rbp. For example, if you reserved 16 bytes for local variables, and you need space for four 4-byte variables, you can refer to them as -4(%rbp), -8(%rbp), -12(%rbp), and -16(%rbp).

Don’t forget that the amount by which the stack pointer is changed needs to be an odd multiple of 8 (so 8, or 24, or 40, etc.), and that each pushq subtracts 8 from %rsp. Also, don’t forget to pop back the original values of any saved callee-saved registers, including %rbp. In general, your function epilogue code should look like

...pop callee-saved registers...
addq $N, %rsp
popq %rbp

Don’t forget that you need to prefix constant values with $. For example, if you want to set register %r10 to 16, the instruction is

movq $16, %r10

and not

movq 16, %r10

When calling a function, the stack pointer (%rsp) must contain an address which is a multiple of 16. However, because the callq instruction pushes an 8 byte return address on the stack, on entry to a function, the stack pointer will be “off” by 8 bytes. You can subtract 8 from %rsp when a function begins and add 8 bytes to %rsp before returning to compensate. Pushing an odd number of callee-saved registers also works, and has the benefit that you can then use the callee-saved registers freely in your function. Sometimes you may need to subtract 8 from %rsp even if your function doesn’t allocate storate for any local variables in memory, just to ensure that %rsp is aligned correctly.

We strongly recommend that you have a comment in each function explaining how it uses callee-saved registers and (if relevant) stack memory, since these are the equivalent of local variables in assembly code. For example, here is a comment taken from the implementation of the imgproc_emboss function in the reference solution:

/*
 * Register use:
 *   %r12 - pointer to input Image
 *   %r13 - pointer to output Image
 *   %r14d - row index
 *   %r15d - column index
 *   %ebx - original/updated pixel value
 */

Recall that your assembly language code must have detailed comments explaining each line of assembly code. The following example function illustrates the level of commenting that we expect to see:

/*
 * Determine the length of specified character string.
 *
 * Parameters:
 *   %rdi - pointer to a NUL-terminated character string
 *
 * Returns:
 *    number of characters in the string
 */
	.globl str_len
str_len:
	/* prologue to create ABI-compliant stack frame */
	pushq %rbp
	movq %rsp, %rbp

.Lstr_len_loop:
	cmpb $0, (%rdi)               /* found NUL terminator? */
	jz .Lstr_len_done             /* if so, done */
	inc %r10                      /* increment count */
	inc %rdi                      /* advance to next character */
	jmp .Lstr_len_loop            /* continue loop */

.Lstr_len_done:
	movq %r10, %rax               /* return count */

	/* epilogue */
	popq %rbp

	ret

As illustrated in the example function, labels for control flow should be local labels, with names beginning with “.L”. If you don’t use local labels within functions, debugging with gdb will be difficult because gdb will think that each control flow label is the beginning of a function.

Debugging tips

You primary means of determining whether or not your code works correctly is running the unit test programs (c_imgproc_tests and asm_imgproc_tests.)

If a unit test fails, you should use gdb to debug the code to determine why it is not working.

Setting a breakpoint on the specific test function that is failing is one way to start. For example, if the test_is_in_ellipse test function is failing, in gdb set a breakpoint on that function, then run the program so that it only runs that test function:

break test_is_in_ellipse
run test_is_in_ellipse

You will gain control of the program at the beginning of the test function, at which point you can step through the code, inspect variables, registers, and memory, etc.

Another good option for setting a breakpoint is the tctest_fail function, because this is the function called when a test assertion fails. For example, assuming test_is_in_ellipse has an assertion failure:

break tctest_fail
run test_is_in_ellipse

When the tctest_fail breakpoint is reached, use the up command (as many times as needed) to enter the stack frame for the failing assertion. This can allow you to check variables at the location of the assertion.

Don’t forget that you can inspect register values in gdb by prefixing the register name with the “$” character. For example:

print $ebx

would show you the contents of the %ebx register. Using print/x allows you to see integer values in hexadecimal (very useful for checking color values.)

Casting a register to a pointer allows you to interpret memory as values belonging to C data types. For example, let’s say %r10 points to a struct Image instance. You could check the value of the element at index 18 of the data array using the command

print/x ((struct Image *)$r10)->data[18]

If you are storing local variables in stack memory, and using %rsp to access them, it is easy to see their values. In particular, if all of the local variables are the same size and type (e.g., they are all 4-byte integers), then you can think of them as an array. For example, in the comment above about local variable allocation, there are 7 local variables allocated in stack memory, six of which are 4 byte integer values, and one of which is an 8 byte integer value. We can see the six four-byte values at once with the gdb comamnd

print (unsigned [6]) *((unsigned *)($rbp - 24))

Here we are pretending that these variables belong to the unsigned type, which is the same as the uint32_t type. The (unsigned [6]) at the beginning of the expression tells gdb that we are interpreting the memory as an array of 6 unsigned elements. We use the expression $rbp - 24 to compute the address of the beginning of the area containing the 4-byte variables, because it is 24 bytes in size, and %rbp points to the “top” of the area. Note that the print command will show the values of the local variables starting with the local variable with the “lowest” address, i.e., the one referred to as -24(%rbp).

We can see the 8 byte value in memory (at offset -32 from %rbp) using the gdb command

print (unsigned long) *((unsigned long)($rbp - 32))

Submitting

Before you upload your submission, make sure that your README.txt contains the name of each team member and a brief summary of each team member’s contributions to the submission. If there is anything you would like us to know about your submission, you can also add it to README.txt.

To prepare a zipfile for submission, run the command

make solution.zip

Please do not submit object files, executables, PNG image files, or other files not mentioned above. (If you use make solution.zip as recommended above, only the necessary files will be included in the zipfile.)

Upload the zipfile to Gradescope as Assignment 2 MS1, Assignment 2 MS2, or Assignment 2 MS3, depending on which milestone you are submitting.