/*
 * CRC32C multicollision name generator for DF-2628.
 *
 * hammer2_dirhash() (sys/vfs/hammer2/hammer2_subr.c:178) maps a filename
 * without '.', '-', '_', '~' delimiters to a 64-bit key that is a pure
 * function of c = iscsi_crc32(name) = CRC32C(name) (Castagnoli poly
 * 0x1EDC6F41 reflected 0x82F63B78, init ~0, xorout ~0):
 *
 *      key = 0x8000000000000000 | (c << 32) | ((c ^ (c << 16)) & 0xFFFF0000) | 0x8000
 *
 * so N distinct 8-char names sharing one CRC32C value all hash to the same
 * key and hammer2_dirent_create() packs them into consecutive slots
 * X8000, X8001, ... of the same 64K collision window.  32768 such names
 * exhaust the window; the next same-key link(2) target makes
 * hammer2_dirent_create() return ENOSPC deterministically
 * (hammer2_inode.c:1324-1326).
 *
 * We find 8-char names with crc32c == T by meet-in-the-middle over 4-char
 * halves:  crc32c(A||B) = ~( S32(~crc32c(A)) ^ r0(B) )  where S32 is the
 * linear operator of 32 zero bits and r0(B) the raw state of B from 0.
 *
 * Usage: gen_names <target-crc-hex> <count> <names.txt>
 * (each emitted name is re-verified by direct crc32c before output)
 */
#include <stdio.h>
#include <stdint.h>
#include <stdlib.h>
#include <string.h>

static uint32_t tbl[256];

static void
mk_tbl(void)
{
	uint32_t i, j, c;
	for (i = 0; i < 256; ++i) {
		c = i;
		for (j = 0; j < 8; ++j)
			c = (c >> 1) ^ (0x82F63B78 & (-(c & 1)));
		tbl[i] = c;
	}
}

static uint32_t
raw_update(uint32_t r, const char *b, size_t n)
{
	size_t i;
	for (i = 0; i < n; ++i)
		r = (r >> 8) ^ tbl[(r ^ (uint8_t)b[i]) & 0xFF];
	return r;
}

static uint32_t
crc32c(const char *b, size_t n)
{
	return raw_update(0xFFFFFFFF, b, n) ^ 0xFFFFFFFF;
}

/* ---- GF(2) 32x32 matrix: img[j] = map(1<<j) ----------------------- */
typedef uint32_t gf32_mat[32];

static uint32_t
mat_apply(const gf32_mat m, uint32_t v)
{
	uint32_t r = 0, j;
	for (j = 0; j < 32; ++j)
		if (v & (1u << j))
			r ^= m[j];
	return r;
}

/* shift operator for 32 zero bits (4 zero bytes) on a raw crc state */
static void
mk_shift32(gf32_mat m)
{
	uint32_t j, k, v;
	for (j = 0; j < 32; ++j) {
		v = 1u << j;
		for (k = 0; k < 32; ++k)	/* 32 zero bits */
			v = (v >> 1) ^ (0x82F63B78 & (-(v & 1)));
		m[j] = v;
	}
}

static int
mat_inv(const gf32_mat in, gf32_mat out)
{
	uint32_t a[32][2], i, j, t;
	for (i = 0; i < 32; ++i) {
		a[i][0] = in[i];
		a[i][1] = 1u << i;
	}
	for (i = 0; i < 32; ++i) {
		if (!(a[i][0] & (1u << i))) {
			uint32_t found = 0;
			for (j = i + 1; j < 32; ++j) {
				if (a[j][0] & (1u << i)) {
					t = a[i][0]; a[i][0] = a[j][0]; a[j][0] = t;
					t = a[i][1]; a[i][1] = a[j][1]; a[j][1] = t;
					found = 1;
					break;
				}
			}
			if (!found)
				return -1;
		}
		for (j = 0; j < 32; ++j) {
			if (j != i && (a[j][0] & (1u << i))) {
				a[j][0] ^= a[i][0];
				a[j][1] ^= a[i][1];
			}
		}
	}
	for (i = 0; i < 32; ++i)
		out[i] = a[i][1];
	return 0;
}

/* ---- enumeration -------------------------------------------------- */
static const char alphabet[] =
    "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz";
#define AL 62

struct ent {
	uint32_t crc;
	uint32_t str;	/* index: 4 base-62 digits, str[0] is LSB */
};

