程序代写代做代考 algorithm ./bignums/BigNum-3/makefile

./bignums/BigNum-3/makefile

./bignums/BigNum-3/bn.h

./bignums/BigNum-3/calc.c

./bignums/BigNum-3/bn.c

./bignums/BigNum-5/bn.h

./bignums/BigNum-5/calc.c

./bignums/BigNum-5/Makefile

./bignums/BigNum-5/bn_stack.c

./bignums/BigNum-5/bn_stack.h

./bignums/BigNum-5/bn.c

./bignums/BigNum-4/calc.h

./bignums/BigNum-4/bn.h

./bignums/BigNum-4/calc.c

./bignums/BigNum-4/Makefile

./bignums/BigNum-4/bn.c

./bignums/BigNum-1/makefile

./bignums/BigNum-1/bn.h

./bignums/BigNum-1/calc.c

./bignums/BigNum-1/bn.c

./bignums/BigNum-2/makefile

./bignums/BigNum-2/._.DS_Store

./bignums/BigNum-2/main.c

./bignums/BigNum-2/bn.h

./bignums/BigNum-2/._bn.c

./bignums/BigNum-2/._bn.h

./bignums/BigNum-2/bn.c

./bignums/BigNum-2/.DS_Store

./bignums/BigNum-8/bn.h

./bignums/BigNum-8/calc.c

./bignums/BigNum-8/Makefile

./bignums/BigNum-8/bn.c

./bignums/BigNum-7/makefile

./bignums/BigNum-7/bn.h

./bignums/BigNum-7/calc.c

./bignums/BigNum-7/bn.c

./bignums/BigNum-6/makefile

./bignums/BigNum-6/._makefile

./bignums/BigNum-6/._calculator.c

./bignums/BigNum-6/stack.c

./bignums/BigNum-6/._stack.c

./bignums/BigNum-6/bn.h

./bignums/BigNum-6/._bn.c

./bignums/BigNum-6/calculator.c

./bignums/BigNum-6/._bn.h

./bignums/BigNum-6/._stack.h

./bignums/BigNum-6/bn.c

./bignums/BigNum-6/stack.h

./bignums/BigNum-0/._.DS_Store

./bignums/BigNum-0/util.h

./bignums/BigNum-0/bn.h

./bignums/BigNum-0/calc.c

./bignums/BigNum-0/Makefile

./bignums/BigNum-0/util.c

./bignums/BigNum-0/bn.c

./bignums/BigNum-0/.DS_Store

./bignums/BigNum-9/main.c

./bignums/BigNum-9/bn.h

./bignums/BigNum-9/Makefile

./bignums/BigNum-9/bn.c

./samples/bn.h

./samples/bn-sample.c

all: .o libbn calc

.o: bn.c calc.c
gcc -Wall -c -o bn.o bn.c
gcc -Wall -c -o calc.o calc.c

libbn: bn.o
ar rcs libbn.a bn.o

calc: calc.o libbn.a
gcc -Wall -o calc calc.o libbn.a

clean:
rm -f calc *.o *.a

#ifndef __BN_H__
#define __BN_H__ 1

typedef struct bn *bn_t;

bn_t bn_alloc();
void bn_free(bn_t bn);

int bn_add(bn_t result, bn_t a, bn_t b);
int bn_sub(bn_t result, bn_t a, bn_t b);
int bn_mul(bn_t result, bn_t a, bn_t b);

int bn_fromString(bn_t bn, const char *s);
int bn_toString(bn_t bn, char *buf, int buflen);

int bn_IAmAnUndergrad();

#endif // __BN_H__

#include
#include
#include
#include
#include
#include

#include “bn.h”

struct Node {
bn_t data;
struct Node *next;
};

struct Node *new_node(bn_t bn) {
struct Node *node = (struct Node *)malloc(sizeof(struct Node));
node->data = bn;
node->next = NULL;
return node;
}

struct Node *root = NULL;

static int parse(char *op) {
char buf[100000];
if(isdigit(op[0]) != 0) {
for(int i = 1; i < strlen(op); i++) { if(isdigit(op[i] == 0)) { return -1; } } bn_t bn_new = bn_alloc(); if(bn_fromString(bn_new, op) != 0) { return -1; } struct Node *node = new_node(bn_new); node->next = root;
root = node;
return 0;
}
else if(strcmp(“+”, op) == 0) {
bn_t result = bn_alloc();
if(root == NULL || root->next == NULL) {
return -1;
}
if(bn_add(result, root->data, root->next->data) != 0) {
return -1;
}
struct Node *temp1 = root;
struct Node *temp2 = root->next;
root = root->next->next;
bn_free(temp1->data);
bn_free(temp2->data);
free(temp1);
free(temp2);
struct Node *node = new_node(result);
node->next = root;
root = node;
return 0;
}
else if(strcmp(“-“, op) == 0) {
bn_t result = bn_alloc();
if(root == NULL || root->next == NULL) {
return -1;
}
if(bn_sub(result, root->next->data, root->data) != 0) {
return -1;
}
struct Node *temp1 = root;
struct Node *temp2 = root->next;
root = root->next->next;
bn_free(temp1->data);
bn_free(temp2->data);
free(temp1);
free(temp2);
struct Node *node = new_node(result);
node->next = root;
root = node;
return 0;
}
else if(strcmp(“*”, op) == 0) {
bn_t result = bn_alloc();
if(root == NULL || root->next == NULL) {
return -1;
}
if(bn_mul(result, root->data, root->next->data) != 0) {
return -1;
}
struct Node *temp1 = root;
struct Node *temp2 = root->next;
root = root->next->next;
bn_free(temp1->data);
bn_free(temp2->data);
free(temp1);
free(temp2);
struct Node *node = new_node(result);
node->next = root;
root = node;
return 0;
}
else if(strcmp(“dup”, op) == 0) {
bn_t bn_dup = bn_alloc();
if(root == NULL) {
return -1;
}
if(bn_toString(root->data, buf, sizeof(buf)) != 0) {
return -1;
}
if(bn_fromString(bn_dup, buf) != 0) {
return -1;
}
struct Node *node = new_node(bn_dup);
node->next = root;
root = node;
return 0;
}
else if(strcmp(“pop”, op) == 0) {
if(root != NULL) {
struct Node *temp = root;
root = root->next;
bn_free(temp->data);
free(temp);
return 0;
}
else {
return -1;
}
}
else if(strcmp(“print”, op) == 0) {
if(root == NULL) {
return -1;
}
if(bn_toString(root->data, buf, sizeof(buf)) != 0) {
return -1;
}
printf(“%s\n”, buf);
return 0;
}
else if(strcmp(“swap”, op) == 0) {
if(root == NULL || root->next == NULL) {
return -1;
}
struct Node *temp_r = root;
struct Node *temp_n = root->next->next;
root = root->next;
root->next = temp_r;
root->next->next = temp_n;
return 0;
}
else if(strcmp(“dump”, op) == 0) {
struct Node *temp = root;
while(temp != NULL) {
if(bn_toString(temp->data, buf, sizeof(buf)) != 0) {
return -1;
}
printf(“%s\n”, buf);
temp = temp->next;
}
return 0;
}
else if(strcmp(“clear”, op) == 0) {
while(root != NULL) {
struct Node *temp = root;
root = root->next;
bn_free(temp->data);
free(temp);
}
return 0;
}
else {
return -1;
}
}

int main() {
char buf[10000];
char *token;
char delim[] = ” \t\n\v\f\r”;
while(fgets(buf, sizeof(buf), stdin) != NULL) {
token = strtok(buf, delim);
while(token != NULL) {
if(parse(token) == -1) {
parse(“clear”);
fprintf(stderr, “Error\n”);
return -1;
}
token = strtok(NULL, delim);
}
}
parse(“clear”);
return 0;
}

#include
#include
#include
#include
#include
#include

#include “bn.h”

struct bn {
int bn_len;
int bn_size;
int bn_sign;
uint16_t *bn_data;
};

static int bn_resize(bn_t bn, int size) {
if (size <= bn->bn_size)
return 0;
uint16_t *data = (uint16_t *)realloc(bn->bn_data, size * sizeof(uint16_t));
if (data == NULL)
return -1;
for (int i = bn->bn_size; i < size; i++) data[i] = 0; bn->bn_data = data;
bn->bn_size = size;
return 1;
}

static int bn_reallen(bn_t bn) {
int l = bn->bn_len;
while (l– > 0) {
if (bn->bn_data[l] != 0)
return l+1;
}
return 0;
}

static void dbn_push(bn_t bn, uint8_t data) {
uint32_t carry = data;
for (int j = 0; j < bn->bn_len; j++) {
carry += bn->bn_data[j] * 256;
bn->bn_data[j] = carry % 10000;
carry = carry / 10000;
}
if (carry != 0)
bn->bn_data[bn->bn_len++] = carry;
}

static bn_t todec(bn_t bn) {
int binlen = bn_reallen(bn);
int declen = ((binlen + 3)/4) * 5;
bn_t dbn = bn_alloc();
if (dbn == NULL)
return NULL;
bn_resize(dbn, declen);
for (int i = binlen; i–; ) {
dbn_push(dbn, bn->bn_data[i] >> 8);
dbn_push(dbn, bn->bn_data[i] & 0xFF);
}
return dbn;
}

bn_t bn_alloc(void) {
bn_t bn = (bn_t)malloc(sizeof(struct bn));
if (bn == NULL)
return NULL;
bn->bn_data = (uint16_t *)calloc(1, sizeof(uint16_t));
if (bn->bn_data == NULL) {
free(bn);
return NULL;
}
bn->bn_len = 0;
bn->bn_size = 1;
bn->bn_sign = 1;
return bn;
}

void bn_free(bn_t bn) {
free(bn->bn_data);
free(bn);
}

int bn_add(bn_t result, bn_t a, bn_t b) {
if(result == NULL || a == NULL || b == NULL) {
return -1;
}
int len = (a->bn_len >= b->bn_len) ? a->bn_len : b->bn_len;
result->bn_len = len+1;
if(bn_resize(result, len+1) == -1) {
return -1;
}
int add = 0;
for(int i = 0; i < len; i++) { if(a->bn_len > i) {
add += a->bn_data[i];
}
if(b->bn_len > i) {
add += b->bn_data[i];
}
if(add >= 65536) {
add -= 65536;
result->bn_data[i] = add;
add = 1;
}
else {
result->bn_data[i] = add;
add = 0;
}
}
result->bn_data[len] = add;
return 0;
}

int bn_sub(bn_t result, bn_t a, bn_t b) {
if(result == NULL || a == NULL || b == NULL) {
return -1;
}
int len = (a->bn_len >= b->bn_len) ? a->bn_len : b->bn_len;
result->bn_len = len;
if(bn_resize(result, len) == -1) {
return -1;
}
int sub = 0;
for(int i = 0; i < len; i++) { if(a->bn_len > i) {
sub += a->bn_data[i];
}
if(b->bn_len > i) {
sub -= b->bn_data[i];
}
if(sub < 0) { sub += 65536; result->bn_data[i] = sub;
sub = -1;
}
else {
result->bn_data[i] = sub;
sub = 0;
}
}
if(sub == -1) {
for(int i = 0; i < len; i++) { result->bn_data[i] = 0;
}
result->bn_len = 1;
}
return 0;
}

int bn_mul(bn_t result, bn_t a, bn_t b) {
if(result == NULL || a == NULL || b == NULL) {
return -1;
}
int len = (a->bn_len >= b->bn_len) ? a->bn_len : b->bn_len;
result->bn_len = len*2;
if(bn_resize(result, len*2) == -1) {
return -1;
}
uint32_t *temp = (uint32_t *)calloc(len*2, sizeof(uint32_t));
if(temp == NULL) {
return -1;
}
for(int i = 0; i < a->bn_len; i++) {
for(int j = 0; j < b->bn_len; j++) {
if(a->bn_data[i] == 0 || b->bn_data[j] == 0) {}
else {
temp[i+j] += a->bn_data[i] * b->bn_data[j];
temp[i+j+1] += temp[i+j] / 65536;
temp[i+j] = temp[i+j] % 65536;
}
}
}
for(int i = 0; i < 2*len-1; i++) { temp[i+1] += temp[i] / 65536; temp[i] = temp[i] % 65536; result->bn_data[i] = temp[i];
}
result->bn_data[2*len-1] = temp[2*len-1];
free(temp);
return 0;
}

int bn_fromString(bn_t bn, const char *s) {
int l = strlen(s);
if(bn == NULL || l == 0) {
return -1;
}
uint32_t *arr = (uint32_t *)calloc(l, sizeof(uint32_t));
if(arr == NULL) {
return -1;
}
int number, temp;
for(int i = 0; i < l; i++) { for(int j = 0; j < l; j++) { arr[j] *= 10; } number = s[i] - '0'; temp = arr[0] + number; arr[0] = temp % 65536; if(l > 1) {
arr[1] += temp / 65536;
if(l > 2) {
for(int j = 1; j < l-1; j++) { temp = arr[j]; arr[j] = temp % 65536; arr[j+1] += temp / 65536; } } } } int len = l - 1; while(1) { if(arr[len] != 0) { break; } else if(len == 0) { break; } else { len--; } } len++; if(bn_resize(bn, len) == -1) { return -1; } bn->bn_len = len;
for(int i = 0; i < len; i++) { bn->bn_data[i] = arr[i];
}
free(arr);
return 0;
}

int bn_toString(bn_t bn, char *buf, int buflen) {
bn_t dbn = todec(bn);
if (dbn == NULL)
return -1;
int dlen = dbn->bn_len;
uint16_t *data = dbn->bn_data;

int requiredlen;
if (dlen == 0)
requiredlen = 2;
else
requiredlen = 2 + (bn->bn_sign < 0) + (dlen - 1) * 4 + (data[dlen-1] > 999) +
(data[dlen-1] > 99) +
(data[dlen – 1] > 9);
if (requiredlen > buflen) {
bn_free(dbn);
return requiredlen;
}

char *p = buf;

if (dlen == 0) {
*p++ = ‘0’;
} else {
if (bn->bn_sign < 0) *p++ = '-'; dlen--; if (data[dlen] > 999)
*p++ = ‘0’ + (data[dlen] / 1000) % 10;
if (data[dlen] > 99)
*p++ = ‘0’ + (data[dlen] / 100) % 10;
if (data[dlen] > 9)
*p++ = ‘0’ + (data[dlen] / 10) % 10;
*p++ = ‘0’ + data[dlen] % 10;
while (dlen–) {
*p++ = ‘0’ + (data[dlen] / 1000) % 10;
*p++ = ‘0’ + (data[dlen] / 100) % 10;
*p++ = ‘0’ + (data[dlen] / 10) % 10;
*p++ = ‘0’ + (data[dlen] / 1) % 10;
}
}
*p = ‘\0’;
bn_free(dbn);
return 0;
}

int bn_IAmAnUndergrad() {
return 1;
}

#ifndef __BN_H__
#define __BN_H__ 1

typedef struct bn *bn_t;

bn_t bn_alloc();
void bn_free(bn_t bn);

int bn_add(bn_t result, bn_t a, bn_t b);
int bn_sub(bn_t result, bn_t a, bn_t b);
int bn_mul(bn_t result, bn_t a, bn_t b);

int bn_fromString(bn_t bn, const char *s);
int bn_toString(bn_t bn, char *buf, int buflen);

int bn_sqr(bn_t result, bn_t a);
int bn_div(bn_t quot, bn_t rem, bn_t a, bn_t b);

int bn_IAmAnUndergrad();

#endif // __BN_H__

#define _GNU_SOURCE
#include
#include
#include

#include “bn.h”
#include “bn_stack.h”

#define DEFAULT_SIZE 1024

//add a new number into stack
int add_num(bn_s stack, const char *s){
bn_t a = bn_alloc();
if(a == NULL){
fprintf(stderr,”Error: failed to allocate new bignum\n”);
return -1;
}
if(bn_fromString(a, s) == -1){
fprintf(stderr,”Error: failed to read number %s\n”, s);
return -1;
}
if(stack_push(stack, a) == -1){
fprintf(stderr,”Error: failed to push bignum in stack\n”);
return -1;
}
return 0;
}

//calculate and push back the result
//if calculate has any error, push back the original number
int calc(bn_s stack, const char *op){
bn_t a = stack_top(stack);
if(a == NULL){
fprintf(stderr,”Error: don’t have enough number for calculate\n”);
return -1;
}
stack_pop(stack);
bn_t b = stack_top(stack);
if(b == NULL){
stack_push(stack, a);
fprintf(stderr,”Error: don’t have enough number for calculate\n”);
return -1;
}
stack_pop(stack);
bn_t result = bn_alloc();
if(strcmp(op, “+”) == 0){
if(bn_add(result, a, b) == -1){
stack_push(stack, b);
stack_push(stack, a);
fprintf(stderr,”Error: failed to calculate sum\n”);
return -1;
}
}
else if(strcmp(op, “-“) == 0){
if(bn_sub(result, b, a) == -1){
stack_push(stack, b);
stack_push(stack, a);
fprintf(stderr,”Error: failed to calculate difference\n”);
return -1;
}
}
else if(strcmp(op, “*”) == 0){
if(bn_mul(result, a, b) == -1){
stack_push(stack, b);
stack_push(stack, a);
fprintf(stderr,”Error: failed to calculate product\n”);
return -1;
}
}
stack_push(stack, result);
return 0;
}

//function for dup
int calc_dup(bn_s stack){
bn_t a = stack_top(stack);
if(a == NULL){
fprintf(stderr,”Error: stack is empty, can’t dup\n”);
return -1;
}
if(stack_push(stack, a) == -1){
fprintf(stderr,”Error: failed to dup\n”);
return -1;
}
return 0;
}

//function for pop
int calc_pop(bn_s stack){
if(stack_pop(stack) == -1){
fprintf(stderr,”Error: stack is empty, can’t pop\n”);
return -1;
}
return 0;
}

//function for print. Buffer size is dynamic
int calc_print(bn_s stack){
bn_t a = stack_top(stack);
if(a == NULL){
fprintf(stderr,”Error: stack is empty, can’t print\n”);
return -1;
}
char *buf = (char*)malloc(sizeof(char*)*DEFAULT_SIZE);
int status = bn_toString(a, buf, DEFAULT_SIZE);
while(status != 0){
if(status == -1){
fprintf(stderr,”Error: failed to convert bignum to string\n”);
return -1;
}
buf = (char*)realloc(buf,sizeof(char*)*status);
status = bn_toString(a, buf, status);
}
printf(“%s\n”, buf);
free(buf);
return 0;
}

//function for swap.
int calc_swap(bn_s stack){
bn_t a = stack_top(stack);
if(a == NULL){
fprintf(stderr,”Error: don’t have enough number for swap\n”);
return -1;
}
stack_pop(stack);
bn_t b = stack_top(stack);
if(b == NULL){
stack_push(stack, a);
fprintf(stderr,”Error: don’t have enough number for swap\n”);
return -1;
}
stack_pop(stack);
stack_push(stack, a);
stack_push(stack, b);
return 0;
}

//function for dump
int calc_dump(bn_s stack){
if(stack_print(stack) == -1)
return -1;
return 0;
}

void calc_clear(bn_s stack){
stack_clear(stack);
}

//main function
//read stdin via getline() because getline() has dynamic buffer size
//use strtok to split input line
//use strspn to check the each char of token is digit
int main(){
bn_s stack = init_stack();
char* line = NULL;
size_t len = 0;
ssize_t read;
while ((read = getline(&line, &len, stdin)) != -1){
char* token = strtok(line,”\n”);
token = strtok(token,” “);
while(token){
if(strcmp(token, “+”)==0 ||
strcmp(token, “-“)==0 ||
strcmp(token, “*”)==0){
calc(stack, token);
}
else if(strcmp(token, “dup”)==0){
calc_dup(stack);
}
else if(strcmp(token, “pop”)==0){
calc_pop(stack);
}
else if(strcmp(token, “print”)==0){
calc_print(stack);
}
else if(strcmp(token, “swap”)==0){
calc_swap(stack);
}
else if(strcmp(token, “dump”)==0){
calc_dump(stack);
}
else if(strcmp(token, “clear”)==0){
calc_clear(stack);
}
else if(strspn(token, “0123456789”)==strlen(token)){
add_num(stack,token);
}
else{
fprintf(stderr,”Error: undefined word %s\n”, token);
}
token = strtok(NULL,” “);
}
}
free(line);
return 0;
}

all: calc

bn.o: bn.h bn.c
gcc -std=c99 -Wall -c bn.c -o bn.o

libbn.a: bn.o
ar cr libbn.a bn.o

bn_stack.o: bn_stack.h bn_stack.c libbn.a
gcc -std=c99 -Wall -c bn_stack.c -o bn_stack.o

calc.o: calc.c bn_stack.o
gcc -std=c99 -Wall -c calc.c -o calc.o

calc: calc.o bn_stack.o libbn.a
gcc -std=c99 -Wall calc.o bn_stack.o -o calc -L. -lbn -lm

clean:
rm -f *.o *.a calc

#include
#include

#include “bn_stack.h”

#define DEFAULT_SIZE 1024

//Implement a bignum stack base on Linked list

struct bn_stack {
bn_t data;
bn_s next;
};

//allocate memory for stack head
bn_s init_stack(){
bn_s stack = (bn_s)malloc(sizeof(struct bn_stack));
if(stack == NULL)
return NULL;
stack->next = NULL;
return stack;
}

//free the stack
void stack_free(bn_s stack){
stack_clear(stack);
free(stack);
}

//push a bignum into stack
int stack_push(bn_s stack, bn_t bn){
bn_s node = init_stack();
if(node == NULL){
return -1;
}
node->data = bn;
node->next = stack->next;
stack->next = node;
return 0;
}

//pop the top node from stack
int stack_pop(bn_s stack){
bn_s node = stack->next;
if(node == NULL){
return -1;
}
stack->next = node ->next;
free(node);
return 0;
}

//return the bignum in the top of stack
bn_t stack_top(bn_s stack){
bn_s node = stack->next;
if(node == NULL){
return NULL;
}
return node->data;
}

