[assembler] Code omslachtig of niet?

[Tomatoman]

In Delphi heb ik wat inline assembler geschreven. De functie IsPowerOfTwo controleert of de parameter Value een macht van twee is. De functie MakePowerOfTwo controleert of Value niet kleiner is dan LoBound en niet Groter is dan HiBound; als hieraan is voldaan, wordt Value opgerond naar de eerstvolgende macht van twee.

Delphi:

function IsPowerOfTwo(Value: Cardinal): Boolean;
asm
        { Check if Value < 2 }
        CMP     Value,2
        JL      @False
        { Check if only one bit is set }
        BSR     ECX,Value
        BSF     EDX,Value
        CMP     ECX,EDX
        JNE     @False
        MOV     EAX,True
        JMP     @End
@False: MOV     EAX,False
@End:
end;

function MakePowerOfTwo(Value, LoBound, HiBound: Cardinal): Cardinal;
asm
        { Test lower bound }
        CMP     Value,LoBound
        JNL     @High
        MOV     EAX,LoBound
        JMP     @End
        { Test higher bound }
@High:  CMP     Value,HiBound
        JNG     @1
        MOV     EAX,HiBound
        JMP     @End

@1:     MOV     EAX,Value
        { Check if only one bit is set }
        BSR     ECX,Value
        BSF     EDX,Value
        CMP     ECX,EDX
        JE      @End
        { Set Value to first higher power of two }
        MOV     EAX,1
        INC     CL
        SHL     EAX,CL
@End:
end;

Delphi kent alleen de 80386 instructieset en retourneert de functiewaarde in AL/AX/EAX. Aangezien ik nog maar weinig ervaring heb met assembler ben ik benieuwd of mijn code een beetje efficiënt geschreven is of juist heel omslachtig. Het gaat me hierbij niet zozeer om de code die het snelst wordt uitgevoerd, maar om zo min mogelijk regels broncode.

Iemand commentaar?

[klinz]

Er is een truc waarmee je met luttele instructies kunt bepalen of het een macht van twee is (er mag maximaal één '1' in de meegegeven waarde voorkomen).

Ook het afronden naar de dichtsbijzijnde macht van twee kan heel simpel (bepaal de eerste '1' binnen de meegegeven waarde en AND de rest weg en SHL 1). De instructie BSF kan je van dienst zijn om de '1' te vinden.

[ Voor 14% gewijzigd door klinz op 05-04-2004 00:30 ]

[Tomatoman]

klinz schreef op 05 april 2004 @ 00:29:
Er is een truc waarmee je met luttele instructies kunt bepalen of het een macht van twee is (er mag maximaal één '1' in de meegegeven waarde voorkomen).

Ook het afronden naar de dichtsbijzijnde macht van twee kan heel simpel (bepaal de eerste '1' binnen de meegegeven waarde en AND de rest weg en SHL 1). De instructie BSF kan je van dienst zijn om de '1' te vinden.

Zover had mijn eigen inventiviteit me al gebracht. Nu graag nog wat opmerkingen over de kwaliteit van mijn code.

[.oisyn]

klinz schreef op 05 april 2004 @ 00:29:
Er is een truc waarmee je met luttele instructies kunt bepalen of het een macht van twee is (er mag maximaal één '1' in de meegegeven waarde voorkomen).

Ook het afronden naar de dichtsbijzijnde macht van twee kan heel simpel (bepaal de eerste '1' binnen de meegegeven waarde en AND de rest weg en SHL 1). De instructie BSF kan je van dienst zijn om de '1' te vinden.

dat doet ie toch al?
De mov eax, false zou je evt. nog kunnen vervangen naar een xor eax, eax, dat scheelt 4 bytes
Ik begrijp trouwens uit je startpost dat ie alleen de 386 instructieset ondersteunt? Vanaf de pentium pro is er namelijk zoiets als een conditional move

[ Voor 63% gewijzigd door .oisyn op 05-04-2004 00:51 ]

[klinz]

Ik liet me misleiden door al die CMP's. Zijn die wel nodig?

[.oisyn]

Idd, je kunt de SETcc instructie gebruiken om een register 0 of 1 te laten zijn, adhv een conditie. Helemaal vergeten

[Tomatoman]

Volgens mij heb je minstens het aantal CMP's nodig dat ik heb gebruikt. Bij de eerste functie staat er een CMP om te controleren of Value niet kleiner is dan 2 (je moet voor BSR/BSF hoe dan ook controleren of er wel nul bits gezet zijn) en een CMP voor de bit shifts. Bij de tweede functie heb je twee CMP's nodig om te vergelijken met MinBound en MaxBound en nog een CMP voor de bit shifts.

Ik vraag me eerder af of al jumps wel nodig zijn.

@.oisyn: jouw - inmiddels verwijderde - C++ code heeft geen goed equivalent in Delphi. Dat is precies de reden dat ik het maar in assembler heb geprobeerd.

