;  Purpose:	- "n choose k".
;  		- size of 16 Bit (take care of an overflow)
;
;
;
;-------------------------------------------------------------------------------------
;-------------------------------------------------------------------------------------
str_std_in  	equ  3fh		; read character from standard input with echo
ch_std_out    equ	02h 		; write character to standard output
st_std_out 	equ	40h		; write string to standard output
dos		equ	21h		; dos interrupt
exit		equ	4ch		; interuppt to exit
lf		equ	0ah       	; linefeed
cr		equ	0dh		; carriage return
base		equ	10        	; base:=10 dec
maxlng		equ	7		; max stringlength for 16 Bit number in ascii
;-------------------------------------------------------------------------------------
;
;cpu model:
;-------------------------------------------------------------------------------------
.MODEL 	SMALL,C
;-------------------------------------------------------------------------------------
;
;stack size
;-------------------------------------------------------------------------------------
.STACK	100H
;-------------------------------------------------------------------------------------
;
;decleration of variables
;-------------------------------------------------------------------------------------
.DATA

PWORD TYPEDEF NEAR PTR WORD


hello		BYTE	'This program calculates n choose k (result and arguments are only 16 BIT!!! K&N=0->exit)'
		BYTE	lf,cr				; <LFCR> and end of string

helloLNG	WORD	$-hello

Nmsg		BYTE lf,cr				; <LFCR> and end of string
              BYTE    'Please enter n:'
		BYTE	cr,lf				; <LFCR> and end of string
;NmsgOFF		WORD	Nmsg

Kmsg		BYTE lf,cr				; <LFCR> and end of string
		BYTE    'Please enter k:'
		BYTE	cr,lf				; <LFCR> and end of string
;KmsgOFF		WORD	Kmsg
NKmsgLNG	WORD	$-NKmsg

resmsg		BYTE lf,cr
  		BYTE    'Result:'
		BYTE	lf,cr				; <LFCR> and end of string
;resmsgOFF	WORD	resmsg
resmsgLNG	WORD	$-resmsg

error		BYTE lf,cr
		BYTE	'ERROR:Overflow!!!'			; <LFCR> and end of string
		BYTE	lf,cr				; <LFCR> and end of string
;errorOFF	WORD	error
errorLNG		WORD $-error

N_		WORD    ?
K		WORD    ?
result		WORD    ?
Narr		WORD	200 DUP(0)
Karr		WORD	200 DUP(0)



;-------------------------------------------------------------------------------------
.CODE
.STARTUP

;-------------------------------------------------------------------------------------
;Procedure Prototypes

;stringin: reads a string from standard input and writes it in the address of strOFF
stringin	PROTO NEAR C, strOFF:PWORD,strLNG:WORD,errOFF:WORD

;stringout: writes a string with the address of msgOFF to standard output
stringout	PROTO NEAR C, msgOFF:WORD ,msgLNG:WORD

;errormsg:  writes an errormessage with the address of errOFF to standard output
errormsg	PROTO NEAR C, errOFF:WORD

;convert: converts numbers saved in ascii to "real" numbers
convert		PROTO NEAR C, value:PWORD,msgOFF:WORD,msgLNG:WORD,errOFF:WORD

;fillN: fills the Narr with values depending on Nval and Kval
;fillN		PROTO NEAR C, Nval:WORD,Kval:WORD,arrN:WORD

;fillK: fills the Karr with values depending on Kval
fill		PROTO NEAR C,val:WORD,Kval:WORD,arr:WORD

;N_K: solves result of "n choose k" when solvable and returns result in res
N_K		PROTO NEAR C, Nval:WORD,Kval:WORD,arrN:PWORD,arrK:PWORD,res:PWORD,msgOFF:WORD,msgLNG:WORD,errOFF:WORD

;reconvert: converts "real" numbers to numbers in ascii and writes the result to standard out
reconvert	PROTO NEAR C, value:WORD,msgOFF:WORD,msgLNG:WORD
;-------------------------------------------------------------------------------------
;Programstart

INVOKE stringout,ADDR hello   ,helloLNG
.WHILE(1)
INVOKE convert, ADDR N_  ,ADDR Nmsg  ,NKmsgLNG,ADDR error
INVOKE convert, ADDR K   ,ADDR Kmsg  ,NKmsgLNG,ADDR error
  .IF((N_==0)&&(K==0))		; Exit Programm when K and N_ are 0
        jmp 	skip
  .ENDIF
INVOKE N_K, N_ ,K, ADDR Narr, ADDR Karr, ADDR result, ADDR resmsg,resmsgLNG,ADDR error
.ENDW
jmp	skip
skip:

;Exit to dos
	mov	AH,exit		; and exit via DOS
	int	dos		; [ same as .EXIT ]

;PROCEDURES
;-------------------------------------------------------------------------------------
;stringout: writes a string with the address of msgOFF to standard output
stringout 	PROC NEAR C USES BX CX DX, msg:WORD, lng:WORD

	mov 	BX,1			; write to screen
	mov	CX,lng		; write lng chars
	mov	AH,st_std_out	; prepare for string output
        mov	DX,msg		; DX <-- Offset of message
        int 	dos		     ; output to screen
RET
stringout	ENDP
;-------------------------------------------------------------------------------------
;errormsg:  writes an errormessage with the address of errOFF to standard output
errormsg	PROTO NEAR C, errOFF:WORD
errormsg 	PROC NEAR C USES BX CX DX, msg:WORD
	LOCAL lng:WORD
	mov 	BX,1		; write to screen
	mov	CX,19		; write lng chars
	mov	AH,st_std_out	; prepare for string output
        mov	DX,msg	        ; DX <-- Offset of message
        int 	dos		; output to screen
RET
errormsg	ENDP
;-------------------------------------------------------------------------------------
;stringin: reads a string from standard input and writes it in the address of strOFF
stringin 	PROC NEAR C USES BX CX DX,strOFF:PWORD,strLNG:WORD,errOFF:WORD

	sub 	BX,BX		; BX=0 =>read
	mov	AH,str_std_in	; standard input in ah
	mov  CX,strLNG		; CX=stringlength => string to read is at most strLNG long
	mov 	DX,strOFF		; DX = startadress string
	int	dos			; with DOS interrupt 21H/2
	.IF(AX>maxlng)
	INVOKE errormsg ,errOFF ; print errormsg
	mov	AX,1			; returnvalue no number checking necessary
	.ENDIF

RET
stringin 	ENDP

;-------------------------------------------------------------------------------------
;convert: converts numbers saved in ascii to "real" numbers
convert	PROC NEAR C USES BX CX DX SI,number:PWORD,msgOFF:WORD,msgLNG:WORD,errOFF:WORD
		LOCAL string[80]:BYTE, strlng:WORD,LNG:WORD,numADD:WORD

	mov 	LNG,80		; max stringlength of stringinput
	mov	BX,number	; copy address of number in BX
	mov	numADD,BX	; copy address of number in numADD
.REPEAT
begin:
INVOKE stringout,msgOFF ,msgLNG
INVOKE stringin ,ADDR string  ,LNG, errOFF
.IF(AX==1)
  	jmp 	begin
.ENDIF
;Check if only numbers wrere entered
 .IF (string[0]!=cr)
	sub	CX,CX           ; CX=0
	sub 	SI,SI		; SI=0
  .REPEAT
  .IF (string[SI]<'0')||(string[SI]>'9')
	mov	CX,1		; CX:=1 if there is no number from 0 to 9 in string[SI]
  .ENDIF
	inc	SI		; SI+1
  .UNTIL(string[SI]==cr)	; until carriage return in string [SI]
 .ENDIF
.UNTIL(CX==0)			; until only numbers from 0 to 9 were entered
	mov	strlng,SI	; copy the stringlength into strlng
;Horner
	mov	AL,string	; copy the first number in ascii into AL
	cbw			; convert BYTE to WORD (AX:=AL)
	sub	AX,'0'		; subtract '0'to convert ascii numbers to integers
	mov     SI,1		; SI:=1 the first character is converted

.WHILE (SI < strlng)
	mov	DX,base		; prepare DX for multiplication with 10
	mul	DX		; DX:AX=AX*DX
	jo	err1		; jump on overflow to errmessage
	mov	BX,AX		; copy result of multiplication into BX
	mov 	AL,string[SI]	; copy number ascii number in string[SI] into AL
	cbw			; convert BYTE to WORD (AX:=AL)
	sub     AX,'0'		; subtract '0' to convert ascii numbers to integers
	add	AX,BX		; add mutiplied number to number entered in string[SI]
	jc	err1		; jump on carry to erroormessage
	inc	SI		; SI++
.ENDW
	mov	BX,numADD
	mov	[BX],AX		; copy number in its address
	jmp   	skip1
err1:
INVOKE errormsg ,errOFF
	jmp	begin
skip1:
	RET
convert ENDP

;-------------------------------------------------------------------------------------
reconvert	PROC NEAR C USES BX CX DX SI DI CX,number:WORD,msgOFF:WORD,msgLNG:WORD
		LOCAL string[7]:BYTE, strLNG:WORD,LNG:WORD,strOFF:WORD

sub si,si
mov bx,base
mov ax,number

.while(ax>0)
	sub dx,dx 	;dx initialisieren
	div bx		;teilen mit basis
	push dx		;stack
	inc si		;länge des strings
.endw

mov strLNG,si
mov ax,number

mov bx,si
sub si,si

.while(si<bx)

	pop dx
	add dx,'0'
	mov string[si],dl

	inc si
.endw

	sub bx,bx
	add bx,strLNG
	mov strLNG,bx
	lea ax,string
	mov strOFF,ax

invoke stringout, msgOFF,msgLNG
invoke stringout,strOFF,strLNG

ret
reconvert endp
;-------------------------------------------------------------------------------------
;reconvert: converts "real" numbers to numbers in ascii and writes the result to standard out
;reconvert	PROC NEAR C USES BX CX DX SI DI CX,number:WORD,msgOFF:WORD,msgLNG:WORD
;		LOCAL string[7]:BYTE, strLNG:WORD,LNG:WORD,strOFF:WORD
;Stringlength
;
;	sub	SI,SI		; SI:=0
;	mov	BX,base		; copy base in BX
;	mov 	AX,number		; copy number in AX
;
;.WHILE(AX>0)
;	sub	DX,DX		; DX:=0 to divide only AX in next step!!!
;	div 	BX			; DX:AX/base DX:=Rest
;	;push dx
;	inc 	SI			; SI++
;.ENDW
;	mov	strLNG,SI		; copy stringlenth in strLNG
;
;Horner backwards
;
;	mov 	AX,number		; copy number in AX
;.IF(number==0)
;	mov	string[SI],'0'	; copy asci 0 in string[0]
;	inc	SI			; SI:=1
;	mov	strLNG,SI		; strLNG:=1
;.ENDIF
;
;	mov	string[SI+1],cr	; copy carriage return in string[SI+2]
;	mov	string[SI],lf   ; copy linefeed in string[SI+1]
;
;.WHILE(AX>0)
;	sub	DX,DX		; DX:=0 to divide only AX in next step!!!
;	div 	BX			; DX:AX/base DX:=Rest
;	add	DX,'0'		; DX:=DX+'0' convert digit in ascii
;	dec 	SI			; SI--
;	mov 	string[SI],DL	; copy char for each digit in string[SI]
;.ENDW
;
;	mov	BX,2
;	add	BX,strLNG	; add 2 to strLNG // necessary to print lf and cr
;	mov	strLNG,BX	; mov strLNG+2 back to strLNG
;	lea	AX,string	; AX:= address of string
;	mov	strOFF,AX	; stringOFF:= adress of string
;
;INVOKE stringout,msgOFF,msgLNG
;INVOKE stringout,strOFF,strLNG
;
;RET
;reconvert 	ENDP
;-------------------------------------------------------------------------------------
;N_K: solves result of "n choose k" when solvable and returns result in res
N_K	PROC NEAR C USES BX CX DX SI DI CX ,Nval:WORD,Kval:WORD,arrN:PWORD,arrK:PWORD,res:PWORD,msgOFF:WORD,msgLNG:WORD,errmsg:WORD
	LOCAL resOFF:WORD,arrNOFF:WORD,arrKOFF:WORD,num:WORD,denum:WORD

	mov	BX,arrN
	mov	arrNOFF,BX	; copy address of arrN in arrNOFF
	mov	BX,arrK
	mov	arrKOFF,BX	; copy address of arrK in arrKOFF
	mov	BX,res		;
	mov	resOFF,BX	; copy address of res in resOFF
	mov	AX,Kval

.IF(AX==0)||(Nval==AX)			;"n choose 0"
INVOKE reconvert, 1 ,msgOFF,msgLNG	;"n choose n"
	mov	DX,1			; both are 1
	mov	[BX],DX
	jmp	solved
.ENDIF
.IF(Nval<AX)				; n<k
INVOKE reconvert, 0 ,msgOFF,msgLNG	; result is 0
	mov	DX,0
	mov 	[BX],DX
	jmp	solved
.ENDIF
	inc	AX
.IF(Nval==AX)||(Kval==1)		;"n choose n-1"
INVOKE reconvert,Nval ,msgOFF,msgLNG    ;"n choose 1"
	mov	DX,Nval			; both are n
	mov 	[BX],DX
	jmp	solved
.ENDIF
	dec	AX			; AX := Kval again
	mov	BX,Nval			; BX := Nval
	shr	BX,1			; BX:=Nval/2
