YouTube の動画をアラームにして、推しの声で目覚める

はじめに

私は VTuber をしばしば観る人なのですが、寝る前に「朝配信」の予約枠を開きっぱなしにしてアラーム代わりにすることで、快適に起床できた経験がありました。 （人の声が良い感じなのでしょうか…？）

しかしこの手法には、朝の時間帯に配信がないことが多い（特定の時刻ならなおさら）、配信者側が寝坊して一緒に寝坊する可能性もある、などの難点がありました。 *1

もちろん生配信を任意に開始することはできないので、アーカイブを適当に再生することでアラームにするプログラムを作成し、この問題の解決を図ります。

目標

• YouTube のプレイリストを取得する
• 指定された時刻になったら、プレイリストからランダムに動画を選択し、再生する
• 一日で動くところまで実装できる

という感じの、とりあえず動くクライアントプログラムを作成します。

実装（インストール手順）

YouTube の情報にアクセスする API のライブラリが幸い C# (.NET) に対応していたので、使い慣れている C# (と WinForms) で作成することにします。開発環境は Visual Studio 2019 です。 とりあえず動く目標で作ったので汚いのはご容赦ください…

https://github.com/andanteyk/YouTubeAsAlerm

なお、クライアントキーは安直に公開すると危ないということしか知らないので、自前で用意していただく方式としました。そしてキーをご用意できる方ならバイナリもビルドできるだろうということで、ソースのみの公開となります。 文字通りの日曜プログラミングの成果ですのでご容赦いただければ…　あと万が一まずいものがあればこっそり教えてください…

また、YouTube のチャンネルを持っている（自分のプレイリストを追加・編集できる状態にある）ことが前提となります。

ビルド方法

インストール（ビルド？）方法とともに、開発で引っかかった点などを書いていければと思います。

まず、リポジトリを https://github.com/andanteyk/YouTubeAsAlerm.git から clone して Visual Studio で開き、プロジェクト→NuGet パッケージの管理からパッケージの復元を行います。YouTube API を使用するため Google.Apis.YouTube.v3 を使っています。

加えて、 YouTube のアカウント情報にアクセスするため、認証情報が必要になります。ビルドする前に以下の手順で認証情報を取得します。

認証情報の作成

※予防線：使用歴 6 時間の人間が書いています。以下手順でとりあえず動きますが、管理的に危険などあれば突っ込んでいただけると幸いです。

https://console.cloud.google.com/apis/dashboard にアクセスして、「プロジェクトを作成」します。 適当なプロジェクト名をつけて作成したら、「＋　API とサービスの有効化」から「YouTube Data API v3」を選択して有効にします。

すると、以下のように表示されるので、

この API を使用するには、認証情報が必要になる可能性があります。開始するには、[認証情報を作成] をクリックしてください。

「認証情報を作成」します。

使用する API は先程追加した「YouTube Data API v3」, API を呼び出す場所は今回の用途的に「その他の UI (Windows, CLI ツールなど)」を選択します。 アクセスするデータの種類については、今回はプレイリストにアクセスしたいので「ユーザーデータ」とします。

すると、「OAuth 同意画面の設定」をしろと言われるので、設定します。

User Type は「外部」にします。 *2

次に、アプリ情報を適当に入力します。ガイドにあるように、同意画面（このアプリケーションによる操作を許可しますか？的な画面）でこれらの情報が表示されます。

次に、スコープ（許可される操作）を指定します。今回は「YouTube プレイリストの取得」だけできればよいので、 .../auth/youtube.readonly を追加して「保存して次へ」移動します。

次に、テストユーザの指定があるので、お使いの Google アカウント（使いたい YouTube チャンネルがあるアカウント）を登録します。削除はできないらしいので注意してください。（とはいえ、100 枠もあるのでひとりで使う分には問題なさそうです。）

以上が完了したら、元の「プロジェクトへの認証情報の追加」ページに戻ります。 OAuth 2.0 クライアント ID に適当なものを設定し、「作成」ボタンを押します。

以上が完了したら、「認証情報」画面に移動し、OAuth 2.0 クライアント ID から作成した項目のダウンロードボタンを押すと client_secret_<ClientID>.json ファイルが入手できます。これを認証に使います。 なお、このファイルは秘密なので、git リポジトリに含めたりしないよう十分注意してください。 私の理解の範囲では、API を無限に叩いてリミットを使い果たすとか悪いことをされる可能性があります。

以上で認証情報の取得が完了しました。

実行

アプリを一度ビルドした後、exe と同じ場所 (…/bin/Debug など) に先程の JSON ファイルを client_secrets.json にリネームして配置します。

実行すると初回はブラウザで認証画面が開くので、使いたいチャンネルを指定して許可してください。信用されていないので警告が出ますが、自分自身がユーザなので大丈夫だと思います。多分…

うまくいけばプレイリストが勝手に取得されるので、Alerm タブで適宜アラームを設定すれば、指定した時刻にプレイリスト内のランダムな動画がブラウザで開かれます。これで快適な朝が迎えられますね…？

あとは、開発で得られた知見（つまづきポイント）を書いていきます。

データ取得の流れ

Channels.List   - チャンネル取得
    Playlists.List    - チャンネル内のプレイリスト取得
        PlaylistItems.List   - プレイリスト内の各項目（動画）取得

上から順に取得してサーチしていくイメージです。 具体的な処理は ApiManager.cs を参照してください。

後で見る (Watch Later) は取得できない

https://t.co/05evYD0uvs
> As of Sep 12 2016, watch later and watch history can no longer be retrieved YouTube Data API v3.
ﾝﾝﾝﾝﾝﾝ

— Andante (@andanteyk) 2020年12月13日

「後で見る」のプレイリストは API から取得できないようです。元々の目標はこのリストから再生することだったので、最初から知っていれば実装しなかったかもしれません……

