Augment TBits.
Looking at how most of TBits
functions have no Delphi counterparts and were added in 5418b837, I wondered if I can propose my own.
-
Find / FindRev / Find0 / Find0Rev / Find1 / Find1Rev
that perform the same task asSetIndex / FindFirstBit / FindNextBit
, but store no state insideTBits
. This allows plain things impossible with current design: iterating cartesian product of a set with itself, or searching bits concurrently without synchronization. -
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.
-
GetUint
andSetUint
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 i
th record is bits.GetUint(100 * i + 20, 4)
, removing i
th 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.
- Bitwise operations over ranges, similar to
MoveRange
(including support for overlapping) but doingSelf[...] := Self[...] op B[...]
instead ofB[...] := A[...]
:AndRange, OrRange, XorRange, AndNotRange
, which are reduced toOpRange
supporting any 2-input boolean function. Also 1-inputNotRange
.
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)
.
-
ClearRange
andSetRange
that fill ranges with zeros/ones. -
PopCount
that counts bits set, possibly breaking early on reaching the limit. -
IntersectionPopCount
that counts bits set in the intersection (virtual result ofAndRange
), andHasIntersection
that determines if there are any such bits. Maybe worth generalizing toOpPopCount
, but I had no use cases beyondand
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.
-
DumpBinary / LoadBinary
that convert the bitfield into portable binary representation (essentially, to the bitfield withbyte
base type), andDumpText / 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).