Suche Algorithmen in Assembler

SirLant

Prinzipiell suche ich alle arten von Algorithmen, wobei ich fürs erste am liebsten sehr einfache
bevorzugen würde, z.B. Insertion Sort, Bubble Sort, ...
Müssen nicht unbedingt Sortieralgorithmen sein, aber daran sitze ich gerade

Habe bereits mit google gesucht, aber nur ein Programm gefunden, bei welchem die Quellcodes nicht kommentiert
sind und daher nützt es mir nicht viel, denn die Algorithmen verstehe ich ja, mir
fehlt nur die Übung mit Assembler

Am liebsten wäre mir das ganze auf Deutsch, aber Englisch ist auch ok

und es sollte auf jeden Fall die Intel-Syntax sein und am besten mit masm/tasm funktionieren

DocJunioR

Wenn ein Programm kommentiert wird, sollte eh nur der Algorithmus im Programm stehen, nicht in jeder Zeile, welcher Wert denn in welches Register geschrieben wird..

Drück dich ein wenig deutlicher aus. Was genau willst du denn haben ?
Wie sieht dein Variablenbereich aus, etc..

Vellas

Hi!

@SirLant:
Gerade als Übung wäre es doch sinnvoll, die Algorithmen selbst zu implementieren. Selbst dann wen du die ganze Zeit ein Buch neben dir liegen hast. Wenigstens lernst du es so effizient. Immerhin wirst du von Zeit zu Zeit weniger Zeit beanspruchen.

Ich würde es so machen. Nimm das Daten-Segment und hau da ein Array von Zahlen rein. Dann schreibst du die Routine und greifst erstmal auf das komplette Array direkt zu. Wenn der Algo funktioniert, schreibst du nen neuen. Wenn du dann etwas fitter in Assembler bist, dann kannst du es ja mal damit Versuchen Segment- und Offset-Adresse an die Funktion zu übergeben, sprich das Array (bzw. die Adresse) als Parameter zu übergeben und schreibst die Sortierfunktion dafür um.

Bubblesort in ASM findest du hier, musst ein wenig nach unten scrollen:
http://www.developer.be/index.cfm/fuseaction/tutorialDetail/GroupID/159/tutorialName/profile.htm

Du kannst di Anschließend auch mit einer der folgenden Routinen die Zahlen ausgeben lassen:
Doppelwort (Routine ddout): http://www.fh-wedel.de/~wol/ass/sose2004/ddout.asm.html
Wort (Routine dezi): http://www.fh-wedel.de/~wol/mproz/sose2003/messung.asm.html
(wobei ddout natürlich auch ein Wort ausgeben kann, Zahl zur Ausgabe wird bei erster Routine in DX:AX und bei zweiter Routine in AX erwartet.)

Code-Hacker

SirLant

Mein Problem ist, dass ich halt mal sowas sehen müsste mit ein paar Erklärungen dazu was gerade geschieht, damit ich weiß wie das geht.
Z.B. wie man auf größer(-gleich) und kleiner(-gleich) prüft, es gibt zwar Jump-Befehle,
aber die werten ja auch nur die Flags aus welche irgendwie gesetzt werden müssen, usw.

Und in meinem Buch wurde sowas halt nie gezeigt, wodurch ich mich bei sowas schwer tue.

Werde mit den Bubble sort mal anschauen

Vellas

Hi!

Sorry, aber was ist das für ein Buch in dem einen nicht einmal ein Vergleich beigebracht wird. Natürlich mit dem Jump-Befehlen zum vergleichen, das ist klar. Dazu brauchst du noch den Vergleich-Befehel cmp:

xor ax,ax
init_eins: mov ax,00001h
cmp ax,0000h
jnz init_eins

Wenn das Zero-Flag nicht gesetzt ist nach dem Verlgeich, dann wird zu init_eins gesprungen. So setzt du eigentlich alle Befehle ein, allerdings evtl. mit anderen Sprungbefehlen. Obiges Beispiel ergibt im Endeffekt eine Endlosschleife.

Aber eigentlich sollte jedes Buch erklären wie ein Vergleich funktioniert. Das macht sogar das kleine von Reiner Backer, vom rororo Verlag für 9,90EUR.

Code-Hacker

SirLant

jnz und jne bzw je wird schon verwendet, aber wie ich auf größer(-gleich) und kleiner(-gleich) prüfe nicht.
Verwendet man dazu auch cmp, oder wie funktioniert das da?

camper

cmp ist nichts weiter als ein sub mit dem unterschied, dass das ergebnis nicht gespeichert wird, lediglich die flags werden entsprechend dem ergebnis gestzt.

