<<>>
    <<BasicsImpl.mesa>>
        <<Copyright Ó 1985, 1986, 1990, 1991, 1992 by Xerox Corporation.  All rights reserved.>>
        <<JKF August 26, 1988 10:49:27 am PDT>>
        <<Russ Atkinson (RRA) April 19, 1990 9:58 pm PDT>>
        <<Willie-s, March 5, 1992 3:52 pm PST>>
        <<Michael Plass, April 9, 1993 1:25 pm PDT>>
        <<Doug Wyatt, August 27, 1991 4:38 pm PDT>>
        <<>>
    DIRECTORY Basics;

    BasicsImpl: CEDAR PROGRAM 
    IMPORTS Basics
    = BEGIN OPEN Basics;

<<External Names>>
    ExternalNames: PROC [] = TRUSTED MACHINE CODE  {
    "^ExternalNames\n";
    "CopyWords Basics_CopyWords\n";
    "MoveWords Basics_MoveWords\n"; -- may be assembly-coded - see below
    "FillWords Basics_FillWords\n"; -- may be assembly-coded - see below
    "CopyBytes Basics_CopyBytes\n";
    "MoveBytes Basics_MoveBytes\n";
    "FillBytes Basics_FillBytes\n";
    "CopyBits  Basics_CopyBits \n";
    "MoveBits  Basics_MoveBits \n";
    "FillBits  Basics_FillBits \n";
    "CompareBits  Basics_CompareBits\n";
    "ByteBlt Basics_ByteBlt\n";
    "BITSHIFT Basics_BITSHIFT\n";
    "CopyBitsDecreasing  Basics_CopyBitsDecreasing \n";
    "RegisterLogMisalign Basics_RegisterLogMisalign\n";
        };

    assemblyMoveAndFillWords: BOOL ~ AssemblyMoveAndFillWords[];
    AssemblyMoveAndFillWords: PROC [] RETURNS [BOOL] = TRUSTED MACHINE CODE  {
        <<This crockery allows the assembly-coded versions of these routines to be used in lieu of the Mesa versions; we don't assume that 
        such routines are available on all architecures.>>
        "*#ifdef sparc\n";
        "#define AssemblyMoveAndFillWordsHelp() 1\n";
        "#define Basics_MoveWords Basics_MoveWords_Soft\n";
        "#define Basics_FillWords Basics_FillWords_Soft\n";
        "#else\n";
        "#define AssemblyMoveAndFillWordsHelp() 0\n";
        "#endif\n";
        ".AssemblyMoveAndFillWordsHelp";
        };

<<Support for bit-oriented block operations>>
    bpw: NAT ~ BITS[WORD];
    BitOff: TYPE = [0..bpw);
    BitCount: TYPE = [0..bpw];

    WordsForBits: PROC [bits: CARD] RETURNS [CARD] ~ INLINE {
        RETURN [CARD[bits+(bpw-1)]/bpw]
        };

    RightJustifiedOnes: PROC [n: BitCount] RETURNS [WORD] ~ INLINE {
        RETURN [BITLSHIFT[1, n MOD bpw] - 1 - n/bpw]
        };

    RightJustifiedZeros: PROC [n: BitOff] RETURNS [WORD] ~ INLINE {
        RETURN [-BITRSHIFT[2**(bpw-1), (bpw-1)-n]]
        };

    StartingWord: PROC [base: POINTER TO RawBits, bitIndex: CARD] RETURNS [POINTER TO RawWords] ~ TRUSTED INLINE {
        RETURN [LOOPHOLE[base, POINTER] + (UNITS[WORD]*(bitIndex/bpw))]
        };

    MF: PROC [d, s, mask: WORD] RETURNS [WORD] ~ INLINE {
        <<Replaces bits of d with s under the mask.>>
        RETURN [BITXOR[BITAND[BITXOR[s, d], mask], d]]
        };

