#include <stdio.h>
#include <stdint.h>
#include <stdlib.h>
#include <string.h>
#include <errno.h>
#include <getopt.h>
#include <sys/time.h>

/*--------------------------------------------------------------------*/
#define VERSION  "v1.0 (2-ene-2024)"
/*--------------------------------------------------------------------*/

static const char *optString = "M:m:G:Hvh?";

static const struct option longOpts[] =
{
    {"message",    required_argument,  NULL,   'M'},
    {"msize",      required_argument,  NULL,   'm'},
    {"generator",  required_argument,  NULL,   'G'},
    {"hamming",    no_argument,        NULL,   'H'},
    {"version",    no_argument,        NULL,   'v'},
    {"help",       no_argument,        NULL,   'h'},
    {NULL,         0,                  NULL,    0 }
};

static struct option_help {
    const char *long_opt, *short_opt, *desc;
} opts_help[] = {
    { "--message", "-M",
      "polinomio del mensaje, por ejemplo: 101010" },
    { "--msize", "-m",
      "tamaño del mensaje" },
    { "--generator", "-G",
      "polinomio generador, por ejemplo: 10101" },
    { "--hamming", "-H",
      "calcula la distancia de Hamming del código para mensajes mayores de 14 bits" },     
    { "--version", "-v",
      "Muestra versión y finaliza" },
    { "--help", "-h",
      "Muestra el uso del programa"},
    { NULL, NULL, NULL }
};

/*************************** FUNCTIONS  ***********************/

static void
muestra_version()
{
    fprintf(stderr, "crc %s\n\n", VERSION);
    return;
}
/*--------------------------------------------------------------------*/

static void
muestra_uso(char *name, int exit_code)
{
  struct option_help *h;

  muestra_version();
  printf("uso: %s opciones\n", name);
  for (h = opts_help; h->long_opt; h++)
  {
      printf(" %s, %s\n ", h->short_opt, h->long_opt);
      printf("    %s\n", h->desc);
  }
  exit(exit_code);
}
/*--------------------------------------------------------------------*/

/* convierte cadena de 1s y 0s a formato polinómico:
 * 10101 -> x^4+x^2+1 */
static void showpoly(const char *a)
{
    uint32_t nobits = strlen(a);
    char str1[256] = { 0 };

    if (nobits == 1)
    {
        strcat(str1, a[0] == 0? "0":"1");
        printf("%s", str1);
        return;
    }

    for (uint32_t x = 0; x < nobits - 2; x++)
    {
        if (a[x] == '1')
        {
            if (strlen(str1) > 0) strcat(str1, "+");
            sprintf(str1 + strlen(str1), "x^%u", nobits - x - 1);
        }
    }

    /* casos especiales: términos de grado 1 y 0 */
    if (a[nobits - 2] == '1')
    {
        if (strlen(str1) > 0) strcat(str1, "+");
        strcat(str1, "x");
    }

    if (a[nobits - 1] == '1')
    {
        if (strlen(str1) > 0) strcat(str1, "+");
        strcat(str1, "1");
    }
    printf("%s", str1);
}
/*--------------------------------------------------------------------*/

/* devuelve una cadena con la representación binaria de un número natural
 * 23 -> 10111 */
static const char *bit_rep[16] = {
    [ 0] = "0000", [ 1] = "0001", [ 2] = "0010", [ 3] = "0011",
    [ 4] = "0100", [ 5] = "0101", [ 6] = "0110", [ 7] = "0111",
    [ 8] = "1000", [ 9] = "1001", [10] = "1010", [11] = "1011",
    [12] = "1100", [13] = "1101", [14] = "1110", [15] = "1111",
};

static char *bin_str(uint32_t value, uint32_t width, char *str)
{
    str[0] = 0;
    if ((width == 0) || (width > 32)) width = 8;
    strcat(str, bit_rep[(value >> 28) & 0x0F]);
    strcat(str, bit_rep[(value >> 24) & 0x0F]);
    strcat(str, bit_rep[(value >> 20) & 0x0F]);
    strcat(str, bit_rep[(value >> 16) & 0x0F]);
    strcat(str, bit_rep[(value >> 12) & 0x0F]);
    strcat(str, bit_rep[(value >>  8) & 0x0F]);
    strcat(str, bit_rep[(value >>  4) & 0x0F]);
    strcat(str, bit_rep[(value >>  0) & 0x0F]);
    str[strlen(str)] = 0;
    return str + 32 - width;
}
/*--------------------------------------------------------------------*/

