home *** CD-ROM | disk | FTP | other *** search
/ DP Tool Club 21 / CD_ASCQ_21_040595.iso / dos / prg / c / complzw / lzw.cpp < prev    next >
C/C++ Source or Header  |  1995-01-30  |  13KB  |  355 lines
  1. #include "lzw.h"
  2. #include "fbits.h"    // notre librairie d'entrées-sorties de bits sur disque,
  3.                             // pour les constructeurs ifBits et ofBits et les fonc-
  4.                             // tions writeBits et readBits
  5.  
  6.  
  7. // Constructeur (voir aussi lzwdico.h et lzwdico.cpp)
  8. LZW::LZW( unsigned int nombre_bits_final )
  9.     : NBITS_FINAL( nombre_bits_final ),
  10.       DICO( *new LZWDico( nombre_bits_final ) ),
  11.       PILE( *new Pile( LZWDico::maxval( nombre_bits_final ) ) )
  12. { }
  13.  
  14.  
  15. // Destructeur
  16. LZW::~LZW()
  17. {
  18.     delete & DICO ; delete & PILE ;
  19. }
  20.  
  21.  
  22. LZW::erreur LZW::compresse( const char * source, const char * cible )
  23. //
  24. // On compresse le fichier existant de nom source, vers un nouveau
  25. // fichier devant être nommé cible. On retourne le statut final sous
  26. // la forme d'un type énuméré.
  27. {
  28.     // Ouvrir, si possible, le fichier source comme un flux d'octets,
  29.     // et le fichier cible comme un flux de bits (notre classe ofBits)
  30.     ifstream SOURCE( source, ios::binary ) ;
  31.     ofBits     CIBLE( cible, ios::binary ) ;
  32.     if( ! SOURCE.good() )
  33.         return fsource ;
  34.     if( ! CIBLE.good() )
  35.         return fcible ;
  36.  
  37.     // Laisser de la place pour l'en-tête au début du fichier cible
  38.     ecrireEnTeteDeb( CIBLE ) ;
  39.     LG_ORIG = 0 ;    CRC_ORIG.raz() ;
  40.  
  41.     // Ce qui suit est l'implémentation, avec nos outils et classes, de
  42.     // l'algorythme LZW tel que décrit par Mark Nelson ; voir son livre
  43.  
  44.     DICO.vider() ;
  45.  
  46.     // Lire le premier octet ; si source vide, émettre le code FIN_FICHIER,
  47.     // sinon émettre caractère lu, puis incrémenter longueur et calculer crc
  48.     int car = SOURCE.get() ;
  49.     LZWEntree::code code = car == EOF ? LZWEntree::FIN_FICHIER : ( LZWEntree::code )car ;
  50.     if( car != EOF )
  51.     {
  52.         ++LG_ORIG ;
  53.         CRC_ORIG.valeur( ( unsigned char )car ) ;
  54.     }
  55.  
  56.     // Boucle de traitement des caractères suivants lus dans le source
  57.  
  58.     while( /* SOURCE.good() && CIBLE.good() && */ ( car = SOURCE.get() ) != EOF )
  59.     // les tests en commentaires sont très souhaitables théoriquement, hélas
  60.     // ils coûtent du temps : si source est 1 MO, on passe 1 million de fois !
  61.     {
  62.         // Pour chaque caractère lu, incrémenter longueur, et recalculer crc
  63.         ++LG_ORIG ;    CRC_ORIG.valeur( ( unsigned char )car ) ;
  64.  
  65.         // Recherche dans le dictionnaire
  66.         LZWEntree::code index = DICO.index( code, car ) ;
  67.         // Si l'on a trouvé, le code de cette entrée devient le code courrant
  68.         if( DICO[ index ].leCode() != LZWEntree::RIEN )
  69.             code = DICO[ index ].leCode() ;
  70.         // Si l'on a pas trouvé, on ajoute une entrée au dictionnaire, en
  71.         // émettant le code avec le nombre de bits actuel (car il variera)
  72.         else
  73.         {
  74.             DICO[ index ].ajoute( DICO.codeSuivant(), code, (unsigned char)car ) ;
  75.             CIBLE.writeBits( code, DICO.nbits() ) ;
  76.             code = ( LZWEntree::code ) car ;
  77.  
  78.             // On demande au dictionnaire d'allouer un autre code libre ; celui
  79.             // ci est mis dans la variable ancien_nombre_bits, passée comme une
  80.             // référence. Il y a 2 cas particuliers : si la longueur actuelle du
  81.             // code est saturée, le dico l'augmente, et nous signale cela en re-
  82.             // tournant pluslong (type énuméré) ; nous devons alors émettre un
  83.             // code spécial pour prévenir le décompresseur de faire la même cho-
  84.             // se, au même moment ; d'autre part, si la longueur de code elle-
  85.             // même est arrivée à son maximum, le dico se vide, et nous le si-
  86.             // gnale en retournant troplong ; nous devons alors émettre pour le
  87.             // décompresseur le code spécial de vidage du dictionnaire.
  88.             // Il importe de remarquer qu'en cas de changement de longueur du
  89.             // code, le code spécial signalant ce fait est lui-même émis avec
  90.             // l'ancienne longueur.
  91.             unsigned int ancien_nombre_bits ;
  92.             switch( DICO.incrementer( ancien_nombre_bits ) )
  93.             {
  94.                 case LZWDico::troplong : CIBLE.writeBits( LZWEntree::VIDER_DICO, ancien_nombre_bits ) ;
  95.                                                  break ;
  96.                 case LZWDico::pluslong : CIBLE.writeBits( LZWEntree::ALLONGER_CODE, ancien_nombre_bits ) ;
  97.             }
  98.         }
  99.     }
  100.     // On écrit le dernier octet, puis le code spécial de fin de fichier
  101.     CIBLE.writeBits( code, DICO.nbits() ) ;
  102.     CIBLE.writeBits( LZWEntree::FIN_FICHIER, DICO.nbits() ) ;
  103.     // On revient sur l'en-tête, puisqu'on possède désormais les informations
  104.     // pour le remplir (longueur, crc, etc).
  105.     return ecrireEnTeteFin( CIBLE ) ;
  106. }
  107.  
  108.  
  109. LZW::erreur LZW::decompresse( const char * source, const char * cible )
  110. //
  111. // Cette fois, source est le nom du fichier comprimé,et cible celui du
  112. // nouveau fichier décompressé à créer. On renvoie un statut d'erreur.
  113. {
  114.     ifBits     SOURCE( source, ios::binary ) ;    // flux de lecture de bits
  115.     ofstream    CIBLE( cible, ios::binary ) ;        // flux d'écriture d'octets
  116.     if( ! SOURCE.good() )
  117.         return fsource ;
  118.     if( ! CIBLE.good() )
  119.         return fcible ;
  120.  
  121.     LG_ORIG = 0 ;    CRC_ORIG.raz() ;
  122.  
  123.     // On lit l'en-tête et l'on vérifie son intégrité
  124.     erreur er = lireEnTete( SOURCE ) ;
  125.     if( er != ras )
  126.         return er ;
  127.  
  128.     // Algorythme de décompression LZW (cf Mark Nelson)
  129.  
  130.     while( 1 /* SOURCE.good() && CIBLE.good() */ )
  131.     // tests souhaitables mais coûteux en temps
  132.     {
  133.         DICO.vider() ;    // survient aussi à réception du code de vidage
  134.         LZWEntree::code ancien_code = 0 ;
  135.  
  136.         // Traitement du premier code lu (avec la longueur de code initiale)
  137.         SOURCE.readBits( ancien_code, DICO.nbits() ) ;
  138.         if( ancien_code == LZWEntree::FIN_FICHIER )
  139.             return ras ;
  140.         unsigned char car = ( unsigned char )ancien_code ;
  141.         CIBLE.put( car ) ;    ++LG_ORIG ;     CRC_ORIG.valeur( car ) ;
  142.  
  143.         // Traitement des autres codes
  144.  
  145.         while( 1 /* SOURCE.good() && CIBLE.good() */ )
  146.         // tests souhaitables mais coûteux en temps
  147.         {
  148.             LZWEntree::code nouveau_code = 0 ;
  149.             SOURCE.readBits( nouveau_code, DICO.nbits() ) ;
  150.  
  151.             // Fin du source ; on vérifie sa longueur, son
  152.             // crc, par rapport aux données de l'en-tête
  153.             if( nouveau_code == LZWEntree::FIN_FICHIER )
  154.                 return verifEnTete() ;
  155.  
  156.             // Traitement des codes spéciaux émis par le compresseur :
  157.             // allongement du code, ou vidage du dictionnaire. Il est
  158.             // essentiel de faire exactement la même chose que le com-
  159.             // presseur, et au même moment !
  160.             if( nouveau_code == LZWEntree::VIDER_DICO )
  161.                 break ;
  162.             if( nouveau_code == LZWEntree::ALLONGER_CODE )
  163.             {
  164.                 DICO.allongerCode() ;
  165.                 continue ;
  166.             }
  167.  
  168.             // Cas particulier de l'algo LZW : on reçoit un code
  169.             // qui n'est pas encore dans le dictionnaire ! Il faut
  170.             // empiler le caractère dans la pile (cf Mark Nelson)
  171.             if( nouveau_code >= DICO.codeSuivant() )    // cas spécial : code inconnu
  172.             {
  173.                 PILE.push( car ) ;
  174.                 empilerChaine( ancien_code ) ;
  175.             }
  176.             else
  177.                 empilerChaine( nouveau_code ) ;
  178.  
  179.             // On dépile en émettant les caractères, et l'on met à jour le crc
  180.             car = PILE.top() ;                // simple consultation sans dépilement
  181.             while( ! PILE.isEmpty() )
  182.             {
  183.                 unsigned char c = PILE.pop() ;
  184.                 CIBLE.put( c ) ;    ++LG_ORIG ;     CRC_ORIG.valeur( car ) ;
  185.             }
  186.  
  187.             // On ajoute une entrée au dictionnaire
  188.             DICO[ DICO.codeSuivant() ].ajoute( LZWEntree::RIEN, ancien_code, car ) ;
  189.             DICO.incrementer() ;
  190.             ancien_code = nouveau_code ;
  191.         }
  192.     }
  193. }
  194.  
  195.  
  196. void LZW::empilerChaine( LZWEntree::code code_depart )
  197. //
  198. // On remonte l'arborescence du dictionnaire depuis code_depart,
  199. // en empilant dans notre PILE les caractères rencontrés.
  200. //
  201. {
  202.     LZWEntree::code code = code_depart ;
  203.  
  204.     while( code >= LZWDico::codeDepart() )
  205.     {
  206.         PILE.push( DICO[ code ].leCar() ) ;
  207.         code = DICO[ code ].leParent() ;
  208.     }
  209.     PILE.push( ( unsigned char )code ) ;
  210. }
  211.  
  212.  
  213. #ifdef DEPANNAGE
  214. void LZW::lister() const
  215. //
  216. // Vous voyez bien que vous n'êtes pas seul à éprouver
  217. // des difficultés de mise au point de temps à autre !
  218. {
  219.     DICO.lister() ;
  220. }
  221. #endif
  222.  
  223.  
  224. LZW::erreur LZW::lireEnTete( ifBits & fbits )
  225. //
  226. // On lit et on vérifie l'en-tête, en renvoyant
  227. // nos conclusions sous forme d'un type énuméré.
  228. {
  229.     // Lire l'en-tête comme un tableau d'octets
  230.     fbits.read( en_tete.ucars, sizeof( en_tete.ucars ) ) ;
  231.  
  232.     // Le crc des informations de l'en-tête qui fut stocké par le décom-
  233.     // presseur doit être égal à celui que nous recalculons maintenant.
  234.     if( en_tete.infos.crc_infos != CRCEnTete() )
  235.         return crctete ;
  236.  
  237.     // La longueur de code initiale et maximale étant paramétrables,
  238.     // il faut s'assurer que l'on décompresse avec les mêmes bornes
  239.     // que lors de la compression : une décompression 9 à 13 bits
  240.     // après une compression 9 à 12 bits par exemple, donnerait évi-
  241.     // demment du chinois (ou du français, si vous êtes chinois !).
  242.     if( en_tete.infos.nbits_depart != 9 )
  243.         return version ;
  244.     if( en_tete.infos.nbits_limite != NBITS_FINAL )
  245.         return version ;
  246.  
  247.     return ras ;    // ouf, c'est heureusement le cas le plus fréquent !
  248. }
  249.  
  250.  
  251. LZW::erreur LZW::verifEnTete() const
  252. //
  253. // On compare la longueur et le crc recalculés du fichier
  254. // avec leurs valeurs mémorisées dans l'en-tête , et l'on
  255. // renvoie le verdict sous forme d'un type énuméré.
  256. {
  257.     if( en_tete.infos.lg_fich_originel != LG_ORIG )
  258.         return lgfich ;
  259.     if( en_tete.infos.crc_fich_originel != CRC_ORIG.valeur() )
  260.         return crcfich ;
  261.  
  262.     return ras ;
  263. }
  264.  
  265.  
  266. void LZW::ecrireEnTeteDeb( ofBits & fbits )
  267. //
  268. // Nous écrivons séquentiellement dans le flux cible en argument,
  269. // donc il nous faut dès le début réserver la place nécessaire
  270. // pour l'en-tête. Comme la plupart des informations sont indis-
  271. // ponibles avant d'avoir lu entièrement le source (longueurs,
  272. // crc, etc), nous remplissons provisoirement avec des zéros...
  273. {
  274.     en_tete.infos.crc_infos                = 0 ;    // sera mis à jour par ecrireEnTeteFin
  275.     en_tete.infos.nbits_depart            = 9 ;
  276.     en_tete.infos.nbits_limite            = NBITS_FINAL ;
  277.     en_tete.infos.lg_fich_originel    = 0 ;    // sera mis à jour par ecrireEnTeteFin
  278.     en_tete.infos.crc_fich_originel    = 0 ; // sera mis à jour par ecrireEnTeteFin
  279.     en_tete.infos.lg_fich_comprime    = 0 ; // sera mis à jour par ecrireEnTeteFin
  280.  
  281.     fbits.write( en_tete.ucars, sizeof( en_tete.ucars ) ) ;
  282. }
  283.  
  284.  
  285. LZW::erreur LZW::ecrireEnTeteFin( ofBits & fbits )
  286. //
  287. // En fin de compression, nous disposons des informations à mémoriser dans
  288. // l'en-tête ; donc nous y revenons (en début de fichier) pour les mettre à
  289. // jour. Noter que ces informations d'en-tête font elles-mêmes l'objet d'un
  290. // crc mémorisé, qui sera vérifié en tout premier lieu par le décompresseur.
  291. {
  292.     fbits.flush() ;                                    // sage précaution
  293.     unsigned long lg_compr = fbits.tellp() ;    // longueur comprimée
  294.  
  295.     // Remplir la structure d'en-tête avec les infos désormais disponibles
  296.     en_tete.infos.lg_fich_originel    = LG_ORIG ;
  297.     en_tete.infos.crc_fich_originel    = CRC_ORIG.valeur() ;
  298.     en_tete.infos.lg_fich_comprime    = lg_compr ;
  299.     en_tete.infos.crc_infos                = CRCEnTete() ;    // à laisser en dernier !!
  300.                                                                         // (crc de ce qui précède =
  301.                                                                         //  auto-vérif de l'en-tête)
  302.  
  303.     // Revenir sur l'en-tête en début de fichier, pour le ré-écrire
  304.     fbits.seekp( 0 ) ;
  305.     fbits.write( en_tete.ucars, sizeof( en_tete.ucars ) ) ;
  306.  
  307.     // Renvoie un avertissement si le fichier comprimé est égal ou supérieur
  308.     // à l'original (peut arriver si l'on comprime un fichier déjà comprimé)
  309.     return lg_compr < LG_ORIG ? ras : taille ;
  310. }
  311.  
  312.  
  313. CRC32::crc LZW::CRCEnTete() const
  314. //
  315. // Calcule le crc des informations de l'en-tête, qui sera lui même mémorisé
  316. // dans l'en-tête passé au décompresseur. Voir aussi crc32.h et crc32.cpp.
  317. {
  318.     CRC32 C ;    // classe de calcul de crc, cf crc32.h et crc32.cpp
  319.     C.valeur( en_tete.ucars+sizeof( en_tete.infos.crc_infos ), sizeof( en_tete.ucars ) - sizeof( en_tete.infos.crc_infos ) ) ;
  320.     return C.valeur() ;    // consultation de crc calculé
  321. }
  322.  
  323.  
  324. const char * LZW::message( erreur er ) const
  325. //
  326. // Renvoie une chaîne de message d'erreur explicite,
  327. // selon la valeur du code en argument (type énuméré)
  328. {
  329.     char * pt ;
  330.     switch( er )
  331.     {
  332.         case ras            :    pt = "aucune erreur" ;
  333.                                 break ;
  334.         case taille        :    pt = "taille compressée supérieure ; original probablement compressé" ;
  335.                                 break ;
  336.         case version      :     pt = "la compression fut effectuée avec une autre version du programme" ;
  337.                                 break ;
  338.         case lgfich       :  pt = "le fichier décompressé a une longueur différente de l'originel" ;
  339.                                 break ;
  340.         case crcfich      :     pt = "le crc du fichier décompressé est différent de l'originel" ;
  341.                                 break ;
  342.         case crctete    :  pt = "le crc de l'en-tête est erronné" ;
  343.                                 break ;
  344.         case fsource   :  pt = "impossible d'ouvrir le fichier source" ;
  345.                                 break ;
  346.         case fcible        :  pt = "impossible de créer le fichier cible" ;
  347.                                 break ;
  348.         default            :    pt = "erreur non répertoriée" ;    // ne devrait pas survenir
  349.     }
  350.     return ( const char * )pt ;    // tricher pour la bonne cause (expression STROUSTRUPienne !)
  351.                                             // (j'ai assigné pt dans le switch, donc je ne pouvais le dé-
  352.                                             //  clarer const ; toutefois, je dois tenir la promesse faite
  353.                                             //  quand j'ai déclaré renvoyer un const char *).
  354. }
  355.