型の最大最小値

長かった…
これがしたかっただけなんだけど、ずいぶん大げさになってしまった。

// 型の最大値
template <typename X> struct max_of {
        typedef typename SelectNegativePresentation
        <X, limits_of_u<X>, limits_of_s2<X>, limits_of_s1<X>, limits_of_sa<X>
         >::Result Selected;
        static X value() { return Selected::max(); }
};

// 型の最小値
template <typename X> struct min_of {
        typedef typename SelectNegativePresentation
        <X, limits_of_u<X>, limits_of_s2<X>, limits_of_s1<X>, limits_of_sa<X>
         >::Result Selected;
        static X value() { return Selected::min(); }
};

ちなみに、シフトによる桁あふれがあるのでg++でコンパイルするとご丁寧に警告を出してくれるのだけど、これが3000行近かったりするw

型の選択

これはLoki(というかModern C++ Design)からのパクリ。

// 型選択
// flagが真ならResultがT1、偽ならResultがT2となるクラステンプレート
template <bool flag, typename T1, typename T2> struct Select {
        typedef T1 Result;
};
template <typename T1, typename T2> struct Select<false, T1, T2> {
        typedef T2 Result;
};

// 整数の表現形式を選択する
template <typename X, typename U, typename S2, typename S1, typename SA>
struct SelectNegativePresentation {
        typedef typename Select<
                is_unsigned<X>::value, U,
                typename Select<has_sign_and_abs_part_unsafe<X>::value, SA,
                                typename Select<
                                        is_1s_complement_unsafe<X>::value, S1, S2
                                >::Result
                >::Result
        >::Result Result;
};

こいつを使うと、型の最大最小がわかるはず…

整数の表現形式ごとの最大最小

これはWikipediaを参考にしつつ。
1の補数表現と2の補数表現が同じになってしまってあれっと思ったけど、そういえば+1されてるかどうかの違いだった… 忘れてるなあ。

// 2の補数表現での最大最小
template <typename X> struct limits_of_s2 {
        static X max() { return msb<X>::value() ^ ~X(0) ; }
        static X min() { return msb<X>::value(); }
};

// 1の補数表現での最大最小
template <typename X> struct limits_of_s1 {
        static X max() { return msb<X>::value() ^ ~X(0) ; }
        static X min() { return msb<X>::value(); }
};

// 符号ビット+絶対値表現での最大最小
template <typename X> struct limits_of_sa {
        static X max() { return msb<X>::value() ^ ~X(0); }
        static X min() { return ~X(0); }
};

// 符号なし整数の最大最小
template <typename X> struct limits_of_u {
        static X max() { return ~X(0); }
        static X min() { return X(0); }
};

整数型のビット数

// Xの範囲で1 << Nが算術的に桁あふれするならvalue==1
template <typename X, unsigned N> struct arith_overflow {
        // 1<<0は算術的に桁あふれしないと定義する。
        // N>0に対しては、1<<(N-1)が算術的に桁あふれしておらず、
        // かつ(1<<N)/2 == 1<<(N-1)が成立する場合、
        // 1<<Nは算術的に桁あふれしないと定義する。
        // なお、Nビット幅の整数Xに対して(X(1)<<N)==0は必ずしも成立しない。
        enum { value = arith_overflow<X, N-1>::value
               || X(X(1) << N) / 2 != X(1) << (N - 1) };
};
template <typename X> struct arith_overflow<X, 0> {
        enum { value = 0 };     // 定義より、1<<0は算術的に桁あふれしない

};


// 整数型の有効桁のビット数を得る
template <typename X, unsigned N = 0, bool flag = false> struct valid_bits_of {
        // X(1)<<Nが桁あふれする場合(flag != false)の定義
        enum { value = N };
};
template <typename X, unsigned N> struct valid_bits_of<X, N, false>
{
        // X(1)<<Nが桁あふれしない場合(flag == false)の定義
        enum {
                // N+1〜N+3で桁あふれするか調べ、分からなければN+4で調べる
                value = arith_overflow<X, N + 1>::value ? N + 1
                : arith_overflow<X, N + 2>::value ? N + 2
                : arith_overflow<X, N + 3>::value ? N + 3
                : valid_bits_of<X, N + 4,
                arith_overflow<X, N + 4>::value>::value
        };
};


// 整数型のビット数を得る
template <typename X> struct bits_of {
        enum {
                value = valid_bits_of<X>::value + is_signed<X>::value
        };
};


