— Basé sur l'article publié dans Quasar CPC numéro 18, Assembleur : Software, par CNGSoft.

Alors, comme le titre de la rubrique le laisse penser, vous trouverez ici des informations sur l'art et la manière de réaliser de belles compressions. Bon, vu l'illustration que m'a collée le petit blond à lunettes il n'a visiblement pas tout compris…

Bref, la compression des données est un vaste sujet il y a beaucoup à en dire tant sur le plan théorique que sur le plan de l'implémentation. Il existe déjà de nombreuses ressources à ce sujet sur l'internet mais vous trouverez ici des articles plus spécialement dédiés à l'implémentation sur CPC.

Il existe deux problèmes intimement liés en informatique : la lenteur et le manque d'espace. C'est simple, si nous devons travailler avec beaucoup de données, on a besoin d'espace. S'il n'y a pas suffisamment d'espace, on travaille par petits paquets ; mais le traitement devient alors plus lent car il est divisé en plusieurs petits traitements.

Heureusement, la lenteur a toujours été moins contraignante que le manque d'espace. Notre cher Z80 exécute tout de même quatre millions de cycles par seconde, mais il travaille avec seulement 65536 adresses de mémoire. En ce qui concerne les derniers membres de la famille i86… bon, nous ne sommes pas là pour parler des performances des différents microprocesseurs. Ça signifie qu'il est préférable de perdre un peu de temps pour optimiser l'espace. Le processus d'optimisation de l'espace est la compression.

Il existe un grand nombre de méthodes de compression. Les trois méthodes les plus importantes sont RLE, Huffman, et Lempel-Ziv.

La méthode la plus simple est la compression RLE. Un signal qui est répété plusieurs fois consécutives peut-être remplacé par deux signaux : le nombre de répétitions et le signal lui-même. Pour permettre la décompression, un troisième signal d'identification doit être ajouté au début de la séquence.

Mais il y a un problème. Pour faire simple et optimiser l'enchainement des données et des signaux, le même répertoire de signaux doit être utilisé. Le problème apparait lorsque le signal représentant la compression existe aussi dans le répertoire original. La solution est peu agréable : chaque fois que le compresseur trouve dans les données le signal qu'il utilise pour la compression, il doit le traduire en un signal qu'il utilise pour la compression, le nombre 1 (pour la répétition), et enfin le signal. Une optimisation est possible quand le signal de compression apparaît deux fois : signal, nombre 2, signal.

Cette méthode est très simple, et l'implémentation est immédiate. En plus, si le signal de compression a bien été choisi, les résultats sont bons.

Comment choisir le signal de compression ? Cherchez le signal le moins répété (de façon non consécutive) dans les données. C'est de cette manière que le problème de la répétition est réduit au minimum.

La méthode RLE fait la compression des données au fur et à mesure qu'elle les lit et le signal de compression est choisi à priori. C'est bien, mais pas optimal. Une méthode examinant les statistiques des données serait meilleure n'est-ce-pas ?

La compression d'Huffman fait comme ça : d'abord on lit les données et on compte le nombre de fois que chaque signal apparaît. Ensuite, le signal le plus abondant est remplacé par un nouveau signal de taille minimale, le deuxième plus abondant par un autre signal de taille un peu plus grande, et ainsi de suite jusqu'au signal le moins abondant, remplacé par le signal de taille maximale.

Cette méthode donne toujours le résultat minimum pour une équivalence signal à signal, mais la construction de la liste des nouveaux signaux est assez compliquée car elle doit être faite d'après les résultats statistiques. En résumé, les signaux avec le double de fréquence deviennent des signaux de longueur deux fois moindre et vice-versa. Un autre problème vient du fait que les ordinateurs ne travaillent pas avec de longues chaînes de bits mais avec de petits paquets toujours de la même longueur (8 bits dans le cas du Z80) ; dès lors, la compression et la décompression deviennent lourdes.

En plus, l'efficacité dépend de la taille du répertoire des signaux : soit n le nombre de signaux du répertoire, le résultat minimum est tout simplement log2(n) fois plus petit que les données originales. Ça signifie qu'avec n=16, les données ne sont plus compressées qu'au 1/4 ; avec n=256, au 1/8ème, etc.

Revenons à l'idée des répétitions consécutives. Elle est bonne, mais avec un texte comme celui-ci, elle n'arriverait pas à compresser quoi que ce soit car il n'y a pas de groupes de trois fois la même lettre. Mais si on examine le texte, il y a beaucoup de mots qui se répètent. Est-il possible de profiter de cette répétition non linéaire ?

La réponse nous est donnée par la compression de Lempel-Ziv. C'est simple, si la répétition d'une chaîne de signaux est trouvée, la répétition est remplacée par une référence à la première chaîne du même type.

