26

Odp: kompresja - wynik na 1 stronie

zerknalem jeszcze raz. dane sa bardzo specyficzne...

moze zamiast danych wejsciowych zastosowac 'opis dekompresji' (dwubajtowe rozkazy)

w takim przypadku

przyklad1: 14 bajtow + 1 bajt dlugosc 'opisu'
przyklad2: 16 bajtow + 1 bajt dlugosc 'opisu'

http://atari.pl/hsc/ad.php?i=1.

27

Odp: kompresja - wynik na 1 stronie

Tak jak w moim opisie. po 4 bity. grupujemy po dwa zeby miec bajt. tablicujemy.

d_00000000   dta c'DDX'
d_00000001   dta c'DDDX'
d_00000010   dta d'DCX'
...
d_11111101   dta d'AAAAAAAAAAAAAAX'
d_11111110   dta d'AAAAAAAAAAAAAAAX'
d_11111111   dta d'AAAAAAAAAAAAAAAAX'

* gdzie X to znak o kodzie > $7f
* w sumie tablica na 900 bajtow
* srednio kazd tablica ma 3.5 bajta (900/256)

tableL dta l(d_00000000),l(d_00000001),l(d_00000010), ... ,l(d_11111101),l(d_11111110),l(d_11111111)
tableH dta h(d_00000000),h(d_00000001),h(d_00000010), ... ,h(d_11111101),h(d_11111110),h(d_11111111)

*tablica ma 512 bajtow

dekompresuj                 ;cykle
    lda #0                  ;2
    tax                     ;2
    sta strona_zero         ;3
loop
    ldy bufor_wejsciowy,x   ;4
    lda tableL,y            ;4 z kawalkiem
    sec                     ;2
    sbc strona_zero         ;3
    sta L+1                 ;4
    lda tableH,y            ;4 z kawalkiem
    sbc #0                  ;2
    sta L+2                 ;4
    ldy strona_zero         ;3
L   lda $ffff,y             ;4
    sta bufor_docelowy,y    ;5
    iny                     ;2
    bpl L                   ;3 bez kawaleczka
    sty strona_zero         ;3
    inx                     ;2
    cpx #dlugosc            ;2
    bpl loop                ;3 (bez kawaleczka dla ostatniego testu)
    rts                     ;2

srednio na wynikowy bajt mamy (40+14*3.5)/3.5 = 25 cykli (najmniej 16 cykli najwiecej 27, a zreszta srednia na zdekompresowany blok zalezy scisle od bloku)

Wiem, ze algorytm jest abstrakcyjny i nieoplacalny (bo wymaga 1.5 kB tablic) ale jest szybki :P

jellonek. Podnosisz rękawice? :cool:

(Mam nadzieje, ze nie pomylilem sie w obliczeniach)

Ostatnio edytowany przez laoo/ng (2006-02-14 11:33:40)

Odp: kompresja - wynik na 1 stronie

laoo/ng: faktycznie maximum perwersum. ;)

29

Odp: kompresja - wynik na 1 stronie

nie takie rzeczy na atari juz sie kodowalo (rozpisane setki kilobajtow kodu itp.... :P )

30

Odp: kompresja - wynik na 1 stronie

e chyba cos poknocilem. juz sam niewiem


hmm, a moze tak:

przyklad 1: 12 +1 bajtow
przyklad 2: 12 +1 bajtow

1. wypelniamy blok 192 bajtow kodem powtarzajacym sie najczesciej
2. rozkaz 1 bajt index w bloku, 2 bajt |M|T|D|D|P|P|P|P|W| gdzie
M - metoda fill, plot (plot stawia dana na poczatku i po przesunieciu, fill wypelnia)
T - tryb patrz P dla plot automatyczna zmiana na draw
D - dane - sa juz tyklko 3 rozne elementy
P - przesuniecie 1-16 lub index+x*16
W - jakas wartosc bitu 9

