koturnの日記

普通の人です.ブログ上のコードはコピペ自由です.

SIMDの組み込み関数のことはじめ

はじめに

現代のCPUではSIMD(Single Instruction Multiple Data)命令を利用することができる. SIMD命令とはその名の通り,ひとつの命令で複数のデータを処理するものである.

Intel系のCPUでは,MMX/SSE/AVX/AVX-512といったSIMD命令が利用可能であり,ARM CPUではNEONというSIMD命令が用意されている. 各SIMDSIMD用のレジスタの対応関係は以下のようになる.

項目 利用可能レジスタ
MMX 64bit のMMレジスタ
SSE 128bit のXMMレジスタ
AVX 256bit のYMMレジシタ
AVX-512 512bit のZMMレジシタ
ARM NEON 64bitのD(Double-Word)レジスタおよび128bitのQ(Quad-Word)レジスタ

これらのレジスタを用いて,例えば4つのint型を一気に処理するといったことを行うのがCPUにおけるSIMDである.

この記事では,このSIMD命令をC/C++から利用することについて記述する.

2017/02/20 追記

以下の記事に,より詳細な内容を書いたので,参考になるかもしれない.

2019/02/03 追記

実行時にSSE/AVX等のx86/x64の命令が利用可能であるかをcpuidを用いて判断する方法について追記した. また,この記事中のユーティリティ関数をまとめたシングルヘッダファイルをkoturn/SimdUtilにて公開している.

SIMDをプログラム利用するには

SIMD命令というと小難しそうで,インラインアセンブラを利用しなければならないかというと,そうではない. C/C++から関数の形で利用できるように,各コンパイラで共通のAPIである組み込み関数が提供されている. 組み込み関数とはいえ関数なので,関数呼び出しの形で記述することになるが,実際に関数呼び出しが発生するわけではなく,インライン展開され,対応するアセンブラの命令へとコード生成される.

なお,SIMDレジスタに対して,メモリのロードやストアを行う場合,後述するように利用幅と同じ境界に配置されている位置に対して行う必要がある. 特に,MMX/SSE/AVX/AVX-512の場合,アラインメント条件を満たさなければ,SEGVで落ちる関数がある. 落ちない版の関数もあるが,そういった関数は落ちる関数より動作としては遅い.

ARM NEONは落ちる関数は無いが,アラインメント条件を満たしておいた方が高速に動作すると思われる.

インクルード

何はともあれ,まず組み込み関数が宣言されているヘッダをインクルードしなければ始まらない. 各SIMD命令セットとヘッダの対応関係は以下のようになる.

命令セット ヘッダファイル
MMX <mmintrin.h>
SSE <xmmintrin.h>
SSE2 <emmintrin.h>
SSE3 <pmmintrin.h>
SSSE3 <tmmintrin.h>
SSE4.1 <smmintrin.h>
SSE4.2 <nmmintrin.h>
AES <wmmintrin.h>
AVX, AVX2, FMA <immintrin.h>
AVX-512 <zmmintrin.h>
ARM NEON <arm_neon.h>

MMX/SSE/AVX/AVX-512関連のヘッダは多く,これらをいちいちインクルードするのは面倒である. 現実的にはまとめてインクルードすることが可能なヘッダを利用するのがよい. ただし,MSVCとgcc/clangでヘッダが異なるため,注意しなければならない.

環境 ヘッダファイル
MSVC <intrin.h>
gcc/clang <x86intrin.h>

具体的なインクルード部分のコードを書くと以下のようになる.

#ifdef _MSC_VER
#  include <intrin.h>
#else
#  include <x86intrin.h>
#endif

なお,gcc/clangでも,x64環境ならば <intrin.h> が存在するが,x86環境でも利用可能な方に合わせておく方が何かと都合が良いだろう.

コンパイルオプション

実はヘッダをインクルードするだけではSIMDの組み込み関数は利用できない. 以下のようにコンパイルオプションを指定する必要がある.

gccではヘッダをインクルードするだけではSIMDの組み込み関数は利用できないため,以下のようにコンパイルオプションを指定する必要がある. 一方,MSVCはオプション指定をしなくてもSIMDの組み込み関数を利用できる.

なお,全てのx64プロセッサではSSE2までは利用できるため,gccであってもx64バイナリを生成するのであれば, -msse2 といったオプションの指定無しにSSE2までの組み込み関数が利用できるようだ.

gccの場合,コンパイラの自動ベクトル化でどの命令を利用するかの許可と利用可能な組み込み関数の許可を兼ねているのに対し,MSVCは自動ベクトル化でどの命令を利用するかの許可のみである. x86/x64においては,後述するcpuidによる実行時の利用可能なSIMD命令の判定が可能なため,MSVCの方が融通が利くように思われる.

命令セット gccのオプション MSVCのオプション 定義されるマクロ
MMX -mmmx /arch:MMX __MMX__
SSE -msse /arch:SSE __SSE__
SSE2 -msse2 /arch:SSE2 __SSE2__
SSE3 -msse3 __SSE3__
SSSE3 -mssse3 __SSSE3__
SSE4.1 -msse4.1 __SSE4_1__
SSE4.2 -msse4.2 __SSE4_2__
AES -maes __AES__
AVX -mavx /arch:AVX __AVX__
AVX2 -mavx2 /arch:AVX2 __AVX2__
FMA -mfma __FMA__
AVX-512 -mavx512* ( *bw, cq, ed など) __AVX512*__
ARM NEON -mfpu=neon など __ARM_NEON または __ARM_NEON__

MMX/SSE/AVX/AVX-512関連のオプションは, -march=native-mtune=native などを指定することで,一括で上記のオプションのうち,利用可能なものを指定できる. ARM CPU環境のgccでは, -march=native-mtune=native と指定することができない場合があり,そのときは利用しているARM CPUに合わせて, -fpu=neon-fp-armv8 などと指定する必要がある(これはRaspberry Pi 3の例).

上記の表では簡略に紹介したが,gccのAVX-512に関するオプションは以下のように多数ある.

  • -mavx512f
  • -mavx512er
  • -mavx512cd
  • -mavx512pf
  • -mavx512dq
  • -mavx512bw
  • -mavx512vl
  • -mavx512ifma
  • -mavx512vbmi

なお,現在のところAVX-512が利用できるCPUは限られている. -march=native を指定したとしても,AVX-512が有効にならない場合の方が多いので,上記のオプションを別途指定すると,コンパイルだけは通るだろう. しかし,非対応のCPUでAVX-512命令を実行したとても,以下のようなエラーメッセージが出力されるだろう. (これはMSYS2でzsh上で実行した結果である)

$ ./main.exe
zsh: illegal hardware instruction  ./main.exe

AVX-512の動作を確認するだけならば,Intel公式のエミュレータを利用するとよい. 予め,AVX-512命令が含まれる実行バイナリを生成し,以下のように実行する.

$ sde -- ./main.exe

変数のアラインメントを指定する

C++11,C11から言語の標準機能として,変数のアラインメントを指定することができるようになったが,それ以前は変数のアラインメントはコンパイラ独自の機能を利用しなければ,指定することができない. 古いコンパイラコンパイルすることを考慮すると,以下のように差を吸収するマクロを定義するとよい.

#include <cstddef>
#include <iostream>

#if defined(__cplusplus) && __cplusplus < 201103L
#  ifdef _MSC_VER
#    define alignas(n)  __declspec(align(n))
#  else
#    define alignas(n)  __attribute__((aligned(n)))
#  endif  // _MSC_VER
#endif  // defined(__cplusplus) && __cplusplus < 201103L


// 以下,利用コード


int
main()
{
  static const int ALIGN = 32;
  alignas(ALIGN) unsigned char array[10] = {0};
  if ((reinterpret_cast<std::ptrdiff_t>(array)) % ALIGN == 0) {
    std::cout << "Static array is " << ALIGN << " byte aligned.\n";
  } else {
    std::cout << "Static array is not " << ALIGN << " byte aligned.\n";
  }

  return 0;
}

上記はC++用だが,C言語なら以下のように定義するとよい.

#include <stddef.h>
#include <stdio.h>

#if defined(__STDC_VERSION__) && __STDC_VERSION__ < 201102L
#  ifdef _MSC_VER
#    define _Alignas(n)  __declspec(align(n))
#  else
#    define _Alignas(n)  __attribute__((aligned(n)))
#  endif  // _MSC_VER
#endif  // defined(__cplusplus) && __cplusplus < 201103L


/* 以下,利用コード */


#define ALIGN  32

int
main(void)
{
  _Alignas(ALIGN) unsigned char array[10] = {0};
  if ((ptrdiff_t) array % ALIGN == 0) {
    printf("Static array is %d byte aligned.\n", ALIGN);
  } else {
    printf("Static array is not %d byte aligned.\n", ALIGN);
  }

  return 0;
}

アラインされたメモリを動的確保する

通常のC/C++における std::malloc()std::calloc()new 等では16byteや32byte境界にアラインメントされたメモリを動的確保することはできない. 以下に示す専用のメモリ確保関数が必要となる. (C言語の場合, <cstdlib><stdlib.h> に読み換えること)

メモリ確保関数 メモリ解放関数 ヘッダ 特徴
_aligned_malloc() _aligned_free() <malloc.h> MSVCのみ.
posix_memalign() std::free() <cstdlib> gcc/clangのみ.
aligned_alloc() std::free() <cstdlib> gcc/clangのみ.確保サイズはアラインメントの整数倍に限る.C11/C++17の標準ライブラリ関数
memalign() std::free() <malloc.h> gcc/clangのみ.廃止されているとのこと.
_mm_malloc() _mm_free() <malloc.h> Intel CPUのみ.

種々のアラインされたメモリ確保関数があり,どれを利用すればいいか判断に困るかもしれない. しかし,おおまかには,以下のように利用する関数を判断すればよい.

  • MSVCなら _aligned_malloc()_aligned_free()
  • gcc/clangなら posix_memalign()std::free()

これを考慮し,条件コンパイルで利用する関数を分岐するラッパー関数を作るとよい. 簡単なコードは以下のようになる.

なお,C++11以降, std::align()std::aligned_storage() といった関数が利用できるが, std::align() は既に確保されたバッファの指定されたアドレスからポインタを進め,アラインメント条件を満たす位置のアドレスを返却するだけの関数であり, std::aligned_storage() はアラインされた静的配列を作成するための関数なので,やや使い勝手が悪いといえる.

// <type_traits> はC++11以降のものなので,それ以前でコンパイルしたい場合は関連部分を削除すること
#include <cstddef>
#include <iostream>
#include <memory>
#include <type_traits>
#if defined(_MSC_VER) || defined(__MINGW32__)
#  include <malloc.h>
#else
#  include <cstdlib>
#endif  // defined(_MSC_VER) || defined(__MINGW32__)


/*!
 * @brief アラインメントされたメモリを動的確保する関数
 * @tparam T  確保するメモリの要素型.この関数の返却値はT*
 * @param [in] nBytes     確保するメモリサイズ (単位はbyte)
 * @param [in] alignment  アラインメント (2のべき乗を指定すること)
 * @return  アラインメントし,動的確保されたメモリ領域へのポインタ
 */
template<typename T = void>
static inline T*
alignedMalloc(std::size_t nBytes, std::size_t alignment = alignof(T)) noexcept
{
#if defined(_MSC_VER) || defined(__MINGW32__)
  return reinterpret_cast<T*>(::_aligned_malloc(nBytes, alignment));
#else
  void* p;
  return reinterpret_cast<T*>(::posix_memalign(&p, alignment, nBytes) == 0 ? p : nullptr);
#endif  // defined(_MSC_VER) || defined(__MINGW32__)
}


/*!
 * @brief アラインメントされたメモリを動的確保する関数.配列向けにalignedMallocの引数指定が簡略化されている
 * @tparam T  確保する配列の要素型.この関数の返却値はT*
 * @param [in] size       確保する要素数.すなわち確保するサイズは size * sizeof(T)
 * @param [in] alignment  アラインメント (2のべき乗を指定すること)
 * @return  アラインメントし,動的確保されたメモリ領域へのポインタ
 */
template<typename T>
static inline T*
alignedAllocArray(std::size_t size, std::size_t alignment = alignof(T)) noexcept
{
  return alignedMalloc<T>(size * sizeof(T), alignment);
}


/*!
 * @brief アラインメントされたメモリを解放する関数
 * @param [in] ptr  解放対象のメモリの先頭番地を指すポインタ
 */
static inline void
alignedFree(void* ptr) noexcept
{
#if defined(_MSC_VER) || defined(__MINGW32__)
  ::_aligned_free(ptr);
#else
  std::free(ptr);
#endif  // defined(_MSC_VER) || defined(__MINGW32__)
}


// 以下,利用コード


/*!
 * @brief std::unique_ptr で利用するアラインされたメモリ用のカスタムデリータ
 */
struct AlignedDeleter
{
  void
  operator()(void* p) const noexcept
  {
    alignedFree(p);
  }
};


int
main()
{
  static constexpr int ALIGN = 32;
  std::unique_ptr<unsigned char[], AlignedDeleter> array(alignedAllocArray<unsigned char>(10, ALIGN));
  if (array.get() == nullptr) {
    std::cerr << "Failed to allocate memory" << std::endl;
    return 1;
  }

  if ((reinterpret_cast<std::ptrdiff_t>(array.get())) % ALIGN == 0) {
    std::cout << "Dynamic allocated memory is " << ALIGN << " byte aligned.\n";
  } else {
    std::cout << "Dynamic allocated memory is not " << ALIGN << " byte aligned.\n";
  }

  return 0;
}

このコードはC++11の範疇のものであるが,C言語の範囲で書き直すと以下のようになる. C99以降は inline が利用可能であるが,古いコンパイラを使用することを考慮し,置き換えるマクロを記述する.

#include <stdio.h>
#include <stddef.h>
#if defined(_MSC_VER) || defined(__MINGW32__)
#  include <malloc.h>
#else
#  include <stdlib.h>
#endif  /* defined(_MSC_VER) || defined(__MINGW32__) */

#ifndef __cplusplus
#  if defined(_MSC_VER)
#    define inline      __inline
#    define __inline__  __inline
#  elif !defined(__GNUC__) && !defined(__STDC_VERSION__) || __STDC_VERSION__ < 199901L
#    define inline
#    define __inline
#  endif
#endif


/*!
 * @brief アラインメントされたメモリを動的確保する関数
 * @param [in] size       確保するメモリサイズ (単位はbyte)
 * @param [in] alignment  アラインメント (2のべき乗を指定すること)
 * @return  アラインメントし,動的確保されたメモリ領域へのポインタ
 */
static inline void*
alignedMalloc(size_t size, size_t alignment)
{
#if defined(_MSC_VER) || defined(__MINGW32__)
  return _aligned_malloc(size, alignment);
#else
  void* p;
  return posix_memalign((void**) &p, alignment, size) == 0 ? p : NULL;
#endif  /* _MSC_VER */
}


/*!
 * @brief アラインメントされたメモリを解放する関数
 * @param [in] ptr  解放対象のメモリの先頭番地を指すポインタ
 */
static inline void
alignedFree(void* ptr)
{
#if defined(_MSC_VER) || defined(__MINGW32__)
  _aligned_free(ptr);
#else
  free(ptr);
#endif  /* _MSC_VER */
}


/* 以下,利用コード */


int
main(void)
{
  static const int ALIGN = 32;
  unsigned char* array = (unsigned char*) alignedMalloc(10 * sizeof(unsigned char), ALIGN);
  if (array == NULL) {
    fprintf(stderr, "Failed to allocate memory\n");
    return 1;
  }

  if (((ptrdiff_t) array) % ALIGN == 0) {
    printf("Dynamic allocated memory is %d byte aligned.\n", ALIGN);
  } else {
    printf("Dynamic allocated memory is not %d byte aligned.\n", ALIGN);
  }
  alignedFree(array);

  return 0;
}

なお,今回は適当なアラインメントを指定したが,実際にSSE/AVX/AVX-512/NEONを用いるときは,SSE/AVX/AVX-512/NEONの変数型からアラインメントを取得するとよい. 型や変数からアラインメントを得る機能はC++11およびC11以降であれば, alignof 演算子で取得でき,それ以前の環境であれば,コンパイラ拡張機能を用いることで取得できる. この差を吸収するなら,以下のようなマクロを定義するとよい.

#if defined(__cplusplus) && __cplusplus < 201103L
#  ifdef _MSC_VER
#    define alignof(n)  __alignof(n)
#  else
#    define alignof(n)  __alignof__(n)
#  endif  // _MSC_VER
#endif  // defined(__cplusplus) || cplusplus < 201103L

// alingas(alignof(__m256i)) のような形で使用

SSE/AVX/NEON のサンプルコード

簡単なサンプルコードをSSE/AVX/NEONの例として提示する. このコードはMSVC/gc/clangのいずれのコンパイラでもコンパイルすることができるようにしている.

AVX-512については,利用可能なCPUを搭載したマシンが手元に無いため割愛するが,AVXと同様のコードで記述できると思う. コンパイル時に以下のマクロを定義すると,対応した命令を用いたコードが有効化される. 有効化しようとしても,コンパイラが対応していない場合は,冒頭の部分でエラーが発生するはずだ. また,以下のいずれのマクロも定義しなかった場合,SIMDを用いないコードとなる.

マクロ 有効化されるSIMD
ENABLE_AVX AVX
ENABLE_SSE SSE
ENABLE_NEON ARM NEON

直接的に __AVX____SSE2__ 等のマクロが定義されているかどうかで判断しないのは,コンパイラAPIとして提供していたとしても,CPUが対応しておらず,SIMD命令を利用できない場合もあるからだ. また,AVXやSSEの切り替えが容易になり,ベンチマークテストがしやすいという利点もあるだろう.

さて,具体的には以下のようにオプションを指定してコンパイルするとよい. gccの場合は,

有効化する機能 コマンド
AVX-512 $ g++ -std=gnu++11 -march=native -mavx512f -DENABLE_AVX main.cpp -o main.o
AVX $ g++ -std=gnu++11 -march=native -DENABLE_AVX main.cpp -o main.o
SSE $ g++ -std=gnu++11 -march=native -DENABLE_SSE main.cpp -o main.o
ARM NEON $ g++ -std=gnu++11 -mfpu=neon-fp-armv8 -DENABLE_NEON main.cpp -o main.o
SIMDを利用しない $ g++ -std=gnu++11 main.cpp -o main.o

であり,MSVCの場合は,

有効化する機能 コマンド
AVX > cl.exe /arch:AVX /DENABLE_AVX main.cpp
SSE > cl.exe /arch:SSE2 /DENABLE_SSE main.cpp
SIMDを利用しない > cl.exe main.cpp

といった具合である.

ベクトルの内積計算

定番のベクトルの内積を計算するコードを示す. FMA(積和演算)が利用可能な場合は,そちらを用いて,高速に処理できるようにしてある. また,SIMDを用いない場合であっても,C++11/C11以降で <cmath> から提供されている std::fma() を用いることで,内積計算の高速化が期待できるようにする.

#if defined(ENABLE_AVX512) && !defined(__AVX512F__)
#  error Macro: ENABLE_AVX512 is defined, but unable to use AVX512F intrinsic functions
#elif defined(ENABLE_AVX) && !defined(__AVX__)
#  error Macro: ENABLE_AVX is defined, but unable to use AVX intrinsic functions
#elif defined(ENABLE_SSE) && !defined(__SSE2__)
#  error Macro: ENABLE_SSE is defined, but unable to use SSE intrinsic functions
#elif defined(ENABLE_NEON) && !defined(__ARM_NEON) && !defined(__ARM_NEON__)
#  error Macro: ENABLE_NEON is defined, but unable to use NEON intrinsic functions
#else


#include <cmath>
#include <cstddef>
#include <algorithm>
#include <iostream>
#include <memory>
#include <type_traits>
#if defined(_MSC_VER) || defined(__MINGW32__)
#  include <malloc.h>
#else
#  include <cstdlib>
#endif
#if defined(ENABLE_AVX512) || defined(ENABLE_AVX) || defined(ENABLE_SSE)
#  ifdef _MSC_VER
#    include <intrin.h>
#  else
#    include <x86intrin.h>
#  endif  // _MSC_VER
#elif defined(ENABLE_NEON)
#  include <arm_neon.h>
#endif  // defined(ENABLE_AVX512) || defined(ENABLE_AVX) || defined(ENABLE_SSE)


/*!
 * @brief アラインメントされたメモリを動的確保する関数
 * @tparam T  確保するメモリの要素型.この関数の返却値はT*
 * @param [in] nBytes     確保するメモリサイズ (単位はbyte)
 * @param [in] alignment  アラインメント (2のべき乗を指定すること)
 * @return  アラインメントし,動的確保されたメモリ領域へのポインタ
 */
template<typename T = void>
static inline T*
alignedMalloc(std::size_t nBytes, std::size_t alignment = alignof(T)) noexcept
{
#if defined(_MSC_VER) || defined(__MINGW32__)
  return reinterpret_cast<T*>(::_aligned_malloc(nBytes, alignment));
#else
  void* p;
  return reinterpret_cast<T*>(::posix_memalign(&p, alignment, nBytes) == 0 ? p : nullptr);
#endif  // defined(_MSC_VER) || defined(__MINGW32__)
}


/*!
 * @brief アラインメントされたメモリを動的確保する関数.配列向けにalignedMallocの引数指定が簡略化されている
 * @tparam T  確保する配列の要素型.この関数の返却値はT*
 * @param [in] size       確保する要素数.すなわち確保するサイズは size * sizeof(T)
 * @param [in] alignment  アラインメント (2のべき乗を指定すること)
 * @return  アラインメントし,動的確保されたメモリ領域へのポインタ
 */
template<typename T>
static inline T*
alignedAllocArray(std::size_t size, std::size_t alignment = alignof(T)) noexcept
{
  return alignedMalloc<T>(size * sizeof(T), alignment);
}


