SSEでインターリーブ解除

たまたま２種類のデータが交互に並んでいるデータを分ける必要があったので覚書として。

16bitのデータがA1,B1,A2,B2,...と並んでいるものを
A1,A2,A3,...とB1,B2,B3,...に分けたい時に使えるかもしれません。


SSE2までの命令を使っているものと、SSSE3までの命令を使っている物両方を書きました。
コンパイラはVisualC++を使っています。
構文チェックをしていないので、セミコロンなどが抜けてるかもしれません。


```deinterleave.cpp

// 結果をチェック。
// 面倒くさいので8個x2固定
int check(const unsigned short* answer1, const unsigned short* answer2,
  const unsigned short* correct1, const unsigned short* correct2)
{
  for (i = 0 ; i < 8 ; ++i) {
    if (answer1[i] != correct1[i])
      break;
    if (answer2[i] != correct2[i])
      break;
  }

  if (i != 8) {
    // なにか間違ってた
    printf("A1:");  // 結果
    for (i = 0 ; i < 8 ; ++i) {
      printf("%04X,", answer1[i]);
    }
    printf("\nC1:");  // 正答
    for (i = 0 ; i < 8 ; ++i) {
      printf("%04X,", correct1[i]);
    }
    printf("\nA2:");  // 結果
    for (i = 0 ; i < 8 ; ++i) {
      printf("%04X,", answer2[i]);
    }
    printf("\nC2:");  // 正答
    for (i = 0 ; i < 8 ; ++i) {
      printf("%04X,", correct2[i]);
    }
    return 0;
  } else {
    // 大変良く出来ました(花マル)
    puts("very well done!!");
    return 1;
  }
}

main()
{
  // 入力データ例
  unsigned short data1[16] = {
    0x0123,0x8123,0x1234,0x8234,0x2345,0x8345,0x3456,0x8456,
    0x4567,0x8567,0x5678,0x889A,0x6789,0x89AB,0x789A,0x8ABC,
  };
  unsigned short *data2 = &data1[8];

  // 処理結果
  unsigned short answer1[8];
  unsigned short answer2[8];

  // 正答
  unsigned short correct_answer[2][8];

  int i;
  unsigned char shuffleptn[16] = {0,1,4,5,8,9,12,13, 2,3,6,7,10,11,14,15};
  __m128i src1, src2, src3, src4, sptn;

  // SISD
  for (i = 0 ; i < 8 ; ++i) {
    correct_answer[0][i] = data1[2*i];
    correct_answer[1][i] = data1[2*i+1];
  }


  puts("// SSSE3");

  src1 = _mm_loadu_si128((const __m128i*)data1);  // A1 B1 A2 B2 A3 B3 A4 B4
  src2 = _mm_loadu_si128((const __m128i*)data2);  // A5 B5 A6 B6 A7 B7 A8 B8
  sptn = _mm_loadu_si128((const __m128i*)shuffleptn);  // 0,1,4,5,8,9,12,13,2,3,6,7,10,11,14,15
  src1 = _mm_shuffle_epi8(src1, sptn);  // A1 A2 A3 A4 B1 B2 B3 B4
  src2 = _mm_shuffle_epi8(src2, sptn);  // A5 A6 A7 A8 B5 B6 B7 B8
  src3 = _mm_unpacklo_epi64(src1, src2);  // A1 A2 A3 A4 A5 A6 A7 A8
  src4 = _mm_unpackhi_epi64(src1, src2);  // B1 B2 B3 B4 B5 B6 B7 B8
  _mm_storeu_si128((__m128i*)answer1, src3);
  _mm_storeu_si128((__m128i*)answer2, src4);

  check(answer1, answer2, correct_answer[0], correct_answer[1]);


  puts("// SSE2");

  src1 = _mm_loadu_si128((const __m128i*)data1);  // A1 B1 A2 B2 A3 B3 A4 B4
  src2 = _mm_loadu_si128((const __m128i*)data2);  // A5 B5 A6 B6 A7 B7 A8 B8
  src1 = _mm_shufflelo_epi16(src1, _MM_SHUFFLE(3, 1, 2, 0));  // A1 A2 B1 B2 A3 B3 A4 B4
  src1 = _mm_shufflehi_epi16(src1, _MM_SHUFFLE(3, 1, 2, 0));  // A1 A2 B1 B2 A3 A4 B3 B4
  src2 = _mm_shufflelo_epi16(src2, _MM_SHUFFLE(3, 1, 2, 0));  // A5 A6 B5 B6 A7 B7 A8 B8
  src2 = _mm_shufflehi_epi16(src2, _MM_SHUFFLE(3, 1, 2, 0));  // A5 A6 B5 B6 A7 A8 B7 B8
  src1 = _mm_shuffle_epi32(src1, _MM_SHUFFLE(3, 1, 2, 0));  // A1 A2 A3 A4 B1 B2 B3 B4
  src2 = _mm_shuffle_epi32(src2, _MM_SHUFFLE(3, 1, 2, 0));  // A5 A6 A7 A8 B5 B6 B7 B8
  src3 = _mm_unpacklo_epi64(src1, src2);  // A1 A2 A3 A4 A5 A6 A7 A8
  src4 = _mm_unpackhi_epi64(src1, src2);  // B1 B2 B3 B4 B5 B6 B7 B8
  _mm_storeu_si128((__m128i*)answer1, src3);
  _mm_storeu_si128((__m128i*)answer2, src4);

  check(answer1, answer2, correct_answer[0], correct_answer[1]);
}
```

# 参考
こちらをかなり参考にさせて頂いています。--> http://www.officedaytime.com/tips/simd.html

# 追記(2015/07/22)
ググると色々出てきますね。マスクして符号拡張してパックするやつとか。
SSE2だとDWORD->WORDのパックは符号ありとして扱われるから実は使えない？(符号なしのDWORD->WORDパック(PACKUSDW命令)はSSE4.1っぽい。)
NEONだとdeinterleaveが標準で実装されているのが羨ましい。

# 追記(2015/07/24)
64個のデータ x 2 を100000000回やってみた。
あれ？SSE2のほうが速いぞ？！

| 方式  | 時間[msec] |
|:-----:|----------:|
|  SISD |       5200 |
| SSSE3 |       1520 |
|  SSE2 |       1430 |