RSS Feed

Sa utilizam bubble sort …

December 29th, 2007
Posted in Programare(Visual C++) | No Comments

M-am gandit sa ma mai joc putin cu bubble sort-ul, sa-l folosesc in cadrul unei anumite probleme. Problema care mi-a venit in minte este urmatoarea : Sa se scrie o functie care primeste ca parametru un numar natural si care returneaza cel mai mare numar care se poate forma cu cifrele sale . Algoritmul banal cu care se rezolva aceasta problema este urmatorul:

-retinem cifrele numarului intr-un vector
-le ordonam
-compunem noul numar

Am implementat totul in ASM desigur. Pentru a nu mai recurge la fel de fel de artificii, am organizat vectorul in felul urmator:
v[0] - numarul de cifre
v[1] ... v[v[0] - cifrele numarului

Bineinteles, am modificat usor bubble-sort-ul ( cel scris de mine avea nevoie de 2 variabile , un pointer catre primul element al vectorului, v[0] , si numarul de elemente ... cateva modificari minore si a fost gata. O alta problema care mi-a atras atentia la bubble sort a fost urmatoarea : ce se intampla daca exista un singur element in vector ? Am vrut sa merg la f**** masa si sa-l las asa, dar atunci cand compara v[i] cu v[i+1], sare la o adresa la care nu se gaseste nimic ... eroare :) ... am prevazut acest caz in functia maxim() . Este cel mai lung programel scris de mine in ASM ( vreo 90 linii de cod ) ... Sper sa nu mai am placerea sa scriu programe atat de lungi in ASM, e foarte dificil sa caut erori, chiar si cu ajutorul debugger-ului ... Iata codul...

PLAIN TEXT
C++:
  1. #include <iostream>
  2. using namespace std;
  3.  
  4. void bubble_sort(int*)
  5. {
  6.     _asm
  7.     {
  8. bucla_mare:
  9.         mov ecx,0
  10.         mov eax,[ebp+8]
  11.         mov ebx,[eax]
  12.         add eax,4
  13. bucla_mica:
  14.         mov edx,eax
  15.         add edx,4
  16.         mov esi,[eax]
  17.         cmp esi,[edx]
  18.         ja interschimbare
  19.         jmp continua
  20. interschimbare:
  21.         push dword ptr [edx]
  22.         push dword ptr [eax]
  23.         pop dword ptr [edx]
  24.         pop dword ptr [eax]
  25.         mov ecx,1
  26.         jmp continua
  27. continua:
  28.         add eax,4
  29.         dec ebx
  30.         cmp ebx,1
  31.         jne bucla_mica
  32.         cmp ecx,1
  33.         je bucla_mare
  34.     }
  35. }
  36.  
  37. int maxim(int)
  38. {
  39.     int v[12];
  40.     _asm
  41.     {
  42.         mov eax,[ebp+8]
  43.         cmp eax,10
  44.         jb exceptie
  45.         jmp continua
  46. exceptie:
  47.         mov ecx,eax
  48.         jmp stop2
  49. continua:
  50.         mov ebx,10
  51.         mov ecx,0
  52.         lea esi,v
  53.         add esi,4
  54. bucla1:
  55.         mov edx,0
  56.         cmp eax,0
  57.         je stop1
  58.         div ebx
  59.         inc ecx
  60.         mov [esi],edx
  61.         add esi,4
  62.         jmp bucla1
  63. stop1:
  64.         lea eax,v
  65.         mov [eax],ecx
  66.         push eax
  67.         call bubble_sort
  68.         add esp,4
  69.  
  70.         mov ecx,0
  71.         mov eax,1
  72.         lea esi,v
  73.         mov ebx,[esi]
  74.         add esi,4
  75. bucla2:
  76.         cmp ebx,0
  77.         je stop2
  78.         push ecx
  79.         mov ecx,[esi]
  80.         mov edx,0
  81.         push eax
  82.         mov edi,eax
  83.         mov eax,1
  84.         mul edi
  85.         mul ecx
  86.         pop edx
  87.         pop ecx
  88.         push edx
  89.         add ecx,eax
  90.         pop eax
  91.         mov edi,10
  92.         mul edi
  93.         dec ebx
  94.         add esi,4
  95.         jmp bucla2
  96. stop2:
  97.         mov eax,ecx
  98.     }
  99. }
  100.  
  101. int main()
  102. {
  103.     int x;
  104.     cin>>x;
  105.     cout<<maxim(x)<<endl;
  106.     system("pause");
  107.     return 0;
  108. }

O mica problema in ASM … de Craciun

December 26th, 2007
Posted in Programare(Visual C++) | No Comments

Pentru ca tot era Craciunul si nu aveam ce face, m-am apucat de o mica problema in ASM ... am apelat la un coleg de facultate,Alex D., care mi-a dat urmatoarea problema : Sa se ordoneze un vector de numere naturale dupa numarul de biti necesari pentru a le scrie in baza 2 ... aveam deja bubble sort-ul implementat in asm ... Am procedat in felul urmator: stiam ca bubble sort compara, la un moment dat cate 2 elemente si verifica daca unul e mai mare ca celalalt. In loc de aceasta condiitie, eu trebuia sa aflu daca numarul de biti al primului e mai mare ca numarul de biti al celui de-al doilea... ca sa evit o seara "plina", am scris o alta functie, tot in asm , care imi returneaza numarul de biti pentru un numar. De aici totul a fost simplu ... ba nu ! Am stat o ora intreaga, uitandu-ma dupa pop-uri, push-uri, unele adrese se pierdeau, o adevarata dezordine... noroc cu prietenul meu AndreiASM ( numele spune tot :) ), care m-a ajutat cu diverse chestii tehnice pe care nu aveam de unde sa le cunosc ( apelarea unei functii cu parametri, etc. ) . In cele din urma, a rezultat codul de mai jos, care "merge", dar nu am absolut niciun chef sa ma mai bag pe el in caz ca gasesc vreo eroare...

