{"id":43223,"date":"2015-01-05T07:00:00","date_gmt":"2015-01-05T22:00:00","guid":{"rendered":"https:\/\/blogs.msdn.microsoft.com\/oldnewthing\/2015\/01\/05\/more-notes-on-calculating-constants-in-sse-registers\/"},"modified":"2019-03-13T12:11:45","modified_gmt":"2019-03-13T19:11:45","slug":"20150105-00","status":"publish","type":"post","link":"https:\/\/devblogs.microsoft.com\/oldnewthing\/20150105-00\/?p=43223","title":{"rendered":"More notes on calculating constants in SSE registers"},"content":{"rendered":"

A few weeks ago I noted some tricks for creating special bit patterns in all lanes<\/a>, but I forgot to cover the case where you treat the 128-bit register as one giant lane: Setting all of the least significant N<\/var> bits or all of the most significant N<\/var> bits. <\/p>\n

This is a variation of the trick for setting a bit pattern in all lanes, but the catch is that the pslldq<\/code> instruction shifts by bytes, not bits. <\/p>\n

We’ll assume that N<\/var> is not a multiple of eight, because if it were a multiple of eight, then the pslldq<\/code> or psrldq<\/code> instruction does the trick (after using pcmpeqd<\/code> to fill the register with ones). <\/p>\n

One case is if N<\/var> ≤ 64. This is relatively easy because we can build the value by first building the desired value in both 64-bit lanes, and then finishing with a big pslldq<\/code> or psrldq<\/code> to clear the lane we don’t like. <\/p>\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n
;<\/code> set the bottom N<\/var> bits, where N<\/var> ≤ 64<\/td>\n<\/tr>\n
pcmpeqd xmm0, xmm0<\/code><\/td>\n;<\/code><\/td>\nFFFF<\/tt><\/td>\nFFFF<\/tt><\/td>\nFFFF<\/tt><\/td>\nFFFF<\/tt><\/td>\nFFFF<\/tt><\/td>\nFFFF<\/tt><\/td>\nFFFF<\/tt><\/td>\nFFFF<\/tt><\/td>\n<\/td>\n<\/tr>\n
<\/td>\n<\/tr>\n
<\/td>\nunsigned shift right
64 − N<\/var> bits<\/td>\n		unsigned shift right
64 − N<\/var> bits<\/td>\n<\/tr>\n
<\/td>\n<\/tr>\n
psrlq   xmm0, 64 - N<\/code><\/td>\n;<\/code> <\/p>\n0000<\/tt><\/td>\n0000<\/tt><\/td>\n0FFF<\/tt><\/td>\nFFFF<\/tt><\/td>\n0000<\/tt><\/td>\n0000<\/tt><\/td>\n0FFF<\/tt><\/td>\nFFFF<\/tt><\/td>\n<\/tr>\n
<\/td>\n<\/tr>\n
<\/td>\nunsigned shift right 64 bits<\/td>\n<\/tr>\n
<\/td>\n<\/tr>\n
psrldq  xmm0, 8<\/code><\/td>\n;<\/code> <\/p>\n0000<\/tt><\/td>\n0000<\/tt><\/td>\n0000<\/tt><\/td>\n0000<\/tt><\/td>\n0000<\/tt><\/td>\n0000<\/tt><\/td>\n0FFF<\/tt><\/td>\nFFFF<\/tt><\/td>\n<\/tr>\n
 <\/td>\n<\/tr>\n
;<\/code> set the top N<\/var> bits, where N<\/var> ≤ 64<\/td>\n<\/tr>\n
pcmpeqd xmm0, xmm0<\/code><\/td>\n;<\/code><\/td>\nFFFF<\/tt><\/td>\nFFFF<\/tt><\/td>\nFFFF<\/tt><\/td>\nFFFF<\/tt><\/td>\nFFFF<\/tt><\/td>\nFFFF<\/tt><\/td>\nFFFF<\/tt><\/td>\nFFFF<\/tt><\/td>\n<\/tr>\n
<\/td>\n<\/tr>\n
<\/td>\nunsigned shift left
64 − N<\/var> bits<\/td>\n		unsigned shift left
64 − N<\/var> bits<\/td>\n<\/tr>\n
<\/td>\n<\/tr>\n
psllq   xmm0, 64 - N<\/code><\/td>\n;<\/code><\/td>\nFFFF<\/tt><\/td>\nFFF0<\/tt><\/td>\n0000<\/tt><\/td>\n0000<\/tt><\/td>\nFFFF<\/tt><\/td>\nFFF0<\/tt><\/td>\n0000<\/tt><\/td>\n0000<\/tt><\/td>\n<\/tr>\n
<\/td>\n<\/tr>\n
<\/td>\nunsigned shift left 64 bits<\/td>\n<\/tr>\n
<\/td>\n<\/tr>\n
pslldq  xmm0, 8<\/code><\/td>\n;<\/code><\/td>\nFFFF<\/tt><\/td>\nFFF0<\/tt><\/td>\n0000<\/tt><\/td>\n0000<\/tt><\/td>\n0000<\/tt><\/td>\n0000<\/tt><\/td>\n0000<\/tt><\/td>\n0000<\/tt><\/td>\n<\/tr>\n<\/table>\n

If N<\/var> ≥ 80, then we shift in zeroes into the top and bottom half, but then use a shuffle to patch up the half that needs to stay all-ones. <\/p>\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n
;<\/code> set the bottom N<\/var> bits, where N<\/var> ≥ 80<\/td>\n<\/tr>\n
pcmpeqd xmm0, xmm0<\/code><\/td>\n;<\/code><\/td>\nFFFF<\/tt><\/td>\nFFFF<\/tt><\/td>\nFFFF<\/tt><\/td>\nFFFF<\/tt><\/td>\nFFFF<\/tt><\/td>\nFFFF<\/tt><\/td>\nFFFF<\/tt><\/td>\nFFFF<\/tt><\/td>\n<\/td>\n<\/tr>\n
<\/td>\n<\/tr>\n
<\/td>\nunsigned shift right
128 − N<\/var> bits<\/td>\n		unsigned shift right
128 − N<\/var> bits<\/td>\n<\/tr>\n
<\/td>\n<\/tr>\n
psrlq   xmm0, 128 - N<\/code><\/td>\n;<\/code><\/td>\n0000<\/tt><\/td>\n0000<\/tt><\/td>\n0FFF<\/tt><\/td>\nFFFF<\/tt><\/td>\n0000<\/tt><\/td>\n0000<\/tt><\/td>\n0FFF<\/tt><\/td>\nFFFF<\/tt><\/td>\n<\/tr>\n
<\/td>\n<\/tr>\n
<\/td>\ncopy<\/td>\nshuffle<\/td>\n↓<\/td>\n<\/tr>\n
<\/td>\n↓<\/td>\n↓<\/td>\n↓<\/td>\n↓<\/td>\n↙<\/td>\n↙<\/td>\n↙<\/td>\n↓<\/td>\n<\/tr>\n
<\/td>\n<\/tr>\npshuflw xmm0, _MM_SHUFFLE(0, 0, 0, 0)<\/code><\/td>\n;<\/code><\/td>\n0000<\/tt><\/td>\n0000<\/tt><\/td>\n0FFF<\/tt><\/td>\nFFFF<\/tt><\/td>\nFFFF<\/tt><\/td>\nFFFF<\/tt><\/td>\nFFFF<\/tt><\/td>\nFFFF<\/tt><\/td>\n<\/tr>\n
 <\/td>\n<\/tr>\n
;<\/code> set the top N<\/var> bits, where N ≥ 80<\/td>\n<\/tr>\n
pcmpeqd xmm0, xmm0<\/code><\/td>\n;<\/code><\/td>\nFFFF<\/tt><\/td>\nFFFF<\/tt><\/td>\nFFFF<\/tt><\/td>\nFFFF<\/tt><\/td>\nFFFF<\/tt><\/td>\nFFFF<\/tt><\/td>\nFFFF<\/tt><\/td>\nFFFF<\/tt><\/td>\n<\/tr>\n
<\/td>\n<\/tr>\n
<\/td>\nunsigned shift left
128 − N<\/var> bits<\/td>\n		unsigned shift left
128 − N<\/var> bits<\/td>\n<\/tr>\n
<\/td>\n<\/tr>\n
psllq   xmm0, 128 - N<\/code><\/td>\n;<\/code><\/td>\nFFFF<\/tt><\/td>\nFFF0<\/tt><\/td>\n0000<\/tt><\/td>\n0000<\/tt><\/td>\nFFFF<\/tt><\/td>\nFFF0<\/tt><\/td>\n0000<\/tt><\/td>\n0000<\/tt><\/td>\n<\/tr>\n
<\/td>\n<\/tr>\n
<\/td>\n↓<\/td>\nshuffle<\/td>\ncopy<\/td>\n<\/tr>\n
<\/td>\n↓<\/td>\n↘<\/td>\n↘<\/td>\n↘<\/td>\n↓<\/td>\n↓<\/td>\n↓<\/td>\n↓<\/td>\n<\/tr>\n
<\/td>\n<\/tr>\n
pshufhw xmm0, _MM_SHUFFLE(3, 3, 3, 3)<\/code><\/td>\n;<\/code><\/td>\nFFFF<\/tt><\/td>\nFFFF<\/tt><\/td>\nFFFF<\/tt><\/td>\nFFFF<\/tt><\/td>\nFFFF<\/tt><\/td>\nFFF0<\/tt><\/td>\n0000<\/tt><\/td>\n0000<\/tt><\/td>\n<\/tr>\n<\/table>\n

We have N<\/var> ≥ 80, which means that 128 – N<\/var> ≤ 48, which means that there are at least 16 bits of ones left in low-order bits after we shift right. We then use a 4×16-bit shuffle to copy those known-all-ones 16 bits into the other lanes of the lower half. (A similar argument applies to setting the top bits.) <\/p>\n

This leaves 64 < N<\/var> < 80. That uses a different trick: <\/p>\n\n\n\n\n\n\n\n\n\n\n\n
;<\/code> set the bottom N<\/var> bits, where N<\/var> ≤ 120<\/td>\n<\/tr>\n
pcmpeqd xmm0, xmm0<\/code><\/td>\n;<\/code><\/td>\nFFFF<\/tt><\/td>\nFFFF<\/tt><\/td>\nFFFF<\/tt><\/td>\nFFFF<\/tt><\/td>\nFFFF<\/tt><\/td>\nFFFF<\/tt><\/td>\nFFFF<\/tt><\/td>\nFFFF<\/tt><\/td>\n<\/tr>\n
<\/td>\n<\/tr>\n
<\/td>\nunsigned shift right 8 bits<\/td>\n<\/tr>\n
<\/td>\n<\/tr>\n
psrldq  xmm0, 1<\/code><\/td>\n;<\/code><\/td>\n00FF<\/tt><\/td>\nFFFF<\/tt><\/td>\nFFFF<\/tt><\/td>\nFFFF<\/tt><\/td>\nFFFF<\/tt><\/td>\nFFFF<\/tt><\/td>\nFFFF<\/tt><\/td>\nFFFF<\/tt><\/td>\n<\/tr>\n
<\/td>\n<\/tr>\n
<\/td>\nsigned shift right
120 − N<\/var> bits<\/td>\n		signed shift right
120 − N<\/var> bits<\/td>\n<\/tr>\n
<\/td>\n<\/tr>\n
psrad  xmm0, 120 - N<\/code><\/td>\n;<\/code><\/td>\n0000<\/tt><\/td>\n00FF<\/tt><\/td>\nFFFF<\/tt><\/td>\nFFFF<\/tt><\/td>\nFFFF<\/tt><\/td>\nFFFF<\/tt><\/td>\nFFFF<\/tt><\/td>\nFFFF<\/tt><\/td>\n<\/tr>\n<\/table>\n

The sneaky trick here is that we use a signed<\/i> shift in order to preserve the bottom half. Unfortunately, there is no corresponding left shift that shifts in ones, so the best I can come up with is four instructions: <\/p>\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n
;<\/code> set the top N<\/var> bits, where 64 ≤ N<\/var> ≤ 96<\/td>\n<\/tr>\n
<\/td>\n<\/tr>\n
pcmpeqd xmm0, xmm0<\/code><\/td>\n;<\/code><\/td>\nFFFF<\/tt><\/td>\nFFFF<\/tt><\/td>\nFFFF<\/tt><\/td>\nFFFF<\/tt><\/td>\nFFFF<\/tt><\/td>\nFFFF<\/tt><\/td>\nFFFF<\/tt><\/td>\nFFFF<\/tt><\/td>\n<\/tr>\n
<\/td>\nunsigned shift left
96 − N<\/var> bits<\/td>\n		unsigned shift left
96 − N<\/var> bits<\/td>\n<\/tr>\n
<\/td>\n<\/tr>\n
psllq   xmm0, 96 - N<\/code><\/td>\n;<\/code><\/td>\nFFFF<\/tt><\/td>\nFFFF<\/tt><\/td>\nFFF0<\/tt><\/td>\n0000<\/tt><\/td>\nFFFF<\/tt><\/td>\nFFFF<\/tt><\/td>\nFFF0<\/tt><\/td>\n0000<\/tt><\/td>\n<\/tr>\n
<\/td>\n<\/tr>\n
<\/td>\nshuffle<\/td>\n<\/tr>\n
<\/td>\n↓<\/td>\n↘<\/td>\n↓<\/td>\n↓<\/td>\n<\/tr>\n
<\/td>\n<\/tr>\n
pshufd  xmm0, _MM_SHUFFLE(3, 3, 1, 0)<\/code><\/td>\n;<\/code><\/td>\nFFFF<\/tt><\/td>\nFFFF<\/tt><\/td>\nFFFF<\/tt><\/td>\nFFFF<\/tt><\/td>\nFFFF<\/tt><\/td>\nFFFF<\/tt><\/td>\nFFF0<\/tt><\/td>\n0000<\/tt><\/td>\n<\/tr>\n
<\/td>\n<\/tr>\n
<\/td>\nunsigned shift left 32 bits<\/td>\n<\/tr>\n
<\/td>\n<\/tr>\n
pslldq  xmm0, 4<\/code><\/td>\n;<\/code><\/td>\nFFFF<\/tt><\/td>\nFFFF<\/tt><\/td>\nFFFF<\/tt><\/td>\nFFFF<\/tt><\/td>\nFFFF<\/tt><\/td>\nFF00<\/tt><\/td>\n0000<\/tt><\/td>\n0000<\/tt><\/td>\n<\/tr>\n<\/table>\n

We view the 128-bit register as four 32-bit lanes. split the shift into two steps. First, we fill Lane 0 with the value we ultimately want in Lane 1, then we patch up the damage we did to Lane 2, then we do a shift the 128-bit value left 32 places to slide the value into position and zero-fill Lane 0. <\/p>\n

Note that a lot of the ranges of N<\/var> overlap, so you often have a choice of solutions. There are other three-instruction solutions I didn’t bother presenting here. The only one I couldn’t find a three-instruction solution for was setting the top N<\/var> bits where 64 < N<\/var> < 80. <\/p>\n

If you find a three-instruction solution for this last case, share it in the comments. <\/p>\n","protected":false},"excerpt":{"rendered":"

All at the top or bottom.<\/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-43223","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-oldnewthing","tag-code"],"acf":[],"blog_post_summary":"

All at the top or bottom.<\/p>\n","_links":{"self":[{"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/posts\/43223","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=43223"}],"version-history":[{"count":0,"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/posts\/43223\/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=43223"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/categories?post=43223"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/tags?post=43223"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}