ホイミテーブル技術解説！

この記事はホイミテーブルの技術解説です。
知ってることを全部アウトプットするつもりで書いていきます
簡単で
す！

記事まとめ
https://daisukedaisuke.hatenablog.com/entry/2024/04/29/115453

Cテーブル(概要)

動画で触れれるように先にCテーブルについて少しだけ触れます

Cテーブルの乱数アルゴリズムは64bit LGCで、ゲームではBと全く同じコードでパーセントを計算しています。
Cテーブルの初期シード戦闘が始まる暗転辺りで生成され、フレーム事に変化します。
初期シードは28bitでおおよそ 2.6億通り。 符号なし32bitの最大値である42億通り。時間が経過すればするほど桁が増える。
0xffff(ソフトウェアタイマー)ffff(cpuのハードウェアタイマー)
例: 0x588 4952
また、戦闘アニメーション中のフリーカメラの乱数としても使用されています。。
コマンド選択フェーズでシード値が無駄消費されることはないため、 (敵の行動決定は1フレーム目なので) 行動順乱数が先、素早さに0.51～1の数値をかけてソート。この時点でどんなコマンド選択しようが既にボスの行動は決まっているはずです。
これは、エミュレータのステートセーブで何回ロードしても常に同じ行動をとる現象で証明できます

(コマンド決定後の消費とモーション中の消費以外消費が発生しない)

初回の強制戦闘関して、初期シード生成アルゴリズムはA, B, C全て共通なので、メッセージ送り操作の速さや、初回戦闘は処理落ちによりますがある程度絞られている(数百種類)と推測できます(多分)
戦闘中、Aテーブルは戦闘モーションで消費するので、毒消し草やスライムゼリーが頻繁に落ちるのも似たような乱数を引いている証拠と断言して良さそうです。

Q. 内部的な数字はどこから取得したのですか

A.
動作中の特定の場所にテーブルが保存されており、動作中のメモリの内容を全てダンプして、そのダンプファイルをプログラムで読み取ることで内部的な数字を取得します。
私がダンプしたメモリファイルは現在2GBです
(エンカウントテーブルとかを作る時にまとめてデータを取れるので保管しています。生のバイナリの配布はできません。処理後のデータなら配布できます)
例えば、お供のデータは(0x020FDBCC + n * 0x4c) + N * 4 + 0x34に下記の形式で保存されています
4バイト事で、最大6個です。
上記の式で、日中のテーブルと夜のテーブルなどがある場合に、nが2以上になります

020FDC00		84 F0 08 00 6C D0 08 00 53 D0 08 00 03 90 04 00 	....l...S.......
020FDC10		08 F0 08 00 1F D0 08 00 00 00 00 00 00 00 00 00 	................

リトルエンディアンなので逆から読んで、例えばこの中の0x0008F084の中身は次の通りです

コード	結果	内容	補足
0x0008F084 & 0xfff	0x84	モンスターid	まじゅつし
(0x0008F084 << 0x11 & 0xFFFFFFFF) >> 0x1d)	0x7	このお供の確率	7, 5, 1などの形式、確率をすべて足した値が最大乱数
(0x0008F084 << 0xe & 0xFFFFFFFF) >> 0x1d)	0x1	最小数	1体
(0x0008F084 << 0xb & 0xFFFFFFFF) >> 0x1d)	0x2	最大数	2体

エンカウント情報(スポーンレートではない)は、(0x020FDBCC + n * 0x4c) + N * 8 + 4に保存されており、次の通りです
8バイト事に保管されており、最初の4バイトを読み取ります。最大数は6個です

020FDBC0		00 00 00 00 00 00 00 00 01 00 00 00 1E 00 04 06 	................
020FDBD0		1F 10 9D 01 00 00 00 00 6C 10 9D 01 00 00 00 00 	........l.......
020FDBE0		53 10 9D 01 00 00 00 00 03 90 9C 00 00 00 00 00 	S...............
020FDBF0		00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 	................

例えば、この中の0x019D101Fの中身は次の通りです
(主にお供判定の数値)

