/* ecmp_sim: cuentas sobre el reparto de flujos con un hash, sin red de por medio.
 *
 *   ecmp_sim balance  <caminos> <flujos> <ensayos>   qué tan parejo sale el reparto
 *   ecmp_sim elephant <caminos> <flujos> <ensayos>   flujos grandes que chocan en un camino
 *   ecmp_sim rehash   <caminos> <flujos>             cuántos flujos cambian si muere un camino
 *
 * El hash es FNV-1a sobre la 5-tupla. No es el del kernel, pero sirve igual: lo que importa
 * es que sea determinista por flujo y que reparta como si fuera al azar.
 */
#include <stdint.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define MAX_PATHS 64

struct five_tuple {
    uint32_t source_ip;
    uint32_t dest_ip;
    uint16_t source_port;
    uint16_t dest_port;
    uint8_t protocol;
};

/* Se recorren los campos uno a uno: una struct puede tener relleno sin inicializar. */
static uint32_t fnv_bytes(uint32_t hash, uint64_t value, int count) {
    for (int i = 0; i < count; i++) {
        hash ^= (uint8_t)(value >> (8 * i));
        hash *= 16777619u;
    }
    return hash;
}

static uint32_t hash_flow(const struct five_tuple *flow) {
    uint32_t hash = 2166136261u;
    hash = fnv_bytes(hash, flow->source_ip, 4);
    hash = fnv_bytes(hash, flow->dest_ip, 4);
    hash = fnv_bytes(hash, flow->source_port, 2);
    hash = fnv_bytes(hash, flow->dest_port, 2);
    hash = fnv_bytes(hash, flow->protocol, 1);
    /* FNV mezcla mal los bits altos con entradas cortas: una vuelta más los reparte. */
    hash ^= hash >> 15;
    hash *= 2246822519u;
    hash ^= hash >> 13;
    return hash;
}

/* Generador xorshift con semilla fija: los resultados se pueden repetir. */
static uint64_t rng_state = 0x9E3779B97F4A7C15ull;

static uint32_t next_random(void) {
    rng_state ^= rng_state << 13;
    rng_state ^= rng_state >> 7;
    rng_state ^= rng_state << 17;
    return (uint32_t)(rng_state >> 32);
}

static struct five_tuple random_flow(void) {
    struct five_tuple flow = {.source_ip = next_random(),
                              .dest_ip = next_random(),
                              .source_port = (uint16_t)next_random(),
                              .dest_port = 443,
                              .protocol = 6};
    return flow;
}

/* Módulo: el hash dividido entre la cantidad de caminos. */
static int pick_modulo(uint32_t hash, int paths) {
    return (int)(hash % (uint32_t)paths);
}

/* Hash-threshold (RFC 2992): el espacio del hash se parte en regiones iguales. */
static int pick_threshold(uint32_t hash, int paths) {
    return (int)(((uint64_t)hash * (uint64_t)paths) >> 32);
}

/* Rendezvous: cada camino saca un puntaje con el hash del flujo y gana el mayor. Si muere un
 * camino, solo se mueven los flujos que estaban en él. */
static int pick_rendezvous(uint32_t hash, const int *alive, int paths) {
    int best = -1;
    uint32_t best_score = 0;
    for (int path = 0; path < paths; path++) {
        if (!alive[path]) {
            continue;
        }
        uint32_t score = fnv_bytes(hash, (uint64_t)path, 2);
        score ^= score >> 15;
        score *= 2246822519u;
        score ^= score >> 13;
        if (best < 0 || score > best_score) {
            best = path;
            best_score = score;
        }
    }
    return best;
}

static int run_balance(int paths, int flows, int trials) {
    double ratio_sum = 0;
    double worst_ratio = 0;
    for (int trial = 0; trial < trials; trial++) {
        int load[MAX_PATHS] = {0};
        for (int i = 0; i < flows; i++) {
            struct five_tuple flow = random_flow();
            load[pick_threshold(hash_flow(&flow), paths)]++;
        }
        int largest = 0;
        for (int path = 0; path < paths; path++) {
            if (load[path] > largest) {
                largest = load[path];
            }
        }
        double ratio = (double)largest / ((double)flows / paths);
        ratio_sum += ratio;
        if (ratio > worst_ratio) {
            worst_ratio = ratio;
        }
    }
    printf("%d caminos, %d flujos: el camino más cargado lleva %.2f veces lo justo en promedio "
           "(peor ensayo: %.2f)\n", paths, flows, ratio_sum / trials, worst_ratio);
    return 0;
}

