コンパイル時のCRC32行の計算

プログラミングの性質上、コードの非最適性と冗長性は本当に嫌いです。 そのため、職場のプロジェクトのソースコードをもう一度読んで、製品ラインをさまざまな言語に翻訳する方法の1つの機能に再び出会いました。



ここでのローカライズは非常に簡単です。 翻訳が必要なすべての行は、 _TR()



マクロでラップされます。

 wprintf(L"%s\n", _TR("Some translating string"));
      
      





マクロは、使用されている現在の言語に応じて、テキストの目的のバージョンを返します。 次のように定義されます。

 #define _TR(x) g_Translator.Translate(x)
      
      





ここでは、グローバルオブジェクトg_Translator



。このオブジェクトは、 Translate()



関数で、ランタイムの指定された文字列からcrc32を考慮し、xmlデータベースで同じチェックサムを持つ翻訳を検索して返します。



私はこの決定がどの程度正当であるかを判断しませんが、それは時間によってテストされており、非常に信頼できることが証明されています。 そして、すべてがうまくいきますが、そのような解決策には欠点があります:実際、関数は余分な仕事をします-チェックサムはコンパイル段階で一度カウントされ、将来、既製の数値が使用される可能性があります。 また、実行可能なイメージに重複した行を保存する必要もなくなります。これは、それらが既に翻訳済みの外部xmlファイルにあるためです。



「compile-time crc32」という要求に少しグーグルで答えてみたところ、このタスクが最も些細な作業ではないことがすぐにわかりましたが、既成のソリューションは見つかりませんでした。



残念ながら、純粋な形式でテンプレートメタプログラミングを使用しても機能しません。 テンプレートパラメータとして使用される文字列の文字への参照は、コンパイラがテンプレート関数の再帰呼び出しを折り畳むことを防ぎます。 たとえば、 この記事ではcrc32計算用のテーブルの作成についてのみ説明します。 そして、完全に標準に準拠したソリューションから、 Boost.MPLのみが見つかりました。 次の入力フォームを使用することをお勧めします。

 meta::hash_cstring< mpl::string<'bunn','ies'> >::value;
      
      





文字列リテラルを使用する代わりに、文字列を断片に分割し、個別のテンプレートパラメータで指定することをお勧めします。 しかし、使用される録音の癖に加えて、プロジェクトの2450行すべてをこの形式に変換するには、外部コードジェネレーターを作成し、プロジェクトチーム全体に新しい録音形式を教える必要があります。

メッセージは、新しいC ++ 11ではこのアイデアがクラシックテンプレートメタプログラミングとconstexpr



を使用して実装されるというフォーラムをすり抜けましたが、残念ながら、プロジェクトを長い血統から新しい標準に移行することはできません。



コードジェネレーターを使用する別のアイデアがありました。 ビルド前のイベントを作成して、翻訳された文字列をこの形式に変換することができます。

 _TR(0x12345678/*"Some hashing string"*/);
      
      





しかし、再び、私は普遍的な何かが欲しかった...不必要なジェスチャーなしできれいなcrc32を単に残すような魔法の_TR()



が欲しかった。 それから、自転車の再発明を始めました。



試行番号1。 きれいなマクロ



この段階で、頭の中で暖かくなったのは1つの考えだけです。テンプレートは別として、マクロはコンパイル前に計算されます。使用する必要があります。



Visual Studioで新しいプロジェクトを作成し、最適化設定を最大インラインおよび最大速度に設定しました。 よく知られているユーザーモードデバッガーOllyDbgで、ハッシュへの行の折りたたみの成功/失敗を分析することにしました 。そのため、結果のexeで、不要なゴミなしにコードとデータごとに1つの小さなセクションだけを見たいと思います。 これを行うには、Cランタイムをオフにしました。これにより、他の複数のレシーバーと組み合わせて、サイズが2 KBだけの空のexeを取得できました。



いくつかの実験の後、3文字以下の文字列に対してcrc32計算の最も単純な実装を作成しました。

 static const unsigned int Crc32Table[256] = { 0x00000000, 0x77073096, 0xEE0E612C, 0x990951BA, 0x076DC419, 0x706AF48F, 0xE963A535, 0x9E6495A3, 0x0EDB8832, 0x79DCB8A4, 0xE0D5E91E, 0x97D2D988, /* ... ,*/ 0xB40BBE37, 0xC30C8EA1, 0x5A05DF1B, 0x2D02EF8D }; template <typename T, int N> char (&array_length(T (&)[N]))[N]; //       #define lengthof(x) (sizeof(array_length(x))) //    crc32 #define TR_CRC(crc,i,s) (crc >> 8)^Crc32Table[(crc^s[i])&0xFF] //            #define TR_CRC_COND(crc,i,s) (i<lengthof(s)-1 ? TR_CRC(crc,i,s):crc) //   CRC     ( 3 ) #define _TR(s) TR_CRC_COND(TR_CRC_COND(TR_CRC_COND(TR_CRC_COND(0xFFFFFFFF,0,s),1,s),2,s),3,s)^0xFFFFFFFF int main(int argc, char *argv[]) { //     ,    - DWORD, //             Olly Sleep(_TR("123")); }
      
      