プレイリスト内容取得 API のリファレンス を見ると、確かに

forbidden (403)
watchLaterNotAccessible
Items in "watch later" playlists cannot be retrieved through the API.

とあります…

これが載っているのは英語版だけで、日本語版にアクセスすると書いていません。古い翻訳が残っている感じでしょうか… 軽くググった限りでもそこそこ差分があるようなので、英語版を翻訳して読んだほうがよさそうです。

非公開・削除済み動画を検出する

非公開・削除済みの動画が再生されるとアラームにならないので、ランダム再生から除外する必要があります。

公式のフラグは 3 秒で見つけられなかったので、サムネイルが存在するかどうかで判定しました。 *3 playlistItem.Snippet.Thumbnails.Standard == null なら、非公開か削除されている…はずです。

*4

参考文献

https://developers.google.com/youtube/v3/getting-started
こんな記事を読まなくても、公式のドキュメントを見ると雰囲気で分かります。サンプルも充実しているのでとりあえず動かしてみることができます。（最新版のコードである保証はないですが…？）

https://developers.google.com/youtube/v3/docs
API リファレンスです。何が返ってくるかはこちらを参照してください。

おわりに

思っていたよりだいぶ簡単に YouTube の情報にアクセスできることが分かりました。
ここ 2 日ほど稼働試験してみていますが、普通のアラーム音より快適に起きられます。とりあえずお歌リストを突っ込んだところ、朝一番でイントロクイズを楽しむことができています。（？）

内容がだいぶ薄い感じなので参考になるか微妙ですが、インストール手順の記録がてら残しておきます。

*1:それで何度かお昼になっていたことがあります……

*2:普通のアカウントでは 外部 しか選べなさそうです。

*3:後で調べたところ status.privacyStatus がそれらしいですが、試せていません

*4:完全に余談ですが、この検証の際に 湊あくあ さんの magnet が非公開になっているのに気づいてしまいました…

.NET 標準ライブラリの新機能と、乱数生成における利用

はじめに

2020/11/10 に .NET 5 がリリースされました。 🎉

何気なく MSDN を見ていると、結構便利なメソッドがちょくちょく追加されていることに気づいたので、擬似乱数の実装（または、何らかの数学的処理や黒魔術）で役立ちそうなものを実例と合わせてピックアップして紹介します。加えて、古い環境で悲しみを背負った場合のために、代替実装もできる限り載せておきたいと思います。

普段が .NET Standard 2.0 だったり果ては .NET Framework 4.5.2 だったりする民なので、最新環境の方からすれば既知の情報が多いかもですがご容赦ください。 また、.NET 5 に限らず、比較的新しめ[要出典]の .NET Core 3.0 あたりで追加されたものについても取り上げていきます。

System.Math

数学ライブラリ System.Math にもいくつか追加があります。

BigMul (.NET 5)

public static ulong BigMul (ulong a, ulong b, out ulong low);

a * b を 128 bit で計算して、上位 64 bit (と out 引数で下位 64 bit) を返します。 使用例としては、 64 bit の乱数を 0 <= x < max の範囲に加工するときが挙げられます。

// Next() は ulong (64 bit) の乱数を返すものとします

// [0, max) の乱数を得ます
static ulong Next(ulong max) => Math.BigMul(Next(), max, out _);

どうしてこれが成り立つのかは、小数点以下 64 bit の固定小数点数に見立ててみると分かりやすいです。 Next() / 2^64 は 0 <= x < 1 となるので、それに max を掛ければ 0 <= x < max が得られるというわけです。上位 64 ビットだけ取り出すことで / 2^64 の部分と同じ効果が得られます。 *1

上の例のように、コストの重い除算や剰余算の代替として使える場合があります。 *2 そこそこ使う割に実装しようとすると面倒なので、標準で採用されて本当にうれしいです。

代替実装の例を以下に挙げます。 *3

public static (ulong lo, ulong hi) BigMul(ulong a, ulong b)
{
    ulong
        ahi = a >> 32,
        alo = a & uint.MaxValue,
        bhi = b >> 32,
        blo = b & uint.MaxValue;

    ulong tlo = alo * blo;
    ulong thi = ahi * bhi;

    ulong tmid = (ahi - alo) * (blo - bhi);
    long carry = tmid == 0 ? 0 : (long)(ahi - alo) >> 63 ^ (long)(blo - bhi) >> 63;

    tmid += tlo;
    if (tmid < tlo)
        carry++;

    tmid += thi;
    if (tmid < thi)
        carry++;

    carry <<= 32;
    ulong lo = tlo + (tmid << 32);
    if (lo < tlo)
        carry++;
    ulong hi = thi + (tmid >> 32) + (ulong)carry;

    return (lo, hi);
}

BitIncrement / BitDecrement (.NET Core 3.0)

public static double BitIncrement (double x);
public static double BitDecrement (double x);

指定した浮動小数点値の次に大きい・小さい値を返します。例えば 1 を渡すと、それぞれ 1.0000000000000002, 0.9999999999999999 を返します。

乱数生成のほうでは、例えば厳密に 0 <= x < max の範囲を求めたい際に計算誤差で x == max となってしまった場合に 1 つ小さくして x < max を保証する、といった使い方をします。 *4

今までは擬似 union でビットレイアウトを重ねることで、整数として +1/-1 してまた戻す、といった手法で実現していました。

[StructLayout(LayoutKind.Explicit)]
internal struct DoubleUint64Union
{
    [FieldOffset(0)]
    public double d;

    [FieldOffset(0)]
    public ulong i;
}

public static double BitIncrement(double d)
{
    if (double.IsNaN(d) || double.IsInfinity(d))
        return d;

    if (d == 0)
        return double.Epsilon;

    var conv = new DoubleUint64Union() { d = d };
    if (d > 0)
        conv.i++;
    else
        conv.i--;

    return conv.d;
}

