
<<Adder.mesa >>
<<Copyright c 1985 by Xerox Corporation.  All rights reserved.>>
<<RemoveButton CD; CreateButton A Compile Adder; Run Adder>>
<<Last Edited by Curry, April 2, 1985 10:51:48 am PST>>
<<>>
<<>>
DIRECTORY 
Basics,
CD,
CDCells,
CMos,
IFUPW,
PW, 
PWBasics;

Adder: CEDAR PROGRAM    
IMPORTS    Basics, CDCells, CMos, IFUPW, PW, PWBasics
EXPORTS    IFUPW =
BEGIN OPEN IFUPW;


AdderTree: PUBLIC PROC[
design:            CD.Design,
firstSumBits:        CARDINAL,
interleaveDepth:    CARDINAL,
resultSums:        CARDINAL,
names:            LIST OF AdderNames _ NIL,
blankCells:        LIST OF BOOL _ NIL ]
RETURNS[new: PW.ObjName]= {    -- positive bus on top
<<Generates a flat adder of width firstSumBits * interleaveDepth with resultSums results>>
<<For instance:>>
<<AdderTree[32, 1, 1]    => One ordinary 32 bit adder>>
<<AdderTree[8, 4, 1]    => One 32 bit adder organized in the Dragon byte format >>
<<AdderTree[8, 4, 4]    => Four 8 bit adders organized in the Dragon byte format >>
<<Parameter Requirements: (for now at least)>>
<<all parameter must be powers of 2 >>
<<IF firstSumBits is 1 THEN resultSums must be 1>>
<<resultSums must be <= interleaveDepth>>
<<Uses 4 cells:>>
<<AdderSum, AdderGCP0, AdderGCP1 and AdderWireTile;>>
<<AdderWireTile contains 7 conditional objects:>>
<<Pass, ExtRt, ExtLt, ConnLtRt, ConnLtLt, ConnLtLtX and ConnRtRt>>
iDepth1:            CARDINAL    _ PW.TwoToTheLog2[interleaveDepth];
iDepth2:            CARDINAL    _ PW.TwoToTheLog2[resultSums];
size1:                CARDINAL    _ PW.TwoToTheLog2[firstSumBits];
size2:                CARDINAL    _ iDepth1/iDepth2;
levels1:            CARDINAL    _ PW.Log2[size1];        -- Not counting zero
levels2:            CARDINAL    _ PW.Log2[size2];        -- Not counting zero
tree2InputsPos:    BOOL            _ (levels1 MOD 2)=1;    -- => upside down
tree1,        tree2:    PW.ObjName    _ NIL;
xform,    base:    PW.ObjName    _ NIL;
outPutD1:    CARDINAL _ (levels1+1)/2*iDepth1;                -- Tree1 output side depth
outNotD1:    CARDINAL _  levels1    /2*iDepth1;                -- Tree1 not output side depth
inPutD2:    CARDINAL _  levels2    /2*iDepth2+iDepth1;    -- Tree2 input side depth+xform
inNotD2:    CARDINAL _ (levels2+1)/2*iDepth2;                -- Tree2 not input side depth
IF levels1#0 THEN {
PWBasics.Output["\nBuilding Adder tree1"];
tree1 _ AdderGCPTree[
design:        design,
size:            size1,
depth:            iDepth1,
endCell:        levels2= 0,
inputsPos:    FALSE,
inPutPad:        0,
inNotPad:        0,
outPutPad:    inPutD2 - MIN[outPutD1, inPutD2],
outNotPad:    inNotD2 - MIN[outNotD1, inNotD2],
blankCells:    blankCells,
names:        names ]};
IF levels2#0 THEN {
PWBasics.Output["\nBuilding Adder tree2"];
tree2 _ AdderGCPTree[
design:        design,
size:            size2,
depth:            iDepth2,
endCell:        TRUE,
inputsPos:    tree2InputsPos,
inPutPad:        outPutD1 - MIN[inPutD2, outPutD1],
inNotPad:        outNotD1 - MIN[inNotD2, outNotD1],
outPutPad:    0,
outNotPad:    0,
blankCells:    NIL,
names:        names ] };
IF levels1#0 AND levels2#0 THEN {
PWBasics.Output["\nBuilding Adder xform"];
xform _ AdderIDepthXForm[iDepth1, iDepth2];    -- Defined for positive bus
IF NOT tree2InputsPos THEN xform _ PW.FlipY[xform]};
PWBasics.Output["\nBuilding Adder base"];
base _ AdderBaseTree[size1, iDepth1, blankCells];
PWBasics.Output["\nBuilding Adder ... "];
IF levels1#0 AND levels2#0 THEN IF tree2InputsPos
THEN    new _ PW.AbutY[tree2,        xform]
ELSE    new _ PW.AbutY[xform,    tree2];
new _ PW.AbutX[tree1,    new];
new _ PW.AbutY[base,    new];
PWBasics.Output["done\n"]};

