Quido

Z PMD 85 Infoserver

Verzia zo dňa a času 13:51, 25. apríl 2010

Quido je PC utilita určená pre pakovanie dát a programov pre (obvykle) 8 bitové počítače. Quido, ako taký, pôvodne vznikol ako obrazovková utilita pre ZX Spectrum, ale keďže pri tvorbe novej hry Kvádro pre PMD 85 kvôli nedostatku miesta v pamäti vznikla nutnosť mať "nepotrebné" dáta spakované, prepísal som Quida v jazyku C ako utilitu pre PC. Myšlienka preportovania Quida na PMD 85 bola zavrhnutá okamžite kvôli pomerne komplikovaným algoritmom, ktoré by sa v assembleri i8080 písali veľmi problematicky (i keď by to nebolo nemožné) a zároveň by samotné pakovanie na PMD 85 trvalo odhadom dva až tri-krát dlhšie, ako na ZX Spectre. Quido okrem spakovania daných dát poskytuje možnosť pripojiť k spakovaným dátam aj rozpakovaciu rutinu a vytvoriť aj súbor pásky pre emulátory.

Základné vlastnosti

Quido používa pri pakovaní dva algoritmy. Prvým je Shrink a druhým Implod. Tieto dva algoritmy sa v priebehu pakovania striedajú, resp. sa na práve nasledujúcom bloku dát aplikujú oba tieto algoritmy a do pakovaného prúdu dát sa použije ten, ktorý vyšiel lepšie. To bol aj dôvod, prečo pôvodná Speccy verzia Quida pakovala aj dva-krát dlhšie, ako Turbo Imploder. V prípade PC verzie je čas pakovania pochopiteľne zanedbateľný.

• maximálna veľkosť zdrojového súboru je 49152 bytov
• 4 voliteľné módy pakovania (detailne ďalej) - pokiaľ sa užívateľ nerozhodne inak, Quido vyskúša všetky 4 módy a použije ten, ktorý vyšiel najlepšie
• možnosť uložiť iba samotný spakovaný blok dát
• možnosť uložiť spakované dáta vrátane rozpakovacej rutiny, ktorá môže byť buď vo verzii pre Z80 alebo vo verzii pre Intel 8080; naviac, v prípade PMD 85 môže byť rozpakovacia rutina umiestnená do nevyužitej oblasti VRAM
• uloženie výsledku do súboru pásky PTP (PMD 85) alebo TAP (ZX Spectrum); v prípade TAP môže byť naviac pridaný aj BASICový zavádzač (ako to robí utilita bin2tap)

Algoritmus Implodu je prevzatý, resp. vychádza z algoritmu Turbo Implodera a tak aj Quido môže pri pakovaní zlyhať. Najkritickejším okamihom je úvod pakovania, teda prípad, kedy na konci dát (Módy 1 a 2), resp. na začiatku dát (Módy 3 a 4) nie je pakovateľná sekvencia. Dôvodom je skutočnosť, že v takomto prípade flag byte označujúci nepakovateľné dáta prekryje pôvodné dáta. Táto skutočnosť je o to nepríjemnejšia, že dáta ako celok s najväčšou pravdepodobnosťou pakovateľné sú a problémovým miestom je iba úvod dát. V tomto prípade je riešením iba (pokiaľ je to možné) rozšírenie dát o vhodne dlhú sekvenciu rovnakých bytov buď na začiatku alebo na konci dát. K zlyhaniu môže pochopiteľne dôjsť aj v priebehu pakovania, pokiaľ sa zdrojový a cieľový ukazovateľ stretnú.

Použitie

Quido je konzolová utilita, takže sa dá s výhodou použíť v dávkových súboroch. Požadované chovanie utility sa volí príslušnými prepínačmi. V hranatých zátvorkách sú uvedené defaultné hodnoty parametrov, pokiaľ sa daný prepínač nepoužije.

