home *** CD-ROM | disk | FTP | other *** search
/ DP Tool Club 21 / CD_ASCQ_21_040595.iso / dos / prg / c / complzw / lzwdico.cpp < prev    next >
Encoding:
C/C++ Source or Header  |  1995-02-02  |  6.0 KB  |  160 lines
  1. #include "lzwdico.h"
  2. #include <assert.h>
  3. #include <iostream.h>
  4.  
  5. // Code spécial signifiant échec d'une recherche de caractère
  6. const LZWEntree::code LZWEntree::RIEN                 = 256 ;
  7. // (cette sémantique du RIEN est courante : lorsque vous échouez
  8. // à trouver un pointeur, vous renvoyez 0 ; lorsque EXCEL échoue
  9. // à trouver une valeur, il renvoie #N/A ; lorsque vous cherchez
  10. // un index positif vous pouvez renvoyer -1 s'il est absent, etc ;
  11. // Moi j'aime bien appeler les choses par leur nom : RIEN !!)
  12. //
  13. // Je rappelle que les codes 0 à 255 sont réservés pour les carac-
  14. // tères ordinaires trouvés dans le source à comprimer.
  15.  
  16. // Codes spéciaux émis à destination du décompresseur
  17. const LZWEntree::code LZWEntree::FIN_FICHIER    = 257 ;
  18. const LZWEntree::code LZWEntree::ALLONGER_CODE  = 258 ;
  19. const LZWEntree::code LZWEntree::IGNORER_DICO   = 259 ;    // ne sert pas
  20. const LZWEntree::code LZWEntree::VIDER_DICO     = 260 ;
  21.  
  22. // Divers paramètres pour assurer l'évolutivité du code
  23. const LZWEntree::code LZWDico::CODE_DEPART         = 261 ;    // premier code libre
  24. const unsigned int      LZWDico::NOMBRE_BITS_MIN    = 9 ;        // longueur min de code
  25. const unsigned int      LZWDico::NOMBRE_BITS_MAX    = 16 ;   // lg max absolue de code
  26.                                                                             // (tient encore dans un int)
  27.  
  28. LZWEntree::code LZWDico::premier( unsigned int nbits )
  29. //
  30. // Renvoie un nombre premier dépendant de la longueur actuelle du
  31. // code, passée en argument. En effet, l'accès au dico comporte un
  32. // calcul de hachage. Or, pour obtenir des performances correctes,
  33. // la taille d'une hashtable doit être :
  34. // - un nombre premier ;
  35. // - sensiblement supérieure au nombre maximum d'éléments à stocker.
  36. //
  37. // Les premiers ci-dessous sont 23% supérieurs à la puissance de 2
  38. // correspondant au nombre de bits, ce qui est juste suffisant selon
  39. // mes constatations. (par exemple, pour 13 bits (max 8192 éléments),
  40. // la valeur choisie de 10103 conduit à un temps 5 fois meilleur que
  41. // 9851, alors qu'aller au-delà n'apporte plus aucune amélioration).
  42. // (Nelson préconise une marge de 20%, moi j'ai trouvé qu'il vaut en-
  43. // la peine d'aller à 23%, mais pas au-delà ; je suppose que cela peut
  44. // dépendre des environnements : mémoire, processeur, etc).
  45. {
  46.     switch( nbits )
  47.     {
  48.         case 9 :        return 641 ;
  49.         case 10 :   return 1277 ;
  50.         case 11 :   return 2531 ;
  51.         case 12 :   return 5051 ;    // Nelson préconisait 5021
  52.         case 13 :   return 10103  ;
  53.         case 14 :   return 20219 ;
  54.         case 15 :   return 40423;
  55.     }
  56.     assert( 0 ) ;    // fera tilt si nbits < 9 ou > 15
  57.     return 0 ;        // jamais exécuté, mais calme le (stupide) compilateur
  58. }
  59.  
  60.  
  61. // Constructeur du dictionnaire LZW
  62. // nombre_bits_final est la longueur de code au delà de laquelle
  63. // on souhaite vider le dictionnaire (tout le monde n'a pas 16MO
  64. // de mémoire !)
  65. // CODE_LIMITE est le dernier code pouvant être émis avec la lon-
  66. // gueur de code actuelle
  67. // CODE_FINAL est le plus haut code que nous pourrons émettre avec
  68. // la longueur de code nombre_bits_final (donc juste avant vidage)
  69. // Il est crucial de faire un minimum de calculs à chaque octet lu,
  70. // c'est pourquoi l'on stocke de nombreux paramètres (quitte à les
  71. // remettre à jour dès que nécessaire).
  72. //
  73. // maxval est une fonction renvoyant le plus haut code possible pour
  74. // une longueur donnée (par exemple 511 pour 9 bits).
  75. //
  76. LZWDico::LZWDico( unsigned int nombre_bits_final )
  77.          : NOMBRE_BITS_ACTUEL( NOMBRE_BITS_MIN ),
  78.             TAILLE_DICO( premier( nombre_bits_final ) ),
  79.             DICO( new LZWEntree[ premier( nombre_bits_final ) ] ),
  80.             CODE_FINAL( maxval( nombre_bits_final ) ),
  81.             CODE_LIMITE( maxval( NOMBRE_BITS_MIN ) ),
  82.             CODE_LIBRE_SUIVANT( CODE_DEPART )
  83. {
  84.     assert(     nombre_bits_final >= NOMBRE_BITS_MIN
  85.             && nombre_bits_final <= NOMBRE_BITS_MAX
  86.             && DICO != 0 ) ;
  87. }
  88.  
  89.  
  90. LZWDico::~LZWDico()
  91. {
  92.     delete [] DICO ;
  93. }
  94.  
  95.  
  96. void LZWDico::vider()
  97. //
  98. // Rétablit le dico dans son état de départ (en mettant des RIEN dans
  99. // ses entrées, en mettant la longueur de code à celle de départ, etc)
  100. {
  101.     NOMBRE_BITS_ACTUEL = NOMBRE_BITS_MIN ;
  102.     CODE_LIBRE_SUIVANT = CODE_DEPART ;
  103.     CODE_LIMITE = maxval( NOMBRE_BITS_MIN ) ;
  104.     for( LZWEntree::code i = 0 ; i < TAILLE_DICO ; ++i )
  105.         DICO[ i ].ajoute( LZWEntree::RIEN, LZWEntree::RIEN ) ;
  106. }
  107.  
  108.  
  109. LZWEntree::code LZWDico::index ( LZWEntree::code cparent, unsigned char carfils ) const
  110. //
  111. // Cette fonction reçoit en argument :
  112. // - le code (l'index dans le dico) cparent, dont on veut trouver le fils ;
  113. // - le caractère qui étiquette le fils que l'on cherche.
  114. // Elle doit renvoyer l'index du noeud fils dans le dictionnaire. Ce n'est
  115. // pas trivial car il n'y a pas de pointeur dans le sens parent vers fils.
  116. // Le principe est qu'un noeud fils est rangé à un index calculé par hacha-
  117. // ge à partir du code du parent et du caractère qui étiquette le fils.
  118. {
  119.     // Ceci est la fonction de hachage donnant l'index présumé du fils
  120.     LZWEntree::code ix    = ( ( ( LZWEntree::code )carfils ) << ( nbits() - 8 ) ) ^ cparent ;
  121.  
  122.     // Il reste à résoudre les ex-aequos à cet index (collisions)
  123.     // Pour cela on parcourt circulairement le dictionnaire, jusqu'à
  124.     // trouver un noeud vide (on renvoie RIEN), ou un noeud dont les
  125.     // éléments code et car sont conformes à ceux en argument (réso-
  126.     // lution réussie de la collision). On renvoie alors l'index.
  127.     LZWEntree::code dec  = ix ? tailleDico() - ix : 1 ;
  128.     for( ; ; ix = ( ix >= dec ) ? ix - dec : ix + tailleDico() - dec )
  129.     {
  130.         if( DICO[ ix ].leCode() == LZWEntree::RIEN )
  131.             break ;
  132.         if( DICO[ ix ].leParent() == cparent && DICO[ ix ].leCar() == carfils )
  133.             break ;
  134.     }
  135.     return ix ;
  136. }
  137.  
  138.  
  139. #ifdef DEPANNAGE
  140. void LZWDico::lister() const
  141. //
  142. // J'avoue humblement que cela m'a servi durant la mise au point...
  143. {
  144.     cout << endl ;
  145.     cout << "taille dico : " << TAILLE_DICO
  146.           << endl ;
  147.     cout << "nbre bits :"
  148.           << "\tmin "        << NOMBRE_BITS_MIN
  149.           << "\tmax "        << NOMBRE_BITS_MAX
  150.           << "\tactuel "  << NOMBRE_BITS_ACTUEL
  151.           << endl ;
  152.     cout << "codes :"
  153.           << "\tdépart "    << CODE_DEPART
  154.           << "\tlibre "    << CODE_LIBRE_SUIVANT
  155.           << "\tlimite "    << CODE_LIMITE
  156.           << "\tfinal "    << CODE_FINAL
  157.           << endl ;
  158. }
  159. #endif
  160.