AdderGCPTree: PROC[    -- positive bus on top
design:        CD.Design,
size:            CARDINAL,
depth:            CARDINAL,
endCell:        BOOL,
inputsPos:    BOOL,
inPutPad:        CARDINAL,
inNotPad:        CARDINAL,
outPutPad:    CARDINAL,
outNotPad:    CARDINAL,
blankCells:    LIST OF BOOL            _ NIL,
names:        LIST OF AdderNames    _ NIL] RETURNS[new: PW.ObjName] = {
InputSide:    PROC[levIndex: CARDINAL] RETURNS[BOOL] = {RETURN[(levIndex MOD 2)=0]};
list:            LIST OF PW.ObjName    _ NIL;
tile:            PW.ObjName                _ NIL;
sizeUsed:        CARDINAL _ IF endCell THEN size ELSE size-1;
outLevel:        CARDINAL    _ PW.Log2[size];
topPad:        CARDINAL;
botPad:        CARDINAL;
topTile:        PW.ObjName;
botTile:        PW.ObjName;
sglBlank:        PW.ObjName _ PW.Inst["AdderWireTile", LIST[                    ],    FALSE];
sglExtend:    PW.ObjName _ PW.Inst["AdderWireTile", LIST["ExtLt",  "ExtRt"],     FALSE];
sglExtLt:        PW.ObjName _ PW.Inst["AdderWireTile", LIST["ExtLt"],             FALSE];
endCellOutsOnInputSide: BOOL _ NOT InputSide[outLevel];
wires: GCPWires _ GCPWireGen[PW.Log2[depth], blankCells, design, names];
FOR index: CARDINAL DECREASING IN [0..sizeUsed) DO
FOR group: CARDINAL DECREASING IN [0..depth) DO
tile, cell:        PW.ObjName _ NIL;
input, other:    PW.ObjName _ NIL;
level:            CARDINAL    _ 0;
isEdgeCell:    BOOL    _ FALSE;
isEndCell:    BOOL    _ FALSE;
inputSide:    LIST OF PW.ObjName _ NIL;
otherSide:        LIST OF PW.ObjName _ NIL;
wire:            GCPWireNames _ wires[group];
test:            CARDINAL    _ 0;
PWBasics.Output["."];
FOR test_index, test/2 WHILE (test MOD 2 )=1 DO level _ level +1 ENDLOOP;
test            _ Basics.BITXOR[index/2, index];
isEndCell        _ level = outLevel;    -- EndCell would connect at outLevel
isEdgeCell    _ isEndCell AND (group = (depth-1));
FOR lev: CARDINAL DECREASING IN (0..outLevel] DO
tile _ wire[(SELECT lev FROM
> level+1        => IF PW.XthBitOfN[lev-1, test]
THEN    (IF level=0 AND InputSide[lev] THEN extPass    ELSE pass)
ELSE    (IF level=0 AND InputSide[lev] THEN extend    ELSE blank),
  level+1        => IF PW.XthBitOfN[lev, index]    THEN    driveLtX    ELSE    driveRt,
  level        => IF isEdgeCell THEN connNm ELSE conn,
< level        => IF InputSide[level]=InputSide[lev]    THEN    extend     ELSE    extLt,
ENDCASE     => ERROR)];
IF isEndCell AND outLevel>1 AND InputSide[lev]#InputSide[level]
THEN tile _ wire
[(IF lev>2 THEN blank ELSE IF isEdgeCell THEN driveRtNm ELSE driveRt)];
IF InputSide[lev]
THEN    inputSide    _ CONS[tile, inputSide]
ELSE    otherSide    _ CONS[tile, otherSide];
ENDLOOP;
tile _ IF Blanking[group, blankCells]
THEN "AdderGCPBlank"
ELSE IF  InputSide[level] = inputsPos
THEN    "AdderGCP1"        -- Defined Pos inputs UP and  inverted output Down
ELSE    "AdderGCP0";    -- Defined Pos output UP and  inverted inputs Down
IF inputsPos THEN tile _ PW.FlipY[tile];    -- Input side down
input    _ PW.AbutListY[ inputSide];
IF input#NIL THEN input    _ PW.FlipY[input];
other    _ PW.AbutListY[ otherSide];
topPad _ inNotPad+(IF InputSide[outLevel] THEN outNotPad ELSE outPutPad);
botPad _ inPutPad+(IF InputSide[outLevel] THEN outPutPad ELSE outNotPad);
topTile _ IF InputSide[level] THEN sglExtLt        ELSE sglExtend;
botTile _ IF InputSide[level] THEN sglExtend    ELSE sglExtLt;
IF isEndCell AND outLevel<2 THEN { -- not yet included in tree
IF            endCellOutsOnInputSide AND botPad>=depth THEN {
tile_PW.AbutY[PW.FlipY[
wire[(IF isEdgeCell THEN driveRtNm ELSE driveRt)]    ],    tile];
botTile _ sglBlank;
botPad _ botPad-depth};
IF     NOT    endCellOutsOnInputSide AND topPad>=depth THEN
{tile _ PW.AbutY[tile, wire[IF isEdgeCell THEN driveRtNm ELSE driveRt]];
topTile _ sglBlank;
topPad _ topPad-depth } };
THROUGH [0..topPad) DO    tile _ PW.AbutY[tile,        topTile]    ENDLOOP;
THROUGH [0..botPad) DO    tile _ PW.AbutY[botTile,        tile]    ENDLOOP;
cell    _ PW.AbutListY[ LIST[input, tile, other]];    -- Input side down
IF inputsPos THEN cell _ PW.FlipY[cell]; -- positive side up
new _ PW.AbutX[cell, new];
ENDLOOP;
ENDLOOP };


