<> <> <> <> DIRECTORY Basics, IO, PLAOps, Rope; PLAOpsImplA: CEDAR PROGRAM IMPORTS Basics, IO, PLAOps, Rope EXPORTS PLAOps = BEGIN OPEN Basics, PLAOps; Trace: PUBLIC BOOL _ FALSE; FinishMin: PUBLIC BOOL _ FALSE; FinishCS: PUBLIC BOOL _ FALSE; Abort: PUBLIC BOOL _ FALSE; InvalidTermRope: PUBLIC SIGNAL[rope: IO.ROPE] = CODE; CardSeq: TYPE = REF CardSeqRec; CardSeqRec: TYPE = RECORD[SEQUENCE size: CARDINAL OF CARDINAL]; incross: QWSeq _ NIL; SavedTerms: PUBLIC Term _ NIL; -- must reuse terms to keep VM from running out NewTerm: PUBLIC PROC[inBitSize, outBitSize: CARDINAL] RETURNS[term: Term] = { inWdSize: CARDINAL _ (inBitSize -1)/16+1; outWdSize: CARDINAL _ (outBitSize -1)/16+1; IF SavedTerms# NIL THEN { term _ SavedTerms; SavedTerms _ SavedTerms.next; IF inWdSize # term.in.wdSize THEN term.in _ NEW[QWSeqRec[inWdSize]]; IF outWdSize # term.out.wdSize THEN term.out _ NEW[QWSeqRec[outWdSize]] } ELSE { term _ NEW[TermRec _ [ ]]; term.in _ NEW[QWSeqRec[inWdSize]]; term.out _ NEW[QWSeqRec[outWdSize]] }; term.next _ term.last _ term.kkin _ NIL; term.use _ term.old _ avail; term.kin _ NIL; FOR i: INT IN [0..inWdSize) DO term.in[i] _ initInQrtWdc ENDLOOP; FOR i: INT IN [0..outWdSize) DO term.out[i] _ initOutQrtWz ENDLOOP }; CopyTerm: PUBLIC PROC[ref: Term] RETURNS[new: Term] = { new _ NewTerm[ref.in.wdSize*16, ref.out.wdSize*16]; new.use _ ref.use; new.old _ ref.old; new.kin _ ref.kin; new.kkin _ ref.kkin; FOR i: CARDINAL IN [0..ref.in.wdSize) DO new.in[i] _ ref.in[i] ENDLOOP; FOR i: CARDINAL IN [0..ref.out.wdSize) DO new.out[i] _ ref.out[i] ENDLOOP }; RopeToTerm: PUBLIC PROC[ rope: IO.ROPE, list: TermList, iFormat: Format _ NIL, oFormat: Format _ NIL] RETURNS[term: Term] = { SetIn: PROC[q: Qrt] = { IF iFormat#NIL THEN IF recIdx=(iFormat[fldIdx].firstBit+iFormat[fldIdx].bitSize) THEN {fldIdx_fldIdx+1; recIdx _ iFormat[fldIdx].firstBit}; IF recIdx >= list.inBits THEN SIGNAL InvalidTermRope[rope]; SetInQrt[q, term, recIdx]; recIdx _ recIdx + 1 }; SetOut: PROC[q: Qrt] = { IF oFormat#NIL THEN IF recIdx=(oFormat[fldIdx].firstBit+oFormat[fldIdx].bitSize) THEN {fldIdx_fldIdx+1; recIdx _ oFormat[fldIdx].firstBit}; IF recIdx >= list.outBits THEN SIGNAL InvalidTermRope[rope]; SetOutQrt[q, term, recIdx]; recIdx _ recIdx + 1}; fldIdx: INT _ 0; recIdx: INT _ 0; ropeIdx: INT _ 0; term _ NewTerm[list.inBits, list.outBits]; recIdx _ iFormat[fldIdx].firstBit; FOR ropeIdx _ ropeIdx, ropeIdx+1 WHILE ropeIdx < rope.Length[] DO SELECT rope.Fetch[ropeIdx] FROM '0, '- => SetIn[zero]; '1 => SetIn[one]; 'x, '. => SetIn[dontcare]; '| => EXIT; ENDCASE ENDLOOP; fldIdx _ 0; recIdx _ oFormat[fldIdx].firstBit; FOR ropeIdx _ ropeIdx, ropeIdx+1 WHILE ropeIdx < rope.Length[] DO SELECT rope.Fetch[ropeIdx] FROM '0, '- => SetOut[ zero]; '1, '+ => SetOut[ one]; 'x, '. => SetOut[ dontcare]; '( => GOTO use; ENDCASE; REPEAT use => term.use _ RopeToUse[rope.Substr[ropeIdx+1]] ENDLOOP }; TermToRope: PUBLIC PROC[ term: Term, list: TermList, showUse: BOOL _ FALSE, iFormat: Format _ NIL, oFormat: Format _ NIL] RETURNS[rope: IO.ROPE] = { fldIdx: CARDINAL _ 0; st: IO.STREAM _ IO.ROS[]; inFieldSp: BOOL _ iFormat#NIL AND iFormat[iFormat.size -1].firstBit+1 > iFormat.size; outFieldSp: BOOL _ oFormat#NIL AND oFormat[oFormat.size -1].firstBit+1 > oFormat.size; FOR recIdx: INT IN [0..list.inBits) DO IF iFormat#NIL THEN { IF recIdx=(iFormat[fldIdx].firstBit+iFormat[fldIdx].bitSize) THEN{IF inFieldSp THEN st.PutChar[' ];fldIdx_fldIdx+1}; IF fldIdx=iFormat.size THEN EXIT; IF recIdx< iFormat[fldIdx].firstBit THEN LOOP }; SELECT GetInQrt[term, recIdx] FROM dontcare => st.PutChar['.]; one => st.PutChar['1]; zero => st.PutChar['0]; ENDCASE ENDLOOP; st.PutRope[" | "]; fldIdx _ 0; FOR recIdx: INT IN [0..list.outBits) DO IF oFormat#NIL THEN { IF recIdx=(oFormat[fldIdx].firstBit+oFormat[fldIdx].bitSize) THEN{IF outFieldSp THEN st.PutChar[' ];fldIdx_fldIdx+1}; IF fldIdx=oFormat.size THEN EXIT; IF recIdx< oFormat[fldIdx].firstBit THEN LOOP }; SELECT GetOutQrt[term, recIdx] FROM dontcare => st.PutChar['.]; one => st.PutChar['1]; zero => st.PutChar['-] ENDCASE ENDLOOP; IF showUse THEN st.PutF[" (%g)", IO.rope[UseToRope[term.use]]]; RETURN[IO.RopeFromROS[st] ]}; AppendTerm: PUBLIC PROC[ref: Term, list: TermList] = { IF list.end # NIL THEN list.end.next _ ref ELSE list.begin _ ref; ref.last _ list.end; list.end _ ref; ref.next _ NIL; list.length _ list.length +1 }; DeleteTerm: PUBLIC PROC[old: Term, list: TermList] = { <> IF old.next # NIL THEN old.next.last _ old.last ELSE list.end _ old.last; IF old.last # NIL THEN old.last.next _ old.next ELSE list.begin _ old.next; list.length _ list.length -1; SaveTerm[old] }; Add: PUBLIC PROC[tl1, tl2, tl3, tl4, tl5: TermList _ NIL] RETURNS[new: TermList] = { tl: ARRAY[1..5] OF TermList _ [tl1, tl2, tl3, tl4, tl5]; IF tl1 = NIL THEN RETURN[NIL]; new _ tl1; FOR i: NAT IN [2..5] DO IF tl[i] = NIL THEN EXIT; new _ AddTermLists[new, tl[i]] ENDLOOP }; AddTermLists: PROC[list1, list2: TermList] RETURNS[new: TermList] = { IF list1.inBits # list2.inBits THEN ERROR; IF list1.outBits # list2.outBits THEN ERROR; IF list1.length=0 THEN RETURN[list2]; IF list2.length=0 THEN RETURN[list1]; new _ list1; list1.end.next _ list2.begin; list2.begin.last _ list1.end; list1.end _ list2.end; list1.length _ list1.length + list2.length; list2^ _ [ ]; RETURN[list1]}; MissingArguments: SIGNAL = CODE; Or: PUBLIC PROC[tl1, tl2, tl3, tl4, tl5: TermList _ OrFalse] RETURNS[new: TermList] = { tl: ARRAY[1..5] OF TermList _ [tl1, tl2, tl3, tl4, tl5]; new _ OrFalse; FOR i: NAT IN [1..5] DO IF tl[i] = OrFalse THEN LOOP; IF new=OrFalse THEN new _ CopyTermList[tl[i]] ELSE new _ OrTermLists[new, tl[i]] ENDLOOP; IF new = OrFalse THEN {MissingArguments[]; new _ NIL}}; <> OrTermLists: PROC[list1, list2: TermList] RETURNS[new: TermList] = { IF list1.inBits # list2.inBits THEN ERROR; IF list1.outBits # list2.outBits THEN ERROR; IF list1.length=0 THEN RETURN[CopyTermList[list2]]; IF list2.length=0 THEN RETURN[CopyTermList[list1]]; list1 _ CopyTermList[list1]; FOR t: Term _ list2.begin, t.next WHILE t#NIL DO AppendTerm[CopyTerm[t], list1]; ENDLOOP; IF list1.length>1 THEN [ ] _ ConvertTermListToCompleteSum[list1, FALSE, FALSE]; RETURN[list1]}; AndTrue: PUBLIC TermList _ NEW[TermListRec]; And: PUBLIC PROC[tl1, tl2, tl3, tl4, tl5: TermList _ AndTrue] RETURNS[new: TermList] = { tl: ARRAY[1..5] OF TermList _ [tl1, tl2, tl3, tl4, tl5]; new _ AndTrue; FOR i: NAT IN [1..5] DO IF tl[i] = AndTrue THEN LOOP; IF new=AndTrue THEN new _ tl[i] ELSE new _ AndTermLists[new, tl[i]] ENDLOOP; IF new = AndTrue THEN {MissingArguments[]; new _ NIL}}; <> AndTermLists: PROC[list1, list2: TermList] RETURNS[new: TermList] = { IF list1 = NIL OR list2 = NIL THEN RETURN[NIL]; IF list1.inBits # list2.inBits THEN ERROR; IF list1.outBits # list2.outBits THEN ERROR; IF list1.length = 0 OR list2.length = 0 THEN RETURN[NIL]; new _ NEW[TermListRec _ [inBits: list1.inBits, outBits: list1.outBits] ]; FOR t: Term _ list1.begin, t.next WHILE t#NIL DO andTerms: TermList _ AndTerm[t, list2]; IF andTerms.end = NIL OR andTerms.begin = NIL THEN LOOP; andTerms.end.next _ new.begin; new.begin _ andTerms.begin; andTerms.begin _ andTerms.end _ NIL; new.length _ new.length + andTerms.length; andTerms.length _ 0; IF new.length>1 THEN [ ] _ ConvertTermListToCompleteSum[new, FALSE, FALSE]; ENDLOOP}; AndTerm: PROC[term: Term, list: TermList] RETURNS[new: TermList] = { intersection: Term _ NewTerm[inBitSize: term.in.wdSize*16, outBitSize: term.out.wdSize*16]; new _ NEW[TermListRec _ [inBits: list.inBits, outBits: list.outBits] ]; FOR t: Term _ list.begin, t.next WHILE t#NIL DO IF NOT Intersection[term, t, intersection] THEN LOOP; [ ] _ UpdateCompleteSumWithTerm[new, intersection, FALSE, FALSE]; ENDLOOP }; Not: PUBLIC PROC[tl: TermList] RETURNS[new: TermList] = { true: Term _ NewTrueTerm[inBitSize: tl.inBits, outBitSize: tl.outBits]; new _ NEW[TermListRec _ [inBits: tl.inBits, outBits: tl.outBits] ]; AppendTerm[true, new]; FOR t: Term _ tl.begin, t.next WHILE t#NIL DO old: TermList _ new; notTerm: TermList _ NotTerm[t]; new _ AndTermLists[old, notTerm]; IF old #NIL THEN SaveListTerms[old]; IF notTerm #NIL THEN SaveListTerms[notTerm]; ENDLOOP }; NotTerm: PROC[term: Term] RETURNS[new: TermList] = { true: Term _ NewTrueTerm[term.in.wdSize*16, term.out.wdSize*16]; new _ NEW[TermListRec _ [inBits: term.in.wdSize*16, outBits: term.out.wdSize*16] ]; FOR i: CARDINAL IN [0..term.in.wdSize*16) DO q: Qrt _ GetInQrt[term, i]; SELECT q FROM dontcare => LOOP; one => SetInQrt[zero, true, i]; zero => SetInQrt[one, true, i]; ENDCASE; AppendTerm[CopyTerm[true], new]; SetInQrt[q, true, i] ENDLOOP; SaveTerm[true] }; NewTrueTerm:PROC[inBitSize, outBitSize: CARDINAL] RETURNS[copy: Term] = { copy _ NewTerm[inBitSize: inBitSize, outBitSize: outBitSize]; FOR i: NAT IN [0..copy.in.wdSize) DO copy.in[i].d _ copy.in[i].m _ 0 ENDLOOP; FOR i: NAT IN [0..copy.out.wdSize) DO copy.out[i].d _ copy.out[i].m _ 177777B ENDLOOP}; InsUsed: PUBLIC PROC[ list: TermList] RETURNS[count: CARDINAL] = { term: Term _ NewTerm[list.inBits, list.outBits]; IF list = NIL THEN RETURN[0]; FOR i: CARDINAL IN [0..term.in.wdSize) DO term.in[i] _ initInQrtWdc ENDLOOP; FOR t: Term _ list.begin, t.next WHILE t#NIL DO FOR i: CARDINAL IN [0..term.in.wdSize) DO term.in[i].m _ BITOR[term.in[i].m, t.in[i].m] ENDLOOP; ENDLOOP; count _ CountInMaskOnes[term.in]; SaveTerm[term] }; CopyTermListForField: PUBLIC PROC[ list: TermList, firstBit: CARDINAL, bitSize: CARDINAL ] RETURNS[newList: TermList] = { term: Term; IF list = NIL THEN RETURN[NIL]; term _ NewTerm[list.inBits, list.outBits]; term.in _ NIL; -- Throw away sequence FOR i: CARDINAL IN [0..term.out.wdSize) DO term.out[i] _ initOutQrtWz ENDLOOP; newList _ NEW[TermListRec _ [inBits: list.inBits, outBits: list.outBits]]; FOR t: Term _ list.begin, t.next WHILE t#NIL DO interesting: BOOL _ FALSE; FOR i: CARDINAL IN [firstBit..firstBit+bitSize) DO q: Qrt _ GetOutQrt[t, i]; SetOutQrt[q, term, i]; interesting _ interesting OR q=one OR q=dontcare ENDLOOP; IF ~interesting THEN LOOP; term.in _ t.in; ACopy[term, newList ]; ENDLOOP; term.in _ NIL }; CopyTermList: PUBLIC PROC[ list: TermList, firstOut: CARDINAL _ 0, lastOut: CARDINAL _ 177777B] RETURNS[newList: TermList] = { term: Term; IF list = NIL THEN RETURN[NIL]; lastOut _ MIN[list.outBits-1, lastOut]; term _ NewTerm[list.inBits, lastOut+1-firstOut]; term.in _ NIL; -- Throw away sequence FOR i: CARDINAL IN [0..term.out.wdSize) DO term.out[i] _ initOutQrtWz ENDLOOP; newList _ NEW[TermListRec _ [inBits: list.inBits, outBits: lastOut+1-firstOut ]]; FOR t: Term _ list.begin, t.next WHILE t#NIL DO interesting: BOOL _ FALSE; FOR i: CARDINAL IN [firstOut..lastOut] DO q: Qrt _ GetOutQrt[t, i]; SetOutQrt[q, term, i-firstOut]; interesting _ interesting OR q=one OR q=dontcare ENDLOOP; IF ~interesting THEN LOOP; term.in _ t.in; ACopy[term, newList ]; ENDLOOP; term.in _ NIL }; ListTermList: PUBLIC PROC[ list: TermList, showUse: BOOL _ FALSE, omitDeletes: BOOL _ FALSE, log: IO.STREAM _ NIL, iFormat: Format _ NIL, oFormat: Format _ NIL ] = { IF log=NIL THEN log _ IO.noWhereStream; FOR term: Term _ list.begin, term.next WHILE term#NIL DO IF omitDeletes AND term.use = del THEN LOOP; log.PutRope["\n"]; log.PutRope[TermToRope[term, list, showUse, iFormat, oFormat]] ENDLOOP; log.PutRope["\n"] }; SortTermList: PUBLIC PROC[ list: TermList, bigFirst: BOOL _ TRUE] = { size: CardSeq _ NEW[CardSeqRec[list.length]]; temp: Term _ NEW[TermRec]; term: Term _ list.begin; done: BOOL _ FALSE; FOR i: CARDINAL IN [0..list.length) DO size[i] _ InSize[term]; term _ term.next; ENDLOOP; WHILE NOT done DO done _ TRUE; term _ list.begin; FOR i: CARDINAL IN [0..list.length-1) DO IF (IF bigFirst THEN (size[i] < size[i+1]) ELSE (size[i+1] < size[i])) THEN { s: CARDINAL _ size[i]; size[i] _ size[i+1]; size[i+1] _ s; done_FALSE; temp^_term^; term.use _ term.next.use; term.next.use _ temp.use; term.old _ term.next.old; term.next.old _ temp.old; term.best _ term.next.best; term.next.best _ temp.best; term.kin _ term.next.kin; term.next.kin _ temp.kin; term.kkin _ term.next.kkin; term.next.kkin _ temp.kkin; term.in _ term.next.in; term.next.in _ temp.in; term.out _ term.next.out; term.next.out _ temp.out; term _ term.next}; ENDLOOP; ENDLOOP}; CompareTerms: PUBLIC PROC[t0,t1: Term] RETURNS[comp: Basics.Comparison] = { FOR i: INT IN [0..t0.in.wdSize) DO SELECT Basics.CompareCard[t0.in[i].m, t1.in[i].m] FROM less => RETURN[less]; greater => RETURN[greater]; ENDCASE => LOOP ENDLOOP; FOR i: INT IN [0..t0.in.wdSize) DO SELECT Basics.CompareCard[t0.in[i].d, t1.in[i].d] FROM less => RETURN[less]; greater => RETURN[greater]; ENDCASE => LOOP ENDLOOP; FOR i: INT IN [0..t0.out.wdSize) DO SELECT Basics.CompareCard[t0.out[i].d, t1.out[i].d] FROM less => RETURN[less]; greater => RETURN[greater]; ENDCASE => LOOP ENDLOOP; RETURN[equal]}; FastSortTermList: PUBLIC PROC[list: TermList] RETURNS[new: TermList] = { TermSzSeqRec: TYPE = RECORD[SEQUENCE size: CARDINAL OF TermSzRec]; TermSzRec: TYPE = RECORD[sz: INT, term: Term]; TwoTermSzRec: TYPE = RECORD[t0, t1: TermSzRec]; terms: REF TermSzSeqRec _ NEW[TermSzSeqRec[list.length]]; term: Term _ list.begin; new _ NEW[TermListRec _ [inBits: list.inBits, outBits: list.outBits ]]; FOR i: CARDINAL IN [0..list.length) DO terms[i].sz _ InSize[term]; terms[i].term _ CopyTerm[term]; term _ term.next; ENDLOOP; DO done: BOOL _ TRUE; FOR i: CARDINAL IN [0..terms.size-1) DO SELECT Basics.CompareInt[terms[i].sz, terms[i+1].sz] FROM less => LOOP; equal => SELECT CompareTerms[terms[i].term, terms[i+1].term] FROM less => LOOP; equal => LOOP; ENDCASE; ENDCASE; [terms[i], terms[i+1]] _ TwoTermSzRec[terms[i+1], terms[i]]; done _ FALSE ENDLOOP; IF done THEN EXIT ENDLOOP; FOR i: CARDINAL IN [0..list.length) DO AppendTerm[terms[i].term, new]; ENDLOOP}; GetTermVal: PUBLIC PROC[term: Term, list: TermList] = { <> FOR i: CARDINAL IN [0..term.out.wdSize) DO term.out[i].d _ 0; term.out[i].m _ 177777B; ENDLOOP; FOR i: CARDINAL IN [0..term.in.wdSize) DO IF term.in[i].m # 177777B THEN ERROR ENDLOOP; -- supposed to be completely specified FOR ref: Term _ list.begin, ref.next WHILE ref#NIL DO FOR i: CARDINAL IN [0..term.in.wdSize) DO IF BITAND[ref.in[i].m, BITXOR[ref.in[i].d, term.in[i].d]]#0 THEN GOTO Loop; REPEAT Loop => LOOP ENDLOOP; FOR i: CARDINAL IN [0..ref.out.wdSize) DO term.out[i].d _ BITOR[ref.out[i].d, term.out[i].d]; IF BITAND[ref.out[i].m, term.out[i].m] # 177777B THEN ERROR; -- no dontcares ENDLOOP; ENDLOOP }; ConvertTermListToCompleteSum: PUBLIC PROC[ list: TermList, addMerges: BOOLEAN, addConsensus: BOOLEAN, log: IO.STREAM _ IO.noWhereStream] RETURNS[unfinished: BOOL] = { unfinished_FALSE; ConvertListStartingAt[list.begin, list, addMerges, addConsensus, log]; IF FinishCS THEN {FinishCS_FALSE; unfinished_TRUE} }; UpdateCompleteSumWithTerm: PUBLIC PROC [ sum: TermList, term: Term, addMerges: BOOLEAN, addConsensus: BOOLEAN, log: IO.STREAM _ IO.noWhereStream ] RETURNS[unfinished: BOOL] = { unfinished_FALSE; FOR i: CARDINAL IN [0..term.out.wdSize) DO IF term.out[i].d # 0 THEN EXIT; REPEAT FINISHED => IF FinishCS THEN {FinishCS_FALSE; RETURN[TRUE]} ELSE RETURN[FALSE] ENDLOOP; ACopy[term, sum]; ConvertListStartingAt[sum.end.last, sum, addMerges, addConsensus, log]; IF FinishCS THEN {FinishCS_FALSE; unfinished_TRUE} }; <<********* PRIVATE **********>> VerifyList: PROC[list: TermList] = { FOR temp: Term _ list.begin, temp.next WHILE temp#NIL DO IF list.end=temp THEN {IF temp.next#NIL THEN ERROR} ELSE {IF temp.next.last#temp THEN ERROR}; IF list.begin=temp THEN {IF temp.last#NIL THEN ERROR} ELSE {IF temp.last.next#temp THEN ERROR}; ENDLOOP}; ConvertListStartingAt: PROC[ pB: Term, list: TermList, addMerges: BOOLEAN, addConsensus: BOOLEAN, log: IO.STREAM _ IO.noWhereStream] = { DelA: PROC = INLINE {pA_pA.next; DeleteTerm[pA.last, list]}; DelB: PROC = INLINE {pB_pB.last; DeleteTerm[pB.next, list]; pA_list.begin}; pA, pC: Term; IF pB=NIL THEN RETURN; pC _ NewTerm[pB.in.wdSize*16, pB.out.wdSize*16]; IF pB # NIL THEN WHILE pB.next # NIL DO IF Abort THEN EXIT; pB _ pB.next; IF Trace THEN { cntTerm: Term; doneCount, leftCount: CARDINAL _ 0; FOR cntTerm _ list.begin, cntTerm.next WHILE cntTerm # pB DO doneCount _ doneCount+1 ENDLOOP; FOR cntTerm _ cntTerm, cntTerm.next WHILE cntTerm # NIL DO leftCount _ leftCount+1 ENDLOOP; log.PutF["\nSum size = %03g|%03g at %g", IO.card[doneCount], IO.card[leftCount], IO.time[]]}; FOR pA _ pB.last, pA.last WHILE pA # NIL DO covered: BOOL _ FALSE; p: Term; SELECT Consensus[pA,pB,pC] FROM bad => ERROR; nop => {LOOP}; delB => {DelB[]; LOOP}; delA => {DelA[]; LOOP}; addC => {IF ~addConsensus OR FinishCS THEN LOOP}; addM => {IF ~addMerges OR FinishCS THEN LOOP}; delBaddC => {DelB[]}; delAaddC => {DelA[]}; del2addC => {DelA[]}; ENDCASE => ERROR; p _ list.begin; WHILE p#NIL DO IF InCrossed[pC, p] THEN {p_p.next; LOOP}; IF FstInSecXdIns[pC, p] AND FstInSecXdOuts[pC, p] THEN {p_p.next; covered _ TRUE; LOOP}; IF ~FstInSecXdIns[p, pC] OR ~FstInSecXdOuts[p, pC] THEN {p_p.next; LOOP}; IF p#pA AND p#pB AND p.next#NIL THEN {p_p.next; DeleteTerm[p.last, list]; LOOP}; IF p#pA AND p#pB THEN {DeleteTerm[p, list]; p_NIL; LOOP}; IF p=pA AND p#pB THEN {p_p.next; DelA[]; LOOP}; IF p#pA AND p=pB THEN {p_p.next; DelB[]; LOOP}; IF p.last # NIL THEN {p_p.next; DelB[]; LOOP}; IF p.next # NIL THEN {p_pB_p.next; DeleteTerm[pB.last, list]; pA_list.begin; LOOP}; IF covered THEN ERROR; ACopy[pC, list]; IF list.length#2 THEN ERROR; DeleteTerm[list.begin, list]; pA_pB_list.end; EXIT; REPEAT FINISHED => IF ~covered THEN ACopy[pC, list] ENDLOOP; ENDLOOP; ENDLOOP; SaveTerm[pC]}; ConsensusResult: TYPE = {nop,delB,delA,addC,addM,delBaddC,delAaddC,del2addC,bad}; Consensus: PROC[pA,pB,pC: Term] RETURNS [r: ConsensusResult] = INLINE { sel: [0..32) _ 16; inCrossMask: QWSeq _ InCrossMask[pA, pB]; cnt: CARDINAL _ CountInMaskOnesLmt[inCrossMask]; IF cnt>1 THEN RETURN[nop]; IF OutCrossed[pA,pB] THEN IF cnt = 1 THEN RETURN[nop] ELSE ERROR; -- Error["Bad Terms"]; RETURN[bad] ConsensusInputs[pA,pB,pC,inCrossMask]; IF cnt=1 THEN {sel _ 16; IF ~ConsensusOutputs[pA,pB,pC] THEN RETURN[nop]} ELSE {sel _ 0; MergeOutputs[pA,pB,pC]}; IF FstInSecXdIns [pB,pA] THEN sel _ sel + 8; -- A>B inputs IF FstInSecXdIns [pA,pB] THEN sel _ sel + 4; -- B>A inputs IF FstInSecXdOuts [pB,pA] THEN sel _ sel + 2; -- A>B outputs IF FstInSecXdOuts [pA,pB] THEN sel _ sel + 1; -- B>A outputs r _ SELECT sel FROM 0 => addM, 1 => nop, 2 => nop, 3 => nop, 4 => addM, 5 => delA, 6 => nop, 7 => delA, 8 => addM, 9 => nop, 10 => delB, 11 => delB, 12 => del2addC, 13 => delA, 14 => delB, 15 => delA, 16 => addC, 17 => addC, 18 => addC, 19 => addC, 20 => addC, 21 => delAaddC, 22 => addC, 23 => delAaddC, 24 => addC, 25 => addC, 26 => delBaddC, 27 => delBaddC, 28 => addC, 29 => delAaddC, 30 => delBaddC, 31 => del2addC, ENDCASE => ERROR; RETURN[r]}; CountInMaskOnesLmt: PROC [cross: QWSeq] RETURNS[cnt: CARDINAL] = INLINE{ cnt _ 0; FOR i: CARDINAL IN [0..cross.wdSize) WHILE cnt < 2 DO word: CARDINAL _ cross[i].m; word _ BITAND[word,052525B] + BITSHIFT[BITAND[word,125252B], -1]; word _ BITAND[word,031463B] + BITSHIFT[BITAND[word,146314B], -2]; word _ BITAND[word,007417B] + BITSHIFT[BITAND[word,170360B], -4]; word _ BITAND[word,000377B] + BITSHIFT[BITAND[word,177400B], -8]; cnt _ cnt + word; ENDLOOP}; <<>> CountInMaskOnes: PROC [cross: QWSeq] RETURNS[cnt: CARDINAL] = { cnt _ 0; FOR i: CARDINAL IN [0..cross.wdSize) DO word: CARDINAL _ cross[i].m; word _ BITAND[word,052525B] + BITSHIFT[BITAND[word,125252B], -1]; word _ BITAND[word,031463B] + BITSHIFT[BITAND[word,146314B], -2]; word _ BITAND[word,007417B] + BITSHIFT[BITAND[word,170360B], -4]; word _ BITAND[word,000377B] + BITSHIFT[BITAND[word,177400B], -8]; cnt _ cnt + word; ENDLOOP}; <<>> InSize: PROC [term: Term] RETURNS[cnt: CARDINAL] = { cnt _ 0; FOR i: CARDINAL IN [0..term.in.wdSize) DO word: CARDINAL _ 177777B - term.in[i].m; -- compliment => counting dontcares word _ BITAND[word,052525B] + BITSHIFT[BITAND[word,125252B], -1]; word _ BITAND[word,031463B] + BITSHIFT[BITAND[word,146314B], -2]; word _ BITAND[word,007417B] + BITSHIFT[BITAND[word,170360B], -4]; word _ BITAND[word,000377B] + BITSHIFT[BITAND[word,177400B], -8]; cnt _ cnt + word; ENDLOOP}; <<>> <<1 0 => TRUE>> InCrossed: PROC[pA, pB: Term] RETURNS[inCrossed: BOOL] = INLINE { FOR i: CARDINAL IN [0..pA.in.wdSize) DO IF BITAND[BITAND[pA.in[i].m, pB.in[i].m], BITXOR[pA.in[i].d, pB.in[i].d]]#0 THEN RETURN[TRUE] ENDLOOP; RETURN[FALSE]}; <<1 0 => TRUE>> InCrossMask: PROC[pA, pB: Term] RETURNS[QWSeq] = INLINE { IF incross = NIL OR incross.wdSize#pA.in.wdSize THEN incross _ NEW[QWSeqRec[pA.in.wdSize]]; FOR i: CARDINAL IN [0..pA.in.wdSize) DO incross[i].m _ BITAND[BITAND[pA.in[i].m, pB.in[i].m], BITXOR[pA.in[i].d, pB.in[i].d]] ENDLOOP; RETURN[incross]}; <<1 * => TRUE>> OutCrossed: PROC[pA,pB: Term] RETURNS[crossed: BOOL] = INLINE { crossed _ FALSE; FOR i: CARDINAL IN [0..pA.out.wdSize) DO crossed _ crossed OR (BITAND[BITAND[pA.out[i].d, pB.out[i].d], BITXOR[pA.out[i].m, pB.out[i].m]]) # 0; ENDLOOP}; <> <> <> << 0 1 *>> <<0 | 0 1 0>> <<1 | 1 1 1>> <<* | 0 1 *>> ConsensusInputs: PROC[pA,pB,pC: Term, mask: QWSeq _ NIL] = INLINE { IF mask = NIL THEN FOR i: CARDINAL IN [0..pA.in.wdSize) DO pC.in[i].d _ BITOR[pA.in[i].d, pB.in[i].d]; pC.in[i].m _ BITOR[pA.in[i].m, pB.in[i].m] ENDLOOP ELSE FOR i: CARDINAL IN [0..pA.in.wdSize) DO pC.in[i].d _ BITAND[ BITOR[pA.in[i].d, pB.in[i].d], BITNOT[mask[i].m]]; pC.in[i].m _ BITAND[ BITOR[pA.in[i].m, pB.in[i].m], BITNOT[mask[i].m]] ENDLOOP}; << 0 1 *>> <<0 | 0 0 0>> <<1 | 0 1 1>> <<* | 0 1 *>> ConsensusOutputs: PROC[pA, pB, pC: Term] RETURNS[BOOLEAN] = INLINE { allZero: BOOL _ TRUE; FOR i: CARDINAL IN [0..pA.out.wdSize) DO pC.out[i].d _ BITAND [pA.out[i].d, pB.out[i].d]; pC.out[i].m _ BITOR [pA.out[i].m, pB.out[i].m]; allZero _ allZero AND pC.out[i].d = 0; ENDLOOP; RETURN[NOT allZero]}; << 0 1 *>> <<0 | 0 1 0>> <<1 | 1 1 *>> <<* | 0 * *>> MergeOutputs: PROC[pA,pB,pC: Term] = INLINE { FOR i: CARDINAL IN [0..pA.out.wdSize) DO pC.out[i].d _ BITOR [pA.out[i].d, pB.out[i].d]; pC.out[i].m _ BITAND [pA.out[i].m, pB.out[i].m]; ENDLOOP}; FstInSecXdIns: PROC[aa,AA: Term] RETURNS[result: BOOLEAN] = INLINE { result _ TRUE; FOR i: CARDINAL IN [0..aa.in.wdSize) DO result _ result AND (BITAND[BITNOT[aa.in[i].m], AA.in[i].m]=0) ENDLOOP}; FstInSecXdOuts: PROC[aa,AA: Term] RETURNS[result: BOOLEAN] = INLINE { result _ TRUE; FOR i: CARDINAL IN [0..aa.out.wdSize) DO result _ result AND (BITAND[aa.out[i].d, BITNOT[AA.out[i].d]]=0) ENDLOOP}; SetInQrt: PUBLIC PROC[q: Qrt, t: Term, index: CARDINAL] = { t.in[index/16].m _ SetBit[t.in[index/16].m, index MOD 16, q=zero OR q=one]; t.in[index/16].d _ SetBit[t.in[index/16].d, index MOD 16, q=one]}; GetInQrt: PUBLIC PROC[term:Term, index:CARDINAL] RETURNS[q:Qrt] = { IF GetBit[term.in[index/16].m, index MOD 16] THEN IF GetBit[term.in[index/16].d, index MOD 16] THEN RETURN[one] ELSE RETURN[zero] ELSE IF GetBit[term.in[index/16].d, index MOD 16] THEN ERROR ELSE RETURN[dontcare]}; SetOutQrt: PUBLIC PROC[q: Qrt, t: Term, index: CARDINAL] = { t.out[index/16].m _ SetBit[t.out[index/16].m, index MOD 16, q=zero OR q=one]; t.out[index/16].d _ SetBit[t.out[index/16].d, index MOD 16, q#zero]}; GetOutQrt: PUBLIC PROC[term:Term, index:CARDINAL] RETURNS[q: Qrt] = { IF GetBit[term.out[index/16].m, index MOD 16] THEN IF GetBit[term.out[index/16].d, index MOD 16] THEN RETURN[one] ELSE RETURN[zero] ELSE IF GetBit[term.out[index/16].d, index MOD 16] THEN RETURN[undefined] ELSE ERROR}; SetBit: PROC[word, index: CARDINAL, val: BOOL] RETURNS[CARDINAL] = {IF val THEN RETURN[Basics.BITOR [word, Basics.BITSHIFT[1, 15-index]]] ELSE RETURN[Basics.BITAND [word, Basics.BITNOT[ Basics.BITSHIFT[1, 15-index]]] ]}; GetBit: PROC[word: CARDINAL, index:CARDINAL] RETURNS[BOOLEAN] = { RETURN[ Basics.BITAND[word, Basics.BITSHIFT[1, 15-index]] # 0 ]}; RopeToFormat: PUBLIC PROC [rope: IO.ROPE] RETURNS[iFormat, oFormat: Format] = { ropeIdx, spaceIndex, bitIndex, startIndex: INT _ 0; spaceBefore: BOOL; temp: CardSeq _ NEW[CardSeqRec[rope.Length[]]]; startIndex _ ropeIdx; spaceIndex _ bitIndex _ 0; spaceBefore _ TRUE; FOR ropeIdx _ startIndex, ropeIdx+1 WHILE ropeIdx < rope.Length[] DO SELECT rope.Fetch[ropeIdx] FROM '0, '1, '-, '+, 'x, 'X, '. => { IF spaceBefore THEN {temp[spaceIndex]_bitIndex; spaceIndex_spaceIndex+1}; bitIndex _ bitIndex+1; spaceBefore _ FALSE }; IO.SP, IO.TAB => spaceBefore _ TRUE; '| => EXIT; ENDCASE ENDLOOP; temp[spaceIndex]_bitIndex; iFormat _ NEW[FormatSeq[spaceIndex]]; FOR fldIdx: NAT _ 0, fldIdx+1 WHILE fldIdx < spaceIndex DO iFormat[fldIdx].firstBit _ temp[fldIdx]; iFormat[fldIdx].bitSize _ temp[fldIdx+1]-temp[fldIdx]; iFormat[fldIdx].name _ "field"; iFormat[fldIdx].name _ iFormat[fldIdx].name.Cat[IO.PutFR["%02g",IO.card[fldIdx]]] ENDLOOP; startIndex _ ropeIdx; spaceIndex _ bitIndex _ 0; spaceBefore _ TRUE; FOR ropeIdx _ startIndex, ropeIdx+1 WHILE ropeIdx < rope.Length[] DO SELECT rope.Fetch[ropeIdx] FROM '0, '1, '-, '+, 'x, 'X, '. => { IF spaceBefore THEN {temp[spaceIndex]_bitIndex; spaceIndex_spaceIndex+1}; bitIndex _ bitIndex+1; spaceBefore _ FALSE }; IO.SP, IO.TAB => spaceBefore _ TRUE; ENDCASE ENDLOOP; temp[spaceIndex]_bitIndex; oFormat _ NEW[FormatSeq[spaceIndex]]; FOR fldIdx: NAT _ 0, fldIdx+1 WHILE fldIdx < spaceIndex DO oFormat[fldIdx].firstBit _ temp[fldIdx]; oFormat[fldIdx].bitSize _ temp[fldIdx+1]-temp[fldIdx]; oFormat[fldIdx].name _ "field"; oFormat[fldIdx].name _ oFormat[fldIdx].name.Cat[IO.PutFR["%02g",IO.card[fldIdx]] ] ENDLOOP }; RopeToUse: PROC[rope: IO.ROPE] RETURNS[Use] = { SELECT rope.Fetch[0] FROM 'A => RETURN[avail]; 'U => RETURN[used]; 'E => RETURN[ess]; 'S => RETURN[skip]; 'D => RETURN[del]; ENDCASE => SIGNAL InvalidTermRope[rope]; RETURN[avail] }; UseToRope: PROC[use: Use] RETURNS[IO.ROPE] = { SELECT use FROM avail => RETURN["Available"]; used => RETURN["Used"]; ess => RETURN["Essential"]; skip => RETURN["Skipped"]; del => RETURN["Deleted"]; ENDCASE => ERROR }; ACopy: PUBLIC PROC[ref: Term, list: TermList] = { allDontCare: BOOL _ TRUE; FOR i: CARDINAL IN [0..ref.in.wdSize) DO IF NOT (allDontCare _ allDontCare AND ref.in[i] = initInQrtWdc) THEN EXIT ; REPEAT FINISHED => ERROR ENDLOOP; AppendTerm[CopyTerm[ref], list] }; END.