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 defined in the file bn.h. The file bn.c provides an implementation of bn alloc() and bn toString(). It also includes the skeletons of the other five functions (bn free(), bn add(), bn sub(), bn mul(), and bn fromString()), which you should implement.
• bn t bn alloc(void) Allocates a new bignum and initialises it to (positive) 0. Returns NULL if not enough resources are available.
• void bn free(bn t bn) Frees all the resources associated with the bignum bn.
• int bnadd(bnt result, bnt a, bnt b)Addsthebignumsaandbandplacesthesum in result. Returns 0 if completed successfully and −1 otherwise. Note that result may be the
same bignum as a or b.
• int bn sub(bn t result, bn t a, bn t b) Subtracts the bignum b from a and places the
difference in result. Returns 0 if completed successfully and −1 otherwise. Note that result may
be the same bignum as a or b.
• int bn mul(bn t result, bn t a, bn t b) Multiplies the bignums a and b and places the
product in result. Returns 0 if completed successfully and −1 otherwise. Note that result may
be the same bignum as a or b.
• int bn fromString(bn t bn, const char *str) Read the decimal number in the string
str and stores its value in bn. Returns 0 if completed successfully and −1 otherwise.
• int bn toString(bn t bn, char *buf, int buflen) Converts a bignum bn to a string. including the terminating NUL character. If buflen is large enough to store the converted string, the function stores the string in buf and returns 0. Otherwise, buf is not changed and the return value is the number of characters required to store the string representation, The function returns a negative
number in case of error.
struct bn
The file bn.c defines the bignum structure struct bn as:
struct bn {
int bn_len;
int bn_size;
int bn_sign;
2
uint16_t *bn_data;
};
The fields of the structure are:
• bn len The length (number of digits) of the number represented by the structure.
• bn data An array that stores the values of the digits of the number.
• bn sign The sign of the number. The value of the sign is 1 for positive numbers and −1 for negative
numbers.
• bn size The number of digits allocated in bn data.
The number is reprsented as a sequence of digits in radix (base) 216 = 65536. That is, if s is the value of
bn sign, l the value of bn len, and di the value of the ith element in bn data (i.e. bn data[i]), then
the value represented by the structure is given by: s · l−1(216)idi. i=0
Use Example
The example below shows a program that uses the library to calculate the first 100 elements of the Fibonacci sequence.
#include
#include “bn.h”
int main() {
char buf[1000];
bn_t a = bn_alloc();
bn_t b = bn_alloc();
bn_fromString(a, “0”);
bn_fromString(b, “1”);
for (int i = 0; i < 100; i++) {
bn_toString(a, buf, sizeof(buf));
printf("%2d: %s\n", i, buf);
bn_add(a, a, b);
bn_t t = a;
a = b;
b = t;
}
Part 3 — 6% (COMP SCI 7307 only)
Note: This part is only for Masters students taking COMP SCI 7307.
Use a subset of the C language to implement the function uint32 t mul(uint16 t a, uint16 t b) ,
which calculates the product of a and b. You are only allowed to use the following subset of the language: • Variables of types uint16 t and uint32 t.
• The binary operators +, &, |, ˆ, ==.
• The ternary operator ?:.
• The assignment operator =, as well as its combination with other allowed operators, e.g. +=, &=, etc. • The return statement.
3
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 find four items:
• A text file named info.txt, which contains two lines. The first line is your name, and the second is your student a-number.
• A PDF document named assignment4.pdf, which contains the answers to Questions 1–4. The file should be typed-up, i.e. scanning a handwritten paper is not acceptable. Also, the file must be a PDF document. Text or Word documents are not acceptable, even if you changed the extension to .pdf. The file should also include the answer to Part 3, if you did that.
• A folder named part2 with the implementation of your bignum library. Typing make in this folder should build libbn.so, which contains an implementation of all of the required functions. Note that we plan to look at your code, so please make sure it is readable.
Soundness Test: We will provide a soundness test script to test your submission. If your submission does not pass a soundness test it will not be marked and will be graded as zero.
4