[ASM] x86 vermenigvuldigen (quick)

[nzyme]

goed, leuk probleem voor de zondagmiddag

vermenigvuldigen in ASM _zonder_ de trage MUL instructie...

ik ben er achter dat het moet met machten van 2, dan een SHL (en later SHR voor als ik delen wil).

Echter hoe krijg ik een "dynamisch" getal als macht van 2

ow en voor de gein doen we dat niet met 16 maar met 8bits registers.

xl = 4
yl = 13

GAS:

PUSH AX
PUSH BX

SHL LX, <de hoogste macht van 2 die in yl past>

POP BX
POP AX

dit moet ik loopen lijkt me maar is dat ook niet traag ofzo ?

/me is niet helemaal helder op het moment van vragen aangzien hij de hele ochtend en gistermiddag al op got/google geweest is...
/me heeft dus al _veeeel_ asm gelezen over vermenigvuldigen wat jammer genoeg niet bruikbaar was.

ik moet gewoon ff op weg geholpen worden

[RayNbow]

Volgens een post op een bepaald forum is MUL niet zo traag:

quote: http://www.gamedev.net/co.../topic.asp?topic_id=19973

[...]
Actually, fmul is somewhere around 3-5 cycles (same for fadd).

Little summary:

           fmul  fadd   fdiv    (i)mul  (i)div
PPro/PII :  5/2   3/1  17f/36d     4
PIII     :  5/2   3/1  18f/32d     4
Athlon   :  4/1   4/1  16f/20d    4-5    ~40
K6(-2)   :  2/2   2/2              2
Pentium  :  3/1   3/1             11     ~40

fmul and fadd : 5/2 - result after 5 cycles / may start new operation each second cycle
fdiv - delay for float/double

En volgens een andere post:

quote: http://www.gamedev.net/co...topic.asp?topic_id=146697

That used to be true on old-skool microprocessors.

At some point, most integer instructions (except for divide and square root) started having a pipeline latency of one cycle, and the difference between bit shifts and multiplies disappeared (except for scheduling constraints). THEN, in a mysterious, un-fathomable decision, Intel decided to make bit shifts SLOWER than multiplies in the Pentium IV. Go figure.

Note that bit masking is still faster than modulo, though, as modulo inherently is a division operation:

fast = foo & 127;
slow = foo % 128;

Dus tja, ik weet niet of je iets kan verzinnen wat sneller is dan mul.

[Kuhlie]

Precies. Ik zie je al 5 instructies doen, dat zijn er nu al 4 teveel

[ Voor 5% gewijzigd door Kuhlie op 15-05-2005 14:41 . Reden: /me kent geen x86-asm, misschien zijn die buitenste 4 sowieso nodig, maar dan nog, details :) ]

[nzyme]

dan zeg ik het anders, het MOET zonder mul

[Daos]

Voorbeeld in c (assembly is te veel werk):

C:

#include <stdio.h>

unsigned mul(unsigned a, unsigned b) {
    int res = 0;
    int pow = 0;

    while(a > 0) {
        if (a & 1)
            res += b << pow;

        a >>= 1;
        pow++;
    }

    return res;
}

int main() {
    unsigned x = 5;
    unsigned y = 9;

    unsigned m = mul(x, y);

    printf("%u x %u = %u\n", x, y, m);
}

[nzyme]

wil niet lullig zijn maar waarom antwoord je in C als ik vraag in ASM

[Daos]

Hellraizer schreef op zondag 15 mei 2005 @ 15:34:
wil niet lullig zijn maar waarom antwoord je in C als ik vraag in ASM

Daos schreef op zondag 15 mei 2005 @ 15:28:
... (assembly is te veel werk)

Het gaat om het algoritme. C is gewoon veel sneller te programmeren en het is makkelijker te testen. Als je assembly niet nodig hebt, dan moet je het niet gebruiken.


versie 2:

C:

unsigned mul(unsigned a, unsigned b) {
    unsigned res = 0;

    while(a > 0) {
        if (a & 1)
            res += b;

        a >>= 1;
        b <<= 1;
    }

    return res;
}

In assembly wordt het zoiets (niet getest):

code:

procedure mul

