Unsigned deleni pomoci 1 az 256 bajtovych cisel pres pointery je hotove. Aspon prvni iterace.
Zacal jsem jednim bajtem, takze jsem pouzil neco napul mezi pointery a nactenim do registru. To me moc nepomohlo.
Takze jsem pokracoval dvoubajtovym cislem a schvalne se snazil vse drzet v pameti, abych mel lepsi predstavu co musim udelat u vetsich cisel.
A pak zacala bolest... .)
Orezal jsem ten algoritmus uplne na nejprimitivnejsi zaklad, zadne rychlostni optimilizace i tak to byla vyzva.
Prvne jsem resil 256 bajtovou variantu, protoze je nejsnazsi a nemu se drzet v pameti moc hodnot.
Pak resil obecnou variantu 3..255 bajtu.
Pri testovani jsem zjistil, ze me vubec nedoslo ze to pocitadlo o kolik bitu jsem posunul delitele vlevo se mi fakt nevleze do registru B.
Takze jsem to rozdelil na 3..32 a 33..255 varianty.
A prepisoval a prepisoval a resil neustale chyby, jak jsem zapomnel ze zrovna tady mam tuhle zavislost a nebo cekam ze carry bude zrovna nula. Nakonec se mi podarilo neco sesmolit co nebylo na prvni pohled az tak strasne.
Jenze to bylo "inline" a ja to potreboval jako funkci. Coz znamenalo ze jsem to musel prepsat zase znovu, protoze uz jsem nemohl pouzit pro inicializaci smycek neco jako
ld B, 23
kdyz delim 23 bajtove hodnoty, ale 23 musel byt parametr.
Takze dalsi kolecko prepisovani a vytvareni a opravovani novych chyb. Nakonec se ukazalo ze varianta 3..32 je ted temer totozna jako 33..255. Dokonce presneji ta posledni varianta je napsana rovnou tak aby, zvladla 1..256 bajtove hodnoty.
Takze mam 4 funkce a zobrazi se v runtime jen jedna podle toho co pouzijete v kodu. Zavedl jsem 2 nove promenne do M4.
PUDM_MIN
PUDM_MAX
a do tech se pri tokenizaci nacita co bylo pouzito.
Pokud obe ukazuji 1 tak runtine knihovna ma jen verzi pro deleni jednobajtovych hodnot.
Pokud obe ukazuji 2 tak runtine knihovna ma jen verzi pro deleni dvoubajtovych hodnot.
Pokud obe ukazuji 256 tak runtine knihovna ma jen verzi pro deleni 256 bajtovych hodnot.
Pokud obe ukazuji mene nez 32 tak runtine knihovna ma jen verzi pro deleni pri 8 bitovem citaci posunu.
Cokoliv jineho udela tu univerzalni rutinu.
Pri tom deleni potrebuji tri pointery. Protoze ten algoritmus potrebuje drzet v pameti tri.
Jeden je cislo co se deli a ktere se postupne meni ve zbytek po deleni jak se od nej odcita ruzne posunuty delitel.
Dalsi je ten delitel, ten se na konci vrati na puvodni hodnotu.
A posledni je vysledek.
Vysledek jsem umistil do TOS(HL), protoze to vetsinou ocekavate ze nejaka operace udela.
Zbytek po deleni a vlastne delene cislo je v NOS(DE).
Cim delite je jeste predtim v NNOS((SP)).
Je to trosku proti logice Forthu, kdy kdyz odcitate nebo delite tak je to
NOS TOS / --> NOS/TOS
NOS TOS - --> NOS-TOS
a ted jsou NOS a NNOS to prohozene
NNOS NOS TOS --> NNOS NOS%NNOS NOS/NNOS
Ale v algoritmu provedu swap NNOS a TOS a mam nejdulezitejsi pameti v registrech. S vysledkem uz neni tolik prace a pracuje se s nim samostante. U odcitani naopak musim mit jak delitele tak delence v registrech.
Dalsi vyhoda je ze jde rychle udelat postupne deleni.
Vemte si situaci ze mate 256 bajtove cislo a chcete ho vypsat decimalne.
Do zasobniku date
ukazatel_na_hodnotu_10 ukazatel_co_tisknete_X ukazatel_na_vysledek
Zavolate deleni a mate ve vysledku cislo 0..9 a tisknute cislo je 10x mensi.
Pokracujete tak dlouho dokud je zbytek po deleni nenulovy, desitka vam zustane a pointery jsou stale spravne nastaveny.
To je podle me pekne, jedina chybka bude, ze si asi muzete u 256 bajtoveho cisla postavit na kafe. .)
Jeste ukazi kod pro univerzalni rutinu. Popisek je vzdy pod kodem.
Kód:
dworkin@dw-A15:~/Programovani/ZX/Forth/Nova_testovaci$ ../check_word.sh 'PUDIVMOD(1) PUDIVMOD(200)'
pop BC ; 1:10 p8u/mod
ld A, 0x01 ; 2:7 p8u/mod
call PUDM ; 3:17 p8u/mod
push BC ; 1:11 p8u/mod
pop BC ; 1:10 p1600u/mod
ld A, 0xC8 ; 2:7 p1600u/mod
call PUDM ; 3:17 p1600u/mod
push BC ; 1:11 p1600u/mod
Takhle vypada volani, nechtelo se me resit problemy s tretim parametrem a ze se schova za navratovou hodnotu takze jsem zvolil rychlejsi reseni, ale delsi na volani, protoze se treti parametr nacte do BC a v rutine hned vrati zpet.
Kód:
;==============================================================================
; Divide 8..2048-bit unsigned value from pointer
; In: [BC], [DE], [HL]
; A = sizeof(number) in bytes
; Out: [HL] = [DE] / [BC], [DE] = [DE] % [BC]
PUDM: ; pudm
push BC ; 1:11 pudm
ld C, A ; 1:4 pudm C = x bytes
akumulator protrebuji, takze odted drzim sizeof(number) v registru C a je neustale nacitan na zacatku smycek do B. Takze nemam volny registr. Jen A, ve kterem budu za chvili potrebovat nejaky cas nulu.
Kód:
xor A ; 1:4 pudm
exx ; 1:4 pudm
ld B, A ; 1:4 pudm
ld C, A ; 1:4 pudm BC' = shift_counter = 0
exx ; 1:4 pudm
Pocitadlo posunu delitele je teda ve stinovem BC
Kód:
ld B, C ; 1:4 pudm
ld (HL),A ; 1:7 pudm
inc L ; 1:4 pudm px_res = 0
djnz $-2 ; 2:8/13 pudm
ex AF, AF' ; 1:4 pudm
ld A, L ; 1:4 pudm
sub C ; 1:4 pudm
ld L, A ; 1:4 pudm return to original value
Vynulovani vysledku. Vsimnete si ze abych vratil ukazatel na puvodni hodnotu tak ho musim odecist. Pokud by to cislo koncilo presne na predelu segmentu tak nastane carry. To se stane vzdy u 256 bajtovych hodnot. V teto variante kodu to ale nevadi. Pouziti pro uchovani zasobnik by usetrilo jeden bajt a bylo o 11+10-12 = 9 taktu pomalejsi. Hmm... vlastne jen o 5 protoze musim pouzit EX. To bych mel zmenit protoze je to o 2 bajty kratsi a jen 5 taktu pomalejsi, to uz prevazuje muj prevod 1 bajt = 4 takty. Ale zase je to rutina a bude volana asi vickrat jak jednou...
Kód:
ex (SP),HL ; 1:19 pudm
Vysledek je inicializovan a odted potrebuji v HL delitele.
Kód:
ld A, L ; 1:4 pudm A' = original value L
ex AF, AF' ; 1:4 pudm
Nove v stinovem A drzim puvodni offset delitele. Tenhle trik me taky bolel, protoze nesmite nikdy zapomenout ze prohazujete i F. V A je opet nula.
Kód:
ld B, C ; 1:4 pudm
or (HL) ; 1:7 pudm
inc L ; 1:4 pudm
djnz $-2 ; 2:8/13 pudm px_3 == 0?
or A ; 1:4 pudm
jr z, PUDM_EXIT ; 2:7/12 pudm exit with div 0
Test zda delitel neni nula. Dulezity test, protoze nasledujici cast posouva delitele tak dlouho dokud nepretece.
Kód:
ex AF, AF' ; 1:4 pudm
ld L, A ; 1:4 pudm return to original value
ex AF, AF' ; 1:4 pudm
ld B, C ; 1:4 pudm
exx ; 1:4 pudm
inc BC ; 1:6 pudm shift_counter++
exx ; 1:4 pudm
rl (HL) ; 2:15 pudm
inc L ; 1:4 pudm
djnz $-3 ; 2:8/13 pudm px_3 *= 2
jr nc, $-12 ; 2:7/12 pudm px_3 overflow?
Je to slozeno ze svou smycek. Vnitrni posouva delitele a vnejsi nastavuje spravne parametry pro vnitrni. Vraci zpet L a zveda pocitadlo HL'. Na konci je vzdy carry a L ukazuje ZA KONEC. Protoze pri posunu doprava se musi zacit od konce.
Kód:
PUDM_LOOP: ; pudm
ld B, C ; 1:4 pudm L = orig L + $1
dec L ; 1:4 pudm
rr (HL) ; 2:15 pudm
djnz $-3 ; 2:8/13 pudm px_3 >>= 1
Hlavni smycka. Posun o bit doprava. Poprve nacte carry, v dalsich krocich musim zajistit aby bylo carry vynulovano.
Kód:
ex (SP),HL ; 1:19 pudm
ld A, L ; 1:4 pudm
ld B, C ; 1:4 pudm
rl (HL) ; 2:15 pudm
inc L ; 1:4 pudm
djnz $-3 ; 2:8/13 pudm result *= 2
ld L, A ; 1:4 pudm return to original value
ex (SP),HL ; 1:19 pudm
Nasobeni vysledku dvema. Tady je volny A, takze jde pouzit pro uchovani puvodniho offsetu.
Kód:
push DE ; 1:11 pudm
ld B, C ; 1:4 pudm
ld A,(DE) ; 1:7 pudm
sbc A,(HL) ; 1:7 pudm
inc L ; 1:4 pudm
inc E ; 1:4 pudm
djnz $-4 ; 2:8/13 pudm (px_mod < px_3)?
pop DE ; 1:10 pudm
Takove CP nad pointery. Pokud budu vychazet z predpokladu ze vysledek ma pravdepodobne stejny poctet jednickovych bitu jako nulovych tak je to stale rychlejsi jako odcitani natvrdo a pricitani zpet pri nulovem bitu. Usetrim stale jeden "ld (DE),A". Je dulezite ze na konci ukazuje L na konec, je to pripraveno pro dalsi krok smycky.
Kód:
jr c, PUDM_NEXT ; 2:7/12 pudm
Pokud je vysledek carry tak nemuzeme odecist posunuteho delitele, protoze je vetsi jak zbytek.
Kód:
ex (SP),HL ; 1:19 pudm
inc (HL) ; 1:11 pudm result += 1
ex (SP),HL ; 1:19 pudm
Pridani jednickoveho bitu k vysledku. Postupne se to nasobi dvema jak bylo videt vysse.
Kód:
push DE ; 1:11 pudm
ex AF, AF' ; 1:4 pudm
ld L, A ; 1:4 pudm return to original value
ex AF, AF' ; 1:4 pudm
Musime vratit offset na zacatek.
Kód:
ld B, C ; 1:4 pudm
ld A,(DE) ; 1:7 pudm
sbc A,(HL) ; 1:7 pudm
ld (DE),A ; 1:7 pudm
inc L ; 1:4 pudm
inc E ; 1:4 pudm
djnz $-5 ; 2:8/13 pudm px_mod -= px_3
pop DE ; 1:10 pudm
Zase mame offset na konci.
Kód:
PUDM_NEXT: ; pudm
exx ; 1:4 pudm
dec BC ; 1:6 pudm
ld A, B ; 1:4 pudm
or C ; 1:4 pudm
exx ; 1:4 pudm
jr nz, PUDM_LOOP ; 2:7/12 pudm
Vynulovani carry! A djnz nad 16 bitovym BC'.
Kód:
PUDM_EXIT: ; pudm
ex AF, AF' ; 1:4 pudm
ld L, A ; 1:4 pudm return to original value
ex (SP),HL ; 1:19 pudm
pop BC ; 1:10 pudm
ret ; 1:10 pudm
;[110:658]
Vraceni offsetu delitele. I ve variante ze je sem skoceno kdyz je delitel nulovy. Tohle jsem netestoval hmm...
A prohozeni delitele za vysledek v zasobniku a vyzvednuti do BC, aby se mohla pouzit navratova hodnota.
PS: V podstate je to takova primitivni rutina a ja to smolim nekolik dni, vcetne testovani, proc me to sakra zase nefunguje.
PPS: Zrychleni by slo udelat tim, ze by se jeste pote co se zkontroluje ze delitel je nenulovy tak od konce zjistovat zda delenec i delitel nema nejvyssi bajty nulove a pokud ano tak postupne snizovat hodnotu C, ktery drzi velikost tech cisel. Pokud by bylo na zacatku hodne nul tak to algoritmus hodne zrychli, jinak o trochu zpomali.
PPPS: Dalsi reseni by bylo mit jeste funkci pro to kdyz pouzivame sudy pocet pro velikost cisel. Tak by slo mit smycky s polovicnim citacem, ale za to uvnitre vse dvakrat. Vydelilo by to cenu skoku na polovinu. Ale moc extra by to nepomohlo. Takova cena pro jedno CP je 22 taktu plus 13 za kazdy skok. Takze z 35 taktu za bajt by to bylo neco jako (44+13)/2 = 28.5 taktu na bajt.
PPPPS: Dost jsem se strilel do nohy, protoze jsem mel misto labelu neco jako $+18 a jak ten kod hodne editujete tak... .)