Walkie-Talkieをビルドする方法

Walkie-Talkieをビルドします。

f:id:oupo:20200122154201p:plain

古いdevkitProが必要です。

linuxバージョンはここから落とせるようです。

この場合32bitのlinuxで動きますから、それを用意します。私はVirtualBoxの上でCentOS 6を立ち上げました。

devkitProをホームディレクトリの下に用意する

上のリンクからdevkitARM_r23b-i686-linux.tar.bz2とlibnds-20071023.tar.bz2をダウンロードして解凍します。

$ tar xf devkitARM_r23b-i686-linux.tar.bz2
$ tar xf libnds-20071023.tar.bz2

~/devkitpro以下にコピーします。

$ mkdir -p ~/devkitpro/libnds
$ mv devkitARM ~/devkitpro
$ mv include lib ~/devkitpro/libnds

環境編集をエクスポートします。

$ export DEVKITARM=/home/user/devkitpro/devkitARM
$ export DEVKITPRO=/home/user/devkitpro

Walkie-Talkieをビルドする

Walkie-Talkieのソースコードhttp://home.kabelfoon.nl/~moongies/nds_en.htmlからダウンロードします。

解凍します。

$ tar xf walkietalkie-src-0v3.tar.gz
$ cd walkietalkie-0v3

まずmisc/libnds/ipc.hのコメントがバグっているで修正します。

--- walkietalkie-0v3.orig/misc/libnds/ipc.h  2008-11-10 06:49:14.000000000 +0900
+++ walkietalkie-0v3/misc/libnds/ipc.h    2020-01-22 14:54:11.477041756 +0900
@@ -24,14 +24,14 @@
        must not be misrepresented as being the original software.
    3.  This notice may not be removed or altered from any source
        distribution.
-
+*/
 /* 
    ===========================
    nov 2008: adapted by Eric for walkie-talkie v0.1
    ===========================
 */
 
----------------------------------------------------------------------------------*/
+/*---------------------------------------------------------------------------------*/
 
 #ifndef NDS_IPC_INCLUDE
 #define NDS_IPC_INCLUDE

次にlibndsのipc.hを今書き換えたもので上書きしましょう。

cp misc/libnds/ipc.h ~/devkitpro/libnds/include/nds

次に中にあるliblobbyをビルドしましょう。

$ cd misc/liblobby
$ tar xf liblobby_for_walkietalkie.tar.gz
$ cd liblobby_for_walkietalkie
$ make

ビルドできたらlib/liblobby7d.a, lib/liblobby9d.aが出来ているはずです。

ビルドできたものをdevkitproにコピーします。

cp include lib ~/devkitpro/libnds

walkietalkieのディレクトリに戻りましょう。

$ cd ../../..

makeします。

$ make

これでwalkietalkie-0v3.ndsができるはずです。

終わりに

新しいdevkitProでもビルドできるようにしたいですね…。

GBAのROMを二次元コードを使ってダンプするNDSプログラム

GBAのROMを二次元コードを使ってダンプするNDSプログラムとそれを読み取るwebプログラムを書きました。

f:id:oupo:20200118203856j:plain

f:id:oupo:20200118203921p:plain

f:id:oupo:20200118210330p:plain

  • 二次元コードQRコードを改造した独自仕様を採用。 正方形ではなくDSの画面を全部使いたかったのと、機能モジュールがいらないと思ったので。 QRコードのライブラリ、QR-Code-generatorとzxing-jsをいじって使っています。
  • 最初は1モジュールを2ピクセル×2ピクセルで描画していましたが、1モジュール1ピクセル×2ピクセルでも十分読み取れると分かってそうしました。
  • webプログラムはiPadSafariだと最初カメラが止まる問題点がある。一旦カメラをオフにしてもう一度オンにすれば直ります。

pattirudonアルゴリズムのオーダー

このアルゴリズムのオーダーを調べます。

