Selection-sort-Verfahren in der Montage

Ich glaube, ich habe Probleme mit meinem swap, und wie ich Zugriff auf die Elemente in meinem array. Gerade jetzt, alle von der code läuft, aber die Liste ändert sich nicht, nach dem Sortieren. Er ist der high-level-Art, die ich bin versucht zu implementieren

for(k=0; k<request-1; k++) {
    i = k;
    for(j=k+1; j<request; j++) {
        if(array[j] > array[i])
        i = j;
    }
    exchange(array[k], array[i]);
}

Hier ist der Assembler-code. Hinweis: die Zuordnung ist über pushing und popping-Elementen auf/aus dem Stapel, so kann ich nicht die Parameter ändern.

;this is a library with macros for things like printing numbers and strings    
INCLUDE Irvine32.inc

    MIN = 10            ;lower range limit
    MAX = 200           ;upper range limit
    LRANGE = 100        
    HRANGE = 999        

.data

;title, intro, and prompts
    title_1     BYTE    "PROGRAMMING ASSIGNMENT 5: RANDOM GEN/SORT", 0dh, 0ah, 0

    intro_1     BYTE    "This program generates random numbers in the range (100 - 999),", 0dh, 0ah
        BYTE    "displays the original list, sorts the list, and calculates the median value.", 0dh, 0ah
        BYTE    "Finally, it displays the sorted list in descending order.", 0dh, 0ah, 0

    prompt_1    BYTE    "How many numbers should be generated? (10 - 200): ", 0 

    error_1     BYTE    "Out of range.", 0dh, 0ah, 0

    display_1   BYTE    "List of random numbers: ", 0dh, 0ah, 0
    display_2   BYTE    "The median is: ", 0
    display_3   BYTE    "The sorted list: ", 0dh, 0ah, 0

;placeholders for user entries and calculated data
    randArray   DWORD   MAX DUP(?)
    userNum     DWORD   ?           ;integer to be entered by user

;strings for posting results
    goodBye_1   BYTE    "Thank you for using the Gen/sort-ulator! Good-bye!", 0


.code
main PROC
    call    Randomize

;Title Screen
    push    OFFSET  title_1
    push    OFFSET  intro_1
    call    Intro

;Get and validate user numbers
    push    OFFSET  error_1
    push    OFFSET  prompt_1
    push    OFFSET  userNum
    call    GetData

;Fill Array with random numbers
    push    OFFSET  randArray
    push    userNum
    call    FillArray

;display unsorted results
    push    OFFSET  randArray
    push    userNum
    push    OFFSET  display_1
    call    DisplayList

;sort the results
    push    OFFSET  randArray
    push    userNum
    call    SortList

;display the median
    push    OFFSET  randArray
    push    userNum
    push    OFFSET  display_2
    call    median

;display sorted results
    push    OFFSET  randArray
    push    userNum
    push    OFFSET  display_3
    call    DisplayList

;Say "goodbye"
    push    OFFSET  goodBye_1
    call    Goodbye

    exit        ; exit to operating system
main ENDP

;-------------------------------------------------------
;Gives an Intro to the program
; Receives parameters on the system stack (in the order pushed):
;       Address of the title
;       Address of the intro
;post: intro displayed
;registers: none
;-------------------------------------------------------
Intro PROC
    pushad
    mov     ebp, esp
    mov     edx, [ebp+40]
    call    writeString
    call    CrLf
    mov     edx, [ebp+36]
    call    writeString
    call    CrLf
    popad
    ret     8
Intro   ENDP

;-------------------------------------------------------
;Prompts user for an integer, int stores in userNum
; Receives parameters on the system stack (in the order pushed):
;       Address of the error message
;       Address of the prompt
;       Address of return value
;Post: userNum
;registers: none
;-------------------------------------------------------
GetData PROC
    pushad

;setup stack and prompt for entry   
    mov     ebp, esp
reenter:
    mov     edx, [ebp+40]
    mov     ebx, [ebp+36]
    call    WriteString
    call    ReadInt

;validate entry
    cmp     eax, MIN            ;if eax < LOWER
    jl      badEntry            ;jump to summary 
    cmp     eax, MAX            ;if eax > UPPER
    jg      badEntry            ;reprompt 
    jmp     goodEntry           ;else jump to end, we have a good value

;bad entry reprompt
badEntry:
    mov     edx, [ebp+44]
    call    WriteString
    jmp     reenter

goodEntry:
    call    CrLf
    mov     [ebx], eax
    popad
    ret     12
