Vydělávej až 160.000 Kč měsíčně! Akreditované rekvalifikační kurzy s garancí práce od 0 Kč. Více informací.
Hledáme nové posily do ITnetwork týmu. Podívej se na volné pozice a přidej se do nejagilnější firmy na trhu - Více informací.

Diskuze: Bitové pole, struktura ?

Aktivity
Avatar
švrčajs
Člen
Avatar
švrčajs:6.5.2016 17:04

Zdravím, mám takový menší problém s assemblerem.. Naprogramoval jsem dvě funkce, ale když jsem je šel odevzdávat, bylo mi řečeno, že mé řešení je špatné. Jednalo se o napsání fcí:

int *bitset_new(un­signed int n):
fce, která má vytvořit pole, které reprezentuje množinu o velikosti n, množina po vytvoření musí být prázdná a k alokaci se má zavolat malloc, s jeho pomocí naalokovat co nejmenší místo v paměti. Množina je reprezentovaná pomocí unsigned int. První prvek pole udává maximální počet prvků dané množiny a do ostatních prvků jsou v podobě jednotlivých bitů uloženy hodnoty z dané množiny

int bitset_add(unsigned int *set, unsigned int n):
fce, která přidá prvek n do množiny, pokud je n větší než velikost množiny, fce vrací -1, jinak 0

Sesmolil jsem toto a nevím, jak to opravit, jelikož moc materiálů k assembleru, s touto problematikou, nemám
Nekoukl by na to někdo ?

struct {
        unsigned int n;
        unsigned int * pole;
        unsigned int i;
}bar;


unsigned int *bitset_new(unsigned int n)
{
        bar.n = n;
        bar.i = 0;
        bar.pole = (unsigned int)malloc(4 * n);
        _asm
        {
                mov ecx, offset bar

                        mov eax, 4
                        mul[ecx]

                        push eax
                        call malloc
                        mov[ebx + 4], eax
                        add esp, 4
        }
}

int bitset_add(unsigned int *set, unsigned int n)
{
        _asm
        {
                mov ebx, offset bar
                mov[ebx + 4], set               // bar.pole = set

                mov eax, 4

                cmp n, [ebx + 8]                // if (n == bar.i) return -1;
                jz _endm1

                mul[ebx + 8]                    // eax = pole.i
                mov[ebx + 4 + eax], n   // bar.pole[i] = n
                inc[eax]                                // bar.i++
                mov eax, 0
                jmp end

                endm1:
                mov eax, -1;
        end:

        }
}
 
Odpovědět
6.5.2016 17:04
Avatar
Martin Dráb
Tvůrce
Avatar
Odpovídá na švrčajs
Martin Dráb:6.5.2016 17:44

V zadání píšou, že na reprezentaci množiny má alokovat minimum paměti. Což by v tvém případě pro množinu o max. N prvkách mělo být 4 + (N + 7) / 8, čtyřka je na uložení velikosti množiny (unsigned int), zbytek je alokace N bitů zarovnaná na nejbližší vyšší násobek 8.

Pak mi úplně není jasné, jak předáváš parametr při volání funkce malloc. Měl bys jí předat velikost bloku, kterou chceš naalokovat. Nebýt té instrukce add esp, 4, řekl bych, že používáš volací konvenci stdcall. Skoro bych ale řekl, že malloc bude přes cdecl či něco podobného (zkusil bych předat parametr v EXC... ale nejlepší bude se podívat do assembleru, co ti vygeneruje překladač).

U konvence stdcall se předávají parametry přes zásobník (výlučně) a uklízí je volaný (obvykle instrukcí ret n), takže pokud chceš použít tuto konvenci, neuklízej.

Nahoru Odpovědět
6.5.2016 17:44
2 + 2 = 5 for extremely large values of 2
Avatar
švrčajs
Člen
Avatar
Odpovídá na Martin Dráb
švrčajs:6.5.2016 19:53

No, právě v tomhle se už moc neorientuji, ve skriptech mám assembler probraný jen po vytvoření lehké struktury, ale žádné hraní s bitama tam už popsané není... Jinak, co se týče toho volání, tak takhle to právě máme uvedené ve skryptech.. že se na zásobník hodí registr s argumentem, zavolá se funkce a pak se dá add esp, 4 * počet pushnutých registrů..

Jinak na obrázku je orig. zadání, co se týče reprezentace množiny. jelikož jsem to blbě opsal

Editováno 6.5.2016 19:55
 
Nahoru Odpovědět
6.5.2016 19:53
Avatar
Martin Dráb
Tvůrce
Avatar
Odpovídá na švrčajs
Martin Dráb:7.5.2016 12:13

Pokud je to úkol na VŠ, tak bych se na nějaká skripta moc nevymlouval. Samostudium se tam může tak trochu předpokládat. Co se týče bitových operací, mohou se hodit instrukce AND, OR, XOR, NOT, ale to se podívej do referenční příručky k dané instrukční sadě (zde x86 či ia32).

Nemyslím, že bys tady potřeboval nějakou strukturu, ona je totiž tak jednoduchá, že se obejdeš bez její definice (stejně tu strukturu nevidí nikdo mimo ty dvě funkce).

Co se týče volání funkce malloc, fakt doporučuju se podívat, jaký kód pro něj generuje překladač (nejlépe v Debug režimu, kdy neoptimalizuje).

Mimochodem, zkoušel jsi nad těmi tvými funkcemi provádět nějaké testy?

Plus, pokud chceš psát funkce čistě v Assembleru, MSVS na to má kouzlo jménem __declspec(na­ked).

Nahoru Odpovědět
7.5.2016 12:13
2 + 2 = 5 for extremely large values of 2
Avatar
švrčajs
Člen
Avatar
Odpovídá na Martin Dráb
švrčajs:7.5.2016 14:58

