Skip to content

Better TBits.

Rika requested to merge runewalsh/source:tbits into main

First, TBits has a bug (I added a test tests/test/units/classes/ttbits:TestZeroUpper, among others): .SetSize (and .NotBits) can leave non-zeros above .Size. For example, truncating 10111 to 3 bits gives 101, and then resizing it to 6 bits gives 101110, resurrecting some 1s. (Delphi 7 does the same, but this is still a bug; see the first comment.)

Second, I made it use PtrInt base type, and SizeInt indices as in 13 years old idea voiced in 658dc2d8.

Third, I used some clever intrinsics. On my computer, FindFirstBit can be 50–150× faster on sparse bitfields, 3× on random, and still ~20% on almost-all-1s. Could be even faster, but at the cost of further complications, namely, manual reading FBits into a local, which is also applicable for bitwise operations, and splitting out first iterations of the Bsf/Bsr loops.

FR: deprecate SetIndex / FindFirstBit / FindNextBit / FindPrevBit and replace them with something like FindNextBit(start, value) / FindPrevBit(start, value) or Find0(start) / Find0Rev(start) / Find1(start) / Find1Rev(start) that accept start argument instead of storing the state inside TBits.

Edited by Rika

Merge request reports