metoda wolna, zero tablic, dekompresor bardzo :-) krotki.

i tu sie zastanawiam czy to tylko na kartce tak fajnie wyglada?

Ostatnio edytowany przez xxl (2006-02-14 12:53:56)

http://atari.pl/hsc/ad.php?i=1.

31

Odp: kompresja - wynik na 1 stronie

Niestety nie rozumiem tego algorytmu:

a) dlaczego 2. bajt ma 9 bitow?
b) T - zupelnie nie wiem co sie dzieje? zmiana na draw jestli byl plot? w jakim kontekscie?
c) czym jest W?

jedyny pomysl jaki mam, to skoro sa 3 mozliwe wartosci, to zamiast na stale przypisac im 2 bitow az prosi sie kod przedrostkowy, czyli dla najczestrzej wartosci 1 dla drugiej 01 dla trzeciej 00. i oszczedzaby jeden bit przy najczestrzej wartosci. wada: mamy rozna dlugosc rozkazu, ale jesli drugi bajt jest 9-cio bitowy to i tak trzeba pobierac po bitach :P

32

Odp: kompresja - wynik na 1 stronie

zapisze jeszcze raz:

rozpakowane bloki maja po 192 bajty, wypelniamy go wartoscia wystepujaca najczesciej

pobieramy dlugosc 'programu z opisem dekompresji'
pobieramy kolejno 2 bajty

co zawieraja te dwa bajty:
pierwszy bajt - index - od ktorego miejsca w boku 192 b zaczynamy
drugi bajt bity od najstarszego:

|M|T|D|D|P|P|P|P|W|

M - metoda fill, plot
plot stawia dana na poczatku i po przesunieciu innymi slowy moze zrobic tak: ABBBBBA lub tak: A (A istotny),
fill wypelnia, moze zrobic tak:AAAbbbAAAbbbAAA (A istotny) - nie z przykladu powyzej

T - tryb patrz P dla plot automatyczna zmiana na draw
jesli M bylo plot to przy ustawieniu T mamy draw oraz zmiane interpretacji P

D - dane - sa juz tyklko 3 rozne elementy
dane: 01, 10, 11

P - przesuniecie 1-16 lub index+x*16
w zaleznosci od T mozemy zrobic przy plot tak: A lub AbbbbbA a przy draw tak: AAAAAA lub tak: AbbAbbA (A dane istotne)
to dekompresor musi zadbac i obliczac koniec dzialania rozkazow ale to jest akurat b.proste.


analogia w nazwie fill, draw i plot jest trafna w przypadku tego algorytmu i TYCH konkretnych danych.

W - jakas wartosc bitu 9
moj poprzedni post byl zaszumiony i to jest wlasnie ta niechciana tresc ;-)

Ostatnio edytowany przez xxl (2006-02-14 13:46:42)

http://atari.pl/hsc/ad.php?i=1.

33

Odp: kompresja - wynik na 1 stronie

laoo/ng napisał/a:

Tak czytam co Ty tu napisales ... i mysle, ze chyba nie zrozumiales

Tia, cofnalem sie i przeczytalem, że WYJSCIOWYCH bedzie 3k, a wczesniej
nie wiem czemu mi sie przeczytalo, że wejsciowych :), czyli nawet liczac te 3k
jako bajty, a nie symbole wyszlo mi ze trza spakowac 768 bajtow do <256 :)
czyli do 33,(3)% co się takie łatwe nie wydaje jak nie ma odpowiedniego rozkladu
danych :). No, ale jak widac wzialem pod uwage gorszy problem niż był w rzeczywistości.

---==<<Sc0rpi0>>==---

34

Odp: kompresja - wynik na 1 stronie

Algorytm konkretnie pod zastosowanie, czyli rzeczywiscie w praktyce program i maszyna wirtualna ktora go wykonuje :)
Pobierannie po dwa bajty jest bardzo wygodne i faktycznie chyba juz nie ma co kombinowac dalej, bo kodujac na bitach moznaby uszczknac tylko z 2-3 bajty ale IMHO za duzym kosztem.