//print all bignum in the stack
int stack_print(bn_s stack){
bn_s p = stack->next;
while(p!=NULL){
char *buf = (char*)malloc(sizeof(char*)*DEFAULT_SIZE);
int status = bn_toString(p->data, buf, DEFAULT_SIZE);
while(status != 0){
if(status == -1){
fprintf(stderr,”Error: failed to convert bignum to string\n”);
return -1;
}
buf = (char*)realloc(buf,sizeof(char*)*status);
status = bn_toString(p->data, buf, status);
}
printf(“%s\n”, buf);
free(buf);
p = p->next;
}
return 0;
}

//clear the stack
void stack_clear(bn_s stack){
while(stack->next != NULL){
bn_free(stack_top(stack));
stack_pop(stack);
}
}

#include “bn.h”

#ifndef __BN_STACK_H__
#define __BN_STACK_H__ 1

typedef struct bn_stack *bn_s;

bn_s init_stack();
void stack_free(bn_s stack);

int stack_push(bn_s stack, bn_t bn);
int stack_pop(bn_s stack);
bn_t stack_top(bn_s stack);
int stack_print(bn_s stack);
void stack_clear(bn_s stack);

#endif // __BN_H__

#include
#include
#include
#include
#include
#include

#include “bn.h”

struct bn {
int bn_len;
int bn_size;
int bn_sign;
uint16_t *bn_data;
};

static int bn_reallen(bn_t bn) {
int l = bn->bn_len;
while (l– > 0) {
if (bn->bn_data[l] != 0)
return l+1;
}
return 0;
}

//push data to binary bignum. Same as dbn_push()
static void bn_push(bn_t bn, uint16_t data){
uint32_t carry = data;
for(int j = 0; j < bn->bn_len; j++){
carry += bn->bn_data[j] * 10000;
bn->bn_data[j] = carry % 65536;
carry = carry / 65536;
}
if(carry != 0)
bn->bn_data[bn->bn_len++] = carry;
}

//convert decimal bignum to binary bignum, same as todec()
static bn_t tobin(bn_t dbn) {
int len = bn_reallen(dbn);
bn_t bn = bn_alloc();
if(bn == NULL)
return NULL;
if(bn_resize(bn,len) == -1){
free(bn);
return NULL;
}
for(int i = len; i–; ){
bn_push(bn, dbn->bn_data[i]);
}
return bn;
}

//pow function implement by me.
static int myPow(int base, int exponent){
int result = 1;
for(int i=0; ibn_len;
int tempSize = a->bn_size;
int tempSign = a->bn_sign;
uint16_t * tempData = a->bn_data;
a->bn_len = b->bn_len;
a->bn_size = b->bn_size;
a->bn_sign = b->bn_sign;
a->bn_data = b->bn_data;
b->bn_len = tempLen;
b->bn_size = tempSize;
b->bn_sign = tempSign;
b->bn_data = tempData;
bn_free(b);
}

//function for free bignum
void bn_free(bn_t bn) {
int l = bn->bn_len;
memset(bn->bn_data, 0, l*sizeof(uint16_t));
free(bn->bn_data);
bn->bn_len = 0;
bn->bn_size = 0;
bn->bn_sign = 0;
free(bn);
}

int bn_add(bn_t result, bn_t a, bn_t b){
int alen = bn_reallen(a);
int blen = bn_reallen(b);
int newlen = alen>blen?alen:blen;
if(newlen < INT_MAX) newlen++; bn_t newbn = bn_alloc(); if(newbn == NULL) return -1; if(bn_resize(newbn,newlen) == -1){ bn_free(newbn); return -1; } uint32_t carry = 0; for (int i = 0; i < newlen; i++) { uint16_t adata = ibn_data[i]:0;
uint16_t bdata = ibn_data[i]:0;
carry += adata + bdata;
newbn->bn_data[i] = carry % 65536;
carry = carry / 65536;
}
if(carry == 0){
bn_copy(result,newbn);
result->bn_len = result->bn_size;
result->bn_len = bn_reallen(result);
return 0;
}
else{
bn_free(newbn);
return -1;
}
}

int bn_sub(bn_t result, bn_t a, bn_t b) {
int alen = bn_reallen(a);
int blen = bn_reallen(b);
int newlen = alen>blen?alen:blen;
bn_t newbn = bn_alloc();
if(newbn == NULL)
return -1;
if(bn_resize(newbn,newlen) == -1){
free(newbn);
return -1;
}
int32_t carry = 0;
for (int i = 0; i < newlen; i++) { uint16_t adata = ibn_data[i]:0;
uint16_t bdata = ibn_data[i]:0;
carry += (signed)adata – (signed)bdata;
newbn->bn_data[i] = carry<0?65536+carry:carry; carry = carry<0?-1:0; } if(carry!=0) { memset(newbn->bn_data, 0, newlen*sizeof(uint16_t));
}
bn_copy(result,newbn);
result->bn_len = result->bn_size;
result->bn_len = bn_reallen(result);
return 0;
}

int bn_mul(bn_t result, bn_t a, bn_t b) {
int alen = bn_reallen(a);
int blen = bn_reallen(b);
long newlen = alen+blen;
if(newlen > INT_MAX)
newlen = INT_MAX;
bn_t newbn = bn_alloc();
if(newbn == NULL)
return -1;
if(bn_resize(newbn,(int)newlen) == -1){
bn_free(newbn);
return -1;
}
bn_t temp = bn_alloc();
if(temp == NULL){
bn_free(newbn);
return -1;
}
if(bn_resize(temp,(int)newlen) == -1){
bn_free(newbn);
bn_free(temp);
return -1;
}
for(int i=0; ibn_data[j] * b->bn_data[i];
temp->bn_data[i+j] = carry % 65536;
carry = carry / 65536;
}
temp->bn_data[i+alen] = carry;
temp->bn_len = temp->bn_size;
temp->bn_len = bn_reallen(temp);
if(bn_add(newbn, newbn, temp)==-1){
bn_free(newbn);
bn_free(temp);
return -1;
}
memset(temp->bn_data, 0, newlen*sizeof(uint16_t));
temp->bn_len = 0;
}
bn_copy(result,newbn);
result->bn_len = result->bn_size;
result->bn_len = bn_reallen(result);
return 0;
}

//Read string to a decimal bignum. Then convert decimal bignum to binary.
int bn_fromString(bn_t bn, const char *s) {
int slen = strlen(s);
int dlen = slen/4+1;
bn_t dbn = bn_alloc();
if (dbn == NULL)
return -1;
if(bn_resize(dbn,dlen) == -1){
free(dbn);
return -1;
}
for(int i=0; ibn_data[(slen-i-1)/4] += digit * myPow(10, (slen-i-1)%4);
}
dbn->bn_len = dbn->bn_size;
dbn->bn_len = bn_reallen(dbn);
bn_t t = bn;
free(t);
bn = tobin(dbn);
if(bn == NULL)
return -1;
return 0;
}

int bn_toString(bn_t bn, char *buf, int buflen) {
bn_t dbn = todec(bn);
if (dbn == NULL)
return -1;
int dlen = dbn->bn_len;
uint16_t *data = dbn->bn_data;

char *p = buf;

int bn_IAmAnUndergrad(void){
return 1;
}

#ifndef __CALC_H__
#define __CALC_H__ 1

typedef struct stack_t *bn_stack;

#endif // __CALC_H__

#ifndef __BN_H__
#define __BN_H__

typedef struct bn *bn_t;

bn_t bn_alloc();
void bn_free(bn_t bn);

int bn_add(bn_t result, bn_t a, bn_t b);
int bn_sub(bn_t result, bn_t a, bn_t b);
int bn_mul(bn_t result, bn_t a, bn_t b);

int bn_fromString(bn_t bn, const char *s);
int bn_toString(bn_t bn, char *buf, int buflen);

int bn_sqr(bn_t result, bn_t a);
int bn_div(bn_t quot, bn_t rem, bn_t a, bn_t b);

#endif // __BN_H__

#include
#include
#include
#include
#include
#include “bn.h”
#include “calc.h”

struct stack_t
{
int top; // Current position of top of stack
int size; // Maximum number of items the stack can hold.
bn_t * array; // Holds bignums data
};

/*
* Allocates a new stack
*/
bn_stack bn_stackAlloc(){
bn_stack stack = (bn_stack) malloc(sizeof( struct stack_t));
if (stack == NULL){
return NULL;
fprintf(stderr, “Error allocating stack\n”);
exit(0);
}
stack->array = (bn_t * )calloc(10, sizeof(bn_t));
if (stack->array == NULL){
free(stack);
return NULL;
fprintf(stderr, “Error allocating stack\n”);
exit(0);
}
stack->top = 0;
stack->size = 10;
return stack;
}
/*
* Creates a bignum from str and puts it on the top of the stack
*/
int push(bn_t bn, bn_stack stack){
// Increase stack size if stack full
if (stack->top + 1 == stack->size){
int newSize = stack->size * 2;
stack->array = realloc(stack->array, newSize * sizeof(bn_t));

if (stack->array == NULL){
bn_free(bn);
fprintf(stderr, “Error could not push to null stack\n”);
return -1;
}
for (int i=stack->size;iarray[i] = 0;
}
stack->size = newSize;
}
stack->top += 1;
stack->array[stack->top] = bn;
return 0;
}

/*
* Removes top value of stack
*/
int pop(bn_stack stack){
if (stack->top > 0){
bn_t result = stack->array[stack->top];

if (result == NULL){
fprintf(stderr, “Error NULL pop result\n”);
exit(0);
}

stack->top -= 1;

// Shrink stack if top below half current capacity (minimum 10)
if ((stack->top == (stack->size+1)/2) && (stack->top > 10)){
stack->array = realloc(stack->array, (stack->size+1)/2 * sizeof(bn_t));
if (stack->array == NULL){
fprintf(stderr, “Error unable to shrink stack\n”);
return -1;
}
stack->size = (stack->size+1)/2;
}
}
else{
fprintf(stderr, “Error cannot pop an empty stack\n”);
return -1;
}
return 0;
}

/*
* Prints the value of the bignum at the top of the stack
*/
int print(bn_stack stack){
if (stack->top > 0){
int bufSize = bn_toString(stack->array[stack->top], “”, 0);
char * buf = (char*) malloc(bufSize * sizeof(char));
bn_toString(stack->array[stack->top], buf, bufSize);
printf(“%s\n”,buf);
free(buf);
}

// Empty stack
else{
fprintf(stderr, “Error cannot print empty stack\n”);
exit(0);
}
return 0;
}

/*
* Helper function that checks if top two stack items are valid for operations
*/
int checkStackTop(bn_stack stack){
int top = stack->top;
if (top < 2){ fprintf(stderr, "Error need at least two items on stack to perform operation\n"); exit(0); } if ((stack->array[stack->top] == NULL) || (stack->array[top-1] == NULL)){
fprintf(stderr, “Error NULL value found in stack\n”);
exit(0);
}
return 1;
}

/*
* Swaps positions of top stack item with item below
*/
int swap(bn_stack stack){
if (checkStackTop(stack) != 1){
fprintf(stderr, “Error not enough numbers to swap\n” );
exit(0);
}
bn_t temp = stack->array[stack->top];
stack->array[stack->top] = stack->array[stack->top-1];
stack->array[stack->top-1] = temp;
return 0;
}
/*
* Prints each item in the stack without altering values
*/
int dump(bn_stack stack){
if (stack->top > 0){
// for (size_t i = stack->top; i>0; i–){
for (size_t i = 0; i < stack->top; i++){
bn_t bn = stack->array[stack->top – i];
if (bn == NULL){
fprintf(stderr, “Error null entry in stack\n”);
exit(0);
}
//Get size of buffer
int bufSize = bn_toString(bn, “”, 0);
char * buf = (char*) malloc(bufSize * sizeof(char));
bn_toString(bn, buf, bufSize);
printf(“%s\n”,buf);
free(buf);
}
}
return 0;
}

/*
* Clears the stack
*/
int clear(bn_stack stack){
free(stack->array);
stack->array = (bn_t *) calloc(10, sizeof(bn_t));
stack->size = 10;
stack->top = 0;
return 0;
}

/*
* Duplicates item on top of stack and places it on top
*/
int dup(bn_stack stack){
// Requires item on stack
if (stack->top > 0){
// Quit if null
if (stack->array[stack->top] == NULL){
fprintf(stderr, “NULL item in stack\n”);
exit(0);
}
bn_t bn = bn_alloc();
bn_t zero = bn_alloc();
bn_add(bn, zero, stack->array[stack->top]);

bn_free(zero);

push(bn, stack);
return 0;
}
else{
fprintf(stderr, “Error cannot duplicate an empty stack\n”);
exit(0);
}
return 0;
}

/*
* Multiplies top stack result with second result
* Places result on top of stack
*/
int mult(bn_stack stack){
int top = stack->top;
if (checkStackTop(stack) !=1){
return -1;
}
bn_t ans = bn_alloc();

if (bn_mul(ans, stack->array[top], stack->array[top-1])==-1){
fprintf(stderr, “Error multiplying\n”);
return -1;
}
pop(stack);
pop(stack);
push(ans, stack);
return 0;
}
/*
* Adds top stack result to second result
* Places result on top of stack
*/
int add(bn_stack stack){
int top = stack->top;
if (checkStackTop(stack) !=1){
return -1;
}
bn_t ans = bn_alloc();
if (bn_add(ans, stack->array[top], stack->array[top-1])==-1){
fprintf(stderr, “Error adding\n”);
return -1;
}
pop(stack);
pop(stack);
push(ans, stack);
return 0;
}
/*
* Subtracts top stack result from second stack result
* Places result on top of stack
*/
int sub(bn_stack stack){
int top = stack->top;
if (checkStackTop(stack) !=1){
return -1;
}
bn_t ans = bn_alloc();
if (bn_sub(ans, stack->array[top-1], stack->array[top]) == -1){
fprintf(stderr, “Error subtracting\n”);
return -1;
}
pop(stack);
pop(stack);
push(ans, stack);
return 0;
}
/**
* Reads a command string and performs the appropriate action
*/
int readString(char* str, bn_stack stack){

if (strcmp(“*”, str ) == 0){
return mult(stack);
}
if (strcmp(“+”, str)== 0){
return add(stack);
}
if (strcmp(“-“, str) == 0){
return sub(stack);
}
if (strcmp(“dup”, str) == 0){
return dup(stack);
}
if (strcmp(“pop”, str) == 0){
return pop(stack);
}
if (strcmp(“print”, str) == 0){
return print(stack);
}
if (strcmp(“swap”, str) == 0){
return swap(stack);
}
if (strcmp(“dump”, str) == 0){
return dump(stack);
}
if (strcmp(“clear”, str) == 0){
return clear(stack);
}
else{
bn_t bn = bn_alloc();
if (bn_fromString(bn, str) != 0){
bn_free(bn);
fprintf(stderr, “Error unrecognised string %s\n”,str);
exit(0);
}
int result = push(bn, stack);
return result;
}
}
/*
* Reads input from file and converts it to a string
*/
static char * getInputString(FILE * pf, size_t size){
char *str;
int ch;
size_t len = 0;
str = realloc(NULL, size);
if (!str){
return str;
}
while (EOF!=(ch = fgetc(pf))){
str[len++] = ch;
if(len == size){
str = realloc(str, size+=16);
if(!str){
return str;
}
}
}
str[len++] = ‘\0’;
return realloc(str, len);
}

int main(){

bn_stack stack = bn_stackAlloc();

char * str;
str = getInputString(stdin, 1) ;
char * pch;

// Parse the string
pch = strtok (str, ” \t\n\v\f\r”);

while (pch != NULL)
{
if (readString(pch, stack) == -1){
fprintf(stderr, “Error detected\n”);
exit(0);
}
pch = strtok (NULL, ” \t\n\v\f\r”);
}

free(stack->array);
free(stack);
free(pch);
free(str);

return 0;
}

all: libbn.a calc

libbn.a: bn.c bn.h
gcc –std=gnu99 -Wall -O2 -c -o libbn.a bn.c

calc: calc.c calc.h bn.c
gcc –std=gnu99 -O2 -Wall -o calc calc.c bn.c

clean:
rm libbn.a calc

#include
#include
#include
#include
#include

#include “bn.h”

#define MAX(x, y) (((x) > (y)) ? (x) : (y))
#define MIN(x, y) (((x) < (y)) ? (x) : (y)) struct bn { int bn_len; int bn_size; int bn_sign; uint16_t *bn_data; }; // // Prints contents of bignum struct (used for debugging) // static int bn_print(bn_t bn){ // printf("bn_size: %d\n", bn->bn_size);
// printf(“bn_sign %d\n”, bn->bn_sign);
// printf(“bn_len %d\n”, bn->bn_len);
// for (int i=0;ibn_size;i++){
// printf(“bn_data[%d] %d\n”,i, bn->bn_data[i]);
// }
// return 0;
// }

void bn_free(bn_t bn){
free(bn->bn_data);
free(bn);
}

// Resizes allocation of bn->data to size
static int bn_resize(bn_t bn, int size) {
// Given size is less or equal to the size of bn
if (size <= bn->bn_size)
return 0;
// Resizes data to size
uint16_t *data = (uint16_t *)realloc(bn->bn_data, size * sizeof(uint16_t));
if (data == NULL)
return -1;
// Zeroes out data of new section
for (int i = bn->bn_size; i < size; i++) data[i] = 0; // Updates bn data to newly sized data bn->bn_data = data;
// Updates size of bn to new size
bn->bn_size = size;
return 1;
}

// Returns real length of a bignum (ignores leading zeros)
static int bn_reallen(bn_t bn) {
int l = bn->bn_len;
while (l– > 0) {
if (bn->bn_data[l] != 0){
return l+1;
}
}
return 0;
}

// Decimal bignum push?
static void dbn_push(bn_t bn, uint8_t data) {
// Carry data
uint32_t carry = data;
for (int j = 0; j < bn->bn_len; j++) {
carry += bn->bn_data[j] * 256;
bn->bn_data[j] = carry % 10000;
carry = carry / 10000;
}
if (carry != 0)
bn->bn_data[bn->bn_len++] = carry;
}

static bn_t todec(bn_t bn) {
//Binary length
int binlen = bn_reallen(bn);
// decimal length
int declen = ((binlen + 3)/4) * 5;
bn_t dbn = bn_alloc();
if (dbn == NULL)
return NULL;
bn_resize(dbn, declen);
for (int i = binlen; i–; ) {
dbn_push(dbn, bn->bn_data[i] >> 8);
dbn_push(dbn, bn->bn_data[i] & 0xFF);
}
return dbn;
}

// Allocates a bn to default value 0
bn_t bn_alloc(void) {
// Allocate bn
bn_t bn = (bn_t)malloc(sizeof(struct bn));
if (bn == NULL)
return NULL;
// Allocate bn->data
bn->bn_data = (uint16_t *)calloc(1, sizeof(uint16_t));
if (bn->bn_data == NULL) {
free(bn);
return NULL;
}
bn->bn_len = 0;
bn->bn_size = 1;
bn->bn_sign = 1;
return bn;
}

// Returns 1 if character is ASCII numeral
// Otherwise returns 0
static int isNumber(char c){
// ASCII numeric character 0-9
if (c >= 48 && c <= 57){ return 1; } return 0; } /* bn Bignum to be converted to text *buf String buffer buflen Length of buffer return 0 if conversion successful, otherwise Number of chars needed to store bn as a string */ int bn_toString(bn_t bn, char *buf, int buflen) { bn_t dbn = todec(bn); if (dbn == NULL) return -1; int dlen = dbn->bn_len;
uint16_t *data = dbn->bn_data;
int requiredlen;

if (dlen == 0){
requiredlen = 2;
}
else{
requiredlen = 2 + (bn->bn_sign < 0) + (dlen - 1) * 4 + (data[dlen-1] > 999) +
(data[dlen-1] > 99) +
(data[dlen – 1] > 9);
}

if (requiredlen > buflen) {
bn_free(dbn);
return requiredlen;
}

char *p = buf;

// Changes sign of bn to be negative
static void bn_makeNegative(bn_t bn){
bn->bn_sign = -1;
}

/*
* Chops leading zeros from most significant bit
* of bn to first non-zero digit
*/
static int bn_shrink(bn_t bn){
int reallen = bn_reallen(bn);

if (reallen == 0) reallen = 1;
//printf(“IN SHRINK: reallen %d\n”, reallen); //TODO DEBUG
if (reallen > 0){
uint16_t * data = (uint16_t *) realloc(bn->bn_data, (reallen) * sizeof(uint16_t));
if (data == NULL){
return -1;
}
bn->bn_data = data;
bn->bn_len = reallen;
bn->bn_size = reallen;
}

// Special case zero, cannot be negative
if (bn->bn_size == 1 && bn->bn_data[0] == 0){
bn->bn_len = 0;
bn_makePositive(bn);
}
return 0;
}

static int bn_grow(bn_t bn, int size){

if (bn->bn_size > size){
return -1;
}
uint16_t * data = (uint16_t *) realloc(bn->bn_data, size * sizeof(uint16_t));
if (data == NULL){
return -1;
}

bn->bn_data = data;
bn->bn_size = size;

return 1;
}

/*
* Append k zero digits to bignum
* (equivalent to multiplying by 2^k)
*/
static int bn_timesBaseK(bn_t result, bn_t a, int k){
free(result->bn_data);
uint16_t * data = (uint16_t *)calloc(k + a->bn_size, sizeof(uint16_t));
// result->bn_data = (uint16_t *)calloc(k + a->bn_size, sizeof(uint16_t));
if (data == NULL){
free(result);
return -1;
}

for (int i = 0; i < a->bn_size; i++){
data[i+k] = a->bn_data[i];
}
result->bn_data = data;
result->bn_size = a->bn_size + k;
result->bn_len = a->bn_len + k;
return 0;
}

/*
* Splts bignum a at position k/2, producing
* a1 (ceil(k/2) most sig digits) and a0 (k/2 least significant digits)
* Returns 0 if completed successfully, otherwise -1
*/
static int bn_split(bn_t a1, bn_t a0, bn_t a){
// Split at point
int k2 = (a->bn_size+1)/2; // ceil(k/2)
int a1Size = k2;
int a0Size = a->bn_size – k2;

int a1Resize = bn_resize(a1, a1Size);
int a0Resize = bn_resize(a0, a0Size);

if (a1Resize == -1 || a0Resize == -1){
return -1;
}
// Fill a1 with top
for (int i=0; ibn_len;i++){
if (a0Size + i < a->bn_len){
a1->bn_data[i] = a->bn_data[a0Size+i];
// printf(“SPLIT ADDING TO a1: %d from pos %d \n”,a->bn_data[a0Size+i], i);
}

if (i < a0Size) { a0->bn_data[i] = a->bn_data[i];
}
}

a1->bn_size = a1Size;
a0->bn_size = a0Size;
a1->bn_len = MAX(a->bn_len – a0Size, 0);
a0->bn_len = a0Size;
bn_shrink(a0);
bn_shrink(a1);
return 0;
}

/*
* Adds the bignums a and b and places the sum in result
* Returns 0 if successful, otherwise -1
*/
int bn_add(bn_t result, bn_t a, bn_t b){

// Maximum possible number of digits from adding a and b
int maxSize = MAX(a->bn_size, b->bn_size) + 1;

// Attempt to resize result to fit maximum size
int resize = bn_resize(result, maxSize);
// Return error if failed
if (resize == -1){
return -1;
}

long carry = 0;

for (int i = 0; i < maxSize; i++){ // For every digit of a if (i < a->bn_len){
// Add if positive
if (a->bn_sign > 0) {
carry += a->bn_data[i];
}
// Subtract if negative
else {
carry -= a->bn_data[i];
}
}
// For every digit of b
if (i < b->bn_len){
// Add if positive
if (b->bn_sign > 0){
carry += b->bn_data[i];
}
// Subtract if negative
else {
carry -= b->bn_data[i];
}
}
// Put carry into result
result->bn_data[i] = (uint16_t) carry;
// Shift carry for next digit up
carry >>= 16;
}
// If carry ends negative, need to change sign of result
// and apply borrows to whole
if (carry < 0){ carry = 0; for (int i = 0; i < maxSize; i++){ carry -= result->bn_data[i];
result->bn_data[i] = (uint16_t) carry;
carry >>= 16;
}
bn_makeNegative(result);
}
result->bn_len = maxSize;
bn_shrink(result);
return 0;
}

/*
* Substracts the bignums b from a and places the sum in result
* Returns 0 if successful, otherwise -1
*/
int bn_sub(bn_t result, bn_t a, bn_t b){

// Maximum possible number of digits from subtracting a and b
int maxSize = MAX(a->bn_len, b->bn_len) + 1;

// Attempt to resize result to fit maximum size
int resize = bn_resize(result, maxSize);
// Return error if failed
if (resize == -1){
return -1;
}

long carry = 0;

for (int i = 0; i < maxSize; i++){ // For every digit of a if (i < a->bn_len){
// Add if positive
if (a->bn_sign > 0) {
carry += a->bn_data[i];
}
// Subtract if negative
else {
carry -= a->bn_data[i];
}
}
// For every digit of b
if (i < b->bn_len){
// Subtract if positive
if (b->bn_sign > 0){
carry -= b->bn_data[i];
}
// Add if negative
else {
carry += b->bn_data[i];
}
}
// Put carry into result
result->bn_data[i] = (uint16_t) carry;
// Shift carry for next digit up
carry >>= 16;
}
// If carry ends negative, need to change sign of result
// and apply borrows to whole
if (carry < 0){ carry = 0; for (int i = 0; i < maxSize; i++){ carry -= result->bn_data[i];
result->bn_data[i] = (uint16_t) carry;
carry >>= 16;
}
bn_makeNegative(result);
}
result->bn_len = maxSize;
bn_shrink(result);
return 0;
}

