/* Part of rainbow tables as graphs, experiment to get some stats */

/* gcc -O3 -lcrypto ossl3.c && time ./a.out */

/*
 * Copyright © 2021 Aleksey Cherepanov <lyosha@openwall.com>
 *
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted.
 */

#pragma GCC diagnostic ignored "-Wdeclaration-after-statement"
#pragma GCC optimize 3

#include <stdio.h>
#include <openssl/md5.h>
#include <string.h>

/* We are generous on allocations due to small keyspace. */
#define total_count (256 * 256 * 256)
#define u64 unsigned long long

/* globals */
u64 graph[total_count];
u64 refs_counts[total_count] = { 0 };

/* index of candidate to next index of candidate */
u64 get_next(u64 idx)
{
    /* index to candidate */
    char buf[21];
    sprintf(buf, "%llu", idx);
    /* candidate to hash */
    MD5_CTX ctx;
    unsigned char hash_out[MD5_DIGEST_LENGTH];
    MD5_Init(&ctx);
    MD5_Update(&ctx, buf, strlen(buf));
    MD5_Final(hash_out, &ctx);
    /* hash to next index */
    u64 r = hash_out[0] * 256 * 256 + hash_out[1] * 256 + hash_out[2];
    return r;
}

int main(void)
{
    printf("total_count: %llu\n", total_count);

    /* Populate graph */
    for (u64 i = 0; i < total_count; i++) {
        graph[i] = get_next(i);
    }

    /* Count references */
    for (u64 i = 0; i < total_count; i++) {
        refs_counts[graph[i]]++;
    }

    /* Count pure leafs */
    u64 leafs_k = 0;
    for (u64 i = 0; i < total_count; i++) {
        if (refs_counts[i] == 0) {
            leafs_k++;
        }
    }
    printf("leafs: %llu\n", leafs_k);
    /* Also all distinguished points as ends of chains are leafs in other chains */

    return 0;
}