つまり、線形な遷移で決まっている疑似乱数で、状態から乱数は足し算で決まっているものとする。 このとき乱数値からseedを復元するアルゴリズムを考える。 ただし、簡単のため一個の乱数で見れるbit長を固定でkとする。

seedの長さをn bitとする。 このときアルゴリズムの計算時間は次の通り。

アルゴリズム 計算時間
愚直なアルゴリズム Θ(2n)
pattirudonアルゴリズム Ω(2n/2)

ただしseedの候補を決めたとき、それが本当にseedかはΘ(1)時間でできるものと仮定する。

ここにΘ(f(n))はちょうどf(n)のオーダー、Ω(f(n))は少なくともf(n)のオーダーを意味する。

説明

何個の乱数を見るかをlとする。最適なlを調べる。

seedから乱数値を決める足し算する前の値を得る写像をf: F_2^n -> F_2^(2kl)とする (1個の乱数ごとに2l bitあることに注意)。 探索しないといけないbit数はkl + dim(Ker f)である。 ここにklは足し算する前の値の片割れのbit数、dim(Ker f)はそれを決めたときのf(x) = aの解空間の次元。

次元公式よりdim(Ker f) = n - dim(Im f) ≦ n - 2klなため、

(探索しないといけないbit数) = kl + dim(Ker f) ≧ kl + max{n - 2kl, 0} = max {n - kl, kl}。

これが最小となるのはl = n / (2k)のときで最小値はn / 2。 よって(n / 2) bitの探索をしなければいけないため、計算量はΩ(2n/2)である。

pattirudon氏のアルゴリズムについて

背景

ポケモンソード・シールドのレイドバトルと呼ばれるイベントではxoroshiro128+という疑似乱数を使ってモンスターを生成している。 これについて、セーブデータを抽出せず、ゲームのプレイから得られる情報からxoroshiro128+の乱数の種を復元できないかということが問題になっていた。

xoroshiro128+は状態遷移はF_2線形 *1であるが、状態から乱数値を得るのに算術和を使っており、それが非線形なため復元は難しいのではないかとされていた。 しかし、驚くべきことにpattirudon氏はそれを可能にした。

github.com

ゲームでのxoroshiro128+の使われ方

ゲームのセーブデータにレイドバトルの各巣ごとの64bitのseedが格納されている。 seedはレイドバトルのイベントを起こしたり、日付が変わったりするごとに以下の式で更新される。

seed = (seed + 0x82a2b175229d6a5b) mod 2^64

レイドバトルのイベントを起こしたときは、巣のseedと定数を使ってxoroshiro128+の種を与える。

s0 = seed
s1 = 0x82a2b175229d6a5b

この種からxoroshiro128+で暗号化定数やPIDや個体値、特性、性格などのモンスターの属性が決定される。 その決定のされ方は以下に書かれている。

github.com

xoroshiro128+について

xoroshiro128+は詳細を省けば以下のような疑似乱数生成器である。 線形写像next: F_2^128 -> F_2^128が固定されており、状態遷移はこのnextで行う。 状態から疑似乱数の発生は次のようになっている

u64 s0, s1; // 状態

u64 getrand() {
    u32 val = s0 + s1;
    (s0, s1) = next(s0, s1);
    return val;
}

つまり、算術和を使っている。これが問題の困難な点である。

なお、このゲームでは0以上m未満の乱数を生成する場合は、m以上の最小の2べきの数2^kをとりgetrand() % 2^kで乱数を発生させている。これがm以上の数ならばm未満の数が出るまでgetrand()を繰り返し呼んでいる。

ゲーム内からわかる情報

上に述べた通り、モンスターの属性がxoroshiro128+で決定されているわけだが、そのすべてがゲーム内からわかるわけではない。 暗号化定数やPIDはそれぞれ32bitの情報があり、これが分かれば簡単にseedを復元できたはずだが、それはゲーム内から得られない。 分かる情報はV固定箇所(3bit)、個体値(5bitの情報が5つ)、特性(1bit)である。 合計29bitの情報が分かる。 もちろん非線形関数を使っているので、単純な64-29=35bitのしらみつぶしというわけにはいかない。

