undefined

bokuweb.me

Rustで書いたWebAssemblyインタプリタ上でGoで書いたゲームボーイエミュレータを動かした

概要

最近はWebAssemblyに興味があり、勉強していたんだけど仕様を読み始めても頭に入らないのでインタプリタを作ってみることにした。よくわからないものは作ってみるのが一番よい。

github.com

まだ残された課題は多いのだけれども、一つ目標にしていた「Goで書いたゲームボーイエミュレータを動かす」を達成できたのでここに書いておく。

こツイートに貼られているのは残念ながら、静止画ではなく、動画でありパフォーマンスが悲しいことになっていることを示している。あまりに遅くてプレイ画面まで到達できない。今後これは改善していきたい。

Goでゲームボーイエミュレータを書いた話は以下の記事を参照のこと。

blog.bokuweb.me

blog.bokuweb.me

インタプリタを作る

仕様書を読みながら実装していくのだけど、日本語でさくっと全体を知るのに以下のリポジトリがとても参考になった。

github.com

Hello wasm

開発は最小限のバイナリを実行できるようにし、そこに命令を足していく方針で進めた。これにはWebAssembly Studioがとても役立った

webassembly.studio

これでEmpty Wat Projectを開くとプロジェクトが作成されいくつかのファイルが生成される。この中のmain.watを書き換えて実行したり、バイナリを覗いたりすることができる。*.watというのはWebAssemblyのテキストフォーマットでWebAssembly/wabt*.wasmに変換したり、ランタイムの一つであるwasmtimeで実行できたりする。

例えば一番シンプルな42を返すだけの関数を定義してみるとこうなる。

  • main.wat
(module
  (func $hello (result i32)
    i32.const 42)
  (export "hello" (func $hello))
)

呼び出し側のJSは以下のようになる

fetch('../out/main.wasm').then(response =>
  response.arrayBuffer()
).then(bytes => WebAssembly.instantiate(bytes)).then(results => {
  instance = results.instance;
  document.getElementById("container").textContent = instance.exports.hello();
}).catch(console.error);

これを実行すると42が返ってくることがわかる。

インタプリタを作る上で便利なのはBinary Explorerという機能でプロジェクトの成果物である*.wasmを解析し表示してくれる。例えば今回のサンプルであれば以下のようなものが表示される。mousehoverで詳細も表示してくれる。

f:id:bokuweb:20200312025514p:plain

先頭の橙色はマジックナンバー。重要なのは(このサンプルでは)2Byteの赤色の箇所、具体的には01 05のような箇所だ。これはセクション番号とそのサイズを表している。

セクションの番号と概要は以下のようなになっている

番号 セクション名 概要
0x1 Type 関数シグネチャー宣言
0x2 Import インポート宣言
0x3 Function 関数宣言
0x4 Table テーブル宣言
0x5 Memory メモリー属性
0x6 Global グローバル宣言
0x7 Export エクスポート
0x8 Start 開始関数宣言
0x9 Element 要素セクション
0xA Code 関数実体
0xB Data データセグメント

0x00はカスタムセクションだが今回は不要なため無視するとして、0x01 Typeセクション0x03 Functionセクション0x07 Exportセクション0x0A Codeセクションが含まれていることがわかる。

ここでは端折って0x07 Exportセクション0x0A Codeセクションについて見ていく。

0x07 Exportセクション

Exportは以下のようなデータで表現されており、先頭の0x07はセクション番号、次の0x09はセクションのデータサイズを示す。

f:id:bokuweb:20200312025532p:plain

紫部分の先頭の0x01はExportするエントリ数。今回はhelloという関数のみをExportしているので0x01。次の0x05はExport名の長さを示す。

f:id:bokuweb:20200312025548p:plain

Export名の長さが0x05であることがわかったので、次の5Byte0x68 0x65 0x6c 0x6c 0x6fを見るとこれがhelloであることがわかる。

f:id:bokuweb:20200312025600p:plain

末尾の0x00 0x00だが、前者はExport種別を表す。今回は関数をExportしているので0x00だが、MemoryやTableなどもExportできる。

最後尾はインデックスで今回の場合はモジュールが持っている関数一つの中から先頭の関数をExportしているので0x00になる。

f:id:bokuweb:20200312025615p:plain

詳細は省いているが、Rustで書くと以下のようになった。

impl Decoder for ExportSection {
    type Error = DecodeError;

    fn decode<R: Read>(reader: &mut R) -> Result<Self, Self::Error> {
        let count: u32 = VarUint32::decode(reader)?.into();
        let mut entries: Vec<ExportEntry> = vec![];
        for _ in 0..count {
            let field_len = VarUint32::decode(reader)?.into();
            let name = read_bytes(reader, field_len)?;
            let name = String::from_utf8(name)?;
            let kind = read_next(reader)?;
            let kind = ExternalKind::from_u8(kind)?;
            let index: u32 = VarUint32::decode(reader)?.into();
            entries.push(ExportEntry { name, kind, index });
        }
        Ok(ExportSection { count, entries })
    }
}
LEB128

順番が前後するが、例えばExport数を表すcountや最後尾のExportするエントリのインデックスの型はなにかと言うとu8u32ではなくvaruint32になっている。これはLEB128という可変長の整数エンコード形式で表現された型で、値の大きさと表現にバイト数が比例する。

具体的にはMSBがデータの継続を表すフラグとして使用されており、実データ部は8bitのうち7bitになる。つまり100であれば1byteで表現できるし、255であれば表現に2byte必要になる。u32において4byteで表現されていたデータを表現するのに5byte必要になることもあるが、多くの場合で固定で4byte確保するよりバイナリを小さくできる。のだと思う。

もともとはデバッグ用ファイルフォーマットのDWARFのために設計されたものらしい。知らなかった。

もし、wasmファイルをごにょごにょするものを作るなら早い段階でLEB128を読めるようにする必要がある。

実装は愚直にMSBをチェックしながら結合していく実装になっている。より効率的な読み方があったら教えて下さい。。。

impl Decoder for VarUint32 {
    type Error = DecodeError;

    fn decode<R: io::Read>(reader: &mut R) -> Result<Self, Self::Error> {
        let mut value = 0;
        let mut i = 0;
        loop {
            let b = u32::from(read_next(reader)?);
            value |= (b & 0x7f)
                .checked_shl(i * 7)
                .ok_or(DecodeError::InvalidVarUint32Error)?;
            i += 1;
            if i > 5 {
                return Err(DecodeError::InvalidVarUint32Error);
            }
            if b & 0x80 == 0 {
                if i == 5 && b >= 0x10 {
                    return Err(DecodeError::InvalidVarUint32Error);
                }
                break;
            }
        }
        Ok(VarUint32(value))
    }
}

Exportはこれで完了で、つまり外部からhelloが呼ばれたら関数インデックス0の関数を実行すればいいということがわかる。

0x0A Codeセクション

じゃあ関数がどのようになっているかとCodeセクションを見れば良い。 先頭の0x0A 0x06はExportのときと同様セクション番号とサイズだ。

f:id:bokuweb:20200312025720p:plain

0x01 0x04 0x000x01はエントリ数、0x04はエントリのBodyサイズ、0x00はローカル変数の数を表す。

f:id:bokuweb:20200312025733p:plain

0x41 0x2A 0x0Bはいよいよバイトコード部、すなわちi32.const 42に該当する部分になる。0x41i32.const0x2A42を表しており、0x0Bendを表している。

f:id:bokuweb:20200312025800p:plain

ちょっと複雑だけれども、やっていることはExportセクションのデコードと変わらず愚直に読んでいくことになると思う。

impl Decoder for CodeSection {
    type Error = DecodeError;

    fn decode<R: Read>(reader: &mut R) -> Result<Self, Self::Error> {
        let count: u32 = VarUint32::decode(reader)?.into();
        let mut bodies: Vec<FunctionBody> = vec![];
        for _ in 0..count {
            let body_size: usize = VarUint32::decode(reader)?.into();
            let mut body = Cursor::new(read_bytes(reader, body_size)?);
            let local_count: u32 = VarUint32::decode(&mut body)?.into();
            let mut locals: Vec<LocalEntry> = vec![];
            for _ in 0..local_count {
                let count = VarUint32::decode(&mut body)?.into();
                let value_type = ValueType::from_u8(read_next(&mut body)?)
                    .ok_or(DecodeError::InvalidValueTypeError)?;
                locals.push(LocalEntry { count, value_type });
            }
            let mut code: Vec<u8> = vec![];
            body.read_to_end(&mut code)?;
            code.pop();
            bodies.push(FunctionBody {
                locals,
                decoded: decode_function_body(&code)?,
            })
        }
        Ok(CodeSection { count, bodies })
    }
}

今回の例で取り扱う命令はi32.constのみだが、他にどれくらいあるかと言うとMVPで以下くらい、これからBulkMemoryとかSIMDとかの命令に対応していくことになると思う

github.com

実行

ここまでで外部からhelloが呼ばれたときに0x41 0x2A 0x0B(i32.const 42)を実行すれば、なんとかなりそうなのがわかった。

かなり簡素化して書くと以下のようなイメージ。

    // (1) 名前を指定して関数を呼び出す
    pub fn invoke(&self, name: &str) -> Result<Vec<RuntimeValue>, YawError> {
        // (2) 名前から関数indexを解決する
        let index = self.exports.resolve(name)?;
        // (3)  indexからバイトコードを引いてくる
        let func = self.functions.get_ref(index as usize)?;
        let mut stack = vec![];
        // (4) バイトコードを読んで命令を判別
        let opcode = get_op(&func.code);
        let arg = get_arg(&func.code);
        match opcode {
            // (5) 実行
           Opcode::I32const => {
             stack.push(arg);
           }
           _ => { ... }
        }
        Ok(stack)
    }

wasmの実行はスタックマシンとして定義されているので、値用のスタック(この例ではstackという変数)を用意し、そこに値を出し入れするようにしている。i32.constはもらった値をスタックに積むだけの命令なのでstack.push(arg)して終了。stackに残った値(この場合42)が返り値となる。

かなり端折ったけど、ミニマムなものはだいたい、これくらいでできると思う。あとは命令やセクションを拡充しながらテストを通していくことになると思う。

テスト

wasmにはtestsuiteが用意されているのでそれを使用するのがよい。

github.com

ここでは以下のようなテストが定義されており、これを実行していくことでテストができる。

(assert_return (invoke "add" (i32.const 1) (i32.const 1)) (i32.const 2))

assert_returnなどはテスト用のテキスト表現でwasm自体のこの、命令が備わっているわけではない。のでテストを実行するのはこのテキストフォーマットもparseして実行してやる必要がある。

そのあたりを自分で実装するのはさすがに嫌だったので今回はwabtのRustバインディングを使った。これを使うと以下のようにテストが書ける。

github.com

    let s = String::from_utf8(buf).unwrap();
    let mut parser = ScriptParser::from_str(&s).unwrap();
    while let Some(Command { kind, .. }) = parser.next().unwrap() {
        match kind {
            CommandKind::AssertReturn { action, expected } => {
                if let Action::Invoke {
                    field,
                    args,
                    module,
                    ..
                } = action
                {
                    ... omitted ...
                    let ret = ins.invoke(&field.to_string(), &args)?;
                    match ret[ret.len() - 1] {
                        RuntimeValue::I32(v) => assert_eq!(expected, vec![Value::I32(v)]),
                        _ => { ... omitted ...}
                    }
                }
            }
            _ => {} 
        }
    }

テストが実行できるようになったらあとはテストが落ちたところを直していけばよい。ただ、このテストを走らすこと自体結構たいへんだったので、もしこの記事を見て試してみる人がいたら序盤からテストの実行について考慮することをおすすめしたい。

ゲームボーイエミュレータ

テストが通るようになり、Goで書いたゲームボーイエミュレータを動かそうと試みた。方針としてはGo側には手を加えずブラウザで動くwasmファイルをそのまま動かそう、という方針。

