*-----------------------------------------------------------
Title[CedarOps.mc...May 11, 1984  4:14 PM...Willie-Sue];
* Cedar Allocator and Reference-Counting opcodes (version 5.0)
*-----------------------------------------------------------

* General notes:
* 1. These opcodes as presently implemented are NOT restartable in the
*    face of write-protect faults.
* 2. zct.wp is cached and is not stored in memory except when the microcode
*    is disabled.

*-----------------------------------------------------------
* Data structures -- from Allocator.mesa, ZCT.mesa, and Collector.mesa
*-----------------------------------------------------------
  MC[microcodeVersion, 4];	* for Cedar 5.2 release

* -- Header preceding allocated normal Cedar reference-counted objects.
* -- 2 words long, and always even-word aligned.
* NHeaderP: TYPE = LONG POINTER TO NormalHeader;
* NormalHeader: TYPE = MACHINE DEPENDENT RECORD [
MSC[NH.rcWord, 0];
  MC[NHR.inZCT, 100000];	* inZCT (0: 0..0): BOOLEAN, -- must be bit 0
  MC[NHR.maybeOnStack, 40000];	* maybeOnStack (0: 1..1): BOOLEAN, -- must be bit 1
  MC[NHR.blockSizeIndex, 37400]; * blockSizeIndex (0: 2..7): BlockSizeIndex,
  MC[NHR.finalizable, 200];	* finalizable (0: 8..8): BOOLEAN,
  MC[NHR.refCount, 176];	* refCount (0: 9..14): RefCount,
  MC[NHR.rcOverflowed, 1];	* rcOverflowed (0: 15..15): BOOLEAN, -- must be bit 15
MSC[NH.type, 1];		* -- type: SafeStorage.Type];
	* Note: for compatibility with Cedar 4, the actual definition is:
				* typePad: (1: 0..1): [0..3] _ 0,
  MC[NHT.type, 37777];		* type (1: 2..15): SafeStorage.Type];

MC[sizeNH, 2];			* must be 2

* RefCount: TYPE = [0..77B];	* Microcode requires max value less than 200B

MC[nullType, 0];		* nullType: SafeStorage.Type = [0]; -- must be zero

* -- Header for free normal Cedar objects (the only kind this allocator deals with).
* -- Following is a simplification of the variant record declaration in Allocator.mesa.
* FNHeaderP: TYPE = LONG POINTER TO NormalFreeHeader;
* NormalFreeHeader: TYPE = MACHINE DEPENDENT RECORD [
*				* fnh (0): NormalHeader,
MC[NFH.nextFree, 2];		* nextFree (2): FNHeaderP];