/* Calcula el CRC (Cyclic Redundancy Check) */
// messageSize: nº de bits del mensaje
// generatorSize: nº de bits del polinomio generador (grado + 1)
static uint32_t calcCRC(uint32_t message, uint32_t generator, uint32_t messageSize, uint32_t generatorSize)
{
    uint32_t crc = message << (generatorSize - 1);

    for (uint32_t i = 0; i < messageSize; i++)
    {
        // el bit de más peso del dividendo es 1?
        if (crc & (1 << (messageSize + generatorSize - 2 - i)))
        {
            crc ^= (generator << (messageSize - 1 - i));
        }
    }
    return crc;
}
/*--------------------------------------------------------------------*/


/* Calcula el CRC (Cyclic Redundancy Check) */
// messageSize: nº de bits del mensaje
// generatorSize: nº de bits del polinomio generador (grado + 1)
static uint32_t calcCRCverbose(uint32_t message, uint32_t generator, uint32_t messageSize, uint32_t generatorSize)
{
    char m_str[33] = { 0 }, crc_str[33] = { 0 }, gen_str[33] = { 0 }, zero_str[33] = { 0 };
    char *pg_str, *pz_str, *p_str;
    uint32_t crc = message << (generatorSize - 1);

    // generamos cadenas generador y cero
    pg_str = bin_str(generator, generatorSize, gen_str);
    pz_str = bin_str(0, generatorSize, zero_str);

    // M 0..0 | G
    //         ---
    printf("%s | %s \n", bin_str(crc, messageSize + generatorSize - 1, m_str), bin_str(generator, generatorSize, crc_str));
    printf("%*c ", messageSize + generatorSize, ' '); // imprime messageSize + generatorSize espacios
    // cajetin divisor
    for (uint32_t j = 0; j < generatorSize + 2; j++) putchar('-');
    putchar('\n');

    for (uint32_t i = 0; i < messageSize; i++)
    {
        // printf("%s\n", bin_str(1 << (messageSize + generatorSize - 2 - i), messageSize + generatorSize - 1, m_str));

        printf("%*s", i, "");    // imprime i espacios
        
        // el bit de más peso del dividendo es 1?
        if (crc & (1 << (messageSize + generatorSize - 2 - i)))
        {
            crc ^= (generator << (messageSize - 1 - i));
            // printf("%s (%u)\n", bin_str(crc, messageSize + generatorSize - 1, crc_str), i);

            // imprime el polinomio generador
            printf("%s\n", pg_str);
        }
        else
        {
            // imprime generatorSize ceros
            printf("%s\n", pz_str);
        }

        // imprime línea horizontal bien alineada
        printf("%*s", i, "");    // imprime i espacios
        for (uint32_t j = 0; j < generatorSize; j++) putchar('-');
        putchar('\n');

        // imprime dividendo actualizado
        // no se muestran los caracteres iniciales (sustituidos por espacios)
        // ni los finales
        p_str = bin_str(crc, messageSize + generatorSize - 1, crc_str);
        for (uint32_t j = 0; j < i; j++) p_str[j] = ' ';
        p_str[i] = '/';
        p_str[i + generatorSize + 1] = 0;
        printf("%s\n", p_str);
    }
    printf("\n");
    return crc;
}
/*--------------------------------------------------------------------*/

/* no hace falta escribir un código más complejo para que las siguientes funciones
 * se ejecuten de forma eficiente, el compilador las optimiza */

/* devuelve el número de bits significativos de un valor */
static uint32_t nbits(uint32_t v)
{
    uint32_t r = 0;

    while (v)
    {
        r++;
        v = v >> 1;
    }
    return r;
}
/*--------------------------------------------------------------------*/

/* devuelve el número de 1s en num */
/* Wegner function */
static uint32_t popcount32b(uint32_t num)
{
    uint32_t count = 0;

    while (num > 0)
    {
        count++;
        num = num & (num - 1);
    }
    return count;
}
/*--------------------------------------------------------------------*/

/* devuelve la distancia de Hamming entre a y b */
uint32_t hammingDistance(uint32_t a, uint32_t b)
{
    uint32_t count = popcount32b(a ^ b);
    // printf("hamming(%u,%u) = %u\n", a, b, count);
    return count;
}
/*--------------------------------------------------------------------*/

/* devuelve la posición del 1 menos significativo */
static uint32_t least_significant_bit_set(uint32_t value)
{
   uint32_t pos = 0;
   while ((value & 1) == 0)
   {
      value >>= 1;
      pos++;
   }
   return pos;
}
/*--------------------------------------------------------------------*/

