/*************************************************************************************************************************************/
/*                                                                                                                                   */
/*        C O M P R E S S I O N / D E C O M P R E S S I O N   ' RLE '   M O N O D I M E N S I O N N E L L E  :                       */
/*                                                                                                                                   */
/*                                                                                                                                   */
/*        Nota :                                                                                                                     */
/*                                                                                                                                   */
/*                    Ce programme a inspire 'v $xrC/CompressionDeCompressionRunLengthEncoding.11$vv$I'                              */
/*                  Il y a une petite difference au sujet du compte des repetitions :                                                */
/*                                                                                                                                   */
/*                                                                                                                                   */
/*                                      $xtc/CompressionDecompression_RLE_1D.01$c                                                    */
/*                                                                                                                                   */
/*                                                          x         --> x                                                          */
/*                                                          xx        --> xx                                                         */
/*                                                          xxx       --> xxx                                                        */
/*                                                          xxxx      --> xxxx4                                                      */
/*                                                          xxxxx     --> xxxx5                                                      */
/*                                                          xxxxxx    --> xxxx6                                                      */
/*                                                          (...)                                                                    */
/*                                                                                                                                   */
/*                                                                                                                                   */
/*                  alors que :                                                                                                      */
/*                                                                                                                                   */
/*                                      $xrC/CompressionDeCompressionRunLengthEncoding.11$vv$I                                       */
/*                                                                                                                                   */
/*                                                          x         --> x                                                          */
/*                                                          xx        --> xx                                                         */
/*                                                          xxx       --> xxx                                                        */
/*                                                          xxxx      --> xxxx0                                                      */
/*                                                          xxxxx     --> xxxx1                                                      */
/*                                                          xxxxxx    --> xxxx2                                                      */
/*                                                          (...)                                                                    */
/*                                                                                                                                   */
/*                  ce qui est donc plus optimise...                                                                                 */
/*                                                                                                                                   */
/*                                                                                                                                   */
/*        Author of '$xtc/CompressionDecompression_RLE_1D.01$c' :                                                                    */
/*                                                                                                                                   */
/*                    Jean-Francois Colonna (LACTAMME, 20141208104225).                                                              */
/*                                                                                                                                   */
/*************************************************************************************************************************************/

#include  "INCLUDES.01.I"

extern    void      *malloc();

#define   CHAR                                                                                                                          \
                    unsigned char

#define   LONGUEUR_MAXIMALE_DES_BUFFERS                                                                                                 \
                    (1000)                                                                                                              \
                                        /* Longueur maximale des buffers pour valider les 'malloc(...)'s.                            */

#define   QUE_FAIRE(x)                                                                                                                  \
                    (0)
#define   NOMBRE_D_OCTETS_POUR_LES_NOMBRES_DE_REPETITIONS                                                                               \
                    (1)
#define   BASE_DE_NUMERATION_DES_NOMBRES_DE_REPETITIONS                                                                                 \
                    (256)
#define   BORNE_INFERIEURE_DE_REPETITIONS                                                                                               \
                    ((4)+QUE_FAIRE(NOMBRE_D_OCTETS_POUR_LES_NOMBRES_DE_REPETITIONS))
#define   BORNE_SUPERIEURE_DE_REPETITIONS                                                                                               \
                    borne_superieure()
                                        /* Definitions des bornes :                                                                  */
                                        /*                                                                                           */
                                        /*        INFERIEUR a partir de laquelle on compacte,                                        */
                                        /*        SUPERIEUR limite superieure du compactage a cause de la capacite d'un octet.       */
                                        /*                                                                                           */
                                        /* On notera que si l'on utilise plus d'un octet pour stocker les nombres de repetitions,    */
                                        /* la borne inferieure doit etre augmentee, mais comment et de combien ?                     */

int       borne_superieure()
          {
          int       cumul=1;
          int       compteur;

          for       (compteur=1 ; compteur<=NOMBRE_D_OCTETS_POUR_LES_NOMBRES_DE_REPETITIONS ; compteur++)
                    {
                    cumul = BASE_DE_NUMERATION_DES_NOMBRES_DE_REPETITIONS*cumul;
                    }

          return(cumul-1);
          }

int       Editer=VRAI;
                                        /* Afin de controler toutes les editions (sauf les messages d'erreur evidemment...).         */

