Due:

• Milestone 1 due Friday, Feb 14th by 11 pm
• Milestone 2 due Friday, Feb 21st by 11 pm
• Milestone 3 due Wednesday, Feb 26th by 11 pm

Update 2/6: Corrected an error in the formula for the gradient function in the fade transformation.

Update 2/7: Improved example of a comment to show register use and layout of variables in the stack frame.

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

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 grayscale and rgb 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 fade and kaleidoscope 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_to_grayscale );
//TEST( test_gradient );

The tests for get_r, get_g, get_b, get_a, make_pixel, and to_grayscale are enabled because they are all test functions involved in the implementations of the grayscale transformation, which is part of the requirements for MS2. The test for gradient is commented out because it is used in the fade 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: 45%

• Functional correctness of imgproc_rgb and imgproc_grayscale: 30%
• Unit testing of helper functions: 10%
• Design/coding style of assembly functions: 5%

Milestone 3: 25%

• Functional correctness of imgproc_fade: 10%
• Functional correctness of imgproc_kaleidoscope: 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”.

Grayscale

In the grayscale transformation, color pixels are converted to gray pixels as follows. From the color pixel’s red, green, and blue color component values, denoted as \(r\), \(g\), and \(b\), a “gray” value, denoted \(y\), is computed using the following formula:

The resulting gray pixel should have its red, green, and blue color component values set to \(y\), and its alpha value should be the same as the original color pixel’s alpha value.

Image transformation functions

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

void imgproc_grayscale( struct Image *input_img,
                        struct Image *output_img );
void imgproc_rgb( struct Image *input_img, struct Image *output_img );
void imgproc_fade( struct Image *input_img, struct Image *output_img );
int imgproc_kaleidoscope( 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 grayscale transformation

The grayscale transformation converts a color image to grayscale.

The Grayscale section documents how color pixel values are converted to grayscale pixel values.

Example images (click for full size):

Original image	Transformed image

The rgb transformation

The rgb transformation renders four copies of the original input image. The upper-left image is identical to the input image. The upper-right, lower-left, and lower-right images contain (respectively) only the red, green, and blue color components of the original image. The width and height of the output image are (respectively) twice the width and height of the input image, so each “quadrant” of the output image is the same size as the input image.

Example images (click for full size):

Original image	Transformed image

The fade transformation

In the fade transformation, the intensity of each pixel is modified so that pixels “fade out” the closer they are to the edges of the image.

Example images (click for full size):

Original image	Transformed image

The transformation should be implemented as follows.

The gradient function takes a pixel row or column coordinate and yields a value indicating how intense the pixels at that row or column should be, based on their proximity to an edge of the image. It is defined as

where \(x\) is the index of a pixel row or column and \(n\) is the number of pixels in that row or column (i.e., the height or width of the image.) The result of the gradient function is a value between \(0\) and \(1{,}000{,}000\), where \(0\) means that the pixel will be entirely faded (black), and \(1{,}000{,}000\) means that the pixel is displayed unmodified.

Because each pixel has two coordinates (column and row), the transformation will compute two gradient values for each pixel. Let’s call them \(t_{r}\) for the row gradient value and \(t_{c}\) for the column gradient value. For each color component value \(c\), a modified color component value \(c'\) should be computed as

Doing this computation for each of a pixel’s color component values (red, green, and blue) yields the color component values for the result pixel. (The alpha value of the original pixel should be used unmodified.)

Note that because these computations will involve large integer values, you should use signed 64-bit arithmetic to implement them.

The kaleidoscope transformation

In the kaleidoscope transformation, which can be applied only to images which are square (width and height are the same), the original image is divided into 8 “wedges”:

The transformation can be described this way:

1. The pixels of the wedge labeled “A” are copied to the wedge labeled “B” by swapping their horizontal and vertical coordinates; i.e., they are mirrored along the diagonal separating A and B
2. All of the other wedges are filled with copies of the pixels in A, such that all pixels are mirrored along all four dividing lines (horizontal, vertical, and the two diagonals)

Another way to look at point 2 above is that wedges A and B describe one quadrant of the image (the upper left), and that each of the other quadrants are “reflections” of the upper left quadrant, mirrored either horizontally (the upper right), vertically (the lower left), or both horizontally and vertically (the lower right.)

Also note that in point 1, which describes how pixels in wedge A are replicated in wedge B, the pixels along the diagonal separating wedges A and B are not modified.

As a special case, if width/height of the image is odd, meaning that the quadrants of the image can’t be exactly the same size, the transformation should round up the width and height to the next larger even value, and “pretend” that the original image had those dimensions. For example, for a 785x785 image, the transformation should “pretend” that it’s really a 786x786 image. You will need to take care to avoid out of bounds array accesses if the effective width and height are rounded up in this way.

Example of the kaleidoscope transformation:

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 rgb transformation using the c_imgproc program:

mkdir -p actual
./c_imgproc rgb input/ingo.png actual/c_ingo_rgb.png

The commands in this example would apply the rgb transformation on the input image input/ingo.png to produce the output image file actual/c_ingo_rgb.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 );
uint32_t to_grayscale( uint32_t pixel );
int64_t gradient( int64_t x, int64_t max );
int32_t compute_index( struct Image *img, int32_t col, int32_t row );

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 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_fade function in the reference solution:

/*
 * Register use:
 *   %r12d - i (pixel row index)
 *   %r13d - j (pixel column index)
 *   %r14 - pointer to input Image
 *   %r15 - pointer to output Image
 *   %rbx - computed pixel fade factor (row factor * col factor)
 *
 * Stack memory:
 *   -4(%rbp)  - current pixel value
 *   -8(%rbp)  - pixel r component value (from get_r)
 *   -12(%rbp) - pixel g component value (from get_g)
 *   -16(%rbp) - pixel b component value (from get_b)
 *   -20(%rbp) - pixel a component value (from get_a)
 *   -24(%rbp) - computed pixel index
 *   -32(%rbp) - computed row factor (from gradient fn)
 */

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_to_grayscale 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_to_grayscale
run test_to_grayscale

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_to_grayscale has an assertion failure:

break tctest_fail
run test_to_grayscale

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.