// checksum.c — cuatro checksums sobre un archivo y qué errores detecta cada uno.
//
// Uso: ./checksum ARCHIVO [OFFSET]
//
// Calcula XOR (8 bits), Fletcher-16, Adler-32 y CRC-32 de ARCHIVO y luego
// prueba tres daños en una copia en memoria, a partir de OFFSET (por defecto 0):
//   1. un bit volteado          2. el mismo bit volteado en dos bytes
//   3. dos bytes intercambiados
// Para cada daño indica qué checksum lo detecta (cambia) y cuál no.
#include <stdint.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

static uint32_t xor8(const uint8_t *d, size_t n) {
    uint8_t x = 0;
    for (size_t i = 0; i < n; i++)
        x ^= d[i];
    return x;
}

// Fletcher-16: dos sumas módulo 255; s2 acumula s1 y así depende de la posición.
static uint32_t fletcher16(const uint8_t *d, size_t n) {
    uint32_t s1 = 0, s2 = 0;
    for (size_t i = 0; i < n; i++) {
        s1 = (s1 + d[i]) % 255;
        s2 = (s2 + s1) % 255;
    }
    return (s2 << 8) | s1;
}

// Adler-32: la misma idea, módulo 65521 (primo) y s1 empieza en 1.
static uint32_t adler32(const uint8_t *d, size_t n) {
    uint32_t a = 1, b = 0;
    for (size_t i = 0; i < n; i++) {
        a = (a + d[i]) % 65521;
        b = (b + a) % 65521;
    }
    return (b << 16) | a;
}

// CRC-32 (el de Ethernet, zip y gzip), bit a bit: lento pero corto.
static uint32_t crc32(const uint8_t *d, size_t n) {
    uint32_t c = 0xFFFFFFFFu;
    for (size_t i = 0; i < n; i++) {
        c ^= d[i];
        for (int k = 0; k < 8; k++)
            c = (c >> 1) ^ (0xEDB88320u & -(c & 1));
    }
    return ~c;
}

struct algo {
    const char *name;
    uint32_t (*fn)(const uint8_t *, size_t);
};

static const struct algo algos[] = {
    {"XOR-8", xor8}, {"Fletcher-16", fletcher16},
    {"Adler-32", adler32}, {"CRC-32", crc32},
};
#define NALGO (sizeof(algos) / sizeof(algos[0]))

static void check(const char *what, const uint8_t *orig, const uint8_t *bad, size_t n) {
    printf("\n%s\n", what);
    for (size_t a = 0; a < NALGO; a++) {
        uint32_t before = algos[a].fn(orig, n), after = algos[a].fn(bad, n);
        printf("  %-12s %08x -> %08x  %s\n", algos[a].name, before, after,
               before != after ? "detectado" : "NO DETECTADO");
    }
}

int main(int argc, char *argv[]) {
    if (argc < 2) {
        fprintf(stderr, "uso: %s ARCHIVO [OFFSET]\n", argv[0]);
        return 1;
    }
    FILE *f = fopen(argv[1], "rb");
    if (!f) {
        perror(argv[1]);
        return 1;
    }
    fseek(f, 0, SEEK_END);
    long n = ftell(f);
    rewind(f);
    size_t off = argc > 2 ? strtoul(argv[2], NULL, 0) : 0;
    if (n < 2 || off + 1 >= (size_t)n) {
        fprintf(stderr, "el archivo debe tener más de OFFSET+1 bytes\n");
        return 1;
    }
    uint8_t *orig = malloc(n), *bad = malloc(n);
    if (!orig || !bad || fread(orig, 1, n, f) != (size_t)n) {
        fprintf(stderr, "no se pudo leer %s\n", argv[1]);
        return 1;
    }
    fclose(f);
    printf("%s: %ld bytes, daños en el offset %zu\n", argv[1], n, off);
    if (orig[off] == orig[off + 1])
        printf("(aviso: los bytes %zu y %zu son iguales; el daño 3 no cambia nada)\n",
               off, off + 1);

    memcpy(bad, orig, n);
    bad[off] ^= 0x04;
    check("1. Un bit volteado (bit 2 del byte OFFSET)", orig, bad, n);

    memcpy(bad, orig, n);
    bad[off] ^= 0x04;
    bad[off + 1] ^= 0x04;
    check("2. El mismo bit volteado en dos bytes seguidos", orig, bad, n);

    memcpy(bad, orig, n);
    bad[off] = orig[off + 1];
    bad[off + 1] = orig[off];
    check("3. Dos bytes seguidos intercambiados", orig, bad, n);

    free(orig);
    free(bad);
    return 0;
}

