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] ~ {
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)
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];
};
PROC no longer returns numCycles
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;
The least significant 2 bits are special
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];