// MSBのみが立った数を得る
template <typename X> struct msb {
        static X value() {
                return X(1) << (bits_of<X>::value - 1);
        }
};

valid_bits_ofで名前あってるかな?
なんで4つ飛びに調べてるかというと、Sun C++でテンプレートのネストが深すぎると警告がでたため。

符号つき数値型の表現方式判定

これは http://www.kijineko.co.jp/tech/cpptempls をまるパクリで。
ただし、クラス定義の中で静的クラス変数を定義できる処理系かちょっと思い出せなかったので、列挙定数に置き換え。
あと、符号なしの型を与えるとコンパイルエラーになるようにちょっとだけ修正。

// condが成立しない場合にコンパイルエラーにするマクロ
#define STATIC_ASSERT(cond) typedef char assertFailed[(cond) ? 1 : -1]


// 符号ありの型Xが2の補数表現ならvalue==1
template <typename X> struct is_2s_complement_unsafe {
        enum { value = (X(-1) & 3) == 3 };
};
template <typename X>
class is_2s_complement: public is_2s_complement_unsafe<X> {
        STATIC_ASSERT(is_signed<X>::value);
};

// 符号ありの型Xが1の補数表現ならvalue==1
template <typename X> struct is_1s_complement_unsafe {
        enum { value = (X(-1) & 3) == 2 };
};
template <typename X>
class is_1s_complement: public is_1s_complement_unsafe<X> {
        STATIC_ASSERT(is_signed<X>::value);
};

// 符号ありの型Xが符号ビット+絶対値表現ならvalue==1
template <typename X> struct has_sign_and_abs_part_unsafe {
        enum { value = (X(-1) & 3) == 1 };
};
template <typename X>
class has_sign_and_abs_part: public has_sign_and_abs_part_unsafe<X> {
        STATIC_ASSERT(is_signed<X>::value);
};

型の符号有無判定

http://www.kijineko.co.jp/tech/cpptempls を読んで、「numeric_limitsって便利だなあ」と感心することしきり。さっそく使ってみたい(超ミーハー)のだけど、仕事で使うとなると用意されてないかもしれない。

ということで、似たようなものをテンプレートメタプログラミングでつくれないかなと試行錯誤中。はてさて…

まずは型の符号有無をコンパイル時に判定するテンプレート。

// Xが符号つきの型ならvalue==1
template  struct is_signed {
 enum { value = 0 > X(-1) };
};

// Xが符号なしの型ならvalue==1
template  struct is_unsigned {
 enum { value = 0 < X(-1) };
};

こんな調子でいいのかな?

long longの左シフト

コンパイル時に整数型のビット数を得るテンプレートを試していて、(long long)(1ll << 64)が0にならないことに気が付いた。しかも、4294967296とかいう妙な値。

そんなわけで、検証プログラム。

#include <iostream>
int main(int argc, char *argv[]) {
        signed long long sll = 1;
        unsigned long long ull = 1;
        for(int i = 30; i < 70; i++) {
                std::cout << "1ll<<" << i << " = " << (sll << i)
                          << "\t1ull<<" << i << " = " << (ull << i)
                          << std::endl;
        }
        return 0;
}

Sun C++でコンパイルして実行してみると

1ll<<60 = 1152921504606846976     1ull<<60 = 1152921504606846976
1ll<<61 = 2305843009213693952     1ull<<61 = 2305843009213693952
1ll<<62 = 4611686018427387904     1ull<<62 = 4611686018427387904
1ll<<63 = -9223372036854775808    1ull<<63 = 9223372036854775808
1ll<<64 = 4294967296      1ull<<64 = 4294967296
1ll<<65 = 8589934592      1ull<<65 = 8589934592
1ll<<66 = 17179869184     1ull<<66 = 17179869184
1ll<<67 = 34359738368     1ull<<67 = 34359738368
1ll<<68 = 68719476736     1ull<<68 = 68719476736
1ll<<69 = 137438953472    1ull<<69 = 137438953472

g++でコンパイルして実行してみると

1ll<<60 = 1152921504606846976     1ull<<60 = 1152921504606846976
1ll<<61 = 2305843009213693952     1ull<<61 = 2305843009213693952
1ll<<62 = 4611686018427387904     1ull<<62 = 4611686018427387904
1ll<<63 = -9223372036854775808    1ull<<63 = 9223372036854775808
1ll<<64 = 1       1ull<<64 = 1
1ll<<65 = 2       1ull<<65 = 2
1ll<<66 = 4       1ull<<66 = 4
1ll<<67 = 8       1ull<<67 = 8
1ll<<68 = 16      1ull<<68 = 16
1ll<<69 = 32      1ull<<69 = 32