コード	結果	内容	補足
0x019D101F & 0xfff	0x1F	モンスターid	しにがみ
(0x019D101F << 0x8 & 0xFFFFFFFF) >> 0x1d)	0x4	2Gの確率の差分	7+4=11
(0x019D101F << 0xb & 0xFFFFFFFF) >> 0x1d)	0x7	1Gの確率	7
(0x019D101F << 0x5 & 0xFFFFFFFF) >> 0x1d)	0x1	3Gの確率差分	7+4+1=12が最大乱数
(0x019D101F << 0x11 & 0xFFFFFFFF) >> 0x1d)	0x1	最小数	1体
(0x019D101F << 0xe & 0xFFFFFFFF) >> 0x1d)	0x2	最大数	2体

Q. ゲーム内では何桁目まで算出されているですか?

A.
気になったので新規に調べました
ゲーム内で使用されているパーセントは、3F5FD441です。
これは0.8743324875831604に相当します。これを100倍した数値がパーセントなので14桁です
乱数表だと87.4332507140934467315673828125なので、5桁目以降は誤差が発生していると考えて良さそうです
(検証で7桁目ぐらいまで正確である事は調査済みなので、なぜずれているのはか良く分かりません)
つまり、4桁目まで正確です
(phpプログラムのせいかは分かりませんが、2の倍数で保存するのでうまく表現できない仕様など)

3F5FD441 → 0.8743324875831604
3F4741C1 → 0.7783470749855042
3DAD9514 → 0.084757000207901

例えば、63.63636285532265%はゲーム内では63.63636255264282%(3F22E8BA)として処理されており、63.63636363以下にも関わらず、お供が出ます。
このケースでは-0.00000030267983%ほど誤差があります
誤差は固定ではないようです

-0.00000030267983%
-0.000001955%

64bit LGCの更新式について

式は

\text{前の乱数} \times \text{0x5d588b656c078965} + \text{0x269ec3}\mod 2^{64}

です。
この処理は関数FUN_207544C(UpdateLCG)で行われており、引数1は更新先のアドレスです。
引数1が0x2108D20の場合は、Bテーブル、引数1が0x2385F0Cの場合は、Cテーブルです。

エクセルだと精度が足りないのでここでは触れませんが代替手段を使う必要があります
(具体的には乱数値を4分割して処理する)
modは割り算のあまりです
ここで0xと付く数値は16進数です
64bit LGCは、前の乱数値から次の乱数値を計算します
つまり、ホイミテーブルと呼ばれてますがrom上にはテーブルはありあせん
このとき、前の乱数値を使用して計算します。(某サイトの嘘説明について)最初から乱数値が決まっているわけではありません
パーセントの計算は、算出した乱数値を使用して行います。

前の乱数を0x3276cだとすると、
まず定数0x5d588b656c078965を掛けて(両方64bitの場合、Windows電卓くんだと精度足りません)

0x3276c \times 0x5d588b656c078965 = \text{0x80c78655554b599c}

次に0x269ec3を足します

\text{0x80c78655554b599c} + \text{0x269ec3} = \text{0x80c786555571f85f}

次に、64bitの範囲を超えた部分を切り捨てます
単純に64bitの範囲を超えた部分を切り捨てればいいのでmodする代わりに0xFFFFFFFFFFFFFFFFとANDしても良いです
Windows電卓くんだとこの操作はできないので、プログラムで行うことになります
(AND = 1111 & 1010 = 1010のように、1の部分以外削除)

\text{0x80c786555571f85f}\mod 2^{64} = \text{0x80c786555571f85f}

0x80c786555571f85fが次の乱数値です
この乱数値はかならず、(どっちから始まるかはさておき)奇数、偶数、奇数、偶数になります。不思議

javascriptで書くとこうです

/**
 * @param {BigInt} seed - input seed
 * @returns {BigInt}
 */
function rand(seed) {
    seed = seed * BigInt("0x5d588b656c078965");
    seed = seed + BigInt("0x269ec3");
    seed = seed & BigInt("0xFFFFFFFFFFFFFFFF");
    return seed;
}

サイト

私が参考にしたサイトです
https://oupo.hatenadiary.com/entry/20171219/1513609225

%計算について(表)

上限が100%になるパーセントの計算式は

\frac{{(\text{input} \gg 32) \times 100}}{{2 \ll {31}}}

です。全く分かりませんね
つまり、

((input >> 32) * 100) / 4294967296

です

(input >> 32)

は下32bitを切り捨てて詰める処理です

\text{0x80c78655554b599c} \gg 32 = \text{0x80c78655}

次に、100倍にします

\text{0x80c78655} \times \text{0x64} = \text{0x324df07934}

