MDPlaceImpl:
CEDAR
PROGRAM
IMPORTS
Basics,
MDGlobalVars,
MDUtils
= BEGIN OPEN Basics, MDADefs, MDDefs, MDGlobalVars;
NotUniqueInPlace: SIGNAL = CODE;
bTemp: Xbt ← NEW[XbtRec ← ALL[0]];
aTryTab: ARRAY [0..5) OF WORD ← ALL[0];
maskPtrTab: ARRAY [0..17) OF CARDINAL; -- index into maskTab
maskTabLen: CARDINAL = 16+15+14+13+12+11+10+9+8+7+6+5+4+3+2+1;
maskTab: ARRAY [0..maskTabLen) OF WORD; -- table of i-bit masks rshift j
PlaceSubpage:
PUBLIC PROC[sub: SubPage, absPage:
CARDINAL, xbt: XDoradoPage]
RETURNS[BOOL] = TRUSTED {
data: CARDINAL ← 0;
end: CARDINAL = sub.subPageHeader.length;
spn: CARDINAL ← sub.subPageHeader.spn1;
w, lw: CARDINAL;
sBT: Xbt ← NEW[XbtRec ← ALL[177777B]];
assignList: LIST OF Assignment ← NIL;
IF spn = 0 THEN { w ← 0; lw ← xbtWords-1} ELSE w ← lw ← spn - 1;
DO
j: CARDINAL ← data;
BEGIN
sBT[w] ← xbt.bt[w]; -- just look at subpage
UNTIL j = end
DO
i0: CARDINAL ← sub.data[j];
imPtr: IMRecordPtr = MDUtils.IMPtr[i0];
j0: CARDINAL ← j;
loc: CARDINAL;
IF imPtr.links.aLink # i0
THEN
-- got a +1 list
DO
j ← j + 1;
IF MDUtils.IMPtr[sub.data[j]].links.aLink = i0 THEN EXIT;
ENDLOOP;
IF imPtr.word0.atW0AndatWord = 0
THEN {
-- need to find a place
loc ←
IF j = j0
THEN Find1Place[imPtr.mask, sBT]
ELSE FindAlistPlace[imPtr.mask, j-j0+1, sBT];
IF loc = 177777B THEN GOTO nxw;
}
ELSE loc ← MDUtils.CardAnd[imPtr.word0.W0Addr, WordMask];
FOR j1:
CARDINAL
IN [j0..j]
DO
-- fill in assignment
w0: CARDINAL = absPage+loc+j1-j0;
jx: CARDINAL = sub.data[j1];
imPtr: IMRecordPtr = MDUtils.IMPtr[jx];
IF (imagToRealAddrs+jx)^ # 177777B THEN SIGNAL NotUniqueInPlace;
IF (realToImagAddrs+w0)^ # 177777B THEN SIGNAL NotUniqueInPlace;
imPtr.word0.W0Addr ← w0;
ENDLOOP;
j ← j + 1;
ENDLOOP;
xbt.bt[w] ← sBT[w]; -- success
RETURN[TRUE];
EXITS
nxw => sBT[w] ← 177777B; -- failure
END;
w ← w + 1;
IF w > lw THEN EXIT;
ENDLOOP;
RETURN[FALSE];
};
Find1Place:
PUBLIC PROC[mask:
WORD, xBT: Xbt]
RETURNS[pageLoc:
CARDINAL] =
TRUSTED {
The common special case of FindAlistPlace (see below)
bMerge: WORD ← BITAND[NOTAndXbtBlock[xBT], mask];
ap: CARDINAL ← 0;
IF bMerge = 0
THEN {
find1Failed ← find1Failed + 1;
RETURN[177777B];
};
There must be a match somewhere - go find it
UNTIL
BITAND[bMerge, aTryTab[ap]] # 0
DO
ap ← ap + 1;
ENDLOOP;
Now there must be a match somewhere in bt with this ap
BEGIN
OPEN Basics;
m: WORD ← BITAND[mask, aTryTab[ap]];
bp: CARDINAL ← 0;
x: WORD;
loc: CARDINAL;
pBT: Pbt ← LOOPHOLE[xBT];
UNTIL (x ←
BITAND[
BITNOT[xBT[bp]], m]) # 0
DO
bp ← bp + 1;
ENDLOOP;
loc ← Lsh4[bp] + FirstBitPos[x];
IF pBT[loc] THEN SIGNAL NotUniqueInPlace;
pBT[loc] ← TRUE;
find1Placed ← find1Placed + 1;
RETURN[loc];
END;
};
FindAlistPlace:
PUBLIC
PROC[mask:
WORD, len:
CARDINAL, xBT: Xbt]
RETURNS[pageRel: CARDINAL] = TRUSTED {
Mask gives permissible first locations
Length is number of instructions in alist, 1 le length le 16
Bt is a bit table of occupied locations
Returns location, or 177777B if not possible
Find possible starting locations (runs ge length)
OPEN Basics;
bMerge: WORD ← 0;
bp: CARDINAL ← xbtWords;
FOR j:
CARDINAL
IN [0..xbtWords)
DO
bTemp[j] ← xBT[j];
ENDLOOP;
DO
newBp: WORD;
bp ← bp - 1;
bTemp[bp] ← newBp ← BITAND[MakeRunMask[BITNOT[bTemp[bp]], len], mask];
bMerge ← BITOR[bMerge, newBp];
IF bp = 0 THEN EXIT;
ENDLOOP;
IF bMerge = 0
THEN {
findFailed ← findFailed + 1;
RETURN[177777B];
};
There must be a match somewhere
BEGIN
ap: CARDINAL ← 0;
ax, bx: WORD;
loc: CARDINAL;
pBT: Pbt = LOOPHOLE[xBT];
UNTIL
BITAND[bMerge, ax ← aTryTab[ap]] # 0
DO
ap ← ap + 1;
ENDLOOP;
Now there must be a match somewhere in Btemp with this ap
UNTIL (bx ←
BITAND[bTemp[bp], ax]) # 0
DO
bp ← bp + 1; -- previous loop left bp=0
ENDLOOP;
loc ← Lsh4[bp] + FirstBitPos[bx];
FOR i:
CARDINAL
IN [0..len)
DO
IF pBT[loc+i] THEN SIGNAL NotUniqueInPlace;
pBT[loc+i] ← TRUE;
ENDLOOP;
RETURN[loc];
END;
};
Lsh4:
PROC[x:
CARDINAL]
RETURNS[
CARDINAL] =
INLINE
{ RETURN[LOOPHOLE[BITSHIFT[LOOPHOLE[x], 4]]] };
FirstBitPos:
PROC[x:
WORD]
RETURNS[
CARDINAL] = {
FOR j:
CARDINAL
IN [0..16)
DO
y: INTEGER = LOOPHOLE[x];
IF y < 0 THEN RETURN[j];
x ← BITSHIFT[x, 1];
ENDLOOP;
RETURN [177777B]; -- shouldn't happen
};
NOTAndXbtBlock:
PROC[xBT: Xbt]
RETURNS[m:
WORD] =
TRUSTED {
m ← 177777B;
FOR i:
CARDINAL
IN [0..xbtWords)
DO
m ← BITAND[m, xBT[i]];
ENDLOOP;
RETURN[BITNOT[m]];
};
MakeRunMask:
PROC[mask:
WORD, len:
CARDINAL]
RETURNS[m:
WORD] =
TRUSTED {
m ← mask;
FOR i:
CARDINAL
IN [2..len]
DO
m ← BITAND[BITSHIFT[m, 1], m];
ENDLOOP;
};
SetUpMasks:
PROC = {
mtIndex: CARDINAL ← 0;
jbceMask: WORD = BITOR[jbctMask, BITSHIFT[jbctMask, -1] ];
notOneBitTab: ARRAY [0..16) OF WORD;
aTryTab[0] ← BITNOT[BITOR[calledMask, BITOR[ifuMask, jbceMask]]];
aTryTab[1] ← BITNOT[BITOR[calledMask, jbceMask]];
aTryTab[2] ← BITNOT[BITOR[calledMask, BITAND[ifuMask, jbceMask]]];
aTryTab[3] ← BITNOT[calledMask];
aTryTab[4] ← 177777B;
BEGIN
one: WORD ← 100000B;
FOR i:
CARDINAL
IN [0..16)
DO
notOneBitTab[i] ← BITNOT[one];
one ← BITSHIFT[one, -1];
ENDLOOP;
END;
FOR i:
CARDINAL
IN [1..17)
DO
mask: WORD ← notOneBitTab[i-1];
maskPtrTab[i] ← mtIndex;
FOR pos:
CARDINAL
IN [0..16-i)
DO
maskTab[mtIndex] ← mask;
mtIndex ← mtIndex + 1;
mask ← BITSHIFT[mask, -1]; -- rshift
ENDLOOP;
ENDLOOP;
};
since we only do the Dorado Model 1, SetUpMasks need be done only once
SetUpMasks[];
END.