<<Block word operations>>
    CopyWords: UNSAFE PROC [
    dst: POINTER TO RawWords, 
    src: POINTER TO RawWords, 
    count: CARDINAL] ~ { 
        FOR i: CARDINAL IN [0..count) DO
            TRUSTED { dst[i] Ź src[i] };
            ENDLOOP;
        };

    MoveWords: UNSAFE PROC [
    dst: POINTER TO RawWords, 
    src: POINTER TO RawWords, 
    count: CARDINAL] ~ { 
        IF LOOPHOLE[dst, CARD]<LOOPHOLE[src, CARD]
            THEN {
                FOR i: CARDINAL IN[0..count) DO
                    TRUSTED { dst[i] Ź src[i] };
                    ENDLOOP;
                }
            ELSE {
                FOR i: CARDINAL DECREASING IN[0..count) DO
                    TRUSTED { dst[i] Ź src[i] };
                    ENDLOOP;
                };
        };

    FillWords: UNSAFE PROC [
    dst: POINTER TO RawWords, 
    count: CARDINAL, value: WORD] ~ UNCHECKED { 
        p: LONG POINTER TO ARRAY [0..4) OF WORD Ź LOOPHOLE[dst];
        WHILE count >= 4 DO
            p[0] Ź value;
            p[1] Ź value;
            p[2] Ź value;
            p[3] Ź value;
            p Ź p + SIZE[ARRAY [0..4) OF WORD];
            count Ź count - 4;
            ENDLOOP;
        IF count = 0 THEN RETURN;
        p[0] Ź value;
        IF count = 1 THEN RETURN;
        p[1] Ź value;
        IF count = 2 THEN RETURN;
        p[2] Ź value;
        };
<<Block byte operations>>
    CopyBytes: UNSAFE PROC [
    dstBase: POINTER TO RawBytes, dstStart: CARD, 
    srcBase: POINTER TO RawBytes, srcStart: CARD, 
    count: CARDINAL] ~ TRUSTED { 
        IF count>(CARD.LAST-dstStart) THEN RaiseBoundsFault[];
        IF count>(CARD.LAST-srcStart) THEN RaiseBoundsFault[];
        IF count>= 2**(BITS[WORD]-BITS[BYTE]) THEN RaiseBoundsFault[];
        CopyBits[
            dstBase: LOOPHOLE[dstBase], dstStart: dstStart*BITS[BYTE],
            srcBase: LOOPHOLE[srcBase], srcStart: srcStart*BITS[BYTE],
            count: count*BITS[BYTE]
            ];
        };

    MoveBytes: UNSAFE PROC [
    dstBase: POINTER TO RawBytes, dstStart: CARD, 
    srcBase: POINTER TO RawBytes, srcStart: CARD, 
    count: CARDINAL] ~ { 
        d0: CARD ~ LOOPHOLE[dstBase, CARD]*BYTES[UNIT]+dstStart;
        s0: CARD ~ LOOPHOLE[srcBase, CARD]*BYTES[UNIT]+srcStart;
        IF count>(CARD.LAST-dstStart) THEN RaiseBoundsFault[];
        IF count>(CARD.LAST-srcStart) THEN RaiseBoundsFault[];
        IF count>= 2**(BITS[WORD]-BITS[BYTE]) THEN RaiseBoundsFault[];
        IF d0 IN (s0 .. s0+count)
            THEN { -- bad overlap 
                FOR i: CARDINAL DECREASING IN[0..count) DO
                    TRUSTED { dstBase[dstStart+i] Ź srcBase[srcStart+i] };
                    ENDLOOP;
                }
            ELSE TRUSTED {
                CopyBits[
                    dstBase: LOOPHOLE[dstBase], dstStart: dstStart*BITS[BYTE],
                    srcBase: LOOPHOLE[srcBase], srcStart: srcStart*BITS[BYTE],
                    count: count*BITS[BYTE]
                    ];
                };
        };

    FillBytes: UNSAFE PROC [
    dstBase: POINTER TO RawBytes, dstStart: CARD, 
    count: CARDINAL, value: BYTE] ~ CHECKED { 
        wordValue: CARD Ź value + 100H*value;
        wordValue Ź wordValue + 10000H*wordValue;
        TRUSTED {
            FillBits[
                dstBase: LOOPHOLE[dstBase], dstStart: dstStart*BITS[BYTE],
                count: count*BITS[BYTE], value: wordValue
                ];
            };
        };
<<Misalignment Logging>>
    <<This is a hook to allow detection and logging of misaligned arguments to the block-oriented procedures, using, for example, Spy.>>
    logMisalign: PROC Ź NIL;
    RegisterLogMisalign: PROC [p: PROC] ~ {
        logMisalign Ź p;
        };
