COSC-2425 Programming Project Four

One of the very practical uses of assembly language programming is its ability to optimize the speed and size of computer programs. While programmers do not typically write large-scale applications in assembly language, it is not uncommon to solve a performance bottle neck by replacing code written in a high level language with an assembly language procedure.

In this programming project you will be given a C++ program that generates an array of pseudorandom integers and sorts the array using the selection sort algorithm.

Your job is to write an assembly language procedure that also sorts the array of pseudorandom integers using the selection sort algorithm. The C++ program will time multiple repetitions of the sort performed by both the C++ code and your assembly language procedure. The C++ program will compare the result. If all goes as expected, your assembly language procedure should be faster than the C++ code.

Chapter 13 of your textbook contains a discussion of how to interface an assembly language procedure with a high-level programming language like C++.

The Visual Studio solution for the C++ program that you are given has been packaged and compressed into a file called ProjectFour.zip. Create a location on your computer for this project. Download the compressed file, ProjectFour.zip, and unpack it into that location in your computer.

Look in the unpacked folder for a file named ProjectFour.sln. The .sln file extension stands for solution. Double clicking on this file will start up the Visual Studio solution for ProjectFour and allow you to execute the C++ program.

Modify ProjectFour by following these steps:

1. Click on the project name, ProjectFour in the Solution Explorer pane.
2. Click on the Project choice in the menu bar at the top of the screen.
3. Select Build Customizations.
4. In the Visual C++ Build Customization Files dialog box, check the checkbox next to masm(.targets,.props). Choose OK to save your selection and close the dialog box.
5. On the menu bar, choose Project, then choose Add Existing Item.
6. In the Add New Item dialog box, select the file named AsmSelectionSort.asm. Choose Add to add the file to your project and close the dialog box.

Use Ctrl+F5 or click on Debug in the Menu Bar followed by Start Without Debugging to execute the program. The MASM assembler will assemble AsmSelectionSort.asm into an object file that is then linked into your project.

A stub assembly language procedure has been provided so that you can execute the C++ program to get a feel for how it works. Your job is to improve on the efficiency of the C++ compiled code by writing an assembly language procedure that is faster. Click on the file named AsmSelectionSort.asm in the Solution Explorer pane. This file is your starting point for creating an assembly language version of the selection sort routine.

As always, start small. DO NOT be the Cookie Monster and gobble up the whole project at once. Steps you might consider, but are not limited to are:

• Have your assembly language procedure return the number of elements in the array. This will tell you if what is being passed as an argument is the value you expected.
• Have your assembly language procedure return the value of the first element in the array. This will tell you if you understand how to address and retrieve the value of an element in the array.
• Have your procedure return the value of the second (or fifth) element in the array. This will tell you if you understand how to address and retrieve the value of a particular element in the array.

This project will provide you with the opportunity to:

• Link an assembly language procedure to an existing C++ program.
• Create an assembly language version of a C++ program.
• Demonstrate your ability to work with a one-dimensional array.
• Show that you can implement a while loop in assembly language.
• Demonstrate your ability to implement nested loops in assembly language.
• Display your understanding of what an assembly language procedure is and how they can be used.
• Provides a chance for you to show that you understand how to compare values and take conditional action based on the results.
• Observe how assembly language procedures can be used to optimize programs written in a high-level language like C++.

Given C++ program:

// ProjectFour.cpp : Defines the entry point for the console application. // // COSC-2425, Project 4 // ASM Procedure Linking with C++ for Selection Sort comparison // George A. Driscoll - 5/23/2020

#include #include #include

using namespace std;

// Function prototypes for the selection sort and swap functions. void selectionSort(int array[], int size); void swap(int &a, int &b);

// Function prototype for the boolean isAscending function. bool isAscending(int numbers[], int size);

// Function Prototype for the assembly language version of selection sort. extern "C" { void AsmSelectionSort(int array[], int count); }

