25. apríla 2010

QUIDO utilita pre PC

Quido je PC utilita určená pre pakovanie dát a programov pre (obvykle) 8 bitové počítače. Quido pôvodne vznikol ako obrazovková utilita pre ZX Spectrum, ale keďže pri tvorbe 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. Táto utilita 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.

quido10.zip - archív obsahujúci binárky pre win32 konzolu a x86 linux + zdrojové texty + zdrojové texty rozpakovacích rutín

Quido používa pri pakovaní dva algoritmy. Prvým je Shrink a druhým Implod. 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ú.

Tieto dva algoritmy, Shrink a Implod, 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 2x dlhšie ako Turbo Imploder. V prípade PC utility je čas pakovania pochopiteľne zanedbateľný.

Kľúčové vlastnosti a výhody Quido PC utility:

  • 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 TAP (ZX Spectrum) alebo PTP (PMD 85);
    v prípade TAP môže byť naviac pridaný aj BASICový zavádzač (ako utilita bin2tap)

Použitie PC utility Quido

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.

Príkazový riadok: quido [prepinace] vstupny_subor.ext

  • -o vystup.ext
    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 nastavený, existujúci výstupný súbor sa prepíše.
  • -m 1234
    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. [1234]
  • -z80
    vloží pred dáta rozpakovciu rutinu pre Z80.
  • -i8080
    vloží pred dáta rozpakovciu rutinu pre Intel 8080.
  • -a adresa
    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. [32768 (z80) / 0 (i8080)]
  • -ra adresa
    určuje adresu kam sa umiestni rozpakovacia rutina.
    [23456 (z80) / 32512 (i8080)]
  • -ja adresa
    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

Možnosti špecifické pre PMD 85:

  • -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

Možnosti špecifické pre ZX-Spectrum:

  • -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ží BASIC loader.
  • -c adresa
    adresa pre príkaz 'CLEAR adr' v BASIC loaderi. [24575]
  • -r adresa
    adresa pre príkaz 'RANDOMIZE USR adr' v BASIC loaderi. [32768]
  • -cb
    voľba farby BORDER pre BASIC loader. [0]
  • -cp
    voľba farby PAPER pre BASIC loader. [0]
  • -ci
    voľba farby INK pre BASIC loader. [7]
  • -d80
    príkaz LOAD bude obsahovať '*' pre nahratie súboru z diskety.
  • -hp
    pred riadok s príkazom LOAD vloží príkaz POKE 23739,111 pre zamedzenie výpisu kazetových hlavičiek.

Všetky číselné hodnoty je možné zadávať v týchto troch číselných sústavách:

  • desiatkovo (decimal): 12345
  • osmičkovo (octal): 01234
  • šestnástkovo (hexadecimal): 0x1234

Módy pakovania a formát pakovaných dát

Quido pakuje štyroma módmi, ktoré sa líšia smerom 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.

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] flag 0 FR_LEN-3 OFFSET_HI
    [1] OFFSET_LO
  • 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] flag 0 OFFSET_HI FR_LEN-3
    [1] OFFSET_LO
  • Dlhý SHRINK
    počet opakovaných bytov 67 až 322
      7 6 5 4 3 2 1 0
    [0] flag 1 0 0 0 0 0 0 0
    [1] COUNT-67
    [2] REPT_BYTE
  • Krátky SHRINK
    počet opakovaných bytov 3 až 66
      7 6 5 4 3 2 1 0
    [0] flag 1 1 COUNT-3
    [1] REPT_BYTE
  • Nepakovateľné
    počet nepakovateľných bytov 1 až 63
      7 6 5 4 3 2 1 0
    [0] flag 1 0 COUNT
    [1]
     ...
    [n]
    ...
    BYTES
    ...

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.

Dĺžky rozpakovacích rutín v bytoch
  Z80 i8080 i8080 pre PMD 85 VRAM
Mód 1 101 / 79 143 / 116 177 / 139
Mód 2 103 / 81 143 / 116 177 / 139
Mód 3 98 / 79 140 / 116 177 / 139
Mód 4 100 / 81 140 / 116 177 / 139

Žiadne komentáre:

Zverejnenie komentára