/*
* Applies system method of multiplication to a and b
* Places product in result
*/
static int bn_school_mul(bn_t result, bn_t a, bn_t b){
if (bn_resize(result, 2) == -1){
// printf(“failed to resize”);
return -1;

result->bn_len = 1;
result->bn_size = 2;
}
// Multipliers too long
if (a->bn_len > 1 || b->bn_len > 1){
return -1;
}
long carry = a->bn_data[0] * b->bn_data[0];
result->bn_data[0] = (uint16_t) carry;

if ((carry >>=16) != 0){
result->bn_data[1] = carry;
result->bn_len = 2;
}
bn_shrink(result);
return 0;
}

/*
* Mutliplies bignums a and b and places product in result
* Returns 0 if complete, -1 otherwise
*/
int bn_mul(bn_t result, bn_t a, bn_t b){
int signA = a->bn_sign;
int signB = b->bn_sign;

bn_makePositive(a);
bn_makePositive(b);

// Deal with zero case instantly
if (a->bn_len == 0 && a->bn_data[0] == 0)
{
bn_resize(result, 1);
result->bn_data[0] = 0;
result->bn_len = 0;

a->bn_sign = signA;
b->bn_sign = signB;

return 0;
}

if (b->bn_len == 0 && b->bn_data[0] == 0){
bn_resize(result, 1);
result->bn_data[0] = 0;
result->bn_len = 0;

a->bn_sign = signA;
b->bn_sign = signB;

return 0;
}

// Padding numbers with zeros so they have same number of digits
if (a->bn_size != b->bn_size){
int resize = 1;//TODO FIX GROW
if (a->bn_size < b->bn_size){
resize = bn_grow(a, b->bn_size);
}
else {
resize = bn_grow(b, a->bn_size);
}
if (resize == -1)
return -1;
}

// If digit length is 1, base case multiplication
if (a->bn_len <= 1 && b->bn_len <= 1){ if (bn_school_mul(result, a, b)==-1){ return -1; } } // Karatsuba multiplication else{ // Split components of a and b bn_t a1 = bn_alloc(); bn_t a0 = bn_alloc(); bn_t b1 = bn_alloc(); bn_t b0 = bn_alloc(); // Results of component multiplication bn_t r0 = bn_alloc(); bn_t r1 = bn_alloc(); bn_t r2 = bn_alloc(); // Split a and b bn_split(a1, a0, a); bn_split(b1, b0, b); bn_t a0SubA1 = bn_alloc(); bn_t b0SubB1 = bn_alloc(); bn_sub(a0SubA1, a0, a1); bn_sub(b0SubB1, b0, b1); int sign = a0SubA1->bn_sign * b0SubB1->bn_sign * -1;// added -1

bn_makePositive(a0SubA1);
bn_makePositive(b0SubB1);

bn_mul(r2, a0SubA1, b0SubB1);
bn_free(a0SubA1);
bn_free(b0SubB1);

bn_mul(r1, a1, b1);
bn_free(a1);
bn_free(b1);
r2->bn_sign = sign;

bn_t rk = bn_alloc();
bn_add(rk, r2, r1); // Add R1 and R2

bn_free(r2);

bn_mul(r0, a0, b0);
bn_free(a0);
bn_free(b0);
bn_add(rk, rk, r0); // Add R0

int k = a->bn_size – ((a->bn_size + 1)/2);

bn_timesBaseK(result, rk, k); // R^K
bn_free(rk);

bn_add(result, result, r0);
bn_free(r0);
bn_t r2k = bn_alloc();
bn_timesBaseK(r2k, r1, 2*k); //R1^2K
bn_free(r1);

bn_add(result, r2k, result);
bn_free(r2k);

bn_shrink(result);

}

if (signA == signB){
bn_makePositive(result);
}
else{
bn_makeNegative(result);
}

a->bn_sign = signA;
b->bn_sign = signB;

return 0;

}

/**
* Converts a string to a bignum
* Returns 0 if successful, otherwise -1
**/
int bn_fromString(bn_t bn, const char *str){
// Get length of string
// printf(“fromstring: %s\n”, str);

int len = strlen(str);
// No null strings
if (len < 1){ //TODO return -1; } // Length 1 strings must only contain an integer if (len == 1){ if (isNumber(str[0]) == 1){ bn->bn_data[0] = str[0]-‘0’;
bn->bn_len = 1;
return 0;
}
else{
return -1;
}
}

int i = 0;

int sign = 1; // Sign is positive by default

// Negative number
if (str[0] == ‘-‘){
sign = -1;
i = 1;
}

// Positive number
if (str[0] == ‘+’) {
sign = 1;
i = 1;
}

// Numbers larger than 1 digit multiplied by 10
// for each digit
bn_t ten = bn_alloc();
ten->bn_len = 1;
ten->bn_data[0] = 10;

while (ibn_data[0] = str[i] – ‘0’;
temp->bn_len = 1;
bn_add(bn, bn, temp);
bn_free(temp);
i++;
}
bn->bn_sign = sign;

bn_free(ten);

return 0;
}

int bn_IAmAnUndergrad(){
return 0;
}

all: calc

calc: calc.o libbn.a
gcc -std=c99 -L -lb -o calc calc.o libbn.a -Wall

calc.o: calc.c bn.h
gcc -std=c99 -c calc.c -Wall

bn.o: bn.c bn.h
gcc -std=c99 -c bn.c -Wall

libbn.a: bn.o
ar rcs libbn.a bn.o

libs: libbn.a

clean:
rm -f calc *.o *.a

#ifndef __BN_H__
#define __BN_H__ 1
#define MAXUINT16 65535
#define UINT64 18446744073709551616
#define MAXUINT64 18446744073709551615
#define MAX(x, y) ((x >= y) ? x : y)
#define MIN(x, y) ((x >= y) ? y : x)
typedef struct bn *bn_t;

bn_t bn_alloc();
void bn_free(bn_t bn);

int bn_add(bn_t result, bn_t a, bn_t b);
int bn_sub(bn_t result, bn_t a, bn_t b);
int bn_mul(bn_t result, bn_t a, bn_t b);

int bn_fromString(bn_t bn, const char *s);
int bn_toString(bn_t bn, char *buf, int buflen);

int bn_sqr(bn_t result, bn_t a);
int bn_div(bn_t quot, bn_t rem, bn_t a, bn_t b);
int bn_IAmAnUndergrad();

int copyBN(bn_t destBN, bn_t copyBn);

#endif // __BN_H__

#include
#include
#include
#include
#include
#include #include
#include “bn.h”

#define buffer_size 32767
extern int errno;
char *printBuffer;
int bufferLength;
int bufferStatus;

static int status = 0;

// A structure to represent a stack
struct StackNode {
bn_t bn;
struct StackNode* next;
};

static struct StackNode* root = NULL;

struct StackNode* newNode(bn_t this_bn) {
struct StackNode* stackNode = (struct StackNode*) malloc(sizeof(struct StackNode));
stackNode->bn = this_bn;
stackNode->next = NULL;
return stackNode;
}

int isEmpty(struct StackNode* root) {
return !root;
}

int getStackLength(struct StackNode** root) {
if (isEmpty(*root)) return 0;
struct StackNode* temp = *root;
int length = 1;
while (temp->next != NULL)
length++;

return length;
}

void push(struct StackNode** root, bn_t bn) {
struct StackNode* stackNode = newNode(bn);
stackNode->next = *root;
*root = stackNode;
}

bn_t pop(struct StackNode** root) {
if (isEmpty(*root)) { status = -1; return NULL; }
struct StackNode* temp = *root;
*root = (*root)->next;
bn_t popped = temp->bn;
free(temp);
return popped;
}

void dup(struct StackNode** root) {
if (isEmpty(*root)) { status = -1; return; }
bn_t a = pop(root);
bn_t temp = bn_alloc();
if (temp == NULL) { status = -1; return; }
if (copyBN(temp, a) == -1) { status = -1; return; }
push(root, a);
push(root, temp);
}

void swap(struct StackNode** root) {
bn_t a = pop(root);
if (a == NULL) return;
bn_t b = pop(root);
if (b == NULL) return;
push(root, a);
push(root, b);
}

void clear(struct StackNode** root) {
bn_t temp;
while ((*root) != NULL) { temp = pop(root); bn_free(temp); }
}

void printStack(struct StackNode** root) {
if (!isEmpty(*root)) {
bufferStatus = bn_toString((*root)->bn, printBuffer, bufferLength);
while (bufferStatus > 0) {
bufferLength = bufferStatus;
printBuffer = (char*) realloc (printBuffer, bufferLength + 1);
bufferStatus = bn_toString((*root)->bn, printBuffer, bufferLength);
}
if (bufferStatus == -1) { status = -1; return; }
printf(“%s\n”, printBuffer);
}
}

void dump(struct StackNode** root) {
bn_t temp;
struct StackNode* tempNode = *root;

while (tempNode != NULL) {
temp = tempNode->bn;
bufferStatus = bn_toString(temp, printBuffer, bufferLength);
while (bufferStatus > 0) {
bufferLength = bufferStatus;
printBuffer = (char*) realloc (printBuffer, bufferLength + 1);
bufferStatus = bn_toString(temp, printBuffer, bufferLength);
}
if (bufferStatus == -1) { status = -1; return; }
printf(“%s\n”, printBuffer);
tempNode = tempNode->next;
}
}

int main() {
bufferLength = buffer_size;
bufferStatus = 0;
printBuffer = (char*) realloc (printBuffer, bufferLength);

char c[buffer_size];
memset(c, 0, sizeof (c));
char s;
char str[2];
bn_t operand1, operand2;
bool isAllDigits = true;

while (status != -1) {
s = getchar();
if ((!isdigit(s)) && (s != EOF && s != ‘\n’ && !isspace(s)))
isAllDigits = false;
if (isspace(s) || (s == ‘\n’) || (s == EOF)) {

if (strcmp(c, “+”) == 0) {
if ((operand2 = pop(&root)) == NULL) { status = -1; break; }
if ((operand1 = pop(&root)) == NULL) { status = -1; break; }
if ((status = bn_add(operand1, operand1, operand2)) == -1) { status = -1; break; }
push(&root, operand1);
}
else if (strcmp(c, “-“) == 0) {
if ((operand2 = pop(&root)) == NULL) { status = -1; break; }
if ((operand1 = pop(&root)) == NULL) { status = -1; break; }
if ((status = bn_sub(operand1, operand1, operand2)) == -1) { status = -1; break; }
push(&root, operand1);
}
else if (strcmp(c, “*”) == 0) {
if ((operand2 = pop(&root)) == NULL) { status = -1; break; }
if ((operand1 = pop(&root)) == NULL) { status = -1; break; }
if ((status = bn_mul(operand1, operand1, operand2)) == -1) { status = -1; break; }
push(&root, operand1);
}
else if (strcmp(c, “dup”) == 0)
dup(&root);
else if (strcmp(c, “pop”) == 0)
pop(&root);
else if (strcmp(c, “print”) == 0)
printStack(&root);
else if (strcmp(c, “swap”) == 0)
swap(&root);
else if (strcmp(c, “dump”) == 0)
dump(&root);
else if (strcmp(c, “clear”) == 0)
clear(&root);
else if (strlen(c) > 0 && isAllDigits) {
bn_t temp = bn_alloc();
if (temp == NULL) { status = -1; break; }
if (bn_fromString(temp, c) == -1) { status = -1; break; }
push(&root, temp);
}
else if (!isAllDigits) { status = -1; break; }

memset(c, 0, sizeof (c));
isAllDigits = true;
}
else if (s != ‘\n’){
memcpy(str, &s, sizeof(char));
strcat(c, str);
}
if (s == EOF) return 0;
}

if (status == -1) { fprintf(stderr, “Error\n”); return -1; }
return 0;
}

#include
#include
#include
#include
#include
#include
#include
#include #include

#include “bn.h”

struct bn {
int bn_len;
int bn_size;
int bn_sign;
uint16_t *bn_data;
};

static int bn_reallen(bn_t bn) {
int l = bn->bn_len;
while (l– > 0) {
if (bn->bn_data[l] != 0)
return l+1;
}
return 0;
}

int bn_toString(bn_t bn, char *buf, int buflen) {
bn_t dbn = todec(bn);
if (dbn == NULL)
return -1;
int dlen = dbn->bn_len;
uint16_t *data = dbn->bn_data;

char *p = buf;

void bn_free(bn_t bn) {
bn->bn_len = 0;
memset(bn->bn_data, 0, bn->bn_size);
free(bn->bn_data);
bn->bn_data = NULL;
bn->bn_size = 0;
free(bn);
bn = NULL;
}

int copyBN(bn_t destBN, bn_t copyBn) {
destBN->bn_sign = copyBn->bn_sign;
destBN->bn_len = copyBn->bn_len;
if (bn_resize(destBN, copyBn->bn_size) == -1) return -1;
memcpy(destBN->bn_data, copyBn->bn_data, sizeof(uint16_t) * copyBn->bn_size);
return 0;
}

int bn_add(bn_t result, bn_t a, bn_t b) {
int i = 0;
uint16_t carry = 0x00;
uint32_t d_a = 0x00, d_b = 0x00, data = 0x00;

int maxLen = MAX(a->bn_len, b->bn_len);
if (bn_resize(result, maxLen+1) == -1 ) return -1;
result->bn_len = maxLen;

for (i=0; i a->bn_len-1) d_a = 0x0000;
else d_a = (uint32_t) (a->bn_data[i]);
if (i > b->bn_len-1) d_b = 0x0000;
else d_b = (uint32_t) (b->bn_data[i]);

data = (uint32_t) (d_a + d_b + carry);
result->bn_data[i] = (uint16_t) (data & 0xffff);
carry = (uint16_t) ((data & 0xffff0000) >> 16);
if (i == maxLen-1) {
result->bn_len++;
result->bn_data[i+1] += carry;
}
}
result->bn_len = bn_reallen(result);
return 0;
}

int bn_sub(bn_t result, bn_t a, bn_t b) {
int i = 0, borrow = 0;
uint32_t d_a = 0x00, d_b = 0x00, tmp = 0x00;
if (bn_resize(result, a->bn_len) == -1)return -1;
result->bn_len = a->bn_len;

if (a->bn_len < b->bn_len) {
bn_free(result);
result = bn_alloc();
if (result == NULL) return -1;
return 0;
}
else if (a->bn_len == b->bn_len) {
for (i=a->bn_len-1; i>=0; i–) {
if (a->bn_data[i] > b->bn_data[i])
break;
else if (a->bn_data[i] < b->bn_data[i]) {
bn_free(result);
result = bn_alloc();
if (result == NULL) return -1;
return 0;
}
}
}

for (i=0; ibn_len; i++) {
d_a = (uint32_t) a->bn_data[i] + (MAXUINT16 + 1);
if (i < b->bn_len) { d_b = (uint32_t) (b->bn_data[i] + borrow); }
else { d_b = (uint32_t) borrow; }
tmp = d_a – d_b;
result->bn_data[i] = (uint16_t) (tmp & 0xffff);
borrow = (tmp <= MAXUINT16); } result->bn_len = bn_reallen(result);
return 0;
}

int bn_mul(bn_t result, bn_t a, bn_t b) {
int i = 0, j = 0;
uint16_t carry = 0x00;
uint32_t tempD = 0x00;

if (bn_resize(result, a->bn_len + b->bn_len + 1) == -1) return -1;
result->bn_len = a->bn_len + b->bn_len + 1;
uint16_t *dataArray = (uint16_t *) calloc (result->bn_len, sizeof(uint16_t));

for (i=0; ibn_len; i++) {
carry = 0x00;
for (j=0; jbn_len; j++) {
tempD = (uint32_t) (a->bn_data[i] * b->bn_data[j]);
tempD = tempD + dataArray[i+j] + carry;
dataArray[i+j] = (uint16_t) (0xffff & tempD);
carry = (uint16_t) ((0xffff0000 & tempD) >> 16);

if (j == b->bn_len-1 && carry != 0)
dataArray[i+j+1] += carry;
}
}

memset(result->bn_data, 0, result->bn_size);
free(result->bn_data);
result->bn_data = dataArray;
result->bn_len = bn_reallen(result);
return 0;
}

int bn_fromString_itr(bn_t bn, bn_t add_bn) {
bn_t base10 = bn_alloc();
if (bn_fromString(base10, “10”) == -1) return -1;
if (bn_mul(bn, bn, base10) == -1) return -1;
if (bn_add(bn, bn, add_bn) == -1) return -1;
bn_free(base10);
bn_free(add_bn);
return 0;
}

