/* cycles.c
créé le 5 juin 2007 par whygee@f-cpu.org

Ce programme tente de compter le nombre
de cycles indépendants à l'intérieur de
l'espace d'état du tGFSR32x4. Il utilise
une grande table de 512Mi octets
(4Gi bits) pour vérifier plus rapidement
si un nombre donné appartient à un cycle.
*/

#include <stdio.h>
#include <stdlib.h>
#include <strings.h>

typedef unsigned int  U32;
typedef unsigned char U8;

#define MACRO_tGFSR32x4_SHFT(current, last, ptr) \
  current ^= last;        \
  current ^= ptr;         \
  t = current;            \
  current >>= 1;          \
  t &= 0x01010101;        \
  current &= 0x7F7F7F7F;  \
  t <<= 4;                \
  current ^= t;           \
  t <<= 3;                \
  current ^= t;

U32 cycles=0;

#define SetBit(i) { b[(i)>>3] |= 1 << ((i)&7); }
#define GetBit(i) ( b[(i)>>3] & (1 << ((i)&7)) )

int main() {
  U32 r0, r1, r2, r3, t, init, len;

/* mise en place de 512MiB */
  U8 *b=(U8*)malloc(512*1024*1024);
  if (b==NULL)  {
    printf("malloc() marche pas\n");
    return 0;
  }
  bzero(b, 512*1024*1024); /* dure 2 à 3s */
  printf("C'est parti.\n");

  init=0;
  do {
    if (! GetBit(init)) {
      printf("cycle n°%d, %d : ", cycles++, init);
      fflush(stdout);
      SetBit(init);
      len=0;
      r0= init      & 255;
      r1=(init>>8)  & 255;
      r2=(init>>16) & 255;
      r3=(init>>24) & 255;

dirtyloop:
        MACRO_tGFSR32x4_SHFT(r0, r3, 0)
        MACRO_tGFSR32x4_SHFT(r1, r0, 0)
        MACRO_tGFSR32x4_SHFT(r2, r1, 0)
        MACRO_tGFSR32x4_SHFT(r3, r2, 0)
        len++;
        t= r0 | (r1 << 8) | (r2 << 16) | (r3 << 24);
        if (! GetBit(t)) {
          SetBit(t);
          goto dirtyloop;
        }

      printf("%d\n", len);
    }

    init++;
  } while (init!=0); /* rebouclage de i ?
       ==> balayage des 2^32 états */

  printf("Fini.\n");
  free(b);

  return 0;
}