diff options
Diffstat (limited to 'compiler/bitsets.nim')
| -rw-r--r-- | compiler/bitsets.nim | 106 |
1 files changed, 66 insertions, 40 deletions
diff --git a/compiler/bitsets.nim b/compiler/bitsets.nim index 5454ef5e7..7d142b01d 100644 --- a/compiler/bitsets.nim +++ b/compiler/bitsets.nim @@ -10,62 +10,88 @@ # this unit handles Nim sets; it implements bit sets # the code here should be reused in the Nim standard library +when defined(nimPreviewSlimSystem): + import std/assertions + type - TBitSet* = seq[int8] # we use byte here to avoid issues with + ElemType = byte + TBitSet* = seq[ElemType] # we use byte here to avoid issues with # cross-compiling; uint would be more efficient # however - const - ElemSize* = sizeof(int8) * 8 - -proc bitSetInit*(b: var TBitSet, length: int) -proc bitSetUnion*(x: var TBitSet, y: TBitSet) -proc bitSetDiff*(x: var TBitSet, y: TBitSet) -proc bitSetSymDiff*(x: var TBitSet, y: TBitSet) -proc bitSetIntersect*(x: var TBitSet, y: TBitSet) -proc bitSetIncl*(x: var TBitSet, elem: BiggestInt) -proc bitSetExcl*(x: var TBitSet, elem: BiggestInt) -proc bitSetIn*(x: TBitSet, e: BiggestInt): bool -proc bitSetEquals*(x, y: TBitSet): bool -proc bitSetContains*(x, y: TBitSet): bool -# implementation - -proc bitSetIn(x: TBitSet, e: BiggestInt): bool = - result = (x[int(e div ElemSize)] and toU8(int(1 shl (e mod ElemSize)))) != - toU8(0) - -proc bitSetIncl(x: var TBitSet, elem: BiggestInt) = + ElemSize* = 8 + One = ElemType(1) + Zero = ElemType(0) + +template modElemSize(arg: untyped): untyped = arg and 7 +template divElemSize(arg: untyped): untyped = arg shr 3 + +proc bitSetIn*(x: TBitSet, e: BiggestInt): bool = + result = (x[int(e.divElemSize)] and (One shl e.modElemSize)) != Zero + +proc bitSetIncl*(x: var TBitSet, elem: BiggestInt) = assert(elem >= 0) - x[int(elem div ElemSize)] = x[int(elem div ElemSize)] or - toU8(int(1 shl (elem mod ElemSize))) + x[int(elem.divElemSize)] = x[int(elem.divElemSize)] or + (One shl elem.modElemSize) -proc bitSetExcl(x: var TBitSet, elem: BiggestInt) = - x[int(elem div ElemSize)] = x[int(elem div ElemSize)] and - not toU8(int(1 shl (elem mod ElemSize))) +proc bitSetExcl*(x: var TBitSet, elem: BiggestInt) = + x[int(elem.divElemSize)] = x[int(elem.divElemSize)] and + not(One shl elem.modElemSize) -proc bitSetInit(b: var TBitSet, length: int) = +proc bitSetInit*(b: var TBitSet, length: int) = newSeq(b, length) -proc bitSetUnion(x: var TBitSet, y: TBitSet) = - for i in countup(0, high(x)): x[i] = x[i] or y[i] +proc bitSetUnion*(x: var TBitSet, y: TBitSet) = + for i in 0..high(x): x[i] = x[i] or y[i] -proc bitSetDiff(x: var TBitSet, y: TBitSet) = - for i in countup(0, high(x)): x[i] = x[i] and not y[i] +proc bitSetDiff*(x: var TBitSet, y: TBitSet) = + for i in 0..high(x): x[i] = x[i] and not y[i] -proc bitSetSymDiff(x: var TBitSet, y: TBitSet) = - for i in countup(0, high(x)): x[i] = x[i] xor y[i] +proc bitSetSymDiff*(x: var TBitSet, y: TBitSet) = + for i in 0..high(x): x[i] = x[i] xor y[i] -proc bitSetIntersect(x: var TBitSet, y: TBitSet) = - for i in countup(0, high(x)): x[i] = x[i] and y[i] +proc bitSetIntersect*(x: var TBitSet, y: TBitSet) = + for i in 0..high(x): x[i] = x[i] and y[i] -proc bitSetEquals(x, y: TBitSet): bool = - for i in countup(0, high(x)): +proc bitSetEquals*(x, y: TBitSet): bool = + for i in 0..high(x): if x[i] != y[i]: return false result = true -proc bitSetContains(x, y: TBitSet): bool = - for i in countup(0, high(x)): - if (x[i] and not y[i]) != int8(0): +proc bitSetContains*(x, y: TBitSet): bool = + for i in 0..high(x): + if (x[i] and not y[i]) != Zero: return false result = true + +# Number of set bits for all values of int8 +const populationCount: array[uint8, uint8] = block: + var arr: array[uint8, uint8] + + proc countSetBits(x: uint8): uint8 = + return + ( x and 0b00000001'u8) + + ((x and 0b00000010'u8) shr 1) + + ((x and 0b00000100'u8) shr 2) + + ((x and 0b00001000'u8) shr 3) + + ((x and 0b00010000'u8) shr 4) + + ((x and 0b00100000'u8) shr 5) + + ((x and 0b01000000'u8) shr 6) + + ((x and 0b10000000'u8) shr 7) + + + for it in low(uint8)..high(uint8): + arr[it] = countSetBits(cast[uint8](it)) + + arr + +proc bitSetCard*(x: TBitSet): BiggestInt = + result = 0 + for it in x: + result.inc int(populationCount[it]) + +proc bitSetToWord*(s: TBitSet; size: int): BiggestUInt = + result = 0 + for j in 0..<size: + if j < s.len: result = result or (BiggestUInt(s[j]) shl (j * 8)) |