Skip to content

Augment TBits.

Rika requested to merge runewalsh/source:bits into main

Looking at how most of TBits functions have no Delphi counterparts and were added in 5418b837, I wondered if I can propose my own.

  1. Find / FindRev / Find0 / Find0Rev / Find1 / Find1Rev that perform the same task as SetIndex / FindFirstBit / FindNextBit, but store no state inside TBits. This allows plain things impossible with current design: iterating cartesian product of a set with itself, or searching bits concurrently without synchronization.

  2. MoveRange that moves N bits from one bitfield to another, or to the same with overlap.

This also changes TBitsBase to unsigned type, because it suites bit operations better: subrange operations use a lot of arithmetics that constantly tries to sign-extend if TBitsBase is signed type smaller than native (let’s say you want it for some reason like debugging), requiring a lot of explicit casts.

  1. GetUint and SetUint that treat consecutive N bits as a number.

2+3 allow to interpret the bit field as a dynamic bitpacked array of numbers or structures. If the bitfield is an array of 100-bit records that have 4-bit x member at offset 20, reading x of ith record is bits.GetUint(100 * i + 20, 4), removing ith record out of n shifting everything above is bits.MoveRange({srcPos=}100 * (i + 1), {dstPos=}100 * i, {count=}100 * (n - i - 1)); bits.Size := bits.Size - 100;, and so on.

  1. Bitwise operations over ranges, similar to MoveRange (including support for overlapping) but doing Self[...] := Self[...] op B[...] instead of B[...] := A[...]: AndRange, OrRange, XorRange, AndNotRange, which are reduced to OpRange supporting any 2-input boolean function. Also 1-input NotRange.

OpRange uses VPTERNLOG-style encoding of arbitrary two-input boolean function as the last column of its truth table, from 0 to 15 (%1111). For example, A and not B,

A  B  | R
0  0  | 0
0  1  | 0
1  0  | 1
1  1  | 0

is encoded as %0100. Presently, non-trivial functions are implemented with a generic code that invokes (Base; Base): Base callback, and on my computer, such a callback is +33% (x86-32) to +133% (2.3×, x86-64) slower than hardcoding the function, but still hundreds of times faster than handling one bit at a time, and the underlying code is bulky enough to not want to duplicate it. At the same time, this form makes it easy for the implementation to hardcode common functions if it wants to, dispatching them with case functionCode of, as it already does with functions that don’t depend on both operands, e.g. redirecting %1100 (f(A, B) = A) to no-op and %1010 (f(A, B) = B) to MoveRange(B, A).

  1. ClearRange and SetRange that fill ranges with zeros/ones.

  2. PopCount that counts bits set, possibly breaking early on reaching the limit.

  3. IntersectionPopCount that counts bits set in the intersection (virtual result of AndRange), and HasIntersection that determines if there are any such bits. Maybe worth generalizing to OpPopCount, but I had no use cases beyond and so far ¯\_(ツ)_/¯.

4+7 allow to interpret the bit field as a grid whose cells are occupied or not, determine if other objects fit at certain points, place them and erase. Multidimensional functions are up to the user, but can now be reduced to these one-dimensional primitives.

  1. DumpBinary / LoadBinary that convert the bitfield into portable binary representation (essentially, to the bitfield with byte base type), and DumpText / LoadText that do the same with text (preferably with 1-byte characters, but in general supporting any strings for 0 and 1, as to get doubled characters like ## to draw 1:1 squares assuming 1:2 monospace character aspect ratio).

Merge request reports