Obligement - L'Amiga au maximum

Samedi 18 novembre 2017 - 05:45  

Translate

En De Nl Nl
Es Pt It Nl


Rubriques

 · Accueil
 · A Propos
 · Articles
 · Galeries
 · Glossaire
 · Hit Parade
 · Liens
 · Liste jeux Amiga
 · Quizz
 · Téléchargements
 · Trucs et astuces


Articles

 · Actualité (récente)
 · Actualité (archive)
 · Comparatifs
 · Dossiers
 · Entrevues
 · Matériel (tests)
 · Matériel (bidouilles)
 · Points de vue
 · En pratique
 · Programmation
 · Reportages
 · Tests de jeux
 · Tests de logiciels
 · Tests de compilations
 · Articles divers

 · Articles in english
 · Articles in other languages


Twitter

Suivez-nous sur Twitter




Liens

 · Sites de téléchargements
 · Associations
 · Pages Personnelles
 · Moteurs de recherche
 · Pages de liens
 · Constructeurs matériels
 · Matériel
 · Autres sites de matériel
 · Réparateurs
 · Revendeurs
 · Presse et médias
 · Programmation
 · Développeurs logiciels
 · Logiciels
 · Développeurs de jeux
 · Jeux
 · Autres sites de jeux
 · Scène démo
 · Divers
 · Informatique générale


Jeux Amiga

0, A, B, C, D, E, F,
G, H, I, J, K, L, M,
N, O, P, Q, R, S, T,
U, V, W, X, Y, Z


Trucs et astuces

0, A, B, C, D, E, F,
G, H, I, J, K, L, M,
N, O, P, Q, R, S, T,
U, V, W, X, Y, Z


Glossaire

0, A, B, C, D, E, F,
G, H, I, J, K, L, M,
N, O, P, Q, R, S, T,
U, V, W, X, Y, Z


Partenaires

Annuaire Amiga

Amedia Computer

Relec

Hit Parade


Contact

David Brunet

Courriel

 


Programmation : Assembleur - la compression topographique
(Article écrit par Xavier Leclercq et extrait d'Amiga News - mai 1991)


Compression topographique de fichier de données graphiques (RAW)

...avec routines en assembleur 68000 de compression/décompression.

Dans la série "plus comprimé que moi tu meurs" je vous propose d'appliquer un régime amaigrissant à vos fichiers de données graphiques au format RAW (c'est-à-dire, et je parviens à l'exprimer sans violence, de données brutes) ou au format ILBM/IFF (Interleave BitMap File/Interchange File Format). Nous avons déjà revu ensemble la méthode de compression de données IFF et donc je n'aborderai plus le sujet.

La méthode que je vais envisager avec vous cette fois-ci est supérieure en gain à la méthode IFF, presque aussi rapide en compression/décompression, mais est malheureusement peu exploitée par les non spécialistes comme vous et moi car très peu documentée. Il s'agit d'une méthode de compression par topographie à laquelle j'ai ajouté deux améliorations visant à majorer encore le gain.

Topo (sur la) graphie ?

Le but du jeu est de pouvoir réduire le volume des données (la taille du fichier) grâce à une routine de compression. Les données comprimées pourront être décomprimées à leur tour afin d'obtenir le fichier initial.

Considérons le fichier de données suivant : [10|00|00|00|00|40|00|00|13] (constitué de 8 octets consécutifs).

Pour décrire le fichier, nous pouvons dire qu'il contient cinq octets 0, et des octets de valeur 10, 40 et 13. J'ai donné quatre informations pour le décrire mais cela ne m'avance pas beaucoup si je dois le décrire à quelqu'un pour le reconstituer. En effet, mon interlocuteur ne connaît pas la place et l'ordre qu'occupent ces octets dans le fichier. Une manière d'opérer serait de me demander (poliment) où sont placés (c'est-à-dire à quelle place relativement au premier octet du fichier) les octets 0 puis de me donner les autres octets dans l'ordre d'apparition. L'interlocuteur m'a donc entendu déclarer les positions des octets 0 (2, 3, 4, 6 et 7) puis les octets suivants de valeur 10, 40 et 13. Il en déduit que le premier octet du fichier n'est pas zéro car les positions des octets zéros ont été données dans l'ordre et que la première position est 2.

Il prend donc le premier octet qui n'a pas été déclaré comme étant une position, c'est-à-dire l'octet 10 et le place comme premier octet dans le fichier. Le deuxième octet dans le fichier occupant la position deux, il en déduit en regardant dans sa table de positions des octets zéros que ce deuxième octet est bien un octet zéro puisqu'il se retrouve dans la table des positions. Il va procéder de même jusqu'à épuisement des octets de position zéro, et n'aura alors qu'à recopier les octets restant dans l'ordre où ils ont été donnés (il est certain qu'aucun des octets suivant n'est zéro). La table des positions des octets (ici zéro) est le rendu en quelque sorte d'une carte des octets zéro du fichier. On appelle cette partie topographie des octets zéro.

