パスワードを忘れた? アカウント作成
890275 journal
日記

ttの日記: Thumb2パズル 15

日記 by tt

新UIになって今まで以上におっくうになってたんだけど、余りにも日記を書かないとなんなので…
今苦しんでるパズルのヒントを/.Jの皆様に求めてみたりします。

今をときめくARMアーキテクチャのThumb2モードでは、即値アドレッシングの演算系命令で使える値がかなり限られます(ちなみにARMモードだともっと制限が厳しい)。具体的には以下のどれか。

  1. 8bit値をnビット左シフトしたもの(nは0以上24以下の整数)
  2. 8bit値を0x00010001倍したもの
  3. 8bit値を0x01000100倍したもの
  4. 8bit値を0x01010101倍したもの

加減算に限っては任意の12bit値を使う専用命令があったり、同じ値を加算と減算とか、ビット反転した命令でも使えるので、実質もう少し他の値も使えるのだけれど、まあ基本はこれ。

一方、定数代入はレジスタの上位・下位16bitを設定する命令があるので、2命令の組み合わせで任意の32bit値を設定できます。

ということで、例えば x+0x12345678 みたいな事をしたい場合、

  1. 2命令かけてワーク用のスクラッチレジスタyに0x12345678を代入し、xに足す(3命令)
  2. 何とかして0x12345678を上の定数パターンに分割してがんばる

のどちらかになります。

で、後者の「何とかして」が問題になる。

答えを先に書くと
    0x12345678 = 0x12001200(0x12*0x01000100) + 0x00344000(0xD1*0x4000) + 0x00000478(0x8F*8)
というふうに分割できるので、加算命令3つでx+0x12345678を実現できます。
前者に比べると命令数(=サイクル数)は同じだけど、こちらの方がスクラッチレジスタなしで済む分有利になります。

問題はこういう分割を求めるのが泣きそうに難しいところ。
8ビットずつ4つに分割すれば、つまり0x12345678=0x12000000+0x00340000+0x00005600+0x00000078とすれば確実に再現できるので、4分割すれば絶対に実現できるのは明確。2分割で作れるかどうか、も割と容易に分かる。なのだけど、3分割で作る方法があるかどうかを調べるのが非常に難しい。
現時点で私はブルートフォースで計算する以外の方法が思いつかないでいます。前述の例である0x12345678も総当りで出しました。

ちなみに現状のgccは割とすぐにあきらめて「ワーク用レジスタ使う」になります。
が、時々なぜか0x12000000+0x00340000+0x00005600+0x00000078になることも。ヒドス。

ということで、いい方法思いついた人居たら教えてください。
2分割のときは0x00010001の剰余系で考えると、ってので簡単に実現できたんだけど、3分割だと色々考えたんだけど全然ダメでした。
こういうのに関係する数学の分野名とかあったらそれでもいいです。

更新:20:15コメントにあった疑問を追記しました。

この議論は賞味期限が切れたので、アーカイブ化されています。 新たにコメントを付けることはできません。
typodupeerror

クラックを法規制強化で止められると思ってる奴は頭がおかしい -- あるアレゲ人

読み込み中...