int bn_fromString(bn_t bn, const char *s) {

int len = strlen(s);
int itr = 0;
if (s[0] == ‘-‘)
return -1;

if (len < 19) { char *pEnd; unsigned long long int temp; temp = strtoull(s, &pEnd, 10); while (temp != 0x00) { bn->bn_len++;
if (bn_resize(bn, len + 1) == -1) return -1;
bn->bn_data[itr] = (temp % (MAXUINT16 + 1));
itr++;
temp = temp / (MAXUINT16 + 1);
}
bn->bn_len = bn_reallen(bn);
}
else {
bn_t temp;
for (int i=0; i
#include
#include
#include
#include

#include “bn.h”

int main(int argc, char *argv[]) {

bn_t stack[1000];

int sp = 0;

char buffer[100000];

while(fscanf(stdin, “%s”, buffer) != EOF) {
if( strcmp(“dup”, buffer) == 0 ) {
if(sp < 1) { fprintf(stderr, "Error: Not Enough Numbers on the Stack\n"); exit(0); } char buf[1000000]; if( bn_toString(stack[sp-1], buf, 1000000) == -1 ) { fprintf(stderr, "Error: toString Failed\n"); exit(0); } stack[sp] = bn_alloc(); if( bn_fromString(stack[sp], buf) == -1 ) { fprintf(stderr, "Error: fromString Failed\n"); exit(0); } sp++; } else if( strcmp("+", buffer) == 0 ) { if(sp < 2) { fprintf(stderr, "Error: Not Enough Numbers on the Stack\n"); exit(0); } if( bn_add(stack[sp-2], stack[sp-2], stack[sp-1]) != 0) { fprintf(stderr, "Error: Add Failed\n"); exit(0); } bn_free(stack[sp-1]); sp--; } else if( strcmp("*", buffer) == 0 ) { if(sp < 2) { fprintf(stderr, "Error: Not Enough Numbers on the Stack\n"); exit(0); } if( bn_mul(stack[sp-2], stack[sp-2], stack[sp-1]) != 0) { fprintf(stderr, "Error: Multiply Failed\n"); exit(0); } bn_free(stack[sp-1]); sp--; } else if( strcmp("-", buffer) == 0 ) { if(sp < 2) { fprintf(stderr, "Error: Not Enough Numbers on the Stack\n"); exit(0); } if( bn_sub(stack[sp-2], stack[sp-2], stack[sp-1]) != 0 ) { fprintf(stderr, "Error: Subtract Failed\n"); exit(0); } bn_free(stack[sp-1]); sp--; } else if( strcmp("pop", buffer) == 0 ) { if(sp < 1) { fprintf(stderr, "Error: Not Enough Numbers on the Stack\n"); exit(0); } bn_free(stack[sp-1]); sp--; } else if( strcmp("print", buffer) == 0 ) { if(sp < 1) { fprintf(stderr, "Error: Not Enough Numbers on the Stack\n"); exit(0); } char buf[100000]; if( bn_toString(stack[sp-1], buf, sizeof(buf)) == -1) { fprintf(stderr, "Error: toString failed\n"); exit(0); } printf("%s\n", buf); } else if( strcmp("swap", buffer) == 0 ) { if(sp < 2) { fprintf(stderr, "Error: Not Enough Numbers on the Stack\n"); exit(0); } char bn1[100000]; if( bn_toString(stack[sp-1], bn1, 100000) == -1 ) { fprintf(stderr, "Error: toString Failed\n"); exit(0); } char bn2[100000]; if( bn_toString(stack[sp-2], bn2, 100000) == -1 ) { fprintf(stderr, "Error: toString Failed\n"); exit(0); } bn_free(stack[sp-1]); bn_free(stack[sp-2]); sp = sp - 2; stack[sp] = bn_alloc(); stack[sp+1] = bn_alloc(); if( bn_fromString(stack[sp], bn1) == -1 ) { fprintf(stderr, "Error: fromString failed!\n"); exit(0); } if( bn_fromString(stack[sp+1], bn2) == -1 ) { fprintf(stderr, "Error: fromString failed!\n"); exit(0); } sp = sp + 2; } else if( strcmp("clear", buffer) == 0 ) { while(sp > 0) {
bn_free(stack[sp-1]);
sp–;
}
}

else if( strcmp(“dump”, buffer) == 0 ) {
if(sp < 1) { fprintf(stderr, "Error: Not Enough Numbers on the Stack\n"); exit(0); } for(int i = sp ; i > 0 ; i–) {
char buffer[100000];
if( bn_toString(stack[i-1], buffer, 100000) == -1) {
fprintf(stderr, “Error: toString failed\n”);
exit(0);
}
printf(“%s\n”, buffer);

}
}

else {
stack[sp] = bn_alloc();
if( bn_fromString(stack[sp], buffer) == -1 ) {
fprintf(stderr, “Error: fromString failed!\n”);
exit(0);
}
sp++;

}
}

}

#ifndef __BN_H__
#define __BN_H__ 1

typedef struct bn *bn_t;

bn_t bn_alloc();
void bn_free(bn_t bn);

int bn_add(bn_t result, bn_t a, bn_t b);
int bn_sub(bn_t result, bn_t a, bn_t b);
int bn_mul(bn_t result, bn_t a, bn_t b);

int bn_fromString(bn_t bn, const char *s);
int bn_toString(bn_t bn, char *buf, int buflen);

int bn_sqr(bn_t result, bn_t a);
int bn_div(bn_t quot, bn_t rem, bn_t a, bn_t b);

#endif // __BN_H__

#include
#include
#include
#include
#include

#include “bn.h”

struct bn {
int bn_len;
int bn_size;
int bn_sign;
uint16_t *bn_data;
};

static int bn_resize(bn_t bn, int size);

int bn_fromString(bn_t bn, const char *str){
//if the string length is less than 5 then the number cannot exceed 65536 therefore
//a size of one and you only need to modify bn_data[0]
if (strlen(str) < 5){ int bnNum = 0; for (int i = 0 ; i < strlen(str) ; i++){ //get current number, multiply previous by 10 and add the new number //i.e for 12345 //1 => 10 => 12 => 120 => 123 => 1230 => 1234 => 12340 => 12345
int number = str[i] – ‘0’;
bnNum *= 10;
bnNum += number;
}

bn -> bn_data[0] = bnNum;

bn -> bn_len = bn -> bn_size;

return 0;
}

//a bn for 10 and a bn for the next number
bn_t multiple = bn_alloc();
bn_t currentNum = bn_alloc();
multiple -> bn_data[0] = 10;

for (int i = 0; i < strlen(str); i++){ currentNum -> bn_data[0] = str[i] – ‘0’;

//increment by 10 for each digit in the string
if (bn_mul(bn, bn, multiple) == -1) {
fprintf(stderr, “Error: Multiply Failed\n”);
return -1;
}

//add the current number to the bignum
if (bn_add(bn, bn, currentNum) == -1) {
fprintf(stderr, “Error: Add Failed\n”);
return -1;
}

}

bn_free(multiple);
bn_free(currentNum);

bn -> bn_len = bn -> bn_size;
return 0;

}

int bn_add(bn_t result, bn_t a, bn_t b){
int max = 0;
uint32_t number = 0;

//storing the largest length and setting result to that length
max = (a -> bn_size > b -> bn_size) ? a -> bn_size : b -> bn_size;
if (bn_resize(result, max) == -1){
fprintf(stderr, “Error: Resize Failed\n”);
return -1;
}

int carry = 0;

for (int i = 0; i < max; i++){ number = 0; //adding the digits as long as their size has not been exceeded //(otherwise it adds garbage occasionally for some reason) if( i <= a -> bn_size – 1 ) {
number += a -> bn_data[i];
}

if( i <= b -> bn_size – 1 ) {
number += b -> bn_data[i];
}

number += carry;

//if number exceeded the base then find the overflow and make a carry
if (number >= 65536){
number -= 65536;
carry = 1;
}

else{
carry = 0;
}

result->bn_data[i] = number;
}

//set final carry and resize if final carry exceeds the result size
if (carry == 1){
if (bn_resize(result, (result -> bn_size) + 1) == -1){
fprintf(stderr, “Error: Resize Failed\n”);
return -1;
}

result -> bn_data[ ( result -> bn_size ) – 1 ] += 1;
}

result -> bn_len = result -> bn_size;

return 0;
}

int bn_sub(bn_t result, bn_t a, bn_t b) {
int max = 0;

//result = b – a, so we only iterate along b
max = b -> bn_size;

//if a’s length is smaller than b’s, result is 0 so save some time here
if( a -> bn_len < b -> bn_len ) {
result -> bn_data[0] = 0;
result -> bn_size = 1;
result -> bn_len = 0;
return 0;
}

for(int i = 0 ; i < max ; i++) { //if a digit is smaller than b digit, add base and a digit and remove one from the //next a digit if(a -> bn_data[i] < b -> bn_data[i] ) {
uint32_t newVal = a->bn_data[i] + 65536;
a -> bn_data[i+1]–;
result -> bn_data[i] = newVal – b -> bn_data[i];
}

//else simply do the subtraction
else {
result -> bn_data[i] = a -> bn_data[i] – b -> bn_data[i];
}

}

//as resize doesn’t resize down, this is another way to do so
for(int i = result -> bn_size – 1 ; i >= 0 ; i–) {
if(result -> bn_data[i] != 0) {
break;
}

result -> bn_size–;
}

result -> bn_len = result -> bn_size;
return 0;

}

int bn_mul(bn_t result, bn_t a, bn_t b){
int curDigit;
int carry = 0;
uint32_t number;
bn_t mulResult = bn_alloc();

//if one of either a or b is zero then the result will always be zero
if ( a -> bn_size == 1 && a -> bn_data[0] == 0){
result->bn_len = 0;
result->bn_size = 1;
result->bn_data[0] = 0;
return 0;
}

if( b-> bn_size == 1 && b -> bn_data[0] == 0) {
result->bn_len = 0;
result->bn_size = 1;
result->bn_data[0] = 0;
return 0;
}

for (int i = 0 ; i <= b -> bn_size – 1; i++){
carry = 0;
curDigit = i;

for (int j = 0 ; j <= a -> bn_size – 1; j++){
//resize if current digit exceeds size
if (curDigit >= mulResult -> bn_size){
if(bn_resize( mulResult, curDigit + 1 ) == -1){
fprintf(stderr, “Error: Resize Failed\n”);
return -1;
}
}

//a value + b value + carry + the result already stored there
number = ( a -> bn_data[j] * b -> bn_data[i] ) + mulResult -> bn_data[curDigit] + carry;
mulResult->bn_data[curDigit] = number % 65536;
carry = number / 65536;

//as per long division, equal to a’s digit location + b’s digit location
curDigit = curDigit + 1;
}

//update size for the extra carry and add it
if(carry > 0) {
if(curDigit >= mulResult -> bn_size) {
if( bn_resize( mulResult, curDigit + 1 ) == -1 ) {
fprintf(stderr, “Error: Resize Failed\n”);
return -1;
}
}

mulResult->bn_data[curDigit] += carry;

}

//set result to the values of mulResult and free previous result data
result -> bn_size = mulResult -> bn_size;
free(result -> bn_data);
result -> bn_data = mulResult -> bn_data;
result -> bn_len = mulResult -> bn_size;

return 0;
}

void bn_free(bn_t bn) {
free(bn -> bn_data);
free(bn);
}

int bn_IAmAnUndergrad() {
return 1;
}

static int bn_reallen(bn_t bn) {
int l = bn->bn_len;
while (l– > 0) {
if (bn->bn_data[l] != 0)
return l+1;
}
return 0;
}

int bn_toString(bn_t bn, char *buf, int buflen) {
bn_t dbn = todec(bn);
if (dbn == NULL)
return -1;
int dlen = dbn->bn_len;
uint16_t *data = dbn->bn_data;

char *p = buf;

#ifndef __BN_H__
#define __BN_H__ 1

typedef struct bn *bn_t;

bn_t bn_alloc();
void bn_free(bn_t bn);

int bn_add(bn_t result, bn_t a, bn_t b);
int bn_sub(bn_t result, bn_t a, bn_t b);
int bn_mul(bn_t result, bn_t a, bn_t b);

int bn_fromString(bn_t bn, const char *s);
int bn_toString(bn_t bn, char *buf, int buflen);

int bn_sqr(bn_t result, bn_t a);
int bn_div(bn_t quot, bn_t rem, bn_t a, bn_t b);

#endif // __BN_H__

#include
#include
#include
#include
#include
#include
// #include

// #include “calc.h”
#include “bn.h”
#include “bn.c”

//Structure representing a stack
struct Stack {
int top;
int size;
bn_t* array;
};

static int str_len(const char* s) {
int count = 0;
while(s[count] != ‘\0’) {
count++;
}
return count;
}

//prints top of stack
int print_top(struct Stack* s) {
if(s->top == -1) {
return 1;
}
char* buf = (char*) malloc(100 * sizeof(char));
if(buf == NULL) {
fprintf(stderr, “Error: NULL assignment\n”);
return 1;
}
int required = bn_toString(s->array[s->top], buf, 100);
if(required > 0) {
buf = (char*) realloc(buf, required*required);
required = bn_toString(s->array[s->top], buf, required);
if(buf == NULL) {
fprintf(stderr, “Error: NULL assignment\n”);
return 1;
}
}
printf(“%s\n”, buf);
free(buf);
return 0;
}

//Create a new stack with input size
struct Stack* new_stack(unsigned size) {
struct Stack* s = (struct Stack*) malloc(sizeof(struct Stack));
if(s == NULL) {
fprintf(stderr, “Error: NULL assignment\n”);
}
s->size = size;
s->top = -1;
s->array = (bn_t*) malloc(s->size * sizeof(bn_t*));
if(s->array == NULL) {
fprintf(stderr, “Error: NULL assignment\n”);
}
for(int i=0 ; iarray[i] = bn_alloc();
s->array[i]->bn_len = 0;
}
return s;
}

//Pushes an item onto the stack from string
int push(struct Stack* s, char* num) {
//If Stack is full
if(s->top == s->size) {
fprintf(stderr, “Error: stack full\n”);
return 1;
}
s->top++;
bn_fromString(s->array[s->top], num);
return 0;
}

//Pushes an item onto the stack from bn_t
int push_bn(struct Stack* s, bn_t num) {
if(s->top == s->size) {
fprintf(stderr, “Error: stack full\n”);
return 1;
}
s->top++;
s->array[s->top] = num;
return 0;
}

//Pops an item from the stack
int pop(struct Stack* s) {
//If Stack is empty
if(s->top == -1) {
fprintf(stderr, “Error: stack empty\n”);
return 1;
}
s->top–;
return 0;
}

//Pops an item from the stack as bn_t
bn_t pop_bn(struct Stack* s) {
//If Stack is empty
if(s->top == -1) {
fprintf(stderr, “Error: stack empty\n”);
return NULL;
}
return s->array[s->top–];
}

//Copies value at top of stack and pushes it
int dup(struct Stack* s) {
if(s->top == s->size) {
fprintf(stderr, “Error: stack full\n”);
return 1;
}
if(s->top == -1) {
fprintf(stderr, “Error: stack empty\n”);
return 1;
}

s->top++;
memcpy(s->array[s->top], s->array[s->top-1], sizeof(s->array[s->top-1]) * sizeof(bn_t*));
return 0;
}

//Swap the order of the top two numbers
int swap(struct Stack* s) {
if(s->top < 1) { fprintf(stderr, "Error: less than one element on stack\n"); return 1; } bn_t t1 = pop_bn(s); bn_t t2 = pop_bn(s); push_bn(s, t1); push_bn(s, t2); return 0; } //Print contents of stack int dump(struct Stack* s) { char* buf = (char*) malloc(100 * sizeof(char)); if(buf == NULL) { fprintf(stderr, "Error: NULL assignment\n"); return 1; } for(int i=s->top ; i>=0 ; i–) {
int required = bn_toString(s->array[i], buf, 100);
if(required > 0) {
buf = (char*) realloc(buf, required*required);
required = bn_toString(s->array[i], buf, required);
if(buf == NULL) {
fprintf(stderr, “Error: NULL assignment\n”);
return 1;
}
}
printf(“%s\n”, buf);
}
free(buf);
return 0;
}

//Applies an operator to the top two elements
int operator(struct Stack* s, char c) {
if(s->top < 1) { fprintf(stderr, "Error: less than one element on stack\n"); return 1; } bn_t b1 = pop_bn(s); bn_t b2 = pop_bn(s); bn_t result = bn_alloc(); if(c == '+') { bn_add(result, b1, b2); } else if(c == '-') { bn_sub(result, b2, b1); } else if(c == '*') { bn_mul(result, b1, b2); } else { fprintf(stderr, "Error: invalid operator. Note: THIS SHOULD NEVER HAPPEN\n"); return 1; } if(push_bn(s, result)) { return 1; } return 0; } //Clears the stack int clear_stack(struct Stack* s) { s->top = -1;
return 0;
}

//empties string of size n
void clear_string(char* str, int n) {
for(int i=0 ; i 57)) {
notnum = 1;
}
}
//If it is a number
if((!notnum) && (word_size > 0)) {
if(push(s, word)) { return 1; }
}
//Checking for operator
else if(((word[0] == ‘*’) || (word[0] == ‘+’) || (word[0] == ‘-‘))
&& (word_size == 1)) {
if(operator(s, word[0])) { return 1; }
}
//dup
else if(((word[0] == ‘d’) && (word[1] == ‘u’) && (word[2] == ‘p’))
&& (word_size == 3)) {
if(dup(s)) { return 1; }
}
//pop
else if(((word[0] == ‘p’) && (word[1] == ‘o’) && (word[2] == ‘p’))
&& (word_size == 3)) {
if(pop(s)) { return 1; }
}
//swap
else if(((word[0] == ‘s’) && (word[1] == ‘w’) && (word[2] == ‘a’) && (word[3] == ‘p’))
&& (word_size == 4)) {
if(swap(s)) { return 1; }
}
//dump
else if(((word[0] == ‘d’) && (word[1] == ‘u’) && (word[2] == ‘m’) && (word[3] == ‘p’))
&& (word_size == 4)) {
if(dump(s)) { return 1; }
}
//print
else if(((word[0] == ‘p’) && (word[1] == ‘r’) &&
(word[2] == ‘i’) && (word[3] == ‘n’) && (word[4] == ‘t’))
&& (word_size == 5)) {
if(print_top(s)) { return 1; }
}
//clear
else if(((word[0] == ‘c’) && (word[1] == ‘l’) &&
(word[2] == ‘e’) && (word[3] == ‘a’) && (word[4] == ‘r’))
&& (word_size == 5)) {
if(clear_stack(s)) { return 1; }
}
//Invalid word
else if (word_size != 0) {
fprintf(stderr, “Error: ‘%s’ is not a valid word type\n”, word);
return 1;
}

word_size = 0;
}
else {
word[word_size++] = input[i];
}
}

return 0;
}

int main(int argc, const char* argv[]) {
struct Stack* stack = new_stack(500);

char input[5000];
while(!feof(stdin)) {
input[0] = ‘\0’;
fgets(input, 5000, stdin);
if(parse_input(stack, input)) {
return 1;
}
}

return 0;
}

calc:
gcc -c bn.c -o bn.o -Wall -std=c99
ar rcs libbn.a bn.o
gcc calc.c -L. -lbn -o calc -Wall

#include
#include
#include
#include
#include

#include “bn.h”

struct bn {
int bn_len; //Number of digits represented
int bn_size; //Num of digits allocated in data
int bn_sign; //Sign (Always 1)
uint16_t *bn_data; //Values of each digit
};

//Base 2^16, the size of each digit in a bn_t
static int BASE = 65536;

//
static int bn_reallen(bn_t bn) {
int l = bn->bn_len;
while (l– > 0) {
if (bn->bn_data[l] != 0)
return l+1;
}
return 0;
}

//Convert bn_t to decimal
static bn_t todec(bn_t bn) {
int binlen = bn_reallen(bn);
int declen = ((binlen + 3)/4) * 5;
bn_t dbn = bn_alloc();
if (dbn == NULL)
return NULL;
bn_resize(dbn, declen);
for (int i = binlen; i–; ) {
dbn_push(dbn, bn->bn_data[i] >> 8);
dbn_push(dbn, bn->bn_data[i] & 0xFF);
}
return dbn;
}

void bn_setvalues(bn_t bn, int size, uint16_t *bn_data) {
bn->bn_len = size;
bn_resize(bn, size);
for(int i=0 ; ibn_data[size-i-1] = bn_data[i];
}
bn->bn_size = size;
}

//Create a new bn_t
bn_t bn_alloc(void) {
bn_t bn = (bn_t)malloc(sizeof(struct bn));
if (bn == NULL)
return NULL;
bn->bn_data = (uint16_t *)calloc(1, sizeof(uint16_t));
if (bn->bn_data == NULL) {
free(bn);
return NULL;
}
bn->bn_len = 0;
bn->bn_size = 1;
bn->bn_sign = 1;
return bn;
}

//Frees all resources in bn
void bn_free(bn_t bn) {
free(bn->bn_data);
free(bn);
}

//Copy a big num
bn_t bn_copy(bn_t in) {
bn_t out = bn_alloc();
bn_resize(out, in->bn_size);
out->bn_size = in->bn_size;
out->bn_len = in->bn_len;
for(int i=0 ; ibn_len ; i++) {
out->bn_data[i] = in->bn_data[i];
}
return out;
}

//Display a number in big-endian notation
void bn_print(bn_t bn) {
printf(“\n{“);
for(int i=0 ; ibn_len ; i++) {
printf(“%d”, bn->bn_data[i]);
if(i != bn->bn_len-1) {
printf(“, “);
}
}
printf(“}\n”);
}

//Adds so that a+b=result
int bn_add(bn_t result, bn_t a, bn_t b) {

if((a == NULL) || (b == NULL)) {
return -1;
}

bn_t a_copy = bn_copy(a);
bn_t b_copy = bn_copy(b);

int shorter = a_copy->bn_len;
int longer = b_copy->bn_len;
int bigger_a = 0;

if(b_copy->bn_len < a_copy->bn_len) {
shorter = b_copy->bn_len;
longer = a_copy->bn_len;
bigger_a = 1;
}

if(bigger_a) {
bn_resize(result, a_copy->bn_len+1);
} else {
bn_resize(result, b_copy->bn_len+1);
}

result->bn_len = longer+1;

uint16_t temp = 0;
uint16_t carry = 0;
for(int i=0 ; ibn_data[i] + b_copy->bn_data[i] + carry;

if((temp < a_copy->bn_data[i]) || (temp < b_copy->bn_data[i])) {
carry = 1;
}
else {
carry = 0;
}
result->bn_data[i] = temp;
}
for(int i=shorter ; ibn_data[i] + carry;
if(temp < b_copy->bn_data[i]) {
carry = 1;
}
else {
carry = 0;
}
}
else {
temp = a_copy->bn_data[i] + carry;
if(temp < a_copy->bn_data[i]) {
carry = 1;
}
else {
carry = 0;
}
}
result->bn_data[i] = temp;
}

if(carry == 1) {
result->bn_data[longer] = carry;
}

if((result->bn_data[result->bn_len-1] == 0) && (result->bn_len > 0)) {
result->bn_len–;
}

bn_free(a_copy);
bn_free(b_copy);

return 0;
}

//Subtracts so that a-b=result
int bn_sub(bn_t result, bn_t a, bn_t b) {
if((a == NULL) || (b == NULL)) {
return -1;
}

int shorter = b->bn_len;
int longer = a->bn_len;
//If abn_len < shorter) { bn_resize(result, 1); result->bn_len = 1;
result->bn_data[0] = 0;
return 0;
}
else if(a->bn_len == shorter) {
for(int i=0 ; ibn_data[shorter-1-i] < b->bn_data[shorter-1-i]) {
bn_resize(result, 1);
result->bn_data[0] = 0;
return 0;
}
else if(a->bn_data[shorter-1-i] > b->bn_data[shorter-1-i]) {
break;
}
}

}

bn_t a_copy = bn_alloc();
a_copy->bn_len = a->bn_len;
a_copy->bn_size = a->bn_size;
for(int i=0 ; ibn_len ; i++) {
a_copy->bn_data[i] = a->bn_data[i];
}

bn_resize(result, a->bn_size);
uint16_t temp = 0;
for(int i=0 ; ibn_data[i] >= b->bn_data[i]) {
temp = a_copy->bn_data[i] – b->bn_data[i];
}
else {
for(int j=i+1 ; jbn_data[j] == 0) {
a_copy->bn_data[j] = BASE-1;
}
else {
a_copy->bn_data[j]–;
break;
}
}

temp = BASE – b->bn_data[i];
temp += a->bn_data[i];
}
result->bn_data[i] = temp;
result->bn_len++;
}
for(int i=shorter ; ibn_data[i] = a_copy->bn_data[i];
result->bn_len++;
}