[Edit]
Setcc kende ik nog niet, die ga ik eens bekijken.

[ Voor 6% gewijzigd door Tomatoman op 05-04-2004 01:06 ]

[.oisyn]

Ik vraag me eerder af of al jumps wel nodig zijn.

uh ja idd, daar ging ik ook vanuit ondankds dat er CMP stond, ik moet echt naar bed

jouw - inmiddels verwijderde - C++ code heeft geen goed equivalent in Delphi

ik had het weer verwijderd omdat ik zag dat je zoiets al deed (het was meer pseudo-c++, in c++ zul je je ook moeten beroepen op assembly code voor die msb/lsb functies die ik gebruikte (wat in feite gewoon de BSR en BSF instructies zijn))

[ Voor 3% gewijzigd door .oisyn op 05-04-2004 01:06 ]

[Soultaker]

Ik kijk altijd eerst naar wat een compiler er mee doet. GCC 3.3 is wel creatief met de code om de waarde van Value geclipt in EAX te krijgen:

code:

        movl    8(%ebp), %edx       ; load Value into EDX
        movl    12(%ebp), %eax      ; load LoBound into EAX
        cmpl    %eax, %edx          ; compare EDX (=Value) with EAX (=LoBound)
        jb      .L1                 ; jump if Value < LoBound
        movl    16(%ebp), %eax      ; load HiBound into EAX
        cmpl    %eax, %edx          ; compare EDX (=Value) with EAX (=HiBound)
        ja      .L1                 ; jump if Value > HiBound
        movl    %edx, %eax          ; load EDX (=Value) into EAX
.L1:

Het aantal instructies is gelijk, maar er zitten twee onconditionele jumps minder in. Verder lijkt GCC alle argumenten eerst in registers te plaatsen alvorens er verder mee te rekenen. Ik weet niet of dat ook te maken heeft met efficiëntiewinst.

Dezelfde truc kan ik voor die alignment niet uithalen, omdat het niet redelijkerwijs in C/C++ te schrijven is (en GCC is ook niet slim genoeg om het zelf uit te zoeken).

[ Voor 9% gewijzigd door Soultaker op 05-04-2004 01:17 ]

[Soultaker]

tomatoman schreef op 05 april 2004 @ 00:21:

code:

        JNE     @False
        MOV     EAX,True
        JMP     @End
@False: MOV     EAX,False
@End:

Deze code zou vervangen kunnen worden door een enkele SETE EAX instructie.

[Soultaker]

tomatoman schreef op 05 april 2004 @ 00:21:

code:

@1:     MOV     EAX,Value
        { Check if only one bit is set }
        BSR     ECX,Value
        BSF     EDX,Value
        CMP     ECX,EDX
        JE      @End
        { Set Value to first higher power of two }
        MOV     EAX,2
        INC     CL
        SHL     EAX,CL
@End:

Met een beetje creatief rekenwerk kun je het geval waarbij er maar 1 bit geset is net zo behandelen als de overige gevallen en de dan kan de test of er maar één bit geset is achterwege blijven. Verder is de combinatie van 1 in EAX stoppen en vervolgens met CL+1 shiften hetzelfde als 2 in EAX stoppen en met CL shiften. De code kan je dan vervangen door iets als:

code:

        DEC EAX
        BSF CL, EAX
        MOV EAX, 1
        SHL EAX, CL

Dit zou zelfs voor 0 als waarde in EAX goed moeten gaan (EAX-1 wordt dan FFFFFFFFh en dus komt er uiteindelijk 32 in CL, waardoor EAX helemaal leeggeshift wordt).

edit:
Jammer genoeg gaat dit niet goed voor Value=1, want dan zit er in EAX-1 helemaal geen 1-bit meer. Het moet dan zoiets worden:

code:

        DEC EAX
        BSF CL, EAX
        SETZ EAX
        JNZ @L
        ADD AL, 2
        SHL EAX, CL
@L:

Maar de meerwaarde ten opzichte van de originele code wordt dan wel wat kleiner.

[ Voor 41% gewijzigd door Soultaker op 05-04-2004 02:19 ]

[Tomatoman]

Soultaker schreef op 05 april 2004 @ 01:34:
[...]

code:

DEC EAX
BSF CL, EAX
MOV EAX, 1
SHL EAX, CL

Dit zou zelfs voor 0 als waarde in EAX goed moeten gaan (EAX-1 wordt dan FFFFFFFFh en dus komt er uiteindelijk 32 in CL, waardoor EAX helemaal leeggeshift wordt).

edit:
Jammer genoeg gaat dit niet goed voor Value=1, want dan zit er in EAX-1 helemaal geen 1-bit meer.