<<Block bit operations>>
    CopyBits: UNSAFE PROC [
    dstBase: POINTER TO RawBits, dstStart: CARD, 
    srcBase: POINTER TO RawBits, srcStart: CARD, 
    count: CARDINAL] ~ CHECKED { 
        dstCorr: CARD ~ LOOPHOLE[dstBase, CARD] MOD UNITS[WORD];
        srcCorr: CARD ~ LOOPHOLE[srcBase, CARD] MOD UNITS[WORD];
        IF dstCorr+srcCorr # 0 THEN {
            p: PROC Ź logMisalign;
            IF p # NIL THEN p[];
            dstBase Ź dstBase - dstCorr;
            dstStart Ź dstStart + BITS[UNIT]*dstCorr;
            srcBase Ź srcBase - srcCorr;
            srcStart Ź srcStart + BITS[UNIT]*srcCorr;
            };
        IF count # 0 THEN {
            dst: POINTER TO RawWords Ź StartingWord[dstBase, dstStart];
            dstBit: BitOff ~ dstStart MOD bpw;
            src: POINTER TO RawWords Ź StartingWord[srcBase, srcStart];
            srcBit: BitOff ~ srcStart MOD bpw;
            ndw: CARD ~ WordsForBits[dstBit + count];
            lMask: WORD ~ RightJustifiedOnes[bpw-dstBit];
                <<mask for the leftmost dest word (ones where bits are to go)>>
            rMask: WORD ~ RightJustifiedZeros[(LOOPHOLE[bpw-dstBit-count, CARD]) MOD bpw];
                <<mask for the rightmost dest word>>
            IF dstBit = srcBit
                THEN { -- Aligned case is simpler
                    SELECT ndw FROM
                        1 => TRUSTED {
                            dst[0] Ź MF[dst[0], src[0], BITAND[lMask, rMask]];
                            };
                        2 => TRUSTED {
                            dst[0] Ź MF[dst[0], src[0], lMask];
                            dst[1] Ź MF[dst[1], src[1], rMask];
                            };
                        3 => TRUSTED {
                            dst[0] Ź MF[dst[0], src[0], lMask];
                            dst[1] Ź  src[1];
                            dst[2] Ź MF[dst[2], src[2], rMask];
                            };
                        ENDCASE => TRUSTED {
                            nw: CARD Ź LOOPHOLE[ndw-2, CARD];
                            dst[0] Ź MF[dst[0], src[0], lMask];
                            dst Ź dst+UNITS[WORD];
                            src Ź src+UNITS[WORD];
                            WHILE nw >= 4 DO
                                dst[0] Ź src[0];
                                dst[1] Ź src[1];
                                dst[2] Ź src[2];
                                dst[3] Ź src[3];
                                dst Ź dst+UNITS[WORD]*4;
                                src Ź src+UNITS[WORD]*4;
                                nw Ź nw - 4;
                                ENDLOOP;
                            IF nw >= 2 THEN {
                                dst[0] Ź src[0];
                                dst[1] Ź src[1];
                                dst Ź dst+SIZE[WORD]*2;
                                src Ź src+SIZE[WORD]*2;
                                nw Ź nw - 2;
                                };
                            IF nw # 0 THEN {
                                dst[0] Ź  src[0];
                                dst Ź dst+SIZE[WORD];
                                src Ź src+SIZE[WORD];
                                };
                            dst[0] Ź MF[dst[0], src[0], rMask];
                            };
                    }
                ELSE { -- Unaligned case.
                    w: WORD Ź 0; -- source word, aligned with destination
                    hi: WORD; -- left unshifted source word
                    lo: WORD Ź 0; -- right unshifted source word
                    lSA: BitOff = LOOPHOLE[srcBit-dstBit, CARDINAL] MOD bpw; -- left shift amount
                    rSA: BitOff = LOOPHOLE[bpw - lSA, CARDINAL] MOD bpw; -- amount to shift source words right to line them up
                    nsw: CARD = WordsForBits[srcBit + count];
                    fetchLastWord: BOOL ~ IF srcBit >= dstBit THEN (nsw>ndw) ELSE (nsw>=ndw);
                        <<true if last source word needs to be fetched>>
                    FetchNext: PROC ~ INLINE {
                        <<fetches the next aligned source bits, and bumps source pointer>>
                        hi Ź lo;
                        TRUSTED {lo Ź src[0]};
                        src Ź src+SIZE[WORD];
                        w Ź BITLSHIFT[hi, lSA]+BITRSHIFT[lo, rSA]
                        };
                    FetchNextOff: PROC [wordOffset: CARD] ~ INLINE {
                        <<fetches the next word at the given offset, no pointer change>>
                        hi Ź lo;
                        TRUSTED {lo Ź src[wordOffset]};
                        w Ź BITLSHIFT[hi, lSA]+BITRSHIFT[lo, rSA]
                        };
                    FetchLast: PROC [wordOffset: CARD, fetch: BOOL] ~ INLINE {
                        <<fetches the final source bits on a line, avoiding a spurious fetch>>
                        w Ź BITLSHIFT[lo, lSA];
                        IF fetch THEN TRUSTED {w Ź w + BITRSHIFT[src[wordOffset], rSA]};
                        };
                    IF srcBit >= dstBit THEN FetchNext[];
                    SELECT ndw FROM
                        1 => TRUSTED {
                            bothMask: WORD ~ BITAND[lMask, rMask];
                            FetchLast[0, fetchLastWord];
                            dst[0] Ź MF[dst[0], w, bothMask];
                            };
                        2 => TRUSTED {
                            FetchNextOff[0];
                            dst[0] Ź MF[dst[0], w, lMask];
                            FetchLast[1, fetchLastWord];
                            dst[1] Ź MF[dst[1], w, rMask];
                            };
                        3 => TRUSTED {
                            FetchNextOff[0];
                            dst[0] Ź MF[dst[0], w, lMask];
                            FetchNextOff[1];
                            dst[1] Ź  w;
                            FetchLast[2, fetchLastWord];
                            dst[2] Ź MF[dst[2], w, rMask];
                            };
                        ENDCASE => TRUSTED {
                            nw: CARD Ź LOOPHOLE[ndw-2, CARD];
                            FetchNextOff[0];
                            dst[0] Ź MF[dst[0], w, lMask];
                            dst Ź dst+SIZE[WORD];
                            src Ź src+SIZE[WORD];
                            WHILE nw >= 2 DO
                                FetchNextOff[0];
                                dst[0] Ź  w;
                                FetchNextOff[1];
                                dst[1] Ź  w;
                                dst Ź dst+SIZE[WORD]*2;
                                src Ź src+SIZE[WORD]*2;
                                nw Ź nw - 2;
                                ENDLOOP;
                            IF nw # 0 THEN {
                                FetchNextOff[0];
                                dst[0] Ź  w;
                                dst Ź dst+SIZE[WORD];
                                src Ź src+SIZE[WORD];
                                };
                            FetchLast[0, fetchLastWord];
                            dst[0] Ź MF[dst[0], w, rMask];
                            };
                    };
            };
        };

    CopyBitsDecreasing: UNSAFE PROC [
    dstBase: POINTER TO RawBits, dstStart: CARD, 
    srcBase: POINTER TO RawBits, srcStart: CARD, 
    count: CARDINAL] ~ CHECKED { 
        dstCorr: CARD ~ LOOPHOLE[dstBase, CARD] MOD UNITS[WORD];
        srcCorr: CARD ~ LOOPHOLE[srcBase, CARD] MOD UNITS[WORD];
        IF dstCorr+srcCorr # 0 THEN {
            p: PROC Ź logMisalign;
            IF p # NIL THEN p[];
            dstBase Ź dstBase - dstCorr;
            dstStart Ź dstStart + BITS[UNIT]*dstCorr;
            srcBase Ź srcBase - srcCorr;
            srcStart Ź srcStart + BITS[UNIT]*srcCorr;
            };
        IF count # 0 THEN {
            dst: POINTER TO RawWords Ź StartingWord[dstBase, dstStart];
            dstBit: BitOff ~ dstStart MOD bpw;
            src: POINTER TO RawWords Ź StartingWord[srcBase, srcStart];
            srcBit: BitOff ~ srcStart MOD bpw;
            ndw: CARD ~ WordsForBits[dstBit + count];
            lMask: WORD ~ RightJustifiedOnes[bpw-dstBit];
                <<mask for the leftmost dest word (ones where bits are to go)>>
            rMask: WORD ~ RightJustifiedZeros[(LOOPHOLE[bpw-dstBit-count, CARD]) MOD bpw];
                <<mask for the rightmost dest word>>
            IF dstBit = srcBit
                THEN { -- Aligned case is simpler
                    SELECT ndw FROM
                        1 => TRUSTED {
                            dst[0] Ź MF[dst[0], src[0], BITAND[lMask, rMask]];
                            };
                        2 => TRUSTED {
                            dst[1] Ź MF[dst[1], src[1], rMask];
                            dst[0] Ź MF[dst[0], src[0], lMask];
                            };
                        3 => TRUSTED {
                            dst[2] Ź MF[dst[2], src[2], rMask];
                            dst[1] Ź  src[1];
                            dst[0] Ź MF[dst[0], src[0], lMask];
                            };
                        ENDCASE => TRUSTED {
                            nw: CARD Ź LOOPHOLE[ndw-2, CARD];
                            dst Ź dst+ndw*UNITS[WORD] - UNITS[WORD];
                            src Ź src+ndw*UNITS[WORD] - UNITS[WORD];
                            dst[0] Ź MF[dst[0], src[0], rMask];
                            WHILE nw >= 4 DO
                                dst Ź dst-UNITS[WORD]*4;
                                src Ź src-UNITS[WORD]*4;
                                dst[3] Ź src[3];
                                dst[2] Ź src[2];
                                dst[1] Ź src[1];
                                dst[0] Ź src[0];
                                nw Ź nw - 4;
                                ENDLOOP;
                            IF nw >= 2 THEN {
                                dst Ź dst-UNITS[WORD]*2;
                                src Ź src-UNITS[WORD]*2;
                                dst[1] Ź src[1];
                                dst[0] Ź src[0];
                                nw Ź nw - 2;
                                };
                            IF nw # 0 THEN {
                                dst Ź dst-UNITS[WORD];
                                src Ź src-UNITS[WORD];
                                dst[0] Ź src[0];
                                };
                            dst Ź dst-UNITS[WORD];
                            src Ź src-UNITS[WORD];
                            dst[0] Ź MF[dst[0], src[0], lMask];
                            };
                    }
                ELSE { -- Unaligned case.
                    w: WORD Ź 0; -- source word, aligned with destination
                    hi: WORD Ź 0; -- left unshifted source word
                    lo: WORD; -- right unshifted source word
                    lSA: BitOff = LOOPHOLE[srcBit-dstBit, CARDINAL] MOD bpw; -- left shift amount
                    rSA: BitOff = LOOPHOLE[bpw - lSA, CARDINAL] MOD bpw; -- amount to shift source words right to line them up
                    nsw: CARD = WordsForBits[srcBit + count];
                    fetchLeftmost: BOOL ~ srcBit >= dstBit;
                    fetchRightmost: BOOL ~ IF fetchLeftmost THEN (nsw>ndw) ELSE (nsw>=ndw);
                    FetchNext: PROC ~ INLINE {
                        <<fetches the next aligned source bits, and bumps source pointer>>
                        lo Ź hi;
                        TRUSTED {hi Ź src[0]};
                        src Ź src-UNITS[WORD];
                        w Ź BITLSHIFT[hi, lSA]+BITRSHIFT[lo, rSA]
                        };
                    FetchLast: PROC ~ INLINE {
                        <<fetches the last (leftmost) source bits on a line, avoiding a spurious fetch>>
                        lo Ź hi;
                        IF fetchLeftmost THEN TRUSTED {hi Ź src[0]} ELSE hi Ź 0;
                        w Ź BITLSHIFT[hi, lSA]+BITRSHIFT[lo, rSA]
                        };
                    src Ź src + nsw*UNITS[WORD] - UNITS[WORD];
                    IF fetchRightmost THEN FetchNext[];
                    SELECT ndw FROM
                        1 => TRUSTED {
                            bothMask: WORD ~ BITAND[lMask, rMask];
                            FetchLast[];
                            dst[0] Ź MF[dst[0], w, bothMask];
                            };
                        2 => TRUSTED {
                            FetchNext[];
                            dst[1] Ź MF[dst[1], w, rMask];
                            FetchLast[];
                            dst[0] Ź MF[dst[0], w, lMask];
                            };
                        3 => TRUSTED {
                            FetchNext[];
                            dst[2] Ź MF[dst[2], w, rMask];
                            FetchNext[];
                            dst[1] Ź w;
                            FetchLast[];
                            dst[0] Ź MF[dst[0], w, lMask];
                            };
                        ENDCASE => TRUSTED {
                            nw: CARD Ź LOOPHOLE[ndw-2, CARD];
                            FetchNext[];
                            dst Ź dst + ndw*UNITS[WORD] - UNITS[WORD];
                            dst[0] Ź MF[dst[0], w, rMask];
                            WHILE nw >= 2 DO
                                dst Ź dst-UNITS[WORD]*2;
                                FetchNext[];
                                dst[1] Ź w;
                                FetchNext[];
                                dst[0] Ź w;
                                nw Ź nw - 2;
                                ENDLOOP;
                            IF nw # 0 THEN {
                                dst Ź dst-UNITS[WORD];
                                FetchNext[];
                                dst[0] Ź w;
                                };
                            dst Ź dst-UNITS[WORD];
                            FetchLast[];
                            dst[0] Ź MF[dst[0], w, lMask];
                            };
                    };
            };
        };

    MoveBits: UNSAFE PROC [
    dstBase: POINTER TO RawBits, dstStart: CARD, 
    srcBase: POINTER TO RawBits, srcStart: CARD, 
    count: CARDINAL] ~ CHECKED {
        d0: CARD ~ LOOPHOLE[dstBase, CARD]*BITS[UNIT]+dstStart;
        s0: CARD ~ LOOPHOLE[srcBase, CARD]*BITS[UNIT]+srcStart;
        IF d0 IN (s0 .. s0+count)
            THEN { -- bad overlap.  This is a pretty slow impl right now...
                FOR i: CARDINAL DECREASING IN [0..count) DO
                    TRUSTED { dstBase[dstStart+i] Ź srcBase[srcStart+i] };
                    ENDLOOP;
                }
            ELSE TRUSTED {
                CopyBits[dstBase: dstBase, dstStart: dstStart, srcBase: srcBase, srcStart: srcStart, count: count];
                };
        };

    FillBits: UNSAFE PROC [
    dstBase: POINTER TO RawBits, dstStart: CARD, 
    count: CARDINAL, value: WORD] ~ CHECKED {
    <<NOTE: A better name might be PatternFillBits, since the value is a whole word of bits rather than a single bit.>>
        dstCorr: CARD ~ LOOPHOLE[dstBase, CARD] MOD UNITS[WORD];
        IF dstCorr # 0 THEN {
            p: PROC Ź logMisalign;
            IF p # NIL THEN p[];
            dstBase Ź dstBase - dstCorr;
            dstStart Ź dstStart + BITS[UNIT]*dstCorr;
            };
        IF count # 0 THEN {
            dst: POINTER TO RawWords Ź StartingWord[dstBase, dstStart];
            dstBit: BitOff ~ dstStart MOD bpw;
            ndw: CARD ~ WordsForBits[dstBit + count];
            lMask: WORD ~ RightJustifiedOnes[bpw-dstBit];
                <<mask for the leftmost dest word (ones where bits are to go)>>
            rMask: WORD ~ RightJustifiedZeros[(LOOPHOLE[bpw-dstBit-count, CARD]) MOD bpw];
                <<mask for the rightmost dest word>>
            SELECT ndw FROM
                1 => TRUSTED {
                    dst[0] Ź MF[dst[0], value, BITAND[lMask, rMask]];
                    };
                2 => TRUSTED {
                    dst[0] Ź MF[dst[0], value, lMask];
                    dst[1] Ź MF[dst[1], value, rMask];
                    };
            ENDCASE => TRUSTED {
                nw: CARD Ź LOOPHOLE[ndw-2, CARD];
                dst[0] Ź MF[dst[0], value, lMask];
                dst Ź dst+UNITS[WORD];
                WHILE nw >= 4 DO
                    dst[0] Ź value;
                    dst[1] Ź value;
                    dst[2] Ź value;
                    dst[3] Ź value;
                    dst Ź dst+UNITS[WORD]*4;
                    nw Ź nw - 4;
                    ENDLOOP;
                IF nw >= 2 THEN {
                    dst[0] Ź value;
                    dst[1] Ź value;
                    dst Ź dst+UNITS[WORD]*2;
                    nw Ź nw - 2;
                    };
                IF nw # 0 THEN {
                    dst[0] Ź  value;
                    dst Ź dst+SIZE[WORD];
                    };
                dst[0] Ź MF[dst[0], value, rMask];
                };
            };
        };

    CompareBits: UNSAFE PROC [
    aBase: POINTER TO RawBits, aStart: CARD, 
    bBase: POINTER TO RawBits, bStart: CARD, 
    count: CARDINAL] RETURNS [Comparison] ~ CHECKED {
        aCorr: CARD ~ LOOPHOLE[aBase, CARD] MOD UNITS[WORD];
        bCorr: CARD ~ LOOPHOLE[aBase, CARD] MOD UNITS[WORD];
        IF aCorr+bCorr # 0 THEN {
            p: PROC Ź logMisalign;
            IF p # NIL THEN p[];
            aBase Ź aBase - aCorr;
            aStart Ź aStart + BITS[UNIT]*aCorr;
            bBase Ź bBase - bCorr;
            bStart Ź bStart + BITS[UNIT]*bCorr;
            };
        IF count # 0 THEN {
            a: POINTER TO RawWords Ź StartingWord[aBase, aStart];
            aBit: BitOff ~ aStart MOD bpw;
            b: POINTER TO RawWords Ź StartingWord[bBase, bStart];
            bBit: BitOff ~ bStart MOD bpw;
            ndw: CARD ~ WordsForBits[aBit + count];
            lMask: WORD ~ RightJustifiedOnes[bpw-aBit];
                <<mask for the leftmost dest word (ones where bits are to go)>>
            rMask: WORD ~ RightJustifiedZeros[(LOOPHOLE[bpw-aBit-count, CARD]) MOD bpw];
                <<mask for the rightmost dest word>>
            aWord: WORD Ź 0;
            bWord: WORD Ź 0;
            X: PROC [aW, bW, m: WORD] ~ INLINE {
                aWord Ź BITAND[aW, m];
                bWord Ź BITAND[bW, m];
                };
            Y: PROC [aW, bW: WORD] ~ INLINE { aWord Ź aW; bWord Ź bW };
            {
                IF aBit = bBit
                    THEN { -- Aligned case is simpler
                        SELECT ndw FROM
                            1 => TRUSTED {
                                X[a[0], b[0], BITAND[lMask, rMask]]; IF aWord # bWord THEN GOTO Differ;
                                };
                            2 => TRUSTED {
                                X[a[0], b[0], lMask]; IF aWord # bWord THEN GOTO Differ;
                                X[a[1], b[1], rMask]; IF aWord # bWord THEN GOTO Differ;
                                };
                            3 => TRUSTED {
                                X[a[0], b[0], lMask]; IF aWord # bWord THEN GOTO Differ;
                                Y[a[1], b[1]]; IF aWord # bWord THEN GOTO Differ;
                                X[a[2], b[2], rMask]; IF aWord # bWord THEN GOTO Differ;
                                };
                            ENDCASE => TRUSTED {
                                nw: CARD Ź LOOPHOLE[ndw-2, CARD];
                                X[a[0], b[0], lMask]; IF aWord # bWord THEN GOTO Differ;
                                a Ź a+UNITS[WORD];
                                b Ź b+UNITS[WORD];
                                WHILE nw >= 2 DO
                                    Y[a[0], b[0]]; IF aWord # bWord THEN GOTO Differ;
                                    Y[a[1], b[1]]; IF aWord # bWord THEN GOTO Differ;
                                    a Ź a+SIZE[WORD]*2;
                                    b Ź b+SIZE[WORD]*2;
                                    nw Ź nw - 2;
                                    ENDLOOP;
                                IF nw # 0 THEN {
                                    Y[a[0], b[0]]; IF aWord # bWord THEN GOTO Differ;
                                    a Ź a+SIZE[WORD];
                                    b Ź b+SIZE[WORD];
                                    };
                                X[a[0], b[0], rMask]; IF aWord # bWord THEN GOTO Differ;
                                };
                        }
                    ELSE { -- Unaligned case.
                        w: WORD Ź 0; -- source word, aligned with destination
                        hi: WORD; -- left unshifted source word
                        lo: WORD Ź 0; -- right unshifted source word
                        lSA: BitOff = LOOPHOLE[bBit-aBit, CARDINAL] MOD bpw; -- left shift amount
                        rSA: BitOff = LOOPHOLE[bpw - lSA, CARDINAL] MOD bpw; -- amount to shift source words right to line them up
                        nsw: CARD = WordsForBits[bBit + count];
                        fetchLastWord: BOOL ~ IF bBit >= aBit THEN (nsw>ndw) ELSE (nsw>=ndw);
                            <<true if last source word needs to be fetched>>
                        FetchNext: PROC ~ INLINE {
                            <<fetches the next aligned source bits, and bumps source pointer>>
                            hi Ź lo;
                            TRUSTED {lo Ź b[0]};
                            b Ź b+SIZE[WORD];
                            w Ź BITLSHIFT[hi, lSA]+BITRSHIFT[lo, rSA]
                            };
                        FetchNextOff: PROC [wordOffset: CARD] ~ INLINE {
                            <<fetches the next word at the given offset, no pointer change>>
                            hi Ź lo;
                            TRUSTED {lo Ź b[wordOffset]};
                            w Ź BITLSHIFT[hi, lSA]+BITRSHIFT[lo, rSA]
                            };
                        FetchLast: PROC [wordOffset: CARD, fetch: BOOL] ~ INLINE {
                            <<fetches the final source bits on a line, avoiding a spurious fetch>>
                            w Ź BITLSHIFT[lo, lSA];
                            IF fetch THEN TRUSTED {w Ź w + BITRSHIFT[b[wordOffset], rSA]};
                            };
                        IF bBit >= aBit THEN FetchNext[];
                        SELECT ndw FROM
                            1 => TRUSTED {
                                bothMask: WORD ~ BITAND[lMask, rMask];
                                FetchLast[0, fetchLastWord];
                                X[a[0], w, bothMask]; IF aWord # bWord THEN GOTO Differ;
                                };
                            2 => TRUSTED {
                                FetchNextOff[0];
                                X[a[0], w, lMask]; IF aWord # bWord THEN GOTO Differ;
                                FetchLast[1, fetchLastWord];
                                X[a[1], w, rMask]; IF aWord # bWord THEN GOTO Differ;
                                };
                            3 => TRUSTED {
                                FetchNextOff[0];
                                X[a[0], w, lMask]; IF aWord # bWord THEN GOTO Differ;
                                FetchNextOff[1];
                                Y[a[1], w]; IF aWord # bWord THEN GOTO Differ;
                                FetchLast[2, fetchLastWord];
                                X[a[2], w, rMask]; IF aWord # bWord THEN GOTO Differ;
                                };
                            ENDCASE => TRUSTED {
                                nw: CARD Ź LOOPHOLE[ndw-2, CARD];
                                FetchNextOff[0];
                                X[a[0], w, lMask]; IF aWord # bWord THEN GOTO Differ;
                                a Ź a+SIZE[WORD];
                                b Ź b+SIZE[WORD];
                                WHILE nw >= 2 DO
                                    FetchNextOff[0];
                                    Y[a[0], w]; IF aWord # bWord THEN GOTO Differ;
                                    FetchNextOff[1];
                                    Y[a[1], w]; IF aWord # bWord THEN GOTO Differ;
                                    a Ź a+SIZE[WORD]*2;
                                    b Ź b+SIZE[WORD]*2;
                                    nw Ź nw - 2;
                                    ENDLOOP;
                                IF nw # 0 THEN {
                                    FetchNextOff[0];
                                    Y[a[0], w]; IF aWord # bWord THEN GOTO Differ;
                                    a Ź a+SIZE[WORD];
                                    b Ź b+SIZE[WORD];
                                    };
                                FetchLast[0, fetchLastWord];
                                X[a[0], w, rMask]; IF aWord # bWord THEN GOTO Differ;
                                };
                        };
                EXITS Differ => {IF aWord < bWord THEN RETURN [less] ELSE RETURN [greater]};
                };
            };
        RETURN [equal];
        };

<<Shifts>>
    BITSHIFT: PROC [value: WORD, count: INTEGER] RETURNS [WORD] ~ {
        c: [0..bitsPerWord);
        c Ź LOOPHOLE[count, CARDINAL] MOD bitsPerWord;
        IF count = c THEN RETURN [BITLSHIFT[value, c]];
        count Ź -count;
        c Ź LOOPHOLE[count, CARDINAL] MOD bitsPerWord;
        IF count = c THEN RETURN [BITRSHIFT[value, c]];
        RETURN [0]
        };
<<ByteBlt (compatibility).>>
    ByteBlt: UNSAFE PROC [to, from: ByteBltBlock] RETURNS [nBytes: CARDINAL] ~ { 
        nBytes Ź MIN[
            MAX[to.startIndex, to.stopIndexPlusOne] - to.startIndex,
            MAX[from.startIndex, from.stopIndexPlusOne] - from.startIndex
            ];
        TRUSTED{MoveBytes[to.blockPointer, to.startIndex, from.blockPointer, from.startIndex, nBytes]};
        };

    ExternalNames[];

    END.