AdderIDepthXForm: PROC[ depth1, depth2: CARDINAL]    -- for positive bus (top)
RETURNS[new: PW.ObjName] = { -- for top positive bus
xIndexRange:        CARDINAL    _ (depth1/depth2)/2;
yIndexRange:    CARDINAL    _ (depth1/depth2)/2;
xSumRange:        CARDINAL    _ depth1/xIndexRange;
ySumRange:        CARDINAL    _ xSumRange/2;
conn, cross, pass, extend, blank, cell: PW.ObjName;
conn        _                PW.Inst["AdderWireTile", LIST["ConnLtLtX"], FALSE];
conn        _ PW.AbutY[    PW.Inst["AdderWireTile", LIST["ExtLt", "ConnRtLtX"], FALSE], conn];
cross        _                PW.Inst["AdderWireTile", LIST["ExtLt", "ExtRt", "Pass"], FALSE];
cross        _ PW.AbutY[    cross, cross];
pass        _                PW.Inst["AdderWireTile", LIST["Pass"], FALSE];
pass        _ PW.AbutY[    pass, pass];
extend    _                PW.Inst["AdderWireTile", LIST["ExtLt", "ExtRt"], FALSE];
extend    _ PW.AbutY[    extend, extend];
blank        _                PW.Inst["AdderWireTile", LIST[ ], FALSE];
blank        _ PW.AbutY[    blank, blank];
new _ NIL;
<<>>
<<Build from Rt to Lt and bottom to top assuming top bus application>>
FOR xIndex:    CARDINAL DECREASING IN [0..xIndexRange) DO
FOR xSum:    CARDINAL DECREASING IN [0..xSumRange) DO
cell _ NIL;
FOR ySum:    CARDINAL DECREASING IN [0..ySumRange) DO
FOR yIndex:    CARDINAL DECREASING IN [0..yIndexRange) DO
cell _ PW.AbutY[cell, (SELECT TRUE FROM
ySum        =    xSum    AND yIndex    =    xIndex    =>    conn,
ySum        >=    xSum    AND yIndex    >=    xIndex    =>    cross,
yIndex    >    xIndex                                =>    pass,
ySum        >    xSum                                    =>    extend
ENDCASE                                                =>    blank)];
ENDLOOP
ENDLOOP;
new _ PW.AbutX[cell, new];
ENDLOOP
ENDLOOP};

Blanking: PROC[index: INT, blankCell: LIST OF BOOL] RETURNS [BOOL] = {
IF blankCell=NIL    THEN RETURN[FALSE];
IF index=0            THEN RETURN[blankCell.first];
IF index>0            THEN RETURN[Blanking[index-1, blankCell.rest]];
ERROR};

GCPWires:        TYPE = REF GCPWireRec;
GCPWireRec:        TYPE = RECORD[SEQUENCE size: CARDINAL OF GCPWireNames];
GCPWireNames:    TYPE = ARRAY GCPWireType OF PW.ObjName;
GCPWireType:    TYPE =
{pass, blank, driveLtX, driveRt, extend, extLt, extPass, conn, connNm, driveRtNm};