これは今からGo側を変更するのが面倒だったし、手を加えたことで、問題が発生した場合の切り分けをしたくなかったからなんだけど、これはこれであまりいい方針ではなかったような気がしてる。。。

wasmを吐く場合、たとえばGoから以下のようにブラウザのwindowに対して値をセットできる。

js.Global().Get("window").Set("hello", "world")

これを実行するとwindowに値がセットされていることが確認できる。

console.log(window.hello) // world

wasm-JS間は数値でしかやり取りできないのにこのようなことができるのか調べる必要があった。これはグルーコードとして提供されているwasm_exec.jsを見るとだいたい分かる。

github.com

JS側では以下のように値を保持しておき、配列のindexをリニアメモリ経由で指定することで値のやりとりをしているよう。

this._values = [
        NaN,
        0,
        null,
        true,
        false,
        global,
        this
];

js.Global().Get("window").Set("hello", "world")を例にとると、まずsyscall/js.stringValを呼んで"world"this._valuesに登録する。

簡素化すると以下のようになっていて、"world"this._valuesに登録したあとthis._valuesの最後尾のindexをメモリに書き戻しているためGo側で"world"this._values格納されたindexを知ることができる。

go: {
   "syscall/js.stringVal": sp => {
       storeValue(sp + 24, loadString(sp + 8)); //  "world"
    },
}

const storeValue = (addr, v) => {
    this._values.push(v);
    // ... ommitted ...
    mem().setUint32(addr, this._values.length - 1, true);
};

次に、リニアメモリに"hello"を書き込みつつ、先に得られた"world"格納先のindexとwindowが格納されたindexをリニアメモリに書き込みyscall/js.valueSetを呼び出す。

そうするとRefrect.setによりwindow.hello"world"が代入されるという仕組みだ。

"syscall/js.valueSet": sp => {
    Reflect.set(
        loadValue(sp + 8), // window
        loadString(sp + 16), // "hello"
        loadValue(sp + 32) // "world"
    );
}

これは一番簡単な例だが、関数呼び出しなどもこの応用でできている。

あとは、Rustでなんとかwasm_exec.jsに擬態することにした。 うすうす分かってはいたがwasm_exec.jsReflectを多用しており、Rustとの相性はよくない。あまりいい方針ではなかったと前述したのはこれが理由。

かなりアドホックでひどい作りな自覚があるのだけれども、なんとか擬態することはでき、syscall/js.copyBytesToJS経由でVRAMの内容を受け取りSDL2で描画することに成功した。たとえば"syscall/js.valueSet"は以下のようになった。(ひどい。)

 "syscall/js.valueSet" => {
        let sp: u32 = args[0].into();
        let _value = self.load_value(sp + 8, &self.values.borrow())?;
        let name: &str = &self.load_string(sp + 16).unwrap();
        let value = &self.load_value(sp + 32, &self.values.borrow())?;
        match name {
          "GB" => {
            if let BridgeValue::WrappedFunc(f) = value.clone() {
              *self.gb.borrow_mut() = Some(f);
            }
          }
          "result" => {}
          "next" => {
            if let BridgeValue::WrappedFunc(f) = value.clone() {
              *self.next.borrow_mut() = Some(f);
            }
          }
          _ => {}
        }
        Ok(vec![])
      }

全体が気になる方はこちら

github.com

他のランタイムはどうしているのかと見てみたら、wasmerは専用のGoライブラリを用意しているようだった。正しい。。。。

github.com

パフォーマンスはまだひどいけど、ひとまず目標の一つであるゲームボーイエミュレータの起動は達成できた。

これから

まずはWASIに対応したい。WASIに対応すればpythonが動かせるはずなのでこれはこれで面白い。

合わせてパフォーマンスの改善。インタプリタではかなり速いと言われるwasm3の実装を見ていいところを取り込みたい。

github.com

また、[no_std]に対応してベアメタル、強いて言うならARM7で動かしたい。JITAOTの機構の検討もしたいが、ベアメタルでの動作を考慮にいれるとこのリポジトリでは採用することはなさそう。

今回実装した機能はMVPで、あとにはGCThreadなども控えているので勉強の題材としてはよさそう。以上。

AWS CDKで Rust + AppSyncの構成をつくるメモ

構成としては認証をCognito UserPoolで行い、AppSyncからLambdaを呼び出してJSONを返す構成とする。

UserPool

UserPoolを用意する。this.node.tryGetContextでコンテキストが渡せるのでここに環境名、例えばprodなどを与えてSuffixとするようにした。

import * as path from "path";

import * as cdk from "@aws-cdk/core";
import * as cognito from "@aws-cdk/aws-cognito";

export class MyStack extends cdk.Stack {
  constructor(scope: cdk.Construct, id: string, props?: cdk.StackProps) {
    super(scope, id, props);
    const env = this.node.tryGetContext("env");
    const userPool = new cognito.UserPool(this, "MyUserPool" + env, {
      userPoolName: "MyUserPool-" + env
    });
    }
}

cognito.UserPoolHigh-level constructsというものっぽくて細かい設定が隠蔽されてて触れない気がする。

正しいかわからないけど

const userPoolCfn = userPool.node.defaultChild as cognito.CfnUserPool;

とすると細かい設定ができるように見える

github.com

Lambda

Lambdaとロールを作る。ひとまずCloudWatchLogsのみアクセス可能とする。必要に応じてDynamoやRDS、S3への権限をつける。

Rustの場合はruntimeはlambda.Runtime.PROVIDEDとする。PROVIDEDの場合handlerの設定は無視されるっぽい。

lambda.Code.fromAssetにバイナリのパスを設定しておくとcdk deployでバイナリをS3にあげてセットしてくれる。

import * as path from "path";

import * as cdk from "@aws-cdk/core";
import * as appsync from "@aws-cdk/aws-appsync";
import * as cognito from "@aws-cdk/aws-cognito";
import * as lambda from "@aws-cdk/aws-lambda";
import * as iam from "@aws-cdk/aws-iam";

import { definition } from "./schema";

export class MyStack extends cdk.Stack {
  constructor(scope: cdk.Construct, id: string, props?: cdk.StackProps) {
  
     ...省略...

    const lambdaRole = new iam.Role(this, "MyLambdaRole", {
      assumedBy: new iam.ServicePrincipal("lambda.amazonaws.com"),
      path: "/service-role/",
      inlinePolicies: {
        CloudWatchWritePolicy: new iam.PolicyDocument({
          statements: [
            new iam.PolicyStatement({
              actions: [
                "logs:CreateLogGroup",
                "logs:CreateLogStream",
                "logs:PutLogEvents"
              ],
              resources: ["*"]
            })
          ]
        })
      }
    });

    const MyLambda = new lambda.Function(this, "MyLambda", {
      functionName: `my-function-${env}`,
      runtime: lambda.Runtime.PROVIDED,
      handler: "index.handler",
      code: lambda.Code.fromAsset(
        path.join(
          __dirname,
          "../../target/x86_64-unknown-linux-musl/release"
        )
      ),
      role: lambdaRole
    });
  }
}

AppSync

AppSync作成時にauthenticationType: "AMAZON_COGNITO_USER_POOLS"にしてUserPoolIdを渡す。

new appsync.CfnGraphQLSchemaにSchemaを渡す。 schemaは別ファイルに以下のように書いといてこれを読ます。

export const definition = `
  type Hello {
    world: String!
  }

  type Query {
    getHello: Hello!
  }

  type Schema {
    query: Query
  }
`;

あとはDataSourceとResolverを追加する。 DataSource用のRoleにはLambda呼び出し権限を忘れないように。

import * as path from "path";

import * as cdk from "@aws-cdk/core";
import * as appsync from "@aws-cdk/aws-appsync";
import * as cognito from "@aws-cdk/aws-cognito";
import * as lambda from "@aws-cdk/aws-lambda";
import * as iam from "@aws-cdk/aws-iam";

import { definition } from "./schema";

export class MyStack extends cdk.Stack {
  constructor(scope: cdk.Construct, id: string, props?: cdk.StackProps) {

    ...省略...

    const gql = new appsync.CfnGraphQLApi(this, "AppSyncAPI", {
      name: `MyGQL-${env}`,
      authenticationType: "AMAZON_COGNITO_USER_POOLS",
      userPoolConfig: {
        awsRegion: "ap-northeast-1",
        defaultAction: "ALLOW",
        userPoolId: userPool.userPoolId
      }
    });

    const schema = new appsync.CfnGraphQLSchema(this, "GqlSchema", {
      apiId: gql.attrApiId,
      definition
    });

    const dataSourceIamRole = new iam.Role(this, "dataSourceIamRole", {
      assumedBy: new iam.ServicePrincipal("appsync.amazonaws.com"),
      inlinePolicies: {
        InvokeLambdaFunction: new iam.PolicyDocument({
          statements: [
            new iam.PolicyStatement({
              effect: iam.Effect.ALLOW,
              actions: ["lambda:invokeFunction"],
              resources: ["*"]
            })
          ]
        })
      }
    });

    const dataSource = new appsync.CfnDataSource(this, "DataSource", {
      apiId: gql.attrApiId,
      name: "LambdaDataSource",
      serviceRoleArn: dataSourceIamRole.roleArn,
      type: "AWS_LAMBDA",
      lambdaConfig: {
        lambdaFunctionArn: MyLambda.functionArn
      }
    });

    const addItemResolver = new appsync.CfnResolver(this, "HelloResolver", {
      apiId: gql.attrApiId,
      typeName: "Query",
      fieldName: "getHello",
      dataSourceName: dataSource.name,
      requestMappingTemplate: `{
        "version": "2018-05-29",
        "operation": "Invoke",
        "payload": {
          "now": $util.toJson($util.time.nowISO8601()),
        }
      }`,
      responseMappingTemplate: `$util.toJson($ctx.result)`
    });
    addItemResolver.addDependsOn(schema);
  }
}

Rust

main.rsを以下のように用意。 基本的にはここに書いてある通り。

aws.amazon.com

実行バイナリの名前をbootstrapにするのを忘れないこと。

#[macro_use]
extern crate lambda_runtime as lambda;
#[macro_use]
extern crate serde_derive;
#[macro_use]
extern crate log;

use lambda::error::HandlerError;
use std::error::Error;

#[derive(Deserialize, Clone)]
struct CustomEvent {}
#[derive(Serialize, Clone)]
struct CustomOutput {
    world: String,
}
fn main() -> Result<(), Box<dyn Error>> {
    simple_logger::init_with_level(log::Level::Info)?;
    lambda!(my_handler);
    Ok(())
}
fn my_handler(e: CustomEvent, c: lambda::Context) -> Result<CustomOutput, HandlerError> {
    Ok(CustomOutput {
        world: format!("Dekita!"),
    })
}

あとはビルド。今回はmuslで。

cargo build --release --target x86_64-unknown-linux-musl

あとはCDKでデプロイすればよい。

cdk deploy -c env="dev"

ローカルでLambdaを実行

ローカルで動かすにはSAMを使えばいいっぽい。 以下のようなtemplate.yamlを用意し

AWSTemplateFormatVersion: "2010-09-09"
Transform: AWS::Serverless-2016-10-31
Resources:
  TestRustFunc:
    Type: "AWS::Serverless::Function"
    Properties:
      Handler: sam_local_test
      Runtime: provided
      CodeUri: ./rust.zip

zipしてから

zip -j rust.zip ./target/x86_64-unknown-linux-musl/release/bootstrap

以下で一応動作は確認できた

sam local invoke "TestRustFunc" -e event.json
2020-01-29 19:34:57 Mounting /tmp/tmp6efof_c2 as /var/task:ro,delegated inside runtime container
START RequestId: 136f6ca2-6a4f-121d-5ece-30d4999340b1 Version: $LATEST
2020-01-29 10:34:58,203 INFO  [lambda_runtime::runtime] Received new event with AWS request id: 136f6ca2-6a4f-121d-5ece-30d4999340b1
2020-01-29 10:34:58,205 INFO  [lambda_runtime::runtime] Response for 136f6ca2-6a4f-121d-5ece-30d4999340b1 accepted by Runtime API
END RequestId: 136f6ca2-6a4f-121d-5ece-30d4999340b1
REPORT RequestId: 136f6ca2-6a4f-121d-5ece-30d4999340b1  Init Duration: 277.65 ms        Duration: 3.08 ms       Billed Duration: 100 ms Memory Size: 128 MB     Max Memory Used: 9 MB