push ebp
mov  ebp, esp
xor  eax, eax     ;res
mov  ecx, 8(ebp)  ;a 
mov  edx, 12(ebp) ;b 

jmp  multest
mulloop:

test ecx, 1
jz   mulendif
add  eax, edx
mulendif:

shr  ecx, 1
shl  edx, 1

multest:
cmp  ecx, 0
ja   mulloop

leave
ret

endp

edit:
Ter informatie:
eax is 32 bits
ax is 16 bits
ah, al zijn 8 bits

code:

31                                0
|                                 |
******** ******** ******** ********
<-              eax              ->
                  <-      ax     ->
                  <- ah -> <- al ->

Het register lx dat jij gebruikt ken ik niet.

[ Voor 20% gewijzigd door Daos op 15-05-2005 16:20 ]

[nzyme]

oepz typfoutje

tgaat om inline asm in delphi, en 8bit registers.

je uitleg over die registers weet ik

snap alleen niet waarom je SP gebruikt, das nl zown aparte in inline asm toch die je niet mag gebruiken

het gaat erom de variabelen xl en yl te vermenigvuldigen. Beide zijn 8bits (dus de low) van het ingevulde 16bit getal.

[ Voor 22% gewijzigd door nzyme op 15-05-2005 16:20 ]

[Daos]

Hellraizer schreef op zondag 15 mei 2005 @ 16:18:
oepz typfoutje

tgaat om inline asm in delphi, en 8bit registers.

je uitleg over die registers weet ik

snap alleen niet waarom je SP gebruikt, das nl zown aparte in inline asm toch die je niet mag gebruiken

het gaat erom de variabelen xl en yl te vermenigvuldigen. Beide zijn 8bits (dus de low) van het ingevulde 16bit getal.

Die "push ebp", "mov ebp, esp" en "leave" zorgen voor het maken en verwijderen van een soort frame op de stack. Het is handig als je bij de argumenten en locale variabelen (hier niet van toepassing) op de stack wilt komen. De stackpointer (esp) kan veranderen in de functie, maar de framepointer (basepointer, ebp) blijft altijd naar het frame wijzen.

Stack ziet er na die twee instructies er zo uit:

code:

[      b       ]        + 12
[      a       ]        + 8
[return address]    ebp + 4
[   oude ebp   ] <- ebp, esp

En als je bijvoorbeeld een lokale variabele res hebt (na push 0), dan ziet het er zo uit

code:

[      b       ]        + 12
[      a       ]        + 8
[return address]    ebp + 4
[   oude ebp   ] <- ebp
[     res      ]    ebp - 4, esp

Ik ging er van uit dat je echt alles in assembly deed. Je moet even kijken hoe je je Delphi-variabelen kan lezen in die inline-assembly.

Waarom probeer je het niet gewoon in Delphi? Je zal met assembly waarschijnlijk toch geen snellere code krijgen.

[ Voor 10% gewijzigd door Daos op 15-05-2005 16:41 ]

[nzyme]

die delphi vars kan je gewoon lezen das geen probleem:

code:

xl,xh,yl,yh

tis een school opdracht,vandaar dat t in asm moet en zonder mul

probleem is dat ik het logaritme niet "begrijp" en dus niet zo 123 kan toepassen

machten van 2......

of ik zoek het zoals altijd weer eens te moeilijk . . .

[kvdveer]

Hellraizer schreef op zondag 15 mei 2005 @ 14:48:
dan zeg ik het anders, het MOET zonder mul

Ik kan geen reden verzinnen waarom je dat zou willen (behalve dan op een processor waar de mul-instructie kapot is...)
Een mul instructie is tegenwoordig een cycle, een shift meestal ook. Alleen heb je om een getal van 8 bits te vermenigvuldigen 16 shifts en 8 tests, 8 conditionaljumps, 8 unconditional jumps en max 8 optellingen nodig. Daarnaast heb je een extra register nodig voor je bitmask. Dan hebben we het nog niet gehad over initialisatie en instructie-fetchen (>10 instructies ipv 1)
* kvdveer denkt Huiswerkopdracht?

edit:
Net te traag. Desondanks lijk ik wel helderziend.

Hellraizer schreef op zondag 15 mei 2005 @ 15:34:
wil niet lullig zijn maar waarom antwoord je in C als ik vraag in ASM

