Kompresja od środkaDość popularny staje się ostatnio problem zmniejszania rozmiarów zbiorów wszelkimi dostępnymi sposobami. Jednym z nich jest: archiwizacja,Jaki algorytm zastosować do kompresji jakiego typu zbiorów i na czym polega kompresja oraz jak wygląda to w praktyce? Na początek bardzo prosta metoda zwana wyszukiwaniem Powtarzających Się Elementów ciągu (PSE). Przykładowo, mając ciąg abbbbccaa-abfffffccc możemy zapisać go następująco: a4b2c3ab5f3c. Oznacza to, że a wystąpiło na początku ciągu dokładnie raz, następne było b, które powtórzyło się cztery razy itd. W rzeczywistości rzecz ma się trochę inaczej. Spróbujmy więc zagęścić na przykład następujący ciąg: 122224444436666. Otrzymujemy: 14254346, nieprawdaż? Ale czym odróżnić długość powtarzających się elementów od elementu ciągu. Nie da się? Bzdura! Wprowadźmy dodatkowy bit na początku każdego elementu ciągu wyjściowego wskazujący na to, czy:
Klocek pierwszy.
_opt equ %100101
_org equ $3000
org _org
opt _opt
* -procedury ROM
ciov equ $e456
dschar equ $f2b0
* -system
dosrun equ $a
savmsg equ $64
runad equ $2e0
initad equ $2e2
memhi equ $2e5
memlo equ $2e7
hatabs equ $31a
iocb equ $340
skctl equ $d20f
io_com equ iocb+2
io_sta equ iocb+3
io_adr equ iocb+4 (2)
io_len equ iocb+8 (2)
io_mod equ iocb+10
io_aux equ iocb+11
* -stałe
shift equ $8
chn0 equ $00
chn1 equ $10
chn2 equ $20
putt equ $9
gett equ $5
putb equ $b
getb equ $7
eol equ $9b
eof equ $88
len_text equ $80
len_bufor equ $bc1f-_org
outbit equ 3
* -numery komunikatow
hello_m equ 0
compres_m equ 1
decomp_m equ 2
get_m equ 3
put_m equ 4
err_m equ 5
long_m equ 6
* -strona zerowa
pse_z0 equ $80 (2)
Znaczenie większości stałych oraz procedur zostało
dokładnie opisane w artykułach z cyklu "Programowanie procesora 6502". Dokładnego omówienia wymagają stałe OUTBIT oraz LEN_BUFOR. Pierwsza z nich wskazuje liczbę bitów reprezentujących długość wskaźnika. Prześledźmy dokładnie przypadek dla OUTBIT równego 3. Za pomocą trzech bitów możemy przedstawić maksymalną liczbę 111 binarnie, czyli 7 dziesiętnie. Oznacza to, iż wskaźnik będzie zliczał wszystkie powtarzające się elementy, których suma nie przekroczy 7. Następnie przyjmie wartość zero, po czym rozpocznie poszukiwanie nowego podciągu. Stała LEN_BUF wskazuje długość bufora do odczytu pliku. Większość z Was zapyta dlaczego tej długości nie obliczyć w znany już sposób MEMHI - MEMLO? Otóż zależy nam na tym, aby wszystkie wersje archiwizera były kompatybilne (współpracujące). Niemożliwe byłoby odzyskanie długiego pliku skompresowanego przy użyciu jednego DOS-a pod kontrolą innego w przypadku zmniejszenia się liczby wolnych bajtów pamięci.Ładnie się przywitajmy,
main equ *
ldx #hello_m
jsr dsp_msg
i przystąpmy do pracy.
code ldx #compres_m
jsr dsp_msg
ldx #get_m
jsr get_text
bpl *+5
Jeżeli wystąpił błąd odczytu specyfikacji znaczy to, iż naciśnięto BREAK i czas przejść do dekompresji.
jmp decode
Wszystko w porządku, więc zabezpieczmy się przed roztargnionymi programistami,
ldx #chn1
jsr close
a następnie spokojnie odczytajmy zbiór.
lda #4 -odczyt
jsr open
bmi code -wystapil blad!
W przypadku wystąpienia błędu sygnalizowanego znacznikiem N procesora, następuje ponowna prośba o podanie prawidłowej specyfikacji zbioru.
* -czytaj plik
lda
Gdy plik zmieści się cały, otrzymamy wartość statusu równą $88 (skończyły się dane, plik umieszczony w całości w buforze). W przeciwnym wypadku bufor został zapełniony, ale znacznik końca pliku nie osiągnął wartości krytycznej (został wczytany tylko kawałek pliku). Poinformujmy użytkownika o tym fakcie odpowiednim komunikatem.
jsr close
ldx #long_m
jsr dsp_msg
jmp code
Ustalmy rzeczywisty koniec pliku w pamięci oraz fikcyjnie powiększmy go o jeden. Wynika to z ustawienia znacznika flagowego C procesora również w przypadku równości zmiennych zawartych w słowach PSE_ZO oraz END_FILE kontrolowanych w podprogramie CHECK_RG.
isok clc
lda io_len,x
sta read
adc bufa
sta end_file -ustal koniec pliku
lda io_len+1,x
sta read+1
adc bufa+1
sta end_file+1
inc end_file
bne *+5
inc end_file+1
Plik został wczytany, zmienne ustalone, przystąpmy zatem do zapisu wyników kompresji.
code_out ldx #chn1
jsr close
ldx #put_m -target
jsr get_text
bpl *+5 -BREAK zmiana na odczyt
jmp code
ldx #chn1
lda #8 -plik do zapisu
jsr open
bmi code_out
Ustawmy jeszcze liczniki programu.
jsr reg_zero
Do tego miejsca wszystkie opisywane metody kompresji będą takie same. Podobnie podprogramy również będą wyglądały analogicznie.Wyzerujmy znacznik zakończenia pliku.
lda #0
sta all_mode
Pobierzmy pierwszy bajt.
jsr get_one
bcc comp_l
Jeżeli skończył się plik (ustawiony znacznik C procesora) wykonajmy skok do procedury kończącej kompresję.
jmp all_byte
Zapiszmy bajt, jaki otrzymaliśmy, jeszcze się przyda.comp_l sta rebyteWyzerujmy wskaźnik powtórzeń
comp_f lda #0
sta ile
i pobierajmy kolejne bajty.
comp_d jsr get_one
bcs all_byte -koniec pliku
Nowo odczytany bajt przechowajmy w zmiennej COMP_b
sta comp_b
oraz porównajmy go z wartością otrzymaną poprzednio.
cmp rebyte
bne new_byte -rozne bajty
W przypadku równości sprawdźmy, czy wskaźnik powtórzeń nie osiągnął już swojej maksymalnej wartości.
lda ile
cmp pse_bit
Równość oznacza zakończenie starej frazy i rozpoczęcie nowej.
beq new_byte
Zwiększ licznik powtórzeń.
inc ile
Operację odczytu powtarzaj w kółko.
jmp comp_d
Otrzymaliśmy nowy bajt lub wskaźnik powtórzeń został przepełniony. Zbadajmy, czy poprzedni bajt powtórzył się przynajmniej raz (ILE<>0).
new_byte lda ile
beq only_one
Powtórzył się co najmniej raz. Wyślijmy skasowany bit, o którym była mowa na początku.
clc
jsr putbit
Podobno oszczędność jest zaletą prawdziwych programistów. Wykonajmy skok względny bez używania etykiety. W przypadku pomyślności operacji zapisu bitu przeskoczmy o trzy bajty w przód (omińmy JMP CODE_OUT).W miejscu *+2+3 zaznaczmy asemblerowi, że ma przeliczyć skok względny od tego adresu, przez dwa bajty skoku względnego (rozkaz BPL oraz jednobajtowy operand) i trzy bajty z następnej linii (jeden bajt rozkazu JMP i dwa bajty adresu CODE_OUT). Sposób ten jest nieco skomplikowany, jednak odciąża asembler.
bpl *+2+3 (bmi code_out)
jmp code_out
Przesuńmy w lewo 8-OUTBIT razy wartość wskaźnika powtórzeń, aby otrzymać znaczące bity na skrajnej lewej pozycji.
lda ile
ldx #8-outbit
comp_r beq comp_g
asl @
dex
bpl comp_r (jmp)
Wyślijmy OUTBIT bitów.
comp_g ldx #outbit
jsr pt_xbit
bpl comp_a
jmp code_out
Do wysłania tylko jeden bajt.
only_one sec
jsr putbit
bpl *+5 (bmi code_out)
jmp code_out
comp_a lda rebyte
jsr pt_8bit
bpl *+5
jmp code_out
Kolejny sposób oszczędzania. Zastosowanie zmiennej COMP_B bezpośrednio w programie.
comp_b equ *+1
comp_c lda #0
jmp comp_l
all_mode equ *+1
all_byte lda #0
bne all_end
Poprzez zastosowanie sprytnej sztuczki polegającej na jednorazowym przejściu przez poniższe rozkazy zabezpieczamy się przed niewystaniem np. nie dokończonej frazy lub bajtu znajdującego się w zmiennej COMP_B. Drugie dojście do etykiety ALL_BYTE spowoduje skok do ALL_END. Sprawdźcie sami.
inc all_mode
W starym bajcie zamieńmy bity. W ten sposób okłamiemy ATARI, że otrzymało nowy bajt różny od poprzedniego (pozwoli nam to na zamknięcie frazy powtarzających się elementów).
lda rebyte
eor #$ff
jmp comp_l
Dopilnujmy, żeby wysłane zostały wszystkie ważne bity z bufora.
all_end lda pbit_cnt
cmp #8
beq all_ok
jsr putbit
bpl all_end
jmp code_out
Zamknijmy kanał i zacznijmy wszystko od początku.
all_ok ldx #chn1
jsr close
jmp code_out
Dekompresja danych.
decode equ *
ldx #decomp_m -decode
jsr dsp_msg
ldx #get_m
jsr get_text
bpl *+5
* -break zmiana na kompresje
jmp code
deco_in ldx #chn1
jsr close
lda #4 -odczyt
jsr open
bmi decode -blad !!!
clc
lda bufa
adc <len_buf
sta end_file
lda bufa+1
adc >len_buf
sta end_file+1
jsr reg_zer
Niecierpliwi mogą spróbować własnych sił. Pozostałym życzę odrobiny cierpliwości, zamieszczam jednak wszystkie procedury do odczytu pojedynczego bitu (GETBIT), całego bajtu (GETBYTE) oraz zapisu odkodowanego bajtu (PUT_ONE).Procedury I/O.
* -wyslij 8 bitow
pt_8bit ldx #8
* -wyslij x bitow
pt_xbit stx pt_xcnt
sta ptbyte
pt_xcnt equ *+1
pt_cn lda #0
bne pt_lop
ldy #1
rts
pt_lop dec pt_xcn
rol ptbyte
jsr putbit
bpl pt_cn
rts
* -proc putbit
putbit rol byte_r
dec pbit_cnt
beq *+3
rts
lda #8
sta pbit_cnt
* -znowu 8 bitow do wyslania
inc write
bne *+5
inc write+1
byte_r equ *+1
lda #0
putbyte pha
lda #putb
put_u ldx #chn1
sta io_com,x
lda #0
sta io_len,x
sta io_len+1,x
pla
jmp mcio
*- Wez jeden bajt z urzadzenia.
getbyte lda #getb
pha
bne put_u (jmp)
Przy odczycie pojedynczego bitu wygodnie będzie skorzystać z licznika zapisu bitów PBIT_CNT.
getbit inc pbit_cnt
lda pbit_cnt
cmp #9
bcs get_g -pobrano juz caly bajt
rol byte_r
ldx #chn1
ldy io_sta,x
rts
get_g lda #0
sta pbit_cnt
jsr getbyte
bpl *+3
rts
sta byte_r
jmp getbit
gt_8bit ldx #8
gt_xbit stx gt_xcnt
lda #0
sta gtbyte
gt_xcnt equ *+1
gt_cnt lda #0
bne gt_lop
lda gtbyte
ldy #1
rts
gt_lop dec gt_xcnt
jsr getbit
bpl *+3
rts
rol gtbyte
jmp gt_cnt
put_one jsr check_rg
bcc *+3
rts
sta (pse_z0),y
jmp get_cd
get_one jsr check_rg
bcc *+3
rts
lda (pse_z0),y
get_cd inc pse_z0
bne *+4
inc pse_z0+1
rts
Sprawdź, czy nie został osiągnięty koniec pliku. Odpowiednio ustaw znacznik C procesora.
check_rg pha
lda pse_z0
cmp end_file
lda pse_z0+1
sbc end_file+1
pla
ldy #0
rts
reg_zero ldx #1
rg_zr lda #0
sta write,x
lda bufa,x
sta pse_z0,x
dex
bpl rg_zr
Ustalmy maksymalną wartość wskaźnika.
lda #0
ldx #outbit
rg_ob sec
rol @
dex
bne rg_ob
sta pse_bit
Zaznaczmy, że żaden bit nie został wysłany ani odebrany.
lda #8
sta pbit_cnt
rts
* -zamknij kanal
close lda #12
sta io_com,x
jsr ciov
lda #3
sta skctl -cicho !
rts
* -otworz kanal
open sta io_mod,x
lda #3
sta io_com,x
* szukaj dwukropka
ldy #':'
cpy text+1
beq seti
cpy text+2
beq seti
lda #0
* ustaw iocb
seti clc
adc dnma
sta io_adr,x
lda #0
adc dnma+1
sta io_adr+1,x
lda skctl
and #shift
asl @
asl @
asl @
asl @
sta io_aux,x
jsr mcio
php
lda bufa
sta io_adr,x
lda bufa+1
sta io_adr+1,x
lda io_mod,x
ora #$3
sta io_com,x
plp
rts
* cio z ew. komunikatem
mcio jsr ciov
bpl iook
cpy #eof
beq iook
error ldx #err_m
derr jsr dsp_msg
ldy #$ff
rts
iook ldy #1
rts
Nieznacznie zmodyfikowana procedura odczytu tekstu z edytora.
get_text jsr dsp_msg
ldx #chn0
lda #gett
sta io_com,x
lda txta
sta io_adr,x
lda txta+1
sta io_adr+1,x
lda
Procedura wyświetlania komunikatu.
dsp_msg equ *
* odszukaj tekst nr x
ldy #0
fm0 dex
bmi mout
fmes lda data,y
iny
cmp #eol
bne fmes
beq fm0 (jmp)
* wypisz tekst
mout txa
ldx #chn0
sta io_len,x
clc
tya
adc dtaa
sta io_adr,x
lda #0
sta io_len+1,x
adc dtaa+1
sta io_adr+1,x
lda #putt
sta io_com,x
jmp ciov
Pomimo, że program nie jest relokowalny, zachowajmy sposób zapisu niektórych stałych - przyzwyczajenia też są ważne!
dtaa dta a(data)
dnma dta a(dnam)
txta dta a(text)
bufa dta a(bufor)
* dane
data equ *
dta c'TA PSE de/compressor',b(eol)
dta c' Compress',b(eol)
dta c' Decompress',b(eol)
dta c'Source:',b(eol)
dta c'Target:',b(eol)
dta c'I/O error !',b(eol)
dta c'Buffor full!',b(eol)
dnam dta c'D1:'
text org *+len_text
pbit_cnt org *+1 -ile bitow wyslano/odczytano
pse_bit org *+1 -ile bitow wskaznika
write org *+2 -ile bajtow wyslano
end_file org *+2 -rzeczywisty koniec pliku
read org *+2 -ile bajtow wczytano
ptbyte org *+1 -zapisywany bajt
gtbyte org *+1 -odczytywany bajt
rebyte org *+1 -powtarzajacy sie bajt
ile org *+1 -ile takich samych bajtow wystapilo
bufor equ * -bufor odczytu pliku
Nieznacznie zmieniony sposób odczytu nazwy oraz numeru urządzenia, z jakiego program został uruchomiony.
run_me ldx $2e
ldy iocb,x
lda hatabs,y
sta dnam
lda $21
ora #'0'
sta dnam+1
rts
org runad
dta a(main)
dta a(run_me)
Za miesiąc o tym, jak odkodować PSE i jak zakodować Imploding!
MATHNOID'93
|