/*************************************************************************************************************************************/
/*                                                                                                                                   */
/*        C O M P R E S S I O N / D E C O M P R E S S I O N   ' CDCM1 '   D ' U N E   C H A I N E  :                                 */
/*                                                                                                                                   */
/*                                                                                                                                   */
/*        Nota :                                                                                                                     */
/*                                                                                                                                   */
/*                    Ce module est inspire de 'v $xtc/Compression.11$I'                                                             */
/*                  qui a servi a sa mise au point...                                                                                */
/*                                                                                                                                   */
/*                                                                                                                                   */
/*        Author of '$xrC/CompressionDeCompression_Compression.01$vv$I' :                                                            */
/*                                                                                                                                   */
/*                    Jean-Francois Colonna (LACTAMME, 20151227143723).                                                              */
/*                                                                                                                                   */
/*************************************************************************************************************************************/

/*************************************************************************************************************************************/
/*                                                                                                                                   */
/*        D E F I N I T I O N   G E N E R A L E S  :                                                                                 */
/*                                                                                                                                   */
/*************************************************************************************************************************************/
#include  "images.01.vv.I"

#include  < sys/stat.h >
#include  < string.h >
#include  < fcntl.h >
#include  < math.h >
#include  < time.h >
#include  < sys/time.h >

#define   Argument                                                                                                                      \
                    int
#define   Logical                                                                                                                       \
                    int

#define   F_INFINI                                                                                                                      \
                    1.0e+300

Logical   CDC_MettreEnConcurrenceLesDifferentesOptions=FAUX;

double    Complexite_K__Cumulee__Minimale=F_INFINI;
double    Complexite_LD_Cumulee__Associee_A_Complexite_K__Cumulee__Minimale;

Logical   BWT_Utiliser__Associee_A_Complexite_K__Cumulee__Minimale;
Logical   HUF_Utiliser__Associee_A_Complexite_K__Cumulee__Minimale;

#define   D_METTRE_EN_CONCURRENCE(Controle_BWT,Controle_HUF)                                                                            \
                    {                                                                                                                   \
                    BWT_Utiliser = Controle_BWT;                                                                                        \
                    HUF_Utiliser = Controle_HUF;                                                                                        \
                                                                                                                                        \
                    F_MesureDe_K_EtDe_LD_Globale(BufferDuFichier,TailleDuFichier);                                                      \
                                        /* Mesure de K et de LD du fichier argument avec les options courantes...                    */ \
                                                                                                                                        \
                    if        (Complexite_K__Cumulee__ <= Complexite_K__Cumulee__Minimale)                                              \
                              {                                                                                                         \
                              if        (Complexite_K__Cumulee__ == Complexite_K__Cumulee__Minimale)                                    \
                                        {                                                                                               \
                                        Complexite_LD_Cumulee__Associee_A_Complexite_K__Cumulee__Minimale                               \
                                        = MIN2(Complexite_LD_Cumulee__                                                                  \
                                              ,Complexite_LD_Cumulee__Associee_A_Complexite_K__Cumulee__Minimale                        \
                                               );                                                                                       \
                                        /* La fonction 'MIN2(...)' pourrait etre remplacee par 'MAX2(...)'...                        */ \
                                        }                                                                                               \
                              else                                                                                                      \
                                        {                                                                                               \
                                        Complexite_LD_Cumulee__Associee_A_Complexite_K__Cumulee__Minimale = Complexite_LD_Cumulee__;    \
                                        }                                                                                               \
                                                                                                                                        \
                              Complexite_K__Cumulee__Minimale = Complexite_K__Cumulee__;                                                \
                                                                                                                                        \
                              BWT_Utiliser__Associee_A_Complexite_K__Cumulee__Minimale = BWT_Utiliser;                                  \
                              HUF_Utiliser__Associee_A_Complexite_K__Cumulee__Minimale = HUF_Utiliser;                                  \
                              }                                                                                                         \
                    else                                                                                                                \
                              {                                                                                                         \
                              }                                                                                                         \
                    }

                                        /* ATTENTION : la valeur effective des indicateurs n'est pas celle qui apparait ici, mais    */
                                        /* ce qui est force dans 'v $xrC/CompressionDeCompression_Compression.01$vv$c _Editer'.      */
Logical   CDC_EditerLesLongueurs=FAUX;
Logical   CDC_EditerArguments=VRAI;
Logical   CDC_EditerCDCBits=FAUX;
Logical   CDC_EditerChronometrage=FAUX;
Logical   CDC_EditerUniquement_K_et_LD_Cumulees=VRAI;
Logical   CDC_EditerLesComposantesDes_K_Partielles=FAUX;
Logical   CDC_Editer_K_bits=FAUX;
Logical   CDC_EditionsHexaDecimalesDesChaines=VRAI;
                                        /* Indicateurs de controle des editions...                                                   */
                                        /*                                                                                           */
                                        /* ATTENTION : la valeur effective de ces indicateurs n'est pas celle qui apparait ici, mais */
                                        /* ce qui est force dans 'v $xrC/CompressionDeCompression_Compression.01$vv$c _Editer'.      */

Argument  CDC_TailleDesPaquets=0;
                                        /* La valeur nulle, par defaut, specifie en fait la taille du fichier...                     */

#define   MALLOC(NomdreDOctets)                                                                                                         \
                    malloc((size_t)NomdreDOctets)

#define   CHAR                                                                                                                          \
                    unsigned  char                                                                                                      \
                                        /* Afin que tous les tests effectues fonctionnent correctement et que les relations          */ \
                                        /* d'odre soient bien celles que l'on attend, il est a priori necessaire que les             */ \
                                        /* caracteres soient non signes...                                                           */

#define   SIZEOF(argument)                                                                                                              \
                    (sizeof(argument)*NBITOC)                                                                                           \
                                        /* Taille d'un argument en bits.                                                             */