L'implémentation peut-être faite de deux façons. La première construit un dictionnaire de chaînes, chaque chaîne étant symbolisée par un signal ; ainsi, la compression et la décompression deviennent des traducteurs via le dictionnaire. Cela semble simple, mais la construction du dictionnaire est difficile car il doit être complet (pas de signaux sans traduction) et optimal (les chaînes les plus longues possibles).

La deuxième méthode prend pour base la compression RLE : le signal de compression. On examine les données et, chaque fois qu'une chaîne apparaît répétée, elle est remplacée par : un signal de compression, l'index, et la longueur de la chaîne. Naturellement, le signal de compression est choisi avec attention. Cette méthode a un autre avantage : la compression RLE est automatisée, et d'une façon très intéressante.

Voici un exemple :

AAAAAAAAAAAA -> A   + SIGNAL + -1 (index relatif) + 11 (longueur)
ABABABABABAB -> AB  + SIGNAL + -2 (index relatif) + 10 (longueur)
ABCABCABCABC -> ABC + SIGNAL + -3 (index relatif) +  9 (longueur)

Le problème de l'apparition du signal de compression peut être résolu avec une valeur nulle pour l'index et la longueur.

Vous trouverez ci-après un petit programme pour votre CPC. Il utilise la compression RLE avec des données en mémoire et un fichier ASCII. La syntaxe est la suivante :

CALL &BE80,adresse,longueur,@resultat%

Cette routine compresse linéairement les données placées à adresse jusqu'à adresse+longueur-1 dans un fichier préalablement crée avec OPENOUT”fichier”. La longueur compressée est restituée dans la variable resultat%, une variable de type entier (la variable doit exister lorsqu'on la passe en paramètre, faites par exemple un resultat%=0 pour la déclarer). Le fichier peut-être fermé avec CLOSEOUT ou peut rester ouvert pour recevoir plus de données compressées à l'occasion d'un deuxième appel à la routine.

CALL &BE80,adresse,longueur,0

Dans ce cas, on compresse le contenu d'un fichier ouvert avec OPENIN”fichier”, à adresse, jusqu'à adresse+longueur-1. Le fichier peut être fermé avec CLOSEIN ou reste ouvert pour continuer le travail à l'occasion d'une deuxième passe.

Le signal de compression utilisé est &C7 car c'est le moins utilisé des codes du Z80 (c'est RST 0 !).

Télécharger le listing au format Maxam 1.5

; Programme d'exemple de compression de données
; Par CNGSoft pour Quasar CPC 18
 
	Org &be80
 
CMPByte	equ &c7
PutByte	equ &bc95
GetByte	equ &bc80
 
	cp 3
	ret nz
 
	ld c,(ix+0)
	ld b,(ix+1)
	ld e,(ix+2)
	ld d,(ix+3)
	ld l,(ix+4)
	ld h,(ix+5)
	ld a,c
	or b
	jr z,g1
 
	push bc
	call p1
	pop hl
 
	ld (hl),c
	inc hl
	ld (hl),b
	ret
 
G1	jmp g2
 
P1	xor a
	ld c,a
	ld b,a
	ld (ix+0),a
P2	ld a,d
	or e
	jr z,p4
	ld a,(hl)
	inc hl
	dec de
	cp (ix+1)
	jr nz,p3
	inc (ix+0)
	ld a,(ix+0)
	xor &ff
	call z,p5
	jr p2
 
P3	call p5
	dec hl
	ld a,(hl)
	ld (ix+1),a
	inc hl
	ld (ix+0),1
	jr p2
 
P4	call p5
P5	ld a,(ix+1)
	cp cmpbyte
	jr z,p6
	ld a,(ix+0)
	and a
	jr z,p6
 
	cp 3
	jr c,p7
 
P6	ld a,(ix+0)
	and a
	jr z,p8
	ld a,cmpbyte
	call putbyte
	inc bc
	ld a,(ix+0)
	call putbyte
	inc bc
	ld a,(ix+1)
	call putbyte
	inc bc
	xor a
	ld (ix+0),a
	jr p8
 
P7	ld a,(ix+1)
	call putbyte
	inc bc
	dec (ix+0)
	jr nz,p7
P8	ret
 
G2	ld a,d
	or e
	jr z,g5
	call getbyte
	cp cmpbyte
	jr z,g3
	ld (hl),a
	inc hl
	dec de
	jr g2
 
G3	call getbyte
	and a
	jr z,g5
	ld b,a
	call getbyte
G4	ld (hl),a
	inc hl
	dec de
	djnz g4
	jr g2
 
G5	ret
 
	End