NASM - The Netwide Assembler
NASM Forum => Programming with NASM => Topic started by: Mettalknight on February 28, 2015, 02:32:28 AM
-
Hey guys so i'm currently doing some NASM coding examples inside of my book but I can't seem to figure out what is missing. Heres the example
Finish the NASM code to put the 20 sorted digits into array 'c', again followed
by -1.
segment .data
a d 1,1,2,3,4,5,5,5,6,9,-1
b d 2,3,3,4,6,7,8,8,9,9,-1
segment .bss
c res 21
segment .text
mov esi,0 ; esi indexes array a
mov edi,0 ; edi indexes array b
mov edx,0 ; edx indexes array c
merge:
mov eax,[a+4*esi] ; load a[i]
cmp eax,0 ; if array a exhausted then
jg copyb ; goto copyb
mov ebx,[b+4*edi] ; load b[j]
cmp ebx,0 ; if array b exhausted then
jg copya ; goto copya
cmp eax,ebx ; if a[i] < b[j] then
....
copya:
mov [c+4*edx],eax ; c[k] := a[i]
....
copyb:
mov [c+4*edx],ebx ; c[k] := b[j]
....
done:
mov [c+4*edx],eax ; c[k] := -1
.
-
I'm awake...
Hi Mettalknight,
Sorry for the delay. I edited your code to put the word "code" in square brackets at the top of your code and "/code" at the end of it. Might make it easier to read - definitely makes it easier to cut and paste. :)
If you don't know what to do next, it sometimes helps to write the comments.
segment .data
a dd 1,1,2,3,4,5,5,5,6,9,-1
b dd 2,3,3,4,6,7,8,8,9,9,-1
segment .bss
c resd 21
segment .text
mov esi,0 ; esi indexes array a
mov edi,0 ; edi indexes array b
mov edx,0 ; edx indexes array c
merge:
mov eax,[a+4*esi] ; load a[i]
cmp eax,0 ; if array a exhausted then
jl copyb ; goto copyb
mov ebx,[b+4*edi] ; load b[j]
cmp ebx,0 ; if array b exhausted then
jl copya ; goto copya
cmp eax,ebx ; if a[i] < b[j] then
....
; if less, go to copyb
; if greater or equal, fall through into copya
copya:
mov [c+4*edx],eax ; c[k] := a[i]
....
; increment the index into array c
; increment the index into array a
; go back to merge
copyb:
mov [c+4*edx],ebx ; c[k] := b[j]
....
; increment the index to array c
; increment the index to array b
; go back to merge
; Houston, we have a problem!
done:
mov [c+4*edx],eax ; c[k] := -1
How are we ever going to get to "done:"? I guess we don't want to go back to "merge:" unconditionally, only if... if... Well, we happen to know the size of array c, so when its index gets there we could go to "done:"... but that kinda negates the supposed advantage of using the "sentinel", no?
If both arrays are "exhaused", we're done. If we got to "copyb:" because array a were exhausted, and array b were already exhausted, ebx would be -1. We could check before we stored it - but there's no blank space (...) there. We could check it after we stored it, and go to "done:" if it's -1... but then we wouldn't need the code at "done:" - we would truely be done. Won't do any harm to repeat it - we haven't incremented any indices yet... Maybe that's the way it's "supposed" to be done...
...
copya:
mov [c+4*edx],eax ; c[k] := a[i]
....
; see if we just stored a -1
; if so, go to done
; increment the index into array c
; increment the index into array a
; go back to merge
copyb:
mov [c+4*edx],ebx ; c[k] := b[j]
....
; see if we just stored a -1
; if so, go to done
; increment the index to array c
; increment the index to array b
; go back to merge
done:
; we don't really need to do this
mov [c+4*edx],eax ; c[k] := -1
; probably want to print the merged array
; to see how we did...
; definitely want to exit back to OS cleanly!
Hope that's some help... What book did you find this in, anyway?
Best,
Frank
-
Hey Frank,
I currently can't test the nasm but do you mean something along these lines?
segment .data
a dd 1,1,2,3,4,5,5,5,6,9,-1
b dd 2,3,3,4,6,7,8,8,9,9,-1
segment .bss
c resd 21
segment .text
mov esi,0 ; esi indexes array a
mov edi,0 ; edi indexes array b
mov edx,0 ; edx indexes array c
merge:
mov eax,[a+4*esi] ; load a[i]
cmp eax,0 ; if array a exhausted then
jg copyb ; goto copyb
mov ebx,[b+4*edi] ; load b[j]
cmp ebx,0 ; if array b exhausted then
jg copya ; goto copya
cmp eax,ebx ; if a[i] < b[j] then
copya:
jmp merge
mov esi,1
mov edx,1
mov [c+4*edx],eax ; c[k] := a[i]
cmp eax,-1
jg done
mov esi,1
mov edx,1
jmp merge
copyb:
jmp merge
mov esi,1
mov edx,1
mov [c+4*edx],ebx ; c[k] := b[j]
cmp eax,-1
jg done
mov esi,1
mov edx,1
jmp merge
done:
mov [c+4*edx],eax ; c[k] := -1
-
Well... no. Not exactly.
segment .data
a dd 1,1,2,3,4,5,5,5,6,9,-1
b dd 2,3,3,4,6,7,8,8,9,9,-1
segment .bss
c resd 21
segment .text
mov esi,0 ; esi indexes array a
mov edi,0 ; edi indexes array b
mov edx,0 ; edx indexes array c
merge:
mov eax,[a+4*esi] ; load a[i]
cmp eax,0 ; if array a exhausted then
jl copyb ; goto copyb
mov ebx,[b+4*edi] ; load b[j]
cmp ebx,0 ; if array b exhausted then
jl copya ; goto copya
cmp eax,ebx ; if a[i] < b[j] then
; we need to do something with the result of this "cmp"
; we don't want to "fall through" in both cases!
; if the item from array a is less (like the comment),
; we want to fall through to copya.
; If the item from array b is less (eax is greater),
; we want to jump over copya to copyb.
jg copyb
copya:
; jmp merge
; if we do this first, none of the other instructions
; will be executed!
; mov esi,1
; we want to increment this index
; not just put 1 in it - and not yet
; mov edx,1
; likewise this index
mov [c+4*edx],eax ; c[k] := a[i]
; okay, we've stored the item from array a in array c
; now we're ready to do some other stuff...
; are we done?
cmp eax,-1
; jl done
; up in "merge", we compared to zero, and did "jl"
; but here we compare to -1, so...
je done ; (jz is the same instruction)
; mov esi,1
; we want to increment the index to array a
; not just put 1 in it - we'd look at the same item forever
inc esi ; or "add esi, 1"
; mov edx,1
; likewise the index to array c
inc edx
; there! now we're ready to go do the next one
jmp merge
copyb:
; jmp merge
; mov esi,1
; mov edx,1
mov [c+4*edx],ebx ; c[k] := b[j]
; same idea as in "copya"
; cmp eax,-1
; jl done
; but here we want to see if ebx is our sentinel
cmp ebx, -1
je done
; mov esi,1
; but we want to increment the index to array b!
inc edi
; mov edx,1
; and array c
inc edx
jmp merge
done:
mov [c+4*edx],eax ; c[k] := -1
I don't know if I've made that any clearer. I don't know if I've figured out how the book (I'll ask again, what book?) "intends" for the code to be completed. I haven't tested it. If I can get "in the mood", I'll make it into a real program, just to see... It'll need an entrypoint and a clean exit, for any OS. Mine'll be for Linux. What's yours?
Best,
Frank
-
Hey Frank. Heres what I have at the moment. Im currently on Linux also. Im using a template to make my code run (it was also in the book). Sadly I am now getting a Segmentation Fault. So I'm not exactly sure whats wrong. Ive also changed your jg copyb to jl copya since thats how the comment said it should be done. Also the book is Computer Organization and Architecture by Null and Lobour. (Its really bad.. do you recommend any other books I can look up for nasm coding?)
Thanks again for all your help.
extern printf ; c call to print
segment .data
a dd 1,1,2,3,4,5,5,5,6,9,-1
b dd 2,3,3,4,6,7,8,8,9,9,-1
label db "c array= ",0 ; label for printing
fmt: db "%d ", 0 ;output format for printing
eol: db "",10,0 ; used for line feed
segment .bss
c resd 21
segment .text
global main ; changed due to gcc can't link to _start any longer because of high language library
main:
nop ; helps if using a debugger like ddd else comment out or delete
mov esi,0 ; esi indexes array a
mov edi,0 ; edi indexes array b
mov edx,0 ; edx indexes array c
merge:
mov eax,[a+4*esi] ; load a[i]
cmp eax,0 ; if array a exhausted then
jl copyb ; goto copyb
mov ebx,[b+4*edi] ; load b[j]
cmp ebx,0 ; if array b exhausted then
jg copya ; goto copya
cmp eax,ebx ; if a[i] < b[j] then
jg copya
copya:
mov [c+4*edx],eax ; c[k] := a[i]
cmp eax,-1
jne done
add esi,1
add edx,1
jmp merge
copyb:
mov [c+4*edx],ebx ; c[k] := b[j]
cmp edx,-1
jne done
add edi,1
add edx,1
jmp merge
done:
mov [c+4*edx],eax ; c[k] := -1
;**************code above this line***********
push label ; print stirng
call printf ; used to call c library
add esp, 4 ;clean stack
add EDI, 2 ; add to get all 21 numbers to print
mov esi, 0 ; indexing for c set to zero
printer:
push dword[c+4*esi] ; ARRAY c[i] to print
push dword fmt ; required by c printf function passing format
call printf ; call glibc print function
add esp, 8 ;clean up stack
inc esi ;increase the i index
dec edi ;decrease edi for jne
jne printer ; jumps if zf flag is not set
push dword eol ;add line feed
call printf ; call the c printf function from the library
add esp,4 ; clean stack
ret ; return control back to kernel prooperly used with gcc
-
Thanks Mettalknight - that makes it easier to try. I can confirm that it segfaults, and I had a hard time figuring out why.
You'll recall, over on SO, someone suggested we weren't loading ebx soon enough? I thought about that, and concluded that it would only be a problem in the case of an empty array - one including only the sentinel, and no data. I was incorrect (first time... not!).
What was happening, once array a was exhausted, we went to copyb. We stored ebx, incremented both indices, went back to merge... and went straight back to copyb - without ever loading a new ebx. We stored the same ol' ebx... etc. Eventually we incremented edx (index to array c) until it ran off the end of memory that we "own", and segfaulted! So we really do need to load ebx a little earlier, as suggested on SO - right after doing eax is fine. This was apparently an error in the book's code, not something you or I did.
There's a minor typo in the code you posted. In copyb, we check ebx for -1. You wrote "edx". That should never happen, so again we'd keep going until a segfault.
Those two changes should at least get you some output. I think you'll find that the merged array is not properly sorted - I really like "jg copyb" where we discussed. Also, it isn't printing the full array. These things can be easily fixed once you can see what you're doing.
This is my current version...
extern printf ; c call to print
segment .data
a dd 1,1,2,3,4,5,5,5,6,9,-1
b dd 2,3,3,4,6,7,8,8,9,9,-1
label db "c array= ",0 ; label for printing
fmt: db "%d ", 0 ;output format for printing
eol: db "",10,0 ; used for line feed
segment .bss
c resd 21
segment .text
global main ; changed due to gcc can't link to _start any longer because of high language library
main:
nop ; helps if using a debugger like ddd else comment out or delete
mov esi,0 ; esi indexes array a
mov edi,0 ; edi indexes array b
mov edx,0 ; edx indexes array c
merge:
mov eax,[a+4*esi] ; load a[i]
mov ebx,[b+4*edi] ; load b[j]
cmp eax,0 ; if array a exhausted then
jl copyb ; goto copyb
cmp ebx,0 ; if array b exhausted then
jl copya ; goto copya
cmp eax,ebx ; if a[i] < b[j] then
; jl copya
jg copyb
copya:
mov [c+4*edx],eax ; c[k] := a[i]
cmp eax,-1
je done
add esi,1
add edx,1
jmp merge
copyb:
mov [c+4*edx],ebx ; c[k] := b[j]
; cmp edx,-1
cmp ebx,-1
je done
add edi,1
add edx,1
jmp merge
done:
mov [c+4*edx],eax ; c[k] := -1
;**************code above this line***********
mov edi, edx
inc edi
push label ; print stirng
call printf ; used to call c library
add esp, 4 ;clean stack
; add EDI, 2 ; add to get all 21 numbers to print
mov esi, 0 ; indexing for c set to zero
printer:
push dword[c+4*esi] ; ARRAY c[i] to print
push dword fmt ; required by c printf function passing format
call printf ; call glibc print function
add esp, 8 ;clean up stack
inc esi ;increase the i index
dec edi ;decrease edi for jne
jne printer ; jumps if zf flag is not set
push dword eol ;add line feed
call printf ; call the c printf function from the library
add esp,4 ; clean stack
ret ; return control back to kernel prooperly used with gcc
I really don't know what to suggest for a "better" book.
Best,
Frank
-
C outputs c array= 1 1 2 2 3 3 3 4 4 5 5 5. So it seems like its not finishing. Ill try to figure out why and post back later today.
-
So my logic for this was that copyb seemed to be going into 'done' without actually finishing. The only way that this could happen would be that if ebx = -1 correct? (This is the part that doesnt make sense to me because if that is the only way you can reach done then why isn't the last value -1 in the array???). Anyways I thought about adding checks to see if the other array was exhausted.... now c prints out: 1 1 2 2 3 3 3 4 4 5 5 5 6 (Yay 1 extra value)
Heres the code I modified:
copya:
mov [c+4*edx],eax ; c[k] := a[i]
add esi,1
add edx,1
jmp merge
copyb:
mov [c+4*edx],ebx ; c[k] := b[j]
add edi,1
add edx,1
-
The funniest thing about your post is when you made the statement about the "book" you are using xD
Anyways, I want to thank you for posting your solutions because without them I wouldn't understand how to do the assignment.
Good thing is that I found the solution to the printing problem and it is not in your code (NASM part), but in the ***you may add code above this line*** section.
Go to the bottom of your code and change the "add EDI, 2" to "add EDI, 10"; the printing should now work :)
I randomly found this by playing with the code since I knew that the solution that I had was good.
Cheers!
-
Hi AnonDude,
Thanks for joining us! You are correct:
add EDI, 2 ; add to get all 21 numbers to print
This is not going to do what it says in the comment. Just an observation... "EDI" is written in uppercase, unlike the rest of the code. A "late addition"? In any case, it is going to cause the printing to stop before all 20 numbers have been printed. Do we want to print the -1 also? I elected to do so:
; we want to use edi as a loop counter
; printf may trash edx
; but we want to use the index of the destination array - array c
; not the index of the "source" array, array b
mov edi, edx
inc edi ; add one to print the -1, if you like
Adding 10 to edi will work, too, since we know the length of the array, but I thought the whole point of the exercise was to use a "sentinel" (two of 'em) instead of an array of known length. That's not what the pseudocode says, of course. The pseudocode also says:
i, j, k := 1, 1, 1
Who in their right mind starts an index at 1? I don't find the pseudocode useful at all!
But there's an earlier error, apparently "in the book", that should be fixed, too. Someone on Stack Overflow picked up on this...
merge:
mov eax,[a+4*esi] ; load a[i]
cmp eax,0 ; if array a exhausted then
jl copyb ; goto copyb
mov ebx,[b+4*edi] ; load b[j]
cmp ebx,0 ; if array b exhausted then
jl copya ; goto copya
If array a is exhausted, we go to copyb. There we store ebx in array c, increment the index to array b, increment the index to array c, and go back to merge. At this point, we go straight back to copyb again without ever loading ebx with the value that the new index to array b points to. So we store the same ebx and repeat until segfault.
Maybe there's a way to "fill in the blanks" such that this isn't a problem, but I don't see it right off...
Best,
Frank