DIRECTORY Basics USING [DoubleShiftRight], TamarinBlocks, TamarinOps USING [FourBitIndex, FiveBitIndex, OnesWord, SixBitIndex, Word, ZerosWord], TamarinOpsUtils USING [CardToWord, DoubleWordShiftLeft, IntToWord, SingleWordShiftLeft, TamAnd, TamNot, TamOr, TamXor, WordToCard, WordToInt]; TamarinBlocksImpl: CEDAR PROGRAM IMPORTS Basics, TamarinOpsUtils EXPORTS TamarinBlocks = BEGIN OPEN TamarinOps, TamarinOpsUtils; onesInByte: ARRAY [0..256) OF [0..8] = [ 0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4, 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7, 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7, 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7, 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7, 4, 5, 5, 6, 5, 6, 6, 7, 5, 6, 6, 7, 6, 7, 7, 8]; priorityOfByte: ARRAY [0..256) OF INT = [-1, 0, 1, 1, 2, 2, 2, 2, 3, 3, 3, 3, 3, 3, 3, 3, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7]; Signs: TYPE = MACHINE DEPENDENT { a0b0c0 (0), a0b0c1 (1), a0b1c0 (2), a0b1c1 (3), a1b0c0 (4), a1b0c1 (5), a1b1c0 (6), a1b1c1 (7)}; luOp: TYPE = MACHINE DEPENDENT { tAND (1), tXOR (6), tOR (7), tNOR (8), tNAND (14)}; adderOp: TYPE = MACHINE DEPENDENT { tADD (0), tADDC (1), tSUB (8), tSUBC (9)}; ALUHelper: PROC [a,b,c: BOOL] RETURNS [Signs] = INLINE { RETURN [LOOPHOLE[ 4*LOOPHOLE[a, CARDINAL] + 2*LOOPHOLE[b, CARDINAL] + LOOPHOLE[c, CARDINAL]]]; }; WordCarryAdd: PROC [wordA, wordB: Word, carryIn: BOOL] RETURNS [wordC: Word, carryOut: BOOL _ FALSE] = { cardA: CARD _ WordToCard[wordA]; cardB: CARD _ WordToCard[wordB]; cardC: CARD _ cardA+cardB; SELECT cardC FROM < cardA, < cardB => carryOut _ TRUE; ENDCASE; IF carryIn THEN {cardC _ cardC+1; IF cardC = 0 THEN carryOut _ TRUE}; wordC _ CardToWord[cardC]; }; Adder: PUBLIC PROC [euOp: FourBitIndex, d1, d2: Word] RETURNS [result: Word, overFlow, carry, gt: BOOL] ~ { carryIn: BOOL _ ((LOOPHOLE[euOp, adderOp] = tADDC) OR (LOOPHOLE[euOp, adderOp] = tSUBC)); in1: Word _ d1; IF ((LOOPHOLE[euOp, adderOp] = tSUB) OR (LOOPHOLE[euOp, adderOp] = tSUBC)) THEN in1 _ TamXor[d1, OnesWord]; [result, carry] _ WordCarryAdd[in1, d2, carryIn]; SELECT ALUHelper[in1[0], d2[0], result[0]] FROM a0b0c1, a1b1c0 => overFlow _ TRUE; ENDCASE; gt _ IF in1[0] # d2[0] THEN carry ELSE d1[0]; RETURN [result, overFlow, carry, gt] }; Shifter: PUBLIC PROC [top, bot: Word, shiftAmount: SixBitIndex] RETURNS [shifterResult: Word] ~ { shifterResult _ DoubleWordShiftLeft[top, bot, shiftAmount]; RETURN [shifterResult]; }; PriorityEncoder: PUBLIC PROC [inword: Word] RETURNS [result: Word] ~ { inNum: INT _ WordToInt[inword]; bytePriority: INT; i: NAT _ 3; zeroByte: BOOL; bytePriority _ priorityOfByte[Basics.DoubleShiftRight[[li[inNum]], 8*i].li]; zeroByte _ bytePriority = -1; THROUGH [0..2] WHILE zeroByte DO i _ i -1; bytePriority _ priorityOfByte[Basics.DoubleShiftRight[[li[inNum]], 8*i].li]; zeroByte _ bytePriority = -1; ENDLOOP; IF (bytePriority # -1) THEN RETURN [IntToWord[bytePriority + 8*i]] ELSE RETURN [IntToWord[32]]; }; LUOpNotImplemented: SIGNAL [euOp: FourBitIndex] = CODE; LogicalUnit: PUBLIC PROC [euOp: FourBitIndex, d1, d2: Word] RETURNS [result: Word] ~ { SELECT LOOPHOLE[euOp, luOp] FROM tAND => result _ TamAnd[d1, d2]; tXOR => result _ TamXor[d1, d2]; tOR => result _ TamOr[d1, d2]; tNOR => result _ TamNot[TamOr[d1, d2]]; tNAND => result _ TamNot[TamAnd[d1, d2]]; ENDCASE => SIGNAL LUOpNotImplemented[euOp]; RETURN [result]; }; Multiplier: PUBLIC PROC [d1, d2: Word, sgnd: BOOL _ TRUE] RETURNS [resultH, resultL: Word] ~ { numCycles0, numCycles1: NAT; BoothVal: TYPE = {zero, X1, Xminus1, X2, Xminus2}; BoothValArray: TYPE = ARRAY [0..8) OF BoothVal; BoothRec: TYPE = RECORD [ pos: NAT, val: BoothVal]; BoothArray: TYPE = ARRAY [0..16) OF BoothRec; bArray: BoothArray; pos: NAT; val: BoothVal; shiftRL: Word; shiftRH: Word; carry: BOOL; MultShifter: PROC [word: Word, shft: SixBitIndex] RETURNS [resL, resR: Word] ~ { resR _ SingleWordShiftLeft[word, shft]; resL _ DoubleWordShiftLeft[ZerosWord, word, shft]; RETURN [resL, resR]; }; Booth: PROC [word: Word] RETURNS [bArray: BoothArray, numCycles0, numCycles1: NAT] ~ { bva: BoothValArray = [zero, X1, X1, X2, Xminus2, Xminus1, Xminus1, zero]; bv: BoothVal; boothIndex: NAT; wordIndex: NAT _ 32; i: NAT _ 0; numCycles0 _ 0; numCycles1 _ 0; boothIndex _ 4*LOOPHOLE[word[wordIndex-2], NAT] + 2*LOOPHOLE[word[wordIndex-1], NAT]; bv _ bva[boothIndex]; IF bv # zero THEN numCycles1 _ 1; bArray[i] _ [wordIndex, bv]; i _ i+1; WHILE wordIndex >= 4 DO wordIndex _ wordIndex -2; boothIndex _ 4*LOOPHOLE[word[wordIndex-2], NAT] + 2*LOOPHOLE[word[wordIndex-1], NAT] + LOOPHOLE[word[wordIndex], NAT]; bv _ bva[boothIndex]; IF bv # zero THEN IF (wordIndex MOD 4 = 0) THEN numCycles1 _ numCycles1 + 1 ELSE numCycles0 _ numCycles0 + 1; bArray[i] _ [wordIndex, bv]; i _ i+1; ENDLOOP; RETURN [bArray, numCycles0, numCycles1]; }; resultH _ resultL _ ZerosWord; IF ~sgnd THEN resultH _ d2; [bArray, numCycles0, numCycles1] _ Booth[d1]; FOR i: INT IN [0..16) DO [pos, val] _ bArray[i]; SELECT val FROM zero => NULL; X1 => { [shiftRH, shiftRL] _ MultShifter[d2, 32-pos]; [resultL, carry] _ WordCarryAdd[resultL, shiftRL, FALSE]; [resultH, carry] _ WordCarryAdd[resultH, shiftRH, carry]; }; Xminus1 => { [shiftRH, shiftRL] _ MultShifter[d2, 32-pos]; shiftRH _ TamNot[shiftRH]; shiftRL _ TamNot[shiftRL]; [resultL, carry] _ WordCarryAdd[resultL, shiftRL, TRUE]; [resultH, carry] _ WordCarryAdd[resultH, shiftRH, carry]; }; X2 => { [shiftRH, shiftRL] _ MultShifter[d2, 32-pos+1]; [resultL, carry] _ WordCarryAdd[resultL, shiftRL, FALSE]; [resultH, carry] _ WordCarryAdd[resultH, shiftRH, carry]; }; Xminus2 => { [shiftRH, shiftRL] _ MultShifter[d2, 32-pos+1]; shiftRH _ TamNot[shiftRH]; shiftRL _ TamNot[shiftRL]; [resultL, carry] _ WordCarryAdd[resultL, shiftRL, TRUE]; [resultH, carry] _ WordCarryAdd[resultH, shiftRH, carry]; }; ENDCASE => ERROR; ENDLOOP; RETURN [resultH, resultL]; }; END. ΤTamarinBlocksImpl.mesa Copyright Σ 1987 by Xerox Corporation. All rights reserved. December 31, 1986 3:40:14 pm PST Last Edited by: Ross March 4, 1987 9:31:58 am PST Performs the add function based on euOp. The various operations are defined below: 0 => add no carry (d1 + d2) 1 => add with carry (d1 + d2 + 1) 8 => sub no carry (NOT(d1) + d2) 9 => sub with carry (NOT(d1) + d2 + 1) PROC no longer returns numCycles The least significant 2 bits are special Κc˜™Icode™K˜——Kšœ'˜'Kšœ˜—Kšœ"˜(K˜K˜—K˜Kšœœ˜Kšœ-˜-K˜šœœœ ˜K˜šœœ˜Kšœœ˜ ˜K˜-Kšœ2œ˜9K˜9K˜—˜ K˜-K˜K˜Kšœ2œ˜8K˜9K˜—˜K˜/Kšœ2œ˜9K˜9K˜—˜ K˜/K˜K˜Kšœ2œ˜8K˜9K˜—Kšœœ˜—Kšœ˜—K˜Kšœ˜˜K˜——šœ˜K˜———…—ΰ)