mirror of
https://github.com/nim-lang/Nim.git
synced 2025-12-28 17:04:41 +00:00
816589b667
Theoretical Benefits / Plans: - Typed assembler-like language. - Allows for a CPS transformation. - Can replace the existing C backend by a new C backend. - Can replace the VM. - Can do more effective "not nil" checking and static array bounds checking. - Can be used instead of the DFA. - Easily translatable to LLVM. - Reasonably easy to produce native code from. - Tiny memory consumption. No pointers, no cry. **In very early stages of development.** Todo: - [x] Map Nim types to IR types. - [ ] Map Nim AST to IR instructions: - [x] Map bitsets to bitops. - [ ] Implement string cases. - [ ] Implement range and index checks. - [x] Implement `default(T)` builtin. - [x] Implement multi string concat. - [ ] Write some analysis passes. - [ ] Write a backend. - [x] Integrate into the compilation pipeline.
98 lines
2.7 KiB
Nim
98 lines
2.7 KiB
Nim
#
|
|
#
|
|
# The Nim Compiler
|
|
# (c) Copyright 2012 Andreas Rumpf
|
|
#
|
|
# See the file "copying.txt", included in this
|
|
# distribution, for details about the copyright.
|
|
#
|
|
|
|
# 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
|
|
ElemType = byte
|
|
TBitSet* = seq[ElemType] # we use byte here to avoid issues with
|
|
# cross-compiling; uint would be more efficient
|
|
# however
|
|
const
|
|
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.divElemSize)] = x[int(elem.divElemSize)] or
|
|
(One shl elem.modElemSize)
|
|
|
|
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) =
|
|
newSeq(b, length)
|
|
|
|
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 0..high(x): x[i] = x[i] and not 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 0..high(x): x[i] = x[i] and y[i]
|
|
|
|
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 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))
|