PLAIN TEXT
C++:
  1. #include <stdio.h>
  2. #include <iostream>
  3. using namespace std;
  4.  
  5.  
  6. int nr_biti(int)
  7. {
  8.     _asm
  9.     {
  10.         mov eax,[ebp+8]
  11.         cmp eax,0
  12.         je final
  13.         mov ebx,0
  14. bucla:
  15.         cmp eax,0
  16.         je stop
  17.         inc ebx
  18.         shr eax,1
  19.         jmp bucla
  20. stop:
  21.         mov eax,ebx
  22.         jmp stop2
  23. final:
  24.         mov ebx,1
  25.         jmp stop
  26. stop2:
  27.        
  28.     }
  29. }
  30.  
  31. void bubble_sort(int*,int)
  32. {
  33.     _asm
  34.     {
  35. bucla_mare:
  36.         mov ecx,0
  37.         mov eax,[ebp+8]
  38.         mov ebx,[ebp+12]
  39. bucla_mica:
  40.         mov edx,eax
  41.         add edx,4
  42.        
  43.         push dword ptr[eax]
  44.         push dword ptr[edx]
  45.  
  46.         push eax
  47.  
  48.         mov edi,eax
  49.  
  50.         push dword ptr[edx]
  51.         call nr_biti
  52.         mov  [edx],eax
  53.         add esp,4
  54.  
  55.         push dword ptr[edi]
  56.         call nr_biti
  57.         mov [edi],eax
  58.         add esp,4
  59.  
  60.         pop eax
  61.         push ecx
  62.         mov ecx,[edi]
  63.         mov [eax],ecx
  64.         pop ecx
  65.         mov esi,[eax]
  66.         cmp esi,[edx]
  67.         ja interschimbare
  68.         cmp esi,[edx]
  69.         jle nu_e
  70.        
  71. interschimbare:
  72.         pop dword ptr[edx]
  73.         pop dword ptr[eax]
  74.         push dword ptr [edx]
  75.         push dword ptr [eax]
  76.         pop dword ptr [edx]
  77.         pop dword ptr [eax]
  78.         mov ecx,1
  79.         jmp continua
  80. nu_e:   pop dword ptr[edx]
  81.         pop dword ptr[eax]
  82.         jmp continua
  83.  
  84. continua:
  85.  
  86.         add eax,4
  87.         dec ebx
  88.         cmp ebx,1
  89.         jne bucla_mica
  90.         cmp ecx,1
  91.         je bucla_mare
  92.     }
  93. }
  94.  
  95. int main()
  96. {
  97.     int v[100],n,i;
  98.     cin>>n;
  99.     for(i=0;i<n;i++) cin>>v[i];
  100.     bubble_sort(v,n);
  101.     for(i=0;i<n;i++) cout<<v[i]<<' ';
  102.     system("pause");
  103.     return 0;
  104. }

Use the stack , Luke !

December 23rd, 2007
Posted in Programare(Visual C++) | No Comments