/*!
 * @brief アラインメントされたメモリを解放する関数
 * @param [in] ptr  解放対象のメモリの先頭番地を指すポインタ
 */
static inline void
alignedFree(void* ptr) noexcept
{
#if defined(_MSC_VER) || defined(__MINGW32__)
  ::_aligned_free(ptr);
#else
  std::free(ptr);
#endif  // defined(_MSC_VER) || defined(__MINGW32__)
}


/*!
 * @brief std::unique_ptr で利用するアラインされたメモリ用のカスタムデリータ
 */
struct AlignedDeleter
{
  void
  operator()(void* p) const noexcept
  {
    alignedFree(p);
  }
};


#if defined(ENABLE_AVX512)
static constexpr int ALIGN = alignof(__m512);
#elif defined(ENABLE_AVX)
static constexpr int ALIGN = alignof(__m256);
#elif defined(ENABLE_SSE)
static constexpr int ALIGN = alignof(__m128);
#elif defined(ENABLE_NEON)
static constexpr int ALIGN = alignof(float32x4_t);
#else
static constexpr int ALIGN = 8;
#endif  // defined(ENABLE_AVX512)


/*!
 * @brief 内積計算を行う関数
 * @param [in] a  ベクトルその1
 * @param [in] b  ベクトルその2
 * @param [in] n  ベクトルのサイズ
 * @return  内積
 */
static inline float
innerProduct(const float* a, const float* b, std::size_t n)
{
#if defined(ENABLE_AVX512)
  static constexpr std::size_t INTERVAL = sizeof(__m512) / sizeof(float);
  __m512 sumx16 = {0};
  for (std::size_t i = 0; i < n; i += INTERVAL) {
    __m512 ax16 = _mm512_load_ps(&a[i]);
    __m512 bx16 = _mm512_load_ps(&b[i]);
#  ifdef __FMA__
    sumx16 = _mm512_fmadd_ps(ax16, bx16, sumx16);
#  else
    sumx16 = _mm512_add_ps(sumx16, _mm512_mul_ps(ax16, bx16));
#  endif  // __FMA__
  }

  alignas(ALIGN) float s[INTERVAL] = {0};
  _mm512_store_ps(s, sumx16);

  std::size_t offset = n - n % INTERVAL;
  return std::inner_product(
      a + offset,
      a + n,
      b + offset,
      std::accumulate(std::begin(s), std::end(s), 0.0f));
#elif defined(ENABLE_AVX)
  static constexpr std::size_t INTERVAL = sizeof(__m256) / sizeof(float);
  __m256 sumx8 = {0};
  for (std::size_t i = 0; i < n; i += INTERVAL) {
    __m256 ax8 = _mm256_load_ps(&a[i]);
    __m256 bx8 = _mm256_load_ps(&b[i]);
#  ifdef __FMA__
    sumx8 = _mm256_fmadd_ps(ax8, bx8, sumx8);
#  else
    sumx8 = _mm256_add_ps(sumx8, _mm256_mul_ps(ax8, bx8));
#  endif  // __FMA__
  }

  alignas(ALIGN) float s[INTERVAL] = {0};
  _mm256_store_ps(s, sumx8);

  std::size_t offset = n - n % INTERVAL;
  return std::inner_product(
      a + offset,
      a + n,
      b + offset,
      std::accumulate(std::begin(s), std::end(s), 0.0f));
#elif defined(ENABLE_SSE)
  static constexpr std::size_t INTERVAL = sizeof(__m128) / sizeof(float);
  __m128 sumx4 = {0};
  for (std::size_t i = 0; i < n; i += INTERVAL) {
    __m128 ax4 = _mm_load_ps(&a[i]);
    __m128 bx4 = _mm_load_ps(&b[i]);
#  ifdef __FMA__
    sumx4 = _mm_fmadd_ps(ax4, bx4, sumx4);
#  else
    sumx4 = _mm_add_ps(sumx4, _mm_mul_ps(ax4, bx4));
#  endif  // __FMA__
  }

  alignas(ALIGN) float s[INTERVAL] = {0};
  _mm_store_ps(s, sumx4);
  float sum = std::accumulate(std::begin(s), std::end(s), 0.0f);

  std::size_t offset = n - n % INTERVAL;
  return std::inner_product(
      a + offset,
      a + n,
      b + offset,
      std::accumulate(std::begin(s), std::end(s), 0.0f));
#elif defined(ENABLE_NEON)
  static constexpr std::size_t INTERVAL = sizeof(float32x4_t) / sizeof(float);
  float32x4_t sumx4 = {0};
  for (std::size_t i = 0; i < n; i += INTERVAL) {
    float32x4_t ax4 = vld1q_f32(&a[i]);
    float32x4_t bx4 = vld1q_f32(&b[i]);
    sumx4 = vmlaq_f32(sumx4, ax4, bx4);
  }

  std::size_t offset = n - n % INTERVAL;
  return std::inner_product(
      a + offset,
      a + n,
      b + offset,
      std::accumulate(std::begin(s), std::end(s), 0.0f));
#else
  float sum = 0.0f;
  for (std::size_t i = 0; i < n; i++) {
    // <cmath>のstd::fma関数を用いると,積和演算がハードウェアのサポートを受けることを期待できる
    // 処理としては, sum += a[i] * b[i]; と同じ
    sum = std::fma(a[i], b[i], sum);
  }
  return sum;
#endif  // defined(ENABLE_AVX512)
}


int
main()
{
  static constexpr int N_ELEMENT = 256;

  std::unique_ptr<float[], AlignedDeleter> a(alignedAllocArray<float>(N_ELEMENT, ALIGN));
  std::unique_ptr<float[], AlignedDeleter> b(alignedAllocArray<float>(N_ELEMENT, ALIGN));
  for (int i = 0; i < N_ELEMENT; i++) {
    a[i] = static_cast<float>(i);
    b[i] = static_cast<float>(i);
  }
  std::cout << innerProduct(a.get(), b.get(), N_ELEMENT) << std::endl;

  return 0;
}


#endif  // defined(ENABLE_AVX512) && !defined(__AVX512F__)

最近傍法による画像の2倍拡大

最近傍法,すなわち単純なピクセルコピーのみを行って,8bitグレースケール画像を2倍に拡大するコードを記述する. 2倍拡大という条件に限定すれば,出力先画像のインデックス値のとる値が単純になるので,SIMDで簡単に処理を記述できる.

読み込む画像ファイル名は test.jpg とし,読み込みにOpenCVを用いる. 画像ファイルの横幅は,16または32の倍数でなければならない.

コンパイルは以下のようにするとよい.

$ g++ -std=gnu++11 main.cpp -march=native -DENABLE_AVX -I/usr/include/opencv -I/usr/include/opencv2 -lopencv_core -lopencv_highgui -lopencv_imgcodecs -o main.o

AVX-512を利用する場合は, -mavx512vbmi -DENABLE_AVX512 を付加するとよい.

なお,OpenCVcv::Matカスタムアロケータを適用することができるらしいが,コードが煩雑になりそうなので,SSE/AVXにおいてはアラインメント条件を満たさなくてもよい関数を用いている.

#if defined(ENABLE_AVX512) && !defined(__AVX512F__)
#  error Macro: ENABLE_AVX512 is defined, but unable to use AVX512F intrinsic functions
#elif defined(ENABLE_AVX) && !defined(__AVX__)
#  error Macro: ENABLE_AVX is defined, but unable to use AVX intrinsic functions
#elif defined(ENABLE_SSE) && !defined(__SSE2__)
#  error Macro: ENABLE_SSE is defined, but unable to use SSE intrinsic functions
#elif defined(ENABLE_NEON) && !defined(__ARM_NEON) && !defined(__ARM_NEON__)
#  error Macro: ENABLE_NEON is defined, but unable to use NEON intrinsic functions
#else  // defined(ENABLE_AVX512) && !defined(__AVX512F__)


#include <cmath>
#include <cstddef>
#include <iostream>
#include <memory>
#include <type_traits>
#if defined(_MSC_VER) || defined(__MINGW32__)
#  include <malloc.h>
#else
#  include <cstdlib>
#endif
#if defined(ENABLE_AVX512) || defined(ENABLE_AVX) || defined(ENABLE_SSE)
#  ifdef _MSC_VER
#    include <intrin.h>
#  else
#    include <x86intrin.h>
#  endif  // _MSC_VER
#elif defined(ENABLE_NEON)
#  include <arm_neon.h>
#endif  // defined(ENABLE_AVX512) || defined(ENABLE_AVX) || defined(ENABLE_SSE)

#include <opencv2/opencv.hpp>


#if defined(_MSC_VER) && _MSC_VER >= 1400 || \
  defined(__GNUC__) && defined(__GNUC_MINOR__) && (__GNUC__ > 2 || __GNUC__ == 2 && __GNUC_MINOR__ >= 92)
#  define restrict  __restrict
#else
#  define restrict
#endif


/*!
 * @brief アラインメントされたメモリを動的確保する関数
 * @tparam T  確保するメモリの要素型.この関数の返却値はT*
 * @param [in] nBytes     確保するメモリサイズ (単位はbyte)
 * @param [in] alignment  アラインメント (2のべき乗を指定すること)
 * @return  アラインメントし,動的確保されたメモリ領域へのポインタ
 */
template<typename T = void>
static inline T*
alignedMalloc(std::size_t nBytes, std::size_t alignment = alignof(T)) noexcept
{
#if defined(_MSC_VER) || defined(__MINGW32__)
  return reinterpret_cast<T*>(::_aligned_malloc(nBytes, alignment));
#else
  void* p;
  return reinterpret_cast<T*>(::posix_memalign(&p, alignment, nBytes) == 0 ? p : nullptr);
#endif  // defined(_MSC_VER) || defined(__MINGW32__)
}


/*!
 * @brief アラインメントされたメモリを動的確保する関数.配列向けにalignedMallocの引数指定が簡略化されている
 * @tparam T  確保する配列の要素型.この関数の返却値はT*
 * @param [in] size       確保する要素数.すなわち確保するサイズは size * sizeof(T)
 * @param [in] alignment  アラインメント (2のべき乗を指定すること)
 * @return  アラインメントし,動的確保されたメモリ領域へのポインタ
 */
template<typename T>
static inline T*
alignedAllocArray(std::size_t size, std::size_t alignment = alignof(T)) noexcept
{
  return alignedMalloc<T>(size * sizeof(T), alignment);
}


/*!
 * @brief アラインメントされたメモリを解放する関数
 * @param [in] ptr  解放対象のメモリの先頭番地を指すポインタ
 */
static inline void
alignedFree(void* ptr) noexcept
{
#if defined(_MSC_VER) || defined(__MINGW32__)
  ::_aligned_free(ptr);
#else
  std::free(ptr);
#endif  // defined(_MSC_VER) || defined(__MINGW32__)
}


#if defined(ENABLE_AVX512)
static constexpr int ALIGN = alignof(__m512i);
#elif defined(ENABLE_AVX)
static constexpr int ALIGN = alignof(__m256i);
#elif defined(ENABLE_SSE)
static constexpr int ALIGN = alignof(__m128i);
#elif defined(ENABLE_NEON)
static constexpr int ALIGN = alignof(uint8x16_t);
#else
static constexpr int ALIGN = 8;
#endif  // defined(ENABLE_AVX512)


/*!
 * @brief 入力画像データを最近傍法により,2倍のサイズに拡大する
 * @param [out] dstImageData  出力画像データ領域の先頭へのポインタ
 * @param [in]  dstWidth      出力画像データの横幅
 * @param [in]  dstHeight     出力画像データの縦幅
 * @param [in]  srcImageData  入力画像データ領域の先頭へのポインタ
 * @param [in]  srcWidth      入力画像データの横幅
 * @param [in]  srcHeight     入力画像データの縦幅
 * @return  アラインメントし,動的確保されたメモリ領域へのポインタ
 */
static inline void
scale2x(
    unsigned char* restrict dstImageData,
    int dstWidth,
    int dstHeight,
    const unsigned char* restrict srcImageData,
    int srcWidth,
    int srcHeight) noexcept
{
  static constexpr int X_RATIO = 2;
  static constexpr int Y_RATIO = 2;
#if defined(ENABLE_AVX512)
  static constexpr int INTERVAL = sizeof(__m512i) / sizeof(unsigned char);
  static const __m512i LOWIDX = _mm512_setr_epi64(
      0x4303420241014000,
      0x4707460645054404,
      0x4b0b4a0a49094808,
      0x4f0f4e0e4d0d4c0c,
      0x5313521251115010,
      0x5717561655155414,
      0x5b1b5a1a59195818,
      0x5f1f5e1e5d1d5c1c);
  static const __m512i HIGHIDX = _mm512_setr_epi64(
      0x6323622261216020,
      0x6727662665256424,
      0x6b2b6a2a69296828,
      0x6f2f6e2e6d2d6c2c,
      0x7333723271317030,
      0x7737763675357434,
      0x7b3b7a3a79397838,
      0x7f3f7e3e7d3d7c3c);
#elif defined(ENABLE_AVX)
  static constexpr int INTERVAL = sizeof(__m256i) / sizeof(unsigned char);
#elif defined(ENABLE_SSE)
  static constexpr int INTERVAL = sizeof(__m128i) / sizeof(unsigned char);
#elif defined(ENABLE_NEON)
  static constexpr int INTERVAL = sizeof(uint8x16_t) / sizeof(unsigned char);
#else
  static constexpr int INTERVAL = sizeof(unsigned char);
#endif  // defined(ENABLE_AVX512)

  for (int i = 0; i < dstHeight; i++) {
    for (int j = 0; j < dstWidth; j += INTERVAL * X_RATIO) {
#if defined(ENABLE_AVX512)
      // 64pixel分の画素データをロード
      __m512i v512 = _mm512_loadu_si512(reinterpret_cast<const __m512i*>(&srcImageData[i / Y_RATIO * srcWidth + j / X_RATIO]));
      // インタリーブ
      __m512i v512l = _mm512_permutex2var_epi8(v512, LOWIDX, v512);
      __m512i v512u = _mm512_permutex2var_epi8(v512, HIGHIDX, v512);
      // 64pixel x 2のデータを書き込み
      _mm512_storeu_si512(reinterpret_cast<__m512i*>(&dstImageData[i * dstWidth + j + sizeof(__m512i) * 0]), v512l);
      _mm512_storeu_si512(reinterpret_cast<__m512i*>(&dstImageData[i * dstWidth + j + sizeof(__m512i) * 1]), v512u);
#elif defined(ENABLE_AVX)
      // 32pixel分の画素データをロード
      __m256i v256 = _mm256_loadu_si256(reinterpret_cast<const __m256i*>(&srcImageData[i / Y_RATIO * srcWidth + j / X_RATIO]));
      // インタリーブ
      __m256i v256l_ = _mm256_unpacklo_epi8(v256, v256);
      __m256i v256u_ = _mm256_unpackhi_epi8(v256, v256);
      // 上下128bit交換
      __m256i v256l = _mm256_permute2f128_si256(v256l_, v256u_, 0x20);
      __m256i v256u = _mm256_permute2f128_si256(v256l_, v256u_, 0x31);
      // 32pixel x 2のデータを書き込み
      _mm256_storeu_si256(reinterpret_cast<__m256i*>(&dstImageData[i * dstWidth + j + sizeof(__m256i) * 0]), v256l);
      _mm256_storeu_si256(reinterpret_cast<__m256i*>(&dstImageData[i * dstWidth + j + sizeof(__m256i) * 1]), v256u);
#elif defined(ENABLE_SSE)
      // 16pixel分の画素データをロード
      __m128i v128 = _mm_loadu_si128(reinterpret_cast<const __m128i*>(&srcImageData[i / Y_RATIO * srcWidth + j / X_RATIO]));
      // インタリーブ
      __m128i v128l = _mm_unpacklo_epi8(v128, v128);
      __m128i v128u = _mm_unpackhi_epi8(v128, v128);
      // 16pixel x 2のデータを書き込み
      _mm_storeu_si128(reinterpret_cast<__m128i*>(&dstImageData[i * dstWidth + j + sizeof(__m128i) * 0]), v128l);
      _mm_storeu_si128(reinterpret_cast<__m128i*>(&dstImageData[i * dstWidth + j + sizeof(__m128i) * 1]), v128u);
#elif defined(ENABLE_NEON)
      // 16pixel分の画素データをロード
      uint8x16_t v128 = vld1q_u8(&srcImageData[i / Y_RATIO * srcWidth + j]);
      // インタリーブ
      uint8x16x2_t v128x2 = vzipq_u8(v128, v128);
      // 16pixel x 2のデータを書き込み
      vst1q_u8(dstImageData[i * dstWidth + j + sizeof(uint8x16_t) * 0], v128x2.val[0]);
      vst1q_u8(dstImageData[i * dstWidth + j + sizeof(uint8x16_t) * 1], v128x2.val[1]);
#else
      dstImageData[i * dstWidth + j] = srcImageData[i / Y_RATIO * srcWidth + j];
#endif  // defined(ENABLE_AVX512)
    }
  }
}


int
main()
{
  cv::Mat img = cv::imread("test.jpg", 0);
  if (img.data == nullptr) {
    std::cerr << "Cannot open image file: test.jpg" << std::endl;
    return 1;
  }
  cv::Mat scaledImg(cv::Size(img.cols * 2, img.rows * 2), CV_8UC1);
  scale2x(scaledImg.data, scaledImg.cols, scaledImg.rows, img.data, img.cols, img.rows);

  cv::namedWindow("src", CV_WINDOW_AUTOSIZE);
  cv::namedWindow("scaled", CV_WINDOW_AUTOSIZE);
  cv::imshow("src", img);
  cv::imshow("scaled", scaledImg);
  std::cout << "Please hit any key on the window to exit this program" << std::endl;
  cv::waitKey(0);

  return 0;
}


#endif  // defined(ENABLE_AVX512) && !defined(__AVX512F__)

何の脈略も無しに,SSE/AVXやARM NEONの組み込み関数や型を利用したが,SSE/AVXに関してはIntelIntrinsics Guideを,ARM NEONに関してはARM NEON Intrinsicsを参照するとよい.

SSE/AVXの変数型は以下の通り.

内容
__m128 float 型4個分
__m128d double 型2個分
__m128i 整数型 (intunsigned char などを格納できる)
__m256 float 型8個分
__m256d double 型4個分
__m256i 整数型 (intunsigned char などを格納できる)
__m512 float 型16個分
__m512d double 型8個分
__m512i 整数型 (intunsigned char などを格納できる)

SSE/AVXの組み込み関数は基本的に

  • SSEの場合, _mm_[xxx]{[u]}_[yyy]
  • AVXの場合, _mm256_[xxx]{[u]}_[yyy]
  • AVX-512の場合, _mm512_[xxx]{[u]}_[yyy]

の形式で命名されている. [xxx][{u}][yyy] の部分については以下の通り.

該当部分 内容
[xxx] loadstore など,行いたい命令がここにくる
[u] u が付いている関数はアラインメント条件を満たしていなくても,SEGVで落ちない
[yyy] 引数の型によって変化する. ps なら __m128pd なら __m128dsi128 なら __m128i

pspd はそれぞれ Precision Single, Precision Double の略であるそうだ. (si は調べていない)

ARM NEONの変数型は見た目通り, [xxx][size]x[NNN]{x[MMM]} の形式となっている.

該当部分 内容
[xxx] uintintfloat などのベクタの1要素の型がここにくる
[size] ベクタの要素型1つのサイズ (単位はbit)
[NNN] ベクタ要素の個数
[MMM] インタリーブ用にくっつけたNEONレジスタの個数.2から4までの値ろ取り,1つの場合は省略される

ARM NEONの組み込み関数も直感的に利用できる命名で, v[xxx]{[q]}_{yyy} となっている.

該当部分 内容
[xxx] addld など,行いたい命令がここにくる
[q] qが付いていればQレジスタ(128bit)を用いる命令,付いていないならばDレジスタ(64bit)を用いる命令
[yyy] 引数の型によって変化する. u8s16f32 など

SSEやAVXが実行時に利用可能かどうかを調べる

利用可能かどうかを調べるモチベーション

ここまではコンパイル時にどの命令を使用するかを指定することを前提にしていた. しかし,実行時にSIMD命令が利用可能かどうかを調べたい場合がある.

Linuxであれば,基本的にプログラムはその環境でコンパイルし,実行することが多いため,実行時にSIMD命令が利用可能かどうかを調べなくてもよいが,Windowsにおいてはある環境でコンパイルしたプログラムを様々な環境で動作させることが多いため,利用可否を調べる必要がある.

ここでは,SSE/AVX等のx86/x64におけるSIMD命令が利用可能かどうかを調べる方法を示す. (ARMのNEONについては未調査)

cpuid命令とcpuidの組み込み関数

答えは簡単でcpuid命令を利用するとよい. この命令はアセンブラでは1命令として用意されている.

mov $1,%eax  ; cpuidの引数1
mov $0,%ecx  ; cpuidの引数2
cpuid  ; これでeax, ebx, ecx, edxに結果が格納される

まず eax および ecx に取得したいCPUの情報に関する値をセットし,その後cpuid命令を実行すると,eax, ebx, ecx, edxに情報が返却される命令となっている.

アセンブラ,およびインラインアセンブラでなければ利用できないのかというとそうではなく,gcc, clang, MSVCであれば,cpuidの組み込み関数が用意されている. しかし,gcc/clangとMSVCで引数等が異なるため,以下のように統一して利用できるインライン関数を用意すると楽である.

#include <array>
#include <type_traits>

#if defined(__GNUC__)
#  include <cpuid.h>
#elif defined(_MSC_VER)
#  include <intrin.h>
#endif

/*!
 * @brief cpuidの実行結果を第一引数に格納する
 *
 * 実行結果のeaxをcpuInfo[0],ebxをcpuInfo[1],ecxをcpuInfo[2],edxをcpuInfo[3]にコピーする
 *
 * @tparam T  int*
 * @param [out] cpuInfo  cpuidの結果格納先.cpuInfo[0]からcpuInfo[3]に結果が格納される.
 * @param [in]  eax  cpuidの引数
 */
