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


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

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

## Cテーブル(概要)

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

Cテーブルの乱数アルゴリズムは64bit LGCで、ゲームではBと全く同じコードでパーセントを計算しています。
Cテーブルの初期シード戦闘が始まる暗転辺りで生成され、フレーム事に変化します。
初期シードは28bitでおおよそ ~~2.6億通り。~~ ~~符号なし32bitの最大値である42億通り。~~ 調査したところ、281兆通り(48bit)ある。時間が経過すればするほど桁が増える。0xffffffffffff(281兆)に到達するには起動から17.03年かかるので一周(オーバーフロー)する心配はない。

0xffffffff(ソフトウェアタイマー)ffff(cpuのハードウェアタイマー)
例: 0x588 4952
また、戦闘アニメーション中のフリーカメラの乱数としても使用されています。。
コマンド選択フェーズでシード値が無駄消費されることはないため、 ~~(敵の行動決定は1フレーム目なので)~~ 行動順乱数が先、素早さに0.51～1の数値をかけてソート。この時点でどんなコマンド選択しようが既にボスの行動は決まっているはずです。
これは、エミュレータのステートセーブで何回ロードしても常に同じ行動をとる現象で証明できます

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

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

## Q. 内部的な数字はどこから取得したのですか
A.
※この表の話してます
https://daisukedaisuke.hatenablog.com/entry/2024/04/29/072629

動作中の特定の場所にテーブルが保存されており、動作中のメモリの内容を全てダンプして、そのダンプファイルをプログラムで読み取ることで内部的な数字を取得します。
私がダンプしたメモリファイルは現在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.
追記:
※割り算の分母が4294967296ではなく4294967295であることが最近判明した。ズレてるのも納得。
ゲーム内のパーセントシステムはbinary64(64bitの浮動小数点)を使って計算されており、非常に高精度であると思われるが、外部に出力するのはbinary32なので、そのときの変換(キャスト)誤差によってある程度の誤差が生じるものと思われる。

気になったので新規に調べました
ゲーム内で使用されているパーセントは、`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の更新式について
式は
```math
\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電卓くんだと精度足りません)
```math
0x3276c \times 0x5d588b656c078965 = \text{0x80c78655554b599c}
```
次に`0x269ec3`を足します
```math
\text{0x80c78655554b599c} + \text{0x269ec3} = \text{0x80c786555571f85f}
```
次に、64bitの範囲を超えた部分を切り捨てます
単純に64bitの範囲を超えた部分を切り捨てればいいのでmodする代わりに`0xFFFFFFFFFFFFFFFF`とANDしても良いです
Windows電卓くんだとこの操作はできないので、プログラムで行うことになります
(AND = 1111 & 1010 = 1010のように、1の部分以外削除)
```math
\text{0x80c786555571f85f}\mod 2^{64} = \text{0x80c786555571f85f}
```
`0x80c786555571f85f`が次の乱数値です
この乱数値はかならず、(どっちから始まるかはさておき)奇数、偶数、奇数、偶数になります。不思議

javascriptで書くとこうです
```js
/**
 * @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%になるパーセントの計算式は
```math
\frac{{(\text{input} \gg 32) \times 100}}{{2 \ll {31}}}
```
です。全く分かりませんね
つまり、
```
((input >> 32) * 100) / 4294967296
```
です

```
(input >> 32)
```
は下32bitを切り捨てて詰める処理です
```math
\text{0x80c78655554b599c} \gg 32 = \text{0x80c78655}
```
次に、100倍にします
```math
\text{0x80c78655} \times \text{0x64} = \text{0x324df07934}
```
次に、乱数の出目の最大値と割り算します
この時、小数点が表示されませんが、プログラムパワーによって割り算の小数点まで計算します。
16進数モードだと結果は16進数であることに注意してください
```math
\text{0x324df07934} \div \text{0x100000000} = \text{50.304450583644211292266845703125}
```

理屈としては、乱数の上位32bitを100倍して、それを乱数値の~~最大値???~~ で割っているだけです
つまり、確率が100%になるには
```math
\text{0x100000000} \times \text{0x64} \div \text{0x100000000} = 100
```
を満たす必要があります
0に近づけるには数値が小さければいいので、
```math
\text{0x1000000} \times \text{0x64} \div \text{0x100000000} = 1
```
みたいな感じです

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

javascriptで書くとこうです
入力はbigintである必要があります
```js
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桁程度で桁数が増える)
```js
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個)の数値を返します
これが、確率が小数点まで要求する原因です
ゲーム内部では、乱数からランダムな小数点を生成し、それを最大値で掛けているようです

パーセント表記を乱数値に変換する式は下記の通りです
```math
\lfloor \text{Percent} \div \text{100} \times \text{Max} \rfloor
```
小数点に変換してから最大値で掛けるだけです。簡単！
上で計算した乱数値の場合、5が計算されます。もしそれがお供判定なら7以下なので1Gです
厳密には+1するので少し違いますが、(乱数 + 1) > 7が成立する時に2Gになります
```math
\text{50.304450583644211292266845703125} \div \text{100} \times \text{11} = \text{5}
```




### 確率計算について

1Gが出る確率の確率計算はphpプログラムで計算されており、phpプログラムは下記の通りです
```php
number_format(100 - calculateExpectedValue($g3_1 / $maxrand, 100), 4)
function calculateExpectedValue($probability, $maxValue){
	return (1 - $probability) * $maxValue;
}
```

AIが生成したコードなので遠回りに計算されていますが、つまり
```math
7 \div  11 \times 100 = 63.636363636363
```
と同じです

3Gの確率も同じく、

```math
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ステップ辺りの確率を計算します
次に次のように計算して算出します
```math
100.0 \div 30 = 3.33333333333333333333333
```
まじゅつしは
```math
7 \times 3.33333333333333333333333 = 23.33333333333333333333331
```
ミイラ男は
```math
12 \times 3.33333333333333333333333 \approx 40
```
のように計算されています。


