title: Extract set bytes position from SIMD vector
body: <p>I run a bench of computations using SIMD intructions. These instructions return a vector of 16 bytes as result, named <code>compare</code>, with each byte being <code>0x00</code> or <code>0xff</code> :</p>
  
  <pre><code>             0    1    2    3    4    5    6    7       15   16
  compare : 0x00 0x00 0x00 0x00 0xff 0x00 0x00 0x00 ... 0xff 0x00
  </code></pre>
  
  <p>Bytes set to <code>0xff</code> mean I need to run the function <code>do_operation(i)</code> <em>with i being the position of the byte</em>.</p>
  
  <p>For instance, the above <code>compare</code> vector mean, I need to run this sequence of operations :</p>
  
  <pre><code>do_operation(4);
  do_operation(15);
  </code></pre>
  
  <p>Here is the fastest solution I came up with until now :</p>
  
  <pre><code>for(...) {
          //
          // SIMD computations
          //
          __m128i compare = ... // Result of SIMD computations
  
          // Extract high and low quadwords for compare vector
          std::uint64_t cmp_low = (_mm_cvtsi128_si64(compare));
          std::uint64_t cmp_high = (_mm_extract_epi64(compare, 1));
  
          //  Process low quadword 
          if (cmp_low) {
              const std::uint64_t low_possible_positions = 0x0706050403020100;
              const std::uint64_t match_positions = _pext_u64(
                      low_possible_positions, cmp_low);
              const int match_count = _popcnt64(cmp_low) / 8;
              const std::uint8_t* match_pos_array =
                      reinterpret_cast&lt;const std::uint8_t*&gt;(&amp;match_positions);
  
              for (int i = 0; i &lt; match_count; ++i) {
                  do_operation(i);
              }
          }
  
          // Process high quadword (similarly)
          if (cmp_high) { 
  
              const std::uint64_t high_possible_positions = 0x0f0e0d0c0b0a0908;
              const std::uint64_t match_positions = _pext_u64(
                      high_possible_positions, cmp_high);
              const int match_count = _popcnt64(cmp_high) / 8;
              const std::uint8_t* match_pos_array =
                      reinterpret_cast&lt;const std::uint8_t*&gt;(&amp;match_positions);
  
              for(int i = 0; i &lt; match_count; ++i) {
                  do_operation(i);
              }
          }
  }
  </code></pre>
  
  <p>I start with extracting the first and second 64 bits integers of the 128 bits vector (<code>cmp_low</code> and <code>cmp_high</code>). Then I use <code>popcount</code> to compute the number of bytes set to <code>0xff</code> (number of bits set to 1 divided by 8). Finally, I use <code>pext</code> to get positions, without zeros, like this : </p>
  
  <pre><code>0x0706050403020100
  0x000000ff00ff0000
          |
        PEXT
          |
  0x0000000000000402
  </code></pre>
  
  <p>I would like to find a <strong>faster solution</strong> to <strong>extract the positions</strong> of the bytes set to <code>0xff</code> in the <code>compare</code> vector. More precisely, the are very often only <strong>0, 1 or 2 bytes set to <code>0xff</code> in the <code>compare</code> vector</strong> and I would like to use this information to avoid some branches.</p>