public static double BitDecrement(double d)
{
    if (double.IsNaN(d) || double.IsInfinity(d))
        return d;

    if (d == 0)
        return -double.Epsilon;

    var conv = new DoubleUint64Union() { d = d };
    if (d > 0)
        conv.i--;
    else
        conv.i++;

    return conv.d;
}

FusedMultiplyAdd (.NET Core 3.0)

public static double FusedMultiplyAdd (double x, double y, double z);

x * y + z を返します。いわゆる積和演算というものです。 一見存在意義が不明そうですが、通常の x * y + z が (t =) x * y と t + z の 2 回丸め処理が入るのに対し、このメソッドでは 1 回だけに抑えることができます。したがって等価な計算ではないため、互いに置き換えると結果が微妙に変わる場合があって注意が必要です。

実用的には、例えば 0.0 <= x < 1.0 の乱数を min <= x < max に加工する際に FusedMultiplyAdd(x, max - min, min) などとして使えます。

これについてはソフトウェア的に再現するのが面倒そうです。 他の言語で fma などとして使われているものを正しく移植する際にも役立ちそうです。

ScaleB (.NET Core 3.0)

public static double ScaleB (double x, int n);

x * 2^n を返します。こちらも効率的らしいです。 n には負値も指定できます。

実用的には、64 bit の乱数を 0.0 <= x < 1.0 の浮動小数点数に変換する際に使えそうです。 (ほぼ)等価な演算と合わせて例を載せます。

double NextDouble() => Math.ScaleB(Next() >> 11, -53);
// double NextDouble() => (Next() >> 11) * (1.0 / (1ul << 53));

（ちなみに少し試した感じでは、結果はほぼ同じで後者のほうが若干速い気がしました…　環境によるのでしょうか…？）

System.MathF (.NET Core 2.1)

System.Math の float 版です。 Unity の UnityEngine.Mathf とは微妙に文字が違います…

float 版のメソッドを作成する際にキャストが不要になるため便利です。 （結構前からあったようですが気づきませんでした…）

System.BitConverter

Int32BitsToSingle / SingleToInt32Bits (.NET Core 2.0)

public static float Int32BitsToSingle (int value);
public static int SingleToInt32Bits (float value);

float ⇔ int の変換を行います。キャストと違うのは、 浮動小数点数のビット構造 をそのままコピーする点です。 例えば、 SingleToInt32Bits(1f) == 0x3f800000 となります。 今までは BitIncrement の項と同じように擬似 union で得ていました。

実用例としては、整数 (uint/ulong) の出力を浮動小数点数に変換する手法のひとつが知られています。

// returns 0f <= x < 1f
float NextFloat() => BitConverter.Int32BitsToSingle(0x3f800000 | NextUint() >> 9) - 1f;

雑に解説すると、ビットパターン 0x3fxXXXXX (x = 8~f) は (1.xXXXXX * pow(2, 0))、すなわち 1.0f <= x < 2.0f となります。そこから 1 を引いて　0f <= x < 1f を得ています。

なお、double ⇔ long 版の Int64BitsToDouble, DoubleToInt64Bits は昔 (.NET Framework 1.1) から存在しました。なぜ double だけ…とか言いながら float 版の互換実装を用意する必要がなくなりました。

ところで、なぜ float ⇔ uint, double ⇔ ulong ではないのか、と思ったのは私だけではないと信じています…　完全に推測ですが CLS 準拠 のためかと思っています。

System.Buffers.Binary.BinaryPrimitives (.NET Core 2.1)

クラスの存在自体気づいていませんでした…

ReverseEndianness

public static ulong ReverseEndianness (ulong value);
(その他のプリミティブ型も同様)

バイトオーダーを逆転させます (いわゆる BSWAP です)。 0x0123456789abcdef ⇔ 0xefcdab8967452301 となります。 まれに BSWAP を使ったプログラムを書きたくなったときに便利そうです…？ *5

今までは System.Net.IPAddress.HostToNetworkOrder (かその逆) の目的外使用をすることもあったかと思いますが、正式にこちらが使えそうです。ちなみに、普通に実装しようとすると以下のようになります。

ulong ReverseEndianness(ulong x) 
{
    x = (x & 0x00ff00ff00ff00ff) << 8 ^ (x >> 8 & 0x00ff00ff00ff00ff);
    x = (x & 0x0000ffff0000ffff) << 16 ^ (x >> 16 & 0x0000ffff0000ffff);
    return x << 32 ^ x >> 32;
}

ちなみにちなみに、 ReverseEndianness(byte value) とかいう虚無も存在します。なにもしません。

このクラスには、これ以外にも ReadOnlySpan<byte> からそれぞれのエンディアンでプリミティブ型を読み込む・書き込むメソッドが用意されています。

System.Half (.NET 5)

16 bit の浮動小数点型です。精度を犠牲にするかわりに、スペースや処理負荷を軽減する際に使う用です。

今のところは別環境との相互運用のためにあるらしく、直接計算はできず、比較や float / double へのキャストのみが行えます。 導入の経緯については 公式のブログ に詳しいです。

ちなみに、まだ half ではありません。Half と大文字で書く必要があります。

おわりに

書き終わってみると .NET 5 より前に出ていた API が多いですね…　アンテナが低いです…

この記事を要約すると Math.BigMul がうれしい になります。他にも Index/Range や Span, MemoryMarshal.Cast など、便利アイテムが続々追加されているので (例によって .NET 5 よりも前からあるものですが)、興味のある方は調べてみてください。

いつの日か Unity で使えることを願って……

*1:なお、この使い方は厳密には正しい分布が得られないことは注記しておきます。 max が 2 のべき乗でなければわずかに生成確率に偏りが生じます。偏らない改善手法などについては https://www.pcg-random.org/posts/bounded-rands.html が詳しいです。

*2:実測だとあまり変わらない場合もありますが…

