// ------------------------------------------------------------------
// File:    rs_cal.c
// Author:  Florent PORTELATINE
// Date:    mai 2005
//
// Todo:    simplifier la génération de GF.
//          equation de la multiplication (cas général A.B)
// ------------------------------------------------------------------

#include <math.h>
#include <stdio.h>
#include <float.h>
#include <limits.h>
#include <stdlib.h>

typedef unsigned char uchar;

int i;
int m, n, length, k, t, d, red;
int init_zero;
int p[10];
int alpha_to[1024], index_of[1024], g[1024];
int poly_prim[13];

void generate_gf(void);
void gen_coef(void);
void gen_mult(void);

const unsigned char tab_poly[][13]={
{0},
{1,1},
{1,1,1},
{1,1,0,1},
{1,1,0,0,1},
{1,0,1,0,0,1},
{1,1,0,0,0,0,1},
{1,0,0,1,0,0,0,1},
{1,0,1,1,1,0,0,0,1},
{1,0,0,0,1,0,0,0,0,1},
{1,0,0,1,0,0,0,0,0,0,1},
{1,0,1,0,0,0,0,0,0,0,0,1},
{1,1,0,0,1,0,1,0,0,0,0,0,1}};

main(int argc, char *argv[])
{
  // traitement simplifié de la ligne de commande
  if (argc != 5)
  {
  printf("\nCalcul des paramètres d'un code RS \n");
  printf("Usage: m length red init_zero \n", argv[0]);
  printf(" - m est l'odre de GF(2^m)\n");
  printf(" - l longueur du code RS (n symboles)\n");
  printf(" - red = (2t parity) = n-k\n");
  printf(" - init_zero = initialisation du polynome générateur\n");
  printf(" exemple : ./rs_cal 8 204 16 0 pour la TnT (ou G709)\n");
  exit(0);
  }

  sscanf(argv[1],"%d", &m);
  sscanf(argv[2],"%d", &length);
  sscanf(argv[3],"%d", &red);
  sscanf(argv[4],"%d", &init_zero);
  
  // calcul préliminaire et affichage des principaux paramètres
  k = length - red;
  t = red/2;
  n = 1;

  for (i=0; i<=m; i++) 
      n *= 2;
  n = n / 2 - 1;  // correspond au nombre d'élément du corps de galois zéro inclus

  for(i=0; i<m+1; i++)
    poly_prim[i]=tab_poly[m][i]; // on récupère le polynome primitif assoscié à GF(2^m)
  
  printf("--> Calcul pour un code RS(%d,%d,%d) avec GF(2^%d) = GF(%d), t = %d\n",
          length, k, red, m, n, t);
  
  printf("--> Polynome primitif   : p(x)= ");
  for(i=m;i>=0;i--)
  {    
    if(poly_prim[i])
    {
      if (i==0)
        printf("1");
      else if (i==1)
        printf("x + ");
      else
        printf("x^%d + ",i);
    }
  }
  printf("\n");

  generate_gf();   // Construction du corps de Galois GF(2^m)
  gen_coef();      // Calcul des coefficients du polynome générateur
  gen_mult();      // Equations de la multiplication
}

void generate_gf()
// génération de GF(2^m) à partir d'un polynome primitif p(x)
// c'est un peu complex mais c'est ce que l'on trouve partout sur le web
// pourrait être simplifié en une seule boucle et test du MSB
// pour un éventuel xor entre le mot de code et le polynome...
{
register int i, mask;        // commentaires pour GF(256)
  mask = 1;
  alpha_to[m] = 0;
  for (i=0; i<m; i++)        // i de 0 à 7
   {
     alpha_to[i] = mask;
     index_of[alpha_to[i]] = i;
     if (poly_prim[i]!=0)
       alpha_to[m] ^= mask;  // i=8 crée alpha_to(8) c'est le polynome primitif
     mask <<= 1;
   }
  index_of[alpha_to[m]] = m;
  mask >>= 1;
  for (i=m+1; i<=n; i++)     // i de 9 à 255
   {
     if (alpha_to[i-1] >= mask)
        alpha_to[i] = alpha_to[m] ^ ((alpha_to[i-1]^mask)<<1);
     else alpha_to[i] = alpha_to[i-1]<<1;
     index_of[alpha_to[i]] = i;
   }
  index_of[0] = -1;

  printf("Table of GF(%d):\n",n);
  printf("----------------------\n");
  printf("power \tvector \t log\n");
  printf("----------------------\n");
  for (i=0; i<=n; i++)
  printf("%4d\t%4x\t%4d\n", i, alpha_to[i], index_of[i]);
}

void gen_coef()
{
// colonne(i) = colonne(i-1).A^(ligne-1) xor colonne(i)
// 0 : index_of(vector) retourne la puissance de alpha : index_of(6) retourne 4
// 1 : pour effectuer la multiplication prendre la puissance de alpha
//     de colonne(i-1) puis appliquer la relation :
//     alpha^i.alpha^j = alpha(i+j)modulo(2^m)
// 2 : pour effectuer le xor : prendre index_of(valeur) afin de calculer
//     sur les valeurs décimales.
// Le résultat obtenu sera sous forme décimale. (vectorielle)
int ligne;         // Indice de lignes
int colonne;       // Indice de colonnes
int gg[red];       // Le tableau d'ordre n-k = redondance

  gg[0] = alpha_to[init_zero];  // forme vectorielle de alpha^init_zero
  gg[1] = 1;                    // g(x) = (X+alpha^init_zero)

  for (ligne = 2; ligne <= red; ligne++) {
    gg[ligne] = 1;              // poids fort forcément à 1
    for (colonne = ligne-1; colonne > 0; colonne--)
      gg[colonne] = alpha_to[(index_of[gg[colonne]]+ligne-1+init_zero)%n] ^ gg[colonne-1];
    gg[0] = alpha_to[(index_of[gg[0]]+ligne-1+init_zero)%n];
  }
  printf("Polynome générateur (b=%d forme vectorielle):\ng(x) = ",init_zero);
  for (i=0; i<=length-k; i++) printf("%5d x^%d", gg[i],i);
  printf("\n");
}

void gen_mult()
{
// Génération des équations de la multiplication dans GF(2^m) dans un cas général.
// Equations avant normalisation :
// Le nombre de ligne du tableau est de 2(m-1) + 1 (partant de zéro)
// Le nombre de colonnes est de m+1
int i, j, x;
int mult_a[2*(m-1)][m];
int mult_b[2*(m-1)][m];

printf("m=%d, tab[%d][%d]\n",m,2*(m-1), m);
printf("Equation de la multiplication avant normalisation):\n");

  for(i=0;i<m;i++)
  {
    for(j=0;j<i+1;j++)
    {
      mult_a[i][j]=i-j;
      mult_b[i][j]=j;
      printf("a(%d).b(%d) ", mult_a[i][j], mult_b[i][j]);
    }
    printf("\n");
  }
  for(i=m;i<=2*(m-1);i++)
  {
    x=0;
    for(j=i-(m-1);j<m;j++)
    {
      mult_a[i][x]=m-x-1;
      mult_b[i][x]=i-m+x+1;
      //printf("i=%d, j=%d, x=%x :: %d.%d\n",i,j,x, mult_a[i][x], mult_b[i][x]);
      printf("a(%d).b(%d) ", mult_a[i][x], mult_b[i][x]);
      x++;
    }
    printf("\n");
  }

// Par la suite il faut ramener la dimension de l'équation à la taille des symboles (m)
// pour cela il faut utiliser les racines des termes 2(m-1) à m-1
}