0. はじめに

この記事は C++ Advent Calendar 2017 の DAY 1 に寄稿したものです。😃

初日は楽しい記事が良いだろうと考え、クイズ形式で C++ コードを楽しむコンセプトで記事を書くことにしました。今年は UE4 の C++ 実装を眺める時間が業務でも多くなりましたので、 Unreal Engine のソースコードを基に C++ の Tips などをクイズ形式で紹介します。

Unreal Engine について

Unreal Engine は Epic Games が現在は OSS として github で公開しながら開発を続けている C++ の実装を基にしたゲームエンジン、フレームワークです。執筆現在の現行版は 4.18 です。この記事は 4.18 のソースコードを基に執筆します。

https://github.com/EpicGames/UnrealEngine/tree/4.18
- Unreal Engine としてのソースコード
- 最終製品向けではないエンジンの開発用コードなども含む
https://github.com/EpicGames/UnrealEngine/tree/4.18/Engine/Source/Runtime
- Unreal Engine を使用する開発者が製品用に使用するライブラリーのソースコードはこの辺り

実行環境について

Wandbox にて gcc-7.2.0 を Warning=ON, Optimization=OFF, Verbose=OFF, Don't Use Boost, Sprout=OFF, MessagePack=OFF, C++14, -pedantic-errors, Compiler options="" 設定を基本の実行環境とします。

https://wandbox.org/

また、この記事の内容は一般的な x64 アーキテクチャーの PC や互換性のある処理系を対象の範囲とします。これは、例えば float は IEEE754/binary32 を前提とする事を意味します。

出題について

Unreal Engine の実装を基に問題を作成していますが、 Unreal Engine には依存しない C++ の問題となるよう調整しています。また、本記事の問題はあくまでも QUIZ として楽しめるよう工夫したもので、問題に登場するバグが実際の Unreal Engine のソースコードでバグとして対処されないまま埋め込まれているという事ではありません。

また、問題は C++ のコードを例示して出題していますが、 C++ の言語仕様に起因するクイズを中心とした C++ Quiz とはことなり、本記事ではもっと緩く C++ 以外でも起こり得る問題を広く扱います。

非常勤講師をしていた頃を思い出して、学生へ講座のはじまりに遊びを兼ねて出題するような気持ちで作りますので、 C++ 初心者、学生さんに楽しんで貰えれば嬉しく思います。

記法について

文章中で template 仮引数を一般に詳細に明記せずとも意図が通じると思われる範囲内で std::vector<T> のように略記する事があります。
文章中で値域を [ 0.0 .. 1.0 ] のように表記する場合があります。端の括弧は端の値も含まれる場合には [ または ] を用い、端の値が含まれない場合には ( または ) を用います。また、値の間に .. があれば明示された値で挟まれた任意の値を取り得る事を意味し、 2つ以上数値が , で区切られて続いていれば , で区切られた間隔で連続する事を意味し、 .. の前後に具体的な数値が無い場合には文脈上の最小値または最大値、もしくは理論上の -∞ または +∞ へ続く意図です。
文章中では変数の値などの数値に , や + を加えて読みやすく表現する場合があります。
文章中では C++ コードとしてではなく一般的な数式の表現として a=2π+π/2 のような表現をする場合があります。
uint8, int32 など UE4 で定義される型で、一般にその型名から定義が明白と考えられる型については特に解説なく用います。
ソースコード中に UE4 由来の check() マクロが登場する事があります。これは <cassert> で使用可能となる assert() マクロを #define check(X) { assert(X); } と薄くラップしたものと同様と考えて下さい。簡易的な試験として括弧の中の式が実行時に評価され、 false の場合にはプログラムの動作が停止し問題が検出される一般的なアサーションとして用います。

こたえについて

答えが見えてしまうとクイズとして楽しみ難い方も多いと思います。そこで、クイズに対する著者が想定したこたえはこの記事に続けて投稿する別の記事として掲載し、この記事のおわりからリンクする事にします。

