New
PTermSeq:
PROC [ nTerms:
NAT]
RETURNS [ s: pTermSeq ] =
{ s ← NEW[pTermSeqRep[ nTerms ]] };
CopyPTerm:
PROC [old:
REF PTerm, size:
CARDINAL]
RETURNS [
REF PTerm] =
BEGIN
new: REF PTerm ← NEW[PTerm[size]];
-- compiler bug: can't assign sequences (as in new ← NEW[PTerm[size] ← old^])
FOR i:
INT
IN [0..size)
DO
new[i] ← old[i];
ENDLOOP;
RETURN[new];
END;
MergeOrOfDuplicateAndTerms: PROC [tt: TruthTable] RETURNS [TruthTable] = BEGIN
tab: ptermHashTab;
hash: INT;
ins: CARDINAL ~ tt.numInputs;
outs: CARDINAL ~ tt.numOutputs;
newTt: TruthTable;
-- hash each pterm into a bucket, combining terms if possible
FOR i:
INT
IN [0..tt.numPTerms)
DO
deleteMe, addMe: REF PTerm ← NIL;
term: REF PTerm ~ tt.pterms[i];
matched: BOOL;
hash ← 0;
FOR bit:
INT
IN [0 .. ins)
DO
hash ← hash * 3 + ORD[term[bit]];
ENDLOOP;
hash ← ABS[hash] MOD ptermHashSize;
-- do the input bits match an existing term?
matched ← FALSE;
FOR pt:
LIST
OF
REF PTerm ← tab.vals[hash], pt.rest
WHILE pt #
NIL
DO
matched ← TRUE;
FOR i:
INT
IN [0 .. ins)
DO
IF pt.first[i] # term[i] THEN matched ← FALSE;
ENDLOOP;
IF matched
THEN {
-- OR in the new term
newList: LIST OF REF PTerm ← NIL;
newTerm: REF PTerm ← CopyPTerm[pt.first, ins + outs];
FOR k:
INT
IN [ins .. ins + outs)
DO
IF term[k] = $One THEN newTerm[k] ← $One;
ENDLOOP;
FOR old:
LIST
OF
REF PTerm ← tab.vals[hash], old.rest
WHILE old #
NIL
DO
IF old.first = pt.first
THEN
newList ← CONS[newTerm, newList]
ELSE
newList ← CONS[old.first, newList];
ENDLOOP;
tab.vals[hash] ← newList;
EXIT;
};
ENDLOOP;
IF ~matched
THEN {
-- can not be combined with existing term
tab.vals[hash] ← CONS[term, tab.vals[hash]];
tab.numEntries ← tab.numEntries + 1;
};
ENDLOOP;
newTt ← NEW[TruthTableRec[tab.numEntries]];
newTt.numInputs ← ins;
newTt.numOutputs ← outs;
newTt.numPTerms ← 0;
FOR i:
INT
IN [0..ptermHashSize)
DO
FOR pt:
LIST
OF
REF PTerm ← tab.vals[i], pt.rest
WHILE pt #
NIL
DO
newTt.pterms[newTt.numPTerms] ← pt.first;
newTt.numPTerms ← newTt.numPTerms + 1;
ENDLOOP;
ENDLOOP;
IF newTt.numPTerms # tab.numEntries THEN ERROR; -- more items than indicated by h.numEntries
RETURN[newTt];
END;
MergeAndOfLikeOrTerms:
PROC [tt: TruthTable]
RETURNS [TruthTable] =
BEGIN
tab: ptermHashTab;
hash: INT;
ins: CARDINAL ~ tt.numInputs;
outs: CARDINAL ~ tt.numOutputs;
newTt: TruthTable;
-- hash each pterm into a bucket based upon the output bits
FOR i:
INT
IN [0..tt.numPTerms)
DO
term: REF PTerm ~ tt.pterms[i];
hash ← 0;
FOR bit:
INT
IN [ins .. ins + outs)
DO
hash ← hash * 3 + ORD[term[bit]];
ENDLOOP;
hash ← ABS[hash] MOD ptermHashSize;
tab.vals[hash] ← CONS[term, tab.vals[hash]];
tab.lengths[hash] ← tab.lengths[hash] + 1;
tab.numEntries ← tab.numEntries + 1;
ENDLOOP;
newTt ← NEW[TruthTableRec[tab.numEntries]];
newTt.numInputs ← ins;
newTt.numOutputs ← outs;
newTt.numPTerms ← 0;
FOR i:
INT
IN [0..ptermHashSize)
DO
numPTermsThisBucket: NAT ← tab.lengths[i];
bucketPTerms: pTermSeq ← NewPTermSeq[ numPTermsThisBucket ];
transfer bucket LIST to a working SEQUENCE
bucketIndex: NAT ← 0;
FOR pt:
LIST
OF
REF PTerm ← tab.vals[i], pt.rest
WHILE pt #
NIL
DO
bucketPTerms[bucketIndex] ← pt.first;
bucketIndex ← bucketIndex + 1;
ENDLOOP;
combine terms in each bucket
FOR pt1:
NAT ← 0 , pt1+1
WHILE pt1 < numPTermsThisBucket
DO
pt2: INTEGER ← 0;
WHILE pt2 < numPTermsThisBucket
DO
sameOuts: BOOL ← TRUE;
differInBits: INT ← 0;
differBit: INT;
FOR bit:
INT
IN [ins .. ins + outs)
DO
IF bucketPTerms[pt1][bit] # bucketPTerms[pt2][bit]
THEN {
sameOuts ← FALSE;
EXIT;
};
ENDLOOP;
IF sameOuts
THEN {
FOR bit:
INT
IN [0 .. ins)
DO
IF bucketPTerms[pt1][bit] # bucketPTerms[pt2][bit]
THEN {
differInBits ← differInBits + 1;
differBit ← bit;
};
ENDLOOP;
IF differInBits = 1
THEN {
-- remake the bucket, replacing bucketPTerms[pt1] with a combined term and removing bucketPTerms[pt2]
bucketPTerms[pt1][differBit] ← $NC;
FOR pt3:
NAT
IN [0..numPTermsThisBucket)
DO
IF pt3=pt2
THEN {
numPTermsThisBucket ← numPTermsThisBucket -1;
tab.numEntries ← tab.numEntries - 1;
};
IF pt3 > pt2 THEN bucketPTerms[pt3-1] ← bucketPTerms[pt3];
ENDLOOP;
pt2 ← -1;
};
};
pt2 ← pt2 + 1;
ENDLOOP;
ENDLOOP;
-- make the truth table
FOR pt:
NAT
IN [0..numPTermsThisBucket)
DO
newTt.pterms[newTt.numPTerms] ← bucketPTerms[pt];
newTt.numPTerms ← newTt.numPTerms + 1;
ENDLOOP;
ENDLOOP;
IF newTt.numPTerms # tab.numEntries THEN ERROR; -- differing # items than indicated by tab.numEntries
RETURN[newTt];
END;
DO
lastNumPterms ← tt.numPTerms;
tt ← MergeOrOfDuplicateAndTerms[tt];
tt ← MergeAndOfLikeOrTerms[tt];
IF tt.numPTerms > lastNumPterms THEN ERROR;
IF tt.numPTerms = lastNumPterms THEN EXIT;
ENDLOOP;