#define   PRINT(sequence)                                                                                                               \
                    {                                                                                                                   \
                    if        (Editer == VRAI)                                                                                          \
                              {                                                                                                         \
                              sequence;                                                                                                 \
                              }                                                                                                         \
                    else                                                                                                                \
                              {                                                                                                         \
                              }                                                                                                         \
                    }

#define   bSTORE(valeur)                                                                                                                \
                    {                                                                                                                   \
                    *(chaineR+indexR) = (valeur);                                                                                       \
                                                                                                                                        \
                    if        (indexR < NombreVersIndex(LONGUEUR_MAXIMALE_DES_BUFFERS))                                                 \
                              {                                                                                                         \
                              indexR++;                                                                                                 \
                              }                                                                                                         \
                    else                                                                                                                \
                              {                                                                                                         \
                              fprintf(stderr,"Erreur de compression/decompression (debordement de capacite) -1-\n");                    \
                              }                                                                                                         \
                    }
#define   STORE(format,valeur,Lchaine)                                                                                                  \
                    {                                                                                                                   \
                    bSTORE(valeur);                                                                                                     \
                                                                                                                                        \
                    Lchaine++;                                                                                                          \
                                                                                                                                        \
                    PRINT(printf(format,(valeur)););                                                                                    \
                    }

#define   STORE_REPETITION(nombre)                                                                                                      \
                    {                                                                                                                   \
                    int       compteur;                                                                                                 \
                    int       quotient=nombre;                                                                                          \
                    int       reste;                                                                                                    \
                                                                                                                                        \
                    for       (compteur=1 ; compteur<=NOMBRE_D_OCTETS_POUR_LES_NOMBRES_DE_REPETITIONS ; compteur++)                     \
                              {                                                                                                         \
                              reste = quotient % BASE_DE_NUMERATION_DES_NOMBRES_DE_REPETITIONS;                                         \
                              quotient = quotient / BASE_DE_NUMERATION_DES_NOMBRES_DE_REPETITIONS;                                      \
                              STORE("=%d ",(CHAR)reste,LchaineC_);                                                                      \
                              }                                                                                                         \
                                                                                                                                        \
                    if        (quotient != 0)                                                                                           \
                              {                                                                                                         \
                              fprintf(stderr,"Erreur de compression (debordement de capacite de repetition) -1-\n");                    \
                              }                                                                                                         \
                    else                                                                                                                \
                              {                                                                                                         \
                              }                                                                                                         \
                    }
#define   GET_REPETITION(NombreDeCaracteres)                                                                                            \
                    {                                                                                                                   \
                    int       compteur;                                                                                                 \
                    int       facteur=1;                                                                                                \
                                                                                                                                        \
                    NombreDeCaracteres=0;                                                                                               \
                                                                                                                                        \
                    for       (compteur=1 ; compteur<=NOMBRE_D_OCTETS_POUR_LES_NOMBRES_DE_REPETITIONS ; compteur++)                     \
                              {                                                                                                         \
                              CHAR      caractere=*(chaineA+indexA);                                                                    \
                              NombreDeCaracteres = NombreDeCaracteres+(caractere*facteur);                                              \
                              facteur = BASE_DE_NUMERATION_DES_NOMBRES_DE_REPETITIONS*facteur;                                          \
                                                                                                                                        \
                              if        (compteur < NOMBRE_D_OCTETS_POUR_LES_NOMBRES_DE_REPETITIONS)                                    \
                                        {                                                                                               \
                                        indexA++;                                                                                       \
                                        }                                                                                               \
                              else                                                                                                      \
                                        {                                                                                               \
                                        }                                                                                               \
                              }                                                                                                         \
                                                                                                                                        \
                    NombreDeCaracteres = NombreDeCaracteres-BORNE_INFERIEURE_DE_REPETITIONS;                                            \
                    }