nie wiem tylko jak obliczana jest ta ilosc literek 'b' do pominiecia i od ktorego momentu pomijamy, ale wierzę, ze to jest zakodowane jakos w P :) Jezeli te kodowanie w P jest dobre, to powinno dzialac :P

35

Odp: kompresja - wynik na 1 stronie

laoo:

ptr1    equ $80
ptr2    equ $82
ptr3    equ $84

        org $2000

qniec   rts
decomp  lda ptr2+1
        sta ptr3+1
        ldy #0

loop    lda (ptr1),y
        beq qniec
        inc ptr1
        asl @
        ror @
        tax
        lda (ptr1),y
        bcc rle

; offsetowanie
        sta ptr3
loopp   lda (ptr3),y
        sta (ptr2),y
        inc ptr3
        inc ptr2
        dex
        bne loopp
koniec  inc ptr1
        bne loop
        inc ptr1+1
        jmp loop

; rle
rle     sta (ptr2),y
        inc ptr2
        dex
        bne rle
quit   inc ptr1
        bne loop
        inc ptr+1
        jmp loop
; w miejsce od "quit" wpisac: beq koniec (co da krotszy kod, ale sie wolniej wykona... )

policzy ktos cykle? ;)

dekompresja do tego co wczesniej opisalem - tylko zaznaczam - to moj pierwszy kod od jakichs 15 lat ;)
pewnie cos spartolilem...
ptr1 - wskaznik na dane wyjsciowe
ptr2 - wskaznik gdzie dekompresowac
zalozenie - bufor wyjsciowy zaczynaja sie od adresu w miare niskiego wzgledem poczatku strony (<64), bo brak sprawdzania przepelnienia ;)

Ostatnio edytowany przez jellonek (2006-02-14 15:00:00)

The UNIX Guru`s view of Sex:
unzip; strip; touch; finger; mount; fsck; more; yes; umount; sleep

36

Odp: kompresja - wynik na 1 stronie

Cyklujac najbardziej zagniezczone petle mamy

loopp   lda (ptr3),y    ;5
        sta (ptr2),y    ;6
        inc ptr3        ;5
        inc ptr2        ;5
        dex             ;2
        bne loopp       ;3

26 cykli

oraz

rle     sta (ptr2),y      ;6
        inc ptr2          ;5
        dex               ;2
        bne rle           ;3

16 cykli.

Dodatkowo zauwazylem, ze w mojej procce jest blad bo zapomnialem, ze iny tez ustawia bit N. Rozwiazaniem jest dodanie np lsr @ czyli

L   lda $ffff,y             ;4
    lsr @                   ;2
    sta bufor_docelowy,y    ;5
    iny                     ;2
    bcc L                   ;3

i mam 16 cykli zamiast 14 i moje obliczenia sredniego czasu zwiekszaja sie do  27 cykli (najmniej 18 cykli najwiecej 29) oczywisice pamietajac zeby dane byly przesuniete w lewo i konczacy znak miał ustawiony najmlodszy bit.

Reasumujac petlę ofsetującą masz bardzo dluga, a RLE jest identyczna. Nie wiem jak ulozy sie srednia, bo jest inna reprezentacja danych, ale chyba na moją korzysc :P


PS.: wydaje mi sie, ze

        asl @
        ror @

jest równoważne

        clc

wiem ze chciales skoczyc jesli najstarszy bit byl ustawiony ale tak sie nie da. (no i dodatkowo skaczac do rle jest ustawiony bit N i bedzie się krecilo troche dluzej :) ) Ale da sie samym lsr @ jesli bedzie sie inadzej pamietalo ten bajt w buforze.

37

Odp: kompresja - wynik na 1 stronie

        asl @
        ror @

to rzeczywiscie mialo dac najstarszy bit w C, ale i ewentualne jego skasowanie - a ze dawno w 6502 klepalem
to i bladnie przyjalem ze 'ror' rotuje z pominieciem C...

The UNIX Guru`s view of Sex:
unzip; strip; touch; finger; mount; fsck; more; yes; umount; sleep

