BasicsImpl.mesa
Copyright Ó 1985, 1986, 1990, 1991, 1992 by Xerox Corporation. All rights reserved.
JKF August 26, 1988 10:49:27 am PDT
Russ Atkinson (RRA) April 19, 1990 9:58 pm PDT
Willie-s, March 5, 1992 3:52 pm PST
Michael Plass, April 9, 1993 1:25 pm PDT
Doug Wyatt, August 27, 1991 4:38 pm PDT
DIRECTORY Basics;
BasicsImpl: CEDAR PROGRAM
IMPORTS Basics
= BEGIN OPEN Basics;
External Names
ExternalNames: PROC [] = TRUSTED MACHINE CODE {
"^ExternalNames\n";
"CopyWords Basics𡤌opyWords\n";
"MoveWords Basics←MoveWords\n"; -- may be assembly-coded - see below
"FillWords Basics𡤏illWords\n"; -- may be assembly-coded - see below
"CopyBytes Basics𡤌opyBytes\n";
"MoveBytes Basics←MoveBytes\n";
"FillBytes Basics𡤏illBytes\n";
"CopyBits Basics𡤌opyBits \n";
"MoveBits Basics←MoveBits \n";
"FillBits Basics𡤏illBits \n";
"CompareBits Basics𡤌ompareBits\n";
"ByteBlt Basics𡤋yteBlt\n";
"BITSHIFT Basics𡤋ITSHIFT\n";
"CopyBitsDecreasing Basics𡤌opyBitsDecreasing \n";
"RegisterLogMisalign Basics←RegisterLogMisalign\n";
};
assemblyMoveAndFillWords: BOOL ~ AssemblyMoveAndFillWords[];
AssemblyMoveAndFillWords: PROC [] RETURNS [BOOL] = TRUSTED MACHINE CODE {
This crockery allows the assembly-coded versions of these routines to be used in lieu of the Mesa versions; we don't assume that such routines are available on all architecures.
"*#ifdef sparc\n";
"#define AssemblyMoveAndFillWordsHelp() 1\n";
"#define Basics←MoveWords Basics←MoveWords←Soft\n";
"#define Basics𡤏illWords Basics𡤏illWords←Soft\n";
"#else\n";
"#define AssemblyMoveAndFillWordsHelp() 0\n";
"#endif\n";
".AssemblyMoveAndFillWordsHelp";
};
Support for bit-oriented block operations
bpw: NAT ~ BITS[WORD];
BitOff: TYPE = [0..bpw);
BitCount: TYPE = [0..bpw];
WordsForBits: PROC [bits: CARD] RETURNS [CARD] ~ INLINE {
RETURN [CARD[bits+(bpw-1)]/bpw]
};
RightJustifiedOnes: PROC [n: BitCount] RETURNS [WORD] ~ INLINE {
RETURN [BITLSHIFT[1, n MOD bpw] - 1 - n/bpw]
};
RightJustifiedZeros: PROC [n: BitOff] RETURNS [WORD] ~ INLINE {
RETURN [-BITRSHIFT[2**(bpw-1), (bpw-1)-n]]
};
StartingWord: PROC [base: POINTER TO RawBits, bitIndex: CARD] RETURNS [POINTER TO RawWords] ~ TRUSTED INLINE {
RETURN [LOOPHOLE[base, POINTER] + (UNITS[WORD]*(bitIndex/bpw))]
};
MF: PROC [d, s, mask: WORD] RETURNS [WORD] ~ INLINE {
Replaces bits of d with s under the mask.
RETURN [BITXOR[BITAND[BITXOR[s, d], mask], d]]
};
Block word operations
CopyWords: UNSAFE PROC [
dst: POINTER TO RawWords,
src: POINTER TO RawWords,
count: CARDINAL] ~ {
FOR i: CARDINAL IN [0..count) DO
TRUSTED { dst[i] ¬ src[i] };
ENDLOOP;
};
MoveWords: UNSAFE PROC [
dst: POINTER TO RawWords,
src: POINTER TO RawWords,
count: CARDINAL] ~ {
IF LOOPHOLE[dst, CARD]<LOOPHOLE[src, CARD]
THEN {
FOR i: CARDINAL IN[0..count) DO
TRUSTED { dst[i] ¬ src[i] };
ENDLOOP;
}
ELSE {
FOR i: CARDINAL DECREASING IN[0..count) DO
TRUSTED { dst[i] ¬ src[i] };
ENDLOOP;
};
};
FillWords: UNSAFE PROC [
dst: POINTER TO RawWords,
count: CARDINAL, value: WORD] ~ UNCHECKED {
p: LONG POINTER TO ARRAY [0..4) OF WORD ¬ LOOPHOLE[dst];
WHILE count >= 4 DO
p[0] ¬ value;
p[1] ¬ value;
p[2] ¬ value;
p[3] ¬ value;
p ¬ p + SIZE[ARRAY [0..4) OF WORD];
count ¬ count - 4;
ENDLOOP;
IF count = 0 THEN RETURN;
p[0] ¬ value;
IF count = 1 THEN RETURN;
p[1] ¬ value;
IF count = 2 THEN RETURN;
p[2] ¬ value;
};
Block byte operations
CopyBytes: UNSAFE PROC [
dstBase: POINTER TO RawBytes, dstStart: CARD,
srcBase: POINTER TO RawBytes, srcStart: CARD,
count: CARDINAL] ~ TRUSTED {
IF count>(CARD.LAST-dstStart) THEN RaiseBoundsFault[];
IF count>(CARD.LAST-srcStart) THEN RaiseBoundsFault[];
IF count>= 2**(BITS[WORD]-BITS[BYTE]) THEN RaiseBoundsFault[];
CopyBits[
dstBase: LOOPHOLE[dstBase], dstStart: dstStart*BITS[BYTE],
srcBase: LOOPHOLE[srcBase], srcStart: srcStart*BITS[BYTE],
count: count*BITS[BYTE]
];
};
MoveBytes: UNSAFE PROC [
dstBase: POINTER TO RawBytes, dstStart: CARD,
srcBase: POINTER TO RawBytes, srcStart: CARD,
count: CARDINAL] ~ {
d0: CARD ~ LOOPHOLE[dstBase, CARD]*BYTES[UNIT]+dstStart;
s0: CARD ~ LOOPHOLE[srcBase, CARD]*BYTES[UNIT]+srcStart;
IF count>(CARD.LAST-dstStart) THEN RaiseBoundsFault[];
IF count>(CARD.LAST-srcStart) THEN RaiseBoundsFault[];
IF count>= 2**(BITS[WORD]-BITS[BYTE]) THEN RaiseBoundsFault[];
IF d0 IN (s0 .. s0+count)
THEN { -- bad overlap
FOR i: CARDINAL DECREASING IN[0..count) DO
TRUSTED { dstBase[dstStart+i] ¬ srcBase[srcStart+i] };
ENDLOOP;
}
ELSE TRUSTED {
CopyBits[
dstBase: LOOPHOLE[dstBase], dstStart: dstStart*BITS[BYTE],
srcBase: LOOPHOLE[srcBase], srcStart: srcStart*BITS[BYTE],
count: count*BITS[BYTE]
];
};
};
FillBytes: UNSAFE PROC [
dstBase: POINTER TO RawBytes, dstStart: CARD,
count: CARDINAL, value: BYTE] ~ CHECKED {
wordValue: CARD ¬ value + 100H*value;
wordValue ¬ wordValue + 10000H*wordValue;
TRUSTED {
FillBits[
dstBase: LOOPHOLE[dstBase], dstStart: dstStart*BITS[BYTE],
count: count*BITS[BYTE], value: wordValue
];
};
};
Misalignment Logging
This is a hook to allow detection and logging of misaligned arguments to the block-oriented procedures, using, for example, Spy.
logMisalign: PROC ¬ NIL;
RegisterLogMisalign: PROC [p: PROC] ~ {
logMisalign ¬ p;
};
Block bit operations
CopyBits: UNSAFE PROC [
dstBase: POINTER TO RawBits, dstStart: CARD,
srcBase: POINTER TO RawBits, srcStart: CARD,
count: CARDINAL] ~ CHECKED {
dstCorr: CARD ~ LOOPHOLE[dstBase, CARD] MOD UNITS[WORD];
srcCorr: CARD ~ LOOPHOLE[srcBase, CARD] MOD UNITS[WORD];
IF dstCorr+srcCorr # 0 THEN {
p: PROC ¬ logMisalign;
IF p # NIL THEN p[];
dstBase ¬ dstBase - dstCorr;
dstStart ¬ dstStart + BITS[UNIT]*dstCorr;
srcBase ¬ srcBase - srcCorr;
srcStart ¬ srcStart + BITS[UNIT]*srcCorr;
};
IF count # 0 THEN {
dst: POINTER TO RawWords ¬ StartingWord[dstBase, dstStart];
dstBit: BitOff ~ dstStart MOD bpw;
src: POINTER TO RawWords ¬ StartingWord[srcBase, srcStart];
srcBit: BitOff ~ srcStart MOD bpw;
ndw: CARD ~ WordsForBits[dstBit + count];
lMask: WORD ~ RightJustifiedOnes[bpw-dstBit];
mask for the leftmost dest word (ones where bits are to go)
rMask: WORD ~ RightJustifiedZeros[(LOOPHOLE[bpw-dstBit-count, CARD]) MOD bpw];
mask for the rightmost dest word
IF dstBit = srcBit
THEN { -- Aligned case is simpler
SELECT ndw FROM
1 => TRUSTED {
dst[0] ¬ MF[dst[0], src[0], BITAND[lMask, rMask]];
};
2 => TRUSTED {
dst[0] ¬ MF[dst[0], src[0], lMask];
dst[1] ¬ MF[dst[1], src[1], rMask];
};
3 => TRUSTED {
dst[0] ¬ MF[dst[0], src[0], lMask];
dst[1] ¬ src[1];
dst[2] ¬ MF[dst[2], src[2], rMask];
};
ENDCASE => TRUSTED {
nw: CARD ¬ LOOPHOLE[ndw-2, CARD];
dst[0] ¬ MF[dst[0], src[0], lMask];
dst ¬ dst+UNITS[WORD];
src ¬ src+UNITS[WORD];
WHILE nw >= 4 DO
dst[0] ¬ src[0];
dst[1] ¬ src[1];
dst[2] ¬ src[2];
dst[3] ¬ src[3];
dst ¬ dst+UNITS[WORD]*4;
src ¬ src+UNITS[WORD]*4;
nw ¬ nw - 4;
ENDLOOP;
IF nw >= 2 THEN {
dst[0] ¬ src[0];
dst[1] ¬ src[1];
dst ¬ dst+SIZE[WORD]*2;
src ¬ src+SIZE[WORD]*2;
nw ¬ nw - 2;
};
IF nw # 0 THEN {
dst[0] ¬ src[0];
dst ¬ dst+SIZE[WORD];
src ¬ src+SIZE[WORD];
};
dst[0] ¬ MF[dst[0], src[0], rMask];
};
}
ELSE { -- Unaligned case.
w: WORD ¬ 0; -- source word, aligned with destination
hi: WORD; -- left unshifted source word
lo: WORD ¬ 0; -- right unshifted source word
lSA: BitOff = LOOPHOLE[srcBit-dstBit, CARDINAL] MOD bpw; -- left shift amount
rSA: BitOff = LOOPHOLE[bpw - lSA, CARDINAL] MOD bpw; -- amount to shift source words right to line them up
nsw: CARD = WordsForBits[srcBit + count];
fetchLastWord: BOOL ~ IF srcBit >= dstBit THEN (nsw>ndw) ELSE (nsw>=ndw);
true if last source word needs to be fetched
FetchNext: PROC ~ INLINE {
fetches the next aligned source bits, and bumps source pointer
hi ¬ lo;
TRUSTED {lo ¬ src[0]};
src ¬ src+SIZE[WORD];
w ¬ BITLSHIFT[hi, lSA]+BITRSHIFT[lo, rSA]
};
FetchNextOff: PROC [wordOffset: CARD] ~ INLINE {
fetches the next word at the given offset, no pointer change
hi ¬ lo;
TRUSTED {lo ¬ src[wordOffset]};
w ¬ BITLSHIFT[hi, lSA]+BITRSHIFT[lo, rSA]
};
FetchLast: PROC [wordOffset: CARD, fetch: BOOL] ~ INLINE {
fetches the final source bits on a line, avoiding a spurious fetch
w ¬ BITLSHIFT[lo, lSA];
IF fetch THEN TRUSTED {w ¬ w + BITRSHIFT[src[wordOffset], rSA]};
};
IF srcBit >= dstBit THEN FetchNext[];
SELECT ndw FROM
1 => TRUSTED {
bothMask: WORD ~ BITAND[lMask, rMask];
FetchLast[0, fetchLastWord];
dst[0] ¬ MF[dst[0], w, bothMask];
};
2 => TRUSTED {
FetchNextOff[0];
dst[0] ¬ MF[dst[0], w, lMask];
FetchLast[1, fetchLastWord];
dst[1] ¬ MF[dst[1], w, rMask];
};
3 => TRUSTED {
FetchNextOff[0];
dst[0] ¬ MF[dst[0], w, lMask];
FetchNextOff[1];
dst[1] ¬ w;
FetchLast[2, fetchLastWord];
dst[2] ¬ MF[dst[2], w, rMask];
};
ENDCASE => TRUSTED {
nw: CARD ¬ LOOPHOLE[ndw-2, CARD];
FetchNextOff[0];
dst[0] ¬ MF[dst[0], w, lMask];
dst ¬ dst+SIZE[WORD];
src ¬ src+SIZE[WORD];
WHILE nw >= 2 DO
FetchNextOff[0];
dst[0] ¬ w;
FetchNextOff[1];
dst[1] ¬ w;
dst ¬ dst+SIZE[WORD]*2;
src ¬ src+SIZE[WORD]*2;
nw ¬ nw - 2;
ENDLOOP;
IF nw # 0 THEN {
FetchNextOff[0];
dst[0] ¬ w;
dst ¬ dst+SIZE[WORD];
src ¬ src+SIZE[WORD];
};
FetchLast[0, fetchLastWord];
dst[0] ¬ MF[dst[0], w, rMask];
};
};
};
};
CopyBitsDecreasing: UNSAFE PROC [
dstBase: POINTER TO RawBits, dstStart: CARD,
srcBase: POINTER TO RawBits, srcStart: CARD,
count: CARDINAL] ~ CHECKED {
dstCorr: CARD ~ LOOPHOLE[dstBase, CARD] MOD UNITS[WORD];
srcCorr: CARD ~ LOOPHOLE[srcBase, CARD] MOD UNITS[WORD];
IF dstCorr+srcCorr # 0 THEN {
p: PROC ¬ logMisalign;
IF p # NIL THEN p[];
dstBase ¬ dstBase - dstCorr;
dstStart ¬ dstStart + BITS[UNIT]*dstCorr;
srcBase ¬ srcBase - srcCorr;
srcStart ¬ srcStart + BITS[UNIT]*srcCorr;
};
IF count # 0 THEN {
dst: POINTER TO RawWords ¬ StartingWord[dstBase, dstStart];
dstBit: BitOff ~ dstStart MOD bpw;
src: POINTER TO RawWords ¬ StartingWord[srcBase, srcStart];
srcBit: BitOff ~ srcStart MOD bpw;
ndw: CARD ~ WordsForBits[dstBit + count];
lMask: WORD ~ RightJustifiedOnes[bpw-dstBit];
mask for the leftmost dest word (ones where bits are to go)
rMask: WORD ~ RightJustifiedZeros[(LOOPHOLE[bpw-dstBit-count, CARD]) MOD bpw];
mask for the rightmost dest word
IF dstBit = srcBit
THEN { -- Aligned case is simpler
SELECT ndw FROM
1 => TRUSTED {
dst[0] ¬ MF[dst[0], src[0], BITAND[lMask, rMask]];
};
2 => TRUSTED {
dst[1] ¬ MF[dst[1], src[1], rMask];
dst[0] ¬ MF[dst[0], src[0], lMask];
};
3 => TRUSTED {
dst[2] ¬ MF[dst[2], src[2], rMask];
dst[1] ¬ src[1];
dst[0] ¬ MF[dst[0], src[0], lMask];
};
ENDCASE => TRUSTED {
nw: CARD ¬ LOOPHOLE[ndw-2, CARD];
dst ¬ dst+ndw*UNITS[WORD] - UNITS[WORD];
src ¬ src+ndw*UNITS[WORD] - UNITS[WORD];
dst[0] ¬ MF[dst[0], src[0], rMask];
WHILE nw >= 4 DO
dst ¬ dst-UNITS[WORD]*4;
src ¬ src-UNITS[WORD]*4;
dst[3] ¬ src[3];
dst[2] ¬ src[2];
dst[1] ¬ src[1];
dst[0] ¬ src[0];
nw ¬ nw - 4;
ENDLOOP;
IF nw >= 2 THEN {
dst ¬ dst-UNITS[WORD]*2;
src ¬ src-UNITS[WORD]*2;
dst[1] ¬ src[1];
dst[0] ¬ src[0];
nw ¬ nw - 2;
};
IF nw # 0 THEN {
dst ¬ dst-UNITS[WORD];
src ¬ src-UNITS[WORD];
dst[0] ¬ src[0];
};
dst ¬ dst-UNITS[WORD];
src ¬ src-UNITS[WORD];
dst[0] ¬ MF[dst[0], src[0], lMask];
};
}
ELSE { -- Unaligned case.
w: WORD ¬ 0; -- source word, aligned with destination
hi: WORD ¬ 0; -- left unshifted source word
lo: WORD; -- right unshifted source word
lSA: BitOff = LOOPHOLE[srcBit-dstBit, CARDINAL] MOD bpw; -- left shift amount
rSA: BitOff = LOOPHOLE[bpw - lSA, CARDINAL] MOD bpw; -- amount to shift source words right to line them up
nsw: CARD = WordsForBits[srcBit + count];
fetchLeftmost: BOOL ~ srcBit >= dstBit;
fetchRightmost: BOOL ~ IF fetchLeftmost THEN (nsw>ndw) ELSE (nsw>=ndw);
FetchNext: PROC ~ INLINE {
fetches the next aligned source bits, and bumps source pointer
lo ¬ hi;
TRUSTED {hi ¬ src[0]};
src ¬ src-UNITS[WORD];
w ¬ BITLSHIFT[hi, lSA]+BITRSHIFT[lo, rSA]
};
FetchLast: PROC ~ INLINE {
fetches the last (leftmost) source bits on a line, avoiding a spurious fetch
lo ¬ hi;
IF fetchLeftmost THEN TRUSTED {hi ¬ src[0]} ELSE hi ¬ 0;
w ¬ BITLSHIFT[hi, lSA]+BITRSHIFT[lo, rSA]
};
src ¬ src + nsw*UNITS[WORD] - UNITS[WORD];
IF fetchRightmost THEN FetchNext[];
SELECT ndw FROM
1 => TRUSTED {
bothMask: WORD ~ BITAND[lMask, rMask];
FetchLast[];
dst[0] ¬ MF[dst[0], w, bothMask];
};
2 => TRUSTED {
FetchNext[];
dst[1] ¬ MF[dst[1], w, rMask];
FetchLast[];
dst[0] ¬ MF[dst[0], w, lMask];
};
3 => TRUSTED {
FetchNext[];
dst[2] ¬ MF[dst[2], w, rMask];
FetchNext[];
dst[1] ¬ w;
FetchLast[];
dst[0] ¬ MF[dst[0], w, lMask];
};
ENDCASE => TRUSTED {
nw: CARD ¬ LOOPHOLE[ndw-2, CARD];
FetchNext[];
dst ¬ dst + ndw*UNITS[WORD] - UNITS[WORD];
dst[0] ¬ MF[dst[0], w, rMask];
WHILE nw >= 2 DO
dst ¬ dst-UNITS[WORD]*2;
FetchNext[];
dst[1] ¬ w;
FetchNext[];
dst[0] ¬ w;
nw ¬ nw - 2;
ENDLOOP;
IF nw # 0 THEN {
dst ¬ dst-UNITS[WORD];
FetchNext[];
dst[0] ¬ w;
};
dst ¬ dst-UNITS[WORD];
FetchLast[];
dst[0] ¬ MF[dst[0], w, lMask];
};
};
};
};
MoveBits: UNSAFE PROC [
dstBase: POINTER TO RawBits, dstStart: CARD,
srcBase: POINTER TO RawBits, srcStart: CARD,
count: CARDINAL] ~ CHECKED {
d0: CARD ~ LOOPHOLE[dstBase, CARD]*BITS[UNIT]+dstStart;
s0: CARD ~ LOOPHOLE[srcBase, CARD]*BITS[UNIT]+srcStart;
IF d0 IN (s0 .. s0+count)
THEN { -- bad overlap. This is a pretty slow impl right now...
FOR i: CARDINAL DECREASING IN [0..count) DO
TRUSTED { dstBase[dstStart+i] ¬ srcBase[srcStart+i] };
ENDLOOP;
}
ELSE TRUSTED {
CopyBits[dstBase: dstBase, dstStart: dstStart, srcBase: srcBase, srcStart: srcStart, count: count];
};
};
FillBits: UNSAFE PROC [
dstBase: POINTER TO RawBits, dstStart: CARD,
count: CARDINAL, value: WORD] ~ CHECKED {
NOTE: A better name might be PatternFillBits, since the value is a whole word of bits rather than a single bit.
dstCorr: CARD ~ LOOPHOLE[dstBase, CARD] MOD UNITS[WORD];
IF dstCorr # 0 THEN {
p: PROC ¬ logMisalign;
IF p # NIL THEN p[];
dstBase ¬ dstBase - dstCorr;
dstStart ¬ dstStart + BITS[UNIT]*dstCorr;
};
IF count # 0 THEN {
dst: POINTER TO RawWords ¬ StartingWord[dstBase, dstStart];
dstBit: BitOff ~ dstStart MOD bpw;
ndw: CARD ~ WordsForBits[dstBit + count];
lMask: WORD ~ RightJustifiedOnes[bpw-dstBit];
mask for the leftmost dest word (ones where bits are to go)
rMask: WORD ~ RightJustifiedZeros[(LOOPHOLE[bpw-dstBit-count, CARD]) MOD bpw];
mask for the rightmost dest word
SELECT ndw FROM
1 => TRUSTED {
dst[0] ¬ MF[dst[0], value, BITAND[lMask, rMask]];
};
2 => TRUSTED {
dst[0] ¬ MF[dst[0], value, lMask];
dst[1] ¬ MF[dst[1], value, rMask];
};
ENDCASE => TRUSTED {
nw: CARD ¬ LOOPHOLE[ndw-2, CARD];
dst[0] ¬ MF[dst[0], value, lMask];
dst ¬ dst+UNITS[WORD];
WHILE nw >= 4 DO
dst[0] ¬ value;
dst[1] ¬ value;
dst[2] ¬ value;
dst[3] ¬ value;
dst ¬ dst+UNITS[WORD]*4;
nw ¬ nw - 4;
ENDLOOP;
IF nw >= 2 THEN {
dst[0] ¬ value;
dst[1] ¬ value;
dst ¬ dst+UNITS[WORD]*2;
nw ¬ nw - 2;
};
IF nw # 0 THEN {
dst[0] ¬ value;
dst ¬ dst+SIZE[WORD];
};
dst[0] ¬ MF[dst[0], value, rMask];
};
};
};
CompareBits: UNSAFE PROC [
aBase: POINTER TO RawBits, aStart: CARD,
bBase: POINTER TO RawBits, bStart: CARD,
count: CARDINAL] RETURNS [Comparison] ~ CHECKED {
aCorr: CARD ~ LOOPHOLE[aBase, CARD] MOD UNITS[WORD];
bCorr: CARD ~ LOOPHOLE[aBase, CARD] MOD UNITS[WORD];
IF aCorr+bCorr # 0 THEN {
p: PROC ¬ logMisalign;
IF p # NIL THEN p[];
aBase ¬ aBase - aCorr;
aStart ¬ aStart + BITS[UNIT]*aCorr;
bBase ¬ bBase - bCorr;
bStart ¬ bStart + BITS[UNIT]*bCorr;
};
IF count # 0 THEN {
a: POINTER TO RawWords ¬ StartingWord[aBase, aStart];
aBit: BitOff ~ aStart MOD bpw;
b: POINTER TO RawWords ¬ StartingWord[bBase, bStart];
bBit: BitOff ~ bStart MOD bpw;
ndw: CARD ~ WordsForBits[aBit + count];
lMask: WORD ~ RightJustifiedOnes[bpw-aBit];
mask for the leftmost dest word (ones where bits are to go)
rMask: WORD ~ RightJustifiedZeros[(LOOPHOLE[bpw-aBit-count, CARD]) MOD bpw];
mask for the rightmost dest word
aWord: WORD ¬ 0;
bWord: WORD ¬ 0;
X: PROC [aW, bW, m: WORD] ~ INLINE {
aWord ¬ BITAND[aW, m];
bWord ¬ BITAND[bW, m];
};
Y: PROC [aW, bW: WORD] ~ INLINE { aWord ¬ aW; bWord ¬ bW };
{
IF aBit = bBit
THEN { -- Aligned case is simpler
SELECT ndw FROM
1 => TRUSTED {
X[a[0], b[0], BITAND[lMask, rMask]]; IF aWord # bWord THEN GOTO Differ;
};
2 => TRUSTED {
X[a[0], b[0], lMask]; IF aWord # bWord THEN GOTO Differ;
X[a[1], b[1], rMask]; IF aWord # bWord THEN GOTO Differ;
};
3 => TRUSTED {
X[a[0], b[0], lMask]; IF aWord # bWord THEN GOTO Differ;
Y[a[1], b[1]]; IF aWord # bWord THEN GOTO Differ;
X[a[2], b[2], rMask]; IF aWord # bWord THEN GOTO Differ;
};
ENDCASE => TRUSTED {
nw: CARD ¬ LOOPHOLE[ndw-2, CARD];
X[a[0], b[0], lMask]; IF aWord # bWord THEN GOTO Differ;
a ¬ a+UNITS[WORD];
b ¬ b+UNITS[WORD];
WHILE nw >= 2 DO
Y[a[0], b[0]]; IF aWord # bWord THEN GOTO Differ;
Y[a[1], b[1]]; IF aWord # bWord THEN GOTO Differ;
a ¬ a+SIZE[WORD]*2;
b ¬ b+SIZE[WORD]*2;
nw ¬ nw - 2;
ENDLOOP;
IF nw # 0 THEN {
Y[a[0], b[0]]; IF aWord # bWord THEN GOTO Differ;
a ¬ a+SIZE[WORD];
b ¬ b+SIZE[WORD];
};
X[a[0], b[0], rMask]; IF aWord # bWord THEN GOTO Differ;
};
}
ELSE { -- Unaligned case.
w: WORD ¬ 0; -- source word, aligned with destination
hi: WORD; -- left unshifted source word
lo: WORD ¬ 0; -- right unshifted source word
lSA: BitOff = LOOPHOLE[bBit-aBit, CARDINAL] MOD bpw; -- left shift amount
rSA: BitOff = LOOPHOLE[bpw - lSA, CARDINAL] MOD bpw; -- amount to shift source words right to line them up
nsw: CARD = WordsForBits[bBit + count];
fetchLastWord: BOOL ~ IF bBit >= aBit THEN (nsw>ndw) ELSE (nsw>=ndw);
true if last source word needs to be fetched
FetchNext: PROC ~ INLINE {
fetches the next aligned source bits, and bumps source pointer
hi ¬ lo;
TRUSTED {lo ¬ b[0]};
b ¬ b+SIZE[WORD];
w ¬ BITLSHIFT[hi, lSA]+BITRSHIFT[lo, rSA]
};
FetchNextOff: PROC [wordOffset: CARD] ~ INLINE {
fetches the next word at the given offset, no pointer change
hi ¬ lo;
TRUSTED {lo ¬ b[wordOffset]};
w ¬ BITLSHIFT[hi, lSA]+BITRSHIFT[lo, rSA]
};
FetchLast: PROC [wordOffset: CARD, fetch: BOOL] ~ INLINE {
fetches the final source bits on a line, avoiding a spurious fetch
w ¬ BITLSHIFT[lo, lSA];
IF fetch THEN TRUSTED {w ¬ w + BITRSHIFT[b[wordOffset], rSA]};
};
IF bBit >= aBit THEN FetchNext[];
SELECT ndw FROM
1 => TRUSTED {
bothMask: WORD ~ BITAND[lMask, rMask];
FetchLast[0, fetchLastWord];
X[a[0], w, bothMask]; IF aWord # bWord THEN GOTO Differ;
};
2 => TRUSTED {
FetchNextOff[0];
X[a[0], w, lMask]; IF aWord # bWord THEN GOTO Differ;
FetchLast[1, fetchLastWord];
X[a[1], w, rMask]; IF aWord # bWord THEN GOTO Differ;
};
3 => TRUSTED {
FetchNextOff[0];
X[a[0], w, lMask]; IF aWord # bWord THEN GOTO Differ;
FetchNextOff[1];
Y[a[1], w]; IF aWord # bWord THEN GOTO Differ;
FetchLast[2, fetchLastWord];
X[a[2], w, rMask]; IF aWord # bWord THEN GOTO Differ;
};
ENDCASE => TRUSTED {
nw: CARD ¬ LOOPHOLE[ndw-2, CARD];
FetchNextOff[0];
X[a[0], w, lMask]; IF aWord # bWord THEN GOTO Differ;
a ¬ a+SIZE[WORD];
b ¬ b+SIZE[WORD];
WHILE nw >= 2 DO
FetchNextOff[0];
Y[a[0], w]; IF aWord # bWord THEN GOTO Differ;
FetchNextOff[1];
Y[a[1], w]; IF aWord # bWord THEN GOTO Differ;
a ¬ a+SIZE[WORD]*2;
b ¬ b+SIZE[WORD]*2;
nw ¬ nw - 2;
ENDLOOP;
IF nw # 0 THEN {
FetchNextOff[0];
Y[a[0], w]; IF aWord # bWord THEN GOTO Differ;
a ¬ a+SIZE[WORD];
b ¬ b+SIZE[WORD];
};
FetchLast[0, fetchLastWord];
X[a[0], w, rMask]; IF aWord # bWord THEN GOTO Differ;
};
};
EXITS Differ => {IF aWord < bWord THEN RETURN [less] ELSE RETURN [greater]};
};
};
RETURN [equal];
};
Shifts
BITSHIFT: PROC [value: WORD, count: INTEGER] RETURNS [WORD] ~ {
c: [0..bitsPerWord);
c ¬ LOOPHOLE[count, CARDINAL] MOD bitsPerWord;
IF count = c THEN RETURN [BITLSHIFT[value, c]];
count ¬ -count;
c ¬ LOOPHOLE[count, CARDINAL] MOD bitsPerWord;
IF count = c THEN RETURN [BITRSHIFT[value, c]];
RETURN [0]
};
ByteBlt (compatibility).
ByteBlt: UNSAFE PROC [to, from: ByteBltBlock] RETURNS [nBytes: CARDINAL] ~ {
nBytes ¬ MIN[
MAX[to.startIndex, to.stopIndexPlusOne] - to.startIndex,
MAX[from.startIndex, from.stopIndexPlusOne] - from.startIndex
];
TRUSTED{MoveBytes[to.blockPointer, to.startIndex, from.blockPointer, from.startIndex, nBytes]};
};
ExternalNames[];
END.