ハッカーのたのしみ

d:20050615:p1 「エンディアン変換（バイト・オーダ反転）」のトラックバック経由で、紹介されていた「ハッカーのたのしみ」 (asin:4434046683) を買って読んでみたら、これが面白い！（NyaRuRuさん、ありがとうございます！） 面白いけど、

本書のアルゴリズムは、なぜそれでよいかが殆んど書いていない。その理由を考えるのももう一つの楽しみである。

（Page.vi「推薦の辞」より） とあって、そこに書かれている式を読み解いていく事を要求される。私は数学が不得意で計算が遅いので 1 ページ読むのに10分位掛かる。しかし、それが面白いので埋没していってしまう。まだ30ページ程度しか進んでいないけど、死にそう。とても恐ろしい魔の書。

Page.20 に PowerPCのニーモニックが挙げられていたので気になって（キャリーを理解していなかったので）展開してみた。

命題

(x < y) のとき -1、 (x = y) のとき 0、 (x > y) のとき 1 となる関数 cmp(x, y) は

(x > y) - (x < y) または (x >= y) - (x <= y)

で表現可能 (条件式が真のとき 1、偽のとき 0) であるが、x, y 共に 0 または正の値の場合、それを以下の PowerPC 4命令（分岐無し）で実装出来る。

subf  R5, Ry, Rx    … (1)
subfc R6, Rx, Ry    … (2)
subfe R7, Ry, Rx    … (3)
subfe R8, R7, R5    … (4)

ニーモニック説明

subfc/subfe 命令は、

subfc rD, rA, rB →  rD = ¬(rA) + rB + 1  = rB - rA
subfe rD, rA, rB →  rD = ¬(rA) + rB + CA = rB - rA + CA - 1

である (¬はビット反転。 -(rA) = ¬(rA) + 1)。 CA はキャリーを表し、最上位ビットがオーバーフローしたときに発生する。この演算では rA は 0または正の値を扱うので、¬(rA) は 負。よって結果 rD が 0 または正の値になったときに発生する。

subfc での CA の値は、

  (rB - rA) >= 0 → (rB >= rA)

subfe では 前回値の CA を使用して演算し、終了後に CA を更新する。

  (rB - rA + CA - 1) >= 0  → ((rB + CA) >= (rA + 1))

PowerPCの命令・ニーモニックについては、http://www.freescale.co.jp/doc.html の「32ビットPowerPCアーキテクチャ　プログラミング環境」（MPCFPE32BJ_R0.pdf）を参照。もしくは、PearPC (http://pearpc.sourceforge.net/) のソース (src/cpu/cpu_jitc_x86/ppc_alu.cc) が参考になる。エミュレータは良い教材だ。

式の証明

上の (1)〜(4) 命令を書き換えると、(CA を ca1, ca2 と分けて記述する)

(1) … R5 = Rx - Ry
(2) … R6 = Ry - Rx
      ca1 = (Ry >= Rx)
(3) … R7 = Rx - Ry + ca1 - 1
      ca2 = (Rx + ca1 >= Ry + 1)
(4) … R8 = R5 - R7 + ca2 - 1,
          = (Rx - Ry) - (Rx - Ry + ca1 - 1) + ca2 - 1
          = ca2 - ca1

Rx > Ry のとき、ca1 = 0 なので、
  ca2 = (Rx >= Ry + 1) 
Rx と Ry が 1 の差でも等式が成り立つので、 
  ca2 = (Rx > Ry)
Rx <= Ry のとき, ca1 = 1 なので、
  ca2 = (Rx >= Ry)
よって、ca1 の値 (Rx と Ry の関係) に関わらず、
  ca2 = (Rx >= Ry)
は成立する。したがって、
  R8 = (Rx >= Ry) - (Rx <= Ry)
になる。

という訳で、4命令は (x >= y) - (x <= y) を表現していることになる。

(ノ｀Д´)ノ彡＝＝＝＝＝＝＝＝＝＝ ┻━┻