次に、乱数の出目の最大値と割り算します
この時、小数点が表示されませんが、プログラムパワーによって割り算の小数点まで計算します。
16進数モードだと結果は16進数であることに注意してください

\text{0x324df07934} \div \text{0x100000000} = \text{50.304450583644211292266845703125}

理屈としては、乱数の上位32bitを100倍して、それを乱数値の最大値??? で割っているだけです
つまり、確率が100%になるには

\text{0x100000000} \times \text{0x64} \div \text{0x100000000} = 100

を満たす必要があります
0に近づけるには数値が小さければいいので、

\text{0x1000000} \times \text{0x64} \div \text{0x100000000} = 1

みたいな感じです

これら処理はFUN_20754D8(getFloatRand)及び、FUN_2075488(RandInt)で行われています。
getFloatRandはパーセント*0.01を返す関数であり、RandIntは引数2で指定した数値-1までの範囲の乱数を返す関数です。

javascriptで書くとこうです
入力はbigintである必要があります

function calculatePercent(input) {
    let output = input >> BigInt(32);
    output = output * BigInt(100);
    output = output / (BigInt(2) << BigInt(31));
    return output;
}

calculatePercent(rand(BigInt("0x3276c")));

小数点以下対応版(10000の0を増やすと上限16桁程度で桁数が増える)

function calculatePercentFloat(input) {
    let output = input >> BigInt(32);
    output = output * BigInt(100);
    let test = (BigInt(2) << BigInt(31));
    //output = output / test;
    output = division(output, test);
    return output;
}

function division(a, b){
    return Number(a * 10000n / b) / 10000;
}

実行サイト

無料の実行サイトにプログラムを置いたので自由に実験してください
https://paiza.io/projects/pebLPqdhonaYtk2AcDS-qQ?language=javascript

電卓用

式は

((input >> 32) * 100) / 4294967296

なので、

(floor(input / 4294967296) * 100) / 4294967296

に変換すれば電卓で計算できます
Windows電卓くんは関数電卓の関数にfloorがあります
ここで16進数を10進数に変換して(0xを削除する必要があります)
https://hogehoge.tk/tool/number.html

((floor(9279533258281539996 / 4294967296))) * 100) / 4294967296 = 50.304450583644211292266845703125

内部的な仕様について

内部的な関数FUN_02075488では、%ではなく最大値を指定する方式が取られています
例えば、関数に11を指定すると、0から10まで(11個)の数値を返します
これが、確率が小数点まで要求する原因です
ゲーム内部では、乱数からランダムな小数点を生成し、それを最大値で掛けているようです

パーセント表記を乱数値に変換する式は下記の通りです

\lfloor \text{Percent} \div \text{100} \times \text{Max} \rfloor

小数点に変換してから最大値で掛けるだけです。簡単！
上で計算した乱数値の場合、5が計算されます。もしそれがお供判定なら7以下なので1Gです
厳密には+1するので少し違いますが、(乱数 + 1) > 7が成立する時に2Gになります

\text{50.304450583644211292266845703125} \div \text{100} \times \text{11} = \text{5}

確率計算について

1Gが出る確率の確率計算はphpプログラムで計算されており、phpプログラムは下記の通りです

number_format(100 - calculateExpectedValue($g3_1 / $maxrand, 100), 4)
function calculateExpectedValue($probability, $maxValue){
	return (1 - $probability) * $maxValue;
}

AIが生成したコードなので遠回りに計算されていますが、つまり

7 \div  11 \times 100 = 63.636363636363

と同じです

3Gの確率も同じく、

11 \div  12 \times 100 = 91.666666666666666666666666666667

のように計算されています

話が変わってお供の確率は少し複雑で、

モンスター	確率	内部的な値	2Gの最小数	2Gの最大数	乱数幅
まじゅつし	0.0000%-23.3333%	0-7	1	2	1
ミイラ男	23.3333%-40.0000%	8-12	1	2	1
はにわナイト	40.0000%-56.6667%	13-17	1	2	1
メタルスライム	56.6667%-60.0000%	18-18	1	1	0
さまようたましい	60.0000%-83.3333%	19-25	1	2	1
しにがみ	83.3333%-100.0000%	26-30	1	2	1

モンスター	確率	内部的な値	1Gの最小数	1Gの最大数	乱数幅
しにがみ	58.3333	7/12/11/12	1	2	1
ミイラ男	58.3333	7/12/11/12	1	2	1
はにわナイト	58.3333	7/12/11/12	1	2	1
メタルスライム	63.6364	7/11/11/11	1	1	0