*3:Karatsuba 法の勉強もかねて実装したのですが、安直に 4 回乗算する手法のほうがなぜか早くなってつらみを背負っています…？正直あまり自信がないので安直にやったほうがいい気もします

*4:C# ではないですが、Java の Random.doubles(double, double) の実装において見られます。

*5:擬似乱数の出力関数の設計をするときに使っていたことがありました。キャリーによる非線形性は上位ビットに集まりがちなので、これで上下を入れ替えてまんべんなく非線形にしよう、という狙いがありました。例えば bswap(s0 + s1) + s1 など。

Z3 Solver で擬似乱数の内部状態を復元する＋α

はじめに

擬似乱数の出力列から内部状態を復元することができれば、未来予測が可能になります。 以前の記事 でその一部を紹介しましたが、その構造についてよく理解して解析する必要があるなど、手間がかかっていました。 ここでは、ツールを使っていい感じに問題を解いてもらう方法について紹介します。

Z3 Solver

Z3 は、Microsoft Research が開発している SMT ソルバです。 私もふんわり使用しているだけなので適当に説明すると、関係式をいくつか投入すると、それらの式が成立するか、もし成立するなら値が何のときか、といったことを求めてくれるプログラムです。例えば、

* x, y は自然数
* x + y == 5
* x >= 3

をすべて満たす x, y は存在するか?

に対して、

(x = 3, y = 2) のとき成立する

といった感じで答えが返ってきます。

様々な言語に対応しており、Readme 曰く python, C++, C#, Java などで使えます。

C# での利用

NuGet で Microsoft.Z3.x64 をインストールすれば使えるようになります。

実装例を以下に示します。これは上に挙げた例を実際にコード化したものです。

using (var context = new Context())
using (var solver = context.MkSolver())
{
    // 変数 x, y を定義
    var x = context.MkIntConst("x");
    var y = context.MkIntConst("y");

    // 関係式 x + y == 5 を追加
    solver.Assert(context.MkEq(context.MkAdd(x, y), context.MkInt(5)));

    // 関係式 x >= 3 を追加
    solver.Assert(context.MkGe(x, context.MkInt(3)));


    // 式が成立するかを調べて、成立すればそれを出力
    var issat = solver.Check();
    Console.WriteLine(issat);

    if (issat == Status.SATISFIABLE)
    {
        Console.WriteLine(solver.Model);
    }

}

実行すると以下の出力を得ました。計算できていることが分かります。

SATISFIABLE
(define-fun y () Int
  2)
(define-fun x () Int
  3)

なお、解が複数あったとしてもそのうちのどれか一つが得られます。今回で言えば (x = 4, y = 1) も条件を満たしますが、こちらは得られるとは限りません。
また、どうやっても成立しない場合は UNSATISFIABLE が得られます。

記述がつらい

上の例を見れば分かると思いますが、Z3 では関係式の記述はすべてメソッド context.Mk***() を通して行います。とてもつらいので、普通の式と同じように演算子を使って書きたくなります。 ということで、ちょっとしたラッパー RngSolver を実装しました。 RngSolver と書いてはいますが、乱数用途以外にも使えるかもです。

https://github.com/andanteyk/RngSolver

詳しくは SolveRng.cs を参照してください。

実用例

xoshiro256+ の内部状態復元

上述した RngSolver の SolveRng.cs をちょっといじって、 xoshiro256+ の内部状態復元を試みます。 解説コメントも適当に付け足しました。

public static void Solve()
{
    // seed: 適当なシード値(正解)
    var seed = new ulong[] { 0x0123456789abcdef, 0xfedcba9876543210, (ulong)Environment.TickCount, (ulong)DateTime.Now.Ticks }
        .Select(s => new Arithmetic(s)).ToArray();

    // outputs: 観測された出力
    // 今回は検証目的なのでシードから実際に出力させて outpus を設定していますが、
    // 実際に観測から復元するときは outputs に直接突っ込みます
    var outputs = new Arithmetic[seed.Length + 1];
    {
        var clone = seed.Select(s => s.Identity()).ToArray();
        for (int i = 0; i < outputs.Length; i++)
            outputs[i] = Next(clone) as Arithmetic;
    }


    Console.WriteLine($"start: {DateTime.Now:yyyy/MM/dd HH:mm:ss.fff}");

    using (var context = new Context())
    using (var solver = context.MkSolver())
    {
        // state を変数として宣言
        var state = Enumerable.Range(0, seed.Length).Select(i => new BitVecWrapper(context.MkBVConst("state" + i, 64), context)).ToArray();

        // 「出力列 [Next(state), ...] が outputs と等しい」制約を設定
        for (int i = 0; i < outputs.Length; i++)
        {
            var res = Next(state);
            solver.Assert(res.Equals(outputs[i]) as BoolExpr);
        }


        // したがって、outputs と同じ出力を生成する内部状態 state が得られる（かも）
        var issat = solver.Check();
        Console.WriteLine(issat);

        if (issat == Status.SATISFIABLE)
        {
            Console.WriteLine(solver.Model);
        }

    }

    Console.WriteLine($"end  : {DateTime.Now:yyyy/MM/dd HH:mm:ss.fff}");
}

// RngSolver を使うと、以下のように関係式定義が簡潔に行え、 Mk***() 地獄を回避できます 
// ついでに ulong と BitVecExpr の計算を 1 つの定義で行えます
// このメソッドを書き換えれば別の乱数の出力推測ができます
public static IArithmetic Next(IArithmetic[] s)
{
    var result = (s[0] + s[3]);

    var t = s[1] << 17;

    s[2] ^= s[0];
    s[3] ^= s[1];
    s[1] ^= s[2];
    s[0] ^= s[3];

    s[2] ^= t;

    s[3] = s[3].Rol(45);

    return result;
}

実行すると以下が得られました。40 秒程度で、連続した 64 bit の出力 x 5 から内部状態を復元することができました。

