不可解計画

« 2010年03月 | メイン | 2010年05月 »

2010年04月25日

昨日の続き

　さて、本題に入るとしよう。テンプレートを使用したメタプログラミングでエンディアンを操作するやつだ。

　使い方から先に書くと、以下のような感じになる。

int n = LittleEndian::ConvertTo<BigEndian>( 0x12345678 );

　このことからわかるのは、クラス LittleEndian にクラススコープのメンバ関数テンプレートがあり、テンプレート引数に BigEndian を渡してエンディアン変換をしているということだ。実際には、LittleEndian および BigEndian は typedef であり、以下のように定義されている。

typedef Endian<__LITTLE_ENDIAN> LittleEndian;
typedef Endian<__BIG_ENDIAN>    BigEndian;

　つまり、Endian というクラステンプレートがあり、その内部にメンバ関数テンプレートとして ConvertTo() があるわけだ。で、この __LITTLE_ENDIAN と __BIG_ENDIAN とはなにか。これは、endian.h にある数値で、バイトオーダーを表現している。

#define __BIG_ENDIAN    4321
#define __LITTLE_ENDIAN 1234

　ちなみに、endian.h ではマシンのバイトオーダーを __BYTE_ORDER として定義しているので、以下の定義によりマシンのエンディアンを取得できる。

typedef Endian<__BYTE_ORDER> MachineEndian;

　ここまでで、Endian クラステンプレートの定義が見えてくる。以下のような感じだ。

template<int BYTEORDER>
struct Endian {
  static const int byte_order = BYTEORDER;
  template<typename ENDIAN>
  static inline int ConvertTo( int n );
};

　static const int byte_order がここでのキモだ。これをコンパイラが定数として扱うことで、コンパイル時点でできる計算をかなり増やすことができる。

　ここで少し脱線すると、こいつは little endian と big endian だけでなく、他のバイトオーダーも扱うことができる。例えば以下のように。

typedef Endian<3412> PDPEndian;

　で、問題はメンバ関数テンプレートである ConvertTo の実装だ。これは、以下のようになる。

template<int BYTEORDER>
template<typename ENDIAN>
inline int Endian<BYTEORDER>::ConvertTo( int n ) {
  return __ConvertEndian( n, Endian<BYTEORDER>(), ENDIAN() );
};

　これは、変換元と変換先の Endian クラスをタグディスパッチに使うことで、__ConvertEndian() の関数オーバーロードを使用して処理を振り分けている。このオーバーロードによって LittleEndian、BigEndian、それ以外の相互変換を個別に実装しているのだ。最初はメンバ関数テンプレート ConvertTo() 自体を特殊化しまくって対処しようと考えていたのだが、いかんせんメンバ関数自体のパラメータは int だけなので断念したような次第。

　例えば、little to big の変換では、以下のような __ConvertEndian() になる。これは一番素直な変換だ。

inline int __ConvertEndian( int val, LittleEndian, BigEndian ) {
  return ( ( val & 0xFF000000 ) >> 24 ) |
         ( ( val & 0x00FF0000 ) >>  8 ) |
         ( ( val & 0x0000FF00 ) <<  8 ) |
         ( ( val & 0x000000FF ) << 24 );
};

　ちなみに、変換元と変換先のバイトオーダーが等しい場合、なにもしないようにオーバーロードされている。だから例えば、MachineEndian が LittleEndian に等しいことに気付いていなくても、以下のコールは安全だ。

int n = MachineEndian::ConvertTo<LittleEndian>( 0x12345678 );

　そして、もうひとつだけ例をあげておこう。little endian から little でも big でもないエンディアンに変換する場合のオーバーロードだ。

template<typename TO>
inline int __ConvertEndian( int val, LittleEndian, TO ) {
  union { int val; char ch[4]; } wk;
  wk.ch[3] = ((char*)&val)[( TO::byte_order      %10)-1];
  wk.ch[2] = ((char*)&val)[((TO::byte_order/  10)%10)-1];
  wk.ch[1] = ((char*)&val)[((TO::byte_order/ 100)%10)-1];
  wk.ch[0] = ((char*)&val)[((TO::byte_order/1000)%10)-1];
  return wk.val;
};

　なんだか複雑そうに見えるが、重要なのは変換対象である val 以外は全て定数ということだ。つまり、これは計算のほとんどをコンパイル時点でやってしまえる。昨日試した限りでは、配列解釈による転置よりもビットシフトで実装する方が速いが、このような変換でも同じように実装することが可能だろう。

　ひとまずこんなところだが、冷静に考えるとまだまだ改善の余地があるような気がしてくる。全てをビットシフトでなんとかでき、計算の多くをコンパイル時点にやってしまえるなら、ConvertTo からタグディスパッチを使って __ConvertEndian のたくさんのオーバーロードの中から処理を選ぶ必要などないのかもしれない。そこのところを上手く書くことができれば、同じ効率でも実装はもっと短くなる。

投稿者 kagelow : 18:00 | コメント (4)

2010年04月24日

アセンブラまで降りるとわからない

　なぜだか、エンディアンを操作する処理をクラステンプレートを使用したメタプログラミングでやる、というのを楽しんでいる。が、その話は後だ。読んで楽しいと思う人が少ないだろうからだ。それよりも、自分が悩んでいることを先に書いて助けを請うことにしよう。

