Due:

• Milestone 1 due Friday, Feb 13th by 11 pm
• Milestone 2 due Friday, Feb 20th by 11 pm
• Milestone 3 due Friday, Feb 27th by 11 pm

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

Update 2/3 — fixed some details so they are relevant to the this semester’s image transformations

Update 2/4 — added Template assembly language function and Computing average pixel values sections.

Update 2/5 — minor edits to more accurately reflect the helper functions implemented in the reference implementation

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 squash and color_rot 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.) Note that we will not officially grade the quality and comprehensiveness of your unit tests until Milestone 3.

In Milestone 3, you will implement the blur transformation and expand 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_blur_pixel );

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 blur_pixel is commented out because it is used in the blur 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 149 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_squash and imgproc_color_rot: 30%
• Design/coding style of assembly functions: 5%

Milestone 3: 35%

• Functional correctness of imgproc_blur: 10%
• Functional correctness of imgproc_expand: 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_squash( struct Image *input_img,
                     struct Image *output_img,
                     int32_t xfac, int32_t yfac );
void imgproc_color_rot( struct Image *input_img,
                        struct Image *output_img );
void imgproc_blur( struct Image *input_img,
                   struct Image *output_img,
                   int32_t blur_dist );
void imgproc_expand( 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 squash transformation

The squash transformation transforms the input image by shrinking it both horizontally and vertically by (potentially different) integer factors.

In the following explanation, we’ll refer to the horizontal factor as \(a\) and the vertical factor as \(b\). (In the code, they are referred to by the names xfac and yfac.)

Each pixel of the output image is determined by sampling a pixel from the input image. Specifically, the output pixel at row \(i\) and column \(j\) copies the input pixel at row \(bi\) and column \(aj\). This is equivalent to keeping only the pixels whose row index is divisible by \(b\) and whose column index is divisible by \(a\). For example, consider the image below where each letter corresponds to a pixel:

XAAAYBBB
AAAABBBB
ZCCCWDDD
CCCCDDDD

If the user specifies \(a = 4\) and \(b = 2\), only pixels in rows 0 and 2 with columns 0 and 4 are sampled. The resultant image is:

XY
ZW

If the width and height of the original image are \(w\) and \(h\), respectively, the output image will have width equal to \(\lfloor w / a \rfloor\) and height equal to \(\lfloor h / b \rfloor\).

Example (note that the transformed image has been enlarged, click to see it at its correct size):

Original image	Transformed image (xfac 8, yfac 4)

The color_rot transformation

The color_rot transformation transforms the input image by shifting around the color components’ values in each pixel.

Each pixel of the output image should have its color components determined by taking the previous color component’s value and applying it to that pixel. The old pixel’s red component value will be used for the new pixel’s green component value, the old pixel’s green component value will be used new pixel’s blue component value and the old pixel’s blue component value will be used new pixel’s red component value. The alpha value each output pixel should be identical to the corresponding input pixel.

For example, if a pixel had the hex value 0xAABBCCDD, the transformed pixel would become 0xCCAABBDD in the same location. (Recall that the red color channel occupies the most-significant 8 bits of a pixel, and the alpha channel occupies the least-significant 8 bits of a pixel.)

Example:

Original image	Transformed image

The blur transformation

The blur transformation transforms the input image using a blur effect.

Each pixel of the output image should have its color components determined by taking the average of the color components of pixels within blur_dist number of pixels horizontally and vertically from the pixel’s location in the original image. For example, if blur_dist is 0, then only the original pixel is considered, and the the output image should be identical to the input image. If blur_dist is 1, then the original pixel and the 8 pixels immediately surrounding it would be considered, etc. Pixels positions not within the bounds of the image should be ignored: i.e., their color components aren’t considered in the computation of the result pixels.

The alpha value each output pixel should be identical to the corresponding input pixel.

Averages should be computed using purely integer arithmetic with no rounding.

Example:

Original image	Transformed image (blur distance 5)

The expand transformation

The expand transformation doubles the width and height of the image.

Let’s say that there are \(n\) rows and \(m\) columns of pixels in the input image, so there are \(2n\) rows and \(2m\) columns in the output image. The pixel color and alpha value of the output pixel at row \(i\) and column \(j\) should be computed as follows.

If both \(i\) and \(j\) are even, then the color and alpha value of the output pixel are exactly the same as the input pixel at row \(i/2\) and column \(j/2\).

If \(i\) is even but \(j\) is odd, then the color components and alpha value of the output pixel are computed as the average of those in the input pixels in row \(i/2\) at columns \(\lfloor j/2 \rfloor\) and \(\lfloor j/2 \rfloor + 1\).

If \(i\) is odd and \(j\) is even, then the color components and alpha value of the output pixel are computed as the average of those in the input pixels in column \(j/2\) at rows \(\lfloor i/2 \rfloor\) and \(\lfloor i/2 \rfloor + 1\).

If both \(i\) and \(j\) are odd then the color components and alpha value of the output pixel are computed as the average of the input pixels

1. At row \(\lfloor i/2 \rfloor\) and column \(\lfloor j/2 \rfloor\)
2. At row \(\lfloor i/2 \rfloor\) and column \(\lfloor j/2 \rfloor + 1\)
3. At row \(\lfloor i/2 \rfloor + 1\) and column \(\lfloor j/2 \rfloor\)
4. At row \(\lfloor i/2 \rfloor + 1\) and column \(\lfloor j/2 \rfloor + 1\)

Note that in the cases where either \(i\) or \(j\) is odd, it is not necessarily the case that either row \(\lfloor i/2 \rfloor + 1\) or column \(\lfloor j/2 \rfloor + 1\) are in bounds in the input image. Only input pixels that are properly in bounds should be incorporated into the averages used to determine the color components and alpha value of the output pixel.

Averages should be computed using purely integer arithmetic with no rounding.

Example (note that the transformed image is twice the size of the original in each dimension, click to see it full size):

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 [args...]
./asm_imgproc transformation input.png output.png [args...]

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
• [args...] represents additional arguments needed by the transformation; for example, the blur transformation needs an integer blur distance as an additional argument

For example, to run the blur transformation with a blur distance of 3 using the c_imgproc program:

mkdir -p actual
./c_imgproc blur input/ingo.png actual/c_ingo_blur_3.png 3

The commands in this example would apply the blur transformation with a blur distance of 3 on the input image input/ingo.png to produce the output image file actual/c_ingo_blur_3.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. Some of the helper functions defined in the reference implementation are:

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 );
uint32_t blur_pixel( struct Image *img, int32_t row, int32_t col, int32_t blur_dist );
uint32_t rot_colors( struct Image *img, int32_t index );