{"world":"Dekita!"}

今やってるお仕事、これに置き換えたい...

Go Conference 2019 Autumn「GoでつくるGameBoyエミュレータ」を発表してきた

表題の通りGo Conference 2019 Autumnで発表させていただきました。運営・スタッフの方々、スピーカーの方々、スポンサーの方々、発表を聞きに来てくださった方々、懇親会でお話させていただいた方々ありがとうございました。非常に楽しかったです。

今回は発表資料の補足や、質問いただいた内容の回答、補足などを記事としてまとめておこうと思い記事にしてみることにしました。

発表資料

発表資料は以下です。

speakerdeck.com

補足

発表がかなり駆け足になってしまったのと、資料だけではよくわからない箇所があると思うので補足を以下にあげていきます。

DEMO

このページから遊ぶことができると思います。

bokuweb.github.io

さぼってページに載せていないんですがキーマップは以下です。

keyboard game pad
← button
↑ button
↓ button
→ button
Z A button
X B button
Enter Start button
Backspace Select button

スマートフォンの場合は画面上のGameBoyの各ボタンがタッチできるようになっています。 デフォルトでプレイできるのはtobutobugirlという2017年製のオープンソースGameBoyソフトです。

github.com

スペック

f:id:bokuweb:20191106015520p:plain

ブロック図

LR35902に色々詰まっているのが印象的です。なので基板上で目につく大物部品はLR35902RAM2個くらいじゃないでしょうか。ファミコンの場合CPUPPU(ピクチャープロセッシングユニット)が別パッケージになっていたため、CPUからPPUの持つVRAMにアクセスするのがとても面倒でしたが、その点が解消されており、物理的にもソフト的にもシンプルになっています。

f:id:bokuweb:20191106015541p:plain

その辺は以下の記事でも触れているので参照してみてください。

blog.bokuweb.me

レジスタ

Fはフラグを管理する特殊なレジスタです。 また基本8bitレジスタですがBCをくっつけてBCの16bitレジスタとして扱うことが可能です。

f:id:bokuweb:20191106015612p:plain

f:id:bokuweb:20191106015621p:plain

CPUの基本動作

乱暴な言い方をするとCPUはずっとこのステップを繰り返しているだけです。実際には割り込みの処理などがありますが、割り込み処理も各ステップ実行時に割り込みフラグをチェックして割り込みがかかっていたら指定番地へジャンプするただけなので、難しい処理ではありません。

f:id:bokuweb:20191106015645p:plain

f:id:bokuweb:20191106015712p:plain

フェッチ

CPUは次に実行すべき命令が何かを知る必要があります。なので次に実行すべき命令の番地を記録しておくプログラムカウンタ(以下PC)の指し先からリードを行います。これはカートリッジ内のROMかもしれませんし、どこかのRAMかもしれません。

f:id:bokuweb:20191106015730p:plain

リードを行った後はPCをインクリメントし、次の命令orデータを指すようにします。

この例はPC0x1000番地を指しており、LD B, 0xA5というBレジスタに即値0xA5を格納する命令が入っている様子です。この命令のコードは0x06なのでPCの指し先には0x06がその次の番地にはデータとして0xA5が格納されています。

f:id:bokuweb:20191106023444p:plain

デコード

CPUは読んできたコードが何か調べる必要があります。今回の例で言うと0x06が何者かを調べる必要があります。自分は命令コードを渡すと命令の情報が引き出せる配列を用意しました。

f:id:bokuweb:20191106015819p:plain

f:id:bokuweb:20191106015837p:plain

今回は情報として、オペランドのサイズ、実行サイクル数、命令実行関数を引き出せるようにしています。 オペランドのサイズはこのCPUの場合0~2です。オペランドのサイズに応じてフェッチするようにしています。

f:id:bokuweb:20191106102540p:plain

発表時点でforでいいところ、なぜかswitchで書かれており、@Linda_ppが指摘してくれました。ありがとうございました。

実行

あとは実行するだけです。この例はレジスタB0xA5に格納するだけなので一行で済んでしまいます。「なんだ簡単じゃないか」と思われた方もいるかと思いますが、まさにそのとおりでこのCPUは乗算・除算命令もなくデータの移動、加算、減算、ジャンプなどの単純な命令をちまちま実装していくだけで完成します。

f:id:bokuweb:20191106015939p:plain

ただ、数が多いのでその点はちょっと大変です。このCPUでいうと命令数は500弱くらいでしょうか。最初の数命令は動き始めると楽しいんですが、加算や減算をひたすら追加していくルーチンワークになると非常にだるくなります。

CPUを実行した際の返り値としてCPUの実行サイクル数を返しています。この値を元にGPUをどれだけ稼働させるかを決定するので、この値はCPU-GPU間の同期をとるための重要な値となります。

f:id:bokuweb:20191106020003p:plain

メモリマップ

色がついている箇所がカセット内のメモリ領域ですね。swichableと書いてあるのは、この領域はバンク方式をとっているので、ある特定の処理を行うことでその領域がごそっと切り替わることになります。ある特定の処理というのはROM領域バンク番号を書き込むなどの気持ち悪い処理なんですが、よく取られていた方法のようです。

f:id:bokuweb:20191106020046p:plain

省略されていますが上位のほうには割り込みLCDタイマーなどのペリフェラルに関する領域が取られています。

あと個人的に自分が気をつけていることですが、メモリマップの情報はCPUが知ることがないように気をつけています。CPU自身はデバイスの詳細を知る必要がないはずで、CPU自身がメモリマップの情報を知ってしまうとCPUのてスタビリティが下がるので別のモジュールに切り出してCPUにインジェクトできるような構成を取っています。

自分は単体テストは以下のように書いてみました。

func setupCPU(offset types.Word, data []byte) (*CPU, *mocks.MockBus) {
    b := mocks.MockBus{}
    b.SetMemory(offset, data)
    irq := interrupt.NewInterrupt()
    l := logger.NewLogger(logger.LogLevel("Debug"))
    return NewCPU(l, &b, irq), &b
}

func TestLDn_nn(t *testing.T) {
    assert := assert.New(t)
    cpu, _ := setupCPU(0, []byte{0x01, 0xDE, 0xAD})
    cpu.PC = 0x00
    cpu.Step()
    assert.Equal(byte(0xAD))
    assert.Equal(byte(0xDE))
}

この部分をコードに落とすには基本的にはアドレスの範囲に応じてアクセス先のデバイスを変更する単純な処理になります。たとえばリードであれば以下のような感じです。

f:id:bokuweb:20191106022515p:plain

GPUの描画タイミング

画面の右端まで描画を行ったら次ライン描画までのブランク期間HBlankという期間があります。この期間を含めると1ラインあたり456クロックとなります。

f:id:bokuweb:20191106020247p:plain

また、表示領域を描画し終わってから次の描画を始めるまでのブランク期間VBlankという期間が10ライン分あります。

f:id:bokuweb:20191106020303p:plain

これらを考慮すると1フレームあたり70,224クロックで完了する計算になります。 この数字は重要な数字でCPUと同期をとるために必要となります。

GPUの基本動作

GPUは稼働するクロック数を入力し、それらをカウントアップ。クロックが1ライン分の456クロック積算されるごとに描画処理を行うような作りとしました。

f:id:bokuweb:20191106020323p:plain

具体的には以下のタイミングで各処理を行うようにしました。

  • 表示領域内
  • 表示領域描画完了
  • VBlank完了
表示領域内

表示領域内、すなわちg.ly < 144の場合。g.lyというのは0xFF44番地に配置されているLCD Y座標レジスタです。CPUはこのレジスタを読むことで現在GPUが液晶の何ライン目を描画しているのかを知ることができます。

表示領域内であれば背景を1ライン分組み立てるようにしています。

f:id:bokuweb:20191106020345p:plain

表示領域描画完了

表示領域描画完了時にはスプライトをまとめて描画しています。スプライトというのは所謂マリオやクリボーなどのキャラクター画像で、背景の上にキャラクターを最大40個配置することが可能です。

f:id:bokuweb:20191106020420p:plain

文章だとわかりにくいですが、以下のGPUデータの可視化デモを見てもらえると分かりやすいかもしれません。

bokuweb.github.io

本来スプライトも各ライン毎に描画していくべきなのですが、エミュレータの場合はさぼって表示領域描画完了のタイミングにまとめて全てのスプライトを描画してしまっています。

「ではなぜ背景も同じようにまとめて描画しないのか」という疑問があると思うのですがライン毎にスクロール量が変更される可能性があるためです。

具体例として、スーパーマリオランドでマリオが画面右側へ進んでいくとどんどん画面がスクロールしていくと思うのですが、スコアやタイマを表示しているヘッダ(と勝手に呼びます)はスクロールせずに固定したままになっています。これはヘッダ部分をスクロール量0で描画した後にスクロール量を変更しているためです。

よって、表示領域描画完了時にまとめて背景を描画するような処理にするとこのような挙動が再現できなくなってしまいます。

また資料では割愛していますが、このタイミングでVBlank期間に入ることを通知するための割り込み処理が必要となります。この割り込みが何故必要かと言うと、描画中にVRAMを変更すると画像が乱れる可能性があるためで、基本的にはVRAMVBkank中に触ることになているためです。

VBlank完了

g.lyを先頭の0に戻したり、VBlank割り込みフラグを解除したりします。

f:id:bokuweb:20191106020545p:plain

背景の描画

8Byteで8x8サイズのスプライトが1枚分作れます。16Byteで8x8サイズのスプライトを2枚作り足し合わせることで、色情報が3bitのタイルが表現できます。

f:id:bokuweb:20191106020631p:plain

タイルデータ

タイルデータを格納する領域は決められており、VRAM内の0x8000~0x97FF番地に格納されることになっています。格納された順にタイル番号がふられます。

f:id:bokuweb:20191106020758p:plain

タイルマップ

背景を作るにはタイルマップと呼ばれる領域、具体的には0x9800~0x9BFFに先のタイル番号を敷き詰めていくことになります。タイルマップ32x32タイルすなわち256X256px分の領域が確保されており、その一部が表示領域として切り取られLCDに表示されます。

f:id:bokuweb:20191106020812p:plain

なぜ余分な領域があるかというと、スムーズなスクロールに対応するためだと思います。当時のスペックだとVRAMへのアクセスはかなり遅い上に、先述したように書き込みできるタイミングは限られてしまいます。

VBlank中に多くの背景を書き換えることは不可能なため、256X256pxの領域から表示分160X144pxを切り取って表示しているものと思われます。

これは以下のツイートのタイルマップを見ると分かりやすいかもしれません。

また、発表では割愛しましたがタイルマップは二面分の領域が確保されており、どちらを選択することはレジスタを編集することで切り替えることが可能です。

スクロール

表示領域を256x256pxの領域から切り出せるということを説明しましたが、どの領域を切り出すかをScrollX(0xFF43番地)ScrollY(0xFF42番地)で設定することができます。 f:id:bokuweb:20191106020845p:plain

図は一番シンプルな例ですが、前述したようにスクロール量は描画の途中でも編集が可能なため、この図でいうところの青枠の切り取り領域はかならずしも1つの四角形になるとは限りません。

背景の描画

背景の描画データの組み立ては泥臭くやるしかなくて基本的には以下の手順です。

  • 現在の描画座標から、タイルの座標を割り出す
  • タイルの座標から該当するタイルマップのアドレスを算出する
  • タイルマップからタイル番号を読み出す
  • タイル番号からタイルデータを引いてくる
  • 画像データを組み立ててバッファに格納

f:id:bokuweb:20191106020919p:plain

エミュレータの基本動作