Concrètement, il y a donc eu transmission de cinq positions puis de trois données. Il est possible de réduire la carte des positions en affectant un bit (il y a huit bits dans un octet) pour chaque octet. Un bit à 1 (instruction bset en assembleur) signifiera "il y a un octet zéro à la position du bit dans l'octet" un bit 0 (bclr) signifiant la présence d'un octet qui peut prendre toutes les valeurs sauf zéro. Pour comprendre, voici ce que cela donne pour notre fichier de 8 octets : [10|00|00|00|40|00|00|13] donne [0|1|1|1|0|1|1|0] comme premier octet, représentant la topographie du fichier des données nulles, auquel il faut ajouter les octets consécutifs 10|40|13.

Notre fichier a donc en définitive l'aspect suivant : [76|10|40|13] ($76 est bien l'équivalent binaire 01110110).

Calcul du gain

Ce que l'on va "gagner en place" s'appelle le gain et il est très aisé de le calculer :

Gain = V - (V/8 + (V - Nombres_de_Zéros))

...avec "V" représentant le volume initial du fichier de données. Avec notre exemple pédagogique, cela donne :

Gain = 8 - (8/8 + (8 - 5)) = 8 - (1 + (3)) = 4

...ou encore le gain est la taille du fichier initial - la taille du fichier comprimé. Le gain étant positif, il y a compression ; négatif on parlera de décompression.

Première amélioration