pattirudon氏のアルゴリズム

pattirudon氏が気づいたのは「乱数値はseedから非線形だが、その乱数値の一歩手前の足し算する前の値は線形に得られる」という点である。 つまりseedから次の情報は線形に得られる。

  • V固定箇所の3bitを決める足し算する前の値6bit
  • 個体値5bitを決める足し算する前の値10bit (それが5つで50bit)
  • 特性を決める1bit (これは最下位bitを使っているため線形である)

よって64bitのseedからこれら57bitの情報を得る線形写像f: F_2^64 -> F_2^57が定まる。

f:id:oupo:20191223155858p:plain

ゲーム内からわかる情報(足し算の結果)29bitがあり、足し算の片割れの情報28bit分をしらみつぶししてF_2^57の元xを考える。 ここでf(seed) = xという方程式を解けばよい。 fのkernelの次元が7なので各xについて解は128個求まる。 そのそれぞれについて、2匹目のモンスターの情報を使い絞り込む。

これは28bit + 7bit = 35bitの空間の探索なので現実的な時間で終了する。

f:id:oupo:20191223155922p:plain

補足

話を少し単純化した部分がある。 V固定箇所は6通りであるが、これをgetrand() % 8で決めるため、6未満の値が出るまで乱数を振っている。 したがって、本当はこの部分に不定個数の乱数消費がある。 この部分が現時点のツール (ver.1.0)では1個の消費で済んでいると仮定しているようだ。 つまりここで2個以上消費したseedは検索にヒットしないはずである。

それから、seedから57bitの情報を得る部分は、s1の定数があるため、実際には線形ではなく線形写像と並行移動の合成である。 しかしこれは考える方程式の定数項に影響を及ぼすだけである。

*1:F_2とは2元体{0, 1}のこと

ゲームボーイのポケモンの疑似乱数

疑似乱数アルゴリズム、「pokemon rng ffd3」で検索したら出てきた。

http://tasvideos.org/GameResources/GBx/PokemonGen1.html

http://wiki.pokemonspeedruns.com/index.php/Pokémon_Red/Blue/Yellow_DSum_Manipulation

乱数生成のたびにIOレジスタの一つ0xff04の値を足す(あるいは引く)というもの

ポケモン赤の疑似乱数を0に固定するLuaスクリプト書いた。攻撃が必ず急所に当たるようになったのでたぶんうまく動いている

https://gist.github.com/oupo/58b2a858360b574661a3

f:id:oupo:20190503185515p:plain

ここによると金銀のRNGも赤緑と同じみたいですね

http://tasvideos.org/4205S.html

線形合同法とp進整数と縮小写像

p素数eを正整数,a, bを整数とする. f: \mathbb{Z}/p^e\mathbb{Z} \to \mathbb{Z}/p^e\mathbb{Z}を $$f(x) = a x + b$$ で定める.

命題1

apの倍数であると仮定する. このとき次が成立する.

  1. f不動点,すなわち $$f(x) = x$$ を満たすx \in \mathbb{Z}/p^e\mathbb{Z}が存在する.

  2. f不動点は一意である.

  3. 任意のx_0 \in \mathbb{Z}/p^e\mathbb{Z}について次で定義される数列: $$ x_n = f^n(x_0) $$ は不動点に収束する.(ここにf^nfn回合成)

証明.(1)と(2):

$$ f(x) = x \iff (a-1)x \equiv -b \pmod{p^e} $$ だが,今apの倍数なので,a-1pと互いに素.よってこの一次合同方程式には解が一意に存在する.

