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