Nasm Coding Question

[Mettalknight]

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.

Code: [Select]

    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
.

[Frank Kotler]

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.

Code: [Select]

    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...

Code: [Select]

    ...
    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

[Mettalknight]

Hey Frank,
I currently can't test the nasm but do you mean something along these lines?

Code: [Select]

    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


[Frank Kotler]

Well... no. Not exactly.

Code: [Select]

    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

[Mettalknight]

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.

Code: [Select]

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


[Frank Kotler]

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...

Code: [Select]

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

[Mettalknight]

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.

[Mettalknight]

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:

Code: [Select]

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



[AnonDude]

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!

[Frank Kotler]

Hi AnonDude,

Thanks for joining us! You are correct:

Code: [Select]

  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:

Code: [Select]

; 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:

Code: [Select]

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...

Code: [Select]

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