{File name: Stack.mc
Last Edited: Jim Frandeen, March 26, 1981 3:16 PM: change SuppressTimingWarning to LOOPHOLE[niblTiming],
Last Edited: Garner, April 8, 1980 5:29 PM,
Author: R. Garner,
Created: 12 April 1979,
Description: PrincOps version 3.0 microcode for Dandelion,
(ADD, SUB, DADD, and DSUB based on Wildflower microcode by R. Levin, 18 Oct 1978),
}

{The Stack mesa op-codes consist of the following.

OPvalbytesstktime

PUSH164’b1+11
POP165’b1—11
EXCH166’b1—2+21
DUP170’b1—1+21
NILCK171’b1—1+12
NILCKL172’b1—2+22
BNDCK173’b1—2+12
NEG256’b1—1+11
INC257’b1—1+11
DECxxxx1—1+11
ADD2xxxx1—1+11
ADDSBxxxx2—1+12
DBL253’b1—1+11
AND260’b1—2+11
OR261’b1—2+11
XOR262’b1—2+11
SHIFT263’b1—2+13
ADD250’b1—2+11
ADD01271’b1—2+11 {NOT in PrincOps}
SUB251’b1—2+11
DADD264’b1—4+23
DSUB265’b1—4+23
MUL252’b1—2+118
DIV254’b1—2+120
SDIVxxxx1—2+1x
LDIV255’b1—3+120
MAXxxxx1—2+1x
UMAXxxxx1—2+1x
MINxxxx1—2+1x
UMINxxxx1—2+1x
DCOMP266’b1—4+12/3
DUCOMP267’b1—4+13/4
}

{5.1 Stack Primitives}

{——————————————————————————————————————————————————————
PUSH
——————————————————————————————————————————————————————}
{Timing:1 click}

{In order to maintain the Stack, TOS is saved into STK.}

{entry:exit:

TOS =| v|| u|

STK =| u|| u|
| ~| -->| v|
-->| t|| t|}

@PUSH:push {point to ~},c1, opcode[164’b];
STK ← TOS, PC ← PC + PC16, IBDisp, push, GOTO[SLTail],c2;

{——————————————————————————————————————————————————————
POP
——————————————————————————————————————————————————————}
{Timing:1 click}
{In order to maintain the Stack, TOS is saved into STK.}

{entry:exit:

TOS =| v|| u|

STK =| ~|| v|
-->| u|| u|
| t| -->| t|}

@POP:T ← STK, push,c1, opcode[165’b];
STK ← TOS, PC ← PC + PC16, IBDisp, pop,c2;
TOS ← T, pop, DISPNI[OpTable],c3;

{——————————————————————————————————————————————————————
EXCH
——————————————————————————————————————————————————————}
{Timing:1 click}

{entry:exit:

TOS =| v|| u|

STK =| ~|| ~|
-->| u| -->| v|
| t|| t|}

@EXCH:T ← STK {u}, fXpop, fZpop, push, {Underflow?} GOTO[LInTail],c1, opcode[166’b];

{——————————————————————————————————————————————————————
DUP
——————————————————————————————————————————————————————}
{Timing:1 click}

{entry:exit:

TOS =| v|| v|

STK =| ~| -->| v|
-->| u|| u|
| t|| t|}

@DUP:fXpop, push, {Underflow?}c1, opcode[170’b];
PC ← PC+PC16, push, IBDisp,c2;
STK ← TOS, push, fZpop, {Overflow?} DISPNI[OpTable],c3;

{5.2 Check Instructions}

{——————————————————————————————————————————————————————
NILCK
——————————————————————————————————————————————————————}
{Timing:2 clicks}

@NILCK:fXpop, push{underflow?},c1, opcode[171’b];
[] ← TOS, ZeroBr, push,c2;
NilTest:T ← sPointerFault, STK ← TOS, pop, BRANCH[NotNIL, NIL],c3;

NotNIL:GOTO[NegIB],c1;
NIL:L2 ← L2.TRAPStashr, GOTO[Trapc2],c1;

{——————————————————————————————————————————————————————
NILCKL
——————————————————————————————————————————————————————}
{Timing:2 clicks}