template<
  typename T,
  typename std::enable_if<std::is_same<T, int*>::value, std::nullptr_t>::type = nullptr
>
static inline void
cpuid(T cpuInfo, int eax) noexcept
{
#if defined(__GNUC__)
  ::__cpuid(eax, cpuInfo[0], cpuInfo[1], cpuInfo[2], cpuInfo[3]);
#elif defined(_MSC_VER)
  ::__cpuid(cpuInfo, eax);
#endif  // defined(__GNUC__)
}


/*!
 * @brief cpuidの実行結果を第一引数の配列に格納する
 *
 * 実行結果のeaxをcpuInfo[0],ebxをcpuInfo[1],ecxをcpuInfo[2],edxをcpuInfo[3]にコピーする
 *
 * @tparam kSize  配列サイズ
 * @param [out] cpuInfo  cpuidの結果格納先配列.要素数が4以上でなければコンパイルエラーとなる
 * @param [in]  eax  cpuidの引数
 */
template<std::size_t kSize>
static inline void
cpuid(int (&cpuInfo)[kSize], int eax) noexcept
{
  static_assert(kSize >= 4, "CPU info array size must be four or more");

  cpuid(&cpuInfo[0], eax);
}


/*!
 * @brief cpuidの実行結果を第一引数のstd::arrayに格納する
 *
 * 実行結果のeaxをcpuInfo[0],ebxをcpuInfo[1],ecxをcpuInfo[2],edxをcpuInfo[3]にコピーする
 *
 * @tparam kSize  配列サイズ
 * @param [out] cpuInfo  cpuidの結果格納先配列.要素数が4以上でなければコンパイルエラーとなる
 * @param [in]  eax  cpuidの引数
 */
template<std::size_t kSize>
static inline void
cpuid(std::array<int, kSize>& cpuInfo, int eax) noexcept
{
  static_assert(kSize >= 4, "CPU info array size must be four or more");

  cpuid(cpuInfo.data(), eax);
}


/*!
 * @brief cpuidの実行結果を第一引数に格納する
 *
 * 実行結果のeaxをcpuInfo[0],ebxをcpuInfo[1],ecxをcpuInfo[2],edxをcpuInfo[3]にコピーする
 *
 * @tparam T  int*
 * @param [out] cpuInfo  cpuidの結果格納先.cpuInfo[0]からcpuInfo[3]に結果が格納される.
 * @param [in]  eax  cpuidの引数
 * @param [in]  ecx  cpuidの引数
 */
template<
  typename T,
  typename std::enable_if<std::is_same<T, int*>::value, std::nullptr_t>::type = nullptr
>
static inline void
cpuidex(T cpuInfo, int eax, int ecx) noexcept
{
#if defined(__GNUC__)
  ::__cpuid_count(eax, ecx, cpuInfo[0], cpuInfo[1], cpuInfo[2], cpuInfo[3]);
#elif defined(_MSC_VER)
  ::__cpuidex(cpuInfo, eax, ecx);
#endif  // defined(__GNUC__)
}


/*!
 * @brief cpuidの実行結果を第一引数の配列に格納する
 *
 * 実行結果のeaxをcpuInfo[0],ebxをcpuInfo[1],ecxをcpuInfo[2],edxをcpuInfo[3]にコピーする
 *
 * @tparam kSize  配列サイズ
 * @param [out] cpuInfo  cpuidの結果格納先配列.要素数が4以上でなければコンパイルエラーとなる
 * @param [in]  eax  cpuidの引数
 * @param [in]  ecx  cpuidの引数
 */
template<std::size_t kSize>
static inline void
cpuidex(int (&cpuInfo)[kSize], int eax, int ecx) noexcept
{
  static_assert(kSize >= 4, "[util::cpuidex] CPU info array size must be four or more");

  cpuidex(&cpuInfo[0], eax, ecx);
}


/*!
 * @brief cpuidの実行結果を第一引数のstd::arrayに格納する
 *
 * 実行結果のeaxをcpuInfo[0],ebxをcpuInfo[1],ecxをcpuInfo[2],edxをcpuInfo[3]にコピーする
 *
 * @tparam kSize  配列サイズ
 * @param [out] cpuInfo  cpuidの結果格納先配列.要素数が4以上でなければコンパイルエラーとなる
 * @param [in]  eax  cpuidの引数
 * @param [in]  ecx  cpuidの引数
 */
template<std::size_t kSize>
static inline void
cpuidex(std::array<int, kSize>& cpuInfo, int eax, int ecx) noexcept
{
  static_assert(kSize >= 4, "[util::cpuidex] CPU info array size must be four or more");

  cpuidex(cpuInfo.data(), eax, ecx);
}

cpuid() はeaxを指定し,ecxは0として,第一引数にeaxからedxの値を順に格納する関数, cpuidex()cpuid() のecx指定版である.

上記は第一引数に配列や sd::array を放り込んだとき,サイズをコンパイル時に判定するようにしてある. C言語用に書き直すなら以下のような単純な形でよい.

#if defined(__GNUC__)
#  include <cpuid.h>
#elif defined(_MSC_VER)
#  include <intrin.h>
#endif

#ifndef __cplusplus
#  if defined(_MSC_VER)
#    define inline      __inline
#    define __inline__  __inline
#  elif !defined(__GNUC__) && !defined(__STDC_VERSION__) || __STDC_VERSION__ < 199901L
#    define inline
#    define __inline
#  endif
#endif


/*!
 * @brief cpuidの実行結果を第一引数に格納する
 *
 * 実行結果のeaxをcpuInfo[0],ebxをcpuInfo[1],ecxをcpuInfo[2],edxをcpuInfo[3]にコピーする
 *
 * @param [out] cpuInfo  cpuidの結果格納先.cpuInfo[0]からcpuInfo[3]に結果が格納される.
 * @param [in]  eax  cpuidの引数
 */
static inline void
cpuid(int* cpuInfo, int eax)
{
#if defined(__GNUC__)
  __cpuid(eax, cpuInfo[0], cpuInfo[1], cpuInfo[2], cpuInfo[3]);
#elif defined(_MSC_VER)
  __cpuid(cpuInfo, eax);
#endif  // defined(__GNUC__)
}


/*!
 * @brief cpuidの実行結果を第一引数に格納する
 *
 * 実行結果のeaxをcpuInfo[0],ebxをcpuInfo[1],ecxをcpuInfo[2],edxをcpuInfo[3]にコピーする
 *
 * @param [out] cpuInfo  cpuidの結果格納先.cpuInfo[0]からcpuInfo[3]に結果が格納される.
 * @param [in]  eax  cpuidの引数
 * @param [in]  ecx  cpuidの引数
 */
static inline void
cpuidex(int* cpuInfo, int eax, int ecx)
{
#if defined(__GNUC__)
  __cpuid_count(eax, ecx, cpuInfo[0], cpuInfo[1], cpuInfo[2], cpuInfo[3]);
#elif defined(_MSC_VER)
  __cpuidex(cpuInfo, eax, ecx);
#endif  // defined(__GNUC__)
}

これで,CPUの情報を取得する準備はできた.

cpuidから取得できる情報から,どうすればSIMD命令が利用できるか判定できるかはcpuidについてのドキュメント等を参照するとよいが,表にまとめると以下の通りである.

SIMD命令 引数eax 引数ecx レジスタとフラグビット
MMX 1 0 edx [bit 23]
SSE 1 0 edx [bit 25]
SSE2 1 0 edx [bit 26]
SSE3 1 0 ecx [bit 0]
SSSE3 1 0 ecx [bit 9]
SSE4.1 1 0 ecx [bit 19]
SSE4.2 1 0 ecx [bit 20]
SSE4A 0x80000001 0 ecx [bit 6]
AVX 1 0 ecx [bit 28]
AVX2 7 0 ebx [bit 5]
FMA 1 0 ecx [bit 12]
AVX512F 7 0 ebx [bit 16]
AVX512BW 7 0 ebx [bit 30]
AVX512CD 7 0 ebx [bit 28]
AVX512DQ 7 0 ebx [bit 17]
AVX512ER 7 0 ebx [bit 27]
AVX512IFMA52 7 0 ebx [bit 21]
AVX512PF 7 0 ebx [bit 26]
AVX512VL 7 0 ebx [bit 31]
AVX512_4FMAPS 7 0 edx [bit 2]
AVX512_4VNNIW 7 0 edx [bit 3]
AVX512BITALG 7 0 ecx [bit 12]
AVX512VPOPCNTDQ 7 0 ecx [bit 14]
AVX512VBMI 7 0 ecx [bit 1]
AVX512VBMI2 7 0 ecx [bit 6]
AVX512VNNI 7 0 ecx [bit 11]

ちなみに,x64ではSSE,SSE2は利用可能であるとのことなので,わざわざ判定する必要はない.

以上を踏まえて,以下のようなインライン関数を定義したヘッダファイルを用意しておくと便利である. なお,名前空間を加える等,多少改良したものをGitHubに置いてある.

// cpuid.hpp
#ifndef CPUID_HPP
#define CPUID_HPP

#include <algorithm>
#include <array>
#include <string>
#include <type_traits>
#include <utility>

#if defined(__GNUC__)
#  include <cpuid.h>
#elif defined(_MSC_VER)
#  include <intrin.h>
#endif


/*!
 * @brief cpuidの実行結果を第一引数に格納する
 *
 * 実行結果のeaxをcpuInfo[0],ebxをcpuInfo[1],ecxをcpuInfo[2],edxをcpuInfo[3]にコピーする
 *
 * @tparam T  int*
 * @param [out] cpuInfo  cpuidの結果格納先.cpuInfo[0]からcpuInfo[3]に結果が格納される.
 * @param [in]  eax  cpuidの引数
 */
template<
  typename T,
  typename std::enable_if<std::is_same<T, int*>::value, std::nullptr_t>::type = nullptr
>
static inline void
cpuid(T cpuInfo, int eax) noexcept
{
#if defined(__GNUC__)
  ::__cpuid(eax, cpuInfo[0], cpuInfo[1], cpuInfo[2], cpuInfo[3]);
#elif defined(_MSC_VER)
  ::__cpuid(cpuInfo, eax);
#endif  // defined(__GNUC__)
}


/*!
 * @brief cpuidの実行結果を第一引数の配列に格納する
 *
 * 実行結果のeaxをcpuInfo[0],ebxをcpuInfo[1],ecxをcpuInfo[2],edxをcpuInfo[3]にコピーする
 *
 * @tparam kSize  配列サイズ
 * @param [out] cpuInfo  cpuidの結果格納先配列.要素数が4以上でなければコンパイルエラーとなる
 * @param [in]  eax  cpuidの引数
 */
template<std::size_t kSize>
static inline void
cpuid(int (&cpuInfo)[kSize], int eax) noexcept
{
  static_assert(kSize >= 4, "CPU info array size must be four or more");

  cpuid(&cpuInfo[0], eax);
}


/*!
 * @brief cpuidの実行結果を第一引数のstd::arrayに格納する
 *
 * 実行結果のeaxをcpuInfo[0],ebxをcpuInfo[1],ecxをcpuInfo[2],edxをcpuInfo[3]にコピーする
 *
 * @tparam kSize  配列サイズ
 * @param [out] cpuInfo  cpuidの結果格納先配列.要素数が4以上でなければコンパイルエラーとなる
 * @param [in]  eax  cpuidの引数
 */
template<std::size_t kSize>
static inline void
cpuid(std::array<int, kSize>& cpuInfo, int eax) noexcept
{
  static_assert(kSize >= 4, "CPU info array size must be four or more");

  cpuid(cpuInfo.data(), eax);
}


/*!
 * @brief cpuidの実行結果を第一引数に格納する
 *
 * 実行結果のeaxをcpuInfo[0],ebxをcpuInfo[1],ecxをcpuInfo[2],edxをcpuInfo[3]にコピーする
 *
 * @tparam T  int*
 * @param [out] cpuInfo  cpuidの結果格納先.cpuInfo[0]からcpuInfo[3]に結果が格納される.
 * @param [in]  eax  cpuidの引数
 * @param [in]  ecx  cpuidの引数
 */
template<
  typename T,
  typename std::enable_if<std::is_same<T, int*>::value, std::nullptr_t>::type = nullptr
>
static inline void
cpuidex(T cpuInfo, int eax, int ecx) noexcept
{
#if defined(__GNUC__)
  ::__cpuid_count(eax, ecx, cpuInfo[0], cpuInfo[1], cpuInfo[2], cpuInfo[3]);
#elif defined(_MSC_VER)
  ::__cpuidex(cpuInfo, eax, ecx);
#endif  // defined(__GNUC__)
}


/*!
 * @brief cpuidの実行結果を第一引数の配列に格納する
 *
 * 実行結果のeaxをcpuInfo[0],ebxをcpuInfo[1],ecxをcpuInfo[2],edxをcpuInfo[3]にコピーする
 *
 * @tparam kSize  配列サイズ
 * @param [out] cpuInfo  cpuidの結果格納先配列.要素数が4以上でなければコンパイルエラーとなる
 * @param [in]  eax  cpuidの引数
 * @param [in]  ecx  cpuidの引数
 */
template<std::size_t kSize>
static inline void
cpuidex(int (&cpuInfo)[kSize], int eax, int ecx) noexcept
{
  static_assert(kSize >= 4, "[util::cpuidex] CPU info array size must be four or more");

  cpuidex(&cpuInfo[0], eax, ecx);
}


/*!
 * @brief cpuidの実行結果を第一引数のstd::arrayに格納する
 *
 * 実行結果のeaxをcpuInfo[0],ebxをcpuInfo[1],ecxをcpuInfo[2],edxをcpuInfo[3]にコピーする
 *
 * @tparam kSize  配列サイズ
 * @param [out] cpuInfo  cpuidの結果格納先配列.要素数が4以上でなければコンパイルエラーとなる
 * @param [in]  eax  cpuidの引数
 * @param [in]  ecx  cpuidの引数
 */
template<std::size_t kSize>
static inline void
cpuidex(std::array<int, kSize>& cpuInfo, int eax, int ecx) noexcept
{
  static_assert(kSize >= 4, "[util::cpuidex] CPU info array size must be four or more");

  cpuidex(cpuInfo.data(), eax, ecx);
}


/*!
 * @brief cpuidの実行結果のうち,指定レジスタの指定ビットが立っているかどうか調べる
 * @param [in] eax    cpuidの引数
 * @param [in] index  cpuidの結果のインデックス.0ならeax,1ならebx,2ならecx,3ならedx
 * @param [in] nBit       立っているかどうか調べたいビット
 * @return 指定レジスタの指定ビットが立っているならtrue,そうでなければfalse
 */
static inline bool
cpuidBit(int eax, int index, int nBit) noexcept
{
    std::array<int, 4> cpuInfo;
    cpuid(cpuInfo, eax);
    return (cpuInfo[index] & (1 << nBit)) != 0;
}


/*!
 * @brief cpuidの実行結果のうち,指定レジスタの指定ビットが立っているかどうか調べる
 * @param [in] eax    cpuidの引数
 * @param [in] ecx    cpuidの引数
 * @param [in] index  cpuidの結果のインデックス.0ならeax,1ならebx,2ならecx,3ならedx
 * @param [in] nBit  立っているかどうか調べたいビット
 * @return 指定レジスタの指定ビットが立っているならtrue,そうでなければfalse
 */
static inline bool
cpuidexBit(int eax, int ecx, int index, int nBit) noexcept
{
  std::array<int, 4> cpuInfo;
  cpuidex(cpuInfo, eax, ecx);
  return (cpuInfo[index] & (1 << nBit)) != 0;
}


/*!
 * @brief MMX命令が利用可能かどうかを調べる.
 * @return MMX命令が利用可能ならばtrue,そうでなければfalse.
 */
static inline bool
isMmxAvailable() noexcept
{
  return cpuidBit(1, 3, 23);
}

/*!
 * @brief SSE命令が利用可能かどうかを調べる.
 * @return SSE命令が利用可能ならばtrue,そうでなければfalse.
 */
static inline bool
isSseAvailable() noexcept
{
  return cpuidBit(1, 3, 25);
}

/*!
 * @brief SSE2命令が利用可能かどうかを調べる.
 * @return SSE2命令が利用可能ならばtrue,そうでなければfalse.
 */
static inline bool
isSse2Available() noexcept
{
  return cpuidBit(1, 3, 26);
}

/*!
 * @brief SSE3命令が利用可能かどうかを調べる.
 * @return SSE3命令が利用可能ならばtrue,そうでなければfalse.
 */
static inline bool
isSse3Available() noexcept
{
  return cpuidBit(1, 2, 0);
}

/*!
 * @brief SSSE3命令が利用可能かどうかを調べる.
 * @return SSSE3命令が利用可能ならばtrue,そうでなければfalse.
 */
static inline bool
isSsse3Available() noexcept
{
  return cpuidBit(1, 2, 9);
}


/*!
 * @brief SSE4.1命令が利用可能かどうかを調べる.
 * @return SSE4.1命令が利用可能ならばtrue,そうでなければfalse.
 */
static inline bool
isSse41Available() noexcept
{
  return cpuidBit(1, 2, 19);
}

/*!
 * @brief SSE4.2命令が利用可能かどうかを調べる.
 * @return SSE4.2命令が利用可能ならばtrue,そうでなければfalse.
 */
static inline bool
isSse42Available() noexcept
{
  return cpuidBit(1, 2, 20);
}

/*!
 * @brief SSE4A命令が利用可能かどうかを調べる.
 * @return SSE4A命令が利用可能ならばtrue,そうでなければfalse.
 */
static inline bool
isSse4aAvailable() noexcept
{
  std::array<int, 4> cpuInfo;
  cpuid(cpuInfo, 0x80000000);
  if (static_cast<unsigned int>(cpuInfo[0]) < 0x80000001U) {
    return false;
  }
  return cpuidBit(0x80000001, 2, 6);
}

/*!
 * @brief AVX命令が利用可能かどうかを調べる.
 * @return AVX命令が利用可能ならばtrue,そうでなければfalse.
 */
static inline bool
isAvxAvailable() noexcept
{
  return cpuidBit(1, 2, 28);
}

/*!
 * @brief AVX2命令が利用可能かどうかを調べる.
 * @return AVX2命令が利用可能ならばtrue,そうでなければfalse.
 */
static inline bool
isAvx2Available() noexcept
{
  return cpuidBit(7, 1, 5);
}

/*!
 * @brief FMA命令が利用可能かどうかを調べる.
 * @return FMA命令が利用可能ならばtrue,そうでなければfalse.
 */
static inline bool
isFmaAvailable() noexcept
{
  return cpuidBit(1, 2, 12);
}

/*!
 * @brief AVX512F命令が利用可能かどうかを調べる.
 * @return AVX512F命令が利用可能ならばtrue,そうでなければfalse.
 */
static inline bool
isAvx512FAvailable() noexcept
{
  return cpuidBit(7, 1, 16);
}

/*!
 * @brief AVX512BW命令が利用可能かどうかを調べる.
 * @return AVX512BW命令が利用可能ならばtrue,そうでなければfalse.
 */
static inline bool
isAvx512BwAvailable() noexcept
{
  return cpuidBit(7, 1, 30);
}

/*!
 * @brief AVX512CD命令が利用可能かどうかを調べる.
 * @return AVX512CD命令が利用可能ならばtrue,そうでなければfalse.
 */
static inline bool
isAvx512CdAvailable() noexcept
{
  return cpuidBit(7, 1, 28);
}

/*!
 * @brief AVX512DQ命令が利用可能かどうかを調べる.
 * @return AVX512DQ命令が利用可能ならばtrue,そうでなければfalse.
 */
static inline bool
isAvx512DqAvailable() noexcept
{
  return cpuidBit(7, 1, 17);
}

/*!
 * @brief AVX512ER命令が利用可能かどうかを調べる.
 * @return AVX512ER命令が利用可能ならばtrue,そうでなければfalse.
 */
static inline bool
isAvx512ErAvailable() noexcept
{
  return cpuidBit(7, 1, 27);
}

/*!
 * @brief AVX512IFMA52命令が利用可能かどうかを調べる.
 * @return AVX512IFMA52命令が利用可能ならばtrue,そうでなければfalse.
 */
static inline bool
isAvx512Ifma52Available() noexcept
{
  return cpuidBit(7, 1, 21);
}

/*!
 * @brief AVX512PF命令が利用可能かどうかを調べる.
 * @return AVX512PF命令が利用可能ならばtrue,そうでなければfalse.
 */
static inline bool
isAvx512PfAvailable() noexcept
{
  return cpuidBit(7, 1, 26);
}

/*!
 * @brief AVX512VL命令が利用可能かどうかを調べる.
 * @return AVX512VL命令が利用可能ならばtrue,そうでなければfalse.
 */
static inline bool
isAvx512VlAvailable() noexcept
{
  return cpuidBit(7, 1, 31);
}

/*!
 * @brief AVX512_4FMAPS命令が利用可能かどうかを調べる.
 * @return AVX512_4FMAPS命令が利用可能ならばtrue,そうでなければfalse.
 */
static inline bool
isAvx512_4fmapsAvailable() noexcept
{
  return cpuidBit(7, 3, 2);
}

/*!
 * @brief AVX512_4VNNIW命令が利用可能かどうかを調べる.
 * @return AVX512_4VNNIW命令が利用可能ならばtrue,そうでなければfalse.
 */
static inline bool
isAvx512_4vnniwAvailable() noexcept
{
  return cpuidBit(7, 3, 3);
}

/*!
 * @brief AVX512BITALG命令が利用可能かどうかを調べる.
 * @return AVX512BITALG命令が利用可能ならばtrue,そうでなければfalse.
 */
static inline bool
isAvx512BitalgAvailable() noexcept
{
  return cpuidBit(7, 2, 12);
}

/*!
 * @brief AVX512VPOPCNTDQ命令が利用可能かどうかを調べる.
 * @return AVX512VPOPCNTDQ命令が利用可能ならばtrue,そうでなければfalse.
 */