#define   EntierCourt                                                                                                                   \
                    1
#define   EntierMoyen                                                                                                                   \
                    2
#define   EntierLong                                                                                                                    \
                    3
#define   Precision                                                                                                                     \
                    EntierMoyen
                                        /* La Precision est soit 'EntierCourt' soit 'EntierLong'. En fait, a cause de                */
                                        /* 'v $xrC/OperateursComptage$vv$I LongInt', il convient d'utiliser 'EntierLong'...          */
                                        /*                                                                                           */
                                        /* ATTENTION : on notera que 'EntierCourt' et 'EntierLong' doivent etre defines a l'aide     */
                                        /* de valeurs entieres si l'on veut que le '#if' qui suit fonctionne correctement...         */

#define   SEntier                                                                                                                       \
                    short     int
#define   MEntier                                                                                                                       \
                    int
#define   LEntier                                                                                                                       \
                    long      int

#if       (Precision == EntierCourt)
#         define    Entier                                                                                                              \
                              SEntier
#         define    For10                                                                                                               \
                              "d"
#         define    For16                                                                                                               \
                              "x"
#else
#         if        (Precision == EntierMoyen)
#                   define    Entier                                                                                                    \
                                        MEntier
#                   define    For10                                                                                                     \
                                        "d"
#                   define    For16                                                                                                     \
                              "x"
#         else
#                   define    Entier                                                                                                    \
                                        LEntier
#                   define    For10                                                                                                     \
                                        "ld"
#                   define    For16                                                                                                     \
                                        "lx"
#         endif
#endif
                                        /* Types de donnees et Formats utiles...                                                     */

#define   DIVISION_PAR_EXCES(a,b)                                                                                                       \
                    (((a)+(b)-1)/(b))

#include  "CompressionDeCompression_OperateursComptage.01.vv.I"

#define   FORMAT_CARACTERE                                                                                                              \
                    COND((CDC_EditionsHexaDecimalesDesChaines == VRAI),"%02x ","%c")                                                    \
                                        /* Format d'edition des caracteres des chaines et de la matrice...                           */
#define   FORMAT_VRAI_FAUX(condition)                                                                                                   \
                    COND((condition == VRAI),"VRAI","FAUX")                                                                             \
                                        /* Afin de pouvoir editer la valeur d'une variable "Logical"...                              */

#define   ACCES_CHAINE(Chaine,IndexCaractere)                                                                                           \
                    *mINDX(Chaine,IndexCaractere)
                                        /* Acces a une chaine quelconque...                                                          */

#include  "CompressionDeCompression_BurrowsWheeler.01.vv.I"

#define   HUF_FIN_DE_CHAINE                                                                                                             \
                    0                                                                                                                   \
                                        /* Afin de ne pas prevoir de caractere de fin de chaine...                                   */
#include  "CompressionDeCompression_RunLengthEncoding.01.vv.I"

#include  "CompressionDeCompression_HuffmanCoding.01.vv.I"

#define   CDC_INDEXN                                                                                                                    \
                    NombreVersIndex(CDC_LongueurDeToutesLesChaines)
Entier    CDC_LongueurDeToutesLesChaines;

CHAR      *CDC_ChaineA;
CHAR      *CDC_ChaineR;

CHAR      CDC_ChaineBits[]="bits";
CHAR      CDC_ChaineOctets[]="octets";
#define   BITS_OU_OCTETS                                                                                                                \
                    COND((CDC_Editer_K_bits == VRAI),CDC_ChaineBits,CDC_ChaineOctets)
#define   CONVERSION_BITS_OCTET(NombreDeBits)                                                                                           \
                    COND((CDC_Editer_K_bits == VRAI),NombreDeBits,DIVISION_PAR_EXCES(NombreDeBits,NBITOC))
                                        /* Afin d'editer K en bits ou en octets...                                                   */

/*************************************************************************************************************************************/
/*                                                                                                                                   */
/*        V E R I F I C A T I O N   D E S   L O N G U E U R S  :                                                                     */
/*                                                                                                                                   */
/*************************************************************************************************************************************/
#define   D_CDC_VerificationsDesLongueurs(verifier,commentaire,longueur1,longueur2)                                                     \
                    {                                                                                                                   \
                    if        (verifier == VRAI)                                                                                        \
                              {                                                                                                         \
                              if        (longueur1 != longueur2)                                                                        \
                                        {                                                                                               \
                                        fprintf(stderr                                                                                  \
                                               ,"ERREUR(CDC) : les longueurs '%s' different (%d # %d).\n"                               \
                                               ,commentaire                                                                             \
                                               ,longueur1                                                                               \
                                               ,longueur2                                                                               \
                                                );                                                                                      \
                                        }                                                                                               \
                              else                                                                                                      \
                                        {                                                                                               \
                                        }                                                                                               \
                              }                                                                                                         \
                    else                                                                                                                \
                              {                                                                                                         \
                              }                                                                                                         \
                    }

/*************************************************************************************************************************************/
/*                                                                                                                                   */
/*        E D I T I O N   D E S   L O N G U E U R S  :                                                                               */
/*                                                                                                                                   */
/*************************************************************************************************************************************/
#define   D_CDC_EditionLongueur(commentaire,longueur)                                                                                   \
                    {                                                                                                                   \
                    if        (CDC_EditerLesLongueurs == VRAI)                                                                          \
                              {                                                                                                         \
                              printf("LONGUEUR (%s) = %d\n"                                                                             \
                                    ,commentaire                                                                                        \
                                    ,longueur                                                                                           \
                                     );                                                                                                 \
                              }                                                                                                         \
                    else                                                                                                                \
                              {                                                                                                         \
                              }                                                                                                         \
                    }