static int run_elephant(int paths, int flows, int trials) {
    /* Cada flujo quiere un enlace completo. Los que comparten un camino se lo reparten, así
     * que el total es la cantidad de caminos ocupados. */
    long clean = 0;
    long used_sum = 0;
    for (int trial = 0; trial < trials; trial++) {
        int load[MAX_PATHS] = {0};
        for (int i = 0; i < flows; i++) {
            struct five_tuple flow = random_flow();
            load[pick_threshold(hash_flow(&flow), paths)]++;
        }
        int used = 0;
        int collision = 0;
        for (int path = 0; path < paths; path++) {
            if (load[path] > 0) {
                used++;
            }
            if (load[path] > 1) {
                collision = 1;
            }
        }
        used_sum += used;
        clean += !collision;
    }
    printf("%d caminos, %d flujos grandes: sin choques en %.1f %% de los ensayos; "
           "caminos ocupados en promedio %.2f; throughput total %.0f %% del ideal\n",
           paths, flows, 100.0 * (double)clean / trials, (double)used_sum / trials,
           100.0 * ((double)used_sum / trials) / (flows < paths ? flows : paths));
    return 0;
}

static int run_rehash(int paths, int flows) {
    int alive[MAX_PATHS];
    for (int path = 0; path < paths; path++) {
        alive[path] = 1;
    }
    /* Muere un camino de en medio: en módulo y en hash-threshold, la tabla
     * se vuelve a numerar con un camino menos. */
    long moved_modulo = 0, moved_threshold = 0, moved_rendezvous = 0, on_dead = 0;
    int dead = paths / 2;
    alive[dead] = 0;
    int remap[MAX_PATHS];
    for (int path = 0, next = 0; path < paths; path++) {
        if (path != dead) {
            remap[next++] = path;
        }
    }
    int all[MAX_PATHS];
    for (int path = 0; path < paths; path++) {
        all[path] = 1;
    }
    for (int i = 0; i < flows; i++) {
        struct five_tuple flow = random_flow();
        uint32_t hash = hash_flow(&flow);
        int before_modulo = pick_modulo(hash, paths);
        int before_threshold = pick_threshold(hash, paths);
        int before_rendezvous = pick_rendezvous(hash, all, paths);
        on_dead += before_threshold == dead;
        moved_modulo += remap[pick_modulo(hash, paths - 1)] != before_modulo;
        moved_threshold += remap[pick_threshold(hash, paths - 1)] != before_threshold;
        moved_rendezvous += pick_rendezvous(hash, alive, paths) != before_rendezvous;
    }
    printf("%d caminos, muere uno; estaban en él: %.1f %% de los flujos\n", paths,
           100.0 * (double)on_dead / flows);
    printf("  módulo:         se mueven %.1f %%\n", 100.0 * (double)moved_modulo / flows);
    printf("  hash-threshold: se mueven %.1f %%\n", 100.0 * (double)moved_threshold / flows);
    printf("  rendezvous:     se mueven %.1f %%\n", 100.0 * (double)moved_rendezvous / flows);
    return 0;
}

static int parse_count(const char *text, int low, int high) {
    char *end;
    long value = strtol(text, &end, 10);
    if (*text == '\0' || *end != '\0' || value < low || value > high) {
        fprintf(stderr, "valor fuera de rango: %s\n", text);
        exit(2);
    }
    return (int)value;
}

int main(int argc, char **argv) {
    if (argc == 5 && strcmp(argv[1], "balance") == 0) {
        return run_balance(parse_count(argv[2], 1, MAX_PATHS), parse_count(argv[3], 1, 10000000),
                           parse_count(argv[4], 1, 100000));
    }
    if (argc == 5 && strcmp(argv[1], "elephant") == 0) {
        return run_elephant(parse_count(argv[2], 1, MAX_PATHS), parse_count(argv[3], 1, 10000),
                            parse_count(argv[4], 1, 10000000));
    }
    if (argc == 4 && strcmp(argv[1], "rehash") == 0) {
        return run_rehash(parse_count(argv[2], 2, MAX_PATHS), parse_count(argv[3], 1, 100000000));
    }
    fprintf(stderr, "uso: %s balance|elephant <caminos> <flujos> <ensayos>\n"
                    "     %s rehash <caminos> <flujos>\n", argv[0], argv[0]);
    return 2;
}