bn_free(a_copy);
return 0;
}

//Multiplies so that a*b=result
int bn_mul(bn_t result, bn_t a, bn_t b) {
if((a == NULL) || (b == NULL)) {
return -1;
}
bn_t bigger;
bn_t smaller;
if(b->bn_len > a->bn_len) {
bigger = b;
smaller = a;
}
else {
bigger = a;
smaller = b;
}
uint32_t temp = 0;
uint16_t carry = 0;
uint16_t remain = 0;
bn_t steps[smaller->bn_len];

for(int i=0 ; ibn_len ; i++) {
steps[i] = bn_alloc();
bn_resize(steps[i], bigger->bn_len + 1 + i);
for(int k=0 ; kbn_data[k] = 0;
steps[i]->bn_len++;
}
for(int j=0 ; jbn_len ; j++) {
temp = smaller->bn_data[i] * bigger->bn_data[j];
remain = (temp + carry) % BASE;
carry = (temp + carry) / BASE;
steps[i]->bn_data[j+i] = remain;
steps[i]->bn_len++;
}
if(carry != 0) {
steps[i]->bn_data[bigger->bn_len + i] = carry;
steps[i]->bn_len++;
carry = 0;
}
}

bn_t res_temp = bn_copy(steps[0]);
for(int i=1 ; ibn_len ; i++) {
bn_add(res_temp, res_temp, steps[i]);
bn_free(steps[i]);
}

bn_resize(result, res_temp->bn_size);
result->bn_len = res_temp->bn_len;
for(int i=0 ; ibn_len ; i++) {
result->bn_data[i] = res_temp->bn_data[i];
}
bn_free(res_temp);

return 0;
}

//Check if undergraduate
int bn_IAmAnUndergrad() {
return 1;
}

//Converts decimal to big num
int bn_fromString(bn_t bn, const char *s) {
bn_t ten = bn_alloc();
bn_t c = bn_alloc();
ten->bn_len = 1;
c->bn_len = 1;
ten->bn_data[0] = 10;
c->bn_data[0] = 0;
bn->bn_len = 1;
bn->bn_data[0] = 0;

for(int i=0 ; s[i] != ‘\0’ ; i++) {
c->bn_data[0] = s[i]-‘0’;
bn_mul(bn, bn, ten);
bn_add(bn, bn, c);
}
return 0;
}

//Converts big num to a string
int bn_toString(bn_t bn, char *buf, int buflen) {
bn_t dbn = todec(bn);
if (dbn == NULL)
return -1;
int dlen = dbn->bn_len;
uint16_t *data = dbn->bn_data;

int requiredlen;
if (dlen == 0)
requiredlen = 2;
else
requiredlen = 2 + (bn->bn_sign < 0) + (dlen - 1) * 4 + (data[dlen-1] > 999) +
(data[dlen-1] > 99) +
(data[dlen – 1] > 9);
if (requiredlen > buflen) {
bn_free(dbn);
return requiredlen;
}

char *p = buf;

if (dlen == 0) {
*p++ = ‘0’;
} else {
if (bn->bn_sign < 0) *p++ = '-'; dlen--; if (data[dlen] > 999)
*p++ = ‘0’ + (data[dlen] / 1000) % 10;
if (data[dlen] > 99)
*p++ = ‘0’ + (data[dlen] / 100) % 10;
if (data[dlen] > 9)
*p++ = ‘0’ + (data[dlen] / 10) % 10;
*p++ = ‘0’ + data[dlen] % 10;
while (dlen–) {
*p++ = ‘0’ + (data[dlen] / 1000) % 10;
*p++ = ‘0’ + (data[dlen] / 100) % 10;
*p++ = ‘0’ + (data[dlen] / 10) % 10;
*p++ = ‘0’ + (data[dlen] / 1) % 10;
}
}
*p = ‘\0’;
bn_free(dbn);
return 0;
}

CC = gcc
CFLAGS = -Wall -std=c99
all: calc
calc: calc.o libbn.a
$(CC) calc.o libbn.a -o calc
calc.o: calc.c
$(CC) -c $(CFLAGS) calc.c
libbn.a: bn.c
$(CC) -c $(CFLAGS) bn.c -o libbn.a
clean:
rm -rf *o calc

#ifndef __BN_H__
#define __BN_H__ 1

typedef struct bn *bn_t;

bn_t bn_alloc();
void bn_free(bn_t bn);

int bn_add(bn_t result, bn_t a, bn_t b);
int bn_sub(bn_t result, bn_t a, bn_t b);
int bn_mul(bn_t result, bn_t a, bn_t b);

int bn_fromString(bn_t bn, const char *s);
int bn_toString(bn_t bn, char *buf, int buflen);

int bn_sqr(bn_t result, bn_t a);
int bn_div(bn_t quot, bn_t rem, bn_t a, bn_t b);

#endif // __BN_H__

#include
#include
#include
#include
#include
#include
#include
#include
#include “bn.h”

void push(bn_t *stack, int * sp, bn_t toPush){
stack[*sp] = toPush;
(*sp)++;
}

void decimalNumber(bn_t *stack, int *sp, char * str){
bn_t temp = bn_alloc();
bn_fromString(temp,str);
push(stack,sp,temp);
}

bn_t pop(bn_t *stack, int *sp){
(*sp)–;
return stack[*sp];
}

void action(bn_t *stack, int *sp, char sign){
switch(sign)
{
case ‘+’:
{
bn_t res = bn_alloc();
bn_t b = pop(stack,sp);
bn_t a = pop(stack,sp);
bn_add(res,a,b);
push(stack,sp,res);
break;
}
case ‘-‘:
{
bn_t res = bn_alloc();
bn_t b = pop(stack,sp);
bn_t a = pop(stack,sp);
bn_sub(res,a,b);
push(stack,sp,res);
break;
}
case ‘*’:
{
bn_t res = bn_alloc();
bn_t b = pop(stack,sp);
bn_t a = pop(stack,sp);
bn_mul(res,a,b);
push(stack,sp,res);
break;
}
}

}

void dup(bn_t *stack, int *sp){
bn_t a = pop(stack,sp);
bn_t b = a;
push(stack,sp,a);
push(stack,sp,b);
}

void print(bn_t *stack, int *sp){
char test[100];
int buffsize = bn_toString(stack[*sp-1], test, sizeof(test));
if(buffsize == 0){
printf(“%s\n”, test);
} else {
char buf[buffsize];
bn_toString(stack[*sp-1], buf, sizeof(buf));
printf(“%s\n”, buf);
}

}

void swap(bn_t *stack, int *sp){
bn_t a = pop(stack,sp);
bn_t b = pop(stack,sp);
push(stack,sp,b);
push(stack,sp,a);
}

void dump(bn_t *stack, int sp){
while(sp >= 0){
sp–;
char test[100];
int buffsize = bn_toString(stack[sp], test, sizeof(test));
if(buffsize == 0){
printf(“%s\n”, test);
} else {
char buf[buffsize];
bn_toString(stack[sp], buf, sizeof(buf));
printf(“%s\n”, buf);
}
}
}

void clear(bn_t *stack, int *sp){
while(*sp > 0){
pop(stack,sp);
}
}

char *inputString(FILE* fp){
char *str;
int ch;
size_t size = 50;
size_t len = 0;
str = realloc(NULL, sizeof(char)*size);//size is start size
if(!str)return str;
while(EOF!=(ch=fgetc(fp)) && ch != ‘\n’){
str[len++]=ch;
if(len==size){
str = realloc(str, sizeof(char)*(size+=50));
if(!str)return str;
}
}
str[len++]=’\0′;
return realloc(str, sizeof(char)*len);
}

int main(int argc, char **argv){
/*if(argc != 1){
printf(“usage: calc [testfile], errno = %d\n”, errno);
return 1;
}
FILE *fp;
fp = fopen(argv[1], “r”);
if (fp == NULL) {
printf (“Error, File not opened correctly, errno = %d\n”, errno);
return 1;
}
*/
char c, testNum;
bn_t stack[100];
int sp = 0;

while(1) {
c = fgetc(stdin);
while(isspace(c)){
c = fgetc(stdin);
if( feof(stdin) ) {
break ;
}
}
if( feof(stdin) ) {
break ;
}
int size = 50;
int len = 0;
char *str = (char*)malloc(size * sizeof(char));
while(!isspace(c)){
str[len]=c;
len++;
if(len==size){
str = realloc(str, sizeof(char)*(size+=50));
if(!str){
printf(“Failed to realloc, errno = %d\n”, errno);
exit(1);
}
}
c = fgetc(stdin);
if( feof(stdin) ) {
break ;
}
}
str[len]=’\0′;
if((strcmp(str,”+”) == 0) || (strcmp(str,”-“) == 0) || (strcmp(str,”*”) == 0)){
action(stack, &sp, str[0]);
} else if(strcmp(“dup”,str) == 0){
dup(stack,&sp);
} else if(strcmp(“pop”,str) == 0){
pop(stack,&sp);
} else if(strcmp(“print”,str) == 0){
print(stack,&sp);
} else if(strcmp(“swap”,str) == 0){
swap(stack,&sp);
} else if(strcmp(“dump”,str) == 0){
dump(stack,sp);
} else if(strcmp(“clear”,str) == 0){
clear(stack,&sp);
} else {
int testNumCount = 0;
testNum = str[testNumCount];
while(testNum){
if(isdigit(testNum)){
testNumCount++;
testNum = str[testNumCount];
} else {
printf(“Error, Enter a correct command or number, errno = %d\n”, errno);
exit(1);
}
}
decimalNumber(stack,&sp,str);
}
free(str);
}
return 0;
}

#include
#include
#include
#include
#include
#include
#include

#include “bn.h”

const int MAX_VAL = 65536;

struct bn {
int bn_len;
int bn_size;
int bn_sign;
uint16_t *bn_data;
};

static int bn_resize(bn_t bn, int size) {
if (size <= bn->bn_size)
return 0;
uint16_t *data = (uint16_t *)realloc(bn->bn_data, size * sizeof(uint16_t));
if (data == NULL)
return -1;
for (int i = bn->bn_size; i < size; i++) data[i] = 0; bn->bn_data = data;
bn->bn_size = size;
return 1;
}

static int bn_reallen(bn_t bn) {
int l = bn->bn_len;
while (l– > 0) {
if (bn->bn_data[l] != 0)
return l+1;
}
return 0;
}

static void dbn_push(bn_t bn, uint8_t data) {
uint32_t carry = data;
for (int j = 0; j < bn->bn_len; j++) {
carry += bn->bn_data[j] * 256;
bn->bn_data[j] = carry % 10000;
carry = carry / 10000;
}
if (carry != 0)
bn->bn_data[bn->bn_len++] = carry;
}

static bn_t todec(bn_t bn) {
int binlen = bn_reallen(bn);
int declen = ((binlen + 3)/4) * 5;
bn_t dbn = bn_alloc();
if (dbn == NULL)
return NULL;
bn_resize(dbn, declen);
for (int i = binlen; i–; ) {
dbn_push(dbn, bn->bn_data[i] >> 8);
dbn_push(dbn, bn->bn_data[i] & 0xFF);
}
return dbn;
}

bn_t bn_alloc(void) {
bn_t bn = (bn_t)malloc(sizeof(struct bn));
if (bn == NULL)
return NULL;
bn->bn_data = (uint16_t *)calloc(1, sizeof(uint16_t));
if (bn->bn_data == NULL) {
free(bn);
return NULL;
}
bn->bn_len = 0;
bn->bn_size = 1;
bn->bn_sign = 1;
return bn;
}

int bn_toString(bn_t bn, char *buf, int buflen) {
bn_t dbn = todec(bn);
if (dbn == NULL)
return -1;
int dlen = dbn->bn_len;
uint16_t *data = dbn->bn_data;

int requiredlen;
if (dlen == 0)
requiredlen = 2;
else
requiredlen = 2 + (bn->bn_sign < 0) + (dlen - 1) * 4 + (data[dlen-1] > 999) +
(data[dlen-1] > 99) +
(data[dlen – 1] > 9);
if (requiredlen > buflen) {
bn_free(dbn);
return requiredlen;
}

char *p = buf;

if (dlen == 0) {
*p++ = ‘0’;
} else {
if (bn->bn_sign < 0) *p++ = '-'; dlen--; if (data[dlen] > 999)
*p++ = ‘0’ + (data[dlen] / 1000) % 10;
if (data[dlen] > 99)
*p++ = ‘0’ + (data[dlen] / 100) % 10;
if (data[dlen] > 9)
*p++ = ‘0’ + (data[dlen] / 10) % 10;
*p++ = ‘0’ + data[dlen] % 10;
while (dlen–) {
*p++ = ‘0’ + (data[dlen] / 1000) % 10;
*p++ = ‘0’ + (data[dlen] / 100) % 10;
*p++ = ‘0’ + (data[dlen] / 10) % 10;
*p++ = ‘0’ + (data[dlen] / 1) % 10;
}
}
*p = ‘\0’;
bn_free(dbn);
return 0;
}

void bn_free(bn_t bn){
/*Frees all the resources associated with the bignum bn. */

free(bn->bn_data);
free(bn);
}

int bn_add(bn_t result, bn_t a, bn_t b){
/*Adds the bignums a and b and places the sum in result. Returns 0 if completed successfully and −1
otherwise.*/
int carry = 0;
uint32_t addingElements = 0;
int bigLen, smlLen;
if(a->bn_len == b->bn_len){
bigLen = smlLen = a->bn_len;
} else if(a->bn_len > b->bn_len){
bigLen = a->bn_len;
smlLen = b->bn_len;
} else {
bigLen = b->bn_len;
smlLen = a->bn_len;
}
if(smlLen == bigLen){
result->bn_len = 0;
for(int i=0; ibn_len++;
bn_resize(result, result->bn_len);
addingElements = a->bn_data[i] + b->bn_data[i] + carry;
if(addingElements >= MAX_VAL){
carry = 1;
result->bn_data[i] = addingElements-MAX_VAL;
} else {
result->bn_data[i] = addingElements;
carry = 0;
}
}
if(carry == 1){
result->bn_len++;
bn_resize(result, result->bn_len);
result->bn_data[result->bn_len-1] = 1;
}
} else if(smlLen == a->bn_len){
result->bn_len = 0;
for(int i=0; ibn_len++;
bn_resize(result, result->bn_len);
addingElements = a->bn_data[i] + b->bn_data[i] + carry;
if(addingElements >= MAX_VAL){
carry = 1;
result->bn_data[i] = addingElements-MAX_VAL;
} else {
result->bn_data[i] = addingElements;
carry = 0;
}
}
for(int i=smlLen; ibn_len++;
bn_resize(result, result->bn_len);
addingElements = b->bn_data[i] + carry;
if(addingElements >= MAX_VAL){
carry = 1;
result->bn_data[i] = addingElements-MAX_VAL;
} else {
result->bn_data[i] = addingElements;
carry = 0;
};
}
if(carry == 1){
result->bn_len++;
bn_resize(result, result->bn_len);
result->bn_data[result->bn_len-1] = 1;
}
} else if(smlLen == b->bn_len){
result->bn_len = 0;
for(int i=0; ibn_len++;
bn_resize(result, result->bn_len);
addingElements = a->bn_data[i] + b->bn_data[i] + carry;
if(addingElements >= MAX_VAL){
carry = 1;
result->bn_data[i] = addingElements-MAX_VAL;
} else {
result->bn_data[i] = addingElements;
carry = 0;
}
}
for(int i=smlLen; ibn_len++;
bn_resize(result, result->bn_len);
addingElements = a->bn_data[i] + carry;
if(addingElements >= MAX_VAL){
carry = 1;
result->bn_data[i] = addingElements-MAX_VAL;
} else {
result->bn_data[i] = addingElements;
carry = 0;
};
}
if(carry == 1){
result->bn_len++;
bn_resize(result, result->bn_len);
result->bn_data[result->bn_len-1] = 1;
}
}

return 0;
}

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.
Undergraduate students: if a is smaller than b, the result is set to 0.*/
int subElements = 0;
int bigLen, smlLen;
if(a->bn_len < b->bn_len){
return 0;
} else if(a->bn_len == b->bn_len){
int lengthTest = a->bn_len-1;
int aIsBigger = 0;
while((lengthTest >= 0) && (aIsBigger == 0)){
if(a->bn_data[lengthTest] < b->bn_data[lengthTest]){
return 0;
} else if(a->bn_data[lengthTest] > b->bn_data[lengthTest]){
aIsBigger++;
} else {
lengthTest–;
}
}
}
bigLen = a->bn_len;
smlLen = b->bn_len;
result->bn_len = 0;
for(int i=0; ibn_len++;
bn_resize(result, result->bn_len);
subElements = a->bn_data[i] – b->bn_data[i];
if(subElements < 0){ if(bigLen >= i){
a->bn_data[i+1]–;
subElements += MAX_VAL;
}
}
result->bn_data[i]= subElements;
}
for(int i=smlLen; ibn_len++;
bn_resize(result, result->bn_len);
result->bn_data[i] = a->bn_data[i];
}
return 0;
}

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.*/
uint32_t carry;
uint32_t currentDigit;
int i = 0;
int j;
if(((void*)&a->bn_data[0] == (void*)&result->bn_data[0]) && ((void*)&b->bn_data[0] == (void*)&result->bn_data[0])){
printf(“Exiting, errno = %d\n”, errno);
return -1;
} else if ((void*)&a->bn_data[0] == (void*)&result->bn_data[0]){
printf(“Error bn_mul usage:result != a, errno = %d\n”, errno);
return -1;
} else if ((void*)&b->bn_data[0] == (void*)&result->bn_data[0]){
printf(“Error bn_mul usage:result != b, errno = %d\n”, errno);
return -1;
} else {
for(int i=0; ibn_len; i++){
result->bn_data[i] = 0;
}
result->bn_len = 0;
bn_resize(result,result->bn_len);
}
for(i=0; ibn_len; i++){
carry = 0;
for(j=i; jbn_len + i; j++){
result->bn_len++;
bn_resize(result,result->bn_len);
currentDigit = result->bn_data[j] + (b->bn_data[i] * a->bn_data[j-i] + carry);
carry = currentDigit/MAX_VAL;
result->bn_data[j] = currentDigit%MAX_VAL;
}
if(carry){
result->bn_len++;
bn_resize(result,result->bn_len);
currentDigit = result->bn_data[j] + carry;
carry = currentDigit/MAX_VAL;
result->bn_data[j] = currentDigit%MAX_VAL;
}
}
return 0;
}

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.
1
Undergraduate students need only handle non-negative numbers. Postgraduate students need to handle
both positive and negative numbers.*/
int count = 0;

bn_t a = bn_alloc();
a->bn_len++;

bn_t multi10 = bn_alloc();
multi10->bn_data[multi10->bn_len] = 10;
multi10->bn_len++;

while(str[count] != ‘\0’){
bn_t temp = bn_alloc();
bn_resize(temp,bn->bn_len);
for(int i=0; ibn_len; i++){
temp->bn_data[i] = bn->bn_data[i];
}
temp->bn_sign = bn->bn_size;
temp->bn_size = bn->bn_size;
temp->bn_len = bn->bn_len;

a->bn_data[0] = str[count] – ‘0’;
bn_mul(bn,temp,multi10);
bn_add(bn,bn,a);
count++;
bn_free(temp);
}
bn_free(a);
bn_free(multi10);
/*int count = 0;
bn_t temp = bn_alloc();
bn->bn_data[0] = 1;
bn->bn_len = 1;

charStore->bn_data[0] = str[count] – ‘0’;
printBN(bn);
bn_mul(temp,bn,charStore);
printBN(temp);
bn->bn_len = temp->bn_len;
for(int i=0; ibn_len; i++){
bn_resize(bn,i+1);
bn->bn_data[i] = temp->bn_data[i];
temp->bn_data[i] = 0;
}
printBN(bn);
bn_resize(temp,1);
bn_add(bn,bn,charStore);
count++;
}*/
return 0;
}

int bn_IAmAnUndergrad(){
/*Returns 1 if you’re an undergraduate student, 0 if you’re a postgraduate student. It is highly recommended
not to return the wrong value. Implementations that return 0 will be marked on handling both positive and
negative numbers.. Implementations that return 1 will only be marked on handling non-negative numbers
only, with a penalty of 20% for postgraduate students that use this option.*/
return 1;
}

int printBN(bn_t bn){
printf(“Printing BN\n”);
for(int i =0; ibn_len; i++){
printf(“%d: %d\n”, i, bn->bn_data[i]);
}
printf(“\n”);
return 0;
}

clean: calc
rm -f *.o *.gch

calc: calculator.o stack.o libbn.a
gcc -Wall -std=gnu99 -lm -o calc calculator.o stack.o -L. -lbn

bn.o: bn.c bn.h
gcc -Wall -std=gnu99 -O -c bn.c

stack.o: stack.c stack.h bn.o
gcc -Wall -std=gnu99 -O -c stack.c

calculator.o: calculator.c
gcc -Wall -std=gnu99 -O -c calculator.c

libbn.a: bn.o
ar rcs libbn.a bn.o

#include
#include
#include
#include

#include “bn.h”
#include “stack.h”

struct stackElement
{
bn_t data;
stEl next;
};

struct stackStore
{
stEl head;
int mode;
};

st initStack(int mode)
{
st newStack = (st)malloc(sizeof newStack);
if(newStack == NULL)
{
return NULL;
}
newStack->head = NULL;
return newStack;
}

int pushStack(st myStack, bn_t i)
{
if(myStack == NULL)
{
return 1;
}
if(i == NULL)
{
return 1;
}
stEl element = (stEl)malloc(sizeof element);
if(element == NULL)
{
return 1;
}
else
{
element->data = i;
element->next = myStack->head;
myStack->head = element;

}
return 0;
}

bn_t topStack(st myStack)
{
if(myStack == NULL)
{
fprintf(stderr, “Error: stack not initialized\n”);
return NULL;
}
if(myStack->head!=NULL)
{
return myStack->head->data;
}
else
{
return NULL;
}
}

int popStack(st myStack)
{
if(myStack == NULL)
{
fprintf(stderr, “Error: stack not initialized\n”);
return 1;
}
if(myStack->head != NULL)
{
stEl temp = myStack->head;
myStack->head = myStack->head->next;
if(temp->data != NULL && myStack->mode==1)
{
bn_free(temp->data);
}
free(temp);
}
else
{
fprintf(stderr, “Error: nothing to pop\n”);
return 1;
}
return 0;
}

