Jun 22, 2008

ビット数を数えるルーチン

32bitの立っているビット数を高速に数えるアルゴリズムとして、

int bitcount(unsigned long n)
{
    n = ((n&0xaaaaaaaa) >> 1) + (n&0x55555555); 
    n = ((n&0xcccccccc) >> 2) + (n&0x33333333); 
    n = ((n&0xf0f0f0f0) >> 4) + (n&0x0f0f0f0f); 
    n = ((n&0xff00ff00) >> 8) + (n&0x00ff00ff); 
    n = ((n&0xffff0000) >> 16) + (n&0x0000ffff); 
    return n;
}
こういうのが良く知られている。1行目で2ビットずつ足し合わせることで2ビットの中の立っているビット数を求め、2行目でそれらを2つずつ合計して4ビットの中の立っているビット数を求め…というのを32bit使って並列にやっている訳だ。ポイントを理解すれば単純明快、1ビットずつ32回評価するより段違いに速いのは明らかである。

数年前にこれを初めて見た時、独学の計算量節約プログラミングを長年続け、私の頭の中で完成しつつあった独自のプログラム理論は、一気に消し飛んだ。

そんな記憶も彼方の昨日、ネットサーフィンしていて、下のようなコードを見つけた。HAKMEM 169と呼ばれるアルゴリズムらしい。ネット上の色々なC言語実装を参考に勝手に整形した。

int bitcount2(unsigned long n){
    n = n - ((n >> 1) & 033333333333) - ((n >> 2) & 011111111111);
    return ((n + (n >> 3)) & 030707070707) % 077;
}
短い!
1つ目の例と同じ香りが漂うが、演算子の数が少ない。もしかして最強コードか?と思って解読しようとすると、数学的に大変ややこしい。
1行目は、3bitの整数m内の立っているビット数がm - (m>>1) - (m>>2)で計算できる(※1)ことを利用して、3bitずつ並列に、立っているビット数を計算する。2行目は、3bitずつのビット数を2つずつ足し合わせて6bitずつのビット数にしてから(※2)、bが6bitの整数、kが6の倍数の時にb*2^kを6bitの111111で割った余りがbになる(※3)ことを利用して、6bitずつの合計を求めている。

よく読むと、剰余演算を使ってるので、1つ目の例の方が速い。
参考:http://infolab.stanford.edu/~manku/bitcount/bitcount.html
("Parallel"が1つ目の例、"MIT"が2つ目の例に相当する。"Parallel"より速いのはビット数のテーブルを予め用意している。)

元々のMITのHAKMEMのコードは剰余演算のあるアセンブラで書かれており、アセンブラとしては目を疑うほど短い。HAKMEM 169は最速ではないが、コードのコンパクトさと合わせて称えるべきアルゴリズムなのだろう。

See more ...

Posted at 20:11 in PC一般 | WriteBacks (1)
WriteBacks

アセンブラとは

英語表記は、assembler。アセンブリ言語を使って作られたソースを、コンピュータが実行できる形に変換するためのソフトのこと。アセンブリ言語とは、コンピ...[link]

Posted by at 07/07/2008 06:26:22 AM

Jun 21, 2008

C言語の悪習

ある所で、C言語のソースに

