コグノスケ

何を補うの？

毎回話題がバラバラな日記ですみません。今日は補数の話です。

N進数の補数は2つあります。Nの補数と、N-1の補数です。10進数ならば10の補数と10-1の補数（9の補数ともいう）があります。

N進数における二つの補数

あるN進数xの Nの補数yとは、足すと桁上がりする最小の数値を指します。
10進数でいきますと、x = 123だとしたら、10の補数は足すと桁上がり（1,000になる）する最小の数値ですから877です。

要するにy = 1,000 - x = 1,000 - 123 = 877と計算します。4桁の数字なら10,000から引けばいいですし、5桁なら100,000から、n桁なら10^(n) から引いてください。

あるN進数xの N-1の補数zとは、足しても桁上がりしない最大の数値を指します。
また10進数を例に取ると、x = 123として、10-1の補数は足しても桁上がり（1,000）に達しない最大の数ですから、876です。足すと999になります。

これも要するにz = (1,000 - 1) - x = 999 - x = 876と計算します。特徴として、10の補数から1引いても得られますし、逆に10-1の補数に1を加えると10の補数になります（この性質は後ほど重要です）。

補数の活用方法

Nの補数は何が嬉しいかというと「負の数の表現として使えば、引き算が不要になる」という点です。

3桁の10進数500 - 300を計算したいとします。「引き算は知らないが3桁の足し算と10の補数を書いた表だけ持ってる」と仮定します。むちゃくちゃに見えますけど、後で意味が分かると思います。

引き算は知りませんので、まずは負の数を消しにかかります。負の数は絶対値の補数に置き換えて消します。表を見ると300の10の補数は700（計算で出すなら1,000 - 300）ですから、
500 - 300 = 500 + 700
こう置き換えます。すると足し算のみになって、計算できるようになります。
500 + 700 = 1,200
4桁目が出てきてしまいましたが、3桁の足し算しか知らんので4桁目は捨てます。さようなら〜。
1,200 => 200
この結果は500 - 300 = 200の結果と一致します。

不思議に見えますが、そもそも補数yの定義がy = 1,000 - xなので、x = 300で式を展開すると、
500 + (1,000 - 300) = 1,200 --(4桁目無視)--> 200
となるのは当たり前といわれれば当たり前の結果です。しつこいですが大事なポイントは「引き算が足し算に化ける」という点です。

2進数だと非常に嬉しい

とはいえ、10進数だと補数を計算するために結局引き算が必要で、ありがたみがありません。これはその他の記数法（図では3進数を例とした）でも同じです。

3進数と3の補数、3-1の補数

ところが2進数となると非常に嬉しい性質があります。以下の図を見てください。

2進数と2の補数、2-1の補数

2進数においては全桁を反転させる演算（Not演算）によって、容易に2-1の補数を得ることができ、そこに1加えれば2の補数を得ることができます。つまりNot演算さえあれば2の補数の導出に引き算は不要です。コンピュータだからこそできる技といえましょう。

この性質のためコンピュータに減算器は不要で（※）、加算器の前にNot演算と1加える回路をつけるだけで良いのです。回路が少なくなればコンピュータも安くなります。いやあ、補数って素晴らしいですね。

（※）コンピュータは前章の説明に出てきた「引き算は知らないが3桁の足し算と10の補数を書いた表だけ持ってる」の代表格です。コンピュータの場合2進数を扱うため10の補数ではなく2の補数です。
まとめると「一定桁（32桁、64桁など）の足し算と、2の補数しか知らない」変な奴と言えます。本当は意図的にそう作っていると言った方が正しいですけど…。

負の数を解釈

補数を負の数として扱うと良いこと（減算がなくなる）があるのは分かっていただけたかとおもいます。残る問題はどこからを負の数と見なすかです。卑近な例で言うとprintfしたときに、どこからマイナスなのよ？って話です。

前章まで話してきた計算の問題と関係ありそうに見えますが、実は全然関係ありません。ぶっちゃけた話、どこから負の数と見なしても構いません。以下の図をご覧下さい。

2進数から10進数へ解釈する一方法

この図にある解釈方法ですと2進数の101以上を負の数と見なします。

