2012/10/27

ビットの位置(≒2の冪指数)を静的算出するtemplateメタプログラム

ビットフラグを使用していると、
たまに「そのフラグが立てているビットの位置」を知りたいというときがあります。


結論から言って、
以下のテンプレートクラス(構造体ですが、、)を書きました。
==================================
typedef unsigned int U32;

// ビット位置の静的算出
// 値Nについて、最大のビット位置を求める
//(例:N:127→7, N:128→8
template<U32 N> struct BitPos
{
 enum {
  pos = BitPos<N/2>::pos + 1,
 };
};
template<> struct BitPos<1> { enum { pos = 0 }; };  // 終了条件1
template<> struct BitPos<0> { enum { pos = -1 }; }; // 終了条件2
==================================


これはテンプレートメタプログラミングと呼ばれる、
C++のテクニックとしては古いものです。

このテクニックを利用すると、入力値に対しコンパイル時に値が算出されるため、
実行時の演算コストがなくなります。
コンパイル時に時間的なコストがあるといえばありますが。

動作的原理については、Wikipediaに詳しく書かれています。

このテンプレートは定数posの値を、
コンパイル時の再帰呼び出しによって決定します。

たとえば以下のように使用します。
==================================
static const U32 BIT_FLG = 0x04000000; // 例えばこんな定数がある

std::cout << BitPos<BIT_FLG>::pos << std::endl;


// 結果は26となる
// 0x04000000 => 0000 0100 0000 0000 0000 0000 0000 0000

==================================
 
大まかには以上です。 

※ 終了条件2について、-1としていますが、
この辺りは人によって意見が分かれるかもしれません。
個人的には、ビットフラグに0というのはフラグとして成り立っていないと考え、
設定値として無効な値であるから-1というエラー値を設定しています。
これが正しいというには難しいため、好みにより-1でも0でも良いと思います。


〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜
以下は説明と見せかけて駄文です。
興味のある方だけお読みください。


例えば、
==================================
typedef unsigned short U16;
static const U16 BIT_FLG_A = 0x1000;
static const U16 BIT_FLG_B = 0x2000;
static const U16 BIT_FLG_C = 0x4000;
static const U16 BIT_FLG_D = 0x8000;
==================================

という定義があったとして、
ある変数について、このビットフラグを扱うとき、
【0x0000】または【0x0001】という結果を、
演算で求めたい場合があるとします。

そのとき場合のコードはこうなると思います。
==================================
// 入力値 U16 hoge = 0x2018 から0x2000を得て、
// 0x0000 or 0x0001を得る

U16 ret = 0x0000;
ret = (hoge & BIT_FLG_B) >> 13;  // ここにリテラルが発生する
==================================

この例題だと正直、素直にif文でもよいですが、
ここではそういう話はしません。

コメントに記したように、
0x0001を得るために13bit右シフトを意味するリテラルを書くわけですが、
この13というリテラルは気持ち悪いと感じる事もあるでしょう。
だからこの13に対して BIT_FLG_Bの対となる定数をまた用意したりして、
==================================
// BIT_FLG_Bでマスクした結果から 
// 0x0000 or 0x0001を得るための定数値
static const U16 FLG_B_SHIFT_NUM = 13;


// 入力値 U16 hoge = 0x2018
U16 ret = 0x0000;
ret = (hoge & BIT_FLG_B) >> FLG_B_SHIFT_NUM;  // 定数に変更
==================================

とかやってはみるものの、
非常に無駄な作業をしている気がしてならなくなってくるわけです。

もう面倒だから13でいいやとか、投げやりにもなりたくなります。

更に、データフォーマットが変わってしまって、
型がU16からU8(unsigned charとします)に変えなければならない時、

この【FLG_B_SHIFT】の型、定数値も変えてやらなければならないという事態になります。
==================================
static const U8 BIT_FLG_A = 0x10;
static const U8 BIT_FLG_B = 0x20;
static const U8 BIT_FLG_C = 0x40;
static const U8 BIT_FLG_D = 0x80;

// BIT_FLG_Bでマスクした結果から 
// 0x00 or 0x01を得るための定数値
static const U8 FLG_B_SHIFT_NUM = 5;

