IMULで整数の割り算を実現する

  • (by K, 2019.09.17)

(1)

  • gccが生成したアセンブラを見ていたら、EAXに入っている値を40で割るときに、
    SAR EAX,3
    IMUL EAX,EAX,0xcccccccd
  • という見慣れないコードを生成していた。何だこれは?
  • でも確かにこの方法で、40での割り算が実現できている。
  • これは面白いと思ったので、ちょっと探求してみたい。

(2)

  • まず5での割り算をIMULでやる方法を考えてみる。ここで仮定としては、EAXには5の倍数以外は入っていないとする。
    5 * 0x33333333 = 0x0:ffffffff  失敗(-1/5倍)
    5 * 0x33333334 = 0x1:00000004  失敗(+4/5倍)
    5 * 0x66666666 = 0x1:fffffffe  失敗(-2/5倍)
    5 * 0x66666667 = 0x2:00000003  失敗(+3/5倍)
    5 * 0x99999999 = 0x2:fffffffd  失敗(-3/5倍)
    5 * 0x9999999a = 0x3:00000002  失敗(+2/5倍)
    5 * 0xcccccccc = 0x3:fffffffc  失敗(-4/5倍)
    5 * 0xcccccccd = 0x4:00000001  成功(+1/5倍)
    • [Q]この0x33333333とかはどうやって思いついたの?
    • [A]ええと、0x100000001を5で割ってみただけです。0x200000001を5で割ったら0x66666666が出ます。
  • なるほどこういう仕組みなのかー。逆に言うと、-5で割りたいときは、0x33333333を掛け算すればいいということか。
  • 他の数値はどうだろう。主要な値を調べてみた。
    3 * 0x55555555 = 0x0:ffffffff (-1/3倍)
    3 * 0xaaaaaaab = 0x2:00000001 (+1/3倍)
    7 * 0x49249249 = 0x1:ffffffff (-1/7倍)
    7 * 0xb6db6db7 = 0x5:00000001 (+1/7倍)
  • こうしてみると、その気になれば大抵の奇数は逆数もどきが作れそうな感じだ。

(3)

  • では偶数ではどうだろう?
    6 * 0x2aaaaaaa = 0x0:fffffffc (-4/6倍)
    6 * 0x2aaaaaab = 0x1:00000002 (+2/6倍)
    6 * 0x55555555 = 0x1:fffffffe (-2/6倍)
    6 * 0x55555556 = 0x2:00000004 (+4/6倍)
    6 * 0xaaaaaaaa = 0x3:fffffffc (-4/6倍)
    6 * 0xaaaaaaab = 0x4:00000002 (+2/6倍)
  • どうやら、1/6倍や-1/6倍というのはできないようだ。
  • だから40で割るときも、まずは8で割っていたのか・・・。

(4)

  • ここをみると、ターゲットが倍数ではない場合でさえ、乗算とシフトでDIVを回避しているように見える。
  • うーん、まだまだ奥が深い・・・。

こめんと欄


コメントお名前NameLink

リロード   新規 編集 差分 添付   トップ 一覧 検索 最終更新 バックアップ   ヘルプ   最終更新のRSS
Last-modified: 2019-09-17 (火) 12:12:39 (65d)