🚀 go-pugleaf

RetroBBS NetNews Server

Inspired by RockSolid Light RIP Retro Guy

🏠 Home 📰 News 🗂️ Usenet Search 🔑 Login
Thread View: pl.comp.lang.asm
15 messages
[T] Back to Threads [V] Tree View [G] Group Articles
15 total messages Started by Andrzej Grażyński Mon, 15 Mar 2010 19:02
Zagadka
#2132
Author: Andrzej Grażyński
Date: Mon, 15 Mar 2010 19:02
17 lines
1175 bytes 
1.
386 i wyżej.

W EAX i EDX są dwie liczby całkowite BEZ ZNAKU. Należy spowodować, by w 
EAX znalazła się mniejsza (w sensie relacji JB) z tych liczb - NIE WOLNO 
UŻYWAĆ SKOKÓW.



2.

Jak wyżej, ale zawartości rejestrów traktowane są jako liczby ze znakiem 
("mniejsza" oznacza "w sensie relacji" JL).

WSKAZÓWKA: To zadanie jest w 3. tomie "Sztuki programowania" D.E. 
Knutha, jego rozwiązanie z książki na nic się tu nie przyda.
Re: Zagadka
#2133
Author: Wojciech Muła
Date: Mon, 15 Mar 2010 19:46
26 lines
1461 bytes 
Andrzej Grażyński <grazynsk@petex.com.pl> wrote:

> 1.
> 386 i wyżej.
> 
> W EAX i EDX są dwie liczby całkowite BEZ ZNAKU. Należy spowodować, by w 
> EAX znalazła się mniejsza (w sensie relacji JB) z tych liczb - NIE WOLNO 
> UŻYWAĆ SKOKÓW.
> 
> 2.
> 
> Jak wyżej, ale zawartości rejestrów traktowane są jako liczby ze znakiem 
> ("mniejsza" oznacza "w sensie relacji" JL).

Dla 686 i nowszych :)

cmp   eax, edx
cmovb eax, edx	; 1
cmovl eax, edx	; 2

Odpowiedź poprawną znam, ale nie chcę psuć innym zabawy.

w.

-- 
Mamy oswojoną sarnę i w związku z tym projektuję, by dorobić do niej kłódkę.
Re: Zagadka
#2134
Author: Bogdan (bogdro)
Date: Tue, 16 Mar 2010 18:03
37 lines
1871 bytes 
W dniu 15.03.2010 20:02, Andrzej Grażyński pisze:
> 
> 1.
> 386 i wyżej.
> 
> W EAX i EDX są dwie liczby całkowite BEZ ZNAKU. Należy spowodować, by w
> EAX znalazła się mniejsza (w sensie relacji JB) z tych liczb - NIE WOLNO
> UŻYWAĆ SKOKÓW.

 Nietestowane, a poza tym pewnie powolne jak nie wiem co:

	mov	ebx, eax
	mov	ecx, edx
	cmp	eax, edx
	sbb	eax, eax	; 0 / -1
	cmp	eax, edx
	sbb	edx, edx	; -1 / 0
	and	eax, ebx	; 0 / EAX
	and	edx, ecx	; EDX / 0
	add	eax, edx	; EDX / EAX

> 2.
> 
> Jak wyżej, ale zawartości rejestrów traktowane są jako liczby ze znakiem
> ("mniejsza" oznacza "w sensie relacji" JL).

 Jak wyżej, ale zacząć od
	add	eax, 80000000h
	add	edx, 80000000h
 a skończyć na
	sub	eax, 80000000h

-- 
Pozdrawiam/Regards - Bogdan                     (GNU/Linux & FreeDOS)
Kurs asemblera x86 (DOS, GNU/Linux):http://rudy.mif.pg.gda.pl/~bogdro
Grupy dyskusyjne o asm:  pl.comp.lang.asm alt.pl.asm alt.pl.asm.win32
www.JabberPL.org www.TorProject.org Soft (EN): miniurl.pl/bogdro-soft
Re: Zagadka
#2135
Author: Wojciech Muła
Date: Tue, 16 Mar 2010 19:24
30 lines
1640 bytes 
"Bogdan (bogdro)" <bogdan@poczta.gazeta.pl> wrote:

> W dniu 15.03.2010 20:02, Andrzej Grażyński pisze:
> > 
> > 1.
> > 386 i wyżej.
> > 
> > W EAX i EDX są dwie liczby całkowite BEZ ZNAKU. Należy spowodować, by w
> > EAX znalazła się mniejsza (w sensie relacji JB) z tych liczb - NIE WOLNO
> > UŻYWAĆ SKOKÓW.
> 
>  Nietestowane, a poza tym pewnie powolne jak nie wiem co:
> 
> 	mov	ebx, eax
> 	mov	ecx, edx
> 	cmp	eax, edx
> 	sbb	eax, eax	; 0 / -1
> 	cmp	eax, edx
> 	sbb	edx, edx	; -1 / 0
> 	and	eax, ebx	; 0 / EAX
> 	and	edx, ecx	; EDX / 0
> 	add	eax, edx	; EDX / EAX

Taka mała uwaga: niepotrzebnie dwa razy porównujesz, wystarczy raz,
a potem 'neg maska'.

w.

-- 
Mamy oswojoną sarnę i w związku z tym projektuję, by dorobić do niej kłódkę.
Re: Zagadka
#2136
Author: Wojciech Muła
Date: Tue, 16 Mar 2010 20:24
24 lines
1540 bytes 
Wojciech Muła <wojciech_mula@poczta.null.onet.pl.invalid> wrote:

> >  Nietestowane, a poza tym pewnie powolne jak nie wiem co:
> > 
> > 	mov	ebx, eax
> > 	mov	ecx, edx
> > 	cmp	eax, edx
> > 	sbb	eax, eax	; 0 / -1
> > 	cmp	eax, edx
> > 	sbb	edx, edx	; -1 / 0
> > 	and	eax, ebx	; 0 / EAX
> > 	and	edx, ecx	; EDX / 0
> > 	add	eax, edx	; EDX / EAX
> 
> Taka mała uwaga: niepotrzebnie dwa razy porównujesz, wystarczy raz,
> a potem 'neg maska'.

Powiem jeszcze, że można zejść do 6 instrukcji.
Kombinujcie. :)

w.

-- 
Mamy oswojoną sarnę i w związku z tym projektuję, by dorobić do niej kłódkę.
Re: Zagadka
#2137
Author: Andrzej Grażyński
Date: Fri, 19 Mar 2010 09:00
53 lines
1951 bytes 
Bogdan (bogdro) pisze:
> W dniu 15.03.2010 20:02, Andrzej Grażyński pisze:
>> 1.
>> 386 i wyżej.
>>
>> W EAX i EDX są dwie liczby całkowite BEZ ZNAKU. Należy spowodować, by w
>> EAX znalazła się mniejsza (w sensie relacji JB) z tych liczb - NIE WOLNO
>> UŻYWAĆ SKOKÓW.
> 
>  Nietestowane, a poza tym pewnie powolne jak nie wiem co:
> 
> 	mov	ebx, eax
> 	mov	ecx, edx
> 	cmp	eax, edx
> 	sbb	eax, eax	; 0 / -1
> 	cmp	eax, edx
> 	sbb	edx, edx	; -1 / 0
> 	and	eax, ebx	; 0 / EAX
> 	and	edx, ecx	; EDX / 0
> 	add	eax, edx	; EDX / EAX
> 
>> 2.
>>
>> Jak wyżej, ale zawartości rejestrów traktowane są jako liczby ze znakiem
>> ("mniejsza" oznacza "w sensie relacji" JL).
> 
>  Jak wyżej, ale zacząć od
> 	add	eax, 80000000h
> 	add	edx, 80000000h
>  a skończyć na
> 	sub	eax, 80000000h
> 
EAX <- MIN(EAX, EDX) unsigned


    CMP EAX,EDX
    SBB EBX,EBX
    AND EAX,EBX
    NOT EBX
    AND EDX,EBX
    OR  EAX,EDX


EAX <- MIN(EAX, EDX) signed

    CMP EAX,EDX
    SETL BL
    NEG  BL
    SBB EBX,EBX
    AND EAX,EBX
    NOT EBX
    AND EDX,EBX
    OR  EAX,EDX
Re: Zagadka
#2138
Author: Wojciech Muła
Date: Fri, 19 Mar 2010 10:45
60 lines
2227 bytes 
Andrzej Grażyński <grazynsk@petex.com.pl> wrote:

