/* algo3_pow2.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, seulement si la taille est une
puissance de deux */

#include <stdio.h>

#define TAILLE_SHIFT 6
#define TAILLE_FRAGMENT (1 << TAILLE_SHIFT)

#define ISPOW2(x)  (((- x) & x) == x)

int histo[TAILLE_FRAGMENT+1];

int main() {
  int i, taille_bloc, taille_fragment, nombre_fragments;

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

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

    /* arrondit la taille du bloc au multiple de fragment supérieur
       avant de diviser par la taille du fragment */
    nombre_fragments = (taille_bloc+ TAILLE_FRAGMENT -1) >> TAILLE_SHIFT;

    taille_fragment = TAILLE_FRAGMENT;
    while (taille_bloc > TAILLE_FRAGMENT) {
      if (ISPOW2(nombre_fragments)) {
        /* recalcule la taille par division à décalages successifs */
        taille_fragment = taille_bloc;
        while (taille_fragment > TAILLE_FRAGMENT) {
          taille_fragment >>= 1; // divisions par 2
        }
      }

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

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

  return 0;
}