Haskellで書いたウェブサービスの習作です。ウェブサービス、習作ばっかりつくってる気がしてならない。

画像をぴったりサイズ指定して印刷する

コミケのサークルカットを印刷するのには毎回毎回苦労しています。申し込むためには、このサークルカットを4cm x 5.7cmに印刷して所定の用紙に貼り付けて申し込む必要がありますが、そのサイズを指定して印刷するのが結構めんどくさい。

プリンタへUSBで接続したプリンタへ、直接印刷できるときはGIMPを使えばサイズを指定して印刷できます。しかし、コンビニのプリンタなどのプリンタの場合はそのような指定を行う事が全くできません。画像を印刷すると固定の解像度で出力されたり、拡大されて出力されたり…。この問題を解決しない限りコミケに申し込むのが億劫なので、いい加減システムで解決することにしました。

このサービスを使うと、画像を指定したサイズに印刷するためのpdfを生成してくれます。このpdfを共用プリンタで「等倍指定」で印刷すると、ちょうどぴったりのサイズで印刷してくれます。少なくともセブンイレブンの印刷機ではうまくいくのを確かめました。

コミケの締め切り（8/20）までに公開できれば一番よかったのですが、結局間に合わなくてネットワーク申し込みにしたので、わたし自身には結局必要なくなってしまいましたｗ

せっかくなのでHaskellで書いた

やってる事自体は「証明写真作成工房」と全く同じことなので、今回は言語を変えてHaskellで書いてみました。意外とIOモナドは辛くないですね…！！

また翻訳です！

• Efficient float32 arithmetic in JavaScript

---

コンピュータ上で浮動小数点を表現する方法はいくつか存在する。だいたいのアーキテクチャではIEEE754標準を使っている。この標準では、倍精度浮動小数点(a.k.a. double or float64)を64bitで表し、単精度浮動小数点(a.k.a. float or float32)を32bitで表している。名前が示す通り、float64はfloat32よりもっと正確なんだ。だからパフォーマンスがあんまり重要視されないときは大体こっちを使おうねってアドバイスされる。

でもね、float32を使うことにもこんな利点がある：

• float32は計算操作をするのにfloat64よりCPUサイクルがしばしば少ない。精度が低いからだ。
• float64の計算をfloat32に対して行うには、いくらかオーバーヘッドが存在する。なぜなら、一旦float64に変換しないといけないから。これは、Float32arrayを使ってデータを格納しているときにしばしば発生する。WebGLを使ったコードや、EmscriptenでコンパイルされてC++のfloatがfloat32として格納されいるけど計算はJavaScriptのfloat64として行っている場合ではよくあることだ。
• float32は半分のメモリしか使わない。プログラムのメモリ総使用量を減らすし、メモリーがボトルネックになるような（memory-bound)計算では速度も速くなるだろう。
• float32に特化した標準C関数は、我々の調査したいくつかのライブラリではfloat64のバージョンより速かった。

JavaScriptにおいて、Number値はfloat64として定義されていて、すべての計算もfloat64として行うことが定義されている。さて、JS処理系がいままで長い間高速化のために利用していたfloat64の特性が、float64の値が十分小さい整数のとき、float64での計算結果は整数での計算結果と全くおなじ、ということだ（桁溢れが発生しなければ！）。JS処理系は、この特性を、整数の値を（floatでなく）生の整数として保持しておいて、整数演算で計算することで（そして桁溢れをチェックすることで）利用してきた。実際、次の少なくとも３種類の表現が実際に使われている：31bit整数、int32_t、uint32_t（くわしくはAndy Wingoの書いたこの値の表現に関する記事を見てみてね！）。

これらを全部踏まえると、一ついい感じの疑問が湧いてくる：似たような事を、float32で出来ないかな！？

答えは「しばしば可能」で、ES6で追加される新しいMath.fround関数を使うとプログラマ側がいつfloat32演算を使うかをコントロールすることが出来る。

いつ安全にfloat64演算の代わりにfloat32演算が使える？

Samuel A. Figueroaが“When is double rounding innocuous?” (SIGNUM Newsl. 30, 3, July 1995, 21-26)で書いているんだけど、float32とfloat64で交換がなりたつ恒等式がいくつかある。入力がfloat32であるかぎり、float32での演算とfloat64での演算、どちらを使ってもよくて、同じ結果を得られるんだ。もっと正確に言うなら、{+,-,*,/}のそれぞれの演算について、float32版の演算を行う関数であるop_f32と、float64版の演算を行う関数であるop_f64があったとすると、次の恒等式が成り立つんだ。C++で表現すると、こんな感じ：

  float op_f32(float x, float y);
  double op_f32(double x, double y);
  assert(op_f32(x,y) == (float) op_f64( (double)x, (double)y ));