int dupStack(st myStack)
{
if(myStack == NULL)
{
fprintf(stderr, “Error: stack not initialized\n”);
return 1;
}
if(pushStack(myStack,topStack(myStack))!=0)
{
fprintf(stderr, “Error: nothing on stack to duplicate\n”);
return 1;
}
return 0;
}

int printStack(st myStack)
{
if(myStack == NULL)
{
fprintf(stderr, “Error: stack not initialized\n”);
return 1;
}
if(myStack->head != NULL)
{
if(myStack->head->data != NULL)
{
char* buf = (char*)malloc(100);

if(buf == NULL)
{
fprintf(stderr, “Error: could not allocate memory for print buffer\n”);
return 1;
}
int i = bn_toString(myStack->head->data,buf,1000);
if(i>0)
{
buf = (char*)realloc(buf,i);

if(buf == NULL)
{
fprintf(stderr, “Error: could not allocate memory for print buffer\n”);
return 1;
}
if(bn_toString(myStack->head->data,buf,i)!=0)
{
fprintf(stderr, “Error: could not allocate memory for print buffer\n”);
return 1;
}
}
if(i==-1)
{
fprintf(stderr, “Error: could not allocate memory for print buffer\n”);
return 1;
}
printf(“%s\n”,buf);

free(buf);
}
}
return 0;
}

int swapStack(st myStack)
{
if(myStack == NULL)
{
fprintf(stderr, “Error: stack not initialized\n”);
return 1;
}

stEl temp = myStack->head;
if(temp == NULL)
{
fprintf(stderr, “Error: nothing to swap\n”);
return 1;
}
bn_t tempData = temp->data;

if(temp->next == NULL)
{
fprintf(stderr, “Error: need two elements to swap\n”);
return 1;
}

stEl temp2 = temp->next;

temp->data = temp2->data;

temp2->data = tempData;

return 0;
}

int dumpStack(st myStack)
{
if(myStack == NULL)
{
fprintf(stderr, “Error: stack not initialized\n”);
return 1;
}
if(myStack->head != NULL)
{
stEl temp = myStack->head;
do
{
char* buf = (char*)malloc(100);

if(buf == NULL)
{
fprintf(stderr, “Error: could not allocate memory for print buffer\n”);
return 1;
}
int i = bn_toString(temp->data,buf,1000);
if(i>0)
{
buf = (char*)realloc(buf,i);

if(buf == NULL)
{
fprintf(stderr, “Error: could not allocate memory for print buffer\n”);
return 1;
}
if(bn_toString(temp->data,buf,i)!=0)
{
fprintf(stderr, “Error: could not allocate memory for print buffer\n”);
return 1;
}
}
if(i==-1)
{
fprintf(stderr, “Error: could not allocate memory for print buffer\n”);
return 1;
}
printf(“%s\n”,buf);
free(buf);
temp = temp->next;
} while (temp != NULL);
}
return 0;
}

int clearStack(st myStack)
{
if(myStack == NULL)
{
fprintf(stderr, “Error: stack not initialized\n”);
return 1;
}
while(myStack->head != NULL)
{
popStack(myStack);
}
return 0;
}

void freeStack(st myStack)
{
free(myStack);
}

#ifndef __BN_H__
#define __BN_H__ 1

typedef struct bn* bn_t;

// Allocates a new bignum and initialises it to (positive) 0.
// Returns NULL if not enough resources are available.
bn_t bn_alloc();

// Frees all the resources associated with the bignum bn.
void bn_free(bn_t bn);

// Adds the bignums a and b and places the sum in result.
// Returns 0 if completed successfully and −1 otherwise.
int bn_add(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.
// Undergraduate students: if a is smaller than b, the result is set to 0.
int bn_sub(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.
int bn_mul(bn_t result, bn_t a, bn_t b);

// Read the decimal number in the string str and stores its value in bn.
// Returns 0 if completed successfully and −1 otherwise.
int bn_fromString(bn_t bn, const char *s);

// 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.
int bn_toString(bn_t bn, char *buf, int buflen);

int bn_sqr(bn_t result, bn_t a);
int bn_div(bn_t quot, bn_t rem, bn_t a, bn_t b);

// Returns 1 if you’re an undergraduate student
int bn_IAmAnUndergrad();

#endif // __BN_H__

#include
#include
#include
#include
#include
#include
#include
#include “bn.h”
#include “stack.h”

int checkIfDup(char* ptr)
{
return !strncmp(ptr,”dup”,3);
}

int checkIfPop(char* ptr)
{
return !strncmp(ptr,”pop”,3);
}

int checkIfPrint(char* ptr)
{
return !strncmp(ptr,”print”,5);
}

int checkIfSwap(char* ptr)
{
return !strncmp(ptr,”swap”,4);
}

int checkIfClear(char* ptr)
{
return !strncmp(ptr,”clear”,5);
}

int checkIfDump(char* ptr)
{
return !strncmp(ptr,”dump”,4);
}

int checkIfOperator(char c)
{
return (c==’+’ || c==’-‘ || c==’*’);
}

int checkIfNum(char* ptr, int size)
{
for(int i = 0; i0)
{
strInput[i] = ‘\0′;
//printf(“%s\n”,strInput);

if(checkIfNum(strInput,i)==0)
{
bn_t num = bn_alloc();
if(num == NULL)
{
fprintf(stderr, “Error: out ofmemory\n”);
return 1;
}
if(bn_fromString(num,strInput)!=0)
{
fprintf(stderr, “Error: could not convert string: %s to number\n”,strInput);
return 1;
}
if(pushStack(inStack,num)!=0)
{
fprintf(stderr, “Error: could not push to stack\n”);
return 1;
}

}
else if(i==1)
{
if(checkIfOperator(strInput[0])!=0)
{
bn_t a = topStack(inStack);
if(a == NULL)
{
fprintf(stderr, “Error: need two operands on stack\n”);
return 1;
}
if(popStack(inStack)!=0)
{
fprintf(stderr, “Error: need two operands on stack\n”);
return 1;
}
if(pushStack(poppedStack,a)!=0)
{
fprintf(stderr, “Error: out of memory popped stack\n”);
return 1;
}
bn_t b = topStack(inStack);
if(b == NULL)
{
fprintf(stderr, “Error: need two operands on stack\n”);
return 1;
}
if(popStack(inStack)!=0)
{
fprintf(stderr, “Error: need two operands on stack\n”);
return 1;
}
if(pushStack(poppedStack,b)!=0)
{
fprintf(stderr, “Error: out of memory popped stack\n”);
return 1;
}
bn_t result = bn_alloc();
if(result == NULL)
{
fprintf(stderr, “Error: out of memory \n”);
return 1;
}
if(strInput[0]==’+’)
{
if(bn_add(result,b,a)!=0)
{
fprintf(stderr, “Error: could not perform add operation\n”);
return 1;
}
}
else if(strInput[0]==’-‘)
{
if(bn_sub(result,b,a)!=0)
{
fprintf(stderr, “Error: could not perform subtract operation\n”);
return 1;
}
}
else if(strInput[0]==’*’)
{
if(bn_mul(result,b,a)!=0)
{
fprintf(stderr, “Error: could not perform multiply operation\n”);
return 1;
}
}
if(pushStack(inStack,result)!=0)
{
fprintf(stderr, “Error: could not push result onto stack\n”);
return 1;
}
}
}
else if(i==3)
{
if(checkIfDup(strInput))
{
if(dupStack(inStack)!=0)
{
fprintf(stderr, “Error: could not perform duplicate operation\n”);
return 1;
}
}
else if(checkIfPop(strInput))
{
bn_t temp = topStack(inStack);
if(temp == NULL)
{
fprintf(stderr, “Error: nothing to pop\n”);
return 1;
}
if(popStack(inStack)!=0)
{
fprintf(stderr, “Error: nothing to pop\n”);
return 1;
}
if(pushStack(poppedStack,temp)!=0)
{
fprintf(stderr, “Error: could not push onto popped stack\n”);
return 1;
}
}
else
{
fprintf(stderr, “Error: Invalid input\n”);
return 1;
}
}
else if(i==4)
{
if(checkIfSwap(strInput))
{
if(swapStack(inStack)!=0)
{
fprintf(stderr, “Error: could not perform swap operation\n”);
return 1;
}
}
else if(checkIfDump(strInput))
{
if(dumpStack(inStack)!=0)
{
fprintf(stderr, “Error: could not perform dump operation\n”);
return 1;
}
}
else
{
fprintf(stderr, “Error: Invalid input\n”);
return 1;
}
}
else if(i==5)
{
if(checkIfClear(strInput))
{
if(clearStack(inStack)!=0 && clearStack(poppedStack)!=0)
{
fprintf(stderr, “Error: could not perform clear operation\n”);
return 1;
}
}
else if(checkIfPrint(strInput))
{
if(printStack(inStack)!=0)
{
fprintf(stderr, “Error: could not perform print operation\n”);
return 1;
}
}
else
{
fprintf(stderr, “Error: Invalid input\n”);
return 1;
}
}
else{
fprintf(stderr, “%s%s\n”,strInput,”Error: Invalid input”);
return 1;
}

}
i = 0;
continue;
}

strInput[i] = (char)c;

i++;

//if i reached maximize size then realloc size
if(i == currSize)
{
currSize = i+lenMax;
if(currSize>=INT_MAX-2000){
fprintf(stderr, “%s%s\n”,strInput,”Error: Maximum input string length reached”);
return 1;
}
strInput = (char* )realloc(strInput, currSize);
if(strInput == NULL)
{
fprintf(stderr, “%s%s\n”,strInput,”Error: Out of memory for input string storage”);
return 1;
}
}

}
if(i>0)
{
strInput[i] = ‘\0’;
//printf(“%s\n”,strInput);
}

//printf(“%s\n”, strInput);
free(strInput);
strInput = NULL;

}
else
{
return 1;
}
if(clearStack(inStack)!=0)
{
// could not clear active stack
return 1;
}
if(clearStack(poppedStack)!=0)
{
// could not clear popped stack
return 1;
}
freeStack(inStack);
freeStack(poppedStack);
return 0;

}

int main()
{
parseInput();

return 0;
}

#include
#include
#include
#include
#include

#include “bn.h”
#include “stack.h”

struct bn
{
int bn_len;
int bn_size;
int bn_sign;
uint16_t *bn_data;
};

// allocates space for 1 element in the array
bn_t bn_alloc(void)
{
bn_t bn = (bn_t)malloc(sizeof(struct bn));
if (bn == NULL)
{
fprintf(stderr, “Error in bn_alloc: could not allocate memory for data\n”);
return NULL;
}

bn->bn_data = (uint16_t *)calloc(1, sizeof(uint16_t));
if (bn->bn_data == NULL)
{
free(bn);
fprintf(stderr, “Error in bn_alloc: could not allocate memory for data\n”);
return NULL;
}
bn->bn_len = 0;
bn->bn_size = 1;
bn->bn_sign = 1;
return bn;
}

void bn_free(bn_t bn)
{
if(bn != NULL)
{
free(bn->bn_data);
free(bn);
}
}

static int bn_resize(bn_t bn, int size)
{
if (size <= bn->bn_size)
return 0;
uint16_t *data = (uint16_t *)realloc(bn->bn_data, size * sizeof(uint16_t));
if (data == NULL)
{
fprintf(stderr, “Error: could not allocate memory\n”);
return -1;
}
for (int i = bn->bn_size; i < size; i++) data[i] = 0; bn->bn_data = data;
bn->bn_size = size;
return 1;
}

static int bn_reallen(bn_t bn)
{
int l = bn->bn_len;
while (l– > 0)
{
if (bn->bn_data[l] != 0)
return l+1;
}
return 0;
}

static void dbn_push(bn_t bn, uint8_t data)
{
uint32_t carry = data;
for (int j = 0; j < bn->bn_len; j++)
{
carry += bn->bn_data[j] * 256;
bn->bn_data[j] = carry % 10000;
carry = carry / 10000;
}
if (carry != 0)
bn->bn_data[bn->bn_len++] = carry;
}

static bn_t todec(bn_t bn)
{
int binlen = bn_reallen(bn);
int declen = ((binlen + 3)/4) * 5;
bn_t dbn = bn_alloc();
if (dbn == NULL)
{
fprintf(stderr, “Error: could not allocate memory\n”);
return NULL;
}
bn_resize(dbn, declen);
for (int i = binlen; i–; ) {
// shift 8 bits to right
dbn_push(dbn, bn->bn_data[i] >> 8);
// bitwise and with 255
dbn_push(dbn, bn->bn_data[i] & 0xFF);
}
return dbn;
}

static void bn_push(bn_t bn, uint8_t data)
{
uint32_t carry = data;
for (int j = 0; j < bn->bn_len; j++)
{
carry += bn->bn_data[j] * 10;
bn->bn_data[j] = carry % 65536;
carry = carry / 65536;
}
if (carry != 0)
bn->bn_data[bn->bn_len++] = carry;
}

int bn_fromString(bn_t bn, const char* s)
{
if(bn == NULL)
{
fprintf(stderr, “Error in bn_fromString: bn is not declared\n”);
return -1;
}

if(bn_resize(bn,(strlen(s)/4)+1)==-1)
{
fprintf(stderr, “Error in bn_fromString: could not convert to bignum from string\n”);
return -1;
}
for (int i = 0; ibn_len = a->bn_size;
b->bn_len = b->bn_size;

a->bn_len = bn_reallen(a);
b->bn_len = bn_reallen(b);

int sizea = a->bn_len;
int sizeb = b->bn_len;

if(result == NULL)
{
fprintf(stderr, “Error in bn_add: bn_t result is not initialized\n”);
return -1;
}

uint32_t carry = 0;

if(sizea>=sizeb)
{
if(bn_resize(result,sizea+1) == -1)
{
fprintf(stderr, “Error in bn_add:\n”);
return -1;
}
result->bn_len = sizea+1;
int i;
for(i = 0; ibn_data[i];
carry += b->bn_data[i];
result->bn_data[i] = carry % 65536;
carry = carry / 65536;
}
for(i=sizeb; ibn_data[i];
result->bn_data[i] = carry % 65536;
carry = carry / 65536;
}
result->bn_data[i] = carry;
}
else{
if(bn_resize(result,sizeb+1) == -1)
{
fprintf(stderr, “Error in bn_add:\n”);
return -1;
}
result->bn_len = sizeb+1;
int i;
for(i = 0; ibn_data[i];
carry += b->bn_data[i];
result->bn_data[i] = carry % 65536;
carry = carry / 65536;
}
for(i = sizea; ibn_data[i];
result->bn_data[i] = carry % 65536;
carry = carry / 65536;
}
result->bn_data[i] = carry;
}
result->bn_len = bn_reallen(result);
return 0;
}

// returns 1 if b is greater than a
static int bn_compare(bn_t a, bn_t b)
{
if(a->bn_len < b->bn_len)
{
return 1;
}
if(a->bn_len == b->bn_len)
{
for(int i=a->bn_len-1; i>=0; i–)
{
// for first digit in b not the same as a and bigger then b is greater
if(a->bn_data[i]!=b->bn_data[i]){
if(b->bn_data[i]>a->bn_data[i])
{
return 1;
}
else{
return 0;
}
}
}
}
return 0;
}

int bn_sub(bn_t result, bn_t a, bn_t b)
{

if(a == NULL || b == NULL || result == NULL)
{
fprintf(stderr, “Error in bn_sub: result, a or b is not initialized\n”);
return -1;
}

a->bn_len = a->bn_size;
b->bn_len = b->bn_size;

a->bn_len = bn_reallen(a);
b->bn_len = bn_reallen(b);

int sizea = a->bn_len;

// if a is not greater than b result should be set to 0
if(bn_compare(a,b) != 0)
{
for(int i = 0; ibn_size ; i++)
{
result->bn_data[i] = 0;
}
}
else
{
if(bn_resize(result, sizea) == -1)
{
fprintf(stderr, “Error in bn_sub:\n”);
return -1;
}
result->bn_len = sizea;
for(int i = 0; ibn_data[i]bn_data[i])
{
a->bn_data[i+1]–;
result->bn_data[i] = (a->bn_data[i]+65536) – (b->bn_data[i]);
}
else
{
result->bn_data[i] = a->bn_data[i] – b->bn_data[i];
}
}
}
result->bn_len = bn_reallen(result);
return 0;
}

int bn_mul(bn_t result, bn_t a, bn_t b)
{
if(a == NULL || b == NULL || result == NULL)
{
fprintf(stderr, “Error in bn_mul: result, a or b is not initialized\n”);
return -1;
}

if(result==a || result==b)
{
fprintf(stderr, “Error in bn_mul: bn_t result cannot be the same as bn_t a or bn_t b\n”);
return -1;
}

a->bn_len = a->bn_size;
b->bn_len = b->bn_size;

a->bn_len = bn_reallen(a);
b->bn_len = bn_reallen(b);

int sizea = a->bn_len;
int sizeb = b->bn_len;

if(bn_resize(result, sizea+sizeb) == -1)
{
fprintf(stderr, “Error in bn_sub:\n”);
return -1;
}
result->bn_len = result->bn_size;

uint32_t carry = 0;
long temp = 0;

for(int i = 0; ibn_data[i+j]+carry+((long)a->bn_data[j]*b->bn_data[i]);
carry = temp/65536;
result->bn_data[i+j] = temp % 65536;
}
result->bn_data[i+sizea] += carry;
}

result->bn_len = bn_reallen(result);
return 0;
}

int bn_toString(bn_t bn, char *buf, int buflen)
{
bn_t dbn = todec(bn);
if (dbn == NULL)
{
fprintf(stderr, “Error in bn_toString: could not allocate memory for data\n”);
return -1;
}

if(buf == NULL)
{
fprintf(stderr, “Error in bn_toString: buf is not initialized\n”);
return -1;
}
int dlen = dbn->bn_len;
//printf(“dbnlen: %i\n”,dlen);
uint16_t *data = dbn->bn_data;

int requiredlen;
if (dlen == 0)
requiredlen = 2;
else
requiredlen = 2 + (bn->bn_sign < 0) + (dlen - 1) * 4 + (data[dlen-1] > 999) +
(data[dlen-1] > 99) +
(data[dlen – 1] > 9);
if (requiredlen > buflen)
{
bn_free(dbn);
fprintf(stderr, “Error in bn_toString: required length of buffer is: %i\n”,requiredlen);
return requiredlen;
}

char *p = buf;

if (dlen == 0)
{
*p++ = ‘0’;
}
else
{
if (bn->bn_sign < 0) *p++ = '-'; dlen--; if (data[dlen] > 999)
*p++ = ‘0’ + (data[dlen] / 1000) % 10;
if (data[dlen] > 99)
*p++ = ‘0’ + (data[dlen] / 100) % 10;
if (data[dlen] > 9)
*p++ = ‘0’ + (data[dlen] / 10) % 10;
*p++ = ‘0’ + data[dlen] % 10;
while (dlen–)
{
*p++ = ‘0’ + (data[dlen] / 1000) % 10;
*p++ = ‘0’ + (data[dlen] / 100) % 10;
*p++ = ‘0’ + (data[dlen] / 10) % 10;
*p++ = ‘0’ + (data[dlen] / 1) % 10;
}
}
*p = ‘\0′;
bn_free(dbn);
return 0;
}

int bn_IAmAnUndergrad()
{
return 1;
}

#ifndef __STACK_H_
#define __STACK_H__ 1

#include “bn.h”

typedef struct stackElement* stEl;
typedef struct stackStore* st;

// initializes the stack
// if int m is set to 1 it will also free space for bn_t elements when popStack is called.
// This can be used in conjunction with a second stack B (m=1) in which elements popped from stack A (m=0)
// are pushed. This is so if elements are duplicated and have the same memory address popping one from
// stack A would not also free the space for the other.]
// returns NULL if memory for stack cannot be allocated
st initStack(int m);

// pushes elements onto the stack
// returns 1 if can’t push element i on to stack
int pushStack(st myStack, bn_t i);

// returns the element on the top of the stack
// returns NULL if no elements on stack
bn_t topStack(st myStack);

// removes element on top of the stack
// returns 1 if nothing to pop
int popStack(st myStack);

// duplicates the top element of the stack and
// pushes it on to the stack
// returns 1 if nothing to duplicate or cant create new element
int dupStack(st myStack);

// prints the contents of top element of the stack to console
// returns 1 if unsuccessful or nothing to print
int printStack(st myStack);

// swaps the top two elements of the stack
// returns 1 if two elements are not present to swap or swap cant be performed
int swapStack(st myStack);

// prints contents of the stack one line at a time starting from the top
// returns 1 if not successful
int dumpStack(st myStack);

// clears the content of the stack
int clearStack(st myStack);

// frees resources for stack head
void freeStack(st myStack);

#endif // __STACK_H__

#ifndef __UTIL_H__
#define __UTIL_H__ 1

// Macro to check if a char is a delimiter.
#define is_delim(x) ((x)==’ ‘||(x)==’\t’)

// Prints an error message and exits.
void error(char* msg1);

char* read_line(FILE* fp);
char** splitline(char* line);

char* newstr(char *str, int length);

void* emalloc(size_t n);
void* erealloc(void *p, size_t n);

#endif // __UTIL_H__

#ifndef __BN_H__
#define __BN_H__ 1

#include

typedef struct bn *bn_t;

struct bn {
int bn_len;
int bn_size;
int bn_sign;
uint16_t *bn_data;
};

bn_t bn_alloc();
void bn_free(bn_t bn);

int bn_resize(bn_t bn, int size);

int bn_add(bn_t result, bn_t a, bn_t b);
int bn_sub(bn_t result, bn_t a, bn_t b);
int bn_mul(bn_t result, bn_t a, bn_t b);

int bn_fromString(bn_t bn, const char *s);
int bn_toString(bn_t bn, char *buf, int buflen);

int bn_sqr(bn_t result, bn_t a);
int bn_div(bn_t quot, bn_t rem, bn_t a, bn_t b);

int bn_IAmAnUndergrad();

void bn_copy_deep(bn_t src, bn_t dst);

#endif // __BN_H__

#include
#include

#include “bn.h”
#include “util.h”