Testy jsem zkoušel a zjistil jsem, že to nefunguje, píšu si programy nejdřív na papír (stejný styl, jako u písemek) a až pak to testuji, sem jsem to vložil bez otestování...

Nad tou strukturou jsem taky přemýšlel a nejlepší bude, když tam bude jen jedno pole, první prvek bude to N a pak jednotlivé čísla, ale zaráží mě tam nejmenší možné využití paměti, což mě dovedlo k myšlence, že když množina může obsahovat N prvků a zároveň, alespoň, jak já jsem to pochopil, může být max. prvek množiny N-1, tak zjistit kolik b zabírá N-1, počet b vynásobit N a zaokrouhlit na násobek 8, když to má být int.. A tím dostanu co nejmenší paměť, je to jen nápad :D Protože s řešením, budu mít problém :D

Jinak co se týče volacích konvencí (fastcall a CDECL), tak ty znám, ale nejsou vyžadovány...

Programy píšeme v C-čku a struktura je vlasně

int funkce()
{
_asm
{

}
}

Editováno 7.5.2016 14:58
 
Nahoru Odpovědět
7.5.2016 14:58
Avatar
Martin Dráb
Tvůrce
Avatar
Odpovídá na švrčajs
Martin Dráb:7.5.2016 15:32

Nad tou strukturou jsem taky přemýšlel a nejlepší bude, když tam bude jen jedno pole, první prvek bude to N a pak jednotlivé čísla, ale zaráží mě tam nejmenší možné využití paměti, což mě dovedlo k myšlence, že když množina může obsahovat N prvků a zároveň, alespoň, jak já jsem to pochopil, může být max. prvek množiny N-1, tak zjistit kolik b zabírá N-1, počet b vynásobit N a zaokrouhlit na násobek 8, když to má být int.. A tím dostanu co nejmenší paměť, je to jen nápad :D Protože s řešením, budu mít problém :D

No, ta množina si u každého z N prvků musí pamatovat, zda-li v ní je či není. To je binární informace (0 = není, 1 = je), takže na každý z N prvků (0, 1, ..., N - 1) ti stačí jeden bit. Plus sizeof(unsigned int) na uložení N. Moje formule 4 + (N + 7) / 8 právě dává velikost množiny zarovnanou na bajty (ne tedy na sizeof(unsigned int), ale jelikož nikdo jiný do té struktury sahat nebude, je to jedno).

Jinak co se týče volacích konvencí (fastcall a CDECL), tak ty znám, ale nejsou vyžadovány...

Vyžadovány jsou funkcí malloc, kterou potřebuješ zavolat. Pokud ji zavoláš se špatnou konvencí, může to vypadat dobře; obvykle se to později někde náhodně složí.

Programy píšeme v C-čku a struktura je vlasně

Tak, to mi je jasné. Jen mi přijde poněkud podivný tento způsob výuky Assembleru. Logičtější by mi přišlo psát celé ty funkce v Assembleru. Takhle ti překladač vygeneruje začátek a konec funkce, takže tě to např. vede k tomu, že volací konvence řešit nemusíš.


Ono asi nejjednodušší způsob, jak vyřešit tu úlohu, je naprogramovat ji normálně v Cčku a nechat si překladačem vypsat instrukce těch funkcí. Pak je stačí použít a případně trochu upravit (v Debug verzi tam bude asi dost zbytečností).

Nahoru Odpovědět
7.5.2016 15:32
2 + 2 = 5 for extremely large values of 2
Avatar
švrčajs
Člen
Avatar
Odpovídá na Martin Dráb
švrčajs:7.5.2016 15:40

Díky za rady, moc si toho cením

Ono asi nejjednodušší způsob, jak vyřešit tu úlohu, je naprogramovat ji normálně v Cčku a nechat si překladačem vypsat instrukce těch funkcí. Pak je stačí použít a případně trochu upravit (v Debug verzi tam bude asi dost zbytečností).

Je to i ve VS ? Teď to tam hledám a nenacházím.. Popř. nějaké jiné prostředí, kde to je ?

Editováno 7.5.2016 15:41
 
Nahoru Odpovědět
7.5.2016 15:40
Avatar
Martin Dráb
Tvůrce
Avatar
Odpovídá na švrčajs
Martin Dráb:7.5.2016 16:39

Mělo by jít zapnout nastavení překladače, aby ti generoval výpis v Assembleru (Assembler listing). A mají to i jiné překladače (GCC určitě, ICC/ICPC bych řekl, že taky). Pokud to nepůjde, tak by mohlo stačit program začít debuggovat a v menu Debug -> Windows si otevřít okno Disassembly.

Nahoru Odpovědět
7.5.2016 16:39
2 + 2 = 5 for extremely large values of 2
Avatar
švrčajs
Člen
Avatar
Odpovídá na Martin Dráb
švrčajs:7.5.2016 19:36

Začal jsem si s tím hrát, pohledal jsem ten malloc ve skriptech + i pomocí toho debugu a napsal zatím tu první funkci

ten malloc byl řešen v debugu takto:

                push ecx
00E8140A  push        ecx
                call malloc
00E8140B  call        dword ptr ds:[0E89110h]
                add esp, 4
00E81411  add         esp,4

a ve skriptech podobně, akorát místo dword ptr ds:.... je malloc