Lucrez de foarte putin timp timp in ASM si , cum imi sta mie mai bine, imi place sa ma complic al naibii de tare cand rezolv o problema... de exemplu, azi m-am gandit la urmatoarea problema in ASM : se da un vector de numere intregi. Sa se scrie o functie in ASM care inverseaza elementele vectorului .
Ok . Bag in registrul eax adresa elementului curent, calculez cati bytes trebuie sa sar ca sa ajung la ultimul element, fac o bucla, sar la elementul al doilea, calculez cati bytes am nevoie sa sar la penultimul ... etc., nervi, pana la urma adaug un sub edx,ecx ... minune, merge. De ce? Nu ma mai intereseaza... Merge si atat. Iata minunatul cod:

PLAIN TEXT
C++:
  1. void inversare(int*,int)
  2. {
  3.     _asm
  4.     {
  5.         mov ecx,0
  6.         mov ebx,[ebp+12]
  7.         shr ebx,1
  8.         dec ebx
  9. bucla:
  10.         mov eax,[ebp+8]
  11.        
  12.         push ecx
  13.         shl ecx,2
  14.         add eax,ecx
  15.         pop ecx
  16.        
  17.         mov edx,[ebp+12]
  18.         dec edx
  19.         sub edx,ecx
  20.         sub edx,ecx
  21.         shl edx,2
  22.  
  23.         push eax
  24.         add eax,edx
  25.         mov edx,eax
  26.         pop eax
  27.  
  28.         push dword ptr [eax]
  29.         push dword ptr [edx]
  30.         pop dword ptr [eax]
  31.         pop dword ptr [edx]
  32.    
  33.         cmp ecx,ebx
  34.         jne continua
  35.         cmp ecx,ebx
  36.         je stop
  37. continua:
  38.          inc ecx
  39.          jmp bucla
  40. stop:
  41.     }
  42. }

Ok... , ma minunam si eu de cat de frumos e codul asta ... ma simteam mandru... USE THE STACK LUKE... mi-am adus aminte de Star Wars ... si de o mica chestie numite STIVA... care avea interesenta proprietate ca ultimul intrat era primul iesit . Sa vezi si sa nu crezi ... exact ce-mi trebuia mie . :)) Mi-am tras o palma peste cap, am pornit alt proiect, am scris repede codul, a rezultat cel de mai jos. Elegant, simplu, fara shiftari de biti sau alte magarii ...

PLAIN TEXT
C++:
  1. void inverseaza2(int*,int)
  2. {
  3.     _asm
  4.     {
  5.         mov eax,[ebp+8]
  6.         mov ecx,[ebp+12]
  7.         mov edx,0
  8. bucla:
  9.         cmp edx,ecx
  10.         je final
  11.         push dword ptr [eax]
  12.         add eax,4
  13.         inc edx
  14.         jmp bucla
  15. final:
  16.         mov eax,[ebp+8]
  17.         mov edx,0
  18. bucla2:
  19.         cmp edx,ecx
  20.         je final2
  21.         pop dword ptr [eax]
  22.         add eax,4
  23.         inc edx
  24.         jmp bucla2
  25. final2:
  26.     }
  27. }

De acum incolo voi folosi stiva !
De acum incolo voi folosi stiva !
De acum incolo voi folosi stiva !
De acum incolo voi folosi stiva !
De acum incolo voi folosi stiva !
De acum incolo voi folosi stiva !

Bubble Sort - ASM

December 20th, 2007
Posted in Programare(Visual C++) | 1 Comment

Astazi am reusit , cu ajutor ce-i drept ( din partea prof. meu de arhitectura ), sa implementez ultra-performantul, ultra-schimbistul si nemaipomenitul Bubble Sort . Il pun aici, in speranta ca mai exista cineva care este interesat de ASM ...

PLAIN TEXT
C++:
  1. void bubble_sort(int*,int)
  2. {
  3.     _asm
  4.     {
  5. bucla_mare:
  6.         mov ecx,0
  7.         mov eax,[ebp+8]
  8.         mov ebx,[ebp+12]
  9. bucla_mica:
  10.         mov edx,eax
  11.         add edx,4
  12.         mov esi,[eax]
  13.         cmp esi,[edx]
  14.         ja interschimbare
  15.         jmp continua
  16. interschimbare:
  17.         push dword ptr [edx]
  18.         push dword ptr [eax]
  19.         pop dword ptr [edx]
  20.         pop dword ptr [eax]
  21.         mov ecx,1
  22.         jmp continua
  23. continua:
  24.         add eax,4
  25.         dec ebx
  26.         cmp ebx,1
  27.         jne bucla_mica
  28.         cmp ecx,1
  29.         je bucla_mare
  30.     }
  31. }

