/* dcf_sim: un modelo muy simplificado de CSMA/CA, ranura por ranura, en tráfico saturado.
 *
 *   dcf_sim shared <estaciones> <ranuras>    todos se oyen entre sí
 *   dcf_sim hidden <ranuras>                 dos estaciones que no se oyen, y un access point
 *   dcf_sim hidden_rts <ranuras>             las mismas, con RTS/CTS
 *
 * Una estación espera un backoff al azar y transmite. Sin ACK, duplica la ventana. No es 802.11
 * completo: no hay SIFS ni DIFS ni velocidades, y el ACK y el CTS están dentro de los tiempos de
 * abajo. Sirve para comparar casos, no para predecir megabits. Unidad de tiempo: la ranura.
 */
#include <stdint.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define CW_MIN 16
#define CW_MAX 1024
#define FRAME_SLOTS 150 /* datos más ACK */
#define RTS_SLOTS 4     /* RTS más CTS */
#define MAX_STATIONS 128

static uint64_t rng_state = 0x2545F4914F6CDD1Dull;

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 int new_backoff(int window) {
    return (int)(next_random() % (uint32_t)window);
}

static int next_window(int window) {
    return window * 2 > CW_MAX ? CW_MAX : window * 2;
}

/* Todos se oyen: mientras alguien transmite, los demás congelan su backoff. Solo chocan
 * quienes llegan a cero en la misma ranura. */
static int run_shared(int stations, long slots) {
    int backoff[MAX_STATIONS], window[MAX_STATIONS];
    for (int i = 0; i < stations; i++) {
        window[i] = CW_MIN;
        backoff[i] = new_backoff(window[i]);
    }
    long now = 0, delivered = 0, attempts = 0, failures = 0;
    while (now < slots) {
        int talking = 0;
        for (int i = 0; i < stations; i++) {
            talking += backoff[i] == 0;
        }
        if (talking == 0) {
            for (int i = 0; i < stations; i++) {
                backoff[i]--;
            }
            now++;
            continue;
        }
        attempts += talking;
        if (talking == 1) {
            delivered++;
        } else {
            failures += talking;
        }
        for (int i = 0; i < stations; i++) {
            if (backoff[i] == 0) {
                window[i] = talking == 1 ? CW_MIN : next_window(window[i]);
                backoff[i] = new_backoff(window[i]);
            }
        }
        now += FRAME_SLOTS;
    }
    printf("%3d estaciones que se oyen: tiempo útil %5.1f %%; intentos que chocan %5.1f %%\n", stations,
           100.0 * (double)delivered * FRAME_SLOTS / (double)now,
           attempts ? 100.0 * (double)failures / (double)attempts : 0.0);
    return 0;
}

enum state { BACKOFF, HANDSHAKE, DATA, DEFER };

struct station {
    enum state state;
    int window;
    int left;
    int damaged;
};

static void start_backoff(struct station *station) {
    station->state = BACKOFF;
    station->left = new_backoff(station->window);
}

/* Dos estaciones que el access point oye, pero que no se oyen entre ellas: ninguna congela su
 * backoff por la otra. Si dos transmisiones se solapan en el access point, las dos se dañan.
 * Con RTS/CTS se arriesgan solo unas pocas ranuras, y el CTS hace callar a la otra (DEFER). */
static int run_hidden(int use_rts, long slots) {
    struct station stations[2];
    for (int i = 0; i < 2; i++) {
        stations[i].window = CW_MIN;
        stations[i].damaged = 0;
        start_backoff(&stations[i]);
    }
    long delivered = 0, attempts = 0, failures = 0;
    for (long now = 0; now < slots; now++) {
        for (int i = 0; i < 2; i++) {
            struct station *station = &stations[i];
            if (station->state == BACKOFF && station->left == 0) {
                attempts++;
                station->damaged = 0;
                station->state = use_rts ? HANDSHAKE : DATA;
                station->left = use_rts ? RTS_SLOTS : FRAME_SLOTS;
            }
        }
        int on_air[2];
        for (int i = 0; i < 2; i++) {
            on_air[i] = stations[i].state == HANDSHAKE || stations[i].state == DATA;
        }
        if (on_air[0] && on_air[1]) {
            stations[0].damaged = stations[1].damaged = 1;
        }
        for (int i = 0; i < 2; i++) {
            struct station *station = &stations[i];
            struct station *other = &stations[1 - i];
            station->left--;
            if (station->state == BACKOFF || station->left > 0) {
                if (station->state == BACKOFF && station->left < 0) {
                    station->left = 0;
                }
                continue;
            }
            if (station->state == DEFER) {
                start_backoff(station);
            } else if (station->damaged) {
                failures++;
                station->window = next_window(station->window);
                start_backoff(station);
            } else if (station->state == HANDSHAKE) {
                /* CTS: el access point reserva el medio y la otra estación lo oye. */
                station->state = DATA;
                station->left = FRAME_SLOTS;
                other->state = DEFER;
                other->left = FRAME_SLOTS;
            } else {
                delivered++;
                station->window = CW_MIN;
                start_backoff(station);
            }
        }
    }
    printf("2 estaciones ocultas, %s: tiempo útil %5.1f %%; intentos que chocan %5.1f %%\n",
           use_rts ? "con RTS/CTS" : "sin RTS/CTS",
           100.0 * (double)delivered * FRAME_SLOTS / (double)slots,
           attempts ? 100.0 * (double)failures / (double)attempts : 0.0);
    return 0;
}

static long parse_long(const char *text, long low, long 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 value;
}

int main(int argc, char **argv) {
    if (argc == 4 && strcmp(argv[1], "shared") == 0) {
        return run_shared((int)parse_long(argv[2], 1, MAX_STATIONS), parse_long(argv[3], 1, 1000000000));
    }
    if (argc == 3 && strcmp(argv[1], "hidden") == 0) {
        return run_hidden(0, parse_long(argv[2], 1, 1000000000));
    }
    if (argc == 3 && strcmp(argv[1], "hidden_rts") == 0) {
        return run_hidden(1, parse_long(argv[2], 1, 1000000000));
    }
    fprintf(stderr, "uso: %s shared <estaciones> <ranuras>\n     %s hidden|hidden_rts <ranuras>\n",
            argv[0], argv[0]);
    return 2;
}