start: 2020/12/05 00:18:56.258
SATISFIABLE
(define-fun state3 () (_ BitVec 64)
  #x08d898b35ac76c8c)
(define-fun state1 () (_ BitVec 64)
  #xfedcba9876543210)
(define-fun state0 () (_ BitVec 64)
  #x0123456789abcdef)
(define-fun state2 () (_ BitVec 64)
  #x00000000465512c4)
end  : 2020/12/05 00:19:32.102

ちなみになのですが、 xoshiro256+ は出力関数に + を用いて非線形な出力を行っています。 *1 そのため、生で吐き出す Xorshift や 出力関数が線形な MT19937 に対して有効な「行列計算を用いた内部状態復元」が適用できず、私が知る限りでは solver 利用が最速の手法となっています。

なお、復元できるかどうかは遷移関数や出力関数の複雑さに依存します。関数によっては n 時間かかったり、 n 日かかっても結果が出なかったりします。

x << 2 ^ x >> 19 の可逆性

以前話に出した、 long x; x << 2 ^ x >> 19 (>> は右算術シフトです) が逆算可能かどうか＝可逆であるかを調べたいとします。 厳密には数学的に証明する必要がありますが、今回はソルバーでざっくり調べます。

全ての x に対して逆算可能である、と示すのは大変なので、逆算ができない x が存在しないことを求める方針で実装します。 例えば異なる a, b を入力として同じ結果 z が得られた場合、逆算 inv(z) の値が a, b の "どちらか" になってしまいただ一つに決定できなくなります。したがって、そのような a, b が存在すれば逆算不可能、存在しなければ逆算可能であるといえるでしょう。前の項とは逆に、成立不可能 UNSATISFIABLE であれば嬉しいわけです。

それをコードに落とし込んだのが Invertible.cs です。ちょっと改造・補足説明して、以下に示します。

public static void IsInvertible()
{
    Console.WriteLine($"start: {DateTime.Now:yyyy/MM/dd HH:mm:ss.fff}");

    using (var context = new Context())
    using (var solver = context.MkSolver())
    {
        // 上の説明で言う a, b を定義
        var state = Enumerable.Range(0, 2).Select(i => new BitVecWrapper(context.MkBVConst("state" + i, 64), context)).ToArray();

        // (a != b) かつ (f(a) == f(b)) を満たす (a, b) ？
        solver.Assert(state[0].NotEquals(state[1]) as BoolExpr);
        solver.Assert(Output(state[0]).Equals(Output(state[1])) as BoolExpr);


        // 成立しなければ逆算可能、成立すれば逆算不可能
        var issat = solver.Check();
        Console.WriteLine(issat);

        if (issat == Status.SATISFIABLE)
        {
            Console.WriteLine(solver.Model);
        }

    }

    Console.WriteLine($"end  : {DateTime.Now:yyyy/MM/dd HH:mm:ss.fff}");
}

// x << 2 ^ x >> 19
public static IArithmetic Output(IArithmetic s)
{
    return s << 2 ^ s.Sar(19);
}

これは速やかに UNSATISFIABLE を得ます。したがって、全ての入力に対して逆算ができることが示されました。 （しかしここでは具体的な逆算方法は得られません。自分の目で確かめてみてください。）

start: 2020/12/05 00:51:00.302
UNSATISFIABLE
end  : 2020/12/05 00:51:00.382

では、 x << 6 ^ x >> 19 はどうでしょうか。末尾の Output を書き換えて実行してみると…

start: 2020/12/05 00:53:05.689
SATISFIABLE
(define-fun state1 () (_ BitVec 64)
  #x4b206621b61e1a1b)
(define-fun state0 () (_ BitVec 64)
  #x4f206623b61e1b1b)
end  : 2020/12/05 00:53:05.778

SATISFIABLE を得ます。いわば「反例を得た」状態であり、入力を 0x4f206623b61e1b1b および 0x4b206621b61e1a1b とした場合の出力が一致するため、逆算ができない場合があることが示されました。 実際に計算すると同一の出力 0xc81981098b42b003 が得られます。

ついでに x << a ^ x >> b は全ての a, b において常に逆算できるわけではないことも分かりました。

おわりに

Z3 solver を用いることで、関係式しか知らない状態からでも条件を満たす値があるかどうかを調べることができました。 「なんかよくわからんが、とりあえず求められたら ﾖｼ!」という問題に対して、最初にぶつけてみるには非常に強力なツールだと思います。

ちなみに、python では最初からもうちょっと楽に使えるらしいです。私は残念ながら python 分からない人なので省略します。 公式のリファレンスも充実しており、Web 上で実際に実行できるチュートリアル なんてすごいものもあります。気になった方は一度見てみると楽しいかもしれません。

*1:+ は線形では？となるかもしれませんが、 の世界では加算は ^ (XOR) です

乱数を巻き戻す

はじめに

(ほぼ) 最大周期を実現している擬似乱数生成器は、状態を巻き戻す（逆方向に進める）ことができます。

例えば xoshiro256 が、以下のように一見ランダムな内部状態を持っていたとしましょう。

var state = new ulong[] { 
    0x010F4C454914CD78, 
    0x83A5678480A2B416, 
    0x2652B51299006A0A, 
    0x900FEBAD58D7C533 };

この状態は、5 回の遷移 (next() 呼び出し) を経て、綺麗に並ぶようになります。

var state = new ulong[] { 
    0x0123456789abcdef, 
    0xfedcba9876543210, 
    0xdeadbeefcafebabe, 
    0x1685819840150026 };

もちろんこれは偶然に任せて求めたわけではなく、最初に下の状態があって、そこから巻き戻して上の状態を求めています。 この記事では、どうやったら巻き戻す関数を設計できるか、を紹介します。

xoshiro256 を巻き戻す

まず、xoshiro256 の内部状態 state を次に進めるメソッド Next() のコードを示します。 遷移関数はもちろん 公式の実装 と同じです。出力はここでは不要なので返り値は void にしています。 *1

// ulong[] state = new ulong[4] {...};
public void Next()
{
    ulong t = state[1] << 17;

    state[2] ^= state[0];
    state[3] ^= state[1];
    state[1] ^= state[2];
    state[0] ^= state[3];

    state[2] ^= t;
    state[3] = rotl(state[3], 45);  // rotate left.
}

public static ulong rotl(ulong x, int k) => x << k | x >> -k;

先に答えを示しておきましょう。内部状態 state を巻き戻すメソッド Prev() のコードを示します。

public void Prev()
{
    state[3] = rotl(state[3], 19);
    state[0] ^= state[3];

    ulong t = state[1] ^ state[2];
    state[1] = t ^ t << 17 ^ t << 34 ^ t << 51;
    state[3] ^= state[1];
    state[2] ^= state[0] ^ state[1] << 17;
}

どのようにして求めたか、順を追って説明していきます。

遷移を分かりやすくするため、遷移前の state を prev として保存しておき、それが Next() を通して次の state にどう反映されるかを見ます。 state の各要素について整理すると以下のようになりました。

public void Next()
{
    // copy of initial `state`
    ulong[] prev = state.ToArray();

    state[0] = prev[0] ^ prev[1] ^ prev[3];
    state[1] = prev[0] ^ prev[1] ^ prev[2];
    state[2] = prev[0] ^ prev[1] << 17 ^ prev[2];
    state[3] = rotl(prev[1] ^ prev[3], 45);
}

まず、簡単そうな state[3] の行を見ていきます。 一番下の rotl (n ビット左回転) は、合わせて 64 ビット回転させることで簡単に元に戻せます。両辺を 64 - 45 = 19 ビット左回転させることで、以下の関係式を得ます：

rotl(state[3], 19) == prev[1] ^ prev[3]    // 64 - 45 = 19

関係式の右辺を観察すると、state[0] = ... の式に同じ要素があることに気づけます。任意の x に対して x ^ x == 0 *2 が成り立つので、両式を XOR で足し合わせると：

rotl(state[3], 19) ^ state[0] == prev[0]

prev[0] を求めることができました！

さて、ここでおもむろに state[1] = ... と state[2] = ... を見ると、やはり右辺が似たような要素で構成されています。両式を XOR すると：

state[1] ^ state[2] == prev[1] ^ prev[1] << 17

この右辺が問題になります。長いので t = prev[1]; とおいて、 t ^ t << 17 から t を得る方法を模索します。一見難しそうですが、意外と簡単に戻せます。

まず、 t ^ t << 17 を 17 bit 左シフトすると ((t ^ t << 17) << 17) == (t << 17 ^ t << 34) となります。これを元の式と XOR すると、t << 17 の項が打ち消しあって 0 になるので t ^ t << 34 になります。この操作によって、シフトを 17 → 34 と大きくできました。この調子でシフトを 64 以上にできれば、64 bit の範囲から全ビットが飛び出して 0 とみなせます。

ビット列を図にするとこんな感じです。すべてを XOR することで同じ色の部分が打ち消しあい、 t すなわち prev[1] を得ることができます。

// 左辺にも同じ操作を適用します
ulong t = state[1] ^ state[2];
prev[1] == t ^ t << 17 ^ t << 34 ^ t << 51

あとは XOR のパズルで消していくだけです。 一番最初の式の両辺に、既知である prev[1] を XOR すれば prev[3] が得られます。

rotl(state[3], 19) ^ prev[1] == prev[3]

そして state[2] の式の両辺に、既知である prev[0] ^ prev[1] << 17 を XOR すれば prev[2] が得られます。

state[2] ^ prev[0] ^ prev[1] << 17 == prev[2]

以上によって、 prev を全て求めることができました。

"xor-shift" 逆算について

上の解説や図では t ^ t << k の逆算で t ^ (t << k) ^ (t << 2k) ^ (t << 3k) ^ ... とシフトを k ずつ増やしていましたが、以下のように代入を挟みながらシフトの k を 2 倍にしていくことで、小さな k に対して効率的に求められます。 *3

t ^= t << k;
t ^= t << (k << 1);
t ^= t << (k << 2);

また、逆算手法は右論理シフト t ^ t >> k に対しても、シフト方向を変えるだけで同様に適用可能です。

では右算術シフトの場合はどうでしょうか。 次式について考えてみましょう。

long t = some_value; 
long u = t ^ t >> k;

この場合、どのような t, k を選択しても u の最上位ビットは 0 になります。 t が正 (最上位ビットが 0) なら t >> k の最上位ビットも 0 、t が負 (最上位ビットが 1) なら t >> k の最上位ビットも 1 になります。これを XOR すれば、正負ともに 0 になってしまいます。

そうなると、異なる t から同一の u が得られるので、 u から t の値を確実に求めることができず、逆算はできなくなってしまいます。

ただし算術シフトが絡むとダメなのかといえばそうではなく、例えば t << k ^ t >> a は特定の k, a のペアで逆算可能になります。 shioi128 で使用されている t << 2 ^ t >> 19 などが該当します。 どのようにして逆算するかは、自分の目で確かめてみてください。 *4

PCG / 線形合同法を巻き戻す

さて次は PCG32 を巻き戻してみましょう。 ここでは出力関数を無視するので、結局のところ線形合同法と同じになります。

// ulong state = ..., ulong incr = ... | 1;
public void Next()
{
    state = state * 6364136223846793005 + incr;
}

例によって結果を先に書くと、 Prev() はこのようになります。

public void Prev()
{
    state = (state - incr) * 13877824140714322085;
}

加算 (incr) のほうは移項するだけなので分かりやすいとして、乗算のほうの定数はどこから来たのでしょうか。

実は、ulong では *5 6364136223846793005 * 13877824140714322085 == 1 となります。したがって (state * 6364136223846793005) * 13877824140714322085 == state となり、逆算できます。

では肝心の定数の求め方はというと、以下の MultiplicativeInverse() メソッドによって求めることができます。任意の奇数に対して上記の性質を満たす値を計算できます。 *6

public static ulong MultiplicativeInverse(ulong x)
{
    if ((x & 1) == 0)
        throw new ArgumentException("x must be odd");

    ulong y = x;
    y = y * (2 - y * x);
    y = y * (2 - y * x);
    y = y * (2 - y * x);
    y = y * (2 - y * x);
    y = y * (2 - y * x);

    return y;
}

メソッド内部の不思議な計算は ニュートン法 に基づいています。 時間と体力が厳しかったので解説はリンク先を参照してください。

おわりに

ここでは乱数を巻き戻す手法について紹介しました。 あまり使いどころはないかもしれませんが、実際ひとつ前の記事ではこれを調査に使っていたりします。

また、計算手法自体は出力関数の逆算にも用いることができます。例えば、Mersenne Twister の tempering (出力関数) を逆に進めて内部状態を復元するときに使えたりもします。

あえて xoshiro をチョイスしたのは、 Xorshift など有名なもの・実用されているものは先行研究が充実していて盛大に被ったためです。 それらの逆算に興味がある方は以下の記事が大変参考になります。

• TinyMT の更新関数 tinymt32_next_state(tinymt32_t*) の逆関数に関する考察 - Plus Le Blog
• Xorshift の逆関数に関する考察／正逆双方向に計算できる Xorshift - Plus Le Blog
• xoroshiro128+の状態遷移の逆算の考察 - HackMD

*1:念のため説明しておくと、C# の ulong は符号なし 64 bit 整数を表します。C の uint64_t に相当するものです。

*2:XOR のほうです、念のため

*3: を にする感じです

*4:いつか気力があったら書きます……

*5:数学っぽく言えば、 を法として

*6:偶数は何を掛けても偶数になるため、 1 になりません。したがって計算不能です。

UnityEngine.Random の実装と性質

はじめに

Unity では、組み込みの擬似乱数生成器として UnityEngine.Random が用意されています。 この記事では、その実装や特徴について追っていきます。

※本記事の内容は Unity 2020.1.3f1 の Windows Editor にて確認したものです。

内部実装

UnityEngine.Random の遷移関数は Xorshift アルゴリズムで実装されています。 Xorshift には変種が色々ありますが、一番メジャーな実装 (Wikipedia の xor128 と同じもの) を使用しています。

// uint[] State = new uint[4] { ... };

public uint Next()
{
    uint t = State[0] ^ State[0] << 11;
    State[0] = State[1];
    State[1] = State[2];
    State[2] = State[3];
    return State[3] = State[3] ^ State[3] >> 19 ^ t ^ t >> 8;
}

内部状態

内部状態は UnityEngine.Random.State 構造体 として保持されており、 state プロパティ 経由で取得・設定できます。

この構造体の中身は { int s0, s1, s2, s3; } のようになっています。各メンバーはパブリックではないので直接編集するにはリフレクションを使う必要があります。加えて、 uint ではないため注意が必要です。

内部状態を uint[] で取得・設定するメソッドは以下のようになります。(雑)

public uint[] GetBuiltinState()
{
    var stateObject = UnityEngine.Random.state;

    return stateObject.GetType().GetFields(BindingFlags.NonPublic | BindingFlags.Instance)
        .OrderBy(field => field.Name)
        .Select(field => (uint)(int)field.GetValue(stateObject))
        .ToArray();
}

public void SetBuiltinState(uint[] state)
{
    var stateObject = new UnityEngine.Random.State();

    stateObject.GetType().GetFields(BindingFlags.NonPublic | BindingFlags.Instance)
        .OrderBy(field => field.Name)
        .Select((field, i) => { field.SetValue(stateObject, (int)state[i]); return 0; })
        .ToArray();

    UnityEngine.Random.state = stateObject;
}

初期化

明示的に初期化するときに使う InitState メソッド の実装を調べてみましょう。 試しに公式サンプルにあった InitState(42) を呼び出すと、以下の内部状態が得られました。

0x0000002A, 0xB93C8A93, 0x49105700, 0xF3015301

[0] はそのまま引数の値 (42) のようです。後続はランダムなようですが、最下位ビットが 0, 1, 0, 1 となっており、なんとなく線形合同法の雰囲気があります。 実際にパラメータの逆算を試してみると、同じ数列を生成する線形合同法のパラメータを得ることができました。 *1 再現コードを以下に示します。

// uint State[4] として
public void InitState(uint seed)
{
    for (int i = 0; i < 4; i++)
    {
        State[i] = seed;
        seed = seed * 1812433253 + 1;
    }
}

なお、ビルドしたアプリの起動時・エディタ起動時の初期状態は、InitState() 以外の方法で計算されているようです。 初期状態から 1000000 回前の状態まで遡ってみましたが *2 、どれも線形合同法の関係式を満たしませんでした。

ちなみにエディタ上では、内部状態はプレイをまたいで保持されていそうでした。 プレイ → InitState() → プレイ終了 → プレイ、とすると、前回設定したシード近辺の値が得られました。*3 エディタをいったん終了して再起動すると何らかの初期値が設定されます。 もちろんビルドしたアプリでは、何らかの方法できちんと毎回違うシードが設定されているようです。

出力

一様乱数を求める Random.value と Random.Range の実装を調べてみます。 出力を調べたところ、概ね以下の値を返すことが分かりました。

// public uint Next() がある前提で

// returns [0, 1]
public float value => (Next() & 0x7fffffu) / 8388607.0f;

// returns [min, max)
public int Range(int min, int max) => min + (int)(Next() % (uint)(max - min));

// returns [min, max]. note: 近似値を返します
public float Range(float min, float max)
{
    float t = value;        // [0, 1]
    return t * min + (1 - t) * max;
}

概ね、としたのは float Range の出力について、計算誤差？で微妙に最下位桁付近が合わない場合があるためです。上に挙げた式では正解率 70% 程度でした。もし正しい式をご存知の方がいらっしゃいましたら教えていただけると嬉しいです…

value の定数はどちらも値としては同じ 8388607 、言い換えれば です。したがって、value の出力は概ね 23bit 精度で行われていることになります。

注記すべき点としては、value 及び float Range の出力は max を含みます。 他の言語やシステムで一般的な max を含まない出力を受け付ける前提のアルゴリズムをそのまま使用した場合 (例えば Math.Log(1 - Random.value) など)、-∞ などの予期しない値を返す可能性があるため注意が必要です。 と低確率ではありますが…

また面白い点として、int Range では Next() が大きくなるほど出力が大きくなるのに対し、 float Range では Next() が大きくなるほど出力が小さくなるようになっています。 t と 1 - t は交換しても分布が変わらないためでしょうか…？

float Range の実装が、よりシンプルである min + value * (max - min) ではない理由としては、計算誤差が上記の実装よりも大きくなるから、と推測しています。この辺りは 英語版 Wikipedia の「線形補完」の記事 に情報があります。

ちなみに、ColorHSV など一部のメソッドの実装は、UnityCsReference から確認できます。

遊んでみる

さて、内部実装が分かれば、性質を利用していろいろと遊ぶことができます。

すべて 0 の state を入れて Random を壊す

Random.state = new Random.State(); とすることで、以降 Next() から出力される乱数はすべて 0 になります。 私の環境では、それぞれ以下の数値だけを出力するようになりました。

value = 0
insideUnitCircle = (1, 0)
insideUnitSphere = (0, 0, 0)
onUnitSphere = (0, 0, 1)
rotation = (0.5, 0.5, 0.5, 0.5) (-> euler 0, 90, 90)
rotationUniform = (0, 0, 0, 0) (-> euler 0, 0, 0)
ColorHSV() = (0, 0, 0, 1) (-> Black)
Range(2, 12) = 2
Range(2f, 12f) = 12f

なお、前述したように内部状態はエディタを閉じるまで維持されるため、プレイを終了してもこの状態は残ります。大変邪悪ですのでよいこは真似しないでください。 解除したい場合は InitState() を適当な数値で呼び出してください。

出力から内部状態を復元する

いわゆる乱数調整というやつです。全ての内部状態が計算できれば、将来（あるいは過去）の乱数列を予測・取得することができます。

ベースは Xorshift ですから、出力から生のビット (内部状態がそのまま露出しているビット) が得られれば行列計算で内部状態復元が可能です。 行列計算については汎用的なものなので詳細は別の記事に譲るとして、Unity の出力関数から生のビットを得る方法について検討します。

value 経由

ではない数で割っているので、直接ビットを抽出することはできません。とはいえ 8388607.0 を掛ければほとんどの上位ビットは復元できるはずです。 23 bit のうち上位 16 bit だけを使って 8 個の出力を観測する、のが無難でしょうか。

// value の出力から State[3] & 0x007fff80 の情報を得ます
public static uint ReverseValue(float value) =>
    ((uint)(value * 8388607.0) & 0x7fff80);

不安定な下位ビットも取得したい場合は、& の定数を 0x7fffff としてください。

最も、乱数は大抵 [0, 1] のままではなく特定の範囲に加工して使うので、プレイヤーが value の値を直接観測できるかというと難しいとは思いますが…

int Range() 経由

max - min が偶数ならビットを抽出できます。 なら n ビット全部使えるのでなおよいです。 実用上は最も観測しやすいものかと思います。

// Range(int min, int max) の出力から State[3] の下位 n bit の情報を得ます。
// n == tzcnt(max - min)
public static uint ReverseIntRange(int value, int min, int max)
    => (uint)(value - min) & ((1u << tzcnt((uint)(max - min))) - 1);

ややこしいことをしているように見えますが、要するに max - min の下位ビットが 0 になっているところだけ取り出すイメージです。例えば min = 0, max = pow(2, n) なら単に n ビットを取り出せばよいです。

なお、tzcnt は最下位から連続する 0 ビットの個数を返す関数とします。 System.Numerics.BitOperations.TrailingZeroCount() と等価です（が、このメソッドは Unity から簡単に参照できないようです…）。

float Range() 経由

基本的には value と同様ですが、ただでさえ近似値のところに計算を重ねるため、誤差が大きくなりそうです。 値域を [min, max] から [0, 1] に変換したうえで、value と同じ逆算を行う例を示します。

// Range(float min, float max) の出力から State[3] & 0x007fff80 の情報を得ます
// ReverseValue は上述
public static uint ReverseFloatRange(float value, float min, float max)
    => ReverseValue((max - value) / (max - min));

ランダムな min, max に対してこのメソッドを試した限りでは、上位 16 bit を得ようとした場合の正解率は 1 回あたり 99 % 程度でした。完全復元には 128 bit 分の情報量、つまり連続 8 回の成功が必要となるので、全体としての成功率は概ね 92 % 程度でしょうか。 計算誤差の大きさに依存するので、max と value がほぼ等しい場合などでは成功率が落ちそうではあります。

おわりに

この記事では、 Unity 組み込みの擬似乱数生成器 UnityEngine.Random の実装と性質について調べました。 好きに書いた結果散らかってしまいましたが、思っていた以上に発見があり楽しかったです。

誤り・追加情報等あればご指摘いただけると助かります。

*1:計算方法については別の記事に書ければと思います

*2:Xorshift は状態を過去の方向に進めることも可能です。こちらの記事に理論と文献リンクがあります

*3:終了時の状態から 1-3 個程度進んでいる場合があります。