diff options
Diffstat (limited to 'lib/system/sets.nim')
| -rw-r--r-- | lib/system/sets.nim | 28 |
1 files changed, 7 insertions, 21 deletions
diff --git a/lib/system/sets.nim b/lib/system/sets.nim index 42c448848..97431c296 100644 --- a/lib/system/sets.nim +++ b/lib/system/sets.nim @@ -9,34 +9,20 @@ # set handling -type - NimSet = array[0..4*2048-1, uint8] -# bitops can't be imported here, therefore the code duplication. - -proc countBits32(n: uint32): int {.compilerproc.} = - # generic formula is from: https://graphics.stanford.edu/~seander/bithacks.html#CountBitsSetParallel - var v = uint32(n) - v = v - ((v shr 1'u32) and 0x55555555'u32) - v = (v and 0x33333333'u32) + ((v shr 2'u32) and 0x33333333'u32) - result = (((v + (v shr 4'u32) and 0xF0F0F0F'u32) * 0x1010101'u32) shr 24'u32).int - -proc countBits64(n: uint64): int {.compilerproc, inline.} = - # generic formula is from: https://graphics.stanford.edu/~seander/bithacks.html#CountBitsSetParallel - var v = uint64(n) - v = v - ((v shr 1'u64) and 0x5555555555555555'u64) - v = (v and 0x3333333333333333'u64) + ((v shr 2'u64) and 0x3333333333333333'u64) - v = (v + (v shr 4'u64) and 0x0F0F0F0F0F0F0F0F'u64) - result = ((v * 0x0101010101010101'u64) shr 56'u64).int - -proc cardSet(s: NimSet, len: int): int {.compilerproc, inline.} = +proc cardSetImpl(s: ptr UncheckedArray[uint8], len: int): int {.inline.} = var i = 0 result = 0 + var num = 0'u64 when defined(x86) or defined(amd64): while i < len - 8: - inc(result, countBits64((cast[ptr uint64](s[i].unsafeAddr))[])) + copyMem(addr num, addr s[i], 8) + inc(result, countBits64(num)) inc(i, 8) while i < len: inc(result, countBits32(uint32(s[i]))) inc(i, 1) + +proc cardSet(s: ptr UncheckedArray[uint8], len: int): int {.compilerproc, inline.} = + result = cardSetImpl(s, len) |