GetData ENDP

;-------------------------------------------------------
;Fills array with a number of random integers within RANGE
;Recieves parameters on the system stack (in order pushed)
;       array
;       userNum
;Post: array is filled with userNum number of randoms
;Registers used: none
;-------------------------------------------------------
FillArray   PROC
    pushad
    mov     ebp, esp    
    mov     ecx, [ebp+36]           ;initialize loop counter with user entry
    mov     edi, [ebp+40]           ;setup array offset
    fillLoop:
    call    nextRand
    add     edi, 4  
    loop    fillLoop
    popad
    ret     8
FillArray   ENDP

;-------------------------------------------------------
; Procedure nextRand
; adapted from check lecture 20 solutions
; Procedure to get the next random number in the range specified by the user.
; Preconditions:  LRANGE < HRANGE
; Registers used:  eax, edi
;-------------------------------------------------------
nextRand    PROC            
    mov     eax, HRANGE
    sub     eax, LRANGE
    inc     eax                 ;add 1 to get the number of integers in range
    call    RandomRange 
    add     eax, LRANGE         ;eax has value in [LOW - HIGH]
    mov     [edi],eax       
    ret                     
nextRand    ENDP

;-------------------------------------------------------
;Sorts the contents of an integer array
; Receives parameters on the system stack (in order pushed)
;           Array
;           Array Size
;registers: none
;-------------------------------------------------------
sortList    PROC
    pushad
    mov     ebp, esp
    mov     ecx, [ebp+36]
    mov     edi, [ebp+40]
    dec     ecx                 ;ecx < request-1
    mov     ebx, 0              ;ebx=k

;for(k=0; k<request-1; k++)
outerLoop:
    mov     eax, ebx            ;eax=i=k
    mov     edx, eax
    inc     edx                 ;edx=j=k+1
    push    ecx
    mov     ecx, [ebp+36]       ;ecx < request

;for(j=k+1; j<request; j++)
innerLoop:
    mov     esi, [edi+edx*4]
    cmp     esi, [edi+eax*4]
    jle     skip
    mov     eax, edx
skip:
    inc     edx
    loop    innerLoop

;swap elements
    lea     esi, [edi+ebx*4]
    push    esi
    lea     esi, [edi+eax*4]
    push    esi
    call    exchange
    pop     ecx
    inc     ebx
    loop    outerLoop

    popad
    ret     8
sortList    ENDP

;-------------------------------------------------------
; Exchange k and i
; Receives parameters on the system stack (in order pushed)
;           array[k]
;           array[i]
;registers: none
;-------------------------------------------------------
Exchange    PROC
    pushad
    mov     ebp,esp
    mov     eax, [ebp+40]       ;array[k] low number
    mov     ecx, [eax]
    mov     ebx, [ebp+36]       ;array[i] high number
    mov     edx, [ebx]
    mov     [eax], edx
    mov     [ebx], ecx
    popad       
    ret 8
Exchange    ENDP


;-------------------------------------------------------
;Displays the median of an integer array
; Receives parameters on the system stack (in order pushed)
;           Array
;           Array Size
;           display string
;registers: none
;-------------------------------------------------------
Median PROC
    pushad
    mov     ebp, esp
    mov     edi, [ebp+44]
;display string
    mov     edx, [ebp+36]
    call    writeString

;calculate median element
    mov     eax, [ebp+40]
    cdq
    mov     ebx, 2
    div     ebx
    shl     eax, 2
    add     edi, eax
    cmp     edx, 0
    je      isEven
;Array size is odd, so display the middle value         
    mov     eax, [edi]
    call    writeDec
    call    CrLf
    call    CrLf
    jmp     endMedian
isEven:
;Array size is even so average the two middle values
    mov     eax, [edi]
    add     eax, [edi-4]
    cdq     
    mov     ebx, 2
    div     ebx
    call    WriteDec
    call    CrLf
    call    CrLf
endMedian:
    popad
    ret 12
Median ENDP

;-------------------------------------------------------
;Displays the contents of an integer array, 10 per row
; Receives parameters on the system stack (in order pushed)
;           Array
;           Array Size
;           display string
;registers: none
;-------------------------------------------------------
DisplayList PROC
    pushad
    mov     ebp, esp

;display string
    mov     edx, [ebp+36]
    call    writeString
    call    CrLf
    mov     ecx, [ebp+40]
    mov     edi, [ebp+44]
    mov     ebx, 0

