/* algo5_general.c
créé par Yann Guidon (whygee@f-cpu.org) le 15 septembre 2007
Ce programme génère un histogramme (pour gnuplot)
de taille de fragments générés par un algorithme à base
de divisions par décalages. Le résultat est arrondi
pour favoriser l'alignement des données, mais la taille
maximale du fragment doit être multiple de l'arrondi. */

#include <stdio.h>

#define MAX_APPROX 3

#define ROUND_MASK 3
// arbitraire mais doit être multiple de (ROUND_MASK+1)
#define TAILLE_FRAGMENT 44

int histo[TAILLE_FRAGMENT+1];

int main() {
  int i, taille_bloc, taille_fragment, limite_multiple, log_fragments;

  void SEND(x) {
    if ((x < 1)||(x > TAILLE_FRAGMENT)) {
      printf(" erreur : %d\n ",x);
    }
    else
      histo[x]++;
    if (x<(TAILLE_FRAGMENT/3))
      printf("%d -> send(%d)\n",i, x);
  }

  for  (i=TAILLE_FRAGMENT; i<=TAILLE_FRAGMENT*32; i++) {
    taille_bloc = i;

    /* prépare deux variables, au moyen d'un log2() primaire */
    limite_multiple = TAILLE_FRAGMENT;
    log_fragments = 0;

    while ((limite_multiple <= taille_bloc)
        && (log_fragments < MAX_APPROX)) {
      limite_multiple <<= 1;
      log_fragments++;
    }

    /* boucle principale de fragmentation : */
    taille_fragment = TAILLE_FRAGMENT;
    while (taille_bloc > TAILLE_FRAGMENT) {

      /* recalcule la taille par simple décalage */
      if (limite_multiple > taille_bloc) {
        taille_fragment = taille_bloc >> log_fragments;
        // arrondit au multiple supérieur
        taille_fragment = (taille_fragment + ROUND_MASK) & ~ROUND_MASK;
        log_fragments--;
        limite_multiple >>= 1; // division par 2
      }

      SEND(taille_fragment);
      taille_bloc-=taille_fragment;
    }
    /* envoie le reste */
    SEND(taille_bloc);
  } 

  /* sort l'histogramme sur stdout */
  for (i=0; i<(TAILLE_FRAGMENT+1); i++) {
    printf("%d  %d\n",i, histo[i]);
  }

  return 0;
}