ここまででCPUGPUの基礎はできているので、これらの同期をとってエミュレータとして動作させる必要があります。

f:id:bokuweb:20191106021002p:plain

基本的なステップは以下です。

  1. CPUを1命令実行する
  2. CPUでの命令実行にかかったクロック分GPUを稼働する
  3. 積算クロック数が1フレーム分に達したら画像データを取得して描画する

です。注意すべきはCPUの動作クロックとGPUの動作クロックに差異がある点です。LR35902には4.19MHzが入力されていますが、CPUの動作クロックはそれを4分周したものになっています。つまりCPUで2クロックかかる命令を実行した場合、GPUは8クロック分稼働させる必要があります。x4しているのはそのためです。

今回は画像データを返すところまでをNextという関数にまとめておきました。後述しますが、ここで描画処理までをここで行ってしまうと、WasmNativeで動作を切り分け必要がでてくるのと、テストするのが面倒になってしまうのでここではバッファを返すようにしています。

f:id:bokuweb:20191106021031p:plain

あとは60FPSすなわち16ms周期でNextを実行して画像データを取得・描画してやればエミュレータとしては完成です。イメージは以下のような感じです。

f:id:bokuweb:20191106021126p:plain

もちろん、これは実機のタイミングとは大きく異なりますが、エミュレータとしては入力が反映された画像データが16ms周期で取得できれば、辻褄は合うので問題ないです。この方式で不具合がでるゲームはそうそう無い気はしています。

あとはこの画像データを描画するだけです。特に面白いとこはないので発表でもスキップ気味に話ましたが、今回はfaiface/pixelというglfwライブラリを使用しました。

github.com

余談ですが、現在では治っているかもしれませんが、glfwを使用した場合macでは一度windowを移動しないと描画されない問題があり以下のような謎Hackが入っています。この問題のせいで数時間溶けました。

pos := win.GetPos()
win.SetPos(pixel.ZV)
win.SetPos(pos)

Testing

単体テストは前述したようにこつこつ書いていけばいいのですが、正直効率はあまりよくありません。CPUの作りが極めて単純なこともあり、加算命令やデータ移動のテストを書いていると辛くなってきます。

大抵どのようなレトロゲームにも先人たちがテストROMを作ってくれているのでこれを使うのがいいでしょう。

github.com

こんな感じで結果を表示してくれます。

f:id:bokuweb:20191106094641p:plain

たとえばCPU命令の実行結果が正しいかを検証するのは上記のcpu_instrsを使用します。このテストは落ちた場所を通知してくれますし、11パターンあるテストケースを個別に実行することもできます。また親切なことにシリアル出力に結果を吐いてくれるのでGPU周りが未実装でもこのROMは使用できます。

ある程度までCPUが動いたらまずはこのテストをパスすることを目標にするといいかもしれません。

このようにテストROMを使用して検証していくのは便利なのですが、CIでどう回すか。という別問題が出てきます。今回は以下のように指定したROMの指定フレームをpngとして保存するようにし、VisualRegressionTest`を行うようにしました。

f:id:bokuweb:20191106021502p:plain

これには以前作成したreg-viz/reg-cliというツールを使っています。最近@wadackel@Quramyがレポート画面を刷新してくれて使いやすくなっていますのでぜひ使ってみてください。

github.com

本当は発表当日にgo版を用意して「どやっ」って言うつもりだったんですが資料作成に時間を吸われ全然間に合いませんでした。このツールはWebフロントエンドの開発などで使用することを念頭において作っているのでgo版を用意しても喜ぶのは僕ぐらいかもしれませんが...。

閑話休題。前回実行時に生成された画像をcommitしておき、見本画像とすることでただしく描画されているかが検証できます。

開発中はトライ&エラー的にごにょごにょいじることがあると思います。その際に以前は動いていた箇所を意図せず壊してしまったりしてしまいますが、この仕組みによりこれは防げます。

たとえば意図せずキャラクターの描画部分をコメントアウトしてしまったとしましょう。

if g.ly == constants.ScreenHeight {
    // g.buildSprites() ウワ-マチガッテコメントアウトシチャッタヨ
} 

そうすると以下のようにテストに失敗するようにしました。

変更部分もレポートを見ることですぐに分かるようになっています。

Wasmの初期化

goWasm化してブラウザで動かす場合には、JSgo間でグルーコードが必要となります。wasm_exec.jsというのがそれで、これは公式に用意されています。なのでまずこいつを読みこみ必要があります。

f:id:bokuweb:20191106021652p:plain

Wasmを読んでinstantiateする必要があります。注意点としてはwasm_exec.js経由で用意されているimportObjectを食わせる必要がある点です。これによりWasm側からwasm_exec.jsで用意されている関数を呼ぶことができます。

f:id:bokuweb:20191106021709p:plain

wasmfetchinstantiateを行ってくれるinstantiateStreamingというAPIがあるんですが、safariが対応していないのでここではfetchinstantiate個別で行っています。

caniuse.com

ブラウザで動作させる

初期化時に渡したimportObject経由でgo側の関数をJSから呼べるようにします。このときgo側でsyscall/jsimportする必要があります。

import syscall/js

f:id:bokuweb:20191106021804p:plain

ここではブラウザ側のglobalにGBというオブジェクトを生やしています。実態はnewGBという関数になっていて、JSからは以下のように使用できます。

const rom = await fetch("./tobu.gb");
const buf = await rom.arrayBuffer();
const gb = new GB(new Uint8Array(buf));

ここではROMfetchしてGBに渡しています。 go側ではもらったROMデータをもとに各種データを初期化し、ゲームを開始するための準備を行います。

また、ゲームの描画はcanvasで行うためGPUで生成されるデータをブラウザに引き渡す必要があります。これは以下のようにnextという関数を生やしてバッファを返すようにしました。

f:id:bokuweb:20191106021833p:plain * js.typedArrayOfは後述しますがgo1.13では使用できません。

これで以下のようにgb.next()を呼ぶことでJS側でバッファが取得できるようになります。

const gb = new GB(new Uint8Array(buf));
const image = gb.next();

あとはJS側で16ms周期でgb.next()を呼び、返ってくるデータをcanvasに書き込めばブラウザでゲームが動作します。具体的には以下のような感じです。ディスプレイのリフレッシュレートでコールバックを発火してくれるrequestAnimationFrameを使用しています。(ここはサボっていてディスプレイのリフレッシュレートが30Hzだったり120Hzだと良くないことがおこります)

f:id:bokuweb:20191106021909p:plain

ビルド

ビルドは-tags=wasmとすることでnativeと切り分けています。 f:id:bokuweb:20191106021926p:plain

サイズ

サイズは予想通りかなり大きく、さらにはグルーコードもついてきます。 f:id:bokuweb:20191106021944p:plain

パフォーマンス

f:id:bokuweb:20191106021958p:plain

パフォーマンスは発表後に再測定しています。 Rustで書いたファミコンのエミュレータをwasmにした際には1フレーム当たり3ms程度だったので6~7msくらいは出てほしいと思っていましたが、届きませんでした。もちろんファミコンとは1フレームあたりの命令実行数は異なるはずなので参考値でしかありませんが。

もちろん、まだまだ最適化の余地はあるとは思いますが、それでも現状の書き方で6~7msくらいは出てほしいなーというのが率直な感想です。

FrameGraphをざっと見た感じ、分かりやすいボトルネックはなく、全体的に遅いという印象でした。試しにいくつかの関数がどのようにwasmに変換されるのかを見てみましたが、やはりruntimeの分コードが膨らみじわじわ効いて来ているような印象です。

たとえば以下のようなコードでもwasmに変換した際に大きく膨らんでしまうのである程度の速度低下はさけられないと思います。ただ、wasmにはGCをサポートするプロポーザルも出ているので、これにより改善するかもしれませんし、現時点であればtinyGoを試してみるのもいいかもしれません。

f:id:bokuweb:20191106022027p:plain

↑のコードをwasmにすると↓のようなコードになりました。

f:id:bokuweb:20191106022044p:plain

質疑応答

質問いただいた内容と回答を記載しておきます。 漏れや意図が汲み取れていないところがありましたらご指摘ください。

実装時に参考すべき資料はあるか

基本的にはこのpdfを見ればなんとかなると思います。

http://marc.rawer.de/Gameboy/Docs/GBCPUman.pdf

Go1.13は試したか

発表は1.12を前提に発表しました。すんなり動かなかったのと、資料作成が間に合ってなかったので後回しにしていましたが、発表後検証し、速度の比較を行ってみました。

browser go1.12.11 go1.13.4
Chrome77 10.43ms 9.61ms
Firefox69 10.38ms 10.48ms
Safari 11.27ms 8.80ms

1フレームにおける平均処理時間なので小さいほうが良いです。Firefoxではあまり変化がありませんが、Chrome, Safariでは良くなっていると言って良さそうです。

go1.12.11 go1.13.4
サイズ(MB) 3.4MB 2.8MB

サイズもかなり小さくなっていました。

注意点としてはgo1.13では資料内で紹介したjs.typedArrayOfが削除され、js.CopyBytesToJSを使用するよう変更されていました。

js.typedArrayOfはバッファを返して来ましたが、js.CopyBytesToJSは引数で渡したバッファにセットするIFになっています。

なのでnextは以下のように変更しました。

this.Set("next", js.FuncOf(func(this js.Value, args []js.Value) interface{} {
    img := emu.Next()
    return js.CopyBytesToJS(args[0], img)
}))

ただ、ここでも問題があって、js.CopyBytesToJSは第一引数がUint8Arrayinstanceかチェックしているんですが、canvasImageDataUint8ClampedArrayなので直接セットできず、今回はwasm_exec.jsをちょっと修正し、本体側にもパッチを投げてみました。

既存のツールを使用してwasmのサイズは小さくできるか

発表時は「そもそもruntimeがでかいわけだし、劇的には削れないだろう」と思い試しておらず、発表後にwasm-stripwasm-optをかけてみましたが、サイズはほぼかわりませんでした。

global変数を使ったり、ヒープを使用しないような記述をすることで速くなるか

速度は改善する方向に向かいそうですが、どんなwasmが吐かれるかみてみないとなんとも言えなそうですし、まだ試せていないです。 同Conference@DQNEOさんの以下の発表を聞いて(とても楽しみにしてたし、楽しかった)自分もやりたくなったので、速度やサイズを改善したwasm用goコンパイラ`作れないかなーなど考えるなどしていた。

speakerdeck.com

60FPSは出せるか

ネイティブであれば全く問題なく出るのと、wasmでもJS側でもgo側でも工夫できそうなところはまだまだあるので、新しめのデスクトップPCであれば比較的安定して出せそうだと思います。ただ、スマートフォンだとちょっと苦しそうな気もします。

ファミコンより作りやすいと言ったが具体的にどのようなところか

一例ですが、ゲームボーイは256x256pxのから160x144pxを切り出して表示しますが、ファミコンの場合は以下のように表示領域4面分のメモリ領域から1画面分を切り出すんですが、境界面がメモリ的にはまったく連続しておらずバグりやすいという話をしました。

また、冒頭で話たようにゲームボーイはGPUCPUが同じパッケージにいるのでCPUから直接VRAMがアクセスできる。という点もハードウェア・ソフトウェアの両面をシンプルにしており、わかりやすくなっている点だと思います。

スプライトと背景の違い

発表では時間の都合上スプライトについては省略しました。軽くここで言及しておきます。 スプライトは背景の上に以下のようにキャラクターなどを描画する機能で最大40個配置することができます。

f:id:bokuweb:20191106100020p:plain

背景の場合はタイルマップと言われる領域に8x8のタイルを32x32タイル分敷き詰めるという話をしました。 なので(x , y) = (0, 0 )に2番タイル(x , y) = (0, 8)に8番タイル... (x , y) = (8, 8)に1番タイル、のように8の倍数の座標にタイルを埋めていくことになります。

スプライトの場合は背景の上を縦横無尽に動ける必要があるため(x, y) = (17, 23) のような座標にも配置できなければなりません。スプライトは以下のような4バイトのデータで表現されます。