CPUはいずれもAMD Opteron。コンパイラのバージョンは

CC: Sun C++ 5.7 Patch 117831-02 2005/03/30
g++ (GCC) 3.4.3 (csl-sol210-3_4-branch+sol_rpath)

まあ、ビット幅を越えてシフトした場合の振る舞いは未定義だった気がするので、その意味ではおかしくはない。けど、コンパイラによって振る舞いが違うってのはちょっと意外だったなあ。

けど、ビット幅Nの型Xに対して常に(X)(X(1)<<N)==0が成立するとばかり思い込んでいたので、ちょっと期待が外れてしまったりして。

たらいまわし関数その2

さきのテンプレート版たらい回し関数(関数じゃないけど)、どうもおかしいと思ったら>と<がHTMLタグ扱いになってた… はずかしー

ちなみにg++のバージョンはg++ (GCC) 3.4.3 (csl-sol210-3_4-branch+sol_rpath)。ちょっと古いかもしれないので、4.xでは改良されているかもしれない。

で、今度はSun C++で挑戦。

% CC -V
CC: Sun C++ 5.7 Patch 117831-02 2005/03/30
% time CC tarai_t.cc
7.08u 0.17s 0:07.49 96.7%
% ./a.out
Tarai(384, 192, 0) = 384

これもかなり古いけど、意外とあっさりと成功。

pukiwiki-edit-modeとWikiName

PukiWikiに書く内容をオフラインで下書きするとき、Emacsならば先頭行に「// -*- pukiwiki-edit -*-」と書いておけば自動的にpukiwiki-edit-modeになるので便利だ。
場合によってはoutline-modeよりも視認性がいい場合もある。

ところでこのpukiwiki-edit-modeだが、WikiNameを認識するのがうざったい。
C++やJavaのソースコードを貼り付けると、妙なところでアンダーラインが引かれてしまう。
また、ヘッダ行にWikiNameと認識できるものが入ってしまうと装飾がおかしくなってしまう。

pukiwiki-mode.elを改造しようと思ってソースを読んでみたのだけど、単に~/.emacsに(setq pukiwiki-style-anchor-regexp-alist nil)を入れておけば良いらしい。まあ、今時WikiNameなんか使わないだろうし、これでいいかなと。

あとは、URIに反応するところと、改行時に前行のインデントを継承するのをやめさせたいなあ…

toppers/jsp #2

前に書いたように、GW後半戦にtoppers/jspのpthreadへの移植に挑戦。

pthread_mutexを使ってタスクコンテクストの切り替えはできるようになった。xUnit環境と割り切って使うので、割り込みのサポートはしなかった。

だけど、実はこれは大きな制限だったことが実装後に判明。システムクロック割り込みを受け付けないため、周期ハンドラによるiwup_tsk()などが動作しないのである。やられた orz...

んで、しょうがないので各スレッドにSIGUSR1でも送って、シグナルハンドラ内でCPU使用権のpthread_mutexを解放しようかなあ… と軽く考えていたのだけど、これもうまくないらしい。
シグナルハンドラ内ではasync signal safeな関数しか使えないので、pthread_mutex_unlockなども使えないそうなのだ orz...

pthread_mutexじゃなくて、パイプを使ったメッセージパッシング方式に切り替えるしかないかなあ…

情報処理技術者試験受けてきた

4/15に情報処理技術者試験(エンベデッドシステム)受けてきた。
会場は高千穂大学。どうもES専用の会場だったらしい。
駅についたらそれっぽい乗客がごそっと降りて、人の多さにちょっとびっくり。駅前のセブンイレブンはほとんど食料がなくなっていたし、道中のローソンはレジが長蛇の列。

男女比は99:1といったところ。トイレが混み混みで困った。偏見もあるのだろうけど、なんだか地味っぽい受験者が多い気がする。アドミニストレータ系や基礎情報だともうちょっと若い人が多いのだろうか。

試験のデキは… 微妙。ダメとも言えないし、安心できるほどできたわけでもなし。最近忙しかったから、試験対策はあまりしてなかった。
午後IIがかなりダメだったから、やっぱダメかなあ…

