コグノスケ

どうせやるならとことんやろう

今日はコードを2つ紹介（出典: ハッカーのたのしみ, Henry S. Warren, Jr., 滝沢ら訳）しますがどれもメチャクチャわかりづらいです。どちらも可読性なんかかなぐり捨ててとにかく効率を追った、ある意味潔いコードです。GNU netcatも中途半端に読みづらい変なコードを書くくらいなら、このくらいやって欲しかったなあ。

本についてですけど、前半はまだわかる気がしますが、後半はあまりにも頑張りすぎていて全然わからんです…。こういうコードを読んでいると、根性っていうか、ハッカー達の職人魂みたいなものを感じますよ。

ビット計算は奥は深い

さて1になっているビットを数える処理ですが、比較的わかりやすいコードを一つ例にとってみようと思います。

unsigned int x;
int count;

x = (x & 0x55555555) + ((x >>  1) & 0x55555555);
x = (x & 0x33333333) + ((x >>  2) & 0x33333333);
x = (x & 0x0f0f0f0f) + ((x >>  4) & 0x0f0f0f0f);
x = (x & 0x00ff00ff) + ((x >>  8) & 0x00ff00ff);
x = (x & 0x0000ffff) + ((x >> 16) & 0x0000ffff);

count = x;

以上は32ビット用のコードです。ぱっと見だと、なんじゃこりゃ？って感じですね。このコードでは隣り合う桁を足していきます。最初は隣の1桁、次は2桁、次は4桁という風に倍々ゲームにしていきます。
では8ビットで検証してみます。

 x           = [   1][   0][   1][   1][   0][   1][   0][   0]
 1ビット毎の :     1,    0,    1,    1,    0,    1,    0,    0
 1の個数    :

 x           = [   1][   0][   1][   1][   0][   1][   0][   0]
 x>>1        =       [   1][   0][   1][   1][   0][   1][   0][   0]
 0x55        = [   0][   1][   0][   1][   0][   1][   0][   1]
 
 x&0x55      = [   0][   0][   0][   1][   0][   1][   0][   0]
 (x>>1)&0x55 =       [   1][   0][   1][   0][   0][   0][   0][   0]
 x           = [   0     1][   1     0][   0     1][   0     0]
 2ビット毎の :   1 + 0 = 1,  1 + 1 = 2,  0 + 1 = 1,  0 + 0 = 0
 1の個数    :

 x           = [   0     1][   1     0][   0     1][   0     0]
 x>>2        =             [   0     1][   1     0][   0     1][   0     0]
 0x33        = [   0][   0][   1][   1][   0][   0][   1][   1]

 x&0x33      = [   0     0][   1     0][   0     0][   0     0]
 (x>>2)&0x33 =             [   0     1][   0     0][   0     1][   0     0]
 x           = [   0     0     1     1][   0     0     0     1]
 4ビット毎の :               1 + 2 = 3,              1 + 0 = 1
 1の個数    :

 x           = [   0     0     1     1][   0     0     0     1]
 x>>4        =                         [   0     0     1     1][   0     0     0     1]
 0x0f        = [   0][   0][   0][   0][   1][   1][   1][   1]

 x&0x0f      = [   0     0     0     0][   0     0     0     1]
 (x>>4)&0x0f =                         [   0     0     1     1][   0     0     0     1]
 x           = [   0     0     0     0     0     1     0     0]
 8ビット毎の :                                       3 + 1 = 4
 1の個数    :
よってxには1が4つ含まれていた。

このように検証してみますと、1の数を倍々でまとめていって最後にはxの右端にビットの個数が集約されて計算されることが分かります。凄いんですけど、なんともトリッキーですねえ。

もう一つ似たようなコードで、パリティを求める処理が書けます。単純にパリティを求めるならば、全てのビットのxorを取れば良いのですが、この本では以下のように書きます。

unsigned int x, y;
int parity;

