見切り発車

とりあえずかきとめたい

CRC32 のテーブルを利用した最適化のメモ

解決したこと

CRC32 を計算するプログラムをテーブルを利用して最適化する場合の個人的な引っ掛かりポイントについて再確認しました。

  • 元々の手順とテーブル利用の関連付け
  • データテーブルの計算方法

環境

解決方法?

CRC32 そのものについての説明はこちらのスライド を参考にしました。

まずはスライドの説明に沿って実際にビット演算を手計算しました。

例えば入力データが文字'a' の場合

  • 'a' = 0x61 = 01100001 =[ビット順序反転]=> 10000110
  • 後ろに0 を32 bit 付加して1000011000000000000000000000000000000000
  • 先頭32 bit を反転して0111100111111111111111111111111100000000
  • 多項式は100000100110000010001110110110111
  • シフトとxor の繰り返し
input     :0111100111111111111111111111111100000000
polynomial: 100000100110000010001110110110111
xor result:0011100011001111101110001001001011000000
polynomial:  100000100110000010001110110110111
xor result:0001100001010111100110110010010000100000
polynomial:   100000100110000010001110110110111
xor result:0000100000011011100010101111111101010000
polynomial:    100000100110000010001110110110111
xor result:0000000000111101100000100001001011101000
入力データのMSB が32 bit より下位になったので終了しビットを反転
xor result:--------00111101100000100001001011101000
        =>:--------11000010011111011110110100010111
  • 結果のビット順序を反転した値の16 進数は0xe8b7be43
  • python のcrc32 と同じ結果になることを確認する

ひっかかりポイント

CRC32 の説明などでしばしば「ビット順序の反転」が出てきますが、ここがよく理解できていなかったのがポイントでした。

C++ で任意の長さのデータを取り扱う場合は主に1 byte の基本型であるchar やuint8_t の配列として取り扱います。例えば入力データが"abcd" という長さ4 の文字列の場合、これをC++ 的に素直に表現すると

'a', 'b', 'c', 'd' = 0x61, 0x62, 0x63, 0x64 => 0110 0001 0110 0010 0110 0011 0110 0100

となります。これは、1 byte ごとに2 進数にして並べたものです。

ここで1 byte 中のビットの順序について考えてみます。'a' でいうと上位←0110 0001→下位 ですが、上位ビットと下位ビットはどちらが先なのか? というとリトルエンディアンでは下位ビットが先、ビッグエンディアンでは上位ビットが先、となります。これについては構造体のビットフィールドで確認することができます。

struct Data {
    union {
        uint8_t bit : 1;
        uint8_t value;
    };
};
Data d;
std::memset(&d, 0, sizeof(Data));
d.bit = 1;

とした場合、d.value の値はリトルエンディアンだと0x01, ビッグエンディアンだと0x80 となります。

これを踏まえて改めて入力データ"abcd" をビットの入力順に2 進数表現する場合、リトルエンディアンであれば各1 byte については下位ビットから並べることになります。

'a', 'b', 'c', 'd' = 0x61, 0x62, 0x63, 0x64 => 1000 0110 0100 0110 1100 0110 0010 0110

C++ プログラム中で入力データのbyte 配列に手を加えなくても、modulo 2 の計算に対する入力としてビット列の先頭を最上位ビットとして扱うことで、ビット順序が反転したように見えます。実際にはプログラム・メモリ上の上位ビット方向とmodulo 2 計算上の上位ビット方向が逆であるということです。

プログラム実装時に使用する最上位ビットを省略した多項式は00000100110000010001110110110111 ですが、このときの上位ビット方向はmodulo 2 計算上のものであり、C++ プログラム上でのバイト列としての表現は0010 0000 1000 0011 1011 1000 1110 1101 => 0x20, 0x83, 0xb8, 0xed となります。リトルエンディアンでの32 bit 値とする場合には先に来るバイトが下位になるので0xedb88320 です。

以上の、プログラム・メモリ上のビット順序とmodulo 2 計算時のビット順序の対応 について理解することで計算処理の各操作が何をしているのかもよくわかるようになりました。

データテーブルの計算方法

CRC32 計算の最適化用に作成するデータテーブルの内容は、8 bit のパターンごとに後続の32 bit に適用される多項式のxor を先に計算しておいたものです。modulo 2 で上位から下位に向けて1 のビットを見つけてxor を行う操作で、プログラム上では逆に下位ビットから処理することになります。