static inline bool
isAvx512VpopcntdqAvailable() noexcept
{
  return cpuidBit(7, 2, 14);
}

/*!
 * @brief AVX512VBMI命令が利用可能かどうかを調べる.
 * @return AVX512VBMI命令が利用可能ならばtrue,そうでなければfalse.
 */
static inline bool
isAvx512VbmiAvailable() noexcept
{
  return cpuidBit(7, 2, 1);
}

/*!
 * @brief AVX512VBMI2命令が利用可能かどうかを調べる.
 * @return AVX512VBMI2命令が利用可能ならばtrue,そうでなければfalse.
 */
static inline bool
isAvx512Vbmi2Available() noexcept
{
  return cpuidBit(7, 2, 6);
}

/*!
 * @brief AVX512VNNI命令が利用可能かどうかを調べる.
 * @return AVX512VNNI命令が利用可能ならばtrue,そうでなければfalse.
 */
static inline bool
isAvx512VnniAvailable() noexcept
{
  return cpuidBit(7, 2, 6);
}


//// 以下はおまけ


/*!
 * @brief CPUのベンダIDを第一引数のポインタの指すメモリ領域にコピーする
 *
 * 先頭から13byteの上書きを行う
 *
 * @tparam T  char*
 * @param [out] vendorId  CPUのベンダID
 */
template<
  typename T,
  typename std::enable_if<std::is_same<T, char*>::value, std::nullptr_t>::type = nullptr
>
static inline void
copyCpuVendorId(T vendorId) noexcept
{
  std::array<int, 4> cpuInfo;
  cpuid(cpuInfo, 0);

  const auto p = reinterpret_cast<int*>(vendorId);
  p[0] = cpuInfo[1];
  p[1] = cpuInfo[3];
  p[2] = cpuInfo[2];
  vendorId[12] = '\0';
}


/*!
 * @brief CPUのベンダIDを第一引数の配列にコピーする
 *
 * 配列の要素数は13個以上でなければならない
 *
 * @tparam kSize  配列のサイズ
 * @param [out] vendorId  CPUのベンダID
 */
template<std::size_t kSize>
static inline void
copyCpuVendorId(char (&vendorId)[kSize]) noexcept
{
  static_assert(kSize >= 12, "CPU vendor ID array size must be 12 or more");

  copyCpuVendorId(vendorId.data());
}


/*!
 * @brief CPUのベンダIDを第一引数のstd::arrayにコピーする
 *
 * std::arrayの要素数は13個以上でなければならない
 *
 * @tparam kSize  配列のサイズ
 * @param [out] vendorId  CPUのベンダID
 */
template<std::size_t kSize>
static inline void
copyCpuVendorId(std::array<char, kSize>& vendorId) noexcept
{
  static_assert(kSize >= 12, "CPU vendor ID array size must be 12 or more");

  copyCpuVendorId(vendorId.data());
}


/*!
 * @brief CPUのベンダIDをstd::stringとして得る
 * @return CPUのベンダID
 */
static inline std::string
getCpuVendorId() noexcept
{
  std::array<char, 32> vendorId;
  std::fill(std::begin(vendorId), std::end(vendorId), '\0');

  copyCpuVendorId(vendorId);

  return std::string{ vendorId.data() };
}


/*!
 * @brief CPUのブランド文字列を第一引数のポインタの指すメモリ領域にコピーする
 * @tparam T  char*
 * @param [out] brandString  ブランド文字列出力先配列
 */
template<
  typename T,
  typename std::enable_if<std::is_same<T, char*>::value, std::nullptr_t>::type = nullptr
>
static inline void
copyCpuBrandString(T brandString) noexcept
{
  std::array<int, 4> cpuInfo;

  cpuid(cpuInfo, 0x80000000);
  if (static_cast<unsigned int>(cpuInfo[0]) < 0x80000004) {
    brandString[0] = '\0';
    return;
  }

  const auto p = reinterpret_cast<int*>(brandString);

  cpuid(cpuInfo, 0x80000002);
  std::copy(std::begin(cpuInfo), std::end(cpuInfo), &p[0]);

  cpuid(cpuInfo, 0x80000003);
  std::copy(std::begin(cpuInfo), std::end(cpuInfo), &p[cpuInfo.size()]);

  cpuid(cpuInfo, 0x80000004);
  std::copy(std::begin(cpuInfo), std::end(cpuInfo), &p[cpuInfo.size() * 2]);
}


/*!
 * @brief CPUのブランド文字列を第一引数の配列にコピーする
 * @param [out] brandString  ブランド文字列出力先配列
 */
template<std::size_t kSize>
static inline void
copyCpuBrandString(char (&brandstring)[kSize]) noexcept
{
  static_assert(kSize >= 64, "CPU brand string array size must be 64 or more");

  copyCpuBrandString(brandstring);
}


/*!
 * @brief CPUのブランド文字列を第一引数のstd::arrayにコピーする
 * @param [out] brandString  ブランド文字列出力先配列
 */
template<std::size_t kSize>
static inline void
copyCpuBrandString(std::array<char, kSize>& brandstring) noexcept
{
  static_assert(kSize >= 64, "CPU brand string array size must be 64 or more");

  copyCpuBrandString(brandstring.data());
}


/*!
 * @brief CPUのブランド文字列をstd::stringとして得る
 * @return CPUのブランド文字列
 */
static inline std::string
getCpuBrandString() noexcept
{
  std::array<char, 64> brandStringArray;
  std::fill(std::begin(brandStringArray), std::end(brandStringArray), '\0');

  copyCpuVendorId(brandStringArray);

  return std::string{ brandStringArray.data() };
}


#endif  // CPUID_HPP

上記の関数を用いると,例えば,AVX2が利用可能であるかどうかは

auto hasAvx2 = isAvx2Available();

のようにして調べられる.

MSDNのcpuidのサンプルコード

ちなみに,MSDNにも __cpuid() を利用して利用可能なSIMD命令を調べるサンプルコードがある. このサンプルコードはMSVCではコンパイルできるが,gccではコンパイルできない. 両者共にコンパイルできるようにするなら,以下のように書き直すとよい.

Wandboxでの実行結果はこのようになる

// InstructionSet.cpp Compile by using: cl /EHsc /W4 InstructionSet.cpp
// processor: x86, x64
// Uses the __cpuid intrinsic to get information about
// CPU extended instruction set support.

#include <algorithm>
#include <array>
#include <bitset>
#include <iostream>
#include <string>
#include <vector>


#if defined(__GNUC__)
#  include <cpuid.h>
#elif defined(_MSC_VER)
#  include <intrin.h>
#endif


static inline void
cpuid(int* cpuInfo, int eax) noexcept
{
#if defined(__GNUC__)
  __cpuid(eax, cpuInfo[0], cpuInfo[1], cpuInfo[2], cpuInfo[3]);
#elif defined(_MSC_VER)
  __cpuid(cpuInfo, eax);
#endif  // defined(__GNUC__)
}


template<std::size_t kSize>
static inline void
cpuid(std::array<int, kSize>& cpuInfo, int eax) noexcept
{
  static_assert(kSize >= 4, "CPU info array size must be four or more");
  cpuid(cpuInfo.data(), eax);
}


static inline void
cpuidex(int* cpuInfo, int eax, int ecx) noexcept
{
#if defined(__GNUC__)
  __cpuid_count(eax, ecx, cpuInfo[0], cpuInfo[1], cpuInfo[2], cpuInfo[3]);
#elif defined(_MSC_VER)
  __cpuidex(cpuInfo, eax, ecx);
#endif  // defined(__GNUC__)
}


template<std::size_t kSize>
static inline void
cpuidex(std::array<int, kSize>& cpuInfo, int eax, int ecx) noexcept
{
  static_assert(kSize >= 4, "CPU info array size must be four or more");
  cpuidex(cpuInfo.data(), eax, ecx);
}


class InstructionSet
{
  // forward declarations
  class InstructionSet_Internal;

public:
  // getters
  static std::string Vendor() noexcept { return CPU_Rep.vendor_; }
  static std::string Brand() noexcept { return CPU_Rep.brand_; }
  static bool SSE3() noexcept { return CPU_Rep.f_1_ECX_[0]; }
  static bool PCLMULQDQ() noexcept { return CPU_Rep.f_1_ECX_[1]; }
  static bool MONITOR() noexcept { return CPU_Rep.f_1_ECX_[3]; }
  static bool SSSE3() noexcept { return CPU_Rep.f_1_ECX_[9]; }
  static bool FMA() noexcept { return CPU_Rep.f_1_ECX_[12]; }
  static bool CMPXCHG16B() noexcept { return CPU_Rep.f_1_ECX_[13]; }
  static bool SSE41() noexcept { return CPU_Rep.f_1_ECX_[19]; }
  static bool SSE42() noexcept { return CPU_Rep.f_1_ECX_[20]; }
  static bool MOVBE() noexcept { return CPU_Rep.f_1_ECX_[22]; }
  static bool POPCNT() noexcept { return CPU_Rep.f_1_ECX_[23]; }
  static bool AES() noexcept { return CPU_Rep.f_1_ECX_[25]; }
  static bool XSAVE() noexcept { return CPU_Rep.f_1_ECX_[26]; }
  static bool OSXSAVE() noexcept { return CPU_Rep.f_1_ECX_[27]; }
  static bool AVX() noexcept { return CPU_Rep.f_1_ECX_[28]; }
  static bool F16C() noexcept { return CPU_Rep.f_1_ECX_[29]; }
  static bool RDRAND() noexcept { return CPU_Rep.f_1_ECX_[30]; }
  static bool MSR() noexcept { return CPU_Rep.f_1_EDX_[5]; }
  static bool CX8() noexcept { return CPU_Rep.f_1_EDX_[8]; }
  static bool SEP() noexcept { return CPU_Rep.f_1_EDX_[11]; }
  static bool CMOV() noexcept { return CPU_Rep.f_1_EDX_[15]; }
  static bool CLFSH() noexcept { return CPU_Rep.f_1_EDX_[19]; }
  static bool MMX() noexcept { return CPU_Rep.f_1_EDX_[23]; }
  static bool FXSR() noexcept { return CPU_Rep.f_1_EDX_[24]; }
  static bool SSE() noexcept { return CPU_Rep.f_1_EDX_[25]; }
  static bool SSE2() noexcept { return CPU_Rep.f_1_EDX_[26]; }
  static bool FSGSBASE() noexcept { return CPU_Rep.f_7_EBX_[0]; }
  static bool BMI1() noexcept { return CPU_Rep.f_7_EBX_[3]; }
  static bool HLE() noexcept { return CPU_Rep.isIntel_ && CPU_Rep.f_7_EBX_[4]; }
  static bool AVX2() noexcept { return CPU_Rep.f_7_EBX_[5]; }
  static bool BMI2() noexcept { return CPU_Rep.f_7_EBX_[8]; }
  static bool ERMS() noexcept { return CPU_Rep.f_7_EBX_[9]; }
  static bool INVPCID() noexcept { return CPU_Rep.f_7_EBX_[10]; }
  static bool RTM() noexcept { return CPU_Rep.isIntel_ && CPU_Rep.f_7_EBX_[11]; }
  static bool AVX512F() noexcept { return CPU_Rep.f_7_EBX_[16]; }
  static bool AVX512DQ() noexcept { return CPU_Rep.f_7_EBX_[17]; }
  static bool RDSEED() noexcept { return CPU_Rep.f_7_EBX_[18]; }
  static bool ADX() noexcept { return CPU_Rep.f_7_EBX_[19]; }
  static bool AVX512IFMA() noexcept { return CPU_Rep.f_7_EBX_[21]; }
  static bool AVX512PF() noexcept { return CPU_Rep.f_7_EBX_[26]; }
  static bool AVX512ER() noexcept { return CPU_Rep.f_7_EBX_[27]; }
  static bool AVX512CD() noexcept { return CPU_Rep.f_7_EBX_[28]; }
  static bool SHA() noexcept { return CPU_Rep.f_7_EBX_[29]; }
  static bool AVX512BW() noexcept { return CPU_Rep.f_7_EBX_[30]; }
  static bool AVX512VL() noexcept { return CPU_Rep.f_7_EBX_[31]; }
  static bool PREFETCHWT1() noexcept { return CPU_Rep.f_7_ECX_[0]; }
  static bool AVX512VBMI() noexcept { return CPU_Rep.f_7_ECX_[1]; }
  static bool AVX512VBMI2() noexcept { return CPU_Rep.f_7_ECX_[6]; }
  static bool AVX512VNNI() noexcept { return CPU_Rep.f_7_ECX_[11]; }
  static bool AVX512BITALG() noexcept { return CPU_Rep.f_7_ECX_[12]; }
  static bool AVX512VPOPCNTDQ() noexcept { return CPU_Rep.f_7_ECX_[14]; }
  static bool AVX512_4VNNIW() noexcept { return CPU_Rep.f_7_EDX_[2]; }
  static bool AVX512_4FMAPS() noexcept { return CPU_Rep.f_7_EDX_[3]; }
  static bool LAHF() noexcept { return CPU_Rep.f_81_ECX_[0]; }
  static bool LZCNT() noexcept { return CPU_Rep.isIntel_ && CPU_Rep.f_81_ECX_[5]; }
  static bool ABM() noexcept { return CPU_Rep.isAMD_ && CPU_Rep.f_81_ECX_[5]; }
  static bool SSE4a() noexcept { return CPU_Rep.isAMD_ && CPU_Rep.f_81_ECX_[6]; }
  static bool XOP() noexcept { return CPU_Rep.isAMD_ && CPU_Rep.f_81_ECX_[11]; }
  static bool TBM() noexcept { return CPU_Rep.isAMD_ && CPU_Rep.f_81_ECX_[21]; }
  static bool SYSCALL() noexcept { return CPU_Rep.isIntel_ && CPU_Rep.f_81_EDX_[11]; }
  static bool MMXEXT() noexcept { return CPU_Rep.isAMD_ && CPU_Rep.f_81_EDX_[22]; }
  static bool RDTSCP() noexcept { return CPU_Rep.isIntel_ && CPU_Rep.f_81_EDX_[27]; }
  static bool _3DNOWEXT() noexcept { return CPU_Rep.isAMD_ && CPU_Rep.f_81_EDX_[30]; }
  static bool _3DNOW() noexcept { return CPU_Rep.isAMD_ && CPU_Rep.f_81_EDX_[31]; }

private:
  static const InstructionSet_Internal CPU_Rep;

  class InstructionSet_Internal
  {
  public:
    InstructionSet_Internal()
      : nIds_{0}
      , nExIds_{0}
      , vendor_{}
      , brand_{}
      , isIntel_{false}
      , isAMD_{false}
      , f_1_ECX_{0}
      , f_1_EDX_{0}
      , f_7_EBX_{0}
      , f_7_ECX_{0}
      , f_7_EDX_{0}
      , f_81_ECX_{0}
      , f_81_EDX_{0}
      , data_{}
      , extdata_{}
    {
      std::array<int, 4> cpui;

      // Calling __cpuid with 0x0 as the function_id argument
      // gets the number of the highest valid function ID.
      cpuid(cpui, 0);
      nIds_ = cpui[0];

      for (int i = 0; i <= nIds_; ++i) {
        cpuidex(cpui, i, 0);
        data_.push_back(cpui);
      }

      // Capture vendor string
      std::array<char, 0x20> vendor;
      std::fill(std::begin(vendor), std::end(vendor), '\0');
      *reinterpret_cast<int*>(&vendor[0]) = data_[0][1];
      *reinterpret_cast<int*>(&vendor[4]) = data_[0][3];
      *reinterpret_cast<int*>(&vendor[8]) = data_[0][2];
      vendor_ = std::string(vendor.data());
      if (vendor_ == "GenuineIntel") {
        isIntel_ = true;
      } else if (vendor_ == "AuthenticAMD") {
        isAMD_ = true;
      }

      // load bitset with flags for function 0x00000001
      if (nIds_ >= 1) {
        f_1_ECX_ = data_[1][2];
        f_1_EDX_ = data_[1][3];
      }

      // load bitset with flags for function 0x00000007
      if (nIds_ >= 7) {
        f_7_EBX_ = data_[7][1];
        f_7_ECX_ = data_[7][2];
        f_7_EDX_ = data_[7][3];
      }

      // Calling __cpuid with 0x80000000 as the function_id argument
      // gets the number of the highest valid extended ID.
      cpuid(cpui, 0x80000000);
      nExIds_ = cpui[0];

      std::array<char, 0x40> brand;
      std::fill(std::begin(brand), std::end(brand), '\0');

      for (int i = 0x80000000; i <= nExIds_; ++i) {
        cpuidex(cpui, i, 0);
        extdata_.push_back(cpui);
      }

      // load bitset with flags for function 0x80000001
      if (static_cast<unsigned int>(nExIds_) >= 0x80000001) {
        f_81_ECX_ = extdata_[1][2];
        f_81_EDX_ = extdata_[1][3];
      }

      // Interpret CPU brand string if reported
      if (static_cast<unsigned int>(nExIds_) >= 0x80000004) {
        std::copy(std::cbegin(extdata_[2]), std::cend(extdata_[2]), reinterpret_cast<int*>(&brand[0]));
        std::copy(std::cbegin(extdata_[3]), std::cend(extdata_[3]), reinterpret_cast<int*>(&brand[0] + sizeof(extdata_[0])));
        std::copy(std::cbegin(extdata_[4]), std::cend(extdata_[4]), reinterpret_cast<int*>(&brand[0] + sizeof(extdata_[0]) * 2));
        brand_ = std::string(brand.data());
      }
    };

    int nIds_;
    int nExIds_;
    std::string vendor_;
    std::string brand_;
    bool isIntel_;
    bool isAMD_;
    std::bitset<32> f_1_ECX_;
    std::bitset<32> f_1_EDX_;
    std::bitset<32> f_7_EBX_;
    std::bitset<32> f_7_ECX_;
    std::bitset<32> f_7_EDX_;
    std::bitset<32> f_81_ECX_;
    std::bitset<32> f_81_EDX_;
    std::vector<std::array<int, 4>> data_;
    std::vector<std::array<int, 4>> extdata_;
  };  // class InstructionSet_Internal
};  // class InstructionSet


// Initialize static member data
const InstructionSet::InstructionSet_Internal InstructionSet::CPU_Rep;


// Print out supported instruction set extensions
int
main()
{
  auto &outstream = std::cout;
  auto support_message = [&outstream](std::string isa_feature, bool is_supported) {
    outstream << isa_feature
              << (is_supported ? " supported" : " not supported")
              << std::endl;
  };

  std::cout << InstructionSet::Vendor() << std::endl;
  std::cout << InstructionSet::Brand() << std::endl;

  support_message("3DNOW", InstructionSet::_3DNOW());
  support_message("3DNOWEXT", InstructionSet::_3DNOWEXT());
  support_message("ABM", InstructionSet::ABM());
  support_message("ADX", InstructionSet::ADX());
  support_message("AES", InstructionSet::AES());
  support_message("AVX", InstructionSet::AVX());
  support_message("AVX2", InstructionSet::AVX2());
  support_message("AVX512CD", InstructionSet::AVX512CD());
  support_message("AVX512ER", InstructionSet::AVX512ER());
  support_message("AVX512F", InstructionSet::AVX512F());
  support_message("AVX512DQ", InstructionSet::AVX512DQ());
  support_message("AVX512IFMA", InstructionSet::AVX512IFMA());
  support_message("AVX512PF", InstructionSet::AVX512PF());
  support_message("AVX512BW", InstructionSet::AVX512BW());
  support_message("AVX512VL", InstructionSet::AVX512VL());
  support_message("AVX512VBMI", InstructionSet::AVX512VBMI());
  support_message("AVX512VBMI2", InstructionSet::AVX512VBMI2());
  support_message("AVX512VNNI", InstructionSet::AVX512VNNI());
  support_message("AVX512BITALG", InstructionSet::AVX512BITALG());
  support_message("AVX512VPOPCNTDQ", InstructionSet::AVX512VPOPCNTDQ());
  support_message("AVX512_4VNNIW", InstructionSet::AVX512_4VNNIW());
  support_message("AVX512_4FMAPS", InstructionSet::AVX512_4FMAPS());
  support_message("BMI1", InstructionSet::BMI1());
  support_message("BMI2", InstructionSet::BMI2());
  support_message("CLFSH", InstructionSet::CLFSH());
  support_message("CMPXCHG16B", InstructionSet::CMPXCHG16B());
  support_message("CX8", InstructionSet::CX8());
  support_message("ERMS", InstructionSet::ERMS());
  support_message("F16C", InstructionSet::F16C());
  support_message("FMA", InstructionSet::FMA());
  support_message("FSGSBASE", InstructionSet::FSGSBASE());
  support_message("FXSR", InstructionSet::FXSR());
  support_message("HLE", InstructionSet::HLE());
  support_message("INVPCID", InstructionSet::INVPCID());
  support_message("LAHF", InstructionSet::LAHF());
  support_message("LZCNT", InstructionSet::LZCNT());
  support_message("MMX", InstructionSet::MMX());
  support_message("MMXEXT", InstructionSet::MMXEXT());
  support_message("MONITOR", InstructionSet::MONITOR());
  support_message("MOVBE", InstructionSet::MOVBE());
  support_message("MSR", InstructionSet::MSR());
  support_message("OSXSAVE", InstructionSet::OSXSAVE());
  support_message("PCLMULQDQ", InstructionSet::PCLMULQDQ());
  support_message("POPCNT", InstructionSet::POPCNT());
  support_message("PREFETCHWT1", InstructionSet::PREFETCHWT1());
  support_message("RDRAND", InstructionSet::RDRAND());
  support_message("RDSEED", InstructionSet::RDSEED());
  support_message("RDTSCP", InstructionSet::RDTSCP());
  support_message("RTM", InstructionSet::RTM());
  support_message("SEP", InstructionSet::SEP());
  support_message("SHA", InstructionSet::SHA());
  support_message("SSE", InstructionSet::SSE());
  support_message("SSE2", InstructionSet::SSE2());
  support_message("SSE3", InstructionSet::SSE3());
  support_message("SSE4.1", InstructionSet::SSE41());
  support_message("SSE4.2", InstructionSet::SSE42());
  support_message("SSE4a", InstructionSet::SSE4a());
  support_message("SSSE3", InstructionSet::SSSE3());
  support_message("SYSCALL", InstructionSet::SYSCALL());
  support_message("TBM", InstructionSet::TBM());
  support_message("XOP", InstructionSet::XOP());
  support_message("XSAVE", InstructionSet::XSAVE());
}

