<> <> <> <> <<>> <> <<>> DIRECTORY Core, CoreOps; MCEccImpl: CEDAR PROGRAM IMPORTS CoreOps = BEGIN <> <> <> <> <> <> <> <> <> Log2: PROC[n: CARDINAL] RETURNS[log: CARDINAL_0] = {FOR n _ n, n/2 WHILE n>1 DO log _ log+1 ENDLOOP}; MainTrees: PUBLIC PROC[n: CARDINAL] RETURNS[wire: Core.Wire] = { logn: CARDINAL _ Log2[n]; span: CARDINAL; groupSize: CARDINAL; input: Core.Wire _ NewWires[n, "in"]; out: Core.Wire _ NewWires[logn+1, "out"]; fullInLt: Core.Wire _ NewWires[n, "tl"]; fullInRt: Core.Wire _ NewWires[n, "tr"]; fullOut: Core.Wire _ NewWires[n, "tm"]; subInLt: Core.Wire _ NewWires[n, "bl"]; subInRt: Core.Wire _ NewWires[n, "br"]; subOut: Core.Wire _ NewWires[n, "bm"]; gnd: Core.Wire _ NewWires[0, "Gnd"]; wire _ CoreOps.CreateWire[LIST[input,out,fullInLt,fullInRt,fullOut,subInLt,subInRt,subOut]]; <> out[0] _ fullOut[n/2-1] _ NewWires[0]; span _ n/2; -- span of the two xor inputs (twice the length of a node wire) FOR level: CARDINAL IN [1..logn] DO FOR levelIdx: CARDINAL IN [0..n/(2*span)) DO phIdx: CARDINAL _ span-1 + levelIdx*2*span; IF span>1 THEN { fullInLt[phIdx] _ fullOut[phIdx-span/2] _ NewWires[0]; fullInRt[phIdx] _ fullOut[phIdx+span/2] _ NewWires[0]} ELSE { fullInLt[phIdx] _ input[phIdx] _ NewWires[0]; fullInRt[phIdx] _ input[phIdx+1] _ NewWires[0]}; ENDLOOP; span _ span/2; ENDLOOP; <> out[1] _ fullOut[n/4-1]; -- first subtree needs no XORs in subtree row groupSize _ n/4; FOR tree: CARDINAL IN [1..logn) DO span: CARDINAL _ n/2; out[tree+1] _ subOut[span-1 - groupSize] _ NewWires[0]; FOR span _ span, span/2 WHILE span>groupSize DO FOR levelIdx: CARDINAL IN [0..n/(2*span)) DO phIdx: CARDINAL _ span-1 - groupSize + levelIdx*2*span; IF span > 2*groupSize THEN { subInLt[phIdx] _ subOut[phIdx-span/2] _ NewWires[0]; subInRt[phIdx] _ subOut[phIdx+span/2] _ NewWires[0]} ELSE IF groupSize>1 THEN { subInLt[phIdx] _ fullOut[phIdx - groupSize/2]; subInRt[phIdx] _ fullOut[phIdx + groupSize + groupSize/2]} ELSE { subInLt[phIdx] _ input[phIdx]; subInRt[phIdx] _ input[phIdx+2]}; ENDLOOP; ENDLOOP; groupSize _ groupSize/2; ENDLOOP; FOR index: CARDINAL IN [0..n) DO IF fullInLt [index]=NIL THEN fullInLt [index] _ gnd; IF fullInRt [index]=NIL THEN fullInRt [index] _ gnd; IF fullOut [index]=NIL THEN fullOut [index] _ NewWires[0]; IF subInLt [index]=NIL THEN subInLt [index] _ gnd; IF subInRt [index]=NIL THEN subInRt [index] _ gnd; IF subOut [index]=NIL THEN subOut [index] _ NewWires[0]; ENDLOOP}; <> <> EvenIndex: PROC[i: CARDINAL] RETURNS[even: BOOL _ TRUE] = {FOR i _ i, i/2 WHILE i#0 DO even _ ((i MOD 2)=1)#even ENDLOOP}; EncodeParity: PUBLIC PROC[n: CARDINAL] RETURNS[wire: Core.Wire] = { logn: CARDINAL _ Log2[n]; span: CARDINAL; input: Core.Wire _ NewWires[n, "in"]; out: Core.Wire _ NewWires[0, "out"]; treeInLt: Core.Wire _ NewWires[n, "l"]; treeInRt: Core.Wire _ NewWires[n, "r"]; treeOut: Core.Wire _ NewWires[n, "m"]; gnd: Core.Wire _ NewWires[0, "Gnd"]; wire _ CoreOps.CreateWire[LIST[input,out,treeInLt,treeInRt,treeOut]]; out _ treeOut[n/2-1] _ NewWires[0]; span _ n/2; -- span of the two xor inputs (twice the length of a node wire) FOR level: CARDINAL IN [1..logn) DO FOR levelIdx: CARDINAL IN [0..n/(2*span)) DO phIdx: CARDINAL _ span-1 + levelIdx*2*span; IF span>2 THEN { treeInLt[phIdx] _ treeOut[phIdx-span/2] _ NewWires[0]; treeInRt[phIdx] _ treeOut[phIdx+span/2] _ NewWires[0]} ELSE { off: CARDINAL _ IF EvenIndex[2*n-1-phIdx] THEN 0 ELSE 1; treeInLt[phIdx] _ input[phIdx-off] _ NewWires[0]; treeInRt[phIdx] _ input[phIdx+off+1] _ NewWires[0]}; ENDLOOP; span _ span/2; ENDLOOP; FOR index: CARDINAL IN [0..n) DO IF treeInLt [index]=NIL THEN treeInLt [index] _ gnd; IF treeInRt [index]=NIL THEN treeInRt [index] _ gnd; IF treeOut [index]=NIL THEN treeOut [index] _ NewWires[0]; IF input [index]=NIL THEN input [index] _ NewWires[0]; ENDLOOP}; <> EncodeParity64x8: PUBLIC PROC RETURNS[wire: Core.Wire] = { wire _ EncodeParity64x8Heart[]; -- 64 data bits in high order of 72 bits FOR i: INT IN [0..wire.size) DO IF wire[i].size=72 THEN { w: Core.Wire _ CoreOps.CreateWires[72, CoreOps.GetShortWireName[wire[i]]]; FOR j: INT IN [0..72) DO w[j] _ wire[i][(j+64) MOD 72] ENDLOOP; wire[i] _ w}; ENDLOOP}; Nm: PROC[pre: Core.ROPE, i: CARDINAL] RETURNS[name: Core.ROPE] = {RETURN[NIL]}; <> <<{RETURN[IO.PutFR["%g%g", IO.rope[pre], IO.int[i]]]};>> EncodeParity64x8Heart: PUBLIC PROC RETURNS[wire: Core.Wire] = { n: CARDINAL _ 64; logn: CARDINAL _ 6; m: CARDINAL _ 8; span: CARDINAL; input: Core.Wire _ NewWires[n+m, "in"]; out: Core.Wire _ NewWires[0, "out"]; treeInLt: Core.Wire _ NewWires[n+m, "l"]; treeInRt: Core.Wire _ NewWires[n+m, "r"]; treeOut: Core.Wire _ NewWires[n+m, "m"]; gnd: Core.Wire _ NewWires[0, "Gnd"]; wire _ CoreOps.CreateWire[LIST[input,out,treeInLt,treeInRt,treeOut]]; treeOut[n/2-1] _ out; span _ n/2; -- span of the two xor inputs (twice the length of a node wire) FOR level: CARDINAL IN [1..logn) DO FOR levelIdx: CARDINAL IN [0..n/(2*span)) DO phIdx: CARDINAL _ span-1 + levelIdx*2*span; IF span>2 THEN { treeInLt[phIdx] _ treeOut[phIdx-span/2] _ NewWires[0, Nm["T",phIdx-span/2]]; treeInRt[phIdx] _ treeOut[phIdx+span/2] _ NewWires[0, Nm["T",phIdx+span/2]]} ELSE { off: CARDINAL _ IF EvenIndex[2*n-1-phIdx] THEN 0 ELSE 1; treeInLt[phIdx] _ input[phIdx-off] _ NewWires[0, Nm["I",phIdx-off]]; treeInRt[phIdx] _ input[phIdx+off+1] _ NewWires[0, Nm["I",phIdx+off+1]]}; ENDLOOP; span _ span/2; ENDLOOP; FOR index: CARDINAL IN [0..n+m) DO IF treeInLt [index]=NIL THEN treeInLt [index] _ gnd; IF treeInRt [index]=NIL THEN treeInRt [index] _ gnd; IF treeOut [index]=NIL THEN treeOut [index] _ NewWires[0, Nm["t",index]]; IF input [index]=NIL THEN input [index] _ NewWires[0, Nm ["i",index]]; ENDLOOP}; <<>> <> ExtendedMainTrees64x8: PUBLIC PROC RETURNS[wire: Core.Wire] = { wire _ ExtendedMainTrees64x8Heart[]; -- 64 data bits in high order of 72 bits FOR i: INT IN [0..wire.size) DO IF wire[i].size=72 THEN { w: Core.Wire _ CoreOps.CreateWires[72, CoreOps.GetShortWireName[wire[i]]]; FOR j: INT IN [0..72) DO w[j] _ wire[i][(j+64) MOD 72] ENDLOOP; wire[i] _ w}; ENDLOOP}; <> <> ExtendedMainTrees64x8Heart: PUBLIC PROC RETURNS[wire: Core.Wire] = { n: CARDINAL _ 64; logn: CARDINAL _ 6; m: CARDINAL _ 8; logm: CARDINAL _ 3; span: CARDINAL; groupSize: CARDINAL; input: Core.Wire _ NewWires[n+m, "in"]; out: Core.Wire _ NewWires[m-1, "out"]; dp: Core.Wire _ NewWires[0, "dp"]; fullInLt: Core.Wire _ NewWires[n+m, "tl"]; fullInRt: Core.Wire _ NewWires[n+m, "tr"]; fullOut: Core.Wire _ NewWires[n+m, "tm"]; subInLt: Core.Wire _ NewWires[n+m, "bl"]; subInRt: Core.Wire _ NewWires[n+m, "br"]; subOut: Core.Wire _ NewWires[n+m, "bm"]; gnd: Core.Wire _ NewWires[0, "Gnd"]; wire _ CoreOps.CreateWire [LIST[input,out, dp,fullInLt,fullInRt,fullOut,subInLt,subInRt,subOut]]; <> span _ n/2; -- span of the two xor inputs (twice the length of a node wire) FOR level: CARDINAL IN [1..logn] DO FOR levelIdx: CARDINAL IN [0..n/(2*span)) DO phIdx: CARDINAL _ span-1 + levelIdx*2*span; IF span>1 THEN { fullInLt[phIdx] _ fullOut[phIdx-span/2] _ NewWires[0, Nm["F",phIdx-span/2]]; fullInRt[phIdx] _ fullOut[phIdx+span/2] _ NewWires[0, Nm["F",phIdx+span/2]]} ELSE { last1: CARDINAL _ IF phIdx=n-2 THEN 1 ELSE 0; fullInLt[phIdx] _ input[phIdx] _ NewWires[0, Nm["I",phIdx]]; fullInRt[phIdx] _ input[phIdx+1+last1] _ NewWires[0, Nm["I",phIdx+1+last1]]}; ENDLOOP; span _ span/2; ENDLOOP; <> span _ m/2; FOR level: CARDINAL IN [1..logm] DO FOR levelIdx: CARDINAL IN [0..m/(2*span)) DO phIdx: CARDINAL _ n + span-1 + levelIdx*2*span; IF span>1 THEN { fullInLt[phIdx] _ fullOut[phIdx-span/2] _ NewWires[0, Nm["F",phIdx-span/2]]; fullInRt[phIdx] _ fullOut[phIdx+span/2] _ NewWires[0, Nm["F",phIdx+span/2]]} ELSE { first1: CARDINAL _ IF phIdx=n THEN 1 ELSE 0; fullInLt[phIdx] _ input[phIdx-first1] _ NewWires[0, Nm["I",phIdx-first1]]; fullInRt[phIdx] _ input[phIdx+1] _ NewWires[0, Nm["I",phIdx+1]]}; ENDLOOP; span _ span/2; ENDLOOP; <> fullOut[n + m/2-1] _ dp; -- Decode Parity <> subInLt[n+0] _ input[n-1]; subInRt[n+0] _ input[n+0+1]; -- unique bit index = 62 subInLt[n+1] _ input[n-1]; subInRt[n+1] _ input[n+1+1]; subInLt[n+2] _ input[n-1]; subInRt[n+2] _ input[n+2+1]; subInLt[n+3] _ input[n-1]; subInRt[n+3] _ input[n+3+1]; subInLt[n+4] _ input[n-1]; subInRt[n+4] _ input[n+4+1]; subInLt[n+5] _ gnd; subInRt[n+5] _ input[n+5+1]; out[0] _ fullOut[n/2-1] _ NewWires[0, Nm["O",0]]; -- 64 needs no XORs in subtree row groupSize _ n/2; FOR tree: CARDINAL IN [1..logn] DO out[tree] _ subOut[n-1 - groupSize] _ NewWires[0, Nm["O",tree]]; FOR span: CARDINAL _ n, span/2 WHILE span>groupSize DO IF span = n -- top, right arg in special location THEN { phIdx: CARDINAL _ n-1-groupSize; IF span > 2*groupSize THEN{ -- groupSize<32 subInLt[phIdx] _ subOut[phIdx-n/2] _ NewWires[0, Nm["S",phIdx-span/2]]; subInRt[phIdx] _ subOut[n-1 + tree] _ NewWires[0, Nm["S",n-1 + tree]]} ELSE { -- groupSize=32 subInLt[phIdx] _ fullOut[phIdx - groupSize/2]; subInRt[phIdx] _ subOut[n-1 + tree] _ NewWires[0, Nm["S",n-1 + tree]]} } ELSE FOR levelIdx: CARDINAL IN [0..n/(2*span)) DO phIdx: CARDINAL _ span-1 - groupSize + levelIdx*2*span; IF span > 2*groupSize THEN { subInLt[phIdx] _ subOut[phIdx-span/2] _ NewWires[0, Nm["S",phIdx-span/2]]; subInRt[phIdx] _ subOut[phIdx+span/2] _ NewWires[0, Nm["S",phIdx+span/2]]} ELSE IF groupSize>1 THEN { subInLt[phIdx] _ fullOut[phIdx - groupSize/2]; subInRt[phIdx] _ fullOut[phIdx + groupSize + groupSize/2]} ELSE { subInLt[phIdx] _ input[phIdx]; subInRt[phIdx] _ input[phIdx+2]}; ENDLOOP; ENDLOOP; groupSize _ groupSize/2; ENDLOOP; FOR index: CARDINAL IN [0..n+m) DO IF fullInLt [index]=NIL THEN fullInLt [index] _ gnd; IF fullInRt [index]=NIL THEN fullInRt [index] _ gnd; IF fullOut [index]=NIL THEN fullOut [index] _ NewWires[0, Nm["f",index]]; IF subInLt [index]=NIL THEN subInLt [index] _ gnd; IF subInRt [index]=NIL THEN subInRt [index] _ gnd; IF subOut [index]=NIL THEN subOut [index] _ NewWires[0, Nm["s",index]]; ENDLOOP}; NewWires: PROC[n: INT _ 0, name: Core.ROPE _ NIL] RETURNS[wire: Core.Wire] = {RETURN[CoreOps.CreateWires[n, name]]}; END.