{"id":43333,"date":"2014-12-22T07:00:00","date_gmt":"2014-12-22T07:00:00","guid":{"rendered":"https:\/\/blogs.msdn.microsoft.com\/oldnewthing\/2014\/12\/22\/setting-clearing-and-testing-a-single-bit-in-an-sse-register\/"},"modified":"2014-12-22T07:00:00","modified_gmt":"2014-12-22T07:00:00","slug":"setting-clearing-and-testing-a-single-bit-in-an-sse-register","status":"publish","type":"post","link":"https:\/\/devblogs.microsoft.com\/oldnewthing\/20141222-00\/?p=43333","title":{"rendered":"Setting, clearing, and testing a single bit in an SSE register"},"content":{"rendered":"

\nToday I’m going to set, clear, and test a single bit in an SSE register.\n<\/p>\n

\nWhy?\n<\/p>\n

\nOn Mondays I don’t have to explain why.\n<\/p>\n

\nFirst, we use the trick from\n\nlast time<\/a>\nthat lets us generate constants\nwhere all set bits are contiguous,\nand apply it to the case where we want only one bit.\n<\/p>\n

\n    pcmpeqd xmm0, xmm0      ; set all bits to one\n    psrlq   xmm0, 63        ; set both 64-bit lanes to 1\nIF N LT 64\n    psrldq  xmm0, 64 \/ 8    ; clear the upper lane\nELSE\n    pslldq  xmm0, 64 \/ 8    ; clear the lower lane\nENDIF\nIF N AND 63\n    psllq   xmm0, N AND 63  ; shift the bit into position\nENDIF\n<\/pre>\n
\nWe start by setting all bits in xmm0<\/code>.\n<\/p>\n
\nWe then shift both 64-bit lanes right by 63 positions,\nputting 1 in each lane.\n<\/p>\n
\nIf the bit we want is in the upper half,\nthen we shift the entire value left 8 bytes (64 bits).\nThis clears the bottom 64 bits and leaves the upper 64\nbits with all bits set.\n(Similarly, if the bit we want is in the lower half,\nshifting right instead of left.)\n<\/p>\n
\nFinally, if we need a bit other than 0 or 64, we shift\nleft by the desired amount within the 64-bit lane.\n<\/p>\n
\nNow that we can generate a single bit value,\nwe can use it to set and clear individual bits.\n<\/p>\n
\n; Set bit N in xmm1 (using xmm0 as a helper)\n        ⟨set xmm0 = 2^N⟩\n        por     xmm1, xmm0\n; Clear bit N in xmm1 (putting result in xmm0)\n        ⟨set xmm0 = 2^N⟩\n        pandn   xmm0, xmm1\n<\/pre>\n
\nTo test a bit, we can use the PMOVMSKB<\/code> instruction.\n<\/p>\n
\nIF 7 - (N AND 7)\n    psllq xmm0, 7 - (N AND 7)\nENDIF\n    pmovmskb eax, xmm0\nIF N LT 64\n    test  al, 1 SHL (N \/ 8)\nELSE\n    test  ah, 1 SHL (N \/ 8 - 8)\nENDIF\n<\/pre>\n
\nFirst, we move the bit we want to test into a position that is 7 mod 8,\nbecause those are the bits captured by the\nPMOVMSKB<\/code> instruction.\n(If the bit is already there, then we don’t need to do anything.)\nThen we use the PMOVMSKB<\/code> instruction to extract the bits\ninto a general purpose register and test the one that corresponds to\nthe bit we want.\n<\/p>\n
\nAlternatives<\/b>:\nI tend to stick to SSE2 instructions because they are widely supported\n(and are indeed part of the\n\nminimum system requirements for Windows 8<\/a>),\nbut if you are willing to do CPU dispatching on SSE4, you can\nuse PTEST<\/code>, which might be faster, I haven’t tested it.\n<\/p>\n
\nYou could use movd<\/code> and movq<\/code>\nto load up a constant,\nbut you do incur domain crossing penalties.\nAnother alternative is to put the constant in memory,\nbut then you pay an even bigger cost for memory access\nif the value is not in cache.<\/p>\n
\nOther remarks<\/b>:\nOf course, you want to schedule the instructions better than the\nway I wrote them above.\nI wrote them in a logical order above to make the algorithm clearer,\nbut you will want to reorder them to avoid stalls.\n<\/p>\n
\nUsing intrinsics<\/b>:\n<\/p>\n
\n__m128i Calc2ToTheN(int N)\n{\n __m128i zero = _mm_setzero_si128();\n __m128i ones = _mm_cmpeq_epi32(zero, zero);\n __m128i onesLowHigh = _mm_slli_epi64(ones, 63);\n __m128i singleOne = N < 64 ? _mm_srli_si128(onesLowHigh, 64 \/ 8) :\n                              _mm_slli_si128(onesLowHigh, 64 \/ 8);\n return _mm_slli_epi64(singleOne, N & 63);\n}\n__m128i SetBitN(__m128i value, int N)\n{\n  return _mm_or_si128(value, Calc2ToTheN(N));\n}\n__m128i ClearBitN(__m128i value, int N)\n{\n  return _mm_andnot_si128(value, Calc2ToTheN(N));\n}\n__m128i TestBitN(__m128i value, int N)\n{\n __m128i positioned = _mm_slli_epi64(value, 7 - (N & 7));\n return (_mm_movemask_epi8(positioned) & (1 << (N \/ 8))) != 0;\n}\n<\/pre>\n
\nNote that since these functions pass a non-constant value to\nintrinsics like _mm_slli_epi64<\/code>,\nyou incur additional runtime penalties because the compiler\nis going to use a movd<\/code> to load up the value,\nincurring the exact domain crossing penalty we are trying to avoid.\nTo avoid this, templatize the function to force the bit number\nto be determined at compile time.\n<\/p>\n
\ntemplate<int N>\n__m128i Calc2ToTheN()<\/font>\n{\n __m128i zero = _mm_setzero_si128();\n __m128i ones = _mm_cmpeq_epi32(zero, zero);\n __m128i onesLowHigh = _mm_slli_epi64(ones, 63);\n __m128i singleOne = N < 64 ? _mm_srli_si128(onesLowHigh, 64 \/ 8) :\n                              _mm_slli_si128(onesLowHigh, 64 \/ 8);\n return _mm_slli_epi64(singleOne, N & 63);\n}\ntemplate<int N>\n__m128i SetBitN(__m128i value)<\/font>\n{\n  return _mm_or_si128(value, Calc2ToTheN<N>()<\/font>);\n}\ntemplate<int N>\n__m128i ClearBitN(__m128i value)<\/font>\n{\n  return _mm_andnot_si128(value, Calc2ToTheN<N>()<\/font>);\n}\ntemplate<int N>\n__m128i TestBitN(__m128i value)<\/font>\n{\n __m128i positioned = _mm_slli_epi64(value, 7 - (N & 7));\n return (_mm_movemask_epi8(positioned) & (1 << (N \/ 8))) != 0;\n}\n<\/pre>\n","protected":false},"excerpt":{"rendered":"
Today I’m going to set, clear, and test a single bit in an SSE register. Why? On Mondays I don’t have to explain why. First, we use the trick from last time that lets us generate constants where all set bits are contiguous, and apply it to the case where we want only one bit. […]<\/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-43333","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-oldnewthing","tag-code"],"acf":[],"blog_post_summary":"
Today I’m going to set, clear, and test a single bit in an SSE register. Why? On Mondays I don’t have to explain why. First, we use the trick from last time that lets us generate constants where all set bits are contiguous, and apply it to the case where we want only one bit. […]<\/p>\n","_links":{"self":[{"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/posts\/43333","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=43333"}],"version-history":[{"count":0,"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/posts\/43333\/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=43333"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/categories?post=43333"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/tags?post=43333"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}