(3): 数列の一般項は $$ x_n = a^n x_0 + (1 + a + a^2 + \dots + a^{n-1})b $$ となる.apの倍数なのでa^{n_0} \equiv 0 \pmod{p^e}となるn_0がある.するとn > n_0なら $$ x_n = (1 + a + a^2 + \dots + a^{{n_0}-1})b $$ となって一定値をとる. ■

ところで次のようなよく知られた定理がある.

定理 (Banachの不動点定理)

(X, d)を空でない完備距離空間f: X \to Xを次を満たす写像とする: あるk\ (0 \leq k \lt 1)があって任意のx, y \in Xについて $$ d(f(x), f(y)) \leq k\,d(x, y). $$ このときf不動点がただ一つ存在する. また任意のx_0に対して数列x_n = f^n(x_0)不動点に収束する.

Banachの不動点定理によって最初の命題を証明できないだろうか.\mathbb{Z}/p^e\mathbb{Z}には距離は離散距離しか入らないので使えそうにない.そこでp進整数環\mathbb{Z}_pと呼ばれる空間を考える.

p進整数環の定義はここではしないが,次のような性質を持つ.

  • \mathbb{Z}_pには環構造が入る
  • \mathbb{Z} \subset \mathbb{Z}_pである
  • x \in \mathbb{Z}_pに対してxp進絶対値|x|_pが定まる
  • |x|_p = 0 \iff x = 0
  • |xy|_p = |x|_p |y|_p
  • |x + y|_p \leq \max\{|x|_p, |y|_p\}
  • x \in \mathbb{Z} \setminus \{0\}に対してはx素因数分解したときのpの指数をnとしたとき|x|_p = p^{-n}
  • d(x, y) = |x - y|_pと定めるとき(\mathbb{Z}_p, d)は完備距離空間
  • 全射環準同型\varphi_e: \mathbb{Z}_p \to \mathbb{Z}/p^e\mathbb{Z}があり,特にx \in \mathbb{Z}なら\varphi_e(x) = x \bmod p^e

f\mathbb{Z}/p^e\mathbb{Z}上の写像であったが,これを\mathbb{Z}_p上に修正したものを\tilde{f}で表す: $$ \tilde{f}: \mathbb{Z}_p \ni x \mapsto (ax+b) \in \mathbb{Z}_p$$

この\tilde{f}はBanachの定理の仮定を満たす.実際,

\begin{align*} d(\tilde{f}(x), \tilde{f}(y)) &= |(ax+b)-(ay+b)|_p \\ &= |a(x-y)|_p \\ &= |a|_p |x-y|_p \\ &= |a|_p d(x, y) \end{align*}

であり,apの倍数だから|a|_p \lt 1である.

よって\tilde{f}不動点xが存在し,それを\varphi_eで移せばf不動点を得る.ゆえに命題の(1)が示された. また,\mathbb{Z}/p^e\mathbb{Z}に離散位相を入れたとき,\varphi_e連続写像になるので,そこから命題の(3)を得る. (なお,残念ながら,命題の(2)はこの方法では示せない.)

以上よりBanachの不動点定理によって最初の命題を(一部分を除いて)示せることがわかった.

a = {\rm 0x12344} (偶数なことに注意!), b = {\rm 0x6073}, p = 2, e = 20, x_0 = 1としてみると次の表のようになる.下の桁から順に固定されていっている様子がわかる.

n x_n
0 {\rm 0x00001}
1 {\rm 0x183b7}
2 {\rm 0x0620f}
3 {\rm 0x1796f}
4 {\rm 0xdceef}
5 {\rm 0x504ef}
6 {\rm 0x15cef}
7 {\rm 0x0bcef}
8 {\rm 0x63cef}
9 {\rm 0xc3cef}
10 {\rm 0x43cef}
11 {\rm 0x43cef}
12 {\rm 0x43cef}

クリスマスイブなのでペラップにWe Wish a Merry Christmasを歌ってもらった

Pokémon RNG Advent Calendar 2017 24日目の記事です。

ペラップ演奏会をしました。忙しい人はラスト30秒を見てください。

