title: A better 8x8 bytes matrix transpose with SSE?
body: <p>I found <a href="https://stackoverflow.com/a/2518670/6570821">this post</a> that explains how to transpose an 8x8 bytes matrix with 24 operations, and a few scrolls later there's <a href="https://stackoverflow.com/a/4951060/6570821">the code</a> that implements the transpose. However, this method does not exploit the fact that we can <em>block</em> the 8x8 transpose into four 4x4 transposes, and each one can be done in one shuffle instruction only (<a href="https://stackoverflow.com/a/24819208/6570821">this post</a> is the reference). So I came out with this solution:</p>
  
  <pre><code>__m128i transpose4x4mask = _mm_set_epi8(15, 11, 7, 3, 14, 10, 6, 2, 13,  9, 5, 1, 12,  8, 4, 0);
  __m128i shuffle8x8Mask = _mm_setr_epi8(0, 1, 2, 3, 8, 9, 10, 11, 4,  5, 6, 7, 12,  13, 14, 15);
  
  void TransposeBlock8x8(uint8_t *src, uint8_t *dst, int srcStride, int dstStride) {
      __m128i load0 = _mm_set_epi64x(*(uint64_t*)(src + 1 * srcStride), *(uint64_t*)(src + 0 * srcStride));
      __m128i load1 = _mm_set_epi64x(*(uint64_t*)(src + 3 * srcStride), *(uint64_t*)(src + 2 * srcStride));
      __m128i load2 = _mm_set_epi64x(*(uint64_t*)(src + 5 * srcStride), *(uint64_t*)(src + 4 * srcStride));
      __m128i load3 = _mm_set_epi64x(*(uint64_t*)(src + 7 * srcStride), *(uint64_t*)(src + 6 * srcStride));
  
      __m128i shuffle0 = _mm_shuffle_epi8(load0, shuffle8x8Mask);
      __m128i shuffle1 = _mm_shuffle_epi8(load1, shuffle8x8Mask);
      __m128i shuffle2 = _mm_shuffle_epi8(load2, shuffle8x8Mask);
      __m128i shuffle3 = _mm_shuffle_epi8(load3, shuffle8x8Mask);
  
      __m128i block0 = _mm_unpacklo_epi64(shuffle0, shuffle1);
      __m128i block1 = _mm_unpackhi_epi64(shuffle0, shuffle1);
      __m128i block2 = _mm_unpacklo_epi64(shuffle2, shuffle3);
      __m128i block3 = _mm_unpackhi_epi64(shuffle2, shuffle3);
  
      __m128i transposed0 = _mm_shuffle_epi8(block0, transpose4x4mask);   
      __m128i transposed1 = _mm_shuffle_epi8(block1, transpose4x4mask);   
      __m128i transposed2 = _mm_shuffle_epi8(block2, transpose4x4mask);   
      __m128i transposed3 = _mm_shuffle_epi8(block3, transpose4x4mask);   
  
      __m128i store0 = _mm_unpacklo_epi32(transposed0, transposed2);
      __m128i store1 = _mm_unpackhi_epi32(transposed0, transposed2);
      __m128i store2 = _mm_unpacklo_epi32(transposed1, transposed3);
      __m128i store3 = _mm_unpackhi_epi32(transposed1, transposed3);
  
      *((uint64_t*)(dst + 0 * dstStride)) = _mm_extract_epi64(store0, 0);
      *((uint64_t*)(dst + 1 * dstStride)) = _mm_extract_epi64(store0, 1);
      *((uint64_t*)(dst + 2 * dstStride)) = _mm_extract_epi64(store1, 0);
      *((uint64_t*)(dst + 3 * dstStride)) = _mm_extract_epi64(store1, 1);
      *((uint64_t*)(dst + 4 * dstStride)) = _mm_extract_epi64(store2, 0);
      *((uint64_t*)(dst + 5 * dstStride)) = _mm_extract_epi64(store2, 1);
      *((uint64_t*)(dst + 6 * dstStride)) = _mm_extract_epi64(store3, 0);
      *((uint64_t*)(dst + 7 * dstStride)) = _mm_extract_epi64(store3, 1);
  }
  </code></pre>
  
  <p>Excluding load/store operations this procedure consists of only 16 instructions instead of 24. </p>
  
  <p>What am I missing? </p>