selection sort in assembly language
here is my code.. I have to perform a selection sort on an array. It is homework. The Irvine32.inc sets up my memory model. Any suggestions to what I'm doing wrong would be helpful. I've redone the entire thing a few times now.
INCLUDE Irvine32.inc
.data
myArray DWORD 10, 12, 3, 5
.code
main PROC
call Clrscr
MOV EDI, OFFSET myArray
MOV ECX, LENGTHOF myArray
CALL PRINT_ARRAY
MOV EDI, OFFSET myArray
MOV ECX, LENGTHOF myArray
CALL SORT_ARRAY
CALL CRLF
MOV EDI, OFFSET myArray
MOV ECX, LENGTHOF myArray
CALL PRINT_ARRAY
exit
main ENDP
;-----------------------------------------------------------------------------
PRINT_ARRAY PROC
; requires edi to be pointing to an array
; requires ecx to be the length of the array
;-----------------------------------------------------------------------------
ARRAYLOOP: MOV EAX, [EDI]
CALL WRITEINT
CALL CRLF
ADD EDI, TYPE myArray
LOOP ARRAYLOOP
ret
PRINT_ARRAY ENDP
;-----------------------------------------------------------------------------
SORT_ARRAY PROC
; requires edi to be pointing to an array
; requires ecx to be the length of the array
;
; ebp points to the minimum value
; esp points to edi + 1 (4 in our case)
;-----------------------------------------------------------------------------
PUSHAD ; push all our registers.. dont want to modify
OUTER_LOOP: MOV EBX, ECX ; ebx = inner looper counter
DEC EBX ; dont want to compare same offset
; we want it one less in the ebx count
MOV EBP, EDI ; assign our min value array OFFSET
MOV ESP, EDI ; our value of j which we will inc
ADD ESP, TYPE[EDI] ; j = i + 1
INNER_LOOP: MOV EAX, [EBP] ; save our min VALUE to a register
; ESP (j) < EAX (min) ?
CMP [ESP], EAX
; no, its greater, skip this value
JGE SKIP_ARRAY_VALUE
; yes, array value is less than min
; save a new min value
MOV EBP, ESP
SKIP_ARRAY_VALUE:
ADD ESP, TYPE[EDI]
; decrement our counter
DEC EBX
; if ebx didnt set the zero flag, keep looping
JNZ INNER_LOOP
; move our min value into the position of edi, and move edi
; to the position of the min value
MOV EDX, [EDI] ; edx = numbers[i]
MOV EAX, [EBP] ; eax = numbers[min]
MOV [EDI], EAX ; numbers[i] = numbers[min]
MOV [EBP], EDX ; numbers[min] = numbers[i]
INC EDI
LOOP OUTER_LOOP
POPAD ; pop all registers
RET
SORT_ARRAY ENDP
END main
The program results in printing the array out first off, unsorted. Then it hangs for a little bit and crashes, no errors, or anything.
Answer
You need to diagnose your crash.
- Install and setup DrWatson so that it catches crash data.
- run ML again with options to output a pdb file
- trigger the crash again - you DrWatson should trap it.
Alternative: Run your program through a debugger. Since VS 2008, VS has MASM (ML) built-in, so you might even be able to get source debugging. I documented activating MASM in VS 2008 Express SP1 - free - (and presumably following versions) there. Otherwise, use windbg (not as friendly).
Now I didn't go at all through your algorithm, but the way you use ESP kinda scares me: Are you REALLY sure ESP still points to your PUSHAD stack-based save area when you execute the POPAD in SORT_ARRAY?...
I have programmed and maintained very large software pieces using ML, and my recommendation would be to never messup with ESP, and let MASM take care of (E)BP in most circumstances (LOCAL clause, example below). The only exceptions relate to heavy systems programming, like bitness mode changing (entering / leaving prot mode) and implementing a threading monitor (state saving / restoration).
A few others:
Don't use jumps anymore, use .IF / .ELSE / .ENDIF, .REPEAT / .WHILE / .UNTIL, etc. and the like.
Don't bother with EBP for parms and local vars, let ML pseudo-ops take care of parms and local variable addressing.
Use MASM-managed parameter passing (through INVOKE instead of CALL) and use MASM-managed local variables (through the LOCAL in-PROC directive). You can even define arrays in LOCAL with a syntax such as
Foo[6]: BYTE
In the sample that follows:
CheckRAMPresent is called with two DWORD Parms, LinBufferBase and BufferSize.
Upon entry and exit, MASM saves and restore EAX ECX EBX DI ES because I told it the PROC uses it.
SMAPBuffer, RAMBank and RAMBankEnd are local (stack based) variables (SMPOutput is a STRUCT). MASM manipulates the stack pointer to allocated / deallocate upon entry / exit, and manages the BP-based address mode - see how the code in the PROC addresses both the parms and the local vars.
Finally, you have examples of .IF .ELSE .ENDIF and even a .REPEAT / .UNTIL
Note that you can use condition flags
.IF CARRY?
or HLL-like condition expressions:
(ES:[DI].RangeType == 1)
or even the more complex:
((ECX >= EAX) && (ECX <= EBX)) || ((EDX >= EAX) && (EDX <= EBX))
Those generate totally predictable code, so this is still assembly language. But it's just a much more readable / maintainable kind of assembly. For all the HLL pseudo-ops, look at the generated code (there's an ML option for that).
The whole set of MASM documentation explaining the HLL constructs can be found there in ZIPped .doc & HTML formats. You can find it elsewere in PDF form, methinks (Google around). The Programmer's Guide is by far the most useful part. The MASM reference manual is mostly obsolete, you'd rather use the Intel developer's guide instead.
CheckRAMPresent PROC NEAR STDCALL PUBLIC \
USES EAX ECX EBX DI ES,
LinBufferBase: DWORD,
BufferSize: DWORD
LOCAL SMAPBuffer: SMAPOutput,
RAMBank: DWORD,
RAMBankEnd: DWORD
MOV AX,SS ; Get ES:DI => SMAP buffer,
MOV ES,AX
LEA DI, SMAPBuffer
MOV ECX, SIZEOF SMAPBuffer ; ECX = SMAP buffer size.
PUSHCONTEXT ASSUMES
ASSUME DI:PTR SMAPOutput
XOR EBX,EBX ; Set initial continuation pointer.
MOV RAMBank, EBX ; Zero the RAM bank tracker.
MOV RAMBankEnd, EBX
.REPEAT
INVOKE GetSMAP
.BREAK .IF CARRY?
; If type is Available, then process that range.
.IF (ES:[DI].RangeType == 1) ; If Available RAM, check what we have.
SAVE EBX, ECX
MOV EAX, ES:[DI].LowBase ; Get Bank start in EAX,
MOV EBX, EAX
ADD EBX, ES:[DI].LowLng ; and bank end in EBX.
MOV ECX, LinBufferBase ; Get buffer start in ECX
MOV EDX,ECX
ADD EDX, BufferSize ; and buffer end in EDX.
; If either the lower end or the upper end of the buffer
; intersects with the bank, take that bank (if this is the
; first) or try to coalesce it with the existing one (if we already
; have one).
; This translates as:
; If either the low address (ECX) or the high address (EDX) of the
; buffer is within the bank boundaries [EAX - EBX], then the buffer
; intersects with the bank.
.IF ((ECX >= EAX) && (ECX <= EBX)) \ ; If buffer intersects,
|| ((EDX >= EAX) && (EDX <= EBX))
; then if this is the first intersecting RAM bank, too, then
select it.
.IF (!RAMBank && !RAMBankEnd)
MOV RAMBank, EAX ; Remember bank.
MOV RAMBankEnd, EBX
.ELSE
; We already have a RAM bank.
; If this new one starts where the one we have ends,
; the end of the new one become the end of the merged blocks.
; Else if the end of the new block is the beginning of the one
; we have, then the new block is located just before the one we
; have and its start become the start of the merged blocks.
; Otherwise, the new bank is not contiguous with the previously
; computed one and there's nothing we can do (at least using this
; algorithm).
.IF (EAX == RAMBankEnd)
MOV RAMBankEnd, EBX
.ELSEIF (EBX == RAMBank)
MOV RAMBank, EAX
.ENDIF
.ENDIF
.ENDIF
RESTORE EBX, ECX
.ENDIF
.UNTIL (EBX == 0) ; If SMAP returned EBX == 0, we just did the
; last SMAP bank.
MOV EAX, LinBufferBase ; Get buffer start in EAX
MOV ECX,EAX
ADD ECX, BufferSize ; and buffer end in ECX.
; If our start and our end are both in the bank,
; we win. Otherwise, we loose.
.IF (EAX >= RAMBank) && (ECX <= RAMBankEnd)
CLC
.ELSE
STC
.ENDIF
RET
CheckRAMPresent ENDP
Have fun! ;-)