cpuid命令自体が利用可能かどうかを調べる

cpuid命令自体が利用可能かどうかも調べる必要があるのではないか?と疑問を持たれる人もいるかもしれない. 実はその通りで,かなり昔のCPUではcpuid命令がなかったらしい.

cpuid命令が利用可能かどうかは,インテルのドキュメントに記載してあるように,eflagsの21bit目が変更可能であるかどうかを調べるとよい.

ただし,これはC言語C++で記述することはできないので,インラインアセンブラに頼る必要がある.

#if defined(_MSC_VER) && defined(_WIN64)
#  ifndef WIN32_LEAN_AND_MEAN
#    define WIN32_LEAN_AND_MEAN
#    define CPUID_WIN32_LEAN_AND_MEAN_IS_NOT_DEFINED
#  endif  // !WIN32_LEAN_AND_MEAN
#  ifndef NOMINMAX
#    define NOMINMAX
#    define CPUID_NOMINMAX_IS_NOT_DEFINED
#  endif  // !NOMINMAX
#  include <windows.h>
#  ifdef CPUID_WIN32_LEAN_AND_MEAN_IS_NOT_DEFINED
#    undef CPUID_WIN32_LEAN_AND_MEAN_IS_NOT_DEFINED
#    undef WIN32_LEAN_AND_MEAN
#  endif  // CPUID_WIN32_LEAN_AND_MEAN_IS_NOT_DEFINED
#  ifdef CPUID_NOMINMAX_IS_NOT_DEFINED
#    undef CPUID_NOMINMAX_IS_NOT_DEFINED
#    undef NOMINMAX
#  endif  // CPUID_NOMINMAX_IS_NOT_DEFINED
#endif  // defined(_MSC_VER) && defined(_WIN64)


static inline bool
isCpuidSupported() noexcept
{
#if defined(__x86_64__) || defined(_WIN64) || defined(__MINGW64__)
  // x64とき (全てのIntel x64プロセッサではcpuid命令は利用可能なため,このように真面目に調べる必要はない)
#  if defined(__GNUC__)
  bool result;
  __asm__ __volatile__ (
    "pushfq\n\t"
    "pushfq\n\t"
    "pop %%rax\n\t"
    "mov %%rax, %%rcx\n\t"
    "xor $0x200000, %%rax\n\t"
    "push %%rax\n\t"
    "popfq\n\t"
    "pushfq\n\t"
    "pop %%rax\n\t"
    "xor %%rcx, %%rax\n\t"
    "shr $21, %%rax\n\t"
    "popfq\n\t"
    : "=a" (result)
    :
    : "cc", "%rcx");
  return result;
#  elif defined(_MSC_VER)
  // MSVCのx64ではインラインアセンブラを利用できないので、
  // マシンコード配列を用意し、そのメモリ領域に実行権限を与えて、
  // eflagsの21bit目が変更可能かどうかを調べる

  // cdecl function code
  std::uint8_t code[] = {
    0x9c,                                // pushfq
    0x9c,                                // pushfq
    0x58,                                // pop     rax
    0x48, 0x89, 0xc1,                    // mov     rcx,rax
    0x48, 0x35, 0x00, 0x00, 0x20, 0x00,  // xor     rax,200000h
    0x50,                                // push    rax
    0x9d,                                // popfq
    0x9c,                                // pushfq
    0x58,                                // pop     rax
    0x48, 0x31, 0xc8,                    // xor     rax,rcx
    0x48, 0xc1, 0xe8, 0x15,              // shr     rax,21
    0x9d,                                // popfq
    0xc3                                 // ret
  };
  ::DWORD oldProtect;
  ::VirtualProtect(code, sizeof(code), PAGE_EXECUTE_READWRITE, &oldProtect);
  const auto result = reinterpret_cast<bool(__cdecl*)()>(reinterpret_cast<unsigned char*>(code))();
  ::VirtualProtect(code, sizeof(code), oldProtect, &oldProtect);
  return result;
#  endif  // defined(__GNUC__)
#else
  // x86のとき
#  if defined(__GNUC__)
  bool result;
  __asm__ __volatile__ (
    "pushfl\n\t"
    "pushfl\n\t"
    "pop %%eax\n\t"
    "mov %%eax, %%ecx\n\t"
    "xorl $0x200000, %%eax\n\t"
    "push %%eax\n\t"
    "popfl\n\t"
    "pushfl\n\t"
    "pop %%eax\n\t"
    "xorl %%ecx, %%eax\n\t"
    "shrl $21, %%eax\n\t"
    "popfl\n\t"
    : "=a" (result)
    :
    : "cc", "%ecx");
  return result;
#  elif defined(_MSC_VER)
  bool result;
  __asm {
    pushfd
    pushfd
    pop eax
    mov ecx, eax
    xor eax, 200000h
    push eax
    popfd
    pushfd
    pop eax
    xor eax, ecx
    shr eax, 21
    mov result, al
    popfd
  }
  return result;
#  endif  // defined(__GNUC__)
#endif  // defined(__x86_64__) || defined(_WIN64) || defined(__MINGW64__)
}

Intelによると,全てのx64プロセッサでcpuid命令が利用可能であるため,x64の方のコードは不要で,常に true を返すようにしてもよい.

まとめ

この記事では以下のことを紹介した.

  • SIMDの概要
  • SIMDの組み込み関数の利用方法
  • コンパイラの差を吸収するアラインメントの指定方法
  • ベクトルの内積を計算するサンプルコード
  • SSE/AVX等の実行時利用可能判定

特に,SIMDの組み込み関数の利用方法を簡単にまとめると以下のようになる.

  • alignas(alignof(__m256i)) ... の形で,変数のアラインメント指定
    • 古いMSVCなら __declspec(align(32))
    • 古いgccなら __attribute__((aligned(32)))
  • gcc
    • #include <x86intrin>
    • $ g++ -march=native ...
    • pisix_memalign() でアラインされた動的メモリ確保, std::free() で解放
  • MSVC
    • #include <intrin>
    • > cl.exe /arch:AVX2 ...
    • _aligned_malloc() でアラインされた動的メモリ確保, _aligned_free() で解放
  • AVX-512非対応のCPUでAVX-512をテストする場合は,Intelのエミュレータを利用

この記事はあくまでSIMDの基礎に過ぎないが,あとは組み込み関数を調べ,うまく組み合わせることで,SIMDをプログラムに組み込めるようになるかもしれない.

参考文献

GNU MakeでC/C++の依存関係を自動定義する

背景

C/C++用のMakefileを書いていると,依存関係を記述するのがなかなか厄介に感じられる. 何とか自動的に依存関係を定義したいと考えた.

gcc/g++による依存関係の抽出

gcc/g++は以下のようにして依存関係を抽出することが可能である.

$ g++ -MM foo.cpp
foo.o: foo.cpp aaa.h bbb.h

この機能を利用して,Makefileで依存関係の自動定義を行う.

外部ファイルに依存関係を書き出す

makeには他のMakefileをインクルードすることが可能である. これを利用し,依存関係を記述したファイルを掃き出し,Makefileからインクルードするとよさそうだ.

CXX     := g++
SRCS    := foo.cpp bar.cpp
DEPENDS := depends.mk

.PHONY: depends

depends:
    $(CXX) -MM $(SRCS) > $(DEPENDS)

-include $(DEPENDS)

ただし,この方法だと make depends を実行しなければ,依存関係を更新されない. また,初回はdepends.mkが存在せず,依存関係が定義されない. これを自動的に更新したい.

外部ファイルを用いず,依存関係を自動定義する

GNU Makeには,引数をシェルコマンドとして実行し,出力結果として返却する shell 関数,引数をMakefileに記述されたものとして扱う eval 関数が存在する. これらを利用することで,Makefileから依存関係を定義することができそうだ.

CXX  := g++
SRCS := foo.cpp bar.cpp

$(eval $(shell $(CXX) -MM $(SRCS)))

しかし,この方法では改行が無視されるため,うまくいかない. 具体的には,複数ファイルを一度に g++ -MM の引数として渡せない,行継続の \ によってエラーとなる. したがって,ソースファイルを1つずつに対し, g++ -MM を実行する必要し, \ を消去する必要がある.

GNU Makeには,文字列の置換を行う subst 関数, 与えられたリストの要素それぞれに,指定した処理を実行する foreach 関数がある. これらを利用し,前述の問題を解決する.

CXX  := g++
SRCS := foo.cpp bar.cpp

$(foreach SRC,$(SRCS),$(eval $(subst \,,$(shell $(CXX) -MM $(SRC)))))

具体的なMakefileの全貌は以下のようになるだろう. 圧倒的に依存関係の記述が楽になり,ヘッダファイル名は全く記述する必要が無くなっていることがわかる.

CXX      := g++ -std=gnu++14
CXXFLAGS := -Wall -Wextra -O3 -march=native -DNDEBUG
LDFLAGS  := -s
TARGET   := main
OBJS     := $(addsuffix .o, $(basename $(TARGET)) foo bar)
SRCS     := $(OBJS:.o=.cpp)

ifeq ($(OS),Windows_NT)
    TARGET := $(addsuffix .exe, $(TARGET))
else
    TARGET := $(addsuffix .out, $(TARGET))
endif

%.exe:
  $(CXX) $(LDFLAGS) $(filter %.c %.cpp %.cxx %.cc %.o, $^) $(LDLIBS) -o $@
%.out:
  $(CXX) $(LDFLAGS) $(filter %.c %.cpp %.cxx %.cc %.o, $^) $(LDLIBS) -o $@

.PHONY: all clean

all: $(TARGET)
$(TARGET): $(OBJS)

$(foreach SRC,$(SRCS),$(eval $(subst \,,$(shell $(CXX) -MM $(SRC)))))

clean:
    $(RM) $(TARGET) $(OBJS)

まとめ

GNU Make用のMakefileに以下のような記述を加えることで,オブジェクトファイル(.o)が依存するソースファイル(.c, .cpp)とヘッダファイル(.h, .hpp)依存関係を自動的に定義することができる. あとは,実行ファイルとオブジェクトファイル間の依存関係を定義するだけでよい.

CXX := g++
SRCS := foo.cpp bar.cpp

$(foreach SRC,$(SRCS),$(eval $(subst \,,$(shell $(CXX) -MM $(SRC)))))

NTSC加重平均法の整数演算による高速化

はじめに

NTSC加重平均法という有名なグレースケール変換がある. このグレースケール変換は,ある画素の輝度値 $Y$ を,次の式(\ref{eq:ntscAverage})のように求めるものだ. ($r, g, b$ は赤,緑,青それぞれの値)

\begin{equation} Y = 0.298912 r + 0.586611 g + 0.114478 b \label{eq:ntscAverage} \end{equation}

単純な平均をとったグレースケール変換

\begin{equation} Y = \dfrac{r + g + b}{3} \end{equation}

と比較すると,NTSC加重平均法によるグレースケール変換は人間の赤,緑,青の感じ方を考慮したものになっており,自然なグレースケール化を行うことができる.

あるとき,このNTSC加重平均法によるグレースケール変換を,次のように整数のみで行っているプログラムを見ることがあった.

\begin{equation} Y = \dfrac{77 r + 150 g + 29 b}{256} \label{eq:ntscAverageOptimized08} \end{equation}

浮動小数点演算を整数演算に変換する発想に感動したので,この記事では,どのような過程で式(\ref{eq:ntscAverage})から式(\ref{eq:ntscAverageOptimized08})を得るのかについて解説する.

導出

記述の簡略化のため,

\begin{equation} W_r = 0.298912, \:\: W_g = 0.586611, \:\: W_b = 0.114478 \end{equation}

とおく. まず,理想的なNTSC加重平均法による輝度値を求める関数を以下の式(\ref{eq:ntscIdealFunction})ように定める.

\begin{equation} F(r, g, b) = W_r r + W_g g + W_b b \label{eq:ntscIdealFunction} \end{equation}

これを計算機で計算し,最終的に得られる輝度値(小数点を切り捨てたもの)を求める関数を以下の式(\ref{eq:ntscFlooredFunction})ように定める.

\begin{equation} F'(r, g, b) = \lfloor W_r r + W_g g + W_b b \rfloor \label{eq:ntscFlooredFunction} \end{equation}

ここで,関数 $F (r, g, b)$ を以下のように変形し, $f_N(r, g, b)$ を $F (r, g, b)$ の近似値を求める関数として定義する.

\begin{eqnarray} F(r, g, b) & = & F(r, g, b) \times \dfrac{2^N}{2^N} \nonumber \\ & = & \dfrac{2^N (W_r r + W_g g + W_b b)}{2^N} \nonumber \\ & \approx & \dfrac{\lfloor 2^N W_r + 0.5 \rfloor r + \lfloor 2^N W_g + 0.5 \rfloor g + \lfloor 2^N W_b + 0.5 \rfloor b}{2^N} \nonumber \\ & \equiv & f_N(r, g, b) \label{eq:ntscAverageApproxDerivation} \end{eqnarray}

$2^N$ を掛けているのは,2の累乗の計算はビット演算として表現可能なためである. ビット演算は掛け算や割り算と比べて,比較的高速に計算可能であり,容易に高速化が見込める.

さて, $N = 8$ のとき,すなわち, $f_8(r, g, b)$ は以下のようになる.

\begin{equation} f_8 (r, g, b) = \dfrac{77r + 150g + 29b}{256} \end{equation}

誤差についての考察

前述の導出より,式(\ref{eq:ntscAverageOptimized08})がNTSC加重平均法の近似式であることがわかった. しかし,近似計算に誤差はつきものである. ここでは,$N$ によって,特に $N = 8$ のとき,どの程度の誤差が生じるのかについて調べてみる.

まず,記述の簡略化のために,

\begin{equation} w_{rN} = 2^N \times W_r, \:\: w_{gN} = 2^N \times W_g, \:\: w_{bN} = 2^N \times W_b \end{equation}

\begin{equation} w'_{rN} = \lfloor w_{rN} + 0.5 \rfloor, \:\: w'_{gN} = \lfloor w_{gN} + 0.5 \rfloor, \:\: w'_{bN} = \lfloor w_{bN} + 0.5 \rfloor \end{equation}

とおく. 前述の導出式(\ref{eq:ntscAverageApproxDerivation})より,

