Implémentation de Quicksort (Assembleur Y86)

.pos 0
init:   irmovl stack,%esp # Initialisation du pointeur de la pile

        # Définition de la taille du tableau
        irmovl 9, %eax
        
        # Empilement du second paramètre pour la fonction qsort (taille du tableau)
        pushl %eax
        
        # Récupération de l'adresse du tableau
        irmovl tabdeb, %eax
        
        # Empilement du premier paramètre pour la fonction qsort (adresse du tableau)
        pushl %eax
        
        # Appelle la fonction qsort
        call qsort
        
        # Nettoyage des paramètres
        iaddl 8, %esp
        
        halt # Fin du programme






# Pivot : met tout les éléments inférieurs ou égaux du pivot au début du tableau et ceux supérieurs a la fin 

# ----------------- Fonction pivot-------------------------------
pivot: 
        # Sauvegarde des callee save
        pushl %ebx # sauvegarde de ebx
        pushl %esi # sauvegarde de esi
        pushl %edi # sauvegarde de edi

        # Récupération des paramètres
        mrmovl 16(%esp), %esi # Récupération de l'adresse du début de l'intervalle à trier
        mrmovl 20(%esp), %edi # Récupération de l'adresse de la fin de l'intervalle à trier
        mrmovl 24(%esp), %ecx # Récupération de la valeur du pivot
        
boucle:     
        
        # Condition d'arret : les 2 pointeurs se croisent
        rrmovl %esi, %ebx # on copie esi dans ebx (temp)
        subl %edi, %ebx # comparaison indice debut - indice fin
        jg fin # Si indice début >= indice fin -> ils se sont croisés : condition d'arret
        
        
        
        
        mrmovl (%esi), %ebx # Récupération de la valeur à l'indice du départ
        subl %ecx, %ebx # Comparaison de l'élément du départ avec le pivot
        
        

        jg dgp # Si l'élément du départ est plus grand que le pivot 
        
        # valeur <= pivot
        iaddl 4, %esi # On incrémente le début car on sait que la valeur qu'on vient d'ajouter est au bon endroit
        jmp boucle # On continue la boucle
        


dgp:
    mrmovl (%esi), %ebx # lecture de l'élément à déplacer vers la zone haute
    mrmovl (%edi), %edx # lecture de l'élément à déplacer vers la zone basse
    
    rmmovl %edx, (%esi) # Placement de la petite valeur à l'indice de gauche
    rmmovl %ebx, (%edi) # Placement de la grande valeur à l'indice de droite
    
    
    isubl 4, %edi # On décrémente la fin car on sait que la valeur qu'on vient d'ajouter est au bon endroit
    jmp boucle # On continue la boucle sans avancer esi
    

fin: # arret le programme
    # Placement de l'adresse du premier élément de la zone haute dans %eax 
    rrmovl %esi, %eax
    # Une case avant %esi pour avoir le dernier élément de la zonne basse dans eax
    isubl 4, %eax
    
    # Restauration des callee_save
    popl %edi # Restauration de %edi
    popl %esi # Restauration de %esi
    popl %ebx # Restauration de %ebx
    ret
# ----------------- Fin Fonction pivot-------------------------------


# qsaux deb fin : prend l'élément à l'adresse deb comme pivot, appelle pivot sur deb+4, fin
puis échange deb avec la dernière valeur de la partie basse (nommé F). 
S'appelle récursivement avec deb+4 F-4 et aussi récursivement avec F+4, fin.
# ----------------- Fonction Qsaux-------------------------------

