bi.c

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef struct {
	int *data;
	int size;
} bi;

bi *bi_new() {
	bi *a = malloc(sizeof(bi));
	return a;
}

bi *bi_from_string(char *a) {
	bi *b = bi_new();

	int skip = 0;
	while(a[skip] == '0') { skip++; }

	b->size = strlen(a) - skip;

	if(b->size == 0) {
		b->size++;
		b->data = malloc(b->size * sizeof(int));
		b->data[0] = 0;
	} else {
		b->data = malloc(b->size * sizeof(int));
		int i;
		for(i = 0; i < b->size; i++) {
			b->data[i] = a[skip + i] - '0';
		}
	}

	return b;
}

char *bi_to_string(bi *a) {
	char *b = malloc(a->size * sizeof(char));
	int i;
	for(i = 0; i < a->size; i++) {
		b[i] = a->data[i] + '0';
	}
	return b;
}

bi *bi_add(bi *a, bi *b) {
	bi *c = bi_new();
	// max possible size
	c->size = (a->size > b->size ? a->size : b->size) + 1;
	c->data = malloc(c->size * sizeof(int));
	int i = a->size - 1, j = b->size - 1;
	int k = c->size - 1;
	int carry = 0, tmp;

	while(i >= 0 || j >= 0 || carry > 0) {
		if(i >= 0 && j >= 0) {
			tmp = a->data[i] + b->data[j];
		} else if(i >= 0) {
			tmp = a->data[i];
		} else if(j >= 0) {
			tmp = b->data[j];
		} else {
			tmp = 0;
		}
		tmp += carry;
		carry = tmp / 10;
		c->data[k] = tmp % 10;
		i--; j--; k--;
	}

	// this is definitely leaking memory
	if(c->data[0] == 0) { c->size--; c->data++; }
	return c;
}

bi *bi_multiply(bi *a, bi *b) {
	bi *c = bi_new();
	// max size
	c->size = a->size + b->size;
	c->data = malloc(c->size * sizeof(int));
	{ int i; for(i = 0; i < c->size; i++) { c->data[i] = 0; } }

	int i = a->size - 1, j = b->size - 1, k = c->size - 1;
	int carry = 0, tmp, push_left = 0;
	while(i >= 0) {
		k = c->size - 1 - push_left++;
		j = b->size - 1;
		while(j >= 0 || carry > 0) {
			if(j >= 0) {
				tmp = a->data[i] * b->data[j];
			} else {
				tmp = 0;
			}
			tmp += carry;
			carry = tmp / 10;
			c->data[k] += tmp % 10;
			carry += c->data[k] / 10;
			c->data[k] = c->data[k] % 10;
			j--; k--;
		}
		i--;
	}

	// Leaking memory for sure
	while(c->data[0] == 0) { c->size--; c->data++; }
	return c;
}

test.c

#include <assert.h>
#include "bi.c"


int main() {
	// Simple conversion
	char *a = "21739871283971298371298371289371298371298371298371298371293";
	assert(strcmp(a, bi_to_string(bi_from_string(a))) == 0);

	// Remove leading zeros
	char *b = "000123000";
	assert(strcmp("123000", bi_to_string(bi_from_string(b))) == 0);

	// But don't segfault on empty string or string consisting of only zeros
	assert(strcmp("0", bi_to_string(bi_from_string("000"))) == 0);
	assert(strcmp("0", bi_to_string(bi_from_string(""))) == 0);

	char *c = "11111111111111111111111111111111111111111111111111111111111000";
	char *d = "33333333333333333333333333333333333333333333333333333333333789";
	char *e = "44444444444444444444444444444444444444444444444444444444444789";
	assert(strcmp(e, bi_to_string(bi_add(bi_from_string(c),
						bi_from_string(d)))) == 0);

	assert(strcmp("1024", bi_to_string(bi_add(bi_from_string("512"),
						bi_from_string("512")))) == 0);

	// Starting with 1 digit by n digit multiplication
	assert(strcmp("16384", bi_to_string(bi_multiply(bi_from_string("2048"),
						bi_from_string("8")))) == 0);
	// Now multiple
	assert(strcmp("16384", bi_to_string(bi_multiply(bi_from_string("1024"),
						bi_from_string("16")))) == 0);

	char *f = "781239128739123";
	char *g = "902183901283901283019283012938120";
	char *h = "704821365001497990452726836222051105131222068760";
	assert(strcmp(h, bi_to_string(bi_multiply(bi_from_string(f),
						bi_from_string(g)))) == 0);

	printf("Reached the end!\n");
}