Go up to the Labs table of contents page
This lab is one of two labs meant to familiarize you with the process of writing, assembling, and linking assembly language code. The purposes of the in-lab and in-lab activities are to investigate how various C++ language features are implemented at the assembly level.
There are both 32 bit (md) and 64 bit (md) versions of this lab. This is the 64 bit version.
The Intel x86 assembly language is currently one of the most popular assembly languages and runs on many architectures from the x86 line through the Pentium 4. It is a CISC instruction set that has been extended multiple times (e.g. MMX) into a larger instruction set.
Read the C tutorial for the in-lab.
You may want to reference the “Compiling Assembly With C++” and “Vecsum” sections from the previous x86 lab.
The 3x+1 conjecture (also called the Collatz conjecture) is an open problem in mathematics, meaning that it has not yet been proven to be true. The conjecture states that if you take any positive integer, you can repeatedly apply the following function to it:
The conjecture is that eventually, the result will reach 1. For example, consider x = 13:
Note that this took 9 steps to reach the value 1. And it also shows that this conjecture is true for a number of other values (2, 4, 5, 8, 10, 16, 20, and 40).
An image (from Wikipedia) shows how paths of most integers less than 50 converge to 1.
While this conjecture has been proven only up to at least 5.6 * 10^13, it is widely believed to be true for all positive integers. If you are interested, more information on this conjecture can be found here.
We won’t be testing with any values above 10^6, so you can safely assume that the Collatz conjecture holds true for all of the input values that we will use. That is, you won’t have to worry about integer overflow.
Your task is to write a routine, called threexplusone,
that takes in a positive integer and returns the number of steps
required for that integer to reach 1 by following the Collatz
conjecture. An input of 13 takes 9 steps, as shown above. The Wikipedia
page shows a few other input sizes and the number of steps: an input of
6 takes 8 steps; an input of 14 takes 17 steps; an input of 27 takes 111
steps. If the input is 1, the output should be zero.
This routine MUST call itself recursively using the proper C-style calling convention. The assembly code should be in a threexplusone.s file. If you write your function so that it is an iterative solution, you will not receive credit for this pre-lab.
You will need to write a C++ file called threexinput.cpp that allows you to test your subroutine. This input file should:
You can assume that both x and n are positive integers.
We can now time the subroutine to see how fast it runs. Download the timer code from the hash table lab (lab 6: timer.cpp (src) and timer.h (src)) and use it to guage the average time it took to run each subroutine call in step 4.
You should use an appropriate precision number to make sure you don’t report zero when you divide the total time by the number of runs. Your timer code should only include the loop of n times that calls the routine with x as the parameter. Nothing else (including the print statement) should be inside the timer code.
Now that you can time your program, you will need to optimize it as much as possible. Any optimization is valid, as long as it computes the correct result, is still a recursive subroutine, and follows the C calling convention. The grade on this pre-lab will be based both on the correctness of the subroutine and the optimizations included.
What optimizations do you use?
lea can quickly add and multiply numbers in one
instruction.4*x+x is likely to be faster than
5*x, as the former can be optimized to x << 2 +
x.push and pop).You will need to include at least one optimization beyond just figuring out how to write your subroutine with fewer instructions. You should put the optimizations used as a comment in the beginning of your assembly file.
Note that we, too, can write the function in C++ and compile it with
clang++ -O2 -S -mllvm --x86-asm-syntax=intel. And we will
be looking at that assembly code when we grade the pre-lab. If you write
your program this way, it constitutes an honor violation, so please
hand-code the assembly yourself.
You must list, as comments in your assembly file, the optimizations that you used! Just a brief description of what optimizations you used is fine.
Below is a sample execution run to show you the input and output format we are looking for.
Input
Enter a number: 100
Enter iterations of subroutine: 30Output
Steps: 25See the last lab for details, but all code must be submitted to run under Linux, which is the platform that does the compilation on the submission system.
Download the linkedlist.c (src) test harness, your task is to implement a simple doubly-linked list in C. Read the C tutorial to help familiarize yourself with the C language. This linked list is meant to be simple, and can be implemented however you’d like in linkedlist.c. We don’t really care how you implement the linked list, whether it be with structs, arrays, etc. so long as it works with the provided harness. However, the assignment is considerably easier to do by using an actual linked list solution rather than an array-based solution. Your linked list will need to be able to do the following:
Below is a sample execution run to show you the input and output format we are looking for.
----------------------------------------------------
This test harness operates with one linked list.
Use any of the following options to manipulate it:
* af <num> --- add integer to front
* ab <num> --- add integer to back
* rf --- remove front element
* rb --- remove back element
* p --- print list forward
* help --- print off this list
* -1 --- exit harness
Enter command: af 1
Enter command: af
Invalid command or operand, please input a valid command or help to see the list again.
Enter command: af 2
Enter command: ab 3
Enter command: p
Elements: 2 1 3
Enter command: rf
Enter command: p
Elements: 1 3
Enter command: rb
Enter command: p
Elements: 1
Enter command: -1Download testBinarySearch.cpp (src), timer.cpp (src), and timer.h (timer.h), which you will use to test your code. Make sure you do not alter any of these files, as your must include the original files in your submission.
Your task for the post-lab is to implement the
binarySearch function in assembly. This function will begin
at the middle of a sorted array, and continuously split the search space
in half until it finds the target element or reaches a point where it
knows the target is not in the array. The function takes in four
parameters. The first parameter is a pointer to an int array. The second
parameter is an integer representing the beginning of the array. The
third parameter is an integer representing the end of the array. The
fourth parameter is an integer representing the target element to find
in the array. The return type of this function is int, and will be the
index into the array that the target was found, or -1 if it wasn’t. Just
like with the linearSearch from Post-Lab 8,
testBinarySearch will take input from std and pass it on to
your binarySearch routine. Make sure you test your function
on various sized arrays.
To make sure your function is efficient enough, the testBinarySearch.cpp file will call your function 1000 times and record the overall time taken via timer.cpp.
Below is a sample execution run to show you the input and output format we are looking for.
Enter the array size: 5
Enter value 0: -30
Enter value 1: -15
Enter value 2: 0
Enter value 3: 15
Enter value 4: 30
Enter target to search for: 30
Found 30 at index 4
Took 0.007msThe following resource explains the binary search algorithm. This is what you need to implement in x86 assembly: https://www.hackerearth.com/practice/algorithms/searching/binary-search/tutorial/