qsaux:
    # Sauvegarde tous les callee save
    pushl %ebx # Sauvegarde de ebx 
    pushl %esi # Sauvegarde de esi
    pushl %edi # Sauvegarde de edi
    pushl %ebp # Sauvegarde de ebp
    
    # ---- RECUPERATION DES PARAMETRE ----
    
    # Récupération de l'adresse du début du tableau (PIVOT)
    mrmovl 20(%esp), %ebp
    
    # Récupération de la valeur du pivot
    mrmovl (%ebp), %ecx
    
    # Récupération de  l'adresse de fin du tableau
    mrmovl 24(%esp), %edi
    
    # Copie de l'adresse du tableau
    rrmovl %ebp, %esi 
    
    # Avance d'une case (car la première est le pivot)
    iaddl 4, %esi
    
    
    
    # ---- CONDITION D'ARRET : TABLEAU DE 1 CASE ----
    
    # Copie du début du tableau dans ebx
    rrmovl %ebp, %ebx
    
    # soustraction des adresses du début et de la fin du tableau
    subl %edi, %ebx
    
    # Si les deux adresses sont égales, le tableau fait une case
    jge arret_rec
    
    
    
    
    # ---- APPEL DE PIVOT ----
    
    # Passage de la valeur du pivot en paramètre
    pushl %ecx
    
    # Passage de la fin du tableau en paramètre 
    pushl %edi
    
    # Passage du début du tableau en paramètre 
    pushl %esi
    
    # Appel de la fonction pivot
    call pivot
    
    # Nettoyage la pile des paramètres
    iaddl 12, %esp
    
    # ---- ECHANGE DU PIVOT ET DE LA VALEUR ----
    # L'adresse du dernier élément de la partie basse est dans eax
    # On échange les éléments d'adresse %ebp et %eax
    
    mrmovl (%eax), %ebx # Récupération du dernier élément de la partie basse
    mrmovl (%ebp), %edx # Récupération de la valeur du pivot
    
    rmmovl %ebx, (%ebp) # Déplacement de la valeur du dernier élément de la partie basse à la place du pivot 
    rmmovl %edx, (%eax) # Déplacement du pivot à sa bonne place dans le tableau
    
    # Ici on a la valeur d'adresse eax au bon endroit.
    
    # ---- APPEL RECUSRIF DE QSAUX SUR [debut, %eax-1] ----
    
    # Récupération de l'adresse du dernier élement de la partie basse dans ebx
    rrmovl %eax, %ebx 
    
    # retire 4 octets à %ebx pour avoir l'indice d'avant le pivot (au bon endroit)
    isubl 4, %ebx
    
    # Passage de la fin du tableau en paramètre
    pushl %ebx 
    
    # Passage du début du tableau en paramètre
    pushl %ebp
    
    # Appel récursif de qsaux
    call qsaux
    
    # Nettoyage de la pile
    iaddl 8, %esp
    
    # ---- APPEL RECUSRIF DE QSAUX SUR [%eax+1, fin] ----
    
    # Récupération de l'adresse du dernier élement de la partie basse dans ebx
    rrmovl %eax, %ebx 
    
    # Ajout 4 octets à %ebx pour avoir l'indice d'après le pivot (au bon endroit)
    iaddl 4, %ebx
    
    # Passage de la fin du tableau en paramètre
    pushl %edi 
    
    # Passage du début du tableau en paramètre
    pushl %ebx
    
    # Appel récursif de qsaux
    call qsaux
    
    # Nettoyage de la pile
    iaddl 8, %esp
    
    
arret_rec:
    # Restauration des callee_save
    popl %ebp # Restauration de ebp
    popl %edi # Restauration de edi
    popl %esi # Restauration de esi
    popl %ebx # Restauration de ebx

    ret # On return
    
    
    


# qsort : prépare l'appel de qsaux  
# ----------------- Fonction Qsort-------------------------------

qsort: 
    # Récupération du premier paramètre : l'adresse du tableau
    mrmovl 4(%esp), %edx
    
    # Récupération du deuxième paramètre : la taille du tableau
    mrmovl 8(%esp), %ecx 
    
    # ecx * 4 pour calculer le nombre d'octets entre le début et la fin du tableau
    isubl 1, %ecx # ecx - 1 pour ne pas compter la première
    addl %ecx, %ecx # ecx * 2
    addl %ecx, %ecx # ecx * 2
    
    # Copie de l'adresse du début du tableau
    rrmovl %edx, %eax
    
    # Ajout de la taille * 4 pour otenir l'adrese de fin
    addl %ecx, %eax


    # Pousse l'adresse de fin du tableau sur la pile pour la passer en paramètre
    pushl %eax

    # Pousse l'adresse de début du tableau sur la pile pour la passer en paramètre
    pushl %edx
    
    # Appel de la fonction qsaux
    call qsaux
    # Nettoyage de la pile des paramètres qui ont été passés.
    iaddl 8, %esp




.pos 800
        .align 4
tabdeb: .long 9 # Création du tableau de test
        .long 3
        .long 7
        .long 9
        .long 4
        .long 9
        .long 9 
        .long 2 
tabfin: .long 6


        .pos 0x200
stack: