Male pohadka o 16 bitovem neznamenkovem deleni cislem 46 na procesoru Z80.
Bylo nebylo, za sedmero webovyma strankama se na oldcomp.cz resilo deleni cislem 46.
Kdyz se TO (z Lovercrafta) prochazelo ohradou plnou deleni od nejnizsich cisel a divalo se jak se pekne pasou a zkoumalo, zda be nebylo lepsi nejake trosku ostrihat se podivalo na deleni 23 a reklo si: "Hmm, docela pekne, necham to byt".
My se na deleni 23 muzeme take podivat v tomto vypisu, je hned za tema dvema instrukcema co deli dvema. (...za temi dvemi instrukcemi co deli dvemi...? studujte deti, studujte... at mate co zapominat)
Kód:
dworkin@dw-A15:~/Programovani/ZX/Forth/Pasmo_test$ ../check_word.sh '_46UDIV'
; Work in progress... Need to find a better solution.
;[4:16] 46u/ Variant HL/2 = HL >> 1
srl H ; 2:8 46u/
rr L ; 2:8 46u/ HL >>= 1
;# num16bit = 256*hi8bit + lo8bit
;# num16bit = 11*23*hi8bit + 3*hi8bit + lo8bit
;[33:251] 46u/ Variant HL/23 = 11*H+((3*H+L)*11.1289+11)/256
ld B, 0x00 ; 2:7 46u/
ld C, H ; 1:4 46u/ BC = hi8bit
ld A, H ; 1:4 46u/ A = save hi8bit for after
ld H, B ; 1:4 46u/ HL = lo8bit
add HL, BC ; 1:11 46u/ HL = hi8bit+lo8bit
add HL, BC ; 1:11 46u/ HL = 2*hi8bit+lo8bit
add HL, BC ; 1:11 46u/ HL = 3*hi8bit+lo8bit = 0..1020
inc HL ; 1:6 46u/ +11 round up
ld B, H ; 1:4 46u/
ld C, L ; 1:4 46u/ 1x = base
add HL, HL ; 1:11 46u/ 2x
add HL, HL ; 1:11 46u/ 4x
add HL, BC ; 1:11 46u/ 5x
add HL, HL ; 1:11 46u/ 10x
add HL, BC ; 1:11 46u/ 11x
ld B, 0x00 ; 2:7 46u/
ld C, H ; 1:4 46u/
add HL, BC ; 1:11 46u/ 11+11/256
add HL, BC ; 1:11 46u/ 11+11/128
add HL, BC ; 1:11 46u/ 11+11/128+11/256 = 11.1289x = 0..11362
ld C, A ; 1:4 46u/ BC = hi8bit
ld A, H ; 1:4 46u/
ld H, B ; 1:4 46u/
ld L, C ; 1:4 46u/ 1x
add HL, HL ; 1:11 46u/ 2x
add HL, HL ; 1:11 46u/ 4x
add HL, BC ; 1:11 46u/ 5x
add HL, HL ; 1:11 46u/ 10x
add HL, BC ; 1:11 46u/ 11x
ld C, A ; 1:4 46u/
add HL, BC ; 1:11 46u/ 11*hi8bit+0..44
; seconds: 0 ;[37:267]
33 bajtu a 251 taktu. Rozkosne, nemyslite deti?
TO prochazelo dal a postupne se zalibne divalo na deleni a nebo se je pokusilo, tu a tam trosku ostruhnout, aby byla mensi a hbitejsi.
Kupodivu platilo, ze kdyby je ostrihalo prilis, tak uz by moc hbita nebyla... .)
Takze strihalo s mirou deti, zadna krev a ustrihle koncetiny...
Hmm.. to posledni jsem nerekl.
A narazilo na cislo 46.
Deleni 46 vypadalo presne jako predchozi vypis. Bylo stejne jako deleni 23 ale s nahubkem kde bylo deleni dvema.
Vypadalo to celkem nechutne... Osklive... Nevabne...
TO se teda podivalo znovu na deleni 23 a pokusilo se vytvorit jine, ktere by vypadalo s nahubkem deleni dvema chutne... Krasne... Vabne... Vice integrovane...
A TO selhalo... znovu a znovu...
At TO strihalo jak strihalo... nic pekneho z toho nevzeslo... a nebo to bylo pekne, ale uz se to vubec nehybalo...
Tak se TO vratilo k cislu 46 a pokusilo se ostrihat to.
A vzeslo z toho neco jako...
Kód:
dworkin@dw-A15:~/Programovani/ZX/Forth/Pasmo_test$ ../check_word.sh '_46UDIV'
;# n*256/46 >> 8 = 5.565217 >> 8
;# 256*0.565217 = 144.695652
;# 256*0.695652 = 178.086957
;# Variant HL/46 = HL*(256/46)>>8 = HL*5.565217>>8 = HL*(5+(144+178/256)/256)>>8
;[42:262] 46u/ Variant HL/46 = HL*(256/46)>>8 = HL*5.565217>>8 = HL*(5+(144+178/256)/256)>>8
ld B, H ; 1:4 46u/
ld C, L ; 1:4 46u/ 1x base
xor A ; 1:4 46u/
add HL, HL ; 1:11 46u/
inc HL ; 1:6 46u/ rounding constant
adc A, A ; 1:4 46u/ 2x
add HL, HL ; 1:11 46u/
adc A, A ; 1:4 46u/ 4x
add HL, BC ; 1:11 46u/
adc A, 0x00 ; 2:7 46u/ 5x
push HL ; 1:11 46u/
push AF ; 1:11 46u/
add HL, HL ; 1:11 46u/
adc A, A ; 1:4 46u/ 10x
sbc HL, BC ; 2:15 46u/
sbc A, 0x00 ; 2:7 46u/ 9x
add HL, HL ; 1:11 46u/
adc A, A ; 1:4 46u/ 18x
add HL, HL ; 1:11 46u/
adc A, A ; 1:4 46u/ 36x
ld C, A ; 1:4 46u/ 36
add HL, HL ; 1:11 46u/
adc A, A ; 1:4 46u/ 72x
add HL, HL ; 1:11 46u/
adc A, A ; 1:4 46u/ 144
ld B, A ; 1:4 46u/
add A, C ; 1:4 46u/ 144+36=180
add A, H ; 1:4 46u/
ld C, A ; 1:4 46u/
jr nc, $+3 ; 2:7/12 46u/
inc B ; 1:4 46u/ (144+180/256)/256
pop AF ; 1:10 46u/
pop HL ; 1:10 46u/
add HL, BC ; 1:11 46u/ 144.7031/256
adc A, 0x00 ; 2:7 46u/
ld L, H ; 1:4 46u/
ld H, A ; 1:4 46u/ HL*(5+(144+178/256)/256)>>8
; seconds: 1 ;[42:262]
Ale to bylo oproti 37:267 o celych 5 bajtu tucnejsi a jen o 5 taktu rychleji...
A TO melo pravidlo ze jeden bajt je stejny jako 4 takty.
Takze nad tim TO ohrnulo nos a strihalo dal...
Kód:
dworkin@dw-A15:~/Programovani/ZX/Forth/Pasmo_test$ ../check_word.sh '_46UDIV'
;# n*256/46 >> 8 = 5.565217 >> 8
;# 256*0.565217 = 144.695652
;# 256*0.695652 = 178.086957
;# Variant HL/46 = HL*(256/46)>>8 = HL*5.565217>>8 = HL*(5+(144+178/256)/256)>>8
;[41:266] 46u/ Variant HL/46 = HL*(256/46)>>8 = HL*5.565217>>8 = HL*(5+(144+178/256)/256)>>8
ld B, H ; 1:4 46u/
ld C, L ; 1:4 46u/ 1x base
xor A ; 1:4 46u/
add HL, HL ; 1:11 46u/
inc HL ; 1:6 46u/ rounding constant
adc A, A ; 1:4 46u/ 2x
add HL, HL ; 1:11 46u/
adc A, A ; 1:4 46u/ 4x
add HL, BC ; 1:11 46u/
adc A, 0x00 ; 2:7 46u/ 5x
push HL ; 1:11 46u/
push AF ; 1:11 46u/
add HL, HL ; 1:11 46u/
adc A, A ; 1:4 46u/ 10x
sbc HL, BC ; 2:15 46u/
ld B, 0x00 ; 2:7 46u/
sbc A, B ; 1:4 46u/ 9x
add HL, HL ; 1:11 46u/
adc A, A ; 1:4 46u/ 18x
add HL, HL ; 1:11 46u/
adc A, A ; 1:4 46u/ 36x
ld C, A ; 1:4 46u/ 36
add HL, HL ; 1:11 46u/
adc A, A ; 1:4 46u/ 72x
add HL, HL ; 1:11 46u/
adc A, A ; 1:4 46u/ 144
ld L, H ; 1:4 46u/
ld H, A ; 1:4 46u/
add A, C ; 1:4 46u/ 144+36=180
ld C, A ; 1:4 46u/
add HL, BC ; 1:11 46u/
pop AF ; 1:10 46u/
pop BC ; 1:10 46u/
add HL, BC ; 1:11 46u/ 144.7031/256
adc A, 0x00 ; 2:7 46u/
ld L, H ; 1:4 46u/
ld H, A ; 1:4 46u/ HL*(5+(144+178/256)/256)>>8
; seconds: 0 ;[41:266]
Ustihlo jeden bajt za cenu ze zubozene deleni se hybalo o 4 takty pomaleji...
TO usoudilo ze to neni zadna zmena...
A strihalo zarputile dal a dal...
A neustale selhavalo... kdyz ustrihlo nozicku tak se deleni prestavala prekvapive hybat...
Hadejte co deti! Kdyz deleni potrebuje nozicku na hybani, co takhle ustrihnout hlavicku!
Ano deti, ani pak se deleni nehybalo.
TO ze sebe smylo vsechnu krev a nevzdalo se...
Co kdyz ustrihnu od vseho presne 256/257?
Trosku nozicky, trosku hlavicky...
A po mnoha pokusech, kdy TO omylem ustrihlo neco jinak se podarilo!
Vsechny 3 konstanty, kterymi se nasobilo predchozi deleni jako je
5, 144 a 178 se zmenili na
11,22 a 77...
Ktere maji mezi sebou chutny, krasny, vabny pomer.
Kód:
dworkin@dw-A15:~/Programovani/ZX/Forth/Pasmo_test$ ../check_word.sh '_46UDIV'
;# Dont use! Just for test... Suitable for modification for division by the number 46
;# 257*n*(256/(23*257)) >> 8 = 257*n*11.087125697851/256 >> 8
;# 256*0.08712570 = 22.30417865
;# 256*0.30417865 = 77.86973439
;[45:249] 46u/ Variant (HL/2)/23 = (HL/2)*257*65536/(23*257)>>8 = (HL/2)*257*(11+(22+77/256)/256)>>8
ld B, H ; 1:4 46u/
ld C, L ; 1:4 46u/ 2x base
srl B ; 2:8 46u/
rr C ; 2:8 46u/ 1x base
xor A ; 1:4 46u/
add HL, HL ; 1:11 46u/
adc A, A ; 1:4 46u/ 4x
add HL, BC ; 1:11 46u/
adc A, 0x00 ; 2:7 46u/ 5x
add HL, HL ; 1:11 46u/
adc A, A ; 1:4 46u/ 10x
add HL, BC ; 1:11 46u/
adc A, 0x00 ; 2:7 46u/ 11x
push HL ; 1:11 46u/
push AF ; 1:11 46u/
add HL, HL ; 1:11 46u/
adc A, A ; 1:4 46u/ 22x
ld B, A ; 1:4 46u/
rra ; 1:4 46u/ 11
add A, B ; 1:4 46u/ 33
add A, B ; 1:4 46u/ 55
add A, B ; 1:4 46u/ 77
add A, 6 ; 2:7 46u/ rounding constant
add A, H ; 1:4 46u/
ld C, A ; 1:4 46u/
jr nc, $+3 ; 2:7/12 46u/
inc B ; 1:4 46u/
pop AF ; 1:10 46u/
pop HL ; 1:10 46u/
add HL, BC ; 1:11 46u/
adc A, 0x00 ; 2:7 46u/
ld B, A ; 1:4 46u/
ld C, H ; 1:4 46u/
add HL, BC ; 1:11 46u/
adc A, 0x00 ; 2:7 46u/ *257/256
ld L, H ; 1:4 46u/
ld H, A ; 1:4 46u/ (HL/2)*257*(11+(22+77/256)/256)>>8
; seconds: 0 ;[45:249]
Vysledek byl ale stale prilis velky oproti 37 o 8 bajtu.
Ale zrychleni bylo oproti 267 ktere melo deleni 23 s nahubkem deleni dvema uz o 18 taktu...
TO se na to divalo...
Jeste tomu neco chybi, 8 bajtu nahoru a deleni se ma hybat o 32 taktu rychleji...
Takhle to neni uprednostovane reseni...
Nelibil se mu to pouziti zasobniku, ale registr DE melo TO zakazane, protoze by ho muselo obnovit...
Neslo by to nejak...
Tak znovu zacalo strihat a selhavat...
A nakonec mile deti...
V ratolisti krve a odstihlych kousku...
Vzniklo neco...
Co prezilo.
I pres chybejici zasobnik...
A dokazalo se to jeste hybat...
A pekne rychle.
Kód:
dworkin@dw-A15:~/Programovani/ZX/Forth/Pasmo_test$ ../check_word.sh '_46UDIV'
;# 257*n*(256/(23*257)) >> 8 = 257*n*11.087125697851/256 >> 8
;# 256*0.08712570 = 22.30417865
;# 256*0.30417865 = 77.86973439
;[45:224] 46u/ Variant (HL/2)/23 = (HL/2)*257*65536/(23*257)>>8 = (HL/2)*257*(11+(22+77/256)/256)>>8
ld B, H ; 1:4 46u/
ld C, L ; 1:4 46u/ 2x base
srl B ; 2:8 46u/
rr C ; 2:8 46u/ 1x base
xor A ; 1:4 46u/
add HL, HL ; 1:11 46u/
adc A, A ; 1:4 46u/ 4x
add HL, BC ; 1:11 46u/
adc A, 0x00 ; 2:7 46u/ 5x
add HL, HL ; 1:11 46u/
adc A, A ; 1:4 46u/ 10x
add HL, BC ; 1:11 46u/
adc A, 0x00 ; 2:7 46u/ 11x
ld B, A ; 1:4 46u/
ld C, H ; 1:4 46u/ BC = 11/256
add HL, BC ; 1:11 46u/
adc A, 0x00 ; 2:7 46u/ 11+11/256
add HL, BC ; 1:11 46u/
adc A, 0x00 ; 2:7 46u/ 11+22/256
ld B, A ; 1:4 46u/ save A
ld C, H ; 1:4 46u/
add A, A ; 1:4 46u/ 22
add A, A ; 1:4 46u/ 44
add A, A ; 1:4 46u/ 88
sub B ; 1:4 46u/ 77
add A, 9 ; 2:7 46u/ rounding constant
add A, L ; 1:4 46u/
ld L, A ; 1:4 46u/
jr nc, $+3 ; 2:7/12 46u/
inc BC ; 1:6 46u/
ld A, B ; 1:4 46u/ load A
ld H, C ; 1:4 46u/
add HL, BC ; 1:11 46u/
adc A, 0x00 ; 2:7 46u/ *257/256
ld L, H ; 1:4 46u/
ld H, A ; 1:4 46u/ (HL/2)*257*(11+(22+77/256)/256)>>8
; seconds: 0 ;[45:224]
Bylo to stale o 8 bajtu vetsi...
Ale oproti 267 taktum to bylo o 43 taktu rychlejsi... takze celkove to vypadalo vice... chutne...
TO se na to usmalo, protoze jeste nikdy nevidelo takove podivne deleni, ktere bylo jine nez vsechny ostatni, a slo se divat na dalsi deleni.
Mozna ze kdyz vsemu ustrihne zase tu jednu 256/257 a vytrhne zasobnik tak to prezije a bude chutne a hbite...
Dobrou noc deti.
PS: Nejake vysvetleni k poslednimu reseni.
Kód:
ld B, A ; 1:4 46u/ save A
ld C, H ; 1:4 46u/
add A, A ; 1:4 46u/ 22
add A, A ; 1:4 46u/ 44
add A, A ; 1:4 46u/ 88
sub B ; 1:4 46u/ 77
add A, 9 ; 2:7 46u/ rounding constant
add A, L ; 1:4 46u/
ld L, A ; 1:4 46u
jr nc, $+3 ; 2:7/12 46u/
inc BC ; 1:6 46u/
Trik spociva v tom jak si uchovat ten akumulator kdyz drzime v AHL 24 bitove cislo a pricitame k tomu 8 bitove.
A to 8 bitove musime nejak slozite vytvorit pomoci A.
Udelal jsem to tak ze jsem do BC dal kopii AHL/256.
Tim jsem si uvolnil A. (a zbytecne ukladal i H?)
Vytvoril jsem to 8 bitove cislo (nasobek 7)
Pricetl jsem ho pomoci A do L.
A ted prijde ten trik...
Diky tomu ze v BC lezi AHL/256 tak preteceni v carry mohu vyresit jako proste BC+1. Takze i v B (puvodne A bude spravna hodnota).
Takze kdyz to nakopiruji zpet do AH, tak v AHL mam AHL+8 bitova hodnota.
A to neni vse, za tim nasleduje nasobeni 257.
To se provede jako soucet AHL + AHL/256.
No a my uz vlastne mame v BC to AHL/256!
Chtel bych vedet kolik veci me stale unika a jde udelat lepe.
PPS:
Kód:
ld B, A ; 1:4 46u/
ld C, H ; 1:4 46u/ BC = 11/256
add HL, BC ; 1:11 46u/
adc A, 0x00 ; 2:7 46u/ 11+11/256
add HL, BC ; 1:11 46u/
adc A, 0x00 ; 2:7 46u/ 11+22/256
Tohle by slo resit jeste o 2 takty rychleji, ale za cenu bajtu navic, kdyz vynasobim to BC dvema pres posuny.
Usetrim jedno pricitani 3:18 za cenu 4:16.
PPPS: Bylo to moc krvave?