;display array contents
listloop:
    inc     ebx             ;counter for 10 items per row
    mov     eax, [edi]      
    call    writeDec
    add     edi, 4
    cmp     ebx, 10
    jne     noReturn        ;jump if 10 items are not yet printed
    call    CrLf
    mov     ebx, 0
    jmp     noTab           ;this skips adding a tab on a new row
noReturn:
    mov     al, TAB
    call    writeChar
noTab:
    loop listloop
    call    CrLf
    popad
    ret 12
DisplayList ENDP

;-------------------------------------------------------
;Says good-bye to the user
; Receives parameters on the system stack:
;       Address of string
;registers: none
;-------------------------------------------------------
Goodbye PROC
    pushad
    mov     ebp, esp
    mov     edx, [ebp+36]
    call    writeString
    call    CrLf
    popad
    ret     4
Goodbye ENDP

END main

InformationsquelleAutor hobbes131 | 2012-11-15

2

Um exchange-Elemente sollten Sie die Weitergabe Ihrer Adresse (in anderen Worten, wird ein Zeiger auf jedes). Was du getan hast, war nur der Austausch der Werte als Parameter übergeben, die auch sofort befreit. Ihr code wird die entsprechende C-Funktion:
```
void Exchange(int x, int y)
{
    int eax = x;
    int ebx = y;
    x = ebx;
    y = eax;
}
```
Müssen Sie etwas wie:
```
void Exchange(int* x, int* y)
{
    int eax = *x;
    int ebx = *y;
    *x = ebx;
    *y = eax;
}
```
In asm, das kann so Aussehen:
```
Exchange    PROC
    pushad
    mov     eax, [esp+40]
    mov     ecx, [eax]
    mov     ebx, [esp+36]       
    mov     edx, [ebx]
    mov     [eax], edx
    mov     [ebx], ecx
    popad       
    ret 8
Exchange    ENDP
```
Zum aufrufen dieser Funktion verwenden Sie den folgenden:
```
    lea     esi, [edi+ebx*4]
    push    esi
    lea     esi, [edi+eax*4]
    push    esi
    call    Exchange
```
Hinweis: Ihr Exchange Funktion hatte, eine Anweisung mov eax, [edi] was ich konnte keinen Sinn machen.

Update: ja, Sie können die Emulation der Funktionalität von LEA indem Sie die Berechnungen manuell. Zum Beispiel lea esi, [edi+ebx*4] wird:
```
    mov esi, ebx
    shl esi, 2    ; esi=ebx*4
    add esi, edi  ; esi=edi+ebx*4
```
- Danke, das hat geholfen. Gibt es eine Möglichkeit, dies zu tun, ohne lea? Das ist nicht ein Befehl haben wir in der Klasse gelernt, aber ich würde gerne in der Lage, es zu tun mit Umzügen, wenn möglich.
- Aktualisiert die Antwort.
- Danke Jester. Es funktioniert, das einzige Problem ist jetzt, dass ich zu sein scheinen running out of memory oder so etwas, ich bekomme eine seltsame Anzeige, wenn ich das Obere Ende des Bereichs (200). Wenn Sie irgendwelche Ideen auf, dass ich Sie Schätze.
- Ich hoffe, Sie haben einige zusätzliche code nach call SortList zu beenden Ihr Programm. Wie es ist, wird die Ausführung fortgesetzt wird (fällt durch) in SortList wieder nach dem Aufruf kehrt zurück, aber dieses mal ohne vernünftige Argumente auf den stack.
- Nochmals vielen Dank, ich habe die umliegenden code, damit Sie alles sehen können. Ich verwendete debugger und beobachtete meine registriert, Sie sind korrekt, aber die Ausgabe an die Anzeige kehrt in den Müll. Nicht sicher, warum.
- Wie bin ich auf linux und habe keinen Zugriff auf irvine oder masm, habe ich mich schnell portiert Ihr code für den GNU-assembler. Scheint zu funktionieren, siehe hier in Betrieb.
- Eigentlich nehme ich das zurück, Sie scheinen ein problem zu haben. Ihre innere Schleife läuft zu oft. Dein Kommentar sagt: for(j=k+1; j<request; j++) aber dein code verwendet einfach loop innerLoop so wird es zu lange laufen. Ersetzen Sie einfach, dass mit cmp edx, ecx; jb innerLoop
- lassen Sie uns weiter, diese Diskussion im chat
InformationsquelleAutor Jester

Schreibe einen Kommentar

Du musst angemeldet sein, um einen Kommentar abzugeben.