// fixed.c
// Proposition for fixing unix time overflow.
// copyright 2024, David Polakovic, licensed under GPLv3
//
// Usage:
//   ./fixed                 start at current time, tick once per real second
//   ./fixed -f              fast mode: tick as fast as possible (no sleep)
//   ./fixed [-f] <seconds>  start at an arbitrary (huge) unix time

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdint.h>
#include <inttypes.h>
#include <time.h>
#include <unistd.h>

// Arbitrary-precision unsigned integer.
// Each limb holds 9 decimal digits (base 10^9), limbs[0] is least significant.
// Example: 1793385125 -> limbs[0] = 793385125, limbs[1] = 1
#define BASE        1000000000u
#define BASE_DIGITS 9

typedef struct {
    uint32_t *limbs;
    int size;      // limbs in use, always >= 1
} BigInt;

static void *xcalloc(size_t n, size_t sz) {
    void *p = calloc(n ? n : 1, sz);
    if (!p) { fprintf(stderr, "out of memory\n"); exit(1); }
    return p;
}

// Drop leading zero limbs, but keep at least one.
static void normalizeBigInt(BigInt *num) {
    while (num->size > 1 && num->limbs[num->size - 1] == 0) {
        num->size--;
    }
}

static BigInt allocBigInt(int size) {
    BigInt num;
    num.size = size;
    num.limbs = xcalloc(size, sizeof *num.limbs);
    return num;
}

// Create a BigInt from a decimal string. Returns size 0 on invalid input.
BigInt initBigInt(const char *str) {
    int len = (int)strlen(str);
    for (int i = 0; i < len; i++) {
        if (str[i] < '0' || str[i] > '9') {
            BigInt bad = { NULL, 0 };
            return bad;
        }
    }

    BigInt num = allocBigInt(len / BASE_DIGITS + 1);
    // Read 9-digit chunks starting from the right end of the string.
    int limb = 0;
    for (int end = len; end > 0; end -= BASE_DIGITS, limb++) {
        int start = end - BASE_DIGITS;
        if (start < 0) start = 0;
        uint32_t value = 0;
        for (int i = start; i < end; i++) {
            value = value * 10 + (uint32_t)(str[i] - '0');
        }
        num.limbs[limb] = value;
    }
    normalizeBigInt(&num);
    return num;
}

void freeBigInt(BigInt *num) {
    free(num->limbs);
    num->limbs = NULL;
    num->size = 0;
}

void printBigInt(const BigInt *num) {
    printf("%" PRIu32, num->limbs[num->size - 1]);
    for (int i = num->size - 2; i >= 0; i--) {
        printf("%09" PRIu32, num->limbs[i]);  // inner limbs keep leading zeros
    }
}

int countDigitsBigInt(const BigInt *num) {
    int digits = (num->size - 1) * BASE_DIGITS;
    uint32_t top = num->limbs[num->size - 1];
    do { digits++; top /= 10; } while (top > 0);
    return digits;
}

// Returns <0, 0, >0 like strcmp. Both must be normalized.
int compareBigInt(const BigInt *a, const BigInt *b) {
    if (a->size != b->size) return a->size > b->size ? 1 : -1;
    for (int i = a->size - 1; i >= 0; i--) {
        if (a->limbs[i] != b->limbs[i]) return a->limbs[i] > b->limbs[i] ? 1 : -1;
    }
    return 0;
}

void addBigInt(const BigInt *a, const BigInt *b, BigInt *result) {
    int maxSize = (a->size > b->size) ? a->size : b->size;
    *result = allocBigInt(maxSize + 1);
    uint32_t carry = 0;
    for (int i = 0; i < maxSize; i++) {
        uint32_t sum = carry;  // max 2*(10^9-1)+1, fits in uint32_t
        if (i < a->size) sum += a->limbs[i];
        if (i < b->size) sum += b->limbs[i];
        carry = sum >= BASE;
        result->limbs[i] = carry ? sum - BASE : sum;
    }
    result->limbs[maxSize] = carry;
    normalizeBigInt(result);
}

// In place: a -= b, requires a >= b.
static void subtractInPlace(BigInt *a, const BigInt *b) {
    int64_t borrow = 0;
    for (int i = 0; i < a->size; i++) {
        int64_t sub = (int64_t)a->limbs[i] - borrow - (i < b->size ? b->limbs[i] : 0);
        borrow = sub < 0;
        if (borrow) sub += BASE;
        a->limbs[i] = (uint32_t)sub;
    }
    normalizeBigInt(a);
}

// result = a - b, requires a >= b.
void subtractBigInt(const BigInt *a, const BigInt *b, BigInt *result) {
    *result = allocBigInt(a->size);
    memcpy(result->limbs, a->limbs, a->size * sizeof *a->limbs);
    subtractInPlace(result, b);
}

void multiplyBigInt(const BigInt *a, const BigInt *b, BigInt *result) {
    *result = allocBigInt(a->size + b->size);
    for (int i = 0; i < a->size; i++) {
        uint64_t carry = 0;
        for (int j = 0; j < b->size; j++) {
            // max (10^9-1)^2 + 2*(10^9-1) < 2^64
            uint64_t p = (uint64_t)a->limbs[i] * b->limbs[j]
                       + result->limbs[i + j] + carry;
            result->limbs[i + j] = (uint32_t)(p % BASE);
            carry = p / BASE;
        }
        result->limbs[i + b->size] = (uint32_t)carry;
    }
    normalizeBigInt(result);
}

