BitOps.mesa
Copyright © 1986 by Xerox Corporation. All rights reserved.
Barth, August 7, 1986 6:04:44 pm PDT
Spreitzer, March 19, 1984 8:59:08 pm PST
BitOps: CEDAR DEFINITIONS = BEGIN
Theory
This is an interface for extracting and inserting bit fields and a few other miscellaneous operations.
Extractors/insertors mediate between containers and "external" TYPEs. There are four kinds of containers: CARDINAL, LONG CARDINAL, 4 element ARRAY OF CARDINAL, and ARRAY OF CARDINAL. There are three external TYPEs: BOOLEAN, CARDINAL, and LONG CARDINAL (a.k.a. Long). Thus, there are 2*4*3 = 24 of these procedures.
Increasing index means decreasing significance (the most significant bit is numbered 0). The least significant bit of a field is stored in the least significant bit of a container so that Mesa operations can be performed directly on containers which are 16 or 32 bits wide. Because of the method of numbering the bits and the alignment requirements the field width must be passed to each operation in order to compute how the bits in the containers are numbered.
There are also some boolean operations defined upon the containers.
The containers
BitWord: TYPE = CARDINAL;
BitDWord: TYPE = LONG CARDINAL;
BitQWord: TYPE = ARRAY [0 .. 4) OF CARDINAL;
BitMWord: TYPE = LONG DESCRIPTOR FOR ARRAY CARDINAL OF BitWord;
The externals
BOOL and CARDINAL already exist!
Long: TYPE = LONG CARDINAL;
Handy constants
bitsPerWord: NAT = Basics.bitsPerWord;
bitsPerDWord: NAT = 2*Basics.bitsPerWord;
bitsPerQWord: NAT = 4*Basics.bitsPerWord;
LastWBit: NAT = bitsPerWord - 1;
LastDBit: NAT = bitsPerDWord - 1;
LastQBit: NAT = bitsPerQWord - 1;
BitWordZero: BitWord = 0;
BitWordOnes: BitWord = 65535;
BitDWordZero: BitDWord = 0;
BitDWordOnes: BitDWord = 4294967295;
BitQWordZero: BitQWord = [0, 0, 0, 0];
BitQWordOnes: BitQWord = [BitWordOnes, BitWordOnes, BitWordOnes, BitWordOnes];
Predicates
ODD:
PROC [i:
INT]
RETURNS [
BOOL];
EVEN: PROC [i: INT] RETURNS [BOOL];
Log2
Log2:
PROC [n:
INT]
RETURNS [
INT];
-- Floor of Log2
NBits:
PROC [n:
INT]
RETURNS [
INT];
TwoToThe:
PROC [x:
INT]
RETURNS [
INT];
TwoToTheLog2: PROC [n: INT] RETURNS [INT];
Extraction and Insertion procedures
Definition of parameters and results:
container: The array of bits that the field is inserted into or extracted from.
containerWidth: The number of bits being used in the container. Must be less than or equal to the maximum size which the container can hold.
bitPosition, fieldPosition: The position of the bit, or most significant bit of a field, within the container. The most significant bit is labeled bit zero and the least significant bit is labeled as the field width - 1.
fieldWidth: The width of the field in bits. The last bit position of a field is fieldPosition + fieldWidth - 1.
source: An argument to insertion procedures. It is the value assigned to the described field.
result: The value of the described field. It is returned by the extraction procedures.
newContainer: The updated container returned by insertion procedures except for the multiple word procedures which utilize a call by address argument mechanism rather than a call by value mechanism.
Bools
ExtractBoolFWord,
EBFW:
PROC [container: BitWord, bitPosition:
NAT, containerWidth:
NAT ← bitsPerWord]
RETURNS [result:
BOOL];
InsertBoolInWord,
IBIW:
PROC [source:
BOOL, container: BitWord, bitPosition:
NAT, containerWidth:
NAT ← bitsPerWord]
RETURNS [newContainer: BitWord];
ExtractBoolFDouble,
EBFD:
PROC [container: BitDWord, bitPosition:
NAT, containerWidth:
NAT ← bitsPerDWord]
RETURNS [result:
BOOL];
InsertBoolInDouble,
IBID:
PROC [source:
BOOL, container: BitDWord, bitPosition:
NAT, containerWidth:
NAT ← bitsPerDWord]
RETURNS [newContainer: BitDWord];
ExtractBoolFQuad,
EBFQ:
PROC [container: BitQWord, bitPosition:
NAT, containerWidth:
NAT ← bitsPerQWord]
RETURNS [result:
BOOL];
InsertBoolInQuad,
IBIQ:
PROC [source:
BOOL, container: BitQWord, bitPosition:
NAT, containerWidth:
NAT ← bitsPerQWord]
RETURNS [newContainer: BitQWord];
ExtractBoolFMultiple,
EBFM:
PROC [container: BitMWord, bitPosition:
NAT, containerWidth:
NAT]
RETURNS [result:
BOOL];
InsertBoolInMultiple,
IBIM:
PROC [source:
BOOL, container: BitMWord, bitPosition:
NAT, containerWidth:
NAT];
Cardinals
ExtractCardinalFWord,
ECFW:
PROC [container: BitWord, fieldPosition, fieldWidth:
NAT, containerWidth:
NAT ← bitsPerWord]
RETURNS [result:
CARDINAL];
InsertCardinalInWord,
ICIW:
PROC [source:
CARDINAL, container: BitWord, fieldPosition, fieldWidth:
NAT, containerWidth:
NAT ← bitsPerWord]
RETURNS [newContainer: BitWord];
ExtractCardinalFDouble,
ECFD:
PROC [container: BitDWord, fieldPosition, fieldWidth:
NAT, containerWidth:
NAT ← bitsPerDWord]
RETURNS [result:
CARDINAL];
InsertCardinalInDouble,
ICID:
PROC [source:
CARDINAL, container: BitDWord, fieldPosition, fieldWidth:
NAT, containerWidth:
NAT ← bitsPerDWord]
RETURNS [newContainer: BitDWord];
ExtractCardinalFQuad,
ECFQ:
PROC [container: BitQWord, fieldPosition, fieldWidth:
NAT, containerWidth:
NAT ← bitsPerQWord]
RETURNS [result:
CARDINAL];
InsertCardinalInQuad,
ICIQ:
PROC [source:
CARDINAL, container: BitQWord, fieldPosition, fieldWidth:
NAT, containerWidth:
NAT ← bitsPerQWord]
RETURNS [newContainer: BitQWord];
ExtractCardinalFMultiple,
ECFM:
PROC [container: BitMWord, fieldPosition, fieldWidth, containerWidth:
NAT]
RETURNS [result:
CARDINAL];
InsertCardinalInMultiple,
ICIM:
PROC [source:
CARDINAL, container: BitMWord, fieldPosition, fieldWidth, containerWidth:
NAT];
Longs
ExtractLongFWord,
ELFW:
PROC [container: BitWord, fieldPosition, fieldWidth:
NAT, containerWidth:
NAT ← bitsPerWord]
RETURNS [result: Long];
InsertLongInWord,
ILIW:
PROC [source: Long, container: BitWord, fieldPosition, fieldWidth:
NAT, containerWidth:
NAT ← bitsPerWord]
RETURNS [newContainer: BitWord];
ExtractLongFDouble,
ELFD:
PROC [container: BitDWord, fieldPosition, fieldWidth:
NAT, containerWidth:
NAT ← bitsPerDWord]
RETURNS [result: Long];
InsertLongInDouble,
ILID:
PROC [source: Long, container: BitDWord, fieldPosition, fieldWidth:
NAT, containerWidth:
NAT ← bitsPerDWord]
RETURNS [newContainer: BitDWord];
ExtractLongFQuad,
ELFQ:
PROC [container: BitQWord, fieldPosition, fieldWidth:
NAT, containerWidth:
NAT ← bitsPerQWord]
RETURNS [result: Long];
InsertLongInQuad,
ILIQ:
PROC [source: Long, container: BitQWord, fieldPosition, fieldWidth:
NAT, containerWidth:
NAT ← bitsPerQWord]
RETURNS [newContainer: BitQWord];
ExtractLongFMultiple,
ELFM:
PROC [container: BitMWord, fieldPosition, fieldWidth, containerWidth:
NAT]
RETURNS [result: Long];
InsertLongInMultiple,
ILIM:
PROC [source: Long, container: BitMWord, fieldPosition, fieldWidth, containerWidth:
NAT];
Handy operations for containers
WordAND,
WAND:
PROC [op1, op2: BitWord]
RETURNS [result: BitWord];
WordOR,
WOR:
PROC [op1, op2: BitWord]
RETURNS [result: BitWord];
WordXOR,
WXOR:
PROC [op1, op2: BitWord]
RETURNS [result: BitWord];
WordNOT,
WNOT:
PROC [op: BitWord, containerWidth:
NAT ← bitsPerWord]
RETURNS [result: BitWord];
WordShift,
WShift:
PROC [op: BitWord, shift:
INTEGER, containerWidth:
NAT ← bitsPerWord]
RETURNS [result: BitWord];
DoubleAND,
DAND:
PROC [op1, op2: BitDWord]
RETURNS [result: BitDWord];
DoubleOR,
DOR:
PROC [op1, op2: BitDWord]
RETURNS [result: BitDWord];
DoubleXOR,
DXOR:
PROC [op1, op2: BitDWord]
RETURNS [result: BitDWord];
DoubleNOT,
DNOT:
PROC [op: BitDWord, containerWidth:
NAT ← bitsPerDWord]
RETURNS [result: BitDWord];
DoubleShift,
DShift:
PROC [op: BitDWord, shift:
INTEGER, containerWidth:
NAT ← bitsPerDWord]
RETURNS [result: BitDWord];
QuadAND,
QAND:
PROC [op1, op2: BitQWord]
RETURNS [result: BitQWord];
QuadOR,
QOR:
PROC [op1, op2: BitQWord]
RETURNS [result: BitQWord];
QuadXOR,
QXOR:
PROC [op1, op2: BitQWord]
RETURNS [result: BitQWord];
QuadNOT,
QNOT:
PROC [op: BitQWord, containerWidth:
NAT ← bitsPerQWord]
RETURNS [result: BitQWord];
QuadShift,
QShift:
PROC [op: BitQWord, shift:
INTEGER, containerWidth:
NAT ← bitsPerQWord]
RETURNS [result: BitQWord];
MulitipleAND,
MAND:
PROC [op1: BitMWord, op2: BitMWord, result: BitMWord];
MulitipleOR,
MOR:
PROC [op1: BitMWord, op2: BitMWord, result: BitMWord];
MulitipleXOR,
MXOR:
PROC [op1: BitMWord, op2: BitMWord, result: BitMWord];
MulitipleNOT,
MNOT:
PROC [op: BitMWord, containerWidth:
NAT, result: BitMWord];
MulitipleShift,
MShift:
PROC [op: BitMWord, shift:
INTEGER, containerWidth:
NAT, result: BitMWord];
Masking Arrays
wordMasks: ARRAY [0 .. bitsPerWord] OF BitWord;
doubleMasks: ARRAY [0 .. bitsPerDWord] OF BitDWord;
quadMasks:
ARRAY [0 .. bitsPerQWord]
OF BitQWord;
Indexed by number of right-justified ones
END.