### Aテーブルについて
CテーブルはBと全く同じなので省略
Aテーブルは32bit LCGを使用されて計算されており、更新式は
```math
\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%未満になってるマスが次にあるマスでエンカウントすれば戸惑い、[各種シンボルの確率一覧](https://daisukedaisuke.hatenablog.com/entry/2024/04/29/072629)でメタルが出るパーセントでスポーン処理が行われた場合メタル系が出ます



次にパーセント計算ですが、右シフトして、0x7fffをandします
```math
\text{0x7fff} \, \& \, (\text{{seed}} \, \gg \, \text{0x10})
```
0x7fff = 32767
「電卓ではそんな操作できないよ」と思った人の為に代替策をAIに生成してもらいました
```math
\text{tmp} = \left( \frac{{\text{{seed}}}}{{2^{16}}} \right) \mod (32767+1)
```
```
(seed / (2^16)) mod (32767+1)
```
```math
(\text{0xb9d53d60} \div 2^{16})\mod (32767+1) = 14805
```
```
(3117759840 / (2^16)) mod (32767+1) = 14805
```

あとはいつもの式でパーセントを計算するだけです
```math
\text{input} \times 100 \div \text{0x7fff}
```
代入すると
```math
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を足して、下記を計算します
 ```math
\lfloor 37.4361 \div \text{100} \times (0+1) \rfloor = 0
```
算出した数値に、最小数を足します
```math
0 + 1 = 1
```
なので1グループ目のかまっちは1体ですね

## 2フレーム目(お供判定)
2フレーム目はお供判定です
乱数表から85.8517と、表から`4/14/11/14`を取得します
内部的な数値は、`2Gの確率/最大乱数/3Gの条件1/3Gの条件2`です。
最大値は14です
 ```math
\lfloor 85.8517 \div \text{100} \times 14 \rfloor + 1 = 13
```
まず、1Gの閾値と比較します
```math
13 > 4
```
13の方が大きいので2G確定です。

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

## 3フレーム目(2Gの種類)
3フレーム目は2Gの種類です。1Gの場合スキップします
乱数表から`15.0328`を取得します
 ```math
\lfloor 15.0328 \div \text{100} \times 20 \rfloor + 1 = 3
```
おおきづちが`0-2`で
```math
2 => 3
```
なのでおおきづちではないようです
次はポンポコだぬきで`3-6`なので
```math
6 => 3
```
で成立するので2G目のお供はポンポコだぬきのようです

## 4フレーム目(2Gの数)
乱数表から`69.6181`を取得し、狸の乱数幅が0である事を確認します
 ```math
\lfloor 69.6181 \div \text{100} \times (0+1) \rfloor = 0
```
最小数を足すと1なので、1体です
```math
0+1=1
```

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

## 5フレーム目(3Gの種類)
2Gエンカウントの場合スキップ

乱数表から`68.8604`を取得します
```math
\lfloor 69.6181 \div \text{100} \times 20 \rfloor + 1 = 12
```

おおきづちが`0-2`で
```math
2 => 12
```
なのでおおきづちではないようです
次はポンポコだぬきで`3-6`なので
```math
6 => 12
```
なので狸ではないようです
ブラウニーは`7-11`なので、
```math
11 => 12 
```
これも違うようです
でんでんがえるは`12-14`なので
```math
14 => 12
```
成立しました！これのようです！

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

## 6フレーム目(3Gの数)
乱数表から`97.5625`と乱数幅の0をを取得します
乱数幅に1を足して、下記を計算します
 ```math
\lfloor 97.5625 \div \text{100} \times (0+1) \rfloor = 0
```
算出した数値に、最小数を足します
```math
0 + 1 = 1
```
つまり、でんでんがえる1体です！

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

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

## グループ削除
まとめると、かまっち1体、ポンポコだぬき1体、でんでんがえる1体です
でも全て加算すると3体で最大数2を超えています。つまり削除処理が実行されます！
まず、総数を計算したのち、最大数を引きます
これについては調査メモ2枠目に詳しく書いているので見てください
```math
1+1+1-2 = 1
```
次に、計算した数字 / 3を計算して、0以下なら1にして減らさないといけない数とします

```math
\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でデコンパイルしてくれないなどような良くある落とし穴もインポート方法にて対策済みです。
ぜひインポートをご検討ください。

https://github.com/DaisukeDaisukeTeam/dq9Functions/issues/1