• 101未満の数を表示しなさいと言われたら、そのまま10進数に変換した値を印字します。
• 101以上の数を表示しなさいと言われたら、補数をとって10進数に変換した値と、マイナスの符号をともに印字します。

何？ずれてる？いやいや…。このような解釈でも使っている人がウンと言えばそれで良いんです。とはいったものの、この方式ではウンと言う人は少なそうです。この方式は欠点が多すぎます。

桁が増えたときに正負の境界をどう決めるかがあいまいであるがために、境界を見分ける処理が複雑になる可能性があります。プログラマや回路設計者に嫌われますね。それとやたら正の数ばかりが多くて、負の数を使いたい人にも嫌われます。

良い解釈方法はあるか

多くの方が見慣れたパターンは、最上位のビットが1なら負の数と見なす、以下のような解釈方法でしょう。

2進数から10進数へ解釈する効率的な方法

この解釈方法が採用されている理由は、効率的だからだと思われます。この解釈方法であれば、何桁になろうとも「最上位ビットの有無」という同じルールが適用できます。さらに正の数の範囲と負の数の範囲がほぼ同じ（負の数の範囲が1広いけど）で使いやすいのです。

Linuxのページテーブルが見当たらないときがある

目次: Linux

Linuxのページディレクトリを見ていると0xc000 0000以降（※）はページディレクトリエントリがあるのに、その先のページテーブルがありません。なぜこれで動くんでしょう？

調べてみると、なるほど、トリックがありました。

LinuxはCR4のPSEビット（Page Size Extension、ビット4）を1にして、4MB/4KBどちらのサイズでも使えるようにしています。

確かめ方は、右Alt + ScrLockを押してレジスタダンプすると簡単でしょうか？以下のようなメッセージが出るはずです。Pentium Proから導入されているはずですので、未対応というのはそうそうないかと…。

