File: BoolOptImplB.mesa   
Copyright © 1984 by Xerox Corporation. All rights reserved.
Created by: Mayo, July 16, 1984 4:44:25 pm PDT
Last Edited by: Mayo, September 4, 1984 5:48:47 pm PDT
Last Edited by: TWilliams, August 31, 1984 2:26:29 am PDT
DIRECTORY
BoolOps;
BoolOpsImplB: CEDAR PROGRAM    
EXPORTS BoolOps = BEGIN
OPEN BoolOps;
ptermHashSize: INT = 5000;
ptermArray: TYPE = ARRAY [0..ptermHashSize) OF LIST OF REF PTerm ← ALL[NIL];
ptermHashTab: TYPE = RECORD [
numEntries: INT ← 0,
lengths: REF ptermArrayLengths ← NEW[ptermArrayLengths],
vals: REF ptermArray ← NEW[ptermArray]
];
ptermArrayLengths: TYPE = ARRAY [0..ptermHashSize) OF NATALL[0];
pTermSeq: TYPE = REF pTermSeqRep ← NIL;
pTermSeqRep: TYPE = RECORD [
pterms: SEQUENCE size: NAT OF REF PTerm
];
Optimize a truth table. Method used is tailored for PLAs.
TTOptimize: PUBLIC PROC [tt: TruthTable] RETURNS [TruthTable] = BEGIN
NewPTermSeq: 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: BOOLTRUE;
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;
lastNumPterms: INT;
DO
lastNumPterms ← tt.numPTerms;
tt ← MergeOrOfDuplicateAndTerms[tt];
tt ← MergeAndOfLikeOrTerms[tt];
IF tt.numPTerms > lastNumPterms THEN ERROR;
IF tt.numPTerms = lastNumPterms THEN EXIT;
ENDLOOP;
RETURN[tt];
END;
END.