NASM - The Netwide Assembler
NASM Forum => Programming with NASM => Topic started by: turtle13 on August 11, 2017, 12:22:59 AM
-
I am just starting out learning assembly and NASM and one of my first assignments is to complete this simple bubble sort program.
http://ideone.com/NUovpA (http://ideone.com/NUovpA)
I figured out that it is sorting in descending order, I just need to complete it so that it runs through inner and outer loops as needed.
I believe that I need to have the "outerloop" start at 0 (the first index of the array of integers) and then increment ecx by 1 each time it is run, however, I'm stumped as to how to implement that.
I am then required to create a variable named "passes" that holds the number of times that "outerloop" executes. I believe this should go under the "section .data" ? And how should I implement that in the "outerloop" loop?
An additional array named "output" should be placed in "section .bss" where the values of the array named "array" must be copied.
Please help to guide an exasperated newbie on the right path ;D
-
Hi turtle13,
Welcome to the forum. You will find that we're not going to do your homework for you, but we will help. Is that "ideone" code your own work, or is that the "assignment"?
You would increment ecx with:
inc ecx
your code already does that.
The variable "passes" could go in "section .data" or it could go in "section .bss". Unlike ecx, Nasm doesn't know how big "passes" is, so we'll have to tell it. A byte ought to be big enough...
inc byte [passes]
Since your code obviously sorts "array" in place, I don't see why you need "output", but it shouldn't be a problem...
section .bss
output resd 9
I'm going to have to refresh my memory on just how "bubble sort" is supposed to go. I'm pretty sure I've done it, but it was a long time ago (DOS, I imagine). I think we need a variable - a "flag" to tell us if a "swap" has been done on each pass. We set it to zero before each pass, and if it's still zero, we're done. I think I had a routine to print the array after each pass so we could watch the values "bubble" up and down. This makes a good debugging tool too.
I'll try to get back to you on this. Remind me if I don't. You work on it too, and show us how you're doing. As I said, we're not going to do it for you.
Best,
Frank
-
This is just "your code" with a "print_array" routine. It seems to be "working" as is. I think it can be improved.
BTW, just "code" in square brackets at the beeginning of your code, and "/code" in square brackets at the end.
; from "turtle13" on the forum
; nasm -f elf32 myprog.asm
; ld -o myprog myprog.o -m elf_i386
bits 32
section .text ;section declaration
global _start
_start:
call print_array
mov edx, 9
jmp outerloop
outerloop:
mov ecx, 0 ; instead of 0, value should be the number of times outerloop has traversed
jmp innerloop
innerloop:
mov eax, [array + ecx * 4]
mov ebx, [array + 4 + ecx * 4]
cmp eax, ebx
jge next
mov [array + ecx * 4], ebx
mov [array + 4 + ecx * 4], eax
next:
; call print_array
inc ecx
cmp ecx, edx
jl innerloop
je endinner
endinner:
dec edx
jnz outerloop
done:
call print_array
mov ebx,0 ;first syscall argument: exit code
mov eax,1 ;system call number (sys_exit)
int 0x80 ;"trap" to kernel
print_array:
push eax
push ecx
xor ecx, ecx
.top:
mov eax, [array + ecx * 4]
call showeaxd
mov al, ' '
call putc
inc ecx
cmp ecx, 9
jle .top
mov al, 10
call putc
pop ecx
pop eax
ret
;---------------------------------
; showeaxd - print a decimal representation of eax to stdout
; for "debug purposes only"... mostly
; expects: number in eax
; returns; nothing useful
showeaxd:
push eax
push ebx
push ecx
push edx
push esi
sub esp, 10h
lea ecx, [esp + 12]
mov ebx, 10
xor esi, esi
mov byte [ecx], 0
.top:
dec ecx
xor edx, edx
div ebx
add dl, '0'
mov [ecx], dl
inc esi
or eax, eax
jnz .top
mov edx, esi
mov ebx, 1
mov eax, 4
int 80h
add esp, 10h
pop esi
pop edx
pop ecx
pop ebx
pop eax
ret
;---------------------------------
;---------------------------------
putc:
push edx
push ecx
push ebx
push eax
mov eax, 4 ; sys_write
mov ebx, 1 ; stdout
mov ecx, esp ; buffer is on stack
mov edx, 1 ; just one character
int 80h
pop eax
pop ebx
pop ecx
pop edx
ret
;------------------------
section .data ;section declaration
; This variable must remain named exactly 'array'
array dd 3, 9, 1, 6, 2, 4, 0, 5, 7, 8
Best,
Frank
-
Frank thanks for your help here,
many hours spent reading today trying to learn how this all works and I still feel lost. Here is the latest code I have:
bits 32
section .text ;section declaration
global _start
_start:
mov edx, 9
jmp outerloop
outerloop:
inc passes
mov ecx, 0 ; instead of 0, value should be the number of times outerloop has traversed
jmp innerloop
innerloop:
mov eax, [array + ecx * 4]
mov ebx, [array + 4 + ecx * 4]
cmp eax, ebx
jge next
mov [array + ecx * 4], ebx
mov [array + 4 + ecx * 4], eax
jmp next
next:
inc ecx
cmp ecx, edx
jl innerloop
je endinner
endinner:
dec edx
jnz outerloop
done:
mov ebx,0 ;first syscall argument: exit code
mov eax,1 ;system call number (sys_exit)
int 0x80 ;"trap" to kernel
section .data ;section declaration
; This variable must remain named exactly 'array'
array dd 3, 9, 1, 6, 2, 4, 0, 5, 7, 8
passes dd 0
section .bss
output resd 9
I am trying to declare a variable "passes" which increments each time that outerloop is run (the way I have declared "passes"now in secton.data, I get errors when trying to compile "error: invalid combination of opcode and operands".. how do I declare a variable that increments each time a loop is run?)
Also.. how do I do a printf type operation so I can see what the values are in the array? I am starting to learn gdb but can't figure out how to show the results of an array variable.
-
; inc passes
; this is the address (offset) of the variable
; you want the "[contents]"
inc dword [passes]
See the "showeaxd" routine I posted (I also have a "showeaxh" that displays it in hex). We don't need the number to be in eax, but edx:eax is the implicit operand to "div" (edx * 4gig + eax) so it needs to wind up in eax (and edx!) eventually. I should have commented that more extensively.
The manufacturer's documentation is preferred, but you can find the instruction set reference from the old Nasm manual here:
http://home.myfairpoint.net/fbkotler/nasmdocr.html
If it wuz easy, everybody'd be doing it!
Best,
Frank
-
I'm getting there..
I ended up completing my assignment with the following code (it's a bit quirky because the professor had requirements such as the return code needed to be the number of passes through the bubble sort)
bits 32
section .text ;section declaration
global _start
_start:
mov edx, 19
outerloop:
inc byte [passes]
mov ecx, 0
mov [swapflag], ecx
innerloop:
mov eax, [array + ecx * 4]
mov ebx, [array + 4 + ecx * 4]
cmp eax, ebx
jle next
inc byte [swapflag]
mov [array + ecx * 4], ebx
mov [array + 4 + ecx * 4], eax
next:
inc ecx
cmp ecx, edx
jl innerloop
je endinner
endinner:
mov ebx, [swapflag]
cmp ebx, 0
je done
dec edx
jnz outerloop
done:
cld
mov ecx, 80
mov edi, output
mov esi, array
rep movsb
mov ebx, [passes] ;first syscall argument: exit code
mov eax, 1 ;system call number (sys_exit)
int 0x80 ;"trap" to kernel
section .data ;section declaration
; This variable must remain named exactly 'array'
array dd 7, 11, 4, 5, 19, 20, 8, 10, 9, 15, 6, 16, 12, 3, 2, 17, 14, 13, 1, 18
passes db 0
swapflag db 0
section .bss
output resd 20
I still having some issues with setting the flag and making it more efficient. As you can see I tried to increment the flag only when it swapped numbers through a pass and it is supposed to end the program when it goes through a pass without swapping anything (meaning that the sort is completed) yet doesn't seem to do that. After 11 hours of working on this today it's now 2am and I'm pretty much over it at this point
-
Watch your sizes. Both "passes" and "swapflag" are bytes, but you sometimes move a 32 bit register in and out of them. This can overwrite the next variable. I don't know if it's a problem or not.
Best,
Frank