@NILCKL:fXpop, fZpop, push,c1, opcode[172’b];
[] ← STK or TOS, ZeroBr, push, GOTO[NilTest],c2;

{——————————————————————————————————————————————————————
BNDCK
——————————————————————————————————————————————————————}
{Timing:2 clicks}

@BNDCK:TT ← STK, fXpop, fZpop, push, {underflow?} c1, opcode[173’b];
[] ← TT-TOS, CarryBr, push,c2;
T ← sBoundsFault, STK ← TOS, pop, BRANCH[NotBND, BND],c3;

NotBND:TOS ← TT, pop, GOTO[NegIB],c1;
BND:L2 ← L2.TRAPStashr, GOTO[Trapc2],c1;

{5.3 Unary Operations}

{Stack underflow is checked at NegIB.}

{——————————————————————————————————————————————————————
NEG
——————————————————————————————————————————————————————}
{Timing:1 click}

@NEG:TOS ← -TOS,c1, opcode[256’b];
NegIB:IBDisp, fXpop, push, {Underflow?}c2;
NegNI:PC ← PC+PC16, DISPNI[OpTable],c3;

{——————————————————————————————————————————————————————
INC
——————————————————————————————————————————————————————}
{Timing:1 click}

@INC:TOS ← TOS + 1, GOTO[NegIB],c1, opcode[257’b];

{——————————————————————————————————————————————————————
DBL
——————————————————————————————————————————————————————}
{Timing:1 click}

@DBL:TOS ← LShift1 TOS, GOTO[NegIB],c1, opcode[253’b];

{NOT IN MESA 5.0
{——————————————————————————————————————————————————————
DEC
——————————————————————————————————————————————————————}
{Timing:1 click}

@DEC:TOS ← TOS - 1, GOTO[NegIB],c1, opcode[406’b];

{——————————————————————————————————————————————————————
ADD2
——————————————————————————————————————————————————————}
{Timing:1 click}

@ADD2:TOS ← TOS + 2, GOTO[NegIB],c1, opcode[216];

{——————————————————————————————————————————————————————
ADDSB
——————————————————————————————————————————————————————}
{Timing:2 clicks}

@ADDSB:T ← ib, XLDisp,c1, opcode[217];
TT ← ~0FF xor T, BRANCH[AddSBP, AddSBN, XLowNeg],c2;

AddSBP:TOS ← TOS + T, GOTO[Addpc2],c3;
AddSBN:TOS ← TOS + TT, GOTO[Addpc2],c3;

Addpc2:PC ← PC+PC16, {finish PC update at NegIB} GOTO[NegIB],c1;
}

{5.4 Logic Operations}

{entry:exit:

TOS =| v|| v * w|

STK =| ~|| ~|
-->| w|| w|
| t| -->| t|}

{Stack underflow is checked at NegIB.}

{——————————————————————————————————————————————————————
OR
——————————————————————————————————————————————————————}
{Timing:1 click}

@OR:TOS ← STK or TOS, pop {point to t}, GOTO[NegIB],c1, opcode[261’b];

{——————————————————————————————————————————————————————
AND
——————————————————————————————————————————————————————}
{Timing:1 click}

@AND:TOS ← STK and TOS, pop {point to t}, GOTO[NegIB],c1, opcode[260’b];

{——————————————————————————————————————————————————————
XOR
——————————————————————————————————————————————————————}
{Timing:1 click}

@XOR:TOS ← STK xor TOS, pop {point to t}, GOTO[NegIB],c1, opcode[262’b];

{——————————————————————————————————————————————————————
SHIFT
——————————————————————————————————————————————————————}
{Timing:3 clicks - |shift| <= 15,
3 clicks - |shift| > 15}

{entry:exit:

TOS =| shift|| Shift[u]|

STK =| ~|| ~|
-->| u|| u|
| t| -->| t|}

{shift=rotate(shift-1)[12-15]int maskfinal mask
000F15 left14’d7FFF8000
000E14 left13’d3FFFC000
: : : : :
00011 left01FFFE

0000none15’dFFFFFFFF
FFFF15 left(1 right)14’d7FFF7FFF
FFFE14 left(2 right)13’d3FFF3FFF
: : : : :
FFF22 left133
FFF1 (̄15’d)1 left(15 right)011}

