Part 1 — 24%
In this part, you are asked to analyse a few function to understand what they do. The functions perform simple arithmetic and bitwise operations on their inputs. We do not ask you to describe these operations,but to explain what the outcome is. For example, consider the function:
int32_t example1(int32_t a) {
return (aˆ0xFFFFFFFF)+1;
}
Saying that example1 calculates the exclusive or of the input with the number 0xFFFFFFFF and adds
one is technically correct, but is not the expected answer, and will not give any marks. The correct answer is that the function computes the two’s complement of the input. (Or any equivalent description.) Similarly, for example2 below, the expected answer is that the function returns bit b of a. Saying that it shifts the number 1 by b bits to the left and returns the result of anding that with a is not suffiffifficient.
uint32_t example2(uint32_t a, uint32_t b) {
return (1<
}
For all questions, assume that signed numbers are represented using two’s complement. Moreover, contrary to the C standard, for this assignment the behaviour of integer overflflow is well defifined to wrap around. For example, MAX INT32+1 results in MIN INT32.
Question 1 — 6%
int32_t f1(int32_t a) {
return a & -a;
}
Question 2 — 6%
int32_t f2(int32_t a) {
return (a | -a)>>31;
}
Question 3 — 6%
uint32_t f3(uint32_t a, uint32_t b, int32_t c, int32_t d) {
c ˆ= d;
c = (c | -c) >> 31;
return (a & ∼c) | (b & c);
}
Question 4 — 6%
uint8_t f4(uint8_t a, uint8_t b) {
uint8_t c;
c = (a & b) << 1; a ˆ= b;
b = (a & c) << 1; a ˆ= c;
c = (a & b) << 1; a ˆ= b;
b = (a & c) << 1; a ˆ= c;
c = (a & b) << 1; a ˆ= b;
b = (a & c) << 1; a ˆ= c;
c = (a & b) << 1; a ˆ= b;
b = (a & c) << 1; a ˆ= c;
return a;
}
Part 2 — 76% (70% for COMP SCI 7307)
In this part you are asked to implement a library that performs basic arithmetic with integers of arbitrary lengths, called bignums.
The library provides one abstract data structure bn t, which is a pointer to the (externally abstract) struct bn. The functions operating on this structure are described below. This interface is defifined in the fifile bn.h. The fifile bn.c provides an implementation of bn alloc() and bn toString(). It also includes the skeletons of the other fifive functions (bn free(), bn add(), bn sub(), bn mul(), and bn fromString()), which you should implement.
struct bn
The fifile bn.c defifines the bignum structure struct bn as:
struct bn {
int bn_len;
int bn_size;
int bn_sign;
2uint16_t *bn_data;
};
Use Example
The example below shows a program that uses the library to calculate the fifirst 100 elements of the Fibonacci sequence.
Part 3 — 6% (COMP SCI 7307 only)
Submission Instructions
You should submit a .tar or a .tgz archive. The archive should contain a single directory, whose name is your student a-number. In that directory, we expect to fifind four items: