{"id":101076,"date":"2019-03-01T07:00:00","date_gmt":"2019-03-01T22:00:00","guid":{"rendered":"https:\/\/devblogs.microsoft.com\/oldnewthing\/?p=101076"},"modified":"2019-03-12T23:58:13","modified_gmt":"2019-03-13T06:58:13","slug":"20190301-00","status":"publish","type":"post","link":"https:\/\/devblogs.microsoft.com\/oldnewthing\/20190301-00\/?p=101076","title":{"rendered":"How to compare two packed bitfields without having to unpack each field"},"content":{"rendered":"

Suppose you are packing multiple bitfields into a single integer. Let’s say you have a 16-bit integer that you have packed three bitfields into: <\/p>\n\n\n\n
15<\/td>\n14<\/td>\n13<\/td>\n12<\/td>\n11<\/td>\n10<\/td>\n9<\/td>\n8<\/td>\n7<\/td>\n6<\/td>\n5<\/td>\n4<\/td>\n3<\/td>\n2<\/td>\n1<\/td>\n0<\/td>\n<\/tr>\n
r<\/td>\ng<\/td>\nb<\/td>\n<\/tr>\n<\/table>\n

Suppose you have two of these packed bitfields, x<\/var> and y<\/var>, <\/p>\n\n\n\n\n
15<\/td>\n14<\/td>\n13<\/td>\n12<\/td>\n11<\/td>\n10<\/td>\n9<\/td>\n8<\/td>\n7<\/td>\n6<\/td>\n5<\/td>\n4<\/td>\n3<\/td>\n2<\/td>\n1<\/td>\n0<\/td>\n<\/tr>\n
xr<\/td>\nxg<\/td>\nxb<\/td>\n<\/tr>\n
yr<\/td>\nyg<\/td>\nyb<\/td>\n<\/tr>\n<\/table>\n

and you want to know whether every field in x<\/var> is greater than or equal the corresponding field in y<\/var>. I.e., you want to determine whether xr ≥ yr<\/var>, xg ≥ yg<\/var>, and xb ≥ yb<\/var>. <\/p>\n

One way would be to unpack the bitfields. <\/p>\n

\nbool IsEveryComponentGreaterThanOrEqual(uint16_t x, uint16_t y)\n{\n auto xr = x >> 11;\n auto yr = y >> 11;\n if (xr < yr) return false;\n\n auto xg = (x >> 5) & 0x3F;\n auto yg = (y >> 5) & 0x3F;\n if (xg < yg) return false;\n\n auto xb = x & 0x1F;\n auto yb = y & 0x1F;\n if (xb < yb) return false;\n\n return true;\n}\n<\/pre>\n
There’s an obvious optimization here, which is to avoid the extra shifting. <\/p>\n
\nbool IsEveryComponentGreaterThanOrEqual(uint16_t x, uint16_t y)\n{\n auto xr = x & 0xF100;\n auto yr = y & 0xF100;\n if (xr < yr) return false;\n\n auto xg = x & 0x07E0;\n auto yg = y & 0x07E0;\n if (xg < yg) return false;\n\n auto xb = x & 0x001F;\n auto yb = y & 0x001F;\n if (xb < yb) return false;\n\n return true;\n}\n<\/pre>\n
But suppose this comparison is part of your program’s inner loop, so you’re hoping for something better. <\/p>\n
Well, if you had planned ahead and inserted a zero padding bit at the front of each field: <\/p>\n\n\n\n
18<\/td>\n17<\/td>\n16<\/td>\n15<\/td>\n14<\/td>\n13<\/td>\n12<\/td>\n11<\/td>\n10<\/td>\n9<\/td>\n8<\/td>\n7<\/td>\n6<\/td>\n5<\/td>\n4<\/td>\n3<\/td>\n2<\/td>\n1<\/td>\n0<\/td>\n<\/tr>\n
0<\/td>\nr<\/td>\n0<\/td>\ng<\/td>\n0<\/td>\nb<\/td>\n<\/tr>\n<\/table>\n
then you could subtract the two values and see if any padding bit became set, which indicates that an underflow occurred somewhere to the right. <\/p>\n
\nbool IsEveryComponentGreaterThanOrEqual(uint32_t x, uint32_t y)\n{\n auto m = (x - y) & ((1 << 18) | (1 << 12) | (1 << 5));\n return m == 0;\n}\n<\/pre>\n
However, this forces you to reserve padding bits, and it seems silly to have padding bits all over your data just for this purpose. I mean, those are bits that could’ve been doing something useful! <\/p>\n
In our example, those three extra bits forced us to use a larger integral type, which means our memory usage doubled. <\/p>\n
Can you do it without inserting padding bits? <\/p>\n
Indeed you can, thanks to a trick from emulator master<\/a> Darek Mihocka: The carry-out vector. <\/p>\n
You can read the paper<\/a> or take the easier route and read the presentation<\/a>. <\/p>\n
In this case, we want the subtraction carry-out vector (which is really the borrow vector). The formula is right here in the Bochs emulator source code<\/a>. <\/p>\n
\n#define SUB_COUT_VEC(op1, op2, result) \\\n  (((~(op1)) & (op2)) | ((~((op1) ^ (op2))) & (result)))\n<\/pre>\n
In the subtraction carry-out vector, a bit is set if the subtraction resulted in a borrow at that position. We then check whether there was a borrow at the corresponding high bits 4, 10, or 15. <\/p>\n
Here we go: <\/p>\n
\nbool IsEveryComponentGreaterThanOrEqual(uint16_t x, uint16_t y)\n{\n auto c = ((~x & y) | (~(x ^ y) & (x - y));\n c &= 0x8410;\n return c == 0;\n}\n<\/pre>\n
Slide 13 of the presentation linked above shows how this technique can be used to implement saturating bitfield arithmetic in general-purpose registers. Who needs SIMD registers! <\/p>\n
The carry-out vector is truly magical. <\/p>\n
Bonus reading<\/b>: How Bochs Works Under the Hood<\/a>. The “Lazy flags handling” section has a useful diagram. <\/p>\n","protected":false},"excerpt":{"rendered":"
The magic carry-out vector.<\/p>\n","protected":false},"author":1069,"featured_media":111744,"comment_status":"open","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"_acf_changed":false,"footnotes":""},"categories":[1],"tags":[25],"class_list":["post-101076","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-oldnewthing","tag-code"],"acf":[],"blog_post_summary":"
The magic carry-out vector.<\/p>\n","_links":{"self":[{"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/posts\/101076","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/users\/1069"}],"replies":[{"embeddable":true,"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/comments?post=101076"}],"version-history":[{"count":0,"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/posts\/101076\/revisions"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/media\/111744"}],"wp:attachment":[{"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/media?parent=101076"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/categories?post=101076"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/tags?post=101076"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}