DIRECTORY AbSets, BasicTime, BiRels, IntStuff, IO, LichenArrayPrivate, LichenDataOps, LichenDataStructure, LichenIntBasics, Rope, SetBasics;

LichenArrayFlattening: CEDAR PROGRAM
IMPORTS AbSets, BasicTime, BiRels, IntStuff, IO, LichenArrayPrivate, LichenDataOps, LichenDataStructure, LichenIntBasics, SetBasics
EXPORTS LichenDataOps
=

BEGIN OPEN IS:IntStuff, Sets:AbSets, LIB:LichenIntBasics, LIB, LichenDataStructure, LichenDataOps;

FlattenArrays: PROC [d: Design, cts: Set--of CellType--, fix: BOOL, pacify: IO.STREAM] RETURNS [oks: Set--of CellType--, errs: Fn--CellType _ err msg--] ~ {
PerCT: PROC [ctv: Sets.Value] RETURNS [BOOL] ~ {
ct: CellType ~ NARROW[ctv.VA];
start: BasicTime.Pulses ~ BasicTime.GetClockPulses[];
IF pacify#NIL THEN pacify.PutRope[Describe[d, ct]];
{err: ROPE ~ FlattenArray[ct, fix];
IF err=NIL THEN {IF NOT oks.AddA[ct] THEN ERROR ELSE NULL}
ELSE errs.AddNewAA[ct, err];
IF pacify#NIL THEN {
end: BasicTime.Pulses ~ BasicTime.GetClockPulses[];
pacify.PutF[" %g\n", [real[BasicTime.PulsesToSeconds[end-start]]]]};
RETURN [FALSE]}};
oks _ Sets.CreateHashSet[d.eSpace];
errs _ BiRels.CreateHashTable[[d.eSpace, SetBasics.ropes[TRUE]]];
IF cts.Scan[PerCT].found THEN ERROR;
RETURN};

