Basics.mesa
Copyright © 1985 by Xerox Corporation. All rights reserved.
Levin on September 20, 1983 11:00 am
Russ Atkinson (RRA) February 27, 1985 8:10:50 pm PST
Doug Wyatt, February 26, 1985 2:49:33 pm PST
DIRECTORY
PrincOps USING [zAND, zBNDCK, zDCOMP, zDIV, zDUCOMP, zEXCH, zINC, zLDIV, zLIN1, zLINI, zMUL, zOR, zPUSH, zSHIFT, zXOR];
Commonly-used types and values
bytesPerWord: NAT = 2;
charsPerWord: NAT = bytesPerWord;
bitsPerByte: NAT = 8;
bitsPerChar: NAT = bitsPerByte;
bitsPerWord: NAT = bitsPerByte*bytesPerWord;
logBitsPerByte: NAT = 3; --LogBase2[bitsPerByte]
logBitsPerChar: NAT = logBitsPerByte;
logBytesPerWord: NAT = 1; --LogBase2[bytesPerWord]
logCharsPerWord: NAT = logBytesPerWord;
logBitsPerWord: NAT = logBitsPerByte + logBytesPerWord;
BYTE: TYPE = [0..377B];
Byte: TYPE = BYTE;
Word: TYPE = WORD;
CARD: TYPE = LONG CARDINAL;
LongNumber:
TYPE =
MACHINE
DEPENDENT
RECORD [
SELECT
OVERLAID *
FROM
real => [real: REAL],
lp => [lp: LONG POINTER],
lc => [lc: CARD],
li => [li: INT],
pair => [lo, hi:
WORD],
note: low order word precedes high order word
num => [lowbits, highbits:
CARDINAL],
like pair, but only present for compatibility
bytes => [lh, ll, hh, hl: BYTE],
bits => [bits:
PACKED
ARRAY [0..bitsPerWord*2)
OF
BOOL],
note: bits [0..16) are in the low word, bits [16..32) are in the high word
ENDCASE
];
ShortNumber:
TYPE =
MACHINE
DEPENDENT
RECORD [
SELECT
OVERLAID *
FROM
sc => [lc: CARDINAL],
si => [li: INTEGER],
bytes => [hi, lo: BYTE],
bits => [bits:
PACKED
ARRAY [0..bitsPerWord)
OF
BOOL],
note: bit n is higher order than bit n+1
ENDCASE
];
BytePair: TYPE = MACHINE DEPENDENT RECORD [high, low: BYTE];
Comparison: TYPE = MACHINE DEPENDENT {less(0), equal(1), greater(2)};
RawWords: TYPE = RECORD [SEQUENCE COMPUTED CARDINAL OF WORD];
RawCards: TYPE = RECORD [SEQUENCE COMPUTED CARDINAL OF CARDINAL];
RawBytes: TYPE = RECORD [PACKED SEQUENCE COMPUTED CARDINAL OF BYTE];
RawChars: TYPE = RECORD [PACKED SEQUENCE COMPUTED CARDINAL OF CHAR];
UnsafeBlock:
TYPE =
RECORD [
An UnsafeBlock describes the byte sequence base[startIndex..startIndex+count).
base: LONG POINTER TO RawBytes ← NIL,
startIndex: INT ← 0,
count: INT ← 0
];
Arithmetic utilities
CompareLC:
PROC [a, b:
CARD]
RETURNS [Comparison]
= TRUSTED MACHINE CODE { zDUCOMP; zINC; };
CompareCard:
PROC [a, b:
CARD]
RETURNS [Comparison]
= TRUSTED MACHINE CODE { zDUCOMP; zINC; };
CompareINT:
PROC [a, b:
INT]
RETURNS [Comparison]
= TRUSTED MACHINE CODE { zDCOMP; zINC; };
DivMod:
PROC [num, den:
CARDINAL]
RETURNS [quotient, remainder:
CARDINAL]
= TRUSTED MACHINE CODE { zDIV; zPUSH; };
Can raise RuntimeError.ZeroDivisor.
LongMult:
PROC [
CARDINAL,
CARDINAL]
RETURNS [product:
CARD]
= TRUSTED MACHINE CODE { zMUL; zPUSH; };
LongDiv:
PROC [num:
CARD, den:
CARDINAL]
RETURNS [
CARDINAL]
= TRUSTED MACHINE CODE { zLDIV; };
Can raise RuntimeError.DivideCheck on overflow or RuntimeError.ZeroDivisor if den = 0.
LongDivMod:
PROC [num:
CARD, den:
CARDINAL]
RETURNS [quotient, remainder:
CARDINAL]
= TRUSTED MACHINE CODE { zLDIV; zPUSH; };
Can raise RuntimeError.DivideCheck on overflow or RuntimeError.ZeroDivisor if den = 0.
Bounds checking
BoundsCheck:
PROC [value:
CARDINAL, bound:
CARDINAL]
RETURNS [
CARDINAL]
= TRUSTED MACHINE CODE { zBNDCK };
... RETURN [IF value >= bound THEN ERROR RuntimeError.BoundsCheck ELSE value]
BoundsCheckHighHalf:
PROC [value:
INT, bound:
CARDINAL]
RETURNS [
INT]
= TRUSTED MACHINE CODE { zBNDCK };
... IF HighHalf[LOOPHOLE[value, CARD]] < bound
THEN RETURN [value] ELSE ERROR RuntimeError.BoundsCheck;
example: BoundsCheckHighHalf[int, 400B] will check for int IN [0..2**24)
example: BoundsCheckHighHalf[int, 100000B] will check for int >= 0
warning: bound > 100000B will give peculiar results
NonNegative:
PROC [value:
INT]
RETURNS [
INT]
= TRUSTED MACHINE CODE { zLINI; zBNDCK; };
... IF value < 0 THEN ERROR RuntimeError.BoundsCheck ELSE RETURN [value]
Logic utilities
BitOp:
TYPE =
PROC [
WORD,
WORD]
RETURNS [
WORD];
BITAND: BitOp
= TRUSTED MACHINE CODE { zAND };
BITOR: BitOp
= TRUSTED MACHINE CODE { zOR };
BITXOR: BitOp
= TRUSTED MACHINE CODE { zXOR };
BITNOT:
PROC [
WORD]
RETURNS [
WORD]
= TRUSTED MACHINE CODE { zLIN1; zXOR; };
BITSHIFT:
PROC [value:
WORD, count:
INTEGER]
RETURNS [
WORD]
= TRUSTED MACHINE CODE { zSHIFT };
... shifts the value by the count. If count is positive, the shift is to the left. If count is negative, the count is to the right.
Field Extraction
LowHalf:
PROC [n:
CARD]
RETURNS [
WORD]
= TRUSTED INLINE { RETURN[LOOPHOLE[n, LongNumber].lowbits] };
HighHalf:
PROC [n:
CARD]
RETURNS [
WORD]
= TRUSTED INLINE { RETURN[LOOPHOLE[n, LongNumber].highbits] };
LowByte:
PROC [n:
WORD]
RETURNS [
BYTE]
= TRUSTED INLINE { RETURN[LOOPHOLE[n, BytePair].low] };
HighByte:
PROC [n:
WORD]
RETURNS [
BYTE]
= TRUSTED INLINE { RETURN[LOOPHOLE[n, BytePair].high] };
Other operations on long numbers
SwapHalves:
PROC [n: LongNumber]
RETURNS [LongNumber]
= TRUSTED MACHINE CODE { zEXCH };
... swaps the 16-bit halves of the 32-bit LongNumber
ExtractWordField:
PROC [n: LongNumber, right: [0..2*bitsPerWord)]
RETURNS [
CARDINAL]
= TRUSTED INLINE {
... shifts n right by the given # of bits and returns the resulting low-order 16 bits. This is equivalent to (but much faster than) LowHalf[n.lc / BITSHIFT[1, right]].
RETURN [BITOR [BITSHIFT[n.lo, -right], BITSHIFT[n.hi, 16-right]] ];
};
DoubleShift:
PROC [ln: LongNumber, dist:
INTEGER]
RETURNS [LongNumber]
= TRUSTED INLINE {
... shifts left if the number is positive, right if it is negative. Notice that unlike the single shift operations, distances outside of [-31..31] result in 0, rather than wrapping.
IF dist >= 0
THEN RETURN [DoubleShiftLeft[ln, LOOPHOLE[dist, NAT]]]
ELSE RETURN [DoubleShiftRight[ln, LOOPHOLE[-dist, NAT]]]
};
DoubleShiftLeft:
PROC [ln: LongNumber, dist:
NAT]
RETURNS [new: LongNumber]
= TRUSTED INLINE {
... shifts one LongNumber left by dist bits and returns the shifted LongNumber. Shifting left by 1 bit is equivalent to doubling the pairber.
RETURN [ [pair[
lo: BITSHIFT[ln.lo, dist],
hi: BITOR[BITSHIFT[ln.hi, dist], BITSHIFT[ln.lo, dist-16]]
]]];
};
DoubleShiftRight:
PROC [ln: LongNumber, dist:
NAT]
RETURNS [new: LongNumber]
= TRUSTED INLINE {
... shifts one LongNumber left by dist bits and returns the shifted LongNumber. Shifting right by 1 bit is equivalent to halving the pairber.
RETURN [ [pair[
lo: BITOR[BITSHIFT[ln.lo, -dist], BITSHIFT[ln.hi, 16-dist]],
hi: BITSHIFT[ln.hi, -dist]
]]];
};
DoubleAnd:
PROC [a,b: LongNumber]
RETURNS [LongNumber]
= INLINE {
DoubleAnd is a 32-bit AND
RETURN [ [num[
lowbits: BITAND[a.lowbits, b.lowbits],
highbits: BITAND[a.highbits, b.highbits]
]]];
};
DoubleOr:
PROC [a,b: LongNumber]
RETURNS [LongNumber]
= INLINE {
DoubleOr is a 32-bit OR
RETURN [ [num[
lowbits: BITOR[a.lowbits, b.lowbits],
highbits: BITOR[a.highbits, b.highbits]
]]];
};
DoubleNot:
PROC [ln: LongNumber]
RETURNS [LongNumber]
= INLINE {
DoubleNot is a 32-bit NOT
RETURN [ [num[
lowbits: BITNOT[ln.lowbits],
highbits: BITNOT[ln.highbits]
]]];
};
DoubleXor:
PROC [a,b: LongNumber]
RETURNS [LongNumber]
= INLINE {
DoubleXor is a 32-bit XOR
RETURN [ [num[
lowbits: BITXOR[a.lowbits, b.lowbits],
highbits: BITXOR[a.highbits, b.highbits]
]]];
};