Vlákno názorů k článku Specifika instrukční sady mikroprocesorů Intel 8086/8088 (2) od Ondřej Novák - Dodneska mne líbí, jak překladače realizují dělení konstantou...
-
Dodneska mne líbí, jak překladače realizují dělení konstantou pomocí instrukce násobení, protože dělení trvá déle
Třeba dělení deseti se řeší násobením čísla 6554 v 16bit systému
MOV AX,0x78 ;=120
IMUL 0x199A
DX=0x0C ;=12Na 386 se LEA se dala použít na násobení o různé konstanty
LEA AX,[AX+AX*2] - násobení 3x - pro RGB data .
-
Pavel TišnovskýZlatý podporovateljj LEA se na 386 (ale ne dřív) stala velmi užitečnou instrukcí (která vlastně byla použitelná na všechno možný, nejenom na loading adresy). Na 8086 ale byly možnosti omezené std.adresováním (jak jsme si ukázali minule).
-
Vymenit deleni za nasobeni neni az tak trivialni jak muze vypadat.
Vetsinou ti podminky umozni to nasobit s dvojnasobnou sirkou.
A na konci to nekdy musis posouvat o par bitu doprava.
Vse kvuli zaokrouhleni.
Nedavno jsem cetl nejaky par let stary clanek, ktery ukazoval, ze ani nejlepsi prekladace nenajdou vzdy nejlepsi reseni. A vysvetloval nejake podminky, za kterych to jde udelat lepe.
Pisi jako hobby projekt prekladac pro Z80 a deleni konstanotou je... PEKLO. Vetsina veci kde se objevi konstanta je tezka, ale deleni je extrem. I modulo je lehci i kdyz jsem dlouho nevedel ze to jde delat bez deleni.
Metod na ktere jsem prisel jak udelat deleni je nekolik a kazda ma svoje podvarianty a ty nikdy nevis, ktery kod pujde nejlepe optimalizovat a bude nakonec nejlepsi.Nasobit 6554? 16x16=32 bit...
To je zbytecne slozite (pokud procesor neumi nasobit).
U deleni 10 me nejlepe vychazi pouzit deleni 5. Protoze delit deseti je to same co "delit"dvema a pak deseti. Nebo naopak. Ale prvni se lepe optimalizuje, protoze mas uz zadarmo nasobek 2. Ktery vyuzijes protoze to prevadis na to nasobeni.
Deleni 5 se dela pres nasobeni 13107, ale drzi se to v 16x16=24 bit protoze se pouziva trik, ze ti staci to nasobit 51.
Osetrit zaokrouhleni.
A pak to vynasobit 257! 51*257=13107
A nasobeni 257 je brnkacka... protoze v ramci toho neustale to drzet na co nejmensim poctu bitu se to dela jako
(N*257)>>8
Takze ti staci hornich 8 bitu dat do spodnich a secist s puvodni hodnotou.A ted si vem ze najit tohle pro kazde cislo je dost prace... a stejne nevis zda to nejde lepe... i kdyz to delas rucne.
dworkin@dw-A15:~/repositories/M4_FORTH$ ./check_word.sh 'PUSH(10) UDIV' ;[32:185] 10 u/ Variant HL/10 = (HL/2)*(65536/5)/65536 = (HL/2)*51*257/65536 ld B, H ; 1:4 10 u/ ld C, L ; 1:4 10 u/ srl B ; 2:8 10 u/ rr C ; 2:8 10 u/ 1x base xor A ; 1:4 10 u/ inc BC ; 1:6 10 u/ +19 rounding constant add HL, BC ; 1:11 10 u/ adc A, A ; 1:4 10 u/ 3x AHL add HL, HL ; 1:11 10 u/ inc HL ; 1:6 10 u/ +8 rounding constant adc A, A ; 1:4 10 u/ 6x AHL add HL, HL ; 1:11 10 u/ adc A, A ; 1:4 10 u/ 12x AHL add HL, HL ; 1:11 10 u/ adc A, A ; 1:4 10 u/ 24x AHL add HL, BC ; 1:11 10 u/ adc A, 0x00 ; 2:7 10 u/ 25x AHL add HL, HL ; 1:11 10 u/ adc A, A ; 1:4 10 u/ 50x AHL add HL, BC ; 1:11 10 u/ adc A, 0x00 ; 2:7 10 u/ 51x AHL with rounding constant 26..35 ld B, A ; 1:4 10 u/ (AHL * 257) >> 16 = (AHL0 + 0AHL) >> 16 = AH.L0 + A.HL = A0 + H.L + A.H ld C, H ; 1:4 10 u/ BC = "A.H" add HL, BC ; 1:11 10 u/ HL = "H.L" + "A.H" ld L, H ; 1:4 10 u/ adc A, 0x00 ; 2:7 10 u/ + carry ld H, A ; 1:4 10 u/ HL/10 = (HL/2)*(65536/5)/65536 = (HL/2)*(1+256)*51 >> 16 ; seconds: 0 ;[32:185]Sorry, Z80 je trosku offtopic. .)
-
Nekde na netu jsem kdysi narazil na Pythoni script, ktery po zadani delitele projel definovany rozsah multiplikativnich konstant a k validnim konstantam vypsal tabulku potrebne bitove sirky multiplikace a posunu. Vicemene to vychazelo z HD ale tusim, ze tam bylo jeste rozsireni z nejakeho paperu (patrne rozsah multiplikantu, pokud nebylo potreba nasobit plny rozsah n-bitoveho registru). Ani to nebylo tak pomale.
Prekladac musi podporovat cely rozsah registru, takze generuje konstantu a posuv v dikci algoritmu z HD. -
Existuje na to třeba knihovna libdivide https://libdivide.com/ popř. stačí to dělení napsat do godbolta https://godbolt.org/z/MqoEW5abf
18. 9. 2024, 21:53 editováno autorem komentáře
-
Pouzivam kdyz zkoumam jak to na Z80 resi nejlepsi soucasny prekladac C. Tedy z88dk.
Ale ten vubec neumi delit konstantou.
Krome nasobku 2 a to jeste jen nejake nasobky dvou.
Konkretne umi delit beznamenkove inline 2, 4, 256 a 512.
Pak dokaze volat funkci pro bitovy posun pro deleni 8,16,32,64,128.
1024 a vyse uz radsi vola obecnou funkci pro deleni.Bojim se psat dal abych nebyl prilis kriticky... muselo to dat spoustu prace a je to zdarma.
Vcera jsem zkousel jak umi kopirovat 16 bitovou hodnotu z jednoho pointeru na druhy pointer.
void copypointer(int *adr1, int *adr2) { *adr2 = *adr1; }._copypointer ld hl,2 ;const call l_gintspsp ; ld hl,6 ;const add hl,sp call l_gint ; call l_gint ; pop de call l_pint rethttps://godbolt.org/z/fdxGKabfr
Kdyz si to projdete vcetne neukazanych pomocnych rutin tak ten kod vypada
._copypointer ld hl,2 ; 3:10 call l_gintspsp ; 3:17 .l_gintspsp add hl,sp ; 1:11 inc hl ; 1:6 inc hl ; 1:6 ld a,(hl) ; 1:7 inc hl ; 1:6 ld h,(hl) ; 1:7 ld l,a ; 1:4 ex (sp),hl ; 1:19 jp (hl) ; 1:4 ld hl,6 ; 3:10 add hl,sp ; 1:11 call l_gint ; 3:17 .l_gint ld a,(hl) ; 1:7 inc hl ; 1:6 ld h,(hl) ; 1:7 ld l,a ; 1:4 ret ; 1:10 call l_gint ; 3:17 .l_gint ld a,(hl) ; 0:7 inc hl ; 0:6 ld h,(hl) ; 0:7 ld l,a ; 0:4 ret ; 0:10 pop de ; 1:10 call l_pint ; 3:17 .l_pint ld a,l ; 1:4 ld (de),a ; 1:7 inc de ; 1:6 ld a,h ; 1:4 ld (de),a ; 1:7 ret ; 1:5 ret ; 1:5 ;[41:285]a rucne to jde napsat jako
ldi ; 2:16 __INFO [DE++] = [HL++], BC-- ldd ; 2:16 __INFO [DE--] = [HL--], BC-- ; seconds: 0 ;[ 4:32]HL a DE nebude zmeneno a BC se zmensi o 2.
Jde to napsat i hure, ale neverim ze kdokoliv by to napsal tak slozite jako neironicky opravdu nejlepsi prekladac C na Z80.
10x delsi kod a 9x pomalejsi.
K tomu ocekavejte ze vam to automaticky pribali ke kodu 4 kb asi pro runtime knihovnu. -
Na tohle tema jsem narazil na celkem citelny clanek i pro nematfyzaky na:
https://jk-jeon.github.io/posts/2023/08/optimal-bounds-integer-division/
kde popisuje postup a vysvetleni jednotlivych vet pomalu a srozumitelne s priklady..
Protoze koukani na https://www.ncbi.nlm.nih.gov/pmc/articles/PMC8258644/table/tbl0010/?report=objectonly je proste pro nekoho chytrejsiho nez jsem ja.
Vlastne pekny clanek na deleni 10 na osmibitech je na
https://homepage.cs.uiowa.edu/~dwjones/bcd/decimal.html
Je tam popsana citelne dalsi zajimava metoda.
Ale je videt ze autor to nepsal pro Z80, ale obecne a vlastne cilil na nejlepsi algoritmus pro C.
Protoze kdyz se nakonec kouknete na to co zplodil, tak zjistite, ze v realu kdyz to budete psat v assembleru tak uplne prvni, primitivni varianta s postupnym prostym odcitani nasobku 10000,1000,100,10 je kratsi a asi i rychlejsi varianta, nez po celem tom usili vytvori on.
Ten kod i postup je inspirativni, ale...
Napriklad zkousi nasobit kratsi konstantou a pak resit korekci +1 z vypocitane chyby, protoze vysledek znovu nasobi 10. To je rychle, staci n*10 = n*2*5 = 2*(2*2*n + n).
Pouziva ale bitove posuny DOPRAVA o konstantu vetsi jak 1.
Naprosto NEPRIJATELNE pro 16 bitu na Z80.
Opakovane nasobeni 8*8=16 bitu atd.
C a assembler je proste jiny svet, na techto starych CICS procesorech.
8086 je o neco vic Pascal/C kompatibilni (predavani parametru pres zasobnik a neustala podpora rekurze at to stoji co to stoji), ale asi to take neni a uz nebude zadna slava, protoze je to davno zapomenuty procesor pro vetsinu modernich prekladacu. -
Jj, vypocty na 8bitech byly peklo. V drevnich dobach jsme se ucili zaklady DSP (zde P = processing) na pripravcich s 8051...
Pred 20 lety jsem presel na ARMy a tam treba na slabych Cortexech s jednocyklovou nasobickou, ale casove drahym delenim konci rychla konverze utoa treba takto:uint8_t * bin2dec(uint32_t u, uint8_t * dest) { uint8_t * d = dest; uint64_t r; if (u < 100UL) { /* 1 & 2 digits */ ECHO2DECDIGCOND(d, u) goto lm0; } else if (u < 1000000UL) { if (u < 10000UL) { /* 3 & 4 digits */ /* (100..9999) * (2^32 / 100) -> 2^32 / 100 = 42,949,672.96 -> 42,949,673 */ r = (uint64_t)u * 42949673UL; u = (uint32_t)(r >> 32U); ECHO2DECDIGCOND(d, u) d += 2UL; goto lm2; } else { /* 5 & 6 digits */ /* 10000..999999 * (2^32 / 10000) -> 2^32 / 10000 = 429,496.7296 -> 429,497 */ r = (uint64_t)u * 429497UL; u = (uint32_t)(r >> 32U); ECHO2DECDIGCOND(d, u) d += 4UL; goto lm4; } } else { if (u < 100000000UL) { /* 7 & 8 digits */ /* 1000000..99999999 * (2^32 / 1000000) -> 2^32 / 1000000 = 4,294.967296 -> 4,294 */ /* The multiplication precision is not sufficient */ /* 1000000..99999999 * (2^(32 + 16) / 1000000) -> 2^(32 + 16) / 1000000 = 281,474,976.710656 -> 281,474,977 */ r = ((uint64_t)u * 281474977UL) >> 16U; u = (uint32_t)(r >> 32U); ECHO2DECDIGCOND(d, u) d += 6UL; goto lm6; } else if (u <= 1160773632UL) { // 9 & 9+1/2 digits /* 100000000..4294967295 * (2^32 / 100000000) -> 2^32 / 100000000 = 42.94967296 -> 43 */ /* The multiplication precision is not sufficient */ /* 100000000..1160872980 * (2^(32 + 25) / 100000000) -> 2^(32 + 25) / 100000000 = 1,441,151,880.75855872 -> 1,441,151,882 ! */ // -> it works up to 1160872980 only! // For immediate comparison -> 1,160,773,632 <-> 0x45300000 11-bit value r = ((uint64_t)u * 1441151882UL) >> 25U; u = (uint32_t)(r >> 32U); ECHO2DECDIGCOND(d, u) goto lm8; } else { /* 10 digits */ /* 100000000..4294967295 * (2^32 / 100000000) -> 2^32 / 100000000 = 42.94967296 -> 43 */ /* The multiplication precision is not sufficient */ /* 100000000..4294967295 * (2^(32 + 25) / 100000000) -> 2^(32 + 25) / 100000000 = 1,441,151,880.75855872 -> 1,441,151,881 */ r = (uint64_t)u * 1441151881UL; u = (uint32_t)(r >> 57U); ECHO2DECDIGCOND(d, u) /* Fix back to 32-bit fraction */ r >>= 25U; goto lm8; } } lm8: r = (r & 0xFFFFFFFFUL) * 100UL; u = (uint32_t)(r >> 32U); ECHO2DECDIG(d - 8UL, u) d += 8UL; lm6: r = (r & 0xFFFFFFFFUL) * 100UL; u = (uint32_t)(r >> 32U); ECHO2DECDIG(d - 6UL, u) lm4: r = (r & 0xFFFFFFFFUL) * 100UL; u = (uint32_t)(r >> 32U); ECHO2DECDIG(d - 4UL, u) lm2: r = (r & 0xFFFFFFFFUL) * 100UL; u = (uint32_t)(r >> 32U); ECHO2DECDIG(d - 2UL, u) lm0: *d = 0U; return d; }To ECHO... makro neni nic jineho nez sahnuti do 200bajtove tabulky dvojic znaku. Cilem bylo zvolit takove multiplikativni konstanty, aby byly potreba 32bitove posuny, tj. zadne, takze to uint64_t je vicemene takova berlicka pro C.
