/*
  fichier : primitifs.c
  fonction :
     cherche tous les polynômes générateurs pour GF(2^N)
     avec N < 32 et par test exhaustif (lent) mais assisté
     par quelques éliminations simples.
  compilation :
    gcc -DN=x -Os -march=pentium3 -fomit-frame-pointer -o primitifs primitifs.c
  Vitesse indicative :
    3,95s pour N=16 pour P3@500MHz
    mais le runtime croît un peu plus vite que 2^N
  Occupation mémoire :
    2^(N-4) octets, par exemple : 4K octets pour N=16,
    64K pour N=20, 128M pour 31. 32 nécessite un recodage. 
*/

#include <stdio.h>
#include <string.h>

#ifndef N
#define N 16 /* le degré désiré, de 4 à 31 */
#endif

#define MaskN  (1UL<<N)
#define MaskN1 (MaskN-1UL)
#define SEED 1

char exclusion[1<<(N-4)];
 /* il faut 2^(N-3) octets mais on élimine en plus
  tous les nombres pairs. On pourrait encore éliminer
  les index avec un nombre pair de bits mais c'est
  trop compliqué pour l'instant et la mémoire n'est
  plus trop chère. */

char binaire[N+1];

int affiche_binaire(unsigned int n) {
  int i, j=0;

  for (i=N; i>=0; i--) {
    if (n & 1) {
      j++;
      binaire[i] = '*';
    }
    else
      binaire[i] = ' ';
    n>>=1;
  }

  printf(binaire);
  return j;
}

/* initialisés au début du programme */
unsigned char table_bitrev[256],
              table_parite[256];

int main(void) {
  unsigned int i, j, rev,
      iteration, lfsr,
      nb_primitifs=0, tests=0;

  for (i=0; i<256; i++) {
  /* initialisation de la table de bitrev */
    table_bitrev[i] = ((i & 1) <<7)
                    | ((i & 2) <<5)
                    | ((i & 4) <<3)
                    | ((i & 8) <<1)
                    | ((i & 16) >>1)
                    | ((i & 32) >>3)
                    | ((i & 64) >>5)
                    | ((i & 128) >>7);

  /* initialisation de la table de parité */
    table_parite[i] =  (i & 1)
                    ^ ((i & 2)  >>1)
                    ^ ((i & 4)  >>2)
                    ^ ((i & 8)  >>3)
                    ^ ((i & 16) >>4)
                    ^ ((i & 32) >>5)
                    ^ ((i & 64) >>6)
                    ^ ((i & 128)>>7);
  }

  /* Ne s'intéresser qu'aux "nombres" impairs,
     mais >1 car il n'existe pas de binôme primitif */
  for (i=3; i<MaskN; i+=2) {

    /* élimination des polynômes à nombre pair de termes */
    j=table_parite[ i        & 255]
#if N > 7
    ^(table_parite[(i >> 8 ) & 255])
#if N > 25
    ^(table_parite[(i >> 16) & 255])
#if N > 23
    ^(table_parite[(i >> 24) & 255])
#endif
#endif
#endif
 ;
    if (!j) {

/* recherche du polynôme réfléchi et autres éliminés */
      if (! ((exclusion[i>>4] >> ((i>>1)&7)) & 1)) {
        tests++;

        /* initialise les variables pour les tests */
        iteration=0;
        lfsr=SEED;
        do {
          iteration++;
          /* calcul d'un pas de LFSR : */
          j=((signed int)(lfsr<<(32-N))) >> 31;
          lfsr = (lfsr+lfsr) ^ (i & j);
          lfsr &= MaskN1; /* enlève les MSB qui dépassent */
        } while (lfsr != SEED);

        /* inversion de l'ordre des bits */
        j=i|MaskN;
        j= (table_bitrev[ j        & 255] << 24)
#if N > 7
         | (table_bitrev[(j >> 8)  & 255] << 16)
#if N > 15
         | (table_bitrev[(j >> 16) & 255] << 8)
#if N > 23
         |  table_bitrev[(j >> 24) & 255]
#endif
#endif
#endif
        ;
        rev= ( ((unsigned) j) >> (31-N) ) & MaskN1;

        /* écriture du flag empêchant le test
           de la réflexion du polynôme courant : */
        exclusion[rev>>4] |= 1<< ((rev>>1) & 7);

        if (iteration==MaskN1) {
          nb_primitifs++;
          printf("mask=0x%08X (", i );
          printf("-%d termes) ",affiche_binaire(i|MaskN));
          printf("bitrev: 0x%08X(",rev);
          affiche_binaire(rev|MaskN);
          printf(")\n");
        }
      }
    }
  }

  printf("%d primitifs (sans les réfléchis), %d tests\n",
    nb_primitifs, tests);

  return 0;
}