> Bogdan (bogdro) pisze:
> > W dniu 15.03.2010 20:02, Andrzej Grażyński pisze:
> >> 1.
> >> 386 i wyżej.
> >>
> >> W EAX i EDX są dwie liczby całkowite BEZ ZNAKU. Należy spowodować, by w
> >> EAX znalazła się mniejsza (w sensie relacji JB) z tych liczb - NIE WOLNO
> >> UŻYWAĆ SKOKÓW.
> > 
> >  Nietestowane, a poza tym pewnie powolne jak nie wiem co:
> > 
> > 	mov	ebx, eax
> > 	mov	ecx, edx
> > 	cmp	eax, edx
> > 	sbb	eax, eax	; 0 / -1
> > 	cmp	eax, edx
> > 	sbb	edx, edx	; -1 / 0
> > 	and	eax, ebx	; 0 / EAX
> > 	and	edx, ecx	; EDX / 0
> > 	add	eax, edx	; EDX / EAX
> > 
> >> 2.
> >>
> >> Jak wyżej, ale zawartości rejestrów traktowane są jako liczby ze znakiem
> >> ("mniejsza" oznacza "w sensie relacji" JL).
> > 
> >  Jak wyżej, ale zacząć od
> > 	add	eax, 80000000h
> > 	add	edx, 80000000h
> >  a skończyć na
> > 	sub	eax, 80000000h
> > 
> EAX <- MIN(EAX, EDX) unsigned
> 
> 
>     CMP EAX,EDX
>     SBB EBX,EBX
>     AND EAX,EBX
>     NOT EBX
>     AND EDX,EBX
>     OR  EAX,EDX

Można zejsć do 5 instrukcji.

> EAX <- MIN(EAX, EDX) signed
> 
>     CMP EAX,EDX
>     SETL BL
>     NEG  BL
>     SBB EBX,EBX
>     AND EAX,EBX
>     NOT EBX
>     AND EDX,EBX
>     OR  EAX,EDX

Można zejść do 4 instrukcji.

w.
Re: Zagadka
#2139
Author: Andrzej Grażyński
Date: Mon, 22 Mar 2010 18:18
61 lines
2404 bytes 
Wojciech Muła pisze:
> Andrzej Grażyński <grazynsk@petex.com.pl> wrote:
> 
>> Bogdan (bogdro) pisze:
>>> W dniu 15.03.2010 20:02, Andrzej Grażyński pisze:
>>>> 1.
>>>> 386 i wyżej.
>>>>
>>>> W EAX i EDX są dwie liczby całkowite BEZ ZNAKU. Należy spowodować, by w
>>>> EAX znalazła się mniejsza (w sensie relacji JB) z tych liczb - NIE WOLNO
>>>> UŻYWAĆ SKOKÓW.
>>>  Nietestowane, a poza tym pewnie powolne jak nie wiem co:
>>>
>>> 	mov	ebx, eax
>>> 	mov	ecx, edx
>>> 	cmp	eax, edx
>>> 	sbb	eax, eax	; 0 / -1
>>> 	cmp	eax, edx
>>> 	sbb	edx, edx	; -1 / 0
>>> 	and	eax, ebx	; 0 / EAX
>>> 	and	edx, ecx	; EDX / 0
>>> 	add	eax, edx	; EDX / EAX
>>>
>>>> 2.
>>>>
>>>> Jak wyżej, ale zawartości rejestrów traktowane są jako liczby ze znakiem
>>>> ("mniejsza" oznacza "w sensie relacji" JL).
>>>  Jak wyżej, ale zacząć od
>>> 	add	eax, 80000000h
>>> 	add	edx, 80000000h
>>>  a skończyć na
>>> 	sub	eax, 80000000h
>>>
>> EAX <- MIN(EAX, EDX) unsigned
>>
>>
>>     CMP EAX,EDX
>>     SBB EBX,EBX
>>     AND EAX,EBX
>>     NOT EBX
>>     AND EDX,EBX
>>     OR  EAX,EDX
> 
> Można zejsć do 5 instrukcji.
> 
>> EAX <- MIN(EAX, EDX) signed
>>
>>     CMP EAX,EDX
>>     SETL BL
>>     NEG  BL
>>     SBB EBX,EBX
>>     AND EAX,EBX
>>     NOT EBX
>>     AND EDX,EBX
>>     OR  EAX,EDX
> 
> Można zejść do 4 instrukcji.
> 
> w.

