ttの日記： Thumb2パズル

新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コメントにあった疑問を追記しました。

問題を整理すると

[t-nissie (8647)]

0または255以下の自然数a ₀, ..., a ₂₄, b, c, dによって0xffffffff以下の自然数zを
z=Σa _n2ⁿ + b0x00010001+ c0x01000100 + d0x01010101
と表すとき、a ₀, ..., a ₂₄, b, c, d の０でないものの個数を３個にできるか？
できるとすればその簡単な方法は？

ってことですかね。

--
love && peace && free_software
t-nissie

Re:問題を整理すると

[tt (2867)]

ですです。数学的な問題にするとそうなります。an,b,c,dが自然数で無いといけないのが難しくて挫折してます。 b,c,dの3つが同時に非ゼロになることはない、というのぐらいは簡単に導けたのですが…

逆により一般化して「Xの倍数とYの倍数とZの倍数の組み合わせで作れる数の集合は～」とかも考えたのですが、 当然ながらそっちの方が難しくなって見事に玉砕しました。

--
-- Takehiro TOMINAGA // may the source be with you!

Re:問題を整理すると

[BAK (1020)]

a, b, c, d が整数とかいう格子点の条件があると，整数計画法とかナップサック問題のような NP 困難な話に近づくような気がしないでもない．

ただ，今回の問題は「最適なもの」じゃなくて「格子点を貫く4次元平面」が分かればいいだけだから，また違ってくるのかなぁ．

Re:問題を整理すると

[BAK (1020)]

「格子点」という条件を無視すれば，ニュートン法とかLMS法とか思いつくけれど，解が無いときに発散したり，解があっても極小値に落ち込んで解にたどりつけなかったり．

Re:問題を整理すると

[t-nissie (8647)]

8bit x 3個
0〜24の指数部がだいたい5bit
加算か減算かで3bit
で計32bitだから、だいたい表せるような気がしますが…

最悪、コンパイラはでっかい表を持っておくとか。

--
love && peace && free_software
t-nissie

Re:問題を整理すると

[tt (2867)]

なんですよねー。1-4の各方式で作れる数の種類は(0とかが重複するのですがそいつらを除いて)4000通りちょっとあるし、 足し算・引き算で二倍だと、8000^3ぐらいの組み合わせがあるんで、32bitの空間なんて多分よゆーで埋められるじゃん、 とか思うのですが、どうにも作れない数が(ブルートフォースで探すと)あるわけでして。

やっぱりここはあんちょこ方式(事前計算テーブル)ですかねえ…

--
-- Takehiro TOMINAGA // may the source be with you!

Re:問題を整理すると

[shibuya (17159)]

8bit x 3 となるとtrue color そこから連想されるのは……
文字を色で、香りを形で感じる人たち：「共感覚」と比喩 [wired.jp]
みたいに24bit/32bitを色として、香りとして、音の高さとして認識するニュータイプが新しいことをやってくれる予感が。。。
//　すべてが余談。オフトピにて失礼つかまつる。

答えが先に書いてあるので改良

[Anonymous Coward]

バレルシフタ乗せたらいいんじゃね？

それ以前に

[Anonymous Coward]

1.～4.でどうやって0x00344000(0が1個少なくのはtypoですよね?)と0x00000478が作れるのかさっぱり分かりません。
http://infocenter.arm.com/help/index.jsp?topic=/com.arm.doc.dui0204ij/... [arm.com]
によると、加算命令では任意の12bit値が使えるとのことなので0x00000478については解決しましたが、
0x00344000はやっぱりわかりません。

Re:それ以前に

[t-nissie (8647)]

0x344000=0xd1 * 0x4000
0x478=0x8f * 0x8
では。
0x4000と0x8はそれぞれ2^14と2^3。

--
love && peace && free_software
t-nissie

Re:それ以前に

[tt (2867)]

そのとおりでございます。元日記も修正＆追記しておきました。

--
-- Takehiro TOMINAGA // may the source be with you!

問題がわからない

[Anonymous Coward]

11ビット毎に割るんじゃなぜだめなの？

Re:問題がわからない

[tt (2867)]

そういう分かりやすい命令セットにして欲しかったですよまじで(笑)。MIPS32/64だと16bit値は即値アドレッシング可能、 それ以上は代入命令を使って32bit値を作って使え、というので悩むことなく綺麗に分かれるし、 i386だとどんな値でも即値アドレッシングできるので楽だったんですが…

まーどうせこんなのアセンブラで一命令削るのに命をかける様な時にしか関係ないんで、どーでもいーじゃんという説もあるんですけどね。

--
-- Takehiro TOMINAGA // may the source be with you!

Re:問題がわからない

[t-nissie (8647)]

「8bit値」じゃなくなるからじゃね？

--
love && peace && free_software
t-nissie

もとの質問にもどると

[Anonymous Coward]

ガロワ（ガロア）の群論あたりから触れるといいんでしょうね。でもこのぐらいの規模だったら、しらみつぶしの方が速いと思うし、それ以前に自然に計算した方が速いと思う。