const c = @cImport({
    @cInclude("/usr/include/gmp.h");
});
const std = @import("std");
const Channel = std.event.Channel;

pub const io_mode = .evented;

pub fn main() !void {
    try fact(30000000);
}

fn fact(n: u64) !void {
    var arena = std.heap.ArenaAllocator.init(std.heap.direct_allocator);
    const allocator = &arena.allocator;

    const cores = try std.Thread.cpuCount();

    if (n < cores) {
        var x: c.mpz_t = undefined;
        c.mpz_init(&x);
        mulrange(&x, 1, n);
        c.mpz_clear(&x);
        return;
    }

    var buffer = try allocator.alloc(*c.mpz_t, cores);
    var out = try allocator.create(Channel(*c.mpz_t));
    out.init(buffer);

    var i: usize = 0;
    while (i < cores) : (i += 1) {
        (try allocator.create(@Frame(multrange))).* = async multrange(out, @divFloor(i * n, cores) + 1, @divFloor((i + 1) * n, cores));
    }

    var in = out;
    var procs = cores;

    while (procs > 1) {
        buffer = try allocator.alloc(*c.mpz_t, procs);
        out = try allocator.create(Channel(*c.mpz_t));
        out.init(buffer);
        var odd = procs % 2 == 1;
        procs = @divFloor(procs, 2);
        i = 0;
        while (i < procs) : (i += 1) {
            (try allocator.create(@Frame(mult))).* = async mult(in, out);
        }
        if (odd) {
            out.put(in.get());
            procs += 1;
        }
        in = out;
    }

    var x = in.get();
    c.mpz_clear(x);
}

fn mult(in: *Channel(*c.mpz_t), out: *Channel(*c.mpz_t)) void {
    const a = in.get();
    const b = in.get();

    c.mpz_mul(a, a, b);
    out.put(a);
    c.mpz_clear(b);
}

fn multrange(out: *Channel(*c.mpz_t), a: u64, b: u64) void {
    var x: c.mpz_t = undefined;
    c.mpz_init(&x);
    mulrange(&x, a, b);
    out.put(&x);
}

fn mulrange(out: *c.mpz_t, a: u64, b: u64) void {
    if (a == b) {
        c.mpz_init_set_ui(out, a);
        return;
    }

    var l: c.mpz_t = undefined;
    c.mpz_init(&l);
    var r: c.mpz_t = undefined;
    c.mpz_init(&r);

    const m = @divFloor((a + b), 2);
    mulrange(&l, a, m);
    mulrange(&r, m + 1, b);

    c.mpz_mul(out, &l, &r);

    c.mpz_clear(&l);
    c.mpz_clear(&r);
}