y = x ^ (x >> 1);
y = y ^ (y >> 2);
y = y ^ (y >> 4);
y = y ^ (y >> 8);
y = y ^ (y >> 16);

parity = y & 1;

以上は32ビット用のコードです。やはりこれもぱっと見では、なんじゃこりゃ？って感じです。これも2進数の1桁分, 2桁分, 4桁分…とxorを取っていって最後に32桁分のxorがyの右端に来るという仕掛けです。
では8ビットでの計算の結果をご覧下さい。

 x    = [   7][   6][   5][   4][   3][   2](   1)(   0)
                                                `-----| xor
 x>>1 =       [   7][   6][   5][   4][   3][   2](   1)[   0]
 
 y    = [   7][ 7,6][ 6,5][ 5,4][ 4,3]( 3,2)[ 2,1]( 1,0)
                                          `-----------| xor
 y>>2 =             [   7][ 7,6][ 6,5][ 5,4][ 4,3]( 3,2)[ 2,1][ 1,0]
 
 y    = [   7][ 7,6][ 7-5]( 7-4)[ 6-3][ 5-2][ 4-1]( 3-0)
                              `-----------------------| xor
 y>>4 =                         [   7][ 7,6][ 7-5]( 7-4)[ 6-3][ 5-2][ 4-1][ 3-0]
 
 y    = [   7][ 7,6][ 7-5][ 7-4][ 7-3][ 7-2][ 7-1]( 7-0)
                                                  ~~~~~~

このように検証してみますと、うまく各桁が一回ずつxorされるようにずらしながら計算していることがわかります。最後に yの右端に全てのビットのxorが計算されているのが見事ですね。

今時トリッキーなコードは嫌われる

現在はコンピュータが十分高速化していて、ソフトウェアの規模も大きくなっているため、速度より保守性を重視します。要は遅くて良いから誰もが読める普通のコードが求められます。どんなに速くても誰も理解できないトリッキーなコードは歓迎されません。

ただしそれは商業サーバー用のプログラムとかPC用のプログラムでの話。もっと特殊な分野、例えば究極の速度を求める超高性能計算（計算用のライブラリとか）や、ハードがショボショボな組み込み機器などは、無駄に使えるCPUやメモリがありません。というわけで、まだまだトリッキーなコードも出番があるんじゃないかなあ？

もー！変なことするからこんがらがるんだよ！

GNU netcat 0.7.1（※）でポートのlistenはできるのに、別のホストにconnectしようすると無視されてしまいます。PCでコンパイルすると動くので、環境依存かなあ？と思ってprintfデバッグしていたら、複雑といえば複雑だけどしょうもない問題だったことに気づいてがっくり…。

以下はflagset.cの135行目あたりにあるint netcat_flag_count(void) という関数内の処理です。

char c;
int ret = 0;

while (c) {
  ret -= (c >> 7);
  c <<= 1;
}

この処理はcの中の1になっているビットを数える処理です。retには1だったビットの数が格納されます。例えばc = 3だったらret = 2です。

ぱっと見ret -= とマイナスするの部分が奇妙に見えます。理由としてはcの最上位ビットが1（つまりマイナスの値）ならば、c >> 7としたときに符号が維持されたままシフトされ、-1になるためです。もし最上位ビットが1でなければc >> 7は0になります。つまりc >> 7は -1 or 0になるので、ret -= で符号を反転させて足してあげています。
極めてわかりづらいです。なんでこんなことするんでしょうか。

それはさておき、このコードの何が問題かというと、char = signed charだと決めつけていることです。世の中にはchar = unsigned charとするコンパイラもあります。というか実際、そういうコンパイラが目の前にあります。しかし大抵の人がchar = signed charだと思っていることを踏まえると、char = unsigned charという設計は避けるべきだと思います。
このコンパイラを作った人は意地悪というか…ちょっとひねくれてたんでしょうね。

C言語ではcharがsigned charであるという決まりも、そもそも8ビットであるという決まりすらないので、こういうコードを書くと変な環境に持って行ったときにはまります。え、変な環境を作る方が悪い？ま、それも一理あります。

ちなみにunsiged charのときは、c >> 7の計算で符号拡張されませんので、c >> 7が -1 or 0になって欲しいはずが1 or 0になってしまい、retが減算されてしまいます。すると正負が逆になってしまって、結果netcatは引数がねーよ、と判断してしまうわけです。こんなことになるくらいならいっそsigned charなんて使わずにunsigned charを使った処理の方が感覚的にわかりやすいと思うのは私だけでしょうか？
GNUの中の人も変わってるわねえ。

まとめるとGNU netcatはchar = signed charと仮定した処理が入っていたので、char = unsigned charの環境に持って行くとおかしくなりますよ、って話でした。

それにしてもコンパイラ作者、GNUの中の人と、世の中にはひねくれ者が多いですなあ…。プログラムに限らず何事をやるにしても変な思いこみをしないように気をつけたいものです。

（※）FreeBSDやDebian GNU/Linuxは違うnetcatを使っているようです。GNU netcatを採用しているディストリビューションは少ないと思われます。

脆いもんだ

朝出かけるときに靴を履こうとしたら、バシっと乾いた音がして靴べらがへし折れました。なぜ忙いでいるときに折れるのか…。

折れた靴べら

元々短かったんじゃないか？ってくらいに真っ二つに割れていますね。まあ、百均の安物だったんだけどさ、さすがに半年も持たないというのは短すぎやしないかなあ。

Google一押し

何気なくGoogle Mapsで「鳥取県」と検索したら、以下のような結果が出てきました。Googleからすると、鳥取の高速バスってのはそんな一押しなのか？

「鳥取県」の検索結果

他の県を片っ端から入力してみたのですが、検索結果が出てきたのは「青森県」だけで、他には一つも出てきません。「青森県」に何を求めたのか知りませんが、やたらたくさん登録されています。

ちなみに青森の検索結果は以下のようになっておりました。全国広しと言えども「青森県」の充実っぷりには敵いませんよ！

「青森県」の検索結果

Google Mapsの「お店やサービスを検索」で頻繁に指定された単語が出ているのでしょう。しかし「鳥取」と「高速バス」がそんな頻繁に指定されているかと考えると、かなり微妙だと思います。

恐らくこの機能の利用者が少なくてうまく抽出できていないか、この機能が正常に動作してないか…だと思うんですが。とにかく変ですよね。

一日の約半分は会社で出来ています

会社の話は書いちゃいけないし、日曜日の話を書いて埋めておこう。まだ今日が始まって2時間も経ってないですが、気にせず書いてしまいましょう。

いつも誰かに見られている気がする

榮樂君のお兄さんの日記を見ていたらコンビニの話をしていたので、コンビニ経験者としてはコメントせざるにはいられない。でも恐らくこっちのことなんか知らないだろうから「通りすがり」って名前でコメントしてみました。

さっき日記見てたら、丁寧にコメントの返事が書かれておりましたけど、よく考えたらいきなり知らん奴がコメントしてきてびっくりしたのではなかろうか？まあ、今更言っても遅いですけど…。

君は病んでいる

全く話は変わりますが、上の日記のタイトル「いつも誰かに〜」ってのは、筑波大学に入るときに「心が病んでませんかテスト」（名前忘れたんで勝手に命名）にあった質問です。

他にも「ときどき死にたくなる」とか「生活にやる気を感じない」みたいなストレートすぎる質問が満載で、不覚にも笑ってしまった記憶があります。ちなみに質問にいくつか○をつけると、ホケカンだか病院だかに連れて行かれると噂になっておりました。誰かやった人いるかなあ？

私しか使っちゃダメなんだからね

以前Googleが検索するという意味で「ググる（google something）」と言わないでくれなんて声明を出していました。世論は、せっかくGoogleというブランド名が定着したのに、なぜ邪魔するの？Googleだって嬉しいくせに！！という意見が見受けられました。

しかし実際は全く逆でして、Googleは全く嬉しくありません。一般の単語にされるとむしろGoogleは迷惑なのです。これはGoogleという商標（登録 第4478963号、国際登録番号881006）が何のためにあるのかを考えるとわかります。

商標とは「商品やサービスを見分けるための標識を独占的に使用できる権利」です。Googleという商標が付いていれば「これはGoogle社が提供していて、他の何者でもない」、「Google社の提供する品質を持っている」という点が容易に理解できます。

その役目を果たすためには、Googleという標識はGoogle社しか使えないようにしなければなりません。もし無断で商標を使用する者がいれば、Google社はその会社を訴えて、使用をやめさせることができるのです。

有名になりすぎると損をする

商標は有名になってなんぼ（同様に自社の商品も有名であることを意味するから）ですが、あまりに広まりすぎて一般の単語と同様になってしまうと、商標が取り消されたり、期間を延期できなくなります（商標法 第46条、第47条）。これは商標法 第3条1.（※）の6. にある「需要者が何人かの業務に係る商品又は役務であることを認識することができない商標」に該当するため、でしょうか？ちょっと自信ないです。

例えば、全ての英語辞書に「google = （インターネットで）何かを検索する」という意味で載ったとすると、googleはsearchやfindと同様の普通の単語になってしまいます。つまり一般動詞になってしまったわけです。

一般動詞になれば、利用者がGoogleという単語を見ても「検索する」という意味しか浮かばず、Google社のサービスであることが認識できません。
「え、GoogleってGoogle社の提供するサービスなの？」
と言われるようでは、もはやGoogleという商標が、商標の役目を果たしていない状態と言えます。されば取り消されて当然と言えます。

お前だけ儲けたら面白くないんだよな

よくわからん、っつう人はGoogleを「検索」あるいはもっとわかりやすく「飴」に置き換えるとわかりやすいです。

「飴」という商標を許せば、「飴」を使えるのは世の中で一社だけになります。これは一般の単語の利用を禁止するのとほぼ同様です。「飴」だけならまだしも、他の会社も同様に一般単語を登録し始めれば、そのうち商品に使える一般単語はなくなってしまいます。

法律は社会の維持のためにあるものですから、上記のように社会のバランスを崩す状況に陥る状況を許しません。そのためには一般単語（またはそうみなされるもの）は使えないようにするのが自然、ということですね。

取り消されちゃたまらねえ

というわけで、あまりに有名になりすぎてGoogleが商標を取り消されてしまえば、Google社はgoogle以外のブランドを新たに立ち上げなければならなくなります。また、他社からgoogleなんとかが山のように出てきて、自社の製品が埋没し、大損することは請け合いです。

だからGoogle社は必死になって一般動詞化を阻止しているのです。

ホッチキスは一般名詞

いやいや、そんなこと心配するだけ無駄、って思いますか？でも実際にあるんですよ。

例えば、株式会社イトーキの「ホッチキス」です。かつてはイトーキの登録商標だったそうですが、現在は登録商標に存在しません。N○Kみたいにわざわざステープラーって言い直してる人が居ますが、んなことしなくて良いんです。

ちなみに現在、ホッチキス風の商標は、マックス株式会社の「HOTCHKISS」（紙綴り器）か、キヤノン株式会社の「ホッチキス」（理化学機器、その他）のみです。マックスはまだしも、キヤノンのホッチキスって何に使うのかな…。

（※）商標法（第3条の1.）
自己の業務に係る商品又は役務について使用をする商標については、次に掲げる商標を除き、商標登録を受けることができる。
1．その商品又は役務の普通名称を普通に用いられる方法で表示する標章のみからなる商標
2．その商品又は役務について慣用されている商標
3．その商品の産地、販売地、品質、原材料、効能、用途、数量、形状（包装の形状を含む。）、価格若しくは生産若しくは使用の方法若しくは時期又はその役務の提供の場所、質、提供の用に供する物、効能、用途、数量、態様、価格若しくは提供の方法若しくは時期を普通に用いられる方法で表示する標章のみからなる商標
4．ありふれた氏又は名称を普通に用いられる方法で表示する標章のみからなる商標
5．極めて簡単で、かつ、ありふれた標章のみからなる商標
6．前各号に掲げるもののほか、需要者が何人かの業務に係る商品又は役務であることを認識することができない商標
（以下略）

買い物1、ジョーシン

万歩計を買いました。会社から帰ってくる途中で、自分は一日に何歩歩いているのかが気になったのです。色々種類がありましたが、数日間の歩数メモリ機能があるものを選んだら、なんと3,000円もしました。どれだけ使うかも分からないのに高い買い物でしたね…。

さて、会社の中で歩く分は知れてる（10分は歩かないと意味があまりないらしい）ので、通勤カバンに放り込んでおいて、メモリした歩数（一週間分）を後で記録しようと思います。買って良かったと思えるように役立てていかないとなあ。

買い物2、ニトリ

久しぶりに車でお出かけ、同期の友人とぶらぶらしてきました。

まずはニトリで低反発クッションを買いました。寮の部屋にある椅子は、どうもイマイチなのでこれで少しはましになるはず。

と期待して現在使っておりますが、ずっと座っているとクッションが自分の尻の形に変形してしまうので、直接座っているのと何が違うのかよくわからないです…。

買い物3、マイカル

茨城のマイカルに行って、革靴と普段用の靴を買いました。

革靴は2足あるんですけど、一方は足に合わないのか足が痛くなるのであまり好きじゃないです。で、いつも同じ靴ばかり履いていたらわずか半年でかなりボロっちくなってしまいました。とほほ。

そういえば、革靴の会計をしていたら突然箱がぶっ壊れました。それに気づいた店員さんが
「すぐに新しい箱と取り替えます」
って言うんで、でも、自分用だから箱なんてどうでもいいやと思って、
「テープでくっつけるだけでいいですよ」
と言ったら、テープでくっつけた後、靴の手入れクリームをオマケしてくれました。うーん、そんなつもりじゃなかったんですけど…なんか悪いな。

タモリがいる

後は同じくマイカルにて映画HEROを見ました。いまさら見るのかという気もしますが、面白かったので結果オーライです。

ドラマを見ていなかった（or完全に忘れている）ために、HERO = キムタクが検事のドラマ、という程度の認識しかありません。さすがにそんな状態だと、この人は誰？って場面がちらほらあります。

とはいえ映画の内容を理解するには影響ありません。ドラマ発の映画ってドラマを見ない人は置いてきぼり、というイメージでしたが、HEROはそんなことないです。良くできてます。

去り際鮮やか

いつのまにかWindows XPのログオフ、シャットダウンが異常に遅くなってしまって困っていたのですが、そんな悩みを解決するUser Profile Hive Cleanup Service(ダウンロード) というツールがあると知りました。

早速使ってみたところ、確かに速くなります。Shift + シャットダウンのスピードには及びませんが、いつもの何かのタイムアウトを待っているような時間（その間、ディスクアクセスが止まったまま）がなくなります。

あえて気になる点を挙げれば、変なドライバ（%sysdir%\drivers\uphcleanhlp.sys）をインストールすることくらいかな。カーネル内部の値でもいじっているのかな？

良き羊飼い（Shepherd）

大下さんが京都に来ているそうなので、晩ご飯を一緒に食べました。その後は映画The Good Shepherdを見ました。

第二次大戦から冷戦までを題材にし、CIAができるまでを追ったスパイ物の映画です。スパイ物といっても 007みたいな派手なアクションはないのでとっても地味な映画です。出てくるオッサンどもはほとんど動かないので、表情の渋さとか、仕草の格好良さとか…その辺を見てました。

まあ007のような目立つスパイは居ないと思うので、実際のスパイはこんな感じなんだろうな。

映画の構成なんですが、時間が進んだり戻ったりしながら話が進んでいくので非常にわかりづらいです。きちんと見るならDVDで借りて何度も見た方が良いかもしれません。

あとは…映画のタイトルがいまいち意味わからないです。主人公のエドワードがCIAの幹部で、Shepherd = 羊飼いだとすると。彼はたくさんの羊をあやつる優秀な羊飼い（民衆が「羊」？）って意味ですかね？英語はわからんなー。

初仕事

今日は職場赴任でした。どういう仕事をしている部署なのかという説明を受けて、PCのセットアップをして。後は、読んでまとめて発表してね、と渡された英語の本を読んでたくらいで終わりました。

富山みやげを持って行ったら、チームのほとんどの人が出張中で居なくて渡せなかった…。PCをセットアップしようとしたら、HDDがぶっ壊れててカコンカコン言ってた…。うーむ、幸先悪い感じだな。

それはさておき、英語の本を読んでいると輪講を思い出すなあ。まあ、輪講の本よりは読みやすいかなあ…。内容はリアルタイムスケジューリングの話で、有名な本らしいのでたぶんAmazonあたりで売っていると思います。

その判断が難しい

当サイトのCSSをちょろっと書き換えました。といってもデフォルトのサイズで見ている人にはほとんど影響ないはずです。

このサイトでは今まで、枠と中身の隙間（margin）や、枠とその外の枠の隙間（padding）といったサイズを指定する際に、基本フォントサイズとの相対値（em）を用いていました。しかしそのような指定をすると、文字を巨大化させたときに枠の隙間まででかくなって文字が追いやられてしまう現象が発生します。右側の欄も細いためか、字が入り切らなくて読みづらくなります。

今回は暫定措置として、日記を囲んでいる枠のmarginとpaddingを20pxに変えました。多少はましになったかと思います。

そんな馬鹿でかい文字で見ないでしょ？なんて思われるかも知れませんが、このサイトのデフォルト文字サイズだと「小さすぎて全然見えねえよ！」って人も世の中には居るんです。

こんなへっぽこサイトだったらさほど気にしなくて良いんですが、大勢の人が見るページを作るときは、字を画像にするとか、文字の大きさを固定するなんて愚行をやらないようお願いしたいですね（特にデザイナーさん）。

お気の毒ですが冒険の書1は消えてしまいました

以前の日記（2007年10月14日の日記）で書いたパーサを間違って消してしまいました。パーサがなくなったのは惜しいというか、書き直すのがめんどくさいというか。

肝心の処理である「パース後の分類」がうまくいってなかったのが、せめてもの救いかなあ。これに関してはなかなか良いアイデアが出てこない状態です。

パース部分も次はもう少しましな書き方ができるかもしれないなあ、と思うので、またやる気が出たらチャレンジだな。

それはソニー

昨日か今日くらいから、マイカーの保険がソニー損保に切り替わりました。別に裏切りではありませんよ…。会社の保険がどうなってるのか調べきれず、契約に踏み切れなかったのです。ま、来年までには調べて、安い方に替えますよ。

彼氏彼女の事情

ってタイトルのマンガがありました。高校時代に読んだっけか。面白かったような記憶があるけど、良く覚えていない。

工場での実習も終わったって事で、同期の人とプチ飲み会をしました。寮にいる面々だったので近場の店です。

ただ、昨日付で終わったのは一部の人であって、半導体の製造技術（プロセス）に近い人たちは、年末まで工場実習が続くそうですがね…。

同期の一人に彼女が出来たとか。宴会中しばし惚気ている彼を、周囲は生暖かい目で見守っておりました。実に幸せそうです。そして宴会途中で「彼女に会う。」と言って、彼は帰ってしまいました。こりゃかなりご執心ですな。