<> <> <> <> DIRECTORY Basics, MDADefs, MDDefs, MDGlobalVars, MDUtils; MDPlaceImpl: CEDAR PROGRAM IMPORTS Basics, MDGlobalVars, MDUtils EXPORTS 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 { <> bMerge: WORD _ BITAND[NOTAndXbtBlock[xBT], mask]; ap: CARDINAL _ 0; IF bMerge = 0 THEN { find1Failed _ find1Failed + 1; RETURN[177777B]; }; <<>> <> UNTIL BITAND[bMerge, aTryTab[ap]] # 0 DO ap _ ap + 1; ENDLOOP; <> 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 { <> <> <> <> <> 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]; }; <> 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; <> 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; }; <> SetUpMasks[]; END.