
    <<BitTwiddlingImpl.Mesa>>
<<Last Edited by: Spreitzer, September 26, 1985 8:08:46 pm PDT>>

    DIRECTORY Basics, BitTwiddling, PrincOps, PrincOpsUtils;

    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};
            };

        }.