.IF(AX>BX)				; if (Kval>Nval/2)
	mov	BX,Nval			; BX := Nval again
	sub	BX,AX			; BX := Nval-Kval
	mov	Kval,BX			; Kval := Nval-Kval
.ENDIF


INVOKE fill, Kval,Kval,arrKOFF	;
INVOKE fill, Nval,Kval,arrNOFF	; länge ist Kval

;INVOKE fillK, Kval, arrKOFF		; fill the k array with values


	mov	AX,Kval			;
	mov	SI,2			;
	mul	SI			;
	mov	Kval,AX			; Kval:=Kval*2 to point on arrays Wordwise
	jo	err2			; jump on overflow to errormessage
	sub	CX,CX			; CX=0
	sub	DI,DI			; DI=0

.WHILE(CX<Kval)
	sub	DI,DI			; DI:=0
  .WHILE(DI<Kval)

        mov	BX,arrNOFF		;
	mov	SI,CX			;
    	mov	AX,[BX][SI]		; AX:= arrN[CX]
        mov	BX,arrKOFF		;
	mov	SI,DI			;
    	mov	BX,[BX][SI]		; BX:= arrK[DI]
     .IF(BX!=1)				; IF (arrK[DI]<>1)
	sub 	DX,DX			; DX := 0
    	div	BX			; AX := arrN[CX]/arrK[DI]
       .IF(DX==0)			; IF (arrN[CX] modulo arrK[DI] == 0)
    	mov	BX,arrNOFF		;
	mov	SI,CX			;
    	mov	[BX][SI],AX		; arrN[CX] := arrN[CX]/arrK[DI]
    	mov	BX,arrKOFF		;
	mov	SI,DI			;
	mov	AX,1			;
	mov	[BX][SI],AX		; arrK[DI] := 1
       .ENDIF
     .ENDIF
     	add	DI,2			;DI:=DI+2 to point on arrK Wordwise
   .ENDW
   	add	CX,2			;CX:=CX+2 to point on arrN Wordwise
.ENDW
	mov	AX,1			; AX:= 1
	mov	CX,Kval			; CX:=
.WHILE(CX>0)
	sub	CX,2
	mov	BX,arrNOFF		;
	mov	SI,CX			;
	mov	BX,[BX][SI]		; BX := arrN[CX]
	mul	BX			; AX := AX*arrN[CX]
	jo	err2			; jump on overflow to errormessage
    	mov	num,AX			; num := AX*arrN[CX]
	sub	DI,DI			; DI := 0
  .WHILE(DI<Kval)
        mov	BX,arrKOFF		;
	mov	SI,DI			;
    	mov	BX,[BX][SI]		; BX:= arrK[DI]
     .IF(BX!=1)				; IF (arrK[DI])
	sub 	DX,DX			; DX := 0 for division
    	div	BX			; AX := arrN[CX]*arrN[CX+1]*.../arrK[DI]
       .IF(DX==0)			; IF ((arrN[CX]*arrN[CX+1]*...) modulo arrK[DI] == 0)
    	mov	BX,arrKOFF		;
	mov	SI,DI			;
	mov	denum,AX		; denum := arrN[CX]*arrN[CX+1]*.../arrK[DI]
	mov	AX,1			;
	mov	[BX][SI],AX		; arrK[DI] := 1
        mov	AX,denum		; restore AX, AX := arrN[CX]*arrN[CX+1]*.../arrK[DI]
       .ENDIF
       .IF(DX!=0)
       	mov	AX,num			; restore AX, AX := arrN[CX]*arrN[CX+1]*...
       .ENDIF
     .ENDIF
     	add	DI,2			; DI := DI+2
   .ENDW
   				; CX := CX+2
.ENDW
INVOKE reconvert,AX ,msgOFF,msgLNG	; print AX converted to ascii on screen
	mov	BX,resOFF			;
	mov	[BX],AX			; res := AX
	jmp	solved
err2:
INVOKE errormsg ,ADDR error
solved:
RET
N_K 		ENDP
;-------------------------------------------------------------------------------------
;fill PROC NEAR C USES BX CX DX SI DI,Nval:WORD,Kval:WORD,arrN:WORD,arrK:WORD
;     LOCAL arrNOFF:WORD, arrKOFF:WORD

fill PROC NEAR C USES BX CX DX SI DI,val:WORD,Kval:WORD,arr:WORD
      LOCAL arrOFF:WORD

     mov bx,arr
     mov arrOFF,bx
     sub DI,DI
     sub cx,cx

     mov ax,val

.while(cx<Kval)

     mov [bx][di],ax
     sub ax,1
     inc cx
     add di,2
.endw

RET
fill	endp
end
;-------------------------------------------------------------------------------------