Chętnie zobaczyłbym te krótsze wersje.
Re: Zagadka
#2140
Author: Wojciech Muła
Date: Mon, 22 Mar 2010 18:42
47 lines
1850 bytes 
Andrzej Grażyński <grazynsk@petex.com.pl> wrote:

> >> EAX <- MIN(EAX, EDX) unsigned
> >>
> >>
> >>     CMP EAX,EDX
> >>     SBB EBX,EBX
> >>     AND EAX,EBX
> >>     NOT EBX
> >>     AND EDX,EBX
> >>     OR  EAX,EDX
> > Można zejsć do 5 instrukcji.

cmp eax, edx
sbb ebx, ebx

xor edx, eax
and edx, ebx
xor eax, edx

Ostanie 3 instrukcje można skojarzyć z rozwiązaniem stosownym w
http://en.wikipedia.org/wiki/XOR_linked_list

> >> EAX <- MIN(EAX, EDX) signed
> >>
> >>     CMP EAX,EDX
> >>     SETL BL
> >>     NEG  BL
> >>     SBB EBX,EBX
> >>     AND EAX,EBX
> >>     NOT EBX
> >>     AND EDX,EBX
> >>     OR  EAX,EDX
> > 
> > Można zejść do 4 instrukcji.

sub edx, eax
sbb ebx, ebx

and edx, ebx
add eax, edx	; albo sub

> Chętnie zobaczyłbym te krótsze wersje.

Proszę. :) Fajnie, że trochę rozruszałeś grupę.

w.
Re: Zagadka
#2141
Author: Andrzej Grażyński
Date: Wed, 24 Mar 2010 20:57
61 lines
2459 bytes 
Wojciech Muła pisze:
> Andrzej Grażyński <grazynsk@petex.com.pl> wrote:
> 
>>>> EAX <- MIN(EAX, EDX) unsigned
>>>>
>>>>
>>>>     CMP EAX,EDX
>>>>     SBB EBX,EBX
>>>>     AND EAX,EBX
>>>>     NOT EBX
>>>>     AND EDX,EBX
>>>>     OR  EAX,EDX
>>> Można zejsć do 5 instrukcji.
> 
> cmp eax, edx
> sbb ebx, ebx
> 
> xor edx, eax
> and edx, ebx
> xor eax, edx
> 
> Ostanie 3 instrukcje można skojarzyć z rozwiązaniem stosownym w
> http://en.wikipedia.org/wiki/XOR_linked_list
> 
>>>> EAX <- MIN(EAX, EDX) signed
>>>>
>>>>     CMP EAX,EDX
>>>>     SETL BL
>>>>     NEG  BL
>>>>     SBB EBX,EBX
>>>>     AND EAX,EBX
>>>>     NOT EBX
>>>>     AND EDX,EBX
>>>>     OR  EAX,EDX
>>> Można zejść do 4 instrukcji.
> 
> sub edx, eax

I tu jest problem: jeżeli w eax i edx będą liczby przeciwnych znaków 
takie, że ich różnica nie zmieści się na 32 bitach (jako signed), to CF 
zostanie ustawiony niezależnie od tego, czy EDX<EAX czy EDX>=EAX. I 
ostateczny wynik może nie być poprawny.

Oryginalne rozwiązanie podane przez Knutha bazuje na formule

MIN(X, y) = (X + Y - ABS(X-Y))/2

i jest tak samo wrażliwe na problem nadmiaru.



> sbb ebx, ebx
> 
> and edx, ebx
> add eax, edx	; albo sub
> 
>> Chętnie zobaczyłbym te krótsze wersje.
> 
> Proszę. :) Fajnie, że trochę rozruszałeś grupę.
> 
> w.
Re: Zagadka
#2142
Author: Wojciech Muła
Date: Thu, 25 Mar 2010 19:26
37 lines
2261 bytes 
Andrzej Grażyński <grazynsk@petex.com.pl> wrote:

> >>>> EAX <- MIN(EAX, EDX) signed
> >>>>
> >>>>     CMP EAX,EDX
> >>>>     SETL BL
> >>>>     NEG  BL
> >>>>     SBB EBX,EBX
> >>>>     AND EAX,EBX
> >>>>     NOT EBX
> >>>>     AND EDX,EBX
> >>>>     OR  EAX,EDX
> >>> Można zejść do 4 instrukcji.
> > 
> > sub edx, eax
> 
> I tu jest problem: jeżeli w eax i edx będą liczby przeciwnych znaków 
> takie, że ich różnica nie zmieści się na 32 bitach (jako signed), to CF 
> zostanie ustawiony niezależnie od tego, czy EDX<EAX czy EDX>=EAX. I 
> ostateczny wynik może nie być poprawny.
> 
> Oryginalne rozwiązanie podane przez Knutha bazuje na formule
> 
> MIN(X, y) = (X + Y - ABS(X-Y))/2
> 
> i jest tak samo wrażliwe na problem nadmiaru.

Faktycznie, nie zwróciłem na to uwagi. Ale dalej można wykorzystać
trik z xorem dla dodatnich - w końcu tylko warunkowo podmieniamy bity.

Podrzuć jeszcze jakieś zadanko, to miło czasem ruszyć głową nad
zdałoby się prostym problemem.

w.

-- 
Mamy oswojoną sarnę i w związku z tym projektuję, by dorobić do niej kłódkę.
Re: Zagadka
#2143
Author: Andrzej Grażyński
Date: Thu, 25 Mar 2010 23:12
51 lines
2666 bytes 
Wojciech Muła pisze:
> Andrzej Grażyński <grazynsk@petex.com.pl> wrote:
> 
>>>>>> EAX <- MIN(EAX, EDX) signed
>>>>>>
>>>>>>     CMP EAX,EDX
>>>>>>     SETL BL
>>>>>>     NEG  BL
>>>>>>     SBB EBX,EBX
>>>>>>     AND EAX,EBX
>>>>>>     NOT EBX
>>>>>>     AND EDX,EBX
>>>>>>     OR  EAX,EDX
>>>>> Można zejść do 4 instrukcji.
>>> sub edx, eax
>> I tu jest problem: jeżeli w eax i edx będą liczby przeciwnych znaków 
>> takie, że ich różnica nie zmieści się na 32 bitach (jako signed), to CF 
>> zostanie ustawiony niezależnie od tego, czy EDX<EAX czy EDX>=EAX. I 
>> ostateczny wynik może nie być poprawny.
>>
>> Oryginalne rozwiązanie podane przez Knutha bazuje na formule
>>
>> MIN(X, y) = (X + Y - ABS(X-Y))/2
>>
>> i jest tak samo wrażliwe na problem nadmiaru.
> 
> Faktycznie, nie zwróciłem na to uwagi. Ale dalej można wykorzystać
> trik z xorem dla dodatnich - w końcu tylko warunkowo podmieniamy bity.
> 
> Podrzuć jeszcze jakieś zadanko, to miło czasem ruszyć głową nad
> zdałoby się prostym problemem.
> 
> w.
> 
Ten fragment zlicza jedynki w EAX


MACRO VCOUNTONESSTEP MSK, SHFT
          MOV  ECX,&MSK
          MOV  EDX,EAX
          SHR  EAX,&SHFT
          AND  EAX,ECX
          AND  EDX,ECX
          ADD  EAX,EDX
ENDM

VCOUNTONESSTEP 055555555H,1
VCOUNTONESSTEP 033333333H,2
VCOUNTONESSTEP  0F0F0F0FH,4
VCOUNTONESSTEP  00FF00FFH,8
VCOUNTONESSTEP  0000FFFFH,16
Re: Zagadka
#2144
Author: Michal Schulz
Date: Fri, 26 Mar 2010 06:40
57 lines
2544 bytes 
Andrzej Grażyński wrote:

>> Podrzuć jeszcze jakieś zadanko, to miło czasem ruszyć głową nad
>> zdałoby się prostym problemem.
>> 
>> w.
>> 
> Ten fragment zlicza jedynki w EAX
> 
> MACRO VCOUNTONESSTEP MSK, SHFT
>           MOV  ECX,&MSK
>           MOV  EDX,EAX
>           SHR  EAX,&SHFT
>           AND  EAX,ECX
>           AND  EDX,ECX
>           ADD  EAX,EDX
> ENDM
> 
> VCOUNTONESSTEP 055555555H,1
> VCOUNTONESSTEP 033333333H,2
> VCOUNTONESSTEP  0F0F0F0FH,4
> VCOUNTONESSTEP  00FF00FFH,8
> VCOUNTONESSTEP  0000FFFFH,16