似たような恒等式が、sqrtとかその他の数学関数のような単項演算にも成り立つ。

ただし、この性質は、それぞれの演算の前後でfloat32にcastした場合に成り立っている。たとえば、x=1024でy=0.0001で、さらにz=1024であるときに、(x+y)+zはfloat32の二回の足し算として見た時とfloat64の二回の足し算とみた場合では、もはや同じ結果にはならない。

この恒等式は、コンパイラがfloat64の演算のかわりにfloat32の演算を使って最適化を行うための、前提条件を与える。実際に、gccはこの恒等式を利用していて、さっきの恒等式の右辺のような式（float64のコード）があったら、左辺のような式（float32の式）を生成する。

でも、いつJavaScriptはfloat32の値を持ちうるんだろう？WebGLとそれに付随するTypedArray APIが使えるHTML5では、答えはこうなる：Float32Arrayから読む時と、書く時、だ。

たとえば、このコードを見てみよう：

  var f32 = new Float32Array(1000);
  for(var i = 0; i < 1000; ++i)
    f32[i] = f32[i] + 1;

ループの中の足し算のコードは、たしかにさっきの恒等式と一致してる：f32配列からfloat32の値を持ってきて、float641に変換され、float64同士の足し算演算が行われ、そしてf32に書き戻すためにfloat32に再度キャストされる。（足している”1″というリテラルも、float32からfloat64にキャストしていると考えた。なぜなら、float32で1は正確に表現できるからだ）

でも、もっと複雑な式を書きたいときはどうしよう？不要なFloat32Arrayへの出し入れを式のそれぞれの式の一部分に追加して、計算した式の一部分の結果がつねにfloat32にキャストされるようにすることも出来る。でも、これらの追加の（不要な）出し入れはプログラムを遅くするし、我々の目標はプログラムを速くすることなので、それでは意味がない。

うん、十分に頭のいいコンパイラーさんなら確かに不要なこの手の出し入れを除去することができる。でも、性能の予測可能性は重要だから、もっとこの最適化が行われることを確実にしたい。かわりに、わたしたちは小さな組み込み関数を提案し、Ecma Script 6規格で取り入れられた：Math.froundだ。

Math.fround

Math.froundは来るべきES6標準で提案されている、新しい数学関数だ。この関数は入力された値をいちばん近いfloat32の値にまるめて、そのfloat32をNumber値として返す。つまり、Math.froundは意味としては2つぎのplyfill3と同値だ：

 

  if (!Math.fround) {
    Math.fround = (function() {
      var temp = new Float32Array(1);
      return function fround(x) {
        temp[0] = +x;
        return temp[0];
      }
    })();
  }