(Also see the Computing average pixel values section, which has suggestions for additional helper functions.)

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

/*
 * Register use:
 *   %r12 - pointer to input Image
 *   %r13 - pointer to output Image
 *   %r14d - output pixel row (i)
 *   %r15d - output pixel column (j)
 *   %ebx - computed pixel value
 *
 * Memory use:
 *   -20(%rbp) - base address of PixelAverager instance
 *   -24(%rbp) - 1 if row is odd, 0 if even
 *   -28(%rbp) - 1 if column is odd, 0 if even
 */

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_blur_pixel test function is failing, in gdb set a breakpoint on the blur_pixel function, then run the program so that it only runs that test function:

break test_blur_pixel
run test_blur_pixel

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

break tctest_fail
run test_blur_pixel

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))

Template assembly language function

Here is a possible starting template for your assembly language functions. It has the following properties:

• 5 callee-saved registers (%r12-%r15, %rbx) are available for general use
• An ABI-compliant stack frame is created, using the %rbp register to refer to stack memory
• The stack pointer will be aligned correctly as long as N (the number of bytes of stack memory to reserve) is an odd multiple of 8 (i.e., 8, 24, 40, etc.)
• You can use negative offsets from %rbp for variables allocated in memory (if you run out of callee-saved registers, or if you need to allocate a struct or array instance)

Feel free to use this as a starting point for your assembly functions.

/*
 * Template assembly function
 */
	.globl my_func
my_func:
	/*
	 * Register use:
	 *   TODO: describe how callee-saved registers are used
	 *
	 * Memory use:
	 *   TODO: describe how memory in the stack frame is used
	 */

	pushq %rbp
	movq %rsp, %rbp
	subq $N, %rsp
	pushq %r12
	pushq %r13
	pushq %r14
	pushq %r15
	pushq %rbx

	/* TODO: your code goes here */

	popq %rbx
	popq %r15
	popq %r14
	popq %r13
	popq %r12
	addq $N, %rsp
	popq %rbp
	ret

Computing average pixel values

The blur and expand both involve computing the average color component values of some number of pixels from the input image. The expand transformation also averages alpha values of some number of pixels.

You may find it useful to introduce an abstraction to make it easy to sum the color component and alpha values of some number of pixels, and then (once all of the needed pixels have been looked at) compute a result pixel as the average of the color component and alpha values.

The reference solution used the following struct type and helper functions for this purpose:

// PixelAverager is helpful for the blur and expand transformations
struct PixelAverager {
  uint32_t r, g, b, a, count;
};

void pa_init( struct PixelAverager *pa );
void pa_update( struct PixelAverager *pa, uint32_t pixel );
void pa_update_from_img( struct Image *img,
                         int32_t row, int32_t col,
                         struct PixelAverager *pa );
uint32_t pa_avg_pixel( struct PixelAverager *pa );

Note that the pa_update_from_img function is particularly convenient because it updates a PixelAverager instance based on a pixel at a specific row and column in an image, ignoring it if either the row or column is out of bounds. This can help you avoid needing bounds checks in the caller.

The struct PixelAverager data type shown above is 20 bytes in size, since each field is a uint32_t requiring 4 bytes. If you use the template function shown above, just make sure that N is at least 24, and you can allocate memory in the stack frame for a PixelAverager instance. For example, the reference implementation uses offset -20 from the frame pointer (%rbp) as the base address of a PixelAverager instance. The leaq instruction is useful for computing a pointer to the instance. For example, when calling pa_update_from_img, you could pass the address of your PixelAverager as the fourth argument using code like

leaq -20(%rbp), %rcx      /* pass ptr to PixelAverager as 4th arg */

If all of the fields are 4 bytes in size, then their offsets will be 0, 4, 8, etc. It’s a good idea to use #define to give meaningful names to these offsets. E.g.:

/*
 * struct PixelAverager field offsets
 */
#define PA_R_OFFSET 0
#define PA_G_OFFSET 4
#define PA_B_OFFSET 8
#define PA_A_OFFSET 12
#define PA_COUNT_OFFSET 16

The “base address plus offset” addressing mode is useful for referring to struct fields if you have a pointer to the beginning of the struct. E.g., if %rcx points to a struct PixelAverager, you could increment the count field with the instruction

incl PA_COUNT_OFFSET(%rcx)

You are welcome to follow the approach described above if you wish. If you do, be sure to write good unit tests for these functions so that you can test both your C and assembly language implementations.

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.