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

#define N_UINTS 5
typedef struct _lp_int
{
    unsigned int number[N_UINTS];
} lp_int;

void lpi_init_set_ui(lp_int *lpi, unsigned int initval)
{
    lpi->number[0] = initval;
    for (int i = 1; i < N_UINTS; i++)
        lpi->number[i] = 0;
}

void lpi_out_str(FILE *out, lp_int *lpi)
{
    for (int i = N_UINTS-1; i >= 0; i--)
        fprintf(out, "%.8X", lpi->number[i]);
}

void lpi_add(lp_int *dst, lp_int *src)
{
    #if N_UINTS != 5
    #error FIX THIS
    #endif
    __asm__(
        "addl %1, %0;"
        "adcl %2, 4 %0;"
        "adcl %3, 8 %0;"
        "adcl %4, 12 %0;"
        "adcl %5, 16 %0;"
        "jc 0;" // Overflows crash
        : "=m"(dst->number)
        : "r"(src->number[0]), "r"(src->number[1]), "r"(src->number[2]), "r"(src->number[3]), "r"(src->number[4]));
}

int main(int argc, char *argv[])
{
    const int denominations[] = { 1, 5, 10, 25, 50, 100, 200, 500, 1000, 2000, 5000, 10000 };
    const int lenDenominations = sizeof(denominations)/sizeof(denominations[0]);
    const int target = 9000000;

    lp_int (*table)[lenDenominations] = malloc(sizeof(lp_int)*(target+1)*lenDenominations);
    for (int i = 0; i < lenDenominations; i++)
        lpi_init_set_ui(&table[target][i], 1);

    for (int sumSoFar = target-1; sumSoFar >= 0; sumSoFar--)
    {
        for (int minDenomination = lenDenominations-1; minDenomination >= 0; minDenomination--)
        {
            lpi_init_set_ui(&table[sumSoFar][minDenomination], 0);
            for (int i = minDenomination; i < lenDenominations; i++)
            {
                int newSumSoFar = sumSoFar + denominations[i];
                if (newSumSoFar <= target)
                    lpi_add(&table[sumSoFar][minDenomination], &table[newSumSoFar][i]);
            }
        }
    }

    fprintf(stdout, "Answer (hex): 0x");
    lpi_out_str(stdout, &table[0][0]);
    fputc('\n', stdout);

    return 0;
}