マクロの実装における主な問題は、テンプレートのメタプログラミングのように、行の長さに沿って必要な反復回数までcrc計算サイクルを展開できないことです。 マクロは常に、最初と同じ数の反復を再カウントします。 たとえば、上記の例では、文字列「1」は、長さが1文字しかないにもかかわらず、4回の反復(最大3文字+ '\ 0')で計算されます。 これは、文字列が既に最後の文字まで計算されている場合、前の反復からcrc値を取得する条件付き操作によってバイパスされます。



結果のexeをデバッガで実行すると、大切なPUSH 884863D2



。その正しい計算は、 最初の crc32オンライン計算機で簡単に確認できました。







行の長さでマクロを複製すると、コンパイルの速度がどれだけ低下するかがわかります。これにより、プロジェクトの要件をカバーできます。 翻訳データベースの一番長い行は350文字より少し短いので、少なくとも500文字の制限に合わせたいと思いました。



したがって、短縮形で次のようなマクロ本体を生成しました。

 #define _TR(s) TR_CRC_COND(TR_CRC_COND(/*...*/TR_CRC_COND(TR_CRC_COND(0xFFFFFFFF,0,s),1,s),2,s),3,s)/*...*/,448,s),449,s)^0xFFFFFFFF
      
      





しかし、コンパイラがそのコールドを発行したとき、ここで私は失望しました: 「致命的なエラーC1009:コンパイラの制限:マクロのネストが深すぎます」 。 経験的には、ネストの制限が300の範囲内にあることがわかりました。



試行番号2。 __Forceinline関数



その後、ネストされたマクロの代わりにインライン関数を使用しようとする試みがいくつかありましたが、最終的にはすべてが同様のエラー(正確には覚えていませんが、コンパイラーがあまりにも複雑な文法を呪った)または過度に長いコンパイルになりました。



すべての苦痛の後、私はこのアイデアをほぼ放棄する準備ができていましたが、一連の逐次計算と文字列長チェックを使用して、1つの大きな__forceinline関数を書くことを試みることにしました

 //  ,       #define CRC_STUB_(i) if (i<N-1) { crc = (crc>>8) ^ Crc32Table[(crc^s[i])&0xFF] } template <int N> static __forceinline DWORD CRC_ARR_CALC_(const char (&s)[N]) { static const unsigned int Crc32Table[256] = { 0x00000000, 0x77073096, 0xEE0E612C, 0x990951BA, 0x076DC419, 0x706AF48F, 0xE963A535, 0x9E6495A3, 0x0EDB8832, 0x79DCB8A4, 0xE0D5E91E, 0x97D2D988, /* ... ,*/ 0xB40BBE37, 0xC30C8EA1, 0x5A05DF1B, 0x2D02EF8D }; DWORD crc = 0; CRC_STUB_(0);CRC_STUB_(1);CRC_STUB_(2);CRC_STUB_(3);CRC_STUB_(4);CRC_STUB_(5);CRC_STUB_(6);CRC_STUB_(7);CRC_STUB_(8);CRC_STUB_(9);CRC_STUB_(10);CRC_STUB_(11);CRC_STUB_(12);CRC_STUB_(13);CRC_STUB_(14);CRC_STUB_(15);CRC_STUB_(16);CRC_STUB_(17); /* ... */ CRC_STUB_(498);CRC_STUB_(499); return crc; }
      
      





そしてうまくいきました! コンパイラーは、すべてのコードをすぐに1つの数値にCrc32Table



、結果のバイナリに行自体もCrc32Table



テーブルも残しませんでした。 このような実装を正しくコンパイルするには、/ O2スイッチだけで十分です。 残っていたのは、パラメーターとしてg_Translator.Translate()



を使用してg_Translator.Translate()



メソッドのオーバーロードバージョンを追加することだけで、そのポイントは帽子にあります。



コードをプロジェクトに導入した後、リリースビルドのコンパイルは1〜2分長くなりましたが、バイナリは200 Kbだけ簡単になり、ユーザーに不要な作業を強いることなく、ラップトップがバッテリーで少し長く動作するようになりました:)



テストプロジェクトの完全なソースコードは、 7ztar.gzで入手できます。



All Articles