V22.0201 (sec. 1) - Computer Systems Organization (Honors)

Assignment 5 - Combining C and Assembler

As we have mentioned repeatedly in class, there are few occasions any more when it is worthwhile to program in assembler.  As we have seen from looking at the output of the Microsoft C compiler, compilers can produce very efficient code -- about as good as a skilled assembly language programmer.  However, there are still times when we may be tempted to use assembly code because the machine has some capabilities which we cannot easily use from a higher-level language.  In this assignment, we will look at two such cases.

Part I:  string operations

(1) Prepare your own versions, in C, of the string functions strcpy, strlen, and strchr.  You need not be original;  for example, the Kernighan and Ritchie book gives several versions of the first two functions.

(2) The x86 machines have special instructions for string copy and compare which were meant to be faster than the 'standard' instructions.  Study section 5.2 of the Carter text. Prepare assembly language versions of the same functions ( strcpyand strlenare given by Carter;  you have to do a bit of your own coding for strchr).

(3) Observe the time required by these two sets of functions for strings of at least two different lengths.  Try the C code both in debug mode and in maximal-speed mode. How much gain do you get from using the special string instructions (over optimized C)?

Part II:  extra long integers

Applications such as cryptography and tracking the national debt require large integers.  Java and some C implementations provide 64-bit integers (_int64 type in Visual C++, for example).  For this part of the assignment, you are to write a function for adding 128-bit integers.  Each 128-bit integer is stored as an array of 4 ints (32-bit integers).  If  a 128-bit integer is stored in int num[4], the most significant 32 bits are in int[3] and the least significant 32 bits are in int[0].

(1)  Write a C function for performing this addition:  longlongadd (int* a, int* b, int* sum)

(2)  Write an assembly language function for performing the same task.

(3)  Validate your code by checking that the two implementations return the same results for a range of inputs.  Observe the time required by the C function (unoptimized and optimized) and the assembly code.  How much gain do you get from using assembly code?

(Note:  the optimization level of the Visual C/C++ compiler is selected under Project ... Settings ... C/C++ tab ... Optimizations pull-down menu.  You must also remove the /ZI and /GZ options under "Project Options" at the bottom of that tabbed pane.  The speed of the program can be determined using clock();  doing
 #include <time.h>

 clock_t start, finish;
 double duration;

 start = clock();
 blahblahblah;
 finish = clock();
 duration = (double)(finish - start) / CLOCKS_PER_SEC;
puts in duration the time required for blahblahblah.)

Tabulate, as accurately as you can, the time required (in nanoseconds) for a calls to the different functions.  It is recommended that you run the program several times to make sure you are getting (roughly) consistent times;  you may find the times for the first run somewhat different from later runs. 

This assignment is due on November 19th and is worth 10 points.  As usual, there is a penalty of 1/2 point for each day late.  For 1 point of extra credit, measure the speed of the library string functions with the optimizing C, and explain why they are faster or slower than the functions you coded in C or assembler.

Email your assignment to the grader, with a copy to the instructor (grishman@cs.nyu.edu).  This includes all your code and a 1-2 page write-up (in Word format) describing your results. Show the raw data you obtained and the computed times. Please include the type and speed of the CPU you are running.  Include your name and "Asgn 5" in the subject line.