{"id":106941,"date":"2022-08-03T07:00:00","date_gmt":"2022-08-03T14:00:00","guid":{"rendered":"https:\/\/devblogs.microsoft.com\/oldnewthing\/?p=106941"},"modified":"2022-11-29T10:16:40","modified_gmt":"2022-11-29T18:16:40","slug":"20220803-00","status":"publish","type":"post","link":"https:\/\/devblogs.microsoft.com\/oldnewthing\/20220803-00\/?p=106941","title":{"rendered":"The AArch64 processor (aka arm64), part 7: Bitfield manipulation"},"content":{"rendered":"

Recall that the PowerPC had the magical rlwinm<\/code> instruction which was the Swiss army knife of bit operations<\/a>. Well, AArch64 has its own all-purpose instruction, known as UBFM<\/code>, which stands for unsigned bitfield move<\/i>.<\/p>\n

    ; unsigned bitfield move\r\n    ;\r\n    ; if immr \u2264 imms:\r\n    ;   take bits immr through imms and rotate right by immr\r\n    ;\r\n    ; if immr > imms:\r\n    ;   take imms+1 low bits and rotate right by immr\r\n\r\n    ubfm    Rd\/zr, Rn\/zr, #immr, #imms\r\n<\/pre>\n
This instruction hurts my brain. Although the description of the instruction appears to be two unrelated cases, they are handled by the same complex formula internally. It’s just that the formula produces different results depending on which case you’re in. The complex formula is the same one that is used to  generate immediates for logical operations, so I’ll give the processor designers credit for the clever way they reduced transistor count.<\/p>\n
Fortunately, you never see this instruction in the wild. The two cases are split into separate pseudo-instructions, which re-express the immr<\/var> and imms<\/var> values in a more intuitive way.<\/p>\n
    ; unsigned bitfield extract\r\n    ; (used when immr \u2264 imms)\r\n    ; extract w bits starting at position lsb\r\n    ubfx    Rd\/zr, Rn\/zr, #lsb, #w\r\n<\/pre>\n
The UBFX<\/code> instruction handles the case of UBFM<\/code> where immr<\/var> \u2264 imms<\/var> and reinterprets it as a bitfield extraction:<\/p>\n\n\n\n\n\n
 <\/td>\nw<\/td>\nlsb<\/td>\n<\/tr>\n
\u00a0<\/td>\n\u00a0<\/td>\n\u00a0<\/td>\n\u00a0<\/td>\n<\/tr>\n
 <\/td>\n <\/td>\n\n\n\n\n\n\n
\u21d8<\/td>\n\u21d8<\/td>\n\u21d8<\/td>\n\u21d8<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n<\/td>\n <\/td>\n<\/tr>\n
zero-fill<\/td>\n\u00a0<\/td>\n\u00a0<\/td>\n\u00a0<\/td>\n<\/tr>\n
 <\/td>\n <\/td>\nw<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n
Since immr<\/var> \u2264 imms<\/var>, the right-rotation by immr<\/var> is the same as a right-shift by immr<\/var>.<\/p>\n
And then we have the other case, where immr<\/var> > imms<\/var>:<\/p>\n
    ; unsigned bitfield insert into zeroes\r\n    ; (used when immr > imms)\r\n    ; extract low-order w bits and shift left by lsb\r\n    ubfiz   Rd\/zr, Rn\/zr, #lsb, #w\r\n<\/pre>\n
The UBFIZ<\/code> instruction reinterprets the UBFM<\/code> as a bitfield insertion, and reinterprets the right-rotation as a left-shift. This reinterpretation is valid because immr<\/var> > imms<\/var>, so we are always rotating more bits than we extracted.<\/p>\n\n\n\n\n\n
 <\/td>\n <\/td>\nw<\/td>\n<\/tr>\n
\u00a0<\/td>\n\u00a0<\/td>\n\u00a0<\/td>\n\u00a0<\/td>\n<\/tr>\n
 <\/td>\n <\/td>\n\n\n\n\n\n\n
\u21d9<\/td>\n\u21d9<\/td>\n\u21d9<\/td>\n\u21d9<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n<\/td>\n <\/td>\n<\/tr>\n
zero-fill<\/td>\n\u00a0<\/td>\n\u00a0<\/td>\nzero-fill<\/td>\n<\/tr>\n
 <\/td>\nw<\/td>\nlsb<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n
There is also a signed version of this instruction:<\/p>\n
    ; signed bitfield move\r\n    ;\r\n    ; if immr \u2264 imms:\r\n    ;   take bits immr through imms and rotate right by immr\r\n    ;   sign-fill upper bits\r\n    ;\r\n    ; if immr > imms:\r\n    ;   take imms+1 low bits and rotate right by immr\r\n    ;   sign-fill upper bits\r\n\r\n    sbfm    Rd\/zr, Rn\/zr, #immr #imms\r\n<\/pre>\n
This behaves the same as the unsigned version, except that the upper bits are filled with the sign bit of the bitfield. Like UBFM<\/code>, the SBFM<\/code> instruction is also never seen in the wild; it is always replaced by a pseudo-instruction.<\/p>\n
    ; signed bitfield extract\r\n    ; (used when immr \u2264 imms)\r\n    ; extract w bits starting at position lsb\r\n    ; sign-fill upper bits\r\n    sbfx    Rd\/zr, Rn\/zr, #lsb, #w\r\n\r\n    ; signed bitfield insert into zeroes\r\n    ; (used when immr > imms)\r\n    ; extract low-order w bits and shift left by lsb\r\n    ; sign-fill upper bits\r\n    sbfiz   Rd\/zr, Rn\/zr, #lsb, #w\r\n<\/pre>\n
Here is the operation of SBFX<\/code> in pictures:<\/p>\n\n\n\n\n\n
 <\/td>\nw<\/td>\nlsb<\/td>\n<\/tr>\n
\u00a0<\/td>\nS<\/td>\n\u00a0<\/td>\n\u00a0<\/td>\n<\/tr>\n
 <\/td>\n <\/td>\n\n\n\n\n\n\n
\u21d8<\/td>\n\u21d8<\/td>\n\u21d8<\/td>\n\u21d8<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n<\/td>\n <\/td>\n<\/tr>\n
sign-fill<\/td>\n\u21d0\u21d0\u21d0<\/td>\nS<\/td>\n\u00a0<\/td>\n<\/tr>\n
 <\/td>\n <\/td>\nw<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n
And here is SBFIZ<\/code>:<\/p>\n\n\n\n\n\n
 <\/td>\n <\/td>\nw<\/td>\n<\/tr>\n
\u00a0<\/td>\n\u00a0<\/td>\nS<\/td>\n\u00a0<\/td>\n<\/tr>\n
 <\/td>\n <\/td>\n\n\n\n\n\n\n
\u21d9<\/td>\n\u21d9<\/td>\n\u21d9<\/td>\n\u21d9<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n<\/td>\n <\/td>\n<\/tr>\n
sign-fill \u21d0\u21d0\u21d0<\/td>\nS<\/td>\n\u00a0<\/td>\nzero-fill<\/td>\n<\/tr>\n
 <\/td>\nw<\/td>\nlsb<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n
Note that in the case of SBFIZ<\/code>, the lower bits are still zero-filled.<\/p>\n
The last bitfield opcode is BFM<\/code>, which follows the same pattern, but just combines the results differently:<\/p>\n
    ; bitfield move\r\n    ;\r\n    ; if immr \u2264 imms:\r\n    ;   take bits immr through imms and rotate right by immr\r\n    ;   merge with existing bits in destination\r\n    ;\r\n    ; if immr > imms:\r\n    ;   take imms+1 low bits and rotate right by immr\r\n    ;   merge with existing bits in destination\r\n\r\n    bfm     Rd\/zr, Rn\/zr, #immr #imms\r\n<\/pre>\n
Again, you will never see this instruction in the wild because it always disassembles as a pseudo-instruction:<\/p>\n
    ; bitfield extract and insert low\r\n    ; (used when immr \u2264 imms)\r\n    ; replace bottom w bits in destination\r\n    ; with w bits of source starting at lsb\r\n    ;\r\n    ; Rd[w-1:0] = Rn[lsb+w-1:lsb]\r\n    ;\r\n    bfxil   Rd\/zr, Rn\/zr, #lsb, #w\r\n<\/pre>\n
The BFXIL<\/code> instruction is like the UBFX<\/code> and SBFX<\/code> instructions, but instead of filling the unused bits with zero or sign bits, the original bits of the destination are preserved.<\/p>\n\n\n\n\n\n
 <\/td>\nw<\/td>\nlsb<\/td>\n<\/tr>\n
\u00a0<\/td>\n\u00a0<\/td>\n\u00a0<\/td>\n\u00a0<\/td>\n<\/tr>\n
 <\/td>\n <\/td>\n\n\n\n\n\n\n
\u21d8<\/td>\n\u21d8<\/td>\n\u21d8<\/td>\n\u21d8<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n<\/td>\n <\/td>\n<\/tr>\n
unchanged<\/td>\n\u00a0<\/td>\n\u00a0<\/td>\n\u00a0<\/td>\n<\/tr>\n
 <\/td>\n <\/td>\nw<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n
    ; bitfield insert\r\n    ; (used when immr > imms)\r\n    ; replace w bits in destination starting at lsb\r\n    ; with low w bits of source\r\n    ;\r\n    ; Rd[lsb+w-1:lsb] = Rn[w-1:0]\r\n    ;\r\n    bfi     Rd\/zr, Rn\/zr, #lsb, #w\r\n<\/pre>\n
The BFI<\/code> instruction is like the UBFIZ<\/code> and SBFIZ<\/code> instructions, but instead of filling the unused bits with zero or sign bits, the original bits of the destination are preserved.<\/p>\n\n\n\n\n\n
 <\/td>\n <\/td>\nw<\/td>\n<\/tr>\n
\u00a0<\/td>\n\u00a0<\/td>\n\u00a0<\/td>\n\u00a0<\/td>\n<\/tr>\n
 <\/td>\n <\/td>\n\n\n\n\n\n\n
\u21d9<\/td>\n\u21d9<\/td>\n\u21d9<\/td>\n\u21d9<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n<\/td>\n <\/td>\n<\/tr>\n
unchanged<\/td>\n\u00a0<\/td>\n\u00a0<\/td>\nunchanged<\/td>\n<\/tr>\n
 <\/td>\nw<\/td>\nlsb<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n
    ; bitfield clear\r\n    ; replace w bits in destination starting at lsb\r\n    ; with zero\r\n    ;\r\n    ; Rd[lsb+w-1:lsb] = 0\r\n    ;\r\n    bfc     Rd\/zr, #lsb, #w     ; bfi Rd\/zr, zr, #lsb, #w\r\n<\/pre>\n
The BFC<\/code> instruction just inserts zeroes.<\/p>\n\n\n\n\n
unchanged<\/td>\nzero-fill<\/td>\nunchanged<\/td>\n<\/tr>\n
 <\/td>\nw<\/td>\nlsb<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n
The last instruction in the bitfield manipulation category is word\/doubleword extraction.<\/p>\n
    ; extract a register from a pair of registers\r\n    ;\r\n    ; Wd = ((Wn << 32) | Wm)[lsb+31:lsb]\r\n    ; Xd = ((Xn << 64) | Xm)[lsb+63:lsb]\r\n    ;\r\n    extr    Rd\/zr, Rn\/zr, Rm\/zr, #lsb\r\n<\/pre>\n
The extract register<\/i> instruction treats its inputs as a register pair and extracts a register-sized stretch of bits from them. This can be used to synthesize multiword shifts.<\/p>\n\n\n\n\n\n\n
 <\/td>\nsize<\/td>\nshift<\/td>\n<\/tr>\n
 <\/td>\n <\/td>\n <\/td>\n <\/td>\n<\/tr>\n
\n
Rn<\/div>\n<\/td>\n
\u00a0<\/td>\n\n
Rm<\/div>\n<\/td>\n
\u00a0<\/td>\n<\/tr>\n
 <\/td>\n\n\n\n\n\n
\u21d3<\/td>\n\u21d3<\/td>\n\u21d3<\/td>\n\u21d3<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n<\/td>\n <\/td>\n<\/tr>\n
 <\/td>\nRd<\/td>\n <\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n
Note that the two input registers are concatenated in big-endian order.<\/p>\n
It turns out that a lot of other operations can be reinterpreted as bitfield extractions. We’ll look at some of them next time.<\/p>\n
Bonus chatter<\/b>: AArch32 also had instructions bfi<\/code>, bfc<\/code>, ubfx<\/code>, and sbfx<\/code>, but each was treated as a unique instruction. AArch64 generalizes them to cover additional scenarios, leaving the classic instructions as special cases of the generalized instructions.<\/p>\n","protected":false},"excerpt":{"rendered":"
Peeking inside the words.<\/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":[2],"class_list":["post-106941","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-oldnewthing","tag-history"],"acf":[],"blog_post_summary":"
Peeking inside the words.<\/p>\n","_links":{"self":[{"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/posts\/106941","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=106941"}],"version-history":[{"count":0,"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/posts\/106941\/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=106941"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/categories?post=106941"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/tags?post=106941"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}