hello, world * 6
https://codeiq.jp/ace/nabetani_takenori/q766
を見て、おおこれは面白い問題だーと思ってチャレンジしました。とはいえ 3 言語で重複無しとか、文字種制限経験者には楽勝なんで、 6 言語になりました。第一感では 5 言語くらいはいけるだろーと思って、後で Forth が追加できたんで 6 になったっていう。
Groovy 953B 文字種6 "$-o{}
"${--"${--"${--"${--"${--"${--"${--"${--"${--"${--"${--"{"}"}"}"}"}"}"}"}"}"}"}${--"${--"${--"${--"${--"${--"${--"${--"${--"{"}"}"}"}"}"}"}"}"}${--"${--"${--"${--"${--"${--"o"}"}"}"}"}"}${--"o"}${--"${--"${--"${--"${--"${--"${--"{"}"}"}"}"}"}"}""${--"${--"${--"${--"${--"${--"${--"o"}"}"}"}"}"}"}${--"${--"${--"${--"${--"${--"${--"${--"${--"${--"o"}"}"}"}"}"}"}"}"}"}${--"${--"${--"o"}"}"}${--"${--"${--"o"}"}"}o${--"-"}${--"${--"${--"${--"${--"${--"${--"${--"${--"${--"${--"${--"${--"-"}"}"}"}"}"}"}"}"}"}"}"}"}${--"${--"${--"${--"{"}"}"}"}o${--"${--"${--"${--"${--"${--"${--"${--"${--"{"}"}"}"}"}"}"}"}"}${--"${--"${--"o"}"}"}${--"${--"${--"${--"${--"${--"${--"${--"${--"${--"${--"o"}"}"}"}"}"}"}"}"}"}"}${--"${--"${--"${--"${--"${--"${--"${--"${--"${--"${--"${--"${--"${--"${--"${--"${--"${--"${--"${--"${--"${--"${--"${--"${--"${--"${--"${--"${--"${--"${--"${--"${--"${--"${--"-"}"}"}"}"}"}"}"}"}"}"}"}"}"}"}"}"}"}"}"}"}"}"}"}"}"}"}"}"}"}"}"}"}"}"}"
JavaScript(spidermonkey) 971B 文字種11 !'()+;=[\]_
_=!'';__=_+_+_;___=(''+''['']);([][(''+!_)[+'']+___[__+_+_]+(''+!_)[_+_]+(''+_)[+'']+(''+_)[__]+(''+_)[+_]][(''+[][(''+!_)[+'']+___[__+_+_]+(''+!_)[_+_]+(''+_)[+'']+(''+_)[__]+(''+_)[+_]])[__]+(_+[][(''+!_)[+'']+___[__+_+_]+(''+!_)[_+_]+(''+_)[+'']+(''+_)[__]+(''+_)[+_]])[+_+[+'']]+___[+_]+(''+!_)[__]+(''+_)[+'']+(''+_)[+_]+___[+'']+(''+[][(''+!_)[+'']+___[__+_+_]+(''+!_)[_+_]+(''+_)[+'']+(''+_)[__]+(''+_)[+_]])[__]+(''+_)[+'']+(_+[][(''+!_)[+'']+___[__+_+_]+(''+!_)[_+_]+(''+_)[+'']+(''+_)[__]+(''+_)[+_]])[+_+[+'']]+(''+_)[+_]]((''+_)[__]+('!'+[][(''+!_)[+'']+___[__+_+_]+(''+!_)[_+_]+(''+_)[+'']+(''+_)[__]+(''+_)[+_]])[__+[+'']]+([]+!_)[+_]+([]+!_)[_+_]+'(\'\\'+(+_)+(__+__)+(+'')+(''+_)[+_]+___[__+_+_]+___[+_]+(''+_)[+'']+'(\\\'\\'+(+_)+(__+_+_)+(+'')+(''+_)[__]+(''+!_)[_+_]+(''+!_)[_+_]+'\\'+(+_)+(__+_+_)+(__+__+_)+'\\'+(__+_+_)+(__+_)+'\\'+(__+_)+(+'')+'\\'+(+_)+(__+__)+(__+__+_)+'\\'+(+_)+(__+_+_)+(__+__+_)+(''+_)[+_]+(''+!_)[_+_]+___[_+_]+'\\\')\')'))()
Perl 80B 文字種14 #:@ACFHMW^emqs
s##qq@RRRRR:RRRRQWRRQRRRq:@^qq@qqemq^mqSSSAHmSqSe:^@^qq@SQ^QWFWFmmm::HmQmSAF@#ee
Ruby 123B 文字種12 %0678<inprt (空白も)
print %%%<<770%666<<707%606<<708%600<<708%600<<777%666<<660%77<<700%668<<786%667<<777%666<<780%666<<708%600<<700%600<<70%60
Bash 773B 文字種15 \t&/12>Pacdklwz|
dc czzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzPczzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzPzzzzzzzzPzPzzzzPczzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzPczzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzPzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzPczzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzPzzzzPczzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzPczzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzPczzzzzzzzzzzP 2>&1 | dc 2>&1 | awk /ll/
Forth 208B 文字種11 \n3459DEIMOT
439 335 MOD EMIT 434 333 MOD EMIT 443 335 MOD EMIT 443 335 MOD EMIT 444 333 MOD EMIT 44 EMIT 333 43 MOD EMIT 453 334 MOD EMIT 444 333 MOD EMIT 449 335 MOD EMIT 443 335 MOD EMIT 433 333 MOD EMIT 43 33 MOD EMIT
まとめ
提出物はここに置いておきました。 readme とかも入ってます。
http://shinh.skr.jp/obf/hello6.zip
70種の文字を使ったようです。
\t\n !\"\#$%&'()+-/0123456789:;<=>@ADEFHIMOPQRSTW[\\]^_acdeiklmnopqrstwz{|}言語セットが違えば7言語とか見えるかもしれませんけど、このセットだとなかなかむつかしいなーという印象でした、が、できても不思議ではないとも思います。
何が楽しいって、どの言語をどういうふうに使うか、ってことですね。ていうか 私の場合比較的よくわかってる Perl, Ruby, Bash あたりに負担がかかってくるわけですが…
あと地味にかけられてる 1000B 制限が微妙に厳しくてですね…
robust_quine.pl
Ruby にできて Perl にできないことは無いという格言があります。
http://d.hatena.ne.jp/ku-ma-me/20140219/p1
$$qq.=q';printf"\$\$qq.=q%c%s%c;;##%c;\n\$\$uu.=q%c%s%c;;##%c;\n\n\$\$ii||=%c\$_;;\$\$\$ii.=\$\$qq;;s#^;.{217}\$#\$\$qq#ee;;#;#^^;\n\$\$nn||=%c\$_;;\$\$\$nn.=\$\$uu;;s#;.{217}\$#\$\$uu#ee;#;",39,$&,39,39,39,$&,39,39,92,92;exit';;##'; $$uu.=q';printf"\$\$qq.=q%c%s%c;;##%c;\n\$\$uu.=q%c%s%c;;##%c;\n\n\$\$ii||=%c\$_;;\$\$\$ii.=\$\$qq;;s#^;.{217}\$#\$\$qq#ee;;#;#^^;\n\$\$nn||=%c\$_;;\$\$\$nn.=\$\$uu;;s#;.{217}\$#\$\$uu#ee;#;",39,$&,39,39,39,$&,39,39,92,92;exit';;##'; $$ii||=\$_;;$$$ii.=$$qq;;s#^;.{217}$#$$qq#ee;;#;#^^; $$nn||=\$_;;$$$nn.=$$uu;;s#;.{217}$#$$uu#ee;#;
まぁ Perl はだいぶラクですな…
mingn
MinGW 的な、ミニマルな GCC 開発環境を NaCl 上で動かしたいなってことで冬休みくらいから遊んでた (gcc のポート自体は一昨年からあったが…) ものをちまちま naclports という NaCl に移植したアプリ集みたいなところにコミットして、なんとなく区切りがついたような気がしたのでデモサイトを作ってみました。
http://commondatastorage.googleapis.com/mingn/index.html
できることは gcc で適当なものをコンパイルしたり、 vim で編集したり ruby と python と nethack が動くくらいです。欠点としては redirect と pipe と sub-shell が無いので使いものにならないことです。 ICFPC 2006 の UMIX とかも動くようにコードを置いておきました。
bootstrap の bash と unzip 以外は HTML5 File System に突っ込んだバイナリを起動してるんで、 Chrome OS でオフライン開発する夢に一歩近付いたかなぁと思ってるんですけど、まだ10歩くらいはある道程なのでしんどい。
まあ TODO は死ぬほどたくさんあるんだけど、死ぬほどたくさんありすぎて、かなり巨大なやる気が来ないと解決されないので…
ARM test environment on Debian
$ cat /etc/apt/sources.list.d/emdebian.list deb http://www.emdebian.org/debian/ sid main
とか置いておいて、
$ sudo apt-get update $ sudo apt-get install g++-4.7-arm-linux-gnueabihf qemu gdb-arm-none-eabi
とかで。 gdb-arm-none-eabi は gdb-multiarch はどうもおかしかったので。
実行は
$ arm-linux-gnueabihf-gcc-4.7 hello.c $ qemu-arm -L /usr/arm-linux-gnueabihf ./a.out
デバッグは
$ qemu-arm -L /usr/arm-linux-gnueabihf -g 1234 ./a.out $ arm-none-eabi-gdb ./a.out (gdb) set sysroot /usr/arm-linux-gnueabihf (gdb) target remote :1234 (gdb) b main (gdb) cont
など。
Ubuntu はデフォルトでももうちょい色々入ってたと思います。
ARM にゅうもん
例のごとく、書かないと覚えられません。
参考文献
日本語命令セット: http://www.ced.is.utsunomiya-u.ac.jp/lecture/2013/aca/ARMjp-vH.pdf
コンパイラのマニュアルらしいけど概要的に便利なやつ: http://infocenter.arm.com/help/topic/com.arm.doc.dui0056d/DUI0056.pdf
registers
r0 から r3 は caller save なレジスタで引数に使う。 r4-r11 はたぶん普通は callee save 。
r12 は別名 ip 。 r12 は ARM Thumb の切り替え時に必要なら使うらしい…が、ぱっと見短い R_ARM_CALL なら使わない気もする。まぁいずれにせよ caller save
r13 は sp 。 r14 は lr で bl か blx 時に戻りアドレスが勝手に入る。 r15 は pc 。いじると jmp になる。
d0-d31 倍精度浮動小数点レジスタ。 s0-s31 までは単精度浮動小数点レジスタで、 d0 は s0:s1 。 VFP とか言う。 SIMD 拡張が NEON で、 q0 が d0:d1 みたいな感じで 128 bit の SIMD レジスタになる。
あと NaCl は r9 が thread pointer で触れない
calling convention
r0 から r3 が引数と戻り値。レジスタ一つに入らない struct とかは stack 使う。戻り値は double と long long で r0 r1 使って、 128bit の値は r0-r3 使う。 64bit struct とかは stack 、ぽい。入り切らなくなったら stack 使うけど、これで long long が分割されたりもする。
浮動小数まわりの ABI は GCC だと三種類あって、 -mfloat-abi=soft, -mfloat-abi=softfp (android), -mfloat-abi=hard (chrome) 。 soft だと VFP レジスタをいっさい使わなくて、 softfp は使うけど引数渡しは汎用レジスタ使う、 hard は引数渡しにも VFP レジスタ (NaCl だと d0-d7) 使う。
レジスタ渡しする calling convention は可変長引数が面白いことになりがちですが、 ARM も面白くて、浮動小数点レジスタを絶対使わなくなる。つまり正しい宣言が無いと呼び出しが混乱して、
int main() { va_func(42.0); extern void va_func(float f, ...); va_func(42.0); } void va_func(float f, ...) { printf("va_func: %f\n", f); }
とかだと一個目の結果がおかしくなる。浮動小数の ABI は混ぜるな危険もいいところなんで、 .o の .ARM.attributes って section に ABI 情報が入ってる。
ARM Thumb interwork
Thumb モードは命令エンコードが ARM モードより短い変わりに、少し命令がリッチじゃないモード、らしい。一般的には ARM モードが速いとされてる、らしい。基本的に decoder の state を変えるだけなので変更は一瞬らしい(つっても pipeline は乱れる?)。
Thumb モードの関数ポインタは奇数。 ARM モードは偶数。レジスタ指定のブランチ命令 (bx と blx) はレジスタに入ってる値が偶数なら ARM に、奇数なら Thumb モードに切り変える。 24bit 相対のブランチ命令 (b, bx, bl と blx) は x がついてるやつは ARM Thumb 逆転。 relocation が R_ARM_CALL になってると、飛び先のモードに応じて、 link time に bl と blx を変えたりするっぽい。
今 ARM Thumb モードどっちか、ってのは cpsr ってレジスタの 0x20 の bit に入ってるぽい。 gdb とかはたぶんこれ見て状態を確認してるんだと思われる。ちなみに pc は Thumb でも常に偶数ぽい。
リンカとか objdump とかが適切に ARM Thumb 出せるのは、たぶんシンボルの値が奇数なら Thumb 、とかやってるのかなぁと思います…たぶん。 objdump -b binary とかだとシンボル情報無いんで、 Thumb のコードを見たい、って時は -Mforce-thumb とかつければ良いぽい。
instructions
よく言われる特徴的なのは ARM mode ではたいていの命令は condition bit を見て条件実行する 4bit が先頭についてること。常時実行が 0b1110 なので、 ARM mode の命令はだいたい 0xe で始まってる。ただ、スペースが明らかに足りてない、 24bit 即値ブランチとかは条件無し。
あとは RISC なんで即値代入が2命令にわかれてるのが特徴的か。やたらと movw movt ってのを見る感じ。 0x23456789 とかを代入すると、
10: e3062789 movw r2, #26505 ; 0x6789 14: e3422345 movt r2, #9029 ; 0x2345
とかになる。即値が二箇所に飛び散るからエンコードされたものが読みにくい…
あとは push/pop で任意個の複数レジスタを好き勝手 push/pop できるのが面白いですかね。関数の入口出口でまとめて退避できて便利。レジスタ 16 本なんで 16bit でどれを退避…みたいな感じになる。
objdump とか gas 読む時は基本 destination が左で、まぁ読みやすい。 str だけ destination が右になるけど。
NaCl のメモリレイアウトについて
前から図でも書こうかなぁと思ってたのですが、機会があったのでとりあえずスプレッドシートを作ってみました。
ひとつ前で書いた通り、 NaCl では text は最初の 256MB に位置していて、 data はその後の 768MB を使うことになっています (x86-64 では data は 3840MB)。普通の linux バイナリでは text の直後に data が配置されるようになってるため、大雑把に言うと
main binary の text main binary の data 隙間 libc.so の text libc.so の data 隙間 ...
というように配置されるわけですけど、 NaCl (glibc) では
main binary の text libc.so の text ... 隙間 main binary の data libc.so の data ...
というように配置されます。こういうことを実現するために、 NaCl では ELF binary を作った時点で text と data の距離が 256MB 離れているバイナリが生成されます。例えば適当に作った hello は、通常の linux バイナリでは
$ readelf -l a.out | grep LOAD LOAD 0x000000 0x08048000 0x08048000 0x0059c 0x0059c R E 0x1000 LOAD 0x00059c 0x0804959c 0x0804959c 0x00118 0x0011c RW 0x1000
という感じで、 PT_LOAD が連続して配置されているんですけど、 NaCl バイナリでは
$ readelf -l a.out | grep LOAD LOAD 0x010000 0x01000000 0x01000000 0x10000 0x10000 R E 0x10000 LOAD 0x020000 0x11000000 0x11000000 0x00230 0x00230 R 0x10000 LOAD 0x020230 0x11010230 0x11010230 0x0010c 0x0010c RW 0x10000 LOAD 0x030000 0x11020000 0x11020000 0x00000 0x00020 RW 0x10000
のように、最初の PT_LOAD (text) とその次 (rodata) の間に 256MB==0x10000000 bytes の隙間があります。このため、一つ前で mmap された場所によって、 text が入っても data が入らない場合や、 data が入っても text が入らない場合があるので、 text と data の大きい方のサイズ分だけ両方の領域が消費されます。例えば一つ目のバイナリの text が 1MB で data が 2MB の場合、次のバイナリは text も data も 2MB 進んだところに配置されるし、逆に text が 2MB で data が 1MB の場合も同様です。
このため、空間効率の良い NaCl バイナリは text と data のサイズが近いバイナリってことになるんで、データだけが入ってる so とかは text がムダになるのであまり作りたくない感じになっています。
現状、 so は dlclose されても munmap はするけど消費された領域は再利用しない実装になってるため (直す予定はあるみたいですけど) dlopen と dlclose を繰り返すと領域を使い果たします。そのあたりのコードは https://chromium.googlesource.com/native_client/nacl-glibc/+/master/sysdeps/nacl/nacl_dyncode_alloc.c にあります。余談ですけどこのコードはなんでこんなややこしい書き方するんだろ、ってコードになってて読みにくいです…
また、固定で置き場所が決まっているバイナリなどがいくつかあります
- 0x10000 から 0x20000 は verify されない、 service runtime が NaCl syscall の entry point への jmp 命令を置く空間になってます。直接 service runtime のコードへの jmp は verifier が許さないので、 Pepper API を使う場合などは、ここを経由して NaCl syscall することになっています
- 0x20000 から 0x1000000 までの空間はダイナミックローダ (runnable-ld.so) の text が置かれます。同様に 0x10020000 から 0x11000000 は runnable-ld.so の data が配置されます。残った空間は nacl_dyncode_create や mmap で使うことはできると思いますけど。
- 0x1000000 から 0x0fa00000 までの空間は、 so が順次置かれていきます。 nacl_dyncode_create で JIT したコードを置きたい場合は、後続の dlopen で使う領域と競合されないように、 0x0fa00000 より少し小さいアドレスを適当に使うと良いみたいです。まぁこのへんは service runtime 側でちゃんと allocation して欲しい感じで、まぁ直す予定はあるみたいです…
- 0x0fa00000 から先は IRT が使います。 IRT は text と data の gap が 256MB ではなくて、 untrusted code が使える data 領域の最後の部分、具体的には 0x3ef00000 から先が使われるようになってるみたいです。
- so が配置された後、 IRT の前の data 領域は、 NaCl syscall の mmap が後ろから順に適当に使っていくみたいです。たくさん allocation すると so のための領域とぶつかるので、 dlopen やら mmap が失敗しはじめるはずです。
- 今回調べてて気付いたのですが、 IRT の data 領域の後の領域は main thread の stack になるみたいです。ここに stack guard 無いのは、あった方がいい気しかしないです…こわい
というようなことをまとめたのが最初の spread sheet になっています。
newlib や static link した glibc のバイナリは so が無いのでシンプルで、 newlib の場合 runnable-ld.so が置かれる場所に、 static link した glibc のバイナリは dynamic link された場合の main binary の場所に main binary が置かれます。
残念ながら、これも NaCl のメモリレイアウトについての世界一詳しい記述だと思いますね…
