dymokomi/luce-geocore
Source of release 0.7.2
0.7.2 / src / core / bits.lucb
## Bit sets over elements: groups, selections and group-expression results.
## Bit i is bit i % 64 of word i / 64, which is also the byte layout of a
## boolean attribute's column on little-endian targets, so a group attribute
## is read as words without conversion. Bits past `count` are always zero.
## Whole-set operations run a word at a time, in parallel for large sets.
import memory
from luce_std import parallel
from core.shared import Column
import core.ranges
## Words above this count split across the pool.
let parallel_words: usize = 16384
## Words that hold `count` bits.
pub func word_count(count: usize) -> usize:
return (count + 63) // 64
## A read-only view of a bit set; valid while its column is.
pub struct Bits:
## The bits, 64 to a word.
pub let words: const u64[]
## How many bits there are.
pub let count: usize
## A view of a column of `count` bits (a boolean attribute's bytes or a
## Column[u64]); the column must hold whole words.
pub static func of_bytes(bytes: const u8[], count: usize) -> Bits:
return Bits(u64[]((u64*)bytes.data, word_count(count)), count)
## Whether bit `at` is set.
pub func get(at: usize) -> bool:
return (self.words[at >> 6] >> (u64)(at & 63)) & 1 != 0
## How many bits are set.
pub func population() -> usize:
var total: usize = 0
for word in self.words: total += (usize)popcount(word)
return total
## Whether any bit is set.
pub func any() -> bool:
for word in self.words:
if word != 0: return true
return false
## The set bits' indices, ascending, into `out` (which holds population()).
pub func indices(out: i64[]):
var at: usize = 0
for index in 0..<self.words.length:
var word = self.words[index]
while word != 0:
let bit = (usize)trailing_zeros(word)
out[at] = (i64)(index * 64 + bit)
at += 1
word = word & (word - 1)
## Bits being built: a private column until `finish` publishes it.
pub struct BitsBuilder:
## The words, private until `finish`.
pub var column: Column[u64]
## How many bits there are.
pub var count: usize
## `count` bits, none set.
pub static func zeros(count: usize) -> BitsBuilder!:
var column = try Column[u64].allocate(word_count(count))
let words = column.span()
if words.length > 0: memory.set(u8[]((u8*)words.data, words.length * 8), 0)
return BitsBuilder(column, count)
## `count` bits, all set.
pub static func ones(count: usize) -> BitsBuilder!:
var built = try BitsBuilder.zeros(count)
built.set_range(0, count)
return built
## A private copy of `bits`.
pub static func copy_of(bits: Bits) -> BitsBuilder!:
var column = try Column[u64].copy_of(bits.words)
return BitsBuilder(column, bits.count)
## The words, writable.
pub func words() -> u64[]:
return self.column.span()
## A read-only view of the bits so far.
pub func view() -> Bits:
return Bits(self.column.view(), self.count)
## Set bit `at`.
pub func set(at: usize):
let words = self.column.span()
words[at >> 6] = words[at >> 6] | ((u64)1 << (u64)(at & 63))
## Clear bit `at`.
pub func clear(at: usize):
let words = self.column.span()
words[at >> 6] = words[at >> 6] & ~((u64)1 << (u64)(at & 63))
## Set bits first..<end, a word at a time.
pub func set_range(first: usize, end: usize):
if end <= first: return
let words = self.column.span()
var at = first
while at < end and at & 63 != 0:
words[at >> 6] = words[at >> 6] | ((u64)1 << (u64)(at & 63))
at += 1
while at + 64 <= end:
words[at >> 6] = ~(u64)0
at += 64
while at < end:
words[at >> 6] = words[at >> 6] | ((u64)1 << (u64)(at & 63))
at += 1
## Set every `step`-th bit of first..<end, keeping `keep` of each step
## (Houdini's `a-b:keep,step`).
pub func set_stride(first: usize, end: usize, keep: usize, step: usize):
if step <= 1 or keep >= step:
self.set_range(first, end)
return
var at = first
while at < end:
let stop = at + keep if end - at > keep else end
self.set_range(at, stop)
if end - at <= step: return
at += step
## This = this ∪ other.
pub func unite(other: Bits):
self.combine(other, 0)
## This = this minus other.
pub func subtract(other: Bits):
self.combine(other, 1)
## This = this ∩ other.
pub func intersect(other: Bits):
self.combine(other, 2)
## This = this ∪ ¬other (`!pattern` in a group expression).
pub func unite_complement(other: Bits):
self.combine(other, 3)
## Flip every bit below `count`.
pub func invert():
var nothing: u64[1]
self.combine(Bits(nothing[..<0], self.count), 4)
func combine(other: Bits, operation: u8):
var work = CombineWork(self.column.span(), other.words, operation, self.count)
ranges.each_range(work.target.length, parallel_words, (void*)&work, combine_words)
## Publish: the column becomes immutable. The builder keeps nothing.
pub func finish() -> Column[u64]:
let column = self.column
var empty: Column[u64]
self.column = empty
return column
## Release the column (unless finished).
pub func close():
self.column.release()
struct CombineWork:
let target: u64[]
let other: const u64[]
let operation: u8
let count: usize
func combine_words(context: void*, first: usize, end: usize, worker: usize):
let work = (CombineWork*)context
let last = work.target.length - 1
let tail: u64 = ~(u64)0 if work.count & 63 == 0 else ((u64)1 << (u64)(work.count & 63)) - 1
for at in first..<end:
let value = work.other[at] if at < work.other.length else 0
var result = work.target[at]
match work.operation:
0: result = result | value
1: result = result & ~value
2: result = result & value
3: result = result | ~value
_: result = ~result
# Bits past the count stay zero.
work.target[at] = result & tail if at == last else result
## The number of set bits in a word.
pub func popcount(word: u64) -> u32:
var value = word -% ((word >> 1) & 0x5555555555555555)
value = (value & 0x3333333333333333) +% ((value >> 2) & 0x3333333333333333)
value = (value +% (value >> 4)) & 0x0F0F0F0F0F0F0F0F
return (u32)((value *% 0x0101010101010101) >> 56)
## The index of the lowest set bit of a nonzero word.
pub func trailing_zeros(word: u64) -> u32:
return popcount((word & -%word) -% 1)