BitTwiddlingImpl:
CEDAR
PROGRAM
IMPORTS PrincOpsUtils
EXPORTS BitTwiddling
= {OPEN BitTwiddling;
WordPtr: TYPE = LONG POINTER TO CARDINAL;
disableCopy: BOOL ← FALSE;
Copy:
PUBLIC
PROC [from, to: Ptr, bitCount:
NAT, bbTable: PrincOps.BitBltTablePtr] =
TRUSTED {
lineWidth: NAT ← PrincOpsUtils.BITAND[(bitCount+31), WORD.LAST-31];
bbTable^ ← [
dst: to,
dstBpl: lineWidth,
src: from,
srcDesc: [srcBpl[lineWidth]],
width: bitCount,
height: 1,
flags: []];
IF NOT disableCopy THEN PrincOpsUtils.BITBLT[bbTable];
bitCount ← bitCount;
from ← from;
};
maskAll: CARDINAL ← LAST[CARDINAL];
Equal:
PUBLIC
PROC [p1, p2: Ptr, bitCount:
NAT]
RETURNS [equal:
BOOL] =
TRUSTED {
IF p1.bit = p2.bit
THEN {
mask: CARDINAL ← zeroFirst[p1.bit];
wordCount: NAT ← (p1.bit + bitCount-1)/Basics.bitsPerWord + 1;
wp1: WordPtr ← LOOPHOLE[p1.word];
wp2: WordPtr ← LOOPHOLE[p2.word];
FOR i:
NAT
IN [1 .. wordCount]
DO
IF i = wordCount THEN mask ← PrincOpsUtils.BITAND[mask, lastMasks[(p1.bit + bitCount) MOD Basics.bitsPerWord]];
IF 0 # PrincOpsUtils.BITAND[mask, PrincOpsUtils.BITXOR[wp1^, wp2^]] THEN RETURN [FALSE];
mask ← maskAll;
wp1 ← wp1 + 1;
wp2 ← wp2 + 1;
ENDLOOP;
}
ELSE {
mask: CARDINAL ← zeroFirst[p2.bit];
wordCount2: NAT ← (p2.bit + bitCount-1)/Basics.bitsPerWord + 1;
wp1: WordPtr ← LOOPHOLE[p1.word];
wp2: WordPtr ← LOOPHOLE[p2.word];
residue: CARDINAL ← 0;
rightPart, leftPart: INTEGER;
SELECT
TRUE
FROM
p1.bit > p2.bit => {
rightPart ← p1.bit - p2.bit;
residue ← PrincOpsUtils.BITSHIFT[wp1^, rightPart];
wp1 ← wp1 + 1;
};
p1.bit < p2.bit => {
rightPart ← p1.bit + Basics.bitsPerWord - p2.bit;
residue ← 0;
};
ENDCASE => ERROR;
leftPart ← rightPart - Basics.bitsPerWord;
FOR i:
NAT
IN [1 .. wordCount2]
DO
w1: CARDINAL ← wp1^;
repacked: CARDINAL;
IF i = wordCount2
THEN {
lastBits: NAT = altRem[(p2.bit + bitCount) MOD Basics.bitsPerWord];
mask ← PrincOpsUtils.BITAND[mask, oneFirst[lastBits]];
IF lastBits > -leftPart THEN w1 ← wp1^;
}
ELSE w1 ← wp1^;
repacked ← PrincOpsUtils.BITOR[residue, PrincOpsUtils.BITSHIFT[w1, leftPart]];
IF 0 # PrincOpsUtils.BITAND[mask, PrincOpsUtils.BITXOR[repacked, wp2^]] THEN RETURN [FALSE];
residue ← PrincOpsUtils.BITSHIFT[w1, rightPart];
mask ← maskAll;
wp1 ← wp1 + 1;
wp2 ← wp2 + 1;
ENDLOOP;
};
equal ← TRUE;
};
PtrFromRef:
PUBLIC
PROC [r:
REF
ANY]
RETURNS [p: Ptr] =
TRUSTED {p ← [word: LOOPHOLE[r], bit: 0]};
PtrFromPOINTER:
PUBLIC
PROC [p:
LONG
POINTER]
RETURNS [q: Ptr] =
TRUSTED {q ← [word: p, bit: 0]};
DeReferencePtr:
PUBLIC
PROC [p: Ptr]
RETURNS [q: Ptr] =
TRUSTED {
IF p.bit # 0 THEN ERROR;
q ← [
word: LOOPHOLE[p.word, LONG POINTER TO LONG POINTER]^,
bit: 0];
};
OffsetPtr:
PUBLIC
PROC [p: Ptr, bits:
INT]
RETURNS [q: Ptr] =
TRUSTED {
bo: INT ← bits + p.bit;
dw: INT;
bit: NAT;
[dw, bit] ← FloorDivMod[bo, Basics.bitsPerWord];
q ← [word: p.word + dw, bit: bit];
};
FloorDivMod:
PROC [num:
INT, den:
NAT]
RETURNS [quot:
INT, rem:
INTEGER] = {
quot ← num/den;
rem ← num - quot*den;
IF rem < 0 THEN {rem ← rem + den; quot ← quot - 1};
};
}.