先人はこちら:

使ったseedとか (第5世代はMACアドレスによってseedが変わるので他の人は使えないが)

周波数=400Hz
seed=0x1612c3c5, iseed=610a0397, f=30
A4, A4, A4, B4flat, A4
  • ホワイト DSi(00-22-aa-38-54-68)
周波数=325Hz
2081/05/24 22:13:59 key=40(↑)
iseed=5c1d2d0cd37c0907 seed=37deba833913e966 f=97 (46)
F4, F4, G4, F4, E4, G4, G4, G4, F4, E4, G4, F4, G4, E4, F4
  • ブラック DS Lite (00-21-47-72-91-b3)
周波数=255Hz
2056/06/25 17:37:21 key=00
iseed=b1b95766f2f478a9 seed=627ba589ac411cb1 f=72 (24)
C4, D4, D4, D4, C4, C4, D4, C4, C4, D4

seed検索のソースコードは以下。おだんぽよさんのPokeRNGを利用しています。

#include <iostream>
#include <cstdio>
#include <cstdint>
#include <ctime>
#include <vector>
#include "PokeRNG/Calc5GenSeed.hpp"
#include "PokeRNG/CalcOffset.hpp"

using namespace std;

typedef uint32_t u32;
typedef uint64_t u64;
typedef int64_t s64;

struct AbstractRNG {
    virtual int rand(int n) = 0;
};

struct LCG64bit : AbstractRNG {
    u64 seed;

    LCG64bit(u64 s) : seed(s) {}

    int rand(int n) {
        seed = seed * 0x5D588B656C078965 + 0x269EC3;
        return (seed >> 32) * n >> 32;
    }
};

struct LCG32bit : AbstractRNG {
    u32 seed;

    LCG32bit(u32 s) : seed(s) {}

    int rand(int n) {
        seed = seed * 0x41c64e6d + 0x6073;
        return (seed >> 16) % n;
    }
};

bool valid_seed(AbstractRNG &rng, double baseFreq, vector<double> expectedFreqs, double allowRatio = 1.015) {
    for (double expected : expectedFreqs) {
        double got = ((rng.rand(8192)) / 8192.0 * 0.25 + 1) * baseFreq;
        double ratio;
        if (expected < got) {
                ratio = got / expected;
        } else {
            ratio = expected / got;
        }
        if (ratio >= allowRatio) {
            return false;
        }
    }
    return true;
}


u32 prev_seed(u32 seed) {
    return seed * 0xEEB9EB65 + 0x0A3561A1;
}

bool good_seed(u32 seed) {
    int i;
    for (i = 0; i < 10; i ++) seed = prev_seed(seed);
    for (; i < 40; i ++) {
        u32 upper = seed >> 24;
        u32 hour = (seed >> 16) & 0xff;
        u32 frame = seed & 0xffff;
        u32 second = (frame - 17) / 60 + 10;
        if (12 * 24 + second - 256 <= upper && upper <= 12 * 24 + second + 60 - 256
            && hour < 24 && 0x0270 <= frame && frame <= 0x0400) {
            return true;
        }
        seed = prev_seed(seed);
    }
    return false;
}

constexpr double C4 = 261.626;
constexpr double D4 = 293.665;
constexpr double E4 = 329.628;
constexpr double F4 = 349.228;
constexpr double G4 = 391.995;
constexpr double A4 = 440.000;
constexpr double B4flat = 466.164;