\begin{equation} F (r, g, b) = f_N (r, g, b) + \dfrac{(w_{rN} - w'_{rN}) r + (w_{gN} - w'_{gN}) g + (w_{bN} - w'_{bN}) b}{2^N} \end{equation}

となる.右辺の第二項を理想の値との誤差を求める関数として,

\begin{equation} \epsilon_N (r, g, b) = \dfrac{(w_{rN} - w'_{rN}) r + (w_{gN} - w'_{gN}) g + (w_{bN} - w'_{bN}) b}{2^N} \end{equation}

とおく. ここに $N = 8$ を代入すると,

\begin{equation} \epsilon_8 (r, g, b) = \dfrac{-0.478528 r + 0.172416 g + 0.306368 b}{2^8} \end{equation}

を得る. $r, g, b$ の各係数の符号に注目すると,

\begin{equation} \epsilon_8 (255, 0, 0) \leq \epsilon_8 (r, g, b) \leq \epsilon_8 (0, 255, 255) \end{equation}

すなわち,

\begin{equation} -0.479 \leq \epsilon_8 (r, g, b) \leq 0.479 \end{equation}

を得る(小数第四位で四捨五入している). これは,やや誤差が大きいので,実際に計算機に計算させるときは, $N = 10$ として,

\begin{equation} \epsilon_{10} (0, 255, 0) = -0.0773 \leq \epsilon_{10} (r, g, b) \leq 0.0775 = \epsilon_{10} (255, 0, 255) \end{equation}

程度に誤差を抑えるのがよいだろう. もちろん, $N$ をより大きくすれば,誤差をさらに抑えることができる.そのときには,オーバーフローに気をつけなくてはならない.

ここで,r, g, bの各ビット深度が8bitであり,途中の計算結果を32bit整数として扱うと考える.

\begin{equation} W_r + W_g + W_b = 1 \end{equation}

かつ,

\begin{equation} 0 \leq r, g, b \leq 255 \end{equation}

であるので,

\begin{equation} 0 \leq W_r r + W_g g + W_b b < 2^8 \end{equation}

したがって,

\begin{equation} 0 \leq 2^{24} (W_r r + W_g g + W_b b) < 2^{32} \label{eq:ntscIdealShift} \end{equation}

となり, $N = 24$ がオーバーフローを起こさず,誤差を最も小さくできるビットシフト量である...と結論付けたいところであるが,実際には,$2^N W_r, \:\: 2^N W_g, \:\: 2^N W_b$ をそれぞれ四捨五入した係数 $w'_{rN}, \:\: w'_{gN}, \:\: w'_{bN}$ を用いるので,$N = 24$ のとき,式(\ref{eq:ntscIdealShift})が $2^{32}$ で抑えられるとは限らない. したがって, $N = 23$ が誤差を最も小さくできるビットシフト量であり,そのときの誤差 $\epsilon_{23} (r, g, b)$ は

\begin{equation} -2.061 \times 10^{-5} \leq \epsilon_{23} (r, g, b) \leq 2.025 \times 10^{-6} \end{equation}

となる.

まとめ

この記事では,NTSC加重平均法によるグレースケール変換を,整数演算のみで行う近似計算の導出を行い,その誤差について述べた.

具体的には,以下のような計算を行っているプログラム

y = (unsigned char) (0.298912 * r + 0.586611 * g + 0.114478 * b)

y = (unsigned char) ((306 * r + 601 * g + 117 + b) >> 10)

のように変更すると,元の計算とほとんど相違なく,高速に計算を行うことが可能となる.

グレースケール変換はOpenCVにも実装されているので,自分で実装する機会はほとんどないかもしれないが,整数 -> 整数という計算の途中に浮動小数点が介入する場合の高速化のアイデアとして,示唆に富むものがあるだろう.

各種言語における標準入力からのEOFまでの入力サンプル

はじめに

昨今,CodeIQpaizaといったサービスが登場し,自動採点型のプログラミングの問題に取り組む人が増えている(と思う). 自動採点型のプログラミングの問題では,基本的に標準入力から読み込みを行い,をれに応じて適切な出力をするというものだ. 入力ケースは何パターンか与えられ,その度に送信されたプログラムを実行する仕組みとなっている. このような標準入力から読み込みを行い,標準出力がちゃんとしたのであるかどうかを判定し,自動採点を行う形式のプログラミングの問題は,AOJAtCoderyukicoderなどの競技プログラミングサイトでは一般的なものであったが,CodeIQ,paizaなどの台頭により,より広く認知されるようになったのではないかと思う.

この記事では,僕の忘備録も兼ねて,各種言語における標準入力と標準出力のサンプルを掲載する. というのも,CodeIQの入出力サンプルにはヒドい例が掲載されている言語もあったからだ. 特に,Javaのサンプルは,

import java.io.*;
class Main {
    public static void main(String[] args) throws IOException {
        int c;
        while ((c = System.in.read()) != -1)
            System.out.println(c);
    }
}

となっており,何故か1文字ごとに読み込みを行うようになっている. また,この手の入出力サンプルは1行だけ読み込んで,それをそのまま処理というケースしか書かれていない.

とりあえず,

  1. 標準入力をEOFまで読み込み,
  2. 入力をトークン分割し,
  3. トークンを整数型に変換して.
  4. 標準出力に出力する

という単純なサンプルを掲載する. 具体的な入力としては,

10 20
30 40
50 60
70 80

のようなものだ.

ただ,実際にはデータ数(読み込めばよい行数)が1行目に与えられる問題が多く,EOFまで読み込む必要はないが,たまにEOFまで読み込まなければならない問題があるので,EOFまでの読み込みの例を記載するわけだ. 指定回数を読み込む方法については,各言語におけるループの仕方を調べればよいだけであり,ググれば簡単にヒットするし,ループが記述できないようでは問題自体も解けないであろうから割愛する.

言語

本記事で取り扱う言語は以下の通りである.

C

まずはC言語から. まぁ,C言語で問題を解く人はいないだろうが,サンプルとして掲載する.

#include <stdio.h>
#include <stdlib.h>

#define LINE_BUF_SIZE  1024


int
main(void)
{
  static char line[LINE_BUF_SIZE];

  while (fgets(line, sizeof(line), stdin) != NULL) {
    int a, b;
    if (sscanf(line, "%d %d", &a, &b) != 2) {
      fputs("sscanf: Convert error\n", stderr);
      return EXIT_FAILURE;
    }
  }
  return EXIT_SUCCESS;
}

競プロにおける入力はある程度入力される文字列の長さが想定できるので,それなりのバッファ容量を確保し, scanf() を用いても問題はないだろうが, scanf() を使ってるだけで気持ち悪いと感じるので, fgets()sscanf() を用いることにする. EOFに到達した場合, fgets()NULL を返却するので,それをEOFの判定に利用する. また, sscanf() の返り値は,変換に成功した個数なので,うまく整数に変換できたかどうかの確認に利用する.

なお,64bit整数を sscanf() で読み込むにあたってはやや問題があり, "%lld" といった書式指定文字列を用いないとうまくいかないかもしれない. これはC99から正式に採用され,それ以前ではコンパイラによっては非標準として実装されているレベルなので,やや気持ち悪いかもしれない.

C++

C++を用いている人は多いので,最早説明の必要はないだろう.

#include <cstdlib>
#include <iostream>


int
main()
{
  std::cin.tie(0);
  std::ios::sync_with_stdio(false);

  int a, b;
  while (std::cin >> a >> b) {
    std::cout << a << " " << b << std::endl;
  }
  return EXIT_SUCCESS;
}

一応解説しておくと,

std::cin.tie(0);

std::coutstd::cin の結び付きを解除し,

std::ios::sync_with_stdio(false);

で, stdio との同期を切る. これによって, std::coutstd::cin を用いた入出力を高速化できる. これは, std::cout / std::cin を用いる場合には有効である.

もっとも, std::printf() を用いた方がフォーマット出力は楽なので, std::cout の代わりに std::printf を用いている人も多いだろう. <iostream><cstdio> 系の関数を混在させる場合は,前述の高速化を用いてはいけない.

上記の例では,EOFの判定は std::cin のbool変換演算子を用いているが, std::cin.eof()true かどうかでEOFを判定するという手段もある.

なお,ガチ勢は using namespace std; と膨大なマクロとインクルードを記述したものを用いるだろう.

C Sharp

基本的な部分の解説の必要は無いだろう. C#の場合, Console.WriteLine() はデフォルトだと自動的にフラッシュされる設定になっているので,この自動フラッシュをオフにし,最後にまとめてフラッシュすることで,出力の部分の高速化が期待できる.

using System;
using System.IO;

class MainClass {
    static void Main() {
        Console.SetOut(new StreamWriter(Console.OpenStandardOutput()) { AutoFlush = false });

        string line;
        while ((line = Console.ReadLine()) != null) {
            string[] tokens = line.Split(' ');
            int a = int.Parse(tokens[0]);
            int b = int.Parse(tokens[1]);
            Console.WriteLine(a + " " + b);
        }

        Console.Out.Flush();
    }
}

IEnumerable の操作を用いて,文字列から整数への変換を以下のように書くのもよいだろう.

using System;
using System.IO;

class MainClass {
    static void Main() {
        Console.SetOut(new StreamWriter(Console.OpenStandardOutput()) { AutoFlush = false });

        string line;
        while ((line = Console.ReadLine()) != null) {
            int[] tokens = line.Split(' ').Select(int.Parse).ToArray();
            int a = tokens[0];
            int b = tokens[1];
            Console.WriteLine("{0} {1}", a, b);
        }

        Console.Out.Flush();
    }
}

VB.NET

VB.NETはよくわからないので,C# のものを単純に翻訳してみただけだ. Line予約語らしいので,読み込んだ一行は inputtedLine という名前の変数に格納する.

Imports System
Imports System.IO

Public Class MainClass
    Shared Sub Main(args As String())
        Console.SetOut(New StreamWriter(Console.OpenStandardOutput()) With { .AutoFlush = false })

        Dim inputtedLine As String = Console.ReadLine()
        While (Not inputtedLine Is Nothing)
            Dim tokens As Integer() = inputtedLine.Split(" ").Select(Function(token) Integer.Parse(token)).ToArray()
            Dim a As Integer = tokens(0)
            Dim b As Integer = tokens(1)
            Console.WriteLine("{0} {1}", a, b)

            inputtedLine = Console.ReadLine()
        End While
        Console.Out.Flush()
    End Sub
End Class

Java

Javaはバージョン毎に進化しているので,Java7の場合とJava8の場合に分けて入出力サンプルを掲載する. Java6以下はもう滅びたと考えてよいので,サンプルを掲載する必要はないだろう. なお,基本的に例外処理は記述せず, main() メソッドからthrowする形で記述する. というのも,基本的に例外が発生した時点で,問題に正答することはできなくなっていると考えられるからだ.

Java7

Java7からtry-with-resource文が実装されたので, System.in の読み込み用のオブジェクトのクローズは自動的に行わせる.

import java.io.*;

public class Main {
    public static void main(String[] args) throws Exception {
        try (BufferedReader br = new BufferedReader(new InputStreamReader(System.in))) {
            String line;
            while ((line = br.readLine()) != null) {
                String[] tokens = line.split(" ");
                int a = Integer.parseInt(tokens[0]);
                int b = Integer.parseInt(tokens[1]);
                System.out.println(a + " " + b);
            }
        }
    }
}

java.util.Scanner を用いた場合,split() メソッドによるトークン分割,整数型等への変換処理を自前で書かなくてもよくなる. ただし,java.util.Scanner は遅いという話があるので,入力数が多い場合は気をつけなくてはならない.

import java.util.*;

public class Main {
    public static void main(String[] args) throws Exception {
        try (Scanner sc = new Scanner(System.in)) {
            while (sc.hasNextInt()) {
                int a = sc.nextInt();
                int b = sc.nextInt();
                System.out.println(a + " " + b);
            }
        }
    }
}

Java8

Java8になって, java.io.BufferedReaderlines() メソッドという,Streamを生成するAPIが追加された. このメソッドを用いることで,標準入力からの読み込みをカッコよく書ける. Java8を用いて問題を解く場合,Streamを用いて楽に記述することも多いだろうから,そういう意味でも親和性が高いはずだ.

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws Exception {
        try (BufferedReader br = new BufferedReader(new InputStreamReader(System.in))) {
            br.lines()
                .map(line -> Arrays.stream(line.split(" "))
                        .mapToInt(Integer::parseInt)
                        .toArray())
                .forEach(tokens -> {
                    int a = toknes[0];
                    int b = toknes[1];
                    System.out.println(a + " " + b);
                });
        }
    }
}

もし,分割されたトークンを何らかのコンストラクタに突っ込み,目的とするオブジェクトの型の配列に変換したいのであれば,以下のようにするとよいだろう. この例では,各トークンから BigDecimalインスタンスを生成している. map() メソッドから返却されるストリームの toArray() メソッドは,引数が無い場合, Object 型の配列を返却するので,引数に目的の型の配列を生成する new の参照(メソッド参照?)を渡す必要がある.

import java.io.*;
import java.math.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws Exception {
        try (BufferedReader br = new BufferedReader(new InputStreamReader(System.in))) {
            br.lines()
                .map(line -> Arrays.stream(line.split(" "))
                        .map(BigDecimal::new)
                        .toArray(BigDecimal[]::new))
                .forEach(tokens -> {
                    BigDecimal a = toknes[0];
                    BigDecimal b = toknes[1];
                    System.out.println(a + " " + b);
                });
        }
    }
}

なお,1行目にデータ数nが与えられる場合は,

        try (BufferedReader br = new BufferedReader(new InputStreamReader(System.in))) {
            int n = Integer.parseInt(br.readLine());
            br.lines()
              // ...
        }

のように,事前に1回 readLine() メソッドを呼び出し,ファイルストリームの読み書き位置を移動しておくとよい.

なお, java.util.Scanner にStreamを生成するものはないらしいので,Stream APIを用いたいなら, java.io.BufferedReader を使おう.

Python

Pythonは2と3で大きく仕様が変更されているので,別々に記述する. ただ, fileinput をimportし,標準入力を 1行1行読み取るようにした場合,標準入力からの読み込みに関しては,Python2とPython3 の両対応ができる.

#!/usr/bin/env python
# -*- coding: utf-8 -*-

import fileinput


if __name__ == '__main__':
    for line in fileinput.input():
        tokens = line.strip().split()
        a, b = int(tokens[0]), int(tokens[1])

Python 2

fileinput.input() を用いる場合は以下のようになる.

#!/usr/bin/env python
# -*- coding: utf-8 -*-

import fileinput


if __name__ == '__main__':
    for line in fileinput.input():
        tokens = map(int, line.strip().split())
        a, b = tokens[0], tokens[1]
        print a, b

ただ,標準入力といえば, raw_input() を用いるのが楽である.raw_input() は1行の入力末尾の改行文字を削除してくれるので,自分で strip() メソッドを呼び出す必要が無くなる.

入力データ数 n が与えられる場合,リスト内包表記を用いて [raw_input() for i in range(n)] とすることで,指定された行数の行を一気にリストとして取得できる.

#!/usr/bin/env python
# -*- coding: utf-8 -*-


if __name__ == '__main__':
    n = int(raw_input())
    for line in [raw_input() for i in range(n)]:
        tokens = map(int, line.strip().split())
        a, b = tokens[0], tokens[1]
        print '%d %d' % (a, b)

整数に変換する部分をまとめて,以下のようにまとめるのもよいだろう.

#!/usr/bin/env python
# -*- coding: utf-8 -*-


if __name__ == '__main__':
    n = int(raw_input())
    for tokens in map(lambda line: map(int, line.strip().split()), [raw_input() for i in range(n)]):
        a, b = tokens[0], tokens[1]
        print '%d %d' % (a, b)

Python 3

Python3になってから,print 文が廃止され, print() 関数になってしまった. また, map() の返り値がイテレータになったので,リストに変換するために list() 関数をかませる必要がある.

#!/usr/bin/env python
# -*- coding: utf-8 -*-

import fileinput


if __name__ == '__main__':
    for line in fileinput.input():
        tokens = list(map(int, line.strip().split()))
        a, b = tokens[0], tokens[1]
        print(a, b)

Python3では raw_input() の代わりに input() を用いないといけない. Python2の例と同様に,リスト内包表記を用いることで,指定行数だけ入力をリストとして一気に受け取ることができる.

#!/usr/bin/env python
# -*- coding: utf-8 -*-


if __name__ == '__main__':
    n = int(input())
    for tokens in map(lambda line: list(map(int, line.strip().split())), [input() for i in range(n)]):
        a, b = tokens[0], tokens[1]
        print('%d %d' % (a, b))

Ruby

特に解説することはない.

#!/usr/bin/env ruby
# -*- coding: utf-8 -*-

if __FILE__ == $0
  while line = STDIN.gets
    tokens = line.chomp!.split.map!(&:to_i)
    a, b = tokens[0], tokens[1]
    puts "#{a} #{b}"
  end
end

Perl

Perlはほとんど書いたことはないが,以下のような形になるだろう. $line =~ s/\s+$//; とすることで,入力のstripを行うことができる.

#!/usr/bin/env perl

use strict;
use utf8;
use warnings;


if ($0 eq __FILE__) {
  while (defined(my $line = <STDIN>)) {
    $line =~ s/\s+$//;
    my @tokens = split(/ +/, $line);
    my $a = $tokens[0];
    my $b = $tokens[1];
    printf("%d %d\n", $a, $b);
  }
}

PHP

PHPには詳しくないので,以下のような形でよいのかどうかも怪しい.

#!/usr/bin/env php
<?php
if (basename(__FILE__) == basename($_SERVER['PHP_SELF'])) {
  while ($line = fgets(STDIN)) {
    $tokens = split(' +', $line);
    echo $tokens[0];
    echo $tokens[1];
  }
}
?>

Go

最近,何かと人気のGo言語である. fmt.Scan() を用いるのであれば,以下のようにするとよいだろう.

package main

import (
  "fmt"
)


func main() {
  var a int
  var b int
  for _, err := fmt.Scan(&a, &b); err == nil; _, err = fmt.Scan(&a, &b) {
    fmt.Println(a, b)
  }
}

bifio が利用可能な環境であれば,以下のようにしてもよさそうだ.

package main

import (
  "bufio"
  "fmt"
  "os"
  "strconv"
  "strings"
)


func main() {
  scanner := bufio.NewScanner(os.Stdin)

  for scanner.Scan() {
    tokens := strings.Split(scanner.Text(), " ")
    a, _ := strconv.Atoi(tokens[0])
    b, _ := strconv.Atoi(tokens[1])
    fmt.Println(a, b)
  }
  if err := scanner.Err(); err != nil {
    fmt.Fprintln(os.Stderr, "reading standard input:", err)
  }
}

Lua

Luaは文字列の分割が無いので,自分で実装する必要がある. なかなかゴチャゴチャとした見た目になる.

なお,Luaのコメント形式は -- foo もしくは --[[bar]] という形式であるが,1行目のみshebangが許容されるようになっているので,ありきたりなshebangを記述している.

#!/usr/bin/env lua

if ... then
  module(..., package.seeall)
end


function split(str, delim)
  if string.find(str, delim) == nil then
    return { str }
  end
  local result = {}
  local pat = '(.-)' .. delim .. '()'
  local lastPos
  for part, pos in string.gfind(str, pat) do
    table.insert(result, part)
    lastPos = pos
  end
  table.insert(result, string.sub(str, lastPos))
  return result
end


if not ... then
  line = io.read()
  while line do
    tokens = split(line, ' +')
    print(tonumber(tokens[1]))
    print(tonumber(tokens[2]))
    line = io.read()
  end
end

Javascript (Node)

Node.jsは,標準入力をイベントとして感知することができるようになっている. ただ,受け取った時点で順次処理をしていくのはかなり限定的なケースになると思われるので,入力を配列に格納し,EOFのイベントを検知したら,処理を行うという汎用的な形にして記載する.

(function() {
  'use strict';

  var lines = [];
  require('readline').createInterface({
    input: process.stdin,
    output: process.stdout
  }).on('line', function(line) {
    lines.push(line);
  });
  process.stdin.on('end', function() {
    lines.forEach(function(line) {
      var tokens = line.split(' ').map(Number);
      console.log(tokens[0] + ' ' + tokens[1]);
    });
  });
})();

何となくスコープ化しておいたが,ライブラリを作るわけでもないので,じゃんじゃかグローバル変数,関数を生やしても問題はないはずではある. しかし,気持ちの問題として,スコープ化したくなってしまうものだ.

AtCoderのサンプルのように,

(function(input) {
  'use strict';

  input.split("\n").forEach(function(line) {
    var tokens = line.split(' ').map(Number);
    console.log(tokens[0] + ' ' + tokens[1]);
  });
})(require('fs').readFileSync('/dev/stdin', 'utf8'));

としてもよいが,手元の環境がWindowsであるなら,このサンプルは /dev/stdin が無いため動作しない. したがって,Windows環境でも動作する前者のサンプルをオススメする.

Scheme

標準入力には read 関数を用いることで,分割されたトークンを読み込むことができる. ただし,readLisp式を読み込む関数なので, 半角カッコがある入力の受け取りに用いることはできない.

(define (main-function)
  (letrec ((main-loop (lambda ()
                        (let ((a (read)) (b (read)))
                          (if (or (eof-object? a)
                                  (eof-object? b))
                            #f
                            (begin (display a)
                                   (display " ")
                                   (display b)
                                   (newline)
                                   (main-loop)))))))
    (main-loop)))

(main-function)

Common Lisp

Schemeと同様に read 関数を用いて,読み込みを行うことで,トークン毎の読み込みが可能となる. Common Lispでは末尾再帰最適化の保証がされないため,ループマクロが好んで用いられるという点も踏まえると,以下のようにするのがよいのだろうか?

(defun main ()
  ; (declare (optimize (safety 0) (space 0) (debug 0) (speed 3)))
  (loop for a = nil then b
        and b = nil then
        (progn (princ a)
               (princ b))
        until (or (null (setq a (read)))
                  (null (setq b (read))))))

(main)

もし,1行読み込んで,半角スペースでsplitするなら,以下のようにするのがよいだろう.

(defun split-by-one-space (string)
  ; (declare (optimize (safety 0) (space 0) (debug 0) (speed 3)))
  (loop for i = 0 then (1+ j)
        as j = (position #\Space string :start i)
        collect (subseq string i j)
        while j))

(defun main ()
  ; (declare (optimize (safety 0) (space 0) (debug 0) (speed 3)))
  (loop for line = nil then
        (let ((tokens (mapcar #'parse-integer
                              (split-by-one-space line))))
          (princ tokens))
        until (null (setq line (read-line)))))

(main)

なお,上記の2つの例でコメントアウトしている部分(optimize宣言をしている部分)は,最適化指示をしている部分である. テストがうまく通った後はコメントアウトを外すと,高速化が期待できるだろう.

Clojure

Clojureはほぼ触ったことが無いが,Common Lispと同じノリで書けると信じて,書いてみる.

(defn main
  []
  (loop [line (read-line)]
    (if (nil? line)
      nil
      (do (let [tokens (map #(Long/parseLong %) (.split line " +"))]
            (println tokens))
          (recur (read-line))))))

(main)

多分,普段からClojureを書いている人から見れば,ツッコみどころが満載だが,とりあえずはこの形式で動作させることができると思う. CodeIQのサンプルでは再帰を用いているが,Clojureでは末尾再帰最適化は保証されないと聞いたような気がするので, looprecur を用いた方が良いのではないかと思った.

bash

なかなか用いる機会は少ないが,bashで問題を解く場合は以下のようになる.

#!/bin/bash -eu

declare -i a b
while read a b; do
  echo "$a $b"
done

read コマンドはEOFを読み込んだとき,非0を返却するので,それを利用して,EOFまでの読み込みを行う. declare -i a b の行は無くても動作するが,シェル変数 ab を整数型として宣言しておくと気分が良いと思う.

Vim Script on bash

環境はかなり限られるが,bashからVim Scriptを実行することもできるらしい

#!/bin/bash -eu

vim -u NONE -i NONE -N -n -e -s -S <(cat <<EOF
function! s:main(lines) abort
  let answer = ''
  for line in a:lines
    let tokens = map(split(line, ' '), 'str2nr(v:val)')
    let [a, b] = [tokens[0], tokens[1]]
    answer .= printf("%d %d\n", a, b)
  endfor
  return answer
endfunction

let s:lines = getline(1, '$')
enew
put =s:main(s:lines)
1 delete _
%print
EOF
) <(cat)

CodeIQではbashが使えるが,vimを用いることができなかった. しかし,AtCoderでは利用可能であるらしい.

今後

D言語ScalaHaskell,RやSwift等についても調べたい. 余裕があればAWKも.... おそらく,この記事に追記する形で記載していくと思う.

参考

CodeIQのスクエア・カルテット問題を解いた

はじめに

CodeIQで@riverplus氏による「 スクエア・カルテット」問題 という,初等整数論を絡めた面白いプログラミングの問題があったので,それについての記事を書いた. 高校生の数学を思い出す良い問題であり,楽しかった.

問題

2つの自然数の組 $(a, b)$ が与えられたとき,自然数 $x, y$ に関する次の方程式を考えます.

\begin{equation} x^2 + a^2 = y^2 + b^2 \label{eq:given-equation} \end{equation}

例えば, $(a, b) = (3, 10)$ のとき,方程式(\ref{eq:given-equation})の解は $(x, y) = (10, 3), (46, 45)$ の2組です.

自然数の組 $(a, b)$ に対し,方程式(\ref{eq:given-equation})の全ての解の $x + y$ の和を $F(a, b)$ と定義します. 例えば $F(3, 10) = 10 + 3 + 46 + 45 = 104$ です. 同様に, $F(10, 50) = 3500$ , $F(20, 100) = 15022$ となることが確かめられます.

標準入力から,半角空白区切りで 2つの自然数 $a, b$ ( $1 \leq a < b \leq 10^5$ )が与えられます. 標準出力に $F(a, b)$ の値を出力するプログラムを書いてください.

考え方

ここでは,$0 \notin \mathbb{N}$ とする.

与式(\ref{eq:given-equation})を変形して,

\begin{equation} (x + y)(x - y) = b^2 - a^2 = n \label{eq:converted} \end{equation}

とおく($a, b \in \mathbb{N}$ かつ $a > b$ より $n \in \mathbb{N}$). よって, $x + y \in \mathbb{N}$ , $x - y \in \mathbb{N}$ . 式(\ref{eq:converted})より,$x$, $y$ に関する連立方程式

\begin{eqnarray} \begin{cases} x + y = p & \\ x - y = q & \end{cases} \label{eq:xypq} \end{eqnarray}

を得る($p, q \in \mathbb{N}$ かつ $n = pq$). $i$ 番目の解 $(x_i, y_i)$ に $p_i, q_i$ が対応すると考えると,出力すべき値は,

\begin{equation} F(a, b) = \sum_i (x_i + y_i) = \sum_i p_i = \sum_i \dfrac{n}{q_i} \end{equation}

である. 連立方程式(\ref{eq:xypq})を解くと,

\begin{equation} (x, y) = \left( \dfrac{p + q}{2}, \dfrac{p - q}{2} \right) \end{equation}

を得る. $x \in \mathbb{N}$ なので,

\begin{equation} (p + q) \bmod 2 = 0 \label{eq:pq-constrain} \end{equation}

また,$x, y \in \mathbb{N}$ なので,

\begin{equation} x - y = q < p = x + y \end{equation}

$p, q$ は $n$ を2つの自然数積に分解したもの,すなわち,$n$ の約数のペアであることを踏まえると,

\begin{equation} (1 \leq) \:\: q < \sqrt{n} < p \:\: (\leq n) \end{equation}

以上より, $\sqrt{n}$ より小さく(「以下」ではない),かつ条件(\ref{eq:pq-constrain})を満たす $n$ の約数 $q_i$ を全て見つけ出し,対になる約数 $p_i = \dfrac{n}{q_i}$ の総和 $\sum_i p_i$ を計算して,出力すると良い.

おまけ

$a < b$ という制約が無く,

  1. $a = b$ , すなわち $n = 0$
  2. $a > b$ , すなわち $n < 0$

である場合も,思考実験として考えてみる.

$n = 0$ の場合, $(x, y)$ は $x = y$ なる任意の自然数

$n < 0$ の場合,$x + y > 0$ なので,

\begin{equation} x - y = q < 0 \end{equation}

となり, $q$ がマイナス符号を担当する($p \in \mathbb{N}, q \in \mathbb{Z}$). 連立方程式(\ref{eq:converted})を

\begin{eqnarray} \begin{cases} y + x = p & \\ y - x = -q & \end{cases} \end{eqnarray}

と変形し, $y \rightarrow x'$ , $x \rightarrow y'$ , $p \rightarrow p'$ , $-q \rightarrow q' (> 0)$ と置き直すことで, $n > 0$ のときと同様に処理できる.

\begin{eqnarray} \begin{cases} x' + y' = p' & \\ x' - y' = q' & \end{cases} \end{eqnarray}

$-n (> 0)$ (マイナス符号が無い場合)と比較して, $(x, y)$ の組み合わせは逆転しているが,出力すべき値はその和

\begin{equation} F(a, b) = \sum_i (y'_i + x'_i) = \sum_i p'_i = \sum_i \dfrac{-n}{q'_i} \end{equation}

なので, $n$ と $-n$ のときの $F(a, b)$ は等しい. すなわち, $F(a, b) = F(b, a)$ .

まとめ

  1. $n = b^2 - a^2$ ( $n = | b^2 - a^2 |$ ) とし, $\sqrt{n}$ より小さく,$\left( q + \dfrac{n}{q} \right) \bmod 2 = 0$ となる $n$ の約数 $q_i$ を全て求める
  2. $\sum_i \dfrac{n}{q_i}$ を出力する

本番入力値と考察

以下の6ケースが本番での入力値であった.

10 26
11 389
123 456
35672 61243
71200 82321
19126 98765

1つ目のケース $(a, b) = (10, 26)$ は, $b^2 - a^2 = 576 = 24^2$ となり,コーナーケースであった($p = q = 24$ ,すなわち $(x, y) = (24, 0)$ を含めてしまうのは誤り). また,問題文の例にあった $(a, b) = (10, 50)$ は, $b^2 - a^2 = 576 = 2400$ となり,$2400$ は $\lfloor \sqrt{2400} \rfloor = 48$ を約数に持つので,(ある意味,前述のものと対になる)コーナーケースであった.

この2つのケースを考えると, $n = b^2 - a^2$ の約数を単純に $1, 2, \ldots, \lfloor \sqrt{n} \rfloor - 1$ から見つけ出すのは,本番ケースに限るならばうまくいくが誤りである. 解決策としては,$n$ が2乗数であるかどうかを判定し,範囲を調製しなければならないが,コードで書くと汚くなる上に面倒である. そこで,$1, 2, \ldots, \lfloor \sqrt{n - \epsilon} \rfloor$ ($\epsilon$ は十分に小さな正の実数)から約数を探索するようにすると単純に処理できるはずだ.

解答例

bashJavaC++で解答での解答例を紹介する. $ \epsilon = 1.0 \times 10^{-10}$ とした.

ちなみに,入力は各ケースにつき1行のみだったので,それぞれの解答例のように,whileでEOFまで読み込みを行う必要はない.

bashでの解答

あえて,bashで解くというのも面白い.

#!/bin/bash -eu

declare -i a b
while read a b; do
  declare -i n=$((b ** 2 - a ** 2))
  declare -i qMax=`echo "sqrt($n - 0.00000000001)" | bc | sed 's/\.[0-9]*$//g'`
  declare -i q answer=0
  for q in `seq 1 $qMax`; do
    (( n % q == 0 )) && (( (q + n / q) % 2 == 0 )) && (( answer += n / q ))
  done
  echo $answer
done

bashだと,下手に組むとTLEになるので,やや難易度は高かった(1秒の壁は大きい). expr コマンドは時間がかかるので,基本的にbashの算術式で計算し,平方根などの算術式では計算できないものは bc コマンドに投げて計算するだけだ.

なお,以下のようなbashの算術式のfor文

for ((i = 0; i < 100; i++)) {
  # 処理
}

だと時間がかかるので, seq コマンドで $1$ から $\lfloor \sqrt{n - \epsilon} \rfloor$ までの連続する整数のリストを生成し,通常のシェルのforを用いるとよい. また,ifのパースは時間がかかると予想できるので,短絡評価を利用し,bashの算術式を繋げるとよいだろう.

Javaでの解答

まともな言語,例えばJavaでは以下のように率直に書けばよいだろう.

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.stream.LongStream;

public class Main {
    public static void main(String[] args) throws Exception {
        try (BufferedReader br = new BufferedReader(new InputStreamReader(System.in))) {
            br.lines()
                .map(line -> Arrays.stream(line.split(" "))
                        .mapToLong(Long::parseLong)
                        .map(x -> x * x)
                        .toArray())
                .map(inputs -> inputs[1] - inputs[0])
                .map(n -> LongStream.rangeClosed(1, (long) Math.sqrt(n - 1e-10))
                        .filter(q -> n % q == 0 && ((q + n / q) & 0x01) == 0)
                        .map(q -> n / q)
                        .sum())
                .forEach(System.out::println);
        }
    }
}

Javaでは2の累乗の定数の乗算,除算,剰余はビット演算に置き換えた方が速い. C/C++ならば,2の累乗の定数の乗算,除算,剰余は最適化オプションを付与しなくてもビット演算に置き換えられるが,JavaコンパイラJITコンパイルのためにバイトコードを最適化しないようになっているため,2の累乗の定数の乗算,除算,剰余は,コンパイル後のバイトコードにおいても乗算,除算,剰余のままである. これは生成されるバイトコードを見れば一目瞭然である. しかし,JITコンパイルにより最適化されるかといえばそうではなく,手動でビット演算に置き換えた方が高速に動作する.

なお, $b^2 < 10^{10}$ なので,64bit整数型を用いないとオーバーフローする. この点は気をつけないといけない.

C++での解答

みんな大好きC++で書くと,以下のようになる. for文で逐次的に処理するので,連続する整数の配列やリストを生成する必要がなく, $\lfloor \sqrt{n - \epsilon} \rfloor$ の議論が不要になる. 大半の人はこういった解答をしていると思う. 試していないが,ループ毎に $q^2$ を計算するので, $\lfloor \sqrt{n - \epsilon} \rfloor$ を計算しておく場合と比較すると遅い気がするのだが,実際はどうなのだろうか?

#include <cstdlib>
#include <iostream>

typedef long long  llint;


int
main()
{
  std::cin.tie(0);
  std::ios::sync_with_stdio(false);

  llint a, b;
  while (std::cin >> a >> b) {
    llint n = b * b - a * a;
    llint answer = 0;
    for (llint q = 1; q * q < n; q++) {
      if (n % q != 0) continue;
      llint p = n / q;
      if ((p + q) % 2 == 1) continue;
      answer += p;
    }
    std::cout << answer << std::endl;
  }

  return EXIT_SUCCESS;
}

候補絞り込み型インターフェースを提供するプラグインについて

この記事は Vim Advent calendar 2015 の16日目の記事です.

僕は普段「だ・である」調でブログを書いていますが,今回の記事は多数の人に見ていただくことを考慮して,多くの人がブログで採用している「です・ます」調,語り口調で書いていくことにしましょう.

さて本題です. 候補を絞り込むインターフェースというのは人気で,Vimではunite.vimctrlp.vimなどが有名ですね. そして,コマンドラインツールfzfVimからも利用できるように,本体にVimプラグインが付属しています. また,ctrlp.vimにインスパイアされて開発されたプラグインとして,LeafCageさんによるalti.vimやkamichiduさんによるvim-milqiがあります. この記事では,前述の5つの候補絞り込み型インタフェースを提供するVimプラグイン

について,簡単な解説と比較をしたいと思います. FuzzyFindervim-kuについては取り上げません.

基本操作の比較

unite.vim

unite.vimでは,本体にたくさんの拡張が付属しており,第三者(特に日本人に多い)によって開発された拡張も多数公開されているので,自分で拡張を書く必要は無いですね. 基本的に, :Unite [unite source名] とすることで,unite.vimを起動できます.

unite.vim上でのキーマッピングは以下のようになっています. unite.vimは他の候補絞り込み型プラグインと異なり,ノーマルモードとインサートモードがあり,それぞれのモードで操作が異なります.

キーマッピング

ノーマルモード
キー 動作
i / I インサートモードに
a 候補選択時はアクションを選択,そうでなければ A と同じ
A 入力欄の末尾にカーソル移動をしてインサートモード
q or <C-g> unite.vim を終了し,1つ前のuntieバッファメニューを復元する
Q or g<C-g> unite.vim を終了する
<C-r> uniteを再起動する
<Space> / <S-Space> 候補の選択状態をトグル(複数選択できるsourceのみ)
* 全ての候補選択をトグルする(選択状態が反転する)
M 表示候補数を制限する
<Tab> アクションを選択する
<C-p> / <C-n> sourceを切り替える
<C-a> / <C-k> ログ / 候補を echo する
<C-l> 再描画する
<C-h> 1つ前のパスを削除する
gg or <C-Home> カーソルを1番上に
G or <C-End> カーソルを1番下に
j or <Down> カーソルを1つ下に
k or <Up> カーソルを1つ上に
J / K マッチしない候補をスキップしてカーソルを上 / 下に移動
g? 簡単なuniteのキーマッピングのヘルプを表示
N 候補を追加する(action_tableunite__new_candidate が定義されている場合のみ)
. ドットを絞り込み欄に入力し,インサートモードに
<CR> デフォルトアクションを行う
b ブックマークのアクションを行う
d 削除アクションを行う
e narrowアクションを行う
t 別のタブで開く
yy ヤンクアクションを行う
o オープンアクションを行う
x クイックマッチを用いて,デフォルトのアクションを行う(マークされた候補があるとダメ)
インサートモード
キー 動作
<Esc> ノーマルモード
<Tab> アクションを選択する
<C-n> or <Down> 次の行を選択
<C-p> or <Up> 前の行を選択
<C-f> / <C-b> 前 / 次の行を選択
<C-h> or <BS> カーソルの1つ前の文字を削除
<C-u> カーソルの前の入力を全て削除
<C-w> カーソルの前の単語を削除
<C-a> or <Home> カーソルを先頭に
<Left> / <Right> カーソルを右 / 左に移動
<C-l> 再描画する
<C-g> uniteを終了する
ビジュアルモード
キー 動作
<Space> 選択された範囲の候補全ての選択状態をトグル

本体付属のunite source

以下の表は,unite.vim本体から提供されているunite sourceの一部です. デフォルトのアクションについても併記しています.

他にもたくさんのunite sourceが付属しているので,調べてみると面白いと思います.

unite source名 機能
bookmark UniteBookmarkAdd でブックマークされたファイルを表示し,選択されたファイルを開く
buffer リストされているバッファ一覧を表示し,選択されたバッファを開く
change ファイルの変更履歴(:changeの結果)を表示し,選択された位置に移動
command 利用できるコマンドを表示し,選択されたコマンドをコマンドウィンドウに入力(引数のヒントも表示)
directory カレントディレクトリ以下のディレクトリを表示し,ファイラのように利用できる
file カレントディレクトリ以下のファイルとディレクトリを表示し,ファイラのように利用できる
file_rec カレントディレクトリ以下のファイルを再帰的に検索して表示し,ファイラのように利用できる
find 対象ディレクトリと名前を入力させて,findコマンドを実行した結果を表示
function 利用できる関数を表示し,選択された関数をコマンドウィンドウに入力(引数のヒントも提示)
grep 外部コマンド grep を行うように促し,grepを行った結果を一覧として表示.選択された位置に移動する
history/unite 過去に利用したunite sourceの履歴を表示
jump ジャンプリスト(:jumpsの結果)を表示し,選択された位置に移動
launcher パスが通っているところから,実行可能ファイルを候補として表示する
line 現在のバッファの全ての行を候補として表示し,選択された行に移動
mapping 全てのキーマッピングを表示し,選択されたものを実行する
output Vimコマンドを入力を促し,入力されたコマンドの出力を候補とする
process 起動中のプロセス一覧を表示し,選択した候補にTERMシグナルを送る(確認あり)
register Vimレジスタを表示し,選択されたレジスタの内容を現在位置に挿入
runtimepath runtimepath に追加されているディレクトリ一覧を表示し,選択されたディレクトリに移動
source unite sourceの一覧を表示し,選択されたsourceをもとにUniteを起動
tab 現在利用中のVimのタブ一覧(とタブ内のバッファをヒントとして)を表示し,選択されたタブに移動
vimgrep :vimgrep を行うように促し,vimgrepを行った結果を一覧として表示.選択された位置に移動する
window 現在のタブのウィンドウ一覧を表示し,選択されたウィンドウに移動

ctrlp.vim

プラグイン名になっているように,デフォルトでは <C-p> でCtrlPを起動します. あるいは, :CtrlP というコマンドで起動してもよいでしょう.

unite.vimと同様,ctrlp.vimの本体からも多数の拡張が提供されており,それぞれの拡張は :CtrlPXXXX のようなコマンドを実行することで利用可能です.

CtrlPバッファでのキーマッピングは以下のようになっています.

キー 動作
<C-c> or <Esc> CtrlPを終了する
<C-f> / <C-b> エクステンションを切り替える
<C-a> / <C-e> 入力ウィンドウのカーソルを先頭 / 最後に
<C-j> / <C-k> 候補ウィンドウのカーソルの上下移動
<C-d> フルパス検索モードとファイル名のみの検索モードを切り替え
<C-r> 正規表現検索モードと通常の検索モードのトグル
<CR> 同じタブに開く
<C-t> 新しいタブに開く
<C-v> 垂直分割で開く
<C-x> or <C-s> or <C-CR> 水平分割で開く
<C-p> 1つ前の入力履歴を入力欄に入れる
<C-n> 1つ後の入力履歴を入力欄に入れる
<F5> キャッシュを更新する
<F7> 選択した(マークを付けた)候補を候補から除外する
<C-z> 対象ファイルにマークを付ける(選択状態にする)

また,ctrlp.vimでは,:CtrlP 以外にもコマンドが提供されています. これらは, autoload/ctrlp.vim で定義されている組み込みの拡張とも言えるでしょう.

コマンド 機能
:CtrlPMRUFiles [dir] 最近利用したファイルを表示し,選択されたファイルを開く
:CtrlPBuffer リストされているバッファを表示し,選択されたバッファに移動する
:CtrlPLastMode [args] 最後に利用したCtrlP拡張を実行する,[args]--dir が指定されたとき,最後のワーキングディレクトリも用いる
:CtrlPClearCache or :ClearCtrlPCache CtrlPのキャッシュを削除する
:CtrlPAllClearCache or :ClearAllCtrlPCaches CtrlPのキャッシュを全て削除する
:CtrlPCurWD カレントディレクトリ以下のファイルを再帰的に表示
:CtrlPCurFile 現在編集中のファイルのディレクトリ以下のファイルを再帰的に表示
:CtrlPRoot わからない....

先に述べたように,ctrlp.vimの本体からは多数の拡張が提供されています. 先に述べた組み込みの拡張とは違い,多数の拡張は autoload/ctrlp/xxx.vim で定義されており,本体から分離されております.

拡張名 対応するコマンド 機能
tag :CtrlPTag 見つかったtagsファイル(オプション tags に依存)の項目を表示し,選択された項目の位置へジャンプする
buffertag :CtrlPBugTag [buffer] カレントバッファ,または指定されたバッファからtagsファイルの項目を表示し,選択された項目の位置へジャンプする
buffertag :CtrlPBugTagAll リストされているバッファ
quickfix :CtrlPQuickfix quickfixにある項目を表示し,選択されたエラー位置に移動する
dir :CtrlPDir [dir] カレントディレクトリ,または指定されたディレクトリ以下のディレクトリを表示し,選択されたディレクトリをワーキングディレクトリにする
rtscript :CtrlPRTS runtimepath 以下にあるファイルを表示し,選択されたファイルを開く
undo :CtrlPUndo Undo履歴を表示し,選択されたところまでundoする
list :CtrlPLine リストされている全てのバッファ,または指定されたバッファの行を表示し.選択された位置にジャンプする
changes :CtrlPChange [buffer] カレントバッファ,または指定されたバッファの変更箇所を表示し,選択された位置にジャンプする
changes :CtrlPChangeAll リストされているバッファ全ての変更履歴を表示し,選択された位置にジャンプする
mixed :CtrlPMixed カレントディレクトリ以下のファイル,バッファ,最近使用したファイルを表示し,選択されたものを開く
bookmarkdir :CtrlPBookmarkDir ブックマークされているディレクトリを表示し,
bookmarkdir :CtrlPBookmarkDirAdd [dir] カレントディレクトリ,または指定されたディレクトリをブックマークする(選択後,ブックマークのタイトルの入力が求められる)

fzf

fzfはコマンドラインツールとして呼び出されるので,Vimとして操作することはできません. 用意されているマッピングは以下のように単純なものです.

キー 動作
<C-c> or <C-g> or <Esc> fzfを終了する
<C-f> / <C-b> カーソルを移動する
<CR> 候補を選択する
<S-Tab> 複数選択可能なとき(オプション -m or --multi が指定されているとき),候補にマークを付ける

本体から拡張は提供されていないので,自分で書くことになるでしょう. 公式のwikiにサンプルが多数ありますので,それらを ~/.vimrc にコピペなどすればよいかと思います.

alti.vim

alti.vimグローバル変数 g:alti_default_mappings_base'standard''ctrlplike' を代入することで,操作のプリセットを変更することができます. このグローバル変数のデフォルト値は 'standard' なので,何もしなかったり,無効な値を入力すると,standardのキーマッピングになるでしょう.

standard

キー 動作
<BS> or <C-h> 入力欄のカーソルの前1文字を削除
<Del> or <C-d> 入力欄のカーソルの後ろ1文字を削除
<C-w> 入力欄のカーソルの前1単語を削除
<C-u> 入力欄をクリアする
<C-r> レジスタ挿入モードに
<C-x><C-n> or <C-_> 1つ後の入力履歴を入力欄に入れる
<C-x><C-p> or <C-s> 1つ前の入力履歴を入力欄に入れる
<C-a> / <C-e> 入力欄の先頭 / 末尾にカーソルを移動
<C-b> or <Left> 入力欄のカーソルを左に
<C-f> or <Right> 入力欄のカーソルを右に
<C-j> or <PageDown> or <kPageDown> 候補欄で次のページを表示する
<C-j> or <PageDown> or <kPageDown> 候補欄で前のページを表示する
<C-n> or <Down> 候補欄のカーソルを1つ下に
<C-p> or <Up> 候補欄のカーソルを1つ上に
<C-g>g or <C-g><C-g> or <Home> or <kHome> 候補窓で先頭にカーソルを移動
<C-g>G or <End> or <kEnd> 候補窓で末尾にカーソルを移動
<Tab> 候補窓のカーソル下の候補を,入力欄に入力する
<C-o> 選択候補についてのアクションメニューを出す
<Esc> or <C-c> alti.vimを終了する
<CR> 入力(あるいはカーソル下の候補)に基づいて,アクションを行う
<C-y> 拡張の定義辞書のキー default_actions に指定されたリストの0番目に指定されたアクションを実行
<C-v> 拡張の定義辞書のキー default_actions に指定されたリストの1番目に指定されたアクションを実行

ctrlplike

キー 動作
<BS> or <C-]> 入力欄のカーソルの前1文字を削除
<Del> or <C-d> 入力欄のカーソルの後ろ1文字を削除
<C-w> 入力欄のカーソルの前1単語を削除
<C-u> 入力欄をクリアする
<C-r> or <C-\> レジスタ挿入モードに
<C-n> 1つ後の入力履歴を入力欄に入れる
<C-p> 1つ前の入力履歴を入力欄に入れる
<C-a> / <C-e> 入力欄の先頭 / 末尾にカーソルを移動
<C-h> or <Left> 入力欄のカーソルを左に
<C-l> or <Right> 入力欄のカーソルを右に
<C-f> or <PageDown> or <kPageDown> 候補欄で次のページを表示する
<C-b> or <PageDown> or <kPageDown> 候補欄で前のページを表示する
<C-j> or <Down> 候補欄のカーソルを1つ下に
<C-k> or <Up> 候補欄のカーソルを1つ上に
<C-g>g or <C-g><C-g> or <Home> or <kHome> 候補窓で先頭にカーソルを移動
<C-g>G or <End> or <kEnd> 候補窓で末尾にカーソルを移動
<Tab> 候補窓のカーソル下の候補を,入力欄に入力する
<C-o> 選択候補についてのアクションメニューを出す
<Esc> or <C-c> alti.vimを終了する
<CR> 入力(あるいはカーソル下の候補)に基づいて,アクションを行う
<C-y> 拡張の定義辞書のキー default_actions に指定されたリストの0番目に指定されたアクションを実行
<C-v> 拡張の定義辞書のキー default_actions に指定されたリストの1番目に指定されたアクションを実行

このプラグインも本体に拡張は付属していませんが,使い勝手はかなり良いので,拡張を自分で作って利用するとよいでしょう.

vim-milqi

vim-milqiはドキュメントが無いので,ソースコードを読んだ結果を書きます. このあたりを見る限り,ctrlp.vimから持ってきてると推測できるので,ほとんどctrlp.vimと同じ操作であると言ってよいでしょう.

vim-milqiの本体にも拡張は付属していませんが, :MilqiFromUnite というコマンドが提供されており,引数にunite source名を指定することで,unite sourceから候補を取得し,アクションを実行することができます. 他のプラグインでは提供されていない機能なので,なかなか面白いと思いました. しかし,unite sourceの候補にkindが指定されていない場合,エラーとなるので注意が必要です.

拡張の作りやすさの比較

各絞り込み検索プラグインの拡張の作りやすさを比較してみましょう. まず,拡張において実現できる特徴的なことを比較すると,以下のようになります.

プラグイン 複数選択 複数のアクションの提供 非同期の候補取得 プロンプトの変更
unite.vim ○(起動オプション)
ctrlp.vim △(候補選択時のキー) × ×
fzf × ×
alti.vim × ◎(動的に変更可)
vim-milqi × × ×

ここでいう「非同期の候補取得」とは,定期的に候補を取得処理を呼び出し,選択可能な候補数を増やす(あるいは減らすこともできるでしょう)ことです. Vimでは非同期処理をする手段がちゃんとした形で提供されていないので,非同期の候補の取得は,Shougo/vimproc.vimと, updatetimefeedkeys() , そして, CursorHoldCursorMoved という autocmd を組み合わせたポーリングによって行われるのが主流です. +clientserver の機能と RemoteReply を組み合わせても非同期処理は実現できますが,+clientserver になっているVimは多くないので,こちらが採用されることはありません.

非同期の候補取得でアニメーションを実現するという面白い使い方もあり,例えばsupermomonga/jazzradio.vimでは音量レベルのようなアニメーションを行うunite sourceが提供されています.

さて,同じ目的を達成するそれぞれの拡張を作ってみましょう. 今回は「apple, banana, cakeという3つの候補を表示し,それぞれ選択されたものを echomsg する」という非常に単純なものを作ることにします.

とにかく,コードを書かないと始まりませんね. 以下,それぞれのコードと解説です. なお,このサンプルの拡張は koturn/vim-exts にあります.

plugin/exts.vim : インタフェース

if exists('g:loaded_exts')
  finish
endif
let g:loaded_exts = 1
let s:save_cpo = &cpo
set cpo&vim

command! CtrlPExts  call ctrlp#init(ctrlp#exts#id())
command! FZFExts  call fzf#run(fzf#exts#option())
command! AltiExts  call alti#init(alti#exts#define())
command! MilqiExts  call milqi#candidate_first(milqi#exts#define())
" command! MilqiExts  call milqi#query_first(milqi#exts#define())

let &cpo = s:save_cpo
unlet s:save_cpo

インターフェースを定義しているだけなので,特に言及することはありません. uniteだけはコマンド定義しなくて良いので楽ですね. vim-milqiを用いるコマンドについて,コメントアウトしているものがありますが,これについてはvim-milqiの項目で解説します.

autoload/unite/sources/exts.vim : unite.vimの拡張

let s:save_cpo = &cpo
set cpo&vim


let s:source = {
      \ 'name': 'exts',
      \ 'description': 'descriptions',
      \ 'action_table': {},
      \ 'default_action': 'my_action'
      \}

let s:source.action_table.my_action = {
      \ 'description': 'my action'
      \}
function! s:source.action_table.my_action.func(candidate) abort
  echomsg a:candidate.word
endfunction

function! s:source.gather_candidates(args, context) abort
  return map(['apple', 'banana', 'cake'], '{
        \ "word": v:val
        \}')
endfunction


function! unite#sources#exts#define() abort
  return s:source
endfunction


let &cpo = s:save_cpo
unlet s:save_cpo

unite#sources#exts#define() でunite sourceに関する辞書を返却するようにします. 今回は word のみ指定していますが, abbrkind など,他にも重要な項目もありますので, :h unite-notation-{candidate} で調べてみるとよいでしょう. この関数はunite.vim本体から呼び出されます.

上記の例では,myaction というアクションのみを source に対して定義し,<CR> で選択したときのアクションである default_action に指定しています.

また,今回はやっていませんが,s:source.action_table.my_actionis_selectable: 1 を追加すると複数選択できるようになり,s:source.action_table.myaction.func() の引数が,選択した候補の辞書ではなく,複数の辞書を含むリストになります.

なお,作成したunite sourceに引数を渡して起動したい場合は, Unite exts:arg1:arg2 のように,コロン区切りで引数を指定する形になります. この引数は, s:source.gather_candidates の第一引数 a:args というリストで受け取ることができます. この引数を補完する関数は, s:source のキー complete に,補完関数の関数参照を指定します.

function! s:source.complete(args, context, arglead, cmdline, cursorpos) abort
  return filter(['foo', 'bar', 'piyo'], 'v:val =~? ^"' . a:arglead . '"')
endfunction

のような形になり, <Tab> によって選択できる候補のリストを返却すればよいだけです. ユーザー定義コマンドの補完関数と似たようなもので,引数が2つほど増えているだけですね.

ちなみに,アクションはunite kindとして分離可能であり,丁寧なunite拡張を書くのであれば,候補の取得はsourceで,アクションの担当はkindにした方がよいでしょう(前述の通り,vim-milqiはKindを利用します). kindを指定しなかった場合,untie.vimではkindにcommonが指定されたものとします.

autoload/ctrlp/exts.vim : ctrlp.vimの拡張

if get(g:, 'loaded_ctrlp_exts', 0)
  finish
endif
let g:loaded_ctrlp_exts = 1
let s:save_cpo = &cpo
set cpo&vim

let s:ctrlp_builtins = ctrlp#getvar('g:ctrlp_builtins')

function! s:get_sid_prefix() abort
  return matchstr(expand('<sfile>'), 'function \zs<SNR>\d\+_\zeget_sid_prefix$')
endfunction
let s:sid_prefix = s:get_sid_prefix()
delfunction s:get_sid_prefix

let g:ctrlp_ext_vars = add(get(g:, 'ctrlp_ext_vars', []), {
      \ 'init': s:sid_prefix . 'init()',
      \ 'accept': s:sid_prefix . 'accept',
      \ 'lname': 'sample extension',
      \ 'sname': 'sample',
      \ 'type': 'line',
      \ 'nolim': 1
      \})
let s:id = s:ctrlp_builtins + len(g:ctrlp_ext_vars)
unlet s:ctrlp_builtins s:sid_prefix


function! ctrlp#exts#id() abort
  return s:id
endfunction


function! s:init() abort
  let candidates = ['apple', 'banana', 'cake']
  return candidates
endfunction

function! s:accept(mode, str) abort
  call ctrlp#exit()
  echomsg a:str
endfunction


let &cpo = s:save_cpo
unlet s:save_cpo

ctrlp.vimの拡張の作り方に関しては,以下の記事に詳しく書いてあるので,そちらを見ていただいた方がよいでしょう.

ざっと説明すると, s:init() は候補の取得を担当する関数で, s:accept() がアクションを担当する関数になります. ctrlp#exts#id() は,この拡張のIDを返却する関数で,ctrlp.vimの本体の関数 ctrlp#init() に渡すことで,ctrlpが起動します. 他の候補選択型インターフェースと比較して,作成した拡張の起動に辞書をそのまま渡せる形にしてほしかったと感じます.

autoload/fzf/exts.vim : fzfの拡張

let s:save_cpo = &cpo
set cpo&vim


function! fzf#sampleoption() abort
  return {
        \ 'down': 20,
        \ 'sink': function('s:sink'),
        \ 'source': s:gather_candidates()
        \}
endfunction

function! s:gather_candidates() abort
  return ['apple', 'banana', 'cake']
endfunction

function! s:sink(candidate) abort
  echo len(readfile(a:candidate))
endfunction


let &cpo = s:save_cpo
unlet s:save_cpo

fzfはファイルを分離する必要は無いのですが,他のプラグインに習って分離してみました. 拡張の作り方については,以前書いた

を参考にするとよいでしょう.

autoload/alti/exts.vim : alti.vimの拡張

let s:save_cpo = &cpo
set cpo&vim

function! s:get_sid_prefix() abort
  return matchstr(expand('<sfile>'), 'function \zs<SNR>\d\+_\zeget_sid_prefix$')
endfunction
let s:sid_prefix = s:get_sid_prefix()
delfunction s:get_sid_prefix

let s:define = {
      \ 'name': 'exts',
      \ 'cmpl': s:sid_prefix . 'cmpl',
      \ 'prompt': s:sid_prefix . 'prompt',
      \ 'submitted': s:sid_prefix . 'submitted'
      \}
unlet s:sid_prefix

function! alti#exts#define() abort
  return s:define
endfunction


function! s:cmpl(context) abort
  return a:context.filtered(self.candidates)
endfunction

function! s:prompt(context) abort
  return 'exts> '
endfunction

function! s:submitted(context, line) abort
  if len(a:context.inputs) == 0
    echomsg a:context.selection
  else
    for input in a:context.inputs
      echomsg input
    endfor
  endif
endfunction


let &cpo = s:save_cpo
unlet s:save_cpo

alti.vimはctrlp.vimに不満があって作成されたプラグインだけあって,拡張の作成はctrlp.vimと似た雰囲気になります. しかし,ctrlp.vimよりパワフルな拡張を作ることが可能になっています. alti.vimは入力することに重きを置いたプラグインという雰囲気です.

上記コードにおいて,候補の取得とフィルタリングは s:cmpl() が,アクションは s:submitted() が担当しています. 他の候補絞り込み型プラグインと異なり,s:cmpl() で入力に対する候補の絞り込みを実装する必要があります. alti.vim本体には4つのフィルタリング関数が(引数 context の辞書関数として)用意されており,それぞれ

  • 前方一致:a:context.filtered()
  • 後方一致:a:context.backward_filtered()
  • 部分一致:a:context.partial_filtered()
  • 曖昧一致:a:context.fuzzy_filtered()

となっています. もちろん,自前でフィルタリングを実装してもよいですが,基本的には上記4つのいずれかを用いることで解決できるでしょう.

s:submitted() において,カーソル下にあった候補は, a:context.selection に格納され,入力された候補は a:context.inputs にリストとして格納されています. alti.vimでは,スペース区切りで候補の入力が認識されるようになっていて,複数の候補を選択する場合は,スペース区切りで入力することになります. <Tab> を入力することで,候補窓のカーソル下の候補が入力欄に挿入されるので,ユーザとしては,

  1. 絞り込みクエリを入力し,候補を絞り込む
  2. 候補窓でカーソル移動をして,候補を <Tab> で完全に入力欄に入力する
  3. <CR> で選択を終え,アクションを実行する

という流れになると思います. alti.vim的には,ユーザが <CR> でカーソル下の単語を選択してアクションを実行するのではなく, <CR> によって,入力された候補を送信することが想定されていると思われます. したがって, a:context.selection は基本的にアクション側で見る必要はないでしょう(ただし,受理できる入力が無かった場合は,カーソル下の候補に対してアクションを行うというのもアリかもしれません). なお,入力された候補は,候補窓からは除外されるようになっているので,重複選択の恐れはありません. 手動で重複した入力を与えたとしても,候補から除外されます.

入力欄に入力されたもののうち,元々の候補群になかったものは除外されて a:context.inputs に格納されます. つまり,ユーザがでたらめな入力をしたとしても,それらは全て除外されるということです.

なお,上記コード中の辞書 s:define の中で,値が関数名の文字列となっているものは,関数参照を取ることも可能です. 関数名を渡すより,関数参照を渡した方がコードとしてはシンプルになるのではないかと思います.

autoload/milqi/exts.vim : vim-milqiの拡張

let s:save_cpo = &cpo
set cpo&vim


let s:define = {'name': 'exts'}

function! milqi#exts#define() abort
  return s:define
endfunction

function! s:define.init(context) abort
  " let context.i = 0
  return ['apple', 'banana', 'cake']
endfunction

function! s:define.accept(context, candidate) abort
  call milqi#exit()
  echomsg a:candidate
endfunction

" function! s:define.lazy_init(context, query) abort
"   let a:context.i += 1
"   if query ==# ''
"     return {
"           \ 'reset': 0,
"           \ 'candidates': map(['lazy_apple', 'lazy_banana', 'lazy_cake'],
"           \   'v:val . " - " . a:context.i')
"           \}
"   else
"     return {
"           \ 'reset': 1,
"           \ 'candidates': ['apple_query', 'banana_query', 'cake_query']
"           \}
"   endif
" endfunction

" function! s:define.async_init(context) abort
"   let a:context.i += 1
"   return {
"         \ 'done': a:context.i < 6 ? 0 : 1,
"         \ 'candidates': map(['async_apple', 'async_banana', 'async_cake'],
"         \   'v:val . " - " . a:context.i')
"         \}
" endfunction


let &cpo = s:save_cpo
unlet s:save_cpo

辞書関数ばかりとなっていますが,コードの雰囲気は,ctrlp.vimと似ていますね. 今回の例では活用していませんが(例が悪いのは申し訳ありません),vim-milqiの一番の特徴は, query-firstcandidate-first という2つのインタラクションモードです. 上記コード中では s:define.lazy_inits:define.async_init が,それらのインタラクションモードでのアクションに関係しています この2つのインタラクションモードは,vim-milqiのセールスポイントを語る上では欠かせない要素です. 以下,2015年3月29日のLingrの過去ログからの引用です.

query-firstは入力に応じて動的に内容が変化する系,candidate-firstは単なる非同期ctrlp系ですね candidate-firstだと,例えば時間のかかる処理で候補の取得に時間のかかるもの向けで考えていて query-firstだと,例えば過去の選択状態に応じて最初に一部の候補をキャッシュから出し,入力があれば入力に対応した候補を動的に生成して出すということができます candidate-firstはuniteやctrlpを考えていただければイメージは掴みやすいと思います query-firstは,こっちが私のやりたいメインですが,例えば初期表示でa, bを表示,hogeと入力したときにc, d, eを表示,hogeを消してfugaと入力したときにf, g, h, iを表示,ということができます

candidate-first

candidate-first は,unite.vimにもある「非同期の候補の取得ができるもの」といえるでしょう. candidate-firstモードとして利用する場合, milqi#candidate_first() に拡張の定義辞書を渡します. この辞書のキー async_init に関数参照が指定されていれば, updatetime ハックにより,定期的にその関数がコールされます. async_init に指定された関数は,donecandidates をキーに持つ辞書を返却する必要があります. キーの名前の通り, done は非同期処理が終了したかどうかを, candidates は非同期で取得した候補を表します. candidate に指定したリストは既にある候補群に追加されるので,拡張を作成する側が候補リストの要素に追加するといった処理は不要です. done1 を指定したとき,非同期処理は完了したものとして,関数を定期的なコールが終了します.

query-first

query-first は,入力に応じて,候補を動的に生成する,といったものらしいです. query-firstモードとして利用する場合, milqi#candidate_first() に拡張の定義辞書を渡します. この辞書のキー lazy_init に関数参照が指定されていれば, updatetime ハックにより,定期的にその関数がコールされます. ここまでは,candidate-firstモードと変わらないですが, lazy_init に指定した関数は第二引数に入力クエリを受け取ることができます. そして,返り値は resetcandidates をキーに持つ辞書を返却しなくてはなりません. candidates に指定したリストが候補群に追加されていくのは,candidate-firstモードの async_init と同様ですが, reset1 を指定することで,候補群を(ただの init で返却した候補リストも含めて)全て除去することができます. 入力クエリと reset を活用して,候補を動的に変更するのが,query-firstモードの使い方といえるでしょう.

単純な例の場合

今回のような単純な例(拡張辞書に lazy_initasync_init のどちらも持たない例)では,どちらのモードでも(すなわち, milqi#query_first()milqi#candidate_first のどちらに拡張の定義辞書を渡しても),動作に違いは無いでしょう.

なお,上記コード中のコメントアウト部分を解除し, plugin/exts.vimvim-milqiに関する部分を適切に変更することで,candidate-first , query-firstのそれぞれを体験することができるようにしています. candidate-firstの場合は,関数が5回コールされるまで,候補が増えるようにしています. query-first の場合,何か入力すると,候補が apple_querybanana_querycake_query の3つだけになるようにしています.

感想

この記事では5つの候補絞り込み型インターフェースを提供するプラグインについて,簡単に説明しました. どれもざっと見た限りでは「候補絞り込み型」という風にまとめられますが,それぞれが実現したいことや,目指しているものが少しずつ違っていて面白いですね.

unite.vimは初めから拡張を見越して作られた分,第三者にとってはかなり自由かつパワフルに拡張を作ることができるようになっています. また,作成したsourceの呼び出しは, :Unite のサブコマンド,すなわち第一引数にsource名を与える形になっているので,source作成者が plugin/ 下のファイルにコマンドを定義しなくてよいのも魅力です. :Unite のオプション引数である -auto-preview などは,uniteにしかできないことでしょう.

ctrlp.vimは元々がファイラであり,拡張が後付けのようなものであるため,作ることのできる拡張にやや不自由があるのは否めません. 例えば,複数選択がファイルを開くという操作に限定されるので,第三者にとっては利用しにくいものでしょう. しかし,コンパクトな実装である分,unite.vimより初回の起動時間が短い点は評価できるでしょう.

fzfは外部コマンドとして利用するので,一時的にVimから出る形になります. その点が他の絞り込み検索型のプラグインと比べると異質なところではあります. しかし,tmux上であれば,画面分割を利用し,候補を表示することができたり,neovimであればneovimのターミナルエミュレーター上で起動するようにしていたり,とても面白い機能が実装されています.

alti.vimはctrlp.vimにインスパイアされて開発されたプラグインだけあって,細かい部分での配慮が行きとどいていますね. 本体から前方一致,後方一致,部分一致,ファジーマッチという4つの絞り込み関数が提供されているのも,なかなかよいと感じました. ctrlp.vimはファジーマッチしかできないようになっており,僕としては多数の候補のフィルタリングに苦労することがありました.

vim-milqiは,unite souceから候補を取得できるようにしているのは画期的な機能だと思いました. また,非同期処理を主眼に置いており,他の絞り込み検索プラグインには無い特徴を感じ取ることができました.

おわりに

絞り込み検索型プラグインの拡張を作ることは難しくありません. この記事で紹介したような,たった十数行程度のコード(ほとんどが定型句のようなもので,本質的な部分は数行程度)を書くだけで,自作のプラグインから絞り込み検索型プラグインのUIを利用することができます. もし,これを読んでいるあなたがプラグイン作成の初心者であり,unite sourceやctrlp.vimの拡張を書いたことが無いのであれば,この機会に挑戦してみるのはいかがでしょうか?

なお,unite.vimは日本での知名度がとても高く,ググれば多数の情報が出てくると思います. unite.vimは高機能なため,この記事では紹介しきれていないので,unite.vimの本当の力を知るためにもググることをオススメします.

参考

Cygwinでclipboard機能を有効にしたVimをビルドする

はじめに

昔のCygwinVimではクリップボードが利用できず,Cygwinで用意されているクリップボードデバイス /dev/clipboard に対し,読み書きを行うことや, getclipputclip コマンドを利用することで,クリップボードとのやりとりを行っていた.

kanaさんのkana/vim-fakeclipというプラグインは,Cygwinや他の環境で +clipboard でないVimであっても,外部コマンドなどを用いることによって,クリップボードを何とか利用しようというものであり,かつてのCygwinVimユーザーは,よくこのプラグインを利用していたことだろう.

しかし,Vim 7.3.836以降,k_takataさんにより,CygwinVimでもクリップボード機能が利用できるようになった. 最近では,Cygwinにデフォルトで付属しているVimであっても,クリップボード機能を有効にしてビルドされており,利用することができる. だが,僕がCygwinVimを自前ビルドしたとき, +clipboard となっているのに,クリップボードが利用できなかった. この記事では,そのときにハマったことと,どう解決したかについて述べる.

長い前書きになったが,内容としては「こうやっただけ」というしょうもないものである. 結論を先に言うと, configure--enable-gui=no--without-x を指定しただけである.

CygwinVimをビルドする

最近では,VimソースコードGitHubで管理されているようになっているので,GitHubからソースを落としてくる.

$ git clone https://github.com/vim/vim.git

リポジトリのルートディレクトリに configure が用意されているので,多くのソフトウェアと同じく,

$ ./configure
$ make
$ make install

の順で実行するとよい.

configure については,適当に情報を収集し,以下のようにオプションを追加し,ビルドした.

$ ./configure \
  --prefix=/usr/local/ \
  --enable-fail-if-missing \
  --enable-gui=yes \
  --enable-multibyte=yes \
  --enable-perlinterp=yes \
  --enable-pythoninterp=yes \
  --enable-rubyinterp=yes \
  --enable-tclinterp=yes \
  --enable-luainterp=yes \
  --enable-cscope=yes \
  --enable-gpm \
  --enable-cscope \
  --enable-fontset \
  --with-features=huge \
  --with-x \
  --with-compiledby=koturn && \
  make -j5 && \
  make install

しかし,この設定では +clipboard となったが,クリップボードが利用できなかった. そのときに,ざっと調べたときに見た情報から, --with-x--enable-gui=yes が余計なのではないかと思った. そこで,--with-x の代わりに --without-x を, --enable-gui=yes の代わりに --enable-gui=no を指定して,再度 configure を行いビルドした(1度 configure を行った場合, rm src/auto/config.cache をしておく必要がある).

$ ./configure \
  --prefix=/usr/local/ \
  --enable-fail-if-missing \
  --enable-gui=no \
  --enable-multibyte=yes \
  --enable-perlinterp=yes \
  --enable-pythoninterp=yes \
  --enable-rubyinterp=yes \
  --enable-tclinterp=yes \
  --enable-luainterp=yes \
  --enable-cscope=yes \
  --enable-gpm \
  --enable-cscope \
  --enable-fontset \
  --with-features=huge \
  --without-x \
  --with-compiledby=koturn && \
  make -j5 && \
  make install

これで自前ビルドのCygwinVimであっても,クリップボード機能が利用可能となった. 明示的に --without-x--enable-gui=no を指定しなかった場合でも,クリップボードが有効にならなかったので,ちゃんと指定しなくてはならない.

余談

CFLAGSLDFLAGS に,自分なりの最適化オプションを追加してもビルドできるか?ということが気になったので,

$ ./configure \
  --prefix=/usr/local/ \
  --enable-fail-if-missing \
  --enable-gui=no \
  --enable-multibyte=yes \
  --enable-perlinterp=yes \
  --enable-pythoninterp=yes \
  --enable-rubyinterp=yes \
  --enable-tclinterp=yes \
  --enable-luainterp=yes \
  --enable-cscope=yes \
  --enable-gpm \
  --enable-cscope \
  --enable-fontset \
  --with-features=huge \
  --without-x \
  --with-compiledby=koturn \
  CFLAGS='-Ofast -m64 -march=native -mtune=native -flto -funroll-loops -DNDEBUG' \
  LDFLAGS='-flto' && \
  make -j5 && \
  make install

としてビルドしてみた. しかし,-flto が何かの悪さをしているらしく,出来上がったバイナリを実行すると,Vimが立ち上がった瞬間にエラーが出た. -flto を外すと,エラー無く,無事に実行できた.

まとめ

CygwinVimconfigure--enable-gui=no --without-x を指定しないと,クリップボードが有効にならない.

参考