* Data structures (cont'd)

* ZeroCountTable: TYPE = LONG POINTER TO ZCTObject;
* ZCTObject: TYPE = MACHINE DEPENDENT RECORD [
MSC[ZCT.wp, 0];			* wp (0): LONG POINTER TO Allocator.NHeaderP,
				* rp (2): LONG POINTER TO Allocator.NHeaderP,
				* lastNP (4): LONG POINTER TO LONG POINTER,
				* pad (6: 0..14): [0..77777B],
MSC[ZCT.markingDecrements, 6];	* markingDecrements (6: 15..15): BOOLEAN,
MSC[ZCT.residueMask, 7];	* residueMask (7: 15..15): WORD,
				* unused1 (10B): ARRAY [10B..wordsPerPage) OF WORD,
MC[ZCT.bsiToFreeList, 400];	* bsiToFreeList (wpp): BSIToFreeListObj,
				* unused2 (wpp+SIZE[BSIToFreeListObj]): ARRAY
				*   [wpp+SIZE[BSIToFreeListObj]..2*wpp) OF WORD,
MC[ZCT.bsiToSize, 1000];	* bsiToSize (2*wpp): BSIToSizeObj,
				* unused3 (2*wpp+SIZE[BSIToSizeObj]): ARRAY
				*   [2*wpp+SIZE[BSIToSizeObj]..3*wpp) OF WORD,
MC[ZCT.sizeToBSI, 1400];	* sizeToBSI (3*wpp): SizeToBSIObj,
				* unused4 (3*wpp+SIZE[SizeToBSIObj]): ARRAY
				*   [3*wpp+SIZE[SizeToBSIObj]..5*wpp) OF WORD,
MC[ZCT.fosTable, 2400];		* fosTable (5*wpp): FOSTableObject];

				* wpp: CARDINAL = PrincOps.wordsPerPage;
MC[zctBlockWords, 4000];	* zctBlockWords: INT = 8 * PrincOps.wordsPerPage;


* SizeToBSIObj: TYPE = PACKED ARRAY [0..maxSmallBlockSize] OF BlockSizeIndex;
* BSIToSizeObj: TYPE = ARRAY BlockSizeIndex OF CARDINAL;
* BSIToFreeListObj: TYPE = ARRAY BlockSizeIndex OF FNHeaderP;
MC[maxSmallBlockSize, 1076];	* maxSmallBlockSize: CARDINAL = 1076B;
MC[maxBSI, 77];			* BlockSizeIndex: TYPE = [0..77B];
MC[bsiEscape, maxBSI];		* bsiEscape: BlockSizeIndex = LAST[BlockSizeIndex];
* -- Note: sizes do not include NormalHeader overhead (2 words)

* FOSTableObject: TYPE = ARRAY FOSTableIndex OF FOSTableResidue;
* FOSTableIndex: TYPE = [0..FOSTableLength);
* FOSTableResidue: TYPE = CARDINAL;
* -- except for fosWildCard and fosEmpty, FOSTableResidues will be in [0..3777B]
* -- with a 24-bit virtual address and in [0..77777B] with a 28-bit VA.
* MC[fosWildCard, 177777];	* fosWildCard: FOSTableResidue = 177777B; -- must be -1
MC[fosEmpty, 100000];		* fosEmpty: FOSTableResidue = 100000B;
MC[FOSTableLength, 10000];	* FOSTableLength: CARDINAL = 10000B;

*-----------------------------------------------------------
* Trap parameter values -- from RCMicrocodeImpl.mesa
*-----------------------------------------------------------

MC[tpUnImplemented, 0];
MC[tpRCOverflowOccurred, 1];
MC[tpUCDisabled, 2];
MC[tpRCUnderflowOccurred, 3];
MC[tpZCTFull, 4];
MC[tpRCBug, 5];
MC[tpLookFurtherAtReclaimedRef, 6];
MC[tpNormalFreeListEmpty, 6];


*-----------------------------------------------------------
* R registers
*-----------------------------------------------------------

Set[!RCRegs, !Region15];	* RMRegion[RCRegs] -- move to RegisterDefs someday
SetRMRegion[RCRegs];

RVN[RCFlags];	* B0=1 => microcode enabled, 0 disabled
		* B15 = copy of zct.markingDecrements
RVN[WPOffset];	* Write pointer, relative to WPBR
RVN[RCWord];	* Contents of RC word at nhp^
RV[ZCTBlockLink, Sub[zctBlockWords!, 2]];  * Offset of link cell in ZCTBlock
RVN[RCTemp0];
RVN[RCTemp1];
RVN[RCTemp2];
RVN[RCTemp3];
RVN[RCresidue];
RVN[RCResMask];	* holds the Residue Mask from zct

*-----------------------------------------------------------
* Base registers -- move these to ADefs someday
*-----------------------------------------------------------

* Following 2 registers are an even/odd pair
BR[ZCTBR, 6];	* pointer to ZCT
BR[WPBR, 7];	* cached version of ZCT.wp

* Following 2 registers are an even/odd pair and are IFU-addressable
* BR[LPtr, 34];	* Defined in DMesaDefs
BR[BR35, 35];

TopLevel;

*-----------------------------------------------------------
AllocateM: MiscTable[145],
* Timing: 40 cycles normal, 46 max (+ MISC dispatch)
*-----------------------------------------------------------

* type: SafeStorage.Type = Pop[];
* size: CARDINAL = Pop[];
* IF ucDisabled THEN OpcodeTrap[tpUCDisabled];
	RBase_ RBase[RCRegs], StkP-2;
	MemBase_ ZCTBR, RCFlags, Branch[RCDisabledTrap3, R>=0];

* IF size>maxSmallBlockSize THEN {PushLong[NIL]; RETURN};
	T_ HighByte[maxSmallBlockSize];
	T_ T OR (LowByte[maxSmallBlockSize]);
	PD_ (Stack)-T-1;
	T_ (Stack) RSH 1,		* T_ size/2
		Branch[.+2, Carry'];
	 T_ Stack&+1_ A0, Branch[PushT];

* bsi: BlockSizeIndex = zct.sizeToBSI[size];
* fnhp: FNHeaderP = zct.bsiToFreeList[bsi];
* nhp: NHeaderP = @fnhp.fnh;  -- no-op (just a type conversion)
* IF fnhp=NIL THEN OpcodeTrap[tpNormalFreeListEmpty];
	T_ T+(ZCT.sizeToBSI);		* Fetch[@zct.sizeToBSI[size]]^
	Fetch_ T, RCTemp2_ RShift[ZCT.bsiToFreeList!, 1]C;
	T_ MD, Stack&+1, Branch[.+2, R odd];
	 T_ RSH[T, 10], Branch[.+2];	* Extract left (even) byte
	 T_ T AND (377C);		* Extract right (odd) byte
	RCTemp2_ ((RCTemp2)+T) LSH 1;	* Index into double-word array
	T_ (Fetch_ RCTemp2)+1;		* Fetch[@zct.bsiToFreeList[bsi]]^
	T_ MD, Fetch_ T;
	RCTemp0_ T, MemBase_ LPtr;
	RCTemp1_ MD, PD_ (BRLo_ T) OR (MD);
	T_ A0, BRHi_ RCTemp1, Branch[NormalFreeListEmptyTrap, ALU=0];

* -- touch fnhp.nextFree to ensure it won't fault later
* OnZ[nhp];
* nhp.maybeOnStack _ zct.markingDecrements;
* nhp.type _ type;
* Note that nhp is in RCTemp1,,RCTemp0 at this point.
	Fetch_ T, T_ NFH.nextFree;	* Fetch RCword at nhp^		
	RCWord_ RCFlags;		* nhp.maybeOnStack _ zct.markingDecrements
	RCWord_ DPF[RCWord, 1, MaskPos[NHR.maybeOnStack!], MD];
	Fetch_ T,			* Touch fnhp.nextFree before calling OnZCT
		T_ RCTemp0, Call[OnZCT]; * Put on ZCT; update RCWord and return T=0

* No page faults are possible after here.
	T_ (Store_ T)+1, DBuf_ RCWord;	* Store updated RCWord at nhp^
	T_ (Store_ T)+1, DBuf_ Stack&-1, * Store type at nhp.type
		Call[FetchGetsT];	* Fetch fnhp.nextFree

* zct.bsiToFreeList[bsi] _ fnhp.nextFree;
* fnhp.nextFree _ NIL;
	T_ (Store_ T)+1, DBuf_ 0C, RCTemp3_ MD, Call[FetchGetsT];
	Store_ T, DBuf_ 0C;
	T_ RCTemp3, MemBase_ ZCTBR;
	RCTemp2_ (Store_ RCTemp2)+1, DBuf_ T, T_ MD; * Store[@zct.bsiToFreeList[bsi]]
	Store_ RCTemp2, DBuf_ T;

* PushLong[NHPToRef[nhp]];
	T_ (RCTemp0)+(sizeNH);
	Stack&+1_ T;
	T_ A_ RCTemp1, XorSavedCarry, Branch[PushT];

*-----------------------------------------------------------
FreeM: MiscTable[146],
* Timing: 23 + 1.25 * object size in words (+ MISC dispatch)
*-----------------------------------------------------------

* nhp: NHeaderP = PopLong[];
* IF ucDisabled THEN OpcodeTrap[tpUCDisabled];
	RBase_ RBase[RCRegs], StkP-2,
		Call[TrapIfRCDisabled];	* Sets MemBase_ LPtr and loads BRHi
	T_ A0, BRLo_ Stack;

* bsi: BlockSizeIndex = nhp.blockSizeIndex;
* IF bsi=bsiEscape THEN {Push[FALSE]; RETURN};
* fnhp: FNHeaderP = LOOPHOLE[nhp]; -- no-op (just a type conversion)
	Fetch_ T;			* Fetch[@nhp.rcWord]^
	T_ MD, MemBase_ ZCTBR;
	RCTemp0_ LDF[T, MaskSize[NHR.blockSizeIndex!], MaskPos[NHR.blockSizeIndex!]];
	PD_ (RCTemp0)#(bsiEscape);
	T_ (RCTemp0)+(ZCT.bsiToSize), Branch[.+2, ALU#0];
	 Stack_ A0, IFUNext0;		* Just return FALSE

* Zero[nhp+SIZE[NormalHeader], zct.bsiToSize[bsi]-SIZE[NormalHeader]];
	Fetch_ T,			* Fetch[@zct.bsiToSize[bsi]]^
		RCTemp3_ Add[sizeNH!, 40]C;
	RCTemp2_ ID, T_ MD, MemBase_ LPtr; * RCTemp2_ sizeNH
	RCTemp1_ T-(sizeNH)-1;

* On first iteration, do ((count-1) mod 20B)+1 words;
* on subsequent iterations, do 20B words.
* RCTemp1 = (remaining count)-1; RCTemp2 = current displacement;
* RCTemp3 = current displacement + 40B (for PreFetches);
* Carry=0 iff count is exhausted.
FreeZMunch:
	T_ (RCTemp1) AND (17C),		* T _ (# words to do this iteration)-1
		Branch[FreeZDone, Carry'];
	RCTemp3_ PreFetch_ RCTemp3, Carry20, * PreFetch 40B words ahead
		Branch[.+2, Reschedule'];
	 StkP+1, Branch[MesaReschedTrap];
	Cnt_ T;
	RCTemp2_ (Store_ RCTemp2)+1, DBuf_ 0C, Branch[., Cnt#0&-1];
	RCTemp1_ (RCTemp1)-T-1, Branch[FreeZMunch]; * Update count

* No page faults are possible after here.
* fnhp.fnh.type _ nullType;
* fnhp.nextFree _ zct.bsiToFreeList[bsi];
* zct.bsiToFreeList[bsi] _ fnhp;
* Push[TRUE];
FreeZDone:
	T_ (RCTemp0)+(RCTemp0), MemBase_ ZCTBR; * Indexing into double-word array
	T_ T+(ZCT.bsiToFreeList),
		Call[FetchGetsT];	* Fetch[@zct.bsiToFreeList[bsi]]^ -- low half
	RCTemp0_ MD,
		T_ (Store_ T)+1, DBuf_ Stack&+1, * Store[@zct.bsiToFreeList[bsi]]^ _ fnhp
		Call[FetchGetsT];	* Same for high half
	RCTemp1_ MD, Store_ T, DBuf_ Stack&-1, T_ A0;
	Stack_ T+1, MemBase_ LPtr;	* Stack_ 1 (= TRUE)
	T_ (Store_ NH.type)+1, DBuf_ T;	* nhp.type _ nullType
	T_ (Store_ T)+1, DBuf_ RCTemp0;	* fnhp.nextFree _ ptr fetched from bsiToFreeList
	Store_ T, DBuf_ RCTemp1, IFUNext0;

*-----------------------------------------------------------
IFUR[ASSIGNREF, 2, L];
IFUR[ASSIGNREFNEW, 2, L];
* Timings:	lhs^	rhs	min	max (assuming no trap)
*		=NIL	=NIL	11	11
*		#NIL	=NIL	27	43
*		=NIL	#NIL	25	25
*		#NIL	#NIL	31	47  (except 11 if lhs^=rhs)
*-----------------------------------------------------------

* RCTemp0, RCTemp1: lnhp (= lhs-SIZE[NormalHeader]), arg to OnZCT
* RCTemp2: (updated) header word at rnhp^
* RCTemp3: alpha byte of opcode
* RCWord: (updated) header word at lnhp^
* ScratchBR: lhs
* LPtr: lnhp
* BR35: rnhp
* Cnt is used as a flag: Cnt=0 means rhs=NIL.

* lhs: LONG POINTER TO REF = PopLong[]+GetCodeByte[];
* rhs: REF = PopLong[];
* rrc: RefCount;
* IF ucDisabled THEN OpcodeTrap[tpUCDisabled];
	RBase_ RBase[RCRegs];
	PD_ RCFlags, MemBase_ ScratchBR, Branch[RCDisabledTrap1, R>=0];

* IF lhs^=rhs THEN RETURN;
* Overlapped with this test, load lhs into BR35 and save away lhs^ in
* RCTemp1,,RCTemp0.  Also save the alpha byte in RCTemp3.
	BRHi_ Stack&-1;	
	BRLo_ Stack&-2;
	T_ (Fetch_ ID)+1;		* Fetch[lhs+alpha]^
	RCTemp3_ (Fetch_ T)-1, T_ MD;
	PD_ (Stack&+1)#T, Cnt_ 1S;
	RCTemp0_ T, MemBase_ BR35, Branch[.+2, ALU#0];
	 PD_ (BRHi_ Stack&-1)#MD, Branch[.+2]; * Low halves equal, compare high

* IF rhs#NIL THEN {
*   rnhp: NHeaderP = LOOPHOLE[rhs - SIZE[NormalHeader]];
*   rrc _ rnhp.refCount;
*   IF rrc = LAST[RefCount] THEN OpcodeTrap[tpRCOverflowOccurred]};
	 PD_ (BRHi_ Stack&-1)-(Stack&-1)-1;
	T_ (Stack&+1)-(sizeNH),		* Convert REF to NHeaderP
		Branch[.+2, ALU#0];	* Complete ref equal test
	 StkP-2, IFUNext0;		* Equal, nothing to do
	T_ Stack&-1, BRLo_ T, Branch[.+3, Carry];
	 RCTemp1_ MD, T_ T-1, Branch[RHSNIL, ALU=0];
	 BRHi_ T;
	RCTemp1_ MD, Fetch_ 0S;		* Fetch[rnhp]^
	RCTemp2_ LShift[1, MaskPos[NHR.refCount!]]C;
	RCTemp2_ (RCTemp2)+MD, MemBase_ LPtr; * Add 1 to ref count and see if it wraps
	PD_ (RCTemp2) AND (NHR.refCount);
	RCTemp2_ (RCTemp2) AND NOT (NHR.maybeOnStack), * Prepare for later update to rnhp^
		DblBranch[RCOverflowTrap, CheckLHS, ALU=0];

* ASSIGNREF (cont'd)

* IF lhs^#NIL THEN {
*   lnhp: NHeaderP = LOOPHOLE[lhs - SIZE[NormalHeader]];
*   lrc: RefCount _ lnhp.refCount;
*   CheckForRCUnderflow[lnhp];
*   IF lrc=1 AND ~nhp.rcOverflowed THEN OnZ[lnhp];
*   lnhp.maybeOnStack _ zct.markingDecrements;
*   lnhp.refCount _ lrc-1};
RHSNIL:
	MemBase_ LPtr;
* This branch always goes to .+2 and is executed solely for its side-effect
* of setting Cnt_ 0.
	BRHi_ RCTemp1, DblBranch[.+2, .+3, Cnt#0&-1];

* RCTemp2 remembers new value for RCWord at rnhp^ if non-NIL (Cnt=0 if rhs=NIL);
* Current MemBase = LPtr.  lhs^ was already fetched and saved in RCTemp1,,RCTemp0.
CheckLHS:
	 BRHi_ RCTemp1;
	RCTemp0_ T_ (RCTemp0)-(sizeNH);	* Convert REF to NHeaderP in RCTemp1,,RCTemp0
	PD_ RCTemp1, BRLo_ T, Branch[.+3, Carry];
	 RCTemp1_ (RCTemp1)-1, Branch[LHSNIL, ALU=0];
	 BRHi_ RCTemp1;
	Fetch_ 0S, T_ RCFlags;		* Fetch[lnhp]^
	RCWord_ DPF[T, 1, MaskPos[NHR.maybeOnStack!], MD],
					* nhp.maybeOnStack _ zct.markingDecrements
		Call[CheckForRCUnderflow]; * Returns with ALU = decremented refCount
	T_ A0, Branch[.+3, ALU#0];	* Branch if refCount not zero
	 T_ RCTemp0, Call[OnZCT];	* Put lnhp in ZCT and update flags in RCWord
	 T_ A0, branch[.+3];
	branch[.+3, R Even], RCFlags;	* test for markingDecrements
	 T_ RCTemp0, Call[OnZCT];
	 T_ A0;

	nop;			* placement
	Store_ T, DBuf_ RCWord,		* Store[lnhp]^
		FlipMemBase,		* MemBase_ BR35
		DblBranch[DoRCAssign, UpdateRHS, Cnt=0&-1];

* IF rhs#NIL THEN {
*   rnhp.refCount _ rrc+1;
*   rnhp.maybeOnStack _ FALSE};
* RCTemp2 contains rnhp^ with refCount and maybeOnStack already updated.
LHSNIL:
	MemBase_ BR35, Branch[.+2, Cnt=0&-1]; * Skip if rhs=NIL
UpdateRHS:
	 Store_ 0S, DBuf_ RCTemp2;

* lhs^ _ rhs;
DoRCAssign:
	T_ RCTemp3, MemBase_ ScratchBR;	* Get back alpha
	T_ (Store_ T)+1, DBuf_ Stack&+1; * Store low part of rhs
	Store_ T, DBuf_ Stack&-2, IFUNext0; * Store high part of rhs

*-----------------------------------------------------------
CreateRefM: MiscTable[143],
* Timing: 15 cycles normal, 22 max (+ MISC dispatch)
*-----------------------------------------------------------

* nhp: NHeaderP = PopLong[];
* IF ucDisabled THEN OpcodeTrap[tpUCDisabled];
* nhp.maybeOnStack _ zct.markingDecrements;
* OnZ[nhp];
	RBase_ RBase[RCRegs], StkP-2,
		Call[TrapIfRCDisabled];	* Sets MemBase_ LPtr and loads BRHi
	T_ BRLo_ Stack&-1;
	Fetch_ 0S, RCTemp0_ T;		* Fetch RCword
	T_ RCFlags;
	RCWord_ DPF[T, 1, MaskPos[NHR.maybeOnStack!], MD];
					* nhp.maybeOnStack _ zct.markingDecrements
	T_ RCTemp0, Call[OnZCT];
	Store_ 0S, DBuf_ RCWord, IFUNext0;


*-----------------------------------------------------------
GetCanonicalReferentTypeM: MiscTable[72],
* This implementation is compatible with both Cedar 4 and Cedar 5.
* Timing: 5 cycles (+ MISC dispatch)
*-----------------------------------------------------------

* ref: REF = PopLong[];
* IF ref=NIL THEN {Push[nullType]; RETURN};
* nhp: NHeaderP = LOOPHOLE[ref - SIZE[NormalHeader]];
* Push[nhp.type];
	StkP-2, MemBase_ LPtr;
	PD_ (BRLo_ Stack) OR T;
	T_ (BRHi_ T)-T-1, Branch[.+2, ALU#0];
	 Stack_ A0, IFUNext0;
	LongFetch_ T, B_ T, T_ A0;	* Fetch[@nhp.type]^ -- know @nhp.type = ref-1
* For Cedar 4 compatibility, must mask off some high-order bits.
	Stack_ DPF[T, Sub[20, MaskSize[NHT.type!]], MaskSize[NHT.type!], MD],
		IFUNext0;

*-----------------------------------------------------------
ReclaimableRefM: MiscTable[144],
* Timing: 10 cycles min, 36 max (+ MISC dispatch)
*-----------------------------------------------------------

* nhp: NHeaderP = PopLong[];
* IF ucDisabled THEN OpcodeTrap[tpUCDisabled];
* Push[CheckReclaimable[nhp, FALSE]];
	RBase_ RBase[RCRegs], StkP-2,
		Call[TrapIfRCDisabled];	* Sets MemBase_ LPtr and loads BRHi
	T_ BRLo_ Stack;
	Nop;				* Placement
	Fetch_ 0S, RCTemp0_ T;		* Fetch RCword
	RCWord_ MD,			* This may be updated by CheckReclaimable
		SCall[CheckReclaimable]; * Returns disposition in T
	 Store_ 0S, DBuf_ RCWord;	* +1: need to store RCWord back into nhp^
	Stack_ T, IFUNext0;		* +2: don't need to store; just return disposition


*-----------------------------------------------------------
ReclaimedRefM: MiscTable[140],
* Timing: 16 cycles min, 43 max (+ MISC dispatch)
*-----------------------------------------------------------

* ref: REF = PopLong[];
* ans: REF;
* IF ucDisabled THEN OpcodeTrap[tpUCDisabled];
* nhp: NHeaderP = LOOPHOLE[ref - SIZE[NormalHeader]];
* CheckForRCUnderflow[nhp];
	RBase_ RBase[RCRegs], StkP-2,
		Call[TrapIfRCDisabled];	* Sets MemBase_ LPtr and loads BRHi
	T_ (Stack)-(sizeNH);		* Convert REF to NHeaderP
	RCTemp0_ A0, BRLo_ T, Branch[.+3, Carry];
	RCTemp1_ (RCTemp1)-1;		* Had to borrow from high part
	BRHi_ RCTemp1;
	Fetch_ RCTemp0, RCTemp0_ T;	* Fetch rcWord
	RCWord_ MD, Call[CheckForRCUnderflow]; * Decrements refCount

* SELECT CheckReclaimable[nhp, TRUE] FROM
*   continue => ans _ NIL;
*   reclaimIt => ans _ ref;
*   finalizeIt => OpcodeTrap[tpLookFurtherAtReclaimedRef];
*   ENDCASE;
* nhp.refCount _ nhp.refCount-1;
* PushLong[ans];
	Call[CheckReclaimable];		* Returns T = ALU = disposition
	BDispatch_ T,			* Dispatch on disposition
		DispTable[1, 1, 1];	* Force CheckReclaimable always to return here
	T_ RCWord;			* Prepare to RCWord back into nhp^

* Note that CheckReclaimable may have called OnZCT only if disposition = continue.
* In particular, this means that if disposition = finalizeIt, no changes have
* been made anywhere in memory, so it's OK to trap at that point.  For the other
* cases, we are now committed to finish the opcode.
DispTable[3];
	T_ Stack&+1_ Store_ 0S, DBuf_ T, * disposition = continue: Push[NIL] and exit
		Branch[PushT];
	Store_ 0S, DBuf_ T,		* disposition = reclaimIt: leave ref on stack
		StkP+1, IFUNext0;
	T_ tpLookFurtherAtReclaimedRef,	* disposition = finalizeIt: trap
		Branch[OpcodeTrap];

*-----------------------------------------------------------
EnableMicrocodeM: MiscTable[141],
*-----------------------------------------------------------

* zct _ PopLong[];
* -- Load microcode registers
*	(currently zct, zct.wp, and zct.markingDecrements, zct.residueMask)
* ucDisabled _ FALSE;
* Push[CedarMicrocode.microcodeVersion --currently 4--]; (version change 10 May)
* Note: since the header page of the ZCT is guaranteed to be resident, no precautions
* need be taken to ensure restartability after page faults.
	RBase_ RBase[RCRegs], StkP-1;
	MemBase_ ZCTBR;
	BRHi_ Stack&-1;			* ZCTBR _ zct
	T_ microcodeVersion;		* version = 4 (10 May 84)
	Stack_ T, BRLo_ Stack;		* Stack _ microcodeVersion
* added 10 May 1984 (not being at all clever)
	Fetch_ zct.residueMask;
	RCResMask_ Md;

	T_ NOT (Fetch_ ZCT.markingDecrements); * T_ small negative number
	RCFlags_ DPF[T, 17, 1, MD];	* RCFlags[0] _ 1,
					* RCFlags[15] _ zct.markingDecrements
	T_ (Fetch_ ZCT.wp)+1;		* Load zct.wp
	Fetch_ T, WPOffset_ MD,
		FlipMemBase;		* Flip to WPBR
	T_ (WPOffset) AND NOT (Sub[zctBlockWords!, 1]C); * Mask out WP offset bits
	WPOffset_ (BRLo_ T) XOR (WPOffset), T_ MD; * BR_ base, WPOffset_ offset
	BRHi_ T, IFUNext0;


*-----------------------------------------------------------
DisableMicrocodeM: MiscTable[142],
*-----------------------------------------------------------

* [] _ PopLong[]; -- DISCARD zct arg; assume it's the same as the one we already have
* -- Dump any cached variable state (currently just zct.wp)
* ucDisabled _ TRUE;
* Note: since the ZCT is guaranteed to be resident, no precautions need be taken
* to ensure restartability after page faults.
	T_ A0, RBase_ RBase[RCRegs], StkP-3;
	RCFlags_ T+1, MemBase_ WPBR;	* RCFlags[0] _ 0, RCFlags word # 0
	DummyRef_ WPOffset, T_ MD,	* Compute WPBR+WPOffset
		FlipMemBase;		* Flip to ZCTBR
	RCTemp0_ 7777C;
	RCTemp0_ (RCTemp0) AND (VAHi);	* Damn hardware returns ones in VAHi[0:3]
	T_ VALo;
	T_ (Store_ ZCT.wp)+1, DBuf_ T;	* Store in ZCT.wp
	Store_ T, DBuf_ RCTemp0, IFUNext0; * Can't fault since ZCT is resident

* Subroutines

*-----------------------------------------------------------
CheckReclaimable:
* Enter: RCTemp1,,RCTemp0 = LONG POINTER TO NormalHeader (nhp)
*	RCWord = contents of word at nhp^, with refCount field decremented
*		if there is a decrement pending
* Call:	SCall[CheckReclaimable];
* Exit: Traps if need to put in ZCT and the ZCT is full; otherwise:
*	T = ALU = disposition (0=continue, 1=reclaim, 2=finalize)
*	MemBase either unchanged or set to LPtr (i.e., unchanged if it
*		was equal to LPtr at the time of the call)
* Returns +1 if RCWord has been updated by this subroutine and needs to be stored
* back into memory, +2 otherwise.
* Clobbers T, RCTemp2
* Timing: continue, 2 or 3 cycles normally; 11 to 27 if need to put on ZCT;
*	14 if reclaim or finalize
*-----------------------------------------------------------
Subroutine;

* rc: RefCount _ nhp.refCount;
* IF decrPending THEN rc _ rc-1;  -- done by caller
* IF rc#0 OR nhp.rcOverflowed OR nhp.inZCT THEN RETURN [continue];
	PD_ (RCWord) AND (OR[NHR.refCount!, NHR.rcOverflowed!]C),
		Branch[.+2, R>=0];
	 T_ A0, RCFlags, Return[R<0];	* Return +2 always
	PD_ (RCWord)+(RCWord), Branch[.+2, ALU=0];
	 T_ A0, RCFlags, Return[R<0];	* Return +2 always

* IF nhp.maybeOnStack OR FoundInFHSnapshot[nhp] THEN OnZ[nhp]
* ELSE RETURN [IF nhp.finalizable THEN finalizeIt ELSE reclaimIt];
	T_ RCTemp0, Branch[.+2, ALU>=0]; * OnZCT if maybeOnStack (bit 1)
	 Branch[OnZCTTail];		* Call OnZCT and return +1

* -- Expanded in-line:
* FOSTableHash: PROC [nhp: NHeaderP] RETURNS [x: FosTableIndex, r: FOSTableResidue] = {
*   r _ BITOR[BITSHIFT[HighHalf[nhp], 3], BITSHIFT[LowHalf[nhp], -13]];
*   u: FOSTableResidue _ BITAND[r, zct.residueMask];
*   x _ BITAND[BITXOR[BITSHIFT[LowHalf[nhp], -1], u], FOSTableLength-1]};
* For a 28-bit address space, residue is 15 bits derived from high[4..15],,low[0..2];
* index is 12 bits derived from low[3..14] and hashed with the residue.
* low[15] is ignored since REFs are always even.
	RCTemp2_ LDF[T, 14, 1];		* log[FOSTableLength] bits of nhp
	T_ RCY[RCTemp1, T, 15];		* residue
** added these two lines 11 May 1984
	RCResidue_ T;		* we need this later
	T_ T AND (RCResMask);
	RCTemp2_ (RCTemp2) XOR T, MemBase_ ZCTBR; * hash the index bits with residue
	RCTemp2_ (RCTemp2) AND (Sub[FOSTableLength!, 1]C); * mod FOSTableLength

* -- Expanded in-line:
* FoundInFHSnapshot: PROC [nhp: NHeaderP] RETURNS [found: BOOLEAN _ FALSE] = {
*   index: FOSTableIndex;
*   residue, entry: FOSTableResidue;
*   [index, residue] _ FOSTableHash[nhp];
*   entry _ zct.fosTable[index];
*   RETURN[residue = BITAND[residue, entry]]};
	RCTemp2_ (RCTemp2)+(ZCT.fosTable);
	Fetch_ RCTemp2;			* Fetch[@zct.fosTable[index]]^;
	T_ RCResidue;
	T_ T AND MD;			* BITAND[residue, entry]
	PD_ T XOR (RCResidue), MemBase_ LPtr;	* Compare residue with BITAND
	T_ LDF[RCWord, 1, MaskPos[NHR.finalizable!]], Branch[.+2, ALU#0];
	 T_ RCTemp0, Branch[OnZCTTail];	* residue = BITAND[residue, entry]
	T_ T+1, RCFlags, Return[R<0];	* reclaimIt=1, finalizeIt=2; return +2 always

*  previous code
*	PD_ NOT MD, Branch[.+2, ALU#0];
*	 T_ RCTemp0, Branch[OnZCTTail];	* residue = entry
*	T_ LDF[RCWord, 1, MaskPos[NHR.finalizable!]], Branch[.+2, ALU#0];
*	 T_ RCTemp0, Branch[OnZCTTail];	* entry = fosWildCard
*	T_ T+1, RCFlags, Return[R<0];	* reclaimIt=1, finalizeIt=2; return +2 always

*-----------------------------------------------------------
OnZCT:			* Puts reference in Zero Count Table
* Enter: RCTemp1,,T = LONG POINTER TO NormalHeader (nhp)
*	RCWord = contents of word at nhp^
* Exit: Traps if the ZCT is full; otherwise:
*	RCWord updated but not stored back into memory
*	T = ALU = 0 (for the convenience of CheckReclaimable)
*	MemBase = LPtr
* Timing: 7 cycles usually, 13 if need to chain to a new ZCT block.
*-----------------------------------------------------------
Subroutine;

* wp: LONG POINTER TO NHeaderP;
* IF nhp.inZCT THEN RETURN;
* wp _ zct.wp;
* wp^ _ nhp;
* wp _ wp+SIZE[LONG POINTER];
	MemBase_ WPBR, RCWord,
		DblBranch[AlreadyInZCT, PutInZCT, R<0]; * Test nhp.inZCT

* Duplicate entry point: tail of CheckReclaimable
OnZCTTail:
	MemBase_ WPBR, RCWord, DblBranch[AlreadyInZCT, PutInZCT, R<0];

AlreadyInZCT:
	T_ A0, MemBase_ LPtr, Return;

PutInZCT:
	T_ (Store_ WPOffset)+1, DBuf_ T; * Store low half -- this can fault
	WPOffset_ T_ (Store_ T)+1, DBuf_ RCTemp1; * Store high half -- this cannot fault

* IF BITAND[LowHalf[wp], zctBlockWords-1] = zctBlockWords-SIZE[LONG POINTER] THEN
*   IF (wp _ LOOPHOLE[wp^]) = NIL THEN OpcodeTrap[tpZCTFull];
* nhp.inZCT _ TRUE;
* zct.wp _ wp;
	PD_ T XOR (ZCTBlockLink);
	RCWord_ (RCWord) OR (NHR.inZCT),
		Branch[ZCTNotFull, ALU#0];

* This block is now full; attempt to follow link to next.  If a trap occurs, the
* cell into which we just stored will appear not to have been used.
	T_ (Fetch_ T)+1;
	WPOffset_ (Fetch_ T)-(3C),	* Restore wp to original value in case we trap
		T_ MD;
	PD_ T OR MD;
	Branch[RCZCTFullTrap, ALU=0];	* Branch if it is NIL
	BRLo_ T, T_ MD;			* Set new ZCT block base and reset offset
	BRHi_ T, WPOffset_ A0;
ZCTNotFull:
	T_ A0, MemBase_ LPtr, Return;

*-----------------------------------------------------------
CheckForRCUnderflow:
* Enter: RCWord = word containing RefCount to be checked
* Exit: Traps if the RefCount has underflowed; otherwise:
*	RCWord = entire word with refCount decremented
*	ALU = value of refCount and rcOverflowed fields
* Clobbers T
* Timing: 3 cycles normally
*-----------------------------------------------------------
Subroutine;

* IF nhp.refCount=0 THEN
*   IF nhp.rcOverflowed THEN OpcodeTrap[tpRCUnderflowed] ELSE OpcodeTrap[tpRCBug];
	PD_ (RCWord) AND (NHR.refCount);
	RCWord_ (RCWord)-(LShift[1, MaskPos[NHR.refCount!]]C), * Decrement refCount
		Branch[RefCountZero, ALU=0];
	PD_ (RCWord) AND (OR[NHR.refCount!, NHR.rcOverflowed!]C), Return;

RefCountZero:				* Underflow if rcOverflowed, bug otherwise
	RCWord, DblBranch[RCUnderflowTrap, RCBugTrap, R odd];


*-----------------------------------------------------------
FetchGetsT:
*-----------------------------------------------------------
Subroutine;

	PD_ Fetch_ T, Return, Global;

*-----------------------------------------------------------
TrapIfRCDisabled:
* Enter: RBase = RCRegs
*	T = word to be loaded into high part of LPtr
* Exit: Traps if RC microcode is disabled; otherwise:
*	MemBase = LPtr
*	BRHi = RCTemp1 = T at call
* Timing: 2 cycles
*-----------------------------------------------------------
Subroutine;
KnowRBase[RCRegs];

	MemBase_ LPtr, RCFlags, Branch[RCDisabledTrap2, R>=0];
	RCTemp1_ BRHi_ T, Return;


*-----------------------------------------------------------
* Traps
*-----------------------------------------------------------
TopLevel;

RCOverflowTrap:
	T_ tpRCOverflowOccurred, Branch[OpcodeTrap];
RCDisabledTrap1:
	T_ tpUCDisabled, Branch[OpcodeTrap];
RCDisabledTrap2:
	T_ tpUCDisabled, Branch[OpcodeTrap];
RCDisabledTrap3:
	T_ tpUCDisabled, Branch[OpcodeTrap];
RCUnderflowTrap:
	T_ tpRCUnderflowOccurred, Branch[OpcodeTrap];
RCZCTFullTrap:
	T_ tpZCTFull, Branch[OpcodeTrap];
RCBugTrap:
	T_ tpRCBug, Branch[OpcodeTrap];
NormalFreeListEmptyTrap:
	T_ tpNormalFreeListEmpty, Branch[OpcodeTrap];

*-----------------------------------------------------------
* Needed for coordination
*-----------------------------------------------------------

RTSetup: MiscTable[63], Stack&-2;
	Stack_ A0, IFUNext0;		* not Implemented

*-----------------------------------------------------------
* ReadMap[vp] RETURNS[MapContents, HWFlags]
*  used to read all the available map entries
*-----------------------------------------------------------
RMapPrivate: MiscTable[70], Stack&-1;		* ReadMap[cardinal]
 	RBase_ RBase[RTemp0];
 	Call[SetBRForPage];
 	RMap_ RTemp0;
 	Call[WaitForMap];
 	Stack&+1_ T;
 	T_ Errors';
 	STack_ T, IFUNext0;
*-----------------------------------------------------------
* ExtraMapBits[rp] RETURNS[bit, wordFromArray]
*-----------------------------------------------------------
ExtraMapBits: MiscTable[66], Stack&-1;		* ExtraMapBits[realpage]
 	Call[MapDirtyBit];
 	Stack&+1_ T;
 	T_ Md;
	STack_ T, IFUNext0;
*-----------------------------------------------------------
* Unused MISC opcodes
*-----------------------------------------------------------

	MiscOpcodeUnimplemented[60];	* ReclaimedRef
	MiscOpcodeUnimplemented[61];	* ALTERCOUNT
	MiscOpcodeUnimplemented[62];	* ResetSTKBits
	MiscOpcodeUnimplemented[64];	* RcFinalizeCount
	MiscOpcodeUnimplemented[65];	* IsPiReclaimable
*	MiscOpcodeUnimplemented[66];
	MiscOpcodeUnimplemented[67];	* CREATEREF
*	MiscOpcodeUnimplemented[70];
	MiscOpcodeUnimplemented[73];	* AllocQNode
	MiscOpcodeUnimplemented[74];	* AllocPNode
	MiscOpcodeUnimplemented[75];	* FreeObject
	MiscOpcodeUnimplemented[76];	* FreeQNode
	MiscOpcodeUnimplemented[77];	* FreePNode

	MiscOpcodeUnimplemented[147];
*	MiscOpcodeUnimplemented[150];
*	MiscOpcodeUnimplemented[151];
*	MiscOpcodeUnimplemented[152];
	MiscOpcodeUnimplemented[153];
	MiscOpcodeUnimplemented[154];
	MiscOpcodeUnimplemented[155];
	MiscOpcodeUnimplemented[156];
	MiscOpcodeUnimplemented[157];