• -o - určuje názov výstupného súboru. Pokiaľ sa neuvedie, výstupný súbor bude mať názov podľa vstupného súboru a prípona sa zmení na "pck", "tap" alebo "ptp", podľa toho, či sa má vytvoriť súbor pásky alebo nie.
• -append - spôsobí, že výsledok sa pripojí na koniec výstupného súboru. Pokiaľ nie je uvedený, existujúci výstupný súbor sa prepíše.
• -m - umožňuje voľbu módov pakovania. Za prepínačom môže byť akákoľvek kombinácia číslic 1 až 4. Quido použije na pakovanie iba uvedené módy.
• -z80 - vloží pred dáta rozpakovciu rutinu pre Z80.
• -i8080 - vloží pred dáta rozpakovciu rutinu pre Intel 8080.
• -a - určuje adresu, kde majú ležať rozpakované dáta a zároveň aj adresu od ktorej sa spúšťa samotné rozpakovanie. Defaultné hodnoty sa líšia pre Z80 a i8080 a sú obvyklé pre ZX Spectrum, či PMD 85.
• -ra - určuje adresu kam sa umiestni rozpakovacia rutina.
• -ja - určuje adresu kam sa skočí po rozpakovaní dát. Pokiaľ sa neuvedie, prevedie sa návrat inštrukciou RET.
• -vb - Quido bude pri pakovaní "ukecanejší".
• -h - zobrazí "help"
• -v - zobrazí verziu programu
• -ptp - výsledok sa uloží do PTP súboru pásky pre Emulátor PMD 85.
• -vram - rozpakovacia rutina bude relokovaná tak, aby mohla byť umiestnená do nevyužitej oblasti VRAM PMD 85. V tomto prípade ale zvolená adresa umiestnenia rutiny prepínačom -ra musí spĺňať nasledujúcu podmienku: addr >= 0xC030 AND addr <= 0xFDF0 AND (addr & 0xC03F) = 0xC030.
• -tap - výsledok sa uloží do TAP súboru pásky pre ZX Spectrum Emulátory.
• -b - do pásky sa pred spakovaný blok dát vloží BASICový loader.
• -c - adresa pre príkaz 'CLEAR adr' v BASICovom loaderi.
• -r - adresa pre príkaz 'RANDOMIZE USR adr' v BASICovom loaderi.
• -cb -cp -ci - voľba farby BORDERu, PAPERu a INKu pre BASICovy loader.
• -d80 - príkaz LOAD bude obsahovať '*' pre nahratie súboru z diskety.
• -hp - pred riadok s príkazom LOAD vloží príkaz POKE pre zamedzenie výpisu kazetových hlavičiek.

Quido v1.0 - Roman Borik 04/2010
Usage: Quido [options] infile.ext
 
Common options:
  -o outfile.ext  output file name
  -append         append at the end of the output file
  -m 1234         pack only with given modes [all modes are trying]
  -z80            insert Z80 unpack routine
  -i8080          insert i8080 unpack routine
  -a address      start address of binary file [32768 (z80) / 0 (i8080)]
  -ra address     unpack routine address [23456 (z80) / 32512 (i8080)]
  -ja address     jump address after unpack [ret]
  -vb             verbose
  -h              usage information
  -v              version info
 
Options for PTP file (PMD 85):
  -ptp            create PTP file
  -vram           locate unpack routine to the VideoRAM 
 
Options for TAP file (ZX Spectrum):
  -tap            create TAP file
  -b              include BASIC loader
  -c address      CLEAR address in BASIC loader [24575]
  -r address      address where to start bin. file for BASIC loader [32768]
  -cb colour      border color set by loader [0]
  -cp colour      paper color set by loader [0]
  -ci colour      ink color set by loader [7]
  -d80            create D80 syntax loader
  -hp             include POKE command for disabling tape headers
 
All numeric parameters must be nonnegative integers and can be in three forms:
  decimal (e.g. 12345)
  octal (e.g. 01234)
  hexadecimal (e.g. 0x1234)

Módy pakovania

Quido pakuje štyroma módmi, ktoré sa líšia smerom pakovania a vlastnosťami algoritmu Implod:

1. pakuje sa spätne od konca bloku dát, veľkosť Implod okna sú 4kB a maximálna dĺžka hľadanej frázy je 10 bytov
2. pakuje sa spätne od konca bloku dát, veľkosť Implod okna sú 2kB a maximálna dĺžka hľadanej frázy je 18 bytov
3. pakuje sa dopredu od začiatku bloku dát, veľkosť Implod okna sú 4kB a maximálna dĺžka hľadanej frázy je 10 bytov
4. pakuje sa dopredu od začiatku bloku dát, veľkosť Implod okna sú 2kB a maximálna dĺžka hľadanej frázy je 18 bytov

Shrink je pre všetky módy rovnaký a má dve "formy". Prvá, pre blok maximálne 66 opakujúcich sa bytov. Druhá, pre blok maximálne 322 opakujúcich sa bytov. Minimálna dĺžka Implod frázy, resp. minimálny počet opakujúcich sa bytov je 3.

Formát pakovaných dát

Pre reprezentáciu pakovaných dát sa používa značkový flag byte, ktorý informuje o type nasledujúcich dát. Značkový byte pre Implod je uvedený pre oba prípady a v samotných pakovaných dátach sa vyskytuje pochopiteľne iba jeden z nich podľa módu pakovania. Pre módy 1 a 2 platí uvedené poradie flag bytu a dát. V prípade módov 3 a 4 sú pakované dáta v opačnom poradí.

• IMPLOD - offset ku kopírovanej fráze 12 bitov / 4kB, dĺžka frázy 3 bity / 3 až 10 bytov

   7   6   5   4   3   2   1   0
 ---------------------------------
 | 0 | FR_LEN-3  |  OFFSET_HIGH  |
 ---------------------------------
 
 ---------------------------------
 |          OFFSET_LOW           |
 ---------------------------------

• IMPLOD - offset ku kopírovanej fráze 11 bitov / 2kB, dĺžka frázy 4 bity / 3 až 18 bytov

   7   6   5   4   3   2   1   0
 ---------------------------------
 | 0 | OFF_HIGH  |  FR_LEN-3     |  
 ---------------------------------
 
 ---------------------------------
 |          OFFSET_LOW           |
 ---------------------------------

• Dlhý SHRINK - počet opakovaných bytov 67 až 322

   7   6   5   4   3   2   1   0
 ---------------------------------
 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |  
 ---------------------------------
 
 ---------------------------------
 |            COUNT-67           |
 ---------------------------------
 
 ---------------------------------
 |              BYTE             |
 ---------------------------------

• Krátky SHRINK - počet opakovaných bytov 3 až 66

   7   6   5   4   3   2   1   0
 ---------------------------------
 | 1 | 1 |        COUNT-3        |
 ---------------------------------
 
 ---------------------------------
 |              BYTE             |
 ---------------------------------

• Nepakovateľné - počet nepakovateľných bytov 1 až 63

   7   6   5   4   3   2   1   0
 ---------------------------------
 | 1 | 0 |         COUNT         |
 ---------------------------------
 
 ---------------------------------
 |              BYTE             |
 ---------------------------------
 
 . . . .
 
 ---------------------------------
 |              BYTE             |
 ---------------------------------

Rozpakovacia rutina

Rozpakovacia rutina a jej dĺžka sa líši podľa módu pakovavania a podľa toho, či je určená pre Z80 alebo Intel 8080. Gro rutiny je vždy rovnaké, rozdiel je iba v interpretovaní flag bytu pre Implod a smer rozpakovania.

Z80 verzia rozpakovacej rutiny potrebuje na zásobníku 4 byty, ak bola volaná pomocou CALL a predpokladá sa návrat cez RET. V opačnom prípade postačujú na zásobníku 2 byty. i8080 verzia rozpakovacej rutiny potrebuje na zásobníku 6 bytov, ak bola volaná pomocou CALL a predpokladá sa návrat cez RET. V opačnom prípade postačujú na zásobníku 4 byty.

Nasledujúca tabuľka ukazuje dĺžky jednotlivých rutín. Pred lomítkom je celková dĺžka, za lomítkom je dĺžka po prenesení na pracovné miesto. Dĺžky rutín pre i8080 sú dlhšie z niekoľkých dôvodov. i8080 nepozná relatívne skoky, takže všetky skoky sú o byte dlhšie. Z80 inštrukcie LDIR, LDDR a RLD museli byť pre i8080 zodpovedajúco "rozpísané", čo rutiny podstatne predĺžilo. Rutiny umiestnené v nevyužitej oblasti VRAM PMD 85 sú ešte dlhšie kvôli nutnosti "nasekať" ich na 16 bytové bloky, z ktorých väčšina obsahuje skok do ďalšieho 16 bytového bloku vo VRAM.