int       LchaineC_;
CHAR      *compression__(CHAR *chaineR,CHAR *chaineA,int LchaineA)
          {
          CHAR      CaracterePrecedent;
          int       CaracterePrecedentExiste=FAUX;
          int       CompteurDeRepetitions=1;
          int       indexA;
          int       indexR=INDEX0;

          chaineR = malloc(MIN2(LchaineA,LONGUEUR_MAXIMALE_DES_BUFFERS));
          LchaineC_ = 0;

          for       (indexA=INDEX0 ; indexA<=NombreVersIndex(LchaineA) ; indexA++)
                    {
                    CHAR      CaractereCourant=*(chaineA+indexA);

                    if        (CaracterePrecedentExiste == FAUX)
                              {
                              CaracterePrecedent = CaractereCourant;
                              CaracterePrecedentExiste = VRAI;

                              STORE("%c",CaractereCourant,LchaineC_);
                              }
                    else
                              {
                              if        (    (CaractereCourant == CaracterePrecedent)
                                        &&   (CompteurDeRepetitions < BORNE_SUPERIEURE_DE_REPETITIONS)
                                         )
                                        {
                                        CompteurDeRepetitions++;

                                        if        (    (CompteurDeRepetitions > 1)
                                                  &&   (CompteurDeRepetitions <= BORNE_INFERIEURE_DE_REPETITIONS)
                                                   )
                                                  {
                                                  STORE("%c",CaractereCourant,LchaineC_);
                                                  }
                                        else
                                                  {
                                                  }

                                        if        (    (CompteurDeRepetitions >= BORNE_INFERIEURE_DE_REPETITIONS)
                                                  &&   (indexA == NombreVersIndex(LchaineA))
                                                   )
                                                  {
                                                  STORE_REPETITION(CompteurDeRepetitions);
                                                  }
                                        else
                                                  {
                                                  }
                                        }
                              else
                                        {
                                        if        (CompteurDeRepetitions >= BORNE_INFERIEURE_DE_REPETITIONS)
                                                  {
                                                  STORE_REPETITION(CompteurDeRepetitions);
                                                  }
                                        else
                                                  {
                                                  }

                                        STORE("%c",CaractereCourant,LchaineC_);

                                        CaracterePrecedent = CaractereCourant;
                                        CompteurDeRepetitions = 1;
                                        }
                              }
                    }

          bSTORE(0);

          return(chaineR);
          }

#define   CARACTERE_PRECEDENT_INDEFINI                                                                                                  \
                    -1000000000
int       LchaineDC;
CHAR      *decompression(CHAR *chaineR,int LchaineR,CHAR *chaineA,int LchaineA)
          {
          int       iterer=VRAI;
          int       CaracterePrecedent=CARACTERE_PRECEDENT_INDEFINI;
          int       CompteurDeRepetitions=1;
          int       indexA;
          int       indexR=INDEX0;

          chaineR = malloc(MIN2(LchaineR,LONGUEUR_MAXIMALE_DES_BUFFERS));
                                        /* ATTENTION : combien en fait allouer d'octets ?                                            */
          LchaineDC = 0;

          indexA = INDEX0;
          while     (iterer == VRAI)
                    {
                    CHAR      CaractereCourant=*(chaineA+indexA);

                    if        (CompteurDeRepetitions <= BORNE_INFERIEURE_DE_REPETITIONS)
                              {
                              if        (CompteurDeRepetitions == BORNE_INFERIEURE_DE_REPETITIONS)
                                        {
                                        int       compteur;
                                        int       NombreDeCaracteres_ADupliquer;
                                        GET_REPETITION(NombreDeCaracteres_ADupliquer);

                                        for       (compteur=1 ; compteur <= NombreDeCaracteres_ADupliquer ; compteur++)
                                                  {
                                                  STORE("%c",CaracterePrecedent,LchaineDC);
                                                  }

                                        CaracterePrecedent = CARACTERE_PRECEDENT_INDEFINI;
                                        CompteurDeRepetitions = 1;
                                        }
                              else
                                        {
                                        if        (CaractereCourant == CaracterePrecedent)
                                                  {
                                                  CompteurDeRepetitions++;
                                                  }
                                        else
                                                  {
                                                  CaracterePrecedent = CaractereCourant;
                                                  CompteurDeRepetitions = 1;
                                                  }

                                        STORE("%c",CaractereCourant,LchaineDC);
                                        }
                              }
                    else
                              {
                              fprintf(stderr,"Erreur de decompression -1-\n");
                              }

                    indexA++;
                    if        (indexA<=NombreVersIndex(LchaineA))
                              {
                              }
                    else
                              {
                              iterer = FAUX;
                              }
                    }

          bSTORE(0);

          return(chaineR);
          }