Ik vind je wel ongelofelijk LUI als je klaagt dat je een C algoritme krijgt en dan klaagt dat het geen ASM is. Het is JOU werk, niet ons werk.

[ Voor 28% gewijzigd door kvdveer op 15-05-2005 17:20 . Reden: te traag melding, even hart gelucht ]

[nzyme]

neej dat snap ik ook wel en ik vraag ook echt niet jullie om mn huiswerk te maken, zie ook de SP.

Maar ik vind ASM al pittig en om dan in C een voorbeeld te geven is niet zo fijn aangzien ik daar (nog) niet in thuis ben

En lui ? eerder gefrustreerd omdat ik dr nou al 2 volle dagen mee bzig ben en geen oplossing heb.

[JaWi]

Vermenigvuldigen in het binaire stelsel is niet veel anders dan vermenigvuldigen in het decimale stelsel. Je kunt gewoon het algorithme gebruiken wat je op de basisschool ook hebt geleerd om grote getallen met elkaar te vermenigvuldigen (eerst de eenheden, dan de tientallen, etc.). Het stukje C-code wat Daos gaf, doet nl. precies hetzelfde, maar dan in het binaire stelsel.

Ik zal je 'n hint geven: schrijf beide te vermenigvuldigen getallen onder elkaar in binaire vorm. Schrijf daarboven de machten van 2 beginnend bij 2^0 voor het minst belangrijke bitje en 2^7 voor het meest belangrijke bitje. Nu is het nog een kwestie van slim optellen...

[Woy]

Maar moet je het perse met shifts doen. Als de opdracht is om te vermenigvuldigen zonder mul dan kan je beter gewoon optellen.

code:

function Mul( a, b )
{
    result = 0;
    while( b > 0 )
    {
        result += a;
        b--;
    }
    return result;
}

en dan eventueel nog rekening houden met negatieve getallen maar dat zou niet zo'n probleem moeten zijn.

[ Voor 27% gewijzigd door Woy op 15-05-2005 17:53 ]

[nzyme]

mjah daar dacht ik ook al aan maar ik las dus via google dar dat NOGAL traag is en met SHL zou het sneller zijn .

[Woy]

Hellraizer schreef op zondag 15 mei 2005 @ 17:53:
mjah daar dacht ik ook al aan maar ik las dus via google dar dat NOGAL traag is en met SHL zou het sneller zijn .

Wil je nou iest hebben wat snel is ( Dan gewoon de MUL gebruiken ) of iets wat je opdracht oplost.

[nzyme]

lijkt me dat je voor de meest efficiente oplossing de meeste punten krijgt he en dat had ik al geprobeerd trouwens.

/me zoekt even die code

Gevonden maar werkt niet zoals het moet want halverwege wilde ik dus overstappen op SHL:

code:

  // xl met yl vermenigvuldigen
  ADD BL,0
  @loopl:
  ADD AL,xl    // tel steeds de waarde van xl op bij de waarde in AL
  CMP BL,yl     // vergelijk BL met yl
  JZ @endloopl  // on zero goto @endloop anders doorgaan
  INC BL        // de counter BL met 1 verhogen
  JMP @loopl    // terug naar @loop

  @endloopl:
  MOV z0,AL

  // xh met xh
  ADD BL,0
  @looph:
  ADD AH,xh    // tel steeds de waarde van xh op bij de waarde in AH
  CMP BL,yh     // vergelijk BH met yh
  JZ @endlooph   // on zero goto @endloop anders doorgaan
  INC BL     // de counter BH met 1 verhogen
  JMP @looph     // terug naar @loop

  @endlooph:
  MOV z1,AH

[ Voor 71% gewijzigd door nzyme op 15-05-2005 17:59 ]

[Jrz]

ik ruik schoolvragen

Modbreak:

* Creepy ruikt iemand die niet moet klagen maar een TR moet plaatsen...

[ Voor 70% gewijzigd door Creepy op 15-05-2005 18:05 ]

[Creepy]

Hellraizer schreef op zondag 15 mei 2005 @ 17:57:
lijkt me dat je voor de meest efficiente oplossing de meeste punten krijgt he en dat had ik al geprobeerd trouwens.

