title: Efficiently gather individual bytes, separated by a byte-stride of 4
body: <p>I'm trying to optimize an algorithm that will process massive datasets that could strongly benefit from AVX SIMD instructions.  Unfortunately, the input memory layout is not optimal for the required computations. Information must be reordered, by assembling <code>__m256i</code> values from individual bytes that are exactly 4 bytes apart:</p>
  
  <p><strong>BEGIN EDIT</strong></p>
  
  <p>My target CPUS do not support AVX2 instructions, so like @Elalfer and @PeterCordes pointed out, I can't make use of __m256i values, code must be converted to use __m128i values instead)</p>
  
  <p><strong>END EDIT</strong></p>
  
  <p>DataSet layout in memory</p>
  
  <hr>
  
  <pre><code>Byte 0   | Byte 1   | Byte 2   | Byte 3
  Byte 4   | Byte 5   | Byte 6   | Byte 7
  ...
  Byte 120 | Byte 121 | Byte 122 | Byte 123
  Byte 124 | Byte 125 | Byte 126 | Byte 127
  </code></pre>
  
  <p>Desired values in <code>__m256i</code> variable:</p>
  
  <hr>
  
  <pre><code>| Byte 0 | Byte 4 | Byte 8 |     ...     | Byte 120 | Byte 124 |
  </code></pre>
  
  <hr>
  
  <p><strong>Is there a more efficient way to gather and rearrange the strided data other than this straightforward code?</strong></p>
  
  <pre><code>union {  __m256i   reg;   uint8_t bytes[32]; } aux;
  ...
  for( int i = 0; i &lt; 32; i++ )
      aux.bytes[i] = data[i * 4];
  </code></pre>
  
  <p><strong>Edit:</strong></p>
  
  <p>The step I'm trying to optimize is a bit column transposition; in other words, the bits of a certain column (32 possible bit columns in my data arrangement) should become a single <code>uint32_t</code> value, while the rest of the bits are ignored.</p>
  
  <p>I perform the transposition by rearranging the data as shown, performing a left shift to bring the desired bit column as the most significant bits in each sub-byte, and finally extract and assemble the bits into a single <code>uint32</code>_t value via the <code>_mm256_movemask_epi8()</code> intrinsic.</p>