FlattenArray: PROC [outer: CellType, fix: BOOL _ TRUE] RETURNS [err: ROPE] ~ {
d: Design ~ outer.d;
oct: CellType ~ outer;
oa: Array ~ oct.asArray;
mct: CellType ~ oct.EltType[];
IF oa=NIL OR mct.asArray=NIL THEN RETURN ["not nested arrays"];
{ma: Array ~ mct.asArray;
rm: Int2 ~ Div[ma.size2, ma.basePeriod];
ict: CellType ~ mct.EltType[];
physXfm: Transform ~ VXfm[oa.fXfm.Apply[I2V[[0, 0]]].Val];
connXfm: Transform ~ ma.connToPhys.Compose[physXfm].Compose[oa.connToPhys];
connYfm: Transform ~ connXfm.Invert[];
mul: Int2 ~ connXfm.TransformSize[ma.size2];
xp: Int2 ~ connXfm.TransformSize[ma.basePeriod];
newPeriod: Int2 ~ [
X: IF oa.size2[X]=1 THEN xp[X] ELSE mul[X],
Y: IF oa.size2[Y]=1 THEN xp[Y] ELSE mul[Y]];
nrm: Int2 ~ Div[mul, newPeriod];
w00: Int2 ~ connXfm.TransformPos[[0, 0], mul];
dmul: Int2 ~ LIB.Sub[mul, [1, 1]];
newSize2: Int2 ~ Scale2[mul, oa.size2];
mRange: Range2 ~ SizeRange[ma.size2];
nRange: Range2 ~ SizeRange[newSize2];
cmin: CompositeArrayIndex ~ ma.ComposeAI[[0, 0]];
cmax: CompositeArrayIndex ~ ma.ComposeAI[LIB.Sub[ma.size2, [1, 1]]];
fXfm: Fn--phase _ Transform-- ~ BiRels.CreateHashTable[[int2s, xfmSpace]];
offsets: OffsetSeq ~ NEW [OffsetSequence[Area[newPeriod]]];
IF mul[X]>2 AND oa.size2[X]>1 OR mul[Y]>2 AND oa.size2[Y]>1 OR oa.basePeriod#ALL[1] OR LIB.Scale2[rm, ma.basePeriod]#ma.size2 THEN RETURN ["Thorny case"] --only because not implemented yet (because not efficient with current data structures)--;
FOR nfx: NATURAL IN [0 .. newPeriod[X]) DO FOR nfy: NATURAL IN [0 .. newPeriod[Y]) DO
nf: Int2 ~ [nfx, nfy];
xnf: Int2 ~ connYfm.TransformPos[nf, ma.size2];
mf: Int2 ~ Mod[xnf, ma.basePeriod];
kt: Int2 ~ LIB.Sub[xnf, mf];
xfm: Transform ~ VXfm[ma.fXfm.Apply[I2V[mf]].Val].Compose[physXfm];
cnf: NATURAL ~ newPeriod[Y]*nf[X]+nf[Y];
cmf: NATURAL ~ ComposePhase[ma, mf];
oop: OffsetPat ~ oa.offsets[0];
mop: OffsetPat ~ ma.offsets[cmf];
no1: Int2 ~ Div[oop.o1, nrm];
wo: Int2 ~ Div[LIB.Sub[w00, connXfm.TransformPos[kt, mul]], newPeriod];
no0: Int2 ~ LIB.Sub[Add[oop.o0, physXfm.TransformVector[mop.o0]], Scale2[no1, wo]];
IF Scale2[no1, nrm] # oop.o1 THEN RETURN ["outer step not a multiple of inner size"];
fXfm.AddNewPair[[I2V[nf], XfmV[xfm]]];
offsets[cnf] _ [o0: no0, o1: no1];
ENDLOOP ENDLOOP;
{na: Array ~ CreateArrayPart[oct, ict, newSize2, newPeriod, fXfm, offsets];
ConvertOuterEdge: PROC [val: Sets.Value] RETURNS [BOOL] ~ {
ose: StatEdge ~ NARROW[val.VA];
dd: Int2 ~ connYfm.TransformVector[Scale2[dmul, ose.d]];
cd: CompositeArrayIndex ~ ma.ComposeAI[dd];
dwf: DumbWire ~ NARROW[ma.dumrep.apToWire.ApplyA[ose.SeSv[oa, FALSE].port].MA];
dwt: DumbWire ~ NARROW[ma.dumrep.apToWire.ApplyA[ose.SeSv[oa, TRUE].port].MA];
fis: Set--of CompositeArrayIndex-- ~ dwf.eps.SetOn[right];
tis: Set--of CompositeArrayIndex-- ~ dwt.eps.SetOn[right];
shift: BiRel ~ BiRels.CreateShiftAndClipper[shift: IS.IE[cd], clip: [min: cmin, max: cmax]];
used: Set--of CompositeArrayIndex-- ~ Sets.CreateHashSet[SetBasics.ints];
rangeF: Range2 ~ Range2Intersection[nRange, Range2Off[nRange, Neg[ose.d]]];
fx: NATURAL ~ IF ose.d[X]<0 THEN ma.size2[X]-1 ELSE 0;
fy: NATURAL ~ IF ose.d[Y]<0 THEN ma.size2[Y]-1 ELSE 0;
PerPair: PROC [pair: BiRels.Pair] RETURNS [BOOL] ~ {
IF NOT used.AddElt[pair[left]] THEN RETURN [FALSE];
{tp: Port ~ NARROW[dwt.eps.Lookup[goal: pair[left], order: Sets.alleq].MA];
fp: Port ~ NARROW[dwf.eps.Lookup[goal: pair[right], order: Sets.alleq].MA];
tai: Int2 ~ connXfm.TransformPos[ma.DecomposeAI[pair[left].VI], mul];
fai: Int2 ~ connXfm.TransformPos[ma.DecomposeAI[pair[right].VI], mul];
MakeArrayConnectionAtPhase[d, na, rangeF, fai, ose.d, fp, tp];
RETURN [FALSE]}};
IF shift.ScanRestriction[[tis, fis], PerPair].found THEN ERROR;
IF used.Empty THEN RETURN [TRUE];
RETURN [FALSE]};
ConvertInnerEdge: PROC [val: Sets.Value] RETURNS [BOOL] ~ {
mse: StatEdge ~ NARROW[val.VA];
delta: Int2 ~ connXfm.TransformVector[mse.d];
fA: Int2 ~ connXfm.TransformPos[mse.SeSv[ma, FALSE].phase, mul];
rangeF: Range2 ~ Range2Intersection[nRange, Range2Off[nRange, Neg[delta]]];
MakeArrayConnectionAtPhase[d, na, rangeF, fA, delta, mse.SeSv[ma, FALSE].port, mse.SeSv[ma, TRUE].port];
RETURN [FALSE]};
ConvertExport: PROC [pair: BiRels.Pair] RETURNS [BOOL] ~ {
op: Port ~ NARROW[pair[left].VA];
opai: PortAtIndex ~ VPai[pair[right]];
mp: Port ~ opai.port;
mmpai: Sets.MaybeValue ~ ma.statrep.apToPAI.ApplyA[mp];
IF mmpai.found THEN {
mpai: PortAtIndex ~ VPai[mmpai.it];
mai: Int2 ~ connXfm.TransformPos[mpai.ai, mul];
MakeArrayExport[d, na, op, mpai.port, Mul[opai.ai, mul, mai]];
RETURN [FALSE]
}
ELSE {
IF d.Atomic[mp] THEN ERROR;
RETURN [FALSE]}};
IF oa.statrep.edges.Scan[ConvertOuterEdge].found THEN RETURN ["difficult edge"];
IF ma.statrep.edges.Scan[ConvertInnerEdge].found THEN ERROR;
IF oa.statrep.apToPAI.Scan[ConvertExport].found THEN ERROR;
SetArrayPart[oct, ict, na];
FinishedMakingArrayConnections[oct];
IF fix THEN FixInterleavingsOfArray[oct];
IF mct.Unused THEN DeleteCellType[mct, NIL];
RETURN [NIL]}}};

