Shell > Quicksort sur des donnes dans un tableau

CPU 386

GLOBAL _swap
GLOBAL _trier
GLOBAL _partition
EXTERN _afficherRegistres
EXTERN _afficherHex32
EXTERN _afficherUns32
EXTERN _af
EXTERN _showij

SECTION .data
        retour : DD 0x0

SECTION .text

_trier :
        PUSH EBP                        ; sauve EBP
        MOV EBP, ESP                                ; sauve la valeur ESP
        SUB ESP, 4                                          ; var temporaire pour j
        PUSHA                                                   ; sauvegarde de tout les registres

        ;if  l < r
        MOV EAX, [EBP+12]                               ; var l
        MOV EBX, [EBP+16]                               ; var r
        MOV ECX, [EBP+8]                                ; adr vecteur

        CMP EAX, EBX                                            ; si l < r on continue
        JAE fin                                                         ; sinon sort de la recursivite
       
        ; appel partition                              
        PUSH EBX                                                        ; parm 3 (r)
        PUSH EAX                                                        ; parm 2 (l)
        PUSH ECX                                                        ; parm 1 (vect)
        CALL _partition                                         ; Appel fonction partition
        MOV [EBP-4], EAX                                        ; recupere j qui etait dans EAX
        POP ECX                                                         ; retire les valeurs de la pile
        POP EAX                                                         ; .
        POP EBX                                                         ; .
       
        MOV EDX, [EBP-4]                                        ; j
        DEC EDX                                                         ; j - 1
       
        ; appel tri gauche
        ;PUSHA                                                          ; sauvegarde de tout les registre
        ;PUSH EDX                                                       ; pose (j-1) sur la pile
        ;PUSH EAX                                                       ; pose l sur la pile
        ;PUSH ECX                                                       ; pose adr vecteur sur la pile
        ;CALL _trier                                                    ; appel fonction tri gauche
        ;POP ECX                                                                ; depile
        ;POP EAX                                                                ; depile
        ;POP EDX                                                                ; depile
        ;POPA                                                           ; replace tout les registres
       
        ;INC EDX                                                                ; j
        ;INC EDX                                                                ; j + 1
       
        ; appel tri droite
        ;PUSHA                                                          ; sauvegarde de tout les registre
        ;PUSH EBX                                                       ; pose r sur la pile
        ;PUSH EDX                                                       ; pose (j+1) sur la pile
        ;PUSH ECX                                                       ; pose adr vecteur sur la pile
        ;CALL _trier
        ;POP ECX
        ;POP EDX
        ;POP EBX
        ;POPA
       
fin :  
       
        POPA                                                            ; remet les registres en place
        MOV ESP, EBP                                            ; supprime les varibles temporaire
        POP EBP                                                         ; remet l'ancienne valeur de EBP
               
        RET

