{"id":106335,"date":"2022-03-10T07:00:00","date_gmt":"2022-03-10T15:00:00","guid":{"rendered":"https:\/\/devblogs.microsoft.com\/oldnewthing\/?p=106335"},"modified":"2022-03-10T07:21:15","modified_gmt":"2022-03-10T15:21:15","slug":"20220310-00","status":"publish","type":"post","link":"https:\/\/devblogs.microsoft.com\/oldnewthing\/20220310-00\/?p=106335","title":{"rendered":"Optimizing code to darken a bitmap, part 4"},"content":{"rendered":"

Our investigation into a simple function to darken a bitmap is still trying to beat this function:<\/p>\n

union Pixel\r\n{\r\n    uint8_t c[4]; \/\/ four channels: red, green, blue, alpha\r\n    uint32_t v;   \/\/ full pixel value as a 32-bit integer\r\n};\r\n\r\nvoid darken(Pixel* first, Pixel* last, int darkness)\r\n{\r\n  int lightness = 256 - darkness;\r\n  for (; first < last; ++first) {\r\n    first->c[0] = (uint8_t)(first->c[0] * lightness \/ 256);\r\n    first->c[1] = (uint8_t)(first->c[1] * lightness \/ 256);\r\n    first->c[2] = (uint8_t)(first->c[2] * lightness \/ 256);\r\n  }\r\n}\r\n<\/pre>\n
We tried parallelizing the multiplication by treating a traditional 32-register as a bunch of 10-bit fields, but it turns out that all the overhead of shifting and masking ended up costing more than the savings of reducing the number of multiplications.<\/p>\n
But instead of doing fake SIMD, let’s just do real SIMD.<\/p>\n
First, we’ll use the x86 SIMD intrinsics. I’m going to limit myself to SSE2, since that’s the minimum requirement for x86-based Windows starting with Windows\u00a08.<\/p>\n
For simplicity of exposition, let’s assume that the start of the pixel array is aligned on a 16-byte boundary and the total size is a perfect multiple of 16. This avoids the hassle of dealing with the edge cases at the start and end.<\/p>\n
void darken(Pixel* first, Pixel* last, int darkness)\r\n{\r\n  int lightness = 256 - darkness;\r\n  auto lightness128 = _mm_set_epi16(\r\n        256, lightness, lightness, lightness,\r\n        256, lightness, lightness, lightness);\r\n  void* end = last;\r\n  for (auto pixels = (__m128i*)first; pixels < end; pixels++) {\r\n    auto val = _mm_loadu_si128(pixels);\r\n    auto vlo = _mm_unpacklo_epi8(val, _mm_setzero_si128());\r\n    vlo = _mm_mullo_epi16(vlo, alpha128);\r\n    vlo = _mm_srli_epi16(vlo, 8);\r\n    auto vhi = _mm_unpackhi_epi8(val, _mm_setzero_si128());\r\n    vhi = _mm_mullo_epi16(vhi, alpha128);\r\n    vhi = _mm_srli_epi16(vhi, 8);\r\n    val = _mm_packus_epi16(vlo, vhi);\r\n    _mm_storeu_si128(pixels, val);\r\n  }\r\n}\r\n<\/pre>\n
First, we set up our lightness128<\/code> vector to consists of eight 16-bit lanes. The lanes corresponding to color channels get the specified lightness, and the lanes corresponding to alpha channels get a lightness of 256, which means “do not darken”.<\/p>\n
Inside the loop, we process 16 bytes at a time, which comes out to four pixels.<\/p>\n
First, we load the 16 bytes into an SSE2 register and call it val<\/code>.<\/p>\n
Next, we unpack the low part of the register with a register full of zeroes, putting the result into vlo<\/code>. The “unpack low” instruction interleaves the low bytes of the two source registers.<\/p>\n\n\n\n\n\n\n
source 1<\/td>\n <\/td>\nA7<\/td>\n <\/td>\nA6<\/td>\n <\/td>\nA5<\/td>\n <\/td>\nA4<\/td>\n <\/td>\nA3<\/td>\n <\/td>\nA2<\/td>\n <\/td>\nA1<\/td>\n <\/td>\nA0<\/td>\n<\/tr>\n
source 2<\/td>\nB7<\/td>\n\u2193<\/td>\nB6<\/td>\n\u2193<\/td>\nB5<\/td>\n\u2193<\/td>\nB4<\/td>\n\u2193<\/td>\nB3<\/td>\n\u2193<\/td>\nB2<\/td>\n\u2193<\/td>\nB1<\/td>\n\u2193<\/td>\nB0<\/td>\n\u2193<\/td>\n<\/tr>\n
 <\/td>\n\u2193<\/td>\n\u2193<\/td>\n\u2193<\/td>\n\u2193<\/td>\n\u2193<\/td>\n\u2193<\/td>\n\u2193<\/td>\n\u2193<\/td>\n\u2193<\/td>\n\u2193<\/td>\n\u2193<\/td>\n\u2193<\/td>\n\u2193<\/td>\n\u2193<\/td>\n\u2193<\/td>\n\u2193<\/td>\n<\/tr>\n
destination<\/td>\nD15<\/td>\nD14<\/td>\nD13<\/td>\nD12<\/td>\nD11<\/td>\nD10<\/td>\nD09<\/td>\nD08<\/td>\nD07<\/td>\nD06<\/td>\nD05<\/td>\nD04<\/td>\nD03<\/td>\nD02<\/td>\nD01<\/td>\nD00<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n
In our case, the second source register is all zeroes, so it has the effect of performing a zero extension of the first eight 8-bit values (corresponding to the first two pixels) into eight 16-bit values.<\/p>\n
    auto vlo = _mm_unpacklo_epi8(val, _mm_setzero_si128());\r\n<\/pre>\n\n\n\n\n\n\n\n\n
source 1<\/td>\n <\/td>\nA7<\/td>\n <\/td>\nA6<\/td>\n <\/td>\nA5<\/td>\n <\/td>\nA4<\/td>\n <\/td>\nA3<\/td>\n <\/td>\nA2<\/td>\n <\/td>\nA1<\/td>\n <\/td>\nA0<\/td>\n<\/tr>\n
source 2<\/td>\n00<\/td>\n\u2193<\/td>\n00<\/td>\n\u2193<\/td>\n00<\/td>\n\u2193<\/td>\n00<\/td>\n\u2193<\/td>\n00<\/td>\n\u2193<\/td>\n00<\/td>\n\u2193<\/td>\n00<\/td>\n\u2193<\/td>\n00<\/td>\n\u2193<\/td>\n<\/tr>\n
 <\/td>\n\u2193<\/td>\n\u2193<\/td>\n\u2193<\/td>\n\u2193<\/td>\n\u2193<\/td>\n\u2193<\/td>\n\u2193<\/td>\n\u2193<\/td>\n\u2193<\/td>\n\u2193<\/td>\n\u2193<\/td>\n\u2193<\/td>\n\u2193<\/td>\n\u2193<\/td>\n\u2193<\/td>\n\u2193<\/td>\n<\/tr>\n
destination<\/td>\n00<\/td>\nA7<\/td>\n00<\/td>\nA6<\/td>\n00<\/td>\nA5<\/td>\n00<\/td>\nA4<\/td>\n00<\/td>\nA3<\/td>\n00<\/td>\nA2<\/td>\n00<\/td>\nA1<\/td>\n00<\/td>\nA0<\/td>\n<\/tr>\n
 <\/td>\n<\/tr>\n
 <\/td>\nA7<\/td>\nA6<\/td>\nA5<\/td>\nA4<\/td>\nA3<\/td>\nA2<\/td>\nA1<\/td>\nA0<\/td>\n <\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n
Next up is the multiplication and division:<\/p>\n
    vlo = _mm_mullo_epi16(vlo, alpha128);\r\n    vlo = _mm_srli_epi16(vlo, 8);\r\n<\/pre>\n
We perform a parallel multiply of the 16-bit values against the values in our lightness128<\/code> register, and then we perform a parallel right-shift by 8 positions.<\/p>\n
This combination of operations performs the newPixel = oldPixel * lightness \/ 256<\/code> calculation on eight values at once. Recall that we preloaded the alpha channel with a lightness value of 256, so this multiplies by 256 and the shifts right by 8, which is a net nop.<\/p>\n
We perform the same sequence of operations on the high bytes. The only difference is that we unpack with the unpackhi<\/code> flavor of the intrinsic, so that it operates on the high 8 bytes instead of the low 8 bytes, thereby performing the calculations on the last two pixels instead of the first two.<\/p>\n
We now have the desired results in sixteen 16-bit lanes, spread over two registers. We want to collapse those 16-bit lanes back into sixteen 8-bit lanes of a single register, which we do with the pack<\/code> instruction. The us<\/code> suffix means that this uses unsigned saturation. The unsigned part is important, but the saturation part isn’t, since we know that the values are already in the range 0\u2026255.<\/p>\n\n\n\n\n\n\n\n
source 1<\/td>\n <\/td>\nA7<\/td>\nA6<\/td>\nA5<\/td>\nA4<\/td>\nA3<\/td>\nA2<\/td>\nA1<\/td>\nA0<\/td>\n<\/tr>\n
 <\/td>\n <\/td>\n <\/td>\n\u2193<\/td>\n <\/td>\n\u2193<\/td>\n <\/td>\n\u2193<\/td>\n <\/td>\n\u2193<\/td>\n <\/td>\n\u2193<\/td>\n <\/td>\n\u2193<\/td>\n <\/td>\n\u2193<\/td>\n <\/td>\n\u2193<\/td>\n<\/tr>\n
destination<\/td>\n\u00a0<\/td>\nB7<\/td>\nA7<\/td>\nB6<\/td>\nA6<\/td>\nB5<\/td>\nA5<\/td>\nB4<\/td>\nA4<\/td>\nB3<\/td>\nA3<\/td>\nB2<\/td>\nA2<\/td>\nB1<\/td>\nA1<\/td>\nB0<\/td>\nA0<\/td>\n<\/tr>\n
 <\/td>\n <\/td>\n\u2191<\/td>\n <\/td>\n\u2191<\/td>\n <\/td>\n\u2191<\/td>\n <\/td>\n\u2191<\/td>\n <\/td>\n\u2191<\/td>\n <\/td>\n\u2191<\/td>\n <\/td>\n\u2191<\/td>\n <\/td>\n\u2191<\/td>\n <\/td>\n<\/tr>\n
source 2<\/td>\nB7<\/td>\nB6<\/td>\nB5<\/td>\nB4<\/td>\nB3<\/td>\nB2<\/td>\nB1<\/td>\nB0<\/td>\n <\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n
At each iteration of the loop, we process four pixels.<\/p>\n
This rewrite of the loop using SIMD pays off: It’s 3.5 times faster then the non-SIMD version.<\/p>\n
Next time, we’ll apply the same approach to the ARM version.<\/p>\n
Bonus chatter<\/b>: I tried reducing the strength of the multiplication by using the same “addition with masking” trick that I tried in the general-purpose register version. It didn’t help. The multiplication is fast enough that attempts to reduce its strength end up costing more in overhead than they do in savings by avoiding the multiplcation instruction.<\/p>\n","protected":false},"excerpt":{"rendered":"
Bringing out the big SIMD guns, for x86 at least.<\/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-106335","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-oldnewthing","tag-code"],"acf":[],"blog_post_summary":"
Bringing out the big SIMD guns, for x86 at least.<\/p>\n","_links":{"self":[{"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/posts\/106335","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=106335"}],"version-history":[{"count":0,"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/posts\/106335\/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=106335"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/categories?post=106335"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/tags?post=106335"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}