モンスター	3Gの確率1(以上)	3Gの確率2(かつ以下)
しにがみ	91.6667	100.0000
ミイラ男	91.6667	100.0000
はにわナイト	91.6667	100.0000

この表の場合、まず1ステップ辺りの確率を計算します
次に次のように計算して算出します

100.0 \div 30 = 3.33333333333333333333333

まじゅつしは

7 \times 3.33333333333333333333333 = 23.33333333333333333333331

ミイラ男は

12 \times 3.33333333333333333333333 \approx 40

のように計算されています。

Aテーブルについて

CテーブルはBと全く同じなので省略
Aテーブルは32bit LCGを使用されて計算されており、更新式は

\text{前の乱数} \times \text{0x41c64e6d} + \text{0x3039} \mod 2^{32}

0xFFFFFFFF
https://oupo.hatenadiary.com/entry/20161207/1481079250
です
この処理はFUN_2003C30(UpdateAT)で行われており、引数はありません(結果は後述する右シフト10済み)
秘密裏にAテーブル表作ったので今更公開します
https://daisukedaisuke.github.io/rand/atable.html?filter=0&seed=A74FFD63&end=300
初期シードは臼倉地図です
ここで、約2%～12%未満になってるマスが次にあるマスでエンカウントすれば戸惑い、各種シンボルの確率一覧でメタルが出るパーセントでスポーン処理が行われた場合メタル系が出ます

次にパーセント計算ですが、右シフトして、0x7fffをandします

\text{0x7fff} \, \& \, (\text{{seed}} \, \gg \, \text{0x10})

0x7fff = 32767
「電卓ではそんな操作できないよ」と思った人の為に代替策をAIに生成してもらいました

\text{tmp} = \left( \frac{{\text{{seed}}}}{{2^{16}}} \right) \mod (32767+1)

(seed / (2^16)) mod (32767+1)

(\text{0xb9d53d60} \div 2^{16})\mod (32767+1) = 14805

(3117759840 / (2^16)) mod (32767+1) = 14805

あとはいつもの式でパーセントを計算するだけです

\text{input} \times 100 \div \text{0x7fff}

代入すると

14805 \times 100 \div 32767 = 45.182653279213843195898312326426

この処理(引数1に100を指定した場合)はFUN_2031EA8(ATRandInt)で行われており、引数1で指定した数値-1までの範囲の乱数を返します。
ほとんどのAT関連の処理は、乱数値(updateATの戻り値)を直接割り算関数FUN_200CE08(int32Division1)に渡し、あまりを乱数値として扱うという手法が使われており、rand関数が使われるのは稀です。

エンカウントを手計算してみよう

エラフィタ地方の4テーブルの表です

最大数: 2

モンスター	確率	内部的な値	2Gの最小数	2Gの最大数	乱数幅
おおきづち	0.0000%-10.0000%	0-2	1	1	0
ポンポコだぬき	10.0000%-30.0000%	3-6	1	1	0
ブラウニー	30.0000%-55.0000%	7-11	1	1	0
デンデンがえる	55.0000%-70.0000%	12-14	1	1	0
ねこまどう	70.0000%-85.0000%	15-17	1	1	0
かまっち	85.0000%-100.0000%	18-20	1	1	0

モンスター	確率	内部的な値	1Gの最小数	1Gの最大数	乱数幅
ねこまどう	21.4286	3/14/10/14	1	2	1
ポンポコだぬき	36.3636	4/11/9/11	1	1	0
ブラウニー	28.5714	4/14/11/14	1	1	0
デンデンがえる	28.5714	4/14/11/14	1	2	1
かまっち	28.5714	4/14/11/14	1	2	1

モンスター	3Gの確率1(以上)	3Gの確率2(かつ以下)
ねこまどう	71.4286	100.0000
ポンポコだぬき	81.8182	100.0000
ブラウニー	78.5714	100.0000
デンデンがえる	78.5714	100.0000
かまっち	78.5714	100.0000

0x3276cでシード値は0xBD77A7C592A1733Eです

1フレーム目(1Gの数)

乱数表から37.4361を参照します(Windows電卓くんは精度足りなかった)

次に、かまっちにぶつかったとして、1Gの乱数幅の値を取得します。
0です

