GenField.mesa
Copyright © 1986 by Xerox Corporation. All rights reserved.
Russ Atkinson (RRA) June 1, 1987 8:38:06 pm PDT
DIRECTORY
DragOpsCross,
DragOpsCrossUtils,
HandCoding,
HandCodingPseudos,
HandCodingSupport;
GenField: CEDAR PROGRAM
IMPORTS DragOpsCrossUtils, HandCoding, HandCodingPseudos, HandCodingSupport
= BEGIN OPEN DragOpsCrossUtils, HandCoding, HandCodingPseudos, HandCodingSupport;
Word: TYPE = DragOpsCross.Word;
ZerosWord: Word = DragOpsCross.ZerosWord;
All: PROC = {
area: Area = GetCurrentArea[];
startNext: Label = GenLabel[];
drJDB[UseLabel16[startNext]];
GenTextFetch[];
GenByteFetchUnchecked[];
GenBytePtrFetch[];
GenTextStore[];
GenByteStoreUnchecked[];
GenBytePtrStore[];
GenExtractField[];
GenExtractFieldSingle[];
GenDepositField[];
GenDepositFieldSingle[];
GenStringCompare[];
WordAlign[area];
SetLabel[startNext];
Control flow falls through to the next file that gets generated.
MakeLabelGlobal["GenField.startNext", startNext];
};
Byte Fetch and Store routines
GenTextFetch: PROC = {
(if open coded: 10 instructions, 10 cycles min)
rR: RegSpec = reg0;
rI: RegSpec = reg1;
entryLabel: Label = GenLabel[];
ProcedureEntry[entryLabel, 2];
MakeLabelGlobal["Basics.TextFetch", entryLabel];
drLRIn[rR, 1];
push the bound (at (rR+1)^)
drLRn[rI];
drSHR[DragOpsCrossUtils.FieldDescriptorToCard[[mask: 30, shift: 30]]];
drRADD[rR, rR, popSrc];
drRRI[rR, rR, 2];
read the word containing the byte
rR ← (rR + (rI / 4))^
drSHR[DragOpsCrossUtils.FieldDescriptorToCard[[mask: 16, shift: 0]]];
isolate the bound (in the right half of [S])
drBC[];
bounds check [S-1] (which is rI) against [S] (which is the bound)
drSHL[DragOpsCrossUtils.FieldDescriptorToCard[[mask: 5, shift: 3]]];
make it into a byte index ([S] = (rI * 8) MOD 32)
drFSDB[DragOpsCrossUtils.FieldDescriptorToCard[[mask: 8, shift: 8]]];
setup Field ← FD[0, 8, 8]+[S]; S←S-1
drRFU[rR, const0, rR];
isolate the byte (into the return value)
ProcedureExit[1];
};
GenByteFetchUnchecked: PROC = {
(if open coded: 6 instructions, 6 cycles min)
rR: RegSpec = reg0;
rI: RegSpec = reg1;
entryLabel: Label = GenLabel[];
ProcedureEntry[entryLabel, 2];
MakeLabelGlobal["Basics.ByteFetchUnchecked", entryLabel];
drDUP[];
push the index (rI)
drSHR[DragOpsCrossUtils.FieldDescriptorToCard[[mask: 30, shift: 30]]];
make the index a word index (rI←rI/4; [S] = rI) {overwrites rI}
drRRX[rR, rR, popSrc];
fetch the word into rR (no overhead words)
drSHL[DragOpsCrossUtils.FieldDescriptorToCard[[mask: 5, shift: 3]]];
make rI into a byte index ([S] = (rI * 8) MOD 32)
drFSDB[DragOpsCrossUtils.FieldDescriptorToCard[[mask: 8, shift: 8]]];
setup Field ← FD[0, 8, 8]+[S]; S←S-1
drRFU[rR, const0, rR];
isolate the byte (into the return value)
ProcedureExit[1];
};
GenBytePtrFetch: PROC = {
(if open coded: 6 instructions, 7 cycles min)
rBA: RegSpec = reg0;
entryLabel: Label = GenLabel[];
ProcedureEntry[entryLabel, 1];
MakeLabelGlobal["Basics.BytePtrFetch", entryLabel];
drDUP[];
byte addr in [S], [S-1]
drSHL[DragOpsCrossUtils.FieldDescriptorToCard[[mask: 5, shift: 3]]];
make it into a byte index ([S] = (rI * 8) MOD 32)
drFSDB[DragOpsCrossUtils.FieldDescriptorToCard[[mask: 8, shift: 8]]];
setup Field ← FD[0, 8, 8]+[S]; S←S-1
drSHR[DragOpsCrossUtils.FieldDescriptorToCard[[mask: 30, shift: 30]]];
drRB[0];
fetch the word (no overhead)
drRFU[rBA, const0, popSrc];
isolate the byte (into the return value)
ProcedureExit[1];
};
GenTextStore: PROC = {
(if open coded: 12 instructions, 13 cycles min)
rR: RegSpec = reg0;
rI: RegSpec = reg1;
rB: RegSpec = reg2;
entryLabel: Label = GenLabel[];
ProcedureEntry[entryLabel, 3];
MakeLabelGlobal["Basics.TextStore", entryLabel];
drLRIn[rR, 1];
push the bound
drRVSUB[pushDst, const3, rI];
push 3 - i
drSHL[DragOpsCrossUtils.FieldDescriptorToCard[[mask: 5, shift: 3]]];
make it into a byte index ([S] = ((3-i) * 8) MOD 32)
drSHR[DragOpsCrossUtils.FieldDescriptorToCard[[insert: TRUE, mask: 12, shift: 6]]];
[S] ← [S] + [S]*64
drFSDB[DragOpsCrossUtils.FieldDescriptorToCard[[insert: TRUE, mask: 8, shift: 0]]];
setup Field ← FD[1, 8, 0]+[S]; S←S-1
drSHR[DragOpsCrossUtils.FieldDescriptorToCard[[mask: 16, shift: 0]]];
isolate the bound (in the right half of [S])
drRBC[topDst, rI, topSrc];
bounds check rI against [S] (the bound), leaving rI in [S]
drSHR[DragOpsCrossUtils.FieldDescriptorToCard[[mask: 30, shift: 30]]];
make the index a word index ([S] = rI / 4)
drQADD[topAtop, rR];
add in the base address
drRSB[2];
fetch the word (2 words of overhead)
drRFU[topDst, rB, topSrc];
insert the byte
drWSB[2];
store the changed word
ProcedureExit[0];
};
GenByteStoreUnchecked: PROC = {
(if open coded: 9 instructions, 9 cycles min)
rB: RegSpec = reg0; -- the byte (B: BYTE)
rP: RegSpec = reg1; -- the base pointer (P: LONG POINTER)
rI: RegSpec = reg2; -- the byte index (I: INT)
entryLabel: Label = GenLabel[];
ProcedureEntry[entryLabel, 3];
MakeLabelGlobal["Basics.ByteStoreUnchecked", entryLabel];
drRVSUB[pushDst, const3, rI];
push (3-I)
drSHL[DragOpsCrossUtils.FieldDescriptorToCard[[mask: 5, shift: 3]]];
make it into a byte index ([S] = ((3-P) * 8) MOD 32)
drSHR[DragOpsCrossUtils.FieldDescriptorToCard[[insert: TRUE, mask: 12, shift: 6]]];
[S] ← [S] + [S]*64
drFSDB[DragOpsCrossUtils.FieldDescriptorToCard[[insert: TRUE, mask: 8, shift: 0]]];
setup Field ← FD[1, 8, 0]+[S]; S←S-1
drSHR[DragOpsCrossUtils.FieldDescriptorToCard[[mask: 30, shift: 30]]];
make the index a word index ([S] = rI / 4)
drRRX[pushDst, topSrc, rP];
fetch the word (no overhead)
drRVADD[belowDst, belowSrc, rP];
adjust the dest address in the dead cycle
drRFU[topDst, rB, topSrc];
insert the byte
drWSB[0];
store the changed word
ProcedureExit[0];
};
GenBytePtrStore: PROC = {
(if open coded: 8 instructions, 9 cycles min)
rC: RegSpec = reg0;
rP: RegSpec = reg1;
entryLabel: Label = GenLabel[];
ProcedureEntry[entryLabel, 2];
MakeLabelGlobal["Basics.BytePtrStore", entryLabel];
drRVSUB[pushDst, const3, rP];
push (3-P)
drSHL[DragOpsCrossUtils.FieldDescriptorToCard[[mask: 5, shift: 3]]];
make it into a byte index ([S] = ((3-P) * 8) MOD 32)
drSHR[DragOpsCrossUtils.FieldDescriptorToCard[[insert: TRUE, mask: 12, shift: 6]]];
[S] ← [S] + [S]*64
drFSDB[DragOpsCrossUtils.FieldDescriptorToCard[[insert: TRUE, mask: 8, shift: 0]]];
setup Field ← FD[1, 8, 0]+[S]; S←S-1
drSHR[DragOpsCrossUtils.FieldDescriptorToCard[[mask: 30, shift: 30]]];
make the index a word index ([S] = rI / 4)
drRSB[0];
fetch the word (2 words of overhead)
drRFU[topDst, rC, topSrc];
insert the byte
drWSB[0];
store the changed word
ProcedureExit[0];
};
Field Extract & Deposit routines
In these routines a bit field is described by (P, I, B), where P is a word pointer, I is a bit index (unsigned), and B is a number of bits (in [0..32], but unchecked). We follow the convention that bit 0 is the most-significant bit in a binary number (aka Big-Endian). In the general case fields are allowed to cross word boundaries, in the single case fields must stay within a word.
GenExtractField: PROC = {
(if open coded: 13 instructions, 14 cycles min)
Arguments
rP: RegSpec = reg0; -- the base pointer
rI: RegSpec = reg1; -- the offset (in bits)
rB: RegSpec = reg2; -- the field size [0..32]
Locals
rBI: RegSpec = reg3; -- B+I
entryLabel: Label = GenLabel[];
ProcedureEntry[entryLabel, 3];
MakeLabelGlobal["Basics.ExtractField", entryLabel];
drRVADD[pushDst, rI, rB]; -- BI: WORD ← B+I
drLRn[rB];
drLRn[rBI];
drSHL[DragOpsCrossUtils.FieldDescriptorToCard[[mask: 5, shift: 0]]];
[S] = (B+I) MOD 32 {the # of bits to shift left}
drSHDL[DragOpsCrossUtils.FieldDescriptorToCard[[insert: TRUE, mask: 6+6, shift: 6]]];
drFSDB[0];
setup the field descriptor (no constant part, unfortunately)
FD = [mask: B, shift: (B+I) MOD 32]
drRVSUB[pushDst, rBI, const1];
[S] = B+I-1 {to give offset of rightmost bit}
drSHR[DragOpsCrossUtils.FieldDescriptorToCard[[mask: 32-5, shift: 32-5]]];
drQRX[topAtop, rP];
[S] = right word
drLRn[rI];
[S] = B {to give offset of leftmost bit}
drSHR[DragOpsCrossUtils.FieldDescriptorToCard[[mask: 32-5, shift: 32-5]]];
drQRX[topAtop, rP];
[S] = left word, [S-1] = right word
drRFU[reg0, topSrc, belowSrc];
Extract the field & put it into the return reg
ProcedureExit[1];
};
GenExtractFieldSingle: PROC = {
(if open coded: 7 instructions, 8 cycles min)
rP: RegSpec = reg0; -- the base pointer
rI: RegSpec = reg1; -- the offset (in bits)
rB: RegSpec = reg2; -- the field size [0..32]
entryLabel: Label = GenLabel[];
ProcedureEntry[entryLabel, 3];
MakeLabelGlobal["Basics.ExtractFieldSingle", entryLabel];
drRVADD[pushDst, rI, rB];
drSHL[DragOpsCrossUtils.FieldDescriptorToCard[[mask: 5, shift: 0]]];
[S] = (B+I) MOD 32 {the # of bits to shift left}
drSHDL[DragOpsCrossUtils.FieldDescriptorToCard[[insert: TRUE, mask: 6+6, shift: 6]]];
drFSDB[0];
setup the field descriptor (no constant part, unfortunately)
FD = [mask: B, shift: (B+I) MOD 32]
drSHR[DragOpsCrossUtils.FieldDescriptorToCard[[mask: 32-5, shift: 32-5]]];
[S] = (I / 32) {to give offset of lst bit}
drRX[];
[S] = word containing field
drRFU[reg0, topSrc, topSrc];
Extract the field & put it into the return reg
ProcedureExit[1];
};
GenDepositField: PROC = {
(if open coded (with plenty of spare regs):
single word => 16 instructions, 21 cycles min,
double word => 26 instructions, 27 cycles min)
Arguments
rP: RegSpec = reg0; -- the base pointer
rI: RegSpec = reg1; -- the offset (in bits)
rB: RegSpec = reg2; -- the field size [0..32]
rF: RegSpec = reg3; -- the field to insert
Locals
c32: RegSpec = reg4; -- 32
rBI: RegSpec = reg5; -- B+I
rSH: RegSpec = reg6; -- 31&(-B-I) {bits to shift left}
rMSK: RegSpec = reg7; -- SH+B {bits to mask}
entryLabel: Label = GenLabel[];
exitLabel: Label = GenLabel[];
ProcedureEntry[entryLabel, 4];
MakeLabelGlobal["Basics.DepositField", entryLabel];
drLIB[32];
c32: WORD ← 32
drRVADD[pushDst, rI, rB];
BI: WORD ← B+I
drRVSUB[pushDst, const0, rBI];
drSHL[DragOpsCrossUtils.FieldDescriptorToCard[[mask: 5, shift: 0]]];
SH: WORD = (-B-I) MOD 32
drRVADD[pushDst, rSH, rB];
MSK: WORD = SH+B
{
This part stores the right part of the field, which is the only part for single-word stores.
drLRn[rMSK];
drLRn[rSH];
[S] = SH
[S-1] = MSK
drSHDL[DragOpsCrossUtils.FieldDescriptorToCard[[insert: TRUE, mask: 6+6, shift: 6]]];
[S] holds the new field descriptor (without the insert bit)
= FD[insert: FALSE, mask: MSK, shift: SH]
drFSDB[DragOpsCrossUtils.FieldDescriptorToCard[[insert: TRUE, mask: 0, shift: 0]]];
setup the field descriptor (with the insert bit)
= FD[insert: TRUE, mask: MSK, shift: SH]
drRVSUB[pushDst, rBI, const1];
drSHR[DragOpsCrossUtils.FieldDescriptorToCard[[mask: 32-5, shift: 32-5]]];
drRVADD[rP, popSrc, rP];
form the address of the word to modify
drLRIn[rP, 0];
Fetch the word to modify
drRFU[topDst, rF, topSrc];
Insert the field
drSRIn[rP, 0];
Store the modified word back
drRJLEB[topSrc, c32, UseLabel8B[exitLabel]];
IF MSK <= 32 THEN GO TO exitLabel;
};
At this point the right part has been done, so we try to do the left part
drLRn[rSH];
drFSDB[DragOpsCrossUtils.FieldDescriptorToCard[[insert: FALSE, mask: 32, shift: 0]]];
setup the field descriptor to shift F right
drRVSUB[pushDst, rMSK, c32];
drSHL[DragOpsCrossUtils.FieldDescriptorToCard[[insert: FALSE, mask: 6+6, shift: 6]]];
[S] holds the new field descriptor (without the insert bit)
= FD[insert: FALSE, mask: MSK-32, shift: 0]
drRFU[rF, const0, rF];
Shift the field to get the remainder
drFSDB[DragOpsCrossUtils.FieldDescriptorToCard[[insert: TRUE, mask: 0, shift: 0]]];
setup the field descriptor to insert the remaining F
= FD[insert: TRUE, mask: MSK-32, shift: 0]
drRRX[pushDst, rP, constN1];
Fetch the word to modify
drRVSUB[rP, rP, const1];
Adjust rP while twiddling our thumbs
drRFU[topDst, rF, topSrc];
Insert the field
drSRIn[rP, 0];
Store the modified word back
SetLabel[exitLabel];
ProcedureExit[0];
};
GenDepositFieldSingle: PROC = {
DepositFieldSingle: PROC [P: PTR, I: WORD, B: [0..32], F: WORD]
deposits F into the field described by (P, I, B)
(the caller promises to not cross a word boundary)
(if open coded: 12 instructions, 13 cycles min)
Arguments
rP: RegSpec = reg0; -- the base pointer
rI: RegSpec = reg1; -- the offset (in bits)
rB: RegSpec = reg2; -- the field size [0..32]
rF: RegSpec = reg3; -- the field to insert
Locals
rBI: RegSpec = reg4; -- B+I
rSH: RegSpec = reg5; -- 31&(-B-I) {bits to shift left}
rMSK: RegSpec = reg6; -- SH+B {bits to mask}
entryLabel: Label = GenLabel[];
ProcedureEntry[entryLabel, 4];
MakeLabelGlobal["Basics.DepositFieldSingle", entryLabel];
drRVADD[pushDst, rI, rB];
BI: WORD ← B+I
drRVSUB[pushDst, const0, rBI];
drSHL[DragOpsCrossUtils.FieldDescriptorToCard[[mask: 5, shift: 0]]];
SH: WORD = (-B-I) MOD 32
drRVADD[pushDst, rSH, rB];
MSK: WORD = SH+B
[S] = MSK
[S-1] = SH
drSHDR[DragOpsCrossUtils.FieldDescriptorToCard[[insert: TRUE, mask: 6+6, shift: 6]]];
[S] holds the new field descriptor (without the insert bit)
= FD[insert: FALSE, mask: MSK, shift: SH]
drFSDB[DragOpsCrossUtils.FieldDescriptorToCard[[insert: TRUE, mask: 0, shift: 0]]];
setup the field descriptor (with the insert bit)
= FD[insert: TRUE, mask: MSK, shift: SH]
drLRn[rI];
drSHR[DragOpsCrossUtils.FieldDescriptorToCard[[mask: 32-5, shift: 32-5]]];
drRVADD[rP, popSrc, rP];
form the address of the word to modify
drLRIn[rP, 0];
Fetch the word to modify
drRFU[topDst, rF, topSrc];
Insert the field
drSRIn[rP, 0];
Store the modified word back
ProcedureExit[0];
};
GenStringCompare: PROC = {
Arguments
rS1: RegSpec = reg0; -- string S1
rS2: RegSpec = reg1; -- string S2
Locals
rDelta: RegSpec = reg2; -- rW2-rW1
rL1: RegSpec = reg3; -- L1 ← S1.len
rL2: RegSpec = reg4; -- L2 ← S2.len
rMin: RegSpec = reg5; -- rMin ← MIN[L1, L2]
rDiv: RegSpec = reg6; -- rDiv ← rMin / 4
rMod: RegSpec = reg7; -- rMod ← rMin MOD 4
rW1: RegSpec = reg8; -- last word from S1
rW2: RegSpec = reg9; -- last word from S2
rRel: RegSpec = reg10; -- rRel ← 1
Labels
minFound: Label = GenLabel[];
loopLabel: Label = GenLabel[];
countDone: Label = GenLabel[];
lenOnly: Label = GenLabel[];
retEqual: Label = GenLabel[];
carryOut: Label = GenLabel[];
entryLabel: Label = GenLabel[];
ProcedureEntry[entryLabel, 2];
MakeLabelGlobal["Basics.CompareString", entryLabel];
Initialization
drLC0[]; -- rDelta
drLRIn[rS1, 0]; -- rL1 ← rS1.len
ExtractField[first: 16, bits: 16];
drLRIn[rS2, 0]; -- rL2 ← rS2.len
ExtractField[first: 16, bits: 16];
drDUP[];
drRJGEB[topSrc, rL1, UseLabel8B[minFound]];
drROR[topDst, rL1, const0];
SetLabel[minFound]; -- rMin ← MIN[L1, L2]
drLRn[rMin];
ExtractField[first: 0, bits: 30]; -- rDiv ← rMin / 4
drRAND[pushDst, rMin, const3]; -- rMod ← rMin MOD 4
drLC0[]; -- rW1 ← 0
drLC0[]; -- rW2 ← 0
drLC1[]; -- rRel ← 1
The comparison loop ([S] = rRel)
drRJGB[topSrc, rDiv, UseLabel8B[countDone]];
SetLabel[loopLabel];
drRRX[rW1, rS1, rRel]; -- rW1 ← (LOOPHOLE[rS1, WordPtr]+rRel)^
drRRX[rW2, rS2, rRel]; -- rW2 ← (LOOPHOLE[rS2, WordPtr]+rRel)^
drADDB[1]; -- rRel ← rRel + 1
drRUSUB[rDelta, rW2, rW1]; -- rDelta ← rW2 - rW1 (set carry)
drRJNEB[const0, rDelta, UseLabel8B[carryOut]]; -- IF rDelta = 0 THEN LOOP;
drRJLEBJ[topSrc, rDiv, UseLabel8B[loopLabel]]; -- IF rRel <= rDiv THEN LOOP;
There are 0 to 3 characters left in both strings. If there are any chars left in both strings, then we fetch both words and isolate only the important characters.
SetLabel[countDone];
drRJEB[const0, rMod, UseLabel8B[lenOnly]];
drRRX[rW1, rS1, rRel];
drRRX[rW2, rS2, rRel];
drLRn[rMod];
ShiftLeft[3];
drFSDB[FieldDescriptorToCard[[mask: 32, shift: 0]]];
drRFU[rW1, const0, rW1];
drRFU[rW2, const0, rW2];
drRUSUB[rDelta, rW2, rW1];
drRJNEB[const0, rDelta, UseLabel8B[carryOut]];
The result is strictly determined by the lengths
SetLabel[lenOnly];
drRUSUB[rDelta, rL2, rL1];
drRJNEB[const0, rDelta, UseLabel8B[carryOut]];
We get here when we know for sure that we are returning S1 = S2
SetLabel[retEqual];
drROR[reg0, const0, const1];
ProcedureExit[1];
At this point the carry bit has our result (carry = 1 iff S1 > S2)
SetLabel[carryOut];
drRADD[reg0, const0, const0];
drRADD[reg0, reg0, reg0];
ProcedureExit[1];
};
END.