tana_ash's diary

プログラミングや電子工作など。やってみたこと、わかったことをまとめておく場所。

Vim Scriptでレイトレーシング

経緯

以前、「Vim Scriptでもレイトレーシングができるのではないか?」ということを考えていました。 昨日早朝、布団の中でそのことを突然思い出したので布団を飛び出し衝動的に実装しました。

tana/vimtracer · GitHub

機能

このような画像をPPM形式で生成できます。 256x256ピクセルの画像を54秒で生成できました。(Intel Core i5 3.40GHz、Vim 7.4)

f:id:tana-ash:20150221201422p:plain

点光源と影、反射を実装しました。 物体は球体しか実装していないので、平面のように見える白い床も実は巨大な球体です。

今のところは球体の位置や色、画像サイズもすべてハードコーディングされています。

気づいたこと

Vim Scriptには制御構造や関数のほかに浮動小数点数、リスト、辞書のデータ構造を持っているので、 基本的にはRubyPythonのような言語に近い感覚でプログラムが書けます。

しかしレイトレーシングを書くには若干心細く、

  • max/min関数が浮動小数点数に対応していない/比較方法を指定できない
  • ファイル出力がfilewrite関数(行のリストを一気に書き出す)しかない
  • バイナリファイルに0を出力するためにnr2char(0)を使うと、ヌル文字ではなく空文字列''が返る

という問題がありました。そのために

  • 浮動小数点数リストの最小値を求めるfmin関数を自作する
  • PPMファイルをバイナリ形式(P6)で出力することを断念し、テキスト形式(P3)で出力する

という方法で解決しています。

まとめ

Vim Scriptは浮動小数点数の扱いやバイナリファイル入出力などの機能がレイトレーシングには若干心細く思います。 しかし、他の言語と比べて極端に難しいというわけでもなく、それなりに複雑な処理も書くことができました。

mrubyをSTM32 Nucleoボードで動作させる

今年、STマイクロから新しいSTM32マイコンボード、Nucleo(
STM32 MCU Nucleo - STMicroelectronics)が発売されました。Arduino互換のピンを持ち、最大で96KBのRAMを搭載しています。なおかつmbedに対応しドラッグ&ドロップで書き込みが可能で、そしてそれが1500円です(秋月電子にて)。

私はこのボードを知った時から、mrubyを動作させることを考えていました。そして先週、秋月電子にてついにNucleoを購入することが叶い、早速mrubyを動作させてみることに決めました。

目標

Cortex-M4プロセッサ、512KBのFlash、96KBのSRAMを搭載したNucleo F401REボードでmrubyを動作させる。

(他のNucleoボードではRAMが不足する可能性があるので、今回はF401RE用とします。)

手順

mbedのオフラインコンパイル環境を準備する