// 入力値 U8 hoge = 0x24
U8 ret = 0x00;
ret = (hoge & BIT_FLG_B) >> FLG_B_SHIFT_NUM;
==================================
↑こんなふうに。



ではもっと、効率的で意味を可視化できる方法がないでしょうか?


ここで、0x20と5との関係性を考えたとき、
2^5 = 32 (=0x20)であるということがあります。
これは逆に32を2で5回割れば1となるというとです。

と言うことで、
冒頭のtemplateでは、1 < Nの関係が成り立つ間、
N÷2を再帰的に繰り返せばいいじゃないという発想のもと、ビット位置を算出しています。

前述のソースに適用すると、

==================================
static const U8 BIT_FLG_A = 0x10;
static const U8 BIT_FLG_B = 0x20;
static const U8 BIT_FLG_C = 0x40;
static const U8 BIT_FLG_D = 0x80;

// 入力値 U8 hoge = 0x24
U8 ret = 0x00;
ret = (hoge & BIT_FLG_B) >> BitPos<BIT_FLG_B>::pos;
==================================
となり、BIT_FLG_xがどんな値であるかを意識する必要がなくなります。

ただし、一つ難点があるといえば、
BitPos<xxx>::posとかいってますが、一体どこのposなのか判らないということです。

例えば0x24(0010 0100)という2つのフラグがある場合、
これに対してはどこのbit位置なのか?


そこで、冒頭のテンプレートを
以下のように変更することで、より意味を明確にしました。

==================================
// ビット位置の静的算出
// 値Nについて、最大のビット位置と最小のビット位置を求める
//(例:124→most:7, least:2、 128→most:8, least:8
template<U32 N> struct BitPos
{
 enum {
  most = BitPos<N/2>::most + 1,    // 最大位置
  least = ((N & 1) == 0) ? BitPos<N / 2>::least + 1 : 0 // 最小位置
 };
};
template<> struct BitPos<1> { enum { most = 0, least = 0 }; };
template<> struct BitPos<0> { enum { most = -1, least = -1 }; };
==================================
leastはNのLSBが0である間だけbit位置をカウントします。
LSBが1になれば、つまり最初の最小のビット位置を発見したということなので、
再帰呼び出しを終了します。
また、そもそも最初の入力値Nが0というのはビットフラグとして成り立っていないため、
強制的にカウントを-1として終了します。

N=1のときは、LSBが立っていることが明らかであるため、
結果を0ビット目とします。


以上、
長々とお付き合い頂き、ありがとうございました。

ダウンロードリンクの修正について

コマンドプロンプトゲーム「CardChain」のダウンロード先について、
 ダウンロードに承認が必要な状態になっていたようなので、
 承認が不要であるよう修正しました。

ダウンロード手順は難しくはないですが、
少し迷うこともあるかと思うので記載しておきます。


 ダウンロードリンクをクリックすると、以下のようにファイル一覧が表示されます

上部メニューから、「ファイル」を選択します。

ファイルから「ダウンロード」を選択します。

以上です。
今後のダウンロード先も、同じようにしたいと思います。

また、リンク切れなどの問題や、
やこうした方がもっと良いというご意見があればお知らせください。

2012/10/13

ビット逆転アルゴリズムのテンプレート化と最適化について

ビット逆転のアルゴリズムとして、効率的なコードとして、
以下のようなものがよく見られるようです。


=================================
unsigned int v;
v = ((v & 0xaaaaaaaa) >> 1) | ((v & 0x55555555) << 1);
v = ((v & 0xcccccccc) >> 2) | ((v & 0x33333333) << 2);
v = ((v & 0xf0f0f0f0) >> 4) | ((v & 0x0f0f0f0f) << 4);
v = ((v & 0xff00ff00) >> 8) | ((v & 0x00ff00ff) << 8);
v = (v >> 16) | (v << 16);
=================================

1bit単位、2bit単位、4bit単位、8bit単位で交換し、最後に16bit単位で交換した結果、ビットの並びが上下逆となります。
簡単に8bitでトレースしてみると、、