{At entry to SHIFT, TOS=shift and STK=u. For CycleMask, shift is used to determine the rotation and (shift-1) the mask. Thus, (shift-1) is placed in RH[T], and shift is dispatched on into CycleMask. (shift-1) is used to determine the mask since this has the same conventions as the size specifier of a field descriptor. Thus shift=15 implies mask=7FFF, shift=1 implies mask=1, and shift=0 implies a mask of FFFF.

At the beginning of the SHIFT code, a check is made to determine if the absolute value of shift is greater than 15 (which implies a zero result). If (shift-1) is positive, shifting is canceled if "shift" greater than 15. If (shift-1) is negative, shifting is canceld if (shift-1) is less than -16 (i.e., (shift-1) + 16 doesn’t produce a carry).

Link1 is loaded with the results of the (shift-1) test so that CycleMask returns to either ShNormRet or ShInvRet. For values of shift from 15 to 1, i.e. (shift-1) positive, the mask which CycleMask computes should be inverted, so control goes to ShInvRet in this case. If (shift-1) was negative, control returns at ShNormRet and the mask in TT is not inverted.}

@SHIFT:TT ← LRot1 STK,c1, opcode[263’b];
rhT ← Q ← (TOS ̄ 1) LRot0, NegBr, LOOPHOLE[niblTiming],c2;
T ← STK, [] ← TOS, YDisp, pCall2, pop, BRANCH[ShiftLeft, ShiftRight],c3;

ShiftLeft:[] ← ~0F and TOS, ZeroBr, DISP4[CycleMask],c1, at[L2.shiftInv,10,ShiftRight];
ShiftRight:[] ← Q + 0F + 1, CarryBr, DISP4[CycleMask],c1, at[L2.shiftNorm,10,ShiftLeft];

{Subroutine CycleMask = 1 click}

ShInvRet:TOS ← ~TT and TOS, IBDisp, fXpop, push, {Underflow?} GOTO[NegNI],c2, at[L2.shiftInv,10,MaskRet];
ShNormRet:TOS ← TT and TOS, IBDisp, fXpop, push, {Underflow?} GOTO[NegNI],c2, at[L2.shiftNorm,10,MaskRet];

{5.5 Arithmetic Operations}

{entry:exit:

TOS =| t|| s * t|

STK =| ~|| ~|
-->| s|| s|
| r| -->| r|}

{——————————————————————————————————————————————————————
ADD
——————————————————————————————————————————————————————}
{Timing:1 click}

@ADD:T ← STK, pop,c1, opcode[250’b];
add:TOS ← T + TOS, IBDisp, fXpop, push, {Underflow?} GOTO[NegNI],c2;

{NOT in PrincOps}
@ADD01:T ← STK, pop, GOTO[add],c1, opcode[270’b];

{——————————————————————————————————————————————————————
SUB
——————————————————————————————————————————————————————}
{Timing:1 click}

@SUB:T ← STK, pop,c1, opcode[251’b];
TOS ← T - TOS, IBDisp, fXpop, push, {Underflow?} GOTO[NegNI],c2;

{——————————————————————————————————————————————————————
DADD
——————————————————————————————————————————————————————}
{Timing:3 clicks}

{DADD computes the double length sum uv+ab, and leaves carry above stack}

{entry:exit:

TOS =| a|| u+a|

STK =| ~|| ~|
-->| b|| carry|
| u|| u|
| v| -->| v+b|}

@DADD:T ← STK {T ← b}, pop {point to u},c1, opcode[264’b];
Q ← STK {Q ← u}, pop {point to v},c2;
TT ← STK {TT ← v}, fXpop, fZpop, push, {Underflow?}c3;

T ← T+TT {t←v+b}, CarryBr,c1;
STK ← T, push {point to u}, BRANCH[DaddLowNC, DaddLowC],c2;
DaddLowNC:TOS ← Q+TOS {TOS←u+a}, CarryBr, GOTO[DHigh],c3;
DaddLowC:TOS ← Q+TOS+1 {TOS←u+a+1}, CarryBr, GOTO[DHigh],c3;

