title	Ackermann Funktion
	name	('ACKERMANN')

; Die Ackermann Funktion
; In der Praxis findet diese Funktion Verwendung,
; um die Effizienz von Prozeduraufrufmechanismen zu testen.
;
; Definition:
;
;  A(x,y) = A(x-1,A(x,y-1))
;  A(0,y) = y+1
;  A(x,0) = A(x-1,1)
;

	entry	$memry

MAX_X	equ	1		; Maximale Zeichenlaenge fuer X-Wert
MAX_Y	equ	1		; Maximale Zeichenlaenge fuer Y-Wert

klJA	equ	'j'
grJA	equ	klJA AND 0dfh

OS	equ	0000h
BDOS	equ	0005h
MEMTOP	equ	BDOS+1

.conout	equ	 2
.condir	equ	 6
.string	equ	 9
.kbdlin	equ	10
.consta	equ	11

tab	equ	09h
lf	equ	0ah
cr	equ	0dh
eot	equ	'$'

	ld	sp,(MEMTOP)	; Stack laden
NeueEingabe:
	ld	de,$EINGABE
	call	StrgOut		; Angabe, was benoetigt wird
	ld	de,$ZEILE
	call	ZeileLesen	; Daten eingeben
	ld	de,$ZEILE+2	; Auf Eingabe zeigen
	ld	ix,A.X		; Auf Ziel verweisen
	call	Analyse		; Zahlen einlesen
	jr	c,NeueEingabe	; Bis Zahlen ok
	ld	hl,($memry)
	ld	de,32
	add	hl,de
	ld	(AckMin),hl	; Ackermann Daten setzen
	ld	hl,(A.X)	; Startwerte holen
	ld	de,(A.Y)
	call	ACKERMANN	; Funktion ausfuehren
	push	hl
	ld	bc,$RESULTAT
	ld	hl,(A.X)
	ld	de,(A.Y)
	call	AckerAusgabe	; Funktion aufrufen
	ld	a,'='
	call	ChrOut
	pop	hl
	call	Dezimal16Aus
	call	CrLf
	jr	_ENDE		; Das war's
ACKueber:
	ld	de,$SPEICHER
ACKende:
	call	StrgOut		; Fehlermeldung ausgeben
_ENDE:
	jp	OS		; Abbruch
;
; Funktion HL:=ACKERMANN(HL,DE)
;
ACKERMANN:
	exx
	ld	hl,0
	add	hl,sp
	ld	de,(AckMin)
	or	a
	sbc	hl,de		; Test ob noch Platz vorhanden ist
	jr	c,ACKueber	; Nein, Abbruch
	exx
;
	ld	bc,$ACKERMANN
	call	AckerAusgabe	; Funktion aufrufen
	call	Stacktiefe	; Stacktiefe anzeigen
	call	Iteration	; Iteration ausgeben
	call	IstAbbruch	; Abbruch testen
;
	ld	a,l		; Test Ende
	or	h
	jr	nz,ACKER1
	ld	hl,1
	add	hl,de		; ACKERMANN(0,DE) = DE+1
	ret	nc
	ld	de,$UEBERLAUF	; Fehlermeldung ausgeben
	jp	ACKende		; Abbruch
ACKER1:
	ld	a,e		; Test Spezialfall
	or	d
	jr	nz,ACKER2
	dec	hl		; Neuen Wert setzen
	ld	de,1
	call	ACKERMANN	; ACKERMANN(HL,0) = ACKERMANN(HL-1,1)
	ret
ACKER2:
	push	hl
	dec	de		; Neuen Wert setzen
	call	ACKERMANN	; F = ACKERMANN(HL,DE-1)
	ex	de,hl
	pop	hl
	dec	hl
	call	ACKERMANN	; ACKERMANN(HL,DE) = ACKERMANN(HL-1,F)
	ret
;
; Hilfs-Routinen
; ++++++++++++++
;
; Abbruch testen
;
IstAbbruch:
	call	IstTaste	; Tastatur testen
	ret	z
	call	ChrIn		; Letztes Zeichen lesen
	push	de
	push	hl
	ld	de,$ABBRECHEN
	call	StrgOut		; Soll unterbrochen werden?
	call	ChrWarte
	ld	de,$LEER
	call	StrgOut		; Meldung loeschen
	pop	hl
	pop	de
	cp	grJA		; Test Abbruch
	ret	nz
	ld	de,$ABBRUCH	; Ausgabe
	jp	ACKende		; Und Ende
;
; Gibt Funktion "Ackermann(HL,DE)" aus
;
AckerAusgabe:
	push	de
	push	hl
	push	de
	push	bc
	pop	de
	call	StrgOut		; Ergebnis ausgeben
	call	Dezimal16Aus
	ld	a,','
	call	ChrOut
	pop	hl
	call	Dezimal16Aus
	ld	a,')'
	call	ChrOut
	pop	hl
	pop	de
	ret
;
; Gibt die Stacktiefe aus
;
Stacktiefe:
	exx
	ld	hl,0
	add	hl,sp		; Stack kopieren
	inc	hl		; Aufruf beachten
	inc	hl
	ex	de,hl
	ld	hl,(MEMTOP)
	or	a
	sbc	hl,de		; Differenz holen
	srl	h
	rr	l
	ld	de,$STKTIEF
	call	StrgOut		; Ausgeben
	call	Dezimal16Aus
	exx
	ret
;
; Iteration ausgeben
;
Iteration:
	exx
	ld	de,$ITERATION
	call	StrgOut		; Ausgeben
	ld	hl,$ITERZEILE+IterLan-1
	ld	b,IterLan
	call	InkASCII	; ASCII Wert erhoehen
	exx
	ret
;
; ASCII Zahl in ^HL um 1 erhoehen, Laenge in Reg B
;
MehrASC:
	ld	a,(hl)		; Zeichen holen
	cp	'0'		; Test ob Ziffer
	jr	c,ASC.1
	cp	'9'+1
	jr	c,InkASCII
ASC.1:
	ld	(hl),'0'	; Neu setzen
InkASCII:
	inc	(hl)		; Erhoehen
	ld	a,(hl)
	cp	'9'+1		; Ueberlauf testen
	ret	nz		; Nein, dann fertig
	ld	(hl),'0'	; Neu setzen
	dec	hl
	djnz	MehrASC
	ld	de,$ITERFEHL
	jp	ACKende		; Abbruch bei Ueberlauf
;
; CP/M BDOS Routinen
; ++++++++++++++++++
;
; Konsolzeile schliessen
;
CrLf:
	ld	a,cr
	call	ChrOut
	ld	a,lf
;
; Zeichen im Akku auf Konsole ausgeben
;
ChrOut:
	push	hl
	push	de
	push	bc
	push	af
	ld	c,.conout
	ld	e,a
	jr	..BDOS		; Ausgabe
;
; Meldung in ^DE auf Konsole ausgeben
;
StrgOut:
	push	hl
	push	de
	push	bc
	push	af
	ld	c,.string
..BDOS:
	call	BDOS		; Ausgabe
..POPALL:
	pop	af
..POPREG:
	pop	bc
	pop	de
	pop	hl
	ret
;
; Zeile in ^DE einlesen
;
ZeileLesen:
	push	hl
	push	de
	push	bc
	push	af
	push	de
	ld	c,.kbdlin
	call	BDOS		; Eingabe
	pop	hl		; Zeile holen
	inc	hl
	ld	e,(hl)		; Aktuelle Laenge
	ld	d,0
	inc	de
	add	hl,de
	ld	(hl),cr		; Zeile schliessen
	call	CrLf
	jr	..POPALL
;
; Test ob Taste betaetigt
; Zero wird gesetzt wenn nicht
;
IstTaste:
	push	hl
	push	de
	push	bc
	ld	c,.consta
	call	BDOS		; Tastatur testen
	or	a		; Ergebnis setzen
	jr	..POPREG
;
; Eingabe eines Zeichens von Tastatur in den Akku
; Nicht auf Eingabe warten
;
ChrIn:
	ld	a,-1		; Kein Echo, nicht warten
..ChrIn:
	push	hl
	push	de
	push	bc
	ld	c,.condir
	ld	e,a
	call	BDOS		; Tastatur lesen
	jr	..POPREG
;
; Eingabe eines Zeichens von Tastatur in den Akku
; Auf Eingabe warten
;
ChrWarte:
	ld	a,-3		; Kein Echo, warten
	call	..ChrIn
	cp	klJA		; Test ob kleines JA
	ret	nz
	ld	a,grJA		; Als grosses JA zurueckgeben
	ret
;
; Zahlen aus ^DE in ^IX einlesen
; Carry wird gesetzt im Fehlerfall
;
Analyse:
	ld	b,','
	call	Dezimal16Ein	; Erste Zahl wandeln
	ret	c		; Fehler
	call	ZahlAblegen
	ld	b,cr
	call	Dezimal16Ein	; Zweite Zahl wandeln
	ret	c		; Fehler
ZahlAblegen:
	ld	(ix+0),l	; Zahl ablegen
	ld	(ix+1),h
	inc	ix
	inc	ix
	ret
;
; Eine Zahl aus ^DE nach HL wandeln
; Carry wird gesetzt im Fehlerfall
;
Dezimal16Ein:
	call	KeineBlanks	; Keine Leerzeichen vorne
	ld	hl,0		; Resultat setzen
	ld	a,(de)
        call    IstZiffer	; Test vorzeitiges Ende
	ret	c
NaechsteZiffer:
	ld	a,(de)		; Zeichen holen
	inc	de
	cp	b		; Test ob Ende
	ret	z
	call	IstZiffer
	ret	c		; Ende wenn ungueltig
	push	de
	call	Mult10		; Mit 10 multiplizieren
	pop	de
	ret	c		; Zahl zu gross
	push	bc
	ld	c,a		; Ziffer holen
	ld	b,0
	add	hl,bc		; Ziffer addieren
	pop	bc
	jr	nc,NaechsteZiffer
        ret
;
; Register HL mit 10 multiplizieren
; Carry wird gesetzt im Fehlerfall
;
Mult10:
	ld	d,h		; Alter Wert
	ld	e,l
	add	hl,hl		; * 2
	ret	c
	add	hl,hl		; * 4
	ret	c
	add	hl,de		; * 5
	ret	c
	add	hl,hl		; *10
	ret
;
; Test ob Zeichen im Akku numerisch
; Carry wird gesetzt wenn nicht
;
IstZiffer:
	cp	'9'+1		; Zeichen testen
	ccf
	ret	c
	cp	'0'
	ret	c
	sub	'0'		; Offset abziehen
	ret
;
; Leerzeichen in ^HL uebergehen
;
MehrLeer:
	inc	de
KeineBlanks:
	ld	a,(de)
	cp	' '		; Test Leerzeichen
	jr	z,MehrLeer	; Uebergehen
	cp	tab
	jr	z,MehrLeer	; Oder Tabulator
	ret
;
; Zahl im Register HL dezimal ausgeben
;
Dezimal16Aus:
	ld	de,$ZAHL
	call	ASCIIDezimal	; Zahl wandeln
	call	StrgOut		; Und ausgeben
	ret
;
; Zahl im Register HL in Puffer ^DE wandeln
;
ASCIIDezimal:
	push	de
	push	de
	pop	ix		; Adresse kopieren
	ld	de,DivTabelle	; Zeiger auf Tabelle
	push	de		; Ablegen
	ld	c,1		; Anzeige fuehrende Null
NaechsterWert:
	ex	(sp),hl
	ld	e,(hl)		; Divisor laden
	inc	hl
	ld	d,(hl)
	inc	hl
	ex	(sp),hl
	ld	b,-1		; Resultat voreinstellen
TabDivision:
	inc	b		; Quotienten bilden
	or	a
	sbc	hl,de		; Division
	jr	nc,TabDivision	; Test < 0
	add	hl,de		; Einstelen > 0
	xor	a		; Resultat loeschen
	or	b		; Test Ziffer Null
	jr	nz,SpeicherASCII
	or	c		; Test fuehrende Null
	jr	nz,KeineNull
SpeicherASCII:
	ld	c,0		; Keine fuehrende Null mehr
	or	'0'		; In ASCII wandeln
	ld	(ix+0),a	; Zeichen speichern
	inc	ix
KeineNull:
	ld	a,e		; Test Tabellenende
	cp	10
	jr	nz,NaechsterWert
	ld	a,l		; Letzte Ziffer holen
	or	'0'		; In ASCII wandeln
	ld	(ix+0),a	; Letzte Ziffer speichern
	ld	(ix+1),eot	; Endzeichen setzen
	pop	de		; Stack saeubern
        pop     de		; Adresse holen
        ret

	dseg

$ITERATION:
	db	' - Iteration: '
$ITERZEILE:
	db	'          1'
IterLan	equ	$-$ITERZEILE
	db	cr,lf,eot
$STKTIEF:
	db	' - Stacktiefe ',eot
$ABBRECHEN:
	db	'Taste gedrueckt - Lauf abbrechen (J,N) ? ',eot
$LEER:
	db	cr,'                                         ',cr,eot
$ABBRUCH:
	db	'Lauf abgebrochen',eot
$UEBERLAUF:
	db	'ABBRUCH: Ergebnis zu gross fuer die Berechnung',eot
$SPEICHER:
	db	'ABBRUCH: Zu wenig Speicher fuer die Berechnung',eot
$ITERFEHL:
	db	'ABBRUCH: Zu viele Iterationen',eot
$RESULTAT:
	db	cr,lf,'Ergebnis - '
$ACKERMANN:
	db	'Ackermann(',eot
$EINGABE:
	db	'Eingabe Ackermann(m,n): ',eot
$ZEILE:
	db	MAX_X+1+MAX_Y	; Laenge
	db	0
	ds	MAX_X+1+MAX_Y+1
;
$ZAHL:
	db	'65535',eot
A.X:
	dw	0
A.Y:
	dw	0
$memry:
	ds	2
AckMin:
	ds	2
DivTabelle:
	dw	10000
	dw	1000
	dw	100
	dw	10

	end