Primul parametru al functiei este un pointer catre primul element al vectorului, al doilea parametru reprezentand numarul de elemente din vector .
Functia se poate apela in felul urmator:

PLAIN TEXT
C++:
  1. int v[100],n,i;
  2. citeste n
  3. citeste componentele vectorului
  4. bubble_sort(v,n);

Functie cu numar variabil de parametri - C/C++/ASM

December 15th, 2007
Posted in Programare(Visual C++) | No Comments

In topicul anterior am vorbit despre modurile in care putem extrage parametrii de pe stiva. Cum in C nu puteam sti exact cati parametri sa luam, am apelat la 2 artificii . Ori stiam cati parametri urmau sa apara, ori stiam unde sa ne oprim . C/C++ -ul nu permite in mod normal sa cunoastem numarul de parametri cu care am apelat o functie ( cu numar variabil de parametri ) . Insa acest lucru se poate rezolva cu ajutorul ASM. Nu vom mai folosi stdarg.h , prin urmare nu mai avem nevoie de acel prim parametru static al functiei. Urmatoarea functie afiseaza toti parametrii cu care a fost apelata...

PLAIN TEXT
C++:
  1. void functie(...)
  2. {
  3.     unsigned char nr_parametri;
  4.     int *parametru,i;
  5.  
  6.     _asm
  7.     {
  8.         mov eax,[ebp+4]
  9.         add eax,2
  10.         mov al,[eax]
  11.         shr al,2
  12.         mov nr_parametri,al
  13.         mov parametru,ebp
  14.         add parametru,8
  15.     }
  16.  
  17. for(i=0;i<nr_parametri;i++)
  18. cout<<parametru[i]<<" ";
  19. }

Acum,in vectorul parametru, avem toti parametrii si ne putem juca dupa cum dorim cu ei ... va ramane ca tema sa modificati functia astfel incat sa calculeze suma :D

Functie cu numar variabil de parametri - C/C++

December 15th, 2007
Posted in Programare(Visual C++) | No Comments

Ok, am realizat acest lucru in C#, am vazut cat de simplu se poate realiza, intrebarea se pune in felul urmator: mai putem realiza la fel de usor acest lucru si in C/C++ ?
Putina teorie , pentru inceput. Atunci cand apelam o functie cu anumiti parametri, acestia sunt luati de pe stiva. Daca avem 2 parametri, luam 2 parametri de pe stiva, daca avem 3, luam 3, dar daca avem un numar variabil de parametri , cati vom lua de pe stiva? Se profileaza astfel urmatoarele probleme:
1.O functie care sa ia de pe stiva exact cati parametrii cu care a fost apelata functia
2.O functie care sa stie cumva unde sa se opreasca cand cauta parametrii.

Prima problema va fi discutata separat intr-un alt topic ( fiind mai dificil de inteles ).
In primul rand, in C/C++ numarul variabil de parametri se pune in evidenta prin utilizarea "..." ( trei puncte, foarte sugestiv ). Problema este ca nu putem avea direct un numar variabil de parametri, ci neaparat un parametru care este stabil. Sa trecem in continuare la modul in care putem lua parametrii de pe stiva. Avem doua optiuni. Ori stim de dinainte cati parametri vom avea , ori stim cand sa ne oprim. De exemplum, pentru calcularea sumei a n numere, putem apela in felul urmator:

PLAIN TEXT
C++:
  1. cout<<suma(5,1,2,3,4,7);

Primul parametru,5, reprezinta numar parametrilor ( "variabil" :D ) .

PLAIN TEXT
C++:
  1. cout<<suma(1,2,3,4,7,0);

Ultimul parametru l-am pus 0 ( element neutru la adunare ) . Atunci cand dam de el, stim sa ne oprim ( putem pune absolut orice care sa se potriveasca problemei noastre , doar trebuie sa stim cand sa ne oprim ).Sa scriem doua functii care sa implementeze cele doua concepte. Sa incepem cu prima functie, cea in care cunoastem cati parametri vom avea:

PLAIN TEXT
C++:
  1. int functie(int prim,...)
  2. {
  3.     int contor=1,val,suma=0;
  4.     va_list marker;
  5.     va_start(marker,prim);
  6.     while(contor<=prim)
  7.     {
  8.         val=va_arg(marker,int);
  9.         suma+=val;
  10.         contor++;
  11.     }
  12.     return suma;   
  13. }