D'abord, une remarque qui, je n'en doute pas un instant, a déjà traversé votre esprit. Si le fichier a neuf octets de données il faut deux octets de représentation topographique (dans ce deuxième octet seul un seul bit, celui situé le plus à gauche, est significatif prenant la valeur 1 ou 0 suivant que le neuvième octet est affecté de 00 ou d'un autre octet). Ceci n'ajoute jamais qu'au plus un octet dans le cas où la taille du fichier n'est pas un multiple de 8 et donc est pratiquement sans conséquence sur le gain.

Mais remarquons que le gain est variable au cours du temps suivant le volume topographique des données à analyser. En effet, prenons un nouveau fichier de données d'un volume de douze octets et calculons-en le gain au fur et à mesure d'une image topographique que nous prendrons comme variante de un à douze octets : [10|00|00|00|40|00|00|13|13|13|13|40] la taille variant donc de deux à douze octets le gain est lui consécutivement égal à :

1-(1+(1-0)) = -1
2-(1+(2-1)) = 0
3-(1+(3-2)) = 1
4-(1+(4-3)) = 2
5-(1+(5-3)) = 2
6-(1+(6-4)) = 3

...et ainsi de suite le gain passe à 4, 4, 3, 3, 3 et termine à 3 pour une taille de douze octets. En conséquence pour une compression topographique sur douze octets, il y a gain de trois octets et donc la taille du fichier des données compressées est de neuf octets.

Mais dans le cas d'une représentation topographique sur huit octets, le gain étant de quatre octets, la taille du fichier résultant sera de quatre octets auxquels il faut rajouter quatre octets supplémentaires pour compléter le fichier de manière à pouvoir reproduire dans sa totalité le fichier de douze octets initial.

L'optimisation est donc de prendre la taille topographique correspondant au gain maximum. Une étendue de la carte topographique sur huit ou sept octets ayant tous les deux un gain de quatre maximum donnera les mêmes résultats optimums : (7-4) + (12-7) = 8 et (8-4) + (12-8) = 8.

La routine de compression de données appellera une sous-routine qui sera chargée non seulement de compter un par un le nombre de zéros mais aussi de retenir le volume topographique optimum (en calculant à chaque incrémentation du nombre de zéro le gain et en retenant la taille correspondant au gain le plus élevé).

Cette première amélioration ne permet pas un très grand gain général mais permet malgré tout un ou 2 ko de réduction en volume sur un graphique d'une cinquantaine de ko.

Deuxième amélioration

Je vais d'abord introduire en préambule une notion de compression relative. Lorsqu'un satellite météorologique relève les températures en plein soleil dans une région telle que le désert Saoudien, il pourrait par exemple retransmettre à sa station relai sur Terre des chiffres comme ceux-ci : 50°, 50°, 50°, 52°, 53°, 54°, 54°.

Mais au lieu de bêtement transmettre les températures en valeurs absolues, il peut très bien transmettre les variations relatives des températures par rapport à une température initiale, par exemple 55°, et donc transmettre : -5, -5, -5, -3, -2, -1, -1, ce qui permet de coder les informations sur un nombre de bits moindre. Il s'agit d'une méthode de compression relative qui est utilisée lors de transmissions de données aux valeurs relativement proches les unes des autres.

Maintenant, observons ce que deviennent les températures si je prends comme valeur intermédiaire de comparaison non pas une valeur fixe initiale fixée plus ou moins arbitrairement mais une valeur de référence correspondant à l'avant-dernière température. On part toujours de la première valeur (50°) en calculant "ce qui manque" à cette première température pour atteindre la valeur de la deuxième température (50°) et ainsi de suite. En codage sur 8 bits formant un octet, il faut rajouter 0 à 50 pour obtenir 50. Les données prennent donc l'aspect suivant : 50, 0, 0, 2, 1, 1, 0.

Vous constatez sans doute l'utilité de la chose... Chaque groupement de "n" octets consécutifs semblables se transforment en "n-1" zéros consécutifs ! C'est même tout simplement génial lorsqu'on applique consécutivement à ces différences de octets de rang "m", à chaque octet de rang "m-1" une compression globale par topographie... La démarche inverse, c'est-à-dire une complémentation au lieu d'une différence, permettra de rendre l'aspect d'origine aux données.

Les résultats concrètement parlant

Je vais prendre l'exemple d'un fichier graphique représentant une mire telle que l'on peut en visualiser sur nos téléviseurs. Cette image de 320x256 pixels est composée de 32 couleurs différentes. Les données brutes sont composées de cinq plans de bits de 10240 octets chacun formant un fichier "Mire.RAW" de 10 240x5+(32x2) = 51 264 octets.

Le fichier RAW est la place en mémoire Chip que prendra l'image pour pouvoir être visualisée. C'est donc en fait la place mémoire occupée par cette image durant sa conception sous par exemple Deluxe Paint. Ce programme, pour sauvegarder la mire sur le disque, utilisera le format IFF qui est donc un format de données compressées. Le fichier Mire.IFF aura une taille de 38 954 octets sur le support. Une première compression topographique donnera un fichier de 33 435 octets.

Remarquons le gain déjà supérieur au format IFF (mais ce n'est pas toujours le cas). Et ce n'est pas tout car après avoir appliqué une différence octet par octet comme expliqué ci-dessus et une deuxième passe de compression topographique, le fichier obtenu ne fait plus que 25 732 octets ! La question que vous êtes en droit de vous poser est celle de savoir si une unique passe de compression non pas du fichier RAW mais directement du fichier IFF, donnera un gain aussi appréciable. La réponse est non. Une compression d'un fichier IFF (Comp_IFF) ne donne que des résultats supérieurs aux deux compressions avec différence du fichier RAW. Le fichier Mire.IFF par deux passes de compression topographique occupe un volume de 27 432 octets soit près de 2 ko supplémentaires aux deux passes optimum.

Voici quelques résultats (fichier Mire et fichiers des deux écrans de présentation du MVK2.0) :

assembleur

Le programme de compression/décompression

Assemblé, il ne fait que 1666 octets. Ce qui n'est pas beaucoup surtout en sachant que j'ai programmé les deux routines Proc_Compress et Proc_decompress sans vraiment avoir une technique algorithmique à la base.

Le programme peut être amélioré : tous les accès aux longs mots ne sont pas nécessaires toutes les initialisations non plus (Clear et CB), les boucles peuvent être optimisées. Il faut obligatoirement deux tampons mémoire. Le fichier d'origine sera chargé dans le premier tampon mémoire, chaque résultat de compression/décompression sera placé dans le deuxième tampon mémoire, puis recopié dans le premier pour une deuxième passe.

Je conseille d'utiliser ces routines en prévoyant une interface entre le programme et l'utilisateur à l'aide d'un langage de haut niveau (C, Pascal, etc.). Le langage de haut niveau se chargeant des messages d'entrées sorties et de la gestion de la mémoire. Le label "Début" correspond au premier tampon mémoire, le label "Dest" au deuxième. Ces deux tampons mémoire ne peuvent pas se chevaucher.

assembleur
assembleur
assembleur
assembleur
assembleur

"DebutD", "Find" et "DestD" permettent pour ne pas être contraint à se tenir à un adressage absolu. Ce sont des arguments qui seront utilisés par les langages de haut niveau.

Le temps de compression/décompression prend au plus quelques secondes ce qui n'est pas le cas de tous les décompresseurs (parfois plusieurs heures). C'est même un point très important lorsqu'il s'agit de transmettre des données pratiquement en temps réel (télécommunications). Un tampon d'entrée et un de sortie suffiront à réguler le débit d'une manière efficace. Bon amusement...


[Retour en haut] / [Retour aux articles]