BitOpsImpl.mesa
Copyright Ó 1986, 1987 by Xerox Corporation. All rights reserved.
Barth, April 23, 1987 5:03:33 pm PDT
Spreitzer, September 17, 1985 1:12:52 pm PDT
Gasbarro October 27, 1986 2:43:55 pm PST
Last Edited by: Gasbarro October 27, 1986 5:11:26 pm PST
Bertrand Serlet March 28, 1987 11:49:01 pm PST
DIRECTORY Basics, BitOps;
BitOpsImpl: CEDAR PROGRAM IMPORTS Basics EXPORTS BitOps =
BEGIN OPEN Basics, BitOps;
WordAsBits: TYPE = PACKED ARRAY [0..LastWBit] OF BOOL;
DWordM: TYPE = ARRAY [0 .. 2) OF CARDINAL;
LongAsWords: TYPE = MACHINE DEPENDENT RECORD [
low: CARDINAL,
high: CARDINAL];
Goodies
powersOfTwo: ARRAY [0 .. 33] OF INT = [
1B, 2B, 4B, 1B1, 2B1, 4B1,
1B2, 2B2, 4B2, 1B3, 2B3, 4B3,
1B4, 2B4, 4B4, 1B5, 2B5, 4B5,
1B6, 2B6, 4B6, 1B7, 2B7, 4B7,
1B8, 2B8, 4B8, 1B8, 2B8, 4B8,
1B9, 2B9, 4B9, 1B10];
ODD: PUBLIC PROC [i: INT] RETURNS [BOOL] =
{RETURN [Basics.OddInt[i]]};
EVEN: PUBLIC PROC [i: INT] RETURNS [BOOL] =
{RETURN [NOT Basics.OddInt[i]]};
Log2: PUBLIC PROC [n: INT] RETURNS [INT] = {
IF n<=0 THEN RETURN [0];
FOR i: NAT IN [0..33] DO
IF n<powersOfTwo[i] THEN RETURN [i-1];
REPEAT
FINISHED => ERROR;
ENDLOOP;
};
NBits: PUBLIC PROC [n: INT] RETURNS [INT] = {
IF n<=0 THEN RETURN [0];
IF n=1 THEN RETURN [1];
FOR i: NAT IN [1..33] DO
IF powersOfTwo[i]>=n THEN RETURN [i];
REPEAT
FINISHED => ERROR;
ENDLOOP;
};
TwoToThe: PUBLIC PROC [x: INT] RETURNS [INT] =
{RETURN[powersOfTwo[x]]};
TwoToTheLog2: PUBLIC PROC [n: INT] RETURNS [INT] =
{RETURN [TwoToThe[Log2[n]]]};
Bools
ExtractBoolFWord, EBFW: PUBLIC PROC [container: BitWord, bitPosition: NAT, containerWidth: NAT ← bitsPerWord] RETURNS [result: BOOL] = {
t:WordAsBits ← LOOPHOLE[container];
IF containerWidth>bitsPerWord OR bitPosition>(containerWidth-1) THEN ERROR;
RETURN[t[bitPosition+bitsPerWord-containerWidth]];
};
InsertBoolInWord, IBIW: PUBLIC PROC [source: BOOL, container: BitWord, bitPosition: NAT, containerWidth: NAT ← bitsPerWord] RETURNS [newContainer: BitWord] = {
t:WordAsBits ← LOOPHOLE[container];
IF containerWidth>bitsPerWord OR bitPosition>(containerWidth-1) THEN ERROR;
t[bitPosition+bitsPerWord-containerWidth] ← source;
RETURN[LOOPHOLE[t]];
};
ToDWordM: PUBLIC PROC [container: BitDWord] RETURNS [result: DWordM] = TRUSTED {
result ← LOOPHOLE[Basics.SwapHalves[LOOPHOLE[container]]];
};
ToBitDWord: PUBLIC PROC [container: DWordM] RETURNS [result: BitDWord] = TRUSTED {
result ← LOOPHOLE[Basics.SwapHalves[LOOPHOLE[container]]];
};
ExtractBoolFDouble, EBFD: PUBLIC PROC [container: BitDWord, bitPosition: NAT, containerWidth: NAT ← bitsPerDWord] RETURNS [result: BOOL] = TRUSTED {
swapped: DWordM ← ToDWordM[container];
result ← EBFM[DESCRIPTOR[swapped], bitPosition, containerWidth];
};
InsertBoolInDouble, IBID: PUBLIC PROC [source: BOOL, container: BitDWord, bitPosition: NAT, containerWidth: NAT ← bitsPerDWord] RETURNS [newContainer: BitDWord] = TRUSTED {
swapped: DWordM ← ToDWordM[container];
IBIM[source, DESCRIPTOR[swapped], bitPosition, containerWidth];
newContainer ← ToBitDWord[swapped];
};
ExtractBoolFQuad, EBFQ: PUBLIC PROC [container: BitQWord, bitPosition: NAT, containerWidth: NAT ← bitsPerQWord] RETURNS [result: BOOL] = TRUSTED {
result ← EBFM[DESCRIPTOR[container], bitPosition, containerWidth]
};
InsertBoolInQuad, IBIQ: PUBLIC PROC [source: BOOL, container: BitQWord, bitPosition: NAT, containerWidth: NAT ← bitsPerQWord] RETURNS [newContainer: BitQWord] = TRUSTED {
newContainer ← container;
IBIM[source, DESCRIPTOR[newContainer], bitPosition, containerWidth]
};
ExtractBoolFMultiple, EBFM: PUBLIC PROC [container: BitMWord, bitPosition: NAT, containerWidth: NAT] RETURNS [result: BOOL] = TRUSTED {
pos: CARDINAL ← bitPosition+LENGTH[container]*bitsPerWord-containerWidth;
word: CARDINAL ← pos/bitsPerWord;
IF word>=LENGTH[container] THEN ERROR;
RETURN[EBFW[container[word], pos MOD bitsPerWord, bitsPerWord]];
};
InsertBoolInMultiple, IBIM: PUBLIC PROC [source: BOOL, container: BitMWord, bitPosition: NAT, containerWidth: NAT] = TRUSTED {
pos: CARDINAL ← bitPosition+LENGTH[container]*bitsPerWord-containerWidth;
word: CARDINAL ← pos/bitsPerWord;
IF word >= LENGTH[container] THEN ERROR;
container[word] ← IBIW[source, container[word], pos MOD bitsPerWord, bitsPerWord];
};
Cardinals
ExtractCardinalFWord, ECFW: PUBLIC PROC [container: BitWord, fieldPosition, fieldWidth: NAT, containerWidth: NAT ← bitsPerWord] RETURNS [result: CARDINAL] = {
shift: INTEGER ← INTEGER[fieldPosition] + fieldWidth - containerWidth;
IF containerWidth > bitsPerWord OR shift > 0 THEN ERROR;
RETURN[BITAND[BITSHIFT[container, shift], wordMasks[fieldWidth]]];
};
InsertCardinalInWord, ICIW: PUBLIC PROC [source: CARDINAL, container: BitWord, fieldPosition, fieldWidth: NAT, containerWidth: NAT ← bitsPerWord] RETURNS [newContainer: BitWord] = {
shift: INTEGER ← INTEGER[containerWidth] - (fieldPosition+fieldWidth);
mask: CARDINAL ← BITSHIFT[wordMasks[fieldWidth], shift];
IF containerWidth > bitsPerWord OR shift < 0 THEN ERROR;
RETURN[BITOR[BITAND[mask, BITSHIFT[source, shift]], BITAND[BITNOT[mask], container]]];
};
ExtractCardinalFDouble, ECFD: PUBLIC PROC [container: BitDWord, fieldPosition, fieldWidth: NAT, containerWidth: NAT ← bitsPerDWord] RETURNS [result: CARDINAL] = TRUSTED {
swapped: DWordM ← ToDWordM[container];
result ← ECFM[DESCRIPTOR[swapped], fieldPosition, fieldWidth, containerWidth]
};
InsertCardinalInDouble, ICID: PUBLIC PROC [source: CARDINAL, container: BitDWord, fieldPosition, fieldWidth: NAT, containerWidth: NAT ← bitsPerDWord] RETURNS [newContainer: BitDWord] = TRUSTED {
swapped: DWordM ← ToDWordM[container];
ICIM[source, DESCRIPTOR[swapped], fieldPosition, fieldWidth, containerWidth];
newContainer ← ToBitDWord[swapped];
};
ExtractCardinalFQuad, ECFQ: PUBLIC PROC [container: BitQWord, fieldPosition, fieldWidth: NAT, containerWidth: NAT ← bitsPerQWord] RETURNS [result: CARDINAL] = TRUSTED {
result ← ECFM[DESCRIPTOR[container], fieldPosition, fieldWidth, containerWidth]
};
InsertCardinalInQuad, ICIQ: PUBLIC PROC [source: CARDINAL, container: BitQWord, fieldPosition, fieldWidth: NAT, containerWidth: NAT ← bitsPerQWord] RETURNS [newContainer: BitQWord] = TRUSTED {
newContainer ← container;
ICIM[source, DESCRIPTOR[newContainer], fieldPosition, fieldWidth, containerWidth]
};
ExtractCardinalFMultiple, ECFM: PUBLIC PROC [container: BitMWord, fieldPosition, fieldWidth, containerWidth: NAT] RETURNS [result: CARDINAL] = TRUSTED {
containerSize: INTEGER ← LENGTH[container] * bitsPerWord;
endBit: INTEGER = (containerSize - containerWidth) + fieldPosition + fieldWidth-1;
endWord: INTEGER = endBit/bitsPerWord;
lowWidth: INTEGER = (endBit MOD bitsPerWord) + 1;
IF INTEGER[containerWidth]>containerSize OR fieldPosition+fieldWidth>containerWidth THEN ERROR;
result ← BITSHIFT[container[endWord], lowWidth-bitsPerWord];
IF lowWidth < INTEGER[fieldWidth] THEN result ← BITOR[BITSHIFT[container[endWord-1], lowWidth], result];
result ← BITAND[result, wordMasks[fieldWidth]];
};
InsertCardinalInMultiple, ICIM: PUBLIC PROC [source: CARDINAL, container: BitMWord, fieldPosition, fieldWidth, containerWidth: NAT] = TRUSTED {
containerSize: INTEGER ← LENGTH[container] * bitsPerWord;
endBit: INTEGER = (containerSize - containerWidth) + fieldPosition + fieldWidth-1;
endWord: INTEGER = endBit/bitsPerWord;
lowWidth: INTEGER = (endBit MOD bitsPerWord) + 1;
lowShift: INTEGER = bitsPerWord - lowWidth;
IF INTEGER[containerWidth]>containerSize OR fieldPosition+fieldWidth>containerWidth THEN ERROR;
container[endWord] ← BITOR[
BITSHIFT[source, lowShift],
BITAND[
BITNOT[BITSHIFT[wordMasks[fieldWidth], lowShift]],
container[endWord]]];
IF lowWidth < INTEGER[fieldWidth] THEN container[endWord-1] ← BITOR[
BITSHIFT[source, -lowWidth],
BITAND[
BITNOT[BITSHIFT[wordMasks[fieldWidth], -lowWidth]],
container[endWord-1]]];
};
Longs
ExtractLongFWord, ELFW: PUBLIC PROC [container: BitWord, fieldPosition, fieldWidth: NAT, containerWidth: NAT ← bitsPerWord] RETURNS [result: Long] = {
result ← ECFW[container, fieldPosition, fieldWidth, containerWidth]
};
InsertLongInWord, ILIW: PUBLIC PROC [source: Long, container: BitWord, fieldPosition, fieldWidth: NAT, containerWidth: NAT ← bitsPerWord] RETURNS [newContainer: BitWord] = {
newContainer ← ICIW[LowHalf[source], container, fieldPosition, fieldWidth, containerWidth]
};
ExtractLongFDouble, ELFD: PUBLIC PROC [container: BitDWord, fieldPosition, fieldWidth: NAT, containerWidth: NAT ← bitsPerDWord] RETURNS [result: Long] = TRUSTED {
swapped: DWordM ← ToDWordM[container];
result ← ELFM[DESCRIPTOR[swapped], fieldPosition, fieldWidth, containerWidth];
};
InsertLongInDouble, ILID: PUBLIC PROC [source: Long, container: BitDWord, fieldPosition, fieldWidth: NAT, containerWidth: NAT ← bitsPerDWord] RETURNS [newContainer: BitDWord] = TRUSTED {
swapped: DWordM ← ToDWordM[container];
ILIM[source, DESCRIPTOR[swapped], fieldPosition, fieldWidth, containerWidth];
newContainer ← ToBitDWord[swapped];
};
ExtractLongFQuad, ELFQ: PUBLIC PROC [container: BitQWord, fieldPosition, fieldWidth: NAT, containerWidth: NAT ← bitsPerQWord] RETURNS [result: Long] = TRUSTED {
result ← ELFM[DESCRIPTOR[container], fieldPosition, fieldWidth, containerWidth]
};
InsertLongInQuad, ILIQ: PUBLIC PROC [source: Long, container: BitQWord, fieldPosition, fieldWidth: NAT, containerWidth: NAT ← bitsPerQWord] RETURNS [newContainer: BitQWord] = TRUSTED {
newContainer ← container;
ILIM[source, DESCRIPTOR[newContainer], fieldPosition, fieldWidth, containerWidth]
};
ExtractLongFMultiple, ELFM: PUBLIC PROC [container: BitMWord, fieldPosition, fieldWidth, containerWidth: NAT] RETURNS [result: Long] = {
IF fieldWidth <= bitsPerWord THEN RETURN [ECFM[container, fieldPosition, fieldWidth, containerWidth]]
ELSE TRUSTED {
law: LongAsWords;
rem: CARDINAL = fieldWidth - bitsPerWord;
law.high ← ECFM[container, fieldPosition, rem, containerWidth];
law.low ← ECFM[container, fieldPosition+rem, bitsPerWord, containerWidth];
result ← LOOPHOLE[law]
};
};
InsertLongInMultiple, ILIM: PUBLIC PROC [source: Long, container: BitMWord, fieldPosition, fieldWidth, containerWidth: NAT] = {
IF fieldWidth <= bitsPerWord THEN ICIM[source, container, fieldPosition, fieldWidth, containerWidth]
ELSE TRUSTED {
law: LongAsWords ← LOOPHOLE[source];
rem: CARDINAL = fieldWidth - bitsPerWord;
ICIM[law.high, container, fieldPosition, rem, containerWidth];
ICIM[law.low, container, fieldPosition+rem, bitsPerWord, containerWidth]
};
};
Handy operations for containers
WordAND, WAND: PUBLIC PROC [op1, op2: BitWord] RETURNS [result: BitWord] =
{result ← BITAND[op1, op2]};
WordOR, WOR: PUBLIC PROC [op1, op2: BitWord] RETURNS [result: BitWord] =
{result ← BITOR[op1, op2]};
WordXOR, WXOR: PUBLIC PROC [op1, op2: BitWord] RETURNS [result: BitWord] =
{result ← BITXOR[op1, op2]};
WordNOT, WNOT: PUBLIC PROC [op: BitWord, containerWidth: NAT ← bitsPerWord] RETURNS [result: BitWord] =
{result ← BITAND[wordMasks[containerWidth], BITNOT[op]]};
WordShift, WShift: PUBLIC PROC [op: BitWord, shift: INTEGER, containerWidth: NAT ← bitsPerWord] RETURNS [result: BitWord] =
{result ← BITAND[wordMasks[containerWidth], BITSHIFT[op, shift]]};
DoubleAND, DAND: PUBLIC PROC [op1, op2: BitDWord] RETURNS [result: BitDWord] = {
result ← LOOPHOLE[Basics.DoubleAnd[LOOPHOLE[op1], LOOPHOLE[op2]]];
};
DoubleOR, DOR: PUBLIC PROC [op1, op2: BitDWord] RETURNS [result: BitDWord] = {
result ← LOOPHOLE[Basics.DoubleOr[LOOPHOLE[op1], LOOPHOLE[op2]]];
};
DoubleXOR, DXOR: PUBLIC PROC [op1, op2: BitDWord] RETURNS [result: BitDWord] =
{
result ← LOOPHOLE[Basics.DoubleXor[LOOPHOLE[op1], LOOPHOLE[op2]]];
};
DoubleNOT, DNOT: PUBLIC PROC [op: BitDWord, containerWidth: NAT ← bitsPerDWord] RETURNS [result: BitDWord] = {
result ← LOOPHOLE[Basics.DoubleNot[LOOPHOLE[op]]];
result ← DAND[result, doubleMasks[containerWidth]];
};
DoubleShift, DShift: PUBLIC PROC [op: BitDWord, shift: INTEGER, containerWidth: NAT ← bitsPerDWord] RETURNS [result: BitDWord] = TRUSTED {
result ← LOOPHOLE[Basics.DoubleShift[LOOPHOLE[op], shift]];
result ← DAND[result, doubleMasks[containerWidth]];
};
QuadAND, QAND: PUBLIC PROC [op1, op2: BitQWord] RETURNS [result: BitQWord] = TRUSTED {
MAND[DESCRIPTOR[op1], DESCRIPTOR[op2], DESCRIPTOR[result]];
};
QuadOR, QOR: PUBLIC PROC [op1, op2: BitQWord] RETURNS [result: BitQWord] = TRUSTED {
MOR[DESCRIPTOR[op1], DESCRIPTOR[op2], DESCRIPTOR[result]];
};
QuadXOR, QXOR: PUBLIC PROC [op1, op2: BitQWord] RETURNS [result: BitQWord] = TRUSTED {
MXOR[DESCRIPTOR[op1], DESCRIPTOR[op2], DESCRIPTOR[result]];
};
QuadNOT, QNOT: PUBLIC PROC [op: BitQWord, containerWidth: NAT ← bitsPerQWord] RETURNS [result: BitQWord] = TRUSTED {
MNOT[DESCRIPTOR[op], containerWidth, DESCRIPTOR[result]];
};
QuadShift, QShift: PUBLIC PROC [op: BitQWord, shift: INTEGER, containerWidth: NAT ← bitsPerQWord] RETURNS [result: BitQWord] = TRUSTED {
MShift[DESCRIPTOR[op], shift, containerWidth, DESCRIPTOR[result]];
};
MulitipleAND, MAND: PUBLIC PROC [op1: BitMWord, op2: BitMWord, result: BitMWord] = TRUSTED {
IF LENGTH[op1]#LENGTH[op2] OR LENGTH[op1]#LENGTH[result] THEN ERROR;
FOR i:CARDINAL IN [0..LENGTH[op1]) DO
result[i] ← BITAND[op1[i], op2[i]];
ENDLOOP;
};
MulitipleOR, MOR: PUBLIC PROC [op1: BitMWord, op2: BitMWord, result: BitMWord] = TRUSTED {
IF LENGTH[op1]#LENGTH[op2] OR LENGTH[op1]#LENGTH[result] THEN ERROR;
FOR i:CARDINAL IN [0..LENGTH[op1]) DO
result[i] ← BITOR[op1[i], op2[i]];
ENDLOOP;
};
MulitipleXOR, MXOR: PUBLIC PROC [op1: BitMWord, op2: BitMWord, result: BitMWord] = TRUSTED {
IF LENGTH[op1]#LENGTH[op2] OR LENGTH[op1]#LENGTH[result] THEN ERROR;
FOR i:CARDINAL IN [0..LENGTH[op1]) DO
result[i] ← BITXOR[op1[i], op2[i]];
ENDLOOP;
};
MulitipleNOT, MNOT: PUBLIC PROC [op: BitMWord, containerWidth: NAT, result: BitMWord] = TRUSTED {
IF LENGTH[op]#LENGTH[result] THEN ERROR;
FOR i:CARDINAL IN [0..LENGTH[op]) DO
result[i] ← BITNOT[op[i]];
ENDLOOP;
op[0] ← BITAND[op[0], wordMasks[containerWidth - (LENGTH[op] -1) * bitsPerWord]]
};
MulitipleShift, MShift: PUBLIC PROC [op: BitMWord, shift: INTEGER, containerWidth: NAT, result: BitMWord] = TRUSTED {
wordShift: CARDINAL ← ABS[shift] / bitsPerWord;
bitShift: INTEGER ← ABS[shift] MOD bitsPerWord;
IF LENGTH[op]#LENGTH[result] THEN ERROR;
SELECT shift FROM
>= LENGTH[op]*bitsPerWord, <= -LENGTH[op]*bitsPerWord =>
FOR i: CARDINAL IN [0..LENGTH[op]) DO result[i] ← 0 ENDLOOP;
=0 => FOR i:CARDINAL IN [0..LENGTH[op]) DO result[i] ← op[i] ENDLOOP;
<0 => {
FOR i: CARDINAL DECREASING IN (wordShift..LENGTH[op]-1] DO
result[i] ← BITOR[BITSHIFT[op[i-wordShift], bitShift], BITSHIFT[op[i-1-wordShift], bitsPerWord+bitShift]];
ENDLOOP;
result[wordShift] ← BITSHIFT[op[0], bitShift];
FOR i: CARDINAL IN [0..wordShift) DO result[i] ← 0 ENDLOOP};
>0 => {
FOR i:CARDINAL IN [0..LENGTH[op]-1-wordShift) DO
result[i] ← BITOR[BITSHIFT[op[i+wordShift], bitShift], BITSHIFT[op[i+1+wordShift], bitShift-bitsPerWord]];
ENDLOOP;
result[LENGTH[op]-1-wordShift] ← BITSHIFT[op[LENGTH[op]-1], bitShift];
FOR i: CARDINAL IN [LENGTH[op]-wordShift..LENGTH[op]) DO
result[i] ← 0 ENDLOOP};
ENDCASE;
result[0] ← BITAND[result[0], wordMasks[containerWidth - (LENGTH[op] -1) *bitsPerWord]]};
Masking Arrays
wordMasks: PUBLIC ARRAY [0 .. bitsPerWord] OF BitWord ← ALL[BitWordZero];
doubleMasks: PUBLIC ARRAY [0 .. bitsPerDWord] OF BitDWord ← ALL[BitDWordZero];
quadMasks: PUBLIC ARRAY [0 .. bitsPerQWord] OF BitQWord ← ALL[BitQWordZero];
InitArrays: PROC = {
{
n: BitWord ← BitWordOnes;
FOR i: NAT DECREASING IN [0 .. bitsPerWord] DO
wordMasks[i] ← n;
n ← WShift[n, -1];
ENDLOOP;
};
{
n: BitDWord ← BitDWordOnes;
FOR i: NAT DECREASING IN [0 .. bitsPerDWord] DO
doubleMasks[i] ← n;
n ← DShift[n, -1];
ENDLOOP;
};
{
n: BitQWord ← BitQWordOnes;
FOR i: NAT DECREASING IN [0 .. bitsPerQWord] DO
quadMasks[i] ← n;
n ← QShift[n, -1];
ENDLOOP;
};
};
InitArrays[];
END.