/*************************************************************************************************************************************/
/*                                                                                                                                   */
/*        C H R O N O M E T R A G E  :                                                                                               */
/*                                                                                                                                   */
/*************************************************************************************************************************************/
#define   D_Bclock(commentaire)                                                                                                         \
                    {                                                                                                                   \
                    clock_t   valeur_initiale_du_chronometre=clock();                                                                   \
                                        /* On notera que pour eviter des problemes de format dans les 'Prin?(...)' qui suivent sur   */ \
                                        /* 'SYSTEME_SGO200A2_IRIX_CC', la variable 'valeur_initiale_du_chronometre' est passe du     */ \
                                        /* type 'LongInt' au type 'Int' le 19980925104908.                                           */ \
                    if        (CDC_EditerChronometrage == VRAI)                                                                         \
                              {                                                                                                         \
                              printf("DEBUT DE CHRONOMETRAGE : %s\n"                                                                    \
                                    ,commentaire                                                                                        \
                                     );                                                                                                 \
                              }                                                                                                         \
                    else                                                                                                                \
                              {                                                                                                         \
                              }                                                                                                         \
                                        /* Mise en route du chronometre.                                                             */
#define   D_Eclock(commentaire)                                                                                                         \
                    if        (CDC_EditerChronometrage == VRAI)                                                                         \
                              {                                                                                                         \
                              int       nombre_de_secondes_pour_Eclock=((clock()-valeur_initiale_du_chronometre)/CLOCKS_PER_SEC);       \
                              int       nombre_de_micro_secondes_pour_Eclock=((clock()-valeur_initiale_du_chronometre)%CLOCKS_PER_SEC); \
                                                                                                                                        \
                              printf("FIN DE CHRONOMETRAGE   : %s - temps ecoule : %d s + %d ms\n"                                      \
                                    ,commentaire                                                                                        \
                                    ,nombre_de_secondes_pour_Eclock                                                                     \
                                    ,nombre_de_micro_secondes_pour_Eclock                                                               \
                                     );                                                                                                 \
                              }                                                                                                         \
                    else                                                                                                                \
                              {                                                                                                         \
                              }                                                                                                         \
                    }                                                                                                                   \
                                        /* Et enfin, edition du temps ecoule depuis la mise en route du chronometre.                 */

/*************************************************************************************************************************************/
/*                                                                                                                                   */
/*        I N I T I A L I S A T I O N   D E   L A   C H A I N E   A   T R A I T E R  :                                               */
/*                                                                                                                                   */
/*************************************************************************************************************************************/
#define   D_CDC________Debut(ChaineR,ChaineA,LongueurChaineA)                                                                           \
                    {                                                                                                                   \
                    Entier    IndexCaractere;                                                                                           \
                                                                                                                                        \
                    CDC_LongueurDeToutesLesChaines = LongueurChaineA;                                                                   \
                                        /* ATTENTION : en toute generalite dans 'ChaineA' les 256 codes possibles peuvent            */ \
                                        /* etre presents et donc 'strlen(...)' ne peut pas fonctionner systematiquement. C'est       */ \
                                        /* pourquoi un parametre de longueur 'LongueurChaineA' doit apparaitre explicitement...      */ \
                                                                                                                                        \
                    ChaineR = MALLOC(CDC_LongueurDeToutesLesChaines*sizeof(CHAR));                                                      \
                                                                                                                                        \
                    for       (IndexCaractere=INDEX0 ; IndexCaractere <= CDC_INDEXN ; IndexCaractere++)                                 \
                              {                                                                                                         \
                              ACCES_CHAINE(ChaineR,IndexCaractere) = ACCES_CHAINE(ChaineA,IndexCaractere);                              \
                              }                                                                                                         \
                    }

#define   D_CDC________Fin__(ChaineA)                                                                                                   \
                    {                                                                                                                   \
                    CALLs(free(ChaineA));                                                                                               \
                    }

/*************************************************************************************************************************************/
/*                                                                                                                                   */
/*        V E R I F I C A T I O N   D U   P R O C E S S U S   C O M P L E T  :                                                       */
/*                                                                                                                                   */
/*************************************************************************************************************************************/
void      F_CDC_Verifications(CHAR *ChaineA1,CHAR *ChaineA2)
          {
          Entier    IndexCaractere;

          for       (IndexCaractere=INDEX0 ; IndexCaractere <= CDC_INDEXN ; IndexCaractere++)
                    {
                    if        (ACCES_CHAINE(ChaineA1,IndexCaractere) != ACCES_CHAINE(ChaineA2,IndexCaractere))
                              {
                              fprintf(stderr
                                     ,"ERREUR(CDC) : chaine retablie ('0x%02x') # chaine a traiter ('0x%02x').\n"
                                     ,ACCES_CHAINE(ChaineA1,IndexCaractere)
                                     ,ACCES_CHAINE(ChaineA2,IndexCaractere)
                                      );
                              }
                    else
                              {
                              }
                    }
          }

/*************************************************************************************************************************************/
/*                                                                                                                                   */
/*        F O N C T I O N   D E   C O M P R E S S I O N   E T   I N V E R S E   P A R T I E L L E  :                                 */
/*                                                                                                                                   */
/*************************************************************************************************************************************/
Entier    CDC_NombreDePaquets;
Entier    CDC_NumeroDuPaquetCourant;

#define   D_CDC_CUMUL_Complexite_K__Partielle(cumuler,composante,valeur,ponderation)                                                    \
                    {                                                                                                                   \
                    if        (cumuler == VRAI)                                                                                         \
                              {                                                                                                         \
                              composante = valeur;                                                                                      \
                              Complexite_K__Partielle = Complexite_K__Partielle+(ponderation*composante);                               \
                              }                                                                                                         \
                    else                                                                                                                \
                              {                                                                                                         \
                              }                                                                                                         \
                    }