De operand die BSF en BSR retourneren is trouwens onbepaald als de bronoperand de waarde nul heeft. Daardoor is het resultaat van SHL op regel 4 onbepaald als de functie wordt aangeroepen met de waarde 0.

Na alle aanwijzingen weet ik nu wel hoe sommige jumps eruit kunnen:

Delphi:

function TFastFourier.IsPowerOfTwo(Value: Cardinal): Boolean;
asm
        { Check if Value < 2 }
        CMP     Value,2
        SETNL   AL
        JL      @End
        { Check if only one bit is set }
        BSR     ECX,Value
        BSF     EDX,Value
        CMP     ECX,EDX
        SETE    AL
@End:
end;

Bedankt voor alle aanwijzingen, ik ben weer wat wijzer.

[ Voor 3% gewijzigd door Tomatoman op 05-04-2004 02:21 ]

[Soultaker]

tomatoman schreef op 05 april 2004 @ 02:21:
De operand die BSF en BSR retourneren is trouwens onbepaald als de bronoperand de waarde nul heeft. Daardoor is het resultaat van SHL op regel 4 onbepaald als de functie wordt aangeroepen met de waarde 0.

Inderdaad; zie m'n aangepaste post (ik wilde niet een vierde op een rij maken ) voor een suggestie die daar rekening mee houdt.

Die IsPowerOfTwo kan trouwens nog wat anders:

code:

        MOV EAX, Value      ; load Value into EAX
        BSF CX, EAX         ; load index of most-significant 1-bit into CX
        BTC EAX, CX         ; complement most-significant 1-bit in EAX
        TEST EAX, EAX       ; test if EAX is zero
        SETZ EAX            ; load 1 into EAX if zero-flag is set

De laatste twee instructies zouden trouwens ook wel vervangen kunnen worden door NOT EAX indien Delphi net zo werkt met boolean waarden als C, dat wil zeggen: 0 == FALSE, alles behalve 0 == TRUE.

edit:
Merk op dat dit door het gebruik van BTC in plaats van BTR ook werkt voor 0 als invoer (het resultaat is dan FALSE, want 0 is geen macht van 2), wat de oorspronkelijke code verkeerd deed.

[ Voor 24% gewijzigd door Soultaker op 05-04-2004 02:41 ]

[Tomatoman]

Soultaker schreef op 05 april 2004 @ 02:34:
[...]

Inderdaad; zie m'n aangepaste post (ik wilde niet een vierde op een rij maken ) voor een suggestie die daar rekening mee houdt.

Die IsPowerOfTwo kan trouwens nog wat anders:

code:

MOV EAX, Value    ; load Value into EAX
BSF CX, EAX       ; load index of most-significant 1-bit into CX
BTC EAX, CX       ; complement most-significant 1-bit in EAX
TEST EAX, EAX     ; test if EAX is zero
SETZ EAX          ; load 1 into EAX if zero-flag is set

De laatste twee instructies zouden trouwens ook wel vervangen kunnen worden door NOT EAX indien Delphi net zo werkt met boolean waarden als C, dat wil zeggen: 0 == FALSE, alles behalve 0 == TRUE.

edit:
Merk op dat dit door het gebruik van BTC in plaats van BTR ook werkt voor 0 als invoer (het resultaat is dan FALSE, want 0 is geen macht van 2), wat de oorspronkelijke code verkeerd deed.

Twee aanvullingen om dit topic compleet te maken.

• Jouw code werkt precies zoals je omschrijft, alleen laadt BSF het least significant bit (zie commentaar bij regel 2 en 3).
• Delphi evalueert bij een boolean alleen het least significant byte om te kijken of een getal true of false is:
  0 = False
  1 = True
  2 = True
  255 = $00FF = True
  256 = $0100 = False, want alleen het least significant byte wordt geëvalueerd.
  Gevolg: de laatste twee instructies kunnen niet worden vervangen door NOT EAX, want alleen het AL-register wordt door Delphi gebruikt om het functieresultaat te evalueren.

BTC was trouwens ook nieuw voor mij

[ Voor 6% gewijzigd door Tomatoman op 06-04-2004 04:00 . Reden: opmaak ]

[Zoijar]

En zoiets:

code:

mov eax,value
dec eax
and eax,value
setz eax

En als 0 niet mee mag doen

code:

mov eax,value
dec eax
and eax,value
not eax
and eax,value

[ Voor 42% gewijzigd door Zoijar op 05-04-2004 10:18 ]

[Icelus]

Ik begrijp trouwens uit je startpost dat ie alleen de 386 instructieset ondersteunt? Vanaf de pentium pro is er namelijk zoiets als een conditional move

Voor oudere versies van Delphi is dit inderdaad het geval.
Delphi 7 ondersteunt echter: (uit help)
Supports all instructions found in the Intel Pentium III, Intel MMX extensions, Streaming SIMD Extensions (SSE), and the AMD Athlon (including 3D Now!)