Tracing a NCR assembly program of MASM

Question

I missed the session when our lecturer explained it..

I know the formulae for NCR

NCR = N! / (R! * (N-R)!)

I am not following the NCR PROC, as no factorial is found, and some creepy recursive jobs are being done there. Help would be really appreciated.

print macro str
    lea dx,msg
    mov ah,09h
    int 21h
endm

.model small
.data
    n dw 15
    r dw 6
    ncr dw 1
    msg db "The NCR is : ","$"
.code
     start: mov ax,@data
            mov ds,ax

            mov bx,n
            mov cx,r
            inc bx
            call ncr1
            print msg          
            mov ax,ncr
            call display

            mov ah,4ch
            int 21h

          ncr1 proc
                cmp cx,00      
                  je l1
                push cx         
                dec cx
                call ncr1        
                mov ax,bx       
                pop cx          
                sub ax,cx       
                mul ncr         
                div cx          
                mov ncr,ax      
              l1 : ret
          ncr1 endp

          display proc
                aam
                add ax,3030h
                mov bx,ax
                mov dl,bh
                mov ah,02h
                int 21h
                mov dl,bl
                mov ah,02h
                int 21h                
             ret
      display endp

end start

" no factorial is found" - that is the purpose of the recursion. Note that `cx` is decremented for the next recursion, which terminates when `0` is reached. — Weather Vane, May 30 '16 at 18:52
Also it's broken code because `ncr` is used without being initialized. — Jester, May 30 '16 at 18:53
Pencil and paper: make a table of register and data values, follow a few invocations *by hand* to see what happens. — Weather Vane, May 30 '16 at 18:56
Are you sure this code comes from a lecturer? Beside the obvious mistakes and bad practices of this weak attempt of implementation, the author seems to have interpreted the ubiquitous nCr formula as *(n!/r!) * (n-r)!* which is something, for the sake of my sanity, I need to know it doesn't come from someone allowed to teach. — Margaret Bloom, May 30 '16 at 19:36
@MargaretBloom no, that's not the formula it tries to do, but I agree with the rest of your comment :) — Jester, May 30 '16 at 19:38
@Jester I'm having an hard time figuring out how the code computes nCr, at each step doesn't it first multiplies *(n-r)* and *n* and then divides by *r*? — Margaret Bloom, May 30 '16 at 19:52
It's doing `ncr(n,r)=ncr(n,r-1)*(n-r+1)/r`. The `(n-r)` is misleading, I just realized it does an `inc bx` before the function is called so that's actually `(n+1-r)` which is in fact correct. — Jester, May 30 '16 at 20:03
I got this program from one of my classmates who attended the session... No directly from our lecturer... I got it, there is something wrong with the code... Sorry for that... Hmm.. Suggest me any other methods for ncr ? — c0degeas, May 30 '16 at 20:10
As a quick and ugly hack, replace `ncr dw ?` with `ncr dw 1`. — Jester, May 30 '16 at 20:15
@ Jester : Yup.. Changed that... & @ivan_pozdeev : Need the Tracing / Brief Analysis of "ncr proc" section.... — c0degeas, May 30 '16 at 22:56

score 3 · Accepted Answer · edited May 23 '17 at 12:07

Okay, I see some reuse value in showing how to analyze chunks of assembler code, so here it is.

We're dealing with a subroutine here, a chunk of code that's supposed to be relatively autonomous.

So, first, let's determine the raw effect it has on the program: its inputs, outputs and effect on sp - i.e. its calling convention and signature.

Which entities does it use that are not set by it?

ncr1 proc
    cmp cx,00    # <-- cx
      je l1
    push cx
    dec cx
    call ncr1
    mov ax,bx    # <--bx
    pop cx
    sub ax,cx
    mul ncr      # <--ncr
    div cx
    mov ncr,ax
  l1 : ret
ncr1 endp

Which entities does it modify and not restore afterwards?

ncr1 proc
    cmp cx,00
      je l1
    push cx      # cx->local_stack[-2]
    dec cx       # -->cx? (overridden)
    call ncr1
    mov ax,bx
    pop cx       # local_stack[-2]->cx => cx restored
                 # (the next step is actually needed to deduce push/pop
                 # correspondence so they should be done in parallel)
    sub ax,cx
    mul ncr      # -->ax,dx
    div cx
    mov ncr,ax   # -->ncr
  l1 : ret
ncr1 endp

Only the last changes to the entities are marked (since they prevail over earlier ones).

Does it have any net effect on sp? (numbers are current sp relative to the return address)

ncr1 proc
    cmp cx,00
      je l1
    push cx     #-2
    dec cx
    call ncr1   #delta is same as self
    mov ax,bx
    pop cx      #0
    sub ax,cx
    mul ncr
    div cx
    mov ncr,ax
  l1 : ret      #without an argument, only cleans the return address
ncr1 endp

It doesn't (so "same as self" is 0), and 0 in all cases at ret confirms that it handles the local stack correctly.

Concluding, its signature is:

ncr1 (cx,bx,ncr) -> ax,dx,ncr

Where ax and dx are probably unused (but they are still volatile). And the calling convention is custom pure register with one hardcoded in/out parameter.

Now, all that leaves is to track which physical - and then, conceptual - value each entity holds at any time:

ncr1 proc  --initially: bx=N, cx=R (metavariables)
    cmp cx,00    # if R==0:
      je l1      #   ret (ax,dx,ncr unchanged)
    push cx      #[-2]=R
    dec cx       #cx=R-1
    call ncr1    #ncr1(N,R-1) -> ax,dx,ncr(probably the result)
    mov ax,bx    #ax=N
    pop cx       #cx=[-2]=R
    sub ax,cx    #ax=N-R
    mul ncr      #dx:ax=(N-R)*ncr = (N-R)*ncr1(N,R-1)
    div cx       #ax=[(N-R)*ncr1(N,R-1)]/R
    mov ncr,ax   #ncr=[(N-R)*ncr1(N,R-1)]/R
  l1 : ret
ncr1 endp        # -> ax,dx,ncr(the result, now we're sure)

Here it is: the procedure calculates (N,R) -> [(N-R)*ncr1(N,R-1)]/R where N=bx, R=cx and the result is ncr (which is mutated).

Which looks suspicious: (N-R) shall be (N+1-R) in the canonical formula as per comment62556150. If we substitute n=N-1, it'll become: (n+1,R) -> [(n+1-R)*ncr(n+1,R-1)]/R which looks okay (the first argument never changes)... so the procedure actually calculates nCr(n-1,r).

The choice to pass n+1 must be because n only goes into the formula as n+1, so by this, we save cycles on increasing it each time.

I got the concept... Thanks for your analysis... It became clear that this program is following the formulae “nCr = [ (n+1-r).(n+1-r-1).(n+1-r-2).......(n+1-2).(n+1-1) ] / r!”... — c0degeas, May 31 '16 at 10:40
@PrashantShahi Yes, represented in the regular form, it's an alternative (and easier to compute) formula for nCr. In combinatorics, `n*(n-1)*...*(n-r+1)` is called _"`r`th falling factorial power of `n`"._ — ivan_pozdeev, May 31 '16 at 11:55
This is a great answer to a newbie question. I really like the way you describe and show analysing the inputs/outputs of the function. First, as a separate step to take in the first place, and the really clear way of showing it with commented source code. I added a link to this from [the x86 tag wiki](http://stackoverflow.com/tags/x86/info). — Peter Cordes, May 31 '16 at 14:16

Tracing a NCR assembly program of MASM

1 Answers1

Linked