次に、乱数幅に1を足して、下記を計算します

\lfloor 37.4361 \div \text{100} \times (0+1) \rfloor = 0

算出した数値に、最小数を足します

0 + 1 = 1

なので1グループ目のかまっちは1体ですね

2フレーム目(お供判定)

2フレーム目はお供判定です
乱数表から85.8517と、表から4/14/11/14を取得します
内部的な数値は、2Gの確率/最大乱数/3Gの条件1/3Gの条件2です。
最大値は14です

\lfloor 85.8517 \div \text{100} \times 14 \rfloor + 1 = 13

まず、1Gの閾値と比較します

13 > 4

13の方が大きいので2G確定です。

次に、3Gの閾値1と比較します

11 < 13

13の方が大きいので3G確定です
ゲームは更に3Gの閾値2(100%)と比較していますが意味があるかどうかわからないので省略

3フレーム目(2Gの種類)

3フレーム目は2Gの種類です。1Gの場合スキップします
乱数表から15.0328を取得します

\lfloor 15.0328 \div \text{100} \times 20 \rfloor + 1 = 3

おおきづちが0-2で

2 => 3

なのでおおきづちではないようです
次はポンポコだぬきで3-6なので

6 => 3

で成立するので2G目のお供はポンポコだぬきのようです

4フレーム目(2Gの数)

乱数表から69.6181を取得し、狸の乱数幅が0である事を確認します

\lfloor 69.6181 \div \text{100} \times (0+1) \rfloor = 0

最小数を足すと1なので、1体です

0+1=1

2Gはポンポコだぬき1体のようです

5フレーム目(3Gの種類)

2Gエンカウントの場合スキップ

乱数表から68.8604を取得します

\lfloor 69.6181 \div \text{100} \times 20 \rfloor + 1 = 12

おおきづちが0-2で

2 => 12

なのでおおきづちではないようです
次はポンポコだぬきで3-6なので

6 => 12

なので狸ではないようです
ブラウニーは7-11なので、

11 => 12 

これも違うようです
でんでんがえるは12-14なので

14 => 12

成立しました！これのようです！

つまり、3Gはでんでんがえるです！

6フレーム目(3Gの数)

乱数表から97.5625と乱数幅の0をを取得します
乱数幅に1を足して、下記を計算します

\lfloor 97.5625 \div \text{100} \times (0+1) \rfloor = 0

算出した数値に、最小数を足します

0 + 1 = 1

つまり、でんでんがえる1体です！

7フレーム目

謎消費
(50%かどうかで内部的な順番を入れ替える。これにより見た目の順番が変わることはない)
(1Gの場合発生しない)

それ以降

hp決定(左端→右端)
↑未知の並び替え処理が行われる事があり、見た目の順番がBテーブルで決定された順番と合わない事がある。
モーション選択(1人: 0, 2人: 2,3人: 3, 4人: 4)

グループ削除

まとめると、かまっち1体、ポンポコだぬき1体、でんでんがえる1体です
でも全て加算すると3体で最大数2を超えています。つまり削除処理が実行されます！
まず、総数を計算したのち、最大数を引きます
これについては調査メモ2枠目に詳しく書いているので見てください

1+1+1-2 = 1

次に、計算した数字 / 3を計算して、0以下なら1にして減らさないといけない数とします

\max\left(count \div 3,1\right) = 1

2番目に、先頭から計算した1を順番に引きます

1グループ目から1引いて0
1グループ目は1以下にならないので1に戻す
減った数は0匹
減らないといけない数を0減らす

次グループへ

2グループ目から1引いて0
減った数は1匹
減らないといけない数を1減らす

目標数減らせた(減らさないといけない数 < 0)ので終了

結果

結果はかまっち1体、ポンポコだぬき0体、でんでんがえる1体です！
ツールはx1 狸x0 デンデンがえるx1なので正解です！

宣伝

dsの一般的な解析について知りたい場合は、下記の記事が役に立ちます。
https://www.starcubelabs.com/reverse-engineering-ds/

dq9の解析を検討している場合、dq9Functionsをghidraにインポートすると、基礎的な関数に名前が付き、読みやすくなります。
また、基礎的な関数に対する英語での説明も付属しています。
r0が表示されない、non-returning functionでデコンパイルしてくれないなどような良くある落とし穴もインポート方法にて対策済みです。
ぜひインポートをご検討ください。