Sa scriem aceeasi functie, care de data asta se va opri cand va gasi parametrul 0 :

PLAIN TEXT
C++:
  1. int functie(int prim,...)
  2. {
  3.     int val=1,suma=0;
  4.     va_list marker;
  5.     va_start(marker,prim);
  6.     suma+=prim;
  7.     while(val!=0)
  8.     {
  9.         val=va_arg(marker,int);
  10.         suma+=val;
  11.     }
  12.     return suma;   
  13. }

Pentru ca functiile de mai sus sa functioneze, trebuie sa includeti linia:

PLAIN TEXT
C++:
  1. #include <stdarg.h>

Functie cu numar variabil de parametri - C#

December 14th, 2007
Posted in Programare(Visual C++) | 4 Comments

Sa continuam discutia despre numarul parametri cu acesta noua problema , o functie cu numar variabil de parametri. Ce inseamna acest lucru mai exact ? In mod normal, pana acum cand scriati o functie care primea parametri, scriati in felul urmator:

PLAIN TEXT
C++:
  1. tip nume(tip nume,tip nume ... tip,nume)
  2. {}

Ce se intampla daca nu stiu de dinainte de cati parametri voi avea nevoie ? Sa zicem ca as dori sa apelez in felul urmator:

PLAIN TEXT
C++:
  1. ...
  2. functie(1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17);

Probabil ca unii dintre voi deja s-au apucat sa declare parametrii ( :) ) . Sau sa luam un alt exemplu, mai practic. Ce face urmatoarea functie?

PLAIN TEXT
C++:
  1. int a,b;
  2. a=10;
  3. b=20;
  4. Console.Write("a={0} si b={1}", a, b);

Sau , mai general, urmatorul exemplu:

PLAIN TEXT
C++:
  1. int a = 1;
  2. string b = "text";
  3. float c=1.23f;
  4. double d=11111111000;
  5. Console.Write("a={0} si b={1} si c={2} si d={3}", a, b, c, d);

Exista situatii, unele mai practice decat altele, in care nu stim de la inceput cati parametri va avea functia. Mai mult de atat, poate stim de dinainte cati parametri va avea functia, dar nu stim care este tipul lor. Un caz "celebru" este cel al programatorului anonim,amator de Coca-Cola, cu ochii inrositi, care isi doreste sa aiba o functie pentru care nu stie nici numarul nici tipul parametrilor ( cu toate ca, in practica, asa ceva nu exista , utilizatorul intotdeauna va introduce datele necesare ). Pot spune ca este mai mult un "moft" ( interesant moft totusi ) .
Din fericire, C#-ul ne rezolva toate probleme, punandu-le la dispozitie o metoda speciala de transmitere a parametrilor.Dupa cum probabil stiti din C++, putem transmite parametri prin valoare sau prin referinta. C#-ul introduce o noua modalitate de transmitere, special realizata pentru lucrul cu numarul variabil de parametri, si anume "params".

PLAIN TEXT
C++:
  1. static void functie(params[] int parametri)

In acest exemplu, am specificat faptul ca functia primeste un numar variabil de parametri de tip "int". "Variabil", nu prea putem spune deoarece putem cunoaste numarul lor

PLAIN TEXT
C++:
  1. int nr_parametri=parametri.Length;

Exemplu de program care apeleaza o functie cu un numar variabil de parametri de tip int si calculeaza suma lor:

PLAIN TEXT
C++:
  1. using System;
  2. using System.Collections.Generic;
  3. using System.Linq;
  4. using System.Text;
  5. namespace Parametri
  6. {
  7.     class Program
  8.     {
  9.  
  10.         static int functie(params int[] x)
  11.         {
  12.             int suma = 0,i;
  13.             for (i = 0; i <x.Length; i++)
  14.                 suma += x[i];
  15.             return suma;
  16.  
  17.         }
  18.  
  19.  
  20.         static void Main(string[] param)
  21.         {
  22.             Console.WriteLine(functie(1, 2, 3, 4));
  23.             Console.Read();
  24.  
  25.         }
  26.     }
  27. }

Acum , sa luam celalalt caz, in care nu stim nici ce tip au parametrii . Pentru acest caz, C#-ul de pune la dispozitie un tip generic, numit "object" . Aceste poate fi de orice tip ( int, string, char,float,bool, etc. ) .Antetul functiei cu numar variabil de parametri de tip variabil va fi urmatorul:

PLAIN TEXT
C++:
  1. static void functie(params object[] x)<