1

czyli małe code compo :)

poniższa procedura dekompresujaca RLE zajmuje 56 bajtów, uważam że krócej już nie można (nie chodzi o szybkość), ktoś jest innego zdania, czy moge już ogłosić sie mastahem ;)

dane ktory dekompresujemy skladaja sie z bajtow, a poszczegolne bity oznaczaja:  bit7 = 0 oznacza dane nieskompresowane, pozostale bity (0..6) to liczba nieskompresowanych elementow +1 ktore wystepuja zaraz po tym bajcie, bit7 = 1 oznacza dane powtarzajace sie, bity 0..6 to liczba powtorzen +1 nastepnego bajtu

czyli cos w stylu Koali, proste jak drut


loop
 jsr _src
 cmp #0
 bpl _stored

_rle
 cmp #$ff
 beq stop

 ldy #($100-(_bpl-_lp1+2))&$FF
 sty _bpl+1


_stored
 and #$7f
 tay

_lp0
 jsr _src

_lp1

_dst sta $FFFF
 inw _dst+1

 dey

_bpl
 bpl _lp0

 ldy #($100-(_bpl-_lp0+2))&$FF
 sty _bpl+1
 jmp loop

 
_src lda $FFFF
 inw _src+1 

stop
 rts
*- TeBe/Madteam
3x Atari 130XE, SDX, CPU 65816, 2x VBXE, 2x IDE Plus rev. C

2 Ostatnio edytowany przez Magnus (2005-08-03 02:29:26)

Obniżam adres danych źródłowych o jeden bajt, wycinam, zmieniam, zamieniam...

loop
 ldx #($100-(_bpl-_lp0+2))&$FF

 jsr _src
 bpl _stored

_rle
 cmp #$ff
 beq stop

 and #$7f

 ldx #($100-(_bpl-_lp1+2))&$FF

_stored
 tay

 stx _bpl+1


_lp0
 jsr _src

_lp1

_dst sta $FFFF
 inw _dst+1

 dey

_bpl
 bpl _lp0
 bmi loop

 
_src
 inw _get+1
_get
 lda $FFFF

stop
 rts

... i o ile się nie mylę to zjechałem do 50 :)

3

uu... tebe, starzejesz się! ;) :lol:

I Ty zostaniesz big endianem...

4

gratuluje Magnus, zmienilbym tylko

bmi loop

na mało używany rozkaz

bvc loop

zawsze to krócej aniżeli 'jmp loop'

teraz rozpakowywuje bezbłędnie, no i rzeczywiście po optymalizacji Magnusa zajmuje procedurka tylko 50 bajtów

w takim razie nie bede oglaszal sie mastahem ;)

*- TeBe/Madteam
3x Atari 130XE, SDX, CPU 65816, 2x VBXE, 2x IDE Plus rev. C

5

szanowny tebe umie sprowokowac :)

6

Nie przypominam sobie, aby w liście rozkazów 6502 widniał rozkaz: inw :P

7

hej!

To może i ja swoje 3 grosze dorzucę  :) Pierwsze założenie optymalizacyjne, odwracamy znak w przypadku ilości spakowanych danych, czyli w przypadku ustawionego 7 bitu, wartość $ff będzie oznaczała 1 powtórzenie, $fe - dwa powtórzenia $80 - 127 powtórzeń. Przez taki myk możemy wprowadzić co następuje:

jsr get
bpl store
xor #$ff 
beq stop
...
tay

nie potrzebujemy już and #$7f ;) mamy już 48 bajtów

pierwszym moim pomysłem było zastosowanie nieco innych trybów adresowania i umieszczenie tego na stronie zerowej:

       org     $80

src     dta a(src_address)
dst     dta a(dst_address)

loop    ldx #($100-(_bpl-q0+2))&$ff
        jsr get
        ora #$00
        bpl store
        xor #$ff
        beq stop
        ldx #($100-(_bpl-q1+2))&$ff

store   tay
        stx _bpl+1

q0      jsr get
q1      ldx #dst
        sta ($00,x)
        jsr inc
        dey
_bpl    bpl *

        bvc loop

get     ldx #src
        lda ($00,x)