=================================
v == 01111001
  ↓  左側 ((01111001 & 10101010) >> 1)  => 00010100
  ↓  右側 ((01111001 & 01010101) << 1)  => 10100010
  ↓  00010100 | 10100010
v == 10110110
  ↓  左側 ((10110110 & 11001100) >> 2)  => 00100001
  ↓  右側 ((10110110 & 00110011) << 2)  => 11001000
  ↓  00100001 | 11001000
v == 11101001
  ↓  左側 (11101001 >> 4)  => 00001110
  ↓  右側 (11101001 << 4)  => 10010000
  ↓  00001110 | 10010000
v == 10011110
=================================

という感じです。
書きだしてみると少し長くなりましたが、
頭で考えたほうがかえって分かりやすいアルゴリズムだと思います。
上記のアルゴリズムを見つけたときは感心しました。

因みに最初に自作したのは以下のようなものでした。

=================================
// 自作初期型
T val = 0x89ABCDEF;

const T size = sizeof(T) * 8 - 1;
T tmp = 0;
for(T i = 0; i <= size; i++) {
 tmp |= (val & (1 << size)) >> (size - i);
 val <<= 1;
}
return tmp;
=================================


常にvalのMSBを取り出し、
tmpのLSBからMSBへ順番に型のサイズ分だけ繰り返して設定する事で逆転させています。
sizeofによって可変サイズに対応できるため、template可能です。
この場合のsizeofは、通常コンパイル時には最適化によって定数へと置き換えられ、
例えばunsigned short(以下 U16)の時、実質的なコードは、

=================================
// コンパイラ最適化後イメージ
U16 val = 0xABCD;
// const T size = sizeof(T) * 8 - 1; <=削除される
U16 tmp = 0;
for(U16 i = 0; i <= 15; i++) {
 tmp |= (val & 0x8000) >> (15 - i);
 val <<= 1;
}
return tmp;
=================================

と、言った感じになります。