// ftl.c — un FTL log-structured de juguete: amplificación de escritura y desgaste.
//
// Uso: ./ftl OCUPACION [hot]
//   OCUPACION  porcentaje (10..90) de la capacidad física que ocupan los datos
//   hot        el 80 % de las escrituras va al 20 % de las páginas lógicas
//
// La SSD tiene NBLK bloques de PPB páginas. Se escriben primero todas las
// páginas lógicas y luego 20 sobrescrituras por página, al azar. Cuando quedan
// menos de GC_LOW bloques libres, el recolector (GC) elige el bloque con menos
// páginas vivas (greedy), copia esas páginas al log y borra el bloque.
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define NBLK 128
#define PPB 32
#define NPAGES (NBLK * PPB)
#define GC_LOW 2

static int map[NPAGES];      // página lógica -> página física (-1: nunca escrita)
static int owner[NPAGES];    // página física -> página lógica (-1: libre o muerta)
static int live[NBLK];       // páginas vivas por bloque
static int erases[NBLK];     // borrados por bloque
static int wp[NBLK];         // siguiente página libre del bloque
static int freeq[NBLK], qhead, nfree;  // cola FIFO de bloques borrados
static int active;           // bloque donde se escribe el log
static long host_writes, gc_writes;

static unsigned long long rng = 88172645463325252ULL;
static unsigned rnd(void) {   // xorshift: mismo resultado en cualquier máquina
    rng ^= rng << 13;
    rng ^= rng >> 7;
    rng ^= rng << 17;
    return (unsigned)(rng >> 11);
}

static void push_free(int b) {
    freeq[(qhead + nfree++) % NBLK] = b;
}

static int pop_free(void) {
    int b = freeq[qhead];
    qhead = (qhead + 1) % NBLK;
    nfree--;
    return b;
}

// Escribe la página lógica lpn al final del log.
static void append(int lpn) {
    if (wp[active] == PPB)
        active = pop_free();
    int ppn = active * PPB + wp[active]++;
    map[lpn] = ppn;
    owner[ppn] = lpn;
    live[active]++;
}

static void gc(void) {
    int victim = -1;
    for (int b = 0; b < NBLK; b++)        // solo bloques llenos y no activos
        if (b != active && wp[b] == PPB && (victim < 0 || live[b] < live[victim]))
            victim = b;
    if (victim < 0 || live[victim] == PPB) {
        fprintf(stderr, "sin espacio para recolectar\n");
        exit(1);
    }
    for (int i = 0; i < PPB; i++) {       // copiar las páginas vivas
        int lpn = owner[victim * PPB + i];
        if (lpn >= 0) {
            owner[victim * PPB + i] = -1;
            append(lpn);
            gc_writes++;
        }
    }
    live[victim] = 0;                     // borrar el bloque completo
    wp[victim] = 0;
    erases[victim]++;
    push_free(victim);
}

static void host_write(int lpn) {
    if (map[lpn] >= 0) {                  // la versión anterior queda muerta
        owner[map[lpn]] = -1;
        live[map[lpn] / PPB]--;
    }
    while (nfree < GC_LOW)
        gc();
    append(lpn);
    host_writes++;
}

int main(int argc, char *argv[]) {
    int util = argc > 1 ? atoi(argv[1]) : 0;
    int hot = argc > 2 && strcmp(argv[2], "hot") == 0;
    if (util < 10 || util > 90) {
        fprintf(stderr, "uso: %s OCUPACION(10..90) [hot]\n", argv[0]);
        return 1;
    }
    int nlog = NPAGES * util / 100;

    memset(map, -1, sizeof(map));
    memset(owner, -1, sizeof(owner));
    for (int b = 1; b < NBLK; b++)
        push_free(b);
    active = 0;

    for (int l = 0; l < nlog; l++)        // llenado inicial
        host_write(l);
    host_writes = gc_writes = 0;
    memset(erases, 0, sizeof(erases));

    long total = 20L * nlog;
    int nhot = nlog / 5;
    for (long i = 0; i < total; i++) {
        int lpn;
        if (hot && rnd() % 100 < 80)
            lpn = rnd() % nhot;
        else if (hot)
            lpn = nhot + rnd() % (nlog - nhot);
        else
            lpn = rnd() % nlog;
        host_write(lpn);
    }

    int emin = erases[0], emax = erases[0];
    long esum = 0;
    for (int b = 0; b < NBLK; b++) {
        if (erases[b] < emin) emin = erases[b];
        if (erases[b] > emax) emax = erases[b];
        esum += erases[b];
    }
    printf("ocupación %2d%%%s: escrituras del host %ld, copias del GC %ld\n",
           util, hot ? " (hot/cold)" : "", host_writes, gc_writes);
    printf("  amplificación de escritura = %.2f\n",
           (double)(host_writes + gc_writes) / host_writes);
    printf("  borrados por bloque: mín %d, prom %.1f, máx %d\n",
           emin, (double)esum / NBLK, emax);
    return 0;
}

