Diskuze: Bitové pole, struktura ?
V předchozím kvízu, Online test znalostí Assembler, jsme si ověřili nabyté zkušenosti z kurzu.
š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
š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 
Protože s řešením, budu mít
problém
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
{
}
}
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
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í).
š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
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
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],5což je to stejné, jako mov [eax], n
švrčajs:11.5.2016 17:20
Tak nakonec se příprava vydařila ... 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;
}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;
}švrčajs:14.5.2016 14:08
Jsem kus vola 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 žá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í
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;
}Už vím, kde je chyba v
tom čtvrtém whilu místo podmínek jae umístit ja a funguje
#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;
}
Zobrazeno 20 zpráv z 20.