まず最初に、Cortex-M/Cortex-R用のCコンパイラとして、GCC ARM Embedded(https://launchpad.net/gcc-arm-embedded)を導入します。基本的にはダウンロードしたアーカイブを展開してパスを通すだけで完了です。

次に、mbed SDK(https://github.com/mbedmicro/mbed)を、mbed tools - Handbook | mbed を参考に準備します。

# 必要なライブラリ
pip install jinja2
# ライブラリをビルド
python workspace_tools/build.py -m NUCLEO_F401RE -t GCC_ARM

ところで、mbed SDKにはmakeでコンパイルできるようにプロジェクト全体をエクスポートする機能があるのですが、GCC ARM向けに書き出す機能はNucleoでは未実装のようです。しかし、ライブラリのディレクトリを覗いてみるとNucleo用のターゲット依存ファイルはGCC ARM用のファイルが用意されているようなので、今回は無理矢理エクスポートしてみます。
まず、似たような(と私が思っている)Cortex-M4のSTM32F407を積んだDISCOVERYボード用のテンプレートファイル(?)を、そのままコピーします。

cp workspace_tools/export/gcc_arm_disco_f407vg.tmpl workspace_tools/export/gcc_arm_nucleo_f401re.tmpl

次に、workspace_tools/export/gccarm.py の、GccArmクラスのTARGETS変数(配列)の最後に

'NUCLEO_F401RE'

という文字列を追加しておきます。

これによって、mbedプロジェクトをGCC ARM用に書き出すことができるようになりました。次のコマンドラインで、mbed SDKのテストプログラムを書き出してみます。(この手順については http://embeddedworldweb.blogspot.jp/2013/12/how-to-use-mbed-exporters-tutorial.html が詳しいです。)

python workspace_tools/project.py -m NUCLEO_F401RE -p0 -i gcc_arm

build/exportディレクトリにzipファイルが作られます。これを展開してmakeすると.binファイルが生成されます。今回は、これをベースにmrubyを組み込んでいきます。

mrubyのチューニングとビルド設定

そのままのmrubyはRAMの消費が大きいので、ここではビルド時のオプションでチューニングするとともに、標準ライブラリをいくつか削ってしまいます。
標準ライブラリを削ることで多くのメソッドが使用できなくなってしまいますが、RAM消費量の削減効果は絶大です。
今回はmrblibディレクトリのenum.rb、hash.rb、range.rb、string.rbの拡張子を変更して、組み込まれないようにしました。
さらに、チューニングオプションとARM用のクロスコンパイル設定をbuild_config.rbに追加しました。

MRuby::CrossBuild.new('nucleo') do |conf|
  toolchain :gcc
  conf.cc.command = "arm-none-eabi-gcc"
  conf.linker.command = "arm-none-eabi-gcc"
  conf.archiver.command = "arm-none-eabi-ar"

  conf.cc.flags << "-mcpu=cortex-m4 -mthumb -mfpu=fpv4-sp-d16 -ffunction-sections -fdata-sections"
  conf.cc.defines = %w(MRB_WORD_BOXING MRB_HEAP_PAGE_SIZE=8 MRB_USE_IV_SEGLIST KHASH_DEFAULT_SIZE=8 MRB_STR_BUF_MIN_SIZE=20 DISABLE_STDIO)
  conf.linker.flags << "-Wl,--gc-sections"

  conf.build_mrbtest_lib_only
  conf.bins = []

  #conf.gem 'examples/mrbgems/c_and_ruby_extension_example'

  #conf.test_runner.command = 'env'

end

この状態でmakeします。

使ってみる

続いて、先ほどエクスポートしたGCC ARM用のmbedプロジェクトに、mrubyのライブラリとヘッダファイルをコピーします。
今回は、次のディレクトリ構成にしました。

Makefile
main.cpp
env/ (エクスポートした時にもとからある)
mbed/ (mbedライブラリ)
mruby/
  include/ (mrubyのincludeディレクトリをそのまま持ってくる)
  lib/
    libmruby.a (mrubyのビルド時に生成されるbuild/nucleo/libディレクトリからコピー)

そして、Makefileを次のように変更します。

  • INCLUDE_PATHS変数の末尾に -I./mruby/include を追加
  • 空になっているLIBRARIES変数にmrubyライブラリを追加 LIBRARIES = ./mruby/lib/libmruby.a
  • CC_SYMBOLS変数の末尾に -DMRB_WORD_BOXING を追加 (mrubyビルド時のオプションと合わせる)

次に、いよいよmrubyを組み込んだプログラムを作成します。今回は次のmain.cppを使用します。シリアル通信とLED用のメソッドを追加しておきました。
このプログラムはCの配列としてtest.cに書き込まれたmrubyバイトコードを実行します。

#include "mbed.h"
#include <mruby.h>
#include <mruby/dump.h>
#include <mruby/string.h>
#include <stdint.h>
#include "test.c"

DigitalOut myled(LED1);
Serial pc(SERIAL_TX, SERIAL_RX);

extern const uint8_t bytecode[];

mrb_value mrb_serial_puts(mrb_state *mrb, mrb_value self) {
  mrb_value str;
  mrb_get_args(mrb, "S", &str);
  pc.printf("%s\n", RSTRING_PTR(str));
  return mrb_nil_value();
}

mrb_value mrb_wait(mrb_state *mrb, mrb_value self) {
  mrb_float seconds;
  mrb_get_args(mrb, "f", &seconds);
  wait(seconds);
  return mrb_nil_value();
}

mrb_value mrb_set_led(mrb_state *mrb, mrb_value self) {
  mrb_int state;
  mrb_get_args(mrb, "i", &state);
  myled = state;
  return mrb_nil_value();
}

int main(void) {
  mrb_state *mrb;
  struct RClass *kernel;
  mrb = mrb_open();
  kernel = mrb->kernel_module;
  mrb_define_method(mrb, kernel, "serial_puts", mrb_serial_puts, MRB_ARGS_REQ(1));
  mrb_define_method(mrb, kernel, "wait", mrb_wait, MRB_ARGS_REQ(1));
  mrb_define_method(mrb, kernel, "set_led", mrb_set_led, MRB_ARGS_REQ(1));
  mrb_load_irep(mrb, bytecode);
  mrb_close(mrb);
  return 0;
}

そして、次のRubyプログラムを動作させます。(test.rbというファイル名で保存します)

serial_puts "program start"
while true
  set_led 1
  serial_puts "led on"
  wait 0.5
  set_led 0
  serial_puts "led off"
  wait 0.5
end

次のコマンドでバイトコードを生成します。(/path/to/mruby/bin/mrbcはmrubyをビルドしたディレクトリによって変わります)

/path/to/mruby/bin/mrbc -Bbytecode test.rb

いよいよビルドです。makeコマンドを実行するとバイナリが生成されます。
生成されたMBED_A1.binをNucleoのドライブにドラッグ&ドロップで書き込むと、シリアルポートに文字列を出力しながらLEDが点滅します。

TODO

Vimで二分探索のようにカーソルを移動する

そんなVimプラグインを昔見たことがあったということを突然思い出したので、車輪を再発明するつもりで、初めてVimScriptを書いてみました。

(実際、検索したらそのようなプラグインが見つかりました)

操作方法は以下の通りです。

  • カーソル位置より左に行きたい場合は<C-H>
  • 右に行きたい場合は<C-L> (本来<C-L>は画面を再描画するキーで、それを上書きしてしまいますが)
  • この2つを繰り返して、目的の位置にカーソルを近づける
  • <C-K>で状態をリセット
  • 行を移動すると状態がリセットされる

Vimで二分探索っぽくカーソルを移動する

 

JavaScriptに変換される新しい言語「Mican」を作りました!

この記事は altjs Advent Calendar 2012の8日目です。
今回は私が以前から作っていた、JavaScriptにコンパイルされるaltjsとなる新しい言語について紹介します。

言語の紹介

この言語は簡単に言うと、RubyPythonのいいところを取り入れた、JavaScriptの代わりに使える言語です。
今はまだ機能も少なく不安定な部分もありますが、これから少しずつ開発を進めていきたいと思います。

機能紹介

  • Pythonのようなインデント表記
def func(x):
  x + 1
  • JavaScriptのような中かっこを使った表記

上のプログラムは、この表記と同じ意味になります。

def func(x) {
  x + 1
}
  • Rubyのようなブロック付き呼び出し
map([1, 2, 3]): |a|
  console.log(a)

または

map([4, 5, 6]) {|a|
  console.log(a)
}

のようにブロック付きの関数呼び出しが使えます。
ただし、これはJavaScriptのaddEventListenerのようなメソッドに使えるようにするため、

map([1, 2, 3], fun(a) -> console.log(a))

という無名関数を最後に付けた呼び出しに変換されます。
ちなみにこれも

map([1, 2, 3], fun(a) { console.log(a) })

の別の表記です。

  • 可変長引数の簡単な表記
def func(a, b, *rest)
  console.log(a)
  console.log(b)
  console.log(rest)
func(1, 2, 3, 4, 5, 6, 7, 8, 9)

このように、最後の引数名の最初に*を付けると、その引数に配列として渡されます。
このプログラムは

1
2
[ 3, 4, 5, 6, 7, 8, 9 ]

という出力をします。

  • クラス
class Parent:
  def new():
    console.log("Constructor of Parent")
  def a():
    console.log("a")

class Child extends Parent:
  def new():
    super()
    console.log("Constructor of Child")
  def a():
    console.log("a of Child")

child = new Child()
child.a()

このプログラムでは、メソッドaを持ったParentクラスを作り、それを継承してコンストラクタとaをオーバーライドしたChildクラスを作っています。
JavaScriptはプロトタイプベースですが、よりクラスベースに近い表記を目指しました。

サンプルプログラム

いくつかサンプルプログラムを紹介します。

a = 0;
while a < 5:
  console.log("Loop! " + a.toString())
  a = a + 1

for b in [1, 2, 3, 4]:
  console.log(b)

ループにはwhileとfor inが使えますが、for inはJavaScriptとは逆に配列専用です。

array = filter([1,2,3,4,3,2,1]): |a|
  a > 2
console.log(array)

sum = reduce([1,2,3,4,5,6,7,8,9,10], 0): |s, number|
  s + number
console.log(sum)

配列の中の条件に合った要素を取り出すfilterや、Rubyではinjectとして有名なreduceが使えます。

ダウンロードなど

tana/mican · GitHub
GitHubで公開しています。
GitHubからzipファイルをダウンロードして展開、そして出てきたディレクトリにcdしてから

npm install . -g

でインストールできます。
これから安定して動作するようになればnpmで公開したいと思っています。

Sabayon Linux 10をインストールしてみる

Sabayonはどうだろう

私は最近、PCにインストールするLinuxディストリに迷っていました。
Archには一度はチャレンジしたものの設定が難しく断念、他のディストリも微妙だと思っていました。
そこである日、Sabayon Linuxについて調べてみたらこれがなかなか良さそうで。
早速LiveDVDを焼きました。
SabayonはGentooベースということですが、簡単にインストールでき、パッケージもバイナリになっています。
デフォルトのフォントはあまり綺麗ではなく、IMEがデフォルトでは入っていないことを除けば日本語も使えます。
今回は64bitのGNOME版をインストールしました。

ミラーの設定

パッケージのダウンロードを速くするため、最適なミラーサーバーを選びます。
Sabayonでは自動的に設定するコマンドがありました。
En:Entropy - Sabayon Wiki
このページに書かれているように

sudo equo repo mirrorsort sabayon-weekly

というコマンドを使いました。

インストール

Ubuntuなどのディストリと同じようにGUIのインストーラが使えます。
今回はWindowsとのデュアルブートを行うため、GRUBはディスク全体ではなくパーティションにインストールすることにしました。(これが後に混乱を招く)
インストールの手順は一般的な方法です。ただし、パーティションの設定が終わり「/dev/sdaにブートローダーをインストールする」といったような表示が出てきたところでインストール先を選択すれば、GRUBをパーティションの中にインストールすることができます。
ネットワークが接続されていない状況でもインストールすることができました。

ネットワークドライバ

今回インストールしたPCに搭載されているネットワークチップはAtherosの「AR8161」というチップで、標準では認識されませんでした。
これを使うためには、「alx」というドライバが必要になります。
しかし今回は幸い、USB接続の無線LANアダプタが接続しただけで認識されたため、それを使ってAR8161のドライバを用意します。
まずパッケージを最新版にしておき、念のためカーネルのソースの「Sabayon Sources」というパッケージをインストールしておきます。
パッケージのインストールには「Rigo Application Browser」というツールを使います。デスクトップにあるオレンジ色で矢印の描かれたアイコンです。
検索欄に「sabayon sources」と入力すれば検索結果が出てくるはずなので、それをインストールします。
次に、
alx | The Linux Foundation
このページからcompat-wireless-2012-05-10-p.tar.bz2をダウンロードし、展開します。
そしてページに書かれている通りに

./scripts/driver-select alx
make
sudo make install

でコンパイル、インストールします。
modprobe alxとすればネットワークに接続できます。

Cinnamon

GNOME 3に慣れないので、Windowsなどに似た操作方法のCinnamonというデスクトップ環境をインストールします。
これもRigo Application Browserでcinnamonと検索すれば一発で出てきます。
特にトラブルもなく使えます。

mikutter

Twitterは私の命綱。Twitterクライアントのmikutterをインストールします。
まずはRuby 1.9.3とRuby Gtk2、Ruby Pango、Rcairo、Httpclientをインストールしました。
そしてmikutterをダウンロードし展開、起動しました。
しかしこれではエラーが出てしまい起動できません。gtk2を読み込むあたりでPangoやCairoなどに関係がありそうなエラーです。
パッケージファイルを解凍して中身を調べたり、他ディストリのrcairoのパッケージのファイルリストと比較したりして対処法を決めました。
/usr/lib64/ruby/gems/1.9.1/gems/cairo-1.12.2/lib/ の中にあるディレクトリ「cairo」とファイル「cairo.rb」のシンボリックリンク
/usr/lib64/ruby/site_ruby/1.9.1/ の中に貼り、
ファイル「cairo.so」は/usr/lib64/ruby/site_ruby/1.9.1/x86_64-linux/ というディレクトリの中にシンボリックリンクを貼りました。
これでmikutterが起動します。

EasyBCDというツールを使い、WindowsのブートローダーからGRUBを起動、そこからLinuxを起動するという手順でのデュアルブートを行う予定でした。
しかし、GRUBがNo such partitionとエラーを出してしまい、grub rescueになってしまいます。
そして
GRUB rescueで九死に一生を得た had a narrow escape from death thanks for GRUB rescue - くだらぬみちくさにっき ---- To waste one’s time on the road might be good, I think.
ここを参考に
現在はここから復旧用のコマンドを使い起動しています。
しかし今のところこの問題は解決できていません。

if文をパースするときの混乱と解決法

はじめに

今、私はJavascriptにコンパイルされる新しい言語を作っています。
そこで、この言語のパーサをJavascript版のyaccのようなツール Jison (http://zaach.github.com/jison/ )を使って作っています。
このツールは基本的にyaccと似たようなものらしいのでyaccの解説を読みながら作っています。

現れた問題

この言語は最終的にはインデントを使ったPythonのような表記など、複雑なものになる予定ですが、
現在はシンプルなCやJavascriptのような「{}」を使った書き方になっています。
ところで、

if 1 {
  print(a + b + 10)
}
12

のようなソースコードをパースするときに問題が発生しました。
「}」の後には「else」が来るはずなのに数字が来るのはおかしい、といったような構文エラーが出てしまいます。
その理由は、定義ファイルで

| IF expr optnl '{' optnl optexprs '}'
    { $$ = ["if", $2, $6]; }
| IF expr optnl '{' optnl optexprs '}' ELSE optnl '{' optnl optexprs '}'
    { $$ = ["ifelse", $2, $6, $13]; }
| IF expr optnl '{' optnl optexprs '}' NEWLINE ELSE optnl '{' optnl optexprs '}'
    { $$ = ["ifelse", $2, $6, $13]; }

このような定義があったからです。「optnl」は「改行か何もないか」、「optexprs」は、「式の連続があるかないか」です。
そのため、「}」の後に改行を入れてしまったためelseにつながるのだと認識されてしまったのかこのエラーが出てしまいます。

解決

このエラーを解決するためには悩みましたが、結局「パーサではなくレクサ部分を変更する」という対処法を取りました。

"}"         return '}'

としてカッコが定義されているよりも上に

\}[ \t]*\n?[ \t]*else    return 'CLOSEELSE'

というように、閉じカッコとelseをまとめたトークンを作ってしまいます。
そして、if-elseの定義では閉じカッコとelseの部分をまとめたトークンを使うように変えておきます。
これで無事にパースできるようになりました。

drawableとrawの違い、謎の拡大

全ての始まり

Android端末のバッテリー情報や電波強度を遠隔で確認するアプリを作成している途中。
BitmapFactory.decodeResource(R.drawable.なんとか) を使って画像を読み込み、
その画像に文字や図形を描画しPNG画像として書きだすプログラムを作っていました。
しかし、何故か描画位置がずれます。しかし、画像を見てみるとこれは座標を2倍すれば正しい位置に表示されるのではないかと思いました。
案の定、座標の数字を全て2倍にしてみると正常に描画されました。
何故そんな現象が起こったのかはわかりませんでしたが、そのまま別の部分を作ることにしました。
その時の私は、後に謎の動作に悩まされることになるとは思ってもいなかったのです。

ブラウザの違い?

このアプリは、Android端末上にHTTPサーバーを立て、Webページとして端末状態を表示します。
そのため私は表示されるページのHTMLを書いていました。
それは思っていたよりも厳しい道となりました。思い通りに画面に表示させるCSSやHTMLを書くのは大変です。
ましてや、複数の端末、ブラウザに対応させるとなるとさらに面倒になります。
画像と文字を表示するHTMLがおおかた完成すると、実際の端末のブラウザで動作を確認しました。
まずは普段使用しているOpera Mobile。これは正常に動作します。
次に、標準ブラウザと同じエンジンを利用するAngel Browser。
widthを50%に指定していたものの、何故か大きな画像が表示され、画面の横幅に近くなってしまいます。
無論、画像の右には文字を表示するスペースなどありませんでした。
次に標準ブラウザ。長い起動時間を待ちページを読み込むと、Angel Browserと同じ結果となりました。
画像のサイズが大きくなるのは何が原因だったのでしょう。
私は考えました。まず、これはブラウザの違いによるものではないかと。
しかし、解決の仕方が思いつきません。
そこで私は、PCで表示し、画像のサイズを確認しました。
縦横160pxのはずの画像は、何故か縦横320pxに拡大されていました。
そこでふと私は、以前出会った描画がずれる問題を思い出しました。
2倍に拡大された画像、座標を2倍すると正しく描画される図形。
二つの事実がつながりました。
drawableリソースから画像を読み込んだ時点で、画像は2倍に拡大されていました。
drawableリソースについて検索し、
http://www.techdoctranslator.com/android/guide/resources/available-resources/drawable-resource
このページを読んでみると、drawableの画像は最適化されることがあるとのことです。
確認はできませんが、最適化の関係で画像が拡大された可能性もあります。

エピローグ

こうして私は謎の現象の原因に気づき、画像をdrawableリソースからrawリソースに変更しました。
rawリソースはopenRawResourceでInputStreamを取得し、BitmapFactory.decodeStreamで読み込みます。
無事、画像サイズは正しいサイズになりました。
しかし、私は別の問題が発生することに気づいていませんでした。
拡大されていたために描画する図形の座標を2倍にしていたため、描画される図形がずれてしまいます。
こうして私はプログラミングに戻ることにしました。

おわり