int main() { // Local Variables const int SIZE = 10000; const int REPETITIONS = 50; int numbers[SIZE]; int element[SIZE];

cout << " Selection Sort: C++ versus ASM ";

// Define the array elements. Values will range from 1 to 1000. for (int i = 0; i < SIZE; i++) { element[i] = (rand() % 1000) + 1; } cout.imbue(locale("")); cout << " Sample random values: "; for (int i = 0; i < 4096; i += 256) { cout << " " << element[i]; } cout << endl << endl;

// Use the C++ function to Sort the elements in the array. cout << " Using the C++ Selection Sort Algorithm." << endl; auto start = chrono::high_resolution_clock::now(); for (int n = 0; n < REPETITIONS; n++) { // Copy the randomly generated array. for (int i = 0; i < SIZE; i++) { numbers[i] = element[i]; }

// Use the C++ version of the Selection Sort algorithm. selectionSort(numbers, SIZE); } auto end = chrono::high_resolution_clock::now(); auto cppDiff = end - start; cout << " Duration of C++ Selection Sort Algorithm for " << SIZE << " Elements: " << chrono::duration (cppDiff).count() << " milliseconds. "; for (int i = 0; i < 4096; i += 256) { cout << " " << numbers[i]; } cout << endl << endl;

// Use the Assembly Language procedure to sort the elements in the array. cout << " Using the Assembly Language Selection Sort Algorithm." << endl; start = chrono::high_resolution_clock::now(); for (int n = 0; n < REPETITIONS; n++) { // Copy the randomly generated array. for (int i = 0; i < SIZE; i++) { numbers[i] = element[i]; }

// Use the ASM version of the Selection Sort algorithm. AsmSelectionSort(numbers, SIZE); } end = chrono::high_resolution_clock::now(); auto asmDiff = end - start; if (isAscending(numbers, SIZE)) { cout << setprecision(2) << fixed; cout << " Duration of ASM Selection Sort Algorithm for " << SIZE << " Elements: " << chrono::duration (asmDiff).count() << " milliseconds. "; for (int i = 0; i < 4096; i += 256) { cout << " " << numbers[i]; } cout << endl << endl; auto overallDifference = cppDiff - asmDiff; cout << " This is a difference of " << chrono::duration (overallDifference).count() << " milliseconds. "; auto percentage = chrono::duration (overallDifference).count() / chrono::duration (cppDiff).count(); if (chrono::duration (overallDifference).count() > 0.0) { cout << " Your ASM version of selection sort is " << (chrono::duration (percentage).count() * 100.0) << "% better than the C++ version. "; } else { cout << " Your ASM version of selection sort is no better than the C++ version. "; } } else { cout << " Your ASM version of selection sort did not put the array into ascending order. "; }

return 0; }

void selectionSort(int array[], int size) { int minIndex; // Subscript of smallest value in the scanned area. int minValue; // Smallest value in the scanned area.

// The outer loop steps through all of the array elements, // except the last one. The startScan variable marks the // position where the scan should begin. for (int startScan = 0; startScan < size - 1; startScan++) { // Assume the first element in the scanable area // is the smallest value. minIndex = startScan; minValue = array[startScan];

// Scan the array, starting at the next element in the // scannable area, looking for the smallest value. for (int index = startScan + 1; index < size; index++) { if (array[index] < minValue) { minValue = array[index]; minIndex = index; } }

// Swap the element with the smallest value with the // first element in the scannable area. swap(array[minIndex], array[startScan]); } }

void swap(int &a, int &b) { int temp; temp = a; a = b; b = temp; }

bool isAscending(int numbers[], int size) { // Determine if array is in ascending order. bool result = true;

for (int i = 0; i < size - 1; i++) { if (numbers[i] > numbers[i + 1]) { result = false; break; } }

return result; }

Assembly program starter:

TITLE AsmSelectionSort Procedure (AsmSelectionSort.asm)

.586 .model flat,C

AsmSelectionSort PROTO, arrayPTR:PTR DWORD, count:DWORD

.data

.code

;---------------------------------------------------------- AsmSelectionSort PROC USES edi, arrayPTR:PTR DWORD, count:DWORD ; ; Performs a selection sort on an array of 32-bit integers. ; ---------------------------------------------------------- mov esi,arrayPtr ; Dummy assignment to prevent warning mov ecx,count ; Dummy assignment to prevent warning

mov eax,1 ; Define a dummy return value. jmp short omega

omega: ret ; return AsmSelectionSort ENDP END

Can you provide with the output screenshot too??