Memory Full

Forum / Development

RLE-Cruncher

ast * 17 Mar 2020 21:02:37 * Modified at 21:08:56

Bonsoir,

J'avais envie de partager avec vous, un article que j'ai crée cet après-midi sur le Forum Amstrad Plus

J'espère qu'il vous plaira. Bonne lecture à tous [Sorry BSC, French only]

Après une discussion ce matin à propos du packed/unpacker RLE de CNGSOFT, j'ai décidé de coder mon propre cruncher rle.
L'objectif est le suivant, à savoir, produire un cruncher/decruncher RLE, totalement relogeable.

Qu'à cela ne tienne.

Voici, le fruit de mes recherches dont je me fais le plaisir de partager avec vous.

J'ai travaillé, en début d'après-midi sur une première ébauche que je vais vous tenter devous expliquer.


Le Cruncher (v1)

;
; RLE Cruncher (v1)
; ---by AsT/iMPACT
; hl=source | de=destination | ix=lenght
; structure -> data,flux
;
	org #a000
;
	ld hl,#c000
	ld de,#4000
	ld ix,#4000
;
	ld b,0 ; compteur de flux
loop_rle	
	ld a,(hl) ; prends 1er octet	
	ld (de),a ; octet
	inc de 
nxt_byte
	ld i,a
	ld a,ixl ; si long du fichier=0
	or ixh
	ret z ; alors plus rien a compacter
;
	dec ix
	inc hl
	inc b ; b=b+1
	ld a,b
	or a
	jr z,ba0
;
	ld a,i
;
	ld c,(hl) ; octet 2
	cp c ; compare octet 1 & 2
	jr z,nxt_byte
;
pokeflux
;
	ld a,b
	ld (de),a
	inc de
	ld b,0 ; raz compteur de flux
	jr loop_rle
;
; Un octet de trop
;
ba0 	dec b ; pour garder le flux
	dec hl
	jr pokeflux


La base de celui-ci est fort simple. On prends le 1er octet (source), on le poke dans la destination.On prends le second octet (source) et on regarde si cet octet est identique au 1er. Si ce cas est avéré, on mets en route un petit compteur, dans le cas contraire, l'octet 2 devient l'octet 1. il est poké en ram. reste plus qu'à reboucler le tout.

Si je devais expliquer l'algo d'une façon plus simple cela donnerait :

Si le code à compresser était par exemple

« 
00 00 00 00 00 3F FF 8C 8C 8C 8C 09 09
 »


le programme sortira la suite suivante :

« 
00 05 3F 01 FF 01 8C 03 09 02
 »


Si je traduis cela de façon compréhensive :

5x 00, puis 1x #3F, 1x #ff, 4x #8c, 2x #09

En gros, la structure est la suivante, octet à poker suivi du nombre de fois à le poker.

Le Décruncher (v1)

;
; RLE Decruncher (v1)
; ---by AsT/iMPACT
; hl=source | de=destination 
; structure -> data,flux
; quand 00,00 fin du fichier
;
	org #a100
;
	ld hl,#4000
	ld de,#C000
;
decrunch
	ld c,(hl)
	inc hl
	ld b,(hl)
	inc hl

	ld a,c
	or b
	ret z ; si 00,00 alors fin
;
	ld a,c
;
flux
	ld (de),a
	inc de
	djnz flux
	jr decrunch
	
;



Le code du décruncher fait la même chose à l'envers, à savoir lire l'octet puis le nombre de fois que cet octet est répété.
La fin est détectée quand le programme rencontre "00,00"

J'aurais pu m'arrêter là, mais, je me suis dis que pour les répétitions x1[b] il y avait 2 octets occupés pour un seul octet sorti.
La solution passait donc, par un flag, ou plutôt un identifiant de boucle.

La méthode choisie, je cherche dans le code à compresser parmi 256 valeurs possibles (0-255), la valeur qui n'existe pas dans le code à compresser.

[b]Recherche du Flag


;
; Recherche de Flag
; -- By Ast/iMPACT
; HL=Source | BC=Longueur
;
	org #A200
	
	ld e,0 ; flag de départ (0-255)
;
stream
	ld hl,#c000 ; adresse de départ
	ld bc,#4000 ;longueur du fichier à compresser
;
bouc
	ld a,(hl) ; Lis octet 
	cp e      ; on compare l'octet au flag contenu dans le Reg E
	jr z,found ; l'octet est le même que le flag, on passe au flag suivant (e=e-1)
	inc hl
	dec bc
	ld a,b
	or c
	jr nz,bouc ; on boucle tant que l'octet et le flag ne sont pas égaux durant la longueur déterminée par BC