また、「ぐぐ」れば答えがすぐに見つかる問題もありますが、「クイズ」を楽しみたい方は答えがすぐに思い浮かばない問題にも、しばらくは自分の既存の知識と思考、それから wandbox でコード片を試すなどしてできるだけ答えを "現時点での自力" で見出そうとするとすぐにググってしまうよりも楽しく、また分からなかった問題についても知識として身につく事も増えるかもしれません。

float 型の [ 0.0 .. 1.0 ] の値を uint8 型の [ 0 .. 256 ) へ写像したかった
意図しない整数のオーバーフローと問題の遮蔽
浮動小数点数型
遅すぎた 2 の指数 [ 1, 2, 4, 8, 16, 32, .. ] の判定
正弦と余弦も速くしたい
ニアリーイコール、再び
人間が読みやすい "数値" にしたかった
整数型、再びトラブる
G.C.D.
L.C.M.

1. CPP-QUIZ from Unreal

Q1. `float` 型の `[ 0.0 .. 1.0 ]` の値を `uint8` 型の `[ 0 .. 256 )` へ写像したかった

次の実装にはバグが潜んでいる。どのようなバグか。

/// float 型の [ 0.0 .. 1.0 ] の値を uint8 型の [ 0 .. 256 ) へ写像
/// @in [ 0.0 .. 1.0 ]
/// @out [ 0 .. 256 )
uint8 Quantize8UnsignedByte( float in )
{
  int out = in * 255;
  
  check( out >=   0 );
  check( out <= 255 );
  
  return out;
}

Hint: この方法で写像されて得られる uint8 型の 0 と 255 は巾筒な "幅" に写像されたものだろうか。

Q2. 意図しない整数のオーバーフローと問題の遮蔽

次の実装にはバグが潜んでいる。どのようなバグか。

/// [ 0 .. 1 ] の ratio を [ a .. b ] へ写像
/// @tparam TV a, b, return の型
/// @tparam TR ratio の型
/// @param ratio [ 0 .. 1 ]
/// @param return [ a .. b ]
template < typename TV, typename TR >
TV Lerp( const TV a, const TV b, const TR ratio )
{
  static_assert( std::is_arithmetic_v< TV > , "" )
  static_assert( std::is_arithmetic_v< TR > , "" )
  check( ratio >= 0 );
  check( ratio <= 1 );
  return (TV)( a + ratio * ( b - a ) );
}

Hint: TV が整数型の場合も意図した結果を得られるだろうか？ uint8, int8, uint16, int16, ...

Q3. 浮動小数点数型

宇宙に浮かぶ天体としては小ぶりだがそこそこの重力のある人工の惑星の上を宇宙船が飛ぶゲームを作っているとする。この天体は十分に小さく、考慮すべき宇宙空間は float 型で問題無く扱える範囲内とする。

同じ高度に居る宇宙船同士はミニマップ（画面上に表示される小さな地図）に表示したい。そこで次の実装を行ったとする。

恐らくこれは前提のストーリーを考慮すれば意図通りの動作をせずバグチケットが上がる事になる。どのような問題が発生するだろうか。

/// ある座標を中心とした球面軌道上に浮かぶ2つの物体が同じ高度に居るか判定
/// @param a 位置 o を中心とする系に浮かぶ宇宙船 A の位置
/// @param b 位置 o を中心とする系に浮かぶ宇宙船 B の位置
/// @param o a, b が中心とする人工惑星 O の中心位置
/// @return true: 同じ高度にいる
bool IsSameAltitude( const FVector& a, const FVector& b, const FVector& o )
{
  auto o_to_a = a - o;
  auto o_to_b = b - o;
  auto altitude_of_a = o_to_a.Length();
  auto altitude_of_b = o_to_b.Length();
  return altitude_of_a == altitude_of_b;
}

但し、 FVector 型は次の通り:

// Note: 実際の UE4 の FVector 型はもっと多機能だが
//       さしあたり出題に必要最小限を定義する。
/// 3 次元の直交座標表現用のベクター型
struct FVector
{ float x = 0, y = 0, z = 0;
  float LengthSquared() const
  { return x * x + y * y + z * z; }
  FVector operator-( const FVector& t ) const
  { return FVector{ x - t.x, y - t.y, z - t.z }; }
};

Hint: IEEE754/binary32

Q4. 遅すぎた 2 の指数 `[ 1, 2, 4, 8, 16, 32, .. ]` の判定

次の実装が遅すぎて悲しみを覚えた。もっと高速に処理するためにはどのような実装を施せば良いだろうか。

/// 与えられた整数型の値が 2 の指数か判定する
/// @tparam T 整数型
/// @param in 判定対象の値
/// @return true: 与えられた整数型の値は 2 の指数である
template < typename T >
bool IsPowerOfTwo( const T in )
{
  static_assert( std::is_integral< T >::value, "" );
  return std::pow( (T)2, (T)std::log2( in ) ) == in;
}

なお、執筆時点の wandbox で簡易的に測定したところ、この実装は、 Optimization=OFF で 2,659,708 #/sec 、 Optimization=ON で 4,122,557 #/sec 程度で動作した。

Note: この記事はクイズであり、バグ探しではないのでこういう出題もある。

Q5. 正弦と余弦も速くしたい

もっと速くしたい。実用上、正弦と余弦として理論的に正しく10進数で6桁程度の精度があれば std::sin, std::cos と厳密に数値が一致しなくて構わない。どうにかならないだろうか。

/// 正弦と余弦を取得
/// @param angle_in_radians 弧度法単位の角度
/// @return ｛正弦、余弦｝
std::tuple< float, float > SinCos( const float angle_in_radians )
{
  return std::make_tuple( std::sin( angle_in_radians ), std::cos( angle_in_radians ) );
}

なお、執筆時点の wandbox で簡易的に測定したところ、この実装は、 Optimization=OFF で 2,726,719 #/sec 、 Optimization=ON で 4,148,229 #/sec 程度で動作した。

Hint: 正弦、余弦の数学的特性

Q6. ニアリーイコール、再び

次の実装にはバグが潜んでいる。どのようなバグか。

/// 弧度法単位の角度の差が許容誤差以下か判定
/// @param a angle of A in radians
/// @param b angle of B in radians
/// @param e error_tolerance; default = 1.0e-3f
/// @return true: a と b の角度の差は許容誤差以下である
bool IsNearlyEqualAngleInRadians( const float a, const float b, const float e = 1.0e-3f )
{
  return std::abs( a - b ) < e;
}

Hint: 問題が簡単過ぎて目が回ってきた。

Q7. 人間が読みやすい "数値" にしたかった

次のパワフルな実装を新人くんがしてくれた、とする。先輩であるあなたにはこのコードのマージを躊躇う理由が思い当たる。この実装ではどのような問題が起こり得るだろうか。

/// int32 型の整数値を人間が読みやすい桁区切りした文字列へ変換
/// @param in 数値
/// @return 数値を桁区切した文字列
std::string FormatIntToHumanReadable( const int32 in )
{
  auto buffer = std::to_string( in );
  std::string out;

  if ( in > 999 )
  {
    out = ',' + buffer.substr( buffer.size() - 3, 3 );
    buffer.resize( buffer.size() - 3 );
  }

  if ( in > 999999 )
  {
    out = ',' + buffer.substr( buffer.size() - 3, 3 ) + out;
    buffer.resize( buffer.size() - 3 );
  }

  out = buffer + out;

  return out;
}

実装してくれた新人くんの PC の画面を見たらこのコードの実装を試験したであろうコード片が見えた:

int main()
{
  std::cout << FormatIntToHumanReadable( 123456789 ) << "\n";
}

123,456,789

Hint: 実装が拙い、遅い、などはさておき、もっと致命的な問題が少なくとも2つ、あるいは3つは発生する可能性がある。

