x86 で任意精度整数の演算 (一部) をやってみる
FAT12/FAT16 用のブートローダを書こうとしていたときに気づいた問題。FAT12/16 の最大クラスタ数はそれぞれ 2^12, 2^16 より少し少ない値だが、セクタに関してはそうではない。計算するときには 32 ビットの値でセクタ数を計算し、ディスクからのロード操作を行う必要がある。しかも私はブートローダを 8086 互換命令だけで構成したかったので、ヘタに 32 ビット演算 (や eax とかのレジスタ) を使うわけにもいかない。というわけで、16 ビットの命令だけで必要な演算が賄えるかどうかが鍵だった。必要なのは次の演算だ。
- u32 + u32 -> u32
- u32 - u32 -> u32
- u16 * u16 -> u32
- u32 / u16 -> u32
- u32 % u16 -> u16
最初の 2 つ (加減算) は命令をよく知っていれば特に詰まるところなどない。乗算に関しては mul 命令をそのまま使うだけでこのようになる。ただし最後のふたつ、つまり、32 ビットの値を 16 ビットの値で割ったときの商と剰余に関しては、若干の工夫を必要とする…ように見えた。まぁ最初からやっていこう。
加算/減算
x86 には adc, sbb という命令がある。これは普通に加減算をするだけでなく、キャリー/ボローがある場合に余分に 1 を足す/引く命令だ。*1これを使うことで、多倍長の加減ができる。
; DX:AX <- DX:AX + DI:SI add ax, si adc dx, di ; DX:AX <- DX:AX - DI:SI sub ax, si sbb dx, di
乗算
mul 命令はまさにそのための命令だ。16 ビットの mul 命令は AX * (何か) の演算結果を DX:AX という 32 ビットの値として格納する。つまり…
; DX:AX <- AX * DX mul dx
以上だ。
除算 (商, 剰余)
さて、8086 命令だけを使って u32 / u16 の命令を実装するには、どのように多倍長で計算するかということが重要になる。あれ、x86 の div 命令って u32 / u16 の演算をしなかったっけ? とお気づきの方はかなり頭が良い。しかし、ここには大きな落とし穴がある。念の為に div 命令の主な動作を下に示す。
; div X AX = (DX:AX) / X ; Careful! DX = (DX:AX) % X
ここで注意しておきたいのは、商は 16 ビットに収まらなければならないという点だ。例えば u32 / u16 の計算をして、答えが 0x10000 以上、つまり 16 ビットに収まらない場合については #DE (除算エラー) が発生してしまうのだ。これにより、単純な解は消える。何らかの多倍長演算をしなければならないことは一目瞭然だ。そこで、筆算が参考になるかな、と思い、適当な筆算をメモってみた。*2
; 691 / 7 = 98, 691 % 7 = 5
0 9 8
+---------------
7 | (0) 6 9 1
0
------
6 9
6 3
------
6 1
5 6
------
5お分かりいただけるだろうか。これだけで答えは出たも当然だということを。2 桁の数を引っ張ってきて、それを 1 桁の数で割り、剰余を次に割る 2 桁の数のうちの上位にしたうえで被除数から新たに 1 桁持ってくる。この繰り返しだ。しかも、この原則は 2 進以上なら何でも構わない。10 進数でも、16 進数でも、あるいは 65536 進数や 4294967296 進数でも同じなのだ。*3ただし x86 の div 命令に当てはめると、最初に 2 桁を持ってきてしまった場合に (前述したような) 除算エラーが発生してしまう可能性がある。そのため、最初に持ってくる 2 桁はダミーの 0 を含むことになる。これで商は 16 ビットに収まることが確定する。
次以降は 2 桁 / 1 桁の、一見オーバーフローが発生しそうな演算だが、考えてみてほしい。1 桁毎の商が 10 以上になるのは、どういう場合だ? 上の 10 進数の例で考えるならば、部分的に扱う 2 桁の数が 70 以上になる場合だ。しかし…よく考えてみよう。部分的に扱う 2 桁の数のうち、上位部分は既に行われた演算の剰余だということを。そう、上位からやってくる数は、除数が 7 の場合は 0〜6 しかありえないのだ。下の桁は明らかに、0〜9 だ。つまり、最上位さえ適切に扱ってやれば、後で除算エラーが発生する可能性は消え失せるのだ。
さらに良いお知らせ。div 命令の仕様で、剰余は DX に格納される。しかし、DX というのは次の div 命令において上位 16 ビットとして扱われる値そのものである。つまり、次の桁を「持ってくる」には、AX 部分だけを交換すれば良いのだ。これは効率が良い上に、ブートローダのような小さなプログラムでの実装を容易にする。次のものは実際にブートローダで使うために試験的に実装したものだ。
; (CX:AX) = (AX:CX) / BX, DX = (AX:CX) % BX xor dx, dx ; 31 D2 ; 上位の除算でオーバーフローしないようにする div bx ; F7 F3 ; 上位の部分商と剰余を取る xchg ax, cx ; 91 ; 上位の部分商と下位の桁を交換する div bx ; F7 F3 ; 下位の部分商と剰余 (これは全体の剰余に等しい) を取る
最適化のおかげで、わずか 7 バイトで u32 と u16 の商と剰余が取れている。商 (CX:AX) が元々の被除数 (AX:CX) からひっくり返った配置になるのが気に入らなければ、xchg ax, cx を先頭か末尾に付加して 8 バイト。これだけで全てが間に合う。意外と…小さく済むものだ。