// scrub.c — checksums por bloque guardados aparte, y un "scrubber" que los verifica.
//
// Uso: ./scrub sign  ARCHIVO   calcula un CRC-32 por bloque de 4 KiB y lo guarda
//                              en ARCHIVO.sum (como haría el sistema de archivos)
//      ./scrub check ARCHIVO   relee todo el archivo y compara bloque por bloque
//
// El checksum va en un archivo aparte, no junto a cada bloque: así una escritura
// perdida o mal dirigida no se lleva el dato y su checksum a la vez.
#include <stdint.h>
#include <stdio.h>
#include <string.h>

#define BLK 4096

static uint32_t crc32(const uint8_t *d, size_t n) {
    uint32_t c = 0xFFFFFFFFu;
    for (size_t i = 0; i < n; i++) {
        c ^= d[i];
        for (int k = 0; k < 8; k++)
            c = (c >> 1) ^ (0xEDB88320u & -(c & 1));
    }
    return ~c;
}

int main(int argc, char *argv[]) {
    if (argc != 3 || (strcmp(argv[1], "sign") && strcmp(argv[1], "check"))) {
        fprintf(stderr, "uso: %s sign|check ARCHIVO\n", argv[0]);
        return 2;
    }
    int sign = strcmp(argv[1], "sign") == 0;
    char sumname[4096];
    snprintf(sumname, sizeof(sumname), "%s.sum", argv[2]);

    FILE *f = fopen(argv[2], "rb");
    FILE *s = fopen(sumname, sign ? "wb" : "rb");
    if (!f || !s) {
        perror(!f ? argv[2] : sumname);
        return 2;
    }

    uint8_t buf[BLK];
    size_t n, blk = 0;
    int bad = 0;
    while ((n = fread(buf, 1, BLK, f)) > 0) {
        uint32_t now = crc32(buf, n);
        if (sign) {
            fwrite(&now, sizeof(now), 1, s);
        } else {
            uint32_t saved;
            if (fread(&saved, sizeof(saved), 1, s) != 1) {
                printf("bloque %zu: no hay checksum guardado\n", blk);
                bad++;
            } else if (saved != now) {
                printf("bloque %zu: CORRUPTO (guardado %08x, leído %08x)\n", blk, saved, now);
                bad++;
            }
        }
        blk++;
    }
    fclose(f);
    fclose(s);

    if (sign)
        printf("%zu bloques firmados en %s\n", blk, sumname);
    else
        printf("%zu bloques revisados, %d con errores\n", blk, bad);
    return bad ? 1 : 0;
}

# Semana 15: LFS, SSDs, integridad y sistemas distribuidos.
#   make         compila todo
#   make test    corre cada programa con los ejemplos de las diapositivas
#   make clean   borra los binarios y los archivos de prueba
CFLAGS = -Wall -Wextra -g
PROGS  = udprpc checksum scrub ftl
# Las soluciones aún no publicadas (code/.ocultos) no están en el repositorio:
# se omiten los programas sin fuente y sus líneas en las pruebas.
PROGS := $(foreach p,$(PROGS),$(if $(wildcard $(p).c),$(p)))
RUN    = $(if $(wildcard $(1).c),./$(1),@: sin $(1).c)
T      = /tmp/w15

all: $(PROGS)

$(PROGS): %: %.c
	$(CC) $(CFLAGS) -o $@ $<

test: $(PROGS)
	$(call RUN,udprpc) 200 0
	$(call RUN,udprpc) 200 20
	$(call RUN,udprpc) 200 20 dedup
	mkdir -p $(T)
	seq 1 1000 > $(T)/num.txt
	./checksum $(T)/num.txt 100
	seq 1 5000 > $(T)/datos.txt
	./scrub sign $(T)/datos.txt
	./scrub check $(T)/datos.txt
	printf 'X' | dd of=$(T)/datos.txt bs=1 seek=9000 conv=notrunc status=none
	./scrub check $(T)/datos.txt || true
	./ftl 50
	./ftl 70
	./ftl 90
	./ftl 90 hot

clean:
	rm -f $(PROGS)
	rm -rf $(T)

.PHONY: all test clean