38

Odp: kompresja - wynik na 1 stronie

xxl: bądź tak dobry i podaj dane wyjściowe (ciąg bajtów na wyjściu) dla drugiego przykładu, po spakowaniu go twoim sposobem. thx

39

Odp: kompresja - wynik na 1 stronie

pisze z palca wiec mozliwe ze sie machnalem:

%10,%11011100,%1111,%11011100,%110110,%10110101,%1110110,%10110101,%1001000,%10010001,%1011000,%10100001

12 bajtow

ciezko napisac pakera... depakera o wiele prosciej

Ostatnio edytowany przez xxl (2006-02-15 00:43:21)

http://atari.pl/hsc/ad.php?i=1.

40

Odp: kompresja - wynik na 1 stronie

xxl: Coś mi się nie zgadza, albo nie wszystko zrozumiałem :(

Dane wejściowe były następujące:

_1____________1_
_1____________1_
_1____________1_
_1___3____3___1_
_1_____11_____1_
_1_____44_____1_
_1____________1_
_1___3____3___1_
_1____________1_
_1____________1_
_1____________1_
_1____________1_


Po spakowaniu otrzymałeś  %10,%11011100,%1111,%11011100,%110110,%10110101,%1110110,%10110101,%1001000,%10010001,%1011000,%10100001.

M jest zawsze ustawione, a z analicy danych wychodzi mi, że zawsze robisz plot.
Zakładam, że pierwszy bajt równy zero kończy dekompresję, stad wartość pierwszego bajtu jest zwiększana o 1.
czyli:

%10,        - na poz $1 i +$c
%11011100,    - stawiasz znak 1

%1111,        - na poz $10 i +$c
%11011100,    - stawiasz znak 1

%110110,        - poz $35 i +$5
%10110101,    - stawiasz znak 3

%1110110,    - poz $75 i +$5
%10110101,    - stawiasz znak 3

%1001000,    - na poz $47 i $48
%10010001,    - wpisanie znaku 1

%1011000,    - na poz $57 i $58
%10100001    - wpisanie znaku 4

A co z resztą danych? Poza pierwszym i drugim wierszem brakuje mi jedynek występujących po lewej i prawej stronie...

41

Odp: kompresja - wynik na 1 stronie

M ustawione to plot ale ustawione razem z T to draw (zauwaz, ze draw 'rysuje' tylko w 'pionie' a fill dziala jak draw w poziomie). wartosc pierwszego bajtu dla tego przykladu moze byc: 2,15, 54 itd. akurat w tym przykladzie kolejnosc 'rozkazow' niema znaczenia - bedzie mialo znaczenie ... ale o tym pozniej.

reszta danych? - nie bierzesz pod uwage wartosci P - zwroc tez uwage ze zmienia sie jego interpretacja wraz z T.

dobrze kombinujesz - to bylo moje zadanie przy rekrutacji kolesi na informatykow. wlasciwie to czesc zadania - glownie chodzilo o zerzniecie gry: http://www.jarkey.net/playgames/crabs_game.htm tak sie sklada ze napisalem to w c i kto wie... jak znajdzie sie jakis grafik i muzyk to portne to na atari? chetny jest ktos?

-- dodane

http://atariarea.krap.pl/forum/viewtopi … 795#p50795

Ostatnio edytowany przez xxl (2006-02-15 08:21:23)

http://atari.pl/hsc/ad.php?i=1.

42

Odp: kompresja - wynik na 1 stronie

Dobrze rozumiem ze chodzi o zadanie zadawane kandydatom do pracy informatyka? Czy chodzilo o napisanie takiej gierki? Ciekawy sposob szukania programistow :P

A gierka super!

Ostatnio edytowany przez laoo/ng (2006-02-15 09:25:37)

43

Odp: kompresja - wynik na 1 stronie

Łącząc pomysł Sebana z pomysłem Magnusa i pewnym moim spostrzeżeniem otrzymujemy 78-bajtową prockę dekompresji. Oba obrazki mają po 11 bajtów.

zp   equ $80     ; $18
sreg equ zp+$17  ; 1
inp  equ $98     ; 2

 org $8000
decompr
 lda #$80
 ldx #23
 ldy #0
decompr_byte
 sty zp,x
decompr_bit
 asl @
 bne decompr_next
 lda (inp),y
 inw inp
 rol @
decompr_next
 inc zp,x
 bcs decompr_bit
 dex
 bpl decompr_byte
 ldx #23
draw_byte
 ldy zp,x
 dey
 mva (inp),y sreg
 txa
 pha
 lsr @
 php
 asl @
 plp
 rol @
 asl @
 asl @
 tax
 eor #15
 tay
draw_pixel
 lda sreg
 and #2
 lsr sreg
 adc #$51
 lsr sreg
draw_store1
 sta scr1,x+
draw_store2
 sta scr1,y-
 txa
 and #3
 bne draw_pixel
 pla
 tax
 dex
 bpl draw_byte
 rts

pic1 dta %10010010,%01001100,%10011110,%01110011,%00100100,%10000000,%01010001,%01010101,%01011001,%00010101,%11010101
pic2 dta %11011010,%01001001,%00111100,%10011100,%10010010,%01101100,%01010100,%01010101,%00000000,%01011001,%11111101

main
 mva #$21 $22f
 mwa #dl $230

 mwa #pic1 inp
 mwa #scr1 draw_store1+1
 mwa #scr1 draw_store2+1
 jsr decompr

 mwa #pic2 inp
 mwa #scr2 draw_store1+1
 mwa #scr2 draw_store2+1
 jsr decompr

 jmp *

dl dta $70,$70,$46,a(scr1)
:11 dta 6
 dta $70,$70
:12 dta 6
 dta $41,a(dl)

scr1 org *+192
scr2 org *+192

 run main

 end
https://www.youtube.com/watch?v=jofNR_WkoCE

44

Odp: kompresja - wynik na 1 stronie

rewelacja ....

moglbys spakowac i sprawdzic ile bajtow ma

przyklad5:
aaaaaaaaaaaaaaaa
aaaaaaaaaaaaaaaa
aaaaabbbbbaaaaaa
aaaabaaaaabaaaaa
aaabaababaabaaaa
aaabacaaacabaada
ddabaacccaabaadd
ddaabaaaaabaaada
daaaababbbaaaada
daaaaaaaaaaaaada
daaaaaaaaaaaadaa

moja metoda tu sie calkowicie wyklada : 34 bajty

i taka mala prosba  :-) czy mozna bezczelnie zapierniczyc Twoja procke do rozpakowania plansz w gierce? oczywiscie wymieniajac Cie na liscie plac ?

http://atari.pl/hsc/ad.php?i=1.

45

Odp: kompresja - wynik na 1 stronie

xxl napisał/a:

moja metoda tu sie calkowicie wyklada : 34 bajty

Moja wykłada się jeszcze bardziej. :)

xxl napisał/a:

i taka mala prosba  :-) czy mozna bezczelnie zapierniczyc Twoja procke do rozpakowania plansz w gierce? oczywiscie wymieniajac Cie na liscie plac ?

Bezczelnie zapierniczyc lepiej nie próbuj, ale jeśli grzecznie zapierniczysz, to proszę bardzo. ;)

https://www.youtube.com/watch?v=jofNR_WkoCE

46

Odp: kompresja - wynik na 1 stronie

Wiedzialem, ze jak tytko Fox sie wypowie to wszystkich pozamiata... ;)

A moja metda tez ma 34 bajty. Brzydki przypadek :P