UnorganizeArray: PUBLIC PROC [act: CellType] ~ {
d: Design ~ act.d;
a: Array ~ act.asArray;
ect: CellType ~ act.EltType;
seen: Set ~ Sets.CreateHashSet[a.dumrep.dwSpace];
wConv: OneToOne--DumbWire f Wire-- ~ BiRels.CreateHashOTO[[a.dumrep.dwSpace, d.eSpace]];
iConv: OneToOne--CompositeArrayIndex f CellInstance-- ~ BiRels.CreateHashOTO[[SetBasics.ints, d.eSpace]];
FilloutDumbWire: PROC [dwv: Sets.Value] RETURNS [BOOL] ~ {
IF NOT seen.AddElt[dwv] THEN RETURN [FALSE];
{dw: DumbWire ~ NARROW[dwv.VA];
aPort: Port ~ NARROW[dw.eps.APair.P[][left].VA];
pKids: BiRel ~ d.SubSeq[aPort];
IF pKids#nilBiRel THEN FOR i: INT IN [0 .. pKids.Size.EN) DO
cdw: DumbWire ~ LichenArrayPrivate.GetDumbChild[act, aPort, dw, i];
[] _ FilloutDumbWire[AV[cdw]];
ENDLOOP;
RETURN [FALSE]}};
CopyDumbWire: PROC [dwv: Sets.Value] RETURNS [BOOL] ~ {
IF wConv.Apply[dwv].found THEN RETURN [FALSE];
{dw: DumbWire ~ NARROW[dwv.VA];
composite: BOOL ~ dw.children # nilBiRel;
kids: Seq _ nilBiRel;
IF composite THEN {
n: NAT ~ dw.children.Size.EN;
FOR i: NAT IN [0 .. n) DO [] _ CopyDumbWire[dw.children.ApplyI[i].Val] ENDLOOP;
kids _ dw.children.Compose[wConv, [TRUE, FALSE]].CreateHashCopy[];
IF kids.Size.EN # n THEN ERROR};
{w: Wire ~ CreateWire[act, emptySteppySet, FALSE, FALSE, FALSE, kids];
epc: Fn ~ dw.eps.Collect[right];
MoveName: PROC [pair: BiRels.Pair] RETURNS [BOOL] ~ {
ep: Port ~ NARROW[pair[left].VA];
epNames: Set ~ ect.PNames[ep];
MoveIndex: PROC [caiv: Sets.Value] RETURNS [BOOL] ~ {
cai: CompositeArrayIndex ~ caiv.VI;
ai: Int2 ~ DecomposeAI[a, cai];
ain: SteppyName ~ AIName[a, ai];
KnowPartNames[act, w, w, ActualNames[FALSE, OneSteppy[ain], epNames], FALSE];
RETURN [FALSE]};
cais: Set ~ Sets.VS[pair[right]];
IF cais.Size.EN = a.size THEN KnowPartNames[act, w, w, epNames, FALSE]
ELSE IF cais.Scan[MoveIndex].found THEN ERROR;
RETURN [FALSE]};
wConv.AddNewAA[dw, w];
IF epc.Scan[MoveName].found THEN ERROR;
RETURN [FALSE]}}};
ConnectByDumb: PROC [dwv: Sets.Value] RETURNS [BOOL] ~ {
dw: DumbWire ~ NARROW[dwv.VA];
pcs: BiRel ~ dw.eps.Compose[iConv, [TRUE, FALSE]];
w: Wire ~ NARROW[wConv.Apply[dwv].MA];
ConnectPCs[d, w, pcs];
RETURN [FALSE]};
FixAtoms: PROC [pv: Sets.Value] RETURNS [BOOL] ~ {
p: Port ~ NARROW[pv.VA];
pNames: Set _ nilSet;
IF NOT d.Atomic[p] THEN RETURN [FALSE];
FOR x: NAT IN [0 .. a.size2[X]) DO FOR y: NAT IN [0 .. a.size2[Y]) DO
ai: Int2 ~ [x, y];
cai: CompositeArrayIndex ~ ComposeAI[a, ai];
ci: CellInstance ~ NARROW[iConv.ApplyI[cai].MA];
w: Wire _ ConndWire[ci, p];
IF w=NIL THEN {
ain: SteppyName ~ AIName[a, ai];
IF pNames=nilSet THEN pNames _ ect.PNames[p];
w _ CreateWire[act, ActualNames[FALSE, OneSteppy[ain], pNames], FALSE, FALSE, FALSE];
Connect[d, w, p, ci]};
ENDLOOP ENDLOOP;
RETURN [FALSE]};
ConvertExport: PROC [pair: BiRels.Pair] RETURNS [BOOL] ~ {
ap: Port ~ NARROW[pair[left].VA];
w: Wire ~ NARROW[wConv.Apply[pair[right]].MA];
Connect[d, w, ap, act];
RETURN [FALSE]};
IF a.buildPhase # statrepFixed THEN ERROR;
IF a.dumrep.wires.Scan[FilloutDumbWire].found THEN ERROR;
ForgetArray[act];
FinishCreatingUnorganized[act];
IF a.dumrep.wires.Scan[CopyDumbWire].found THEN ERROR;
FOR x: NAT IN [0 .. a.size2[X]) DO FOR y: NAT IN [0 .. a.size2[Y]) DO
ai: Int2 ~ [x, y];
tf: QuotRem ~ DivMod[ai, a.basePeriod];
cai: CompositeArrayIndex ~ ComposeAI[a, ai];
ain: SteppyName ~ AIName[a, ai];
xfm: Transform _ [];
offset: Int2 _ dullInt2;
IF a.fXfm # nilBiRel THEN xfm _ VXfm[a.fXfm.Apply[I2V[tf.r]].Val];
IF a.offsets#NIL THEN {
cf: CompositeArrayIndex ~ ComposePhase[a, tf.r];
offset _ Mul[a.offsets[cf].o1, tf.q, a.offsets[cf].o0]};
{ci: CellInstance ~ Instantiate[ect, act, FALSE, xfm, offset, OneSteppy[ain]];
iConv.AddNewIA[cai, ci];
}ENDLOOP ENDLOOP;
IF a.dumrep.wires.Scan[ConnectByDumb].found THEN ERROR;
IF ect.CTParts[p].Scan[FixAtoms].found THEN ERROR;
IF a.dumrep.apToWire.Scan[ConvertExport].found THEN ERROR;
RETURN};