unsigned int *bitset_new(unsigned int n)
{
        _asm
        {
                mov ecx, n
                add ecx, 7
                shr ecx, 3
                add ecx, 4

                push ecx
                call malloc
                add esp, 4

                mov eax, n
        }

a teď jsem přemýšlel nad tím přidáváním a nevím, jak na to.. Zkoušel jsem si to i nakreslit ve dvojkové soustavě, prvních 32 míst je pro N, takže na uložení čísel, vzhledem k tomu, že (4 + (N + 7) / 8, při N=5, vyšlo 5.5 => zaokrouhleno na 5) na uložení přidávaných čísel mi zbývá 8 "míst" na uložení čísel... Neporadil bys mi jak na to ? Není to DÚ, je to příprava na zkoušku..

 
Nahoru Odpovědět
7.5.2016 19:36
Avatar
Martin Dráb
Tvůrce
Avatar
Odpovídá na švrčajs
Martin Dráb:7.5.2016 20:00

Uložení hodnoty N bych realizoval asi takto:

  1. zjistím, v kterém bajtu od počátku množiny je bit indikující přítomnost N (4 + N / 8),
  2. zjistím si, který bit v daném bajtu odpovídá N (B = N % 8, ale protože 8 je mocnina dvojky, můžeme psát B = N & 7),
  3. vytvořím si bitovou masku, kde jsou samé nuly, jenom ten bit odpovídající pozici N v bajtu (či v něčem větším, v zásadě nemusíš počítat, v kterém bajtu N je, ale klidně v kterém 32bitovém čísle) (M = 1 shl B),
  4. pomocí OR a masky nastavím příslušný bit na 1 (pokud bys chtěl z množiny odebírat, tak AND NOT).

Takhle nějak by to mohlo vypadat

; 1
mov eax, mnozina
add eax, 4
mov ebx, N
shr ebx, 3
add, eax, ebx
; 2
mov ecx, N
and ecx, (8-1)
; 3
mov edx, 1
shl edx, ecx
; 4
or [eax], edx

Ten malloc je zvláštní, budu se na to muset asi mrknout. Je samozřejmě otázka, zda tam ten add esp, 4 patří k volání té funkce, nebo zda se jedná o úklid lokálních proměnných.

Nahoru Odpovědět
7.5.2016 20:00
2 + 2 = 5 for extremely large values of 2
Avatar
Martin Dráb
Tvůrce
Avatar
Martin Dráb:7.5.2016 21:20

ten malloc byl řešen v debugu takto:

Ah, teď vidím, že jsem si špatně pamatoval cdecl. Takže to přičtení k esp po návratu z mallocu je úplně ok.

https://msdn.microsoft.com/…kwh89ks.aspx

Nahoru Odpovědět
7.5.2016 21:20
2 + 2 = 5 for extremely large values of 2
Avatar
švrčajs
Člen
Avatar
Odpovídá na Martin Dráb
švrčajs:8.5.2016 21:50

Narazil jsem na pár problémů zase :( Už při té alokaci, jak zavolám malloc, tak do eax se mi uloží pointer na tu pamět, tudíž jsem tu funkci upravil takto..

unsigned int *bitset_new(unsigned int n)
{
        /*int a = n;
        a += 7;
        a = a / 8;
        a += 4;*/

        //malloc(a);

        _asm
        {
                movsx eax, n
                        add eax, 7
                        shr eax, 3
                        add eax, 4

                        push eax
                        call dword ptr malloc
                        add esp, 4

                        mov [eax], dword ptr n      //změna, abych uložil n do eax

        }

}

jenže mi to píše error, že tam nemůže být [eax], ale když ty závorky smažu, tak se mi do paměti neuloží n :D
Zkoušel jsem to i v jiném prostředí a ta samá chyba... Stejně jako v tom tvém vzoru, toho přidávání nefunguje or [eax], edx, což mě dosti zaráží, jelikož by to fungovat mělo :D

A když do té paměti, normálně v C-čku, uložím n, tak to funguje, díval jsem se i na generovaný kod (assembler) a tam je to řešeno takto

        x[0] = 5;
00A414DB  mov         eax,4
00A414E0  imul        ecx,eax,0
00A414E3  mov         edx,dword ptr [x]
00A414E6  mov         dword ptr [edx+ecx],5

což je to stejné, jako mov [eax], n

Editováno 8.5.2016 21:53
 
Nahoru Odpovědět
8.5.2016 21:50
Avatar
Martin Dráb
Tvůrce
Avatar
Odpovídá na švrčajs
Martin Dráb:8.5.2016 22:11

No, pokud mov dword ptr [eax], n nefunguje, problém by mohl být v tom, že n bude asi vlastně nějaké místo v paměti ([ebp+něco]) a IA32 nemá instrukce pro přesuny mezi pamětí a pamětí, jenom mezi registrem a registrem a registrem a pamětí. Takže můžeš zkusit místo toho něco jako:

mov edx, n
mov dword ptr [eax], edx
Nahoru Odpovědět
8.5.2016 22:11
2 + 2 = 5 for extremely large values of 2
Avatar
švrčajs
Člen
Avatar
Odpovídá na Martin Dráb
švrčajs:11.5.2016 17:20

Tak nakonec se příprava vydařila :D... Ale mám teď jiný problém, na zápočet potřebuji ještě mergesort v assembleru... Už to mám naprogramované, ale jakmile spustím merge, tak mi to spadne, když chci přistupovat do pole, určitě to bude nějaká "kravinka", ale už na to čumím celý den a nic jsem tam nenašel, nekoukl bys na to ?

hodí to error: Exception thrown at 0x00B84D76 in mergesort_asm.exe: 0xC0000005: Access violation reading location 0x03EB8418.

#include <stdint.h>
#include <stdio.h>
#include <malloc.h>
#include <stdlib.h>
#include <malloc.h>
/*
private void mergeSort(int[] array, int left, int right)
{

        if (left != right)
        {
                //split the array into 2
                int center = (left + right) / 2;

                //sort the left and right array
                mergeSort(array, left, center);
                mergeSort(array, center + 1, right);

                //merge the result
                merge(array, left, center + 1, right);
        }
}*/
void Merge(int * pole, unsigned int left, unsigned int center, unsigned int right);


void Merge_sort_asm(int * pole, unsigned int left, unsigned int right)
{
        _asm
        {
                mov eax, left
                cmp eax, right
                je end
                xor eax, eax

                mov eax, left
                add eax, right
                mov ebx, 2
                xor edx, edx
                idiv ebx
                mov edx, eax     // edx = "pivot" (( left + right ) /2)

                mov esi, pole

                //volání na levou stranu
                push edx
                push left
                push esi
                call Merge_sort_asm
                add esp, 12

                //volání na pravou stranu
                inc edx // pivot+1
                push right
                push edx
                push esi
                call Merge_sort_asm
                add esp, 12

                //volání merge
                push right
                push edx
                push left
                push esi
                call Merge
                add esp, 16

                end:
        }
}


/*
private void merge(int[] array, int left, int center, int right)
{
        int leftArrayEnd = center - 1;
        int numElements = right - left + 1;
        int[] resultArray = new int[numElements];
        int resultArrayBegin = 0;

        while (left <= leftArrayEnd && center <= right)
        {
                if (array[left] <= array[center])
                {
                        resultArray[resultArrayBegin++] = array[left++];
                }
                else
                {
                        resultArray[resultArrayBegin++] = array[center++];
                }
        }

        while (left <= leftArrayEnd)
        {
                resultArray[resultArrayBegin++] = array[left++];
        }

        while (center <= right)
        {
                resultArray[resultArrayBegin++] = array[center++];
        }

        for (int i = numElements - 1; i >= 0; i--, right--)
        {
                array[right] = resultArray[i];
        }
}
*/

void Merge(int * pole, unsigned int left, unsigned int center, unsigned int right)
{
        int * buffer;
        buffer = pole = (int*)malloc(((right - left) + 1) * sizeof(int));//jelikož bude využíváno hodně registrů, pole je nadefinované v C
        _asm
        {
                // ebx = left end
                mov ebx, center
                dec ebx
                //počet elemntů
                mov edx, right
                sub edx, left
                add edx, 1

                mov edi, buffer
                mov esi, pole
                //ecx = index pro while---resultarraybegin
                mov ecx, 0

                firstWhile:
                        //ověření podmínek whilu
                        mov eax, left
                        cmp eax, ebx                            //left <= leftArrayEnd, když neplatí, konec cyklu, když platí tak ověř
                        ja endFirstWhile
                        mov eax, center
                        cmp eax, right                          //center <= right, když platí dělej, když né, končíš
                        ja endFirstWhile
                        xor eax, eax                            //vynulování eax...

                        mov eax, [esi + 4 * left]   // eax = pole[left]            !!!!!!!!!!!!chybová hláška a break programu..
                        cmp eax, [esi + 4 * center]
                        ja firstWhileElse                       //když je pole[center] vetši, proveď else větev

                        inc left
                        inc ecx
                        mov eax, [esi + 4 * left]
                        mov [edi + 4 * ecx], eax    //buffer[index++] = pole[left++]
                        jmp firstWhile

                                firstWhileElse:        //resultArray[resultArrayBegin++] = array[center++];
                                        inc ecx
                                        inc center
                                        mov eax, [esi + 4 * center]
                                        mov [edi + 4 * ecx], eax
                                        jmp firstWhile

                        endFirstWhile:

                secondWhile:
                        cmp left, ebx          //(left <= leftArrayEnd)
                        ja endSecondWhile
                        inc ecx
                        inc left

                        mov eax, [esi + 4 * left]    //resultArray[resultArrayBegin++] = array[left++];
                        mov [edi + 4 * ecx], eax
                        jmp secondWhile

                        endSecondWhile:

                thirdWhile:
                        mov eax, center
                        cmp eax, right                          //(center <= right)
                        ja endThirdWhile

                        inc ecx                                         //resultArray[resultArrayBegin++] = array[center++];
                        inc center
                        mov eax, [esi + 4 * center]
                        mov [edi + 4 * ecx], eax

                        jmp thirdWhile

                        endThirdWhile:

                myFor:
                        cmp edx, 0         //(int i = numElements - 1; i >= 0; i--, right--)
                        jb end

                        mov eax, [edi + 4 * edx]      //array[right] = resultArray[i];
                        mov [esi + 4 * right], eax
                        dec edx
                        dec right
                        jmp myFor

                end:

        }


}



int main()
{
        int * pole;
        pole = (int*)malloc(4 * sizeof(int));
        pole[0] = 3;
        pole[1] = 2;
        pole[2] = 1;
        pole[3] = 5;


        Merge_sort_asm(pole, 0, 3);

        system("pause");

        return 0;
}
 
Nahoru Odpovědět
11.5.2016 17:20
Avatar
švrčajs
Člen
Avatar
švrčajs:12.5.2016 1:30

Upravíl jsem to na

#include <stdint.h>
#include <stdio.h>
#include <malloc.h>
#include <stdlib.h>
#include <malloc.h>
/*
private void mergeSort(int[] array, int left, int right)
{

        if (left != right)
        {
                //split the array into 2
                int center = (left + right) / 2;

                //sort the left and right array
                mergeSort(array, left, center);
                mergeSort(array, center + 1, right);

                //merge the result
                merge(array, left, center + 1, right);
        }
}*/
void Merge(int * pole, unsigned int left, unsigned int center, unsigned int right);


void Merge_sort_asm(int * pole, unsigned int left, unsigned int right)
{
        _asm
        {
                mov eax, left
                cmp eax, right
                je end
                xor eax, eax

                mov eax, left
                add eax, right
                mov ebx, 2
                xor edx, edx
                idiv ebx
                mov edx, eax     // edx = "pivot" (( left + right ) /2)

                mov esi, pole

                //volání na levou stranu
                push edx
                push left
                push esi
                call Merge_sort_asm
                add esp, 12

                //volání na pravou stranu
                inc edx // pivot+1
                push right
                push edx
                push esi
                call Merge_sort_asm
                add esp, 12

                //volání merge
                push right
                push edx
                push left
                push esi
                call Merge
                add esp, 16

                end:
        }
}


/*
private void merge(int[] array, int left, int center, int right)
{
        int leftArrayEnd = center - 1;
        int numElements = right - left + 1;
        int[] resultArray = new int[numElements];
        int resultArrayBegin = 0;

        while (left <= leftArrayEnd && center <= right)
        {
                if (array[left] <= array[center])
                {
                        resultArray[resultArrayBegin++] = array[left++];
                }
                else
                {
                        resultArray[resultArrayBegin++] = array[center++];
                }
        }

        while (left <= leftArrayEnd)
        {
                resultArray[resultArrayBegin++] = array[left++];
        }

        while (center <= right)
        {
                resultArray[resultArrayBegin++] = array[center++];
        }

        for (int i = numElements - 1; i >= 0; i--, right--)
        {
                array[right] = resultArray[i];
        }
}
*/

void Merge(int * pole, unsigned int left, unsigned int center, unsigned int right)
{
        int * buffer;
        buffer = pole = (int*)malloc(((right - left) + 1) * sizeof(int));//jelikož bude využíváno hodně registrů, pole je nadefinované v C
        _asm
        {
                // ebx = left end
                mov ebx, center
                dec ebx
                //počet elemntů
                mov edx, right
                sub edx, left
                add edx, 1

                mov edi, buffer
                mov esi, pole
                //ecx = index pro while---resultarraybegin
                mov ecx, 0

                firstWhile:
                        //ověření podmínek whilu
                        mov eax, left
                        cmp eax, ebx                            //left <= leftArrayEnd, když neplatí, konec cyklu, když platí tak ověř
                        ja endFirstWhile
                        mov eax, center
                        cmp eax, right                          //center <= right, když platí dělej, když né, končíš
                        ja endFirstWhile
                        xor eax, eax                            //vynulování eax...

                                push ebx
                                mov ebx, left
                        mov eax, [esi + 4 * ebx]   // eax = pole[left]
                                mov ebx, center
                        cmp eax, [esi + 4 * ebx]
                                pop ebx
                        ja firstWhileElse                       //když je pole[center] vetši, proveď else větev

                        inc left
                        inc ecx
                                push ebx
                                mov ebx, left
                        mov eax, [esi + 4 * ebx]
                                pop ebx
                        mov [edi + 4 * ecx], eax    //buffer[index++] = pole[left++]
                        jmp firstWhile

                                firstWhileElse:        //resultArray[resultArrayBegin++] = array[center++];
                                        inc ecx
                                        inc center
                                                push ebx
                                                mov ebx, center
                                        mov eax, [esi + 4 * ebx]
                                                pop ebx
                                        mov [edi + 4 * ecx], eax
                                        jmp firstWhile

                        endFirstWhile:

                secondWhile:
                        cmp left, ebx          //(left <= leftArrayEnd)
                        ja endSecondWhile
                        inc ecx
                        inc left

                        mov eax, [esi + 4 * left]    //resultArray[resultArrayBegin++] = array[left++];
                        mov [edi + 4 * ecx], eax
                        jmp secondWhile

                        endSecondWhile:

                thirdWhile:
                        mov eax, center
                        cmp eax, right                          //(center <= right)
                        ja endThirdWhile

                        inc ecx                                         //resultArray[resultArrayBegin++] = array[center++];
                        inc center
                                push ebx
                                mov ebx, center
                        mov eax, [esi + 4 * ebx]
                                pop ebx
                        mov [edi + 4 * ecx], eax

                        jmp thirdWhile

                        endThirdWhile:

                myFor:
                        cmp edx, 0         //(int i = numElements - 1; i >= 0; i--, right--)
                        jb end

                        mov eax, [edi + 4 * edx]      //array[right] = resultArray[i];
                                push ebx
                                mov ebx, right
                        mov [esi + 4 * ebx], eax
                                pop ebx
                        dec edx
                        dec right
                        jmp myFor

                end:

        }


}



int main()
{
        int * pole;
        pole = (int*)malloc(4 * sizeof(int));
        pole[0] = 3;
        pole[1] = 2;
        pole[2] = 1;
        pole[3] = 5;


        Merge_sort_asm(pole, 0, 3);

        system("pause");

        return 0;
}

ale i tak mi to hází v tom For cyklu error..

 
Nahoru Odpovědět
12.5.2016 1:30
Avatar
švrčajs
Člen
Avatar
švrčajs:13.5.2016 16:23

Jelikož jsem se v tom přestal už orientovat, napsal jsem novou verzi, podle jiného pseudokodu... Opravil jsem chyby v rekurzi (podmínky ukončení) + pozicování v polích + vypsání co kam merge přiřazuje. Ale co už nevím, jak upravit je, když chci přistoupit k prvku v předaném poli (ecx + 4 * esi) esi = 0, tak mi to hodí error:
Exception thrown: read access violation.

pole was 0xCD134750.

If there is a handler for this exception, the program may be safely continued.

v prvním foru, funkce merge, vše proběhne v pořádku, ale v druhém foru, vyskočí tato chyba... A nevidím tam nikde chybu :(

nový kod:

#include <stdint.h>
#include <stdio.h>
#include <malloc.h>
#include <stdlib.h>
#include <malloc.h>

//čerpáno z http://csg.sph.umich.edu/abecasis/class/2006/615.09.pdf, jedná se o iterativní implementaci mergesortu...

void merge(int * pole, int start, unsigned int m, int stop)
{
        char * format;
        format = "na index %i  prvek %i";
        char * format2;
        format2 = "razeni do pole index %i prvek %i";
        int * buffer;
        buffer = (int*)malloc(((stop - start) + 1) * sizeof(int));


        _asm
        {
                mov eax, buffer
                mov ecx, pole
                mov esi, start

                FirstFor:
                        cmp esi, m
                        ja EndFirstFor

                        mov ebx, [ecx + 4 * esi]
                        mov dword ptr [eax + 4 * esi], ebx

                                push ebx
                                push esi
                                push format
                                call printf


                        inc esi
                        jmp FirstFor

                        EndFirstFor:

                mov esi,m
                add esi, 1

                SecondFor:
                        cmp esi, stop
                        ja EndSecondFor

                        mov edi, m
                        add edi, 1
                        add edi, stop
                        sub edi, esi

                        mov ebx, [ecx + 4 * esi]                           //chyba !!!
                        mov dword ptr [eax + 4 * edi], ebx

                        push ebx
                        push edi
                        push format
                        call printf


                        inc esi
                        jmp SecondFor

                        EndSecondFor:

                mov esi, start   //k
                mov edi, start   //i
                mov edx, stop    //j
                //eax = buffer
                //ecx = pole
                ThirdFor:
                        cmp esi, stop
                        ja end

                        mov ebx, [eax + 4 * edx]
                        cmp ebx, [eax + 4 * edi]
                        jb isless

                        inc edi
                        mov ebx,[eax + 4 * edi]
                        mov dword ptr[ecx + 4 * esi], ebx
                        push ebx
                        push esi
                        push format2
                        call printf
                        add esp, 12


                        inc esi

                        jmp ThirdFor

                                isless:
                                        dec edx
                                        mov ebx, [eax + 4 * edx]
                                        mov dword ptr[ecx + 4 * edi], ebx

                                                push ebx
                                                push edi
                                                push format2
                                                call printf
                                                add esp, 12


                                        inc esi

                                        jmp ThirdFor


                end:
                        push eax
                        call free
                        add esp, 4

        }
}
void mergesort(int * pole, unsigned int start, unsigned int stop)
{
        _asm
        {
                mov eax, stop
                cmp eax, start


                jbe end

                mov eax, start     //eax = m
                add eax, stop
                mov ebx, 2
                xor edx, edx
                idiv ebx

                push eax

                push eax
                push start
                push pole
                call mergesort
                add esp, 12

                pop eax

                add eax, 1
                push eax

                push stop
                push eax
                push pole
                call mergesort
                add esp, 12

                pop eax
                sub eax, 1


                push stop
                push eax
                push start
                push pole
                call merge
                add esp, 16


                end:
        }
}



int main()
{
        int * pole;
        pole = (int*)malloc(3 * sizeof(int[3]));
        pole[0] = 2;
        pole[1] = 3;
        pole[2] = 1;



        mergesort(pole, 0, 2);


        for (int i = 0; i < 3; i++)
        {
                printf("%i\n", pole[i]);
        }


        system("pause");

        return 0;
}
 
Nahoru Odpovědět
13.5.2016 16:23
Avatar
Martin Dráb
Tvůrce
Avatar
Odpovídá na švrčajs
Martin Dráb:13.5.2016 19:12

No, jeden z problémů se zdá být to, že neuklízíš zásobník po zavolání printf, resp. neděláš to vždy.

Pak samozřejmě musíš mít na paměti, že registry jako EAX, ECX, EDX a EBX (a i jiné) ti může změnit funkce, kterou zavoláš (třeba onen printf) a není její povinností vrátit do nich původní hodnoty (což AFAIK platí pro ESI a EDI a EBP).

0xCD134750 je adresa, krerá může mít v rámci aplikace smysl pouzve v případě, že se jedná o 32bitovou aplikaci spuštěnou pod 64bitovým Windows a s povolením velkého adresového prostoru (/3GB).

Podle mě by pomohlo si ten kód hezky projít v debuggeru instrukce po instrukci, abys viděl, kdy se to pokazí.

Nahoru Odpovědět
13.5.2016 19:12
2 + 2 = 5 for extremely large values of 2
Avatar
švrčajs
Člen
Avatar
Odpovídá na Martin Dráb
švrčajs:13.5.2016 22:20

Kod jsem několikrát prošel, edi a esi pracují v pořádku, ostatní registry si raději uchovávám na zásobníku(asi prasácké řešení?), aby nedocházelo ke změnám, ale pak tam dojde k chybě, při přiřazení prvku do ebx, i když jsou indexy a adresy správné, viz kod.. Tisknutí jsem raději zakomentoval

#include <stdint.h>
#include <stdio.h>
#include <malloc.h>
#include <stdlib.h>
#include <malloc.h>

//čerpáno z http://csg.sph.umich.edu/abecasis/class/2006/615.09.pdf, jedná se o iterativní implementaci mergesortu...

void merge(int * pole, int start, unsigned int m, int stop)
{
        char * format;
        format = "na index %i  prvek %i";
        char * format2;
        format2 = "razeni do pole index %i prvek %i";
        int * buffer;
        buffer = (int*)malloc((stop - start + 1) *sizeof(int));
        for (int i = 0; i < (stop - start + 1); i++)
        {
                buffer[i] = 0;
        }

        _asm{

                mov ecx, pole
                mov eax, buffer
                push ecx
                push eax
                mov esi, start

                FirstFor:
                        cmp esi, m
                        ja EndFirstFor
                                //lea ecx, pole
                                //lea esi, start
                                pop eax
                                pop ecx
                        mov ebx, [ecx + 4 * esi]
                        mov [eax + 4 * esi], ebx
                                push ecx
                                push eax
                                /*push ebx
                                push esi
                                push format
                                call printf*/


                        inc esi
                        jmp FirstFor

                        EndFirstFor:

                mov esi,m
                add esi, 1


                SecondFor:
                        cmp esi, stop
                        ja EndSecondFor
                        //lea eax, buffer
                        //lea ecx, pole

                        mov edi, m
                        add edi, 1
                        add edi, stop
                        sub edi, esi
                                pop eax
                                pop ecx
                        mov ebx, [ecx + 4 * esi]
                        mov [eax + 4 * edi], ebx
                                push ecx
                                push eax
                        /*
                        push ebx
                        push edi
                        push format
                        call printf*/


                        inc esi
                        jmp SecondFor

                        EndSecondFor:

                mov esi, start   //k
                mov edi, start   //i
                mov edx, stop    //j
                //eax = buffer
                //ecx = pole


                push edx
                ThirdFor:
                        //lea eax, buffer
                        //lea ecx, pole

                        cmp esi, stop
                        jnbe end
                                pop edx
                                pop eax
                                pop ecx
                        mov ebx, [eax + 4 * edx]

                        cmp ebx, [eax + 4 * edi]
                        jb isless


                        inc edi
                        mov ebx,[eax + 4 * edi]      ///při druhém průchodu esi edi = 2, eax má furt stejnou hodnotu(adresu), ale i tak se do ebx uloží nesmyslně veliké čílo: 4261281277
                        mov [ecx + 4 * esi], ebx

                                /*push ebx
                        push esi
                        push format2
                        call printf
                        add esp, 12*/


                        inc esi
                                push ecx
                                push eax
                                push edx

                        jmp ThirdFor

                                isless:
                                                pop edx
                                                pop eax
                                                pop ecx
                                        dec edx
                                        //lea eax, buffer
                                        //lea ecx, pole
                                        mov ebx, [eax + 4 * edx]
                                        mov [ecx + 4 * edi], ebx
                                                        //push edx
                                                /*push ebx
                                                push edi
                                                push format2
                                                call printf
                                                add esp, 12*/


                                        inc esi
                                                        push ecx
                                                        push eax
                                                        push edx
                                        jmp ThirdFor


                end:
                        pop edx
                        pop eax
                        pop ecx

        }
}
void mergesort(int * pole, unsigned int start, unsigned int stop)
{
        _asm
        {
                mov eax, stop
                cmp eax, start


                jbe end

                mov eax, start     //eax = m
                add eax, stop
                mov ebx, 2
                xor edx, edx
                idiv ebx


                push eax

                push eax
                push start
                push pole
                call mergesort
                add esp, 12

                pop eax

                add eax, 1
                push eax

                push stop
                push eax
                push pole
                call mergesort
                add esp, 12

                pop eax
                sub eax, 1


                push stop
                push eax
                push start
                push pole
                call merge
                add esp, 16


                end:

        }
}



int main()
{
        int * pole;
        pole = (int*)malloc(3 * sizeof(int[3]));
        pole[0] = 2;
        pole[1] = 3;
        pole[2] = 1;



        mergesort(pole, 0, 2);


        for (int i = 0; i < 3; i++)
        {
                printf("%i\n", pole[i]);
        }


        system("pause");

        return 0;
}
Editováno 13.5.2016 22:23
 
Nahoru Odpovědět
13.5.2016 22:20
Avatar
švrčajs
Člen
Avatar
Odpovídá na Martin Dráb
švrčajs:14.5.2016 14:08

Jsem kus vola :D Na merge jsem použil špatný pseudokod, který počítal s tím, že buffer bude stejně velký jako pole... Takže jsem našel správný pseudokod, přepsal do asm a ejhle :D žádné chybové hlášky.. Ale nastal mi tam problém s tím, že po setřídění mi to vypíše 1,3,1... ale vstup byl 5,3,1... chyba je, že se v posledním cyklu, 1 prvním průchodu uloží do pole 3 3 1 a 5 zmizí :D

kod teď vypadá takto:

#include <stdint.h>
#include <stdio.h>
#include <malloc.h>
#include <stdlib.h>
#include <malloc.h>

//čerpáno z http://csg.sph.umich.edu/abecasis/class/2006/615.09.pdf, jedná se o iterativní implementaci mergesortu...

void merge(int * pole, int start, unsigned int m, int stop)
{

        int * buffer;
        buffer = (int*)malloc(((stop - start) + 1) * sizeof(int));
        for (int i = 0; i < (stop - start + 1); i++)
        {
                buffer[i] = 0;
        }

        _asm {
                mov esi, start  //i

                mov edi, m              //j
                add edi, 1

                mov edx, 0              //k

                mov eax, pole
                mov ecx, buffer

                FirstWhile:
                        cmp esi, m                                      //ověření( i<= mid  && j <= end)
                                ja EndFirstWhile
                        cmp edi, stop
                                ja EndFirstWhile

                                mov ebx, [eax + 4 * esi]
                                cmp ebx, [eax + 4 * edi]
                                        jge FirstWhileElse

                                mov[ecx + 4 * edx], ebx //buffer[k] = pole[i]
                                inc edx
                                inc esi
                                jmp FirstWhile

                                        FirstWhileElse:
                                                mov ebx, [eax + 4 * edi]    //pole[j]
                                                mov[ecx + 4 * edx], ebx
                                                inc edi
                                                inc edx
                                                jmp FirstWhile

                        EndFirstWhile:

                SecondWhile:
                        cmp esi, m
                                ja EndSecondWhile
                        mov ebx, [eax + 4 * esi]
                        mov[ecx + 4 * edx], ebx     //buffer[k] = pole[i]
                                inc esi
                                inc edx
                                jmp SecondWhile

                        EndSecondWhile:

                ThirdWhile:
                        cmp edi, stop
                                ja EndThirdWhile
                        mov ebx, [eax + 4 * edi]
                        mov [ecx + 4 * edx], ebx    //buffer[k] = pole[j]
                                inc edi
                                inc edx
                                jmp ThirdWhile

                        EndThirdWhile:

                mov esi, start   //i
                mov edx, 0               //k
                mov ebx, stop         //ebx = délka buffer, proto pak ukládat na zásobní a využít ebx pro temp, při přehazovaní pole...
                sub ebx, start

                push ebx

                FourthWhile:
                        pop ebx
                        cmp edx, ebx
                                jae End
                        cmp esi, stop
                                jae End

                        push ebx
                        mov ebx, [ecx + 4 * edx]
                        mov [eax + 4 * esi], ebx

                        inc edx
                        inc esi
                        jmp FourthWhile


                End:



        }
}
void mergesort(int * pole, unsigned int start, unsigned int stop)
{
        _asm
        {
                mov eax, stop
                cmp eax, start


                jbe end

                mov eax, start     //eax = m
                add eax, stop
                mov ebx, 2
                xor edx, edx
                idiv ebx


                push eax

                push eax
                push start
                push pole
                call mergesort
                add esp, 12

                pop eax

                add eax, 1
                push eax

                push stop
                push eax
                push pole
                call mergesort
                add esp, 12

                pop eax
                sub eax, 1

                push eax

                push stop
                push eax
                push start
                push pole
                call merge
                add esp, 16

                pop eax
                end:

        }
}



int main()
{
        int * pole;
        pole = (int*)malloc(3 * sizeof(int[3]));
        pole[0] = 5;
        pole[1] = 3;
        pole[2] = 1;



        mergesort(pole, 0, 2);


        for (int i = 0; i < 3; i++)
        {
                printf("%i\n", pole[i]);
        }


        system("pause");

        return 0;
}
 
Nahoru Odpovědět
14.5.2016 14:08
Avatar
švrčajs
Člen
Avatar
švrčajs:14.5.2016 15:09

Už vím, kde je chyba :D v tom čtvrtém whilu místo podmínek jae umístit ja a funguje :D

#include <stdint.h>
#include <stdio.h>
#include <malloc.h>
#include <stdlib.h>
#include <malloc.h>



void merge(int * pole, int start, unsigned int m, int stop)
{

        int * buffer;
        buffer = (int*)malloc(((stop - start) + 1) * sizeof(int));
        for (int i = 0; i < (stop - start + 1); i++)
        {
                buffer[i] = 0;
        }

        _asm {
                mov esi, start  //i

                mov edi, m              //j
                add edi, 1

                mov edx, 0              //k

                mov eax, pole
                mov ecx, buffer

                FirstWhile:
                        cmp esi, m                              //ověření( i<= mid  && j <= end)
                                ja EndFirstWhile
                        cmp edi, stop
                                ja EndFirstWhile

                                mov ebx, [eax + 4 * esi]
                                cmp ebx, [eax + 4 * edi]
                                        jge FirstWhileElse

                                mov[ecx + 4 * edx], ebx //buffer[k] = pole[i]
                                inc edx
                                inc esi
                                jmp FirstWhile

                                        FirstWhileElse:
                                                mov ebx, [eax + 4 * edi]    //pole[j]
                                                mov[ecx + 4 * edx], ebx
                                                inc edi
                                                inc edx
                                                jmp FirstWhile

                        EndFirstWhile:

                SecondWhile:
                        cmp esi, m
                                ja EndSecondWhile
                        mov ebx, [eax + 4 * esi]
                        mov[ecx + 4 * edx], ebx     //buffer[k] = pole[i]
                                inc esi
                                inc edx
                                jmp SecondWhile

                        EndSecondWhile:

                ThirdWhile:
                        cmp edi, stop
                                ja EndThirdWhile
                        mov ebx, [eax + 4 * edi]
                        mov [ecx + 4 * edx], ebx    //buffer[k] = pole[j]
                                inc edi
                                inc edx
                                jmp ThirdWhile

                        EndThirdWhile:

                mov esi, start   //i
                mov edx, 0               //k
                mov ebx, stop         //ebx = délka buffer, proto pak ukládat na zásobní a využít ebx pro temp, při přehazovaní pole...
                sub ebx, start
                add ebx, 1
                push ebx

                FourthWhile:
                        pop ebx
                        cmp edx, ebx
                                ja End
                        cmp esi, stop
                                ja End

                        push ebx
                        mov ebx, [ecx + 4 * edx]
                        mov [eax + 4 * esi], ebx

                        inc edx
                        inc esi
                        jmp FourthWhile


                End:



        }
}
void mergesort(int * pole, unsigned int start, unsigned int stop)
{
        _asm
        {
                mov eax, stop
                cmp eax, start


                jbe end

                mov eax, start     //eax = m
                add eax, stop
                mov ebx, 2
                xor edx, edx
                idiv ebx


                push eax

                push eax
                push start
                push pole
                call mergesort
                add esp, 12

                pop eax

                add eax, 1
                push eax

                push stop
                push eax
                push pole
                call mergesort
                add esp, 12

                pop eax
                sub eax, 1

                push eax

                push stop
                push eax
                push start
                push pole
                call merge
                add esp, 16

                pop eax
                end:

        }
}



int main()
{
        int * pole;
        pole = (int*)malloc(10 * sizeof(int[3]));
        pole[0] = 5;
        pole[1] = 6;
        pole[2] = 1;
        pole[3] = 2;
        pole[4] = 4;
        pole[5] = 3;
        pole[6] = 10;
        pole[7] = 7;
        pole[8] = 9;
        pole[9] = 8;



        mergesort(pole, 0, 9);


        for (int i = 0; i < 9; i++)
        {
                printf("%i\n", pole[i]);
        }


        system("pause");

        return 0;
}
 
Nahoru Odpovědět
14.5.2016 15:09
Děláme co je v našich silách, aby byly zdejší diskuze co nejkvalitnější. Proto do nich také mohou přispívat pouze registrovaní členové. Pro zapojení do diskuze se přihlas. Pokud ještě nemáš účet, zaregistruj se, je to zdarma.

Zobrazeno 20 zpráv z 20.