// Simple stack for the calculator.
typedef struct bn_stack {
bn_t* nums;
int capacity;
int size;
} bn_stack;

/**
* Check if a given string is a valid number.
*
* @param number
* @return 1 if it is number, 0 otherwise.
*/
int is_number(char* str) {
int i;
for (i = 0; str[i] != ‘\0’; i++) {
if (str[i] < '0' || str[i] > ‘9’) return 0;
}
return 1;
}

/**
* Allocates memory for a new stack.
*
* @return a pointer to the new stack.
*/
bn_stack* create_stack() {
bn_stack* stack = emalloc(sizeof(bn_stack));
stack->capacity = 10;
stack->nums = emalloc(sizeof(bn_t) * stack->capacity);
stack->size = 0;
return stack;
}

/**
* Pushes a given big number onto the stack.
*
* @param stack
* @param big number to be pushed.
*/
void stack_push(bn_stack* stack, bn_t bn) {
if (stack->size == stack->capacity) {
stack->capacity *= 2;
erealloc(stack->nums, sizeof(bn_t) * stack->capacity);
}
stack->nums[stack->size++] = bn;
}

/**
* Prints a given big number.
*
* @param bn
*/
void bn_print(bn_t bn) {
char* str = NULL;
int len = 0;
len = bn_toString(bn, str, len);
str = emalloc(sizeof(char) * len);
bn_toString(bn, str, len);
printf(“%s\n”, str);
}

/**
* Prints all the numbers on the stack.
*
* @param stack
*/
void dump_stack(bn_stack* stack) {
int i;
for (i = stack->size-1; i >= 0; i–) {
bn_print(stack->nums[i]);
}
}

/**
* Clears the stack. Deleting all the numbers in it.
*
* @param stack
*/
void clear_stack(bn_stack* stack) {
int i;
for (i = stack->size-1; i >= 0; i–) {
bn_free(stack->nums[i]);
}
stack->size = 0;
}

/**
* Pops the top big num from the stack.
*
* @param stack.
*/
bn_t stack_pop(bn_stack* stack) {
if (stack->size == 0) return NULL;
return stack->nums[(stack->size–)-1];
}

/**
* Returns the big num on the top of the stack.
*
* @param stack.
*/
bn_t stack_peek(bn_stack* stack) {
if (stack->size == 0) return NULL;
return stack->nums[stack->size-1];
}

int main() {
char* line;
char** strings;
bn_stack* stack = create_stack();
while ((line = read_line(stdin)) != NULL) {
strings = splitline(line);
char** ptr = strings;

// Process commands.
while (*ptr != NULL) {
char* command = *ptr;

// If a valid number add it to the stack.
if (is_number(command)) {

bn_t new_number = bn_alloc();
bn_fromString(new_number, command);
stack_push(stack, new_number);

} else if (strcmp(command, “+”) == 0 || strcmp(command, “-“) == 0 || strcmp(command, “*”) == 0) {

bn_t a = stack_pop(stack);
bn_t b = stack_pop(stack);
if (a == NULL || b == NULL) {
error(“Bad input: Need numbers first.”);
}
bn_t result = bn_alloc();
switch (command[0]) {
case ‘+’:
bn_add(result, a, b);
break;
case ‘-‘:
bn_sub(result, b, a);
break;
case ‘*’:
bn_mul(result, a, b);
break;
}
stack_push(stack, result);

} else if (strcmp(command, “dup”) == 0) {

bn_t a = stack_peek(stack);
if (a == NULL) {
error(“Bad input: Nothing to duplicate.”);
}
bn_t b = bn_alloc();
bn_copy_deep(a, b);
stack_push(stack, b);

} else if (strcmp(command, “pop”) == 0) {

stack_pop(stack);

} else if (strcmp(command, “print”) == 0) {

bn_t top_bn = stack_peek(stack);
if (top_bn == NULL) {
error(“Bad input: Nothing to print.”);
}
bn_print(top_bn);

} else if (strcmp(command, “swap”) == 0) {

bn_t a = stack_pop(stack);
bn_t b = stack_pop(stack);
if (a == NULL || b == NULL) {
error(“Bad input: Not enough numbers on the stack.”);
}
stack_push(stack, a);
stack_push(stack, b);

} else if (strcmp(command, “dump”) == 0) {

dump_stack(stack);

} else if (strcmp(command, “clear”) == 0) {

clear_stack(stack);

} else {
error(“Bad input: Command is not valid”);
}

ptr++;
}
}

return 0;
}

CFLAGS=-g -Wall -Wextra -I. $(OPTFLAGS)

LIBS=libbn.a $(OPTLIBS)

TARGET_LIB=libbn.a
TARGET=calc
OBJECTS=bn.o util.o

all: $(TARGET)

$(TARGET_LIB): $(OBJECTS)
ar rcs $@ $(OBJECTS)
ranlib $@

$(TARGET): $(TARGET_LIB)
$(CC) -o $@ calc.c $(CFLAGS) -L. -lbn

clean:
rm $(TARGET) $(TARGET_LIB) $(OBJECTS)

#include
#include
#include

#include “util.h”

/**
* Reads the line from an input stream.
*
* @param fp: Input stream.
* @return line: Line that was read.
*/
char* read_line(FILE* fp) {
char *buffer;
int buffer_size = 0;
int cur_pos = 0;
int input_char;

while((input_char = getc(fp)) != EOF) {
// Resize if no space.
if (buffer_size < cur_pos + 1) { if (buffer_size == 0) { buffer = emalloc(BUFSIZ); } else { buffer = erealloc(buffer, buffer_size + BUFSIZ); } buffer_size += BUFSIZ; } // End of line. if (input_char == '\n') { break; } buffer[cur_pos++] = input_char; } // Empty input. if (cur_pos == 0 && input_char == EOF) { return NULL; } buffer[cur_pos] = '\0'; return buffer; } /** * Splits the line into strings, white-space separated. * * @param line: NULL terminated string. * @return array of strings. */ char** splitline(char* line) { char **strings; int spots = 0; int buffer_size = 0; int num_strings = 0; char* cur_string; int length; char* ptr = line; if (line == NULL) { return NULL; } strings = emalloc(BUFSIZ); buffer_size = BUFSIZ; spots = BUFSIZ / sizeof(char*); while (*ptr != '\0') { while (is_delim(*ptr)) { ptr++; } if (*ptr == '\0') { break; } // Resize if needed. if (num_strings + 1 >= spots) {
strings = erealloc(strings, buffer_size + BUFSIZ);
buffer_size += BUFSIZ;
spots += (BUFSIZ/sizeof(char *));
}

// Get the word.
cur_string = ptr;
length = 1;
while (*++ptr != ‘\0’ && !(is_delim(*ptr))) {
length++;
}
strings[num_strings++] = newstr(cur_string, length);
}
strings[num_strings] = NULL;
return strings;
}

/**
* Copies the string to a new char*.
*
* @param str: source string.
* @param length: the length of the string.
* @return new string.
*/
char* newstr(char* str, int length) {
// Allocate memory for the new string.
char* new_string = emalloc(length + 1);

// Null-terminate.
new_string[length] = ‘\0’;

int i;
for (i = 0; i < length; i++) { new_string[i] = str[i]; } return new_string; } /** * Free the memory for an array of strings. * * @param list: array of strings. */ void freelist(char **list) { char** ptr = list; while (*ptr) { free(*ptr++); } free(list); } /** * Malloc with error handling. * * @param n: requested memory. * @return: pointer to the newly allocated memory. */ void* emalloc(size_t n) { void* new_mem; if ((new_mem = malloc(n)) == NULL) { error("Out of memory!"); } return new_mem; } /** * Realloc with error handling. * * @param p: pointer to reallocate. * @param n: new size. * @return: new pointer to the new allocated memory. */ void* erealloc(void *p, size_t n) { void *rv; if ((rv = realloc(p,n)) == NULL) { error("Realloc() failed."); } return rv; } /** * Prints out an error message to stder and exits the program with code 1. * * @param msg: message to print before exiting. */ void error(char* msg) { fprintf(stderr, "%s\n", msg); exit(1); } #include
#include
#include
#include
#include

#include “bn.h”

/**
* Frees up the memory taken by bn.
*
* @param bn: a bn_t number.
*/
void bn_free(bn_t bn) {
free(bn->bn_data);
free(bn);
}

/**
* Makes a given bn zero by clearing the data.
*
* @param num: bn_t to be cleared.
*/
void bn_make_zero(bn_t num) {
int i;
for (i = 0; i < num->bn_size; i++) {
num->bn_data[i] = 0;
}
num->bn_len = 0;
}

/**
* Copies the content a to b. Shallow copy.
* Frees the data memory of the destination.
*
* @param src: source.
* @param dst: destination.
*/
void bn_copy_shallow(bn_t src, bn_t dst) {
free(dst->bn_data);
dst->bn_len = src->bn_len;
dst->bn_size = src->bn_size;
dst->bn_sign = src->bn_sign;
dst->bn_data = src->bn_data;
}

/**
* Copies the content a to b. Deep copy.
*
* @param src: source.
* @param dst: destination.
*/
void bn_copy_deep(bn_t src, bn_t dst) {
bn_resize(dst, src->bn_size);
dst->bn_len = src->bn_len;
dst->bn_size = src->bn_size;
dst->bn_sign = src->bn_sign;
int i;
for (i = 0; i < src->bn_size; i++) {
dst->bn_data[i] = src->bn_data[i];
}
}

/**
* Creates a 1 digit bn.
*
* @params num: uint16 number.
*/
bn_t bn_create_int(uint16_t num) {
bn_t new_bn = bn_alloc();
bn_resize(new_bn, 1);
new_bn->bn_len = 1;
new_bn->bn_data[0] = num;
return new_bn;
}

/**
* Resizes a bn_t to a given size.
*
* @param bn: number to resize.
* @param size: the new size.
* @return 1 if successful, -1 if unsuccessful.
*/
int bn_resize(bn_t bn, int size) {
if (size <= bn->bn_size)
return 0;
uint16_t *data = (uint16_t *)realloc(bn->bn_data, size * sizeof(uint16_t));
if (data == NULL)
return -1;
int i;
for (i = bn->bn_size; i < size; i++) data[i] = 0; bn->bn_data = data;
bn->bn_size = size;
return 1;
}

/**
* Finds the actual length of a bn_t by ignoring the leading 0s.
*
* @param bn: bn_t to be inspected.
* @return the acutal size of the bn_t.
*/
static int bn_reallen(bn_t bn) {
int l = bn->bn_len;
while (l– > 0) {
if (bn->bn_data[l] != 0)
return l+1;
}
return 0;
}

/**
* Pushes a number to decimal bn.
*
* @param bn: bn_t to be modified.
* @param data: number to be added to bn_t.
*/
static void dbn_push(bn_t bn, uint8_t data) {
uint32_t carry = data;
int j;
for (j = 0; j < bn->bn_len; j++) {
carry += bn->bn_data[j] * 256;
bn->bn_data[j] = carry % 10000;
carry = carry / 10000;
}
if (carry != 0)
bn->bn_data[bn->bn_len++] = carry;
}

/**
* Converts a bn_t to a decimal bn_t. i.e. each digit is based 10000.
*
* @param bn: bn_t to be converted.
* @return new decimal bn_t.
*/
static bn_t todec(bn_t bn) {
int binlen = bn_reallen(bn);
int declen = ((binlen + 3)/4) * 5;
bn_t dbn = bn_alloc();
if (dbn == NULL)
return NULL;
bn_resize(dbn, declen);
int i;
for (i = binlen; i–; ) {
dbn_push(dbn, bn->bn_data[i] >> 8);
dbn_push(dbn, bn->bn_data[i] & 0xFF);
}
return dbn;
}

/**
* Allocates memory for a 0 bn.
*
* @return pointer to the new bn.
*/
bn_t bn_alloc(void) {
bn_t bn = (bn_t)malloc(sizeof(struct bn));
if (bn == NULL)
return NULL;
bn->bn_data = (uint16_t *)calloc(1, sizeof(uint16_t));
if (bn->bn_data == NULL) {
free(bn);
return NULL;
}
bn->bn_len = 0;
bn->bn_size = 1;
bn->bn_sign = 1;
return bn;
}

/**
* Turns a bn_t to string. Decimal representation.
*
* @param bn: bn_t to be converted.
* @param buf: empty char array to put the decimal representation into.
* @param buflen: the length of allocated char array.
* @return 0 if successful, -1 otherwise.
*/
int bn_toString(bn_t bn, char *buf, int buflen) {
bn_t dbn = todec(bn);
if (dbn == NULL)
return -1;
int dlen = dbn->bn_len;
uint16_t *data = dbn->bn_data;

int requiredlen;
if (dlen == 0)
requiredlen = 2;
else
requiredlen = 2 + (bn->bn_sign < 0) + (dlen - 1) * 4 + (data[dlen-1] > 999) +
(data[dlen-1] > 99) +
(data[dlen – 1] > 9);
if (requiredlen > buflen) {
bn_free(dbn);
return requiredlen;
}

char *p = buf;

if (dlen == 0) {
*p++ = ‘0’;
} else {
if (bn->bn_sign < 0) *p++ = '-'; dlen--; if (data[dlen] > 999)
*p++ = ‘0’ + (data[dlen] / 1000) % 10;
if (data[dlen] > 99)
*p++ = ‘0’ + (data[dlen] / 100) % 10;
if (data[dlen] > 9)
*p++ = ‘0’ + (data[dlen] / 10) % 10;
*p++ = ‘0’ + data[dlen] % 10;
while (dlen–) {
*p++ = ‘0’ + (data[dlen] / 1000) % 10;
*p++ = ‘0’ + (data[dlen] / 100) % 10;
*p++ = ‘0’ + (data[dlen] / 10) % 10;
*p++ = ‘0’ + (data[dlen] / 1) % 10;
}
}
*p = ‘\0’;
bn_free(dbn);
return 0;
}

/**
* Compares 2 big numbers. Returns 1 if a is bigger than b, 0 if they are equal, and -1 otherwise.
*
* @param a: bn number 1.
* @param b: bn number 2.
*/
int bn_compare(bn_t a, bn_t b) {
int len_num1 = bn_reallen(a);
int len_num2 = bn_reallen(b);
if (len_num1 > len_num2) return 1;
if (len_num1 < len_num2) return -1; int i; for (i = len_num1-1; i >= 0; i–) {
if (a->bn_data[i] > b->bn_data[i]) return 1;
if (a->bn_data[i] < b->bn_data[i]) return -1;
}
return 0;
}

/**
* Adds a and b, stores the results into `result`.
*
* @param result: bn_t to store the result.
* @param a: the first number.
* @param b: the second number to add.
* @return 0 if successful, -1 otherwise.
*/
int bn_add(bn_t result, bn_t a, bn_t b) {
int len_num1 = bn_reallen(a);
int len_num2 = bn_reallen(b);
bn_t num1 = a;
bn_t num2 = b;
// Num1 is the longer number.
if (len_num1 < len_num2) { num1 = b; num2 = a; len_num1 ^= len_num2; len_num2 ^= len_num1; len_num1 ^= len_num2; } // Make sure result is long enough. if (result->bn_size <= len_num1) { bn_resize(result, len_num1+1); } result->bn_len = len_num1;

uint32_t carry = 0;
int i;
for (i = 0; i < len_num1; i++) { if (i < len_num2) { carry += num1->bn_data[i] + num2->bn_data[i];
} else {
carry += num1->bn_data[i];
}
result->bn_data[i] = carry % 0x10000;
carry = carry / 0x10000;
}
if (carry != 0) {
result->bn_data[len_num1] = carry;
result->bn_len++;
}
return 0;
}

/**
* Subtracts b from a, stores the results into `result`. result = 0 if b > a.
*
* @param result: bn_t to store the result.
* @param a: the first number.
* @param b: the second number.
* @return 0 if successful, -1 otherwise.
*/
int bn_sub(bn_t result, bn_t a, bn_t b) {
int len_num1 = bn_reallen(a);
int len_num2 = bn_reallen(b);
int len_re = bn_reallen(result);
bn_t num1 = a;
bn_t num2 = b;
int cmp = bn_compare(a, b);

if (cmp == 0 || cmp == -1) {
bn_make_zero(result);
return 0;
}

// Make sure result is long enough.
if (len_re <= len_num1) { bn_resize(result, len_num1); } int32_t carry = 0; int i; for (i = 0; i < len_num1; i++) { if (i < len_num2) { carry += num1->bn_data[i] – num2->bn_data[i];
} else {
carry += num1->bn_data[i];
}
if (carry > 0) {
result->bn_data[i] = carry % 0x10000;
carry = 0;
} else {
result->bn_data[i] = (carry + 0x10000) % 0x10000;
carry = -1;
}
}
if (carry != 0) {
result->bn_data[len_num1] = carry;
}
result->bn_len = len_num1;
result->bn_len = bn_reallen(result);
return 0;
}

/**
* Multiplies a by b, stores the results into `result`.
*
* @param result: bn_t to store the result.
* @param a: the first number.
* @param b: the second number.
* @return 0 if successful, -1 otherwise.
*/
int bn_mul(bn_t re, bn_t a, bn_t b) {
bn_t result = bn_alloc();
int len_num1 = bn_reallen(a);
int len_num2 = bn_reallen(b);
bn_t num1 = a;
bn_t num2 = b;

// Num1 is the longer number.
if (len_num1 < len_num2) { num1 = b; num2 = a; len_num1 ^= len_num2; len_num2 ^= len_num1; len_num1 ^= len_num2; } // Make sure result is long enough. if (result->bn_size <= len_num1*len_num2) { bn_resize(result, len_num1*(len_num2 + 1)); } result->bn_len = len_num1*(len_num2 + 1);

int i;
for (i = 0; i < len_num1; i++) { uint64_t carry = 0; int j; for (j = 0; j < len_num2; j++) { uint64_t re = ((uint64_t)num1->bn_data[i] * (uint64_t)num2->bn_data[j]) + result->bn_data[i + j] + carry;
carry = re / 0x10000;
result->bn_data[i + j] = re % 0x10000;
}

if (carry != 0) {
result->bn_data[i + len_num2] += carry;
}
}
result->bn_len = bn_reallen(result);
bn_copy_shallow(result, re);
return 0;
}

/**
* Converts a number string to bn.
*
* @param bn: initialized bn_t to store the results into.
* @param s: string to be converted.
* @return 0 if successful, -1 otherwise.
*/
int bn_fromString(bn_t bn, const char *s) {
// Make bn zero and create a ten bn.
bn_make_zero(bn);
bn_t ten = bn_create_int(10);

int i;
for (i = 0; s[i] != ‘\0’; i++) {
uint16_t d = s[i] – ‘0’;
if (d > 9) return -1;
bn_t bn_digit = bn_create_int(d);

bn_mul(bn, bn, ten);

bn_add(bn, bn, bn_digit);

char* str = malloc(sizeof(char)*50);
bn_toString(bn, str, 50);
}
return 0;
}

int bn_IAmAnUndergrad() {
return 1;
}

#include
#include
#include
#include
#include
#include
#include #include
#include “bn.h”

//check for empty
//new node
//push
//pop
//find length

struct stack{
bn_t bn;
struct stack* next;
};

struct stack* head = NULL;

int is_empty(){
if (head == NULL) {
return 1;
}
return 0;
}

struct stack* create_node(bn_t a){
struct stack* node = (struct stack*) malloc(sizeof(struct stack));
node->bn = a;
node->next = NULL;
return node;
}

void push(bn_t a){
struct stack* node = create_node(a);
node->next = head;
head = node;
}

bn_t pop(){
if (is_empty()) {
return NULL;
}
struct stack* node = head;
head = head->next;
bn_t res = node->bn;
free(node);
return res;
}

int dump_stack(){
if (is_empty()) {
// printf(“Stack is empty\n”);
return 1;
}
bn_t bn;
struct stack* node = head;
while (node != NULL) {
bn = node->bn;
printtostring(bn);
node = node->next;
}
return 0;
}

int print_stack_top(){
if (is_empty()) {
// printf(“Stack is empty\n”);
return 1;
}
bn_t bn;
bn = head->bn;
printtostring(bn);
return 0;
}

int clear_stack(){
if (is_empty()) {
// printf(“Stack is empty\n”);
return 0;
}
bn_t bn;
while (head != NULL) {
bn = pop();
bn_free(bn);
}
return 0;
}

int swap_stack(){
if (is_empty()) {
// printf(“Stack is empty\n”);
return 1;
}
bn_t a = pop();
if (is_empty()) {
// printf(“Stack is empty\n”);
return 1;
}
bn_t b = pop();
push(a);
push(b);
return 0;
}

int dup_stack(){
if (is_empty()) {
// printf(“Stack is empty\n”);
return 1;
}
bn_t a = pop();
bn_t b = bn_alloc();
bn_copy(b,a);
push(a);
push(b);
return 0;
}

int add_stack(){
if (is_empty()) {
// printf(“Stack is empty\n”);
return 1;
}
bn_t a = pop();
if (is_empty()) {
// printf(“Stack is empty\n”);
return 1;
}
bn_t b = pop();
bn_t res = bn_alloc();
bn_add(res,a,b);
push(res);
return 0;
}

int sub_stack(){
if (is_empty()) {
// printf(“Stack is empty\n”);
return 1;
}
bn_t a = pop();
if (is_empty()) {
// printf(“Stack is empty\n”);
return 1;
}
bn_t b = pop();
bn_t res = bn_alloc();
bn_sub(res,b,a);
push(res);
return 0;
}

int mul_stack(){
if (is_empty()) {
// printf(“Stack is empty\n”);
return 1;
}
bn_t a = pop();
if (is_empty()) {
// printf(“Stack is empty\n”);
return 1;
}
bn_t b = pop();
bn_t res = bn_alloc();
bn_mul(res,a,b);
push(res);
return 0;
}

void append(char* res, char a){
char *tmp;
tmp = (char*) malloc(2);
tmp[0] = a;
tmp[1] = ‘\0’;
strcat(res, tmp);
free(tmp);
}

void error(){
fprintf(stderr, “Error\n”);
exit(-1);
}