END.
bLichenArrayFlattening.Mesa
Last tweaked by Mike Spreitzer on August 22, 1988 4:35:01 pm PDT
Κ–

"cedar" style˜
code™Kš
œ@™@—K˜KšΟk	œ&œ[˜Œ
K˜šΟnœœ
˜$Kšœ&œT˜ƒ
Kšœ˜K˜
—K˜Kšœ
œ
œžœ	œœ%˜bK˜šž
œœΟcœœ
œ
œœ
Ÿœ
ŸΠcm
Ÿ
œ˜œ
šžœœœœ˜0Kšœœœ˜Kš
œ5˜5Kšœœ
œ!˜3Kšœœ˜#Kšœœ
œœ
œœ
œ
œ
œ
˜:Kšœ˜šœœ
œ˜Kš
œ3˜3K˜D—Kšœœ˜—K˜#Kšœ9œ˜AKšœœ
œ
˜$Kšœ˜—K˜šžœœœœœœ˜NK˜K˜K˜K˜Kšœœ
œ
œ
œ
œ˜?K˜Kš
œ(˜(K˜KšœΟg
œ
œ˜:Kš
œK˜KKš
œ&˜&Kš
œ,˜,Kš
œ0˜0š
œ˜Kšž
œœœœ˜+Kšž
œœœœ	˜,—K˜ Kš
œ.˜.Kšœ
œ˜"Kš
œ'˜'Kš
œ%˜%Kš
œ%˜%Kš
œ1˜1Kšœ)œ˜DKš‘
œŸ 
Ÿœ-˜JKšœœ#˜;Kšœ
œœ
œœœœ
œ$œ
œŸYœ
˜τ
šœ‘
Οd
œœ
œœ
œ‘
’
œœ
œ˜UKš	œ
‘
œ‘
’
œ‘
’
œ˜Kš	œ‘
œ‘
œ‘
œ
‘
œ˜/Kšœ
‘
œ‘
œ˜#Kšœœ‘
œ‘
œ˜Kšœ‘
œ
œ‘
œ˜CKš	œ‘
œœ‘
œ‘
œ˜(Kšœ‘
œœ‘
œ˜$Kš
œ˜Kšœ‘
œ˜!K˜Kšœœ5˜GKšœœD˜SKšœœ
œ-˜UKš‘
œœ‘
œ˜&Kšœ
‘
œ˜"Kšœ
œ
˜—Kšœ<‘
œ˜Kšžœœœœ˜;Kšœœœ˜Kš‘œ2‘
œ˜8Kšœ
‘
œ%‘œ˜+Kšœœ(œœ˜OKšœœ(œœ˜NKšœŸœ˜:KšœŸœ˜:Kšœ3œ
œ‘
œ!˜\Kšœ	Ÿœ&˜IKšœF‘
œ˜KKš‘
œœœ‘
œœœ˜6Kš‘
œœœ‘
œœœ˜6šžœœœœ˜4Kš
œ
œœ
œœ˜3Kšœœ5œ˜KKšœœ6œ˜KKšœ;œ˜EKšœ<œ˜FKšœ3‘
œ
˜>Kšœœ˜—Kšœ2œ
œ
˜?Kšœœ
œœ˜!Kšœœ˜—šžœœœœ˜;Kšœœœ˜Kšœ*‘
œ˜-Kš‘
œ,œ˜@Kš
œK˜KKšœ*‘
œœœ˜hKšœœ˜—šž
œœœœ˜:Kšœœœ˜!Kš
œ&˜&K˜Kš
œ7˜7šœ
œ˜Kš
œ#˜#Kš
œ/˜/Kš
œ>˜>Kšœœ
˜K˜
—šœ˜Kšœœ
œ
˜Kšœœ˜——Kšœ/œ
œ˜PKšœ/œ
œ
˜<Kšœ.œ
œ
˜;Kš
œ˜Kš
œ$˜$Kšœœ˜)Kšœœœ˜,Kšœœ˜—K˜šžœœ
œ˜0K˜K˜K˜K˜1KšœŸ 
Ÿœ6˜XKšœŸ 
Ÿœ4˜išžœœœœ˜:Kš
œ
œœ
œœ˜,Kšœœœ˜Kšœœœ˜0Kš
œ˜š
œœ
œœ
œœ˜<Kš
œC˜CKšœœ˜Kšœ
˜—Kšœœ˜—šžœœœœ˜7Kšœœ
œœ˜.Kšœœœ˜Kšœœ˜)K˜šœœ˜Kšœœœ
˜Kš
œœ
œ
œ.œ
˜OKšœ#œœ˜BKšœœœ
œ˜ —Kšœ+œœœ˜FK˜ šžœœœœ˜5Kšœœœ˜!Kš
œ˜šž	œœœœ˜5Kšœ œ
˜#Kš
œ˜Kš
œ ˜ Kšœ%œœ˜MKšœœ˜—Kšœœ˜!Kšœœ
œ#œ
˜FKšœ
œœ
œ
˜.Kšœœ˜—Kš
œ˜Kšœœ
œ
˜'Kšœœ˜—šž
œœœœ˜8Kšœœœ˜Kšœ$œœ˜2Kšœ
œœ˜&Kš
œ˜Kšœœ˜—šžœœœœ˜2Kšœ
œœ˜K˜Kš
œ
œ
œ
œœ˜'šœœ
œœ
œœ
œ˜EK˜Kš
œ,˜,Kšœœœ˜0K˜šœœ
œ˜Kš
œ ˜ Kšœœ˜-Kš	œ œœœœ˜UK˜—Kšœ
œ
˜—Kšœœ˜—šž
œœœœ˜:Kšœœœ˜!Kšœ
œœ˜.Kš
œ˜Kšœœ˜—Kšœœ
œ
˜*Kšœ,œ
œ
˜9Kš
œ˜Kš
œ˜Kšœ)œ
œ
˜6šœœ
œœ
œœ
œ˜EK˜Kš‘œ%˜'Kš
œ,˜,Kš
œ ˜ Kš
œ˜K˜Kšœ‘
œœ‘
œ
œ
‘œ
˜Bšœœ
œ˜Kšœ
‘
œ(‘œ˜0Kšœ‘
œ‘œ‘
œ˜8—Kšœ*œ˜NK˜Kšœ
œ
œ
˜—Kšœ*œ
œ
˜7Kšœ%œ
œ
˜2Kšœ-œ
œ
˜:Kšœ˜—K˜Kšœ
˜—…—':3»