GCPWireGen: PROC[
iDepthLog:    CARDINAL,
blankCells:    LIST OF BOOL,
design:        CD.Design,
names:        LIST OF AdderNames _ NIL]
RETURNS[wires: GCPWires] = { -- for top bus
Wire: PROC
[i:            CARDINAL,
type:        GCPWireType,
pieces:    LIST OF PW.ROPE         _ NIL,
alt:        LIST OF PW.ROPE        _ NIL,
flip:        BOOL                        _ FALSE] = {
cell: PW.ObjName;
IF Blanking[i, blankCells] THEN pieces _ alt;
cell _ PW.Inst["AdderWireTile", pieces, FALSE];
IF flip THEN cell    _ PW.FlipY[cell];
wires[i][type]        _ PW.AbutY[wires[i][type],  cell] };
iDepth: CARDINAL    _ PW.TwoToThe[iDepthLog];
wires                    _ NEW[GCPWireRec[iDepth]];
<<Array set up so that if wires placed below GCP row must be flipped in Y>>
PWBasics.Output[" "];
FOR ii: CARDINAL IN [0..iDepth) DO    -- cell group index
PWBasics.Output["!"];
FOR jj: CARDINAL DECREASING IN [0..iDepth) DO    -- bottom to top
<<>>
IF Blanking[jj, blankCells] THEN LOOP;
<<These are used for building the GCP trees>>
Wire[ii, pass,    LIST["Pass"],                        LIST["Pass"]];
Wire[ii, blank,    LIST[ ],                            LIST[ ] ];
Wire[ii, extLt,    LIST["ExtLt"],                    LIST[ ] ];
Wire[ii, extend,    LIST["ExtLt", "ExtRt"],            LIST[ ] ];
Wire[ii, extPass,    LIST["ExtLt", "ExtRt", "Pass"],    LIST["Pass"] ];
SELECT jj FROM
<ii            =>    Wire[ii, driveLtX,    LIST[ ],                                LIST[ ]];
=ii            =>    Wire[ii, driveLtX,    LIST["ConnLtLtX"],                    LIST[ ]];
ENDCASE=>    Wire[ii, driveLtX,    LIST["ExtLt", "Pass"],                LIST["Pass"]];
SELECT jj FROM
<ii            =>    Wire[ii, driveRt,        LIST["Pass"],                            LIST["Pass"]];
=ii            =>    Wire[ii, driveRt,        LIST["ConnLtRt"],                    LIST[ ]];
ENDCASE    =>    Wire[ii, driveRt,        LIST["ExtLt"],                        LIST[ ]];
SELECT jj FROM
<ii            =>    Wire[ii, conn,        LIST["Pass"],                            LIST["Pass"]];
=ii            =>    Wire[ii, conn,        LIST["ConnLtLtX", "ConnRtRt"],    LIST[ ]];
ENDCASE    =>    Wire[ii, conn,        LIST["ExtLt", "ExtRt", "Pass"],        LIST["Pass"] ];
ENDLOOP;
IF ii=(iDepth-1) THEN {
drRtNm:    CD.ObPtr    _ CDCells.CreateEmptyCell[];
connNm:    CD.ObPtr    _ CDCells.CreateEmptyCell[];
drRt:        CD.ObPtr    _ PWBasics.ObjFromName[design, wires[ii][driveRt]];
conn:        CD.ObPtr    _ PWBasics.ObjFromName[design, wires[ii][conn]];
size:    Size        _ PWBasics.GetISize[conn];
loc:    Location    _ [size.x-4, size.y-28];
nameRec:    AdderNames;
[] _ PWBasics.IncludeApplication[drRtNm,    drRt];
[] _ PWBasics.IncludeApplication[connNm,    conn];
FOR jj: CARDINAL IN [0..iDepth) DO
IF Blanking[jj, blankCells] THEN LOOP;
IF names=NIL
THEN    nameRec _ [ ]
ELSE    {nameRec _ names.first; names _ names.rest};
PutPin[drRtNm,    [4,4], [loc.x, loc.y+20], CMos.pol, nameRec.gout ];
PutPin[drRtNm,    [4,4], [loc.x, loc.y+12], CMos.pol, nameRec.cin ];
PutPin[drRtNm,    [4,4], [loc.x, loc.y+04], CMos.pol, nameRec.pout ];
PutPin[connNm,    [4,4], [loc.x, loc.y+20], CMos.pol, nameRec.gin ];
PutPin[connNm,    [4,4], [loc.x, loc.y+12], CMos.pol, nameRec.cout ];
PutPin[connNm,    [4,4], [loc.x, loc.y+04], CMos.pol, nameRec.pin ];
loc.y _ loc.y-28;
ENDLOOP;
PWBasics.RepositionCell[design, drRtNm];
PWBasics.RepositionCell[design, connNm];
wires[ii][driveRtNm]    _ PWBasics.NameFromObj[drRtNm];
wires[ii][connNm]        _ PWBasics.NameFromObj[connNm]};
ENDLOOP };