/me zoekt even die code

Gevonden maar werkt niet zoals het moet want halverwege wilde ik dus overstappen op SHL:

Ok.. de meest effiencte oplossing mag je wat mij betreft zelf gaan zoeken.

In het topic zie ik nu al een paar keer voorbij komen dat een gegeven oplossing niet helemaal goed is en dat je dat aangepast wilt hebben. Ik zou zeggen, ga het zelf aanpassen. Er zijn nu al een aantal algoritmes voorbij gekomen welke je best zelf kan omzetten naar ASM lijkt me.

[WVL_KsZeN]

ikzelf gebruik altijd de formule a*b=((a+b)^2-(a-b)^2)/4.. (a-b)^2 en (a+b)^2 heb ik een klein tabelletje voor..

shifts werkt natuurlijk ook, ongeveer zo :

code:

result=0
while(bits)
{asl a
if carry==set -> result+=b
asl result
bits--
}

6502 assembler en c door elkaar yummy

[Daos]

Hellraizer schreef op zondag 15 mei 2005 @ 17:57:

code:

  // xl met yl vermenigvuldigen
  ADD BL,0
  @loopl:
  ADD AL,xl    // tel steeds de waarde van xl op bij de waarde in AL
  CMP BL,yl     // vergelijk BL met yl
  JZ @endloopl  // on zero goto @endloop anders doorgaan
  INC BL        // de counter BL met 1 verhogen
  JMP @loopl    // terug naar @loop

  @endloopl:
  MOV z0,AL

  // xh met xh
  ADD BL,0
  @looph:
  ADD AH,xh    // tel steeds de waarde van xh op bij de waarde in AH
  CMP BL,yh     // vergelijk BH met yh
  JZ @endlooph   // on zero goto @endloop anders doorgaan
  INC BL     // de counter BH met 1 verhogen
  JMP @looph     // terug naar @loop

  @endlooph:
  MOV z1,AH

- 1 & 13 x * y = 65536 * xh * yh + 256 * xh * yl + 256 * xl * yh + xl * yl. De xh * yh heb je eigenlijk niet nodig. Verder moet je er rekening mee houden dat er 16 bits uit elk product komen.
- 2 Nul maken doe je met MOV BL, 0. Kortere manieren zijn SUB BL, BL en XOR BL, BL.
- 3 Eerst vergelijken en dan pas optellen. Het gaat bv fout als yl = 0. Zoals ik hierboven al zei: Resultaat past niet in AL. Gebruik AX of doe its met de carry (bv ADC AH, 0)


edit:
het oh zo moeilijke bewijs bij mijn eerste punt.
x = 256 * xh + xl
y = 256 * yh + yl

x * y = (256 * xh + xl) * (256 * yh + yl) = 65536 * xh * yh + 256 * xh * yl + 256 * xl * yh + xl * yl

Dit heb je volgens mij ergens halverwege de middelbare school al gehad.

[ Voor 12% gewijzigd door Daos op 15-05-2005 21:17 ]

[nzyme]

sjeeeez wat dom van die MOV en ADD mare, morgen is dr weer een dag |-)

[Daos]

rwb schreef op zondag 15 mei 2005 @ 17:51:
Maar moet je het perse met shifts doen. Als de opdracht is om te vermenigvuldigen zonder mul dan kan je beter gewoon optellen.

Met shiften gaat het veel sneller.

code:

function Mul( a, b )
{
    result = 0;
    while( b > 0 )
    {
        result += a;
        b--;
    }
    return result;
}

Neem N is maximum dat in a en b past.
De complexiteit van dit algoritme = O(N). Dat wil zeggen er moeten ongeveer N iteraties gedaan worden. Bv 1e iteratie b = 30000, 2e b = 29999, ... ,30000e b = 1

Daos schreef op zondag 15 mei 2005 @ 16:00:
versie 2:

C:

unsigned mul(unsigned a, unsigned b) {
    unsigned res = 0;

    while(a > 0) {
        if (a & 1)
            res += b;

        a >>= 1;
        b <<= 1;
    }

    return res;
}