しかしながら、
汎用的ではあるものの、冒頭のアルゴリズムを目にして、
うがががが(;´Д`)。。
となったため、
なんとか冒頭のアルゴリズムをtemplateに適用したいと考えました。

・・・
で、出来たのは以下のコード。

=================================
template<typename t> static T reverseBits(T v) {
 assert(sizeof T <= 4);
 switch(sizeof T) {
  case 4: v = (v >> 16) | (v << 16);
  case 2: v = ((v & 0xff00ff00) >> 8) | ((v & 0x00ff00ff) << 8);
  case 1: v = ((v & 0xf0f0f0f0) >> 4) | ((v & 0x0f0f0f0f) << 4);
   v = ((v & 0xcccccccc) >> 2) | ((v & 0x33333333) << 2);
   v = ((v & 0xaaaaaaaa) >> 1) | ((v & 0x55555555) << 1);
 }
 return v;
}
=================================


switch文が入りました。

冒頭のアルゴリズムの特性として、
各行の交換式は干渉していないということが挙げられます。
なので、順番がどうであれ、最後には交換が出来るはずです。

ということなので、

交換順を逆に定義した上で、
switch文を全て通り抜けるようにしてやることで、必要な分だけ演算を実施させます。


が、このswitch文は入っているように見えるだけで、実際には入らないです。

これは関数テンプレートであり、渡される型はコンパイル時には決まっており、
また、switchの対象が型サイズであるために、これもコンパイル時に解決され、
つまり最初からジャンプ先が決定しているのでswitchする必要がなく、
コンパイラの最適化により、型サイズによって直接的に必要な交換式のみを実行するコードが生成されます。

また、別の問題として考えられるのは、
上記の交換式はすべて32bitのリテラルが組み込まれていることです。
『v = ((v & 0xaaaaaaaa) >> 1) | ((v & 0x55555555) << 1);』
これはキャストが発生するのでは?と懸念が出なくもないですが、
これもよほど頭の悪いコンパイラでない限り、outする型に合わせたコードを生成します。
それに、心配であれば以下のようにしてしまえば確実です。
『v = ((v & static_cast<T>(0xaaaaaaaa)) >> 1) | ((v & static_cast<T>(0x55555555)) << 1);』
これも結局コンパイル時に型が決定するので正しいリテラルになりますね。

というわけで、
仮に各サイズでこの関数テンプレートが実体化された時の最適化後のコードのイメージは、以下のようになります。

=================================
【v == 32bit】
U32 reverseBits(U32 v) {
 v = (v >> 16) | (v << 16);
 v = ((v & 0xff00ff00) >> 8) | ((v & 0x00ff00ff) << 8);
 v = ((v & 0xf0f0f0f0) >> 4) | ((v & 0x0f0f0f0f) << 4);
 v = ((v & 0xcccccccc) >> 2) | ((v & 0x33333333) << 2);
 v = ((v & 0xaaaaaaaa) >> 1) | ((v & 0x55555555) << 1);
 return v;
}
【v == 16bit】
U16 reverseBits(U16 v) {
 v = ((v & 0xff00) >> 8) | ((v & 0x00ff) << 8);
 v = ((v & 0xf0f0) >> 4) | ((v & 0x0f0f) << 4);
 v = ((v & 0xcccc) >> 2) | ((v & 0x3333) << 2);
 v = ((v & 0xaaaa) >> 1) | ((v & 0x5555) << 1);
 return v;
}
【v == 8bit】
U8 reverseBits(U8 v) {
 v = ((v & 0xf0) >> 4) | ((v & 0x0f) << 4);
 v = ((v & 0xcc) >> 2) | ((v & 0x33) << 2);
 v = ((v & 0xaa) >> 1) | ((v & 0x55) << 1);
 return v;
}
=================================


2012/10/13 細かな加筆修正(内容は変更なし)

2012/10/06

コマンドプロンプトゲーム - Card Chain

暇を持て余しているときにコマンドプロンプトでゲーム作りました。
 (一応完結しているが、完全な実装ではないのでver.0.8.0)

実行ファイルとソースのセットです。

なお、ソースはVC++ 2010 Expressのプロジェクト付きです。


■ カードチェイン
▽ Download ▽
https://docs.google.com/file/d/0Bz1zlwZ1RkLWR3FvdVROZFZoaXc/edit

■ 作成環境
 ・Mac(Parallels上にインストールしたWindows XP)
 ・VC++ 2010 Express
 ・Win32 API

■ 動作確認環境
 ・Windows XP、Windows 7
 ・Mac(Parallels上にインストールしたWindows XP, Windows 8)

■ 説明
  1.概要
  ・1人用のカードゲーム
  ・「WhatIf?」だとか、後継の「COOL 104」とルールはほぼ同じ
  ・同じ数字か同じ柄のカードを、出来るだけ多く選択します。
  ・ただし、役によるボーナスなどはありません
  ・52枚の全てのカードを出しきればクリア
  ・10枚以上続けることができて、初めて得点

 2.操作方法
  ・ESCキーでゲームを終了します
  ・左右キーでカードを選びます
  ・ ENTER、Z、スペースのいずれかでカードを決定します

■ ライセンス
 「source」フォルダ内の「lib」フォルダ内のファイルを除き、
 その他の全てのソースファイルは、改変・再配布自由です。

 ただし、 このプログラムは乱数生成にメルセンヌ・ツイスタを使用しています。
 ソースファイルに含まれる「lib」フォルダに含まれているものがそれです。
 この部分に関して、ライセンスは以下のページをご参照ください。
 Mersenne Twister
 
 このゲームではメルセンヌ・ツイスタの関数宣言・定義の一部を改変しています。
 ご使用をお考えの場合は、上記のページにてオリジナルを入手しご使用下さい。

■ 免責
 作者は、このプログラムを使用して起きた不都合・不利益について、
 一切の責任を負いません。ご容赦ください。

■ 連絡事項
 面白そうなご意見や、ダメ出しや、質問等などあれば、
 下記コメント欄やメールなど、状況に応じた方法でご連絡ください。

■ ソースに関して ひとこと
 ・new とかdeleteとか一切不使用なのはそういう作りです。念のため。

このブログについて

暇をみつけて作ったゲームとかを公開。
偶にソース付き。

というか使い方がよくわからない。