diff	ld a,e ; E=octet n'existant pas dans le fichier à compresser. A=E
        ld (#36),a ; adresse où sera poké ce flag
	ret

found
	dec e ; si l'octet est le même que le flag, on change la valeur du flag 
	jr nz,stream ; et on retourne au début rechercher un nouveau flag
	ret



Quand le flag est trouvé, il est directement poké à l'adresse #36.

Le Cruncher (v2)

;
; RLE Cruncher (v2)
; ---by AsT/iMPACT
; hl=source | de=destination | ix=lenght
; structure -> data,flag,flux
;
flag equ #36
;
crunch
	ld hl,#c000
	ld de,#4000
	ld ix,#4000
;
	ld b,0 ; compteur de flux
loop_rle	
	ld a,(hl) ; prends 1er octet	
	ld (de),a ; octet
	inc de 
nxt_byte
	ld i,a
	ld a,ixl ; si long du fichier=0
	or ixh
	ret z ; alors plus rien a compacter
;
	dec ix
	inc hl
	inc b ; b=b+1
	ld a,b
	or a
	jr z,ba0
;
	ld a,i
;
	ld c,(hl) ; octet 2
	cp c ; compare octet 1 & 2
	jr z,nxt_byte
;
	ld a,b
	dec a
	jr z,pokeone
;
pokeflux
;
	ld a,(flag)
	ld (de),a
	inc de
;
pokebyte
;
	ld a,b
	ld (de),a
	inc de
	jr pokeone
;
; Un octet de trop
;
ba0 	dec b ; pour garder le flux
	dec hl
	jr pokeflux
;
pokeone	ld b,0
	jr loop_rle



Si le code à compresser était par exemple

« 
00 00 00 00 00 3F FF 8C 8C 8C 8C 09 09
 »


le programme sortira la suite suivante : (avec #ae comme flag)

« 
00 AE 05 3F FF 8C AE 04 09 AE 02
 »


Si je traduis cela de façon compréhensive :

Octet #00, flag #AE donc répétition 5x
Octet #3F, pas de flag on passe au suivant
Octet #FF, pas de flag on passe au suivant
Octet #8c, flag #AE donc répétition 4x
Octet #09, flag #AE donc répétition 2x
...

Le Décruncher (v2)

;
; RLE Decruncher (v2)
; ---by AsT/iMPACT
; hl=source | de=destination 
; structure -> data,flag,flux
; quand 00,00 fin du fichier
;
	org #a100
;
flag 	equ #36
;
	ld hl,#4000 ; startadr
	ld de,#C000 ; destination
	ld a,(flag) ; le flag a été déterminé par la routine recherche de flag
	ld ixl,a
;
decrunch
	ld c,(hl) ;octet 1
	inc hl
	ld b,(hl) ; flag ou octet 2
	inc hl

	ld a,c ;Est ce que l'octet 1 est l'octet 2 sont à zéro ?
	or b ;
	ret z ; si 00,00 alors fin
;
	ld a,b ; est ce que l'octet 2 est le flag ?
	cp ixl ; #fd
	jr nz,noflux ; s'il n'y a pas de répétition on poke seulement l'octet (sans répétition)
;
	
	ld b,(hl) ; flux
	inc hl
;
	ld a,c ; on récupère l'octet à répéter
;
flux
	ld (de),a ;on poke en mémoire
	inc de
	djnz flux ;on boucle x fois
;
	jr decrunch
;
; Pas de répétion ? On poke juste l'octet
;
noflux
	ld a,c ; recupère l'octet en cours (1er octet)
	ld(de),a ;on poke
	inc de 
 	dec hl ; on revient 1 octet avant
;
	jr decrunch
;



Le décruncher joue son rôle, comme expliqué plus haut.
La fin est détectée quand le programme rencontre "00,00"

Quoiqu'il en en soit :

- Les méthodes 1 & 2 sont relogeables.
- La vitesse de compression/décompression est rapide.

[color=#ff0000]Il faut toutefois rajouter 2 octets de plus en fin de fichier (à zéro) afin que le marqueur "fin" soit en place.
Par exemple, si le fichier compressé fait #19F0 octets, une fois sauvegardé, il devra faire #19F2 octets, les deux derniers octets devant être à zéro.[/color]

Je reste néanmoins à votre disposition pour toute autre méthode, routine proposée ici, dont je suis friand (je dois bien l'avouer!)


Article correspondant, Packer/UnPacker by CNGSOFT

Hicks * 01 Apr 2020 15:22:56

Nice to share with us your researches on crunching!
My personnal works make me think that RLE is neither faster, nor more compact (decrunch routine) nor more efficient than a well implemented LZ routine. But maybe I forget something? It could be interesting to compare the speed of RLE and LZ decrunching routines...
In all cases, it could be a good & easy to implement way to crunch IPMDraw images!

tometjerry * 05 Sep 2020 09:12:19

RLE is the technic used by most of early screen crunchers (and first data crunchers as Zenith). It's the only crunching technic that is easy to understand when you begin Z80 coding (Reductor powa :-) ). Sharing sources is a good idea !