inc     inc ($00,x)
        bne *+2
        inc ($01,x)

stop    rts

wychodzi 49 bajtów, co okazało się porażką ponieważ kod wygenerowany wcześniej przez magnusa ma 45 bajtów gdy umieścimy go na "zero page". no cóż pozostaje wiec pozostawienie wersji magnusa wraz z modyfikacją "xor" i mamy 43 bajty na zero page lub 48 bajtów w "normalnej" pamięci.

        org     $80

loop    ldx #($100-(_bpl-q0+2))&$ff
        jsr get
        bpl store
        xor #$ff
        beq stop
        ldx #($100-(_bpl-q1+2))&$ff

store   tay
        stx _bpl+1

q0      jsr get
q1      sta $dead
        inc q1+1
        bne *+2
        inc q1+2

        dey
_bpl    bpl *

        bvc loop

get     inc adr+1
        bne *+2
        inc adr+2

adr   lda $cafe

stop    rts

pozdrowionka
Seban/SLIGHT

8 Ostatnio edytowany przez pr0be (2005-08-03 11:48:05)

zmieniamy

        ldx #($100-(_bpl-q0+2))&$ff
        jsr get
        bpl store
        xor #$ff
        beq stop
        ldx #($100-(_bpl-q1+2))&$ff

store   tay
          stx _bpl+1

na

        ldy #($100-(_bpl-q0+2))&$ff
        jsr get
        bpl store
        eor #$ff
        beq stop
        ldy #($100-(_bpl-q1+2))&$ff

store   
          sty _bpl+1
          tay

dzieki czemu mamy rejestr X wolny, i mozemy zmienic procke GET na taka:

get    inx
        bne *+5
        inc adr+2

adr   lda $cafe,x

i mamy 2 bajty do przodu, czyli 46 bajtow w "normalnej" pamieci lub 42 na "zero page", do tego procka jest o 3 cykl na bajt szybsza ;)

cala procka wyglada tak:

loop    ldy #($100-(_bpl-q0+2))&$ff
        jsr get
        bpl store
        eor #$ff
        beq stop
        ldy #($100-(_bpl-q1+2))&$ff

store   sty _bpl+1
    tay

q0      jsr get
q1      sta $dead
        inc q1+1
        bne *+5
        inc q1+2

        dey
_bpl    bpl *

        bvc loop

get     inx
        bne *+5
        inc adr+2

adr   lda $cafe,x

stop    rts

9 Ostatnio edytowany przez marok (2005-08-03 13:10:54)

Punktem wyjscia jest dla mnie procka Pr0be. Nie wiem, czy to dziala, ale mysle, ze powinno.
Dodatkowo zmodyfikowalem zalozenia odnosnie sposobu pakowania (o ile to dozwolone):
teraz najmlodszy bit (0) sygnalizuje, czy nastepujace bajty sa spakowane;
teraz tez zgaszeny bit "sygnalizacyjny" oznacza spakowane, zapalony nie.

loop    jsr get
        beq stop
    lsr @

    tay
q0      jsr get
q1      sta $dead
        inc q1+1
        bne *+5
        inc q1+2

        dey
_bpl    bmi loop
    bcs q0
    bcc q1 !


get     inx
        bne *+5
        inc adr+2

adr   lda $cafe,x

stop    rts

10 Ostatnio edytowany przez seban (2005-08-03 13:52:31)

ha!

Marok byłeś pierwszy... ale miałem podobny pomysł pomysł :D

bez modyfikacji spakowanych danych wyszło mi tak:

          org      $80

loop     clc
         jsr     get
         bpl     store
         eor     #$ff
         beq     stop
         sec
store    tay

q0       jsr     get
q1       sta     $dead

         inc     q1+1
         bne     *+4
         inc     q1+2

         dey
         bmi     loop

         bcc     q0
         bcs     q1         ; (!) jump always ;)

get      inx
         bne     *+4
         inc     adr+2

adr      lda     $beef

stop     rts

czyli o ile dobrze licze wychodzi 43 bajty poza "zero page", a 40 na "zero page" :D

ale w porównaniu z 33 bajtami Maroka, mogę się schować :D