uint32_t table[256];
// x^32 を省略した多項式
const uint32_t polynomial = 0xedb88320;
// テーブル各要素を計算
for (uint32_t i = 0; i < 256; ++i) {
    // xor 初期値
    uint32_t xor = 0;
    // 入力データ
    uint32_t input = i;
    // 8 bit を処理
    for (uint32_t j = 0; j < 8; ++j) {
        // ビットがたっていたら
        if (input & (1 << j)) {
            // 入力データにxor 適用
            // ビットがたっているのは多項式のx^32 に対応する位置
            // xor をとるのはその次からなのでi + 1 でシフトする
            input ^= (polynomial << (i + 1));
            // 後続データに対してのxor
            // i = 0 の時には後続32 bit の先頭から見て
            // polynomial はmodulo 2 の計算上で7 bit 上位になる
            // プログラム上では下位に7 bit はみ出していることになる
            xor ^= (polynomial >> (7 - i));
        }
    }
    // 結果をテーブルに収める
    table[i] = xor;
}

その他

github にコードをコミットしました。

Visual C++ でのweak symbol

解決したこと

他のコンパイラでは __attribute__((weak)) などと指定するweak symbol をVisual C++ で使用する方法について調べました。

環境

解決方法

weak symbol はリンク時に他に同じ名前のシンボルが見つからなければリンクされるシンボルです。

通常はリンク時に同じ名前のシンボルが複数ある場合にはエラーとなります。

Visual C++ の場合、 /alternatename:a=b というリンカオプションを使用して、a というシンボルの定義が見つからない場合には b というシンボルをリンクするという方法で同様のことができます。

msvc waek symbol で1年以内に更新された条件でググったら出てきた What does the /ALTERNATENAME linker switch do? を参考にしました。

サンプルコード

/*
 * C リンケージで宣言
 */
/// 呼び出す関数名
extern "C" int func();
/// デフォルト実装
extern "C" int _default_func();
/*
 * リンカーへの指定
 */
#if defined(_M_IX86)
// x86 は_ が付加される
#pragma comment(linker, "/alternatename:_func=__default_func")
#elif defined(_M_IA64) || defined(_M_AMD64)
// x64 は そのままの名前
#pragma comment(linker, "/alternatename:func=_default_func")
#endif

/*
 * C++ リンケージで宣言
 */
/// 呼び出す関数名
extern int func2();
/// デフォルト実装
extern int _default_func2();

// Visual Studio 2019 では以下の指定でリンクできた
// リンクエラーの時に出力されたエラーメッセージを参考に指定
#if defined(_M_IX86)
#pragma comment(linker, "/alternatename:?func2@@YAHXZ=?_default_func2@@YAHXZ")
#elif defined(_M_IA64) || defined(_M_AMD64)
#pragma comment(linker, "/alternatename:?func2@@YAHXZ=?_default_func2@@YAHXZ")
#endif

// 1:デフォルト実装が呼び出される
// 0:独自実装が呼び出される
#define USE_DEFAULT 1

/// メイン関数
int main()
{
    return func() + func2();
}

#if !USE_DEFAULT
/// C リンケージの独自実装
int func() {
    return 0;
}
/// C++ リンケージの独自実装
int func2() {
    return 0;
}
#endif

/// C リンケージのデフォルト実装
int _default_func() {
    return 1;
}
/// C++ リンケージのデフォルト実装
int _default_func2() {
    return 2;
}

/alternatename に指定するのはリンク時のシンボル名なのでソースコード中の関数名そのままではなく、 x86 のC リンケージの場合は名前の前に_ が付加され、C++ リンケージの場合は名前マングリングが適用されています。

その他

github にサンプルをコミットしました。

CMake でWindows SDK バージョンを指定する方法

解決したこと

CMake で生成したvcxproj のWindows SDK バージョンが10.0.18362.0 になっていたのを10.0.19041.0 になるようにしました。

環境

解決方法

CMAKE_SYSTEM_VERSION のページに説明がありますが、新規のビルドツリーを作成するときに指定することができます。 out-of-source ビルド の場合にはコマンドプロンプトから

> mkdir build
> cd build
> cmake .. -G"Visual Studio 16 2019" -DCMAKE_SYSTEM_VERSION="10.0.19041.0"

と実行することで生成されるvcxproj のWindows SDK バージョンが指定の値になります。

-G"Visual Studio 16 2019" は生成するプロジェクトファイルの対象を指定しています。複数のバージョンのVisual Studio がインストールされている場合に指定します。

CMAKE_SYSTEM_VERSION の指定はコマンドライン上で行う必要があります。CMakeLists.txt でset で指定しても反映されません。