DHigh:T ← 1, push {point to carry}, BRANCH[DHighNC, DHighC],c1;
DHighNC:STK ← 0, IBDisp, pop {point to u}, GOTO[DNI],c2;
DHighC:STK ← T, IBDisp, pop {point to u}, GOTO[DNI],c2;

DNI:PC ← PC+PC16, pop {point to v+b}, DISPNI[OpTable],c3;

{——————————————————————————————————————————————————————
DSUB
——————————————————————————————————————————————————————}
{Timing:3 clicks}

{DSUB computes the double length difference uv̄ab, and leaves carry above stack}

{entry:exit:

TOS =| a|| u-a|

STK =| ~|| ~|
-->| b|| carry|
| u|| u|
| v| -->| v-b|}

@DSUB:T ← STK {T ← b}, pop {point to u},c1, opcode[265’b];
Q ← STK {Q ← u}, pop {point to v},c2;
TT ← STK {TT ← v}, fXpop, fZpop, push, {Underflow?}c3;

T ← TT-T {t←v-b}, CarryBr,c1;
STK ← T, push {point to u}, BRANCH[DsubLowNC, DsubLowC],c2;
DsubLowNC:TOS ← Q-TOS-1 {TOS←u-a-1}, CarryBr, GOTO[DHigh],c3, ;
DsubLowC:TOS ← Q-TOS {TOS←u-a}, CarryBr, GOTO[DHigh],c3, ;

{——————————————————————————————————————————————————————
MUL
——————————————————————————————————————————————————————}
{Timing:18 clicks - click of init + 16*(click of inner loop) + click of cleanup}

{This code implements a basic add-shift unsigned mulitply. Q holds the multiplicand (s) and TOS the mulitplier (t). TT holds the loop count. T and Q are the concatenated double word result, with the most significant bits being formed in T and the least significant in Q. The DoubleRightShift1 shifts Cout of the current alu computation into bit 0 of the double length result (T,,Q). At the end, Q is pushed onto the stack, and T is left above the stack.}

{entry:exit:

TOS =| t|| long.low|


STK =| ~|| long.high|
-->| s|| s|
| w| -->| w|}

@MUL:Q ← STK, fXpop, fZpop, push, {Underflow?}c1, opcode[252’b];
T ← 0, push {point at ~},c2;
TT ← 10,c3;

MulLoop:[] ← Q and 1, NZeroBr,c1, at[0,2,MLDEnd];
TT ← TT ̄ 1, ZeroBr, BRANCH[MPlier0, MPlier1],c2;

MPlier0:T ← DARShift1 (T+0), BRANCH[MulLoop, MLDEnd],c3;
MPlier1:T ← DARShift1 (T + TOS), BRANCH[MulLoop, MLDEnd],c3;

MLDEnd:STK ← T {long.high/rem}, pop {point at s},c1, at[1,2,MulLoop];
TOS ← ~Q {long.low/quot}, pop {point at w}, IBDisp, GOTO[NegNI],c2;

{——————————————————————————————————————————————————————
DIV
——————————————————————————————————————————————————————}
{Timing:20 clicks - No Trap = 2 clicks of init + 16*(click of inner loop) + 2 clicks of cleanup}

{entry:normal exit:

TOS =| t|| quot|


STK =| || rem|
-->| s|| quot|
| ~| -->| ~|}

@DIV:T ← 0, GOTO[Ldiv],c1, opcode[254’b];

{NOT IN MESA 5.0
{——————————————————————————————————————————————————————
SDIV
——————————————————————————————————————————————————————}
{Timing:20 clicks = 2 clicks of init + 16*(click of inner loop) + 2 clicks of cleanup}

@SDIV:xxxxxx,c1, opcode[407’b];

}

{——————————————————————————————————————————————————————
LDIV
——————————————————————————————————————————————————————}
{Timing:20 clicks = 2 clicks of init + 16*(click of inner loop) + 2 clicks of cleanup}

{This code implements a basic subtract-shift unsigned restoring divide. TOS holds the divisor (t) and the concatenation T,,Q holds the double length dividend (long). TT holds the loop count. The final quotient appears in Q and the remainder in T. The DoubleLeftShift1 shifts Cin into bit 17B of the accumulating quotient. At the end, Q is pushed onto the stack, and T is left above the stack.}