a i jeszcze jedno na początku wersji zaproponowanej przez Probe z inx,inc powinniśmy mieć wszyscy LDX #0 :) wiec dochodzą nam dwa bajty :(


Seban/SLIGHT

11

seban napisał/a:

ha!
a i jeszcze jedno na początku wersji zaproponowanej przez Probe z inx,inc powinniśmy mieć wszyscy LDX #0 :) wiec dochodzą nam dwa bajty :(

zalezy jak na to patrzec ;)
jesli ma byc to procka do depakowania tylko 1 segmentu danych to tak, jesli np. tych segmentow danych jest wiecej, jest wrecz przeciwnie LDX #<dane zajmuje 2 bajty, a LDA #<dane sta _src+1 az 5 ;)

tak czy inaczej jesli procka Marok'a naprawde dziala to Respect dla niego! ;)

12

heja!

może się źle wyraziłem... dokładnie chodziło mi o to iż tak czy tak musi być jakiś LDX # :D nawet w wersji maroka ;)

Seban

13

No tak! TeBe chcial, zeby ktos mu zoptymalizowal kod, sprowokowal wszystkich, ze krocej sie nie da i natychmiast dostal kod o polowe krotszy... kurcze jak bede cos potrzebowal tez bede musial podrzucic  jakis kod a madre chlopaki z aa mi go rozpykaja :D

14

laoo dobrze kombinujesz :D

*- TeBe/Madteam
3x Atari 130XE, SDX, CPU 65816, 2x VBXE, 2x IDE Plus rev. C

15

przeciez ta prowokacja od razu byla widoczna ;)

ale z drugiej strony - zawsze to mozliwosc do pokazania sie, a i teoretyczna
mozliwosc otrzymania poczta nagrody przez z wyciezce w postaci zgrzewki
byx or somfing...

btw. poczekajcie a moze fox sie odezwie i wszystkich wykosi ;)

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

16

kto wie, ale pewnie Fox ma wieksze problemy do rozwiazania, teraz jednak przetestuje sposob maroka, jesli bedzie dzialac ... umieszcze go w creditsach do Getris'a, albo inna osobe ktora zwyciezy ten mini konkurs :)

*- TeBe/Madteam
3x Atari 130XE, SDX, CPU 65816, 2x VBXE, 2x IDE Plus rev. C

17

Nareszcie ktoś wskrzesił ducha współzawodnictwa w optymalizacji kodu :-) Jak za dawnych lat....
A swoją drogą może by tak popracować wspólnie nad innymi procedurkami i zrobić z tego demko?

18 Ostatnio edytowany przez tebe (2005-08-03 19:49:35)

oto owoc tutejszego współzawodnictwa http://g2f.atari8.info/rle_encoder.zip

kod Maroka liczy 40 bajtów (po zmianie sposobu zapisu spakowanych danych), no i możeciu mu mówić "drogi mastahu Maroku" :)

został wykorzystany w Getris'ie do rozpakowywania danych PMG (dane te zajmują po $500 bajtów), w których to aż roi się od powtarzających fragmentów

deflater Fox'a jest wydajniejszy jednak kod jego depackera i bufory zajmuja prawie $500 bajtów, tak że RLE jest ponad 50% bardziej opłacalny w moim przypadku :)

*- TeBe/Madteam
3x Atari 130XE, SDX, CPU 65816, 2x VBXE, 2x IDE Plus rev. C

19 Ostatnio edytowany przez marok (2005-08-03 20:18:45)

umieszcze go w creditsach do Getris'a, albo inna osobe ktora zwyciezy ten mini konkurs

Bardzo sympatyczna perspektywa, ale z drugiej strony moj wklad w ostateczna postac tej procedury, ktora zamiescilem w swoim poscie, jest jednak znikomy. W sumie wykorzystalem tylko walor znacznika C w przechowywaniu istotnej informacji. Nie jest to doprawdy osiagniecie godne szczegolnego podkreslania. Byloby to nawet przesada wg. mnie. Tak wiec mimo milej propozycji, wolalbym poczekac z umieszczenia swojej ksywy pod jakas produkcja do sytuacji wiekszego wkladu wen. Poza tym kazdy dorzucal cos od siebie, a wiadomo, ze osoba ostatnia jest w sytuacji szczegolnie uprzywulowanej, znajac tresc kodu poprzednikow. Ten konkurs z zalozenia nie byl fair. ;) Ale ciesze sie, ze sie paru osobom "pokazalem".