if (NULL == pointer){...
という表記があるのを見て、好ましくない書き方だ、と言ったら、一緒にいた2人に、この書き方には理由がある、この書き方もありだ、というようなことを言われた。
このC言語特有の"=="の左側に定数を置く書き方は、知ってると通っぽい、知ってることを自慢したくなる、不思議な匂いを漂わせるようだ。プロはみんなこう書いている、という錯覚を起こさせることもあるようだが、事実は全く逆で、まともな書籍には書かれない、最もわかってる人々は使わない書き方だ。著名なオープンソースではマイナーである。
しかし、これが好ましくない書き方であることを簡潔に説明することは難しく、また100%誤りと言えるものではなく、一応利点もあることから、根強い人気があり、まるで宗教論争のように平行線の議論が繰り返される。

C言語のスタイルでよく議論になってるのを見かけるトピックは他にもある。それらと合わせて、個人的な見解を書いてみる。

(1) 定数==変数
"NULL == pointer"に限らず、

0 == integer
とか
true == boolean
というのも見かける。
肯定派の根拠はもちろん、変数==定数という書き方だと、if文などの条件式で間違って(変数=定数)と書いた場合にコンパイルエラーにならないため、バグの元になりやすいというものだ。
しかし、それが唯一の利点であることが、逆に好ましくない理由を示している。もしその利点が無ければ、標記のような書き方は誰もしないだろう。その理由は、読みにくいからである。
その利点には、可読性を犠牲にするまでの価値があるだろうか。

(計算式=定数)だと定数を左にしなくてもコンパイルエラーになるし、(変数=変数)だとコンパイルエラーにする類似の手段はない。まさかそういう間違いをコンパイルエラーにするために普段から(0+変数==変数)と書く人は居るまい。救われるのは"=="と"="の書き間違い全てではなく、(変数=定数)のみである。
それも、現在広く使われているコンパイラでは、条件式の部分が(変数=定数)になっているとワーニングを出してくれるので、さほど問題ではない。それに、そもそもそんな書き間違いは稀であろう。

変数と定数の比較の時だけ比較対象を左に書き、それ以外の比較では比較対象を右に書く、というのは、コーディングスタイルとして整合性に欠けるのではないか。それとも、定数==変数と書く人は、必ず比較対象を左に書くのだろうか?
C言語以外の、比較対象の定数を比較演算子の右に書ける言語では、定数を左に書く人は居ないだろう。C言語の限られた比較演算の場合だけ、役立つかどうか不明な些細な利点のために、敢えてわかりにくい書き方をするべきだろうか。

(2) (char)NULL

char c = (char)NULL;
というやつである。もちろん正しくは
char c = '\0';
だ。
これの支持者は'\0'より(char)NULLの方が「ヌルキャラクタ」として理解しやすいし、(メジャーな誤用のため)よく見かけるし、(char)NULLが'\0'と異なる値になる処理系はまず存在せず誤動作しないので、間違いだと気付かないのだろう。
しかし、ANSIの言語仕様でNULLは「ヌルポインタ」であり、いかなるオブジェクトも指さないポインタの値と決まっている。C言語的には(int)NULLは0でなくても良いのだから、(char)NULLを'\0'の意味で書くのは誤りである。
それでも、実際に問題が起こらないなら読みやすい方がいいだろう、と言われれば、返す言葉が見つからない。

(3) プログラム終了時でもmalloc()したメモリは必ずfree()すべし
コーディングスタイルやコーディングルールとして、malloc()には必ず対になるfree()を書く、というのがある。習慣的に静的にメモリリークを防ぐためには、基本的には好ましいことであるが、main()を抜ける直前やexit()の直前のfree()は無駄である。争点は、そのようなfree()も書くべきかどうかだ。
free()に限らず、ソケットのclose()やファイルポインタのfclose()など、exit時にOSに返されると規定されているリソース全てについて同じ話が当てはまる。

終了時もfree()すべし派の言い分は、
・その方がプログラムの構造として美しい
・free()して害になることはほとんど無い
・exit()後に処理があると、free()を怠ることにより問題が生じる可能性がある
というのがあったのを記憶している。ソースコードの静的解析ツールを使うと警告が出てしまう、というのもあったかも知れない。3つ目はatexit()やon_exit()のことを言っているが、これは世界にそんなコードが1つあるか無いかというオーダーのレアケースであろう。

そりゃ本当に無害なら書いた方が良い、終了直前のfree()は省略できるというのは知らなくてもいい無駄な知識、だとは思うが、終了直前のfree()も書くとコンパイルされてマシン語コードになってしまうのである。例えばfree()1つくらいなら10~20バイトくらいかも知れないが、それも10個になると100~200バイトにもなる(PowerPCで試した1つの例だと120バイトになった)。それだけ実行ファイルのサイズが無駄に大きくなってしまうのである。

例えばソースコードの読みやすさやメンテナンス性を犠牲にしてまで実行ファイルのサイズが小さくなる書き方を選ぶべきかと問われれば、よほどサイズがクリティカルなプロジェクトで無い限りNoであろうが、終了直前のfree()を省略して害になることはほとんど無かろう。ゴミを作り出すコードを埋め込んでまで、ある種のプログラムの対称性を重視する価値があるだろうか。

自分が書くコード、目の前にあるコードに整っていることを求める気持ちはよくわかる。例えばもし、C言語のソースファイルの最後の閉じ括弧は書かなくても良くて、書かない方がオブジェクトコードが小さくなる、というコンパイラがあったとしたら、個人的には最後の閉じ括弧を書かないのは気持ち悪すぎてできない。書いてコメントアウトするのも同様である。読む用とコンパイル用に閉じ括弧ありのソースとなしのソースを別に作るとしても、コンパイル用のソースの閉じ括弧を消して保存する操作が違和感の極みであり、コードを見ながらの手作業ではかなり後味が悪いだろう。

それでも、私はやはり実利を取るべきであり、ゴミを生むコードは書くべきでないと思う。終了直前のfree()は、どうせまとめて焼却されるゴミは分別するコストが無駄、というアナロジーででも割り切って省くべきではないだろうか。

See more ...

Posted at 23:01 in PC一般 | WriteBacks (3)
WriteBacks

僕自身も、終了直前の free() は呼ばなくてもいいとは思うが、 ゴミを生むコードは書くべきではないというのは言い過ぎだと思う。 以前、組み込み系の OS でファイルディスクリプタを開放せずに、 終了するプログラムを書いたが OS がリソースを開放してくれなかった。 組み込みシステムで使われるような OS は例外的かもしれないが、 OS がプロセスの終了時にリソースの開放を確実にしてくれるのかは疑問。 POSIX あたりで、規定されているのだろうか?

Posted by eternalharvest at 02/02/2010 12:55:29 AM

もちろんexit()時に解放されるリソースはOSや使用するライブラリによって異なります。 私も組み込み系の仕事をしているので、コードはOSによって異なるのが当たり前だと思っています。上の記事もその認識で書いています。 ファイルディスクリプタが指すリソースがプロセス終了時に解放されないことがあるのは普通だと思います。(手元のBSD系OSでもそうでした)

Posted by ynomura at 02/02/2010 08:33:11 PM

http://jbbs.livedoor.jp/bbs/read.cgi/computer/5651/1048816258/150 > if(変数=定数)なんてやっちゃうカスは、ど~せ他んところでバグだらけだろうから所詮カス。 > if(定数==変数)は、私はカスなので↑やっちゃうかも、って宣言してるみたいで、所詮カス。 > そんなコード見たら不安で仕方ない。

Posted by at 02/24/2010 04:06:09 PM

Jun 14, 2008

弾性衝突円盤アプレットの設計メモ

先日公開した弾性衝突円盤アプレットはまた改造して別バージョンを作ろうと思ってるので、自分自身がそのソースコードを読めなくならないよう、設計を書き残す。

●Swing関係
・JAppletを継承するクラスは、盤面クラスのインスタンスを作ってタイマー処理するだけにしている。
 表示画面が複数あっても、盤面のインスタンスを増やすだけで済む。

・タイマーはSwing timerを使っている。汎用のjava.util.Timerを使うのに比べて、タイマーイベントがSwingのイベント発行スレッドにて他のイベントと一緒にシリアライズされるので、タイマーイベントによって処理が割り込まれるということがなく、排他制御がシンプルになる。
 というようなことが、JavaSEのAPI仕様書のjavax.swing.Timerの項に書いてある。
 なお、所々でSwingUtilities.invokeLaterを使ってるのは、同様の効果を期待してのことだが、よく考えると、Swing timerを使ってるので意味が無かった。

・JComponentの盤面の大きさは、JComponent#getPreferredSize()が返すようにしている。レイアウトマネージャはFlowLayoutを使っており、FlowLayoutは余計な調節をしないので、これだけで済むはず。

●描画関係
・円盤の画像は、盤面インスタンスの生成時に全パターン用意するようにしている。(50-58行目)

・盤面の描画は、スプライト的なものを使わず、毎回矩形で塗り潰して全描画、としてるので、せっかくなので、描画の度に色相を少しずつ変えながら塗り潰すことにした。(72-73行目)
 bg_countはそのためだけの変数。
 74行目の青色設定は、状態表示にしか効いていない。

・円盤の座標は中心の座標を保持しているため、描画開始位置は半径を引いた座標になる。

●衝突計算関係
・円盤の移動後に衝突判定と衝突後の速度の計算をしている(127-182行目)が、壁との衝突と他の円盤との衝突が同時に起こった場合、円盤同士の衝突を先に計算すると、壁との衝突の影響が考慮されないので、壁がクッションのような扱いになってしまう。かと言って、壁と他の円盤との衝突を同時に計算しようとすると、複雑な計算になる。
 そもそも、円盤と壁が円盤を挟むように同時に衝突する場合、真ん中の円盤は壁の役割を兼ねるので、円盤同士の衝突の計算は、壁に向かう円盤同士の衝突ではなく、壁に向かう円盤と壁から跳ね返ってきた円盤との衝突とするべきである。
 そのため、壁との衝突を先に処理するようにしている。

・壁との衝突判定は、円盤が壁と深く重なってる場合は衝突状態が続くので、速度ベクトルが壁の方を向いているかどうかを考慮するようにした。(131,138行目)
 円盤同士が深く重なってる場合も衝突状態が続くので、前回の中心間の距離を保存して、距離が縮まっているかどうかを衝突判定の材料にしている。(hit_depth[][]が前回の距離の2乗)

・複数の円盤の衝突が同時に発生した場合の計算は非常に複雑になる。
 1つの円盤が他の2つの円盤に同時に衝突するのはまだいいが、さらに衝突相手がまた別の円盤と同時に衝突する場合は、衝突の影響が全ての繋がる円盤に及ぶので、計算が大変である。
 そのため、1つの円盤は同時に他の1つの円盤としか衝突せず、さらに他の円盤との衝突はその瞬間は無視し、めり込むことを許す、とした。(isHit[]が衝突フラグ)

・衝突による速度変化を一旦別の配列に入れているのは、1つの円盤が同時に複数の円盤と衝突する計算をする場合のことを考えてのものであり、今回の方式では意味が無い。

●円盤の増減関係
・動的に円盤の数を減らせるよう、規定の数の円盤以外は、画面外に出るまで衝突判定の対象外とした。(185-193行目)

・動的に円盤の数を増やす時、既にある円盤と同じ場所から、速度ベクトルを30°ずらしてスタートさせるようにしている。それにより、円盤が分裂する感じになる。
 一気に2つ以上の円盤が増える場合は、分裂する円盤をそれぞれ違う円盤にしている。0番の円盤から分裂させると、いつも同じ円盤から分裂する感じになるので、最後尾の円盤から分裂させるようにしている。(201-207行目)

See more ...

Posted at 20:58 in Java | WriteBacks (0)
WriteBacks

Jun 10, 2008

玄箱HGに移行

10年以上前に購入し、ここ3年連続運転のwebサーバーとして活躍してきたノートパソコン、Mebius MN-340(CPU:Pentium 150MHz)の中から、チュイイイン、ギャアアァァンという、回転刃が金属板を削るような音がしてきたので、先々月から準備し始めていた玄箱に本格的に移行することにした。

初代玄箱の試験用のDebian環境をddでパーティションごとバックアップして、試験用のHDDをまともなHDDに換装して、ddでリストアしようとしたら、Debianが起動しなかった。(ddで取ったHDDのイメージファイルはLinuxでループバックデバイスとして正常にマウントできたのに。なぜだろう?)

仕方なく、Debianの再インストールを始めた。何度かインストールに失敗した後のある夜、寝る前にインストール作業をしていて、操作ミスをして慌てて電源を抜いたら、最悪のタイミングだったようで、ファームウェア異常になって玄箱自体が立ち上がらなくなってしまった。
これを修復するには、JTAGの環境が必要だ。長いこと半田こても握ってないし、そもそも半田こてを用意していない。半田こてを入手しても、その先も険しい道のりだろう。

元々、初代玄箱を試験的に動かしてみて、このMebiusの代わりは荷が重いと感じており、これまでも玄箱HGの購入を少し考えていたので、これまでに調べたことが無駄にならないように、忘れない内に玄箱HGを購入した。

●玄箱HG Debian化メモ
http://www.revulo.com/にあるページの通りの方法で、debian-sarge-2.6.17.3-kuroHG-20060702.tgzを使って、一発で成功した。
具体的な手順は以下の通り。

1. ログイン(ファームウェア1.01の初期状態だと、user=root, pass=kuroadmin)
2. echo -n NGNG > /dev/fl3
3. reboot
 →EMモードで起動する
4. 上記.tgzをtmpimage.tgzという名前にしてzip圧縮、ファームウェア1.01のimage.zipをそれに置き換える
5. ファームウェアダウンロード

●Debianセットアップメモ
- IPアドレス変更
 /etc/network/interfacesを書き換える
- Debian upgrade
 apt-get update
 apt-get upgrade
 を順に実行する
- 時刻設定
 dateコマンドで設定する

- テキストエディタの設定
 デフォルト設定では、何かにつけnanoというエディタが起動するので、
 update-alternatives --all
 を実行して、適切な選択肢でviクローンを選択する。

- IBM JDKのインストール
http://chira-ura.seesaa.net/article/28761629.htmlとそのリンク先に、パッケージの入手方法からalternativesの設定方法まで書かれている。
なお、Tomcatの起動スクリプトに書かれているIBM JDKのインストール先のディレクトリ名は、上記ページの説明とは違って、/usr/lib/j2sdk1.5-ibmとなっている。
上記ページの説明のようにalternativesを適切に設定すれば、複数のJavaをインストールした後のJava VMやJavaコンパイラの切り替えは、それぞれ
update-alternatives --config java
update-alternatives --config javac
というコマンドでできる。

- Tomcat5が起動しない場合の対処
 JavaのセキュリティマネージャをOFFにする。具体的には、/etc/init.d/tomcat5内にて
  TOMCAT5_SECURITY=no
 と設定する。

- Tomcatが使うJava VMについて
javaコマンドに関係なく、/etc/init.d/tomcat5にて優先順が決まっている。
別のものを使う場合は、/etc/default/tomcat5のJAVA_HOMEを設定する。

See more ...

WriteBacks

パソコン バックアップ

パソコン バックアップについての情報です。[link]

Posted by at 07/09/2008 07:59:00 AM

パソコン バックアップ 方法

パソコンのバックアップの方法についての情報です。[link]

Posted by at 07/09/2008 10:21:31 AM

HDD バックアップ

HDD バックアップについての情報です。[link]

Posted by at 07/09/2008 05:06:40 PM

Jun 08, 2008

ImageMagickで半透明画像を作る

前のエントリーに貼っている数式画像は、このサイトの数式画像作成CGIで作った画像を、ImageMagickで白黒反転して半透明にしている。
今回実際に行ったコマンドを書き記す。

convert -negate -resize 75% original.png tmp_nega.png
convert tmp_nega.png -channel alpha -fx "g" tmp_blur.png
convert tmp_blur.png -fx "g>0" result.png

1行目が白黒反転と縦横75%縮小、2行目が各ピクセルのα値(非透過率)の設定、3行目が背景でない部分を白にするコマンドだ。2~3行目では白の度合いを緑のレベルで代用しているが、元画像は白黒なので、赤や青を使っても同じだ。

白さに比例したα値を設定した後に色を白にするのは、そうしないと輝度が下がりすぎてしまうからである。例えば輝度50%のピクセルに50%の透過率を与えると、黒地だと輝度が25%に下がってしまう。黒地のモノクロ画像を半透明にするには、その白さをα値にして、白で塗り潰せば良いのである。
しかし、それだと、暗色の背景で透過合成表示してくれない画像ビューワで見ると真っ白になってしまうため、3行目では白の度合いが0のピクセルだけは黒にしている。"g>0"を"1"にすれば白で塗り潰すことになる。

なお、この例では変換の度に異なる画像ファイルを作るようにしているが、上書きで良いなら同じファイル名を指定しても良い。

参考:
convertの使い方ImageMagickのサイト内)

See more ...

Posted at 00:35 in PC一般 | WriteBacks (0)
WriteBacks