ところで、会場でMさんとばったり出くわしてびっくり。聞くところによると、Mさんの会社では合格すると褒賞金として20万円がでるらしい。羨ましいなあ… ていうか、こちらは1円も出ませんよ orz...

Wikiで課題管理

仕事で、モジュール間の設計課題をPukiWikiで管理している。

もともとは親分が「設計過程も記録に残しておくことはできないのか? 新しい機種の設計を行なう毎に似たような検討を繰り返しているのはうんぬん」と言い出してきて、それを受けた中ボスが自分の使っていたPukiWikiを試してみましょうかと応じた次第。

アイデアは仲間と一緒に考える【解決編】(ITmedia Biz.ID)
実践！ 一人で思い浮かばないアイデアは同志を募って集める【解決編】(ITmedia Biz.ID)
Wikiを使ってプロジェクトの進捗管理【解決編】(ITmedia Biz.ID)
企業内でWiki活用の効果はどの程度? (/.j)

今のところ、trackerプラグインをカスタマイズして検討課題を管理してる。
1ページ中に複数の細かい項目が出てくるようになったのでこの方法も試してみるのもいいかも。

人の名前でページを作っておいて、各ページのTODO項目からリンク張っておくと、その人のTODO項目が一度に分かって便利なのに気が付いた(PukiWiki公式でやってた)。

課題のステータスはこれにならってToDo, Doing, Doneの3つに設定。
やはりカンバン方式にならって赤・黄・緑で分かりやすく表示してる。

あと、リアルタイムに進捗が分かるのが親分に受けが良い。
ただ、2時間おきに「緑が増えたね」などとプレッシャーをかけられるようになるとは予想外の事態wwww

整数の対数

整数の平方根を求めるアルゴリズムは奥村先生の本やHacker's Delightで紹介されているけど、整数の対数を求めるアルゴリズムはないようだ。

いや、log2(x)やlog10(x)を求めるのはあるんだけど、使いたいのは1024*log2(x)とかのあらかじめスケーリングされた値。固定小数点形式で得たいというべきか。ちなみにNewton法は遅くて使い物にならなそうだった。

ちょっと考えてみたんだけど、(1<<K)*log2(x)についてはlog2(x)をベースにしてrange coder風の求め方でいけるんじゃないかなと思ってこんなのを作ってみた。

#define K 7

/**
 * (1<<K)*log2(x)を求める。
 * xは0≦x＜(1<<16)を満たす必要がある。
 */
unsigned ilog(unsigned x)
{
 int i;
 unsigned r, th, tl, tm;

 /* log2(x)の整数部分を得る  */
 for(i = 31; i > 0; --i) {
  if(x >= (1u << i)) {
   r = i;
   break;
  }
 }
 if(i == 0) return 0;

 /* range coderを使ってlog2(x)の小数点以下の桁をKビット決定する  */
 th = 0x10000;
 tl = 0x8000;
 x = x << (15 - r);
 for(i = 0; i < K; i++) {
  tm = isqrt(th * tl);
  if(x >= tm) {
   r = (r << 1) | 1;
   tl = tm;
  } else {
   r = r << 1;
   th = tm;
  }
 }
 return r;
}

intが32ビット(以上)のマシン用。どうでしょう?

コンピュータの構成と設計 ハードウエアとソフトウエアのインタフェース 第3版

いわゆるパタヘネ。これも順次読み進めていって、今下巻にさしかかっているところ。

妙にIntelをバカにしている(ように思える)記述があり、その度にニヤリとしてしまうw しかし、やはり名著と呼ばれるだけのことはあって、RISC(MIPS)の設計理念が非常に良く伝わってくる。

8年ほど前に大学の講義で8ビットCPUを設計・実装したことがあったのだけど、この本が出ていたらもっと良いものが作れていたに違いない。

…いや、それはないか。だってあの時は74LSシリーズを手配線していたからなあw メモリ空間が8ビットしかなかったけど、それでもA4サイズ強の基板がワイヤで埋め尽くされたのだっけ。写真取っとけばよかった。

それはそうと、この本の付録CD-ROMを今日になって見てみたのだけど、VHDLやVerilogのチュートリアルが入っていてかなり得した気分。素晴らしい。

コードコンプリート 続き2

「コードコンプリート」はやはり素晴らしかった、というのは前回書いたけど、多少は気にいらない点もある。

1つめはプログラミング言語としてC/C++/Javaといった"一級言語"と、VB"ごとき"を同格に扱っている点。まあ、気に入らないというだけであって、現実世界におけるVBの価値を否定するというわけではないのだけれど… なんか身びいきな感じで良い印象を受けない。

