海鳴りのほこらから出た直後のみでてくるという定説を崩せた.
コメント欄をみるにじつは私も出した経験があるが再現方法がわからなかったと書いた人がいたし、twitter でも同じことを書いている別の人がいた.
(再掲) 新しい出し方はステータスの最後に描写する文字を ? にして (=並び末尾に正常なNPCを置く)、海上で1マス進んで敵がでればそれは海鳴りのほこらから出た直後同様 area 1 になる. (そして2マス以上進めばどこでも area 0)
これだと偶然出たがなぜでたのかわからないとなるだろう. 特に area 1 には area 0 と同じしびれくらげとかもいるわけでそっちがでてたら違いはユーザーにはわからない. つまり area 1 は無意識にでてしまうもののレアモンスターにつながった人はわずかだけだったのだろう. ストーリー上、NPCはそんなに利用されない傾向もある. (パノンだけボス戦に重宝されるらしいが、かなりやり込んだ人のみぽい)
ただ、偶然体験した人たちがウソつきではない証拠を示せた.
逆説的に area 2,3 は偶然出た報告もなく仮に実現可能だったとしても普通の操作ではありえない手順で条件を作ることになるだろう.
ファミコンのドラゴンクエスト4の海のモンスターの出現 areaその1
偶然発見した上に発生条件を調べるために記録まで集めたひと.
https://www.youtube.com/watch?v=99LRwL3E86s
さきに解析した人の考察
https://note.com/xyznote/n/ncf3076b8de44
tcrf での解説
https://tcrf.net/Dragon_Warrior_IV_(NES)
PC:$9C81 にある lda $07 がバグでそれをなくすと妥当だと tcrf では記述している. table の data の bit7:6 を海上, bit5:0 を陸上とみなしているのだろう.
このコードを直さない場合は address $0007 の移動前の値の bit7:6 に依存する. 単に2マス以上移動した場合は陸地は and #$3f, 海上は and #$03 によって bit7:6 = 2'b00 になるので area 0 のままになってしまう.
海鳴りのほこらの出口
ここはダンジョンで南への移動で address $0007 = data 0x59 が入る.
よって、出口を出た直後で敵がでると area 1 にできる.
海上
メニューをだした最後の文字が address $0007 に残っている. 最後の文字はパーティの末尾のレベルの値であり、数値の場合は数字2桁に分かれるので1の位の 1 から 0xa, 状態異常は 7 などの小さい値, ? は 0x6d. よって、レベルに ? を表示したあとに1マス進み、敵が出ると area 1 になる.
リバーサイドから出る
ダンジョンとは別の処理のようで data に大きい値は入らず area 0 ばかり.
他に船を利用しながら外のマップに出るという方法が思い当たらない.
area 2 のデータの妥当性
いまのところ正規の手順で出すことは不可能だが、キラースコップ,ダックスビル,リリパットというストーリー序盤の陸地の敵がなぜか出るので本来用意されていたデータか疑問.
クロック近似計算
前回は総当りでやったが連分数を利用してみる.
前回は最初の Rational の使い方が悪かった. Rational の中に float をいれてはいけない.
master = Rational(12288, 1000) dest = Rational(315, 88) divide_by = master / dest
(45056/13125) となる. これを手で計算すると約分が面倒くさい. この場合約数が 3 だけで済んだが、 3 桁の素数で割るとかなると人では簡単にできない.
continued_fraction = []
loop{
v = m.to_i
continued_fraction << v
m -= v
if m.numerator == 0
break
end
m **= -1
}
p continued_fraction[3, 2, 3, 4, 2, 97, 2] となる. 得られた配列を途中まで使って復元すると近似となり、どの桁まで合ってるかは少数表記だと分かりづらいので底が10の対数を出す.
(1..continued_fraction.size).each{|size|
approximate = restore(continued_fraction[0, size])
error = (divide_by - approximate).abs.to_f
error_log = Math::log10(error)
puts "%3.1f #{approximate.to_s}" % error_log
}復元は漸化式を使えみたいな話らしいが Rational に頼めばコードは単純である.
def restore(continued_fraction)
continued_fraction = continued_fraction.reverse
n = Rational(continued_fraction[0], 1)
continued_fraction[1..-1].each{|t|
n = t + n ** -1
}
n
end結果は下記の通り. 前回と分数が逆数になってるが、この後連立方程式に組むときに間違えなければいい話なので気にしないでほしい. 結果としては総当りでも出した 230/67 が精度もかなりよく、次の近似分数がかなり大きいのでやはり適切となった.
-0.4 3/1 -1.2 7/2 -2.4 24/7 -3.3 103/30 -5.6 230/67 -7.9 22413/6529 -Inf 45056/13125
bitswap の 16bit-16bit の実装について
lut を使う場合に 4bit x4 で無難に実装しているんだが 1 bit + 5 bit x3 の実装を試してみたが、これがかなり tricky にわりと早くメモリ消費もそこそこらしいというコードができた.
lea table+0x80,a0 moveq #0x3e,d1 moveq #0,d0 ;output q add.w d2,d2 ;input d #if delta >= 8 roxr.w #16-delta,d0 #elif delta >= 1 roxl.w #delta+1,d0 #else ;delta == 0 addx.w d0,d0 #endif move.w d2,d3 and.w d1,d3 or.w (-0x80,a0,d3.w),d0 lsr.w #5,d2 move.w d2,d3 and.w d1,d3 or.w (-0x40,a0,d3.w),d0 lsr.w #5,d2 and.w d1,d2 or.w (0,a0,d2.w),d0
src 15 to dest:clocks 0: 112 8: 130 1: 118 9: 128 2: 120 10: 126 3: 122 11: 124 4: 124 12: 122 5: 126 13: 120 6: 128 14: 118 7: 130 15: 116
delta は src bit 15 が dest bit 0 からの移動量ということになり、それらの条件で生成する命令や実行時間がことなってくる.
lut へは (d8,an,IX) の addressing で取り込むのだが、68000 は index に scale をつけられない上に 16 bit 単位アクセスなので、通常は index を左循環1回をやってから右循環を繰り返して index を作成することになる.
ここでは左循環1回ではなく左シフト1回相当の add.w d2,d2 を使って src bit 15 を X に追いやる. X を bit0 にいれる場合は addx d0,d0, bit 1 に入れる場合は roxl.w #2,d0, bit 15 に入れる場合は roxr.w #1,d0 となる.
src bit 15 を片付けると index は都合よくズレているので lsr.w で随時 index 作成となる.
src bit 15 に対する dest bit が 7 とか 8 だと循環回数が 8 回になって遅いが addx が使えるのならとても早くてメモリ消費も悪くないというコード.
lut 3 段は他に試作したコードは下記があり 5*2+6 がバランスがよいだろうということになる.
i o step shift clocks elemnts bytes 16 16 16 1 42 0x10000 0x20000 16 16 8*2 9 98 0x200 0x400 16 16 4*4 13 142 0x40 0x80 16 16 4*2+8 9 116 0x120 0x240 16 16 5*2+6 11 122 0x80 0x100 16 16 1+5*3 11+n 112..130 0x60 0xc0 16 16 4+6*2 11 126 0x90 0x120
病気になった
年末から痔です.
音関連のクロックの近似
FPGA で音関連の回路を作ろうとすると master clock が I2S の都合で12.28800 MHz で音源ICが 3.579545 MHz という場合にどう対応するか苦慮する場合がよくある.
12.28800 MHz の clock domain で 3.579545 MHz の device を動かす場合に分周して動かす方法がある. 12.288 / 3.57945 = 3.43... で割り切れないので 3 分周と4分周を混ぜることで平均の周波数を 3.57945 ... に近似することはできる.
分子分母が整数の分数は ruby であれば Rational で作り出すことができる. 3.579... は NTSC の定義では 315.0 / 88 なので下記で精度100%の分数が得られる.
p Rational(315.0/88,12.288)
(8060419787623331/27670116110564328)
こんな桁数が多い値は実用にならないので分子分母ともに3桁ぐらいで総当りで一番の精度を出す.
ratio = target / master best_approx = nil min_error = Float::INFINITY (2..999).each do |denom| numer = (ratio * denom).round approx = Rational(numer, denom) error = (approx.to_f - ratio).abs if error < min_error best_approx = approx min_error = error end end p best_approx
(67/230)
この近似分数の精度は 1.0000007 倍で音源としては悪くないだろう. *1
67 / 230 が意味することは 3 か 4 で分周した 67 周期のうちで 230 master clock があると約 3.579454 MHz になる. 3 と 4 の分周回数はいくつかは中学2年の連立方程式で解ける.
f1: x + y = p f2: (d + 1)*x + d * y = q d: (1/ratio).to_i p: 近似分数の分子 q: 近似分数の分母
d,p,qの定数を展開すると下記になる.
f1: x + y = 67 f2: 4x + 3y = 230
これは連立方程式の練習問題にいかにもありそうな設定で微積や数列などは一切ないが、周期補正の計算で必要な実用的な連立方程式である. 「4グラムのりんごと3グラムのみかんを数量は合わせて67個,合計の重さは230gにするには何個ずつ買えばいいでしょうか」 そんな練習問題に似すぎていて本当にあっているのか確認してしまった.
x = 29, y = 38. つまり4分周を29回, 3分周を38回すると近似された平均周波数が本当に出る. できるだけ均等に4分周と3分周をまぜるほうがよい.
*1:こういう近似とか平均とかを使うので音関連にはオカルトがつきまとうがそれはご容赦いただきたい
ADC 命令のトリック
概要
bit rotation で CPU が1つのレジスタの幅を超えた場合、または 24 bit などの2の累乗の値ではない 8 の倍数では複数の bit rotation 命令を組み合わせて目的を達成することができる. 本説明ではすべて変数は符号なしの扱いでの計算とする. x64 の命令として記載する.
左循環
C r1 r0 |instructions
-----------+-----------
x 7654 3210|
|shl $1,%r0 -> add %r0,%r0
3 7654 210z|
|rcl $1,%r1 -> adc %r1,%r1
7 6543 210z|
|adc $0,%r0
z 6543 2107|
左側の表記の意味
C: carry flag
r1, r0: 4 bit レジスタ, 理解のために少なくしてある
数字: r1, r0 に最初にあった bit 番号. 数値ではない(重要).
z: 数値の 0
x: 未初期化値carry は1つであるものの入力と出力を区別するため命令前後の挙動の理解が極めて重要. 命令に対して行を半分ずらして記載すべきなのだが、単なるテキストではできないので1行ごとに空白を入れている.
- shl $1: r0 が左にずれて, 数値 0 が r0 bit 0 に 入り, 出力の carry に r0 bit3 の値が入る.
- rcl $1: r1 が左にずれて, 入力の carry が r1 bit 0 に入り, 出力 carry に r1 bit 3 の値が入る.
- adc $0: 入力の carry が r0 bit 0 に加算される. r0 bit 0 は shl 命令により数値は 0 なので, 桁上りなく r1 bit 3 の値が入る.
左シフト1回は数値の 2 倍になる特徴があるので add %r0,%r0 に変えても結果は同じ. carry 入力付き左循環1回は2倍+carryとなるので adc %r1,%r1 に変えても結果は同じ.
右循環
C r2 r1 r0 |instructions
----------------+-----------
x xxxx 7654 3210|
|mov %r0,%r2
x 3210 7654 3210|
|ror $1,%r2
0 0321 7654 3210|
|rcr $1,%r1
4 0321 0765 3210|
|rcr $1,%r0
0 0321 0765 4321|
left rotation の後にその値の bit 0 を 変数に取り込みたい場合
これは複数のレジスタをまたがない場合. Cで書くとこうなる.
d = (d << 1) | (d >> (width - 1)); q |= d & mask;
これは mask の値を限定しない場合は関数最後を除き下記のように一時的なレジスタを介す必要がある.
rol $1,%d mov %d,%temp and $mask,%temp or %temp,%q
mask = 1 かつ q の bit 0 = 0 だと保証されている場合は下記のようにして mov, and, or を adc $0 だけで済ますことが可能. また adc $0 により carry flag が更新されるので2度連続複数の変数への代入は不可能.
rol $1,%d adc $0,%q
さらなる条件:
x64 では adc $immediate,%register の addressing mode が存在するが、 adc %register,%register のみの CPU も多い. この場合は rol の実行前に一時的なレジスタへ 0 を代入しておく必要がある. レジスタを 0 に代入した時点で carry flag = 0 になることが大半である.
最後の説明は条件だらけだがつかえるかもしれない.
病気になりがち
年末から年始
12月29日に発熱 → 1月1日に一旦治る → 1月3日に再発熱 → 1月4日(土曜日)に医者にいこうにも1月4日は輪番診療の対象ではなくどこも年始休みでやってなくて、唯一開院の場所にいった所、長蛇の列を見て断念.無駄にタクシーに乗って家に帰るだけという恐ろしく無駄な消費を食らう.
1月半ば
オンボロ団地の階段で倒れている人を見かける. 階段を踏み外したので私が救急車を呼ぶ. オンボロ団地には狭い階段だけで救急隊員は担いで患者を運んでいて、こんな場所はよくないと思う.
2月半ば
朝8時にそろそろ起きるかというタイミングで腰に激痛が走り、救急車を呼ぶ. 小さい尿路結石では鎮痛剤を打って耐えることしかできないと言われる. 昼になっても痛みが取れず入院. 17時ごろ痛みが止まる. 翌朝主治医の話を聞いてから退院.
翌日23時30分ごろ就寝. その1時間後、激痛が再発. また救急車を呼ぶ. 前回は自分は担がれながらも歩いたが、今回は救急隊員に担がれて降りる. 先月見かけた姿も自分もやることになるとは...
救急搬送先ではたまたま主治医が24時間勤務で15時間ぶりの再会. 昨日同様鎮痛剤を打って耐えろというだけで、1時間経っても私は激痛が止まらず主治医はしゃーないから入院ね. といった直後に痛みが止まる. 結石が膀胱に落ちたのを確認して一連のトラブルは終わる.
父親にそろそろ医療保険に入れと言われたので9か月前に一番安いやつに入っていたが、それが適用された. 一番安い保険から金額は足すことにする.
3月頭
同居人とスキーに行く予定が同居人が風邪で中止. 1週間後同居人の症状が自分にもうつり、翌週のスキーも中止. レンタカー屋にキャンセル料を払うことになる.
古いPCゲームソフトとCPU使用率の改善
古いPCゲームソフトとMIDI ファイルの読み込み - narukoの開発メモ
上記の続き.
このプログラムはゲーム起動中に CPU core 1 つを使用率100%にしつづけてしまう. 原因は GDI を利用しており、Windows の API の PeekMessage() を利用した無限ループになっている. これの直し方について最近試して使っている ChatGPT に聞きながら進めてみた.
ChatGPT が教えてくれた OllyDbg 経由でこのゲームを起動して、使用率があがる場面でとりあえず pause すると PeekMessageA() 付近で停まる. 命令を見る分には下記のようになっており、これは基本的な使い方だと思われる.
while(PeekMessageA()){
GetMessageA();
...
}これを下記に書き換える. コンパイラでは while(cond){...} は if(cond) と do{...}while(cond); に分離されているので、コンパイル後の while(cond) を書き換えることになる.
while(wrap_peek_message_a()){
GetMessageA();
}wrap_peek_message_a() を作る.
int __attribute__((stdcall, dllexport))
wrap_peek_message_a(LPMSG m, HWND h, UINT m0, UINT m1, UINT op)
{
const int r = PeekMessageA(m, h, m0, m1, op);
if(r == 0){
Sleep(1);
}
return r;
}このゲームプログラムは Sleep() を使用してない. 本来は WindowsAPI を呼ぶための import table に Sleep() を追加して80386アセンブル命令を埋め込む形を使いたかった. そのやり方がよくわからなかったので、自前で dll を作り(32 bit コンパイラなんて久しぶりに使った)、 exe ファイルを改変するソフト(ChatGPT が教えてくれたもの. よくしらない)を利用して その dll を読むようにして、wrap_peek_message_a() を呼ぶようにする. これらの過程はちょっと変だし、GUIを毎回触る必要があり改めたい.
とりあえずこれで OllyDbg を読み込み問題の CALL PeekMessageA を CALL wrap_peek_message_a にすることで CPU の使用率が大幅に下がることを確認. EXE ファイルも更新して応急措置としての作業は終わりになる.
ABI と Visual C++ 4
筆者はいままで Windows のソフトをバイナリレベルでいじることがなかったので今回はじめて知ったこと. 80386 系の C で作られた関数の呼び出し規約(ABI)は Windows 独自の __stdcall と __fastcall がある. Windows API は __stdcall であり、問題ない. __fastcall は引数にレジスタ ECX と EDX 、残りは stack に push し、 call 後に呼び出した関数側が stack pointer を戻して呼び出し元に戻る (RET xxx).
それでこのバイナリは解析ソフトによると Visual C++ 4 で作られていて、 __fastcall に似ているがレジスタ渡しは ECX のみである.
先述のように CALL をまるまる書き換えてこっちで作った C の関数を実行させる方法が __stdcall の Windows API ではできるが static 関数ではこれが使えなくて困っている. 自作関数を呼び出す場合はやりかたはあるが、自作関数から元のプログラムの関数を呼ぶ場合には最善策が思いつかない.
この件、詳しい方がこれを読んでいたら対策方法を教えてほしい.
応急処置からのちゃんとした処置方法
今回の問題の根本的な理由は PeekMessage を利用した無限ループ以外に GDI ではマシな方法がなかったことである. Windows のソフトの作り方には詳しくないので最悪はいまもマシな方法がない可能性もある. Sleep() をいれるのは悪くはないのだが、最適な部分で再開させているわけではない. このゲームではさほど問題にならないが、スクロールがあるエンディングシーンでは「処理が異様に早くて読めない」から「処理がやや早くティアリングが目立つ」になったのでやはりあまりよくない.
根本的には適切なループ再開条件を解析して適切なタイミングで動作を再開させることにしたい. その他小さい要改善点を直すとなると、先述の ABI の問題なども障害になっている.