// out = a * m, where out->limbs has room for a->size + 1 limbs.
static void multiplySmallInto(const BigInt *a, uint32_t m, BigInt *out) {
    uint64_t carry = 0;
    for (int i = 0; i < a->size; i++) {
        uint64_t p = (uint64_t)a->limbs[i] * m + carry;
        out->limbs[i] = (uint32_t)(p % BASE);
        carry = p / BASE;
    }
    out->limbs[a->size] = (uint32_t)carry;
    out->size = a->size + 1;
    normalizeBigInt(out);
}

// Long division. quotient and/or remainder may be NULL.
// Returns 0 on success, -1 on division by zero.
int divModBigInt(const BigInt *dividend, const BigInt *divisor,
                 BigInt *quotient, BigInt *remainder) {
    if (divisor->size == 1 && divisor->limbs[0] == 0) return -1;

    BigInt q = allocBigInt(dividend->size);
    BigInt cur;

    if (divisor->size == 1) {
        // Fast path: divisor fits in one limb, plain short division.
        uint64_t d = divisor->limbs[0], rem = 0;
        for (int i = dividend->size - 1; i >= 0; i--) {
            uint64_t v = rem * BASE + dividend->limbs[i];
            q.limbs[i] = (uint32_t)(v / d);
            rem = v % d;
        }
        cur = allocBigInt(1);
        cur.limbs[0] = (uint32_t)rem;
    } else {
        // General path: bring down one limb at a time, then find the
        // quotient limb (0 .. 10^9-1) by binary search.
        cur = allocBigInt(dividend->size + 1);
        cur.size = 1;
        BigInt tmp = allocBigInt(divisor->size + 1);

        for (int i = dividend->size - 1; i >= 0; i--) {
            // cur = cur * BASE + next limb
            memmove(&cur.limbs[1], &cur.limbs[0], cur.size * sizeof *cur.limbs);
            cur.limbs[0] = dividend->limbs[i];
            cur.size++;
            normalizeBigInt(&cur);

            uint32_t lo = 0, hi = BASE - 1;
            while (lo < hi) {
                uint32_t mid = lo + (hi - lo + 1) / 2;
                multiplySmallInto(divisor, mid, &tmp);
                if (compareBigInt(&tmp, &cur) <= 0) lo = mid;
                else hi = mid - 1;
            }
            if (lo > 0) {
                multiplySmallInto(divisor, lo, &tmp);
                subtractInPlace(&cur, &tmp);
            }
            q.limbs[i] = lo;
        }
        freeBigInt(&tmp);
    }

    normalizeBigInt(&q);
    normalizeBigInt(&cur);
    if (quotient) *quotient = q; else freeBigInt(&q);
    if (remainder) *remainder = cur; else freeBigInt(&cur);
    return 0;
}

int divideBigInt(const BigInt *dividend, const BigInt *divisor, BigInt *result) {
    return divModBigInt(dividend, divisor, result, NULL);
}

int moduloBigInt(const BigInt *dividend, const BigInt *divisor, BigInt *result) {
    return divModBigInt(dividend, divisor, NULL, result);
}

BigInt loadCurrentUnixTime(void) {
    char timeStr[32];
    snprintf(timeStr, sizeof(timeStr), "%lld", (long long)time(NULL));
    return initBigInt(timeStr);
}

int main(int argc, char **argv) {
    int fast = 0;
    const char *start = NULL;
    for (int i = 1; i < argc; i++) {
        if (strcmp(argv[i], "-f") == 0) fast = 1;
        else start = argv[i];
    }

    BigInt time_f = start ? initBigInt(start) : loadCurrentUnixTime();
    if (time_f.size == 0) {
        fprintf(stderr, "invalid start value: %s\n", start);
        return 1;
    }

    // Average Gregorian year: 365.2425 days = 31556952 s.
    // (365 * 86400 = 31536000 drifts one day every ~4 years.)
    BigInt year_s = initBigInt("31556952");
    BigInt epoch = initBigInt("1970");
    BigInt one = initBigInt("1");

    while (1) {
        BigInt years, secInYear, finalYear;
        divModBigInt(&time_f, &year_s, &years, &secInYear);
        addBigInt(&years, &epoch, &finalYear);

        printf("Unix Time: ");
        printBigInt(&time_f);
        printf("\tModulo: ");
        printBigInt(&secInYear);
        printf("\t(%d digits)\t\tYear: ", countDigitsBigInt(&time_f));
        printBigInt(&finalYear);
        printf("\n");
        fflush(stdout);

        freeBigInt(&years);
        freeBigInt(&secInYear);
        freeBigInt(&finalYear);

        BigInt next;
        addBigInt(&time_f, &one, &next);
        freeBigInt(&time_f);
        time_f = next;

        if (!fast) sleep(1);
    }

    // Unreachable, kept for completeness.
    freeBigInt(&one);
    freeBigInt(&epoch);
    freeBigInt(&year_s);
    freeBigInt(&time_f);
    return 0;
}