2つめはMSローカルな型の命名規則を、あたかも普遍的な慣習であるかのように紹介している点。C/C++の世界でstructタグ名/typedef名を大文字だけで表記するのはFILE型くらいなのに、C/C++、あるいはUNIX/Linuxの伝統であるという嘘が書いてある。STL(あるいはC++の仕様書)やPOSIXの仕様書を確認したほうがいいんじゃないか。

3つめはどうでもいいんだけど、カッコの内側のスペースの入れ方がまちまちなこと。

for ( i = 0; i < 100; i++ ) ...
if( type == 2 ) ...
corpExpense[ crntQtr ][ i ];

などと書いてある一方で、

profit[i] = 0;
index = (key - 10) / 5;

などという書き方もあって統一が取れておらず、ちょっと気持ち悪い。自分なら後者に統一するところ。

まあ、ケチはつけてみたけど、こういった難癖程度しかつけられないってことはやっぱり良い本だからなんだよね。

テキスト届いた

情報処理技術者試験(TE(ES))のテキストがamazonから届いた。

む、難しい… orz

なんか1ページ目からいきなりアナログ/ロジック混在回路の問題ですか。
一応電気電子工学科卒だけど、ピュアな論理回路くらいしかやらなかったから、かなりキビシイ。まあ、早めにテキスト買ってよかったと思うことにしよう。

ただ、紙が薄いから意外とページあるんだろうな。しくしく…

CNET Japan: MS、「ブルースクリーン」を模倣するジョークソフトを自社サイトで提供

個人的には面白いと思うんだけど… NAIは大人気NAIなあ。なんつってw

むしろ、sysinternalsにあったのに、買収したとたん公開しなくなったとしたら、そっちのほうが批判を浴びるんじゃないかなあ。

NIOS II

組み込みCPUの検討をやることになって、AlteraのNIOS IIの資料をダウンロード。ついでにQuartus IIとNIOS EDSもインストール。で、でかい… 2GBオーバかよ… orz

しかし、この環境はなかなかよさげ。32ビットRISC CPUコアを持ち、Cygwinベースのgcc+gdbとそのGUIインターフェースを開発環境とし、newlibと各種RTOSが採用可能。ソフト開発者はHDLまわりのことは知らなくて良いし、逆もまた同じ。

これで従来のMCUベースのシステムより安く速くなるんだから、これはかなり期待できそう。ひとまず検討用の評価キットの予算を申請中。

コードコンプリート 続き

で、この「コードコンプリート」、今は会社に持っていってしまっているので、家で読めない(泣)。

ことの発端は、今年度の部の方針。
各機種ごとにバラバラで作っていたソフトウェアを標準化しろという話で、これ自体はよくある話なんだけど、下期になってかなり具体的な戦略を出さないといけないことになった。

で、偉い人が打ち出した方針がコンポーネント化による標準部品化。ここまではいいんだけど、何を部品にすればいいのかでまったく方向性が見いだせない状況。こういう時のために上流行程ってのがあるべきなんだけど、「下流行程ができなくなったので上流行程をやってます(やってることになってます)」的なノリの人たちが考え付くはずもなし。

# こういう人たちが「上流行程」と呼んでいるものっていったい何なんだろうね、というイヤミはさておき…

なぜか自分も参考人として召喚されてしまい、意見を述べるはめになったのだけど、「コンポーネント化と言ってみても、ソフトウェアの構成上は単なるモジュールでしかないよね」というわけでくだんの「コードコンプリート」を持っていき、モジュール分割の方法を講釈してあげたという次第。

まあ、どういう検討結果を持ってくるかはお手並み拝見といったところ。

コードコンプリート

先日購入した「コードコンプリート」は、評判に違わない良書だった。

上流工程をあまりに重視するあまり、「実際の設計活動」の知見が失われているんじゃないかと思うことがあるんだけど、これがあるなら大丈夫かもしれないw

(実際のところ、要求分析以降の作業について自分の上司やリーダーが指導してくれたことなんてなかったし、その能力があるのかも疑わしい。
まあ、そういう職種の人じゃないんで別にそれはいいんだけど、だからといって現実の問題を解決する能力を開発しなくていいということにはならないんだけど… ぶつぶつ)

ただ、まだ上巻の半分くらいしかまだ読めてない… ボリューム多すぎ orz
しかも会社に持っていってしまったからなあ(続く)