Neem dezelfde N als bij vorige voorbeeld
De complexiteit van dit algoritme = O(LOG(N). Dat wil zeggen er moeten ongeveer LOG(N) iteraties gedaan worden. Bv 1e iteratie a = 30000, 2e a = 15000, ... , 15e a = 1

Het tweede algoritme is dus veel sneller.

[ Voor 4% gewijzigd door Daos op 15-05-2005 21:44 ]

[Woy]

Daos schreef op zondag 15 mei 2005 @ 21:41:
[...]

Met shiften gaat het veel sneller.


[...]

Neem N is maximum dat in a en b past.
De complexiteit van dit algoritme = O(N). Dat wil zeggen er moeten ongeveer N iteraties gedaan worden. Bv 1e iteratie b = 30000, 2e b = 29999, ... ,30000e b = 1


[...]

Neem dezelfde N als bij vorige voorbeeld
De complexiteit van dit algoritme = O(LOG(N). Dat wil zeggen er moeten ongeveer LOG(N) iteraties gedaan worden. Bv 1e iteratie a = 30000, 2e a = 15000, ... , 15e a = 1

Het tweede algoritme is dus veel sneller.

Daar ben ik het wel mee eens. Maar we waren het er hier al mee eens dat het gewoon veel sneller is om de MUL te gebruiken. Het is een school opdracht om het op te lossen zonder MUL en waarschijnlijk gewoon bedoeld om asm een beetje onder de knie te krijgen. Dan volstaat de manier met ADD ook gewoon. Ook al is jouw algoritme natuurlijk ook niet moeilijk te doen.

[.oisyn]

Hellraizer schreef op zondag 15 mei 2005 @ 15:34:
wil niet lullig zijn maar waarom antwoord je in C als ik vraag in ASM

Ik wil niet lullig zijn, maar hier op GoT streven we niet naar kant en klare antwoorden, zeker niet voor huiswerk. Ga de FAQ dus nog maar een keer doorlezen: P&W FAQ - de "quickstart".

[ Voor 8% gewijzigd door .oisyn op 17-05-2005 12:47 ]

[Janoz]

@rwb : Er staat dat je geen mul mag gebruiken. Er staat nergens dat je geen shift mag gebruiken. Daarnaast is 'de shift manier' dezelfde vermenigvuldig methode als degene die iedereen op de basisschool leert (,maar dan in het 2 tallige stelsel).

[Woy]

Janoz schreef op dinsdag 17 mei 2005 @ 13:10:
@rwb : Er staat dat je geen mul mag gebruiken. Er staat nergens dat je geen shift mag gebruiken. Daarnaast is 'de shift manier' dezelfde vermenigvuldig methode als degene die iedereen op de basisschool leert (,maar dan in het 2 tallige stelsel).

Daar ben ik het mee eens ( dat zeg ik ook in mijn post ), maar het was meer bedoeld om aan te geven dat er ook andere manieren zijn om het op te lossen. De topic starter kwam er blijkbaar niet uit met shifts en dan is de manier met optellen mischien makkelijker te begrijpen.

[Vaan Banaan]

Het vermenigvuldigen zonder mul (good old C64 times) werkt inderaad met shift left en right.
Bij a * b = c shift je a naar rechts en b naar links
Voorbeeld 5 * 3 =15 is in binaire vorm: 00000101 * 00000011 = 00001111
De stappen die gemaakt worden zijn dan (ik heb te lang niet meer met ASM gespeeld, dus dit is pseudo code)

code:

c=0
loop until a=0
shift a right
if carry flag set => c=c+b
shift left b

In dit voorbeeldje krijg je dus de volgende stappen:
a       carry     b         c
00000101  0     00000011    00000000 (c = 0)
00000010  1     00000011    00000000 (shift a right)
00000010  1     00000011    00000011 (carry flag set => c=c+b)
00000010  0     00000110    00000011 (shift b left)
00000001  0     00000110    00000011 (shift a right)
00000001  0     00000110    00000011 (carry flag not set, if wordt niet uitgevoerd)
00000001  0     00001100    00000011 (shift b left)
00000000  1     00001100    00000011 (shift a right)
00000000  1     00001100    00001111 (carry flag set => c=c+b)
00000000  0     00011000    00001111 (shift b left)
klaar (a=0)