Pid: 0, comm:              swapper
EIP: 0060:[<c01019bd>] CPU: 0
EIP is at default_idle+0x31/0x59
 EFLAGS: 00010246    Not tainted  (2.6.18-6-486 #1)
EAX: 00000000 EBX: 00000800 ECX: c1101040 EDX: c030e000
ESI: 00099100 EDI: c0302800 EBP: 003a7007 DS: 007b ES: 007b
CR0: 8005003b CR2: c02bd7f4 CR3: 07175000 CR4: 00000690
 [<c0101a1c>] cpu_idle+0x37/0x4c
 [<c03105fa>] start_kernel+0x270/0x272

肝心なのはCR4レジスタの値です。CR4レジスタが0x0000 0690、2進数だと0110 1001 0000ですから、ビット4（ビット0から数えるので、右から5番目）のPSEビットが1になっていることが分かります。

（※）カーネルが使うリニアアドレス用のマッピングで、物理メモリ先頭896MB分を仮想アドレス0xc000 0000へマップしています。
物理: 0x0000 0000 .... 0x37ff ffff
リニア: 0xc000 0000 .... 0xf7ff ffff
というマッピングです。

二種類のページ

じゃあ4MBと4KBの区別はどこでやってるのさ？というと、ページディレクトリテーブルの要素である、ページディレクトリエントリでやっています。インテルのマニュアルによれば、ページディレクトリエントリの構成は以下のようになっています。

32ビットx86のページディレクトリエントリ

細かい説明は後述しますが、PSビット（Page Size、ビット7）が1になっていれば4MBのページを指し、0ならば4KBのページを使うことを意味します。

128MBの実メモリを割り当てた仮想マシン上でLinuxを起動して、適当なプロセスのページテーブルをダンプしてみると、768要素目から以下のようなページディレクトリエントリが見受けられます。

128MBしか実メモリがないので、768〜799番目（4MB x 32ページ）までしか値が埋まりません。余った800番目以降は別の用途に使われます。

  768: 0x000001e3, 0x004001e3, 0x008001e3, 0x00c001e3, 
  772: 0x010001e3, 0x014001e3, 0x018001e3, 0x01c001e3, 
  776: 0x020001e3, 0x024001e3, 0x028001e3, 0x02c001e3, 
  780: 0x030001e3, 0x034001e3, 0x038001e3, 0x03c001e3, 
  784: 0x040001e3, 0x044001e3, 0x048001e3, 0x04c001e3, 
  788: 0x050001e3, 0x054001e3, 0x058001e3, 0x05c001e3, 
  792: 0x060001e3, 0x064001e3, 0x068001e3, 0x06c001e3, 
  796: 0x070001e3, 0x074001e3, 0x078001e3, 0x07c001e3, 
  800: 0x00000000, 0x00000000, 0x07baf067, 0x00000000, 

772番目を例に取ると、0xc100 0000〜0xc13f ffffの4MB分のアドレスをマップしています。0x010001e3は2進数だと0001 0000 0000 0000 0001 1110 0011ですので、先ほどの図に当てはめてみると、

ビット0: P（存在）: 1

4KBページの時はページテーブルがロードされていることを表します。4MBページの場合はページが存在していることを表します。

ビット1: R/W（読み取り/書き込み）: 1

0は読み取り専用、1なら書き込み可能であることを表します。
CR0のWPビット（書き込み保護、ビット16）を1にすると、スーパバイザからユーザの書き込み禁止ページに書き込んだときに、ページフォルト例外が発生するようになります。コピーオンライト機能の実現に役立ちます。

• ページテーブルエントリEAが指すページAをコピーせよという命令に対し、実際はコピーせず、エントリEAを読み取り専用にし、さらに同じページを指すエントリEBを読み取り専用で作ります。
• 読み取り時
  • エントリEAの指すページAへの読み取りは今まで通りです。
  • エントリEBは書き込みがない限りページAと同じ内容なので、読み取りだけならばエントリの指すページを変更する必要はありません。
• 書き込み時
  • エントリEAの指すページAに書き込もうとすると、ページフォルト例外を発生させてページをコピーし、ページA' を作ります（書き込み時のコピー、コピーオンライト、COWとも）。
    以降はエントリEAは書き込み可能、指す先はページA' です（EA -> A', EB -> A）。
    そうしないとエントリEBが指すページAを使っている人が混乱します。エントリEBを使っている人から見ると、何もしていないのに（エントリEAの指すページAへの書き込み発生時に）勝手にページの内容が変わったように見えます。
  • 同様にエントリEBの指すページAに書き込もうとしても、ページフォルト例外が発生します。そのとき初めてページAの複製、ページBを作ります（コピーオンライト）。
    以降、エントリEBは書き込み可能、指す先はページBに変更されます。(EA -> A, EB -> B)
    ただし既にエントリEAがページAを指していないことが分かっているなら、コピー作業は無駄なのでしません。エントリEBはページAを指したままで、書き込み可能に変更されるだけです（EA -> A', EB -> A）。

ビット2: U/S（ユーザ/スーパバイザ）: 0

0はスーパバイザ用の領域を意味し、1はユーザ/スーパバイザ用の領域を意味します。

ビット3: PWT（ページライトスルー）: 0

0ならページへの書き込み時に、可能ならキャッシュのみを更新（ライトバック方式）します。1にするとキャッシュとメモリを同時に更新（ライトスルー方式）します。PCDが1のときは、そもそもキャッシュを使わないので無意味です。

• CR0のNWビット（非ライトバック、ビット29）が1だと、ライトスルー方式が採用されます。こちらが優先です。
• CR3のPWTビット（ページライトスルー、ビット3）が1だと、ライトスルー方式が採用されます。これはページディレクトリエントリだけのキャッシュ方式に適用されます。

しかしMTRRの設定とも関係します。ライトバックとライトスルーの設定がかち合ったときは、ライトスルーが優先されます。

ビット4: PCD（ページキャッシュ無効）: 0

0にするとページをキャッシュします。1にするとページをキャッシュしなくなります。I/Oメモリなど、キャッシュしても意味がない領域などに使うそうです。

• CR0のCDビット（キャッシュ無効、ビット30）が1だと、メモリに対するキャッシュ全てが無効になります。こちらが優先です。
• CR3のPCDビット（ページキャッシュ無効、ビット4）が1だと、ページ単位のキャッシュは無効になります。これはページディレクトリエントリだけのキャッシュ方式に適用されます。

キャッシュの設定はMTRRの設定とも関係します。ライトバックとライトスルーがかち合ったときは、ライトスルーが優先されます。

ビット5: A（アクセス）: 1

ページ番号が指しているページに読み込み、書き込みがあると1にセットされます。

ビット6: D（ダーティ）: 1

ページ番号が指しているページに書き込みがあると1にセットされます。

ビット7: PS（ページサイズ）: 1

0なら4KBページ、1なら4MBページを表します。ページディレクトリエントリ（一段目のテーブル）だけで有効です。
Linuxではページテーブル（二段目のテーブル）でアクセス権のないページを表すために、Pビットと合わせて使っています（当然CPUは無視します）。P:PS = 0:0なら存在しないページ、P:PS = 0:1ならアクセス権のないページを表します。
（4KBページ、ページテーブルエントリ（二段目のテーブル）のみ）Pentium Pro以降であれば、このビットはPATビットを表します。このビットが1であればPCDおよびPWTの2ビットで4つのメモリ属性（ライトバック、ライトスルー、MTRR優先のキャッシュ無効、MTRR上書きのキャッシュ無効）を表します。このビットが0であれば、従来と同じです。

ビット8: G（グローバル）: 1

0ならTLBフラッシュの時に消されます、1なら消されずにずっと残ります。
CR4のPGEビット（グローバルページ有効、ビット7）を1にしないと意味がありません。

ビット12: PAT（ページ属性テーブル）: 0

（4MBページのみ）0ならPAT機能を無効にして、1ならPAT機能を有効にします。

ビット31-22: ページ番号: 4（0x4）

先頭から16MB（4MB x 4個目）の位置にある4MB分の領域（0x0100 0000〜0x013f ffff）をマップすることを表します。

なぜ使い分けるのか

4MBのページングを使っているのはカーネル用のリニアアドレス（0xc000 0000〜）だけのようです。他のページディレクトリエントリにはPSビットが設定されていません。ページ番号の指す先には、もう一段ページテーブルがあり、その先にやっと4KBのページがあります。

理由ですが、インテルのマニュアルによると4MBと4KBのページは別のTLBに置かれるので、カーネルのように頻繁に使うコードやデータは4MBページに置いておくと、フラッシュされなくて良いよ、ってなことが書いてあります。また、ページサイズが大きければTLBミスも少ないよ、ってな解説もあります。恐らくそんな理由です。

あるプロセスのページディレクトリテーブル

絵にしてみるとこんな感じでしょうか。間違ってるかも…。

サイズはアドレスの範囲を意味するのではなくてテーブル自体の大きさのことです。ページディレクトリテーブル（一段目のテーブル）も、ページテーブル（二段目のテーブル）も 4バイトx 1024要素なので同じ4KBですよ、って言いたかっただけです。

メーデー！メーデー！

今日はメーデーです。そんなことより、エクスプローラのネットワークドライブへの無駄なリトライがすごくイライラする。

あるマシンAでWindowsのネットワークドライブを設定（宛先をBとする）して、接続先であるマシンBを落とすと、当然そのネットワークドライブは使えなくなります。

そこまでは良いのですが、エクスプローラってば使えなくなったネットワークドライブにアクセスしようとすると10秒近くフリーズしてしまいます。TCP SYN+ACK待ちにしては諦めが早すぎるので、NetBIOSでしょうか？

さらに嫌なことに、ネットワークドライブと全く関係ない操作（例：フォーカスを戻す）でも、毎回ネットワークドライブを確認してはフリーズします。もうイライラして仕方ないです。

マシンAを起動した時点でマシンBが死んでいると、ネットワークドライブは切断されている扱いになって、上記の現象は起きません。その後マシンBを起動してもネットワークドライブは切断された扱いのままです。

切断されている状態だとネットワークドライブ上のファイルへのアクセスが軒並み失敗しますので、すぐにわかるかと思います。

しかしエクスプローラからネットワークドライブを見てしまうと再接続処理が走るようで、以降は接続された扱いになります。こうなるともうダメで、マシンBを落とすと上記のフリーズしまくり状態に突入します。

Sambaだとダメ

ネットワークドライブの接続先が Sambaの場合はフリーズ現象が発生します。接続先のマシンを落とすと、ネットワークドライブのプロパティには「ネットワークドライブ：NTFS（または未フォーマットとも）」などと表示されます。

一方で Windows XPの共有ドライブの場合はフリーズ現象が起こりません。接続先のマシンを落とすと、ネットワークドライブのプロパティには「切断されたネットワークドライブ」と表示されます。

どうもSambaはサーバ終了時に、接続中のクライアントに何かを通知すべきなのに、全部すっ飛ばして終了するみたいです。オプションでなんとかならんかなあ…。

原因不明

しかし、いつまでも未練がましく覚えているクライアント側も大概にしてほしいものです。なんとかしてネットワークドライブの記憶を消せないか探ってみました。

まず、以下のコマンドでARPのキャッシュをクリアしました。
arp -d *
しかし症状は変わらず。

次にNetBIOSのホスト名 <-> IPアドレスのキャッシュをクリアしました。
nbtstat -R
やはり直りません。

エクスプローラが何か覚えているのかもと explorer.exeを強制終了させ再起動しましたが、依然として直りません。

残るはSystemプロセス（pid: 4）が覚えている可能性がありますが、確かめる方法がわからんなあ。

黄金ウィーク

うちの会社は5/1と5/2が休みなので、今年のゴールデンウィークは6連休（5/1〜5/6）です。さらに4/29の祝日（昭和の日）を有給休暇（4/30）で繋いで8連休にする人が多いのではないでしょうか。

中には4/28も有給休暇にして 11連休（4/26〜5/6）でイ゛ェアアアア！！という猛者も居ます。

一方、自分は特に予定もなく今日も出社しておりました。普段と違うのは、チームの人が何人か居ないのと、良く知らない仕事（隣のチームの仕事の手伝い）が回ってきたくらいか…。

ちなみに隣のチームは修羅場ってて、ゴールデンウィークなんかねえよｗｗみたいな話をしている方がいました。恐ろしい子…！

一週間以上

ついに一週間更新せずに放置してしまいました。あわてて書き足すも、先週の頭あたりなんてもう覚えてないぜ。

私は正義、貴様を見ているぞ！

先日、JR長岡京駅で発見して以来、気になっていて仕方ないポスターがあります。鉄道警察隊によるちかん防止のポスターです。

せいぎくん

どうみても下手な絵、バラバラで虚ろな瞳、真っ赤な枠、首だけで浮かび「私は見ている 許さない」と決め台詞。「せいぎくん」はちかん被害にあった女性の代弁者なのでしょうか…呪ってやるという雰囲気すら感じます。見れば見るほどに怖いです。

ちなみに発行元が京都府警なので、京都府内の他駅（長岡京駅、以外）でも見かけるかもしれませんね。何、別に見たくない？あ、そう…。

見てるだけなら楽しい

M.U.G.E.Nという格闘ゲームの基盤プログラムがあります。キャラクターやステージを自由に追加でき、市販の格闘ゲームができることがそこそこできてしまう機能性をもっているそうです。（詳しくはWikipediaの M.U.G.E.Nの項をどうぞ）

ニコニコで公開されている MUGENの対戦動画（CPU戦）が面白くて、最近ずっと見ています。

格闘ゲームは見てる限りでは楽しいのですが、実際やると全く勝てずイライラします。コントローラを思い切り投げ飛ばしたくなる。

飲み会

同期の人達と久々に飲み会をしました。どうも仕事の愚痴になっていかんね。酒飲んでいい気分なんだし、もっと前向きな話をした方が良いかもしれんなあ。

いつも使っているお店「とりひめ」のメニューが変わっていました。ピザが小さくなって貧乏くさくなりました。しかしとりひめサラダがVery goooood!! に進化していました。おいしかったので思わず4つ（＠7人）も頼みました。

うまければ何でも良かった。今は反省していない。

やはりそこは社会人

大下さんちに遊びに行きました。金をけちって学生みたいなボロアパートに住んでるんじゃ…なんて思ってたんですけど。

全く心配無用でした。実に立派なお住まいです。部屋こそ前より狭いですが、綺麗だし、駅も近いし、入口もオートロックです。

ただ高い塀と有刺鉄線は、ちとやりすぎ感が拭えませんね。以前に事件が（しかも複数回）起きて、非難に晒されながら付けたか、有刺鉄線が大阪のスタンダードなのか？どちらにせよ、よくわからん街だなあ。