double    Complexite_K__Partielle;

double    Ponderation_Complexite_K__Partielle_BWT_IndexDeLaChaineAPermuterDansLaMatrice=1;
double    Complexite_K__Partielle_BWT_IndexDeLaChaineAPermuterDansLaMatrice;
double    Ponderation_Complexite_K__Partielle_HUF_IdentiteDuNoeudCourantDeLArbre=1;
double    Complexite_K__Partielle_HUF_IdentiteDuNoeudCourantDeLArbre;
double    Ponderation_Complexite_K__Partielle_HUF_Arbre=1;
                                        /* Une ponderation egale a :                                                                 */
                                        /*                                                                                           */
                                        /*                  (NBITOC+1)/SIZEOF(Entier)                                                */
                                        /*                                                                                           */
                                        /* semblerait raisonnable car, en effet, pour memoriser la definition de l'arbre, soit       */
                                        /* {ArbreCaracteresEnChaqueNoeud,ArbreChainageAGauche,ArbreChainageADroite}, il semble       */
                                        /* que 8+1=9 bits suffisent...                                                               */
double    Complexite_K__Partielle_HUF_Arbre;
double    Ponderation_Complexite_K__Partielle_HUF_CodeBinaire=1;
double    Complexite_K__Partielle_HUF_CodeBinaire;
double    Ponderation_Complexite_K__Partielle_HUF_NombreDeBitsApresCodage=1;
double    Complexite_K__Partielle_HUF_NombreDeBitsApresCodage;

double    Complexite_K__Cumulee__=0;

double    Complexite_LD_Partielle;
double    Complexite_LD_Cumulee__=0;
                                        /* Mesures de 'K' et de 'LD'...                                                              */

char      *BWT_Fichier_RLE_1;
char      *BWT_Fichier_BWT__;
char      *BWT_Fichier_RLE_2;
char      *BWT_Fichier_HUF__;
                                        /* Afin de pouvoir eventuellement conserver les resultats de {RLE_1,BWT,RLE_2,HUF}.          */

#define   GENERE_FICHIER(nom,chaine,longueur,mode)                                                                                      \
                    {                                                                                                                   \
                    if        (nom != 0)                                                                                                \
                                        /* Cas ou le nom est present dans 'argv[]', mais eventuellement vide :                       */ \
                              {                                                                                                         \
                              if        (strlen(nom) > 0)                                                                               \
                                        /* Cas ou le nom est present dans 'argv[]' et non vide :                                     */ \
                                        {                                                                                               \
                                        FILE      *Fdescripteur;                                                                        \
                                                                                                                                        \
                                        Fdescripteur = fopen(nom,mode);                                                                 \
                                        /* Le 'mode' est soit "w" la premere fois afin d'initialiser a vide le fichier, puis         */ \
                                        /* "a" ensuite afin de cumuler le resultat des traitements des differents paquets...         */ \
                                                                                                                                        \
                                        if        (Fdescripteur >= 0)                                                                   \
                                                  {                                                                                     \
                                                  fwrite(chaine,longueur,1,Fdescripteur);                                               \
                                                  fclose(Fdescripteur);                                                                 \
                                        /* On notera le 20160520134742 que si :                                                      */ \
                                        /*                                                                                           */ \
                                        /*                  PaquetsBWT == TailleFichier   (par exemple '$taille_Sud'=65536)          */ \
                                        /*                                                                                           */ \
                                        /* alors, par exemple, la sequence :                                                         */ \
                                        /*                                                                                           */ \
                                        /*                  $xci/display$X      A="BWT_FICHIER_BWT__"                             \  */ \
                                        /*                                      (...)                                             \  */ \
                                        /*                                      SeuilLectureFichier="BWT_LongueurDeToutesLesChaines" */ \
                                        /*                                                                                           */ \
                                        /* permettra de visualiser la chaine 'BWT_ChaineP' courante dans le '$formatI' courant...    */ \
                                                  }                                                                                     \
                                        else                                                                                            \
                                                  {                                                                                     \
                                                  fprintf(stderr,"ERREUR(CDC) : Le fichier '%s' ne peut etre cree.\n",nom);             \
                                                  }                                                                                     \
                                        }                                                                                               \
                              else                                                                                                      \
                                        {                                                                                               \
                                        /* Cas ou le nom est present dans 'argv[]', mais vide...                                     */ \
                                        }                                                                                               \
                              }                                                                                                         \
                    else                                                                                                                \
                              {                                                                                                         \
                                        /* Cas ou le nom est absent dans 'argv[]'...                                                 */ \
                              }                                                                                                         \
                    }

