// lpm.c — longest prefix match con una tabla de forwarding leída de un archivo.
//
//   ./lpm tabla.txt 10.1.2.3 10.2.0.1
//
// Cada línea de la tabla tiene "prefijo/largo siguiente-salto"; lo que sigue a
// un # es comentario. La búsqueda recorre toda la tabla: es lo más simple de
// leer, pero un router de verdad no puede darse ese lujo (ver el capítulo).
#define _POSIX_C_SOURCE 200809L
#include <arpa/inet.h>
#include <stdint.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define MAX_ROUTES 256
#define HOP_SIZE 32

struct route {
    uint32_t network;   // en orden de host
    uint32_t mask;
    int length;
    char hop[HOP_SIZE];
};

static uint32_t mask_of(int length) {
    return length == 0 ? 0 : UINT32_MAX << (32 - length);
}

static const char *ip_text(uint32_t addr, char *out) {
    struct in_addr raw = {.s_addr = htonl(addr)};
    if (inet_ntop(AF_INET, &raw, out, INET_ADDRSTRLEN) == NULL) {
        perror("inet_ntop");
        exit(1);
    }
    return out;
}

// Lee una línea de la tabla. Devuelve 1 si había una ruta, 0 si la línea estaba
// vacía y -1 si está mal escrita.
static int parse_line(char *line, struct route *route) {
    char *comment = strchr(line, '#');
    if (comment != NULL) {
        *comment = '\0';
    }

    char prefix[32];
    char hop[HOP_SIZE];
    int fields = sscanf(line, "%31s %31s", prefix, hop);
    if (fields <= 0) {
        return 0;
    }
    if (fields != 2) {
        return -1;
    }

    char *slash = strchr(prefix, '/');
    if (slash == NULL) {
        return -1;
    }
    *slash = '\0';

    char *end;
    long length = strtol(slash + 1, &end, 10);
    if (end == slash + 1 || *end != '\0' || length < 0 || length > 32) {
        return -1;
    }

    struct in_addr parsed;
    if (inet_pton(AF_INET, prefix, &parsed) != 1) {
        return -1;
    }

    route->length = (int)length;
    route->mask = mask_of(route->length);
    route->network = ntohl(parsed.s_addr);
    if ((route->network & route->mask) != route->network) {
        return -1;  // el prefijo tiene bits de host encendidos
    }
    strcpy(route->hop, hop);
    return 1;
}

static int load_table(const char *path, struct route *table) {
    FILE *file = fopen(path, "r");
    if (file == NULL) {
        perror(path);
        return -1;
    }

    char line[128];
    int count = 0;
    int line_number = 0;
    while (fgets(line, sizeof line, file) != NULL) {
        line_number++;
        struct route route;
        int result = parse_line(line, &route);
        if (result < 0) {
            fprintf(stderr, "%s:%d: línea inválida\n", path, line_number);
            fclose(file);
            return -1;
        }
        if (result == 1) {
            if (count == MAX_ROUTES) {
                fprintf(stderr, "%s: más de %d rutas\n", path, MAX_ROUTES);
                fclose(file);
                return -1;
            }
            table[count++] = route;
        }
    }
    if (ferror(file)) {
        perror(path);
        fclose(file);
        return -1;
    }
    if (fclose(file) != 0) {
        perror(path);
        return -1;
    }
    return count;
}

// Devuelve la ruta con el prefijo más largo que contiene a addr, o NULL. El
// orden de la tabla no importa: se revisan todas las entradas.
static const struct route *lookup(const struct route *table, int count, uint32_t addr) {
    const struct route *best = NULL;
    for (int i = 0; i < count; i++) {
        const struct route *route = &table[i];
        if ((addr & route->mask) == route->network
            && (best == NULL || route->length > best->length)) {
            best = route;
        }
    }
    return best;
}

int main(int argc, char *argv[]) {
    if (argc < 3) {
        fprintf(stderr, "uso: %s tabla dirección...\n", argv[0]);
        return 2;
    }

    static struct route table[MAX_ROUTES];
    int count = load_table(argv[1], table);
    if (count < 0) {
        return 2;
    }

    for (int a = 2; a < argc; a++) {
        struct in_addr parsed;
        if (inet_pton(AF_INET, argv[a], &parsed) != 1) {
            fprintf(stderr, "lpm: dirección inválida: %s\n", argv[a]);
            return 2;
        }
        uint32_t addr = ntohl(parsed.s_addr);

        printf("%s\n", argv[a]);
        char text[INET_ADDRSTRLEN];
        for (int i = 0; i < count; i++) {
            if ((addr & table[i].mask) == table[i].network) {
                printf("  coincide  %s/%d -> %s\n", ip_text(table[i].network, text),
                       table[i].length, table[i].hop);
            }
        }
        const struct route *best = lookup(table, count, addr);
        if (best == NULL) {
            printf("  sin ruta: se descarta\n");
        } else {
            printf("  gana      %s/%d -> %s\n", ip_text(best->network, text), best->length,
                   best->hop);
        }
    }
    return 0;
}