_partition :
        PUSH EBP                                ; sauve EBP
        MOV EBP, ESP                                            ; sauve la valeur ESP
        SUB ESP, 12                                                     ; var temporaire pour i et j, while
        PUSHA                                                           ; sauvegarde de tout les registre
       
        MOV EAX, [EBP+12]                                       ; l
        MOV EBX, [EBP+16]                                       ; r
        ;INC EBX                                                        ; r + 1
       
        MOV [EBP-12], EAX                                       ; sauvegarde i tmp
        MOV [EBP-8], EBX                                        ; sauvegarde j tmp
        MOV DWORD[EBP-4], 1                                     ; met la boucle a true
       
        MOV ECX, 0
        PUSH ECX
        CALL _afficherUns32
        POP ECX
       
        boucle :
                CMP DWORD[EBP-4], 1                             ; si toujours true  on continue la boucle
                JNE finbcl                                              ; sinon paritionnement fini
               
                MOV ECX, 1
                PUSH ECX
                CALL _afficherUns32
                POP ECX
               
                gauche :
                        MOV ECX, 2
                        PUSH ECX
                        CALL _afficherUns32
                        POP ECX
               
                        INC DWORD[EBP-12]                       ; incremente i
                       
                        MOV EAX, [EBP+12]                       ; val l
                        MOV ECX, 12                                     ; met dans ecx pour donner une taille de 32bits
                        MUL ECX                                         ; multiplie par 3 car chaque obj vaut 3 cases
                        ADD EAX, [EBP+8]                        ;  + adr vec
                        MOV EBX, EAX                            ; place l dans ebx
                       
                        MOV EAX, [EBP-12]                       ; val i
                        MOV ECX, 12                                     ; met dans ecx pour donner une taille de 32bits
                        MUL ECX                                         ; multiplie par 3 car chaque obj vaut 3 cases
                        ADD EAX, [EBP+8]                        ;  + adr vec
                       
                        MOV EAX, [EAX]                          ; valeur x de gauche
                        MOV EBX, [EBX]                          ; valeur x de pivot
                       
                        ;MOV EDX, [EBP-12]
                       
                        ;PUSHA
                        ;CALL _afficherRegistres
                        ;POPA
                       
                        MOV ECX, [EBP-12]
                        MOV EDX, [EBP-8]
                       
                        PUSH EDX
                        PUSH ECX
                        CALL _showij
                        POP ECX
                        POP EDX
                       
                        CMP EAX, EBX                            ; Si v[i] < v[l]
                        JA  fing                                        ; Sinon on sort
                       
                        MOV ECX, [EBP-12]                       ; prend i
                        MOV EDX, [EBP-8]                        ; prend j
                        CMP ECX, EDX
                        JAE fing
                       
                        JMP gauche
                fing :
               
                droite :
                        MOV ECX, 3
                        PUSH ECX
                        CALL _afficherUns32
                        POP ECX
               
                        DEC DWORD[EBP-8]
                       
                        MOV EAX, [EBP-8]
                        MOV ECX, 12                                     ; met dans ecx pour donner une taille de 32bits
                        MUL ECX                                         ; multiplie par 3 car chaque obj vaut 3 cases
                        ADD EAX, [EBP+8]
                       
                        MOV EAX, [EAX]
                       
                        MOV ECX, [EBP-12]
                        MOV EDX, [EBP-8]
                       
                        ;PUSH EDX
                        ;PUSH ECX
                        ;CALL _showij
                        ;POP ECX
                        ;POP EDX
                       
                        PUSHA
                        CALL _afficherRegistres
                        POPA
                       
                        CMP EBX, EAX  
                        JAE find
                       
                        MOV ECX, [EBP-12]                       ; prend i
                        MOV EDX, [EBP-8]                        ; prend j
                        CMP ECX, EDX
                        JAE find
                       
                        JMP droite
                find :
               
                MOV ECX, [EBP-12]                       ; prend i
                MOV EDX, [EBP-8]                        ; prend j
                CMP ECX, EDX
                JAE sortir
                JMP passortir
                sortir :
                MOV DWORD[EBP-4], 0
                passortir :
               
                MOV EAX, [EBP-12]
                MOV EBX, [EBP-8]
               
                PUSH EBX
                PUSH EAX
                CALL _showij
                POP EAX
                POP EBX
               
                MOV EAX, [EBP-8]
                MOV ECX, 12                                     ; met dans ecx pour donner une taille de 32bits
                MUL ECX                                         ; multiplie par 3 car chaque obj vaut 3 cases
                ADD EAX, [EBP+8]
                MOV EBX, EAX
               
                MOV EAX, [EBP-12]
                MOV ECX, 12                                     ; met dans ecx pour donner une taille de 32bits
                MUL ECX                                         ; multiplie par 3 car chaque obj vaut 3 cases
                ADD EAX, [EBP+8]
               
                PUSH EAX
                PUSH EBX
                CALL _swap
                POP EBX
                POP EAX
               
                JMP boucle
        finbcl :

        MOV EAX, [EBP+12]                       ; recupere l
        MOV ECX, 12                                     ; met dans ecx pour donner une taille de 96bits (3 * 32bits)
        MUL ECX                                         ; multiplie par 3 * 4bytes car chaque obj vaut 3 cases
        ADD EAX, [EBP+8]                        ; addition avec l'adresse du vecteur
        MOV EBX, EAX                            ; on place dans EBX
       
        MOV EAX, [EBP-8]                        ; recupere j
        MOV ECX, 12                                     ; met dans ecx pour donner une taille de 32bits
        MUL ECX                                         ; multiplie par 3 car chaque obj vaut 3 cases
        ADD EAX, [EBP+8]                        ; addition avec l'adresse du vecteur
       
        ;PUSHA
        ;CALL _afficherRegistres
        ;POPA

        PUSH EAX                                        ; place j
        PUSH EBX                                        ; place l
        CALL _swap                                      ; fait un swap
        POP EBX
        POP EAX
       
        MOV ECX, [EBP+8]
        MOV EDX, 8
       
        PUSH EDX
        PUSH ECX
        CALL _af
        POP ECX
        POP EDX
       
        ;SUB EAX, EDX                           ; retire l'adresse de j
        ;DIV ECX
        MOV EAX, [EBP-8]
        MOV [retour], EAX
       
        POPA
       
        MOV EAX,[retour]                                ; retourne valeur de la fonction (j)
       
        MOV ESP, EBP
        POP EBP
       
        RET

_swap :
       
        PUSH EBP                        ; sauve EBP
        MOV EBP, ESP                                ; sauve la valeur ESP
        SUB ESP, 12                                             ; var temporaire pour swap
        PUSHA                                                   ; sauvegarde de tout les registre
       
        MOV EDX, [EBP+8]                                ; adresse case a
       
        MOV EAX, [EDX]                                  ; place var a dans registre
        MOV EBX, [EDX+4]
        MOV ECX, [EDX+8]
       
        MOV [EBP-12],   EAX                             ; place a dans var tmp pile
        MOV [EBP-8], EBX
        MOV [EBP-4], ECX
       
        MOV EDX, [EBP+12]                               ; adresse case b
       
        MOV EAX, [EDX]                                  ; place var b dans registre
        MOV EBX, [EDX+4]
        MOV ECX, [EDX+8]
       
        MOV EDX, [EBP+8]
       
        MOV [EDX],   EAX                                ; place b vers adresse a
        MOV [EDX+4], EBX
        MOV [EDX+8], ECX
       
        MOV EAX, [EBP-12]                               ; place a vers adresse b
        MOV EBX, [EBP-8]
        MOV ECX, [EBP-4]
       
        MOV EDX, [EBP+12]
       
        MOV [EDX],   EAX                                ; place tmp (a) vers adresse b
        MOV [EDX+4], EBX
        MOV [EDX+8], ECX
       
        POPA                                                    ; remet les registres en place
        MOV ESP, EBP                                    ; supprime les varibles temporaire
        POP EBP                                                 ; remet l'ancienne valeur de EBP
       
        RET