{entry:normal exit:

TOS =| t|| quot|


STK = -->| long.high|| rem|
| long.low|| quot|
| w| -->| w|}

@LDIV:T ← STK {long.high}, pop {point at long.low},c1, opcode[255’b];
Ldiv:Q ← STK {long.low}, fXpop, fZpop, push, {Underflow?}c2;
[] ← TOS, ZeroBr,c3;

[] ← T ̄ TOS, CarryBr, BRANCH[LDivNoZD, LDivZD],c1;
LDivNoZD:BRANCH[LDivOK, LDivOv],c2;
LDivOK:TT ← 0F + 1, GOTO[Quot0],c3;

LDivLoop:[] ← T ̄ TOS, CarryBr, BRANCH[QuotUnk, QuotIs1],c2, at[0,2,LDivEnd];
QuotUnk:TT ← TT ̄ 1, ZeroBr, BRANCH[Quot0, Quot1, YOdd],c3, at[0,2,QuotIs1];

Quot0:T ← DLShift1 T, SE←0, NegBr, BRANCH[LDivLoop, LDivEnd],c1;
Quot1:T ← DLShift1 (T ̄ TOS), SE←1, NegBr, BRANCH[LDivLoop, LDivEnd],c1;

QuotIs1:TT ← TT ̄ 1, ZeroBr, CANCELBR[Quot1],c3, at[1,2,QuotUnk];

LDivEnd:push {point at rem}, BRANCH[RemAdj0, RemAdj1],c2, at[1,2,LDivLoop];

RemAdj0:T ← RShift1 T, SE←0, GOTO[MLDEnd],c3;
RemAdj1:T ← RShift1 T, SE←1, GOTO[MLDEnd],c3;

LDivZD:T ← sZeroDivisor, pop, CANCELBR[Trapc3],c2, at[1,2,LDivNoZD];
LDivOv:T ← sDivideCheck, pop, GOTO[Trapc1],c3, at[1,2,LDivOK];

{5.6 Comparison}

{——————————————————————————————————————————————————————
DUCOMP
——————————————————————————————————————————————————————}
{Timing:2 clicks - High Halfs not equal
3 clicks - High Halfs equal}

{entry:exit:

TOS =| r|| comp|

STK = -->| s|| s|
| x|| x|
| y|| y|
| ~| -->| ~|}

{SELECT TRUE FROM
(x<r) OR (x=r AND y<s)=> PUSH[-1];
(x=r AND y=s)=> PUSH[0];
(x>r) OR (x=r AND y>s)=> PUSH[1];
ENDCASE;}

@DUCOMP:T ← STK {s}, pop,c1, opcode[267’b];
TT ← STK {x}, pop,c2;
comp:TT ← DARShift1 (TT-TOS) {x-r}, ZeroBr,c3;

[] ← TT, NegBr {carry of x-r}, BRANCH[CHighNE, CompLow],c1;
CHighNE:PC ← PC+0, Cin←pc16, IBDisp, pop {skip y}, BRANCH[CompL, CompG],c2;

CompL:TOS ← ~TOS xor TOS, fXpop, push, DISPNI[OpTable],c3;
CompG:TOS ← 1, fXpop, push, DISPNI[OpTable],c3;

CompLow:TT ← STK {y}, pop, CANCELBR[$],c2;
TT ← DARShift1 (TT-T) {y-s}, ZeroBr,c3;

[] ← TT, NegBr {carry of y-s}, BRANCH[CLowNE, CompE],c1;
CLowNE:PC ← PC+PC16, IBDisp, BRANCH[CompL, CompG],c2;

CompE:TOS ← 0, IBDisp, fXpop, push, CANCELBR[NegNI],c2;

{——————————————————————————————————————————————————————
DCOMP
——————————————————————————————————————————————————————}
{Timing:3 clicks - High Halfs not equal
4 clicks - High Halfs equal}

@DCOMP:T ← STK {s}, pop,c1, opcode[266’b];
Q ← STK {x}, pop,c2;
TT ← RShift1 0, SE←1 {TT←8000},c3;

TOS ← TOS + TT {r+8000},c1;
TT ← TT + Q {x+8000}, GOTO[comp]c2;