home *** CD-ROM | disk | FTP | other *** search
/ DP Tool Club 21 / CD_ASCQ_21_040595.iso / dos / prg / c / complzw / lzwdico.h < prev    next >
C/C++ Source or Header  |  1995-01-30  |  6KB  |  161 lines
  1. #ifndef LZWDICO_H
  2. #define LZWDICO_H
  3.  
  4. //////////////////////////////////////////////////////////////////////////
  5. // Ce fichier implémente le dictionnaire spécifique LZW décrit par Mark
  6. // Nelson dans son livre "La compression de données", chez Dunod qu'il me
  7. // semble indispensable de consulter : je n'ai ni le courage ni le talent
  8. // pour reprendre ici toutes les explications ; sachez que la suite n'est
  9. // que la transposition en C++ de ce que vous trouvez en C classique dans
  10. // Nelson. Par conséquent, les algorythmes ont été recopiés pratiquement
  11. // tels quels, en tirant simplement parti des outils "objet" développés
  12. // pour simplifier et sécuriser le code (donc faciliter la mise au point).
  13. //
  14. // -> Dans Nelson, voyez spécialement les pages 227 à 235, puis 240 à 248.
  15. //
  16. // Avant le dictionnaire (classe LZWico), il nous faut cependant définir
  17. // une classes LZWEntree décrivant la structure de chacune de ses entrées.
  18. // Chaque entrée est un noeud étiqueté par un caractère (donnée privée CAR).
  19. // La donnée CODE est le code de la chaîne se terminant à ce noeud, tandis
  20. // que CODE_PARENT est celui de la chaîne parente (la précédente, sauf CAR).
  21. // Pour remonter les noeuds, il suffit de suivre les codes parents qui sont
  22. // des numéros d'entrées dans le dictionnaire ; en revanche pour descendre
  23. // il faut réaliser un hachage : voir la fonction index dans le .cpp.
  24. //////////////////////////////////////////////////////////////////////////
  25.  
  26.  
  27. ///////////////
  28. class LZWEntree {
  29. ///////////////
  30. public :
  31.  
  32. typedef    unsigned int    code ;                // un alias pour la clarté
  33.  
  34. static    const code        RIEN ;
  35. static    const code        FIN_FICHIER ;
  36. static    const code        ALLONGER_CODE ;
  37. static    const code        VIDER_DICO ;
  38. static    const code        IGNORER_DICO ;        // inutilisé à ce jour (une autre
  39.                                                         // stratégie suite au débordement
  40.                                                         // du dico, serait de l'ignorer en
  41.                                                         // ne comprimant plus, au lieu de
  42.                                                         // le vider ; j'avais prévu ce code
  43.                                                         // à tout hasard)
  44.  
  45.                                 // Constructeur
  46.                                 LZWEntree() : CODE( RIEN ), CODE_PARENT( RIEN )
  47.                                 { }              // CAR est sans importance ici
  48.  
  49.                                 // Mise à jour ultérieure de l'entrée
  50.             void                ajoute    ( code c, code cparent,
  51.                                               unsigned char car = ( unsigned char )0 )
  52.                                 { CODE = c ; CODE_PARENT = cparent ; CAR = car ; }
  53.  
  54.                                 // Consultation des données de l'entrée
  55.             code                leCode    () const { return CODE ; }
  56.             code                leParent    () const { return CODE_PARENT ; }
  57.             unsigned char    leCar        () const { return CAR ; }
  58.  
  59. private :
  60.             code                CODE, CODE_PARENT ;
  61.             unsigned char    CAR ;
  62. } ;
  63.  
  64.  
  65. /////////////
  66. class LZWDico {
  67. /////////////
  68. public :
  69.                                             // Constructeur et destructeur
  70.                                             LZWDico        ( unsigned int nombre_bits_final ) ;
  71.                                           ~LZWDico        () ;
  72.  
  73.             // Consultation de données internes
  74.             unsigned int                nbits            () const { return NOMBRE_BITS_ACTUEL ; }
  75.             LZWEntree::code            tailleDico    () const { return TAILLE_DICO ; }
  76.  
  77.             // Renvoie une référence à la ième entrée (sans test sur i !)
  78.             LZWEntree &                    operator[]    ( LZWEntree::code i ) { return DICO[ i ] ; }
  79.  
  80.             LZWEntree::code            codeSuivant    () const { return CODE_LIBRE_SUIVANT ; }
  81. static    LZWEntree::code            codeDepart    ()         { return CODE_DEPART ; }
  82.  
  83.             enum                            etatCode        { ras, pluslong, troplong } ;
  84.             etatCode                        incrementer    () ;
  85.             etatCode                        incrementer    ( unsigned int & ancien_nombre_bits ) ;
  86.             void                            allongerCode()    { NOMBRE_BITS_ACTUEL++ ; }
  87.  
  88. static   LZWEntree::code            maxval    ( unsigned int nbits )    { return ( LZWEntree::code )( ( ( ( unsigned long ) 1 ) << nbits ) - 1 ) ; }
  89.             LZWEntree::code            index            ( LZWEntree::code cparent, unsigned char carfils ) const ;
  90.  
  91.             void                            vider            () ;
  92.  
  93. #ifdef DEPANNAGE
  94.             void                            lister        () const ;
  95. #endif
  96.  
  97.  
  98. private :
  99.  
  100. static    const unsigned int        NOMBRE_BITS_MIN ;    // voir le .cpp
  101. static    const unsigned int        NOMBRE_BITS_MAX ;
  102.             unsigned int                NOMBRE_BITS_ACTUEL ;
  103. static     const LZWEntree::code    CODE_DEPART ;
  104.             LZWEntree::code            CODE_LIMITE ;
  105.             const LZWEntree::code    CODE_FINAL ;
  106.             LZWEntree::code            CODE_LIBRE_SUIVANT ;
  107.             LZWEntree *                    DICO ;                    // tableau des entrées
  108.             const LZWEntree::code    TAILLE_DICO ;
  109.  
  110. static   LZWEntree::code            premier    ( unsigned int nbits ) ;
  111.  
  112. } ;
  113.  
  114.  
  115. inline LZWDico::etatCode LZWDico::incrementer()
  116. //
  117. // Incrémente inconditionnellement la valeur du pro-
  118. // chain code disponible, sans autre effet de bord.
  119. // (Ne sert que pour la décompression)
  120. {
  121.     CODE_LIBRE_SUIVANT++ ;
  122.     return ras ;
  123. }
  124.  
  125.  
  126. inline LZWDico::etatCode LZWDico::incrementer( unsigned int & ancien_nombre_bits )
  127. //
  128. // Incrémente le prochain code libre, mais avec des effets de bord en cascade :
  129. // - si la longueur de code est épuisée, il faut l'augmenter ;
  130. // - si elle ne peut plus être augmentée, il faut vider le dico.
  131. // Dans tous les cas, on renvoie une valeur de type énuméré ren-
  132. // dant compte de que qu'on a fait ; quand un code spécial devra
  133. // être émis pour renseigner le décompresseur, il devra l'être
  134. // avec l'ancienne longueur (qu'on aura peut-être changée ici mê-
  135. // me), donc on la passe à l'appelant dans un argument référence.
  136. // Cette fonction sert pendant la compression.
  137. {
  138.     ancien_nombre_bits = NOMBRE_BITS_ACTUEL ;
  139.     CODE_LIBRE_SUIVANT++ ;
  140.  
  141.     // Débordement irrémédiable : la longueur de code ne peut être augmentée
  142.     if( CODE_LIBRE_SUIVANT > CODE_FINAL )
  143.     {
  144.         vider() ;            // rétablit la longueur de code initiale
  145.         return troplong ;        // avis de vidage
  146.     }
  147.  
  148.     // Saturation de la longueur de code, qu'il suffit d'augmenter
  149.     if( CODE_LIBRE_SUIVANT > CODE_LIMITE )
  150.     {
  151.         NOMBRE_BITS_ACTUEL++ ;
  152.         CODE_LIMITE = maxval( NOMBRE_BITS_ACTUEL ) ;
  153.         return pluslong ;        // avis d'incrémentation de la longueur
  154.     }
  155.  
  156.     return ras ;                // rien à signaler (pas de débordement)
  157. }
  158.  
  159.  
  160. #endif
  161.