Q8. 整数型、再びトラブる

次の実装にはバグが潜んでいる。どのようなバグか。

/// 整数型の絶対値を強度として float 型の unorm 値へ変換
/// @tparam T 整数型
/// @param in 入力値
/// @return [ 0 .. 1 ] の強度値
template < typename T >
float GetIntensityToUNormFloat( const T in )
{
  float intensity = std::abs( in );
  return intensity / std::numeric_limits< T >::max();
}

Hint: 関数の各行に少なくとも1つ以上の問題が潜んでいる。

Q9. G.C.D.

新人くんが唸っている。助けてあげよう。

/// 最大公約数
/// @param a >= 0 の整数
/// @param b >= 0 の整数
/// @return a, b の最大公約数
template < typename T >
T GreatestCommonDivisor( T a, T b )
{
  static_assert( std::is_integral< T >::value, "" );
  check( a >= 0 )
  check( b >= 0 )
  // 整数型 `T` の2つの値 `a`, `b` の
  // 最大公約数（= "Greatest Common Divisor" ）を計算するアルゴリズムを実装したい
  // 但し、できるだけ高速に動作させたい
}

Q10. L.C.M.

また、新人くんが唸っている。助けてあげよう。

/// 最小公倍数
/// @param a >= 0 の整数
/// @param b >= 0 の整数
/// @return a, b の最小公倍数
/// @notice 結果のオーバーフローは考慮しない
template < typename T >
T LeastCommonMultiplier( T a, T b )
{
  static_assert( std::is_integral< T >::value, "" );
  check( a >= 0 )
  check( b >= 0 )
  // 整数型 `T` の2つの値 `a`, `b` の
  // 最小公倍数（= "Least Common Multiplier" ）を計算するアルゴリズムを実装したい
  // 但し、できるだけ高速に動作させたい
}

答え

CPP-QUIZ from Unreal 2017 ( part-2/2; 答え編 )

C++ ときどきごはん、わりとてぃーぶれいく☆

USAGI.NETWORKのなかのひとのブログ。主にC++。

CPP-QUIZ from Unreal 2017 ( part-1/2; 出題編 )

0. はじめに

Unreal Engine について

実行環境について

出題について

記法について

こたえについて

もくじ

1. CPP-QUIZ from Unreal

Q1. `float` 型の `[ 0.0 .. 1.0 ]` の値を `uint8` 型の `[ 0 .. 256 )` へ写像したかった

Q2. 意図しない整数のオーバーフローと問題の遮蔽

Q3. 浮動小数点数型

Q4. 遅すぎた 2 の指数 `[ 1, 2, 4, 8, 16, 32, .. ]` の判定

Q5. 正弦と余弦も速くしたい

Q6. ニアリーイコール、再び

Q7. 人間が読みやすい "数値" にしたかった

Q8. 整数型、再びトラブる

Q9. G.C.D.

Q10. L.C.M.

答え

0. はじめに

Unreal Engine について

実行環境について

出題について

記法について

こたえについて

もくじ

1. CPP-QUIZ from Unreal

Q1. float 型の [ 0.0 .. 1.0 ] の値を uint8 型の [ 0 .. 256 ) へ写像したかった

Q2. 意図しない整数のオーバーフローと問題の遮蔽

Q3. 浮動小数点数型

Q4. 遅すぎた 2 の指数 [ 1, 2, 4, 8, 16, 32, .. ] の判定

Q5. 正弦と余弦も速くしたい

Q6. ニアリーイコール、再び

Q7. 人間が読みやすい "数値" にしたかった

Q8. 整数型、再びトラブる

Q9. G.C.D.

Q10. L.C.M.

答え

Q1. `float` 型の `[ 0.0 .. 1.0 ]` の値を `uint8` 型の `[ 0 .. 256 )` へ写像したかった

Q4. 遅すぎた 2 の指数 `[ 1, 2, 4, 8, 16, 32, .. ]` の判定