From cfc9644eb370055a70f3f00a957171630d207007 Mon Sep 17 00:00:00 2001 From: Jose Antonio Ortega Ruiz Date: Mon, 18 Feb 2013 06:06:11 +0100 Subject: Additional samples and doc from TAOCP, via ESR's MIXAL --- samples/Makefile.am | 4 +- samples/elevator.mixal | 305 +++++++++++++++++++++++++++++++++++++++++++++++++ samples/mystery.mixal | 28 +++++ 3 files changed, 336 insertions(+), 1 deletion(-) create mode 100644 samples/elevator.mixal create mode 100644 samples/mystery.mixal (limited to 'samples') diff --git a/samples/Makefile.am b/samples/Makefile.am index 7ec030a..19c9c27 100644 --- a/samples/Makefile.am +++ b/samples/Makefile.am @@ -13,4 +13,6 @@ SUBDIRS = tests EXTRA_DIST = primes.result hello.mixal primes.mixal echo.mixal \ - permutations.mixal permutations.cardrd isains.mixal + permutations.mixal permutations.cardrd isains.mixal \ + elevator.mixal mistery.mixal + diff --git a/samples/elevator.mixal b/samples/elevator.mixal new file mode 100644 index 0000000..98e8f1d --- /dev/null +++ b/samples/elevator.mixal @@ -0,0 +1,305 @@ +*** The elevator simulation +in equ 1:1 Definition of fields +llink1 equ 2:3 within nodes +rlink1 equ 4:5 +nextinst equ 0:2 +out equ 1:1 +llink2 equ 2:3 +rlink2 equ 4:5 +*** Fixed-size tables and list heads +wait con *+2(llink1),*+2(rlink1) List head for WAIT list + con 0 NEXTTIME = 0 always +man1 con *-2(llink1),*-2(rlink1) This node represents action + con 0 M1 and it is initially the + jmp M1 sole entry in the WAIT list. +elev1 con 0 This node represents the + con 0 elevator actions, except + jmp E1 for E5 and E9. +elev2 con 0 This node represents the + con 0 independent elevator + jmp E5 at E5. +elev3 con 0 This node represents the + con 0 independent elevator + jmp E9 at E9. +avail con 0 Link to available nodes +time con 0 Current simulated time +queue equ *-3 + con *-3(llink2),*-3(rlink2) List head for QUEUE[0] + con *-3(llink2),*-3(rlink2) List head for QUEUE[1] + con *-3(llink2),*-3(rlink2) All queues initially + con *-3(llink2),*-3(rlink2) are empty + con *-3(llink2),*-3(rlink2) List head for QUEUE[4] +elevator equ *-3 + con *-3(llink2),*-3(rlink2) List head for ELEVATOR + con 0 + con 0 "Padding" for CALL table + con 0 (see lines 183-186) + con 0 +call con 0 CALLUP[0], CALLCAR[0], CALLDOWN[0] + con 0 CALLUP[1], CALLCAR[1], CALLDOWN[1] + con 0 CALLUP[2], CALLCAR[2], CALLDOWN[2] + con 0 CALLUP[3], CALLCAR[3], CALLDOWN[3] + con 0 CALLUP[4], CALLCAR[4], CALLDOWN[4] + con 0 + con 0 "Padding" for CALL table + con 0 (see lines 178-181) + con 0 +D1 con 0 Indicates door open, activity +D2 con 0 Indicates prolonged standstill +D3 con 0 Indicates door open, inactivity +*** Subroutines and control routine +insert stj 9F Insert NODE(C) to left of NODE(rI1): + ld2 3,1(llink2) rI2 <- LLINK2(rI1). + st2 3,6(llink2) LLINK2(C) <- rI2. + st6 3,1(llink2) LLINK2(rI1) <- C. + st6 3,2(rlink2) RLINK2(rI2) <- C. + st1 3,6(rlink2) RLINK2(C) <- rI1. +9H jmp * Exit from subroutine. +delete stj 9F Delete NODE(C) from its list: + ld1 3,6(llink2) P <- LLINK2(C). + ld2 3,6(rlink2) Q <- RLINK2(C). + st1 3,2(llink2) LLINK2(Q) <- P. + st2 3,1(rlink2) RLINK2(P) <- Q. +9H jmp * Exit from subroutine. +immed stj 9F Insert NODE(C) first in WAIT list: + lda time + sta 1,6 Set NEXTTIME(C) <- TIME. + ent1 wait P <- LOC(WAIT). + jmp 2F Insert NODE(C) to right of NODE(P). +hold add time rA <- TIME + rA. +sortin stj 9F Sort NODE(C) into WAIT list. + sta 1,6 Set NEXTTIME(C) <- rA. + ent1 wait P <- LOC(WAIT). + ld1 0,1(llink1) P <- LLINK1(P). + cmpa 1,1 Compare NEXTTIME fields, right to left. + jl *-2 Repeat until NEXTTIME(C) >= NEXTTIME(P). +2H ld2 0,1(rlink1) Q <- RLINK1(P). + st2 0,6(rlink1) RLINK1(C) <- Q. + st1 0,6(llink1) LLINK1(C) <- P. + st6 0,1(rlink1) RLINK1(P) <- C. + st6 0,2(llink1) LLINK1(Q) <- C. +9H jmp * Exit from subroutine. +deletew stj 9F Delete NODE(C) from WAIT list: + ld1 0,6(llink1) (This is same as lines 58-63 + ld2 0,6(rlink1) except LLINK1, RLINK1 are used + st1 0,2(llink1) instead of LLINK2, RLINK2.) + st2 0,1(rlink1) +9H jmp * +cycle1 stj 2,6(nextinst) Set NEXTINST(C) <- rJ. + jmp cycle +holdc stj 2,6(nextinst) Set NEXTINST(C) <- rJ. + jmp hold Insert NODE(C) in WAIT, delay (rA). +cycle ld6 wait(rlink1) Set current node C <- RLINK1(LOC(WAIT)). + lda 1,6 NEXTTIME(C) + sta time becomes new value of simulated TIME. + jmp deletew Remove NODE(C) from WAIT list. + jmp 2,6 Jump to NEXTINST(C). +*** Coroutine M. M1. Enter, prepare for successor. +M1 jmp values Computer IN, OUT, INTERTIME, GIVEUPTIME. + lda intertime INTERTIME is computed by VALUES subroutine. + jmp hold Put NODE(C) in WAIT, delay INTERTIME. + ld6 avail C <- AVAIL. + j6p 1F If AVAIL != A, jump. + ld6 poolmax + inc6 4 C <- POOLMAX + 4 + ld6 poolmax POOLMAX <- C. + jmp *+3 +1H lda 0,6(rlink1) + sta avail AVAIL <- RLINK1(AVAIL). + ld1 infloor rI1 <- INFLOOR (computed by VALUES above). + st1 0,6(in) IN(C) <- rI1. + ld2 outfloor rI2 <- OUTFLOOR (computed by VALUES). + st2 3,6(out) OUT(C) <- rI2. + enta 39 Put constant 39 (JMP operation code) + sta 2,6 into third word of node format (6). +M2 enta 0,4 M2. Signal and wait. Set rA <- FLOOR. + deca 0,1 FLOOR <- IN + st6 temp Save value of C. + janz 2F Jump if FLOOR != IN. + ent6 elev1 Set C <- LOC(ELEV1). + lda 2,6(nextinst) Is elevator positioned at E6? + deca E6 + janz 3F + enta E3 If so, reposition at E3. + sta 2,6(nextinst) + jmp deletew Remove it from WAIT list + jmp 4F and reinsert it at front of WAIT. +3H lda D3 + jaz 2F Jump if D3 = 0. + st6 D1 Otherwise set D1 != 0. + stz D3 Set D3 <- 0. +4H jmp immed Insert ELEV1 at front of WAIT list. + jmp M3 (rI1, rI2 have changed.) +2H dec2 0,1 rI2 <- OUT - IN. + enta 1 + j2p *+3 Jump if going up. + sta call,1(5:5) Set CALLDOWN(IN) <- 1. + jmp *+2 + sta call,1(1:1) Set CALLUP(IN) <- 1. + lda D2 + jaz decision If D2 = 0, call the DECISION subroutine. + lda elev1+2(nextinst) + deca E1 If the elevator is at E1, call + jaz decision the DECISION subroutine. +M3 ld6 temp M3. Enter queue. + ld1 0,6(in) + ent1 queue,1 rI1 <- LOC(QUEUE[IN]). + jmp insert Insert NODE(C) at right end of QUEUE[IN]. +M4A lda giveuptime + jmp holdc Wait GIVEUPTIME units. +M4 lda 0,6(in) M4. Give up. + deca 0,4 IN(C) - FLOOR + janz *+3 + lda D1 FLOOR = IN(C) + janz M4A See exercise 7. +M6 jmp delete M6. Get out. MODE(C) is deleted + lda avail from QUEUE or ELEVATOR. + sta 0,6(rlink1) AVAIL <= C. + st6 avail + jmp cycle +M5 jmp delete M5. Get in. NODE(C) is deleted + ent1 elevator from QUEUE. + jmp insert Insert it at right of ELEVATOR. + enta 1 + ld2 3,6(out) + sta call,2(3:3) Set CALLCAR[OUT(C)] <- 1. + j5nz cycle Jump if STATE != NEUTRAL. + dec2 0,4 + ent5 0,2 Set STATE to proper direction. + ent6 elev2 Set C <- LOC(ELEV2). + jmp deletew Remove E5 action from WAIT list. + enta 25 + jmp E5A Restart E5 action 25 units from now. +*** Coroutine E. +E1A jmp cycle1 Set NEXTINST <- E1, go to CYCLE. +E1 equ * E1. Wait for call. (no action) +E2A jmp holdc +E2 j5n 1F E2. Change of state? + lda call+1,4 State is GOINGUP. + add call+2,4 + add call+3,4 + add call+4,4 + jap E3 Are there calls for higher floors? + lda call-1,4(3:3) If not, have passenger in the + add call-2,4(3:3) elevator called for lower floors? + add call-3,4(3:3) + add call-4,4(3:3) + jmp 2F +1H lda call-1,4 State is GOINGDOWN. + add call-2,4 + add call-3,4 + add call-4,4 + jap E3 Are there calls for lower floors? [right???] + lda call+1,4(3:3) If not, have passenger in the + add call+2,4(3:3) elevator called for higher floors? + add call+3,4(3:3) + add call+4,4(3:3) +2H enn5 0,5 Reverse direction of STATE. + stz call,4 Set CALL variable to zero. + janz E3 Jump if calls for opposite direction, + ent5 0 otherwise, set STATE <- NEUTRAL. +E3 ent6 elev3 E3. Open door. + lda 0,6 If activity E9 is already scheduled, + janz deletew remove it from the WAIT list. + enta 300 + jmp hold Schedule activity E9 after 300 units. + ent6 elev2 + enta 76 + jmp hold Schedule activity E5 after 76 units. + st6 D2 Set D2 != 0. + st6 D1 Set D1 != 0. + enta 20 +E4A ent6 elev1 + jmp holdc +E4 enta 0,4 E4. Let people out, in. + sla 4 Set OUT field of rA to FLOOR. + ent6 elevator C <- LOC(ELEVATOR). +1H ld6 3,6(llink2) C <- LLINK2(C). + cmp6 =elevator= Search ELEVATOR list, right to left. + je 1F If C = LOC(ELEVATOR), search is complete. + cmpa 3,6(out) Compare OUT(C) with FLOOR. + jne 1B If not equal, continue search, + enta M6 otherwise, prepare to send man to M6. + jmp 2F +1H ld6 queue+3,4(rlink2) Set C <- RLINK2(LOC(QUEUE[FLOOR])). + cmp6 3,6(rlink2) Is C = RLINK2(C)? + je 1F If so, the queue is empty. + jmp deletew If not, cancel action M4 for the man. + enta M5 Prepare to send man to M5. +2H sta 2,6(nextinst) Set NEXTINST(C). + jmp immed Put him at front of WAIT list. + enta 25 + jmp E4A Wait 25 units and repeat E4. +1H stz D1 Set D1 <- 0. + st6 D3 Set D3 != 0. + jmp cycle Return to simulate other events. +E5A jmp holdc +E5 lda D1 E5. Close door. + jaz *+3 Is D1 = 0? + enta 40 If not, people are still getting in or out. + jmp E5A Wait 40 units, repeat E5. + stz D3 If D1 = 0, set D3 <- 0. + enta 20 + ent6 elev1 +E6A jmp holdc Wait 20 units, then go to E6. +E6 j5n *+2 E6. Prepare to move. + stz call,4(1:3) If STATE != GOINGDOWN, CALLUP and CALLCAR + j5p *+2 on this floor are reset. + stz call,4(3:5) If != GOINGUP, reset CALLCAR and CALLDOWN. + j5z decision Perform DECISION subroutine. +E6B j5z E1A If STATE = NEUTRAL, go to E1 and wait. + lda D2 + jaz *+4 + ent6 elev3 Otherwise, if D2 != 0, + jmp deletew cancel activity E9 + stz elev3 (see line 202). + enta 15 + ent6 elev1 Wait 15 units of time. + j5n E8A If STATE = GOINGDOWN, go to E8. +E7A jmp holdc +E7 inc4 1 E7. Go up a floor. + enta 51 + jmp holdc Wait 51 units. + lda call,4(1:3) Is CALLCAR[FLOOR] or CALLUP[FLOOR] != 0? + jap 1F + ent1 -2,4 If not, + j1z 2F is FLOOR = 2? + lda call,4(5:5) If not, is CALLDOWN[FLOOR] != 0? + jaz E7 If not, repeat step E7. +2H lda call+1,4 + add call+2,4 + add call+3,4 + add call+4,4 + janz E7 Are there calls for higher floors? +1H enta 14 It is time to stop the elevator. + jmp E2A Wait 14 units and go to E2. +E8A jmp holdc +* ... (see exercise 8) + + + + + + + + + + + + + + + +E9 stz 0,6 E9. Set inaction indicator. + stz D2 D2 <- 0. + jmp decision Perform DECISION subroutine. + jmp cycle Return to simulation of other events. + +* (fill in VALUES, DECISION routines here) + +begin ent4 2 Start with FLOOR = 2 + ent5 0 and STATE = NEUTRAL. + jmp cycle Begin simulation. +poolmax end begin Storage pool follows literals, temp storage + +* Warning: there's probably a typo or two in this file. diff --git a/samples/mystery.mixal b/samples/mystery.mixal new file mode 100644 index 0000000..faa1775 --- /dev/null +++ b/samples/mystery.mixal @@ -0,0 +1,28 @@ +* Mystery program +* (Knuth, vol 1, p 153) + +printer equ 18 +buf orig *+3000 +1H ent1 1 + ent2 0 + ldx 4F +2H ent3 0,1 +3H stz buf,2 + inc2 1 + dec3 1 + j3p 3B + stx buf,2 + inc2 1 + inc1 1 + cmp1 =75= + jl 2B + enn2 2400 + out buf+2400,2(printer) + inc2 24 + j2n *-2 + hlt + +4H con "aaaaa" + end 1B + +* End of mystery.mix -- cgit v1.2.3