いくつかのブラウザではTypedArraysに対応していないけど、そういう時はまた別の複雑なpolyfillがあるよ。でも、TypedArraysを使わなくても、SpiderMonkey(FirefoxのJSエンジン）とJavaScriptCore(SafariのJSエンジン）の両方ですでにMath.froundが実装されているよ。V8(ChromeのJSエンジン）でも実装する計画があって、このissueでその状況が確認できる（訳注　すでに実装されてるっぽい）。

結果として、float32の演算として演算を行い続けるには、単に途中の結果をMath.froundで包めばいい：

  var f32 = new Float32Array(1000);
  for(var i = 0; i < 999; ++i)
    f32[i] = Math.fround(f32[i] + f32[i+1]) + 1;

プログラマに速いコードを書くのを許すだけではなく、EmscriptenみたいなJSコンパイラにも、float32のコードをよりbetterにすることを許す。たとえば、Emscriptenは現在C++のfloat演算をJSのNumberを用いたコードにコンパイルする。技術的には、Emscriptenは原理的にはFloat32Arrayへの出し入れを全ての演算ごとに行うことで余計なfloat64精度を取り除くことは出来るけど、とても遅くなってしまうだろう。だから、忠実性はパフォーマンスのために犠牲にされた。

この違いが何かを壊すことは非常にレアなんだけど（もし壊れてしまうなら、そのプログラムは「未定義動作」に依存してるということだ）、この違いがバグを起こした所を実際に見たことがあって、しかもそういうバグを追跡するのは全く楽しくない。Math.froundを使えば、Emscriptenはもっと効率的で、もっと元のC++コードに忠実なコードを生成できるんだ！

Float32 in IonMonkey

わたしのインターンシップでのプロジェクトは、Firefoxにこれらの最適化を組み込むことだった。まず最初のステップとして、一般的なFloat32の演算のサポートをIonMonkey JITバックエンドに追加した。つぎに、Math.froundを一般的な（最適化されていない）ビルトインとしてJavaScriptエンジンに追加した。最後に、Float32Array/Math.froundを使っているのを認識してfloat32演算を出来る限り使うように最適化する最適化パスをコンパイラに追加した。これらの最適化は、Firefox27から使うことが出来る（今はAuroraリリースチャンネルに入ってるよ→訳注　もうStableでもVersion30ですね）

で、どれくらい早くなるんだろう？ちいさなベンチマークでは（C++とJavaScript両方で）、50%くらいの大きなスピードアップを示した。でもこういうちいさなベンチマークはしばしばミスリーディングを引き起こすから、わたしは次のようなもっと現実的なベンチマークを書いて、float32の大量の演算がどれくらい速くなるか、実際にありそうな問題で調べた：

• 逆行列計算：このベンチマークでは、いくつか行列を作って、その逆行列を計算し、float64とfloat32でどれくらい精度が失われるかを比べるために、もとの行列と掛け算した。このベンチマークには、gl-matrixの改造したバージョンを利用した。gl-matrixは、WebGLの行列計算を使ったフレームワークで、実世界のアプリケーションでも使われている。float32バージョンを作るためには、Math.froundの呼び出しだけを追加した。
• 画像処理行列計算：このベンチマークでも行列をいくつか生成して、画像処理でよく使われる行列の計算を行う。移動・回転・スケーリング、などなど。このベンチではたくさんの基本操作や複雑な操作（例えばMath.cosやMath.sinを回転操作で呼び出す）をおこなう。で、　float32の演算を最適化したとき、このベンチではすごい改善が見られた。このベンチマークも、gl-matrixの改造したバージョンを使っている。
• 指数関数：このベンチマークでは、大きなFloat32Arrayを予測可能な値で埋めて、つぎにそれぞれの要素の指数関数を、テイラー展開をつかって求めた。このベンチマークの主な目的は、足し算と掛け算の重さを測ることだ。
• 高速離散フーリエ変換：このベンチマークでは、適当なニセのバッファを作って、高速離散フーリエ変換（FFT）を行った。このベンチマークには、他にも基本操作と数回のMath.sqrtへの呼び出しが含まれている。FFTのコードは、既存のライブラリ、dsp.jsから取ってきた。

次の表が違うデバイスで最新のFirefox Nightlyを実行したときの結果を示している。それぞれの数値が、Math.froundの呼び出しを追加してfloat32最適化を許すことで得られたスピードアップを示している（だから、高大きい方がより良いことを示している）。

使っているデスクトップマシンは、「ThinkPad Lenovo W530 (Intel(R) Core(TM) i7-3820QM CPU @ 2.70GHz, 8 cores, 16 GB RAM)」だ。電話もしくはタブレットと書いてあるときは、Firefox NightlyのAndroidバージョンの事をしめしている。

この結果をひと目みたら、自分でもベンチマークを取ってみたいって思うんじゃない？ここで自分で実行できるよ！（あ、でも忘れないで。Firefox 27かそれ以降を使うんだ）

ベンチマークのソースコードはgithubで見れるよ（gh-pagesブランチにある）

Device	Matrix Inversions	Matrix Graphics	Exponential	FFT
Desktop (x86)	33%	60%	30%	16%
Google Nexus 10 (ARM)	12%	38%	33%	25%
Google Nexus 4 (ARM)	42%	26%	38%	5%
Samsung Galaxy S3 (ARM)	38%	38%	24%	33%

Polyfilling Math.fround

すべてのJSエンジンでMath.froundが使えて最適化されるようになるまで、どうすればいいんだろう？上で紹介した忠実な方法ではなくて、こんな単純な恒等関数を使えばいい：

  var fround = Math.fround || function(x) { return x }

これがさっきのベンチマークが使っていて、かつ、上で示したように、殆どのコードで4違いをうまない。

すべてのモダンなJS処理系はだいたい小さな関数をハイエンドなJITでインライン化するので、このplyfillはパフォーマンス上のペナルティになることはない。それを確かめるために、例えばChromeの開発版で実行することもできる。しかしながら、いくつかの巨大なソースコードではインライン化が実行されず、plyfillのせいでパフォーマンスが悪くなったこともあった（たぶん、インライン化の深さ制限か、関数が何かしらの理由でJITコンパイルされなかったんだろう）。

まぁ簡単に言うと、「試してみる価値はある。そしてテストしよう」。

結論

結果は私達を元気づけてくれるものだった。Math.froundはES6の標準にはいるから、ほかのJS処理系も同じ最適化を行うようになってくれることが期待される。Webをゲームプラットフォームにしたいという観点からすると、低レイヤの今回のような最適化はより重要性を増してきていて、Webをよりネイティブ性能に近づけてくれると言えるだろう。ぜひFirefoxのNightlyかAurolaでこの最適化をテストして、何かバグを見つけたらぜひ教えてね5。

今回のことに参加してくれたすべての人に感謝したい：Jon CoppeardとDouglas CrosherにはARMバージョンを実装してくれたことを、Luke Wagner、 Alon ZakaiとDave Herman には校正とフィードバックを、そして、JavaScriptチームのみんなにヘルプとサポートを。

---

 感想

JSの最適化もここまで来たかーって感じがします。今後はこういう「プログラマと処理系が手を組んで行う最適化」が増えてくるのでしょうかね。そういう最適化はたぶんまだ沢山できて効果がありそうな一方、プログラムを書いている人が知ってるか知ってないかでかなり速度が変わってくるわけで、JSを書くのがどんどん大変になっていきそうな…。やっぱJSはアセンブリなんや…（何）。

1. 訳注 JavaScriptのNumberはfloat64と定義されているのでした [↩]
2. 訳註　速度を除いて [↩]
3. なんとWeb時代に生まれた単語で、古いブラウザで新しいブラウザと同じ機能を提供するための方法のこと [↩]
4. 訳註 一度他の関数に代入することによる？ [↩]
5. 訳註 もう30なので、製品版コードに入っています [↩]

土曜日に、ドワンゴC++勉強会 #1に行って発表してきましたっ！

[全画面/表示されない場合]

この記事は、

Resolving ELF Relocation Name / Symbols

の翻訳です。認めてくれたLeaf SRの人ありがとう！訳はがんばりましたが、間違ってる所もあるかもしれません。そこはご了承ください…。

---

共有オブジェクトのELFファイル内関数へのcall命令（たとえば、puts関数の呼び出しとか）は、直接関数のアドレスへ飛ぶのではなくて、PLT（Procedure Linkage Table）に飛ぶよ。PLTを使うと、関数の実際のアドレスを実行時に解決することができる。言い換えると、共有オブジェクトが実際にどこにロードされるかは実行時にならないと分からないので、PLTを使って実際のアドレスを解決している。

次のELFのサンプルを見てみよう：

ここに、ELFのテキスト・セグメント1内にある、アドレス0x804833cへの呼び出し命令がある：

$ objdump -d example-elf | grep 804833c | grep call

804843f: e8 f8 fe ff ff call 804833c

それで、次がこのサンプルファイルのPLTだ。さっきの命令で呼んでたアドレス0x804833cに注意してね。ここには実際には単なる*0x8049684へのジャンプ命令が並んでいる。

$ objdump -d example-elf | grep “section .plt:” -A 31

Disassembly of section .plt:

080482fc <__gmon_start__@plt-0x10>:
80482fc:       ff 35 70 96 04 08       pushl  0x8049670
8048302:       ff 25 74 96 04 08       jmp    *0x8049674
8048308:       00 00                   add    %al,(%eax)
     ...

0804830c <__gmon_start__@plt>:
804830c:       ff 25 78 96 04 08       jmp    *0x8049678
8048312:       68 00 00 00 00          push   $0x0
8048317:       e9 e0 ff ff ff          jmp    80482fc <_init+0x18>

0804831c <__libc_start_main@plt>:
804831c:       ff 25 7c 96 04 08       jmp    *0x804967c
8048322:       68 08 00 00 00          push   $0x8
8048327:       e9 d0 ff ff ff          jmp    80482fc <_init+0x18>

0804832c <__stack_chk_fail@plt>:
804832c:       ff 25 80 96 04 08       jmp    *0x8049680
8048332:       68 10 00 00 00          push   $0x10
8048337:       e9 c0 ff ff ff          jmp    80482fc <_init+0x18>

0804833c :
804833c:       ff 25 84 96 04 08       jmp    *0x8049684
8048342:       68 18 00 00 00          push   $0x18
8048347:       e9 b0 ff ff ff          jmp    80482fc <_init+0x18>

0804834c :
804834c:       ff 25 88 96 04 08       jmp    *0x8049688
8048352:       68 20 00 00 00          push   $0x20
8048357:       e9 a0 ff ff ff          jmp    80482fc <_init+0x18>

（注意：*は、C言語のポインタ参照と同じで、0x8049684に書いてある値、の意味）

*0x8049684が実際には何なのかを知りたければ、Global Offset Table (GOT)を探せばいい。こんな感じだ：

$ objdump -s example-elf | grep got.plt -A3

Contents of section .got.plt:
804966c 98950408 00000000 00000000 12830408  ................
804967c 22830408 32830408 42830408 52830408  "...2...B...R..

0x8049684には、42830408（リトルエンディアンで0x08048342）が書いてあった。ここでPLTに戻ってもう一回0x08048342を見てみると、jmp 命令でこのアドレスに飛んだあと、”push $0x18″という命令を実行することが分かる。0x18=24っていうのは、再配置テーブルへのオフセットアドレスだ。このpush命令に続いて、PLTの最初のアドレスへのジャンプである、”jmp 80482fc”が実行される。

この80482fcに書いてある命令列は、PLTの他の部分と大分ちがっているのはすぐ分かるだろう。最初の2つの命令、”pushl 0x8049670″と”jmp *0x8049674″は結構重要だ。

最初push命令はアドレス0x8049670をスタックにpushしていて、これはGOTを指している。次の(*0x8049674)へのジャンプだけど、このアドレスもGOT内のアドレスだ。この2つのアドレスは、ELFファイルの中ではどちらも”0″が書いてある。

というのも、これらは実行時に動的に埋められるからだ。実行時には、最初のアドレスの値は特定のライブラリが使われているかを識別するための番号になり、次のアドレスにはリンカーのシンボル解決ルーチンのアドレスが入る。これらのルーチンは前にスタックにpushされた0x18を、正しい場所を解決するために使う。

このテクニックは「遅延リンク（lazy linking）」と呼ばれている。再配置された関数のアドレス解決が、実行時に、しかも必要な時に、実際に関数が呼ばれた時だけ行われるからだ。

一度リンカーによって解決されると、リンカーはGOTエントリを書き換えて、最初の jmp *(アドレス)が、それまでのpush $0x18をするコードのアドレスではなく、解決された関数アドレスに直接ジャンプするようになる。

それじゃあ、どうやって関数のアドレスを解決するためのシンボル名を取ってくるんだろう？関数のアドレスを解決するには、’0x8049688’ではなくて、’sprintf’という文字列が必要だ。

SHT_RELというタイプを持っているセクションには、次のような構造体が並んでいる：

 typedef struct
 {
      Elf32_Addr r_offset;    /* Address */
      Elf32_Word r_info;    /* Relocation type and symbol index */
 } Elf32_Rel;

さて、readelfでELFファイル内の再配置エントリを見てみよう2。

$ readelf -r /testbins/sha1

 Relocation section '.rel.dyn' at offset 0x420 contains 3 entries:
 Offset     Info    Type            Sym.Value  Sym. Name
 0804b54c  00001106 R_386_GLOB_DAT    00000000   __gmon_start__
 0804b598  00000505 R_386_COPY        0804b598   stderr
 0804b59c  00000d05 R_386_COPY        0804b59c   stdin

 Relocation section '.rel.plt' at offset 0x438 contains 2 entries:
 Offset     Info    Type            Sym.Value  Sym. Name
 0804b55c  00000107 R_386_JUMP_SLOT   00000000   feof
 0804b560  00000207 R_386_JUMP_SLOT   00000000   putchar

これらの情報はいったい何処から来たんだろう！？Offset/Info/Type/Value/Nameのそれぞれの情報、さっきの構造体に無かったよね？えっとね、これらの値のうち、殆どは実はr_infoフィールドから直接もってこれるか、r_infoフィールドを間接的に使うともってこれるんだ。

offsetの値はPLTの中を指していて、ここに再配置エントリの実体が置かれる。バイナリを逆アセンブルすると、PLTの中の正しいオフセットにある、このアドレスへjmpする命令が見えるはずだ。

今注目したいのは、r_infoフィールドだ。このフィールドに関係する、２つの（ほんとの事をいうと3つあって、3つ目は1と2を組み合わせると得られる）重要なマクロがelf.hに存在する：

#define ELF32_R_SYM(val) ( (val) >> 8)
#define ELF32_R_TYPE(val) ( (val) & 0xff)

これらのマクロはr_infoからそれぞれ別の値を得るためのマクロだ。いっこずつ見てみよう。SHT_RELタイプをもつセクション（さっきからみてる、再配置セクション）は他にsh_linkっていうメンバを持っている。このsh_linkは重要で、これらの再配置情報のシンボル情報（関数名とかね）を持つ、ほかのセクションを指しているんだ。このsh_linkは、gccでは大抵「dynsym」というセクションを指している。

/bin/lsのdynsymを実際に呼んでみた結果がこれ（読みやすくするために、いくつか省略してるよ）：

$ readelf -S /bin/ls

   There are 26 section headers, starting at offset 0x126d8:

 Section Headers:
 [Nr] Name Type Addr Off Size ES Flg Lk Inf Al
 ...
 [ 4] .dynsym DYNSYM 080484a0 0004a0 0006b0 10 A 5 1 4
 ...
 [ 8] .rel.dyn REL 08049170 001170 000028 08 A 4 0 4
 [ 9] .rel.plt REL 08049198 001198 0002f0 08 A 4 11 4
 ...

セクション7と8のsh_linkメンバを見て。それぞれの4が、dynsym(dynamic symbol table)セクションを指している。この第4セクションが、再配置エントリに対応するシンボルネームが書いてあるセクションだ。ここまでやってきたことをまとめておくと、（１）SHT_RELタイプがついてるセクションを探して、（２）sh_linkメンバーの指し示すセクションをたどった。

よし、色々数字があるのは分かったから、あとはそれをどう組み合わせていけばいいんだろう。再配置テーブルのエントリを一個一個見ていって、r_infoフィールドの値を持ってきて、ELF32_R_SYM(val)マクロを使って値を取り出していけばいい。この数字はdynsymセクション（か、sh_linkの指している他のセクション）内のエントリに対応している。で、dynsymテーブルをパースしてエントリを調べれば、シンボルネームが解決できる。

他のマクロは何なんだろう？ELF32_R_TYPE(val)は再配置がどんなタイプなのかを教えてくれる。その値はelf.hにR_386_GOT32とかR_386_JMP_SLOTみたいなのが定義されている。この定義を使うと、再配置テーブルが関数のためのエントリなのかどうかとかが分かる（でも、rel.pltセクションの中のはだいたいそうだ3）。

ただし、ちょっと注意。全てのELFファイルがセクションヘッダを持っているわけじゃない。そういう時は、プログラムヘッダを使うと、動的なセグメントがどこかわかるし、再配置テーブルのアドレスとか、再配置テーブルのシンボルテーブルがどこかとかが分かる。

もしこのエントリに間違いがあったらぜひ教えてね！

1. 訳注：テキストセグメントにはプログラムのコード本体が置かれている [↩]
2. 訳註：これから読むELFは、さっきまでのとは違うELFファイルだから、PLTのアドレスとかは違う [↩]
3. 訳註：PLTはProcedure Linkage Tableの略なのです [↩]

今日はbashと基本的なシェルコマンドだけで3Dレンダリング（ワイヤフレーム）をしてみました！

Github: ledyba / Bash3D

bashプログラミングテクニック

今回つかったbashのプログラミングテクニックについて、記録のついでに少しまとめます。シェルスクリプトの基本的な所は書きません。

あと、3Dプログラミングに関しては本に書いてある事以上のことが書けそうにないので、（今は）書きません。

bashのデータ構造

bashでそこそこ本格的にプログラミングする事を考えた上でまっさきに「辛そう…」ってなるのはデータ構造ですよね！今回のソフトでは、ベクトルや行列を綺麗に扱えないと困ってしまうでしょう。まずはそこを見ます。

bashの「値」は基本的に全てただの文字列ですが、「リスト構造」にだけはネイティブで対応しています。こんな感じ。

$ lst=(1 2 3)
$ echo ${lst[0]}
1
$ echo ${lst[1]}
2
$ echo ${lst[2]}
3
$ echo ${lst[3]}
#空行

データにアクセスする時に、必ず${}でくくらないといけないのが少し面倒です。ちなみに添字を付けないとリスト全体…と思いたいところですが、最初の要素が出てきます。

$ echo $lst
1

全体を表示するには、${lst[@]}とします。

$ echo ${lst[@]}
1 2 3

リストを定義するときに使ったカッコが出てこないので、リストをコピーしたい場合はそのカッコを補わないといけません。

$ lst2=(${lst[@]})
$ echo ${lst2[@]}
1 2 3

慣れればなんとかなるレベルですが、面倒です。

さらに気を付けないといけないのは、”(1 2 3)”という文字列を返す関数を$(command)で受けて変数に代入してもリストになりません。

$ function fun() { echo \(1 2 3\); }
$ lst=$(fun)
$ echo $lst
(1 2 3)

ただの文字列として代入されます。どうしてもしたい場合は、evalを使わないといけません。

#文字列展開が起こってから実行されるので、lst=(1 2 3)というコマンドが実行されることになる
$ eval "lst=$(fun)"
$ echo ${lst[1]}
2
$ echo ${lst[@]}
1 2 3

通常の用途ならそれで済むのですが、今回は出来る限り高速に処理したいので、こうやってコマンドが沢山必要になるのは避けたいところです。

ところで。

後に言うダイナミックスコープとevalを組み合わせると連想配列みたいなことも出来るのですが、今回のプログラムでは基本的にこのリストでデータ構造を管理しています。

インデックスを指定したアクセスをするためにコストが高いevalを行わなくてよいこと、ベクトルと行列が主役なのでリストで十分な事が理由です。

$ matrix=(MAT 1 0 0 0 0 1 .....)
$ vector=(VEC 0 0 0 1)

最初の要素に型の名前を入れて適宜assertすることで、動的型検査みたいなことをしています。

変数のスコープ

名前空間は基本的にひとつしかありません。関数のネストは一切関係なく上書きされていきます。

$ val=0
$ function fun() { val=1; }
$ fun
$ echo $val
1 #関数内の代入だが、グローバル領域が上書きされてしまった
$ function fun2() { val2=2;echo $val2; }
$ fun2
2
$ echo $val2
2　#オフサイドルールではなく、存在しない変数はグローバルに作られるみたい

一種のダイナミックスコープみたいなものだと理解しておけば大体書けます。

呼び出し元の変数がうっかり書き換えられてしまう可能性があるのですごく不便ですが、逆に利用することも出来ます。

「関数の引数に変数名を渡すと、evalと組み合わせることで指定した変数に結果を格納する関数」が作れます。こんな感じ：

$function setOne() { eval "$1=1"; }
$ setOne val1
$ echo $val1
1
$ setOne val2
$ echo $val2
1

これを使って「最初の引数は入力、最後の引数は出力」と規約を決めて関数を設計しています。たとえば行列の計算はこちらにあります。見た目がアセンブラみたいになりますネ。

「こんなスコープ再帰が出来ないのでは？」という気がしますが、案外なんとかなります。というのも、$(command)はサブシェルとかいうので実行されるらしくて、さらにサブシェルは別の変数空間で動作するようです。つまり、このスコープの問題は起こりません。…たぶん。よく分からない(◞‸◟ )

 #再帰関数といえば階乗である
function kaijo() {
    arg=$1
    next=$(expr $arg - 1)
    if [ $arg -gt 1 ]; then
        result=`kaijo $next`
        echo $(expr $arg \* $result)
    else
        echo 1
    fi
}

kaijo 10 --> 3628800

ついでにevalとこのスコープの仕様を使うと、擬似的な連想配列を作れますが、値のコピーが難しいこともあって使いませんでした。

$ val_key1=123
$ val_key2=456
$ function showKey1() { echo $(eval "echo \$$1_key1"); };
$ showKey1 val
123

固定小数点とexprコマンド

シェルスクリプトで計算をするには、exprコマンドを使う必要があります。このコマンドは整数の計算にしか対応していません。

$ expr 1 \* 2 \* 3
6
$ expr 1 \* 2 \* 3.2
expr: non-numeric argument

3Dソフトでそれでは困るので、整数だけで小数を計算します。それにはどうするかというと、扱う小数を適当に1000倍とかして、それを小数に見立てます。つまり、1000は１、1001は1.001、3140は3.140だと思うことにします。その場合、計算する時にちょっとした手間が必要になります。

#3.14 + 3.14
$ expr 3140 + 3140 #足し算・引き算はそのまま足し算で大丈夫です。
6280
#3.14 / 3.14
$ expr 3140 \* 1000 / 3140 #割り算するときは、倍率で掛けてから割ります。この世界では「1.0」は1000であることに注意
1000
#3.14 * 3.14
$ expr 3140 \* 3140 / 1000 #掛け算するときは、掛け算してから倍率で割ります。
9859

倍率を1000じゃなくてもっと高くすれば、もっと小数演算の結果が正確になります。

私の環境だけかもしれませんが、exprはどんな大きな数でもちゃんと扱ってくれるようなので、ガンガン倍率を上げていけば誤差がまったく気にならなくなります。これはすごい楽…（楽すぎた）

なお、sin/cosは（テイラー展開を自分で展開しない限り）計算できないようだったので、0～360度について事前に求めておいて、これを先ほどのリスト構造にいれて使っています。平方根も使いたかったんですが、どうやっても無理そうなので諦めました。

表示：オフスクリーンレンダリング

もちろんターミナルにはピクセルがないので、ターミナル上に表示する文字で代用します。普通に表示するなら、tput cup (line) (col)を使うとターミナル上の任意の位置に移動できるので、これを使いたいところです。

# 斜め45度に線を引いてみた
for;do
    for;do
        tput cup y x
        echo -n \*
    done
done

が、この方法では線を引く様子が目で分かるぐらい時間がかかります。これで最初レンダリングしたみたのですが、レンダリング中に線を引いている様子がバッチリ見えてしまい、あんまり回転アニメーションしてるように見えませんでした。

ほんもののゲームでもそういう、更新途中の絵が表示されてしまってちらつく問題があります。ほんもののゲームでは、そういう時は、書いてもすぐには表示されない「裏の画面」を用意しておいて、そちらに時間を掛けてレンダリングして、最後に表示される「表の画面」と入れ替える「オフスクリーンレンダリング」と「ダブルバッファリング」をしているのでした。私も同様にそのテクニックを使いました。

具体的には、こんな感じ。

SCR_BUFF=$(head -c $size < /dev/zero | tr '\0' '_')

今回の「ピクセル」は文字ですから、「裏の画面」はただの文字列になります。
画面のサイズを取得しておいて、そのサイズ分何もない文字列を意味する「_」をtrを使って入れておきます。空白でいいじゃないかと思うかもしれませんが、シェルスクリプトでは空白はかなり重要な意味を持っていて面倒なのでこうしています。

「ドットを打つ」時は、対応する文字列中のインデックスの文字を*に書き換えます。

SCR_BUFF=$(echo $SCR_BUFF | sed s/./*/<置き換える文字の位置>)

zshだとstr[12]=\*ってやると文字列を更新できるのですが、bashでは使えなかったので、sedを使って書き換えています。この処理が非常に重く、今回のレンダリングエンジン（？）の処理時間の殆どはこのドットを打つ処理に費やされています。上手い方法を知ってたら教えてください！

最後に表の画面に更新する方法ですが、単純にechoするだけです。この時、何も入っていない所には_が入っていたので、空白に直します。

$ tput cup 0 0
$ echo -n $SCR_BUFF | tr '_' ' '

ちゃんと幅に合わせて改行されるので、うまく表示できます。

高速化

インライン展開　→　プロセスforkを抑える

当初綺麗に関数を使って書いた所、行列の掛け算に１秒近く掛かってしまい、さすがにレンダリングは出来ないのかな…と諦めかけたのですが、行列やベクトルの掛け算や足し算を全てインライン展開したところ、座標計算に関しては十二分すぎる程の速度が出せるようになりました。前述した通り、今回遅いのはオフスクリーンにピクセル（文字）を書き込む処理が異常に時間が掛かっているからです。

やはりプロセスの起動はものすごい重い処理のようで、可読性をそこまで損なわない範囲でプロセスの呼び出しを一箇所にまとめています。

感想

線を引くのにえげつない時間が掛かるのを見た時、初めて触ったBASICの処理系を思い出しました。懐かしい。

ところで、なんで3Dライブラリを作るとOpenGL風の名前にしちゃうんだろ。

ニコ動に「次はシェーディングだな！」というコメントがついているのですが、テクスチャの表示をやってみたいです！７色くらいしか使えないので、たいへんそう…。影は「暗い色」が基本的に無いのでかなりつらい気がします。

1. x=0;x<10;++x [↩]
2. y=0;y<10;++y [↩]