How to compare two packed bitfields without having to unpack each field (2019)
devblogs.microsoft.com
devblogs.microsoft.com
This was used in a fast 4 sample player where it could do math on four 8 bit wave table indices all in one 32 bit operation on the 68000. I had forgotten the details so this was a nice reminder of how it must have worked. I would otherwise have to disassemble it since source no longer exists. Speed was necessary since it was for the Atari ST and the work was done in an interrupt which was quite frequent and it was important to keep the overhead as minimal as possibe.
But in any case you can compare the Chip Tune version of the title in Test Drive I vs the MOD player style tune in II
compare: ;; lhs in eax, rhs in ebx
mov ecx, 0b11111011111101111
pdep eax, eax, ecx
pdep ebx, ebx, ecx
sub eax, ebx
test eax, 0b10000010000001000
mov eax, 0
setnz al
retNaive version, best case: [481.40 ps 487.84 ps 494.56 ps]
Naive version, mid case: [751.56 ps 758.84 ps 766.17 ps]
Naive version, worst case: [953.71 ps 970.95 ps 994.65 ps]
Packed bitfield version: [685.98 ps 698.25 ps 711.57 ps]
So on average, the naive version and packed bitfield versions are within 10% of one another. Modern CPUs frequently don't benefit much from these kinds of tricks anymore.
auto c = ((~x & y) | (~(x ^ y) & (x - y));
c &= 0x8410;
return c == 0;
Couldn't this be written equivalently as
auto c = x ^ y ^ (x - y);
c &= 0x10820;
They never really say in the article.
And, the function as a whole is much more vectoriseable - if its in an inner loop, the compiler ought to be able to inline it and autovectorise the loop.
bool IsEveryComponentGreaterThanOrEqual(uint16_t x, uint16_t y) { int rv; auto xr = x & 0xF100; auto yr = y & 0xF100; rv = xr >= yr;
auto xg = x & 0x07E0; auto yg = y & 0x07E0; rv &= xg >= yg;
auto xb = x & 0x001F; auto yb = y & 0x001F; rv &= xb >= yb;
return rv != 0; }
According to the Compiler Explorer, the one presented in the article still has far fewer instructions on x86_64. Interestingly, the optimization of eliminating the bitshifts doesn't change how it is compiled which says something about trusting your compiler for some of this stuff. https://godbolt.org/z/zWf5GnPPb
However, one more interesting thing is that the modified version I made is nearly identical in size on ARMv8 for the one in the article vs my version (12 vs 11 instructions). https://godbolt.org/z/d4TPqGhKe
bool IsEveryComponentGreaterThanOrEqual(uint16_t x, uint16_t y) {
int rv = x >= y;
auto xg = x & 0x07E0; auto yg = y & 0x07E0; rv &= xg >= yg;
auto xb = x & 0x001F; auto yb = y & 0x001F; rv &= xb >= yb;
return rv != 0;
}The data structure from the article would be:
const RGB = packed struct(u16) {
b: u5,
g: u6,
r: u5,
}
const gte: bool = x.r >= y.r and x.g >= y.g and x.b >= y.b;
Or does it? Since the compiler knows about packed structs, it could perform the optimization for me.
Does it, right this instant? Eh, probably not. But compilers have a tendency to improve, and this is a local pattern which would be fairly easy to recognize. The recognition is the point: it's much, much harder to recognize the intent in the initial implementations described in the article, and then replace them with the optimal version. The way I was able to write it in Zig, in addition to being far more expressive of the algorithm's intent, conveys to the compiler: compare the values of these bitfields, I don't care how. The compiler doesn't have to prove that I have no other reason for the other operations, besides making said comparison possible: it can just emit the optimal code.
struct my_bitfield
{
uint16_t b:5;
uint16_t g:6;
uint16_t r:5;
};
bool IsEveryComponentGreaterThanOrEqual4(my_bitfield x, my_bitfield y)
{
return x.b > y.b && x.g > y.b && x.r > y.r;
}Seems there would only be a problem on some proprietary compiler for an embedded, bespoke target.
But there are only a handful of ways to lay out bitfields:
* Use little-endian or big-endian bit order? (this need not match the byte order, but usually does - IIRC recent GCC no longer supports any platforms where it doesn't?). This is the only one you can't control. Networking headers rely on a 2-way preprocessor branch so no other ways are really possible, at least up to `unsigned int` (may be 16) bits.
* If padding is needed, is it on the left or on the right? or, on the top or on the bottom? (this might always be tied to bit-endianness, but theoretically it is detached). For maximum portability, you must add explicit padding, doing math with `CHAR_BIT`.
* What exactly happens if an over-sized bitfield is attempted? (beware, there is no stable ABI for this in practice!)
* Do zero-sized bitfields align to the next unit?
* Can bitfields cross units? Is perhaps a larger-than-user-specified unit used? Consider `struct {uint8_t a:4, b:8, c:4};`
* If a mixture of types is used, do they get aggregated unconditionally, by size, by type? Ignoring signedness or not? Consider `struct { int a:1; long b:1; long long c:1; }`
* Is `int` the same as `signed int` or `unsigned int`, and for what widths?
It's unfortunate that testing some of these can't be done at compile time (a few can via `sizeof`), so you may need to either manually inspect assembly code, or else rely on optimization to do the emit-constants-via-strings trick when cross-compiling (C++, if supported on your platform, may do better than C at accessible compile-time optimization).
> Consecutive bit fields are packed together, but each bit field must fit within a single object of its specified type
[1] https://www.gnu.org/software/c-intro-and-ref/manual/html_nod...
I have no idea if the requirement that each bitfield be reified as its declared type inhibits optimization of that example or not, in practice. Maybe, maybe not.