Dodane. TeBe:

 mwa #source-1 adr+1
 mwa #destination q1+1
 jsr depacker
 rts
...
adr     lda $ffff,x

mam jeszcze taka uwage, ze mozna to skrocic zastepujac te czesci kodu tym:

 lda >source-1
 sta adr+2
 ldx <source-1

 mwa #destination q1+1
 jmp depacker
...
adr     lda $ff00,x:

No i bez LDA #0 na poczatku procedury jeszcze.

20

:) nie boj sie Marok, wszystkich skredytowalem z RLE Encoderze, w okienku 'Depacker'

no i wszystkim, którzy wzięli udział w optymalizacji dziękuję, że zechcieli wziąć w niej udział, w końcu każdemu może się przydać taka "pchełka"

jakby to był Microsoft, już byłby pewnie patent ;)

*- TeBe/Madteam
3x Atari 130XE, SDX, CPU 65816, 2x VBXE, 2x IDE Plus rev. C

21

Zaproponuję jeszcze jedną poprawkę: skoro to depaker, to rejestru X użyłbym do adresowania pamięci przy zapisywaniu danych.

22

deflater Fox'a jest wydajniejszy jednak kod jego depackera i bufory zajmuja prawie $500 bajtów, tak że RLE jest ponad 50% bardziej opłacalny w moim przypadku

Zapomniales TeBe o Flashpackerze Fox'a. Packer ten potrafi pakowac takze bardzo wydajnie ciagi bajtow powtarzajace sie, a poza tym pakuje wg. powtorzen ciagow (chyba nazywa sie to fachowo slownikowo) rozpatrujac poprzednie 127 bajtow. Ale przyznaje, ze w tej chwili nie pamietam dokladnie jego cech.
W kazdym razie wydaje mi sie, ze moze sie okazac nawet znaczaco wydajniejszy niz ten, a kod procki rozpakowujacej jest tez bardzo krotki. Warto sprawdzic.

23

No prosze ... Jaki ten Tebeliusz się słodki zrobił ... ;))))))

Im dłużej czekamy, tym wzorek jest większy" (c) by Sikor

24

zaraz przyjdzie konop i zrobi Wam z dupy jesien sredniowiecza ... albo spali komisariat ;)

25 Ostatnio edytowany przez Marek Konopka (2005-08-04 17:16:13)

Dopisuję się do ostatniej wersji...

Dosyć oczywista optymalizacja - zamiana rejestrów X z Y oraz zmiana adresacji z absolutnej na pośrednią postindeksowaną na stronie zerowej:

loop  jsr get
        beq stop
        lsr @
        tax
q0    jsr get
q1    sta $dead
        inc q1+1
        bne *+5
        inc q1+2

        dex
_bpl  bmi loop
        bcs q0
        bcc q1

get   iny
       bne *+4
       inc src+1
       lda (src),y
stop rts

Zysk 2 bajtów przy wariancie na stronie zerowej oraz 1 przy poza.

To nie było moje ostatnie słowo...

Jest jeszcze bardziej pociśnięta wersja, ale ostrzegam, że jest to już HARDCORE:

loop    brk
         nop
        tax
        beq exit
        lsr @
        tax
q0     brk
        nop
q1     sta $dead
        inc q1+1
        bne *+5
        inc q1+2

        dex
_bpl   bmi loop
        bcs q0
        bcc q1 !

get    iny
        bne *+4
        inc adr+1
        lda (src),y
    rti

Trzeba się tylko "upewnić", że pod $fffe są odpowiednie wartości oraz zezwolić na przerwania niemaskowalne ($d20e ???), ale to raczej nie problem. Zysk jest 1 bajtowy. Exit oznacza adres powrotu, a procedure wywołujemy przez jmp loop.

35 bajtów poza stroną zerową, 33 na zerowej.