static int
cmp_ent(const void *a, const void *b)
{
	uint32_t x = ((const struct ent *)a)->crc;
	uint32_t y = ((const struct ent *)b)->crc;
	return (x < y) ? -1 : (x > y) ? 1 : 0;
}

static void
idx2str(uint32_t s, char *o)
{
	int k;
	for (k = 0; k < 4; ++k) {
		o[k] = alphabet[s % AL];
		s /= AL;
	}
}

int
main(int argc, char **argv)
{
	uint32_t target, crcA;
	int want, emitted = 0;
	const char *outpath;
	FILE *out;
	gf32_mat shift32, shift32inv;
	struct ent *arr;
	size_t total, i, j, k, l, n;
	char a[5], b[5], name[9];
	struct ent key, *hit;
	uint32_t prev;

	if (argc != 4) {
		fprintf(stderr, "usage: %s <target-hex> <count> <out>\n",
		    argv[0]);
		return 1;
	}
	target = (uint32_t)strtoul(argv[1], NULL, 16);
	want = atoi(argv[2]);
	outpath = argv[3];

	mk_tbl();
	/* CRC-32C check value */
	if (crc32c("123456789", 9) != 0xE3069283u) {
		fprintf(stderr, "crc32c self-test FAILED: %08x\n",
		    crc32c("123456789", 9));
		return 1;
	}
	fprintf(stderr, "crc32c self-test ok ('123456789' -> e3069283)\n");
	fprintf(stderr, "target crc32c = %08x, want %d names\n", target, want);

	mk_shift32(shift32);
	if (mat_inv(shift32, shift32inv)) {
		fprintf(stderr, "shift32 not invertible?\n");
		return 1;
	}

	total = (size_t)AL * AL * AL * AL;	/* 14,776,336 */
	arr = malloc(total * sizeof(*arr));
	if (!arr) { perror("malloc"); return 1; }
	fprintf(stderr, "enumerating %zu 4-char halves...\n", total);
	i = 0;
	for (j = 0; j < AL; ++j)
	for (k = 0; k < AL; ++k)
	for (l = 0; l < AL; ++l)
	for (n = 0; n < AL; ++n) {
		arr[i].str = (uint32_t)(j * AL * AL * AL + k * AL * AL +
					l * AL + n);
		idx2str(arr[i].str, a);
		arr[i].crc = crc32c(a, 4);
		++i;
	}
	fprintf(stderr, "sorting...\n");
	qsort(arr, total, sizeof(*arr), cmp_ent);

	out = fopen(outpath, "w");
	if (!out) { perror(outpath); return 1; }
	fprintf(stderr, "meet-in-the-middle join...\n");
	prev = 1;
	for (j = 0; j < AL && emitted < want; ++j)
	for (k = 0; k < AL && emitted < want; ++k)
	for (l = 0; l < AL && emitted < want; ++l)
	for (n = 0; n < AL && emitted < want; ++n) {
		b[0] = alphabet[j]; b[1] = alphabet[k];
		b[2] = alphabet[l]; b[3] = alphabet[n];
		/* need crcA: ~(shift32(~crcA) ^ r0(B)) == T
		 *  => ~crcA = shift32inv(~T ^ r0(B)) */
		crcA = ~mat_apply(shift32inv,
		    ~target ^ raw_update(0, b, 4));
		if (crcA == prev)	/* 4-char space too sparse for 2 hits? */
			continue;
		prev = crcA;
		key.crc = crcA;
		hit = bsearch(&key, arr, total, sizeof(*arr), cmp_ent);
		while (hit && hit >= arr && hit->crc == crcA &&
		    emitted < want) {
			if (hit == arr || (hit - 1)->crc != crcA) {
				idx2str(hit->str, a);
				name[0] = a[0]; name[1] = a[1];
				name[2] = a[2]; name[3] = a[3];
				name[4] = b[0]; name[5] = b[1];
				name[6] = b[2]; name[7] = b[3];
				name[8] = 0;
				/* direct verification - no algebra trust */
				if (crc32c(name, 8) == target) {
					fprintf(out, "%s\n", name);
					++emitted;
					if ((emitted % 5000) == 0)
						fprintf(stderr,
						    "  %d names...\n", emitted);
				}
			}
			--hit;
		}
	}
	fclose(out);
	fprintf(stderr, "emitted %d names with crc32c == %08x -> %s\n",
	    emitted, target, outpath);
	return (emitted == want) ? 0 : 2;
}