#define   COMPRESSION_DECOMPRESSION(chaine__)                                                                                           \
                    {                                                                                                                   \
                    if        (BORNE_SUPERIEURE_DE_REPETITIONS <= MASKO)                                                                \
                              {                                                                                                         \
                              int       Lchaine__=strlen(chaine__);                                                                     \
                              CHAR      *chaineC_;                                                                                      \
                              CHAR      *chaineDC;                                                                                      \
                              int       index;                                                                                          \
                                                                                                                                        \
                              PRINT(printf("%s\n",chaine__););                                                                          \
                              chaineC_ = compression__(chaineC_,chaine__,Lchaine__);                                                    \
                                        /* On notera que 'strlen(...)' ne peut etre utilisee sur 'chaineC_' car, en effet, cette     */ \
                                        /* chaine peut contenir des octets nuls...                                                   */ \
                              PRINT(printf("\n"););                                                                                     \
                              PRINT(printf("longueur=%d -> %d\n",Lchaine__,LchaineC_););                                                \
                              chaineDC = decompression(chaineDC,Lchaine__,chaineC_,LchaineC_);                                          \
                              PRINT(printf("\n\n"););                                                                                   \
                                                                                                                                        \
                              if        (LchaineDC != Lchaine__)                                                                        \
                                        {                                                                                               \
                                        fprintf(stderr,"Erreur de decompression (incoherence des longueurs) -1-\n");                    \
                                        }                                                                                               \
                              else                                                                                                      \
                                        {                                                                                               \
                                        }                                                                                               \
                                                                                                                                        \
                              if        (LchaineDC != strlen(chaineDC))                                                                 \
                                        {                                                                                               \
                                        fprintf(stderr,"Erreur de decompression (incoherence des longueurs) -2-\n");                    \
                                        }                                                                                               \
                              else                                                                                                      \
                                        {                                                                                               \
                                        }                                                                                               \
                                                                                                                                        \
                              for       (index=INDEX0 ; index<=NombreVersIndex(LchaineDC) ; index++)                                    \
                                        {                                                                                               \
                                        if        ((*(chaineDC+index)) != (*(chaine__+index)))                                          \
                                                  {                                                                                     \
                                                  fprintf(stderr,"Erreur de decompression (incoherence des contenus) -3-\n");           \
                                                  }                                                                                     \
                                        else                                                                                            \
                                                  {                                                                                     \
                                                  }                                                                                     \
                                        }                                                                                               \
                              }                                                                                                         \
                    else                                                                                                                \
                              {                                                                                                         \
                              fprintf(stderr,"Erreur de compression/decompression -2-\n");                                              \
                              }                                                                                                         \
                    }

main()
          {
          COMPRESSION_DECOMPRESSION("_0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz");
          COMPRESSION_DECOMPRESSION("abbcccddddeeeeeffffffggggggghhhhhhhh");
          COMPRESSION_DECOMPRESSION("abbcccddddeeeeeffffffggggggghhhhhhhhi");
          COMPRESSION_DECOMPRESSION("abbcccddddeeeeeffffffggggggghhhhhhhhij");
          COMPRESSION_DECOMPRESSION("abbcccddddeeeeeffffffggggggghhhhhhhhijj");
          COMPRESSION_DECOMPRESSION("abbcccddddeeeeeffffffggggggghhhhhhhhijjkkkllllmmmmmnnnnnn");
          COMPRESSION_DECOMPRESSION("abbcccddddeeeeeffffffggggggghhhhhhhhiiiiiiiiijjjjjjjjjjkkkkkkkkkkkk");
          COMPRESSION_DECOMPRESSION("abbcccddddeeeeeffffffggggggghhhhhhhhiiiiiiiiijjjjjjjjjjkkkkkkkkkkkklmm");
          COMPRESSION_DECOMPRESSION("a");
          COMPRESSION_DECOMPRESSION("aa");
          COMPRESSION_DECOMPRESSION("aaa");
          COMPRESSION_DECOMPRESSION("aaaa");
          COMPRESSION_DECOMPRESSION("aaaaa");
          COMPRESSION_DECOMPRESSION("aaaaaa");
          COMPRESSION_DECOMPRESSION("aaaaaaaaaaaaaaaaaaaaaaaaaaaaaa");
          COMPRESSION_DECOMPRESSION("aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa");
          COMPRESSION_DECOMPRESSION("aaaaaaaaaaaaaaaaaaaaaaaaaaaaaa!b");
          COMPRESSION_DECOMPRESSION("aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa!b");
                                        /* Le code hexadecimal de '!' est 0x21 (soit 31) et dans les chaines precedentes il y a      */
                                        /* une trentaine de 'a' et ce afin de voir s'il n'y a pas d'ambiguite...                     */
          }



Copyright © Jean-François Colonna, 2021-2023.
Copyright © CMAP (Centre de Mathématiques APpliquées) UMR CNRS 7641 / École polytechnique, Institut Polytechnique de Paris, 2021-2023.