int main() {
char c;
char token[USHRT_MAX];
int digits = 1;
while (1) {
c = getchar();
if (!isdigit(c) && c!= EOF && c != ‘\n’ && !isspace(c)) {
digits = 0;
}
if (c == EOF) {
return 0;
}else if (isspace(c) || c == ‘\n’ || c == EOF) {
if (strcmp(token,”+”) == 0) {
// printf(“add\n”);
if ( add_stack() ) { error(); }
}else if (strcmp(token,”-“) == 0) {
// printf(“sub\n”);
if ( sub_stack() ) { error(); }
}else if (strcmp(token,”*”) == 0) {
// printf(“mul\n”);
// dump_stack();
if ( mul_stack() ) { error(); }
}else if (strcmp(token,”dup”) == 0) {
// printf(“dup\n”);
if ( dup_stack() ) { error(); }
}else if (strcmp(token,”pop”) == 0) {
// printf(“pop\n”);
pop();
}else if (strcmp(token,”print”) == 0) {
// printf(“print\n”);
print_stack_top();
}else if (strcmp(token,”swap”) == 0) {
// printf(“swap\n”);
swap_stack();
}else if (strcmp(token,”dump”) == 0) {
// printf(“dump\n”);
dump_stack();
}else if (strcmp(token,”clear”) == 0) {
// printf(“clear\n”);
clear_stack();
}else if (digits && strlen(token) > 0) {
// printf(“number: %s\n”, token);
bn_t bn = bn_alloc();
bn_fromString(bn,token);
push(bn);
}else if (!digits) {
printf(“? %s\n”, token);
fprintf(stderr, “Error\n”);
return -1;
}
memset(token, 0, sizeof(token));
digits = 1;
}else if (c != ‘\n’) {
append(token,c);
// printf(“%s\n”, token);
}else{
printf(“| %c %s\n”, c, token);
fprintf(stderr, “Error\n”);
return -1;
}
}
return 0;
}

#ifndef __BN_H__
#define __BN_H__ 1

#include
typedef struct bn *bn_t;

struct bn {
int bn_len;
int bn_size;
int bn_sign;
uint16_t *bn_data;
};

bn_t bn_alloc();
void bn_free(bn_t bn);
int bn_resize(bn_t bn, int size);
void printtostring(bn_t a);
void bn_copy(bn_t result, bn_t a);
void printbn(bn_t a);

int bn_add(bn_t result, bn_t a, bn_t b);
int bn_sub(bn_t result, bn_t a, bn_t b);
int bn_mul(bn_t result, bn_t a, bn_t b);

int bn_fromString(bn_t bn, const char *s);
int bn_toString(bn_t bn, char *buf, int buflen);

int bn_sqr(bn_t result, bn_t a);
int bn_div(bn_t quot, bn_t rem, bn_t a, bn_t b);

#endif // __BN_H__

calc: main.c libbn.a
gcc -o calc main.c libbn.a -lm -Wall

libbn.a: bn.o
ar rc libbn.a bn.o
ranlib libbn.a

bn.o: bn.c bn.h
gcc -c bn.c -o bn.o -lm -Wall

#include
#include
#include
#include
#include
#include #include “bn.h”

int bn_IAmAnUndergrad(){
return 1;
}

int MAX(int a, int b){
if (a>b) {
return a;
}
return b;
}

int MIN(int a, int b){
if (abn_data = (uint16_t *)calloc(1, sizeof(uint16_t));
if (bn->bn_data == NULL) {
free(bn);
return NULL;
}
bn->bn_len = 0;
bn->bn_size = 1;
bn->bn_sign = 1;
return bn;
}

void bn_free(bn_t bn) {
free(bn->bn_data);
free(bn);
}

int bn_resize(bn_t bn, int size) {
if (size <= bn->bn_size)
return 0;
uint16_t *data = (uint16_t *)realloc(bn->bn_data, size * sizeof(uint16_t));
if (data == NULL)
return -1;
int i;
for (i = bn->bn_size; i < size; i++) data[i] = 0; bn->bn_data = data;
bn->bn_size = size;
return 1;
}

static int bn_reallen(bn_t bn) {
int l = bn->bn_len;
while (l– > 0) {
if (bn->bn_data[l] != 0)
return l+1;
}
return 0;
}

static void dbn_push(bn_t bn, uint8_t data) {
uint32_t carry = data;
int j;
for (j = 0; j < bn->bn_len; j++) {
carry += bn->bn_data[j] * 256;
bn->bn_data[j] = carry % 10000;
carry = carry / 10000;
}
if (carry != 0)
bn->bn_data[bn->bn_len++] = carry;
}

static bn_t todec(bn_t bn) {
int binlen = bn_reallen(bn);
int declen = ((binlen + 3)/4) * 5;
bn_t dbn = bn_alloc();
if (dbn == NULL)
return NULL;
bn_resize(dbn, declen);
int i;
for (i = binlen; i–; ) {
dbn_push(dbn, bn->bn_data[i] >> 8);
dbn_push(dbn, bn->bn_data[i] & 0xFF);
}
return dbn;
}

int bn_toString(bn_t bn, char *buf, int buflen) {
bn_t dbn = todec(bn);
if (dbn == NULL)
return -1;
int dlen = dbn->bn_len;
uint16_t *data = dbn->bn_data;

int requiredlen;
if (dlen == 0)
requiredlen = 2;
else
requiredlen = 2 + (bn->bn_sign < 0) + (dlen - 1) * 4 + (data[dlen-1] > 999) +
(data[dlen-1] > 99) +
(data[dlen – 1] > 9);
if (requiredlen > buflen) {
bn_free(dbn);
return requiredlen;
}

char *p = buf;

if (dlen == 0) {
*p++ = ‘0’;
} else {
if (bn->bn_sign < 0) *p++ = '-'; dlen--; if (data[dlen] > 999)
*p++ = ‘0’ + (data[dlen] / 1000) % 10;
if (data[dlen] > 99)
*p++ = ‘0’ + (data[dlen] / 100) % 10;
if (data[dlen] > 9)
*p++ = ‘0’ + (data[dlen] / 10) % 10;
*p++ = ‘0’ + data[dlen] % 10;
while (dlen–) {
*p++ = ‘0’ + (data[dlen] / 1000) % 10;
*p++ = ‘0’ + (data[dlen] / 100) % 10;
*p++ = ‘0’ + (data[dlen] / 10) % 10;
*p++ = ‘0’ + (data[dlen] / 1) % 10;
}
}
*p = ‘\0’;
bn_free(dbn);
return 0;
}

uint16_t get_data(int i, bn_t a){
if (i>a->bn_len-1) {
return 0;
}
return a->bn_data[i];
}

int bn_add(bn_t result, bn_t a, bn_t b){
int i = 0, tmpa = 0, tmpb = 0, carry = 0, tmpres = 0;
int maxlen = MAX(a->bn_len,b->bn_len);
if (bn_resize(result,maxlen+1) == -1) {
return -1;
}
result->bn_len = maxlen;
//printf(“maxlen: %d\n”, maxlen);
for (i = 0; i < maxlen; i++) { tmpa = get_data(i,a); tmpb = get_data(i,b); tmpres = tmpa + tmpb + carry; //printf("%d: %d + %d + %d = %d", i, tmpa, tmpb, carry, tmpres); if (USHRT_MAX > tmpres) {
result->bn_data[i] = (uint16_t)tmpres;
carry = 0;
}else{
tmpres = tmpres – USHRT_MAX – 1;
result->bn_data[i] = (uint16_t)tmpres;
carry = 1;
if (i == maxlen-1) {
result->bn_len++;
result->bn_data[i+1] = carry;
}
}
//printf(” | %d ? %d\n”, result->bn_data[i], carry);
}
result->bn_len = bn_reallen(result);
return 0;
}

int is_valid_sub(bn_t result, bn_t a, bn_t b){
int i = 0, tmpa = 0, tmpb = 0;
if (a->bn_len < b->bn_len) {
return 1;
}
//printf(“\n”);
int maxlen = MAX(a->bn_len,b->bn_len);
for (i = maxlen-1; i >= 0; i–) {
tmpa = get_data(i,a);
tmpb = get_data(i,b);
//printf(“%d: %d ? %d\n”, i, tmpa, tmpb);
if (tmpa < tmpb) { return 1; }else if (tmpa > tmpb) {
return 0;
}
}
return 0;
}

int bn_sub(bn_t result, bn_t a, bn_t b){
if (is_valid_sub(result, a, b)) {
bn_fromString(result,”0″);
return 0;
}

int i = 0, tmpa = 0, tmpb = 0, tmpres = 0;
int maxlen = a->bn_len;
if (bn_resize(result,maxlen) == -1) {
return -1;
}
result->bn_len = maxlen;
//printf(“maxlen: %d\n”, maxlen);

for (i = 0; i < maxlen; i++) { tmpa = get_data(i,a); tmpb = get_data(i,b); tmpres = tmpa - tmpb; //printf("%d: %d - %d = %d", i, tmpa, tmpb, tmpres); if (tmpres >= 0) {
result->bn_data[i] = tmpres;
}else{
tmpres = USHRT_MAX + 1 + tmpa – tmpb;
result->bn_data[i] = tmpres;
int j = 0;
while (1) {
j++;
if (a->bn_data[i+j] == 0) {
a->bn_data[i+j] = USHRT_MAX;
}else{
a->bn_data[i+j] -= 1;
break;
}
}
}
//printf(” | %d\n”, result->bn_data[i]);
}
result->bn_len = bn_reallen(result);
return 0;
}

void printbn(bn_t a){
int i;
for (i = 0; i < a->bn_len; i++) {
printf(“%d “, a->bn_data[i]);
}
printf(“\n”);
}

int shift(int value, bn_t a){
a->bn_len = bn_reallen(a);
//printf(“\n”);
// printbn(a);
if (value == 0) {
// printf(“no shift\n”);
return 0;
}
int initsize = a->bn_len;
// printf(“%d\n”, initsize);
uint16_t *tmp = (uint16_t *)malloc(initsize * sizeof(uint16_t));
// printf(“shift\n”);
memcpy(tmp, a->bn_data, initsize * sizeof(uint16_t));
bn_resize(a,a->bn_len+value);
a->bn_len = a->bn_len+value;
int i;
for (i = 0; i < value; i++) { a->bn_data[i] = 0;
}
for (i = 0; i < initsize; i++) { a->bn_data[i+value] = tmp[i];
}
// memset(tmp, 0, sizeof(tmp));
free(tmp);
// printbn(a);
//printf(“shift: %d ? %d | %d\n\n”, value, initsize, a->bn_len);
return 0;
}

void printtostring(bn_t a){
char buf[USHRT_MAX];
bn_toString(a, buf, sizeof(buf));
printf(“%s\n”, buf);
}

void bn_copy(bn_t result, bn_t a) {
bn_resize(result, a->bn_size);
memcpy(result->bn_data, a->bn_data, sizeof(uint16_t)*a->bn_size);
result->bn_sign = a->bn_sign;
result->bn_len = a->bn_len;
}

int bn_mul(bn_t result, bn_t a, bn_t b){
uint16_t *adata = a->bn_data;
uint16_t *bdata = b->bn_data;
int alen = a->bn_len;
int blen = b->bn_len;
int i, j, reslen = alen+blen, carry = 0, tcarry = 0, base = 65536, k = 0;
uint32_t *res = (uint32_t *)malloc(sizeof(uint32_t) * reslen);
if(res == NULL){
return -1;
}
for(i = 0; i < reslen; i++){ res[i] = 0; } uint32_t tempres = 0; for(i = 0; i < blen; i++){ carry = 0; for(j = 0; j < alen; j++){ tcarry = 0; res[j+k] = res[j+k]+(bdata[i]*adata[j])+carry; if(res[j+k] >= base){
tempres = res[j+k];
res[j+k] = tempres%base;
tcarry = tempres/base;
if(j == alen-1){
res[j+k+1] = res[j+k+1]+tcarry;
}
}
carry = tcarry;
}
k = k+1;
}
if(bn_resize(result,reslen) < 0){ return -1; } result->bn_len = reslen;
for(i = 0; i < reslen; i++){ result->bn_data[i] = res[i];
}

result->bn_len = bn_reallen(result);
return 0;
}

uint16_t mod(const char *str,int maxshort){
uint16_t res = 0, i = 0;
for (i = 0; i < strlen(str); i++) { res = (res * 10 + (uint16_t)str[i] - '0') % maxshort; } return res; } int longDivision(char* result, const char number[], int divisor){ int j = 0; int temp = number[j] - '0'; while (temp < divisor){ temp = temp * 10 + (number[++j] - '0'); } long i = -1; while (strlen(number) > j){
i++;
result[i] = (temp / divisor) + ‘0’;
temp = (temp % divisor) * 10 + number[++j] – ‘0’;
}
if (strlen(result) == 0){
result = “0”;
return -1;
}
result[i+1] = ‘\0’;
return 0;
}

int comp(char str[]){
int maxlen = strlen(str);
if (maxlen > 5) {
return 1;
}
int tmp = atoi(str);
if (tmp > USHRT_MAX) {
return 1;
}
return 0;
}

int bn_fromString(bn_t bn, const char *str){
int maxlen = strlen(str);
int i = 0;
uint16_t remain = 0;
char quotient[maxlen];
int maxshort = (int)USHRT_MAX+1;

bn_resize(bn, maxlen);
bn->bn_len = maxlen;

remain = mod(str,maxshort);
longDivision(quotient, str, maxshort);
//printf(“%s | %d\n”, quotient, remain);
bn->bn_data[i] = remain;
while (comp(quotient)) {
i++;
remain = mod(quotient,maxshort);
bn->bn_data[i] = remain;
longDivision(quotient, quotient, maxshort);
//printf(“%s | %d\n”, quotient, remain);
}
i++;
remain = mod(quotient,maxshort);
//printf(“0 | %d\n”, remain);
bn->bn_data[i] = remain;
bn->bn_len = bn_reallen(bn);
//printbn(bn);
//printtostring(bn);
// printf(“%s %d\n”, quotient, remain);
return 0;
}

#ifndef __BN_H__
#define __BN_H__ 1

typedef struct bn *bn_t;

bn_t bn_alloc();
void bn_free(bn_t bn);

int bn_add(bn_t result, bn_t a, bn_t b);
int bn_sub(bn_t result, bn_t a, bn_t b);
int bn_mul(bn_t result, bn_t a, bn_t b);

int bn_fromString(bn_t bn, const char *s);
int bn_toString(bn_t bn, char *buf, int buflen);

int bn_div(bn_t quotient, bn_t remainder, bn_t numerator, bn_t denominator);

#endif // __BN_H__

#include
#include
#include
#include
#include

#include “bn.h”

struct bn {
int bn_len;
int bn_size;
int bn_sign;
uint16_t *bn_data;
};

void dump(uint16_t *buf, int n) {
for (int i = n; i–;)
printf(“%04X”, buf[i]);
}

static int bn_resize(bn_t bn, int size) {
if (size <= bn->bn_size)
return 0;
uint16_t *data = (uint16_t *)realloc(bn->bn_data, size * sizeof(uint16_t));
if (data == NULL)
return -1;
for (int i = bn->bn_size; i < size; i++) data[i] = 0; bn->bn_data = data;
bn->bn_size = size;
return 1;
}

static int bn_reallen(bn_t bn) {
int l = bn->bn_len;
while (l– > 0) {
if (bn->bn_data[l] != 0)
return l+1;
}
return 0;
}

static void dbn_push(bn_t bn, uint8_t data) {
uint32_t carry = data;
for (int j = 0; j < bn->bn_len; j++) {
carry += bn->bn_data[j] * 256;
bn->bn_data[j] = carry % 10000;
carry = carry / 10000;
}
if (carry != 0)
bn->bn_data[bn->bn_len++] = carry;
}

static bn_t todec(bn_t bn) {
int binlen = bn_reallen(bn);
int declen = ((binlen + 3)/4) * 5;
bn_t dbn = bn_alloc();
if (dbn == NULL)
return NULL;
bn_resize(dbn, declen);
for (int i = binlen; i–; ) {
dbn_push(dbn, bn->bn_data[i] >> 8);
dbn_push(dbn, bn->bn_data[i] & 0xFF);
}
return dbn;
}

bn_t bn_alloc(void) {
bn_t bn = (bn_t)malloc(sizeof(struct bn));
if (bn == NULL)
return NULL;
bn->bn_data = (uint16_t *)calloc(1, sizeof(uint16_t));
if (bn->bn_data == NULL) {
free(bn);
return NULL;
}
bn->bn_len = 0;
bn->bn_size = 1;
bn->bn_sign = 1;
return bn;
}

int bn_toString(bn_t bn, char *buf, int buflen) {
bn_t dbn = todec(bn);
if (dbn == NULL)
return -1;
int dlen = dbn->bn_len;
uint16_t *data = dbn->bn_data;

int requiredlen;
if (dlen == 0)
requiredlen = 2;
else
requiredlen = 2 + (bn->bn_sign < 0) + (dlen - 1) * 4 + (data[dlen-1] > 999) +
(data[dlen-1] > 99) +
(data[dlen – 1] > 9);
if (requiredlen > buflen) {
bn_free(dbn);
return requiredlen;
}

char *p = buf;

if (dlen == 0) {
*p++ = ‘0’;
} else {
if (bn->bn_sign < 0) *p++ = '-'; dlen--; if (data[dlen] > 999)
*p++ = ‘0’ + (data[dlen] / 1000) % 10;
if (data[dlen] > 99)
*p++ = ‘0’ + (data[dlen] / 100) % 10;
if (data[dlen] > 9)
*p++ = ‘0’ + (data[dlen] / 10) % 10;
*p++ = ‘0’ + data[dlen] % 10;
while (dlen–) {
*p++ = ‘0’ + (data[dlen] / 1000) % 10;
*p++ = ‘0’ + (data[dlen] / 100) % 10;
*p++ = ‘0’ + (data[dlen] / 10) % 10;
*p++ = ‘0’ + (data[dlen] / 1) % 10;
}
}
*p = ‘\0’;
bn_free(dbn);
return 0;
}

// shift n digits of b left by d bits and store the result in a.
// Assumptions:
// d < 16 // a and b have space for n digits // The caller will handle setting the length // Returns the carry from the shift static uint16_t shiftleft(uint16_t *a, uint16_t *b, int n, int d) { //printf("shiftleft(res, "); dump(b, n); printf(", %d, %d)\n", n, d); uint32_t carry = 0; for (int i = 0; i < n; i++) { carry |= ((uint32_t)b[i]) << d; a[i] = carry & 0xffff; carry >>= 16;
}
//printf(“shiftleft: %04X + “, carry); dump(a, n); printf(“\n”);
return carry;
}

static uint32_t Step_D3(uint16_t *uj, uint16_t *v, int n) {
uint32_t hat = (uj[n]<<16) + uj[n-1]; uint32_t qhat = hat / v[n-1]; uint32_t rhat = hat % v[n-1]; if (qhat == 0x10000 || ( n>1 && (qhat * v[n-2] > 0x10000 * rhat + uj[n-2]))) {
qhat–;
rhat += v[n-1];
if (rhat < 0x10000 && n>1 && (qhat * v[n-2] > 0x10000 * rhat + uj[n-2])) {
qhat–;
rhat += v[n-1];
}
}
return qhat;
}

static uint16_t Step_D4(uint16_t *uj, uint16_t *v, uint32_t qhat, int n) {
uint32_t borrow = 0;
for (int i = 0; i < n; i++) { borrow += uj[i]; borrow -= qhat * v[i]; uj[i] = borrow & 0xFFFF; borrow >>= 16;
if (borrow)
borrow |= 0xFFFF0000; // The borrow is always non-positive…
}
borrow += uj[n];
uj[n] = borrow & 0xFFFF;
return borrow >> 16; // The return value is 16 bits, so no need for extending the sign bit
}

static void Step_D6(uint16_t *uj, uint16_t *v, int n) {
uint32_t carry = 0;
for (int i = 0; i < n; i++) { carry += uj[i]; carry += v[i]; uj[i] = carry & 0xFFFF; carry >>= 16;
}
carry += uj[n];
uj[n] = carry & 0xFFFF;
//assert(carry > 0xFFFF); // We ignore further carry
}

static void shiftright(uint16_t *u, int n, int d) {
for (int i = 0; i < n; i++) u[i] = (u[i] >> d) | (u[i+1] << (16 - d)); u[n] >>= d;
}

// Using Algorithm 4.3.1 D of Knuth TAOCP
int bn_div(bn_t quotient, bn_t remainder, bn_t numerator, bn_t denominator) {
// Use Knuth’s variable names:
// u — numerator
// v — denominator
// q — quotient
// d — normalisation factor
// n — length of denominator
// m — length difference between numerator and denominator
// b — base = 0x10000
// Our base (b) is 2^16, so we can use the shift method to calculate d.
// We use the space of the remainder for the normalised numerator, so
// need to allocate another variable for that.
if (numerator->bn_sign < 0 || denominator->bn_sign < 0) return -1; if (quotient == numerator || quotient == denominator || quotient == remainder || remainder == numerator || remainder == denominator) return -1; // Step D1 int n = bn_reallen(denominator); if (n == 0) return -1; int d = 0; uint16_t t = denominator->bn_data[n – 1];
assert(t != 0); // This is OK from the calculation of n
while ((t & 0x8000) == 0) {
t <<= 1; d++; } bn_t vbn = bn_alloc(); bn_resize(vbn, n); uint16_t *v = vbn->bn_data;
t = shiftleft(v, denominator->bn_data, n, d);
// Not setting len of vbn because we do not really use it.
assert(t == 0);

int nl = bn_reallen(numerator);
int m = nl < n ? 0 : nl - n; remainder->bn_len = n;
bn_t ubn = remainder;
bn_resize(ubn, m + n + 1);
memset(ubn->bn_data, 0, (m + n + 1) * sizeof(uint16_t));
uint16_t *u = ubn->bn_data;
ubn->bn_data[nl] = shiftleft(u, numerator->bn_data, nl, d);

bn_resize(quotient, m + 1);
quotient->bn_len = m + 1;
uint16_t *q = quotient->bn_data;

// Steps D2, D7
for (int j = m; j >= 0; j–) {
// Step D3
uint32_t qhat = Step_D3(u+j, v, n);

// Step D4
uint16_t borrow = Step_D4(u+j, v, qhat, n);

// Step D5
q[j] = qhat;
if (borrow) {
//Step D6
assert(qhat != 0);
Step_D6(u+j, v, n);
q[j]–;
}
}

// Step D8
assert((u[0] & ((1<

Related Posts