/* This file is part of limb                           https://lila.oss/limb
 * Copyright (C) 2023 Olivier Brunel                          jjk@jjacky.com */
/* SPDX-License-Identifier: GPL-2.0-only */
#include <limb/u16.h>
#include <limb/u64.h>
#include <limb/output.h>

const char *PROG = "mkrabintables";

#define RABIN_FINGERPRINT 0xBFE6B8A5BF378D83ULL

struct rabin {
    u16 window_size;
    u64 T[256];
    u64 U[256];
};

#define MSB64 (1ULL << 63)

static u64
polymod(u64 nh, u64 nl, u64 d)
{
    int i;
    int k = msb64(d) - 1;
    d <<= 63 - k;

    if (nh) {
        if (nh & MSB64)
            nh ^= d;
        for (i = 62; i >= 0; --i)
            if (nh & ((u64) 1) << i) {
                nh ^= d >> (63 - i);
                nl ^= d << (i + 1);
            }
    }
    for (i = 63; i >= k; --i)
        if (nl & 1ULL << i)
            nl ^= d >> (63 - i);
    return nl;
}

static u64
polymmult(u64 x, u64 y, u64 d)
{
    u64 h = 0, l = 0;
    if (x & 1)
        l = y;
    for (int i = 1; i < 64; ++i)
        if (x & (1ULL << i)) {
            h ^= y >> (64 - i);
            l ^= y << i;
        }
    return polymod(h, l, d);
}

static void
init_tables(struct rabin *r)
{
    int i;
    int xshift = msb64(RABIN_FINGERPRINT) - 1;

    u64 T1 = polymod(0, 1ULL << xshift, RABIN_FINGERPRINT);
    for (i = 0; i < 256; ++i) {
        r->T[i] = polymmult(i, T1, RABIN_FINGERPRINT) | ((u64) i << xshift);
    }

#define SHIFT           55  /* == xshift - 8 */
#define APPEND8(p,m)    (((p) << 8) | m) ^ r->T[(p) >> SHIFT]
    u64 sizeshift = 1;
    for (i = 1; i < r->window_size; ++i)
        sizeshift = APPEND8(sizeshift, 0);

    for (i = 0; i < 256; ++i)
        r->U[i] = polymmult(i, sizeshift, RABIN_FINGERPRINT);
}

#include <stdio.h>
#include <inttypes.h>

int
main(int argc, char **argv)
{
    struct rabin r = { .window_size = 32, };

    if (argc == 2) {
        if (!u16_scan0(&r.window_size, argv[1]))
            retw(1, "invalid window size");
    } else if (argc != 1) {
        dieusage(1, "[WINDOWSIZE]");
    }

    init_tables(&r);

    printf( "#ifndef LIMB_RABIN_TABLES_H\n"
            "#define LIMB_RABIN_TABLES_H\n"
            "\n"
            "#include <limb/int.h>\n"
            "\n"
            "#define RABIN_WINDOW_SIZE %u\n"
            "\n"
            "static struct {\n"
            "	u64 T[256];\n"
            "	u64 U[256];\n"
            "} rabin_tables = { {\n", r.window_size);
    for (int i = 0; i < 256; ++i)
        printf("U64_C(%" PRIu64 ")%s", r.T[i], (i == 255) ? "" : ((i + 1) % 4) ? ", " : ",\n");
    printf("\n}, {\n");
    for (int i = 0; i < 256; ++i)
        printf("U64_C(%" PRIu64 ")%s", r.U[i], (i == 255) ? "" : ((i + 1) % 4) ? ", " : ",\n");
    printf("\n} };\n#endif /* LIMB_RABIN_TABLES_H */");

    return 0;
}