Pre zaujímavosť ešte uvediem zdrojový kód rozpakovacej rutiny pre Z80 pre mód 1, ostatné verzie sú analogické a sú súčasťou archívu na stiahnutie:

UnpackMode1:
	ld	hl,M1
	ld	de,RoutineAddr
	ld	bc,M1Length
	push	de
	ldir
	ld	hl,Data1+PackedLength-1
	ld	de,BeginAddr+OrigLength-1
	ld	bc,PackedLength
	ret
Mover1Length	equ	$-UnpackMode1	; 22 bytov
 
M1:	lddr			; presun pakovane data na koniec oblasti, kde az 
	ex	de,hl		; budu vysledne rozpakovane data zasahovat
	ld	de,BeginAddr	; zaciatocna adresa vyslednych dat
	inc	hl		; adresa spakovanych dat
M1NextByte:
	ld	a,(hl)		; vezmi flag byte
	bit	7,a		; je to Implod ?
	jr	nz,M1NoImplod	; nie, skoc dalej
	and	15		; odmaskuj vyssie 4 bity offsetu ku kopirovanej fraze
	ld	b,a		; uloz do B
	rld			; dlzku frazy presun do A
	add	a,3		; uprav na spravny rozsah 3 az 10
	ld	c,a		; a uloz do C
	inc	hl		; posun ukazatel na nizsi byte offsetu frazy
	ld	a,e		; odpocitaj nizsi byte offsetu
	sub	(hl)
	inc	hl		; posun ukazatel na spakovane data
	push	hl		; a odloz si ho
	ld	l,a		; uloz nizsi byte adresy zdrojovej frazy
	ld	a,d		; a odpocitaj aj vyssi byte offsetu
	sbc	a,b
	ld	h,a		; HL=zdrojova adresa frazy
	ld	b,0		; BC=dlzka frazy
	jr	M1FillBlock
 
M1NoImplod:
	inc	hl		; posun ukazatel na spakovane data
	and	127		; odmaskuj iba platne bity
	jr	z,M1BigBlock	; je to dlhy Shrink ? Ak ano, skoc dalej
	bit	6,a		; je to kratky Shrink ?
	jr	nz,M1LitBlock	; ano, skoc dalej
	ld	c,a		; su to nepakovatelne data - BC=pocet
	ldir			; presun na cielovu adresu v DE
	jr	M1NextByte	; spracuj dalsi flag
 
M1LitBlock:
	and	63		; pocet rovnakych bytov
	add	a,3		; uprav pocet na 3 az 66
	jr	M1Block
 
M1BigBlock:
	ld	a,(hl)		; pocet rovnakych bytov
	inc	hl		; posun ukazatel na spakovane data
	add	a,67		; uprav velkost na 67 az 322
	jr	nc,M1Block
	inc	b
M1Block:
	ld	c,a		; BC=pocet
	ldi			; priprav opakovany byte
	push	hl		; odpamataj ukazatel spakovanych dat
	ld	h,d		; budeme vyplnovat
	ld	l,e
	dec	hl		; HL=DE-1, BC=pocet-1
M1FillBlock:
	ldir			; prekopiruj/vypln blok
	pop	hl		; obnov ukazatel na spakovane data
	or	a		; CY=0
	sbc	hl,de		; ak sa DE s HL stretnu, je to koniec rozpakovania
	add	hl,de
	jr	nz,M1NextByte	; opakuj pre cely blok
	jp	RunAddr		; skok na zvolenu adresu alebo navrat cez RET
 
M1Length	equ	$-M1	; 79 bytov
 
Data1:	ds	PackedLength	; samotne pakovane data

Na stiahnutie

• Quido - ZIP archív obsahujúci binárky pre Win32 konzolu a Linux, zdrojové texty Quida a zdrojové texty rozpakovacích rutín