/* Adapted from https://stackoverflow.com/a/1069088/1037634 */
static uint32_t count_ifs(uint32_t n) {
    if (n < 10) return 1;
    if (n < 100) return 2;
    if (n < 1000) return 3;
    if (n < 10000) return 4;
    if (n < 100000) return 5;
    if (n < 1000000) return 6;
    if (n < 10000000) return 7;
    if (n < 100000000) return 8;
    if (n < 1000000000) return 9;
    /* 4294967295 is 2^32-1 */
    return 10;
}
/*--------------------------------------------------------------------*/

/* return wall time in seconds */
__attribute__ ((noinline))
double
get_wall_time()
{
    struct timeval time;
    if (gettimeofday(&time,NULL)) {
        exit(-1); // return 0;
    }
    return (double)time.tv_sec + (double)time.tv_usec * .000001;
}
/*--------------------------------------------------------------------*/

int main(int argc, char *argv[])
{
    uint32_t message = 0;         // mensaje
    uint32_t messageSize = 8;     // tamaño del mensaje por defecto
    uint32_t nmessages = 1 << messageSize;
    uint32_t generator = 0b100000111;  // polinomio generador CRC-8
    // uint32_t generator = 0b111;     // polinomio generador por defecto
    uint32_t generatorSize = nbits(generator);  // tamaño del polinomio generador
    uint32_t crc = 0;
    char m_str[33] = { 0 }, crc_str[33] = { 0 };
    // char t_str[33] = { 0 };
    uint32_t *ptable;
    uint32_t hamming, minhamming = messageSize + generatorSize, code1 = 0, code2 = 0;
    float parcial = 0.0, total;
    int opcion = 0, flagm = 0, flagH = 0;
    double start_t, end_t;

    start_t = get_wall_time();

    while(1)
    {
        opcion = getopt_long(argc, argv, optString, longOpts, NULL /* &longIndex */);
        if (opcion == -1) break;
    
        switch(opcion)
        {
            case 'm':
                sscanf(optarg, "%u", &messageSize);
                nmessages = 1 << messageSize;
                flagm = 1;
                break;

            case 'M':
                errno = 0;    /* to distinguish success/failure after call */
                /* devuelve el valor de una cadena de 0s y 1s
                 * 10111 -> 23 */
                message = (uint32_t) strtol(optarg, NULL, 2);
                if (errno != 0)
                {
                    perror("strtol");
                    exit(EXIT_FAILURE);
                }
                messageSize = nbits(message);
                break;

            case 'G':
                errno = 0;    /* to distinguish success/failure after call */
                /* devuelve el valor de una cadena de 0s y 1s
                 * 10111 -> 23 */
                generator = (uint32_t) strtol(optarg, NULL, 2);
                if (errno != 0)
                {
                    perror("strtol");
                    exit(EXIT_FAILURE);
                }
                generatorSize = nbits(generator);
                break;

            case 'H':
                flagH = 1;
                break;

            case 'v':
                muestra_version();
                exit(0);
    
            case 'h':
                muestra_uso(argv[0], 0);
                break;
    
            default:
                muestra_uso(argv[0], 1);
        }
    }

    if ((messageSize < 2) || (popcount32b(messageSize) == 0))
    {
        printf("ERROR: mensaje inválido\n");
        printf("El mensaje debe tener algún término no nulo y su grado debe ser mayor que 1.\n\n");
        exit(0);
    }
    if ((generatorSize < 2) || (popcount32b(generator) == 0))
    {
        printf("ERROR: polinomio generador inválido\n");
        printf("El polinomio generador debe tener algún término no nulo y su grado debe ser mayor que 1.\n\n");
        exit(0);
    }
    if (messageSize + generatorSize > 32)
    {
        printf("Este programa no soporta el cálculo de mensajes+CRC cuya longitud sea mayor de 32 bits\n");
        exit(0);
    }
    if ((flagm == 1) & (message != 0))
    {
        printf("La opción -M tiene preferencia sobre la opción -m, se ignora el parámetro tamaño del mensaje\n");
        messageSize = nbits(message);
    }

    printf("** crc %s, arrancando ...\n\n", VERSION);
    if (message != 0)
    {
        printf("Mensaje:   M(x)=");
        showpoly(bin_str(message, messageSize, m_str));
        printf(", grado %u\n", messageSize-1);
    }
    else
        printf("Mensajes M de %u bits\n", messageSize);

    printf("Generador: G(x)=");
    showpoly(bin_str(generator, generatorSize, crc_str));
    printf(", grado %u\n\n", generatorSize-1);

    if (message != 0)
    {
        crc = calcCRCverbose(message, generator, messageSize, generatorSize);
        printf("%*s\n", 2 + messageSize + 4, "MSG|CRC");
        //                             \->|CRC 
        printf("%*s|%s\n", 2 + messageSize, bin_str(message, messageSize, m_str),
                                bin_str(crc, generatorSize - 1, crc_str));
        exit(0);
    }

    printf("%*c",  1 + count_ifs(nmessages) + 2 + messageSize - 3, ' '); // imprime 1 + count_ifs(nmessages) + 2 + messageSize - 3 espacios
    //               \-> (       \-> index     \->)_             \->| CRC 
    printf("%s\n", "MSG|CRC");


    ptable = calloc(nmessages, sizeof(uint32_t));
    if (ptable == NULL)
    {
        perror("calloc");
        exit(1);    
    }

    for (uint32_t i = 0; i < nmessages; i++)
    {
        crc = calcCRC(i, generator, messageSize, generatorSize);
        ptable[i] = (i << (generatorSize - 1)) + crc;
        printf("(%0*u) %s|%s\n", count_ifs(nmessages), i, bin_str(i, messageSize, m_str),
                                bin_str(crc, generatorSize - 1, crc_str));
    }

    // printf("Total: %f\n", total);
    printf("\nPolinomio generador G(x)=");
    showpoly(bin_str(generator, generatorSize, crc_str));
    printf(", grado %u\n", generatorSize-1);

    // 1) Capacidad de detectar errores de un bit
    crc = popcount32b(generator);
    printf("- Tiene dos términos? %s\n",
           crc > 1? "SI -> detecta errores de un bit": "NO -> no detecta errores de un bit");

    // 2) Capacidad de detectar numero impar de errores
    crc = calcCRC(generator, 0b11, generatorSize, 2);
    printf("- Factor x+1? %s\n",
            crc == 0? "SI -> detecta numero impar de errores": "NO -> no detecta número impar de errores");

    // 3) Capacidad de detectar dos errores aislados de un bit
    if (generatorSize == 2)
      printf("- Grado 1: no detecta 2 errores separados por 1 bit\n");
    else
    {
        crc = 1;
        for (uint32_t i = 2; (i < generatorSize) & (crc != 0); i++)
        {
            crc = calcCRC(generator, 1 + (1 << i), generatorSize, i+1);
            printf("- Factor ");
            showpoly(bin_str(1 + (1 << i), i+1, crc_str));
            if (crc == 0) printf("? SI -> no detecta 2 errores separados por %u %s\n", i-1, i-1 == 1? "bit":"bits");
            else          printf("? NO -> detecta 2 errores separados por %u %s\n", i-1, i-1 == 1? "bit":"bits");
        }
    }

    // 4) Capacidad de detectar ráfagas de error
    // longitud de ráfaga: distancia entre bit más significativo y menos significativo
    printf("- Distancia entre 1 de mayor y menor peso: %u -> detecta ráfagas de hasta %u %s\n",
           generatorSize - least_significant_bit_set(generator) - 1,
           generatorSize - least_significant_bit_set(generator) - 1,
           generatorSize - least_significant_bit_set(generator) - 1 == 1? "error": "errores");

    // 5) Distancia de Hamming
    if ((flagH == 1) || (messageSize < 15))
    {
        total = nmessages*(nmessages - 1.0)/2.0;
        printf("Buscando distancia de Hamming del código generado (%.0f códigos)...\n", total);
        for (uint32_t i = 1; i < nmessages; i++)
        {
            for (uint32_t j = 0; j < i; j++)
            {
                hamming = hammingDistance(ptable[i], ptable[j]);
                if (hamming < minhamming)
                {
                    minhamming = hamming;
                    code1 = i; code2 = j;
                }
            }
            parcial += i;
            printf("%5.1f%%\r", 100*parcial/total);
            fflush(stdout);
        }
        printf("OK          \n");
        printf("Distancia de Hamming: %u (%u-%u)", minhamming, code1, code2);
        printf(" -> detecta %u %s\n", minhamming - 1, minhamming == 2? "error":"errores");
    }
    else
    {
        printf("- Ejecuta con la opción -H si deseas obtener la distancia de Hamming del código\n");
    }

    end_t = get_wall_time();
    printf("Tiempo de ejecución: %5.1fs\n", end_t - start_t);
    exit(0);
}