void      F_MesureLocaleDe_K_EtDe_LD(CHAR *ChaineAMesurer,int LongueurDeChaineAMesurer)
          {

/*************************************************************************************************************************************/
/*                                                                                                                                   */
/*        D E B U T   D U   P R O C E S S U S  :                                                                                     */
/*                                                                                                                                   */
/*************************************************************************************************************************************/
          Complexite_K__Partielle=0;
          Complexite_LD_Partielle=0;

          D_CDC________Debut(CDC_ChaineA
                            ,ChaineAMesurer,LongueurDeChaineAMesurer
                             );

/*************************************************************************************************************************************/
/*                                                                                                                                   */
/*        C O M P R E S S I O N   " R U N - L E N G T H   E N C O D I N G "   D I R E C T E   ( 1 )  :                               */
/*                                                                                                                                   */
/*************************************************************************************************************************************/
          D_RLE________Debut(RLE_1_ChaineA
                            ,CDC_ChaineA,LongueurDeChaineAMesurer
                             );
          RLE_1_LongueurChainesNonCompressees = RLE_LongueurChainesNonCompressees;

          D_Bclock("RLE_1_Directe");
          D_CDC_EditionLongueur("RLE_1_Directe",RLE_1_LongueurChainesNonCompressees);

          D_RLE_DirecteDebut(RLE_1_ChaineC);
          D_RLE_Directe(RLE_1_ChaineC,RLE_1_LongueurChaineC
                       ,RLE_1_ChaineA
                        );

          GENERE_FICHIER(BWT_Fichier_RLE_1,RLE_1_ChaineC,RLE_1_LongueurChaineC,"a");

          D_RLE_DirecteFin__();

          RLE_Directe_1_LongueurAvant = RLE_Directe_LongueurAvant;
          RLE_Directe_1_LongueurApres = RLE_Directe_LongueurApres;

          D_CDC_EditionLongueur("RLE_1_Directe",RLE_1_LongueurChaineC);
          D_Eclock("RLE_1_Directe");

/*************************************************************************************************************************************/
/*                                                                                                                                   */
/*        T R A N S F O R M A T I O N   D E   B U R R O W S - W H E E L E R   D I R E C T E  :                                       */
/*                                                                                                                                   */
/*************************************************************************************************************************************/
          D_BWT________Debut(BWT_ChaineA
                            ,RLE_1_ChaineC,RLE_1_LongueurChaineC
                             );

          D_Bclock("BWT_Directe");
          D_CDC_EditionLongueur("BWT_Directe",RLE_1_LongueurChaineC);

          D_BWT_DirecteDebut(BWT_ChaineP);
          D_BWT_Directe(BWT_ChaineP
                       ,BWT_ChaineA
                        );

          GENERE_FICHIER(BWT_Fichier_BWT__,BWT_ChaineP,BWT_LongueurDeToutesLesChaines,"a");

          D_BWT_DirecteFin__();

          D_CDC_EditionLongueur("BWT_Directe",BWT_LongueurDeToutesLesChaines);
          D_Eclock("BWT_Directe");

          D_CDC_CUMUL_Complexite_K__Partielle(BWT_Utiliser
                                             ,Complexite_K__Partielle_BWT_IndexDeLaChaineAPermuterDansLaMatrice
                                             ,BWT_SIZE_IndexDeLaChaineAPermuterDansLaMatrice
                                             ,Ponderation_Complexite_K__Partielle_BWT_IndexDeLaChaineAPermuterDansLaMatrice
                                              );

/*************************************************************************************************************************************/
/*                                                                                                                                   */
/*        C O M P R E S S I O N   " R U N - L E N G T H   E N C O D I N G "   D I R E C T E   ( 2 )  :                               */
/*                                                                                                                                   */
/*************************************************************************************************************************************/
          D_RLE________Debut(RLE_2_ChaineA
                            ,BWT_ChaineP,BWT_LongueurDeToutesLesChaines
                             );
          RLE_2_LongueurChainesNonCompressees = RLE_LongueurChainesNonCompressees;

          D_Bclock("RLE_2_Directe");
          D_CDC_EditionLongueur("RLE_2_Directe",RLE_2_LongueurChainesNonCompressees);

          D_RLE_DirecteDebut(RLE_2_ChaineC);
          D_RLE_Directe(RLE_2_ChaineC,RLE_2_LongueurChaineC
                       ,RLE_2_ChaineA
                        );

          GENERE_FICHIER(BWT_Fichier_RLE_2,RLE_2_ChaineC,RLE_2_LongueurChaineC,"a");

          D_RLE_DirecteFin__();

          RLE_Directe_2_LongueurAvant = RLE_Directe_LongueurAvant;
          RLE_Directe_2_LongueurApres = RLE_Directe_LongueurApres;

          D_CDC_EditionLongueur("RLE_2_Directe",RLE_2_LongueurChaineC);
          D_Eclock("RLE_2_Directe");

/*************************************************************************************************************************************/
/*                                                                                                                                   */
/*        C O D A G E   D E   H U F F M A N   D I R E C T  :                                                                         */
/*                                                                                                                                   */
/*************************************************************************************************************************************/
                    {
                    CHAR      *HUF_ChaineB;
                    CHAR      *HUF_ChaineR;

                    D_HUF________Debut(HUF_ChaineB
                                      ,HUF_ChaineR
                                      ,RLE_2_ChaineC,RLE_2_LongueurChaineC
                                       );

                    if        (HUF_Utiliser == VRAI)
                              {
                              D_Bclock("HUF_Directe");
                              D_CDC_EditionLongueur("HUF_Directe",RLE_2_LongueurChaineC);

                              F_HUF_Initialisations();
                              F_HUF_GenerationFrequences(RLE_2_ChaineC,RLE_2_LongueurChaineC);
                              F_HUF_GenerationDeLArbre();
                              F_HUF_EditionDeLArbre();
                              F_HUF_ParcoursRecursifDeLArbre(HUF_RacineDeLArbre,0,0);
                              F_HUF_CompactageDesCodesDeHuffman();
                              F_HUF_EditionDesCodesDeHuffman();
                              F_HUF_Directe(HUF_ChaineB
                                           ,RLE_2_ChaineC,RLE_2_LongueurChaineC
                                            );

#define   HUF_NOMBRE_D_OCTETS_APRES_CODAGE                                                                                              \
                    DIVISION_PAR_EXCES(HUF_NombreDeBitsApresCodage,NBITOC)

                              GENERE_FICHIER(BWT_Fichier_HUF__,HUF_ChaineB,HUF_NOMBRE_D_OCTETS_APRES_CODAGE,"a");

                              D_CDC_EditionLongueur("HUF_Directe",HUF_NOMBRE_D_OCTETS_APRES_CODAGE);
                              D_Eclock("HUF_Directe");

                              D_CDC_CUMUL_Complexite_K__Partielle(HUF_Utiliser
                                                                 ,Complexite_K__Partielle_HUF_IdentiteDuNoeudCourantDeLArbre
                                                                 ,HUF_SIZE_IdentiteDuNoeudCourantDeLArbre
                                                                 ,Ponderation_Complexite_K__Partielle_HUF_IdentiteDuNoeudCourantDeLArbre
                                                                  );

                              D_CDC_CUMUL_Complexite_K__Partielle(HUF_Utiliser
                                                                 ,Complexite_K__Partielle_HUF_Arbre
                                                                 ,HUF_SIZE_Arbre
                                                                 ,Ponderation_Complexite_K__Partielle_HUF_Arbre
                                                                  );

                              D_CDC_CUMUL_Complexite_K__Partielle(HUF_Utiliser
                                                                 ,Complexite_K__Partielle_HUF_CodeBinaire
                                                                 ,HUF_SIZE_CodeBinaire
                                                                 ,Ponderation_Complexite_K__Partielle_HUF_CodeBinaire
                                                                  );
                              }
                    else
                              {
                              mEGAL(HUF_NombreDeBitsApresCodage,MUL2(RLE_2_LongueurChaineC,NBITOC));
                              }


                    D_CDC_CUMUL_Complexite_K__Partielle(VRAI
                                                       ,Complexite_K__Partielle_HUF_NombreDeBitsApresCodage
                                                       ,HUF_NombreDeBitsApresCodage
                                                       ,Ponderation_Complexite_K__Partielle_HUF_NombreDeBitsApresCodage
                                                        );

                    INITIALISATION_DES_COMPTEURS;
                                        /* Cette (re-)initialisation des compteurs doit etre faite ici car, en effet, certains       */
                                        /* d'entre-eux ont ete incrementes dans la phase directe qui precede, en particulier dans    */
                                        /* 'v $xrC/CompressionDeCompression_BurrowsWheeler.01$vv$I TriRapideDeLEnsembleDesChaines'.  */
                    if        (HUF_Utiliser == VRAI)
                              {

/*************************************************************************************************************************************/
/*                                                                                                                                   */
/*        C O D A G E   D E   H U F F M A N   I N V E R S E  :                                                                       */
/*                                                                                                                                   */
/*************************************************************************************************************************************/
                              D_Bclock("HUF_Inverse");
                              D_CDC_EditionLongueur("HUF_Inverse",DIVISION_PAR_EXCES(HUF_NombreDeBitsApresCodage,NBITOC));

                              CALL(F_HUF_DeCompactageDesCodesDeHuffman());
                              CALL(F_HUF_Inverse(HUF_ChaineR
                                                ,HUF_ChaineB
                                                ,HUF_NombreDeBitsApresCodage
                                                 )
                                   );

                              D_CDC_EditionLongueur("HUF_Inverse",HUF_NombreDOctetsApresDecodage);
                              D_Eclock("HUF_Inverse");

                              F_HUF_Verifications(RLE_2_ChaineC,RLE_2_LongueurChaineC
                                                 ,HUF_ChaineR,HUF_NombreDOctetsApresDecodage
                                                  );

                              if        (CDC_EditerCDCBits == VRAI)
                                        {
                                        printf("\nLes %"For10" octets (=%"For10" bits) ont ete compactes "
                                              ,(Entier)LongueurDeChaineAMesurer
                                              ,((Entier)LongueurDeChaineAMesurer)*NBITOC
                                               );
                                        printf("en %"For10" octets (=%"For10" bits).\n"
                                              ,DIVISION_PAR_EXCES(HUF_NombreDeBitsApresCodage,NBITOC)
                                              ,HUF_NombreDeBitsApresCodage
                                               );
                                        }
                              else
                                        {
                                        }
                              }
                    else
                              {
                              Entier    IndexCaractere;

                              DoIn(IndexCaractere,INDEX0,NombreVersIndex(RLE_2_LongueurChaineC))
                                        {
                                        mEGAL(ACCES_CHAINE(HUF_ChaineR,IndexCaractere),ACCES_CHAINE(RLE_2_ChaineC,IndexCaractere));
                                        /* AETTENTION : ceci est obligatoire car, en effet, le 'D_HUF________Debut(...)' a remis     */
                                        /* 'HUF_ChaineR' a zero...                                                                   */
                                        }
                              EDoI
                              }

/*************************************************************************************************************************************/
/*                                                                                                                                   */
/*        C O M P R E S S I O N   " R U N - L E N G T H   E N C O D I N G "   I N V E R S E   ( 2 )  :                               */
/*                                                                                                                                   */
/*************************************************************************************************************************************/
                    D_Bclock("RLE_2_Inverse");
                    D_CDC_EditionLongueur("RLE_2_Inverse",HUF_NombreDOctetsApresDecodage);

                    if        (HUF_Utiliser == VRAI)
                              {
                              if        (HUF_NombreDOctetsApresDecodage != RLE_2_LongueurChaineC)
                                        {
                                        fprintf(stderr
                                               ,"ERREUR(CDC) : la longueur avant 'RLE_2_Inverse' (%d) est mauvaise (#%d).\n"
                                               ,HUF_NombreDOctetsApresDecodage
                                               ,RLE_2_LongueurChaineC
                                                );
                                        }
                              else
                                        {
                                        }
                              }
                    else
                              {
                              }

                    RLE_LongueurChainesNonCompressees = RLE_2_LongueurChainesNonCompressees;
                    D_RLE_InverseDebut(RLE_2_ChaineR);
                    D_RLE_Inverse(RLE_2_ChaineR
                                 ,HUF_ChaineR,RLE_2_LongueurChaineC
                                  );

                    RLE_LongueurChainesNonCompressees = RLE_2_LongueurChainesNonCompressees;

                    RLE_Inverse_2_LongueurAvant = RLE_Inverse_LongueurAvant;
                    RLE_Inverse_2_LongueurApres = RLE_Inverse_LongueurApres;

                    D_CDC_EditionLongueur("RLE_2_Inverse",RLE_2_LongueurChainesNonCompressees);
                    D_Eclock("RLE_2_Inverse");

                    F_RLE_Verifications(RLE_2_ChaineR,RLE_2_ChaineA);

/*************************************************************************************************************************************/
/*                                                                                                                                   */
/*        T R A N S F O R M A T I O N   D E   B U R R O W S - W H E E L E R   I N V E R S E  :                                       */
/*                                                                                                                                   */
/*************************************************************************************************************************************/
                    D_Bclock("BWT_Inverse");
                    D_CDC_EditionLongueur("BWT_Inverse",BWT_LongueurDeToutesLesChaines);

                    D_BWT_InverseDebut_02(BWT_ChaineR);

                    D_BWT_Inverse_02(BWT_ChaineR
                                    ,RLE_2_ChaineR
                                     );

                    D_CDC_EditionLongueur("BWT_Inverse",BWT_LongueurDeToutesLesChaines);
                    D_Eclock("BWT_Inverse");

                    F_BWT_Verifications(BWT_ChaineR
                                       ,BWT_ChaineA
                                        );

/*************************************************************************************************************************************/
/*                                                                                                                                   */
/*        C O M P R E S S I O N   " R U N - L E N G T H   E N C O D I N G "   I N V E R S E   ( 1 )  :                               */
/*                                                                                                                                   */
/*************************************************************************************************************************************/
                    D_Bclock("RLE_1_Inverse");
                    D_CDC_EditionLongueur("RLE_1_Inverse",RLE_1_LongueurChaineC);

                    RLE_LongueurChainesNonCompressees = RLE_1_LongueurChainesNonCompressees;
                    D_RLE_InverseDebut(RLE_1_ChaineR);
                    D_RLE_Inverse(RLE_1_ChaineR
                                 ,BWT_ChaineR,RLE_1_LongueurChaineC
                                  );

                    RLE_Inverse_1_LongueurAvant = RLE_Inverse_LongueurAvant;
                    RLE_Inverse_1_LongueurApres = RLE_Inverse_LongueurApres;

                    D_CDC_EditionLongueur("RLE_1_Inverse",RLE_LongueurChainesNonCompressees);
                    D_Eclock("RLE_1_Inverse");

                    D_HUF________Fin__(HUF_ChaineB,HUF_ChaineR);
                    }

          F_RLE_Verifications(RLE_1_ChaineR,RLE_1_ChaineA);

/*************************************************************************************************************************************/
/*                                                                                                                                   */
/*        F I N   D U   P R O C E S S U S  :                                                                                         */
/*                                                                                                                                   */
/*************************************************************************************************************************************/
          F_CDC_Verifications(ChaineAMesurer,RLE_1_ChaineR);

          D_CDC_VerificationsDesLongueurs(VRAI        ,"DEBUT --> RLE1"    ,LongueurDeChaineAMesurer     ,RLE_Directe_1_LongueurAvant);
          D_CDC_VerificationsDesLongueurs(BWT_Utiliser,"RLE1  --> BWT "    ,RLE_Directe_1_LongueurApres  ,BWT_Directe_LongueurAvant);
          D_CDC_VerificationsDesLongueurs(BWT_Utiliser,"BWT   --> RLE2"    ,BWT_Directe_LongueurApres    ,RLE_Directe_2_LongueurAvant);
          D_CDC_VerificationsDesLongueurs(HUF_Utiliser,"RLE2  --> HUF "    ,RLE_Directe_2_LongueurApres  ,HUF_Codage_LongueurAvant);
          D_CDC_VerificationsDesLongueurs(HUF_Utiliser,"HUF   --> HUF "    ,HUF_Codage_LongueurApres     ,HUF_Decodage_LongueurAvant);
          D_CDC_VerificationsDesLongueurs(HUF_Utiliser,"HUF   --> RLE2"    ,HUF_Decodage_LongueurApres   ,RLE_Inverse_2_LongueurAvant);
          D_CDC_VerificationsDesLongueurs(BWT_Utiliser,"RLE2  --> BWT "    ,RLE_Inverse_2_LongueurApres  ,BWT_Inverse_LongueurAvant);
          D_CDC_VerificationsDesLongueurs(BWT_Utiliser,"BWT   --> RLE1"    ,BWT_Inverse_LongueurApres    ,RLE_Inverse_1_LongueurAvant);
          D_CDC_VerificationsDesLongueurs(VRAI        ,"RLE1  --> FIN "    ,RLE_Inverse_1_LongueurApres  ,LongueurDeChaineAMesurer);

          D_CDC_VerificationsDesLongueurs(VRAI        ,"RLE1  --> RLE1"    ,RLE_Directe_1_LongueurAvant  ,RLE_Inverse_1_LongueurApres);
          D_CDC_VerificationsDesLongueurs(BWT_Utiliser,"BWT   --> BWT "    ,BWT_Directe_LongueurAvant    ,BWT_Inverse_LongueurApres);
          D_CDC_VerificationsDesLongueurs(HUF_Utiliser,"HUF   --> HUF "    ,HUF_Codage_LongueurAvant     ,HUF_Decodage_LongueurApres);
          D_CDC_VerificationsDesLongueurs(VRAI        ,"RLE2  --> RLE2"    ,RLE_Directe_2_LongueurAvant  ,RLE_Inverse_2_LongueurApres);

          D_RLE_InverseFin__(RLE_2_ChaineR
                            ,RLE_2_ChaineC
                             );
          D_RLE_InverseFin__(RLE_1_ChaineR
                            ,RLE_1_ChaineC
                             );
          D_BWT_InverseFin___02(BWT_ChaineR
                               ,BWT_ChaineP
                                );

          D_RLE________Fin__(RLE_2_ChaineA);
          D_BWT________Fin__(BWT_ChaineA);
          D_RLE________Fin__(RLE_1_ChaineA);
          D_CDC________Fin__(CDC_ChaineA);

          Complexite_K__Cumulee__ = Complexite_K__Cumulee__+Complexite_K__Partielle;

          CUMUL_DES_COMPTEURS(Complexite_LD_Partielle);
          Complexite_LD_Cumulee__ = Complexite_LD_Cumulee__+Complexite_LD_Partielle;

          if        (CDC_EditerUniquement_K_et_LD_Cumulees == VRAI)
                    {
                    }
          else
                    {
                    if        (CDC_NombreDePaquets > 1)
                              {
                              printf("paquet courant : %d/%d\n",CDC_NumeroDuPaquetCourant,CDC_NombreDePaquets);
                              }
                    else
                              {
                              }

                    if        (CDC_EditerLesComposantesDes_K_Partielles == VRAI)
                              {
                              printf("K(Partielle/BWT_IndexDeLaChaineAPermuterDansLaMatrice)..=%12.0f (%s)\n"
                                    ,floor(CONVERSION_BITS_OCTET(Complexite_K__Partielle_BWT_IndexDeLaChaineAPermuterDansLaMatrice))
                                    ,BITS_OU_OCTETS
                                     );
                              printf("K(Partielle/HUF_IdentiteDuNoeudCourantDeLArbre).........=%12.0f (%s)\n"
                                    ,floor(CONVERSION_BITS_OCTET(Complexite_K__Partielle_HUF_IdentiteDuNoeudCourantDeLArbre))
                                    ,BITS_OU_OCTETS
                                     );
                              printf("K(Partielle/HUF_Arbre)..................................=%12.0f (%s)\n"
                                    ,floor(CONVERSION_BITS_OCTET(Complexite_K__Partielle_HUF_Arbre))
                                    ,BITS_OU_OCTETS
                                     );
                              printf("K(Partielle/HUF_CodeBinaire)............................=%12.0f (%s)\n"
                                    ,floor(CONVERSION_BITS_OCTET(Complexite_K__Partielle_HUF_CodeBinaire))
                                    ,BITS_OU_OCTETS
                                     );
                              printf("K(Partielle/HUF_NombreDeBitsApresCodage)................=%12.0f (%s)\n"
                                    ,floor(CONVERSION_BITS_OCTET(Complexite_K__Partielle_HUF_NombreDeBitsApresCodage))
                                    ,BITS_OU_OCTETS
                                     );
                              }
                    else
                              {
                              }

                    printf("K(Partielle)=%12.0f (%s)          K(Cumulee)=%12.0f (%s)"
                          ,floor(CONVERSION_BITS_OCTET(Complexite_K__Partielle))
                          ,BITS_OU_OCTETS
                          ,floor(CONVERSION_BITS_OCTET(Complexite_K__Cumulee__))
                          ,BITS_OU_OCTETS
                           );
                    printf("                    ");
                    printf("LD(Partielle)=%12.0f (instructions)          LD(Cumulee)=%12.0f (instructions)\n"
                          ,Complexite_LD_Partielle,Complexite_LD_Cumulee__
                           );
                    }
          }