　何で悩んでいるかというと、エンディアンを little ─ big 間で相互に変換する際の処理で一番早いのがどれか、自分では判断がつかないのだ。候補として扱う条件は、分岐やループなど、遅くなる要因がないことや、可能な限り局所変数の数や演算の量が少ないこと。扱うのは 32 ビット変数のみと（ひとまずは）しておく。最初は std::reverse() で片付けようかと思ったが、ループやスワップが多いので論外。で、ひとまずイケそうなのは以下の２つと考えた。無論、int が 32 ビット幅だという前提はあるものとする。

int endian_invert( int n ) {
    return ( ( n & 0xFF000000 ) >> 24 ) |
           ( ( n & 0x00FF0000 ) >>  8 ) |
           ( ( n & 0x0000FF00 ) <<  8 ) |
           ( ( n & 0x000000FF ) << 24 );
};

int endian_invert( int n ) {
    union { int val; char ch[4]; } wk;
    wk.ch[3] = ((char*)&n)[0];
    wk.ch[2] = ((char*)&n)[1];
    wk.ch[1] = ((char*)&n)[2];
    wk.ch[0] = ((char*)&n)[3];
    return wk.val;
};

　正直言って、どちらが速いのか自分にはわからない。アセンブルリストを出してみた限りでは、後者の方が短いようだ。自分の無根拠な直観も、後者の方が速いのかな‥‥‥と思ってはいる。しかし、アセンブルリスト上で１行でも、命令によって実際に実行するのにかかる処理コストは異なるという話を聞いたことがある。しかし、そもそも自分はアセンブラを読めない、で困っているというわけだ。こういうときの判断のためのガイドラインとか知っている方、教えて下さい。

投稿者 kagelow : 20:30 | コメント (3)

2010年04月20日

昼間の仕事世界に復帰

　昨日から、ようやく昼間の仕事の世界に復帰。仕事内容とかはともかく、生活時間帯のズレを修正するのが大変だ。仕事をしていても、なんだか時差ボケのような状態になっている。これまでは５時とかに寝て１４時とかに起きてたのが、今週からは６時半起きの生活。これがまずツラい。

　あと、毎日昼飯を外で食べるのは財布に優しくない。そりゃ仕事についたんだから仕方ないが、この仕事のお金が入るのは５月の末。それまで毎日昼メシ外でか。弁当買ったって500円。正直厳しいが、この出費を厳しいと認識するほど逼迫してる自分の立ち位置そのものが厳しい。いろんな意味で危機だ。

投稿者 kagelow : 23:30 | コメント (0)

2010年04月10日

Aceeca の Garnet OS 新デバイスについて

　PalmInfoCenter が、ニュージーランドのメーカー Aceeca が 4/10 に発売する Garnet OS の新デバイスについて報じている。PalmFan.com 経由で知った。

　「なんでPalmやねん」の MA-CY さんは、『ちょっとごついですね』 と書かれている。気になったので、Acceca 新デバイスのスペック表と Palm TX の（適当な）実寸を比べてみた。

　まず、重さは 196g で、Palm TX は 150g。Aceeca の方がちょっと重いようだ。次に、デバイスのボディサイズだが、Aceeca は 128 x 76 x 25 mm で、Palm TX は 120 x 75 x 13 mm 程度。TX よりも縦に少し長く、幅はほとんど同じ。厚みが２倍近くあるのが気になるところだ。ついでに書いておくと、Aceeca のは 5-Way Rocker 搭載だが、アプリケーションボタンは２つしかないようだ。そして、WiFi および Bluetooth はオプションである、とされている。

　おそらく、MA-CY さんでなくとも 「ちょっとゴツいな」 と思ったはずだが、それはディプレイに対して筐体が大きく見えるからだ。しかし、厚みを除けば実は Palm TX とほぼ同じ。実は、この Aceeca のデバイス、ディスプレイは W320 x H480 ピクセルで Palm TX と同じ解像度ではあるものの、スペック表には表示領域実寸が W46.64 x H68.95mm と書かれている。一方、手元の Palm TX の画面実寸は W53 x H80 mm なので、より細かいドットを使用していることになる。つまり、筐体サイズはほぼ同じで画面解像度も同じだが、物理的な画面のサイズだけが小さいのだ。

　ここまでをまとめると、筐体サイズは TX とほぼ同じで厚さだけ２倍、少し重く、画面は（解像度は同じだが）物理的に小さい。うん、それほど悪くないような気がしてきた。ただ、デザイン的な意味でバランスが悪いのが気になるところ。しかし、$199 というのは魅力的な値段ではある。国内で購入した場合いくらになるのか、またオプションとされている WiFi や Bluetooth をつけた場合にどうなるのか。やっぱり気になる。

投稿者 kagelow : 04:00 | コメント (2)

2010年04月01日

無線LAN機能付き Tungsten T5、失敗

　タイトルだけだと、なんだかスゴいことをやろうとしたみたいだが、そうではない。単純に Palm TX と中身を交換しようとしただけだ。まぁ実際には「T5 筐体の TX」にしかならないわけだが、ケースや基盤は（ほぼ）同じモノを使用してると思ったのに微妙に違って入らなかった。

　なんでそんなことをやろうと思ったかというと、陰郎は TX よりも Tungsten T5 のボディの方が好きなのだ。メタリックな表面が高級感を感じさせてくれるからだろうか。実際には両方ともプラスチックなのだが。写真は、このブログの以前のエントリから。

　ちなみに、別にエイプリルフールのネタにしようと思ったわけではない。人様のエイプリルフールネタは楽しませて頂いているが、陰郎は自分でやろうとは思わない。自分がやっても（多分）面白くないからだ。

投稿者 kagelow : 22:30 | コメント (2)