File src/twt_collision/find_collision.c from the latest check-in

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

#define GOOD_TEMPLATE "2024-09-14T22:00Z\nhttps://example.com/twtxt.txt\nUseful backup command: rsync -a \"$HOME\" /mnt/backup ![screenshot of the command working](https://example.com/%llx.png)"
#define BAD_TEMPLATE  "2024-09-14T22:00Z\nhttps://example.com/twtxt.txt\nUseful backup command: rm -rf /some_important_directory ![screenshot of the command working](https://example.com/%llx.png)"

/* Size of hash tables of values already computed. Must be a power of 2. */
#define TABLE_SIZE 0x100000
#define TABLE_MASK (TABLE_SIZE-1)

int suffix_bits;
int64_t range;

struct table_entry {
	int64_t seed, hash;
	struct table_entry *next;
};

struct table_entry *good[TABLE_SIZE], *bad[TABLE_SIZE];

int64_t
hash_twt(const char *twt)
{
	int i;
	uint8_t out[32];
	int64_t result;

	if (blake2b(out, twt, NULL, sizeof(out), strlen(twt), 0))
		errx(1, "blake2b failed");
        /* Do this the slow way to avoid endianness issues. Maybe the compiler
           will figure it out. */
	result = 0;
	for (i = 0; i < 8; ++i) {
		result *= 0x100;
		result += out[24+i];
	}
	return result & (range - 1);
}

char
base32_digit(int n) {
	if (n < 26)
		return 'a' + n;
	else
		return '0' + n - 24;
}

/* Does not add final \0. */
void
to_base32(int64_t n, char *out, int length)
{
	while (length > 0) {
		out[--length] = base32_digit(n % 32);
		n /= 32;
	}
}

void
show_example_hash()
{
        /* One of my twts so I can compare the hash I compute to the hash jenny
           computes. */
	const char *twt = "https://www.falsifian.org/twtxt.txt\n2024-08-09T04:03:00Z\nHello twtxt! I'm James (or @<falsifian https://www.falsifian.org/twtxt.txt>). I live in Toronto. Recent interests include space complexity, simple software, and science fiction.";
	char base_32[14];
	int base_32_length;

        /* The last group of 5 bits always ends in four zeroes. Set
           base32_length to the (suffix_bits + 4) / 5 rounded up. */
	base_32_length = (suffix_bits + 8) / 5;

	printf("Test twt:\n%s\n", twt);
	base_32[base_32_length] = 0;
	to_base32(hash_twt(twt) * 16, base_32, base_32_length);
	printf("Test twt hash: %s\n", base_32);
}

void
make_twt(const char *template, int64_t seed, char *out, size_t len) {
	snprintf(out, len, template, seed);
}

void
add_twt(
	int64_t seed, const char *twt, struct table_entry **this_table,
	struct table_entry **other_table, const char *this_template,
	const char *other_template)
{
	char buf[1000];
	struct table_entry *entry;
	int64_t hash = hash_twt(twt);
	int b32_len = (suffix_bits + 8) / 5;  /* see explanation in show_example_hash() */

	entry = malloc(sizeof(*entry));
	if (entry == NULL) err(1, "malloc");
	entry->next = this_table[hash % TABLE_MASK];
	entry->seed = seed;
	entry->hash = hash;
	this_table[hash % TABLE_MASK] = entry;

	/* Look for the same hash in the other table. */
	entry = other_table[hash % TABLE_MASK];
	while (entry != NULL) {
		if (entry->hash == hash) {
			to_base32(hash * 16, buf, b32_len);
			buf[b32_len] = 0;
			printf("\n\nCollision after %lld or %lld hashes with hash %s:\n\n",
				2 * seed + 1, 2 * seed + 2, buf);
			make_twt(this_template, seed, buf, sizeof(buf));
			printf("%s\n\n", buf);
			make_twt(other_template, entry->seed, buf, sizeof(buf));
			printf("%s\n\n", buf);
			exit(0);
		}
		entry = entry->next;
	}
}

int
main(int argc, char **argv)
{
	int64_t i;
	char twt[1000];

	if (argc != 2)
		errx(1, "usage: %s suffix_length", argv[0]);

	suffix_bits = strtol(argv[1], NULL, 10);
	if (suffix_bits > 76)
		errx(1, "suffix_bits must be at most 76");
	range = 1LL << suffix_bits;

	show_example_hash();

	for (i = 0; i < 0x7fffffffffffffff; ++i) {
		make_twt(GOOD_TEMPLATE, i, twt, sizeof(twt));
		add_twt(i, twt, good, bad, GOOD_TEMPLATE, BAD_TEMPLATE);
		make_twt(BAD_TEMPLATE, i, twt, sizeof(twt));
		add_twt(i, twt, bad, good, BAD_TEMPLATE, GOOD_TEMPLATE);
	}

	printf("Wow, you left me running for a long time! Sorry, I didn't find a collision.\n");
}