// 中音 (ホワイト1 + DSi)
int main1() {
    vector<double> expected = { F4, F4, G4, F4, E4, G4, G4, G4, F4, E4, G4, F4, G4, E4, F4 };
    double base = 325;

#pragma omp parallel for
    for (long i = 946652400; i < 4102412400; i ++) {
        PokeRNG::Parameters5Gen<PokeRNG::ROMType::W1JaDSi> param;
        PokeRNG::Calc5GenSeed calc_seed;
        PokeRNG::CalcOffset calc_offset;
        param.set_mac_addr(0x00, 0x22, 0xaa, 0x38, 0x54, 0x68);
        param.set_timer0(0x1233);
        time_t time = i;
        struct tm date;
        localtime_r(&time, &date);
        param.set_year(date.tm_year + 1900 - 2000);
        param.set_month(date.tm_mon + 1);
        param.set_day(date.tm_mday);
        param.set_hour(date.tm_hour);
        param.set_minute(date.tm_min);
        param.set_second(date.tm_sec);
        for (int key = 0; key < 0x100; key ++) {
            if ((key & 0x30) == 0x30 || (key & 0xc0) == 0xc0) continue;

            param.set_key(0x2fff ^ key);
            PokeRNG::u64 seed = calc_seed(param);
            calc_offset.bw1(seed, true, true);
            LCG64bit lcg(calc_offset.get_seed());
            int ofs = (int)calc_offset.get_offset();
            for (int i = 0; i < 100; i ++) {
                LCG64bit l = lcg;
                if (valid_seed(l, base, expected, 1.02))
#pragma omp critical
                {
                    printf("%04d/%02d/%02d %02d:%02d:%02d ", date.tm_year + 1900, date.tm_mon + 1, date.tm_mday, date.tm_hour, date.tm_min, date.tm_sec);
                    printf("key=%02x seed=%016lx %016lx f=%d (%d)\n", key, seed, lcg.seed, ofs + i, i);
                }
                lcg.rand(1);
            }
        }
    }

    return 0;
}

// 低音 (ブラック1 + DSLite)
int main2() {
    vector<double> expected = { C4, D4, D4, D4, C4, C4, D4, C4, C4, D4 };
    double base = 255;

#pragma omp parallel for
    for (long i = 946652400; i < 4102412400; i ++) {
        PokeRNG::Parameters5Gen<PokeRNG::ROMType::B1Ja> param;
        PokeRNG::Calc5GenSeed calc_seed;
        PokeRNG::CalcOffset calc_offset;
        param.set_mac_addr(0x00, 0x21, 0x47, 0x72, 0x91, 0xb3);
        time_t time = i;
        struct tm date;
        localtime_r(&time, &date);
        param.set_year(date.tm_year + 1900 - 2000);
        param.set_month(date.tm_mon + 1);
        param.set_day(date.tm_mday);
        param.set_hour(date.tm_hour);
        param.set_minute(date.tm_min);
        param.set_second(date.tm_sec);
        int key = 0;
        param.set_key(0x2fff ^ key);
        PokeRNG::u64 seed = calc_seed(param);
        calc_offset.bw1(seed, true, true);
        LCG64bit lcg(calc_offset.get_seed());
        int ofs = (int)calc_offset.get_offset();
        for (int i = 0; i < 30; i ++) {
            LCG64bit l = lcg;
            if (valid_seed(l, base, expected, 1.015))
#pragma omp critical
            {
                printf("%04d/%02d/%02d %02d:%02d:%02d ", date.tm_year + 1900, date.tm_mon + 1, date.tm_mday, date.tm_hour, date.tm_min, date.tm_sec);
                printf("key=%02x seed=%016lx %016lx f=%d (%d)\n", key, seed, lcg.seed, ofs + i, i);
            }
            lcg.rand(1);
        }
    }

    return 0;
}

// 高音 (Pt)
int main3() {
    vector<double> expected = { A4, A4, A4, B4flat, A4 };
    double base = 400;

#pragma omp parallel for
    for (s64 seed = 0; seed < 0x20000000; seed ++) {
        LCG32bit lcg(seed);
        if (valid_seed(lcg, base, expected, 1.008) && good_seed(seed)) {
#pragma omp critical
            printf("%08x\n", (u32)seed);
        }
    }

    return 0;
}

int main() {
    return main2();
}
筆者: oupo (連絡先: oupo.nejiki@gmail.com)