zusätzlich gibt es ja noch eine ganze menge weiterer bedingter sprünge:

hier mal eine auswahl der möglichkeiten:

unsigned vs. unsigned: cmp a, b

ja (=jnbe) --- a > b ( jump if above; jump if not below or equal )
jb (=jnae, =jc) --- a < b ( jump if below; jump if not above or equal; jump if carry )
jae (=jnb, =jnc) --- a >= b ( jump if above or equal; jump if not below; jump if not carry )
jbe (=jna) --- a <= b ( jump if below or equal; jump if not above )
je (=jz) --- a = b ( jump if equal; jump if zero )
jne (=jnz) --- a != b ( jump if not equal; jump if not zero )

signed vs. signed

jg (=jnle) --- a > b ( jump if greater; jump if not less or equal )
jl (=jnge) --- a < b ( jump if less; jump if not greater or equal )
jge (=jnl) --- a >= b ( jump if greater or equal; jump if not less )
jle (=jng) --- a <= b ( jump if less or equal; jump if not greater )

weitere bedingte sprünge sind möglich (js, jo etc.), werden i.d.r. aber nicht zusammen mit cmp benutzt.

SirLant

Danke

lade dir doch mal dem masm32 packet (ist sowieso besser als TASM ) runter. Da gibts viele Code-schnipsel, auch verschiedene sortieralgorithmen.
(Beispiel: quicksort)

; #########################################################################

    .486                      ; create 32 bit code
    .model flat, stdcall      ; 32 bit memory model
    option casemap :none      ; case sensitive

    include \masm32\include\oleaut32.inc

    .code

; #########################################################################

nrQsortA proc Arr:DWORD,count:DWORD

    LOCAL First :DWORD
    LOCAL Last  :DWORD
    LOCAL cntr  :DWORD
    LOCAL bLen  :DWORD
    LOCAL hMem  :DWORD
    LOCAL temp  :DWORD

    mov esi, Arr              ; source address in ESI

    mov cntr, 0

  ; --------------------------
  ; allocate temporary buffer
  ; --------------------------
    mov eax, count
    add eax, 40
    mov bLen, eax
    invoke SysAllocStringByteLen,0,bLen
    mov hMem, eax

    mov edi, hMem             ; buffer address in EDI

  ; ------------------------------------
  ; set First and Last reference values
  ; ------------------------------------
    mov First, 0
    mov eax, count
    dec eax
    mov Last, eax             ; Last = count - 1

  outer_loop:
  ; -------------------
  ; calculate midpoint
  ; -------------------
    mov eax, Last
    add eax, First
    shr eax, 1
  ; =========================
    mov ebx, [esi+eax*4]      ; midpoint in EBX
    mov temp, ebx
  ; =========================
    mov ecx, First
    mov edx, Last
  ; ---------------------------------------------------------
  inner_loop:
    cmp [esi+ecx*4], ebx
    jge wl2
    inc ecx
    jmp inner_loop
  wl2:
    cmp [esi+edx*4], ebx
    jle wl2Out
    dec edx
    jmp wl2
  wl2Out:
    cmp ecx, edx              ; If ecx > edx, exit inner loop
    jg exit_innerx
  ; =========================
    mov eax, [esi+ecx*4]
    mov ebx, [esi+edx*4]      ; swap elements
    mov [esi+ecx*4], ebx
    mov [esi+edx*4], eax
  ; =========================
    mov ebx, temp             ; restore EBX
    inc ecx
    dec edx
    cmp ecx, edx
    jle inner_loop
  exit_innerx:
  ; ---------------------------------------------------------
    cmp ecx, Last             ; If ecx < Last jump over
    jg iNxt
  ; =========================
    mov eax, cntr
    mov [edi+eax*4], ecx
    mov ebx, Last
    mov [edi+eax*4+4], ebx
  ; =========================
    add cntr, 2
  iNxt:
    mov ebx, temp             ; restore EBX
    mov Last, edx             ; Last  = EDX
    cmp edx, First            ; compare Last & First
    jg outer_loop

    cmp cntr, 0
    jz qsOut
    sub cntr, 2
  ; =========================
    mov eax, cntr
    mov ebx, [edi+eax*4]
    mov First, ebx
    mov ebx, [edi+eax*4+4]
    mov Last, ebx
  ; =========================
    mov ebx, temp             ; restore EBX
    jmp outer_loop

    qsOut:

    invoke SysFreeString,hMem

    ret

nrQsortA endp

; #########################################################################

    end

http://www.codingcrew.de/marty/win32asm.php

Ganz unten auf der Seite findest du dann: Sortieralgorithmen in Assembler / Sorting algorithms in Assembly - Juni 2004