BaseWires:        TYPE = REF BaseWireRec;
BaseWireRec:        TYPE = RECORD[SEQUENCE size: CARDINAL OF BaseWireNames];
BaseWireNames:    TYPE = ARRAY BaseWireType OF PW.ObjName;
BaseWireType:    TYPE = {extConnRt, connLt};

BaseWireGen: PROC[iDepthLog: CARDINAL, blankCells: LIST OF BOOL]
RETURNS[wires: BaseWires] = { -- for top bus
Wire: PROC
[i:            CARDINAL,
type:        BaseWireType,
pieces:    LIST OF PW.ROPE     _ NIL,
alt:        LIST OF PW.ROPE    _ NIL,
flip:        BOOL                    _ FALSE] = {
cell: PW.ObjName;
IF Blanking[i, blankCells] THEN pieces _ alt;
cell _ PW.Inst["AdderWireTile", pieces, FALSE];
IF flip THEN cell    _ PW.FlipY[cell];
wires[i][type]        _ PW.AbutY[wires[i][type],  cell] };
iDepth: CARDINAL    _ PW.TwoToThe[iDepthLog];
wires                    _ NEW[BaseWireRec[iDepth]];
<<Array set up so that if wires placed below GCP row must be flipped in Y>>
PWBasics.Output[" "];
FOR ii: CARDINAL IN [0..iDepth) DO    -- cell group index
PWBasics.Output["!"];
FOR jj: CARDINAL IN [0..iDepth) DO    -- bottom to top
<<>>
IF Blanking[jj, blankCells] THEN LOOP;
<<>>
<<These are used for connecting the summers below the GCP trees>>
SELECT jj FROM                                    -- msb at bottom
<ii            =>    Wire[ii, extConnRt,    LIST["ExtLt", "Pass"],        LIST["Pass"] ];
=ii            =>    Wire[ii, extConnRt,    LIST["ExtLt", "ConnRtRt"],    LIST[ ], TRUE];
ENDCASE    =>    Wire[ii, extConnRt,    LIST["ExtLt", "ExtRt"],        LIST[ ] ];
SELECT jj FROM                                    -- msb at bottom
<ii            =>    Wire[ii, connLt,        LIST["ExtLt"],                LIST[ ] ];
=ii            =>    Wire[ii, connLt,        LIST["ConnLtLt"],            LIST[ ] ];
ENDCASE    =>    Wire[ii, connLt,        LIST["Pass"],                    LIST["Pass"] ];
ENDLOOP;
ENDLOOP };


AdderBaseTree: PROC[size, depth: CARDINAL, blankCells: LIST OF BOOL _ NIL]
RETURNS[new: PW.ObjName] = {
cell0, cell1, base: PW.ObjName _ NIL;
wires: BaseWires _ BaseWireGen[PW.Log2[depth], blankCells];
new _ NIL;
FOR index: CARDINAL IN [0..depth) DO
cell0    _ PW.AbutX[cell0,    wires[index][extConnRt]];
cell1    _ PW.AbutX[cell1,    wires[index][connLt]];
base    _ PW.AbutX[base,    (IF Blanking[index, blankCells]
THEN    "AdderSumBlank"
ELSE    "AdderSum")];
ENDLOOP;
cell0    _ PW.AbutY[base,    cell0];
cell1    _ PW.AbutY[base,    cell1];
FOR index: CARDINAL IN [0..size) DO
IF ((index MOD 2) = 0)
THEN    new    _ PW.AbutX[new,    cell0]
ELSE    new    _ PW.AbutX[new,    cell1] ENDLOOP };


Adder32x1x1:        PW.UserProc = {RETURN[ AdderTree[design, 32, 1, 1]]};
Adder8x4x1:        PW.UserProc = {RETURN[ AdderTree[design, 8, 4, 1]]};
Adder8x4x4:        PW.UserProc = {RETURN[ AdderTree[design, 8, 4, 4]]};
Adder8x4x4x2:    PW.UserProc = {RETURN[ AdderTree[design, 8, 4, 4,
NIL, LIST[TRUE, FALSE, TRUE, FALSE]]]};

PW.Register[Adder32x1x1,        "Adder32x1x1"];
PW.Register[Adder8x4x1,        "Adder8x4x1"];
PW.Register[Adder8x4x4,        "Adder8x4x4"];
PW.Register[Adder8x4x4x2,        "Adder8x4x4x2"];

END.