W tym pojedynku wygral niestety gcc, ktory ten sam kod:

unsigned long bfcnto(unsigned long v)
{
    unsigned long const w = v - ((v >> 1) & 0x55555555);
    unsigned long const x = (w & 0x33333333) + ((w >> 2) & 0x33333333);
    unsigned long const c = (((x + (x >> 4)) & 0xF0F0F0F) * 0x1010101)>>24;

    return c;
}

przetworzyl na wersje prawie identyczna z twoja:

        mov     edx, eax
        shr     edx
        and     edx, 0x55555555
        sub     eax, edx
        mov     edx, eax
        and     eax, 0x33333333
        shr     edx, 2
        and     edx, 0x33333333
        add     edx, eax
        mov     eax, edx
        shr     eax, 4
        add     eax, edx
        and     eax, 0x0f0f0f0f
        imul    eax, eax, 0x01010101
        shr     eax, 24

PS. W SSE4.2 byloby jeszcze prosciej :)

-- 
Michal Schulz
Re: Zagadka
#2145
Author: Wojciech Muła
Date: Fri, 26 Mar 2010 08:46
57 lines
2791 bytes 
Michal Schulz <michal.schulz@onet.eu> wrote:

> > Ten fragment zlicza jedynki w EAX
> > 
> > MACRO VCOUNTONESSTEP MSK, SHFT
> >           MOV  ECX,&MSK
> >           MOV  EDX,EAX
> >           SHR  EAX,&SHFT
> >           AND  EAX,ECX
> >           AND  EDX,ECX
> >           ADD  EAX,EDX
> > ENDM
> > 
> > VCOUNTONESSTEP 055555555H,1
> > VCOUNTONESSTEP 033333333H,2
> > VCOUNTONESSTEP  0F0F0F0FH,4
> > VCOUNTONESSTEP  00FF00FFH,8
> > VCOUNTONESSTEP  0000FFFFH,16
> 
> W tym pojedynku wygral niestety gcc, ktory ten sam kod:
> 
> unsigned long bfcnto(unsigned long v)
> {
>     unsigned long const w = v - ((v >> 1) & 0x55555555);
>     unsigned long const x = (w & 0x33333333) + ((w >> 2) & 0x33333333);
>     unsigned long const c = (((x + (x >> 4)) & 0xF0F0F0F) * 0x1010101)>>24;
> 
>     return c;
> }
> 
> przetworzyl na wersje prawie identyczna z twoja:
> 
>         mov     edx, eax
>         shr     edx
>         and     edx, 0x55555555
>         sub     eax, edx
>         mov     edx, eax
>         and     eax, 0x33333333
>         shr     edx, 2
>         and     edx, 0x33333333
>         add     edx, eax
>         mov     eax, edx
>         shr     eax, 4
>         add     eax, edx
>         and     eax, 0x0f0f0f0f
>         imul    eax, eax, 0x01010101
>         shr     eax, 24

Uprzedziłeś mnie:
http://graphics.stanford.edu/~seander/bithacks.html

> PS. W SSE4.2 byloby jeszcze prosciej :)

W SSSE3 też dość prosto:
http://wm.ite.pl/articles/sse-popcount.html

w.
Re: Zagadka
#2146
Author: Tomasz Sowa
Date: Fri, 09 Apr 2010 23:14
13 lines
1293 bytes 
Dnia Mon, 22 Mar 2010 19:42:14 +0100, Wojciech Muła napisał(a):

> cmp eax, edx
> sbb ebx, ebx
> 
> xor edx, eax
> and edx, ebx
> xor eax, edx

Sprytne, tylko że to wybiera wartość większą a nie mniejszą :)

-- 
http://www.ttmath.org
Thread Navigation

This is a paginated view of messages in the thread with full content displayed inline.

Messages are displayed in chronological order, with the original post highlighted in green.

Use pagination controls to navigate through all messages in large threads.

Back to All Threads