Byte 詳細 
0 Y座標 - 16
1 X座標 - 8
2 タイル番号
3 オプション   

オプションの詳細は割愛しますが、水平、垂直反転したり、背景との表示優先順位を設定できたりします。 このデータをOAM RAMというRAMに格納するとGPUが画面にスプライトを展開します。

以上まとめになります。ありがとうございました。

ゲームボーイエミュレータをGo言語で書いた

概要

Goはこれまで量を書いたことがなかったので入門にゲームボーイエミュレータを書いてみることにした。ゲームボーイである理由はたまたまよくできたゲームボーイの資料(http://marc.rawer.de/Gameboy/Docs/GBCPUman.pdf)を見つけてしまったため。

成果物

github.com

まだ基本的なカートリッジタイプしか実装できていないがそこそこ動き始めたので公開することにした。直近は対応カートリッジを増やしながらWebAssemblyを吐けるようにしたい。

ゲームボーイの基本仕様

項目 概要
CPU LR35902 4.19MHz 8bit
RAM 8kB
VRAM 8KB
ROM 256k~32MBit
Display 4階調モノクロ、160×144ドット
スプライト 8×8 最大40個表示 / 1ライン上に 最大10個表示
背景 256×256ドット
ウィンドウ機能 後述
サウンド 矩形波2ch+波形メモリ音源1ch+ノイズ1ch
通信ポート シリアル通信ポート搭載
割込み機能 パッド入力割込み、シリアル通信割込み、タイマー割込み、LCDC割込み、Vblank割込み

CPUはシャープ製のLR35902でこの中には画像処理や音声の機能も含まれている。コアはカスタムZ80と聞くことが多いが、Intel8080Z80のハイブリッドとも聞いたことがあって、もうちょっと詳しく知りたいと思い調べていたら以下の記事に辿り着いた。

www.wizforest.com

推測も含んでいるようなので実際のところはわからないが技術面では 8080 カスタムと呼ぶべきで、政治面では Z80 カスタムと呼ぶべきらしく面白かった。

前述したように画像処理(ファミコンで言うところのPPU)はLR35902に含まれているため部品点数がとても少ない。大きな部品はメモリ2つとLCDだけだ。あのスペースに押し込めるのに苦労したんだろうなと思う。

ファミコンとの違い

こんなツイートしたところ反応があったので書いてみることにする。ただ、ファミコン開発時の技術面やコスト面での限界もあっただろうし改善というとすこし大げさな気もするので気になった違いを挙げてみたいと思う。いざまとめてみるとそんなに量も無い気がするけど。

タイマーペリフェラルがある

逆にファミコンに無いということに驚くかもしれませんがファミコンにはタイマーがなかった。ので1秒待つような処理が必要になった場合、各命令がどのくらい時間を食うのか計算してwhile文などで待つ必要あったと思う。辛い。 *1

*1 Vblank割り込みをカウントアップすれば簡易タイマーになるのでは。というコメントをいただきました。

ゲームボーイには簡素なものながらタイマーがついており周波数は4種類から選べるし、もちろん割り込みもついている。

タイマーは指定周期経過するごとにカウンタをインクリメントしていき1byteのレジスタがオーバーフローする際に割り込みがかかるようになっている。なのでこのカウンタを読むことでどのくらい時間が経過したか測定することができる。

この機能を使うことによりゲームボーイではエミュレータのCPUの実行タイミングが正しいか計測できる。そのためファミコンではなかったタイミングが正しいかどうかテストするROMがたくさんあった。(タイミングまで正確にエミュレートするのは難しくてこの手のテストROMは全然PASSできていない)

エミュレータとしては多少タイミングがずれていても動くのでどこまで頑張るかは実装者のやる気次第。

シリアル通信ができる

これもタイマー同様ファミコンに無いということに驚くが、ゲームボーイではシリアル通信ができる。とても原始的な作りになっていて制御すべきレジスタは2個だけ。0xFF01に送信データを書いたあと0xFF02に書くと送信されるっぽい。ぽい、というのはあまり真面目に実装していなくて0xFF01を標準出力に接続するだけでエミュレータとしては十分だからだ。

テストROMによってはテスト結果をシリアルに吐いてくれるので描画の実装がまだできていなくてもCPUの命令テストなどが行える。これはエミュレータを作る側としては非常に助かる。ただ自分は最後の最後までシリアルに出力される文字が化けていてこの恩恵に預かれなかったが。。。

ここまで書いて気づいたんだが、このシリアルポートはゲームボーイ同士の通信に使われているポートらしい。ゲームボーイで通信ケーブルを使った覚えがないのですっかり頭から抜け落ちていた。

なぜかテトリスは0x55をDr.マリオは0x60を連続して出力してくるのでバグっているのかと思っていたんだけど、多分通信相手を探してるんだそうな。

ここのプロトコルがわからないが解析してWebSocketにでもつなげばネット対戦ができるかもしれない。

Hblank割り込みや指定ラインでの割り込みがある

Hblankとはあるラインを描画してから次のラインの描画が開始するまでのブランク期間で、ゲームボーイはHblankでの割り込みや指定したラインが描画された際(正確にはラインバッファに展開された際かもしれない)に割り込みをかけることができる。

このタイミングを知ることで様々なことが可能になるが、代表的なものはやはりラスタスクロールじゃないかと思う。ラスタスクロールは画面描画の途中でスクロール量を調整することで部分的なスクロールなど様々な表現が可能となる。

たとえばこのようにスコアやタイムの表記だけ固定してゲーム部分のみスクロールさせることができる。

実際にこのカートリッジがどうやってるかまでは見てないが恐らく指定ラインで割り込みをかけてスクロール値を変更するなどすれば実現できると思う。

じゃあそれらのタイミングを取れないファミコンはどのようにラスタスクロールを実現しているかというと0爆弾という謎仕様がある。これはスプライト用RAMの先頭に格納されたスプライトがラインバッファ上に展開された際にある特定のレジスタにフラグが立つというものだ。

たとえばこれ。これは失敗例で意図しないとこまでスクロールしてるんだけど、そのおかげ(?)で0爆弾であるスプライトを目視することができる。本来コインが表示される位置にあるコインの影のような黒いスプライトだ。バグによりコインが流れていってしまってわかりにくいが。

このスプライト描画完了を検出してからスクロールを開始することによりスコアやタイムは画面上部に固定したままゲーム部分をスクロールすることができている。

このあたりのスクロールに関しては以下の記事も面白い。

gridbugs.org

ゼルダの伝説ではヘッダを固定したまま縦スクロールがありそれをどのように実装しているかという話。

0爆弾というトリッキーな仕様をシンプルな割り込みで解決できるようになったのは改善といっても良さそうだ。

ウィンドウという機能がある

これは最初説明を見てもなんのことかわからなかったが以下の記事を読んで氷解した。

wentwayup.tamaliver.jp

簡単に言うと背景の上にもう一枚背景をかぶせるようなことができる機能だ。ただ、透過処理ができるわけではないので8x8ピクセルの単位で完全上書きになってしまう。

使用例としては以下のようなものが挙げられる。

下から上がってくるGAME OVER の帯はまさにウィンドウ機能が使用されている。大した機能ではないように見えるが、ファミコンではこの挙動を実現できない*2んじゃないかと思っている。ファミコンではスプライトを並べて表現するか、背景を書き換えるかどちらかの手法になるが、スプライトは横方向最大8個しか並べられないし、背景をこのような速度で書き換えることはできないからだ。

*2 id:u_mid さんの指摘で GAME OVERの帯も不可能でない との指摘をいただきました。確かにタイミングの制御はかなりシビアだけどhblankのタイミングをうまく捉えてscrollを駆使したら行けるのかなーという気がしてきました。ただ少なからずグリッチが出るんじゃないかな...

で、話は戻ってゼルダの伝説のヘッダ固定上下スクロールもひょっとしてこのウィンドウ機能があればシュッと解決できるんじゃないかと思ったりしてる。なので地味だけど画期的な機能だと思う。

画像処理機能がCPUと同じパッケージに入ってる

これは半導体の集積度の向上やゲームボーイの筐体のサイズの都合上自然とこうなるべきという感じではあるが、ゲームボーイでは画像処理機能がCPUと同じパッケージに入ってる。

エミュレータ作成者から見て、何が嬉しいかと言うとCPUからVRAMに直接アクセスできることだろう。 ファミコンではVRAMPPU(画像処理IC)に接続されていたためCPUからは直接アクセスすることができない。(VRAMに画像を配置するのはCPUの仕事であるにも関わらず。)

どうするかと言うとPPU内のアドレスレジスタにアクセスするVRAMのアドレスを書いてからデータレジスタにアクセスすることでようやくVRAMを読んだり書いたりできる。

ここで重要な点はPPU内のデータレジスタは初回ゴミデータが読めるので読み捨てる必要がある点だ。これはファミコン開発サイトNESDEVにもハマりポイントして紹介されており幾多のエミュレータ作者を陥れた仕様だろう。これをちゃんと実装しないと漏れなくスーパーマリオブラザーズの空が黒くなる。

これはCPU側のバスとPPU側のバスが非同期だからで、非同期のバス間でやりとりするにはFIFOをつけたりDual port RAMを使ったりすることが多いと思う。が、当時Dual port RAMなんてものは無かったかもしれないし仕様面、コスト面からも使う必然性もないのでFIFOが入ったんだろう。なので初回はゴミデータになる。

ファミコンにはこんな事情があったのでやはり、VRAMへのアクセスがシンプルになるのは嬉しい。

実装過程

完全な理解

エミュレータ実装の第一歩はHello Worldまたはそれに相当するROMを探しコードを読むことだと思う。今回は以下のものを使用した。

github.com

ブートROM

これもファミコンとの違いの一つではあるのだけど、ゲームボーイはブートROMを持っている。0x0000~0x0100がブートROMの領域なんだけど一度起動後は0x000~0x0100はカートリッジのROM領域に再マッピングされるという仕様らしい。そういう挙動不安になる。

表示はできたもののスクロールが実装できていないので中央に居座っている。

スクロールが絡む座標計算は何度実装しても難しくてすんなりいった試しがない。y方向の座標計算をミスっていたためホラーっぽい仕上がりに。

完成。自分にとってゲームボーイは緑っぽいLCDの色のイメージなのでわざわざこの色に修正した。

CPUテスト

CPUテストROMはここにある。こいつはシリアルにも結果を出力してくれる便利なやつ。

github.com

動かすには苦労した。デフォルトのカートリッジタイプではなくRAMを持ったカートリッジタイプでRAMにプログラムをコピーしてから実行するような作りになっていたためすんなりとはいかなかった。

ただ、このROMは個別実行できたりかなり重宝した。難点としてはアセンブラが結構複雑で読んでもどこで落ちているのかわからないこともしばしば。

Opus5

謎のシューティング風ゲーム。敵もいなければ攻撃もできない主にスクロールとキー入力確認用ROMと言う感じ。またはじめてスプライトが登場したのでここで実装した。たしかスプライト用DMAも使用していてそれも合わせて実装した気がする。

ゲームボーイの解像度は160×144なので4kディスプレイで遊ぶとこうなる。早くスケール機能をつけないといけない。

テトリス

テトリスはなぜかすんなり動いて完成した気になってた。

スーパーマリオランド

これが全然だめだった。一番のミスはタイルIDの取り違い。昔のゲームはメモリ容量が少ないためVRAMにピクセルデータを直接持たせるのではなくスプライトデータを指し示すタイルIDを敷き詰めることになる。が、ゲームボーイはこれが負の値になる場合があるようでこれにハマッた。結局この値の持ち方にどのような利点があるのかさっぱりわからず。タイルIDがずれた分不思議な世界が描画されてた。

マリオがハエだしGが反転しながら襲ってくる。

マリオがたくさん。

反転しながら襲ってくるGを避け3を手にするとやっぱりハエになる。

2つに割れる。

これから

先にも書いたとおり、ひとまずはWebAssembly対応して遊んでみる。 あともう少し技術的詳細を書いた記事はどこかのタイミングで書こうかとは思ってる。けど腰は重そう。

そういえば以前ファミコンエミュレータを書くのをおすすめしたけど、ゲームボーイのほうがハマりポイントが少なくてもっとおすすめ。気になる方はぜひ。

Denoを読む(1)

正月にDenoを読んでたメモです。いろいろ間違ってる可能性が高いのでご注意ください。

Denoとは

deno.land

Node.jsの作者Ryan Dahl氏による新しいTypeSciprtのランタイム。Node.jsの反省点を生かして作られてる。 おおきく分けてTypeScript、V8、Rustの三層で構成されていてTypeScriptとRust間はFlatBuffersでやり取りされ、仲介としてC++で書かれたlibdenoが存在する。

参考資料

scrapbox.io

denolib.gitbook.io

yosuke-furukawa.hatenablog.com

読んでいく

前提

実装は日に日に変化しているのでひとまず以下のバージョンについてのメモとする

github.com

Cargo.toml

まずはCargo.tomlを眺めてみる。package.jsonみたいなやつです。dependenciesは以下のような感じ。特段目を引くようなものは見当たらないようにみえる。

[dependencies]
atty = "=0.2.11"
dirs = "=1.0.4"
flatbuffers = "=0.5.0"
futures = "=0.1.25"
getopts = "=0.2.18"
http = "=0.1.14"
hyper = "=0.12.19"
hyper-rustls = "=0.15.0"
kernel32-sys = "=0.2.2"
lazy_static = "=1.2.0"
libc = "=0.2.46"
log = "=0.4.6"
rand = "=0.6.3"
remove_dir_all = "=0.5.1"
ring = "=0.13.5"
rustyline = "=2.1.0"
serde_json = "1.0.34"
source-map-mappings = "0.5.0"
tempfile = "=3.0.5"
tokio = "=0.1.13"
tokio-executor = "=0.1.5"
tokio-fs = "=0.1.4"
tokio-io = "=0.1.10"
tokio-process = "=0.2.3"
tokio-threadpool = "=0.1.9"
url = "=1.7.2"
winapi = "=0.3.6"

Rust側を見てく

エントリポイントはsrc/main.rsぽいのでここから読んでいく。

  • src/main.rs
fn main() {
  // ... ommited ... 基本的にはロガーの設定

  let state = Arc::new(isolate::IsolateState::new(flags, rest_argv, None));
  let snapshot = snapshot::deno_snapshot();
  let isolate = isolate::Isolate::new(snapshot, state, ops::dispatch);
  tokio_util::init(|| {
    isolate
      .execute("denoMain();")
      .unwrap_or_else(print_err_and_exit);
    isolate.event_loop().unwrap_or_else(print_err_and_exit);
  });
}

前半はロガーの設定などをぼちぼちやる感じ。

isolate::IsolateStateisolate用のフラグやworker用channelsの保持用ぽい。まずこいつを作る。そもそもisolateは何かというとコンテキストが隔離されたJS実行環境と思えばいいのだろうか。chromeでのタブやworkerをイメージすれば良さそう(多分)。実際、最近入ったworker対応でもやはりworker作成時にisolateを作成している。

github.com

let snapshot = snapshot::deno_snapshot()ではv8のsnapshotを作成している。deno_snapshot()は以下。

  • src/snapshot.rs
pub fn deno_snapshot() -> deno_buf {
  #[cfg(not(feature = "check-only"))]
  let data =
    include_bytes!(concat!(env!("GN_OUT_DIR"), "/gen/snapshot_deno.bin"));
  // ... ommited .../

  unsafe { deno_buf::from_raw_parts(data.as_ptr(), data.len()) }
}

deno_snapshotはこれだけでinclude_bytes!でファイルをごそっと読んでそのポインタと長さを返しているだけの様子。snapshotはなんぞやという話は以下を読むと良さそう。

v8.dev

コンテキスト作成時にV8のヒープにロードするのには時間がかかるので、ロード後のsnapshotを撮っておいてそれを使用することで起動を速くする仕組みっぽい。上の記事でもまさにTypeScriptのコンパイラの話をしている。Denoではtools/build.py実行時にdeno/js配下のファイルがトランスパイルかつV8のヒープロードされた状態でスナップショットにされるぽい。なのでjs/*.tsを変更した場合は再ビルドしないと反映されない。ちなみにnew Date()Math.random()は値が焼き付くようなことが書いてある。

あとはtokioの中でdenoMainを実行して、isolate.event_loop()でタスクがなくなるまで待つことになっているぽい。タスクがなくなったらループを抜けて終了する。

tokio_util::init(|| {
  isolate
    .execute("denoMain();")
    .unwrap_or_else(print_err_and_exit);
  isolate.event_loop().unwrap_or_else(print_err_and_exit);
});

tokioの初期化は以下のようになっている。tokioのチュートリアルもやったがこの辺何をやってるのかまだちゃんとわかってない。宿題。

pub fn init<F>(f: F)
where
  F: FnOnce(),
{
  let rt = tokio::runtime::Runtime::new().unwrap();
  let mut executor = rt.executor();
  let mut enter = tokio_executor::enter().expect("Multiple executors at once");
  tokio_executor::with_default(&mut executor, &mut enter, move |_enter| f());
}

そもそもtokioってなにかというとRustの非同期I/Oライブラリで、イベントループを作ってLinuxであればepoll、BSDであればkqueueを使ってディスクリプタを監視し適宜処理を行うやつでNode.jsでいうところのlibuvの役割を果たしているようにみえる。違ったら指摘いただけると。。。 denoを読み始めたんだけど、結局tokioを学ばなければならないとなって正月はほぼ以下を読んでいた。以下はtokioの学習用の簡易実装でいろいろ勉強になる。ひとまずこれを読めばどんなことをやっているかはわかる。(tokioのおもちゃ実装ということで昔はtoykioという名前だった) fahrenheitでは簡素化とポータビリティのためepollではなくselectを使用している。と書いてある。

github.com

ブログ記事もある。

rust-lang-nursery.github.io

ただ、まだ理解できていないのでもう少し勉強して理解できたら別途まとめたい。

isolate.event_loop()がどうなってるかというと以下のようになっていて、self.is_idle()が真になるまでループを抜けてこない。self.is_idle()は非同期タスクが0かつ設定されたtimeoutがなくなると真となる。なので非同期タスクがない(たとえば、console.log("hello");などを実行した)場合は待ちタスクがないのですぐアイドルと判定されループを抜けて終了する。

  pub fn event_loop(&self) -> Result<(), JSError> {
    while !self.is_idle() {
      match recv_deadline(&self.rx, self.get_timeout_due()) {
        Ok((req_id, buf)) => self.complete_op(req_id, buf),
        Err(mpsc::RecvTimeoutError::Timeout) => self.timeout(),
        Err(e) => panic!("recv_deadline() failed: {:?}", e),
      }
      // ommited... promise error check
    }
    // ommited... promise error check
    Ok(())
  }

ループ内では、recv_deadline(&self.rx, self.get_timeout_due())で非同期タスク完了のメッセージを待ち続けることになる。

では送信元はどこかというとdeno/src/isolate.rsextern "C" fn pre_dispatchの以下の箇所っぽい。タスクを登録して、その完了時にsender.sendでメッセージを送信している。

let task = op
  .and_then(move |buf| {
    let sender = tx; // tx is moved to new thread
    sender.send((req_id, buf)).expect("tx.send error");
    Ok(())
  }).map_err(|_| ());
  tokio::spawn(task);

extern "C"がついていることからもC++で書かれたlibsenoから叩かれる箇所だと推測できる。追ってみるとIsorate::newlibdeno::configに受信コールバックとして渡されている。

let config = libdeno::deno_config {
  will_snapshot: 0,
  load_snapshot: snapshot,
  shared: libdeno::deno_buf::empty(), // TODO Use for message passing.
  recv_cb: pre_dispatch,
  resolve_cb,
};

let task = op.and_then(...)opは何かというと、以下のようなシグネチャになってる。

pub type Op = Future<Item = Buf, Error = DenoError> + Send;

deno/src/ops.rsdispatchの返り値となっており、dispatchでメッセージのデシリアライズ後matchでファイルの読み書きやフェッチなどの処理に振り分けられる。例えばメッセージの種別がReadFileであれば以下のようにop_read_fileに振り分けられる。

pub fn dispatch(
  isolate: &Isolate,
  control: libdeno::deno_buf,
  data: libdeno::deno_buf,
) -> (bool, Box<Op>) {
  let base = msg::get_root_as_base(&control);
  let is_sync = base.sync();
  let inner_type = base.inner_type();
  let cmd_id = base.cmd_id();
  let op: Box<Op> = if inner_type == msg::Any::SetTimeout {
    // ... ommited ...
  } else {
    // Handle regular ops.
    let op_creator: OpCreator = match inner_type {
      msg::Any::ReadFile => op_read_file,
      // ... 他の実処理に分岐される ...

たとえば一番シンプルな処理っぽいchdirであれば以下のような感じ。該当する処理を行ってBox<Op>を返すという感じ。

fn op_chdir(
  _state: &Arc<IsolateState>,
  base: &msg::Base,
  data: libdeno::deno_buf,
) -> Box<Op> {
  assert_eq!(data.len(), 0);
  let inner = base.inner_as_chdir().unwrap();
  let directory = inner.directory().unwrap();
  Box::new(futures::future::result(|| -> OpResult {
    std::env::set_current_dir(&directory)?;
    Ok(empty_buf())
  }()))

ここでの結果がpre_dispatchis_syncフラグと一緒に戻されて、非同期/同期で処理が分岐される。

例えば同期モードであれば(https://github.com/denoland/deno/blob/6f79ad721a9f8c9d66d79f21ea479286f3ca5374/src/isolate.rs#L416-L425) のようにbloking_onで処理の完了を待ってからレスポンスメッセージが送られる。

let buf = tokio_util::block_on(op).unwrap();
let buf_size = buf.len();

if buf_size == 0 {
  // FIXME
 isolate.state.metrics_op_completed(buf.len());
} else {
  // Set the synchronous response, the value returned from isolate.send().
  isolate.respond(req_id, buf);

非同期の場合は先に記載したように処理の完了を待って完了後、完了が通知される。この通知は先のisolate.event_loop()内で受信されて非同期タスクの完了処理が実行される。完了処理は現在待機中のタスク数のデクリメント(tokio側のAPIを使いたい旨のコメントがあったが、問題があるのか現在は手動で行っている。)とV8側へのレスポンス

let tx = isolate.tx.clone();
isolate.ntasks_increment();
let task = op
  .and_then(move |buf| {
    let sender = tx; // tx is moved to new thread
    sender.send((req_id, buf)).expect("tx.send error");
    Ok(())
  }).map_err(|_| ());
tokio::spawn(task);

TypeScript側を見てく

Rust側の大枠の流れはわかったのでTypeScript側を見てみる エントリポイントはjs/main.ts。ここにRust側から呼ばれていたdenoMainがある。

export default function denoMain() {
  libdeno.recv(handleAsyncMsgFromRust);
  const startResMsg = sendStart();

  // ... ommited ...

  os.setPid(startResMsg.pid());

  const cwd = startResMsg.cwd();
  log("cwd", cwd);

  for (let i = 1; i < startResMsg.argvLength(); i++) {
    args.push(startResMsg.argv(i));
  }
  log("args", args);
  Object.freeze(args);
  const inputFn = args[0];

  compiler.recompile = startResMsg.recompileFlag();

  if (inputFn) {
    compiler.run(inputFn, `${cwd}/`);
  } else {
    replLoop();
  }
}

まずはlibdeno.recv(handleAsyncMsgFromRust);でRust側からの受信コールバックを設定する。

const promiseTable = new Map<number, util.Resolvable<msg.Base>>();

export function handleAsyncMsgFromRust(ui8: Uint8Array) {
  // If a the buffer is empty, recv() on the native side timed out and we
  // did not receive a message.
  if (ui8.length) {
    const bb = new flatbuffers.ByteBuffer(ui8);
    const base = msg.Base.getRootAsBase(bb);
    const cmdId = base.cmdId();
    const promise = promiseTable.get(cmdId);
    util.assert(promise != null, `Expecting promise in table. ${cmdId}`);
    promiseTable.delete(cmdId);
    const err = errors.maybeError(base);
    if (err != null) {
      promise!.reject(err);
    } else {
      promise!.resolve(base);
    }
  }
  // Fire timers that have become runnable.
  fireTimers();
}

基本的にここに到達するのはTypeScript側から非同期処理を呼んでその応答がRust側から返ってきたケース(だと思う)。非同期処理開始メッセージを送る祭にcommandIdをキーにPromisepromiseTableに登録しておいて、返ってきたメッセージのcommandIdをキーにそれを回収、resolve/rejectを実行してるっぽい。

ちょうど下にsendAsyncというのがいた。promiseTable.set(cmdId, promise);してる。

export function sendAsync(
  builder: flatbuffers.Builder,
  innerType: msg.Any,
  inner: flatbuffers.Offset,
  data?: ArrayBufferView
): Promise<msg.Base> {
  const [cmdId, resBuf] = sendInternal(builder, innerType, inner, data, false);
  util.assert(resBuf == null);
  const promise = util.createResolvable<msg.Base>();
  promiseTable.set(cmdId, promise);
  return promise;
}

次にconst startResMsg = sendStart(); でスタートメッセージを同期モードで送信している。Rust側で各メッセージに対して何をやっているかはops.rsを見ればいいのがわかったいるので覗いてみる。

let inner = msg::StartRes::create(
  &mut builder,
  &msg::StartResArgs {
    cwd: Some(cwd_off),
    pid: std::process::id(),
    argv: Some(argv_off),
    debug_flag: state.flags.log_debug,
    recompile_flag: state.flags.recompile,
    types_flag: state.flags.types,
    version_flag: state.flags.version,
    v8_version: Some(v8_version_off),
    deno_version: Some(deno_version_off),
    ..Default::default()
  },
);

基本的にはRust側でもている基本的情報を返信しているだけっぽい。返してるメッセージは上記のようなものでフラグとか引数、プロセスIDやバージョンなどを詰めて返している模様。 あとは返ってきたメッセージの引数やフラグなどを処理して以下のようにファイルが指定されていればコンパイルして実行。なければREPLモードに入るっぽい。

if (inputFn) {
  compiler.run(inputFn, `${cwd}/`);
} else {
  replLoop();
}

compiler.runの先はどうなってるかまだちゃんとみてないけど、CodeFetchというメッセージが同期が飛んでるのでRust側で該当ファイルを読んで返却後トランスパイルしてどこかにキャッシュしてるのかな。今度みる。

FlatBuffers

メッセージのやり取りにはFlatBuffersが使用されているが、定義はsrc/msg.fbsにいる。

github.com

tools/build.pyを実行するとTypeScriptとRustのコードがtarget/debug/gen/配下にmsg_generated.rsmsg_generated.tsとして生成される。

たとえば先のstartメッセージのレスポンスであれば以下のように定義されている。

table StartRes {
  cwd: string;
  argv: [string];
  debug_flag: bool;
  deps_flag: bool;
  recompile_flag: bool;
  types_flag: bool;
  version_flag: bool;
  deno_version: string;
  v8_version: string;
}

FlatBuffersはロード時にパースせず値が必要なときまで後回しするなどオーバーヘッドが少なく速いらしい。 このへんもまた今度詳しく調べてみる。

qiita.com

setTimeoutを実行してみる

だいたいの流れはわかったのでひとまず何か非同期処理を実行してみる。まずはsetTimeoutを試してみる。あとこの辺試してて気づいたんですが、microtaskのqueueはV8側で面倒見てくれるっぽい。知らなかった。

setTimeout(() => console.log("hello"), 1000);

を実行してみてその流れをみてみる。

setTimeoutjs/timer.tsに定義されている。

export function setTimeout(
  cb: (...args: Args) => void,
  delay: number,
  ...args: Args
): number {
  return setTimer(cb, delay, args, false);
}

これをたどっていくとsetGlobalTimeoutでメッセージを作って送信しているのがわかる。ただし、sendSync で送られている。timeout周りは非同期ながら若干特別扱いされてるっぽい。

function setGlobalTimeout(due: number | null, now: number) {
  // ... ommitted...
  // Send message to the backend.
  const builder = flatbuffers.createBuilder();
  msg.SetTimeout.startSetTimeout(builder);
  msg.SetTimeout.addTimeout(builder, timeout);
  const inner = msg.SetTimeout.endSetTimeout(builder);
  const res = sendSync(builder, msg.Any.SetTimeout, inner);

  globalTimeoutDue = due;
}

これはsrc/ops.rsdispatchのメッセージから各処理への分岐部分に書いてあった。例外的に同期処理として扱われメインスレッドで更新されるとのこと。

let op: Box<Op> = if inner_type == msg::Any::SetTimeout {
  // SetTimeout is an exceptional op: the global timeout field is part of the
  // Isolate state (not the IsolateState state) and it must be updated on the
  // main thread.
  assert_eq!(is_sync, true);
  op_set_timeout(isolate, &base, data)
}

op_set_timeoutを見るとどうもisolate側にtimeout値を設定しているだけのよう。そして同期モードのメッセージなのでdummyの空bufferをひとまず返してTypeScript側がブロックしないようにしてるっぽい。

fn op_set_timeout(
  isolate: &Isolate,
  base: &msg::Base,
  data: libdeno::deno_buf,
) -> Box<Op> {
  let inner = base.inner_as_set_timeout().unwrap();
  let val = inner.timeout() as i64;
  let timeout_due = if val >= 0 {
    Some(Instant::now() + Duration::from_millis(val as u64))
  } else {
    None
  };
  isolate.set_timeout_due(timeout_due);
  ok_future(empty_buf())
}

timeout_dueがセットされると最初の方で記載したisolate.eventloopself.is_idleが偽になってrecv_deadlineで受信待ちになる。

pub fn event_loop(&self) -> Result<(), JSError> {
  while !self.is_idle() {
    match recv_deadline(&self.rx, self.get_timeout_due()) {
      Ok((req_id, buf)) => self.complete_op(req_id, buf),
      Err(mpsc::RecvTimeoutError::Timeout) => self.timeout(),
      Err(e) => panic!("recv_deadline() failed: {:?}", e),
    }
    // ... ommited ...
 }

recv_deadlineは以下のようになっている。dueが設定されていれば、rx.recv_timeout(timeout)でタイムアウトを待つ。が、その後非同期メッセージを受信した場合は一旦rx.recv_timeoutから抜けてきてしまうので、後続の非同期タスクを登録したあと、次ループで再度rx.recv_timeoutで待つんだと思う。

fn recv_deadline<T>(
  rx: &mpsc::Receiver<T>,
  maybe_due: Option<Instant>,
) -> Result<T, mpsc::RecvTimeoutError> {
  match maybe_due {
    None => rx.recv().map_err(|e| e.into()),
    Some(due) => {
        let now = Instant::now();
      let timeout = if due > now {
        due - now
      } else {
        Duration::new(0, 0)
      };
      rx.recv_timeout(timeout)
    }
  }
}
let now = Instant::now();
let timeout = if due > now {
  due - now
} else {
  Duration::new(0, 0)
};

とやっているのは一度ループから抜けた際に経過してしまった時間を吸収してるっぽい。なので、常に設定されるタイマーは一個になる気がする。 なので以下を実行した場合も1,000msと2,000msのタイマーが設定されるわけではなく1,000msのタイマーを待ったあと再度差分の1,000ms(実際には997とか微妙に減った値だと思う)が設定されるぽい。

setTimeout(() => {...}, 1000);
setTimeout(() => {...}, 2000);

そうするとTypeScript側も工夫が必要で複数のタイマーはひとまずconst dueMap: { [due: number]: Timer[] } = Object.create(null); に管理されるっぽい。稼働中のタイマーのみglobalTimeoutDueにセットされて管理される。現在のタイマーが完了前に次のタイマー設定が来た場合はglobalTimeoutDueが未設定、もしくは globalTimeoutDueより期限が近いタイマーが新たに設定されるっぽい。そのへんをやってるのが以下。

function schedule(timer: Timer, now: number) {
  assert(!timer.scheduled);
  assert(now <= timer.due);
  let list = dueMap[timer.due];
  if (list === undefined) {
    list = dueMap[timer.due] = [];
  }
  list.push(timer);
  timer.scheduled = true;
  if (globalTimeoutDue === null || globalTimeoutDue > timer.due) {
    setGlobalTimeout(timer.due, now);
  }
}

なのでタイマーがセットされると同時にタイムアウト完了コールバックも同時に設定され、コールバック内で次に設定すべきタイムアウトがあれば経過時間を調整して設定、なければ完了メッセージ(timeout = -1)を送っている。Rust側では完了メッセージを受けたら、timeout_dueNoneを設定して(他にまちタスクがなければ)isolate.eventloopを抜けて終了という流れっぽい。

なのでhandleAsyncMsgFromRustfireTimersはまさにそれようなんですね。バッファが空の場合はタイムアウトという取り決めのもと次のタイマーをセットしにいってるんだと思う。

export function handleAsyncMsgFromRust(ui8: Uint8Array) {
  if (ui8.length) {
    // ... ommitted ...
  }
  // Fire timers that have become runnable.
  fireTimers();
}

かなり昔にtokio_timerを使ってタイマーを実装するというissueを見かけた気がしたけど、そのような作りではなく、どのような議論を経てこの実装になっているのかはちょっとわからん。

非同期処理を確認したかったんだけどsetTimeoutはちょっと特殊だったっぽい。次はreadFileとかcodeFetch周りを読めたら読みたい。

ひとまずここまで。

Deno用のpretty_assertを作った

あけましておめでとうございます。

tl;dr

Denoの入門に以下を作った

github.com

f:id:bokuweb:20190104183220p:plain

Deno?

https://deno.land/

概要

Ryan DahlがRustでDenoというものを作っていると聞いたとき貢献したいなーと思っていたけど、忙しさを言い訳に長い間ビルドすらできずにいた。

そんな中最近になってTLでDenoを楽しそうに触ってる方々がでてきて、みんなあまりに楽しそうなので触発されて自分の始めることにした。特にhashrockさんの記事をみて自分もやるぞ!となった。

hashrock.hatenablog.com

Denoを読んで見る

最近なかなかまとまった時間が取れてなかったけど正月は時間がとれそうだったのでdenoを読むというのをハイプライオリティなタスクとしてスケジュールし、12/31〜1/1はDenoとその周辺を読んでた。

まだまだ理解が怪しいがどのように動いているかは把握できた気がするのでもうちょっとアップデートしてできれば記事にしたい。

Denoのテスト周り

Denoをきりのいいところまで読んだあとまずは人間に見やすいアサートを書いてみるか。ってことになった。 Denoにはテスト用のモジュールがあり以下のように書ける。

import { test, assertEqual } from 'https://deno.land/x/testing/testing.ts';

test({
  name: 'example',
  fn() {
    assertEqual(10, 10);
  },
});

が、テスト失敗時の出力が見にくかった為だ。

実装

モジュールを作りはじめると「あれもない、これもない」となる。具体的にはjestのもっているpretty-formatを使いたかったのだが、直接は使えないのでひとまず export { default } from 'pretty-format'; を書いてrollupでバンドル後@ts-ignore を付加する方法をとった。anyになるしあまりいい方法ではないので今後何かしらいい方法が提案されるんじゃないかな。

これで一応import prettyFormat from './pretty-format/dist/index.js';として使用できる。

あと自分はたまたまno dependenciesのdiffライブラリを作っていたのでこれらを使用してassert結果を色付してやった。(こっちはまったく手をいれずimport diff, { DiffType } from 'https://denopkg.com/bokuweb/wu-diff-js@0.1.6/lib/index.ts';として使用できた。便利。)

denolandにはregistoryが用意してあって、PRを送ってマージされるとhttps://deno.land/x/pretty_assert@0.1.1/index.tsのようなURLで使用できるようになる。

github.com

多くのnpmモジュールは何かしらの方法で使用することはできるけど、NodeのAPIに依存したものはやはり移植する必要があるので、そのあたりから貢献してみるのは勉強にもなるし良さそうだと思った。

wasm-bindgenを使ってRustのモジュールをnode_modulesに持ってくる

この記事はWebAssembly Advent Calendar 2018の21日目です。wasm-bindgenを使用して何かしてみたいと思っていたので、今回は以前Rustで実装した画像の差分を取るツールをwasm-bindgenを使用してnode_modulesとして使用できるようにしてみたいと思います。

adventar.org

移植元

github.com

これはもともと、go-diff-image(https://github.com/murooka/go-diff-image)というgolang製のツールをRustへポーティングしたものになります。

github.com

同じピクセル同士を比較して差分を出力するのではなく、githubのdiffのような感じで画像の差分を可視化するツールです。 以下のような比較画像を生成します。

f:id:bokuweb:20181221223051p:plain

成果物

github.com

手順

さっそくミニマムなプロジェクトを作ってみます。

  • cargo.toml
[package]
name = "node-lcs-img-diff"
version = "0.1.0"
authors = ["bokuweb"]
edition = "2018"

[lib]
crate-type = ["cdylib"]

[dependencies]
wasm-bindgen = "0.2"

wasm-bindgen-cliが入ってない場合はインストールします。

rustup target add wasm32-unknown-unknown --toolchain nightly
cargo +nightly install wasm-bindgen-cli

まずは1を加算する関数で試してみます。

  • src/lib.rs
use wasm_bindgen::prelude::*;

#[wasm_bindgen]
pub fn add_one(n: usize) -> usize {
    n + 1
}

次にMakefileを用意しておきます。 wasm-bindgenはデフォルトブラウザ向けのコードを吐きますが、今回はnodejs向けに--nodejsつけて実行するようにします。

build:
    cargo +nightly build --target wasm32-unknown-unknown --release
    mkdir -p dist
    wasm-bindgen ./target/wasm32-unknown-unknown/release/node_lcs_img_diff.wasm --out-dir ./dist --nodejs

以下でビルド。

$ make build
  • node_lcs_img_diff_bg.d.ts
  • node_lcs_img_diff_bg.js
  • node_lcs_img_diff_bg.wasm
  • node_lcs_img_diff.d.ts
  • node_lcs_img_diff.js

が吐かれる

  • node_lcs_img_diff_bg.d.ts
/* tslint:disable */
export const memory: WebAssembly.Memory;
export function add_one(a: number): number;

内部で使用される定義

  • nodde-lcs_img_diff.d.ts
/* tslint:disable */
export function add_one(arg0: number): number;

公開関数の定義

  • node_lcs_img_diff_bg.js
const path = require('path').join(__dirname, 'node_lcs_img_diff_bg.wasm');
const bytes = require('fs').readFileSync(path);
let imports = {};

const wasmModule = new WebAssembly.Module(bytes);
const wasmInstance = new WebAssembly.Instance(wasmModule, imports);
module.exports = wasmInstance.exports;

wasmの読み込みからinstanciateまで。

  • node_lcs_img_diff.js
/* tslint:disable */
var wasm;

/**
* @param {number} arg0
* @returns {number}
*/
module.exports.add_one = function(arg0) {
    return wasm.add_one(arg0);
};

wasm = require('./node_lcs_img_diff_bg');

使用方法は以下のように呼ぶだけ。

  • index.ts
import { add_one } from './dist/node_lcs_img_diff';

add_one(1); // -> 2

良さそうです。 後はせっせと移植していきます。 注意点としてはVecは返り値として返せないので、そのような場合JSONにしStringを返すことになりそうです。

github.com

細かい部分は省略しますが、Rust側は以下のようになりました。去年以下の記事を書きましたがwasm-bindgenのおかげで受け取る値も返す値もシンプルになっています。以前はArrayBufferのオフセットやデータの長さを受け取り、自分でバッファに変換する必要がありましたが、そのあたりの処理をwasm-bindgenが受け持ってくれているからですね。

qiita.com

どういうことをやっているかざっくり言うと、画層データを2枚受け取ってデコード。差分が発生した領域を計算して、元画像に緑/赤色をブレンドしたあとpngにエンコードして返しています。細かい処理は省略していますが、mainとなるdiff関数は以下のような感じです。

  • lib.rs
#[wasm_bindgen]
pub fn diff(before: &[u8], after: &[u8]) -> String {
    let mut before = load_from_memory(before).expect("Unable to load image from memory");
    let mut after = load_from_memory(after).expect("Unable to load image from memory");
    let encoded_before = create_encoded_rows(&before.raw_pixels(), before.dimensions().0 as usize);
    let encoded_after = create_encoded_rows(&after.raw_pixels(), after.dimensions().0 as usize);
    let result = lcs_diff::diff(&encoded_before, &encoded_after);
    let mut added: Vec<usize> = Vec::new();
    let mut removed: Vec<usize> = Vec::new();
    for d in result.iter() {
        match d {
            &lcs_diff::DiffResult::Added(ref a) => added.push(a.new_index.unwrap()),
            &lcs_diff::DiffResult::Removed(ref r) => removed.push(r.old_index.unwrap()),
            _ => (),
        }
    }
    create_marked_image(&mut after, (99, 195, 99), RATE, &added);
    create_marked_image(&mut before, (255, 119, 119), RATE, &removed);
    serde_json::to_string(&Result {
        after: to_png(&after),
        before: to_png(&before)
    }).unwrap()
}

typescriptの型まで吐いてくれるので以下のように使用できます。

  • index.ts
import { diff } from './dist/node_lcs_img_diff';

const [before, after] = await Promise.all([readFile("YOUR_IMAGE"), readFile("YOUR_IMAGE")]);
JSON.parse(diff(before, after));

実際にはcliや画像の読み書き処理を追加しています。詳しくは以下を参照してみてください。

github.com

あとはbuildしてnpn publishすれば完了です。

速度

自分はよくJavaScriptとwasmの速度比較を行うのですが、今回はJavaScript実装がないのでRust版と速度比較をしてお茶を濁しときます。

  • wasm(node v10.11.0)
Benchmark #1: node . test/images/before.png test/images/after.png --dist test/expected
  Time (mean ± σ):     720.2 ms ±  57.1 ms    [User: 1.150 s, System: 0.145 s]
  Range (min … max):   687.9 ms … 821.9 ms    5 runs
  • Rust 1.31
Benchmark #1: lcs-image-diff test/images/before.png test/images/after.png aaa.png
  Time (mean ± σ):      29.3 ms ±   0.8 ms    [User: 26.2 ms, System: 5.0 ms]
  Range (min … max):    28.2 ms …  32.4 ms    89 runs

ベンチマークにはhyperfineを使用しました。(MacBook Air (11-inch, Early 2015), 1.6 GHz Intel Core i5, 8 GB 1600 MHz DDR3)です。 結構な差がでましたね。どうもwasmの方はwasmファイルのリードからinstansiateまでで200msくらい持ってかれてるようです。diff関数は185msくらいですね。

ファミコンのエミュレータをRust / WebAssembly で書き直した

f:id:bokuweb:20180208090512p:plain

概要

以前、JSで書いた(ファミコンのエミュレータを書いた - undefined)ファミコンのエミュレータをRustで書き直してみた。 また、技術的な内容はQiitaの方にも書いているので興味のある方は参照してみてください。(まだ Hello, World!までしか書けてませんが。)

qiita.com

もともとファミコンのエミュレータって新しい言語を習得するのにちょうどいい題材だったりするのでは、って話しからスタートしてて、よくわからないのでJSで書いてみて、ようやくRustで一通りは実装できた感じ。まだバグや未実装(音声周りやマッパー)も多いんですが、ひとまずはお腹いっぱいな感じ。

成果物

github.com

あと、いくつかのROMは以下で遊べるようにしてます。音が出るので注意してください。 またAPUの実装にまだバグが残っているのDCMチャンネルが未実装なので音が変だったり出てなかったりします。 描画のほうはマッパー0であれば、ほぼほぼ問題ないと思ってます。

また、現状chromeでのみ動きます。firefoxは(多分)esmodulesのフラグを立てれば動きます。

https://bokuweb.github.io/rustynes/

CPUやPPUやRAM / ROM周りをRustで書いて、描画や音はemscriptenを介してJS側でcanvas / WebAudioのAPIを叩くようにしています。 これに着手し始めたときは、wasm32-unknown-emscripten しか選択肢がなかったのですが、今なら、wasm32-unknown-unknown が選択できます。 今から着手するなら、wasm32-unknown-unknown 前提で、stdwebwasm-bindgen辺りを使用しemscriptenを剥がしたほうが良い面が多いような気がします。

過程

移植するだけなので強くてニューゲーム気分だったんですが、駄目ですね。 前回よりわけの分からない状態は減ったものの、それでもおかしなバグには遭遇しました。

Hello world

ここまでは、とにかくコンパイラに怒られまくったりどうやってブラウザで描画するのがいいのか悩んだりで大変でした。Qiitaかどこかにも書きましたがHello, World!を表示するにはCPUがほぼほぼ実装できていないといけないのでやはりここまでは苦労しますね。

GIKO005

スプライトを表示するサンプル。Hello, Worldからここまではすんなり。

GIKO016

スクロールが絡んでくるとやはりよくわからないこと現象に遭遇する

GIKO017

前回対応していなかった8 * 16形式のスプライトに対応した、が、ばぐってて歩く度に顔が上下するキャラクターが産まれてしまった。

Super mario bros

さすがにハマりどこは抑えてたので着手後早い段階でそこそこ描画されてた。

思わぬところがスクロール

隠しブロックが隠れてない

土管が仕事しない

音の伸びが良すぎる このバグまだ解決できてなくて、地下でブロック叩いたときになんとも言えない音が鳴る

falling

f:id:bokuweb:20180208090512p:plain

今回見つけた謎のROM。ひたすらおっさん(?)が落ちていくゲーム。 実はオープンソースで、initial commitが2018年の1月7日になっている。

github.com

つまり2018年産まれのファミコンROMということになる。タイトルの音楽が好きだったりする(ちょっとAPUの実装の都合でおかしいとこありますが)

速度

WebAssemblyというと速度が気になると思います。JS版との比較を行ってみました。 WebAudio周辺は共通かつJSは側の処理なので比較はAPUをディセーブルにして、giko017.nesでメインループの処理時間20回分の平均値を取っています。マシンはMacBook Air (11-inch, Early 2015) , 1.6 GHz Intel Core i5, 8 GB 1600 MHz DDR3

ブラウザ JS版 Wasm版
Chrome 63 4.36ms 5.68ms
Firefox 58 5.76ms 3.98ms
Safari 11 9.98ms 4.21ms

Firefox, Safariではwasmのほうが速かったんですが、chromeではJS版の方が速くwasm版はイマイチでした。emscriptenのグルーコードのオーバーヘッドやrust / wasm周りに不備、チューニング不足も当然あるでしょうが、firefoxでそこそこ速いこと考えると、v8すごいって話しとchrome x wasmはまだまだってことになるんでしょうか。このあたり正直なところよくわかってないです。

さいごに

まだ未実装箇所やバグも多いんですが、お腹いっぱいなのでひとまずここまでにして、何か次に取り掛かりたいなーという思い。 一応Rustで書いたものの、分からないことだらけでもう少し、いろいろ書いてみないとなーという気持ち。

なにかおかしなことしてたらプルリクエストなどいただけると泣いて喜びます

題材としては、以前お世話になったARM7のエミュレータを書いてみるとか、ラズパイにOSを移植してみるとかが楽しそうだなーと思いつつ、goも勉強したいので時間はかかりそうです。