// Ideas
// 1. Hidden header style array.
// 2. Playing around with Bigint add/subtract.

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

// Utility.

#define SWAP(a, b) \
({ __auto_type _x = &(a); __auto_type _y = &(b); \
   __auto_type _t = *_x; *_x = *_y; *_y = _t; \
   (void) 0; })

div_t floordiv(int x, int y) {
    int q = x / y - ((x % y) && (x ^ y) < 0);
    int r = x - y * q;
    return (div_t) {q, r};
}

// Shadow array (private).

typedef struct {
    int count, capacity;
} _ArrHeader;

#define _PTR_TO_HDR(p) ((_ArrHeader*)((char*)p - sizeof(_ArrHeader)))
#define _HDR_TO_PTR(h) ((void*)((char*)h + sizeof(_ArrHeader)))

void *_arr_reserve(void *p, int capacity, int itemsize)
{
    _ArrHeader *self = _PTR_TO_HDR(p);

    if (self->capacity < capacity)
    {
        self = realloc(self, itemsize*capacity + sizeof *self);
        self->capacity = capacity;
    }
    return _HDR_TO_PTR(self);
}

void *_arr_resize(void *p, int count, int itemsize)
{
    p = _arr_reserve(p, count, itemsize);
    _PTR_TO_HDR(p)->count = count;
    return p;
}

void _arr_free(void *p)
{
    if (p != 0)
        free(_PTR_TO_HDR(p));
}

void *_arr_init(void)
{
    _ArrHeader *self = malloc(sizeof *self);
    self->count = 0;
    self->capacity = 0;
    return _HDR_TO_PTR(self);
}

void *_arr_at(void *p, ptrdiff_t i, int itemsize)
{
    int count = _PTR_TO_HDR(p)->count;
    if (i < 0)
        i += count;
    assert(0 <= i && i < count);
    return (char*)p + i*itemsize;
}

void *_arr_append(void *p, const void *v, int itemsize)
{
    _ArrHeader *self = _PTR_TO_HDR(p);

    if (self->count == self->capacity)
    {
        int capacity = self->capacity ? 2*self->capacity : 1;
        p = _arr_reserve(p, capacity, itemsize);
        self = _PTR_TO_HDR(p);
    }
    self->count++;
    memcpy(_arr_at(p, -1, itemsize), v, itemsize);
    return p;
}

// Shadow array (public).

#define arr_init(a) ((a) = _arr_init())
#define arr_free(a) (_arr_free(a), (a) = 0)
#define arr_resize(a, n) ((a) = _arr_resize(a, n, sizeof *(a)))
#define arr_at(a, i) (((__typeof__(a))_arr_at(a, i, sizeof *(a)))[0])
#define arr_append(a, v) ((a) = _arr_append(a, (__typeof__(*(a))[]){v}, sizeof *(a)))

void arr_pop(void *p)
{
    _ArrHeader *self = _PTR_TO_HDR(p);
    assert(self->count > 0);
    self->count--;
}

void arr_clear(void *p)
{
    _PTR_TO_HDR(p)->count = 0;
}

int arr_count(void *p)
{
    return _PTR_TO_HDR(p)->count;
}

int arr_capacity(void *p)
{
    return _PTR_TO_HDR(p)->capacity;
}

// Bigint.

#define INTERNAL_BASE 10

typedef struct {
    int *digit;
    int  sign;
} Bigint;

int _digit_adc(int *x, int m, const int *y, int n, int (*op)(int, int))
{
    assert(m >= n);

    int carry = 0;
    int i;

    for (i = 0; i < n; i++)
    {
        carry = op(x[i], y[i] + carry);
        div_t d = floordiv(carry, INTERNAL_BASE);
        x[i] = d.rem;
        carry = d.quot & 1;
    }
    for (; carry && i < m; i++)
    {
        carry = op(x[i], carry);
        div_t d = floordiv(carry, INTERNAL_BASE);
        x[i] = d.rem;
        carry = d.quot & 1;
    }
    return carry;
}

int _op_add(int x, int y)
{
    return x + y;
}

int _op_sub(int x, int y)
{
    return x - y;
}

int _digit_add(int *x, int m, const int *y, int n)
{
    return _digit_adc(x, m, y, n, _op_add);
}

int _digit_sub(int *x, int m, const int *y, int n)
{
    return _digit_adc(x, m, y, n, _op_sub);
}

int _digit_cmp(const int *x, int m, const int *y, int n)
{
    if (m != n)
        return (m < n) ? -1 : 1;

    for (int i = m; i > 0; i--)
    {
        int s = x[i-1];
        int t = y[i-1];

        if (s != t)
            return (s < t) ? -1 : 1;
    }
    return 0;
}

void _bigint_normalize(Bigint *a)
{
    // Strip leading zeros; ensure zero is unsigned.
    while (arr_count(a->digit) > 1 && arr_at(a->digit, -1) == 0)
        arr_pop(a->digit);
    if (arr_at(a->digit, -1) == 0)
        a->sign = 0;
}

void _bigint_set(Bigint* a, const Bigint* b)
{
    int n = arr_count(b->digit);
    arr_resize(a->digit, n);
    memmove(a->digit, b->digit, n * sizeof *a->digit);
    a->sign = b->sign;
}

