// Basic 64-bit arithmetic library
// David L. Rager
/* I define a structure to hold the high and low bits of a 64 bit integer. I
then define C functions that operate on this structure and save the result
in a structure pointed to by ans. Note that ans must be in a location valid
after the function returns (either in a calling function or on the heap). */
typedef struct double_ints {
unsigned int high;
unsigned int low;
} double_int;
/* One thing you could do to optimize this is establish a register convention
that says %eax stores the low bits and %edx returns the high bits. You get
to work at a lower level than the C code, which gives you more optimzation
opportunities. */
void shift_left_once (double_int x, double_int * ans) {
// Think of the below declaration as saying "%eax will store the low bits and
// %edx will store the high bits"
double_int res;
res.high = x.high + x.high;
res.low = x.low + x.low;
// remember that you can use any 32-bit constant you want
unsigned high_bit_of_low = x.low & 0x80000000;
if (high_bit_of_low) {
res.high = res.high + 1;
}
(*ans).low = res.low;
(*ans).high = res.high;
}
unsigned int shift_left_once_int (unsigned int x) {
// fill in (easy)
// this is so easy, that you should really just do the operation without
// calling this function.
}
void shift_left_n (double_int x, int n, double_int * ans) {
// more difficult
// Use shift_left_once
}
unsigned shift_left_n_int (unsigned int x, int n) {
// call shift_left_once_int n times
}
void add (double_int x, double_int y, double_int * ans) {
// Note that I can't write this function in C without using the asm command.
// You need to access the carry flag after you issue the low bit addition.
// Do this by branching to code that will
// Code ommittted
}
// In this implementation, I assume that y is the smaller of the two numbers
// and that it fits inside a 32 bit integer. This makes masking and shifting
// easier.
void mult (double_int x, int y, double_int * ans) {
// you'll need to call the add method inclusively between 0 and 31 times.
}
double_int fact (int x, double_int * ans) {
// if you've made it this far, fact is easy
// remember to intialize ans correctly (you probably need to start with one,
// but this depends on your implementation)
}
int main () {
double_int res;
res.high = 0xff00ff00;
res.low = 0xff00ff00;
shift_left_once (res, &res);
if ((res.high == 0xfe01fe01) && (res.low == 0xfe01fe00))
printf ("Shift_left_once passes one test case.\n");
else
printf ("Shift_left_once fails its test case.\n");
shift_left_n (res, 7, &res);
if ((res.high == 0x00ff00ff) && (res.low == 0x00ff0000))
printf ("Shift_left_n passes one test case.\n");
else
printf ("Shift_left_n fails its test case.\n");
double_int x, y;
x.high = 0x00ff00ff;
y.high = 0x00ff00ff;
x.low = 0x80000007;
y.low = 0x80000001;
add (x, y, &res);
if ((res.high == 0x01fe01ff) && (res.low == 0x00000008))
printf ("Shift_left_n passes one test case.\n");
else
printf ("Shift_left_n fails its test case.\n");
if (shift_left_n_int (0x1, 7) == 0x80)
printf ("Shift_left_n_int passes one test case.\n");
else
printf ("Shift_left_n_int fails its test case.\n");
x.high = 0x0;
x.low = 0xff000000;
mult (x, 3, &res);
if ((res.high == 0x00000002) && (res.low == 0xfd000000))
printf ("Mult passes one test case.\n");
else
printf ("Mult fails its test case.\n");
fact (4, &res);
printf ("High bits for Fact(4) are: %d\nLow bits are: %d\n", res.high, res.low);
printf ("High bits for Fact(4) are: 0x%x\nLow bits are: 0x%x\n", res.high, res.low);
fact (20, &res);
printf ("High bits for Fact(20) are: %d\nLow bits are: %d\n", res.high, res.low);
printf ("High bits for Fact(20) are: 0x%x\nLow bits are: 0x%x\n", res.high, res.low);
printf ("Note that the TA isn't sure the result for Fact (20) is correct.\n");
printf ("Please discuss amongst yourselves on the newsgroup.\n");
printf ("Also, remember to do question #1 on the homework and to store the results\n");
printf ("in %eax and %edx.");
}