兼雑記

なにやら先生と紛らわしいそうで生まれてきてすいません。あばうと
<< 2014/04 >>
1 2 3 4 5
6 7 8 9 10 11 12
13 14 15 16 17 18 19
20 21 22 23 24 25 26
27 28 29 30

| サイト本体 | 昔の更新履歴兼雑記 | タイトル一覧 |

分類は アーカイブ任せにした方がいいのかも。


 

2014-03-18

hello, world * 6 03:16

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 制限が微妙に厳しくてですね…

あと 03:47

これのおかげで BashHello broken keyboard の記録が更新されました。

http://golf.shinh.org/p.rb?Hello+broken+keyboard#Bash

2014-02-20

robust_quine.pl 03:30

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 はだいぶラクですな…

2014-02-11

mingn 02:28

MinGW 的な、ミニマルGCC 開発環境を NaCl 上で動かしたいなってことで冬休みくらいから遊んでた (gcc のポート自体は一昨年からあったが…) ものをちまちま naclports という NaCl に移植したアプリ集みたいなところにコミットして、なんとなく区切りがついたような気がしたのでデモサイトを作ってみました。

http://commondatastorage.googleapis.com/mingn/index.html

できることは gcc で適当なものをコンパイルしたり、 vim編集したり rubypythonnethack が動くくらいです。欠点としては redirect と pipe と sub-shell が無いので使いものにならないことです。 ICFPC 2006 の UMIX とかも動くようにコードを置いておきました。

bootstrap の bashunzip 以外は HTML5 File System に突っ込んだバイナリを起動してるんで、 Chrome OSオフライン開発する夢に一歩近付いたかなぁと思ってるんですけど、まだ10歩くらいはある道程なのでしんどい

まあ TODO死ぬほどたくさんあるんだけど、死ぬほどたくさんありすぎて、かなり巨大なやる気が来ないと解決されないので…

nn 2014/02/11 09:52 >redirect と pipe と sub-shell が無い
NaCLについては詳しくありませんが、カーネル機能の諸々が無いのであれば、
カーネル機能をユーザーランドで動かすUML(User-mode Linux)を移植するのはどうでしょうか。

nn 2014/02/11 11:17 上記は撤回します。調べてみたら、残念ながら、UMLはsocketpairやpollなどを使ってるので、その目的には使えないようでした。

shinichiro_hshinichiro_h 2014/02/11 13:58 ああ根っこから持ってきちゃうってのは面白いアイデアだと思います。 UML あまり詳しくないんですけど、仕組みぱっと見た感じですと、 ptrace 使ってるのが一番致命的ですかね… socketpair は二つのプロセス専用ならある程度 emulation できると思われ、 poll が無いのは単にバグって言った方が良い気がしているのでいずれ足されると思っています。

2014-01-13

ARM にゅうもん 01:29

例のごとく、書かないと覚えられません。

参考文献

日本語命令セット: 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 が右になるけど。

ARM test environment on Debian 02:36

$ 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 はデフォルトでももうちょい色々入ってたと思います。

2014-01-05

NaCl のメモリレイアウトについて 23:54

から図でも書こうかなぁと思ってたのですが、機会があったのでとりあえずスプレッドシートを作ってみました。

https://docs.google.com/spreadsheet/ccc?key=0AolcvzoWgN21dG5PVldnM0VJUzByU2hqcXFQaGVVdWc&usp=drive_web

ひとつ前で書いた通り、 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 のメモリレイアウトについての世界一詳しい記述だと思いますね…

 
1970 | 01 |
2003 | 12 |
2004 | 01 | 02 | 03 | 04 | 05 | 06 | 07 | 08 | 09 | 10 | 11 | 12 |
2005 | 01 | 02 | 03 | 04 | 05 | 06 | 07 | 08 | 09 | 10 | 11 | 12 |
2006 | 01 | 02 | 03 | 04 | 05 | 06 | 07 | 08 | 09 | 10 | 11 | 12 |
2007 | 01 | 02 | 03 | 04 | 05 | 06 | 07 | 08 | 09 | 10 | 11 | 12 |
2008 | 01 | 02 | 03 | 04 | 05 | 06 | 07 | 08 | 09 | 10 | 11 | 12 |
2009 | 01 | 02 | 03 | 04 | 05 | 06 | 07 | 08 | 09 | 10 | 11 | 12 |
2010 | 01 | 02 | 03 | 04 | 05 | 06 | 07 | 08 | 10 | 12 |
2011 | 01 | 02 | 03 | 04 | 06 | 08 | 09 | 10 | 11 | 12 |
2012 | 01 | 02 | 03 | 04 | 07 | 08 | 09 | 10 | 12 |
2013 | 01 | 02 | 03 | 04 | 05 | 06 | 07 | 08 | 09 | 11 | 12 |
2014 | 01 | 02 | 03 |
(1999370 since 04.04.21)
なにかあれば下記メールアドレスへ。
shinichiro.hamaji _at_ gmail.com
shinichiro.h