すでにcmake を実行してビルドツリーが作成済みの場合、一度build ディレクトリ内をすべて削除してから実行しなおす必要があります。

その他

インストールされているWindows SDK の中にホスト環境と一致するものがない場合、インストールされている中で一番新しいバージョンが選択されるようです。

参考リンク

C++ のダウンキャストについて考える

今どきのゲーム開発環境を実現しようとするとどうしてもC++ でダウンキャストが必要になってきます。

C++ でダウンキャストを行うにはdynamic_cast を使用するのが通常の手段ですがなかなか重い処理なのでゲームではあまり使いたくない選択肢です。

static_cast でもダウンキャストが可能です。例えばclass B がclass A を継承している場合A からB へのstatic_cast でダウンキャストが可能です。

class A {};
class B : public A {};
class C;
B b;
A * a = &b;
B * pb = static_cast<B *>(a); // OK. 継承関係がある
C * pc = static_cast<C *>(a); // NG. 継承関係がない

dynamic_cast とstatic_cast の違いは、dynamic_cast では実行時型情報を利用してダウンキャストの正当性をチェックするところです。

class A { public: virtual ~A() = default; }
class B : public A{};
class C : public A{};
B b;
A * a = &b;
B * pb = dynamic_cast<B *>(a); // 正しくキャストされる
C * pc = dynamic_cast<C *>(a); // nullptr を返す

pb = static_cast<B *>(a); // 正しくキャストされる
pc = static_cast<C *>(a); // 不正なポインタとなる

dynamic_cast ほどの汎用性は不要という条件であれば、独自に継承関係を解決してやればstatic_cast でそれなりに安全なキャストが可能です。
例えばstatic_cast ではvirtual 継承を使用している場合にはダウンキャストはできませんがそういう使い方はしない、など。
(virtual 継承でなくてもダイヤモンド継承してたらキャストはうまくいかないのでした。)

必要な機能は

  • クラスに静的変数として型の識別子を持たせる
  • インスタンスに型の識別子を持たせる
  • 型の識別子を比較してキャストの正当性を判定する

といったところでしょうか。

これらを実装するときにC++ の機能だけだとわりと定型的な処理を各クラスごとに記述する場面にぶつかります(と予想します)。
こういうのを毎回手書きするのは面倒&エラーのもとになるのでこの辺りの解決策がポイントになりそうです。
解決策は考え中。

Return of WPF

Cinder+ImGui をすこーし触った結果、どうにも日本語の取り扱いが不自由な感じで普通のツールを作るのにはちょっとばかり向いてないかなーという結論に至ってしまいました。

というわけで改めてWPF の復習をすることに。

ツールを作るときにフォームを使いそうになるのをこらえてWPF プロジェクトを作成するなどしております。

実践あるのみ。

Cinder-ImGui

ImGui による開発環境としてcinder をインストールしてプロジェクトを作成してみときに引っかかったところの話です。


cinder (https://libcinder.org/) はhttps://github.com/cinder/Cinder からチェックアウト可能です。

boost を利用しててgit clone するときに--recursive をつけ忘れるとビルドが通らないので要注意です。


また、imgui を利用するためには Cinder/blocks ディレクトリに https://github.com/simongeilfus/Cinder-ImGui をgit clone しておきます。


さてプロジェクトを新規作成する方法ですがCinder/tools にあるTinderBox というツールを使います。

これもgit clone するときに忘れないように—recursive をつけておかないと落ちてきません。

こういうネーミングは好きなんですけども少し分かりやすいところにチュートリアルとかgetting started とかいうのがあるといいなあって思いました。

WPF vs ImGui

去年はせっかく頑張ってWPF に取り組んでたんだけど後半くらいから時間も取れない仕事に活かせるアテもなくなったということですっかり滞ってしまいました。


ツールを作る機会は常にあるので少しずつでも進めていきたいのだけども開発の傍らで内製ツールを作るのにWPF の学習がやや重いかなーと思わなくもない気がしてきたのも捗らなかった要因のひとつです。


代わりに浮上してきたのがImGui でイミディエイト方式ってのはUnity のエディタ拡張と考え方は同じですね。


この方式の良いところは分かりやすさもあるんだけれどもWPF を使いたい理由のひとつであるデータとUI の整合性を取るというのが自明であるというのが一番大きいと思います。


逆に弱そうなところはレイアウトと処理不可。レイアウトは未知数ですけども。

処理不可は正直目をつぶっても良いかなーと思います。どうせゲームを動かす前提のスペックだしモバイルでバッテリーを気にする局面もまず無いはず。


というわけでぼちぼち進めたいと思います。