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

typedef struct {
    unsigned char* digits;
    int length;
} BigUnsignedInt;

int int_length(int n) {
    int count = 0;
    do {
        count++;
        n = n / 10;
    }
    while(n != 0);
    return count;
}

void cleanup(BigUnsignedInt *n) {
    if (n && n->digits) {
        free(n->digits);
        n->digits = NULL;
        n->length = 0;
    }
}


BigUnsignedInt from_integer(unsigned int n) {
    int length = int_length(n);
    unsigned char* digits = malloc(length * sizeof(unsigned char));
    if (!digits) {
        BigUnsignedInt empty = {NULL, 0};
        return empty;
    }
    for(int i = 0; i < length; i++) {
        unsigned char digit = n % 10;
        digits[i] = digit;
        n = n / 10;
    }
    BigUnsignedInt bigUnsignedInt = {digits, length};
    return bigUnsignedInt;
}


BigUnsignedInt multiply(const BigUnsignedInt *a, const BigUnsignedInt *b) {
    if (!a || !b || !a->digits || !b->digits) {
        BigUnsignedInt empty = {NULL, 0};
        return empty;
    }

    int length = a->length + b->length;
    unsigned char* resultDigits = malloc(length * sizeof(unsigned char));
    if (!resultDigits) {
        BigUnsignedInt empty = {NULL, 0};
        return empty;
    }
    memset(resultDigits, 0, length * sizeof(unsigned char));
    for(int i = 0; i < a->length; i++) {
        int carry = 0;
        for(int j = 0; j < b->length; j++) {
            int product = a->digits[i] * b->digits[j] + resultDigits[i + j] + carry;
            resultDigits[i + j] = product % 10;
            carry = product / 10;
        }
        int k = i + b->length;
        while(carry > 0 && k < length) {
            int sum = resultDigits[k] + carry;
            resultDigits[k] = sum % 10;
            carry = sum / 10;
            k++;
        }
    }
    while(length > 1 && resultDigits[length - 1] == 0) {
        length--;
    }
    BigUnsignedInt result = {resultDigits, length};
    return result;
}

BigUnsignedInt factorial(unsigned int n) {
    if(n <= 1) {
        return from_integer(1);
    }
    BigUnsignedInt m = from_integer(n);
    if (!m.digits) {
        BigUnsignedInt empty = {NULL, 0};
        return empty;
    }

    BigUnsignedInt o = factorial(n - 1);
    if (!o.digits) {
        cleanup(&m);
        BigUnsignedInt empty = {NULL, 0};
        return empty;
    }

    BigUnsignedInt result = multiply(&m, &o);
    cleanup(&m);
    cleanup(&o);
    return result;
}

void print_bigint(BigUnsignedInt *n) {
    for(int i = n->length - 1; i >= 0; i--) {
        printf("%d", n->digits[i]);
    }
}

void extraLongFactorials(int n) {
    BigUnsignedInt result = factorial(n);
    print_bigint(&result);
    cleanup(&result);
}