void _bigint_set_si(Bigint *a, int v)
{
    arr_clear(a->digit);
    a->sign = v < 0;

    do
    {
        arr_append(a->digit, abs(v % INTERNAL_BASE));
        v /= INTERNAL_BASE;
    }
    while (v != 0);
}

void _bigint_add_lower(Bigint *c, const Bigint *a, const Bigint *b)
{
    int m = arr_count(a->digit);
    int n = arr_count(b->digit);

    if (m < n)
    {
        SWAP(a, b);
        SWAP(m, n);
    }

    _bigint_set(c, a);

    int carry = _digit_add(c->digit, m, b->digit, n);

    if (carry != 0)
        arr_append(c->digit, carry);
    _bigint_normalize(c);
}

void _bigint_sub_lower(Bigint *c, const Bigint *a, const Bigint *b)
{
    int m = arr_count(a->digit);
    int n = arr_count(b->digit);
    int sign = 0;

    if (_digit_cmp(a->digit, m, b->digit, n) < 0)
    {
        SWAP(a, b);
        SWAP(m, n);
        sign = 1;
    }

    _bigint_set(c, a);

    int borrow = _digit_sub(c->digit, m, b->digit, n);

    assert(borrow == 0);
    c->sign = sign;
    _bigint_normalize(c);
}

void _bigint_add(Bigint *c, const Bigint *a, const Bigint *b, int bsign)
{
    if (a->sign == bsign)
    {
        _bigint_add_lower(c, a, b);
        c->sign = a->sign;
    }
    else
    {
        if (a->sign)
            _bigint_sub_lower(c, b, a);
        else
            _bigint_sub_lower(c, a, b);
    }
}

// Bigint (public).

void bigint_free(Bigint *a)
{
    arr_free(a->digit);
}

void bigint_init(Bigint *a)
{
    a->digit = 0;
    a->sign  = 0;
    arr_init(a->digit);
    arr_append(a->digit, 0);
}

void bigint_init_set_si(Bigint *a, int v)
{
    a->digit = 0;
    arr_init(a->digit);
    _bigint_set_si(a, v);
}

void bigint_set(Bigint *a, const Bigint *b)
{
    _bigint_set(a, b);
}

void bigint_set_si(Bigint *a, int v)
{
    _bigint_set_si(a, v);
}

void bigint_swap(Bigint *a, Bigint *b)
{
    Bigint t = *a; *a = *b; *b = t;
}

void bigint_add(Bigint *c, const Bigint *a, const Bigint *b)
{
    _bigint_add(c, a, b, b->sign);
}

void bigint_sub(Bigint *c, const Bigint *a, const Bigint *b)
{
    _bigint_add(c, a, b, !b->sign);
}

void bigint_print(const Bigint *a)
{
    if (a->sign)
        putchar('-');
    for (int i = arr_count(a->digit); i > 0; i--)
        printf("%d", a->digit[i-1]); // Base 10
    putchar('\n');
}

// Main.

void errorabort(const char *msg)
{
    fprintf(stderr, "Error: %s\n", msg);
    exit(1);
}

int _bigint_to_si(const Bigint *a)
{
    int result = 0;
    for (int i = arr_count(a->digit); i > 0; i--)
    {
        if (__builtin_mul_overflow(result, INTERNAL_BASE, &result) ||
            __builtin_add_overflow(result, a->digit[i-1], &result))
            errorabort("overflow");
    }
    return a->sign ? -result : result;
}

void test(int n)
{
    Bigint a; bigint_init(&a);
    Bigint b; bigint_init(&b);
    Bigint t; bigint_init(&t);

    for (int x = -n; x <= n; x++)
        for (int y = -n; y <= n; y++)
        {
            bigint_set_si(&a, x);
            bigint_set_si(&b, y);
            bigint_add(&t, &a, &b);
            assert(_bigint_to_si(&t) == x+y);
            bigint_sub(&t, &a, &b);
            assert(_bigint_to_si(&t) == x-y);
        }

    bigint_free(&a);
    bigint_free(&b);
    bigint_free(&t);
}

void fibonacci(int n, Bigint *result)
{
    Bigint a; bigint_init_set_si(&a, 0);
    Bigint b; bigint_init_set_si(&b, 1);
    Bigint t; bigint_init(&t);

    for (int i = 0; i < n; i++)
    {
        bigint_add(&t, &a, &b);
        bigint_swap(&b, &a); // a -> b
        bigint_swap(&a, &t); // t -> a
    }

    bigint_swap(&a, result);

    bigint_free(&a);
    bigint_free(&b);
    bigint_free(&t);
}

int main(void)
{
    test(123);

    Bigint a; bigint_init(&a);
    Bigint b; bigint_init(&b);
    Bigint c; bigint_init(&c);

    fibonacci(202, &a);
    fibonacci(101, &b);

    bigint_sub(&c, &a, &b);

    bigint_print(&a);
    bigint_print(&b);
    bigint_print(&c);

    bigint_free(&a);
    bigint_free(&b);
    bigint_free(&c);
    return 0;
}