/*************************************************************************************************************************************/
/*                                                                                                                                   */
/*        F O N C T I O N   D E   C O M P R E S S I O N   E T   I N V E R S E   G L O B A L E  :                                     */
/*                                                                                                                                   */
/*************************************************************************************************************************************/
void      F_MesureDe_K_EtDe_LD_Globale(CHAR *ChaineAMesurer,int LongueurDeChaineAMesurer)
          {
          CHAR      *SousChaineAMesurer=ChaineAMesurer;
          Entier    NombreDOctetsEncoreATraiter=LongueurDeChaineAMesurer;

          CDC_NombreDePaquets=DIVISION_PAR_EXCES(LongueurDeChaineAMesurer,CDC_TailleDesPaquets);
          CDC_NumeroDuPaquetCourant=1;

          Complexite_K__Cumulee__=0;
          Complexite_LD_Cumulee__=0;

          Complexite_K__Cumulee__ = Complexite_K__Cumulee__+SIZEOF(CDC_TailleDesPaquets);
          Complexite_K__Cumulee__ = Complexite_K__Cumulee__+SIZEOF(BWT_TailleDesPaquets);

          while     (NombreDOctetsEncoreATraiter > 0)
                    {
                    Entier    LongueurDeSousChaineAMesurer=MIN2(CDC_TailleDesPaquets,NombreDOctetsEncoreATraiter);

                    F_MesureLocaleDe_K_EtDe_LD(SousChaineAMesurer,LongueurDeSousChaineAMesurer);

                    SousChaineAMesurer = SousChaineAMesurer+LongueurDeSousChaineAMesurer;
                    NombreDOctetsEncoreATraiter = NombreDOctetsEncoreATraiter-LongueurDeSousChaineAMesurer;

                    CDC_NumeroDuPaquetCourant++;
                    }

          if        (CDC_MettreEnConcurrenceLesDifferentesOptions == FAUX)
                    {

                    printf("K.................................... = %.0f (%s)\n"
                          ,floor(CONVERSION_BITS_OCTET(Complexite_K__Cumulee__))
                          ,BITS_OU_OCTETS
                           );
                    printf("LD................................... = %.0f (instructions)\n"
                          ,Complexite_LD_Cumulee__
                           );
                    }
          else
                    {
                    }
          }



Copyright (c) Jean-François Colonna, 2016.
Copyright (c) CMAP (Centre de Mathématiques APpliquées) UMR CNRS 7641 / Ecole Polytechnique, 2016.